Jump to content

  • Log In with Google      Sign In   
  • Create Account


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.

  • You cannot reply to this topic
5 replies to this topic

#1 Devero   GDNet+   -  Reputation: 216

Like
0Likes
Like

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

 



Sponsor:

#2 Tournicoti   Prime Members   -  Reputation: 683

Like
4Likes
Like

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 ! smile.png

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.


#3 DT....   Members   -  Reputation: 487

Like
1Likes
Like

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



#4 Tournicoti   Prime Members   -  Reputation: 683

Like
1Likes
Like

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 smile.png

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.


#5 EWClay   Members   -  Reputation: 659

Like
1Likes
Like

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.

#6 Devero   GDNet+   -  Reputation: 216

Like
0Likes
Like

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.



PARTNERS