

Hi,
I am learning geometric modelling and I want to do some research on 3D Delaunay. I just tried 3d delaunay function provided by CGAL and was impressed by its high efficiency. I implemented 3D delaunay myself with Incremental Insertion Algorithms, but the efficiency was much less than CGAL.
In addition, it needs to add eight auxiliary bounding points before point insertion during 3D Delaunay triangulation. In my program, the coordinates of the eight points was configured with the rules that the bounding box formed by the eight points can contain the whole point set. But the triangulation result is a bit different on surface compared with 3D delaunay of CGAL.
So, I wonder how to find the exact algorithm and references of CGAL's 3D delaunay function.
Thanks for any help.

Administrator

Hi,
Thank you for your nice email.
Though the basic incremental algorithm used is very standard (see e.g., Bowyer 1981), the 3d Delaunay triangulation of CGAL is the result of quite a long research process, in particular on robustness issues. You can find a few references here https://members.loria.fr/Monique.Teillaud/biblio/Keyword/CGAL_.html but they are not the only ones.
If you want to know more about the details of the implementation, well, the CGAL source code is public…
Best regards,
Hi, I am learning geometric modelling and I want to do some research on 3D Delaunay. I just tried 3d delaunay function provided by CGAL and was impressed by its high efficiency. I implemented 3D delaunay myself with Incremental Insertion Algorithms, but the efficiency was much less than CGAL. In addition, it needs to add eight auxiliary bounding points before point insertion during 3D Delaunay triangulation. In my program, the coordinates of the eight points was configured with the rules that the bounding box formed by the eight points can contain the whole point set. But the triangulation result is a bit different on surface compared with 3D delaunay of CGAL.
So, I wonder how to find the exact algorithm and references of CGAL's 3D delaunay function.
Thanks for any help.
 View this message in context: http://cgaldiscuss.949826.n4.nabble.com/TheexactalgorithmandreferencesofCGALs3DDelaunayfunctiontp4662096.html Sent from the cgaldiscuss mailing list archive at Nabble.com.
 You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss


Hi Monique, Thank you for your kind advice. I will learn delaunay of CGAL with the references as you mentioned. For CGAL code, I just searched in the CGAL directory about delaunay and find many related files with .h extension. So, can you recommend the target program files that contain the detail of the algorithm implementation of 3d delaunay. Best wishes!
 Original  Date: Tue, Jul 26, 2016 02:43 PM Subject: Re: [cgaldiscuss] The exact algorithm and references of CGAL's 3DDelaunay function
Hi,
Thank you for your nice email.
Though the basic incremental algorithm used is very standard (see e.g., Bowyer 1981), the 3d Delaunay triangulation of CGAL is the result of quite a long research process, in particular on robustness issues. You can find a few references here https://members.loria.fr/Monique.Teillaud/biblio/Keyword/CGAL_.html but they are not the only ones.
If you want to know more about the details of the implementation, well, the CGAL source code is public…
Best regards,
Hi, I am learning geometric modelling and I want to do some research on 3D Delaunay. I just tried 3d delaunay function provided by CGAL and was impressed by its high efficiency. I implemented 3D delaunay myself with Incremental Insertion Algorithms, but the efficiency was much less than CGAL. In addition, it needs to add eight auxiliary bounding points before point insertion during 3D Delaunay triangulation. In my program, the coordinates of the eight points was configured with the rules that the bounding box formed by the eight points can contain the whole point set. But the triangulation result is a bit different on surface compared with 3D delaunay of CGAL.
So, I wonder how to find the exact algorithm and references of CGAL's 3D delaunay function.
Thanks for any help.
 View this message in context: http://cgaldiscuss.949826.n4.nabble.com/TheexactalgorithmandreferencesofCGALs3DDelaunayfunctiontp4662096.html Sent from the cgaldiscuss mailing list archive at Nabble.com.
 You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss

Administrator

The first line shows: #include <CGAL/Delaunay_triangulation_3.h>
Hi Monique, Thank you for your kind advice. I will learn delaunay of CGAL with the references as you mentioned. For CGAL code, I just searched in the CGAL directory about delaunay and find many related files with .h extension. So, can you recommend the target program files that contain the detail of the algorithm implementation of 3d delaunay. Best wishes!
 Original  Date: Tue, Jul 26, 2016 02:43 PM Subject: Re: [cgaldiscuss] The exact algorithm and references of CGAL's 3DDelaunay function
