CS7491 Project 3:
Ball-Based Mesh Decomposition and Reconstruction
April 20, 2004
| Jaeil Choi jerry@cc.gatech.edu  |
Justin Jang jang@cc.gatech.edu  |
April 20, 2004
| Jaeil Choi jerry@cc.gatech.edu |
Justin Jang jang@cc.gatech.edu |
Decompose a mesh by filling the shape with a set of non-intersecting balls, and use only the set of tuples (Sx, Sy, [Sz,] Sr) of these balls to represent the shape. Reconstruct a mesh given only the set of tuples of these balls.
The goal of decomposition part is to find a minimal set of balls that fills up the interior of given shape.
Each ball can be defined by four numbers (3 coordinates and radius), and can be encoded efficiently.
The accuracy can be measured in terms of :
In decomposition procedure, these accuracy can be controlled by the minimum radius of ball.
We use greedy method to find a minimal set of balls that fills up the interior of the shape. For every iteration, we choose a interior point that is the farthest from any points on the surface, and use the point as the center of a new ball. Its shortest distance to the surface gives the radius.
If we are given piecewise-linear surface model(for example, triangular mesh), the deepest interior position can be found on the vertices of Voronoi regions of the interior space. Voronoi regions in 3D certainly can be calculated in O(n log n) time with respect to the number of vertices and faces of the surface model, but it is very hard to implement. Instead, we chose to use quantized distance field of the interior. Since we only need to find the deepest interior postion from the surface, We don't need 'regional divisions' of Voronoi diagram.
We divide the bounding space of the model into a regular 3D grid, and calculate distance values of each cell by using marching front algorithm. The marching front algorithm first initializes cells on the surface with distance 0, and propagate the distance to the interior neighbors maintaining the contour of iso-level.
Now, with SDF, we can easily decide the center and the radius of new ball by looking up the cell with maximum distance value. And after the addition of a ball, the distance field need to be updated in the neighborhood of new ball. Time complexity of this algorithm is linear to the number of cells and number of balls to be added.
Unfortunately, This greedy approach does not give us the global optimal solution. It's due to the fact that there might be a smaller ball that fits remaining space better. Choosing one from multiple cells with same maximum distance value also affects the number of balls required later.
As accuracy (in terms of either surface distance or volume) increases, the number of balls required to fill the interior space grows in cubic.
The reconstruction phase of the algorithm takes a list of spheres as input and outputs a triangle mesh. The basic approach has two parts: 1) populate and process a scalar field, and 2) extract a triangle mesh from the scalar field.
To populate a scalar field, we simply generate a 3d distance field for the spheres. For each sphere, compute a scalar value for every voxel as the distance from the sphere center to the voxel location minus the sphere radius. (This results in negative values inside the sphere and positive values outside. The isosurface at zero should yield the sphere itself.) Only store this value into the scalar field if it is less than the existing value at the given voxel location. Thus we obtain a distance field with respect to the list of spheres.
The scalar field now represents a collection of balls in space, where a negative value signifies that the space of the voxel is occupied. However, since we know that the list of spheres was constructed to volumetrically fill a shell, we can use the radius of the smallest sphere as an upper bound on the size of holes to fill. Given the scalar field and this radius, our approach is to use grayscale morphological operations to fill the holes. In our algorithm, we define morphological operations for dilate, erode, and close.
Morphological operators:In the dilate operation D(A, B), the value of a cell a[l,m,n] gets the minimum value found in the valid neighbors of the cell, where valid neighbors are determined by superimposing the kernel B at the cell location. This is similar to convolving A with B. The erode operation E(A, B) is similar to dilate except that it takes the maximum value from among valid neighbors. These are somewhat different from the normal definition of grayscale morphology operators. Our definitions treat negative numbers as being primary and the kernel B is effectively a binary kernel. Also, kernel B always has dimensions s x s x s (where s = h * 2 + 1, h >= 0 is an integer) and the indices i, j, k each run from -h to +h.
We use the close operation C(A, B) on scalar field A with kernel B to fill holes. The kernel B is obtained directly from the sphere of minimum radius. It is the distance field for that sphere, and only needs to be big enough to hold all negative values in this field. In practice, we implement the kernel B as a binary kernel, and assign value 1 where this field is negative (i.e. inside the sphere) and value 0 where this field is non-negative (i.e. on or outside the sphere).
We extract a triangle mesh from this processed scalar field by using the marching cubes algorithm with isovalue zero.
The decomposition voxel grid size was limited to 100x100x100 maximum for all results. The reconstruction voxel grid size was limited to 50x50x50 maximum for all results. Full-size results can be found on the results page.
Cube:
 original triangle mesh |
 ball decomposition |
 reconstructed triangle mesh |
Foot:
 original triangle mesh |
 ball decomposition |
 reconstructed triangle mesh |
Torus:
 original triangle mesh |
 ball decomposition |
 reconstructed triangle mesh |
Cube reconstructions:
 10 spheres |
 25 spheres |
225 spheres |
 900 spheres |
We compare the error of the reconstruction with the number of spheres used in the decomposition. The directed Hausdorff error is the maximum axis-aligned Hausdorff error between the reconstructed mesh and the original mesh. The volume error is the difference in volume between the reconstruction and the original.
 Directed Hausdorff error vs. number of spheres. |
 Volume error vs. number of spheres. |
We believe there are two main limitations in using a set of balls as the representation of a shape. The first is that we are restricted to the surface of a regular ball. For some parts of the shape, cylindrical, ellipsoidal or even flat surface may fit better. The second limitation is that we cannot use spheres adaptively over different parts of the shape, whereas the size of triangles in a triangular mesh can grow or shrink to fit local features or curvature.
Another drawback is that as accuracy (in terms of either surface distance or volume) increases, the number of balls required to fill the interior space grows in cubic order. With surface models, the number of faces required grows quadratically.
But obviously, for some special shapes such as sphere and pipes, a set of balls can be a perfect (or near perfect) representation with unbeatable compactness.