Rotated AABBs and frustum intersection

Started by
5 comments, last by kalle_h 8 years, 7 months ago

I'm doing view frustum culling using this fairly standard algorithm


AABBIntersection Intersection(const AABB& aabb, const Mat4& frustumMatrix)
{
	const Vec4 rowX(frustumMatrix[0].x, frustumMatrix[1].x, frustumMatrix[2].x, frustumMatrix[3].x);
	const Vec4 rowY(frustumMatrix[0].y, frustumMatrix[1].y, frustumMatrix[2].y, frustumMatrix[3].y);
	const Vec4 rowZ(frustumMatrix[0].z, frustumMatrix[1].z, frustumMatrix[2].z, frustumMatrix[3].z);
	const Vec4 rowW(frustumMatrix[0].w, frustumMatrix[1].w, frustumMatrix[2].w, frustumMatrix[3].w);

	AABBIntersection ret(AABBIntersection::Inside);

	// left, right, bottom, top, near, far planes
	std::array<Vec4, 6> planes = { rowW + rowX, rowW - rowX, rowW + rowY, rowW - rowY, rowW + rowZ, rowW - rowZ };
	float d = 0.0f, r = 0.0f;
	for (const Vec4& plane : planes)
	{
		d = glm::dot(Vec3(plane), aabb.mAABBCenter);
		r = glm::dot(Vec3(glm::abs(plane)), aabb.mAABBExtent);

		if (d - r < -plane.w)
			ret = AABBIntersection::Partial;
		if (d + r < -plane.w)
			return AABBIntersection::Outside;
	}

	return ret;
}

The frustrumMatrix is the Local-World-View-Projection matrix and the aabb is simply in Local space. This works fine even if the world matrix is scaled or translated. However if a rotation component is added then the test is no longer working.

Why is this? And is there anything I can do to modify the frustrumMatrix to make it play nice with rotations aswell? I could apply a rotation matrix to the aabb but I would very much like to avoid that and only as a last resort if it cannot be done by modifying the frustrumMatrix...

Any ideas?

Thanks

Advertisement

AABB’s are not to be held in local space. They are to be represented in world space. Applying the world matrix, rotations and all, to the AABB is the correct solution and should fix your problems.

L. Spiro

I restore Nintendo 64 video-game OST’s into HD! https://www.youtube.com/channel/UCCtX_wedtZ5BoyQBXEhnVZw/playlists?view=1&sort=lad&flow=grid

There is nothing wrong using AABB's at local space. I have implemented local space frustum culling method that use couple different tricks and is quite efficient and very precise. This method work for any rotation, scale, translation local matrix and I have tested both ortho and perspective projection matrices. Only drawback is that I don't normalize plane equations so I can't get exact distances from aabb to plane so I can't get information about intersection. Only binary in or out. There is my code. http://pastebin.com/9uPvpAfj

For OBB culling alternative is transform 8 corners from AABB's and test all of them against all planes. Or transforming points to clipspace and doing culling on there.

References:

https://fgiesen.wordpress.com/2012/08/31/frustum-planes-from-the-projection-matrix/

https://fgiesen.wordpress.com/2010/10/17/view-frustum-culling/

http://iquilezles.org/www/articles/frustum/frustum.htm

Clipspace reference:

http://zeuxcg.org/2009/01/31/view-frustum-culling-optimization-introduction/

What is the purpose of keeping them in local space? You can’t use them for octrees, quadtrees, BVH’s, coarse-level culling, etc., and you have the much-greater expense of transforming either the frustum of the AABB for each frustum test.
Transforming an AABB into world space once for each update of the object’s world matrix is trivial.

	/**
	 * Computes an AABB from an existing AABB with a matrix-stored translation.
	 *	The matrix must be row-major.
	 *
	 * \param _aabbOther The source bounding box to transform by the given matrix and store in this object.
	 * \param _mTrans The matrix used to transform _aabbOther into this bounding box.
	 */
	LSVOID LSE_CALL CAabb::ComputeAabbFromAabbAndMatrix( const CAabb &_aabbOther, const CMatrix4x4 &_mTrans ) {
		// For each axis.
		for ( LSUINT32 I = 0; I < 3; ++I ) {
			// Add the translation.
			m_vMin[I] = m_vMax[I] = _mTrans( 3, I );

			// Create extents by summing smaller and larger terms on this axis only.
			for ( LSUINT32 J = 0; J < 3; ++J ) {
				LSREAL fE = _mTrans( J, I ) * _aabbOther.m_vMin[J];
				LSREAL fF = _mTrans( J, I ) * _aabbOther.m_vMax[J];

				if ( fE < fF ) {
					m_vMin[I] += fE;
					m_vMax[I] += fF;
				}
				else {
					m_vMin[I] += fF;
					m_vMax[I] += fE;
				}
			}
		}
	}
