Quick Delaunay Triangulation

March 16, 2010 by Luigi Giaccari · 8 Comments
Filed under: Algorithms, C, Computational Geometry, FEM, Geometry 
VN:F [1.8.8_1072]
Rating: +1 (from 1 vote)
VN:F [1.8.8_1072]
Rating: 9.0/10 (5 votes cast)

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):

Download QuickDelMex Version 0.3

A test to evaluate performances is also available on Matlab file exchange (Download Now)

C++

A Win32 executable is available here (v0.2):

Download QuickDel.exe Version 0.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

Contacts

Please send bug reports/suggestions at: giaccariluigi@msn.com

This utility can be greatly enlarged, please compile the following survey.

What would you like too see on the next version of QuickDel?









VN:F [1.8.8_1072]
Rating: 9.0/10 (5 votes cast)
VN:F [1.8.8_1072]
Rating: +1 (from 1 vote)

Popularity: 2% [?]

Share and Enjoy:
  • Print
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Blogplay
  • Live
  • PDF
  • Technorati
  • Twitter
  • Yahoo! Bookmarks
  • Add to favorites
  • email
  • MySpace
  • RSS

Delaunay2_5D: a Straightforward Algorithm for Fast Surface Reconstruction

February 1, 2010 by Luigi Giaccari · 4 Comments
Filed under: Algorithms, Computational Geometry, Graphics 
VN:F [1.8.8_1072]
Rating: 0 (from 0 votes)
VN:F [1.8.8_1072]
Rating: 10.0/10 (2 votes cast)

Contents

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

Perfomances of Delaunay2_5D

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:

Basic Usage

Release

We currently have only one Win32 version of Delaunay2_5D.

Download for Win32

Download Delaunay2_5D Version 1.1 demo

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….

VN:F [1.8.8_1072]
Rating: 10.0/10 (2 votes cast)
VN:F [1.8.8_1072]
Rating: 0 (from 0 votes)

Popularity: 1% [?]

Share and Enjoy:
  • Print
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Blogplay
  • Live
  • PDF
  • Technorati
  • Twitter
  • Yahoo! Bookmarks
  • Add to favorites
  • email
  • MySpace
  • RSS

Delaunay2_5D: Performances

February 1, 2010 by Luigi Giaccari · 17 Comments
Filed under: Algorithms, Computational Geometry, Graphics 
VN:F [1.8.8_1072]
Rating: 0 (from 0 votes)
VN:F [1.8.8_1072]
Rating: 0.0/10 (0 votes cast)

 

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/

(***) http://www.lodbook.com/models/

(†) www.scansystems.it

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.

Go to Main Post

VN:F [1.8.8_1072]
Rating: 0.0/10 (0 votes cast)
VN:F [1.8.8_1072]
Rating: 0 (from 0 votes)

Popularity: 2% [?]

Share and Enjoy:
  • Print
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Blogplay
  • Live
  • PDF
  • Technorati
  • Twitter
  • Yahoo! Bookmarks
  • Add to favorites
  • email
  • MySpace
  • RSS

Next Page »