Choosing a representative in a 3D Periodic Delaunay Tessellation

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

Choosing a representative in a 3D Periodic Delaunay Tessellation

Michael Klatt
Dear all,

To triangulate a point set in the three-dimensional flat torus,
CGAL::Periodic_3_Delaunay_triangulation_3 offers a very good solution to my
needs, switching between Delaunay and Voronoi tessellations.

For each vertex, I want to first iterate over all incident edges and then
(for each edge) circulate over all cells incident to the given edge.
My current code relies on the functions
     OutputIterator incident_edges (Vertex_handle v, OutputIterator edges)
const
and
     Cell_circulator incident_cells (Edge e) const
Thus I obtain a Cell_handle.

How can I choose the representative (tetrahedron in Euclidean space) that
has the initial vertex as one of its four vertices?

For example, if the vertex for which I pick an incident edge has coordinates
(0.1,0.1,0.1), I would like to obtain a tetrahedron whose other points have
negative coordinates, rather than the tetrahedron that is at the opposite
end of the 1- or 27-sheeted covering space.
The latter is the result of my attempt using
     T.tetrahedron(T.periodic_tetrahedron(cit));
(due to my CGAL version 4.7).

Of course, I can manually translate the tetrahedron, but is there a built-in
solution?

Thank you very much!
Best regards,

Michael




--
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: Choosing a representative in a 3D Periodic Delaunay Tessellation

MaelRL
Hello,

There is not exactly any built-in functions for what you describe
(getting consistent offsets around an edge), but there are a few
functions which might help you reach your goal through another path.

You could use the fact that the offset of each vertex in a cell is
accessible via cell_handle->offset(vertex_index). It is then easy to
combine offsets to call other functions of P3DT3 as a lot of functions
of P3DT3 that have a signature like "function(args)" have overloads
"function(args, offsets)", and you might then avoid manually translating
your cells, depending on what you want to do afterwards.

If you are only interested in constructing the dual (geometrically), the
P3DT3::dual() functions give most of what you need: taking a cell, an
edge, or a vertex handle, they return a consistent polyhedron with
points in R^3 (thus possibly outside of the periodic domain). If you
look into the code of these functions, you can tweak the offset value
(using P3DT3::combine_offset()) to change the 3D output to be near the
position of your chosen vertex.

Best,
Mael

On 02/02/2019 01:50, Michael Klatt wrote:

> Dear all,
>
> To triangulate a point set in the three-dimensional flat torus,
> CGAL::Periodic_3_Delaunay_triangulation_3 offers a very good solution to my
> needs, switching between Delaunay and Voronoi tessellations.
>
> For each vertex, I want to first iterate over all incident edges and then
> (for each edge) circulate over all cells incident to the given edge.
> My current code relies on the functions
>       OutputIterator incident_edges (Vertex_handle v, OutputIterator edges)
> const
> and
>       Cell_circulator incident_cells (Edge e) const
> Thus I obtain a Cell_handle.
>
> How can I choose the representative (tetrahedron in Euclidean space) that
> has the initial vertex as one of its four vertices?
>
> For example, if the vertex for which I pick an incident edge has coordinates
> (0.1,0.1,0.1), I would like to obtain a tetrahedron whose other points have
> negative coordinates, rather than the tetrahedron that is at the opposite
> end of the 1- or 27-sheeted covering space.
> The latter is the result of my attempt using
>       T.tetrahedron(T.periodic_tetrahedron(cit));
> (due to my CGAL version 4.7).
>
> Of course, I can manually translate the tetrahedron, but is there a built-in
> solution?
>
> Thank you very much!
> Best regards,
>
> Michael
>
>
>
>
> --
> 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: Choosing a representative in a 3D Periodic Delaunay Tessellation

Michael Klatt
Dear Mael,

Thank you very much! Since I need the specific iteration as described above,
my code now uses the offset to move points.

To identify the correct offset, I have to determine which vertex of the cell
corresponds to my initial vertex (i.e. periodic point).
Is there an alternative to comparing each vertex using the comparison "=="?

If not, I have to make sure that the triangulation does not change at all
(since I assume that for my inexact constructions kernel, the latter is
comparing doubles).

Best regards,

Michael


 



--
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: Choosing a representative in a 3D Periodic Delaunay Tessellation

Michael Klatt
Dear Mael, Dear all,

There are two further important questions for my simulation.

First, how can I set information while inserting a range of points like in
the non-periodic case?
The example there is exactly what I need for the periodic triangulation:
https://doc.cgal.org/4.7/Triangulation_3/index.html#Triangulation_3SettingInformationWhileInserting

