• ### What is your GameDev Story?

#### Archived

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

# Merging triangles

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

## Recommended Posts

Does anyone know where I can find an algorithm to take a set of connected triangles and finds the vertices (in order) on the edge, thus forming an n sided polygon? Wraith BasketQase Software

##### Share on other sites
What are the properties of the connected triangles (ie. how are they stored in memory such that they are connected)?

What type of polygon needs to come out of the other end? Does it need to be convex?

I should be able to provide an algorithm if you can give those details.

##### Share on other sites
They are stored as a set of indices into a vertex array. All that needs to come out is the ordered vertex indices of the merged polygon. It does not need to be convex.

Wraith

##### Share on other sites
Start with one of the (I''ll tell you the algorithm in 2d-space) vertices.

You have to search all triangles which contain this vertex
until you have a group of all triangles containing the vertex.

Now you must examine if this vertex is at a corner of a polygon or not. Therefor calculate the angle of the corner at which your vertex is of each triangle in the group:
angle(i) = arccos((vi1-v)*(vi2-v)/sqrt(((vi1-v).x^2 + (vi1-v).y^2)*((vi2-v).x^2 + (vi2-v).y^2 + (vi2-v).z^2)))

where v is the vertex you examine, vi1 is another vertex of a triangle of the triangle group and vi2 is the third vertex of the same triangle. With (vi1-v)*(vi2-v) I mean the scalar product.
Now add all the angles. If the resulting angle is 2 PI or 360°, the vertex is inside the polygon, only if it''s less than 360° the vertex is at a corner of the poly (triangles must not overlapp for this algorithm!). If it is at a corner, search for a vertex of one triangle in the group which isn''t shared with one or more of the other triangles in the group. If it isn''t, try the same algorithm with the next vertex.

This new vertex must be at a corner.
Search again the group of triangles which share this new vertex. Search again for a vertex of one triangle in the group which isn''t shared with one or more of the other triangles in the group and which isn''t the same vertex you started with.

With this vertex you search the group of triangles which share this vertex, you search again for a vertex which isn''t shared .......................

until you come back to the first vertex.

I''m sure you could find a better algorithm but this one should work if there are no holes in your polygon.

GA

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634092
• Total Posts
3015448
×