Jump to content
  • Advertisement
Sign in to follow this  
Endar

Woo's method

This topic is 4588 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

Taking a look at Woo's method from here for testing to see if a ray intersects with an AABB.
Quote:
From the six planes, reject those with back-facing normals From the three planes remaining, compute the t distance on the ray-plane test Select the farthest of the three distances Test if that point is inside the box's boundaries
And this is what woo's method consists of:
Quote:
  • Six dot products to check the first step
  • Three point-ray tests
  • A few comparisons for the last step
Now, I know that the dot product can show that two vectors are perpendicular, but remind me again, what does the dot product do in this case that will show that three of the planes are back-facing compared to the side of the aabb that the ray is facing?

Share this post


Link to post
Share on other sites
Advertisement
As you note, the dot product of two perpendicular vectors is zero. If the dot product is not zero, the sign tells you whether the vectors are pointing generally in the same direction, or generally in the opposite direction (very generally). Drawing some pictures will make this clear. In the ray-AABB test you're describing, presumably the planes for which the dot product between the ray direction and the plane normal is positive are discarded, as the ray will intersect the corresponding parallel plane first (unless the ray is facing away from the box, in which case the value of t will be negative and the test will return false).

Share this post


Link to post
Share on other sites
So, if we consider 2d vectors and a unit circle, vectors that are in the same quadrant, going out from the origin, therefore going roughly in the same direction have positive dot products. Vectors that are in opposite quadrants have negative dot products. Right?


[Edited by - Endar on November 26, 2005 3:17:10 AM]

Share this post


Link to post
Share on other sites
The comparison with the "aligned" unit circle and quadrants isn't good. Look here:

Please consider the formula behind dot product:
v1 dot v2 = ||v1|| * ||v2|| * cos<v1,v2>

As you could see, there is the cosine of the angle between the both vectors. The cosine is +1 for 0 degree, and it is axis symmetrical. So the cosine is positive (and hence the entire dot product) as long as the angle between the two vectors is less than 90 degree. Due to the symmetry, if fixing v1, v2 could be in the range of (+90,-90) degree around v1! That makes a total of 180 degree, and hence the dot product is positive if v2 is in the same half sphere (or half circle in 2D) where v1 defines the one pole.

Similarly, the dot product will become negative if v2 is in the other half sphere (or half circle) where v1 defines the one pole.

EDIT: Look at the fine ASCII art of jyk below.

Share this post


Link to post
Share on other sites
Here's a little diagram to illustrate:
 A__  |  __B
|\ | /|
\ | /
\ | /
\|/
------------>C
|
|
|
|
|
dot(A,C) is negative, and dot(B,C) is positive. In general, any vector that points to the left of the vertical line (or plane in 3d) has a negative dot product with C, and any vector that points to the right has a positive dot product.

Share this post


Link to post
Share on other sites
Presumably it's possible that eventually, by chance, a ray will be perpendicular to some faces. In that case, since we're picking 3, will it really matter which one I pick?

Eg. I have a ray in the direction of (0,0,-1), now, won't this be perpendicular to both (1,0,0) and (-1,0,0)? So, will it matter which I pick?

Share this post


Link to post
Share on other sites
If I understand you correctly, you ask which planes should remain after Woo's first step if the ray is also (partly) axis aligned, so that it is parallel to a couple of the planes of the BB?

If you mean that, and you pick any of the planes, then you have to compute the travel distance in the second step. But you could not due to the parallelism. So, without having it programmed yet, I assume you have no choice other than dropping all of those belonging planes. IMHO in such case you have no senseful possibility to pick 3 planes.

Quote:
Original post by Endar
Eg. I have a ray in the direction of (0,0,-1), now, won't this be perpendicular to both (1,0,0) and (-1,0,0)?

Definitely, yes.

Share this post


Link to post
Share on other sites
Quote:
Original post by haegarr
If you mean that, and you pick any of the planes, then you have to compute the travel distance in the second step. But you could not due to the parallelism. So, without having it programmed yet, I assume you have no choice other than dropping all of those belonging planes. IMHO in such case you have no senseful possibility to pick 3 planes.


Okay, I'm a little lost. Are you saying that I should forget about any planes that they ray is perpendicular to? So, in my little example, I would end up with only two planes to do the rest of the test against? The ones to which the ray is not perpendicular. Right?

Share this post


Link to post
Share on other sites
The problem will come with the second step, where you have to compute the hit point on the plane, correct?

If the ray is parallel to the plane, then 2 possible solutions may occur:

(1) The origin of the ray is outside the plane. In such case there is no hit point at all.

(2) The origin of the ray is inside the plane. In such case you have infinitely many hit points.

(EDIT: Try it: Compute the t parameter by the Ray-Plane test. You will encounter a division by zero due to the (n dot dir) term in the denominator.)

With both solutions you have computational problems since they simply makes no sense for the algo, as far as I see. So yes, I suggest to drop those planes, too, even if that means that you may have less than 3 planes.

BTW: The worst case would be 1 remaining plane.

Share this post


Link to post
Share on other sites
Appendix: The algo reduces the count of candidate planes to 1, and at last tests the hit on that plane against the volume. So I don't see a problem if the count is restricted formerly to 1 in the worst case. Even in the cases of parallel rays the concluding test seems me to work well.

Attention: You should not drop planes that are perpendicular to the ray, but planes that are _parallel_! The _normals_ of parallel planes are perpendicular to the ray! Please take care of this.

[Edited by - haegarr on November 26, 2005 4:26:29 AM]

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!