Jump to content
  • Advertisement
Sign in to follow this  
BlackJoker

False negative result in bounding frustum test

This topic is 723 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 all,

 

I want to implement frustum culling and I now it must be simple thing.

I am using BoundingFrumstum struct from SharpDX (equivalent to the same in D3D 11) and it seems working correctly except one case - when object more than a half is outside the screen, it give false negative result (Tell me that bound box is out of the frustum, but this is not true).

 

At the same time intersection test with the mouse pointing the same "invisible" part, passed without any issues. So, it should be not bounding box issue.

 

I tried creating planes and intersection algorithms with my own, but result was exactly the same.

 

If I understood correctly, frustum intersection tests should return true even if one pixel from the object is still visible (inside frustum), but I have no idea why intersection tests in described conditions return false negative results.

 

Any guess?

Edited by BlackJoker

Share this post


Link to post
Share on other sites
Advertisement

I'm not familiar with the BoundingFrustum class, but are you checking against every corner of the bounding box? Off the top of my head it sounds like you may just be checking its center coordinate. Another possibility could be if you're translating the bounding box (by the world matrix of your respective objects presumably) and somehow doing this incorrectly?

Share this post


Link to post
Share on other sites

No, I tryied different approaches and they all lead to the same result.

Regarding incorrect translation of BB - I am not sure, because all intersection tests passed correctly. If I translate my OBB incorrectly, it must affect intersections too, but its not, So have no idea now. Maybe you cna share your algorithm for frustum culling? Maybe I am missing something here (some space translations or something else?

Share this post


Link to post
Share on other sites

Maybe you cna share your algorithm for frustum culling? Maybe I am missing something here (some space translations or something else?

Certainly, though it is quite old and could probably do with a revision.

I'm using axis aligned bounding boxes by the way, storing the min and max extents along the X/Y/Z axes in object space:

void BoundingBox::Transform(const XMMATRIX& mat, XMFLOAT3& vecMin, XMFLOAT3& vecMax) const {
	XMFLOAT3 coord[8];
	// Front Vertices
	XMStoreFloat3(&coord[0], XMVector3TransformCoord(XMVectorSet(vecBaseMin.x, vecBaseMin.y, vecBaseMin.z, 1.0f), mat));
	XMStoreFloat3(&coord[1], XMVector3TransformCoord(XMVectorSet(vecBaseMin.x, vecBaseMax.y, vecBaseMin.z, 1.0f), mat));
	XMStoreFloat3(&coord[2], XMVector3TransformCoord(XMVectorSet(vecBaseMax.x, vecBaseMax.y, vecBaseMin.z, 1.0f), mat));
	XMStoreFloat3(&coord[3], XMVector3TransformCoord(XMVectorSet(vecBaseMax.x, vecBaseMin.y, vecBaseMin.z, 1.0f), mat));
	// Back Vertices
	XMStoreFloat3(&coord[4], XMVector3TransformCoord(XMVectorSet(vecBaseMin.x, vecBaseMin.y, vecBaseMax.z, 1.0f), mat));
	XMStoreFloat3(&coord[5], XMVector3TransformCoord(XMVectorSet(vecBaseMax.x, vecBaseMin.y, vecBaseMax.z, 1.0f), mat));
	XMStoreFloat3(&coord[6], XMVector3TransformCoord(XMVectorSet(vecBaseMax.x, vecBaseMax.y, vecBaseMax.z, 1.0f), mat));
	XMStoreFloat3(&coord[7], XMVector3TransformCoord(XMVectorSet(vecBaseMin.x, vecBaseMax.y, vecBaseMax.z, 1.0f), mat));
}
void Camera::ReconstructFrustumPlanes() {
	// Left Frustum Plane
        // Add first column of the matrix to the fourth column
	frustumPlane[0].a = viewProj._14 + viewProj._11; 
	frustumPlane[0].b = viewProj._24 + viewProj._21;
	frustumPlane[0].c = viewProj._34 + viewProj._31;
	frustumPlane[0].d = viewProj._44 + viewProj._41;

	// Right frustum Plane
        // Subtract first column of matrix from the fourth column
	frustumPlane[1].a = viewProj._14 - viewProj._11; 
	frustumPlane[1].b = viewProj._24 - viewProj._21;
	frustumPlane[1].c = viewProj._34 - viewProj._31;
	frustumPlane[1].d = viewProj._44 - viewProj._41;

	// Top frustum Plane
        // Subtract second column of matrix from the fourth column
	frustumPlane[2].a = viewProj._14 - viewProj._12; 
	frustumPlane[2].b = viewProj._24 - viewProj._22;
	frustumPlane[2].c = viewProj._34 - viewProj._32;
	frustumPlane[2].d = viewProj._44 - viewProj._42;

	// Bottom frustum Plane
        // Add second column of the matrix to the fourth column
	frustumPlane[3].a = viewProj._14 + viewProj._12;
	frustumPlane[3].b = viewProj._24 + viewProj._22;
	frustumPlane[3].c = viewProj._34 + viewProj._32;
	frustumPlane[3].d = viewProj._44 + viewProj._42;

	// Near frustum Plane
        // We could add the third column to the fourth column to get the near plane,
        // but we don't have to do this because the third column IS the near plane
	frustumPlane[4].a = viewProj._13;
	frustumPlane[4].b = viewProj._23;
	frustumPlane[4].c = viewProj._33;
	frustumPlane[4].d = viewProj._43;

	// Far frustum Plane
        // Subtract third column of matrix from the fourth column
	frustumPlane[5].a = viewProj._14 - viewProj._13; 
	frustumPlane[5].b = viewProj._24 - viewProj._23;
	frustumPlane[5].c = viewProj._34 - viewProj._33;
	frustumPlane[5].d = viewProj._44 - viewProj._43;


	// Normalize planes
	for(unsigned int p = 0; p < 6; p++) {
		float length = sqrt(
                    (frustumPlane[p].a * frustumPlane[p].a) + 
                    (frustumPlane[p].b * frustumPlane[p].b) + 
                    (frustumPlane[p].c * frustumPlane[p].c)
                );
		frustumPlane[p].a /= length;
		frustumPlane[p].b /= length;
		frustumPlane[p].c /= length;
		frustumPlane[p].d /= length;
	}
}
bool Camera::FrustumCullBoundingBox(const XMFLOAT3 &vecMin, const XMFLOAT3& vecMax) {
	for(unsigned int p = 0; p < 6; p++) {
		if(XMlaneDotCoord(&frustumPlane[p], &XMVectorSet(vecMin.x, vecMin.y, vecMin.z, 1)) >= 0.0f)
			continue;
		if(XMPlaneDotCoord(&frustumPlane[p], &XMVectorSet(vecMax.x, vecMin.y, vecMin.z, 1)) >= 0.0f)
			continue;
		if(XMPlaneDotCoord(&frustumPlane[p], &XMVectorSet(vecMin.x, vecMax.y, vecMin.z, 1)) >= 0.0f)
			continue;
		if(XMPlaneDotCoord(&frustumPlane[p], &XMVectorSet(vecMin.x, vecMin.y, vecMax.z, 1)) >= 0.0f)
			continue;
		if(XMPlaneDotCoord(&frustumPlane[p], &XMVectorSet(vecMax.x, vecMax.y, vecMin.z, 1)) >= 0.0f)
			continue;
		if(XMPlaneDotCoord(&frustumPlane[p], &XMVectorSet(vecMax.x, vecMin.y, vecMax.z, 1)) >= 0.0f)
			continue;
		if(XMPlaneDotCoord(&frustumPlane[p], &XMVectorSet(vecMin.x, vecMax.y, vecMax.z, 1)) >= 0.0f)
			continue;
		if(XMPlaneDotCoord(&frustumPlane[p], &XMVectorSet(vecMax.x, vecMax.y, vecMax.z, 1)) >= 0.0f)
			continue;
		return false;
	}
	return true;
}
Edited by Husbjörn

Share this post


Link to post
Share on other sites

I found out that those parts, on which algorithm says they are not visible, really not visible according to boundingbox projection.

To check this I have projected 8 bounding corners of each box and checked them with my screen rectangle Rectangle.Contains() method.

By default width of my window is 918 pixels, but when I project all 8 corners, I see that nearest X coordinate for "invisible" mesh is 920.

So, its out of the screen and should not be visible. 

But the fact is that it is really not out of the screen and still fully visible.

 

I decided that there something wrong with my oriented bounding box, but this is really strange, because I am updating it with mesh world matrix and OBB should contains correct data (including scale).

 

After that I made another test and get vertex array from vertex buffer, create separate BB from positions array. Then I get its corners and tranform them by world matrix.

 

Then I done this:

for (int i = 0; i < boundCorners.Length; i++)
                           {
                              var point = Vector3.TransformCoordinate(boundCorners[i], worldMatrix);
                              Vector3 screenPos = presenter.Viewport.Project(point, activeCamera.ProjectionMatrix,
                                 activeCamera.ViewMatrix, Matrix.Identity);
                              screenPos.X -= presenter.Viewport.X;
                              screenPos.Y -= presenter.Viewport.Y;

                              if (screenRectangle.Contains(screenPos.X, screenPos.Y))
                              {
                                 intersects = ContainmentType.Contains;
                                 break;
                              }
                           }

And got exactly the same result.

 

Also I have noticed that this bug is not related to all models.I have small scene where 5 shapes present and on that scene frustum works perfectly. All objects stays visible until camera will moved away.

O_o

Edited by BlackJoker

Share this post


Link to post
Share on other sites

Ok, after spending the whole day of debugging I finally fixed this issue:

The root cause of the issue was that OrientedBoundingBox.GetCorners() method returns incorrect points. I don`t know why this is happening, especially that I update my OBB matrix and scale each frame and it should be correct.

But If I get corners from basic OBB (without any transformations applied) and transform all these points with my World matrix with Vector3.TransformCoord(), then issue will gone and all frustum checks goes correctly.

That is very strange issue.

 

Here is SharpdX OBB code for GetCorners()

Is there anything wrong with it:

/// <summary>
      /// Retrieves the eight corners of the bounding box.
      /// </summary>
      /// <returns>An array of points representing the eight corners of the bounding box.</returns>
      public Vector3[] GetCorners()
      {
         var xv = new Vector3(Extents.X, 0, 0);
         var yv = new Vector3(0, Extents.Y, 0);
         var zv = new Vector3(0, 0, Extents.Z);
         Vector3.TransformNormal(ref xv, ref Transformation, out xv);
         Vector3.TransformNormal(ref yv, ref Transformation, out yv);
         Vector3.TransformNormal(ref zv, ref Transformation, out zv);

         var center = Transformation.TranslationVector;

         var corners = new Vector3[8];
         corners[0] = center + xv + yv + zv;
         corners[1] = center + xv + yv - zv;
         corners[2] = center - xv + yv - zv;
         corners[3] = center - xv + yv + zv;
         corners[4] = center + xv - yv + zv;
         corners[5] = center + xv - yv - zv;
         corners[6] = center - xv - yv - zv;
         corners[7] = center - xv - yv + zv;

         return corners;
      }
Edited by BlackJoker

Share this post


Link to post
Share on other sites

Finally, I have found an issue.

I found out that OrientedBoundingBox struct from SharpDX is broken and its really has nothing to do with oriented box.

So, when I update OBB, it produce incorrect results and bounding boxes placing is incorrect. That was the reason of this issue.

 

One of the possible solutions - get original BB without transformations. Then get corners and Transform coordinates with mesh Matrix and after that check with Frustum.

Edited by BlackJoker

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!