Corefinement and Autorefinement

Functions to corefine triangulated surface meshes and triangle soups.

Classes
struct	CGAL::Polygon_mesh_processing::Autorefinement::Default_visitor
struct	CGAL::Polygon_mesh_processing::Corefinement::Default_visitor< class TriangleMesh >
struct	CGAL::Polygon_mesh_processing::Corefinement::Non_manifold_output_visitor< class TriangleMesh, class VPM1, class VPM2 >

Functions
template<class PointRange , class TriangleRange , class NamedParameters = parameters::Default_named_parameters>
bool	CGAL::Polygon_mesh_processing::autorefine_triangle_soup (PointRange &soup_points, TriangleRange &soup_triangles, const NamedParameters &np=parameters::default_values())
	refines a soup of triangles so that no pair of triangles intersects.
template<class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::autorefine (TriangleMesh &tm, const NamedParameters &np=parameters::default_values())
	refines a triangle mesh so that no triangles intersects in their interior.
template<class OutputIterator , class TriangleMesh , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
OutputIterator	CGAL::Polygon_mesh_processing::surface_intersection (const TriangleMesh &tm1, const TriangleMesh &tm2, OutputIterator polyline_output, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
	computes the intersection of triangles of tm1 and tm2.

Function Documentation

autorefine()

template<class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::autorefine	(	TriangleMesh &	tm,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/autorefinement.h>

refines a triangle mesh so that no triangles intersects in their interior.

Note that this function is only provided as a shortcut for calling autorefine_triangle_soup() with a mesh. For any advance usage the aforementioned function should be called directly.

Template Parameters

TriangleMesh	a model of HalfedgeListGraph, FaceListGraph, and MutableFaceGraph
NamedParameters	a sequence of Named Parameters

Parameters

tm	input triangulated surface mesh
np	an optional sequence of Named Parameters among the ones listed below

Warning

clear(tm) will be called before filling tm with the refined mesh.

Optional Named Parameters

concurrency_tag a tag indicating if the task should be done using one or several threads. Type: Either CGAL::Sequential_tag, or CGAL::Parallel_tag, or CGAL::Parallel_if_available_tag Default: CGAL::Sequential_tag
geom_traits an instance of a geometric traits class Type: a class model of PMPSelfIntersectionTraits Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex point type.
vertex_point_map a property map associating points to the vertices of tm Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, tm) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in TriangleMesh.

autorefine_triangle_soup()

template<class PointRange , class TriangleRange , class NamedParameters = parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::autorefine_triangle_soup	(	PointRange &	soup_points,
		TriangleRange &	soup_triangles,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/autorefinement.h>

refines a soup of triangles so that no pair of triangles intersects.

Output triangles may share a common edge or a common vertex (but with the same indexed position in points). Note that if apply_iterative_snap_rounding option is set to false, points in soup_points can only be added (intersection points) at the end of the container, with the initial order preserved. Note that if soup_points contains two or more identical points then only the first copy (following the order in the soup_points) will be used in soup_triangles. if apply_iterative_snap_rounding is set to true, all duplicates points are removed. soup_triangles will be updated to contain both the input triangles and the new subdivided triangles. Degenerate triangles will be removed. Also if apply_iterative_snap_rounding option is set to false, triangles in soup_triangles will be triangles without intersection first, followed by triangles coming from a subdivision induced by an intersection. The named parameter visitor() can be used to track the creation and removal of triangles independently of the apply_iterative_snap_rounding option. If the apply_iterative_snap_rounding parameter is set to true, the coordinates of the vertices are rounded to fit within the precision of a double-precision floating point, while trying to make the triangle soup free of intersections. The snap_grid_size() parameter limits the drift of the snapped vertices. A smaller value is more likely to output an intersection free output and perform more vertex collapses, but it may increase the Hausdorff distance from the input.

Template Parameters

PointRange	a model of the concept RandomAccessContainer whose value type is the point type
TriangleRange	a model of the concepts RandomAccessContainer, BackInsertionSequence and Swappable, whose value type is a model of the concept RandomAccessContainer whose value type is convertible to std::size_t and that is constructible from an std::initializer_list<std::size_t> of size 3.
NamedParameters	a sequence of Named Parameters

Parameters

soup_points	points of the soup of polygons
soup_triangles	each element in the range describes a triangle using the indexed position of the points in soup_points
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

concurrency_tag a tag indicating if the task should be done using one or several threads. Type: Either CGAL::Sequential_tag, or CGAL::Parallel_tag, or CGAL::Parallel_if_available_tag Default: CGAL::Sequential_tag
point_map a property map associating points to the elements of the range soup_points Type: a model of ReadWritePropertyMap whose value type is a point type Default: CGAL::Identity_property_map
geom_traits an instance of a geometric traits class Type: a class model of Kernel Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the point type.
visitor a visitor used to track the creation of new faces Type: a class model of PMPAutorefinementVisitor Default: Autorefinement::Default_visitor Extra: The visitor will be copied.
apply_iterative_snap_rounding Enable the rounding of the coordinates so that they fit in doubles. Type: Boolean Default: false
snap_grid_size A value gs used to scale the points to [-2^gs, 2^gs] before rounding them on integers. Used only if apply_iterative_snap_rounding() is set to true Type: unsigned int Default: 23 Extra: Must be lower than 52.
number_of_iterations Maximum number of iterations performed by the snap rounding algorithm. Used only if apply_iterative_snap_rounding is true. Type: unsigned int Default: 5

Returns

true if apply_iterative_snap_rounding is set to false. Otherwise, returns true if the modified triangle soup is free of self-intersections, or false if the algorithm was unable to produce such a result within the allowed number of iterations. In the latter case, the output triangle soup represents a partial result from the final iteration, with no guarantee of its validity.

Examples

Polygon_mesh_processing/snap_polygon_soup.cpp, and Polygon_mesh_processing/soup_autorefinement.cpp.

surface_intersection()

template<class OutputIterator , class TriangleMesh , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>

OutputIterator CGAL::Polygon_mesh_processing::surface_intersection	(	const TriangleMesh &	tm1,
		const TriangleMesh &	tm2,
		OutputIterator	polyline_output,
		const NamedParameters1 &	np1 = parameters::default_values(),
		const NamedParameters2 &	np2 = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/intersection.h>

computes the intersection of triangles of tm1 and tm2.

The output is a set of polylines with all vertices but endpoints being of degree 2.

Precondition

!CGAL::Polygon_mesh_processing::does_self_intersect(tm1)

!CGAL::Polygon_mesh_processing::does_self_intersect(tm2)

Template Parameters

TriangleMesh	a model of MutableFaceGraph, HalfedgeListGraph and FaceListGraph
NamedParameters1	a sequence of Named Parameters
NamedParameters2	a sequence of Named Parameters
OutputIterator	an output iterator in which std::vector of points can be put. The point type is the one from the vertex property map

Parameters

tm1	first input triangulated surface mesh
tm2	second input triangulated surface mesh
polyline_output	output iterator of polylines. Each polyline will be given as a vector of points
np1	an optional sequence of Named Parameters among the ones listed below
np2	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of tm1 (tm2) Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, tm1 (tm2)) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of tm1 (tm2) Extra: Both vertex point maps must have the same value type

throw_on_self_intersection If true, the set of triangles close to the intersection of tm1 and tm2 will be checked for self-intersections and Corefinement::Self_intersection_exception will be thrown if at least one self-intersection is found. Type: Boolean Default: false Extra: np1 only

See also

do_intersect()