Construction of triangle meshes from point clouds

CS 7491 Spring 2004 Project 2

Group Members

Project Description

Generate randomly-distributed, uniformly-sampled point clouds. Construct a soup of triangles using a ball-rolling algorithm. Construct consistently-oriented corner tables for the generated non-manifold triangle soup. Implement and modify Edgebreaker to work with such non-manifold triangle meshes. Show statistics for various results obtained.

Constructing T-meshes from point clouds

Introduction

Construction of triangle meshes from point clouds is an important problem. If we can throw away connectivity and reconstruct a mesh from just the point locations, then we can store a more compact representation. Furthermore, some applications have a point cloud as a result, such as range scans. In our work, we generate point clouds at random from several primitives to form interesting models. We then employ a ball-rolling algorithm to construct triangles spanning the point samples in the cloud. The only user-defined parameter is the radius R of the rolling ball. Now for any triple of sample points that form a sphere of radius R that is empty of all other samples we construct a triangle. For solid objects that are densely packed with samples, this will form one shell around the object. For surfaces sampled throughout the surface, the algorithm will form a shell on each side of the surface. The end result is an orientable but not necessarily manifold surface possibly made up of several shells.

Size of the radius parameter R

Let d be the sampling density, that is, the average number of points per unit volume. Then the average distance bewteen two sample points should be 2(1/d)^(1/3). Therefore, if we roll a ball of this diameter (R=(1/d)^(1/3)), about half of the samples will be too far apart to form a triangle. Using a ball twice this size should capture most of the triangles that we want. However, if the ball is too large we will not be able to capture fine geometry. Therefore, the radius needs to be smaller than the smallest feature that we want to capture for the model. This gives a range of acceptable values for the parameter R. Now, the smaller the radius, the better the speed improvement of the voxel implementation. We conclude that the best radius for the rolling ball is 2(1/d)^(1/3) if the model has solid objects. If there are only area samplings, then 2(1/d)^(1/2) should be small enough to cover triangles sufficiently.

Ball-rolling algorithm

The naive version of the algorithm operates as follows. For every triple of points, form 0, 1, or 2 spheres of radius R passing through these points. If any two of the samples are further apart than 2R, then no spheres exist and we move on to the next triple. For each of the spheres that do exist (potentially one centered on each side of the plane formed by the triple), we check all the other samples to see if the sphere is empty. If a point inside the sphere is found, we bail out of the loop.

An improved naive version of the algorithm works as follows. For every pair of sample points, if the pair is already further apart than 2R, we skip this pair since no triple containing this pair will pass the 2R test. Given the pair we pick a third sample to form a triple, test this third sample to see if it is within 2R of the other two, and from there we proceed as above. This actually yields a tremendous savings.

Finally, we implemented a voxel approach. Here we partition space into a regular cubical grid where each cube has edge length 2R. Each grid cell has a list of samples contained in the cell. This way, for a given sample point, we only have to check it against points in its own voxel and the neighboring 26 voxels to form triples and check for emptiness of the spheres. This has the potential for tremendous savings, however in practice it was not any better than the improved naive implementation.

Time complexity

After doubling the sample density, the time taken by the brute force algorithm is actually multiplied by 8. It turns out that although the algorithm in O(n^4) in theory, a better analysis gives amortized or expected time O(n^3). The reason is the following. If the three points that are selected to form the sphere of radius R are too far apart even to form such a sphere, then we skip the innermost loop completely. So for any radius less than the smallest distance between two samples, the algorithm literally takes O(n^3) time. On the other hand, for any radius larger than the diameter of the entire model, the innermost loop will always be entered. However, in this case it is very likely to find a point quickly that is inside the sphere, and we bail out of the inner loop early. For a large radius, over half of the triples have a probability of at least 1/4 of finding a point inside after one check, so the expected number of iterations of the inner loop will be constant, giving O(n^3) overall. It seems like there should be a trade-off somewhere between these two extremes that gives something worse than O(n^3), perhaps the formula for minimum radius we described above. However, this does not seem to be the case in practice. The amortized cost appears to be O(n^3) for any radius, due to a combination of the above two scenarios. Figure 1 shows the factor of increase in time taken by the naive algorithm when doubling the number input samples versus the radius of the rolling ball. It confirms that the time complexity of O(n^3) is independent of the ball radius size. Both of our improved algorithms are also O(n^3) in practice, though they have a smaller constant than the naive algorithm.

Ball-rolling results

The ball-rolling algorithm follows an expected behavior when varying the ball radius. With zero radius, no triangles are found. As the radius increases, more and more triangles are spanned by the sphere, but only up to a limit. (See the spike in Figure 2.) This limit occurs when the sphere grows large enough that it cannot be fit without containing other points. As the sphere radius approaches infinity, the triangulation approaches the convex hull.

Figure 1. Time increase ratio when doubling points is independent of radius.	Figure 2. The number of triangles approaches the number of triangles in the convex hull of a point set as the radius approaches infinity.

Matching triangles on non-manifold edges

