Geogram  Version 1.9.1
A programming library of geometric algorithms
GEO::MeshSurfaceIntersection Class Reference

Computes surface intersections. More...

#include <geogram/mesh/mesh_surface_intersection.h>

Classes

class  Halfedges
 Halfedfge-like API wrappers on top of a triangulated mesh. More...
 
class  RadialBundles
 Represents the set of radial halfedge bundles. More...
 
class  RadialPolylines
 
class  RadialSort
 

Public Types

typedef exact::vec3h ExactPoint
 

Public Member Functions

 MeshSurfaceIntersection (Mesh &M)
 
void intersect ()
 
void remove_external_shell ()
 Removes all the facets that are on the outer boundary. More...
 
void remove_internal_shells ()
 Removes all the facets that are not on the outer boundary. More...
 
void remove_fins ()
 
void classify (const std::string &expr)
 Classifies the facets and keep only the ones on the boundary of a combination of regions defined by a boolean expression. More...
 
index_t classify_component (index_t component, index_t v)
 Classifies a connected component. More...
 
index_t tentatively_classify_component_vertex_fast (index_t component, index_t v)
 Classifies a vertex of the computed intersection. More...
 
index_t tentatively_classify_component_vertex (index_t component, index_t v)
 Classifies a vertex of the computed intersection. More...
 
void simplify_coplanar_facets (double angle_tolerance=0.0)
 Merge coplanar facets and retriangulate them using a Constrained Delaunay triangulation. More...
 
void set_verbose (bool x)
 Display information while computing the intersection. Default is unset.
 
void set_monster_threshold (index_t nb)
 Sets the threshold from which triangle is considered to be a monster. More...
 
void set_dry_run (bool x)
 In dry run mode, the computed local triangulations are not inserted in the global mesh. This is for benchmarking. Default is off.
 
void set_delaunay (bool x)
 If set, compute constrained Delaunay triangulation in the intersected triangles. If there are intersections in coplanar facets, it guarantees uniqueness of their triangulation. Default is set.
 
void set_detect_intersecting_neighbors (bool x)
 detect and compute intersections between facets that share a facet or an edge. Set to false if input is a set of conformal meshes. Default is set.
 
void set_radial_sort (bool x)
 Specifies whether surfaces should be duplicated and radial edges sorted in order to create the volumetric partition yielded by the intersection. More...
 
void set_normalize (bool x)
 Specifies whether coordinates should be normalized during computation. If set, original coordinates are restored at the end of intersect(). More...
 
void set_build_skeleton (Mesh *skeleton, bool trim_fins=false)
 Optionally save the skeleton (that is, the collection of non-manifold edges) to a given mesh. This option is not compatible with dry_run (throws an assertion fail if set). More...
 
void set_interpolate_attributes (bool x)
 Specifies that attributes should be interpolated. More...
 

Protected Types

typedef vec3HgLexicoCompare< exact::scalarExactPointCompare
 

Protected Member Functions

void intersect_prologue ()
 substep of intersect(), prepares the mesh More...
 
void intersect_get_intersections (vector< IsectInfo > &intersections)
 substep of intersect(), finds all the intersection points and segments. More...
 
void intersect_remesh_intersections (vector< IsectInfo > &intersections)
 substep of intersect(), inserts the intersection points and segments into the triangles. More...
 
void intersect_epilogue (const vector< IsectInfo > &intersections)
 subset of intersect(), cleans the resulting mesh and undoes optional geometric normalization. More...
 
void lock ()
 Acquires a lock on this mesh. More...
 
void unlock ()
 Releases the lock associated with this mesh.
 
ExactPoint exact_vertex (index_t v) const
 Gets the exact point associated with a vertex. More...
 
index_t find_or_create_exact_vertex (const ExactPoint &p)
 Finds or creates a vertex in the mesh, by exact coordinates. More...
 
Meshtarget_mesh ()
 Gets the target mesh. More...
 
const Meshtarget_mesh () const
 Gets the target mesh. More...
 
const Meshreadonly_mesh () const
 Gets a copy of the initial mesh passed to the constructor. More...
 
void build_Weiler_model ()
 Builds the Weiler model. More...
 
