Advertisement Jump to content
Sign in to follow this  
cozzie

worldspace or not, matrix & extents

This topic is 1729 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

 

I've been working on a correct implementation of a OBB and AABB in worldspace for my dynamic mesh instances or renderables.This gives me the flexibility to cull using either a simple sphere check, OBB or AABB worldspace. The AABB I also use for basic collision detection.

 

When doing all the math, there's something I can't figure out (please not that the results are all fine, just like to understand the math/logics). Here's the code as background:

void OBB::Update(const D3DXMATRIX &pWorldMat, const AABB &pAABB)
{
	D3DXVec3TransformCoord(&Center, &pAABB.Center(), &pWorldMat);

	D3DXVECTOR3 size = pAABB.Extents();
	
	D3DXVECTOR3 mAx, mAy, mAz;
	mAx = D3DXVECTOR3(pWorldMat._11, pWorldMat._12, pWorldMat._13);
	mAy = D3DXVECTOR3(pWorldMat._21, pWorldMat._22, pWorldMat._23);
	mAz = D3DXVECTOR3(pWorldMat._31, pWorldMat._32, pWorldMat._33);

	XHalfExtent = mAx * size.x / 2.0f;
	YHalfExtent = mAy * size.y / 2.0f;
	ZHalfExtent = mAz * size.z / 2.0f;
}

void AABBWORLD::Update(const OBB &pOBB)
{
/*	1. calculate the 8 corners based on the OBB half extents

       E              F
	   /-------------|				A = -X	-Y	-Z
	  / |          / |				B = +X	-Y	-Z
	 /  |         /  |              C = +X	+Y	-Z	
  A	/------------|B  |              D = -X	+Y	-Z
	|   |	     |   |              
	|  / - - - - | - | G			E = -X	-Y	+Z
	| / H        |  /				F = +X	-Y	+Z
	|/           | /				G = +X	+Y	+Z
  	|------------|/					H = -X	+Y	+Z
  D	              C
	*/

	D3DXVECTOR3 OBBcorners[8];
	
	OBBcorners[0] = -pOBB.XHalfExtent -pOBB.YHalfExtent -pOBB.ZHalfExtent;
	OBBcorners[1] = +pOBB.XHalfExtent -pOBB.YHalfExtent -pOBB.ZHalfExtent;
	OBBcorners[2] = +pOBB.XHalfExtent +pOBB.YHalfExtent -pOBB.ZHalfExtent;
	OBBcorners[3] = -pOBB.XHalfExtent +pOBB.YHalfExtent -pOBB.ZHalfExtent;

	OBBcorners[4] = -pOBB.XHalfExtent -pOBB.YHalfExtent +pOBB.ZHalfExtent;
	OBBcorners[5] = +pOBB.XHalfExtent -pOBB.YHalfExtent +pOBB.ZHalfExtent;
	OBBcorners[6] = +pOBB.XHalfExtent +pOBB.YHalfExtent +pOBB.ZHalfExtent;
	OBBcorners[7] = -pOBB.XHalfExtent +pOBB.YHalfExtent +pOBB.ZHalfExtent;

//	2. Find the min and max X Y Z of the corners to get AABB in worldspace

	_Min = OBBcorners[0];
	_Max = _Min;

	for(int j=1;j<8;++j)
	{
		_Min = D3DXVECTOR3((std::min)(OBBcorners[j].x, _Min.x),
						   (std::min)(OBBcorners[j].y, _Min.y),
						   (std::min)(OBBcorners[j].z, _Min.z));

		_Max = D3DXVECTOR3((std::max)(OBBcorners[j].x, _Max.x),
					  	   (std::max)(OBBcorners[j].y, _Max.y),
						   (std::max)(OBBcorners[j].z, _Max.z));
	}

//	3. Transfom Min/Max to worldspace by adding world center to the _Min and _Max
	Center = pOBB.Center;
	_Min += Center;
	_Max += Center;
}

// CULLING FUNCTIONS

int CD3dcam::OBBInFrustum(const OBB &pOBB) const
{
	int _result = 99;
	float d, s;
	
	for(int i=0;i<6;++i)
	{
		d = D3DXPlaneDotCoord(&mFrustumPlane[i], &pOBB.Center);

		s = fabs	(D3DXVec3Dot(&D3DXVECTOR3(mFrustumPlane[i].a, mFrustumPlane[i].b, mFrustumPlane[i].c), &pOBB.XHalfExtent)) +
			fabs	(D3DXVec3Dot(&D3DXVECTOR3(mFrustumPlane[i].a, mFrustumPlane[i].b, mFrustumPlane[i].c), &pOBB.YHalfExtent)) +
			fabs	(D3DXVec3Dot(&D3DXVECTOR3(mFrustumPlane[i].a, mFrustumPlane[i].b, mFrustumPlane[i].c), &pOBB.ZHalfExtent));

		if(d < -s) return OUTSIDE;
		if(d+ -s < 0) _result = INTERSECT;	
	}
	if(_result == INTERSECT) return INTERSECT;
	else return INSIDE;
}

