3
$\begingroup$

Problem. I have a solid torus and a solid cone in $\mathbb R^3$ and need an efficient algorithm that determines if they intersect or not.

  1. The center of the torus is at a given position $\mathbf p \in \mathbb R^3$ and its rotation axis is parallel to the global y axis.

  2. The cone is oriented arbitrarily with its apex being the origin $(0, 0, 0)$.

Comments.

  1. I do not need the point or curve of intersection (if any), I just have to know if they intersect or not.

  2. The shapes are considered solid bodies. For example, if the cone completely contains the torus, the algorithm should report an intersection.

  3. I have no restrictions regarding the representation of the shapes: implicit or explicit - whichever makes the problem easier.

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ Possible simplification: the torus consists of all points at distance at most $r$ from some circle. So an equivalent question is: Is the point in the cone that's nearest the circle at distance at most $r$ from it? $\endgroup$
    – Noam D. Elkies
    Aug 27, 2018 at 19:04

2 Answers 2

Reset to default
3
$\begingroup$

The following paper shows how to compute the minimum distance between a canal surface, e.g., a torus, and a "simple surface," e.g, a cone. She reduces the computation to finding the roots of a polynomial equation in one variable.

Kim, Ku-Jin. "Minimum distance between a canal surface and a simple surface." Computer-Aided Design 35, no. 10 (2003): 871-879. (Elsevier link.)
         

Following Noam Elkies observation, let $C$ be the circle at the core of the torus $T$. First determine if the cone $K$ intersects $C$, in which case $K$ intersects $T$. If $K$ does not intersect $C$, then compute the minimum distance between $K$ and a vanishingly thin torus surrounding $C$. Then use Noam's idea to determine if $K$ intersects $T$.

I believe the inclusions $K \supset T$ and $T \supset K$ can again be settled using the minimum distance calculation.

Improve this answer
$\endgroup$
4
  • $\begingroup$ To extend the idea, consider the minimum distance between the cone axis and the circle. If this distance is d and the torus radius is r, then a ratio between d-r and the distance from the nearest point to the origin of the line should wrap up the calculation. Gerhard "Don't Even Need Conformal Map" Paseman, 2018.08.27. $\endgroup$
    – Gerhard Paseman
    Aug 27, 2018 at 23:46
  • $\begingroup$ @GerhardPaseman: No doubt I am misunderstanding your comment, but the distance $d$ is achieved by a segment perpendicular to the cone axis (or incident to the cone apex), which does not directly take into account where is the boundary of the cone, which depends on the cone apex angle. $\endgroup$
    – Joseph O'Rourke
    Aug 28, 2018 at 12:24
  • $\begingroup$ I may be misunderstanding the situation. I was thinking that it was enough to restrict to the plane containing the cone origin and the segment which is the nearest distance between cone axis and the circle which is the "torus axis", and use similar triangles to resolve the question of intersection. However, the relevant torus cross section may not be circular, and the common intersection may be away from the segment. Gerhard "More Is Needed, I Fear" Paseman, 3018.08.28. $\endgroup$
    – Gerhard Paseman
    Aug 28, 2018 at 14:39
  • 1
    $\begingroup$ Indeed, just from considering positions of two cones of different shapes, I now see the problem is more complex, and that the minimal distance segment between axes is insufficient. I think a computational speed up is achievable by considering the circle "axis of the torus" and the cone axis first, but there remains some subtleties to consider. Gerhard "Oversimplifying Does Not Always Work" Paseman, 2018.08.28. $\endgroup$
    – Gerhard Paseman
    Aug 28, 2018 at 17:35
0
$\begingroup$

In my humble opinion, the only sensible method of solving this problem is to find a point $P$ on the torus (as a surface) such that the angle between $OP$ and the axis of the cone is the smallest. The problem can be simplified further once we take into account that a torus is a union of circles, and finding such a point $P$ on a circle is an easy exercise. (Better to chose small circles, because in this case if the axis goes through the circle, then we are done.)

By the way, if the axis goes through the hole of the torus, then the minimum is not necessarily unique.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The Kim paper I cited finds points on the two surfaces such that the segment connecting them is perpendicular to both surfaces. $\endgroup$
    – Joseph O'Rourke
    Aug 28, 2018 at 15:52
  • $\begingroup$ Do you know of any papers which cover the case that the objects are two solids of revolution, with "not much concavity"? I would hope the torus has not much concavity and would be part of the allowed list of objects. Gerhard "Axes Should Play A Role" Paseman, 2018.08.28. $\endgroup$
    – Gerhard Paseman
    Aug 28, 2018 at 16:00
  • $\begingroup$ @GerhardPaseman: Yes. This paper computes the min distance between two surfaces of revolution (although you would not know that from the title). Seong, Joon-Kyung, Myung-Soo Kim, and Kokichi Sugihara. "The Minkowski sum of two simple surfaces generated by slope-monotone closed curves." In Geometric Modeling and Processing, pp. 33-42. IEEE, 2002. They match normals using the Gauss maps. $\endgroup$
    – Joseph O'Rourke
    Aug 28, 2018 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.