Hi,
Thank you for your nice email.
Though the basic incremental algorithm used is very standard (see e.g., Bowyer 1981), the 3d Delaunay triangulation of CGAL is the result of quite a long research process, in particular on robustness issues. You can find a few references here https://members.loria.fr/Monique.Teillaud/biblio/Keyword/CGAL_.html but they are not the only ones.
If you want to know more about the details of the implementation, well, the CGAL source code is public…
Best regards,
Hi, I am learning geometric modelling and I want to do some research on 3D Delaunay. I just tried 3d delaunay function provided by CGAL and was impressed by its high efficiency. I implemented 3D delaunay myself with Incremental Insertion Algorithms, but the efficiency was much less than CGAL. In addition, it needs to add eight auxiliary bounding points before point insertion during 3D Delaunay triangulation. In my program, the coordinates of the eight points was configured with the rules that the bounding box formed by the eight points can contain the whole point set. But the triangulation result is a bit different on surface compared with 3D delaunay of CGAL.
So, I wonder how to find the exact algorithm and references of CGAL's 3D delaunay function.
Thanks for any help.
 View this message in context: http://cgaldiscuss.949826.n4.nabble.com/TheexactalgorithmandreferencesofCGALs3DDelaunayfunctiontp4662096.html Sent from the cgaldiscuss mailing list archive at Nabble.com.
 You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss

Administrator

There is also this nice article by Liu and Snoeyink which gives details on several important aspects of implementations of 3D Delaunay triangulations, including the one of CGAL (at the time of 2005 at least) : http://library.msri.org/books/Book52/files/23liu.pdf


Hi, Monique Thank you for your instrutction. I will learn the code and the references, although the Delaunay hierarchy is a little difficult to understand. Best regards!
 原始邮件  发送时间: 2016年7月26日(星期二) 晚上10:58 主题: Re: [cgaldiscuss] The exact algorithm and references of CGAL's3DDelaunay function
The first line shows: #include <CGAL/Delaunay_triangulation_3.h>
Hi Monique, Thank you for your kind advice. I will learn delaunay of CGAL with the references as you mentioned. For CGAL code, I just searched in the CGAL directory about delaunay and find many related files with .h extension. So, can you recommend the target program files that contain the detail of the algorithm implementation of 3d delaunay. Best wishes!
 Original  Date: Tue, Jul 26, 2016 02:43 PM Subject: Re: [cgaldiscuss] The exact algorithm and references of CGAL's 3DDelaunay function
Hi,
Thank you for your nice email.
Though the basic incremental algorithm used is very standard (see e.g., Bowyer 1981), the 3d Delaunay triangulation of CGAL is the result of quite a long research process, in particular on robustness issues. You can find a few references here https://members.loria.fr/Monique.Teillaud/biblio/Keyword/CGAL_.html but they are not the only ones.
If you want to know more about the details of the implementation, well, the CGAL source code is public…
Best regards,
Hi, I am learning geometric modelling and I want to do some research on 3D Delaunay. I just tried 3d delaunay function provided by CGAL and was impressed by its high efficiency. I implemented 3D delaunay myself with Incremental Insertion Algorithms, but the efficiency was much less than CGAL. In addition, it needs to add eight auxiliary bounding points before point insertion during 3D Delaunay triangulation. In my program, the coordinates of the eight points was configured with the rules that the bounding box formed by the eight points can contain the whole point set. But the triangulation result is a bit different on surface compared with 3D delaunay of CGAL.
So, I wonder how to find the exact algorithm and references of CGAL's 3D delaunay function.
Thanks for any help.
 View this message in context: http://cgaldiscuss.949826.n4.nabble.com/TheexactalgorithmandreferencesofCGALs3DDelaunayfunctiontp4662096.html Sent from the cgaldiscuss mailing list archive at Nabble.com.
 You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss


Hi, That's an interesting thread. In this article it's said that The hierachical tessellation makes the asymptopic point location time to be O(() log(n)), which is optimal
Does it mean that using CGAL's Delaunay_triangulation_3 I can construct 3D dynamic hull for N points, and then locate each new point in time O(log N) ? Are there any asymptotic estimates for the construction of 3d Delaunay triangulation? Is it O(N log N) ? Thanks, Ilya Palachev There is also this nice article by Liu and Snoeyink which gives details on several important aspects of implementations of 3D Delaunay triangulations, including the one of CGAL (at the time of 2005 at least) : http://library.msri.org/books/Book52/files/23liu.pdf 20160726 7:58 GMT07:00 Monique Teillaud <[hidden email]>: The first line shows: #include <CGAL/Delaunay_triangulation_3.h> Hi Monique, Thank you for your kind advice. I will learn delaunay of CGAL with the references as you mentioned. For CGAL code, I just searched in the CGAL directory about delaunay and find many related files with .h extension. So, can you recommend the target program files that contain the detail of the algorithm implementation of 3d delaunay. Best wishes!  Original  Date: Tue, Jul 26, 2016 02:43 PM Subject: Re: [cgaldiscuss] The exact algorithm and references of CGAL's 3DDelaunay function Hi, Thank you for your nice email. Though the basic incremental algorithm used is very standard (see e.g., Bowyer 1981), the 3d Delaunay triangulation of CGAL is the result of quite a long research process, in particular on robustness issues. You can find a few references here https://members.loria.fr/Monique.Teillaud/biblio/Keyword/CGAL_.html but they are not the only ones. If you want to know more about the details of the implementation, well, the CGAL source code is public… Best regards, Hi, I am learning geometric modelling and I want to do some research on 3D Delaunay. I just tried 3d delaunay function provided by CGAL and was impressed by its high efficiency. I implemented 3D delaunay myself with Incremental Insertion Algorithms, but the efficiency was much less than CGAL. In addition, it needs to add eight auxiliary bounding points before point insertion during 3D Delaunay triangulation. In my program, the coordinates of the eight points was configured with the rules that the bounding box formed by the eight points can contain the whole point set. But the triangulation result is a bit different on surface compared with 3D delaunay of CGAL.
So, I wonder how to find the exact algorithm and references of CGAL's 3D delaunay function.
Thanks for any help.
 View this message in context: http://cgaldiscuss.949826.n4.nabble.com/TheexactalgorithmandreferencesofCGALs3DDelaunayfunctiontp4662096.html Sent from the cgaldiscuss mailing list archive at Nabble.com.
 You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss


