1

I would like to represent a surface, with 3D Delaunay Triangulation. The vertices must be my original input data, a LiDAR point cloud from an urban area. So, the surface must adjust/adapt the input information.

Actually, what I need to do is the following:

  • I have a 3D point cloud (x, y, z) from an urban area;
  • I need to represent the surface of this area;
  • I would like to do a 3D delaunay triangulation (I did with CGAL and I got the tetrahedrons) and identify only the triangles that represent the surface (with CGAL I have 4 vertices and I can't define which ones represent the surface triangle);
  • Since these surface triangles are known, I need to give a point and get the triangle that contains this given point.

I would like to know which function I need. I saw the "3D surface mesh generation", "3D Delaunay Triangulation", "Surface Reconstruction from point sets", "3D Mesh generation" and "3D Alpha Shapes". But I am not sure which one fits better to my work/need. What function could give me the surface triangles (represented by points from my initial dataset) as output.

Does anyone have a suggestion?

Andre Silva
  • 4,782
  • 9
  • 52
  • 65
ricãO
  • 61
  • 1
  • 10
  • If it's a terrain, you can use this [example](http://doc.cgal.org/latest/Triangulation_2/index.html#title14) – sloriot Jan 16 '15 at 13:04
  • Thanks for the tip. Actually, it is a urban area, with buildings. I would like to get the surface triangles by using the 3D Delaunay triangulation / 3D alpha shape. But, I did not figure out yet how can I get it. Cheers! – ricãO Jan 17 '15 at 21:35

1 Answers1

2

You can use Fade 2.5D, it uses triangles to mesh surface points:

http://www.geom.at/fade2d/html/ enter image description here

The library is free for scientific use, you can find a code example in Example7 (I'm the author).

Geom
  • 827
  • 4
  • 15
  • Thank you very much for your reply! I checked the description of 'Fade 2.5D'. It is very interesting! Actually, I was using the 'qhull' with the same type of structure, the 2.5 Delaunay Triangulation. But in my case, in urban areas and LiDAR point cloud, I will probably have 2 points with the same "x and y" and different heights. I guess it doesn't work with 'Fade 2.5D', right? This was the reason why I change my approach to a 3D Delaunay Triangulation. But, I will try to use Fade 2.5D for other application. Thank you for the suggestion! – ricãO Jan 09 '15 at 15:36
  • I understand. Yes, in 2.5D only one height per (x,y) pair is possible but subsequent insertions of existing (x,y) pairs with different heights are not an error, such points are ignored. This is okay for terrain triangulations but in urban areas the result might be bad. – Geom Jan 09 '15 at 16:06
  • Is it possible to ignore the lowest one and keep the tallest one? Does 'Fade 2.5D' have functions to find a triangle that contains a given point? And is it possible to know what are the neighbors of a given triangle? Thanks! – ricãO Jan 09 '15 at 16:19
  • You can sort your (x,y,z) tuples and when identical (x,y) pairs occur, keep only the ones with the largest z-coordinate. Fade_2D::locate(Point2& p) returns a triangle that contains a specific point p and this is very fast. Each triangle knows its three neighbor triangles. Btw: You can also insert constraint edges in order to enforce certain edges in the triangulation. – Geom Jan 09 '15 at 16:31
  • Thank you for the promptly reply. I will think about this option! Regards, Henrique. – ricãO Jan 09 '15 at 18:20