\$25

### Image of the Day Submit

IOTD | Top Screenshots

## Finding a point inside a Pyramid

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.

5 replies to this topic

### #1Devero  Members

Posted 24 February 2013 - 08:36 PM

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 );
}



### #2Tournicoti  Prime Members

Posted 24 February 2013 - 09:49 PM

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, 25 February 2013 - 03:42 AM.

### #3DT....  Members

Posted 24 February 2013 - 10:37 PM

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

### #4Tournicoti  Prime Members

Posted 25 February 2013 - 03:19 AM

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, 25 February 2013 - 03:23 AM.

### #5EWClay  Members

Posted 25 February 2013 - 03:47 AM

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.

### #6Devero  Members

Posted 25 February 2013 - 08:55 AM

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;

}


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.