40#ifndef GEOGRAM_VORONOI_GENERIC_RVD_CELL
41#define GEOGRAM_VORONOI_GENERIC_RVD_CELL
76 static const index_t NO_TRIANGLE = index_t(-1);
77 static const index_t NO_VERTEX = index_t(-1);
78 static const index_t END_OF_LIST = index_t(-1);
111 index_t v0, index_t v1, index_t v2,
112 index_t f0, index_t f1, index_t f2
115 status_(TRI_IS_FREE),
130 status_(TRI_IS_FREE),
174 first_free_(END_OF_LIST),
175 v_to_t_dirty_(false),
177 symbolic_is_surface_(false),
195 return intersections_.dimension();
202 first_free_ = END_OF_LIST;
203 triangles_.resize(0);
205 v_to_t_dirty_ =
false;
206 intersections_.clear();
218 symbolic_is_surface_ = x;
232 const Mesh* mesh, index_t t,
bool symbolic,
245 Mesh* mesh,
bool symbolic
281 template <index_t DIM>
284 index_t i, index_t j,
285 bool exact,
bool symbolic
287 index_t new_v = create_vertex();
288 set_vertex_id(index_t(new_v), signed_index_t(j)+1);
289 index_t conflict_begin, conflict_end;
295 get_conflict_list<DIM>(
296 mesh, delaunay, i, j, exact, conflict_begin, conflict_end
300 if(conflict_begin == END_OF_LIST) {
301 return signed_index_t(new_v);
306 index_t first_conflict_t;
307 index_t first_conflict_e;
308 bool found_h = find_triangle_on_border(
309 conflict_begin, conflict_end,
310 first_conflict_t, first_conflict_e
323 triangulate_hole<DIM>(
324 delaunay, i, j, symbolic,
325 first_conflict_t, first_conflict_e,
330 merge_into_free_list(conflict_begin, conflict_end);
331 return signed_index_t(new_v);
340 return triangles_.size();
348 for(index_t t = 0; t < max_t(); t++) {
349 if(triangle_is_used(t)) {
360 return vertices_.size();
369 return triangles_[t].status_ == TRI_IS_FREE;
381 return !triangle_is_free(t);
392 return triangles_[t].status_ == TRI_IS_USED;
404 return triangles_[t].status_ == TRI_IS_CONFLICT;
417 return triangles_[t].v[iv];
429 return triangles_[t].t[e];
443 triangles_[t].v[iv] = v;
453 index_t t, index_t e, index_t t2
459 triangles_[t].t[e] = t2;
477 index_t result = index_t(
478 (triangles_[t].v[1] == v) | ((triangles_[t].v[2] == v) * 2)
493 index_t t1, index_t t2
503 index_t result = index_t(
504 (triangles_[t1].t[1] == t2) | ((triangles_[t1].t[2] == t2) * 2)
525 return vertices_[v].t;
537 vertices_[v].t = signed_index_t(t);
551 return triangles_[t].dual_;
565 return triangles_[t].dual_;
598 return triangles_[t].id_;
608 triangles_[t].id_ = id;
619 return vertices_[v].id_;
630 vertices_[v].id_ = id;
666 bool operator== (
const Corner& rhs)
const {
667 return t == rhs.t && v == rhs.v;
677 bool operator!= (
const Corner& rhs)
const {
678 return t != rhs.t || v != rhs.v;
691 index_t t2 = triangle_adjacent(c.t, plus1mod3(c.v));
692 index_t v = triangle_vertex(c.t, c.v);
693 c.v = find_triangle_vertex(t2, v);
702 v_to_t_dirty_ =
false;
703 for(index_t v = 0; v < max_v(); v++) {
704 set_vertex_triangle(v, NO_TRIANGLE);
706 for(index_t t = 0; t < max_t(); t++) {
707 if(triangle_is_used(t)) {
708 for(index_t iv = 0; iv < 3; iv++) {
709 set_vertex_triangle(triangle_vertex(t, iv), t);
721 if(first_free_ == END_OF_LIST) {
724 index_t result = first_free_;
725 first_free_ = next_triangle(first_free_);
726 mark_as_used(result);
727 set_triangle_id(result, -1);
741 index_t t = create_triangle();
742 triangles_[t].v[0] = v0;
743 triangles_[t].v[1] = v1;
744 triangles_[t].v[2] = v2;
761 index_t v0, index_t v1, index_t v2,
762 index_t t0, index_t t1, index_t t2
764 index_t t = create_triangle();
765 triangles_[t].v[0] = v0;
766 triangles_[t].v[1] = v1;
767 triangles_[t].v[2] = v2;
768 triangles_[t].t[0] = t0;
769 triangles_[t].t[1] = t1;
770 triangles_[t].t[2] = t2;
786 index_t v0, index_t v1, index_t v2,
787 index_t t0, index_t t1, index_t t2
791 triangles_[t].v[0] = v0;
792 triangles_[t].v[1] = v1;
793 triangles_[t].v[2] = v2;
794 triangles_[t].t[0] = t0;
795 triangles_[t].t[1] = t1;
796 triangles_[t].t[2] = t2;
819 index_t v0, index_t v1, index_t v2,
820 index_t t0, index_t t1, index_t t2
822 index_t t = create_triangle(v0, v1, v2, t0, t1, t2);
823 triangle_dual(t).set_point(p);
824 triangle_dual(t).set_weight(w);
846 index_t v0, index_t v1, index_t v2,
847 index_t t0, index_t t1, index_t t2
849 index_t t = create_triangle(v0, v1, v2, t0, t1, t2);
850 double* np = intersections_.new_item();
851 for(coord_index_t c = 0; c < dimension(); ++c) {
854 triangle_dual(t).set_point(np);
863 v_to_t_dirty_ =
true;
864 vertices_.push_back(
Vertex());
865 return vertices_.size() - 1;
886 template <index_t DIM>
889 index_t i, index_t j,
bool symbolic,
890 index_t t1, index_t t1ebord,
895 index_t t_adj = triangle_adjacent(t,e);
901 index_t new_t_first = index_t(-1);
902 index_t new_t_prev = index_t(-1);
906 index_t v1 = triangle_vertex(t, plus1mod3(e));
907 index_t v2 = triangle_vertex(t, minus1mod3(e));
910 index_t new_t = create_triangle(v_in, v1, v2);
912 triangle_dual(new_t).intersect_geom<DIM>(
915 triangle_dual(triangle_adjacent(t, e)),
920 triangle_dual(new_t).sym().intersect_symbolic(
921 triangle_dual(t).sym(),
922 triangle_dual(triangle_adjacent(t, e)).sym(),
929 set_triangle_adjacent(new_t, 0, t_adj);
930 index_t adj_e = triangle_adjacent_index(t_adj, t);
931 set_triangle_adjacent(t_adj, adj_e, new_t);
936 t_adj = index_t(triangle_adjacent(t,e));
937 while(triangle_is_conflict(t_adj)) {
939 e = minus1mod3(find_triangle_vertex(t,v2));
940 t_adj = index_t(triangle_adjacent(t,e));
944 if(new_t_prev == index_t(-1)) {
947 set_triangle_adjacent(new_t_prev, 1, new_t);
948 set_triangle_adjacent(new_t, 2, new_t_prev);
953 }
while((t != t1) || (e != t1ebord));
956 set_triangle_adjacent(new_t_prev, 1, new_t_first);
957 set_triangle_adjacent(new_t_first, 2, new_t_prev);
979 template <index_t DIM>
982 index_t i, index_t j,
bool exact,
983 index_t& conflict_begin, index_t& conflict_end
985 conflict_begin = END_OF_LIST;
986 conflict_end = END_OF_LIST;
995 for(index_t t = 0; t < max_t(); t++) {
996 if(triangle_is_used(t)) {
1004 append_triangle_to_conflict_list(
1005 t, conflict_begin, conflict_end
1020 index_t furthest_t =
1021 find_furthest_point_linear_scan<DIM>(
1024 propagate_conflict_list<DIM>(
1025 mesh, delaunay, furthest_t,
1027 conflict_begin, conflict_end
1043 template <index_t DIM>
1045 const Delaunay* delaunay, index_t i, index_t j
1047 index_t result = NO_TRIANGLE;
1048 double furthest_dist = 0.0;
1049 for(index_t t = 0; t < max_t(); ++t) {
1050 if(triangle_is_used(t)) {
1051 double d = signed_bisector_distance<DIM>(
1052 delaunay, i, j, triangle_dual(t).point()
1054 if(d < furthest_dist) {
1060 return (furthest_dist < 0) ? result : NO_TRIANGLE;
1074 template <index_t DIM>
1076 const Delaunay* delaunay, index_t i, index_t j,
const double* q
1081 for(coord_index_t c = 0; c < DIM; ++c) {
1104 template <index_t DIM>
1108 index_t i, index_t j,
bool exact,
1109 index_t& conflict_begin, index_t& conflict_end
1111 conflict_begin = END_OF_LIST;
1112 conflict_end = END_OF_LIST;
1115 if(first_t == NO_TRIANGLE) {
1119 std::stack<index_t> S;
1121 append_triangle_to_conflict_list(
1122 first_t, conflict_begin, conflict_end
1125 index_t t = S.top();
1127 for(
unsigned int e = 0; e < 3; e++) {
1128 index_t neigh = index_t(triangle_adjacent(t, e));
1129 if(!triangle_is_conflict(neigh)) {
1132 mesh, delaunay, triangle_dual(neigh),
1137 append_triangle_to_conflict_list(
1138 neigh, conflict_begin, conflict_end
1164 template <index_t DIM>
1168 index_t i, index_t j,
bool exact
1172 result = side_exact(
1177 symbolic_is_surface_
1209 const double* pi,
const double* pj,
1211 bool symbolic_is_surface =
false
1227 index_t conflict_begin, index_t conflict_end,
1228 index_t& t, index_t& e
1233 for(e = 0; e < 3; ++e) {
1234 index_t nt = triangle_adjacent(t, e);
1235 if(triangle_is_used(nt)) {
1239 t = next_triangle(t);
1240 }
while(t != END_OF_LIST);
1252 return triangles_[t].next_;
1265 triangles_[t].next_ = t2;
1276 triangles_[t].status_ = TRI_IS_FREE;
1285 triangles_[t].status_ = TRI_IS_CONFLICT;
1294 triangles_[t].status_ = TRI_IS_USED;
1307 index_t t, index_t& conflict_begin, index_t& conflict_end
1310 set_next_triangle(t, conflict_begin);
1311 mark_as_conflict(t);
1313 if(conflict_end == END_OF_LIST) {
1325 if(list_begin != END_OF_LIST) {
1328 index_t cur = list_begin;
1329 while(cur != list_end) {
1331 cur = next_triangle(cur);
1333 mark_as_free(list_end);
1334 set_next_triangle(list_end, first_free_);
1335 first_free_ = list_begin;
1346 first_free_ = triangles_.size();
1368 const Mesh* mesh, index_t t, index_t lf
1370 index_t t2 = mesh->cells.tet_adjacent(t, lf);
1371 if(t2 != GEO::NO_CELL && t2 > t) {
1372 index_t lf2 = mesh->cells.find_tet_adjacent(
1376 return index_t(4 * t2 + lf2);
1384 index_t first_free_;
1387 bool symbolic_is_surface_;
1388 signed_index_t cell_id_;
1390 static index_t plus1mod3_[3];
1391 static index_t minus1mod3_[3];
1398 static index_t plus1mod3(index_t i) {
1400 return plus1mod3_[i];
1408 static index_t minus1mod3(index_t i) {
1410 return minus1mod3_[i];
A function to suppress unused parameters compilation warnings.
#define geo_debug_assert(x)
Verifies that a condition is met.
Generic mechanism for attributes.
Common include file, providing basic definitions. Should be included before anything else by all head...
A Corner corresponds to a vertex seen from a triangle.
Corner(index_t t_in, index_t v_in)
Creates a Corner from a triangle index and local vertex index.
Corner()
Creates an uninitialized Corner.
Represents a facet of this ConvexCell in dual form.
Vertex()
Creates a new uninitialized Vertex.
Computes the intersection between a set of halfspaces.
std::ostream & show_stats(std::ostream &os) const
Displays the number of free,used,conflict triangles.
void initialize_from_surface_mesh(Mesh *mesh, bool symbolic)
Copies a Mesh into a ConvexCell.
void mark_as_free(index_t t)
Specify that a triangle is free.
void grow()
Allocates a new triangle.
index_t create_triangle(index_t v0, index_t v1, index_t v2)
Creates a new triangle with specified vertices.
index_t create_vertex()
Creates a new vertex.
bool find_triangle_on_border(index_t conflict_begin, index_t conflict_end, index_t &t, index_t &e) const
Gets a triangle and an edge on the internal border of the conflict zone.
const GEOGen::Vertex & triangle_dual(index_t t) const
Gets the dual vertex that corresponds to a triangle.
static index_t global_facet_id(const Mesh *mesh, index_t t, index_t lf)
Computes a unique global facet id from a mesh tetrahedron and local facet index.
void set_vertex_id(index_t v, signed_index_t id)
Sets the id of a vertex.
void set_triangle_id(index_t t, signed_index_t id)
Sets the id of a triangle.
Sign side(const Mesh *mesh, const Delaunay *delaunay, const GEOGen::Vertex &v, index_t i, index_t j, bool exact) const
Tests on which side a vertex is relative to a bisector.
index_t create_triangle()
Creates a new uninitialized triangle.
index_t max_v() const
Gets the maximum valid vertex index plus one.
TriangleStatus
Represents the current state of a triangle.
void get_conflict_list(const Mesh *mesh, const Delaunay *delaunay, index_t i, index_t j, bool exact, index_t &conflict_begin, index_t &conflict_end)
Determines the conflict zone.
static double signed_bisector_distance(const Delaunay *delaunay, index_t i, index_t j, const double *q)
Evaluates the equation of a bisector at a given point.
void set_vertex_triangle(index_t v, index_t t)
Stores in a vertex the index of one the triangles incident to it.
void mark_as_used(index_t t)
Specify that a triangle is used.
bool triangle_is_free(index_t t) const
Tests whether a given triangle is free.
index_t find_furthest_point_linear_scan(const Delaunay *delaunay, index_t i, index_t j) const
Finds the index of the vertex furthest away on the negative side of a bisector.
void initialize_from_mesh_tetrahedron(const Mesh *mesh, index_t t, bool symbolic, const GEO::Attribute< double > &vertex_weight)
Assigns a mesh tetrahedron to this ConvexCell.
Sign side_exact(const Mesh *mesh, const Delaunay *delaunay, const GEOGen::Vertex &v, const double *pi, const double *pj, coord_index_t dim, bool symbolic_is_surface=false) const
Tests on which side a vertex is relative to a bisector using exact predicates.
void propagate_conflict_list(const Mesh *mesh, const Delaunay *delaunay, index_t first_t, index_t i, index_t j, bool exact, index_t &conflict_begin, index_t &conflict_end)
Computes the conflict list by propagation from a conflict triangle.
signed_index_t cell_id() const
Gets the id of this ConvexCell.
void set_cell_id(signed_index_t i)
Sets the id of this ConvexCell.
void set_symbolic_is_surface(bool x)
Specifies that symbolic information is relative to surfacic mesh (rather than volumetric mesh).
signed_index_t clip_by_plane(const Mesh *mesh, const Delaunay *delaunay, index_t i, index_t j, bool exact, bool symbolic)
Clips this ConvexCell with a plane.
index_t nb_t() const
Gets the number of used triangles.
signed_index_t vertex_id(index_t v) const
Gets the id of a vertex.
void clear()
Clears this ConvexCell.
void set_next_triangle(index_t t, index_t t2)
Sets the successor of a triangle.
void merge_into_free_list(index_t list_begin, index_t list_end)
Merges a list of triangles into the free list.
index_t triangle_adjacent_index(index_t t1, index_t t2) const
Finds the edge along which two triangles are adjacent.
void copy(const ConvexCell &rhs)
Copies a ConvexCell.
index_t triangle_adjacent(index_t t, index_t e) const
Gets the index of a triangle adjacent to another one.
bool triangle_is_valid(index_t t) const
Tests whether a given triangle is valid.
void convert_to_mesh(Mesh *mesh, bool copy_symbolic_info=false)
Copies a ConvexCell into a Mesh.
index_t find_triangle_vertex(index_t t, index_t v) const
Finds the local index of a triangle vertex.
void mark_as_conflict(index_t t)
Specify that a triangle belongs to the conflict zone.
index_t create_triangle_copy(const double *p, index_t v0, index_t v1, index_t v2, index_t t0, index_t t1, index_t t2)
Creates a new triangles with specified vertices, adjacent triangles and geometric location at the dua...
index_t create_triangle(index_t v0, index_t v1, index_t v2, index_t t0, index_t t1, index_t t2)
Creates a new triangles with specified vertices and adjacent triangles.
void set_triangle_adjacent(index_t t, index_t e, index_t t2)
Sets a triangle adjacency.
void append_triangle_to_conflict_list(index_t t, index_t &conflict_begin, index_t &conflict_end)
Appends a triangle to the conflict list.
coord_index_t dimension() const
Gets the dimension of this ConvexCell.
void set_triangle(index_t t, index_t v0, index_t v1, index_t v2, index_t t0, index_t t1, index_t t2)
Sets the vertices and adjacent triangles of a triangle.
void set_triangle_vertex(index_t t, index_t iv, index_t v)
Sets a vertex of a triangle.
ConvexCell(coord_index_t dim)
ConvexCell constructor.
void init_v_to_t()
Updates the cache that stores for each vertex a triangle incident to it.
signed_index_t triangle_id(index_t t) const
Gets the id of a triangle.
index_t triangulate_hole(const Delaunay *delaunay, index_t i, index_t j, bool symbolic, index_t t1, index_t t1ebord, index_t v_in)
Triangulates the conflict zone.
bool triangle_is_used(index_t t) const
Tests whether a given triangle is used.
void move_to_next_around_vertex(Corner &c) const
Replaces a corner by the next corner obtained by turing around the vertex.
index_t create_triangle(const double *p, double w, index_t v0, index_t v1, index_t v2, index_t t0, index_t t1, index_t t2)
Creates a new triangles with specified vertices, adjacent triangles and geometric location at the dua...
index_t next_triangle(index_t t) const
Gets the successor of a triangle.
GEOGen::Vertex & triangle_dual(index_t t)
Gets the dual vertex that corresponds to a triangle.
bool triangle_is_conflict(index_t t) const
Tests whether a given triangle belongs to the conflict zone.
signed_index_t vertex_triangle(index_t v) const
Gets one of the triangles incident to a vertex.
index_t max_t() const
Gets the maximum valid triangle index plus one.
index_t triangle_vertex(index_t t, index_t iv) const
Gets the index of a triangle vertex.
An allocator for points that are created from intersections in GenericVoronoiDiagram.
Internal representation of vertices in GenericVoronoiDiagram.
Sign side_fast(const double *p1, const double *p2) const
Computes the side of this vertex relative to a bisector.
Manages an attribute attached to a set of object.
Abstract interface for Delaunay triangulation in Nd.
const double * vertex_ptr(index_t i) const
Gets a pointer to a vertex by its global index.
Vector with aligned memory allocation.
Types and utilities for manipulating vertices in geometric and symbolic forms in restricted Voronoi d...
T geo_sqr(T x)
Gets the square value of a value.
void geo_argused(const T &)
Suppresses compiler warnings about unused parameters.
Represents a vertex of this ConvexCell in dual form.
Triangle()
Creates a new uninitialized Triangle.
Triangle(index_t v0, index_t v1, index_t v2, index_t f0, index_t f1, index_t f2)
Creates a new triangle.