Algorithm for simplifying 3d surface?

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 poi开发者_运维百科nts 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.

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.

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.

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.

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

There exist several different techniques for point-based surface model simplification, including:

• clustering;
• particle simulation;
• iterative simplification.

See the survey:

M. Pauly, M. Gross, and L. P. Kobbelt. Efficient simplification of point- sampled surfaces. In Proceedings of the conference on Visualization’02, pages 163–170, Washington, DC, 2002. IEEE.

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?

It's simpler to simplify a point cloud without the constraints of mesh triangles and indices.

smoothing and simplification are different tasks though. To simplify the cloud you should first get rid of noise artefacts by making a profile of the kind of noise that you have, it's frequency and directional caracteristics and do a noise profile compared type reduction. good normal vectors are helfpul for that.

here is a document about 5-6 simplifications using delauney, voronoi, and k nearest neighbour maths:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.10.9640&rep=rep1&type=pdf

A later version from 2008: http://www.wseas.us/e-library/transactions/research/2008/30-705.pdf

here is a recent c++ version: https://github.com/tudelft3d/masbcpp/blob/master/src/simplify.cpp