robust algorithm for surface reconstruction from 3D point cloud?

by

I have been facing this dilemma for some months now, and made exhaustive research.

Algorithms

Mainly there are 2 categories of algorithms: computation geometry, and implicit surfaces.

Computation Geometry

They fit the mesh on the existing points.

Probably the most famous algorithm of this group is powercrust, because it is theoretically well-established – it guarantees watertight mesh.

Ball Pivoting is patented by IBM. Also, it is not suitable for pointclouds with varying point density.

Implicit functions

One fits implicit functions on the pointcloud, then uses a marching-cube-like algorithm to extract the zero-set of the function into a mesh.

Methods in this category differ mainly by the different implicit functions used.

Poisson, Hoppe’s, and MPU are the most famous algorithms in this category. If you are new to the topic, i recommend to read Hoppe’s thesis, it is very explanatory.

The algorithms of this category usually can be implemented so that they are able to process huge inputs very efficiently, and one can scale their quality<->speed trade-off. They are not disturbed by noise, varying point-density, holes. A disadvantage of them is that they require consistently oriented surface normals at the input points.

Implementations

You will find small number of free implementations. However it depends on whether You are going to integrate it into free software (in this case GPL license is acceptable for You) or into a commercial software (in this case You need a more liberal license). The latter is very rare.

One is in VTK. I suspect it to be difficult to integrate (no documentation is available for free), it has a strange, over-complicated architecture, and is not designed for high-performance applications. Also has some limitations for the allowed input pointclouds.

Take a look at this Poisson implementation, and after that share your experience about it with me please.

Also:
here are a few high-performance algorithms, with surface reconstruction among them.

CGAL is a famous 3d library, but it is free only for free projects.
Meshlab is a famous application with GPL.

Also (Added August 2013):
The library PCL has a module dedicated to surface reconstruction and is in active development (and is part of Google’s Summer of Code). The surface module contains a number of different algorithms for reconstruction. PCL also has the ability to estimate surface normals, incase you do not have them provided with your point data, this functionality can be found in the features module. PCL is released under the terms of the BSD license and is open source software, it is free for commercial and research use.

More Related Contents:

  1. An algorithm for inflating/deflating (offsetting, buffering) polygons
  2. Sort points in clockwise order?
  3. How do I efficiently determine if a polygon is convex, non-convex or complex?
  4. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  5. How to Compute OBB of Multiple Curves?
  6. Largest circle inside a non-convex polygon
  7. How to check if line segment intersects a rectangle?
  8. Geo Fencing – point inside/outside polygon
  9. What is the fastest way to find the closest point to a given point?
  10. Shortest distance between points algorithm
  11. What is the most efficient algorithm to find a straight line that goes through most points?
  12. How to find convex hull in a 3 dimensional space
  13. Circular approximation of polygon (or its part)
  14. How can I create an internal spiral for a polygon?
  15. Mesh generation from points with x, y and z coordinates
  16. Find if a point is inside a convex hull for a set of points without computing the hull itself
  17. Path generation for non-intersecting disc movement on a plane
  18. Compute the area of intersection between a circle and a triangle?
  19. Location of highest density on a sphere
  20. Algorithm to check similarity of colors
  21. Calculating new longitude, latitude from old + n meters
  22. Finding all the shortest paths between two nodes in unweighted undirected graph
  23. Fastest primality test
  24. Efficient maths algorithm to calculate intersections
  25. How to calculate or approximate the median of a list without storing the list
  26. Sort Four Points in Clockwise Order
  27. Obfuscating an ID
  28. Algorithm for autocomplete?
  29. An inverse Fibonacci algorithm?
  30. Calculating frames per second in a game

Leave a Comment