Quick Delaunay Triangulation
Filed under: Algorithms, C, Computational Geometry, FEM, Geometry
Contents
QuickDel
It has always been a dream of mine to code a Delaunay triangulator. Last week I had 3 free days and I did it. I actually thought it was more complicated, as it often happens, when you are outside the problem it seems bigger than it really is.
In this post you will find a Delaunay triangulation algorithm. My idea is to start a project which purpose is to create a robust an efficient triangulation/meshing tool.
The first release will be Delaunay triangulation function QuickDelMex
Below a comparison with DelaunayTri from the computational geometry toolbox.
Number of points QuickDel Built-in Matlab speed-up
10 0.0002 s 0.0142 98.69% s
100 0.0002 s 0.0094 97.61% s
1000 0.0016 s 0.0099 84.13% s
10000 0.0149 s 0.0707 78.96% s
100000 0.1856 s 1.2044 84.59% s
1000000 2.5094 s 14.1102 82.22% s
t=QuickDelMex(p) (version 0.3)
returns the Delaunay triangulation of the 2D point set p;
INPUT:
- * p: double array of size 2xN. The list of unique points [x1 y1,x2 y2];
OUTPUT:
- * t: double array of size ntx3. It contains the triangles of the Delaunay triangulation. Each rows contains 3 indexes of the points forming the triangle. Indexes are sorted counterclockwise; first points is flagged as one.
NOTES:
- * -This function is a prototype so don’t trust too much, please check the results and in case send bug report.
- * -This function is optimized for uniform random dataset, sparse datasets may slow down the algorithm.
- * -This function may not return the whole convex hull. Thin boundary triangles may be discarded.
- *- v0.3 is alittle slower but much more robust than v0.2.
Author: Luigi Giaccari (giaccariluigi@msn.com)
see also DelaunayTri delaunay delaunayn
Downloads
Matlab
You can download MEX Files of QuickDel here (win32 and linux):
A test to evaluate performances is also available on Matlab file exchange (Download Now)
C++
A Win32 executable is available here (v0.2):
it asks for the number of points to be triangulated. Once the triangulation has been done it prints a text file (a matlab m-file) which allows to visualize the triangulations inside Matlab.
I can also build a win32 .dll, but I was too lazy to do it, if you want it please contact me.
Acknowledgements
- This function uses the robust predicates from Jonathan Richard Shewchuk
Contacts
Please send bug reports/suggestions at: giaccariluigi@msn.com
This utility can be greatly enlarged, please compile the following survey.
Popularity: 2% [?]
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: 1% [?]
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: 2% [?]
Translator
Follow Us
Video Posts
