Delaunay2_5D: Performances
Filed under: Algorithms, Computational Geometry, Graphics
17 Comments
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% [?]
Related Posts
Comments
17 Comments on Delaunay2_5D: Performances
-
KARTHIK on
Sun, 14th Feb 2010 06:16
-
Puneeth on
Sun, 21st Feb 2010 07:53
-
Puneeth on
Mon, 22nd Feb 2010 13:23
-
SUNIL on
Tue, 23rd Feb 2010 16:27
-
Luigi Giaccari on
Wed, 24th Feb 2010 16:05
hi sir..
Am doing final year B.TECH( Information Technology) in Jerusalem college of engineering..
My final year project is based on 3D reconstruction from 2D slices..
i have used DELAUNAY triangulation for surface reconstruction..
the final output is not smooth and it contains just connected triangles..
In order to get a smooth output like that bunny or dragon, what should i do…?
If you have any matlab code for that, kindly help me ..
THANKS AND REGARDS
R.KARTHIK
[Reply]
hello sir,
i have downloaded some cloud points from the links given in “Performances” ( the ones you have tested and tabulated ) but unable to run the prog on these databases as they are not in .dat format but in .ply.. .i even downloaded the tools u have provided,but unable to create .dat file from .ply.. . can u please kindly help regardin this.. ?
[Reply]
Luigi Giaccari Reply:
February 21st, 2010 at 09:22
I have checked all the models, they are in .dat format. Can you please be more specific and tell me which model created you problem?
I will fix it as soon as I can
[Reply]
Puneeth Reply:
February 21st, 2010 at 17:17
sir,
thank you for your prompt response 
i executed Delaunay2_5D.exe in windows aswell as in MATLAB R2009b.. .the program works fine on bunny.dat. I went through your “performance” table and was intrested in running the program on dragon (http://lodbook.com/models/) so i downloaded it and found tat the file was in .ply format i.e., dragon_vrip.ply. I think Delaunay2_5D.exe works only on .dat format files (correct me if i am wrong) so i just wanted to know how you could run Delaunay2_5D.exe on those many files in the table.. . And i could convert .mat files to .dat files using BuildD2_5DInputFile.m is this it or can this convert any file to .dat file??? plz help.. . 
Thank you
[Reply]
Puneeth Reply:
February 21st, 2010 at 18:46
sir i wold like to add to the above comment that, these files Nicolò da Uzzano (the one in the picture), Thai Statue, Foot, Armadillo, Happy Buddha, Dragon, Rolling Stage, Pala(Turbine Blade), Neptune which you have uploaded in megaupload work well with the program.. .i just wanted to know how you could run others i.e, those in th table (open surfaces and closed surfaces) which i think you have taken from
http://www.graphics.stanford.edu/data/3Dscanrep/
http://www.lodbook.com/models/
unfortunately 3d samples here are in .ply format
Luigi Giaccari Reply:
February 21st, 2010 at 21:49
You can find all the informations here:
http://www.advancedmcode.org/delaunay2_5d-usage.html
If something is not clear feel free to ask more.
Luigi
Hello sir,
Thank you for your prompt response. Sir i also wanted to ask you few more things about Delaunay2_5D, sorry if i am bothering you too much.. .
1) Was this program Delaunay2_5D written as a m-file and then converted to executable(exe) using MATLAB Compiler or written in c++. I was interested to know because i have been working on surface reconstruction.
2)Can smooth surfaces be reconstructed using your Mycrust just like Delaunay2_5D ?
3) Also can you let me know based on which algorithm,Mycrust was written.
again sorry for the trouble.. .
Thanking you.
[Reply]
Luigi Giaccari Reply:
February 22nd, 2010 at 13:32
Don’t worry, I appreciate your interest.
1)Delaunay2_5D is totally C++ coded. The surface is rendered with opengl using glut.
2)MyCrust is more robust than deluany2.5D but it can only handle closed surfaces a clouds smaller than about 200k-300k. It also more than 100 times slower than delaunay2_5D.
3) It is a long story…..
Thank to you
[Reply]
Puneeth Reply:
February 22nd, 2010 at 15:41
hello sir,
One more doubt 
why use MyCrust when trisurf is available in MATLAB.. ? actually we are a group of 4 members and we have taken a proj on surface reconstruction.. .
First we din know about this function trisurf.. . we came across your program MyCrust part 1,2,3.. . then came across deluany2.5D and now trisurf.. .Actually we haven studied MATLAB extensively.. .we had used it few yrs back in DSP labs.. .other than some DSP functions we don’t know the other commands etc.. .so now confused on how to proceed on this proj
[Reply]
Luigi Giaccari Reply:
February 22nd, 2010 at 16:08
Trisurf is just a command to plot a triangulated surface. MyCrust and deluany2_5D are tools to triangulate scattered points cloud.
Once you have the triangulation you can use trisurf but only after you have it
Hello Sir,
Based on ur reply to puneeth’s questions , I have few more doubts N think u will rectify them. we have taken up the surface reconstruction project as our final year degree project (for a period of 2 months). Now i have this broad overview of our project:
1)we collected some of the databases i.e collection of different 3d models both open and closed surface.
2)we thought of using that MYCRUST and MYCRUSTOPEN algorithm for closed and opensurface respectively.After execution I concluded that they are mutually exclusive .
Based on some sources
We divided our task into 3 phases namely:
phase1:with the dense cloud of input points we form the initial triangulation approximation for the unknown surface.
phase2:Using again the input points and the phase1 output we thought of obtaining the phase2 output that contains less number of vertices (i.e optimisation) using the energy function.
phase3:using phase2 output and input points final surface should be built .
now my doubts is:
After forming that tight triangulation (phase 1)approximation which contains more number of triangles ,how can we proceed to optimize that for fewer number of vertices considering our first approximation..?
[Reply]
You can simplify the surface depending on the curvature. But remember that once simplified the cloud it can be difficult re-use a surface reconstructor.
Look for “surface simplification algorithms”
Surface reconstruction algorithms requires generally a uniform sampling, or higher sampling in high curvature feature. In this field 3 point don’t make a plane.
To reduce the number of points you may be interested in this:
http://www.advancedmcode.org/gltree-matlab-example-nearest-neighbor-filter-function.html
[Reply]
SUNIL Reply:
February 24th, 2010 at 20:36
Thanks for your valuable reply.
Sir I need your help in understanding of the MYROBUSTCRUST algorithm.
I have thought that “delaunayn” function applied to the input points cloud(for ex:skull)
returns the co-ordinates(X,Y,Z ) of the triangles that are formed in the neighbourhood,IS it so ,if not please correct me.
Also the algorithm includes Circumcentre n circumradius calculation . what is the need of that ? is that for reconstruction? if so how is that done ,please explain with an example. if you are not able to explain all the things please provide the source that explains these topics in detail.
Next what is the part of connectivity and manifold extraction ? please provide the concepts that explains the flow of algorithm in each individual function.
Now in phase 2 i had enquired that how to reduce the number of vertices.?
as u have said to go through “surface simplification algorithm, But my doubt is that with the output of first phase (which contains the t and tnorm points ,If u can recall) how can we reduce the normalized functions i.e reducing the number of triangles on the surface where the reduction doesn’t cause significant changes..?
Is that possible..? If i am wrong please correct me…!
I may be disturbing you a lot but kindly note that i will be waiting for your reply…
[Reply]
Luigi Giaccari Reply:
February 24th, 2010 at 23:03
Sir,
you are asking me to do your job.
If you want to develop an utility we can agree a fair price, bu t i can not be your teacher for every single step.
Luigi
[Reply]
Tell me what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!
Include MATLAB code in your comment by doing the following:
<pre lang="MATLAB">
%insert code here
</pre>
Translator
Follow Us
Video Posts
Luigi Giaccari Reply:
February 14th, 2010 at 09:36
O the usage post: http://www.advancedmcode.org/delaunay2_5d-usage.html
You can read: Delaunay2_5D wont work on:
* Sliced data: when the distance among slices is much higher than the distance among points of the same slice.
For sliced data there are specific algorithms because it is a different ” type of points cloud”. The good news is that generally this is an easier case to treat
You can use this algorithm only if you make the points density more uniform, maybe scaling along the axis slices are generated.
Feel free to ask more
[Reply]
karthik ramamurthy Reply:
February 14th, 2010 at 15:43
hello sir..
do you have any suggestions to proceed with this case then…?
do you have any coding for this …
please help me out..
THANKS FOR YOUR TIMELY REPLY
[Reply]
Luigi Giaccari Reply:
February 14th, 2010 at 15:46
I need to see the cloud.
Send them on my e-mail or upload them on megaupload,
if it doesn’t take too much time I’ll give a look.