Woo's method

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]

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

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.

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.

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?

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.

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?

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.

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]

Quote:

Original post by haegarr 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.

Yeah, that's what I meant. I wrote planes, but was thinking about their normals.

Quote:

Original post by Endar Yeah, that's what I meant. I wrote planes, but was thinking about their normals.

Okay okay, I would be sure only you're not dropping the good planes ;-)

Okay, check my common sense.

I have a aabb from (-1,-1,-1) to (2,1,1). I have a ray starting at (3,0,0) going in the direction (-1,0,0).

Now, correct me if I'm wrong, but, shouldn't the intersection point be (2,0,0), not "No intersection found"?

I assume that the normals of the BB's planes are defined to point to the outside. (If they are defined to point inside the BB, then in the following the statements using the result of the dot product has to be negated.)

Then the first step of the algo defines the left plane (w/ the normal (-1,0,0) to be dropped since it is backfaced. You may detect this by the result of the dot product of the ray and the normal being positive.

Furthurmore the front and back planes w/ the normals (0,0,+/-1) as well as the top and bottom plane w/ normals (0,+/-1,0) are parallel to the ray. IMHO they have to be dropped.

The remaining plane is the right one w/ normal (1,0,0) that points against the given ray. So its dot product will be negative and hence the plane survives the first step of the algo.

Next, the second step of the algo could be done since at least one plane has still survived (IMHO at everytime at least one plane will be there). Computing the hit point will result in (2,0,0).

Proove: The ray equation is:
r(t) := (3,0,0)^T + t * (-1,0,0)^T
A valid plane equation of the remaining plane is (notice that infinitely many valid equations exist)
( p - (2,1,1)^T ) dot (1,0,0)^T = 0
so that the 4 plane parameters are computed to be (simply by elimiating the brackets above)
A := 1, B := 0, C := 0, D := -2
Putting into the equation for t (see the site you've cited in the orig. post)
t := - ( (1,0,0)^T dot (3,0,0)^T -2 ) / ( (1,0,0)^T dot (-1,0,0)^T ) = - (3-2) / (-1) = 1
Putting this into the equation for the ray yields in
r(t=1) = (3,0,0)^T + 1 * (-1,0,0)^T = (2,0,0)^T
q.e.d.

I don't see why "No intersection found" should come out. IMHO all works fine.

It looks like my function that finds the intersection point returns (-2,0,0) instead of (2,0,0).

Edit:: From some preliminary (2) tests, it looks like the components should just be multiplied by -1 to get the correct answer. Should I just do this? Or do you think that this is indicative of a possibly bigger problem that would cause more normal cases to fail?

[Edited by - Endar on November 26, 2005 11:20:22 PM]

You should never do a justification only to achieve the expected result. Please ask "why (or why not) does it come out". If you have a reasonable answer found, and the work-around fits into the answer, ok. But if you hide a bug, you don't know at what next opportunity it will have another drawback.

(Ok, I earn my money with programming, and so I may have another relation to that stuff. However, I write unit tests for my classes where ever possible. That costs time, of course, but gives (a) the safety that all goes the right way, and (b) allows quick prooves in cases where changes was made to the code. And (c), sometimes it let me think of cases that where not in my mind at the time of writing the code.)

You may take into account to post the belonging code for inspection by another pair of eyes.

EDIT:

Quote:

Original post by Endar From some preliminary (2) tests, it looks like the components should just be multiplied by -1 to get the correct answer.

What components do you mean? Inverting the ray should not change anything, since the hit point will be the same.

If you use
r'(t) := -r(t) = (-3,0,0)^T + t * (1,0,0)^T
you get
t := - ( (1,0,0)^T dot (-3,0,0)^T -2 ) / ( (1,0,0)^T dot (1,0,0)^T ) = - (-3-2) / (1) = 5
and finally
r'(t=-5) = (-3,0,0)^T + 5 * (1,0,0)^T = (2,0,0)^T
This should work since it is just another representation of the same ray. However, it will fail in general, since negating the ray's origin will generally not yield in just another representation of the same ray.

Inverting the normal of the plane would be the other possibility, but then the formula of t as is given would no longer be correct. (However, the result would be (4,0,0) if I'm right, what still differs from (-2,0,0).)

[Edited by - haegarr on November 27, 2005 4:40:13 AM]

Ok, this is just me being lazy, but the method as such should work fine for all bounding boxes. Seeing how we are using aabb all this can be made a lot simpler.

The normal for the "right" plane is always (1,0,0) (or -1,0,0 I usually like them pointing inward for bounding volumes). A dot product with this will ALWAYS return the direction vectors x.

Bottom line: scrap the dot products, all you want to know is if your ray is basically going left, right or doesn't change in x direction.

ie. you get six tests like this:

float t[3]={0}, *ptr=t;if (RayDir.x<0) *(ptr++)=(bbMax.x-RayP.x)/RayDir.x;

meaning, if your ray is moving left, divice the distance between the start of the ray and the right plane of the box by the "distance" the ray travels along x per "unit" of movement to get the right t. Here the t's are stored in an array. They will be positive and not more than three.

float max=(t[0]>t[1]) ? (t[0]>t[2]?t[0]:t[2]) : (t[1]>t[2]?t[1]:t[2]);

Yes, ugly and I'm sure the stl has some max function for three operands (or at least vectors). Once you have the max t the rest is just getting the point of intersection and checking if it is between all the min and max x/y/z coords.

In other words, for AABB you shouldn't even start throwing the dot products and normals around. Save them for later when you want to do the same test for arbitrarily oriented boxes. That way it should be easier to visualize.

Or start with micro optimizing. I don't like the look of 7 if's and up to 3 / in a function that's potentially called a lot. If's make baby caches cry. On the other hand I would trust the compiler until some profiler tells me that this very function is making my app crawl. And then I would look for ways to call it less often ,-)

Quote:

Original post by Trienco The normal for the "right" plane is always (1,0,0) (or -1,0,0 I usually like them pointing inward for bounding volumes). A dot product with this will ALWAYS return the direction vectors x. Bottom line: scrap the dot products, all you want to know is if your ray is basically going left, right or doesn't change in x direction.

Right you are: This is a suitable (and "should be done") optimization for AABB. I suggest to do such things after having the things working in general. IMHO the general solution introduces the best understanding of the principles.

Quote:

Original post by Trienco ie. you get six tests like this: float t[3]={0}, *ptr=t; if (RayDir.x<0) *(ptr++)=(bbMax.x-RayP.x)/RayDir.x;

I don't see the need for 6 tests. Why to distinct between x>0 and x<0 in this example? That should not be necessary.

Quote:

Original post by haegarr I don't see the need for 6 tests. Why to distinct between x>0 and x<0 in this example? That should not be necessary.

For a second you had me wondering the same thing. Then I remembered that <0 uses a different plane and hence point than >0 and nestling the <0 >0 test inside yet another !=0 test didn't seem too useful.

However, it came to me, that checking for a line segment is much more likely than checking for an infinite ray. So it might be easier to do

float t, max=0;if (rayDir.x<0) {  t=bbMax.x-rayP.x;  if (t>rayDir.x) return 0;  t /= rayDir.x;  if (t>max) max=t;}

Of course rayDir would then have to be the vector to the line segments end point. Anyway, if t>1 then the plane is out of reach. As we use the max distance anyway it doesn't matter if others would be closer and we can still abort the test right there. But I would probably run some tests if the even less cache friendly version is doing any good.

Ah, you use the sign of the x co-ordinate (as an example) to drop the backfacing planes. _That_ is the primary sense behind the "if" clause. That is truly a nice thing, too ;-)

For the moment that leads to 1 to 3 candidate planes as the full Woo algo also does. However, inside the clause one furthur investigates only the nearest plane (w.r.t. x). This is possible because the other 2 planes (if not parallel) will be investigated by the other "if" clauses, since their respective clauses will pick them accordingly (i.e. they are frontfaced w.r.t. the y and z co-ordinates of the ray). Due to the maximum finding on-the-fly, the farthest hit distance will survive.

That's really tricky, and I like it ;-) So you're right in the sense that 6 "if" clauses (*) with 1 plane investigation inside each one is the optimum one could reach. Otherwise one would get only 3 "if" clauses, but each one with 3 plane investigations inside.
(*) from which only at most 3 will be entered due to nearly pairwise mutual exclusive conditions

Quote:

Original post by Trienco and nestling the <0 >0 test inside yet another !=0 test didn't seem too useful.

I agree definitely.

Quote:

Original post by Trienco However, it came to me, that checking for a line segment is much more likely than checking for an infinite ray.

Hmm. That method requires the ray's track to be of a suitable length. As fas as I see is both the size of the BB as well as the origin of the ray unrestricted, and hence a suitable length unknown. Computing it would introduce possibly more effort than could be saved. Choosing an arbitrary but great length means to very seldom get the case of early dropping. No, I'm not convinced that this is better than to use the infinite ray.

[Edited by - haegarr on November 27, 2005 6:30:37 AM]