# Annuloid (Torus)-line intersection

I need calculate ray (line) intersection with torus for my ray-tracing program (I know, its to graphics, but i need math behind it).

I can solve equation of order $x^4$, but thats too way slow (Cardano's method). So is there better way, how to calculate this ?

My torus has center $[0,0,0]$ and $R$, $r$ diameters Line (Ray) is point and its direction vector

Thanks

-
Is applying an explicit formula for the solutions of a 4th-degree polynomial too slow, or are you depressing the polynomial to solve it? Here is an explicit formula for the solutions of a general 4th-degree polynomial. –  Isaac Oct 25 '10 at 17:54
Cross-posted to MO: mathoverflow.net/questions/43552/… –  Joseph O'Rourke Oct 25 '10 at 20:09

## 1 Answer

What kind of speed are you looking for? In general, smart interval-based solvers work well for this sort of thing: the core idea is that by using interval arithmetic you can bound the values of the 'potential function' (the quartic polynomial whose roots you're trying to find) within any given interval, and then fast-reject if those bounds don't contain zero - that is, if you can confirm that the function is always-positive or always-negative on the interval. Find starting values of tmin and tmax by intersecting your ray with the bounding box of the torus, use the interval arithmetic mentioned above to determine whether it's possible for an intersection to appear within that range, and then use binary subdivision (always exploring the 'earlier' - closer to the camera - branch of the subdivision first) to narrow in on the first zero to whatever accuracy is desired. In practice this isn't much slower than explicitly solving the quartic, and it tends to be more robust, particularly around tangent points/double zeroes.

One question I think it's worth asking, though: why are you trying to explicitly handle ray-torus intersection? Tori don't, in general, make very good primitives for composing a scene; they're too geometric and not particularly organic enough. IMHO you're much better off going the pile-of-triangles route and giving yourself more flexibility, rather than tying yourself too closely to complicated geometric primitives.

-
I have been told, that i must use anuloids for ray-tracing :/ (some test scene for performance measuring). Solving quadric is good, but maybe there is faster solution, that came out from analytic geometry and cuts of anuloid vs. planes.. so I can get intersection point –  Johnatan Oct 25 '10 at 18:37
Well, you're solving quartics, not quadrics (AFAIK, 'quadric' is usually a synonym for 'quadratic', i.e. degree-2); unfortunately, while I haven't checked the 'moduli space', I think that you can get any quartic as the equation for some ray-torus intersection test, so I don't think there's much chance of a specialized solution (to put it into CS terms, solving the quartic is reducible to doing ray-torus intersections; if you can do the latter, you can do the former). –  Steven Stadnicki Oct 25 '10 at 20:00
Well I thought about solution with used of analitic geometry... some transformations. But my solution "crashed" on ray translation on "circle"... eg. I need to translate points on line from circle sector to circle diameter, but same point must lie still on circle. perry.cz/files/pic.png (black need to be red and green to blue)... I need transformation equation for this... only translation in XY doesn´t work, scale is unusable either. If I solve this, I can solve ray-torus without quartics. –  Johnatan Oct 25 '10 at 20:27
I'm afraid that's impossible - there's no linear transformation that takes a circle to itself and takes a chord to the diameter. In fact, the only linear transformations that take a circle to itself are the rotations about its center. –  Steven Stadnicki Oct 25 '10 at 21:48
Since toric sections are quartic curves in general, there's really no escaping the solution of a degree four algebraic equation except for very special configurations. In any event, I second Steven's suggestion to just use something triangulated for your tests. –  Guess who it is. Oct 25 '10 at 23:59