int CD3dcam::AABBInFrustum(const Crealysm_dxmath::AABBWORLD &pAABBworld) const
{
	D3DXVECTOR3	_pvtx, _nvtx;
	bool		intersect = false;
	float		dist;

	D3DXVECTOR3 center = pAABBworld.Center;
	D3DXVECTOR3 extents = pAABBworld.Extents();

	for(int i=0;i<6;++i)
	{
		// find the nearest and farthest point along normal direction
		_pvtx.x = center.x + (extents.x / 2.0f) * mFrustumPlaneSign[i].x;
		_pvtx.y = center.y + (extents.y / 2.0f) * mFrustumPlaneSign[i].y;
		_pvtx.z = center.z + (extents.z / 2.0f) * mFrustumPlaneSign[i].z;

		_nvtx.x = center.x - (extents.x / 2.0f) * mFrustumPlaneSign[i].x;
		_nvtx.y = center.y - (extents.y / 2.0f) * mFrustumPlaneSign[i].y;
		_nvtx.z = center.z - (extents.z / 2.0f) * mFrustumPlaneSign[i].z;

		// check positive vertex; further along the normal's direction
		dist = D3DXPlaneDotCoord(&mFrustumPlane[i], &_pvtx);
		if(dist < 0) return OUTSIDE;		// wrong side of plane, completely outside

		// check negative vertex; less far along the normal's direction
		dist = D3DXPlaneDotCoord(&mFrustumPlane[i], &_nvtx);
		if(dist < 0) intersect = true;
	}
	if(intersect) return INTERSECT;
	return INSIDE;
}

Details:

- the OBB extents are transformed by only the 1st, 2nd and 3rd row of the world matrix. My understanding is that the extents are therefor rotated and scaled, but NOT transformed to worlspace (because that would be in the 4th row of my world matrix)

- my OBB culling function compares planes in worldspace and the OBB extents

 

- the AABB in worldspace is calculated from the OBB, using the extents so in local space (oriented).

Therefor I have to add the center to 'translate' the AABB to worldspace. This gives me the expected results and confirms to me the that the OBB extents are not in worldspace.

 

So my question is, why does the OBB culling work with this code, without transforming the OBB extents to worldspace? (using the center).

Since the frustum planes I believe are also in worldspace.

 

Any input is appreciated.

Share this post


Link to post
Share on other sites
Advertisement
Hoping to get an answer, I've been brushing up my math.
My question is now more explicit:

- the OBB extents take only rotation and scaling of the world matrix into account (basically 1st to third column of the world matix, for X, Y and Z rows)
- to check a point against a plane I know that:
"if plane normal dot coord/vector + plane d > 0, then the point is inside / on the positive halfspace of the plane" (0 would be on the plane, < 0 in negative halfspace/ outside frustum)
- that's what happening with the float "d" (basically a point in sphere check)

But then I get confused, next I add up the dot products of plane normal . halfextentX, Y and Z. Plane normal is normalized so has no "position" in worldspace, same for the OBB extents. Does this mean they're both in "local space" and can therefor be used together?

What I think happens is that the OBB extents are basically checked gainst then plane. Using worldspace OBB center in combination with OBB extents in local space.

I can't find out how to illustrate the relation of "d" and "s", hope someone can help me out.
Feels like I'm almost there, maybe a drawing of an example can make things clearer.

Share this post


Link to post
Share on other sites

Hoping to get an answer, I've been brushing up my math.
My question is now more explicit:

- the OBB extents take only rotation and scaling of the world matrix into account (basically 1st to third column of the world matix, for X, Y and Z rows)
- to check a point against a plane I know that:
"if plane normal dot coord/vector + plane d > 0, then the point is inside / on the positive halfspace of the plane" (0 would be on the plane, < 0 in negative halfspace/ outside frustum)
- that's what happening with the float "d" (basically a point in sphere check)

But then I get confused, next I add up the dot products of plane normal . halfextentX, Y and Z. Plane normal is normalized so has no "position" in worldspace, same for the OBB extents. Does this mean they're both in "local space" and can therefor be used together?

What I think happens is that the OBB extents are basically checked gainst then plane. Using worldspace OBB center in combination with OBB extents in local space.

I can't find out how to illustrate the relation of "d" and "s", hope someone can help me out.
Feels like I'm almost there, maybe a drawing of an example can make things clearer.

