🔒 Locked

Line to AABB test issue

Started by j0urnalism Dec 10, 2009 at 1:29 AM 7 replies 1.1k views

Original Post

Dec 10, 2009 at 1:29 AM

So I found this thread, which I've implemented, but no dice. Does anybody have any idea as to why it isn't working? Here's my code:


	bool LineToAABB(const ceLineSeg& line, const bvAABB &aabb)
	{
		// center box at origin
		D3DXVECTOR3 vSegDir = (line.vEndPt - line.vStartPt) * 0.5f;	// segment half width vector
		D3DXVECTOR3 vBoxExtents = (aabb.vMax - aabb.vMin) * 0.5f;				// aabb half width vector
		D3DXVECTOR3 vCentered = line.vStartPt + vSegDir - (aabb.vMin + aabb.vMax) * 0.5f;	// put at origin
		D3DXVECTOR3 absDir = vSegDir;	// no negatives
		absDir.x = fabs(absDir.x);
		absDir.y = fabs(absDir.y);
		absDir.z = fabs(absDir.z);

		if (fabs(vCentered.x) > vBoxExtents.x + absDir.x ||
			fabs(vCentered.z) > vBoxExtents.z + absDir.z ||
			fabs(vCentered.y) > vBoxExtents.y + absDir.y)
				return false;

#define FLOAT_EPSILON 0.0000001
		if (fabs(vSegDir.y * vCentered.z - vSegDir.z * vCentered.y) > 
				vBoxExtents.y * absDir.z + vBoxExtents.z * absDir.y + FLOAT_EPSILON)
			return false;
		if (fabs(vSegDir.z * vCentered.x - vSegDir.x * vCentered.z) > 
				vBoxExtents.z * absDir.x + vBoxExtents.x * absDir.z + FLOAT_EPSILON)
			return false;
		if (fabs(vSegDir.x * vCentered.y - vSegDir.y * vCentered.x) >
				vBoxExtents.x * absDir.y + vBoxExtents.y * absDir.x + FLOAT_EPSILON)
			return false;

		return true;

To note, I've also tried the ray version posted on that thread I linked to(a sort of swept SAT I believe?) to no avail.

Zakwayda

Dec 10, 2009 at 3:47 AM

Your code looks like it matches the code in the other thread (which I'm pretty sure is right, although not absolutely certain).

Can you describe how it's not working? False positives? False negatives? Perhaps you could post some example input (an AABB and line segment configuration) that you know is intersecting (or not intersecting), but for which the code is returning incorrect results.

j0urnalism

Dec 10, 2009 at 11:23 AM

Quote:
Can you describe how it's not working?

Well, it never returns true. Up until I move the line far enough left into the negative x(and it's no longer close to intersecting), it returns false at the first if() check.

When it does get past that check, it always returns here:

		if (fabs(vSegDir.z * vCentered.x - vSegDir.x * vCentered.z) > 				vBoxExtents.z * absDir.x + vBoxExtents.x * absDir.z + FLOAT_EPSILON)			return false;

Also, my vBoxExtents and absDir always are being set to all 1s...pretty sure that's not right?

Thanks for the help btw.

Zakwayda

Dec 10, 2009 at 7:21 PM

If you can post some example data, I might be able to take a closer look. Just pick a configuration (i.e. two line endpoints and a min and max for the box) that you know should be intersecting, but for which the test is returning false, and post those values. (A configuration that would be easy to work with would be a cube centered at the origin intersecting with an axis-aligned segment passing through the origin.)

j0urnalism

Dec 10, 2009 at 8:59 PM

Alright, I centered the aabb at the origin:
min = D3DXVECTOR3(-1.0f, -1.0f, -1.0f),
max = D3DXVECTOR3(1.0f, 1.0f, 1.0f)

the line is passing through:
start = D3DXVECTOR3(-2.8f, -1.1f, -1.1f),
end = D3DXVECTOR3(-0.8f, 1.1f, 1.1f)

the behavior is now that it returns true at this point. note that it returns true when it should now as well.

This false positive occurs when the line is moved in any direction to a point past collision, with behavior identical to what is happening with the x values above.

Zakwayda

Dec 10, 2009 at 9:25 PM

I'm having a little trouble following - earlier you said it never returns true, but here you say it 'returns true when it should now as well' (I'm not sure what that means).

Quote:
Original post by j0urnalism
Alright, I centered the aabb at the origin:
min = D3DXVECTOR3(-1.0f, -1.0f, -1.0f),
max = D3DXVECTOR3(1.0f, 1.0f, 1.0f)

the line is passing through:
start = D3DXVECTOR3(-2.8f, -1.1f, -1.1f),
end = D3DXVECTOR3(-0.8f, 1.1f, 1.1f)

Just so I'm completely clear, a couple of questions. First, does the above input data return the correct result, or the incorrect result? And if the latter, is it returning true when it's supposed to return false, or returning false when it's supposed to return true?

j0urnalism

Dec 11, 2009 at 12:53 AM

Sorry for the confusion. After repositioning the AABB to its current position

Quote:

min = D3DXVECTOR3(-1.0f, -1.0f, -1.0f),
max = D3DXVECTOR3(1.0f, 1.0f, 1.0f)

(centered at the origin) the outcome changed.

NOW, what's happening is it returns true (collision) when it should, if the line were to be at, say,

start = D3DXVECTOR3(-1.1f, -1.1f, -1.1f)
end = D3DXVECTOR3(1.1f, 1.1f, 1.1f)

but it ALSO returns true (collision) if the line is moved to

start = D3DXVECTOR3(-2.8f, -1.1f, -1.1f),
end = D3DXVECTOR3(-0.8f, 1.1f, 1.1f)

which is INCORRECT...this should definitely not result in collision.

I hope that's a bit clearer this time, sorry!

Zakwayda

Dec 11, 2009 at 7:12 PM

I compared your implementation to another reference I have, and it looks correct (although this kind of code can be a little hard to proofread visually).

A couple of things you mentioned suggest to me that the problem might be elsewhere. You said you tried the slab-based clipping method also and that didn't work either, and also that some of the vector variables seem to be coming out as (1, 1, 1) even when they shouldn't. Perhaps there's something wrong with the input data or the testing framework?

I suggested this in another thread recently and I think it might be relevant here as well. It would be a bit tedious, but you could work through your test case by hand using the same algorithm and see if the result is correct or incorrect. If it's incorrect, there may be a problem with the implementation of the algorithm itself. If it's correct but the program is still behaving incorrectly, it would suggest that there's something wrong with the input data or testing framework, in which case you should be able to step through the function in the debugger and identify where the variable values are deviating from what would be expected.

Sorry I don't have a better answer, but I've looked over your function a couple of times now and haven't been able to spot any errors. (That doesn't mean there aren't any - it just means I haven't been able to spot them :)

j0urnalism

Dec 11, 2009 at 10:29 PM

Thanks for the help! Yeah, I'm thinking you may be right. I tried another slightly different implementation from a book, and it has the same type of behavior. Time to dig into the code!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.