Jump to content
  • Advertisement
Sign in to follow this  
Quak

intesection: ray - parallelogram

This topic is 4325 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, my parallelogram is defined as: P = E + alpha*v0 + betha*v1 where E is the midpoint of parallelogram, v0 and v1 are the basis vectors with the magnitude of the edges of the parallelogram. As E is the midpoint and not a corner point the coefficients alpha and betha must be in the range from -0.5 to 0.5. my ray is defined as: P = O + t*d where O is the origin and d the direction vector. Assuming I already have the correct t value at which the parallelogram is intersected by the ray I now want to find the alpha and betha coefficients, thus I plug the first equation into the second and get: O + t*d = E + alpha*v0 + betha*v1 => O - E + t*d = aplha*v0 + betha*v1 substituting P = O - E + t*d => P = aplha*v0 + betha*v1 this gives me a linear system of equations to solve: v0x v1x | Px v0y v1y | Py v0z v1z | Pz As v0 ans v1 are constants my idea is to solve this system in advance: subtracting the second row from the third and the first from the second I get: v0x v1x | Px 0 v1y-(v0y*v1x)/v0x | Py-(v0y*Px)/v0x 0 v1z-(v0z*v1y)/v0y | Pz-(v0z*Py)/v0y subtracting the third from the first: v0x 0 | Px + (Pz-(v0z*Py)/v0y) * (-v1x*v0y)/(v1z*v0y-v0z*v1y) 0 v1y-(v0y*v1x)/v0x | Py-(v0y*Px)/v0x 0 v1z-(v0z*v1y)/v0y | Pz-(v0z*Py)/v0y now I can compute alpha: alpha = [Px + (Pz-(v0z*Py)/v0y) * (-v1x*v0y)/(v1z*v0y-v0z*v1y)]/v0x substituting K0 = 1/v0x and K1 = (-v1x*v0y)/(v1z*v0y-v0z*v1y)/v0x: alpha = Px*K0 + Pz*K1 - Py*v0z/v0y*K1 substituting K2 = -v0z/v0y*K1: alpha = Px*K0 + Pz*K1 + Py*K2 and by adding row 2 and 3 I compute betha: 2*betha = (Py-(v0y*Px)/v0x + Pz-(v0z*Py)/v0y) / (v1y-(v0y*v1x)/v0x + v1z-(v0z*v1y)/v0y) substituting K3 = 1/(v1y-(v0y*v1x)/v0x + v1z-(v0z*v1y)/v0y) 2*betha = Py*K3 + Pz*K3 - Px*v0y/v0x*K3 - Py*v0z/v0y*K3 2*betha = Py*(K3-K3*v0z/v0y) + Pz*K3 - Px*v0y/v0x*K3 substituting K4 = (K3-K3*v0z/v0y) and K5 = -v0y/v0x*K3: 2*betha = Py*K4 + Pz*K3 + Px*K5 I can precomupte the K values and store them with the parallelogram. However it doesn't work correctly so I wonder if the math is correct. Is this a valid way to solve the linear system in advance ? thanks, quak [Edited by - Quak on October 14, 2006 8:23:28 AM]

Share this post


Link to post
Share on other sites
Advertisement
Looks a bit complicated to me.

Bear in mind that a parallelogram is simply a skewed rectangle, which is a stretched square. A consequence of this is that there exists a unique affine-linear transformation that turns any parallelogram into the unit square. It is not too difficult to determine this transformation from your E, v0, v1. If you apply this same transformation to the ray, you're left with a simple ray-unit-square test, which is, more or less, trivial.

Makes sense?

Regards
Admiral

Share this post


Link to post
Share on other sites
Yes makes sense, but this way the computation of alpha and betha is more costly.
The difference may not seem much, but as the intersection test is performed at least once per ray in a raytracer it is really time critical.
If the "K-method" worked only two dot products would be necessary to compute the coefficients.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!