







CTK Exchange
alan
guest

May0606, 06:00 AM (EST) 

"torusray 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 
Printerfriendly page 
Reply 
Reply With Quote  Top 


mr_homm
Member since May2205

May0606, 08:46 PM (EST) 

1. "RE: torusray 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 
Printerfriendly page 
Reply 
Reply With Quote  Top 



alan
guest

May0606, 10:39 PM (EST) 

2. "RE: torusray 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 
Printerfriendly page 
Reply 
Reply With Quote  Top 




mr_homm
Member since May2205

May0706, 10:14 PM (EST) 

3. "RE: torusray 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 nonfactorability 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 airtight 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 
Printerfriendly page 
Reply 
Reply With Quote  Top 



You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Front page
Contents
Copyright © 19962018 Alexander Bogomolny

