Algorithm for simplifying 3d surface?

Question

I have a set of 3d points that approximate a surface. Each point, however, are subject to some error. Furthermore, the set of points contain a lot more points than is actually needed to represent the underlying surface.

What I am looking for is an algorithm to create a new (much smaller) set of points representing a simplified, smoother version of the surface (pardon for not having a better definition than "simplified, smoother"). The underlying surface is not a mathematical one so I'm not hoping to fit the data set to some mathematical function.

Answer 1

I think you are looking for 'Level of detail' algorithms.

A simple one to implement is to break your volume (surface) into some number of sub-volumes. From the points in each sub-volume, choose a representative point (such as the one closest to center, or the closest to the average, or the average etc). use these points to redraw your surface.

You can tweak the number of sub-volumes to increase/decrease detail on the fly.

Answer 2

unless you parametrise your surface in some way i'm not sure how you can decide which points carry similar information (and can thus be thrown away).

i guess you can choose a bunch of points at random to get rid of, but that doesn't sound like what you want to do.

maybe points near each other (for some definition of 'near') can be considered to contain similar information, and so reduced to single representatives for each such group.

could you give some more details?

Answer 3

I'd approach this by looking for vertices (points) that contribute little to the curvature of the surface. Find all the sides emerging from each vertex and take the dot products of pairs (?) of them. The points representing very shallow "hills" will subtend huge angles (near 180 degrees) and have small dot products.

Those vertices with the smallest numbers would then be candidates for removal. The vertices around them will then form a plane.

Or something like that.

Answer 4

Instead of dealing with it as a point cloud, I would recommend triangulating a mesh using Delaunay triangulation: http://en.wikipedia.org/wiki/Delaunay_triangulation

Then decimate the mesh. You can research decimation algorithms, but you can get pretty good quick and dirty results with an algorithm that just merges adjacent tris that have similar normals.

Answer 5

Google for Hugues Hoppe and his "surface reconstruction" work.

Surface reconstruction is used to find a meshed surface to fit the point cloud; however, this method yields lots of triangles. You can then apply mesh a reduction technique to reduce the polygon count in a way to minimize error. As an example, you can look at OpenMesh's decimation methods.

OpenMesh

Hugues Hoppe