Merging triangles
Author
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
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.
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.
Author
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
BasketQase Software
Wraith
BasketQase Software
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.
Visit our homepage: www.rarebyte.de.st
GA
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.
Visit our homepage: www.rarebyte.de.st
GA
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement