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 ;-)

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.

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]

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.

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]