Friday 26 June 2015

A Simple C++ Class for 3D Mesh Decimation


Some time ago I wrote a simple C++ class to simplify a 3D mesh. It is based on Michael Garland's article "Surface Simplification Using Quadric Error Metrics"

The code is available under a BSD license.

A win64 executable is also available for quick testing.

The code produces good quality results. However, it is relatively slow!

Usage:
MeshSimplification fileNameIn.obj targetNTrianglesDecimatedMesh targetNVerticesDecimatedMesh maxDecimationError fileNameOut.obj

For instance, to generate a decimated mesh with 1000 triangles use the following command line:
MeshSimplification input.obj 1000 0 1.0 decimated.obj

To generate a decimated mesh with 1000 vertices:
MeshSimplification input.obj 0 1000 1.0 decimated.obj

To generate a decimated mesh with an error of 1%:
MeshSimplification input.obj 0 0 0.01 decimated.obj

To use the mesh decimation class in your code, proceed as follows:

// input mesh    
Vec3<Float> * points; 
Vec3<int> * triangles;

// Fill points and triangles with input mesh
// ...

// decimate mesh
MeshDecimator myMDecimator;
myMDecimator.Initialize(nPoints, nTriangles, points, triangles);
myMDecimator.Decimate(targetNVerticesDecimatedMesh, targetNTrianglesDecimatedMesh, maxDecimationError);

// allocate memory for decimated mesh
size_t nVerticesDecimatedMesh = myMDecimator.GetNVertices();
size_t nTrianglesDecimatedMesh = myMDecimator.GetNVertices();
Vec3<Float> * decimatedMeshPoints = new Vec3<Float>[nVerticesDecimatedMesh];
Vec3<int> * decimatedMeshTriangles = new Vec3<int>[nTrianglesDecimatedMesh];

// retrieve decimated mesh
myMDecimator.GetMeshData(decimatedMeshPoints, decimatedMeshTriangles);

Wednesday 21 January 2015

OpenCL Acceleration for V-HACD

Since I don’t expect to have time in the near future to work on V-HACD , I am writing this post to keep track of the performance improvements obtained after the latest optimizations I added. The source code is available here.

Experimental Evaluation
Table 1 compares the computation times (cf. Section "Machine description") of V-HACD 2.0 and V-HACD 2.2 obtained by using the configuration described below (cf. Table 2). These results show that V-HACD 2.2 is an order of magnitude faster than V-HACD 2.0. The gains are mainly obtained thanks to the convex-hull approximation (cf. Section "Updates"). The OpenCL acceleration provides 30-50% lower computation times when compared to the CPU-only version of V-HACD 2.2. 

The code is still not fully optimized and more improvements could be expected!



V-HACD 2.0 (CPU only)
V-HACD 2.2 (CPU+GPU)
army_man
650s
65s
block
220s
26s
Bunny
317s
30s
Camel
388s
34s
Casting
744s
79s
Chair
408s
42s
Cow1
314s
30s
Cow2
349s
32s
deer_bound
411s
34s
Table 1: Computation times: V-HACD 2.0 vs V-HACD 2.2 


Parameter
Config. 1
resolution
8000000
max. depth
20
max. concavity
0.001
plane down-sampling
4
convex-hull down-sampling
4
alpha
0.05
beta
0.05
gamma
0.0005
delta
0.05
pca
0
mode
0
max. vertices per convex-hull
64
min. volume to add vertices to convex-hulls
0.0001
convex-hull approximation
1
Table 2: Tested configuration 


Updates
V-HACD 2.2 include the following updates:
  1. OpenCL acceleration to compute the clipped volumes on the GPU
  2. Convex-hull approximation to accelerate concavity calculations
  3. Added local concavity measure to clipping cost calculation
  4. Changed command line parameters
To do
When I'll find time (probably not soon), I need to do the following:

  • Test the code and build executables for different platforms (i.e., Linux, Mac OS), and 
  • Update the Blender add-on to make it work with the new command line parameters.


Machine description

  • OS: Windows 8.1 Pro 64-bit
  • CPU: Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz (8 CPUs), ~3.4GHz
  • GPU: NVIDIA GeForce GTX 550 Ti
  • Memory: 10240MB RAM