[quake3-bugzilla] [Bug 3639] BoxOnPlaneSide patch

[bugzilla-daemon at icculus.org]

http://bugzilla.icculus.org/show_bug.cgi?id=3639

--- Comment #7 from Patrick Baggett <baggett.patrick at gmail.com> 2009-09-17 14:26:58 EDT ---
Two things:

1) Yes, Tim is correct, my test case compares the C version. The x87 FPU
assembly is supposedly faster (I think it is imported from Quake[1]).

2) It is easy to show that the new code fragment is mathematically equivalent
to the previous one. The crux of this algorithm is this formula:

dot(Plane.Normal, Point) + Plane.Dist = D, (signed) distance from plane to
point. If you remove the "+ Plane.Dist" from the equation, you get D', the
distance from point to a plane on the origin. When it happens that the point
isn't a far out along the plane's normal as the plane is (i.e. D' <
Plane.dist), then point is behind the plane, not in front of it.

Mathematically, a box has 8 points, and using the sign bits of the plane,
selects 1 of the eight points which is furthest in the direction of the plane's
normal, and then the opposite corner (can be furthest) from the plane.
In 2D, it is easier to see.

v0       v1
o====\==o
|     \/|
|      \|
|       \
o=======o
v2     v3

In this, you can see the plane has a normal with +X and +Y components.
Therefore it chooses V1, which is the vector {emaxs[0], emaxs[1]} and then V2
which is the vector {emins[0],emins[1]}.

The proposed code use a for() loop from i = 1 to 3 to perform the dot product,
while id's code explicitly maps out every permutation of sign bits and expands
the dot product.

In fact, there is no reason one couldn't do this like (inefficient!)

vec3_t P;

P1[0] = plane->signbits & 1 ? emins[0] : emaxs[0]; //check bit 0
P1[1] = plane->signbits & 2 ? emins[1] : emaxs[1]; //check bit 1
P1[2] = plane->signbits & 4 ? emins[2] : emaxs[2]; //check bit 2

dist1 = P1[0]*plane->normal[0] + P1[1]*plane->normal[1] +
P1[2]*plane->normal[2]
//etc...

In that form, I think it is easier to understand the above mathematics.

Patrick

-- 
Configure bugmail: http://bugzilla.icculus.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.