CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "torus-ray intersection"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #572
Reading Topic #572
alan
guest
May-06-06, 06:00 AM (EST)
 
"torus-ray intersection"
 
   I'm looking for information about finding the intersection point between a torus and a ray. Starting off its easy enough, substitute a ray equation, x(t), y(t), z(t) into an implicit torus equation. From there a quartic polynomial in t can be found. I know this can, and probably should, be solved with a numerical algorithm, but I'm curious about an exact solution. Does anyone know of a way to solve this equation exactly, without resorting to the general quartic solution? I've read that its possible to factor the resulting equation into a product of quadratic terms, but I can't find further information, and I can't figure it out myself. Any ideas? Thanks.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
May-06-06, 08:46 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
1. "RE: torus-ray intersection"
In response to message #0
 
   Hi Alan,

For geometric reasons, I don't think you can factor the quartic. If it did factor, then the surface would be defined by the product of two polynomials, say P(x,y,z)·Q(x,y,z) = 0. But then the equation would be satisfied if either P or Q were to be zero separately, and hence this function would define the set union of two surfaces P=0 and Q=0. This would certainly not look like a torus, but like two surfaces cutting through each other.

The good news is that there is something else you can do, which I think will work. I assume you are situating the torus centered at the origin, and that your ray comes from the origin. In that case, because of the symmetry, if (x,y,z) is a point on the torus, so are (+/-x,+/-y,+/-z). This means that the function describing the torus must be and EVEN function of x, y, and z. Since it is a polynomial, it must therefore contain only even powers of these variables, and so you can redefine s=x^2, t=y^2, and u=z^2. If your ray was originally (x,y,z) = t·(a,b,c), it now must become (s,t,u) = t·(a^2,b^2,c^2).

This will reduce the torus equation to a quadratic, and you can then substitute the ray relationships and solve as usual to find 2 solutions in the variables s, t, and u. Unfortunately these will expand to 16 points of intesection, corresponding to all the possible +/- sign patterns on the x, y, and z variables. However, simply choose the two with the same sign pattern as your ray and you are done.

Hope this helps!

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alan
guest
May-06-06, 10:39 PM (EST)
 
2. "RE: torus-ray intersection"
In response to message #1
 
   What you said about not being able to factor the quartic makes sense for the implicit torus equation itself, but when you try to solve that equation simultaneously with a ray equation, does that logic still apply? Also, I'm actually trying to find the intersection with an arbitrary ray; I want to write a raytracing program, and I'm just curious as to whether its possible to find the intersection analytically instead of needing to rely on an iterative method.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
May-07-06, 10:14 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
3. "RE: torus-ray intersection"
In response to message #2
 
   Hi Alan,

I did not realize you had a more general problem in mind. The word "ray" made me think you had geometric rays from the origin in mind, but clearly you meant "ray" in the sense of "light ray."

This is more complicated, of course. I do not think that my argument about the non-factorability of the quartic carries over directly to the equation you get after substituting the ray equation into the torus equation. However, it'seems to me that there is still an argument that shows that the resulting equation is not factorable:

Logically, if the original torus equation were factorable, then after substituting the ray equation, the result must still be factorable (just factor first and then substitute, QED), but the reverse will hardly ever be true. In order for the equation after substitution to be factorable, while the equation before substitution was not, requires that the coefficients have certain exact values that permit the equation to factor with no remainder. Moving the ray infinitesimally should produce infinitesimal changes in the coefficients which should in general make the remainder nonzero. So I would expect the equation after substitution would only be factorable for certain specific rays, and that these rays would be the exception, rather than the rule.

Now this is not an air-tight argument, because it MAY be true (I haven't checked) that the structure of the torus equation somehow magically makes these changes cancel out, in which case the equation would factor. However, I don't see any way this could happen and it seems extremely unlikely on the face of it.

My trick for reducing the order to quadratic will also not work for a general ray, since there would no longer be a symmetry to the intersection points, so the polynomial describing the intersection could not be even.

I think this means that it's either the quartic formula or iteration, sorry to say. Perhaps there are tricks that I haven't thought of?

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK