A fast and efficient projection-based approach for surface reconstruction

We present a fast and memory efficient algorithm that generates a manifold triangular mesh S with or without boundary passing through a set of unorganized points P⊂ℛ³ with no other additional information. Nothing is assumed about the geometry or topology of the sampled manifold model, except for its reasonable smoothness. The speed of our algorithm is derived from a projection-based approach we use to determine the incident faces on a point. Our algorithm has successfully reconstructed the surfaces of unorganized point clouds of sizes varying from 10,000 to 100,000 in about 3-30 seconds on a 250 MHz, R10000 SGI Onyx2. Our technique can be specialized for different kinds of input and applications. For example, our algorithm can be specialized to handle data from height fields like terrain and range scan, even in the presence of noise. We have successfully generated meshes for range scan data of size 900,000 points in less than 40 seconds.