Hi, That's an interesting thread. In this article it's said that The hierachical tessellation makes the asymptopic point location time to be O(() log(n)), which is optimal
Does it mean that using CGAL's Delaunay_triangulation_3 I can construct 3D dynamic hull for N points, and then locate each new point in time O(log N) ?
Are there any asymptotic estimates for the construction of 3d Delaunay triangulation? Is it O(N log N) ?
of course not, if the result as quadratic size, you cannot compute it in sub quadratic time.
The exact hypotheses on your point set are:  For any random subset of your point set, the size of the 3D Delaunay triangulation is linear in the number of points  You construct the Delaunay triangulation inserting the points in a random order (this is for construction, not for point location)
if the first hypothesis is not fulfilled you can express the complexity in terms using the function: r—> expected size of the triangulation of a subset of size r
https://hal.inria.fr/inria00166711
Olivier


Hi Olivier, Thanks for quick answer. My comments below. Hi, That's an interesting thread. In this article it's said that The hierachical tessellation makes the asymptopic point location time to be O(() log(n)), which is optimal
Does it mean that using CGAL's Delaunay_triangulation_3 I can construct 3D dynamic hull for N points, and then locate each new point in time O(log N) ?
Are there any asymptotic estimates for the construction of 3d Delaunay triangulation? Is it O(N log N) ?
of course not, if the result as quadratic size, you cannot compute it in sub quadratic time.
Yes, it's clear. According to Theorem 8 from your article, the guaranteed working time of algorithm is O(N^2) for 3D case. The exact hypotheses on your point set are:  For any random subset of your point set, the size of the 3D Delaunay triangulation is linear in the number of points  You construct the Delaunay triangulation inserting the points in a random order (this is for construction, not for point location) if the first hypothesis is not fulfilled you can express the complexity in terms using the function: r—> expected size of the triangulation of a subset of size r https://hal.inria.fr/inria0016671
Thanks for this link. For my use case it seems that all points lie almost (with some "epsilon" precision) on the surface of some polyhedra, and points are the "samples" of its surface. It seems to me that for this case the conditions of Theorem 12 from [ https://graphics.stanford.edu/courses/cs46802winter/Papers/linearDT.pdf ] hold and, hence, the first hypothesis holds, too. Is it true, how do you think? Best regards, Ilya Palachev


Hi Olivier, Thanks for quick answer. My comments below. Hi, That's an interesting thread. In this article it's said that The hierachical tessellation makes the asymptopic point location time to be O(() log(n)), which is optimal
Does it mean that using CGAL's Delaunay_triangulation_3 I can construct 3D dynamic hull for N points, and then locate each new point in time O(log N) ?
Are there any asymptotic estimates for the construction of 3d Delaunay triangulation? Is it O(N log N) ?
of course not, if the result as quadratic size, you cannot compute it in sub quadratic time. Yes, it's clear. According to Theorem 8 from your article, the guaranteed working time of algorithm is O(N^2) for 3D case. The exact hypotheses on your point set are:  For any random subset of your point set, the size of the 3D Delaunay triangulation is linear in the number of points  You construct the Delaunay triangulation inserting the points in a random order (this is for construction, not for point location) if the first hypothesis is not fulfilled you can express the complexity in terms using the function: r—> expected size of the triangulation of a subset of size r https://hal.inria.fr/inria0016671 Thanks for this link. For my use case it seems that all points lie almost (with some "epsilon" precision) on the surface of some polyhedra, and points are the "samples" of its surface. It seems to me that for this case the conditions of Theorem 12 from [ https://graphics.stanford.edu/courses/cs46802winter/Papers/linearDT.pdf ] hold and, hence, the first hypothesis holds, too. Is it true, how do you think?
Not exactly. The result of Attali&Boissonnat is for an (epsilon,kappa) sample. So the points are (exactly) on the polyhedron and satisfy some deterministic condition: (not too many points close together, no big void in the sampling).
It seems that your points are not on the surface and your sampling conditions are not detailed.
It should work well, but you cannot deduce directly a formal proof of good complexity.
Olivier

