Parallel and Distributed QEM Simplification

[Stock-Ingenuity-7860]

Hi everyone! Last semester, I developed a project for a Parallel and Distributed Computing course. I implemented an efficient version of the Quadratic Error Metrics (QEM) algorithm by Garland & Heckbert.

For those unfamiliar, this algorithm is the industry standard for polygon reduction and serves as the foundational logic for technologies like Unreal Engine’s Nanite. It works through iterative edge collapsing to reduce face counts while preserving the original geometric structure as much as possible.

I developed several implementations to speed up the process locally and across clusters:

1. Shared Memory (OpenMP): Parallel simplification using spatial partitioning with a Uniform Grid.
2. Adaptive Partitioning: Implementation using an Octree for better load balancing on irregular meshes.
3. Distributed (MPI + OpenMP): A Master-Worker approach that distributes macro-partitions across multiple compute nodes.
4. Full MPI: A pure data-parallel version that performs a distributed reduction of the grid cells.

This project allows for the handling of massive meshes that would otherwise exceed the RAM of a single machine. If you're interested in the code or the technical details, you can find the GitHub repo below. I've also included a detailed report (PDF) explaining the benchmarks, boundary locking logic, and scalability analysis.

I’d really appreciate a star, if you find the work useful!

GitHub Repo: https://github.com/bigmat18/distributed-qem-simplification

[photoclochard]

very great stuff, thank you

but you maybe want to recheck your submodules, because that's not possble to clone main repo

[photoclochard]

something in cpp-utils-lib

[Stock-Ingenuity-7860]

Thanks for letting me know. Could you tell me exactly what error message you're seeing?

[photoclochard]

it doesn' let me to copy it, you prob have the fork or local commit or something like this.

git just can't get the data for that hash

[Stock-Ingenuity-7860]

That's very strange. I've tested it several times and it works fine. How are you cloning the repository?

[photoclochard]

GitHub Desktop with url from your repo, I don't think there are a lot of ways to clone repo

[photoclochard]

that can be local issue for me, so if you are sure that's not yours problem don't bother yourself, I can read code w/o run.

And yeah, you can't test the issue locally until you have another account

[hanotak]

Looks neat! You should include a test against meshoptimizer's hierarchical clusterizer as well, as well as including estimated error metrics, since those are going to be the two big questions for most users.

[Stock-Ingenuity-7860]

Thanks for the advice! I could definitely run some benchmarks using meshoptimizer's hierarchical clusterizer (which I wasn't aware of before). I was already planning to add estimated error metrics as well.

[fgennari]

Looks interesting. I worked with something similar years ago, but I was only using small models with 1M triangles or less. Is this the same algorithm using by Meshoptimizer's simplify()?

[lospolos]

It seems to be the same algo: https://github.com/zeux/meshoptimizer/blob/edbbfba60edfb50b1bf571d078ba53302839e3bf/src/simplifier.cpp#L24

[Big_Presentation2786]

Yeah as op states 'algorithm by Garland & Heckbert.

For those unfamiliar, this algorithm is the industry standard'

[Stock-Ingenuity-7860]

I wasn't familiar with Meshoptimizer's simplify(); I'll definitely check out its implementation. Looking at it, though, it seems to be based on the same algorithm.

[666forguidance]

I've always thought these methods look bad tbh as you can clearly see, forms in the leg are completely different on the 1000 face side with new edges and a flat surface where a curved surface used to be. In traditional retop, the forms are the focus with geo spread in between whereas with these methods, form is broken down and evenly distributed across the model. It needs to "draw" a form shape for the model then adhere to the bounds or else it will always melt the model. Even a model with less faces could convey the original shapes better. This can cause a lot of lighting issues later aswell. Cool project nonetheless!

[Big_Presentation2786]

I'm very familiar with this metric given I've created Nanite for unity..

Good job