Creating Delaunay 3d triangulation with a circumradius bound

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

Creating Delaunay 3d triangulation with a circumradius bound

Dahn
I'd like to create a 3d Delaunay triangulation with a pre-specified
circumradius bound. At first I thought a dense enough regular grid is a good
solution, but due to either the perturbation of the grid points or floating
point arithmetic (which is it?) this creates very large tetrahedra.

Say I want to limit the circumradius to 0.1. With 6000 points, most
tetrahedra indeed have a circumradius below 0.1. However, a few will have
circumradii as large as 3. Increasing the number of points won't help, as it
will only increase the size and number of the tetrahedra with large
circumradii.

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>
#include <CGAL/point_generators_3.h>
#include <vector>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3 Point;
typedef CGAL::Creator_uniform_3<double, Point> Creator;
typedef std::vector<Point> Vector;
typedef CGAL::Delaunay_triangulation_3<K> Dt;
typedef Dt::Tetrahedron Tetrahedron;

double circumradius( const Tetrahedron& t) {
        return
CGAL::sqrt(CGAL::squared_distance(CGAL::circumcenter(t),t.vertex(0)));
}


int main(){
        int npts = 6000;
        //// Create a vector of random points
        Vector points;
        CGAL::points_on_cube_grid_3( 1, npts, std::back_inserter(points), Creator()
);

        //// Create a Delaunay triangulation from those points
        Dt T;
        T.insert(points.begin(),points.end());

    /// Write out tetrahedron whose circumradii are too large
        for (Dt::Finite_cells_iterator cell = T.finite_cells_begin(); cell !=
T.finite_cells_end(); ++cell) {
        double circum = circumradius(T.tetrahedron(cell));
        if (circum > 0.1) {std::cout << circum << std::endl;}

    }
}



Thank you for any help!



--
Sent from: http://cgal-discuss.949826.n4.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: Creating Delaunay 3d triangulation with a circumradius bound

Sebastien Loriot (GeometryFactory)
Can't you use the Mesh_3 package and set a criteria on the size of the
tetrahedron? The triangulation will not be a regular triangulation
(and not a Delaunay one).

https://doc.cgal.org/latest/Mesh_3

Sebastien.

On 07/16/2018 06:36 PM, Dahn wrote:

> I'd like to create a 3d Delaunay triangulation with a pre-specified
> circumradius bound. At first I thought a dense enough regular grid is a good
> solution, but due to either the perturbation of the grid points or floating
> point arithmetic (which is it?) this creates very large tetrahedra.
>
> Say I want to limit the circumradius to 0.1. With 6000 points, most
> tetrahedra indeed have a circumradius below 0.1. However, a few will have
> circumradii as large as 3. Increasing the number of points won't help, as it
> will only increase the size and number of the tetrahedra with large
> circumradii.
>
> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
> #include <CGAL/Delaunay_triangulation_3.h>
> #include <CGAL/point_generators_3.h>
> #include <vector>
> #include <iostream>
>
> typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
> typedef K::Point_3 Point;
> typedef CGAL::Creator_uniform_3<double, Point> Creator;
> typedef std::vector<Point> Vector;
> typedef CGAL::Delaunay_triangulation_3<K> Dt;
> typedef Dt::Tetrahedron Tetrahedron;
>
> double circumradius( const Tetrahedron& t) {
> return
> CGAL::sqrt(CGAL::squared_distance(CGAL::circumcenter(t),t.vertex(0)));
> }
>
>
> int main(){
> int npts = 6000;
> //// Create a vector of random points
> Vector points;
> CGAL::points_on_cube_grid_3( 1, npts, std::back_inserter(points), Creator()
> );
>
> //// Create a Delaunay triangulation from those points
> Dt T;
> T.insert(points.begin(),points.end());
>
>      /// Write out tetrahedron whose circumradii are too large
> for (Dt::Finite_cells_iterator cell = T.finite_cells_begin(); cell !=
> T.finite_cells_end(); ++cell) {
>          double circum = circumradius(T.tetrahedron(cell));
>          if (circum > 0.1) {std::cout << circum << std::endl;}
>
>      }
> }
>
>
>
> Thank you for any help!
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.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: Creating Delaunay 3d triangulation with a circumradius bound

Dahn
Hi Sebastien,

thank you for the suggestion. Sadly I cannot, as the triangulation is an
initial configuration for an  MCMC
<https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo>   algorithm which
attempts to converge to a regular triangulation with certain properties (but
has to start with certain properties for it to work, too).
However, I have realized that a simpler solution might be to create a point
pattern such that the resulting tetrahedra are regular (as in made of
equilateral triangles), a 3d version of the  equilateral triangle tiling
<http://gwydir.demon.co.uk/jo/tess/bigtri.htm>  .
I am not able to test it now, but I will report back once I do. In the
meantime, other suggestions are definitely welcome.



--
Sent from: http://cgal-discuss.949826.n4.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: Creating Delaunay 3d triangulation with a circumradius bound

Sebastien Loriot (GeometryFactory)
Another thing to try it to use the Lloyd algorithm, it should make you
tetrahedron almost identical as the points will be equally spaced.

Sebastien.

On 07/27/2018 08:49 AM, Dahn wrote:

> Hi Sebastien,
>
> thank you for the suggestion. Sadly I cannot, as the triangulation is an
> initial configuration for an  MCMC
> <https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo>   algorithm which
> attempts to converge to a regular triangulation with certain properties (but
> has to start with certain properties for it to work, too).
> However, I have realized that a simpler solution might be to create a point
> pattern such that the resulting tetrahedra are regular (as in made of
> equilateral triangles), a 3d version of the  equilateral triangle tiling
> <http://gwydir.demon.co.uk/jo/tess/bigtri.htm>  .
> I am not able to test it now, but I will report back once I do. In the
> meantime, other suggestions are definitely welcome.
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.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