View Full Version : Splitting a mesh into polygon groups

Adrian Lopez
05-06-2006, 05:34 PM
I've been thinking of a way to split a LW mesh into groups of connected polygons that share the same properties (textures, UV groups, etc.). So far the best I've been able to come up with is the following procedure:

1. Create a list of polygon-vertex pairs. For every pair, this table contains the polygon's ID, the position of the vertex within that polygon's list of vertices, the desired values for each vertex (Position, Texture, UV values, etc), and a reserved column for use in step 3:

(Polygon ID) (Vertex Order) (Polygon/Vertex Values) (reserved)

2. Sort above table by polygon/vertex values and use that to create a list of unique polygon/vertex values:

(Unique Polygon/Vertex Values)

3. To each polygon-vertex pair in the table created in step 1, add an index into the list of unique vertex values:

(Polygon ID) (Vertex Order) (Vertex Values) (UPVV Index)

4. Sort the above table by Polygon ID and Vertex Order.

5. Create a table of polygons and their "colors". Each "color" is actually a single integer value that identifies a polygon as part of a group. All polygons are initially assigned a color of 0:

(Polygon ID) ("Color")

6. Create a table that maps vertices to polygons. This is used to find all polygons that share a particular vertex.

(Vertex) (Polygon)

7. Iterating through the vertex/polygon table created in step 6, assign a color to every polygon that shares that vertex. If any of these polygons has previously been assigned a color, the polygons surrounding the vertex are colored according to the lowest of these colors. Otherwise, the polygons are assigned a unique color.

8. Iterating through the vertex/polygon table, each polygon surrounding a particular vertex is colored according to the lowest of the polygons' colors.

9. Repeat steps 8-9 until no more polygons have been recolored.

10. Output a list of polygons sorted according to "color".

Any comments or suggestions?

05-06-2006, 05:52 PM
Why not just use unweld (^U)?

Adrian Lopez
05-06-2006, 06:00 PM
The idea is to split a mesh into groups of polygons that share the same texture, UV group, etc. in order to make drawing more efficient once the mesh is exported for use in a realtime 3D engine.

05-07-2006, 05:52 AM
Why not use the selpoly/selpoint method for things like surface (you can easily find which surfaces share textures) and cut an paste them to separate them.

In my UV relax and Split by UVs I unweld all the points, convert their UV coordinates to morph values and then merge the points again and clear the morphmap. This leaves discontinuous edges separated. I'm not sure how efficient this is in comparison to your method, but it seems the best way to me.

Adrian Lopez
05-07-2006, 07:35 PM
It hadn't occurred to me to use LW commands. It's an interesting technique, but I'd rather avoid altering the models at all when exporting meshes so I'm going to stick to the method I described above. I'm most interested in other algorithms as alternatives to the one I presented. In any case, thanks for your help. :)

Sebastian G.
05-07-2006, 10:00 PM
for every polygon make a list of incident points
for every point make a list of incident polygons

find a polygon A with desired attributes
call P( arbitrary point of A )

where P is a recursive function:

P( point X )
if X isn't marked
mark X
for all polygons B incident to X
if B isn't marked and has the desired attributes
mark B and add it to the current polygon group
for all points Y of B
call P( Y )

Adrian Lopez
05-08-2006, 01:17 AM
Excellent. Thanks :)