• Create Account

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

2 replies to this topic

### #1newtechnology  Members

1549
Like
0Likes
Like

Posted 09 May 2014 - 12:50 AM

XNACollision does this for testing a AABB-frustum. It converts AABB to OBB and then does intersection tests.

Isn't this complex/slower compared to AABB-frustum test?

//-----------------------------------------------------------------------------
// Exact axis alinged box vs frustum test.  Constructs an oriented box and uses
// the oriented box vs frustum test.
//
// Return values: 0 = no intersection,
//                1 = intersection,
//                2 = box is completely inside frustum
//-----------------------------------------------------------------------------
INT IntersectAxisAlignedBoxFrustum( const AxisAlignedBox* pVolumeA, const Frustum* pVolumeB )
{
XMASSERT( pVolumeA );
XMASSERT( pVolumeB );

// Make the axis aligned box oriented and do an OBB vs frustum test.
OrientedBox BoxA;

BoxA.Center = pVolumeA->Center;
BoxA.Extents = pVolumeA->Extents;
BoxA.Orientation.x = 0.0f;
BoxA.Orientation.y = 0.0f;
BoxA.Orientation.z = 0.0f;
BoxA.Orientation.w = 1.0f;

return IntersectOrientedBoxFrustum( &BoxA, pVolumeB );
}