A plane actually cannot have a position, as it is infinite in 2 directions. What it does have is a normal, and a distance along that normal that the origin is from the plane, along the plane normal (or vice versa if you choose that route), and this normal can be described in many spaces, hence distance is also dependent on the coordinate system used.

 

So a point is on the plane when point dot plane.normal + plane.d= 0, because a point projected onto the plane's normal would have to travel 0 distance along the normal to get to the plane. A positive plane.d  means that the plane is behind origin in the direction of the planes normal, and vice versa. So the sign of D actually tells you which direction origin is from the plane, and is a measure of how far from the intersection of the plane's normal with the plane, to the origin.

 

To test a point, What we are actually doing is vector projection:

we project the point onto the planes normal, which gives a scalar of the distance along the normal, from origin to the plane that said point would exist on. if this d, the distance from origin to the point, is the opposite of the planes.d, or the distance to origin from the plane along it's normal, is 0, the 2 planes are co planar.

 

now with that out of the way, look at d in your function. and then how s is calculated, and finally how it is determined that the OBB is in or out of the frustrum. It should all click eventually.

Share this post


Link to post
Share on other sites

Thanks.
I've been thinking, googling and drawing things out with the following ideas:

- the plane equation can be changed to d = -(plane normal dot point)
- distance from a point (origin) to plane (travellling alongnormal):
D = (plane normal dot point + d) / Magnitude(plane normal)
(which I don't use momentarilly)

- if the plane normal is normalized, d3dxplanedotcoord return value is actually the signed distance to the point/ origin

So let's say my float d saves the shortest signed distance from OBB center (origin) to the plane.

I understand that float s adds up the dot products of the plane normal with the extents vectors, using fabs means that in the end there will always be a positive (absolute) value. Which I conclude as the 'size' of the obb.

- float d is used for determining both the sign and distance
- float s is used to determine the 'size' of the oriented obb

That way if d < -s is outside the frustum, example:
d = 5
s = 7
Would not be outside, because 5 is bigger then -7.
But would be intersecting because center is 5 from plane but size is 7, so "2 on the other side of the plane".

Example 2:
d = -5
s = 4
Would be outside because -5 is smaller then -4 ("1 offset from the other side of the plane)

So I basically compare the obb center to the plane and the 'size' of the obb to see if it intersects, or is in front or back of the plane. All tests I just did prove this logic/ theory smile.png

The only thing I can't get my head around is why adding the dot products of plain normal dot extent, gives me the 'size' of the obb. I read that doing a dot product between two vectors is called vector projection smile.png What I think is that 'size' in this case means the distance from origin/ plane normal to 'longest' extents of the obb

Edited by cozzie

Share this post


Link to post
Share on other sites

Basically yes... if we projected a hypotenuse to the horizontal plane, you would end up with the run, or x1-x0 or how ever you choose to internalize it. if you projected the rise onto the run you would get, 0. because you would travel 0 along the x axis with a vertical line. by projecting each of the extents, you are seeing how far the closest/farthest vertex is from the plane, and comparing that to the  distance to center. if these numbers are the same, than the vertex is on the plane, because d + -s = 0;

Share this post


Link to post
Share on other sites
Thanks, I think I get it.
The normal vector (direction only, normalized) is projected to each of the half extent vectors (not normalized) to get the closest/ farthest vertex from the plane. Which basically is the size, because from the plane I only use the vector/ direction not representing a position. Then d represents a distance the center is from the plane.

I'll make a small test program and do some tests. I'll post the results afterwards, if you want maybe you can see if it's ok.

Share this post


Link to post
Share on other sites

I think I finally got the last part clear.

Imagine this:

        / XH
 YH \  /
     \/
     |
     | 
     |
     | ZH


-->   PLANE NORMAL

   -     +
       .---> 
       .---->XH
YH <---.
       .------> ZH


XH/YH/ZH = the half extents

 

Projecting a unit length vector (plane normal) onto a non-unit length vector B (half extents), using dot product, gives as result the length of vector B projected in the direction of vector A.

 

These 3 results can be either positive or negative, using (fabs) basically adds them all up, so there's one total length.

Is this correct?

Share this post


Link to post
Share on other sites

I think there was either too much or not enough going on in my previous posts, and though you are getting close to your solution, i think there are some grey areas in your understanding that we are glazing past, that will come back to bite you so I'm going to address them first.

 

The dot product of 2 vectors  A , and B,  results in the cosine of the angle (theta) between them, scaled by the magnitude of each vector.

 

A . B = |A||B| cos(theta)

 

This is why you normalize both vectors first to get the angle, as the magnitude of a normalized, or unit length vector is 1.

 

A . B = cos(theta) WHERE |A| = |B| = 1

 

Vector projection exploits that fact, by projecting A on to B, then dividing by B's Magnitude.

 

A . B

------

 | B |

 

Your half extents are the projection of the half sizes onto the OBB's local axii, in world space, and with them and a position of the OBB in world space we can find the world space positions of each vertex.

 

For a plane, one or 2 or 4 of these vertices are going to be the closest vertex to the plane, and dito for the futhest. By using each extent separately, you getting the distance along the normal of each extent. By using fabs, we ensure we are always getting a positive value(along the planes normal). If the sum of all these distances is less than d, then the distance from the closest point to the plane, to the plane, is less than the distance from the center of the OBB to the plane, which means the box is entirely on one side of the plane.

Edited by Burnt_Fyr

Share this post


Link to post
Share on other sites

Ok, good idea to fill the gaps

(I'm actually waiting to implement first steps of nice AABB and OBB collisions between renderables, till I got this cleared up first smile.png)

 

You say that the dot product of A.B = |A| |B| Cos(theta), where the result should be the same as = Ax * Bx + Ay * By + Az * Bz.

So I have two unit length vectors:

 

A. 1 0 0

B. 0 1 0

 

Which have a 90 degree angle, I would expect the dot product to be 0 using both equations:

-- 1 * 0 + 0 * 1 + 0 * 0 = 0

-- 1 * 1 * cos(90) = 0

 

I tried the same with vectors that are in opposite directions, there it works too (1 * 1 * -1 = -1).

So thats cleared up.

 

Now on vector projection I understood that taking the dot product of vector A (unit length) dot vector B (not unit length), gives me the magnitude of vector B projected to vector A. So I project the extents to the normal of plane, giving me the 'distance' per axis, following the plane normal. Is this correct?

I currently don't normalize the extent vector, so I don't understand yet how the angle calculation applies there. Am I overseeing something?

 

I think my half extents are not transformed to worldspace regarding position, only on 'orientation' (world matrix row 4 is not used). In the OBB check function I use the OBB center (which is in worldspace), to find the distance from center worldspace to the plane. Which I then compare to 'projected radius'.

 

Unless.. it's a definition thing, I read 'worldspace' as moved / translated to worldspace, based on the 4th row in my world matrix.

 

You said "For a plane, one or 2 or 4 of these vertices are going to be the closest vertex to the plane, and dito for the futhest. By using each extent separately, you getting the distance along the normal of each extent."

What I don't understand here is what you mean with vertices, in my culling function I only have 1 vertex for the center.

 

It also crossed my mind that you're talking about vector projection to calculate the extents:

	D3DXVECTOR3 size = pAABB.Extents();

	D3DXVECTOR3 mAx, mAy, mAz;
	// orientation: rotation/ scaling (NOT in worldspace)
	mAx = D3DXVECTOR3(pWorldMat._11, pWorldMat._12, pWorldMat._13);		
	mAy = D3DXVECTOR3(pWorldMat._21, pWorldMat._22, pWorldMat._23);		
	mAz = D3DXVECTOR3(pWorldMat._31, pWorldMat._32, pWorldMat._33);

	XHalfExtent = mAx * size.x / 2.0f;
	YHalfExtent = mAy * size.y / 2.0f;
	ZHalfExtent = mAz * size.z / 2.0f;

What happens here (I think) is that I take the X axis from my world matrix (vector) and multiply each component with the size X and divide each component by 2/0 (to get the 'half' extent). I find it difficult to visualize this, how would I describe/ visualize what direction mAx points to? (before the components are multiplied by size and divided by 2).

 

Ps; thanks for your patience and taking the time for this math class ;) I really appreciate it

Edited by cozzie

Share this post


Link to post
Share on other sites

UGH my firefox crashed and I lost everything i just typed out. @#$@#%@#

I still want to help, but i'm going to be brief this time, don't take it the wrong way, I blame mozilla

 

 

1) looks like you have the dot product figured. Congrats, now realize that A Cross B  = |A||B| sin(theta) ( C / |C| ) and your set.

2) Turn around, your orientation has changed, but your translation has not. translation is not a requirement for a transformation from 1 space to another. For origin point in space, an infinite amount of orientations, or relative frames, exist.

3) Your center is a point, or a vector to that point from origin, but a vertex it is not. A vertex is the intersection of 2 edges.

4) your OBB is a cube, so has 8 vertices, the intersections of the 6 planes that bound the space.

5) Like L.Spiro said in your other thread, mAx is your right vector, expressed in the world space coordinate frame. face north(0,1,0) turn 90 degrees to the right. your z+ is now facing east. your x+ is now facing ?????

6) we are transforming the local extents(half width, half height, and half depth) into world space by taking the axis of extent, and scaling it by the size of that extent. every vertex in your OBB is knowable by some combination of these extents and the center(see your AABBworld::update method to clarify).

 

That should help make the last part of my previous post click, if not, I'll knock it out of the park next time.

Edited by Burnt_Fyr

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!