# pouët.net

## Triangle Mesh Partitioning Algorithms

category: code [glöplog]

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:
Code:``` G =(N / M); if (N % M != 0) { // A group < M exists - add it G++; } ```

It has to work on huge meshes.

Any recommandations / references?
added on the 2010-08-31 15:51:59 by las
partitioning = randomize();
while (!correct(partitioning))
partitioning = randomize();
added on the 2010-08-31 15:57:19 by kusma
I have no idea how to do this, but I'm wondering why you need the groups to be exactly the same size.
added on the 2010-08-31 16:01:38 by doomdoom
kusma: no.
added on the 2010-08-31 16:01:52 by las
Doom: Random things, geometry shaders and decompression... So it's kinda nice (branchless) when you can decompress groups of equal size.
added on the 2010-08-31 16:04:29 by las
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?
added on the 2010-08-31 16:14:31 by doomdoom
2-manifold
added on the 2010-08-31 16:23:06 by las
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.
added on the 2010-08-31 17:50:10 by Sinar
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
added on the 2010-09-01 15:05:11 by las
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?
added on the 2010-09-01 15:16:29 by kusma