## Line and Torus Intersection,Help!

### Line and Torus Intersection,Help!

I'm working in a ray-tracing project and I would like to
include the torus as a primitive, my problem is that in order to
find the points of intersection between a line and the torus,
one has to know the roots of a 4th degree polinomial, as far as I
know, there's a formula to determine this roots but it's a very *
one, on the other hand one could use a numeric search ( binary
search, etc). Does any one know which method is best?
Thanks

Sergio Duarte

--
---

|   Departamento de Informatica   +----------------------------------+
|   F.C.T. / Universidade Nova de Lisboa                             |
+--------------------------------------------------------------------+

### Line and Torus Intersection,Help!

Quote:

> I'm working in a ray-tracing project and I would like to
>include the torus as a primitive, my problem is that in order to
>find the points of intersection between a line and the torus,
>one has to know the roots of a 4th degree polinomial, as far as I
>know, there's a formula to determine this roots but it's a very *
>one, on the other hand one could use a numeric search ( binary
>search, etc). Does any one know which method is best?
> Thanks

>   Sergio Duarte

I have a Torus in my ray-tracer.  The formula for finding
the roots is about 2 pages long.  It's not really the length of
the formula which is a problem, it's that since it deals with
numbers that are so close to zero and so far from it,
the precision loss will make the borders of the torus messy.
The length of the formula does not really slow down the program
very much because it's easy to first intersect the ray with
a sphere whose radius is the sum of the radii of the torus (a+b).
You will significantly reduce the round-off errors if, just before
you run the ray through the formula, you make it a unit vector and you
bring its starting point (the constant part of the ray) as close as
possible to the torus.  This is easily done by placing it at the
intersection of the ray and the sphere which you had previously wrapped
around the torus.  If you really want to get fancy, you can wrap a
ellipsoid around it for a closer wrap.  The round-off trouble still
caused holes in the torus, though, so I never use the shape.  I haven't
tried the binary search method, but if I were to go that route I would
go right to Newton's Method since it's so much faster.

Let me know if you find a good algorithm.

Hi all,

I wrote a torus-line intersection routine, based on Ferrari's method. When I
render the scene with my torus flat in the x-z plane (i.e. no
transformations applied to it), a part of the far side of the torus is
clipped somehow. It doesn't look like root problems cause I think
normally that results in some pixel dropouts, not an entire region clipped.
I downloaded povray to see how it would render the exact same scene and to
my surprise it had the same problem. I also tried using Sturm sequences and
the same artifacts occured. Has anybody seen this problem before and what's
going on exactly?

Regards,
Arjen van Rhijn