Delaunay2_5D: a Straightforward Algorithm for Fast Surface Reconstruction
Filed under: Algorithms, Computational Geometry, Graphics
Description
Delaunay2_5D is an algorithm for fast surface reconstruction from scattered points cloud. The algorithm is designed to be quick and light. With this tool you’ll be able to reconstruct on your “little” laptop huge points cloud (several millions of points) which are generally considered a Workstation Job.
The project was made possible thanks to the collaboration of Luca Di Angelo and Di Stefano Paolo.
The algorithm uses a mesh growing approach: starting form a seed triangle a front propagation is performed. This technique is generally less accurate than the ones that use Delaunay Triangulation, on the other side they are terribly faster and lighter, so they are preferred for huge models
Perfomances
Models
A few models to test the algorithm and verify the perfomances:
| Model | Number of points | Call |
| Nicolò da Uzzano (the one in the picture) | 1M | Delaunay2_5D.exe |
| Thai Statue | 5M | Delaunay2_5D.exe i 3 p1 a 20 |
| Foot | 10k | Delaunay2_5D.exe i 2 p1 |
| Armadillo | 170k | Delaunay2_5D.exe |
| Happy Buddha | 500k | Delaunay2_5D.exe i3 p1 f5 a 25 |
| Dragon | 430k | Delaunay2_5D.exe i2 p1 f5 a 30 |
| Rolling Stage | 600k | Delaunay2_5D.exe |
| Pala(Turbine Blade) | 350k | Delaunay2_5D.exe i 3 f 20 p 4 |
| Neptune | 2M | Delaunay2_5D.exe i 3 p1 a 20 |
| Blade | 850k | Delaunay2_5D i 5 p 2 f 20 a 25 |
| Pulley | 580k | Delaunay2_5D a 25 |
Delaunay2_5D take as input a binary file. To build your own input file see the usage below.
Usage
How to build an input file and how input parameter works can be found here:
Release
We currently have only one Win32 version of Delaunay2_5D.
Download for Win32
Release History:
- Delaunay2_5D v1.0 ( 01/02/2010)
- Delaunay2_5D v1.1 ( 15/02/2010)(It is now possible to insert the input file name as parameter)
Demo version
The demo version differs from the original in the output mode. It has no output parameter so it forces tha user to suppress STL file creation and to visualize the reconstructed surface in output window.
Contributor version
The contributor version returns an STL binary file of the reconstructed surface. It can be obtained with a small donation as encouragement to improve the code itself. The project was realized without any kind of economical help from any academic or commercial organizations.
|
Delaunay2_5D: Fast Surface Reconstruction– Contributor version is reserved to donators. The amount of the donation is 30 euro.
|
|||
| Once you have done this, please email us: giaccariluigi@msn.com As soon as possible (in a few days) you will receive our new release (and all future updates) of Delaunay2_5D. Alternatively, you can bestow using our banking coordinates:
|
|||
| Name : | Luigi Giaccari | ||
| IBAN (International Bank Account Number) : | IT 07 E05550 77710 000000483947 | ||
Further informations can be obtained on my skype contact: luigi.giaccari
Release notes
The Software provided has to be considered “as is” and it is without any kind of warranty. The authors deny any kind of warranty concerning the code as well as any kind of responsibility for problems and damages which may be caused by the use of the code itself including all parts of the source code.
Contacts
Delaunay2_5D is always under development…
For any problem, suggestion, question, bug report, whatever….
- giaccariluigi@msn.com
- skype contact: luigi.giaccari
Popularity: 4% [?]
Delaunay2_5D: Usage
Filed under: Algorithms, Computational Geometry, Graphics
Contents
When can it be used
Delaunay2_5D is designed for densely sampled surfaces, both open and closed one. The surface must be not too much rough and possibly with higher sampling in high curvature feature.
…and when can not
Delaunay2_5D wont work on:
- Sliced data: when the distance among slices is much higher than the distance among point of the same slice.
- Rough surfaces
- Not orientable surfaces
- Sharp edges coming from cad models (scanned ones should be meshed).
How to use it
Input format
After struggling on hundreds of points cloud formats I decided to feed the algorithm with a simple binary file. The file is composed by an integer indicating the number of points and a list of doubles indicating the coordinates.
The number of point is the first data and it is an “int” type. Points are stored this way: X1,Y1,Z1,X2,Y2,Z2…….
These are the Matlab commands to generate such file:
fid=fopen(name,'wb');%open input file for Delaunay2_5D fwrite(fid, np, 'int');%first data=the numbers of points; fwrite(fid,p,'double');%points; fclose(fid);%close the file
You can download tools to use D2_5D on matlab here: Download Now
And this are the C++ ones:
pFile =fopen("D2_5DInput.dat", "wb");//open input file for Delaunay2_5D nwritten=fwrite(&N, sizeof(int), 1, pFile);//first line (the number of points) nwritten=fwrite(&p, sizeof(double), N*3, pFile);//Write the points coordinate fclose(pFile);//close the file
Launching the .exe
In Matlab you can use:
!Delaunay2_5D.exe i 2 p 1 f 0 a 90
where the letters after the executable path are the input parameters described in the next section.
In C++, given an array p of Nx3 elemnts representing the points coordinate:
system("Delaunay2_5D.exe i 2 p 1 f 0 a 90 ");
Input parameters
The basic call is:
A professional use of Delaunay2_5D requires some knowledge about its input parameters.
- ‘i’=Number of meshing iteration. Default=1. Too high meshing iteration can slow down the algorithm and sometimes generates bad triangles. On the other side, it helps to fill big holes, so rise up the number of operation only if you find undesired holes in the output.
- ‘f’= enables a nearest neighbour filter. A nearest neighbour graph is computed, the meandist among points calculated. Points with distance less than meandist/f will be deleted. f must be >1, a 0 value will turn off the filtering. Use this parameter only if you have duplicated points in the input or points too close too each other.
- ‘p’=The “strength” of the post-processor. Set to zero turn off post-processing operations. Set to >0 attempts to fill small holes in the output. Default value is 1.
- ‘file’= the input file name. Ex Delaunay2_5D.exe file Bunny.dat . If omitted the input filename must be later inserted as console input.
- ‘w’: output window,(only contributor version) set to 0 suppress output window
- ‘o’: output file:(only contributor version) set to 0 returns an stl file. Set to 1 returns a binary file (this mode is for the developper). Set to 2 returns both of them.
There are several others option but for now it is clearer not considering all of them. A complete documentation will be published shortly.
I the meantime, to run some tests, you can use settings suggested in the model section.
Popularity: 2% [?]
Fast Surface Reconstruction: Delaunay2.5D
Filed under: Algorithms, Computational Geometry, Graphics
Can a surface reconstructor be faster than a 2D mesher?
It is coming soon the Delaunay2.5D algorithm a new fast surface reconstructor. It is currently in a prototype state, still have to code pre-processor and post-processor parts. I will include it in my thesis.
This algorithm can deal with millions of points in a matter of a few second, it is basically faster than a 2d delaunay triangulation. For this reason I am also thinking about extend it to 2D and 3D triangulations.
More infos about the algorithm performances and how does it work will be given in future. At the time I only have this video demostration and a demo version.I was impatient to publish something about it 
.
Delaunay2_5D has been released here.
Popularity: 27% [?]
About Surface Reconstruction From 3D Scatter
Filed under: Computational Geometry, Tutorials
I publish this post hoping to give an answer to the more common questions I receive on my e-mail about surface recostruction from scatter points.
The first thing we’ve got to see in our points cloud is that the resulting surface is in the z=f(x,y) form. If yes, than the solution is easier than it seems, we just have to triangulate x and y coordinates, for example using delaunay, and after that plot all trhee coordinates. Notice that if points are structured (diposed on a grid) there is no need to use delaunay to build a triangular mesh, that’s enough a for loop. An implementation of a structured grid generation can be found at:
http://www.advancedmcode.org/structured-triangular-mesh-generation.html
A complete example on how to plot a coloured surface in the z=f(x,y) form can be downloaded at:
http://www.advancedmcode.org/how-to-plot-a-coloured-surface-from-3d-scatter.html
It also shows how to colour the final surface with assingned rgb triplets at each points.
If the surface is not in the z=f(x,y) form, things get a little more complicated. Now we have to check if the surface is convex, if yes, we can smile. All we have to do now is to tessellate the 3D points with the convhulln function and then simply use the trisurf command to plot our surface. Since the final surface is convex, the convhull function ensure a correct tesselation.
And what if the final surface is not convex? We are entering in the more complicate field of surface recostruction. Now the recostruction is not assured to be correct and the algorithm to choose mainly depends on the kind of dataset we are facing:
- Closed surface: a crust based algorithm will be good, an implementation is on:
http://www.advancedmcode.org/surface-recostruction-from-scattered-points-cloud-mycrust-robust.html - Open surface: open surfaces are tricky, sometimes thay are not even orientable. For those the Crust based algotihm fails because it requires a volume that with an open surface can not be defined. An algorithm for open surfaces can be get at:
http://www.advancedmcode.org/surface-recostruction-from-scattered-points-cloud-mycrustopen.html - Filled clouds: when we want to get a surface from points generally all the points include in the input will be part of the final surface. But sometimes cloud points are filled, they can contain a lot of internal points that are not supposed to lye on the surface. This kind of dataset requires a ball pivoting algorithm or a ballfretting one that can be found at:
http://www.advancedmcode.org/surface-recostruction-from-scattered-points-cloud-the-ball-fretting.html - Sliced data: Sliced data are somehow easier to treat because, differently from scattered points cloud, here we partially know the points disposition. I’ll be working on one of this algorithm, I will publish a link when it is finished.
Popularity: 13% [?]
Surface Reconstruction From Scattered Points Cloud: MyCrustOpen
This part, differently from the first one, supports any kind of open surfaces. It can substitute tools like griddata in cases where points are completly scattered. If they aren’t in z=f(x,y) form griddata doesn’t work, a surface recostructor is needed.
Here is a brief description:
This version has been developed for open surface.
Differently from crust based algorithm does not ensure a tight triangluation and sometimes self-intersecant triangles are generated, it is also generally slower. The final surface may need some repair work which this utility does not offer.
But there are two great advantages, it can be applied on any kind of open surface for which the Crust fails, it supports not regular surface like the Moebius ribbon, and most of all, surface can have any kind of holes, open feature shouldn’t create problem.
You can see the screenshot or demo models for examples.
Here is a simple example:
load Nefertiti.mat%load input points from mat file [t]=MyCrustOpen(p); figure(1) hold on title('Output Triangulation','fontsize',14) axis equal trisurf(t,p(:,1),p(:,2),p(:,3),'facecolor','c','edgecolor','b')
Input:
p is a Nx3 array containing the 3D set of points
Output:
t are points id contained in triangles nx3 array .
If any problems occurs in execution, or if you found a bug, have a suggestion or question just contact me at:
reports about models on which the algorithm fails are greatly aprecciated.
This work is free thanks to users gratitude, if you find it useful consider buying me a beer. Thank you.
Popularity: 33% [?]
Translator
By N2H Follow Us
Video Posts
-