Keeping them in local space may make them tighter fits, but it is unlikely to make up for the overhead and lack of usefulness.


L. Spiro

I restore Nintendo 64 video-game OST’s into HD! https://www.youtube.com/channel/UCCtX_wedtZ5BoyQBXEhnVZw/playlists?view=1&sort=lad&flow=grid

It's only about tighter fit. Frustum test in local space is very fast and isn't problem.

Another advantage is that same test can be used for any frustum and in any space. In my real world usage I only send one frustum matrix in and just use that. Then I can do culling in space what make most sense for current use case. One relevant use case could be use that test only for objects that intersect frustum. So you only spend extra effort when it's needed.

Edit: There are also even better aproach if false positives are problem. http://iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm

There is nothing wrong using AABB's at local space. I have implemented local space frustum culling method that use couple different tricks and is quite efficient and very precise. This method work for any rotation, scale, translation local matrix and I have tested both ortho and perspective projection matrices. Only drawback is that I don't normalize plane equations so I can't get exact distances from aabb to plane so I can't get information about intersection. Only binary in or out. There is my code. http://pastebin.com/9uPvpAfj

For OBB culling alternative is transform 8 corners from AABB's and test all of them against all planes. Or transforming points to clipspace and doing culling on there.

References:

https://fgiesen.wordpress.com/2012/08/31/frustum-planes-from-the-projection-matrix/

https://fgiesen.wordpress.com/2010/10/17/view-frustum-culling/

http://iquilezles.org/www/articles/frustum/frustum.htm

Clipspace reference:

http://zeuxcg.org/2009/01/31/view-frustum-culling-optimization-introduction/

Expanding the dot products in my code it should be exactly the same as yours for testing if its outside or not. And your aabb's are in local space too? And ignoring the typo in the pastebin code, the matrix used is a local*world*view*projection matrix too?

Is there a specific reason as to why only rotations might be causing this test to fail when translation and scaling works fine? Also the object are rendered correctly when not culled so the matrices must be fine...?

The test works when rotating the local AABB using the rotation component from the world matrix aswell like below but I'd rather avoid it...


frustumMatrix = projMatrix * viewMatrix * worldMatrix * localMatrix;
aabb *= (rotationMatrix);

Surely transforming the aabb with the rotation matrix can somehow be worked into the frustumMatrix for the test to work.

Either way I'm gonna have to keep debugging it

There is nothing wrong using AABB's at local space. I have implemented local space frustum culling method that use couple different tricks and is quite efficient and very precise. This method work for any rotation, scale, translation local matrix and I have tested both ortho and perspective projection matrices. Only drawback is that I don't normalize plane equations so I can't get exact distances from aabb to plane so I can't get information about intersection. Only binary in or out. There is my code. http://pastebin.com/9uPvpAfj

For OBB culling alternative is transform 8 corners from AABB's and test all of them against all planes. Or transforming points to clipspace and doing culling on there.

References:

https://fgiesen.wordpress.com/2012/08/31/frustum-planes-from-the-projection-matrix/

https://fgiesen.wordpress.com/2010/10/17/view-frustum-culling/

http://iquilezles.org/www/articles/frustum/frustum.htm

Clipspace reference:

http://zeuxcg.org/2009/01/31/view-frustum-culling-optimization-introduction/

Expanding the dot products in my code it should be exactly the same as yours for testing if its outside or not. And your aabb's are in local space too? And ignoring the typo in the pastebin code, the matrix used is a local*world*view*projection matrix too?

Is there a specific reason as to why only rotations might be causing this test to fail when translation and scaling works fine? Also the object are rendered correctly when not culled so the matrices must be fine...?

The test works when rotating the local AABB using the rotation component from the world matrix aswell like below but I'd rather avoid it...


frustumMatrix = projMatrix * viewMatrix * worldMatrix * localMatrix;
aabb *= (rotationMatrix);

Surely transforming the aabb with the rotation matrix can somehow be worked into the frustumMatrix for the test to work.

Either way I'm gonna have to keep debugging it

My AABB's are in local space and matrices are same as yours. I haven't had any problems with rotations so far. Can you test normalizing your planes? This is needed for partial test to work right,

This topic is closed to new replies.

Advertisement