For a non-manifold edge, we need to associate opposite pairs for the corner table. Therefore we set up a local coordinate system with the edge AB as the z-axis, one triangle projected onto the plane perpendicular to the edge as the x-axis, and a third axis perpendicular to these two as the y-axis. Then for each triangle ABC or BAC (where C = c.v, the vertex associated with the corner opposite edge AB) we define an angle with respect to the xy plane of the orthogonal basis we have constructed. We sort by this angle. In the case of ties for coincident triangles, we sort according to the sign of c.t.normal dot q, where q is AB cross AC. Then, starting with a positive sign, we match up adjacent pairs in the sorted list as opposites, wrapping around if necessary.

Edgebreaker Compression for Non-manifold meshes

Basic Algorithm

Base Edgebreaker is mainly an implementation of Compression and Decompression algorithms from the Handles paper. Instead of writing a clers string in ASCII format, compacted bit strings are written in binary files. Bit manipulation routines are used during decompression to recover the symbols.

Instead of predicting and writing geometry, just the index of each vertex is written as they are encountered by 'C' triangles. This helps in getting rid of the duplicates created due to non-manifold vertices during decompression. Implementation can be easily modified to include simple parallelogram prediction.

// ...
// If c.v is not marked
// output(clers, 'C'), output(vertex, c.v), c = c.r
// ...

Handling non-manifold vertices

Handling of non-manifold vertices only affects encoding and decoding 'C' triangles. A triangle does not disqualify as a 'C' triangle if c.v is visited, but a neighborhood fan of triangles incident upon the vertex is checked for any marks:

// ...
// If c.v is not marked or NotVisited(c)
// output(clers, 'C'), output(vertex, c.v), c = c.r
// ...

//NotVisited(int c)
//corner=c
//repeat
// corner=corner.r.n
// if(corner.t is visited)
// return false
//until corner==c
//return true

Obviously such 'C' triangles will duplicate the vertex index encoded in the encoded stream. The decompression reads the index from input stream when it encounters a 'C' triangle. At the end, the duplicates are automatically cleaned as they point to same entry in the geometry.

File Format

The format of the compressed files .vzip, .gzip and .hzip (for connectivity, geometry indices, and handles respectively) is simply number of elements in the file followed by each element in the file.

Compression achieved using the Edgebreaker technique for the non-manifold models used is reported below. The connectivity part of original .ov file is compared separately with the .vzip compressed file. Significant gains due to Edgebreaker are compared with a simple entropy-based method by adding numbers for zipped (using winzip) connectivity.

Output

To show all the shells at a time, all shells were painted in different colors but with some transparency value. As OpenGL would overwrite any triangles painted on top of each other for non-manifold cases, instead of a simple pass, shells were rendered separately. Finally to show inner shells clearly, outer shell (computed naively as shell with maximum number of triangles) is drawn first followed by remaining shells.

Point cloud for ball with cavity.	Shells for ball with cavity.
Point cloud for sphere with blocker.	Shell for sphere with blocker.
Point cloud for intersecting spheres.	Shells for intersecting spheres.
Point cloud for combo.	Shells for combo.

Results

The following table shows statistics for the point sets above. The average, minimum, and maximum distances between each point and its closest point are listed.

Detailed results and data are shown on the result data page.

Operating in limited memory

In a situation where careful management of memory is required, we would use a least-recently used page swapping strategy. The vertices would be stored in the pages with strong spatial coherence. Edgebreaker is a fairly space-coherent algorithm, so this should work pretty well.

Assuming B bytes storage required per vertex, if we have V vertices, V*B/5 bytes of RAM, and V*B/100 byte memory pages, we have space for 20 pages. Assume the vertex coordinates are spatially paritioned into G pages with a regular voxel grid. In theory, the minimum of G page loads could be achieved if we never have to visit an unvisited part of the spatial partition except when less than 20 pages have been loaded. Another case is when there are already 20 pages in memory but there exists a page that contains vertices that we will never have to access again. As long as the replacement strategy correctly chooses to replace this page, we will achieve G page loads.

With a LRU replacement strategy, we can expect to reload a previously replaced page if the live/hot boundary of the traversal spans 20 or more different grid cells/partitions/pages. Likewise, if the traversal wanders into 20 or more other pages after a S-split before having to return and finish the recursion, it will result in a reload. The total expected number of page loads really depends on the mesh itself and the way the traversal gobbles it up.

The deliverables

Zip Files (containing the VC++ project and source code)

ptcloud_ballroll.zip For generating point clouds and indexed triangle meshes

corner_java.zip For creating .ov files from indexed triangle meshes

Edgebreaker.zip For compression and decompression of connectivity and displaying shells

Data Files

scenedata.zip Scene description files for input into the point cloud generator (all models)

pointdata.zip Point cloud files for the models tested with Edgbreaker

compressiondata.zip Input .ov files and compressed .vzip, .gzip and .hzip files (for connectivity, geometry indices, and handles, respectively).

Instructions for making it work!

Use VC++ environment to compile and run the ptcloud, ballroll, and Edgebreaker programs.

Use "javac *.java" to compile the corner_java files and run using "java Mesh <input file> <output file>".