Finding points close to conic surface in R3

Question

I have a conic surface in R3 defined by cone apex c=(cx,cy,cz), cone axis a=(ax, ay, az), half-apex angle theta and a set of points pi=(px, py, pz).

I want to know which of the points pi lie on the conic surface (=are reasonably close).

So far I have been dealing with this using the cosine of vectors:

• I constructed vectors vi from cone apex to points pi
• I took dot product to compute the angle between vectors vi and cone axis a.
• I compared this angle to the half-apex angle theta and if their difference was smaller than some threshold, I said the points intersect.

This strategy seems to be creating widening cones and does not work well in my application.

I was wondering if there is another way how to find the intersecting points. For example by solving some conic inequation like "ax(px-cx)...+az(pz-cz)<residual" and then looking at the points with some small residual error. But I was not able to find any resources on this in 3D.

Side info: I have a huge number of points pi and I need an algorithm that is fast and compatible with matrix form/GPU computation.

Answer 1

Let $\vec{a}$ be the unit vector directing the axis $\mathfrak{A}$ of the cone (the set of $\lambda \vec{a}, \ \lambda \in \mathbb{R_+}$).

Let $Q_i$ be the orthogonal projection of $P_i$ onto axis $\mathfrak{A}$. Let

$$\pi_i:=CP_i.\vec{a}$$

(dot product). It is well known (due to the fact that $\vec{a}$ has unit norm), that

$$\vec{CQ_i}=\pi_i \vec{a}.$$

Therefore the norm of the difference

$$\delta_i:=\| \vec{P_iQ_i}\|=\| \vec{CP_i}-\vec{CQ_i} \|=\| \vec{CP_i}-(\vec{CP_i}.\vec{a})\vec{a}\|$$

measures the distance from $P_i$ to axis $\mathfrak{A}$.

Ideally, if $P_i$ is on the cone, $CQ_iP_i$ is a right triangle in which we have :

$$\delta_i=\pi_i\tan \theta \tag{1}$$

But in general, we only have :

$$\delta_i \approx \pi_i\tan \theta \tag{2}$$

As a consequence, the discrepancy measure I advise you to take is : $$\Delta_i := |\pi_i\tan \theta - \delta_i|$$

where $\Delta_i$ has to be within a certain interval $(-\varepsilon, \varepsilon)$ for point $P_i$ to be selected.

(other discrepancy measures could have been proposed out of (2), but some of them would have given the pitfall you have observed in your method).

Answer 2

Usually, conical surface means something like this:

$$ x^2 + y^2 = r^2\left(\frac{z}{h}\right)^2 \quad \Rightarrow \quad x^2 + y^2 = z^2\tan^2\alpha \quad \Rightarrow \quad \left(x^2 + y^2 + z^2\right)\cos^2\alpha = z^2. $$

So, if master cone is of the type:

$$ \boxed{ \left|z^2 - \left(x^2 + y^2 + z^2\right)\cos^2\alpha\right| \le 10^{-n} \quad \text{and} \quad \beta \le z \le \gamma \;} $$

the slave cone is obtained through a geometric transformation of the type:

$$ \begin{bmatrix} x \\ y \\ z \\ \end{bmatrix} \mapsto \mathbf{R}(\theta,\mathbf{\hat{w}}) \begin{bmatrix} x-x_c \\ y-y_c \\ z-z_c \\ \end{bmatrix}. $$

---

If $\mathbf{\hat{u}}$, $\mathbf{\hat{v}}$ define a plane of normal $\mathbf{\hat{w}} \equiv \frac{\mathbf{\hat{u}} \times \mathbf{\hat{v}}}{||\mathbf{\hat{u}} \times \mathbf{\hat{v}}||}$, the counterclockwise rotation matrix around $\mathbf{\hat{w}}$ is:

$$ \mathbf{R}(\theta,\mathbf{\hat{w}}) = \mathbf{I} + (\sin\theta)\mathbf{W} + (1-\cos\theta)\mathbf{W}\cdot\mathbf{W} $$

known as Rodrigues' Rotation Formula, where we define the matrices:

$$ \mathbf{I} \equiv \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}, \quad \quad \quad \mathbf{W} \equiv \begin{bmatrix} 0 & -w_3 & w_2 \\ w_3 & 0 & -w_1 \\ -w_2 & w_1 & 0 \\ \end{bmatrix}. $$

Therefore, the matrix that rotates $\mathbf{\hat{u}}$ to the direction of $\mathbf{\hat{v}}$ is nothing but $\mathbf{R}(\arccos(\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}),\mathbf{\hat{w}})$.

---

In this case, it's sufficient to set $\mathbf{\hat{u}} \equiv \frac{(a,\,b,\,c)}{\sqrt{a^2 + b^2 + c^2}}$ and $\mathbf{\hat{v}} \equiv (0,0,1)$ to obtain:

$$ \small \boxed{ \left|\left(\frac{a(x - x_c) + b(y - y_c) + c(z - z_c)}{\sqrt{a^2 + b^2 + c^2}}\right)^2 - \left((x - x_c)^2 + (y - y_c)^2 + (z - z_c)^2\right)\cos^2\alpha\right| \le 10^{-n} \, \\ \color{white}{.} \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \text{and} \\ \color{white}{.} \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad \beta \le \frac{a(x - x_c) + b(y - y_c) + c(z - z_c)}{\sqrt{a^2 + b^2 + c^2}} \le \gamma} $$

where in the case of infinite cone the last two inequalities are ignored.