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.

void	remove_internal_shells ()
	Removes all the facets that are not on the outer boundary.

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.

index_t	classify_component (index_t component, index_t v)
	Classifies a connected component.

index_t	tentatively_classify_component_vertex_fast (index_t component, index_t v)
	Classifies a vertex of the computed intersection.

index_t	tentatively_classify_component_vertex (index_t component, index_t v)
	Classifies a vertex of the computed intersection.

void	simplify_coplanar_facets (double angle_tolerance=0.0)
	Merge coplanar facets and retriangulate them using a Constrained Delaunay triangulation.

void	set_verbose (bool x)
	Display information while computing the intersection. Default is unset.

void	set_fine_verbose (bool x)
	Display detailed 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.

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.

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

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).

void	set_interpolate_attributes (bool x)
	Specifies that attributes should be interpolated.

Protected Types
typedef vec3HgLexicoCompare< exact::scalar >	ExactPointCompare

Protected Member Functions
void	intersect_prologue ()
	substep of intersect(), prepares the mesh

void	intersect_get_intersections (vector< IsectInfo > &intersections)
	substep of intersect(), finds all the intersection points and segments.

void	intersect_remesh_intersections (vector< IsectInfo > &intersections)
	substep of intersect(), inserts the intersection points and segments into the triangles.

void	intersect_epilogue (const vector< IsectInfo > &intersections)
	subset of intersect(), cleans the resulting mesh and undoes optional geometric normalization.

void	lock ()
	Acquires a lock on this mesh.

void	unlock ()
	Releases the lock associated with this mesh.

ExactPoint	exact_vertex (index_t v) const
	Gets the exact point associated with a vertex.

bool	is_original_vertex (index_t v) const
	Tests whether a given vertex is an original mesh vertex or an intersection.

index_t	find_or_create_exact_vertex (const ExactPoint &p)
	Finds or creates a vertex in the mesh, by exact coordinates.

Mesh &	target_mesh ()
	Gets the target mesh.

const Mesh &	target_mesh () const
	Gets the target mesh.

const Mesh &	readonly_mesh () const
	Gets a copy of the initial mesh passed to the constructor.

void	build_Weiler_model ()
	Builds the Weiler model.

void	mark_external_shell (vector< index_t > &on_external_shell)
	Marks all the facets that are on the external shell.

index_t	get_initial_facet (index_t f) const
	Gets the vertices of the initial facet (in mesh_copy_) that supports a facet in the intersection mesh (in mesh_)

bool	initial_facet_is_flipped (index_t f) const
	Indicates whether the initial facet (in mesh_copy_) that supports a facet in the intersection mesh (in mesh_) has same orientation or not.

std::tuple< vec3, vec3, vec3 >	get_initial_facet_vertices (index_t f) const
	Gets the vertices of the initial facet (in mesh_copy_) that supports a facet in the intersection mesh (in mesh_)

Protected Attributes
Process::spinlock	lock_

Mesh &	mesh_

Mesh	mesh_copy_

Attribute< const ExactPoint * >	vertex_to_exact_point_

Attribute< index_t >	original_facet_id_

Attribute< bool >	f_is_flipped_

std::map< ExactPoint, index_t, ExactPointCompare >	exact_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_

Mesh *	skeleton_

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 69 of file mesh_surface_intersection.h.

Member Typedef Documentation

◆ ExactPoint

typedef exact::vec3h GEO::MeshSurfaceIntersection::ExactPoint

Definition at line 72 of file mesh_surface_intersection.h.

◆ ExactPointCompare

typedef vec3HgLexicoCompare<exact::scalar> GEO::MeshSurfaceIntersection::ExactPointCompare

protected

Definition at line 600 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]

expr

the 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]	component	a connected component
[in]	v	a 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] v a 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] p the exact coordinates of a point

Returns: the index of a mesh vertex with p as coordinates

◆ get_initial_facet()

index_t GEO::MeshSurfaceIntersection::get_initial_facet ( index_t f ) const

inlineprotected

Gets the vertices of the initial facet (in mesh_copy_) that supports a facet in the intersection mesh (in mesh_)

Parameters

[in] f the facet in mesh_

Returns: the index of the original facet in mesh_copy_

Definition at line 456 of file mesh_surface_intersection.h.

◆ get_initial_facet_vertices()

std::tuple< vec3, vec3, vec3 > GEO::MeshSurfaceIntersection::get_initial_facet_vertices ( index_t f ) const

inlineprotected

Gets the vertices of the initial facet (in mesh_copy_) that supports a facet in the intersection mesh (in mesh_)

Orientation is preserved. It is important, since it makes it possible to call predicates with points that have simpler coordinates

Parameters

[in] f the facet in mesh_

Returns: the three vertices of the initial facet in mesh_copy_ as a tuple of vec3

Definition at line 483 of file mesh_surface_intersection.h.

◆ initial_facet_is_flipped()

bool GEO::MeshSurfaceIntersection::initial_facet_is_flipped ( index_t f ) const

inlineprotected

Indicates whether the initial facet (in mesh_copy_) that supports a facet in the intersection mesh (in mesh_) has same orientation or not.

Parameters

[in] f the facet in mesh_

Return values

false	if `f` and the initial facet in mesh_copy_ have the same orientation
true	otherwise

Definition at line 469 of file mesh_surface_intersection.h.

◆ 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] intersections the 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] intersections the 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] intersections the 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.

◆ is_original_vertex()

bool GEO::MeshSurfaceIntersection::is_original_vertex ( index_t v ) const

inlineprotected

Tests whether a given vertex is an original mesh vertex or an intersection.

Parameters

[in] v a vertex of the mesh

Return values

true	if v is an original vertex of the mesh
false	if v is an intersection vertex, with exact coordinates

Definition at line 382 of file mesh_surface_intersection.h.

◆ 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 353 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 428 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]	skeleton	a pointer to the mesh that will receive the skeleton.
[in]	trim_fins	if set, do not keep bundles that have less than three halfedges.

Definition at line 268 of file mesh_surface_intersection.h.

◆ set_delaunay()

void GEO::MeshSurfaceIntersection::set_delaunay ( bool x )

inline

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.

Definition at line 223 of file mesh_surface_intersection.h.

◆ set_detect_intersecting_neighbors()

void GEO::MeshSurfaceIntersection::set_detect_intersecting_neighbors ( bool x )

inline

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.

Definition at line 232 of file mesh_surface_intersection.h.

◆ set_dry_run()

void GEO::MeshSurfaceIntersection::set_dry_run ( bool x )

inline

In dry run mode, the computed local triangulations are not inserted in the global mesh. This is for benchmarking. Default is off.

Definition at line 213 of file mesh_surface_intersection.h.

◆ set_fine_verbose()

void GEO::MeshSurfaceIntersection::set_fine_verbose ( bool x )

inline

Display detailed information while computing the intersection. Default is unset.

Definition at line 190 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] x true if attributes should be interpolated, false otherwise. Default is false.

Definition at line 278 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] nb if a triangle has more than nb intersections in it, then it is considered to be a monster.

Definition at line 204 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] x true if coordinates should be normalized. Default is set.

Definition at line 254 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] x true if radial edges should be sorted. Default is set

Definition at line 243 of file mesh_surface_intersection.h.

◆ set_verbose()

void GEO::MeshSurfaceIntersection::set_verbose ( bool x )

inline

Display information while computing the intersection. Default is unset.

Definition at line 179 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_tolerance angle 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 403 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 412 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]	component	a component
[in]	v	a 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]	component	a component
[in]	v	a 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).