Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi,

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 ?

Thanks

share|improve this question
2  
math.stackexchange.com is probably a better fit for your question. If you do not provide details about how you are representing the torus, it is impossible to answer your question. –  Mariano Suárez-Alvarez Oct 25 '10 at 17:38
    
I have Center [0,0,0] and R, r diameters Line (Ray) is represented with point and its direction vector –  Johnatan Oct 25 '10 at 17:45
    
Cross-posted to MSE: math.stackexchange.com/questions/7829/… –  Joseph O'Rourke Oct 25 '10 at 20:08
    
I removed the intersection theory tag since in mathematics it has a specific meaning. I added computing as a trade off. –  Benoît Kloeckner Mar 1 '11 at 18:18
add comment

2 Answers 2

If you can't avoid solving 4th degree equations, don't use complicated solutions in terms of radicals. Computing radicals is not really any more efficient than computing roots of general polynomials, so this only serves to make the problem more complicated (ignoring other problems such as casus irreducibilis). Instead, apply a suitable root-finding algorithm on the original polynomial.

share|improve this answer
add comment

It seems the method developed by J.J. Van Wijk, and described in his paper, "Ray tracing objects defined by sweeping a sphere" (Computers & Graphics, Volume 9, Issue 3, 1985, Pages 283-290) has become the standard approach. The main idea is to avoid the exact 4th-order computation by performing a pre-test that is only 2nd-order, essentially against the shape produced by sweeping a square rather than a circle around a circle. Then only for the rays that pierce this bounding shape do you solve the 4th-order equations.

I believe with effort you can find downloadable implementations of ray-torus intersection following this method. Code written by Han-Wen Nienhuys is available here (but I didn't check to see if he follows Van Wijk).

share|improve this answer
    
Joseph, it does not seem to be widely taught, a theorem of Abel I believe, that the cubic with three irrational real roots leads to solutions involving (A + B i)^(1/3) + (A - B i)^(1/3) where there is no way to "get out of it" and rewrite as roots of just real numbers. That may be relevant here, hard to say, depends on the reason for using exact symbolic solutions. –  Will Jagy Oct 25 '10 at 21:54
    
@Will: Yes, difficult to say whether that is relevant to this situation. My feeling is that one cannot avoid computing the roots of a 4-th degree equation. The speedups come from only performing that computation as a last resort. –  Joseph O'Rourke Oct 26 '10 at 11:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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