# Finding a point inside a Pyramid

This topic is 1916 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

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, vDelta );
float fDistance = DotProduct( vDelta, vNormal );

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, vDelta );
float fDistance = DotProduct( vDelta, vNormal );

float fPlaneDistance = DotProduct( v1, vNormal );

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
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

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;

}


• 16
• 9
• 13
• 41
• 15