Second, (how) can I simultaneously add information to the cells?

Thank you very much!

Best regards,

Michael




--
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: Choosing a representative in a 3D Periodic Delaunay Tessellation

MaelRL
On 05/02/2019 00:08, Michael Klatt wrote:
Dear Mael,

Thank you very much! Since I need the specific iteration as described above,
my code now uses the offset to move points.

To identify the correct offset, I have to determine which vertex of the cell
corresponds to my initial vertex (i.e. periodic point).
Is there an alternative to comparing each vertex using the comparison "=="?

If not, I have to make sure that the triangulation does not change at all
(since I assume that for my inexact constructions kernel, the latter is
comparing doubles).

Just to make sure everything is clear for you: if you are in 27-sheet mode, everything is literally duplicated thrice, along each of the (Ox), (Oy), (Oz) directions. Thus, for the same (periodically speaking) point, there are 27 different vertices. Similarly, cells are also duplicated. Furthermore, if you compare two vertex handles with '==', it will not resolve to comparing their geometries or the geometry of their canonical entity (the one living in the "main" cube), it is only comparing two handles (i.e. pointers).

Now, to find in your cell which vertex is the one corresponding to your chosen vertex, you could proceed as follow: let vh_0 be the vertex you have chosen. We can assume that you are in 27-sheet and that vh_0 is actually a vertex that does not live in the canonical cube, i.e. we can write vh_0->point() = some_canonical_vh_living_in_the_canonical_cube->point() + some_non_null_offset. Finding this canonical vertex handle can be done using he function "origin_vertex(Vertex_handle in_vh)": for the given vertex in_vh, this function will return a pair with the vertex handle canonical_vh which corresponds to the canonical representative of the vertex in_vh and the offset to reach back in_vh from canonical_vh.*

Then, knowing the canonical vertex handle of your chosen vertex, you can find which vertex corresponds to vh_0 in your cell by again calling "original_vertex(...)" for the vertices of your cell, and taking the one that has the same canonical vertex handle. Note that you can also make use of the offset values returned by the calls to "original_vertex()", since by comparing their values and combining it with the offset of the vertex in the cell (using the function combine_offsets), you will be able to deduct which translation you have to apply to your cell.

Something that you might also find useful are the functions "neighbor_offset()" and related, which enable to compute the offset between neighboring cells.

(Answer to the other question below)

On 06/02/2019 01:40, Michael Klatt wrote:
Dear Mael, Dear all,

There are two further important questions for my simulation.

First, how can I set information while inserting a range of points like in
the non-periodic case?
The example there is exactly what I need for the periodic triangulation:
https://doc.cgal.org/4.7/Triangulation_3/index.html#Triangulation_3SettingInformationWhileInserting

Second, (how) can I simultaneously add information to the cells?

Short answer: there is no insertion of a range with info in Periodic_3_triangulation_3, nor a way to set up all cells' info when inserting a range of points (even in a non-periodic setting, AFAIK). Nevertheless, you can probably write it without too much trouble.

Long answer:

In the package Triangulation_3, there are two classes Triangulation_vertex_base_with_info_3 and Triangulation_cell_base_with_info_3, which add a field "info()" to your vertices and cells, enabling to associate whatever info you want, as you have seen for Triangulation_3 in the example you link. This is also what you are supposed to use in a periodic setting, as shown in the following example for vertices: https://github.com/CGAL/cgal/blob/master/Periodic_3_triangulation_3/examples/Periodic_3_triangulation_3/colored_vertices.cpp, and it is the same for cells (note that insert() returns a vertex handle to the new vertex, and you can loop over its incident cells via incident_cells(vertex_handle)).

However, a limitation is that the info() field is not periodic: as said in the first answer above, two different vertices being (geometrically) periodically equivalent are still completely different entities in the data structure, and thus do not share their info() fields. If you simply do:

Vertex_handle new_vh = p3dt3.insert(point);
new_vh->info() = blue;

while being in 27-sheet, you will only be setting the color of a single vertex (and not of its 26 "periodic brothers"). Nonetheless, you can access the periodic copies of your vertex (and thus of the copied cells, using again incident_cells(vertex_handle)) via the function "periodic_copies(Vertex_handle)", which returns a vector of vertex handles with the "periodic brothers".

Whether you would want the info to be duplicated is not clear and is one of the reasons why this insert() function doesn't exist, but you can easily write your own insert(range_with_info) function by copying the code from insert(range) and plugging in info when you need it, using the functions described above.

