Geogram  Version 1.9.1
A programming library of geometric algorithms
periodic_delaunay_3d.h
1 /*
2  * Copyright (c) 2000-2022 Inria
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright notice,
9  * this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  * * Neither the name of the ALICE Project-Team nor the names of its
14  * contributors may be used to endorse or promote products derived from this
15  * software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27  * POSSIBILITY OF SUCH DAMAGE.
28  *
29  * Contact: Bruno Levy
30  *
31  * https://www.inria.fr/fr/bruno-levy
32  *
33  * Inria,
34  * Domaine de Voluceau,
35  * 78150 Le Chesnay - Rocquencourt
36  * FRANCE
37  *
38  */
39 
40 #ifndef PERIODIC_DELAUNAY_TRIANGULATION_3D
41 #define PERIODIC_DELAUNAY_TRIANGULATION_3D
42 
43 #include <geogram/basic/common.h>
47 #include <geogram/basic/process.h>
48 #include <geogram/basic/geometry.h>
49 #include <stack>
50 
52 
53 namespace GEO {
54 
55  class PeriodicDelaunay3dThread;
56 
57 
67  class GEOGRAM_API PeriodicDelaunay3d : public Delaunay, public Periodic {
68  public:
69 
78  std::stack<index_t> S;
79  vector<index_t> incident_tets_set;
80 
85  incident_tets_set.resize(0);
86  }
87 
93  incident_tets_set.push_back(t);
94  }
95 
103  bool has_incident_tet(index_t t) const {
104  for(index_t i=0; i<incident_tets_set.size(); ++i) {
105  if(incident_tets_set[i] == t) {
106  return true;
107  }
108  }
109  return false;
110  }
111 
112  vector<index_t>::const_iterator begin() const {
113  return incident_tets_set.begin();
114  }
115 
116  vector<index_t>::const_iterator end() const {
117  return incident_tets_set.end();
118  }
119  };
120 
126  PeriodicDelaunay3d(bool periodic, double period=1.0);
127 
132  PeriodicDelaunay3d(const vec3& period);
133 
139  index_t nb_vertices, const double* vertices
140  ) override;
141 
150  void set_weights(const double* weights);
151 
155  void compute();
156 
166  convex_cell_exact_predicates_ = x;
167  }
168 
177  vec3 vertex(index_t v) const {
178  if(!periodic_) {
179  geo_debug_assert(v < nb_vertices());
180  return vec3(vertices_ + 3*v);
181  }
182  index_t instance = v/nb_vertices_non_periodic_;
183  v = v%nb_vertices_non_periodic_;
184  vec3 result(vertices_ + 3*v);
185  result.x += double(translation[instance][0]) * period_.x;
186  result.y += double(translation[instance][1]) * period_.y;
187  result.z += double(translation[instance][2]) * period_.z;
188  return result;
189  }
190 
197  double weight(index_t v) const {
198  if(weights_ == nullptr) {
199  return 0.0;
200  }
201  return periodic_ ? weights_[periodic_vertex_real(v)] : weights_[v] ;
202  }
203 
207  index_t nearest_vertex(const double* p) const override;
208 
212  void set_BRIO_levels(const vector<index_t>& levels) override;
213 
223 
235  GEO::index_t i,
236  ConvexCell& C,
238  ) const;
239 
249  GEO::index_t i,
250  ConvexCell& C
251  ) const {
253  copy_Laguerre_cell_from_Delaunay(i,C,W);
254  }
255 
264  bool has_empty_cells() const {
265  return has_empty_cells_;
266  }
267 
276  void save_cells(const std::string& basename, bool clipped);
277 
278  protected:
279 
296  GEO::index_t i,
297  const GEO::vec3& Pi,
298  double wi,
299  double Pi_len2,
300  GEO::index_t t,
301  ConvexCell& C,
303  ) const;
304 
305 
312  index_t compress(bool shrink=true);
313 
320  void update_v_to_cell() override;
321 
325  void update_cicl() override;
326 
332 
333 
342 
355 
364 
372  void insert_vertices(const char* phase, index_t b, index_t e);
373 
385  const char* phase, const vector<index_t>& levels
386  );
387 
391  void check_volume();
392 
398  PeriodicDelaunay3dThread* thread(index_t t) {
399  geo_debug_assert(t < threads_.size());
400  return reinterpret_cast<PeriodicDelaunay3dThread*>(
401  threads_[t].get()
402  );
403  }
404 
409  index_t nb_threads() const {
410  return index_t(threads_.size());
411  }
412 
413  void check_max_t();
414 
415  private:
416  friend class PeriodicDelaunay3dThread;
417 
418  bool periodic_;
419  vec3 period_;
420 
421  const double* weights_;
422  vector<signed_index_t> cell_to_v_store_;
423  vector<signed_index_t> cell_to_cell_store_;
424  vector<index_t> cell_next_;
425 
426  CellStatusArray cell_status_;
427 
428  ThreadGroup threads_;
429  vector<index_t> reorder_;
430  vector<index_t> levels_;
431 
435  bool debug_mode_;
436 
440  bool verbose_debug_mode_;
441 
445  bool benchmark_mode_;
446 
447 
452  vector<Numeric::uint32> vertex_instances_;
453 
454  bool update_periodic_v_to_cell_;
455  vector<index_t> periodic_v_to_cell_rowptr_;
456  vector<index_t> periodic_v_to_cell_data_;
457 
461  bool has_empty_cells_;
462 
467  index_t nb_reallocations_;
468 
472  bool convex_cell_exact_predicates_;
473  };
474 
475 
476 }
477 
478 #endif
#define geo_debug_assert(x)
Verifies that a condition is met.
Definition: assert.h:196
An array of cell status codes associates to each tetrahedron in a Delaunay tetrahedralization.
Definition: delaunay_sync.h:68
Abstract interface for Delaunay triangulation in Nd.
Definition: delaunay.h:71
Multithreaded implementation of Delaunay in 3d with optional periodic boundary conditions.
PeriodicDelaunay3d(const vec3 &period)
Constructs a new PeriodicDelaunay3d.
PeriodicDelaunay3d(bool periodic, double period=1.0)
Constructs a new PeriodicDelaunay3d.
void check_volume()
Checks the volume of Laguerre cells.
void compute()
Computes the Delaunay triangulation.
void use_exact_predicates_for_convex_cell(bool x)
Use exact predicates in convex cell computations.
void handle_periodic_boundaries()
Duplicates the points with Voronoi cells that cross the boundary.
void save_cells(const std::string &basename, bool clipped)
Saves the cells in an Alias-Wavefront file.
void set_BRIO_levels(const vector< index_t > &levels) override
Specifies the bounds of each level to be used when hierarchic ordering is specified from outside.
index_t compress(bool shrink=true)
Removes unused tetrahedra.
void insert_vertices(const char *phase, index_t b, index_t e)
Inserts vertices from reorder_[b] to reorder_[e-1] using multithreaded Delaunay. Called by insert_ver...
void handle_periodic_boundaries_phase_II()
Phase II of periodic boundaries handling.
double weight(index_t v) const
Gets a weight by index.
PeriodicDelaunay3dThread * thread(index_t t)
Gets a thread by index.
bool Laguerre_vertex_is_in_conflict_with_plane(index_t t, vec4 P) const
Tests the position of a Laguerre vertex w.r.t. a plane.
void update_v_to_cell() override
Stores for each vertex v a cell incident to v.
void update_cicl() override
Updates the circular incident cell lists.
void get_incident_tets(index_t v, IncidentTetrahedra &W) const
computes the set of tetrahedra that are incident to a vertex.
void copy_Laguerre_cell_from_Delaunay(GEO::index_t i, ConvexCell &C, IncidentTetrahedra &W) const
Copies a Laguerre cell from the triangulation.
void insert_vertices_with_BRIO(const char *phase, const vector< index_t > &levels)
Inserts vertices as indicated by a reordering vector and a vector of BRIO levels, as obtained using c...
index_t nb_threads() const
Gets the number of threads.
void handle_periodic_boundaries_phase_I()
Phase I of periodic boundaries handling.
index_t nearest_vertex(const double *p) const override
Computes the nearest vertex from a query point.
void copy_Laguerre_cell_from_Delaunay(GEO::index_t i, ConvexCell &C) const
Copies a Laguerre cell from the triangulation.
vec3 vertex(index_t v) const
Gets a vertex by index.
bool has_empty_cells() const
Tests whether the Laguerre diagram has empty cells.
GEO::index_t copy_Laguerre_cell_facet_from_Delaunay(GEO::index_t i, const GEO::vec3 &Pi, double wi, double Pi_len2, GEO::index_t t, ConvexCell &C, IncidentTetrahedra &W) const
Copies a Laguerre cell facet from the triangulation.
void set_weights(const double *weights)
Sets the weights.
void set_vertices(index_t nb_vertices, const double *vertices) override
Sets the vertices of this Delaunay, and recomputes the cells.
Utilities for managing 3D periodic space.
Definition: periodic.h:57
index_t size() const
Gets the number of elements.
Definition: memory.h:674
Computes the intersection between a set of halfplanes using Bowyer-Watson algorithm.
Definition: convex_cell.h:419
Class to compute the intersection of a set of half-spaces in 3D.
Abstract interface for Delaunay.
Synchronization primitives for parallel Delaunay.
Common include file, providing basic definitions. Should be included before anything else by all head...
Geometric functions in 2d and 3d.
Global Vorpaline namespace.
Definition: basic.h:55
std::vector< Thread_var > ThreadGroup
Collection of Threads.
Definition: process.h:155
vecng< 3, Numeric::float64 > vec3
Represents points and vectors in 3d.
Definition: geometry.h:65
geo_index_t index_t
The type for storing and manipulating indices.
Definition: numeric.h:329
Manipulation of indices for 3D periodic space.
Function and classes for process manipulation.
Gathers some structures used by some algorithms, makes multithreading more efficient by avoiding dyna...
void add_incident_tet(index_t t)
Inserts a tet into the set of incident tets.
void clear_incident_tets()
Clears the set of incident tets.
bool has_incident_tet(index_t t) const
Tests whether a tet belongs to the set of incident tets.