Finding a point inside a Pyramid

Recommended Posts

Devero    218

Hi there.  I'm rather green on some of the collision detection/geometry vector math.  I have a Pyramid volume that I want to check to see if a point resides inside of that volume.  I've been looking to find a fast and efficient computation.  I've pieced together the below information from online and some books and its not working right.  I'm always getting a positive value for the scalars.  Is there faster way to do and any suggestion of what i'm doing wrong?

Thanks,

Devero



//Mathematic approach
//1)Calculate the normal for each of the four faces.
//2)choose a point inside each face (one of the vertices for example) and calculate the vector between it and the point you are looking for (r-ri)
//3)Next calculate the inner product(DOT) between this vector and the face normal - the result is a scalar
//4)The point is inside the polygon if the four scalars are negative.

bool CCommandGUI::PointInsidePyramid( const Vector& vPointTest, Vector v1[4], Vector vNormal[4] )
{
for( int i = 0; i < 4; i++ )  //loop through each triangle face
{
Vector vDelta;
VectorSubtract( vPointTest, v1[i], vDelta );
float fDistance = DotProduct( vDelta, vNormal[i] );

if( fDistance > 0 )
return false;
}

return true;

}

//My Normal code
void CCommandGUI::CalculateTriangleNormal( const Vector& v1, const Vector& v2, const Vector& v3, Vector& vNormal )
{
Vector edge1, edge2;
VectorSubtract( v2, v1, edge1 );
VectorSubtract( v3, v1, edge2 );

Vector normal;
CrossProduct( edge1, edge2, normal );
vNormal = normal.Normalized();
}

void CCommandGUI::CaluclatePyramid( Vector vecApex, Vector vecP0, Vector vecP1, Vector vecP2, Vector vecP3, Vector vecTestPoint )
{
//Draw the Pyramid
NDebugOverlay::Triangle( vecApex, vecP0, vecP1, 255, 0, 0, 64, true , 10.02f );  //side  0|1
NDebugOverlay::Triangle( vecApex, vecP1, vecP3, 255, 0, 0, 64, true , 10.02f );  //side  1|3
NDebugOverlay::Triangle( vecApex, vecP3, vecP2, 255, 0, 0, 64, true , 10.02f );  //side  3|2
NDebugOverlay::Triangle( vecApex, vecP2, vecP0, 255, 0, 0, 64, true , 10.02f );  //side  2|0

//Lets calculate stuff here
Vector vecNormal;
Vector vArrayNormal[4];
Vector vPyramidApex[4];
CalculateTriangleNormal( vecApex, vecP0, vecP1, vecNormal );
vArrayNormal[0]=vecNormal;
CalculateTriangleNormal( vecApex, vecP1, vecP3, vecNormal );
vArrayNormal[1]=vecNormal;
CalculateTriangleNormal( vecApex, vecP3, vecP2, vecNormal );
vArrayNormal[2]=vecNormal;
CalculateTriangleNormal( vecApex, vecP2, vecP0, vecNormal );
vArrayNormal[3]=vecNormal;

vPyramidApex[0] = vPyramidApex[1] = vPyramidApex[2] = vPyramidApex[3] = vecApex;
bool isInside = PointInsidePyramid( vecTestPoint, vPyramidApex, vArrayNormal );
}



Share on other sites

A pyramid is a convex volume, so if you can check your point against the 4 planes defining your pyramid, it's done !

So, just compute the 4 planes equations and check if your point is 'below'(in term of half-spaces) all the planes.

Good luck

Edited by Tournicoti

Share on other sites
DonTzzy    487

bool CCommandGUI::PointInsidePyramid( const Vector& vPointTest, Vector v1[4], Vector vNormal[4] )
{
for( int i = 0; i < 4; i++ ) //loop through each triangle face
{
Vector vDelta;
VectorSubtract( vPointTest, v1[i], vDelta );
float fDistance = DotProduct( vDelta, vNormal[i] );

if( fDistance > 0 )
return false;
}

return true;

}

Looks like a subtraction might be missing.

for( int i = 0; i < 4; i++ ) //loop through each triangle face
{
Vector vDelta;
VectorSubtract( vPointTest, v1[i], vDelta );
float fDistance = DotProduct( vDelta, vNormal[i] );

float fPlaneDistance = DotProduct( v1[i], vNormal[i] );

fDistance -= fPlaneDistance;

if( fDistance > 0 )
return false;
}

Share on other sites

I add some code to help to see how it's possible to implement that :

	class PlaneD // a class that describes a plane, with a normal and a distance
{
public:
D3DXVECTOR3 normal;
float distance;

PlaneD(D3DXVECTOR3 & n,D3DXVECTOR3 & p) // a constructor, given the normal and a point of the plane
:normal(n)
,distance(D3DXVec3Dot(&n,&p))
{}
};

// ... and 2 functions I use to check if a point is 'behind' a plane :

float computePointPlaneDistance(PlaneD & plane,D3DXVECTOR3 & point)
{
return D3DXVec3Dot(&plane.normal,&point)-plane.distance;
}

bool pointBehindPlane(D3DXVECTOR3 & point,PlaneD & plane)
{
return computePointPlaneDistance(plane,point)<=0.0f;
}


As you can see I use D3DX API. You can just replace D3DXVECTOR3, D3DXVec3Dot with your own code.

Hope it helps

EDIT : Be sure to use normalized vector for the plane's normal, otherwise the calculations of the distances will be wrong.

Edited by Tournicoti

Share on other sites
EWClay    659
The method looks correct so a little debugging should get it working.

You are not checking the bottom face, which may or may not be necessary in your case.

There is no faster method; however you could precalculate the normals.

Share on other sites
Devero    218

Thanks for the help guys, I was doing a little extra vector subtraction that I didn't need to do.   Below is all I had to do find the 4 sides, now I can just add the the base plane and I'm good.!  Thanks again.

-Devero


bool CCommandGUI::PointInsidePyramid( const Vector& vPointTest, Vector vPyramidBase[4], Vector vNormal[4], const Vector& vPyramidApex )
{
for( int i = 0; i < 4; i++ )  //loop through each triangle face
{
float fPlaneDistance = -DotProduct( vPyramidApex, vNormal[i] );
float fDistance = DotProduct( vPointTest, vNormal[i] );
fDistance += fPlaneDistance;

if( fDistance < 0 )
return false;

}

return true;

}