🔒 Locked

Surface reconstruction from point clouds

Started by Orbital Fan Jan 2, 2010 at 7:54 AM 7 replies 3.6k views

Original Post

Jan 2, 2010 at 7:54 AM

Well my google-fu as failed me today, and I can't seem to find the required information. So was wondering if you guys could point in the right direction. Basically I'm experimenting with a modelling technique which takes a point cloud (with per-point normals) and outputs a GPU-friendly mesh. Google returns lots of academic papers on the subject (mainly for the medical industry), but they are a bit over my head to be honest. a) I can see how Delaunay Triangulation works on 2D data - but can it be extended to work in 3d? Is it even appropriate? b) Does having normal-data help in any way (i'm assuming yes - as it would help the algorithm know the orientation of the original surface). c) I'm trying to avoid putting the point cloud into a voxel dataset and running marching cubes over it - but would it be foolish to try and avoid this? By the way: this is all in aid of easier procedural generation of a level mesh - so is related to game development ;-)

Orbital Fan

Jan 2, 2010 at 8:14 AM

I really should have given an example:

Suppose there are two spheres that are intersecting. I would want a mesh from the resulting intersection of the two primitives. This would be the equivalent of doing a CSG Union operation.

ernow

Jan 2, 2010 at 8:23 AM

Marching cubes are pretty much the standard as far as I know. Why are you trying to avoid them?

Do you have extra information about the point clouds, so you could take advantage of that? Are you using 'voxeldata' to compress the data requirements?

Orbital Fan

Jan 2, 2010 at 8:31 AM

From the way I understand marching cubes - it requires a continuous density function (which I don't have) - otherwise you end up with really blocky meshes. I was also aiming for something that could be used for terrain generation - which voxel datasets aren't completely appropriate for (high memory usage).

Medium9

Jan 2, 2010 at 8:57 AM

For Marching Cubes you'll just need a function that returns "inside" or "outside", and you can refine individual vertices using bisection. The resulting mesh wouldn't be optimal, but quite smooth.

Delaunay can be extended to 3D too, your primitives then become tetrahedera. Downside of this is mainly, that you'll segment entire volumes rather than just surfaces, and you already need a pointcloud to begin with.

Emergent

Jan 2, 2010 at 10:04 AM

Delaunay methods

Quote:
Original post by Orbital Fan
a) I can see how Delaunay Triangulation works on 2D data - but can it be extended to work in 3d? Is it even appropriate?

In 2d, a Delaunay triangulation partitions a region into triangles. In 3d, a Delaunay "triangulation" -- really "tetrahedralization" -- partitions a region into tetrahedra.

The idea in using Delaunay tetrahedralizations to reconstruct surfaces is to
1 - Partition space into tetrahedra using the Delaunay tetrahedralization
2 - Classify the different tetrahedra you get as either "solid" or "air" (let's call them)
3 - Use any tetrahedron face that is at a solid-air interface as a triangle in your mesh.

Ball-pivoting

Another class of algorithms for what you want to do are called "ball-pivoting" algorithms; this should be a useful search term.

TyrianFin

Jan 2, 2010 at 10:19 AM

helping words for google:
alpha shape
isosurface

some links:
http://www.netlib.org/voronoi/hull.html
http://www.loria.fr/~pougetma/software/alpha_shape/alpha_shape.html
http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html (2d java)

Computational Geometry Algorithms Library: (good one)
http://www.cgal.org/
http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

/Tyrian

Orbital Fan

Jan 2, 2010 at 5:40 PM

Wow thanks for the information - ball-pivoting and alpha shapes are what I had in mind.

rubicondev

Jan 3, 2010 at 4:36 AM

I don't know what's wrong with marching cubes tbh. It's true that the original paper looks blocky as it didn't have the refinement that people actually using marching cubes usually put in. This is to move the grid points closer to the intersections to remove that blockiness.

It's all explained here

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.