void mark_external_shell (vector< index_t > &on_external_shell)
 Marks all the facets that are on the external shell.
 

Protected Attributes

Process::spinlock lock_
 
Meshmesh_
 
Mesh mesh_copy_
 
Attribute< const ExactPoint * > vertex_to_exact_point_
 
std::map< ExactPoint, index_t, ExactPointCompareexact_point_to_vertex_
 
bool verbose_
 
bool fine_verbose_
 
bool delaunay_
 
bool detect_intersecting_neighbors_
 
bool use_radial_sort_
 
PCK::SOSMode SOS_bkp_
 
bool rescale_
 
bool normalize_
 
vec3 normalize_center_
 
double normalize_radius_
 
index_t monster_threshold_
 
bool dry_run_
 
Meshskeleton_
 
bool skeleton_trim_fins_
 
bool interpolate_attributes_
 
class GEO::MeshSurfaceIntersection::Halfedges halfedges_
 
class GEO::MeshSurfaceIntersection::RadialBundles radial_bundles_
 
class GEO::MeshSurfaceIntersection::RadialPolylines radial_polylines_
 

Friends

class MeshInTriangle
 
class CoplanarFacets
 

Detailed Description

Computes surface intersections.

New vertices are stored with exact coordinates

Definition at line 68 of file mesh_surface_intersection.h.

Member Function Documentation

◆ build_Weiler_model()

void GEO::MeshSurfaceIntersection::build_Weiler_model ( )
protected

Builds the Weiler model.

The Weiler model is a volumetric representation, where each facet is on the boundary of a closed region. Facets are duplicated, so that when two regions touch each other, each region has its own facet on the boundary. Two facets that touch in this way are connected by alpha3 links. Facets on the boundary of the same region are connected by alpha2 links.

◆ classify()

void GEO::MeshSurfaceIntersection::classify ( const std::string &  expr)

Classifies the facets and keep only the ones on the boundary of a combination of regions defined by a boolean expression.

A facet attribute of type index_t named "operand_bit" indicates for each facet to which operand of a n-ary boolean operation it corresponds to (the same facet might belong to several operands).

Precondition
set_radial_sort(true) was set before calling intersect()
Parameters
[in]exprthe boolean function in ASCII. One can use the following elements, and parentheses:
  • Variables: A..Z or x0..x31, correspond to the bits of the "operand_bit" attribute
  • the special variable '*' corresponds to the union of everything
  • and: '&' or '*'
  • or: '|' or '+'
  • xor: '^'
  • difference: '-'
  • not: '!' or '~' Special values for expr:
  • "union" (union of everything), synonym of '*'
  • "intersection" (intersection of everything).

◆ classify_component()

index_t GEO::MeshSurfaceIntersection::classify_component ( index_t  component,
index_t  v 
)

Classifies a connected component.

Parameters
[in]componenta connected component
[in]va vertex of the connected component
Returns
the inclusion bits of the connected component relative to the operands

◆ exact_vertex()

ExactPoint GEO::MeshSurfaceIntersection::exact_vertex ( index_t  v) const
protected

Gets the exact point associated with a vertex.

If the vertex has explicit exact coordinates associated with it, they are returned, else an exact ExactPoint is constructed from the double-precision coordinates stored in the mesh

Parameters
[in]va vertex of the mesh
Returns
the exact coordinates of this vertex, as a vector in homogeneous coordinates stored as expansions

◆ find_or_create_exact_vertex()

index_t GEO::MeshSurfaceIntersection::find_or_create_exact_vertex ( const ExactPoint p)
protected

Finds or creates a vertex in the mesh, by exact coordinates.

If there is already a vertex with coordinates p, then the existing vertex is returned, else a new vertex is constructed. Note that only the vertices created by find_or_create_vertex() can be returned as existing vertices. Mesh vertices stored as double- precision coordinates are not retreived by this function.

Parameters
[in]pthe exact coordinates of a point
Returns
the index of a mesh vertex with p as coordinates

◆ intersect()

void GEO::MeshSurfaceIntersection::intersect ( )

