Mesh decimation

At Floorplanner we got a request from Migenius to deliver low poly versions of all our models for use in their Bloomunit project. The low poly models are used with a SketchUp plugin to create a scene which is then sent to a webservice for photorealistic rendering using the high poly models.

Mesh decimation aka polygon reduction aka surface simplification is to take a high detail model with many polygons and generate a version using fewer polygons that looks reasonably similar to the original. The topology of the model must remain intact.

bunnies

Most algorithms reduce the amount of polygons by recursively collapsing cq contracting edges until the desired amount of polygons is reached.

edge-collapse

The main problem these algorithms need to solve is what (next) edge to choose for a collapse. If we should pick random edges the model will fall apart and not look like the original.

wireframe-cube.png

In the cube above the problem is obvious. Collapsing the outer edges of the cube will deform the model into something which no longer is a cube. Enter the error metric. The algorithm starts by assigning an error to each edge of the model and adds the edges to a priority queue sorted from low to high error. The outer edges of the cube will have a high error, whilst edges inside the cube’s faces will have a low error. The algorithm progresses by popping the edge with the lowest error from the queue, collapse the edge, recalculates the error of the affected edges and moves on to the next edge until the target amount of polygons is reached.

This is all pretty straightforward if we only have to consider geometry and we can discard attributes like vertex normals and texture coordinates.

I researched the following methods for mesh decimation:

  1. QSlim. A C application developed around 1997. Limitation is that it only takes into account geometry, but its lightning fast. Made by one of the heroes in the field of mesh decimation: Michael Garland.
  2. 3ds Max using its build-in ProOptimizer modifier. This will handle vertex attributes as well, but its rather slow and memory hungry.

For the Bloomunit project only geometry needed to be taken into account so the choice was simple: QSlim. Decimating more than 110K models took around 8 hours. Using 3ds MAX the process would have taken at least a week (!).

In the future, we probably need decimated models with vertex attributes for the Roomstyler preview application. Here 3ds MAX seems our best option, though the QSlim code includes an example application which takes into account vertex attributes. Still researching how stable it is.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s