• Advertisement

Archived

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

Polygon - Collision Detection

This topic is 5991 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

Does anyone know a mathematical algorhytm, that indicates, that one polygon is ''in'' another?? thanks for help, Merlin.

Share this post


Link to post
Share on other sites
Advertisement
If you mean ''do triangles interpenetrate'' then the simple answer
is to find the line at which the planes of both triangles intersect and then ascertain if the line crosses the appropriate
triangular area of each plane. The maths isn''t hard but here
it is anyway:
Let Px,Py,Pz be the normal of triangle P''s plane
Let Qx,Qy,Qz be the normal of triangle Q;s plane
If the line of intersection is expressed in parametric form as:
x = x0 + f*t; y = y0 + g*t; z = z0 + h*t
then: f = Py * Qz - Qy * Pz
g = Pz * Qx - Qz * Px
h = Px * Qy - Qx * Py
Note that if (f^2 + g^2 +h^2) is 0 the two planes
are considered parallel and so we do not have a line of intersection (see note below). Obviously use a numerical accuracy close to 0 for this test.

Then to see if this line (which runs parallel to the plane of each triangle) cuts through each triangle, you test to
see if an edge cuts through a plane which is parallel to the
line and orthonormal to the appropriate triangle (at 90 degrees
to it!). The normal of this plane is taken as the cross product
of the normalised direction vector of the line (f,g,h) and the
appropropriate triangle''s normal. Of course the plane for triangle P''s test is different to that for triangle Q so you
should test the three edges of one triangle first, then if the
test hasn''t rejected intersection perform the other triangle''s
test. The test for a line (edge) cutting a plane is simply to
decide which side each end of the line is on. This is done by
taking the sign of the calculation:
Nx*Px + Ny*Py +Nz*Pz + D
Where Nx,Ny,Nz is the plane normal
Px,Py,Pz is the point
D is the D coefficient for the plane equation in Cartesian form.

I hope this helps, I don''t know whether this is the BEST way but
I have implemented it ok. However if you are planning to test
whether a solid shape intersects another then this test is
probably too expensive and you might look at algorithms for
finding seperating planes between polyhedra.








Share this post


Link to post
Share on other sites
OOPS!!!

Sorry but I forgot to mention that after the test of each edge
against the plane which has been ''extruded'' from the line of
intersection of the two triangle planes, you need to find the
appropriate point on the line of intersection (the coordinate is the same of course) as its parametric co-efficient. This is very
easy since it just involves substituting the intersection point
back into the parametric line equation to get ''t''.
Then intersection will occur if and only if the two sections of line (one per triangle) cross... phew!! its not actually as bad as it sounds... but it needs some thinking about...

Share this post


Link to post
Share on other sites
Your sollution sounds good. I will try to implement it.

Just an Idea:
What do you think about to split the World into Quaders and the Quaders into 4 another Quaders and so on. So i can get a "Section" of polygons (within a Box) which i test for sphere Collision. And then for each Quartal of the Sphere the Polygon to Polygon detection?? Is there a public technique for this? I think its really fast.

many thanks for helping,

Merlin.

Share this post


Link to post
Share on other sites
Surely you mean subdivide the world into 8 (Octree) recursively
rather than 4 unless your world is flat-ish ?
This is a fairly usual way of subdividing up a volume, of course
if your nodes are boxes and world-axis aligned then the intersection test with a sphere at each node is trivial. I''ve done this sort of thing before. Starting at the root node
you recursively test the root nodes bounding box against the
sphere. If it intersects PARTIALLY then you recursively repeat
this procedure for its child nodes. If it intersects TOTALLY then
you simply recursively parse this node to its terminal nodes
without any further tests (since you know that all child nodes
will be contained). Polygons are ''attached'' to terminal nodes in
the tree and when you reach such a node you examine the polygons.
HOWEVER: A polygon could be contained in more than one nodes
bounding box. This is ok. just flag it in some way so you don''t
examine it more than once.

BUT... in general if the polygon''s you have form a closed
surface, particularly a convex solid, then an exhaustive test
of polygons is inefficient. Algorithms exist which are based
on finding a seperating plane between two solids (if such a
plane exists then they are not interpenetrating !).
Since collision algorithms are typically called repeatedly for
small updates in the scene it is worth maintaining data about
each collision test between tests, so that we do not repeatedly
calculate more than we need to.
PS. You may be interested to look at a technique for collision known as AABB (Axis aligned boundiing box) which is hierarchical.

All the best.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
To give you a headstart, there''s some out-of-the-box usable code available with a relevant description of the technique:

http://www.acm.org/jgt/papers/MollerTrumbore97/

HTH

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
ack, I''m sorry. Wrong link. It''s this:

http://www.acm.org/jgt/papers/Moller97/

Share this post


Link to post
Share on other sites

  • Advertisement