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?
[size="2"][size=2]Mort, Duke of Sto Helit: NON TIMETIS MESSOR -- Don't Fear The Reaper
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).
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]
[size="2"][size=2]Mort, Duke of Sto Helit: NON TIMETIS MESSOR -- Don't Fear The Reaper
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.
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.
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?
[size="2"][size=2]Mort, Duke of Sto Helit: NON TIMETIS MESSOR -- Don't Fear The Reaper
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)?
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?
[size="2"][size=2]Mort, Duke of Sto Helit: NON TIMETIS MESSOR -- Don't Fear The Reaper
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.
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]
