2 coplanar triangles intersection and substraction
Hi all,
I''m looking for some refs about an algorithm able to compute the substraction of a triangle to another ; given a triangle A, a triangle B, I want to have the set of triangles resulting from A - B.
This is a basic operation that is not so simple.
Found nothing on google
Thx in advance
standard clipping algorithm? split one triangle with another triangle''s plane. store loop of vertices front facing and back facing the plane. clip the two looped sets with another plane, splits into further loops. At this stage, you should have 4 loops top. Then split the 4 loops of vertices with the last plane. that gives a potential 8 loops. Discard the polygons that are flagged as back facing the three planes. The other give you a list of polys outside the triangle. Tesselate them is needed, and that should give a list of triangles. Given, the list of triangles you end up with could be quite fragmented.
I see, that''s great, thx !! I needed 3 or 4 times to understand but now I''m ok with it (just need to code now ). You tesselate one triangle with the edges of the other one, that''s it ?
Any tips for the tesselation ? Are the final sets convex ?
Any tips for the tesselation ? Are the final sets convex ?
the sets will be convex, since it''s you use infinite planes to split convex polygons into two parts. If you cut triangle B with the plane passing through [A1, A0] (in 2D, it''s the infinite line passing through [A0, A1]), you will have a 4-sided polygon [poly 1] on one side, and a three side polygon [Poly 2] on the other side.
then, you partition the polygons [poly 1] and [poly 2] with the other infinite lines [A0, A2] and [A1, A2], and you end up with a set of polygons.
I''d recommend tesselating at the very end. Keep the polygons as they are, and in the very end, tesselate the polygons you kept into triangles.
for a simple tesselation algorithm, use a triangle Fan technique. It''s quite innacurate, but simple, for a first step.
then, you partition the polygons [poly 1] and [poly 2] with the other infinite lines [A0, A2] and [A1, A2], and you end up with a set of polygons.
// .. + A0// triangle B.... * * // ...... * *// ........ *// .......... *// ............ triangle A// * *// +*************+// A1 A2////// /// /// poly1(4 verts) * A0// .. /// .... / // ...... / // ....... / // ....... / .. poly2 (3 verts) // ....... / .... // / // * A1// /// /// /// /// /// \ // \// \ // \ // poly1(4 verts) * A0// .. \// .... \// ...... \// ....... \// ....... .. poly2 (3 verts) // ....... .... \// \// * A2// \ // \// \// \// // // // // // poly1(4 verts) // .. // .... // ...... // ....... // ....... .. poly2 (3 verts) // ....... .... // // ----------------*------------*-----------// A1 A2// // // Poly 1 is front facing plane [A0, A1], back facing [A1, A2] and [A0, A2] => outside triangle//// Poly 2 is back facing all three planes => inside triangle//// tesselate poly 1 => list of triangles outside triangle A////
I''d recommend tesselating at the very end. Keep the polygons as they are, and in the very end, tesselate the polygons you kept into triangles.
for a simple tesselation algorithm, use a triangle Fan technique. It''s quite innacurate, but simple, for a first step.
for (int i = 0; i < Polygon.NumVertices-2; i ++){ Mesh.AddTriangle(Polygon.Vertex[0], Polygon.Vertex[i+1,], Polygon.Vertex[i + 2]);}
Thx for your help oliiii !
Can you tell me why ? Will this slow down the process ?
I just started coding and I did tesselation at each step (I divide the 4 sided polygon in 2 triangles).
I''m not sure if I really need this, but ... I just started this way ...
quote:Original post by oliii
I''d recommend tesselating at the very end. Keep the polygons as they are, and in the very end, tesselate the polygons you kept into triangles.
Can you tell me why ? Will this slow down the process ?
I just started coding and I did tesselation at each step (I divide the 4 sided polygon in 2 triangles).
I''m not sure if I really need this, but ... I just started this way ...
2 more questions since you seem to be good on this subject :
- is this technique working for any polygons ?
- do you know how to divide a concave polygon in convex polygons ?
Thx in advance
- is this technique working for any polygons ?
- do you know how to divide a concave polygon in convex polygons ?
Thx in advance
quote:Original post by MV
2 more questions since you seem to be good on this subject :
- is this technique working for any polygons ?
- do you know how to divide a concave polygon in convex polygons ?
Thx in advance
that would work for any convex polygons. and for concave polygons as well, as long as they don't have edges that intersects. It's a standard clipping algorithm. look for polygon clipping.
to tesselate a concave polygon, I'm not too sure about this, but there are plenty of references on the subject on the net.
I recommend tesselating in the end, because if you start before, you'll end up with possibly splitting more triangles, which is unecessary. but on the other hand, if you don;t want to use polygons but just triangles, it makes sense to do it the way you want.
[edited by - oliii on February 9, 2004 1:45:35 PM]
quote:Original post by oliii
to tesselate a concave polygon, I''m not too sure about this, but there are plenty of references on the subject on the net.
It''s not to tesselate a concave polygon but realy to create sets of convex polygons.
Never mind, you helped me a lot and gave me keys to go on, once more, thanks !!!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement