Sign in to follow this  
peter_b

What is wrong with my plane-aabb intersection function? =/

Recommended Posts

I have a problem. When im rendering my objects, i first cull them by comparing the view frustum to their axis aligned bounding box. The problem is, that sometimes, when the camera is really close, objects can "pop" away. Ie they are beeing culled when they should not. This only happens when the camera is really close, and most often below the camera, on the bottom plane i think (not sure). See screenshot: http://hem.passagen.se/storage/culling_bug.jpg I think this may be because my plane_to_aabb() intersection function must contain a bug. Could anyone take a look at it for me? Thanks in advance.

enum plane_intersection_t
	{
		PLANE_INTERSECTION_BACK,
		PLANE_INTERSECTION_FRONT,
		PLANE_INTERSECTION_INTERSECT
	};

//////////////////////////////////////////////////////////////////////////
	plane_intersection_t intersect(const plane3_t* plane, const aab3_t* box)
	{
		vector3_t min_point;
		vector3_t max_point;

		if (plane->m_normal.x > 0.0f)
		{
			min_point.x = (float)box->m_min.x;
			max_point.x = (float)box->m_max.x;
		}
		else
		{
			min_point.x = (float)box->m_max.x;
			max_point.x = (float)box->m_min.x;
		}

		if (plane->m_normal.y > 0.0f)
		{
			min_point.y = (float)box->m_min.y;
			max_point.y = (float)box->m_max.y;
		}
		else
		{
			min_point.y = (float)box->m_max.y;
			max_point.y = (float)box->m_min.y;
		}

		if (plane->m_normal.z > 0.0f)
		{
			min_point.z = (float)box->m_min.z;
			max_point.z = (float)box->m_max.z;
		}
		else
		{
			min_point.z = (float)box->m_max.z;
			max_point.z = (float)box->m_min.z;
		}

		float min_distance = plane3_signed_distance(plane, &min_point);
		float max_distance = plane3_signed_distance(plane, &max_point);

		if (min_distance * max_distance < 0.0f)
			return PLANE_INTERSECTION_INTERSECT;
		else if (min_distance >= 0.0f)
			return PLANE_INTERSECTION_FRONT;

		return PLANE_INTERSECTION_BACK;
	}



// the frustum intersection function, tought id add it, but i dont think there could be anything wrong here, since its so simple.
//////////////////////////////////////////////////////////////////////////
	bool intersect(const aab3_t* a, const frustum3_t* f)
	{
		plane_intersection_t left = intersect(&f->m_left, a);
		plane_intersection_t right = intersect(&f->m_right, a);
		plane_intersection_t top = intersect(&f->m_top, a);
		plane_intersection_t bottom = intersect(&f->m_bottom, a);
		plane_intersection_t near = intersect(&f->m_near, a);
		plane_intersection_t far = intersect(&f->m_far, a);

		if((left == PLANE_INTERSECTION_BACK)
			|| (right == PLANE_INTERSECTION_BACK)
			|| (top == PLANE_INTERSECTION_BACK)
			|| (bottom == PLANE_INTERSECTION_BACK)
			|| (near == PLANE_INTERSECTION_BACK)
			|| (far	 == PLANE_INTERSECTION_BACK))
			return false;

		return true;
	}



Share this post


Link to post
Share on other sites
Guest Anonymous Poster
This happened to me once.. it was because I had set up the frustum incorrectly. But in your case it could be you need to change || for &&

[SOURCE]
if((left == PLANE_INTERSECTION_BACK)
&& (right == PLANE_INTERSECTION_BACK)
&& (top == PLANE_INTERSECTION_BACK)
&& (bottom == PLANE_INTERSECTION_BACK)
&& (near == PLANE_INTERSECTION_BACK)
&& (far == PLANE_INTERSECTION_BACK))
return false;

[/SOURCE]

Share this post


Link to post
Share on other sites
changing || to && in this case should result in nothing being culled, as every object in 3D space should be in front of one of your frustum planes. For example something behind the right plane should definitely be in front of the left plane and vice versa. So at least one of these == PLANE_INTERSECTION_BACK statements will be false, and the whole if statement will always evaluate to false, therefore everything would seem to intersect with the frustum.

Sry I can´t help with the plane-aabb-test, don´t see anything obviously wrong with that.

Share this post


Link to post
Share on other sites
This is how i extract the frustum:



//////////////////////////////////////////////////////////////////////////
void frustum3_build(const matrix4x4_t* m, frustum3_t* out)
{
frustum3_t frustum;

// left clipping plane
frustum.m_left.m_normal.x = m->_14 + m->_11;
frustum.m_left.m_normal.y = m->_24 + m->_21;
frustum.m_left.m_normal.z = m->_34 + m->_31;
frustum.m_left.m_distance = m->_44 + m->_41;

// right clipping plane
frustum.m_right.m_normal.x = m->_14 - m->_11;
frustum.m_right.m_normal.y = m->_24 - m->_21;
frustum.m_right.m_normal.z = m->_34 - m->_31;
frustum.m_right.m_distance = m->_44 - m->_41;

// top clipping plane
frustum.m_top.m_normal.x = m->_14 - m->_12;
frustum.m_top.m_normal.y = m->_24 - m->_22;
frustum.m_top.m_normal.z = m->_34 - m->_32;
frustum.m_top.m_distance = m->_44 - m->_42;

// bottom clipping plane
frustum.m_bottom.m_normal.x = m->_14 + m->_12;
frustum.m_bottom.m_normal.y = m->_24 + m->_22;
frustum.m_bottom.m_normal.z = m->_34 + m->_32;
frustum.m_bottom.m_distance = m->_44 + m->_42;

// near clipping plane
frustum.m_near.m_normal.x = m->_13;
frustum.m_near.m_normal.y = m->_23;
frustum.m_near.m_normal.z = m->_33;
frustum.m_near.m_distance = m->_43;

// far clipping plane
frustum.m_far.m_normal.x = m->_14 - m->_13;
frustum.m_far.m_normal.y = m->_24 - m->_23;
frustum.m_far.m_normal.z = m->_34 - m->_33;
frustum.m_far.m_distance = m->_44 - m->_43;

*out = frustum;
}



I use this function after multiplying the projection matrix with the view matrix.


matrix4x4_t view_proj_matrix;
matrix4x4_multiply(&view_proj_matrix, &m_view_matrix, &m_projection_matrix);

// build the view frustum
frustum3_build(&view_proj_matrix, &m_view_frustum);


Share this post


Link to post
Share on other sites
If you have a series of planes representing your frustum, and an AABB represented as a centre and postive extent (vector from centre to maximal vertex) then the test is almost trivial:


fCentreDistanceFromPlane = dot(centre, plane_normal) + plane_constant;
fExtentDistanceFromPlane = dot_abs(extent, plane_normal);
if (fCentreDistanceFromPlane < -fExtentDistanceFromPlane)
return CLIP_OUTSIDE;
if (fCentreDistanceFromPlane < fExtentDistanceFromPlane)
return CLIP_INTERSECTING;
// Test next clip plane etc.
// If all planes are tested without intersection or outside, then MUST be inside


Note that dot_abs(a,b) is fabs(a.x*b.x) + fabs(a.y*b.y) + fabs(a.z*b.z) and the normals of the planes face inside the frustum.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this