INT IntersectOrientedBoxFrustum( const OrientedBox* pVolumeA, const Frustum* pVolumeB )
{
XMASSERT( pVolumeA );
XMASSERT( pVolumeB );

static const XMVECTORI32 SelectY =
{
XM_SELECT_0, XM_SELECT_1, XM_SELECT_0, XM_SELECT_0
};
static const XMVECTORI32 SelectZ =
{
XM_SELECT_0, XM_SELECT_0, XM_SELECT_1, XM_SELECT_0
};

XMVECTOR Zero = XMVectorZero();

// Build the frustum planes.
XMVECTOR Planes[6];
Planes[0] = XMVectorSet( 0.0f, 0.0f, -1.0f, pVolumeB->Near );
Planes[1] = XMVectorSet( 0.0f, 0.0f, 1.0f, -pVolumeB->Far );
Planes[2] = XMVectorSet( 1.0f, 0.0f, -pVolumeB->RightSlope, 0.0f );
Planes[3] = XMVectorSet( -1.0f, 0.0f, pVolumeB->LeftSlope, 0.0f );
Planes[4] = XMVectorSet( 0.0f, 1.0f, -pVolumeB->TopSlope, 0.0f );
Planes[5] = XMVectorSet( 0.0f, -1.0f, pVolumeB->BottomSlope, 0.0f );

// Load origin and orientation of the frustum.
XMVECTOR Origin = XMLoadFloat3( &pVolumeB->Origin );
XMVECTOR FrustumOrientation = XMLoadFloat4( &pVolumeB->Orientation );

XMASSERT( XMQuaternionIsUnit( FrustumOrientation ) );

XMVECTOR Center = XMLoadFloat3( &pVolumeA->Center );
XMVECTOR Extents = XMLoadFloat3( &pVolumeA->Extents );
XMVECTOR BoxOrientation = XMLoadFloat4( &pVolumeA->Orientation );

XMASSERT( XMQuaternionIsUnit( BoxOrientation ) );

// Transform the oriented box into the space of the frustum in order to
// minimize the number of transforms we have to do.
Center = XMVector3InverseRotate( Center - Origin, FrustumOrientation );
BoxOrientation = XMQuaternionMultiply( BoxOrientation, XMQuaternionConjugate( FrustumOrientation ) );

// Set w of the center to one so we can dot4 with the plane.
Center = XMVectorInsert( Center, XMVectorSplatOne(), 0, 0, 0, 0, 1);

// Build the 3x3 rotation matrix that defines the box axes.
XMMATRIX R = XMMatrixRotationQuaternion( BoxOrientation );

// Check against each plane of the frustum.
XMVECTOR Outside = XMVectorFalseInt();
XMVECTOR InsideAll = XMVectorTrueInt();
XMVECTOR CenterInsideAll = XMVectorTrueInt();

for( INT i = 0; i < 6; i++ )
{
// Compute the distance to the center of the box.
XMVECTOR Dist = XMVector4Dot( Center, Planes[i] );

// Project the axes of the box onto the normal of the plane.  Half the
// length of the projection (sometime called the "radius") is equal to
// h(u) * abs(n dot b(u))) + h(v) * abs(n dot b(v)) + h(w) * abs(n dot b(w))
// where h(i) are extents of the box, n is the plane normal, and b(i) are the
// axes of the box.
XMVECTOR Radius = XMVector3Dot( Planes[i], R.r[0] );

// Outside the plane?
Outside = XMVectorOrInt( Outside, XMVectorGreater( Dist, Radius ) );

// Fully inside the plane?
InsideAll = XMVectorAndInt( InsideAll, XMVectorLessOrEqual( Dist, -Radius ) );

// Check if the center is inside the plane.
CenterInsideAll = XMVectorAndInt( CenterInsideAll, XMVectorLessOrEqual( Dist, Zero ) );
}

// If the box is outside any of the planes it is outside.
if ( XMVector4EqualInt( Outside, XMVectorTrueInt() ) )
return 0;

// If the box is inside all planes it is fully inside.
if ( XMVector4EqualInt( InsideAll, XMVectorTrueInt() ) )
return 2;

// If the center of the box is inside all planes and the box intersects
// one or more planes then it must intersect.
if ( XMVector4EqualInt( CenterInsideAll, XMVectorTrueInt() ) )
return 1;

// Build the corners of the frustum.
XMVECTOR RightTop = XMVectorSet( pVolumeB->RightSlope, pVolumeB->TopSlope, 1.0f, 0.0f );
XMVECTOR RightBottom = XMVectorSet( pVolumeB->RightSlope, pVolumeB->BottomSlope, 1.0f, 0.0f );
XMVECTOR LeftTop = XMVectorSet( pVolumeB->LeftSlope, pVolumeB->TopSlope, 1.0f, 0.0f );
XMVECTOR LeftBottom = XMVectorSet( pVolumeB->LeftSlope, pVolumeB->BottomSlope, 1.0f, 0.0f );
XMVECTOR Near = XMVectorReplicatePtr( &pVolumeB->Near );
XMVECTOR Far = XMVectorReplicatePtr( &pVolumeB->Far );

XMVECTOR Corners[8];
Corners[0] = RightTop * Near;
Corners[1] = RightBottom * Near;
Corners[2] = LeftTop * Near;
Corners[3] = LeftBottom * Near;
Corners[4] = RightTop * Far;
Corners[5] = RightBottom * Far;
Corners[6] = LeftTop * Far;
Corners[7] = LeftBottom * Far;

// Test against box axes (3)
{
// Find the min/max values of the projection of the frustum onto each axis.
XMVECTOR FrustumMin, FrustumMax;

FrustumMin = XMVector3Dot( Corners[0], R.r[0] );
FrustumMin = XMVectorSelect( FrustumMin, XMVector3Dot( Corners[0], R.r[1] ), SelectY );
FrustumMin = XMVectorSelect( FrustumMin, XMVector3Dot( Corners[0], R.r[2] ), SelectZ );
FrustumMax = FrustumMin;

for( INT i = 1; i < 8; i++ )
{
XMVECTOR Temp = XMVector3Dot( Corners[i], R.r[0] );
Temp = XMVectorSelect( Temp, XMVector3Dot( Corners[i], R.r[1] ), SelectY );
Temp = XMVectorSelect( Temp, XMVector3Dot( Corners[i], R.r[2] ), SelectZ );

FrustumMin = XMVectorMin( FrustumMin, Temp );
FrustumMax = XMVectorMax( FrustumMax, Temp );
}

// Project the center of the box onto the axes.
XMVECTOR BoxDist = XMVector3Dot( Center, R.r[0] );
BoxDist = XMVectorSelect( BoxDist, XMVector3Dot( Center, R.r[1] ), SelectY );
BoxDist = XMVectorSelect( BoxDist, XMVector3Dot( Center, R.r[2] ), SelectZ );

// The projection of the box onto the axis is just its Center and Extents.
// if (min > box_max || max < box_min) reject;
XMVECTOR Result = XMVectorOrInt( XMVectorGreater( FrustumMin, BoxDist + Extents ),
XMVectorLess( FrustumMax, BoxDist - Extents ) );

if( XMVector3AnyTrue( Result ) )
return 0;
}

// Test against edge/edge axes (3*6).
XMVECTOR FrustumEdgeAxis[6];

FrustumEdgeAxis[0] = RightTop;
FrustumEdgeAxis[1] = RightBottom;
FrustumEdgeAxis[2] = LeftTop;
FrustumEdgeAxis[3] = LeftBottom;
FrustumEdgeAxis[4] = RightTop - LeftTop;
FrustumEdgeAxis[5] = LeftBottom - LeftTop;

for( INT i = 0; i < 3; i++ )
{
for( INT j = 0; j < 6; j++ )
{
// Compute the axis we are going to test.
XMVECTOR Axis = XMVector3Cross( R.r[i], FrustumEdgeAxis[j] );

// Find the min/max values of the projection of the frustum onto the axis.
XMVECTOR FrustumMin, FrustumMax;

FrustumMin = FrustumMax = XMVector3Dot( Axis, Corners[0] );

for( INT k = 1; k < 8; k++ )
{
XMVECTOR Temp = XMVector3Dot( Axis, Corners[k] );
FrustumMin = XMVectorMin( FrustumMin, Temp );
FrustumMax = XMVectorMax( FrustumMax, Temp );
}

// Project the center of the box onto the axis.
XMVECTOR Dist = XMVector3Dot( Center, Axis );

// Project the axes of the box onto the axis to find the "radius" of the box.
XMVECTOR Radius = XMVector3Dot( Axis, R.r[0] );

// if (center > max + radius || center < min - radius) reject;
Outside = XMVectorOrInt( Outside, XMVectorGreater( Dist, FrustumMax + Radius ) );
Outside = XMVectorOrInt( Outside, XMVectorLess( Dist, FrustumMin - Radius ) );
}
}

if ( XMVector4EqualInt( Outside, XMVectorTrueInt() ) )
return 0;

// If we did not find a separating plane then the box must intersect the frustum.
return 1;
}