Best,
Mael









Reply | Threaded
Open this post in threaded view
|

Re: Choosing a representative in a 3D Periodic Delaunay Tessellation

Michael Klatt
Dear Mael,

Thanks! One of my algorithms is implemented and running. Unfortunately, for
the next one I still have some questions.
In particular, I am not sure whether I have understood the uniqueness or
non-uniqueness of the handles correctly.

What is a unique identifier of each cell (where we do not distinguish
periodic copies)?
How can I iterate over unique cells (in the sense of the
Iterator_type=UNIQUE) so that I can analyze some (arbitrary) representative
tetrahedron and assign information to the unique identifier of the cell?

Next, I would like to iterate over unique facets and get the two adjacent
cells, that is, their unique identifier as well as the relative offset of
for example the center of mass of the representatives that form that facet?

It will be a great help to me, if there is a convenient solution to these
problems.
Thank you very much!

Best regards,

Michael




--
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: Choosing a representative in a 3D Periodic Delaunay Tessellation

MaelRL

Hello,

On 09/02/2019 04:52, Michael Klatt wrote:
Dear Mael,

Thanks! One of my algorithms is implemented and running. Unfortunately, for
the next one I still have some questions.
In particular, I am not sure whether I have understood the uniqueness or
non-uniqueness of the handles correctly.
Handles can be thought of as pointers, so each cell has its own address and thus its own unique handle, even if the cell is just a periodic copy of a canonical cell.
What is a unique identifier of each cell (where we do not distinguish
periodic copies)?

There is no such identifier that would be the same for each cell of the triangulation that correspond to the same cell periodically. However, you could create a "signature" function for the cell, which would extract (and order) from its vertices [v0, ..., v3] the corresponding canonical vertices [canonical_v0, ..., canonical_v3], using functions described in the previous emails. This would be unique per cell, regardless of whichever periodic copy you're looking at.

Another way: if you look into the code of the class Periodic_3_triangulation_3, you will find two maps that are members of the class: "virtual_vertices" and "virtual_vertices_reverse", these enable to find the handle of the canonical vertex from any vertex (and reversely). You could build the same thing for cells, noting that the canonical cell is defined as the cell whose vertices have smallest positive offset, e.g.:

c = [vh_0, vh_1, vh_2, vh_3] = [{canon_vh_0, offset(1,1,1)}, {canon_vh_1, offset(1,0,0)}, {canon_vh_2, offset(1,0,1)}, {canon_vh_3, offset(2,1,1)}]

is not canonical, its canonical representative is:

c' = [vh_0', vh_1', vh_2', vh_3'] = [{canon_vh_0, offset(0,1,1)}, {canon_vh_1, offset(0,0,0)}, {canon_vh_2, offset(0,0,1)}, {canon_vh_3, offset(1,1,1)}]

You can check the function called 'is_canonical()' in the class 'Periodic_3_triangulation_tetrahedron_iterator_3'.

How can I iterate over unique cells (in the sense of the
Iterator_type=UNIQUE) so that I can analyze some (arbitrary) representative
tetrahedron and assign information to the unique identifier of the cell?
You can loop over all the cells, and check if it is canonical, using the definition above. Or just build the correspondence map(s) between canonical and non-canonical cells, which seems that it would be all around useful for you.
Next, I would like to iterate over unique facets and get the two adjacent
cells, that is, their unique identifier as well as the relative offset of
for example the center of mass of the representatives that form that facet?

Important note: a facet 'f' is just a pair of a cell handle and an index, which is the index of the fourth vertex opposite of the facet in the cell handle. Therefore, do note that if c1, and c2 are adjacent, there are two different facets (one seen from c1, one seen from c2).

This being said, you can just loop over all your facets (using facets_begin(), facets_end()), and use your unique cell map (or is_canonical(ch)) to check if the cell f.first is unique. If you don't want to see the facet from each side, you can filter one of the two facets by ignoring a facet 'f' if the handle of c1 == f.first is larger than that of c2 == f.first->neighbor(f.second)  (using notations above for c1 and c2).

I am not sure I understand what you mean with 'relative offset of the center of mass': offset with respect to what? If it is the original domain, then you can use the function "construct_periodic_point()" which gives you the canonical point and the offset. If you mean with respect to the facet (i.e. the cell) then use the same function and combine offsets.

Best,
Mael


It will be a great help to me, if there is a convenient solution to these
problems.
Thank you very much!

Best regards,

Michael




--
Sent from: http://cgal-discuss.949826.n4.nabble.com/