Removing meshes by camera view and bounding box?

[cronodragon]

I'm making an optimization method to remove those meshes at are out of the camera's view. I have the bounding box of the mesh, and the transformation. I think the idea would be to compare, using a function, if any point of the bounding box is inside the view of the camera, based on it's projection, aperture, and range. Is there any helper function to detect this in DirectX 9, or do I have to build my own? Thanks in advance.

[JernejL]

you are describing viewing frustum culling: http://en.wikipedia.org/wiki/Frustum_culling

[NecroDOME]

Maybe this will hlep:

[pascal]
uses
D3DX9, Direct3D9;

const
FRUSTUM_IN = 0;
FRUSTUM_INTERSECT = 1;
FRUSTUM_OUT = 2;

FRUSTRUM_LEFT = 0;
FRUSTRUM_RIGHT = 1;
FRUSTRUM_BOTTOM = 2;
FRUSTRUM_TOP = 3;
FRUSTRUM_BACK = 4;
FRUSTRUM_FRONT = 5;

type
// Frustom class
TNecro3D_Frustum = class
private
procedure SetPlaneCoefficients(Index : integer; a, b, c, d : single);
public
Frustum : array[0..5,0..3] of Single;
Planes: array [0..5] of TD3DXPlane;
constructor Create;
procedure LoadFrustum(mView, mProjection: TD3DMatrix);
function ContainsSphere(Pos : TD3DVector; Radius : single) : boolean;
function ContainsPoint(Pos: TD3DVector): boolean;
end;


implementation

{ TNecro3D_Frustum }

//************************************************** ************
// Check if frustum contains a point
//************************************************** ************
function TNecro3D_Frustum.ContainsPoint(Pos: TD3DVector): boolean;
var i : Integer;
begin
Result := True;
for i := 0 to 5 do
with Planes[i] do
if (a*Pos.X + b*Pos.Y + c*Pos.Z + d) <= -1 then
begin
Result := False;
Exit;
end;
end;

//************************************************** ************
// Check if sphere is inside frustrum
//************************************************** ************
function TNecro3D_Frustum.ContainsSphere(Pos: TD3DVector;
Radius: single): boolean;
var i : Integer;
begin
Result := True;
for i := 0 to 5 do
with Planes[i] do
if (a*Pos.X + b*Pos.Y + c*Pos.Z + d) <= -Radius then
begin
Result := False;
Exit;
end;
end;

//************************************************** ************
// Create viewing frustum
//************************************************** ************
constructor TNecro3D_Frustum.Create;
begin
;
end;

//************************************************** ************
// Extract planes from viewing frustum
//************************************************** ************
procedure TNecro3D_Frustum.LoadFrustum(mView, mProjection: TD3DMatrix);
var Mat : TD3DMatrix;
begin
D3DXMatrixMultiply( Mat, mView, mProjection );

SetPlaneCoefficients(FRUSTRUM_LEFT, Mat._14+Mat._11,
Mat._24+Mat._21,
Mat._34+Mat._31,
Mat._44+Mat._41);

SetPlaneCoefficients(FRUSTRUM_RIGHT, Mat._14-Mat._11,
Mat._24-Mat._21,
Mat._34-Mat._31,
Mat._44-Mat._41);

SetPlaneCoefficients(FRUSTRUM_BOTTOM,Mat._14+Mat._ 12,
Mat._24+Mat._22,
Mat._34+Mat._32,
Mat._44+Mat._42);

SetPlaneCoefficients(FRUSTRUM_TOP, Mat._14-Mat._12,
Mat._24-Mat._22,
Mat._34-Mat._32,
Mat._44-Mat._42);

SetPlaneCoefficients(FRUSTRUM_BACK, Mat._14 + Mat._13,
Mat._24 + Mat._23,
Mat._34 + Mat._33,
Mat._44 + Mat._43);

SetPlaneCoefficients(FRUSTRUM_FRONT, Mat._14-Mat._13,
Mat._24-Mat._23,
Mat._34-Mat._33,
Mat._44-Mat._43);
end;

//************************************************** ************
// Set Plane Coefficients
//************************************************** ************
procedure TNecro3D_Frustum.SetPlaneCoefficients(Index: integer; a, b, c,
d: single);
var Mag : single;
begin
Mag := Sqrt((a*a)+(b*b)+(c*c));

Planes[Index].a := a/Mag;
Planes[Index].b := b/Mag;
Planes[Index].c := c/Mag;
Planes[Index].d := d/Mag;
end;
[/pascal]

[cronodragon]

That code is nice, thanks NecroDOME. But what about the case in which points are not contained in the frustrum?:

          _________________
          \    frustrum   /    not contained points
       *---------------------*
       |    \           /    |
       |     \         /  box|
       *---------------------*
               \_____/

[tpascal]

This is the one i am using, which include those case like you describe:

But note, this is for (AABB) AXIS ALIGNED BOUNDING BOX ONLY. for Oriented Object bounding box(OOBB) this will not work.

[pascal]
function FexDX_frustumAABoxInside(_min, _max : t_Vec;
_f : tFrustum): boolean;

// _min & _max - define the axis aligned box
//

var _i : longint;
_amin, _amax, _bmin, _bmax, _cmin, _cmax : single;

begin
for _i := 0 to 5 do
begin
_amin := _f[_i].a * _min[0];
_bmin := _f[_i].b * _min[1];
_cmin := _f[_i].c * _min[2];

if (_amin + _bmin + _cmin + _f[_i].d > 0) then continue;

_amax := _f[_i].a * _max[0];

if (_amax + _bmin + _cmin + _f[_i].d > 0) then continue;

_bmax := _f[_i].b * _max[1];

if (_amin + _bmax + _cmin + _f[_i].d > 0) then continue;
if (_amax + _bmax + _cmin + _f[_i].d > 0) then continue;

_cmax := _f[_i].c * _max[2];

if (_amin + _bmin + _cmax + _f[_i].d > 0) then continue;
if (_amax + _bmin + _cmax + _f[_i].d > 0) then continue;
if (_amin + _bmax + _cmax + _f[_i].d > 0) then continue;
if (_amax + _bmax + _cmax + _f[_i].d > 0) then continue;

Result := false;
exit;
end;
Result := true
end;
[/pascal]

With Today hardware most likely it is not longer needed to check every triangle inthe mesh once the above test return true; but here is the triangle in frustum function is you need it.


[pascal]
function FexDx_frustumTriangleInside(_v1, _v2, _v3 : t_Vec;
_f : tFrustum): boolean;


// Warning: This function is very fast but in fact it is checking the whole rectangular area
// conformed by the 3 vertices.
// Also it will return TRue if the triangle is seen from behind.

//I think it is very usefull to let return true when the triangleis seen from behind, so we can use
//this function for checking bounding boxes from inside/outside.

var _i : longint;

begin
for _i := 0 to 5 do
begin
if (_f[_i].a * _v1[0] + _f[_i].b * _v1[1] + _f[_i].c * _v1[2] + _f[_i].d > 0) then continue;
if (_f[_i].a * _v2[0] + _f[_i].b * _v2[1] + _f[_i].c * _v2[2] + _f[_i].d > 0) then continue;
if (_f[_i].a * _v3[0] + _f[_i].b * _v3[1] + _f[_i].c * _v3[2] + _f[_i].d > 0) then continue;
// Outside
Result := false;
exit;
end;
Result := true;
end;
[/pascal]