Monday, December 1, 2008

So Close Yet So Far

After spending the Friday afternoon with Andor trying to find ray-box intersection samples, we've finally narrowed it down to 3-4 tests to try.
- From www.blitzbasic.com
- Notes from University of Utah
- From 3D Programming Weekly
- And samples from "3D Game Engine Architecture" by David H. Eberly

Spending the weekend trying out the different sample tests, starting from what seemed the simpliest (blitzbasic), I've found the code from 3D Programming to work close to what I needed. This code is mainly used for testing AABB (Axis Aligned Bounding Box), and so, when the camera is set at positions that is not aligned with an axis, it doesn't work.
This test involves 3 separate functions:

// fDst1 and fDst2 are the distance between P1/P2 and the bounding box
// Hit is use to store where the intersection point is
function GetIntersection(fDst1, fDst2, P1, P2, Hit) {
if ((fDst1 * fDst2) >= 0) return 0;
if ( fDst1 == fDst2 ) return 0;

var tmp = new Array();

tmp[0] = P1[0] + (P2[0]-P1[0]) * ( (-1.0 * fDst1) / (fDst2 - fDst1) );
tmp[1] = P1[1] + (P2[1]-P1[1]) * ( (-1.0 * fDst1) / (fDst2 - fDst1) );
tmp[2] = P1[2] + (P2[2]-P1[2]) * ( (-1.0 * fDst1) / (fDst2 - fDst1) );

Hit = tmp;

return Hit;
}

// Checks to see if the Hit point is in the box and which axis it's aligned with
function InBox( Hit, B1, B2, Axis) {
if (Hit != 0) {
if ( Axis==1 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[1] > B1[1] && Hit[1] < B2[1]) return 1;
if ( Axis==2 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[0] > B1[0] && Hit[0] < B2[0]) return 1;
if ( Axis==3 && Hit[0] > B1[0] && Hit[0] < B2[0] && Hit[1] > B1[1] && Hit[1] < B2[1]) return 1;
}
return 0;
}

// Check whether the line hit the box or not
function CheckLineBox(B1, B2, L1, L2, Hit) {
if (L2[0] < B1[0] && L1[0] < B1[0]) return false;
if (L2[0] > B2[0] && L1[0] > B2[0]) return false;
if (L2[1] < B1[1] && L1[1] < B1[1]) return false;
if (L2[1] > B2[1] && L1[1] > B2[1]) return false;
if (L2[2] < B1[2] && L1[2] < B1[2]) return false;
if (L2[2] > B2[2] && L1[2] > B2[2]) return false;
if (L1[0] > B1[0] && L1[0] < B2[0] &&
L1[1] > B1[1] && L1[1] < B2[1] &&
L1[2] > B1[2] && L1[2] < B2[2])
{Hit = L1;
return true;}
if ( (InBox( GetIntersection( L1[0]-B1[0], L2[0]-B1[0], L1, L2, Hit), B1, B2, 1 ))
|| (InBox( GetIntersection( L1[1]-B1[1], L2[1]-B1[1], L1, L2, Hit), B1, B2, 2 ))
|| (InBox( GetIntersection( L1[2]-B1[2], L2[2]-B1[2], L1, L2, Hit), B1, B2, 3 ))
|| (InBox( GetIntersection( L1[0]-B2[0], L2[0]-B2[0], L1, L2, Hit), B1, B2, 1 ))
|| (InBox( GetIntersection( L1[1]-B2[1], L2[1]-B2[1], L1, L2, Hit), B1, B2, 2 ))
|| (InBox( GetIntersection( L1[2]-B2[2], L2[2]-B2[2], L1, L2, Hit), B1, B2, 3 )))
{
return true;
}
return false;
}

Knowing that this test is for AABB, I've tested it to make sure that it at least works when being aligned at an axis at a time. Now, I need to figure out which of the suspected issue is causing the test failure:
- Applying transformation matrix to either box, ray, or camera
- The initial conversion of 2D to 3D coord of mouse is wrong
- Other unnoticeable bugs

But before I look for these errors, I think I will try out the other tests to see if they work any better. And maybe having another session with Andor will clear things up.

No comments: