pouët.net

Hi coders,

I'm currently searching for "good and fast" mesh partitioning algorithm.
What I basically need is an algorithm that partitions a mesh with N vertices into groups (adjacent vertices) of equal size (M) - except for one group that might be smaller than the others.
The number of groups (G) is than simply given by:


It has to work on huge meshes.

Any recommandations / references?

partitioning = randomize();
while (!correct(partitioning))
partitioning = randomize();

I have no idea how to do this, but I'm wondering why you need the groups to be exactly the same size.

kusma: no.

Doom: Random things, geometry shaders and decompression... So it's kinda nice (branchless) when you can decompress groups of equal size.

I guess. Not really helping, I know, but I might start by saying that there's no guarantee such a partitioning is possible for an arbitrary mesh. So what sort of assumptions are you making about the topology of the mesh?

2-manifold

There is an article in Game Engine Gems which describes a basic algorithm for mesh partitioning ("Mesh Partitioning for Fun and Profit"). It looks pretty solid to me.

That article seems to be a good starting point.

Maybe I also should have a look at this library:
http://glaros.dtc.umn.edu/gkhome/views/metis

How about not being 100% strict about the equal size (i.e use groups of close-to-equal size instead), and pad the smaller groups with degenerate triangles until they all are of the same size?