# The exact algorithm and references of CGAL's 3D Delaunay function

10 messages
Open this post in threaded view
|

## The exact algorithm and references of CGAL's 3D Delaunay function

 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.
Open this post in threaded view
|

## Re: The exact algorithm and references of CGAL's 3D Delaunay function

 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, --Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique  On 26 Jul 2016, at 04:56, wen <[hidden email]> wrote:Hi, I am learning geometric modelling and I want to do some research on 3DDelaunay. I just tried 3d delaunay function  provided by CGAL and wasimpressed by its high efficiency. I implemented 3D delaunay myself withIncremental  Insertion Algorithms, but the efficiency was much less thanCGAL. In addition, it needs to add eight auxiliary bounding points before pointinsertion during 3D Delaunay  triangulation. In my program, the coordinatesof the eight points was configured with the rules that the bounding  boxformed by the eight points can contain the whole point set. But thetriangulation result is a bit different on  surface compared with 3Ddelaunay of CGAL. So, I wonder how to find the exact algorithm and references of CGAL's 3Ddelaunay function. Thanks for any help.--View this message in context: http://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.htmlSent from the cgal-discuss mailing list archive at Nabble.com.-- You are currently subscribed to cgal-discuss.To unsubscribe or access the archives, go tohttps://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: The exact algorithm and references of CGAL's 3DDelaunay function

 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 ------------------From:  "Monique Teillaud";<[hidden email]>;Date:  Tue, Jul 26, 2016 02:43 PMTo:  "cgal-discuss"<[hidden email]>; Subject:  Re: [cgal-discuss] The exact algorithm and references of CGAL's 3DDelaunay functionHi,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, --Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique On 26 Jul 2016, at 04:56, wen <[hidden email]> wrote:Hi, I am learning geometric modelling and I want to do some research on 3DDelaunay. I just tried 3d delaunay function  provided by CGAL and wasimpressed by its high efficiency. I implemented 3D delaunay myself withIncremental  Insertion Algorithms, but the efficiency was much less thanCGAL. In addition, it needs to add eight auxiliary bounding points before pointinsertion during 3D Delaunay  triangulation. In my program, the coordinatesof the eight points was configured with the rules that the bounding  boxformed by the eight points can contain the whole point set. But thetriangulation result is a bit different on  surface compared with 3Ddelaunay of CGAL. So, I wonder how to find the exact algorithm and references of CGAL's 3Ddelaunay function. Thanks for any help.--View this message in context: http://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.htmlSent from the cgal-discuss mailing list archive at Nabble.com.-- You are currently subscribed to cgal-discuss.To unsubscribe or access the archives, go tohttps://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: The exact algorithm and references of CGAL's 3DDelaunay function

 Administrator The first line shows: #include   --Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique  On 26 Jul 2016, at 12:15, 王雯 <[hidden email]> wrote: 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 ------------------From:  "Monique Teillaud";<[hidden email]>;Date:  Tue, Jul 26, 2016 02:43 PMTo:  "cgal-discuss"<[hidden email]>; Subject:  Re: [cgal-discuss] The exact algorithm and references of CGAL's 3DDelaunay functionHi,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, --Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique On 26 Jul 2016, at 04:56, wen <[hidden email]> wrote:Hi, I am learning geometric modelling and I want to do some research on 3DDelaunay. I just tried 3d delaunay function  provided by CGAL and wasimpressed by its high efficiency. I implemented 3D delaunay myself withIncremental  Insertion Algorithms, but the efficiency was much less thanCGAL. In addition, it needs to add eight auxiliary bounding points before pointinsertion during 3D Delaunay  triangulation. In my program, the coordinatesof the eight points was configured with the rules that the bounding  boxformed by the eight points can contain the whole point set. But thetriangulation result is a bit different on  surface compared with 3Ddelaunay of CGAL. So, I wonder how to find the exact algorithm and references of CGAL's 3Ddelaunay function. Thanks for any help.--View this message in context: http://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.htmlSent from the cgal-discuss mailing list archive at Nabble.com.-- You are currently subscribed to cgal-discuss.To unsubscribe or access the archives, go tohttps://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: The exact algorithm and references of CGAL's 3DDelaunay function

 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.pdfAlso, for people who want to study the code of CGAL, the "modular view" in git is more organized than the "flat view" that is presented in the releases, so for 3D Delaunay, you can go here : https://github.com/CGAL/cgal/tree/master/Triangulation_32016-07-26 7:58 GMT-07:00 Monique Teillaud :The first line shows: #include   --Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique  On 26 Jul 2016, at 12:15, 王雯 <[hidden email]> wrote: 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 ------------------From:  "Monique Teillaud";<[hidden email]>;Date:  Tue, Jul 26, 2016 02:43 PMTo:  "cgal-discuss"<[hidden email]>; Subject:  Re: [cgal-discuss] The exact algorithm and references of CGAL's 3DDelaunay functionHi,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, --Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique On 26 Jul 2016, at 04:56, wen <[hidden email]> wrote:Hi, I am learning geometric modelling and I want to do some research on 3DDelaunay. I just tried 3d delaunay function  provided by CGAL and wasimpressed by its high efficiency. I implemented 3D delaunay myself withIncremental  Insertion Algorithms, but the efficiency was much less thanCGAL. In addition, it needs to add eight auxiliary bounding points before pointinsertion during 3D Delaunay  triangulation. In my program, the coordinatesof the eight points was configured with the rules that the bounding  boxformed by the eight points can contain the whole point set. But thetriangulation result is a bit different on  surface compared with 3Ddelaunay of CGAL. So, I wonder how to find the exact algorithm and references of CGAL's 3Ddelaunay function. Thanks for any help.--View this message in context: http://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.htmlSent from the cgal-discuss mailing list archive at Nabble.com.-- You are currently subscribed to cgal-discuss.To unsubscribe or access the archives, go tohttps://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## 回复： [cgal-discuss] The exact algorithm and references of CGAL's3DDelaunay function

 In reply to this post by teillaud Hi, MoniqueThank you for your instrutction. I will learn the code and the references, although the Delaunay hierarchy is a little difficult to understand.Best regards!------------------ 原始邮件 ------------------发件人: "Monique Teillaud";<[hidden email]>;发送时间: 2016年7月26日(星期二) 晚上10:58收件人: "cgal-discuss"<[hidden email]>; 主题: Re: [cgal-discuss] The exact algorithm and references of CGAL's3DDelaunay functionThe first line shows: #include --Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique On 26 Jul 2016, at 12:15, 王雯 <[hidden email]> wrote: 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 ------------------From:  "Monique Teillaud";<[hidden email]>;Date:  Tue, Jul 26, 2016 02:43 PMTo:  "cgal-discuss"<[hidden email]>; Subject:  Re: [cgal-discuss] The exact algorithm and references of CGAL's 3DDelaunay functionHi,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, --Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique On 26 Jul 2016, at 04:56, wen <[hidden email]> wrote:Hi, I am learning geometric modelling and I want to do some research on 3DDelaunay. I just tried 3d delaunay function  provided by CGAL and wasimpressed by its high efficiency. I implemented 3D delaunay myself withIncremental  Insertion Algorithms, but the efficiency was much less thanCGAL. In addition, it needs to add eight auxiliary bounding points before pointinsertion during 3D Delaunay  triangulation. In my program, the coordinatesof the eight points was configured with the rules that the bounding  boxformed by the eight points can contain the whole point set. But thetriangulation result is a bit different on  surface compared with 3Ddelaunay of CGAL. So, I wonder how to find the exact algorithm and references of CGAL's 3Ddelaunay function. Thanks for any help.--View this message in context: http://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.htmlSent from the cgal-discuss mailing list archive at Nabble.com.-- You are currently subscribed to cgal-discuss.To unsubscribe or access the archives, go tohttps://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: The exact algorithm and references of CGAL's 3DDelaunay function

 In reply to this post by Sylvain Pion-3 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 27.07.2016, 19:32, "Sylvain Pion" <[hidden email]>: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 Also, for people who want to study the code of CGAL, the "modular view" in git is more organized than the "flat view" that is presented in the releases, so for 3D Delaunay, you can go here : https://github.com/CGAL/cgal/tree/master/Triangulation_3  2016-07-26 7:58 GMT-07:00 Monique Teillaud :The first line shows: #include   --Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique  On 26 Jul 2016, at 12:15, 王雯 <[hidden email]> wrote:  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 ------------------From:  "Monique Teillaud";<[hidden email]>;Date:  Tue, Jul 26, 2016 02:43 PMTo:  "cgal-discuss"<[hidden email]>; Subject:  Re: [cgal-discuss] 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,--Monique Teillaud https://members.loria.fr/Monique.Teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique On 26 Jul 2016, at 04:56, wen <[hidden email]> wrote: Hi,I am learning geometric modelling and I want to do some research on 3DDelaunay. I just tried 3d delaunay function  provided by CGAL and wasimpressed by its high efficiency. I implemented 3D delaunay myself withIncremental  Insertion Algorithms, but the efficiency was much less thanCGAL.In addition, it needs to add eight auxiliary bounding points before pointinsertion during 3D Delaunay  triangulation. In my program, the coordinatesof the eight points was configured with the rules that the bounding  boxformed by the eight points can contain the whole point set. But thetriangulation result is a bit different on  surface compared with 3Ddelaunay of CGAL.So, I wonder how to find the exact algorithm and references of CGAL's 3Ddelaunay function.Thanks for any help.--View this message in context: http://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.htmlSent from the cgal-discuss mailing list archive at Nabble.com.--You are currently subscribed to cgal-discuss.To unsubscribe or access the archives, go tohttps://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: The exact algorithm and references of CGAL's 3DDelaunay function

 On 15 Sep 2016, at 14:42, Илья Палачев <[hidden email]> wrote: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/inria-00166711Olivier
Open this post in threaded view
|

## Re: The exact algorithm and references of CGAL's 3DDelaunay function

 Hi Olivier, Thanks for quick answer. My comments below. 15.09.2016, 18:31, "Olivier Devillers" <[hidden email]>: On 15 Sep 2016, at 14:42, Илья Палачев <[hidden email]> wrote: 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 rhttps://hal.inria.fr/inria-0016671 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/cs468-02-winter/Papers/linearDT.pdf ] hold and, hence, the first hypothesis holds, too. Is it true, how do you think? Best regards,Ilya Palachev
Open this post in threaded view
|

## Re: The exact algorithm and references of CGAL's 3DDelaunay function

 On 15 Sep 2016, at 18:29, Илья Палачев <[hidden email]> wrote:Hi Olivier, Thanks for quick answer. My comments below. 15.09.2016, 18:31, "Olivier Devillers" <[hidden email]>: On 15 Sep 2016, at 14:42, Илья Палачев <[hidden email]> wrote: 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 rhttps://hal.inria.fr/inria-0016671 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/cs468-02-winter/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 polyhedronand 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