Edited by newtechnology, 09 May 2014 - 12:57 AM.

### #2newtechnology  Members

1549
Like
0Likes
Like

Posted 09 May 2014 - 12:56 AM

XNACollision does this for testing a AABB-frustum. It converts AABB to OBB and then does intersection tests.

Isn't this complex/slower compared to AABB-frustum test?

//-----------------------------------------------------------------------------
// Exact axis alinged box vs frustum test.  Constructs an oriented box and uses
// the oriented box vs frustum test.
//
// Return values: 0 = no intersection,
//                1 = intersection,
//                2 = box is completely inside frustum
//-----------------------------------------------------------------------------
INT IntersectAxisAlignedBoxFrustum( const AxisAlignedBox* pVolumeA, const Frustum* pVolumeB )
{
XMASSERT( pVolumeA );
XMASSERT( pVolumeB );

// Make the axis aligned box oriented and do an OBB vs frustum test.
OrientedBox BoxA;

BoxA.Center = pVolumeA->Center;
BoxA.Extents = pVolumeA->Extents;
BoxA.Orientation.x = 0.0f;
BoxA.Orientation.y = 0.0f;
BoxA.Orientation.z = 0.0f;
BoxA.Orientation.w = 1.0f;

return IntersectOrientedBoxFrustum( &BoxA, pVolumeB );
}

Wouldn't this be faster than it?

bool Camera::isVisible(const AABB& box)const
{
// Test assumes frustum planes face inward.

D3DXVECTOR3 P;
D3DXVECTOR3 Q;

//      N  *Q                    *P
//      | /                     /
//      |/                     /
// -----/----- Plane     -----/----- Plane
//     /                     / |
//    /                     /  |
//   *P                    *Q  N
//
// PQ forms diagonal most closely aligned with plane normal.

// For each frustum plane, find the box diagonal (there are four main
// diagonals that intersect the box center point) that points in the
// same direction as the normal along each axis (i.e., the diagonal
// that is most aligned with the plane normal).  Then test if the box
// is in front of the plane or not.
for(int i = 0; i < 6; ++i)
{
// For each coordinate axis x, y, z...
for(int j = 0; j < 3; ++j)
{
// Make PQ point in the same direction as the plane normal on this axis.
if( mFrustumPlanes[i][j] >= 0.0f )
{
P[j] = box.minPt[j];
Q[j] = box.maxPt[j];
}
else
{
P[j] = box.maxPt[j];
Q[j] = box.minPt[j];
}
}

// If box is in negative half space, it is behind the plane, and thus, completely
// outside the frustum.  Note that because PQ points roughly in the direction of the
// plane normal, we can deduce that if Q is outside then P is also outside--thus we
// only need to test Q.
if( D3DXPlaneDotCoord(&mFrustumPlanes[i], &Q) < 0.0f  ) // outside
return false;
}
return true;
}

EDIT: Oops. With a mistake, instead of editing thread, I posted a new post.

Edited by newtechnology, 09 May 2014 - 12:56 AM.

### #3newtechnology  Members

1549
Like
0Likes
Like

Posted 22 May 2014 - 09:26 AM

Anyone?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.