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

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

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

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.

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.

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;

}