CGAL users discussion list

[Alvin Smith <>]

I was curious if the community had any ideas for this problem, which I think is kind of interesting.  Ultimately, I'm trying to build a 3D model from a point cloud that captures the surface the scanned object, but the data source is very bad.  In fact, it's so bad that there are "holes" in my surface.  Other than the holes, the surface is pretty regularly sampled.  I would like to fill in the holes with points.  I can think of many approaches to filling in the holes, but first I have to identify where the holes are in the first place!

I feel if I first identify "edges" on the point cloud surface, then hole ought to be a clustering of edges in the point cloud.

I have one idea on how to do this: I want to construct a Rienmannian graph of K nearest neightbors, and compute the average distance of the nearest neighbors for each vertex.  If the distance is much larger than the average spacing of the point cloud, then it's probably and edge.

1) Do you think this approach will work? 
2) How the heck to I construct the Rienmannian graph?  There is code in mst_orients_normals.h but I have no idea how to use it.
3) Is there a better approach that I am missing here?

Merci beaucoup.

-Alvin