Jump to content
  • Advertisement

Archived

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

MV

2 coplanar triangles intersection and substraction

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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 ?

Share this post


Link to post
Share on other sites
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.






// .. + 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]);
}

Share this post


Link to post
Share on other sites
Thx for your help oliiii !

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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 !!!

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!