A facet attribute of type index_t named "operand_bit" can indicate for each facet to which operand of a n-ary boolean operation it corresponds to (the same facet might belong to several operands). It is taken into account by the two variants of mesh_classify_intersections()

◆ intersect_epilogue()

void GEO::MeshSurfaceIntersection::intersect_epilogue ( const vector< IsectInfo > &  intersections)
protected

subset of intersect(), cleans the resulting mesh and undoes optional geometric normalization.

Parameters
[in]intersectionsthe vector of IsectInfo. Each IsectInfo is either an intersection vertex or a pair of intersection vertices. Intersection vertices are represented in symbolic form, as a couple of triangle indices plus a couple of triangle subregion id (TriangleRegion).

find the intersection that landed exactly onto an existing mesh vertex and merges them. Removes the initial triangles that had intersections (they are replaced with new triangles). Merges duplicated triangles that come from coplanar regions. Undoes geometric normalizations. Restores initial symbolic perturbation mode.

◆ intersect_get_intersections()

void GEO::MeshSurfaceIntersection::intersect_get_intersections ( vector< IsectInfo > &  intersections)
protected

substep of intersect(), finds all the intersection points and segments.

Parameters
[out]intersectionsthe vector of IsectInfo. Each IsectInfo is either an intersection vertex or a pair of intersection vertices. Intersection vertices are represented in symbolic form, as a couple of triangle indices plus a couple of triangle subregion id (TriangleRegion).

First uses a MeshFacetsAABB to detect candidate pairs of intersecting triangles, then calls triangles_intersection() in parallel. Finally, mesh facets are shuffled randomly, to ensure balanced multithreading for the subsequent steps.

◆ intersect_prologue()

void GEO::MeshSurfaceIntersection::intersect_prologue ( )
protected

substep of intersect(), prepares the mesh

Tesselates the facets if they are not triangulated, creates the operand bit for boolean op classification, removes the exactly degenerate triangles, colocate the points, optionally scales the coordinates and sets symbolic perturbation mode to lexicographic.

◆ intersect_remesh_intersections()

void GEO::MeshSurfaceIntersection::intersect_remesh_intersections ( vector< IsectInfo > &  intersections)
protected

substep of intersect(), inserts the intersection points and segments into the triangles.

Parameters
[in,out]intersectionsthe vector of IsectInfo. Each IsectInfo is either an intersection vertex or a pair of intersection vertices. Intersection vertices are represented in symbolic form, as a couple of triangle indices plus a couple of triangle subregion id (TriangleRegion).

Uses MeshInTriangle, a class derived from CDTBase2d, that computes a constrained Delaunay triangulation with intersection points represented with exact coordinates. Operates in parallel. Each thread computes constrained Delaunay triangulations independently, and commits them in the resulting mesh (with a lock to protect concurrent accesses). The initial mesh is copied (and kept in the mesh_copy_ member), so that concurrent read access do not need a lock.

◆ lock()

void GEO::MeshSurfaceIntersection::lock ( )
inlineprotected

Acquires a lock on this mesh.

A single thread can have the lock. When multiple threads want the lock, the ones that do not have it keep waiting until the one that owns the lock calls unlock(). All threads that modify the target mesh should call this function

See also
unlock()

Definition at line 339 of file mesh_surface_intersection.h.

◆ readonly_mesh()

const Mesh& GEO::MeshSurfaceIntersection::readonly_mesh ( ) const
inlineprotected

Gets a copy of the initial mesh passed to the constructor.

It is used by the multithreaded mesh intersection algorithm. Each thread needs to both access the initial geometry and create new vertices and triangles in the target mesh. Creating new mesh elements can reallocate the internal vectors of the mesh, and change the address of the elements. This should not occur while another thread is reading the mesh. Copying the initial geometry in another mesh prevents this type of problems.

Returns
a const reference to the mesh that was copied from the one passed to the constructor

Definition at line 403 of file mesh_surface_intersection.h.

◆ remove_external_shell()

void GEO::MeshSurfaceIntersection::remove_external_shell ( )

Removes all the facets that are on the outer boundary.

Precondition
set_radial_sort(true) was set before calling intersect()

◆ remove_internal_shells()

