Archived

This topic is now archived and is closed to further replies.

looking for a faster way to determine if a polygon is inside a Box

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I wrote a method to determine if a polygon is partially or entirely contained within a bounding box. The box is defined by 6 planes facing inward and a set of 8 verticies. This is what i got:
bool isContained(BoundingBox * boundingBox, CollisionFace * face)
{
if ( 
  face->infrontOf(boundingBox->front) &&
  face->infrontOf(boundingBox->back)  &&
  face->infrontOf(boundingBox->top)   &&
  face->infrontOf(boundingBox->bottom)&&
  face->infrontOf(boundingBox->left)  &&
  face->infrontOf(boundingBox->right) )
{
 //CHECK FURTHER:
 // IF ALL POINTS FROM OUR BOX ARE ALL BEHIND OR ALL ARE INFRONT 
 // OF PLANE OF THE FACE WE HAVE JUST FOUND THEN IT DOES NOT  
 // COLLIDE
 Points * boxVerticies = boundingBox->getBoxVerticies();
 PointSign sign;
 sign = face->plane.whereIsPoint(boxVerticies[0]);

//CHECK THE face with the 8 verticies of the box 
 for (int j = 1; j < 8; j++)
 {
  if (sign != face->plane.whereIsPoint(boxVerticies[j])
  {
     return true;
  };
 };
 return false;
}
return false
}



//loops thru the points of a polygon to determine any of 
//the points are infront(or on) it's plane
bool CollisionFace::infrontOf(Plane  & plane)
{
	for (int i = 0; i < this->points.size() - 1; i ++)
	{
		switch (plane.whereIsPoint(*this->points))
		{
		case positiveSign: return true;
		case zeroSign:     return true;
		};
	};
	//  All points of this face are negativeSign
	return false;
};
 
I've tested this and it works great but, it is slow. if there are n points on the face the this thing runs in worst case of: 6n... does anybody know if there is a way to do it faster? Thanks Edited by - _walrus on March 18, 2002 6:16:08 PM Edited by - _walrus on March 18, 2002 6:16:38 PM Edited by - _walrus on March 18, 2002 6:17:36 PM

Share this post


Link to post
Share on other sites
You have a lot of function calls: try rewriting the code so it accesses and works on the structures (planes, points) directly, instead of through C++ accessor functions. You can also look at using SIMD or other parallel instructions to accelerate the 3D point and plane operations.

Share this post


Link to post
Share on other sites
maybe a boundingsphere around the polygones might speedup the test, cause you can test first, if the sphere is outside the box... maybe you can put a bounding sphere around the box too, this way you just have a sphere-sphere test.... and if the probability isn''t high that this happens, you''ll have 18 times fewer test (just sphere-sphere and not 3points with 6planes)

rapso->greets();

Share this post


Link to post
Share on other sites
Well, what I would do is simply have a box and test all points in your polygon to see whether they fall inside the box vertexes.
Depending on your purpose, if any vertex falls within the box you could breakout at that point, or simply set a flag and continue.
This is of course a precise way.
A common solution for collision-testing is sphere-sphere.
A ellipse-ellipse might also work, depending on your shapes.
Then what would happen is if it tested true for the sphere-sphere, it would run a more precise check.

so my algo woul go like so....
box has 6 vertexes, each with x,y,z
polygon has n vertexes, each with x,z,z
for all vertex in polygon
test the x to see if it is within box
test the y to see if it is within box
test the z to see if it is within box
next
if all vertexes are within the box, presto...
if none are, you are home free
if only some are, you can play around with the data you found.




Bugle4d

Share this post


Link to post
Share on other sites
Vlion, what if none of the verticies of the poly are within the box, but the the but the polygon is bisecting the box. This would imply that none of the points of the polygon are in the box, yet a section of the polygon is clearly contained within the box.

Share this post


Link to post
Share on other sites
Hi _walrus,

What about simply projecting the convex hull of your polygon onto the 3 axis of your bounding box and then checking what happens along these 3 axis??

on each axis you have to check if the projection of the convex hull of your polygon is inside of the projection of your box. If it is true on the 3 axis, your polygone is entirely contained in the box.

I guess this could be very fast, however you will probably only be able to check wether the polygon is entirely contained in the box. You can''t distinguish between not colliding and half-colliding.

Cheers,

Marc

Share this post


Link to post
Share on other sites
You do not take advantage of the symmetry of your box. Evaluating the plane equation gives more information than just inside or outside. It also gives the distance to the plane, multiplied by the length of the plane's normal vector. If your planes are normalized, then you can cut the number of tests in half: (assume the normal of the plane points outside the box)

d1 = frontplane.Evaluate(point)
if(-depth < d1 < 0) then point is inside

This eliminates the need to test the backplane. Of course, you have to store the normal of each plane. This method can adapt to your code quite easily, but it would be better to store the 3 "axes" of the box instead of storing the normal. An axis is such that BoxCenter + axis = center of one of the faces of the box and BoxCenter - axis = another face

if(fabs(Dot(axisZ, (point - BoxCenter))) < depth^2) then point is inside for the Z axis

Another alternative is to transform the points into box space and then just check the x-y-z coordinates of the transformed point against length-height-depth of the box. You can always store the transformation matrix with your box, also.

These are just improvements to check if a point is inside the box. It doesn't solve your biggest problem, I believe:

quote:

Vlion, what if none of the verticies of the poly are within the box, but the the but the polygon is bisecting the box. This would imply that none of the points of the polygon are in the box, yet a section of the polygon is clearly contained within the box.


Your algorithm doesn't either, as far as I can see.

[edited by - cedricl on March 31, 2002 12:55:16 PM]

[edited by - cedricl on March 31, 2002 1:56:42 PM]

Share this post


Link to post
Share on other sites