Geogram Version 1.9.2
A programming library of geometric algorithms
Loading...
Searching...
No Matches
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
49#include <stack>
50
52
53namespace 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
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
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
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
450 bool detailed_benchmark_mode_;
451
456 vector<Numeric::uint32> vertex_instances_;
457
458 bool update_periodic_v_to_cell_;
459 vector<index_t> periodic_v_to_cell_rowptr_;
460 vector<index_t> periodic_v_to_cell_data_;
461
465 bool has_empty_cells_;
466
471 index_t nb_reallocations_;
472
476 bool convex_cell_exact_predicates_;
477
478 struct Stats {
479
480 Stats();
481
482 void reset();
483
484 std::string to_string() {
485 return raw_ ? to_string_raw() : to_string_pretty();
486 }
487
488 std::string to_string_raw() const;
489 std::string to_string_pretty() const;
490
495 bool raw_;
496
497 double total_t_;
498
499 double phase_0_t_;
500
501 double phase_I_t_;
502 double phase_I_classify_t_;
503 index_t phase_I_nb_inside_;
504 index_t phase_I_nb_cross_;
505 index_t phase_I_nb_outside_;
506 double phase_I_insert_t_;
507 index_t phase_I_insert_nb_;
508
509 double phase_II_t_;
510 double phase_II_classify_t_;
511 double phase_II_insert_t_;
512 index_t phase_II_insert_nb_;
513 } stats_;
514
515 friend class LaguerreDiagramOmegaSimple3d;
516 };
517
518
519}
520
521#endif
#define geo_debug_assert(x)
Verifies that a condition is met.
Definition assert.h:196
Common include file, providing basic definitions. Should be included before anything else by all head...
An array of cell status codes associates to each tetrahedron in a Delaunay tetrahedralization.
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.
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.
PeriodicDelaunay3dThread * thread(index_t t)
Gets a thread by index.
Utilities for managing 3D periodic space.
Definition periodic.h:57
Vector with aligned memory allocation.
Definition memory.h:660
index_t size() const
Gets the number of elements.
Definition memory.h:706
Computes the intersection between a set of halfplanes using Bowyer-Watson algorithm.
Class to compute the intersection of a set of half-spaces in 3D.
Abstract interface for Delaunay.
Synchronization primitives for parallel Delaunay.
Geometric functions in 2d and 3d.
Global Vorpaline namespace.
Definition algorithm.h:65
std::vector< Thread_var > ThreadGroup
Collection of Threads.
Definition process.h:155
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.