void GEO::MeshSurfaceIntersection::remove_internal_shells ( )

Removes all the facets that are not on the outer boundary.

Precondition
set_radial_sort(true) was set before calling intersect()

◆ set_build_skeleton()

void GEO::MeshSurfaceIntersection::set_build_skeleton ( Mesh skeleton,
bool  trim_fins = false 
)
inline

Optionally save the skeleton (that is, the collection of non-manifold edges) to a given mesh. This option is not compatible with dry_run (throws an assertion fail if set).

Parameters
[in]skeletona pointer to the mesh that will receive the skeleton.
[in]trim_finsif set, do not keep bundles that have less than three halfedges.

Definition at line 254 of file mesh_surface_intersection.h.

◆ set_interpolate_attributes()

void GEO::MeshSurfaceIntersection::set_interpolate_attributes ( bool  x)
inline

Specifies that attributes should be interpolated.

Parameters
[in]xtrue if attributes should be interpolated, false otherwise. Default is false.

Definition at line 264 of file mesh_surface_intersection.h.

◆ set_monster_threshold()

void GEO::MeshSurfaceIntersection::set_monster_threshold ( index_t  nb)
inline

Sets the threshold from which triangle is considered to be a monster.

Monster triangles are saved to a file for the zoo.

Parameters
[in]nbif a triangle has more than nb intersections in it, then it is considered to be a monster.

Definition at line 190 of file mesh_surface_intersection.h.

◆ set_normalize()

void GEO::MeshSurfaceIntersection::set_normalize ( bool  x)
inline

Specifies whether coordinates should be normalized during computation. If set, original coordinates are restored at the end of intersect().

Parameters
[in]xtrue if coordinates should be normalized. Default is set.

Definition at line 240 of file mesh_surface_intersection.h.

◆ set_radial_sort()

void GEO::MeshSurfaceIntersection::set_radial_sort ( bool  x)
inline

Specifies whether surfaces should be duplicated and radial edges sorted in order to create the volumetric partition yielded by the intersection.

Parameters
[in]xtrue if radial edges should be sorted. Default is set

Definition at line 229 of file mesh_surface_intersection.h.

◆ simplify_coplanar_facets()

void GEO::MeshSurfaceIntersection::simplify_coplanar_facets ( double  angle_tolerance = 0.0)

Merge coplanar facets and retriangulate them using a Constrained Delaunay triangulation.

Parameters
[in]angle_toleranceangle tolerance for detecting coplanar facets and colinear edges (in degrees)

◆ target_mesh() [1/2]

Mesh& GEO::MeshSurfaceIntersection::target_mesh ( )
inlineprotected

Gets the target mesh.

Returns
a modifiable reference to the mesh that was passed to the constructor

Definition at line 378 of file mesh_surface_intersection.h.

◆ target_mesh() [2/2]

const Mesh& GEO::MeshSurfaceIntersection::target_mesh ( ) const
inlineprotected

Gets the target mesh.

Returns
a const reference to the mesh that was passed to the constructor

Definition at line 387 of file mesh_surface_intersection.h.

◆ tentatively_classify_component_vertex()

index_t GEO::MeshSurfaceIntersection::tentatively_classify_component_vertex ( index_t  component,
index_t  v 
)

Classifies a vertex of the computed intersection.

Parameters
[in]componenta component
[in]va vertex of the component
Returns
the operand inclusion bits, or NO_INDEX if classification was not successful.

Uses raytracing along a random direction. The classification can be not successful if degenerate ray-triangle intersections are encountered. Then one needs to try again.

◆ tentatively_classify_component_vertex_fast()

index_t GEO::MeshSurfaceIntersection::tentatively_classify_component_vertex_fast ( index_t  component,
index_t  v 
)

Classifies a vertex of the computed intersection.

Parameters
[in]componenta component
[in]va vertex of the component
Returns
the operand inclusion bits, or NO_INDEX if classification was not successful.

Uses raytracing along a random direction. The classification can be not successful if degenerate ray-triangle intersections are encountered. Then one needs to try again using tentatively_classify_component_vertex() (multiple times if required).


The documentation for this class was generated from the following file: