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

classic Classic list List threaded Threaded
10 messages Options
wen
Reply | Threaded
Open this post in threaded view
|

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

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

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

teillaud
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 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://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



wen
Reply | Threaded
Open this post in threaded view
|

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

wen
 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 PM
To:  "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 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://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Reply | Threaded
Open this post in threaded view
|

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

teillaud
Administrator
The first line shows: #include <CGAL/Delaunay_triangulation_3.h> 

--
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 PM
To:  "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 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://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss




Reply | Threaded
Open this post in threaded view
|

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

Sylvain Pion-3
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

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 <[hidden email]>:
The first line shows: #include <CGAL/Delaunay_triangulation_3.h> 

--
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 PM
To:  "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 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://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss





wen
Reply | Threaded
Open this post in threaded view
|

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

wen
In reply to this post by teillaud
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!


------------------ 原始邮件 ------------------
发件人: "Monique Teillaud";<[hidden email]>;
发送时间: 2016年7月26日(星期二) 晚上10:58
收件人: "cgal-discuss"<[hidden email]>;
主题: Re: [cgal-discuss] The exact algorithm and references of CGAL's3DDelaunay function

The first line shows: #include <CGAL/Delaunay_triangulation_3.h>

--
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 PM
To:  "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 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://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss




Reply | Threaded
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 <[hidden email]>:
The first line shows: #include <CGAL/Delaunay_triangulation_3.h> 
 
--
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 PM
To:  "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 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://cgal-discuss.949826.n4.nabble.com/The-exact-algorithm-and-references-of-CGAL-s-3D-Delaunay-function-tp4662096.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

 
 
Reply | Threaded
Open this post in threaded view
|

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

Olivier Devillers-2

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-00166711

Olivier

Reply | Threaded
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 r
https://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
Reply | Threaded
Open this post in threaded view
|

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

Olivier Devillers-2

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 r
https://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 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