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: 3% [?]
Delaunay2_5D: Performances
Filed under: Algorithms, Computational Geometry, Graphics
Go to Main Post
Perfomances
| Model | n° of input points | n° of output triangles | Time [s] | Mem. Usage [MB] | Rate [ktriangle/s] | Defectivness | |||
| nnmv | holes | ||||||||
| nholes | nbe | ||||||||
| Open surfaces | Foot (**) | 10010 | 19972 | 0.31 | 2.39 | 630.1 | 0 | 0 | – |
| Rolling Stage (**) | 596903 | 1193303 | 2.58 | 150.72 | 460.1 | 3 | 15 | 505 | |
| Valve seat (†) | 675049 | 1348338 | 3.08 | 170.55 | 438.2 | 8 | 20 | 1456 | |
| Nicolò da Uzzano (**) | 946760 | 1891992 | 3.81 | 238.96 | 454.2 | 1 | 0 | – | |
| Thai Statue (*) | 4999997 | 9994088 | 20.43 | 1238.62 | 489.0 | ||||
| Closed surfaces | Rocker-arm (**) | 10044 | 20084 | 0.38 | 2.39 | 515.2 | 0 | 0 | – |
| Stanford Bunny (*) | 35947 | 71884 | 0.097 | 9.05 | 735.3 | 0 | 0 | – | |
| Horse (**) | 48485 | 96859 | 0.14 | 12.61 | 673.9 | 2 | 2 | 19 | |
| Armadillo (*) | 172975 | 345934 | 0.520 | 41.79 | 665.7 | 0 | 0 | – | |
| Pulley (**) | 293672 | 587181 | 0.88 | 77.23 | 661.0 | 1 | 2 | 10 | |
| Turbine Blade 2 (†) | 346103 | 791948 | 1.74 | 100.06 | 449.1 | 14 | 3 | 18 | |
| Dragon (***) | 435545 | 805376 | 1.71 | 107.58 | 427.1 | 12 | 28 | 249 | |
| Bimba (**) | 502694 | 1005172 | 1.49 | 126.99 | 676.1 | 16 | 12 | 220 | |
| Happy Buddha (***) | 503897 | 1004540 | 2.09 | 136.95 | 480.4 | 32 | 47 | 462 | |
| Chinese Dragon (**) | 655980 | 1311296 | 1.81 | 165.59 | 723.7 | 47 | 35 | 928 | |
| Turbine Blade (***) | 869555 | 1759357 | 2.73 | 227.74 | 454.8 | 42 | 66 | 1054 | |
| Amphora (**) | 1308237 | 2616596 | 5.99 | 332.56 | 439.2 | 0 | 1 | 10 | |
| Neptune (**) | 2003933 | 4007628 | 8.32 | 488.79 | 481.6 | X | X | X | |
| Asian Dragon (*) | 3609601 | 7218442 | 12.2 | 894.23 | 587.5 | X | X | X | |
| (*) http://www.graphics.stanford.edu/data/3Dscanrep/ (**) http://shapes.aimatshape.net/ |
|||||||||
The test was performed on My laptop: Asus pro31s. It has 2.4Ghz dual core processor and 2GB of RAM. For some of the models (bigger ones) I was able to mesh them but not to analyze their defectiveness on meshlab or CATIA.
Speed
Tests shows that Delaunay2_5D has a triangles rate production of 400-700 kTriangles/sec. It can mesh a million points cloud in about 4 secs.
Memory Usage
The algorithm is also designed to save memory, the RAM memory usage (in byte) can be estimate before launching the algorithm with the following formula: 240 x N. Where N is the number of points, each points requires about 240 byte of memory. A million points cloud requires only 240MB of RAM.
Quality of Triangles
The quality of triangles is comparable with Delaunay based methods.
Defectiveness
Non manifold vertices and holes
Delaunay2_5D can generated non manifold vertexes and odes not give warranty of a watertight surface reconstruction. If you care about them you have to use a post processing tool.
Non manifold edges
Delaunay2_5D can generate non manifold edges, if you found some, check your clouds has no duplicated points. If it hasn’t you just found a bug, please send me a report.
Duplicated triangles or triangles with different orientation
They can not be generated. if you found some, check your clouds has no duplicated points. If it hasn’t you just found a bug, please send me a report.
Popularity: 5% [?]
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: 28% [?]
Structured Triangular Mesh Generation
Popularity: 21% [?]
Translator
By N2H Follow Us
Video Posts
-
