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;
};
looking for a faster way to determine if a polygon is inside a Box
Author
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:
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.
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();
rapso->greets();
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
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
Author
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.
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
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
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:
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
