15

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.

David Nordvall
  • 12,404
  • 6
  • 32
  • 52
  • You can't actually get both smoother and simpler surface. It's either one or the other. – Mikulas Dite Jul 26 '10 at 19:47
  • 1
    @Mikulas Dite technically he can't (more points, more complicated). But visually, if he removes outliers the curve may appear smoother and less complicated. – µBio Jul 26 '10 at 19:50
  • He could get a simpler surface with less points if the surface is noisy, like a high resolution laser scan of a cube. This is sort of like asking for a low pass filter for 3D surfaces. – darron Jul 26 '10 at 21:02

7 Answers7

8

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.

bshields
  • 3,563
  • 16
  • 16
  • 1
    I remember learning in school that there are surfaces for which no triangulation exists (in 3D.) If the OP is not worried about stumbling across such a surface than this is fine. – ldog Jul 26 '10 at 19:54
  • It really depends on the property of your point cloud data. If it's a grid of points like a height map, then this approach will be very straightforward. If it's a more amorphous cloud of points then this may not work for you. There are whole applications devoted to generating surfaces from complex point cloud data so this is a pretty difficult problem if not constrained. – bshields Jul 26 '10 at 20:01
  • Delauney is only really good for 2.5D - but for heightfield data it's a very good way to start before re-gridding – Martin Beckett Jul 26 '10 at 20:11
2

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.

default locale
  • 13,035
  • 13
  • 56
  • 62
Mah Zarei
  • 21
  • 1
  • 2
    Welcome to Stackoverflow! Would you be able to add more details to your answer (e.g. add descriptions of techniques)? Answers on stackoverflow need to have sufficient information to understand the answer. Link-only answers are [discouraged](http://meta.stackexchange.com/questions/225370/your-answer-is-in-another-castle-when-is-an-answer-not-an-answer) – default locale Dec 08 '14 at 08:29
2

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.

µBio
  • 10,668
  • 6
  • 38
  • 56
2

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.

Carl Smotricz
  • 66,391
  • 18
  • 125
  • 167
2

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

Throwback1986
  • 5,887
  • 1
  • 30
  • 22
1

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?

second
  • 28,029
  • 7
  • 75
  • 76
1

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

bandybabboon
  • 2,210
  • 1
  • 23
  • 33