View Full Version : Unique Polygon Sorting Algorithm?

 renpoo04 April 2005, 09:38 AMHi, I have a question about polygon sorting. I'm using MAYA and editing high-res polygon mesh, but its working speed sometimes gets slower. I think it would be because of the data structure of polygon mesh (=dynamic array) and its internal workflow. I guess it will be able to refine the speed by polygon sorting and am now trying to code filter program. What I'm planning are mainly as follows. 1. Sort the poly mesh by its XYZ coordinates. 2. Pick a START vertex. 3. Traverse the poly mesh (e.g. Breadth-First Traversals in Graph theory) 4. Rebuild the mesh according to the result of (3). If it is able to traverse uniquely the poly mesh, it is application-independent and useful for morphing between different meshs that share the same or equivalent topology. Is there anyone who knows this kind of algorithm? Thanks in advance.
rakmaya
04 April 2005, 01:53 PM
If you are looking to increase the speed during Morph, re-odering the polygon is not necessary. Since the traversal algorithm for morph is a sequential source-target comparision. However, in certain situation, it might go hay-wire if you re-order the polygons.

Static and Dynamic arrays do not effect the speed during searches (well, it does to a little), but the speed hit is not significant compared to the processing of morph for a vertex. It is only a problem during adding and deleting a polygon.

However, If you are modeling for games, reodering the polygonal vertices to for optimized cache hit is more powerful than reodering it for linearity. But this is only good for hardware rendering.

You said, it is very-high right? So I am guessing you are modeling for High-End quality stuff. If that is the case, your final render is done in Software (Mental Ray for ex), which does plenty of optimization on its own. Depending on the Shader you use, even linear sorted vertex can prove counter effective.

The way you do is, to create a tool that extracts the vertices and create a polygonal object with the vertex order you want. You can also provide them additional options such as "Keep Original" etc... You can use most algorithms for this depending on your final purpose.

Hope it helps

renpoo
04 April 2005, 04:52 PM
>rakmaya

Thanks a lot.

My 1st. motivation about sorting is getting better speed in polygon editing for high-res mesh. However, after reading your advice, it might be enough to sort once with one of various algorithm.:D Thank you.

rakmaya
04 April 2005, 05:02 PM
If you are creating your own object type (more complicated than what I sounds), then you could use whatever you want to handle it during editing inside Maya. But it is not possible to change the current internal structure of Maya to the level you are thiking. Maya works on a more complicated philosophy (and implimentation) than simple dynamic lists. It has nodes attached to almost every action you perform. So taking all that out and placing your own pipeline is not possible. So the alternative is to extract/modify the object altogether during the editing stage to make it a little faster. Most of the tool we make are to prevent the unecessary object from even entering the Maya pipeline. One example would be progressive mesh. Another example would be the grid maya use to to create Oceans and other Fluids. Ofcourse such programmable algorithms cannot be used for complecated figures. So what is left is something like I told in prevous post. Hope it helps you someway.

MGernot
04 April 2005, 01:14 AM
Before you start writing your own poly-structure, take a look a this project:

It`s done by Andreas Öberg (f97ao) and uses clever detaching of detail-areas and
caching for the speedup.

renpoo
04 April 2005, 04:25 AM
> rakmaya
Thanks. To tell the truth, I'm not used to CG Programing but it is regretable that we cannot place any pipeline in MAYA.

> MGernot
Thanks a lot. I'm greatly inspired from that kind of idea and trying to do tricky applying in MAYA as possible as I can. It may save a lot of time in editing, and some process in workflow will be automated.

Thanks a lot once more to you two.

CGTalk Moderation
04 April 2005, 04:25 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.

1