blender::meshintersect Namespace Reference

Classes
class	CDT_input
class	CDT_result
struct	CDTVert
struct	CDTEdge
struct	CDTFace
struct	SymEdge
struct	FatCo
struct	FatCo< double >
struct	CDTArrangement
class	CDT_state
class	SiteInfo
class	CrossData
struct	EdgeToSort

Functions
CDT_result< double >	delaunay_2d_calc (const CDT_input< double > &input, CDT_output_type output_type)
template<typename T>
T	math_abs (const T v)
template<>
double	math_abs< double > (const double v)
template<typename T>
double	math_to_double (const T)
template<>
double	math_to_double< double > (const double v)
template<typename T>
SymEdge< T > *	sym (const SymEdge< T > *se)
template<typename T>
SymEdge< T > *	prev (const SymEdge< T > *se)
template<typename T>
std::ostream &	operator<< (std::ostream &stream, const FatCo< T > &co)
template<typename T>
std::string	vertname (const CDTVert< T > *v)
static std::string	trunc_ptr (const void *p)
template<typename T>
std::string	sename (const SymEdge< T > *se)
template<typename T>
std::ostream &	operator<< (std::ostream &os, const SymEdge< T > &se)
template<typename T>
std::ostream &	operator<< (std::ostream &os, const SymEdge< T > *se)
template<typename T>
std::string	short_se_dump (const SymEdge< T > *se)
template<typename T>
std::ostream &	operator<< (std::ostream &os, const CDT_state< T > &cdt_state)
template<typename T>
void	cdt_draw (const std::string &label, const CDTArrangement< T > &cdt)
template<typename T>
static int	filtered_orient2d (const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c)
template<>
int	filtered_orient2d< double > (const FatCo< double > &a, const FatCo< double > &b, const FatCo< double > &c)
template<typename T>
static int	filtered_incircle (const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c, const FatCo< T > &d)
template<>
int	filtered_incircle< double > (const FatCo< double > &a, const FatCo< double > &b, const FatCo< double > &c, const FatCo< double > &d)
template<typename T>
static bool	in_line (const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c)
template<>
bool	in_line< double > (const FatCo< double > &a, const FatCo< double > &b, const FatCo< double > &c)
static bool	id_range_in_list (const blender::Set< int > &id_list, int range_start, int range_end)
static void	add_to_input_ids (blender::Set< int > &dst, int input_id)
static void	add_list_to_input_ids (blender::Set< int > &dst, const blender::Set< int > &src)
template<typename T>
bool	is_border_edge (const CDTEdge< T > *e, const CDT_state< T > *cdt)
template<typename T>
bool	is_constrained_edge (const CDTEdge< T > *e)
template<typename T>
bool	is_deleted_edge (const CDTEdge< T > *e)
template<typename T>
bool	is_original_vert (const CDTVert< T > *v, CDT_state< T > *cdt)
template<typename T>
SymEdge< T > *	find_symedge_between_verts (const CDTVert< T > *v1, const CDTVert< T > *v2)
template<typename T>
SymEdge< T > *	find_symedge_with_face (const CDTVert< T > *v, const CDTFace< T > *f)
template<typename T>
bool	exists_edge (const CDTVert< T > *v1, const CDTVert< T > *v2)
template<typename T>
bool	vert_touches_face (const CDTVert< T > *v, const CDTFace< T > *f)
template<typename T>
bool	site_lexicographic_sort (const SiteInfo< T > &a, const SiteInfo< T > &b)
template<typename T>
void	find_site_merges (Array< SiteInfo< T > > &sites)
template<typename T>
bool	vert_left_of_symedge (CDTVert< T > *v, SymEdge< T > *se)
template<typename T>
bool	vert_right_of_symedge (CDTVert< T > *v, SymEdge< T > *se)
template<typename T>
bool	dc_tri_valid (SymEdge< T > *se, SymEdge< T > *basel, SymEdge< T > *basel_sym)
template<typename T>
void	dc_tri (CDTArrangement< T > *cdt, Array< SiteInfo< T > > &sites, int start, int end, SymEdge< T > **r_le, SymEdge< T > **r_re)
template<typename T>
void	dc_triangulate (CDTArrangement< T > *cdt, Array< SiteInfo< T > > &sites)
template<typename T>
void	initial_triangulation (CDTArrangement< T > *cdt)
template<typename T>
static void	re_delaunay_triangulate (CDTArrangement< T > *cdt, SymEdge< T > *se)
template<typename T>
int	tri_orient (const SymEdge< T > *t)
template<typename T>
bool	get_next_crossing_from_vert (CDT_state< T > *cdt_state, CrossData< T > *cd, CrossData< T > *cd_next, const CDTVert< T > *v2)
template<typename T>
void	fill_crossdata_for_through_vert (CDTVert< T > *v, SymEdge< T > *cd_out, CrossData< T > *cd, CrossData< T > *cd_next)
template<typename T>
void	fill_crossdata_for_intersect (const FatCo< T > &curco, const CDTVert< T > *v2, SymEdge< T > *t, CrossData< T > *cd, CrossData< T > *cd_next, const T epsilon)
template<typename T>
void	get_next_crossing_from_edge (CrossData< T > *cd, CrossData< T > *cd_next, const CDTVert< T > *v2, const T epsilon)
template<typename T>
void	dump_crossings (const Span< CrossData< T > > crossings)
template<typename T>
void	add_edge_constraint (CDT_state< T > *cdt_state, CDTVert< T > *v1, CDTVert< T > *v2, int input_id, LinkNode **r_edges)
template<typename T>
void	add_edge_constraints (CDT_state< T > *cdt_state, const CDT_input< T > &input)
template<typename T>
void	add_face_ids (CDT_state< T > *cdt_state, SymEdge< T > *face_symedge, int face_id, int fedge_start, int fedge_end)
static int	power_of_10_greater_equal_to (int x)
template<typename T>
int	add_face_constraints (CDT_state< T > *cdt_state, const CDT_input< T > &input, CDT_output_type output_type)
template<typename T>
void	dissolve_symedge (CDT_state< T > *cdt_state, SymEdge< T > *se)
template<typename T>
void	remove_non_constraint_edges (CDT_state< T > *cdt_state)
template<typename T>
void	remove_non_constraint_edges_leave_valid_bmesh (CDT_state< T > *cdt_state)
template<typename T>
void	remove_outer_edges_until_constraints (CDT_state< T > *cdt_state)
template<typename T>
void	remove_faces_in_holes (CDT_state< T > *cdt_state)
template<typename T>
void	detect_holes (CDT_state< T > *cdt_state)
template<typename T>
void	prepare_cdt_for_output (CDT_state< T > *cdt_state, const CDT_output_type output_type)
template<typename T>
CDT_result< T >	get_cdt_output (CDT_state< T > *cdt_state, const CDT_input< T >, CDT_output_type output_type)
template<typename T>
void	add_input_verts (CDT_state< T > *cdt_state, const CDT_input< T > &input)
template<typename T>
CDT_result< T >	delaunay_calc (const CDT_input< T > &input, CDT_output_type output_type)
template<typename T>
CDT_input< T >	fill_input_from_string (const char *spec)
static int	get_orig_index (const Span< Vector< int > > out_to_orig, int orig_index)
template<typename T>
static double	math_to_double (const T)
template<>
double	math_to_double< double > (const double v)
template<typename T>
static T	math_abs (const T v)
template<>
double	math_abs (const double v)
template<typename T>
int	get_vertex_by_coord (const CDT_result< T > &out, double x, double y)
template<typename T>
int	get_output_edge_index (const CDT_result< T > &out, int out_index_1, int out_index_2)
template<typename T>
bool	output_edge_has_input_id (const CDT_result< T > &out, int out_edge_index, int in_edge_index)
template<typename T>
int	get_output_face_index (const CDT_result< T > &out, const Array< int > &poly)
template<typename T>
int	get_output_tri_index (const CDT_result< T > &out, int out_index_1, int out_index_2, int out_index_3)
template<typename T>
bool	output_face_has_input_id (const CDT_result< T > &out, int out_face_index, int in_face_index)
template<typename T>
std::ostream &	operator<< (std::ostream &os, const CDT_result< T > &r)
template<typename T>
void	graph_draw (const std::string &label, const Span< VecBase< T, 2 > > verts, const Span< std::pair< int, int > > edges, const Span< Vector< int > > faces)
template<typename T>
void	expect_coord_near (const VecBase< T, 2 > &testco, const VecBase< T, 2 > &refco)
template<>
void	expect_coord_near< double > (const double2 &testco, const double2 &refco)
template<typename T>
void	empty_test ()
template<typename T>
void	onept_test ()
template<typename T>
void	twopt_test ()
template<typename T>
void	threept_test ()
template<typename T>
void	mixedpts_test ()
template<typename T>
void	quad0_test ()
template<typename T>
void	quad1_test ()
template<typename T>
void	quad2_test ()
template<typename T>
void	quad3_test ()
template<typename T>
void	quad4_test ()
template<typename T>
void	lineinsquare_test ()
template<typename T>
void	lineholeinsquare_test ()
template<typename T>
void	nestedholes_test ()
template<typename T>
void	crosssegs_test ()
template<typename T>
void	cutacrosstri_test ()
template<typename T>
void	diamondcross_test ()
template<typename T>
void	twodiamondscross_test ()
template<typename T>
void	manycross_test ()
template<typename T>
void	twoface_test ()
template<typename T>
void	twoface2_test ()
template<typename T>
void	overlapfaces_test ()
template<typename T>
void	twosquaresoverlap_test ()
template<typename T>
void	twofaceedgeoverlap_test ()
template<typename T>
void	triintri_test ()
template<typename T>
void	diamondinsquare_test ()
template<typename T>
void	diamondinsquarewire_test ()
template<typename T>
void	repeatedge_test ()
template<typename T>
void	repeattri_test ()
template<typename T>
void	square_o_test ()
	TEST (delaunay_d, Empty)
	TEST (delaunay_d, OnePt)
	TEST (delaunay_d, TwoPt)
	TEST (delaunay_d, ThreePt)
	TEST (delaunay_d, MixedPts)
	TEST (delaunay_d, Quad0)
	TEST (delaunay_d, Quad1)
	TEST (delaunay_d, Quad2)
	TEST (delaunay_d, Quad3)
	TEST (delaunay_d, Quad4)
	TEST (delaunay_d, LineInSquare)
	TEST (delaunay_d, LineHoleInSquare)
	TEST (delaunay_d, NestedHoles)
	TEST (delaunay_d, CrossSegs)
	TEST (delaunay_d, CutAcrossTri)
	TEST (delaunay_d, DiamondCross)
	TEST (delaunay_d, TwoDiamondsCross)
	TEST (delaunay_d, ManyCross)
	TEST (delaunay_d, TwoFace)
	TEST (delaunay_d, TwoFace2)
	TEST (delaunay_d, OverlapFaces)
	TEST (delaunay_d, TwoSquaresOverlap)
	TEST (delaunay_d, TwoFaceEdgeOverlap)
	TEST (delaunay_d, TriInTri)
	TEST (delaunay_d, DiamondInSquare)
	TEST (delaunay_d, DiamondInSquareWire)
	TEST (delaunay_d, RepeatEdge)
	TEST (delaunay_d, RepeatTri)
	TEST (delaunay_d, SquareO)

Variables
static bool	draw_append = false
constexpr bool	DO_DRAW = false

Function Documentation

add_edge_constraint()

template<typename T>

void blender::meshintersect::add_edge_constraint	(	CDT_state< T > *	cdt_state,
		CDTVert< T > *	v1,
		CDTVert< T > *	v2,
		int	input_id,
		LinkNode **	r_edges )

Add a constrained edge between v1 and v2 to cdt structure. This may result in a number of #CDTEdges created, due to intersections and partial overlaps with existing cdt vertices and edges. Each created CDTEdge will have input_id added to its input_ids list.

If r_edges is not null, the #CDTEdges generated or found that go from v1 to v2 are put into that linked list, in order.

Assumes that #blender_constrained_delaunay_get_output has not been called yet.

Definition at line 1871 of file delaunay_2d.cc.

References add_to_input_ids(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_assert, BLI_linklist_append(), blender::meshintersect::CDT_state< T >::cdt, dump_crossings(), blender::meshintersect::SymEdge< T >::edge, blender::meshintersect::CDT_state< T >::epsilon, find_symedge_between_verts(), find_symedge_with_face(), get_next_crossing_from_edge(), get_next_crossing_from_vert(), i, blender::meshintersect::CrossData< T >::in, blender::meshintersect::CDTEdge< T >::input_ids, is_constrained_edge(), blender::meshintersect::CrossData< T >::lambda, LinkNodePair::list, blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CrossData< T >::out, re_delaunay_triangulate(), blender::Vector< T, InlineBufferCapacity, Allocator >::size(), sym(), blender::meshintersect::CDTEdge< T >::symedges, T, v, v2, blender::meshintersect::CrossData< T >::vert, blender::meshintersect::SymEdge< T >::vert, vertname(), blender::meshintersect::CDT_state< T >::visit_count, and blender::meshintersect::CDTVert< T >::visit_index.

Referenced by add_edge_constraints(), and add_face_constraints().

add_edge_constraints()

template<typename T>

void blender::meshintersect::add_edge_constraints	(	CDT_state< T > *	cdt_state,
		const CDT_input< T > &	input )

Incrementally add edge input edge as a constraint. This may cause the graph structure to change, in cases where the constraints intersect existing edges. The code will ensure that CDTEdge's created will have ids that tie them back to the original edge constraint index.

Definition at line 2096 of file delaunay_2d.cc.

References add_edge_constraint(), blender::meshintersect::CDT_state< T >::cdt, blender::meshintersect::CDT_state< T >::face_edge_offset, i, input, blender::meshintersect::CDT_state< T >::need_ids, and v2.

Referenced by delaunay_calc().

add_face_constraints()

template<typename T>

int blender::meshintersect::add_face_constraints	(	CDT_state< T > *	cdt_state,
		const CDT_input< T > &	input,
		CDT_output_type	output_type )

Incrementally each edge of each input face as an edge constraint. The code will ensure that the CDTEdge's created will have ids that tie them back to the original face edge (using a numbering system for those edges that starts with cdt->face_edge_offset, and continues with the edges in order around each face in turn. And then the next face starts at cdt->face_edge_offset beyond the start for the previous face. Return the number of faces added, which may be less than input.face.size() in the case that some faces have less than 3 sides.

Definition at line 2188 of file delaunay_2d.cc.

References add_edge_constraint(), add_face_ids(), BLI_assert, BLI_linklist_free(), blender::meshintersect::CDT_state< T >::cdt, CDT_CONSTRAINTS_VALID_BMESH, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, ELEM, blender::meshintersect::CDT_state< T >::face_edge_offset, blender::meshintersect::CDTArrangement< T >::get_vert_resolve_merge(), i, blender::Span< T >::index_range(), input, LinkNode::link, blender::meshintersect::CDT_state< T >::need_ids, power_of_10_greater_equal_to(), blender::Span< T >::size(), size(), blender::meshintersect::CDTEdge< T >::symedges, and v2.

Referenced by delaunay_calc().

add_face_ids()

template<typename T>

void blender::meshintersect::add_face_ids	(	CDT_state< T > *	cdt_state,
		SymEdge< T > *	face_symedge,
		int	face_id,
		int	fedge_start,
		int	fedge_end )

Add face_id to the input_ids lists of all CDTFace's on the interior of the input face with that id. face_symedge is on edge of the boundary of the input face, with assumption that interior is on the left of that SymEdge.

The algorithm is: starting from the CDTFace for face_symedge, add the face_id and then process all adjacent faces where the adjacency isn't across an edge that was a constraint added for the boundary of the input face. fedge_start..fedge_end is the inclusive range of edge input ids that are for the given face.

NOTE: if the input face is not CCW oriented, we'll be labeling the outside, not the inside. Note 2: if the boundary has self-crossings, this method will arbitrarily pick one of the contiguous set of faces enclosed by parts of the boundary, leaving the other such un-tagged. This may be a feature instead of a bug if the first contiguous section is most of the face and the others are tiny self-crossing triangles at some parts of the boundary. On the other hand, if decide we want to handle these in full generality, then will need a more complicated algorithm (using "inside" tests and a parity rule) to decide on the interior.

Definition at line 2134 of file delaunay_2d.cc.

References add_to_input_ids(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::meshintersect::SymEdge< T >::edge, blender::meshintersect::SymEdge< T >::face, id_range_in_list(), blender::meshintersect::CDTFace< T >::input_ids, blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), blender::meshintersect::SymEdge< T >::next, blender::Vector< T, InlineBufferCapacity, Allocator >::pop_last(), sym(), blender::meshintersect::CDT_state< T >::visit_count, and blender::meshintersect::CDTFace< T >::visit_index.

Referenced by add_face_constraints().

add_input_verts()

template<typename T>

void blender::meshintersect::add_input_verts	(	CDT_state< T > *	cdt_state,
		const CDT_input< T > &	input )

Add all the input verts into cdt. This will deduplicate, setting vertices merge_to_index to show merges.

Definition at line 2753 of file delaunay_2d.cc.

References add_input_verts(), blender::meshintersect::CDT_state< T >::cdt, i, input, and blender::meshintersect::CDT_state< T >::input_vert_num.

Referenced by add_input_verts(), and delaunay_calc().

add_list_to_input_ids()

void blender::meshintersect::add_list_to_input_ids ( blender::Set< int > & dst, const blender::Set< int > & src )

static

Definition at line 883 of file delaunay_2d.cc.

References blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add().

Referenced by blender::meshintersect::CDTArrangement< T >::add_diagonal(), and blender::meshintersect::CDTArrangement< T >::split_edge().

add_to_input_ids()

void blender::meshintersect::add_to_input_ids ( blender::Set< int > & dst, int input_id )

static

Definition at line 878 of file delaunay_2d.cc.

References blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add().

Referenced by add_edge_constraint(), add_face_ids(), and get_cdt_output().

cdt_draw()

template<typename T>

void blender::meshintersect::cdt_draw	(	const std::string &	label,
		const CDTArrangement< T > &	cdt )

Definition at line 468 of file delaunay_2d.cc.

References blender::meshintersect::CDTVert< T >::co, blender::meshintersect::CDTFace< T >::deleted, e, blender::meshintersect::CDTArrangement< T >::edges, blender::meshintersect::SymEdge< T >::face, blender::meshintersect::CDTArrangement< T >::faces, i, blender::meshintersect::CDTFace< T >::input_ids, blender::math::min_max(), blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, blender::math::scale(), sename(), Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::size(), SX, SY, trunc_ptr(), v, blender::meshintersect::SymEdge< T >::vert, vertname(), and blender::meshintersect::CDTArrangement< T >::verts.

Referenced by dc_tri().

crosssegs_test()

template<typename T>

void blender::meshintersect::crosssegs_test

(

)

Definition at line 678 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, DO_DRAW, in, and out.

cutacrosstri_test()

template<typename T>

void blender::meshintersect::cutacrosstri_test

(

)

Definition at line 710 of file BLI_delaunay_2d_test.cc.

dc_tri()

template<typename T>

void blender::meshintersect::dc_tri	(	CDTArrangement< T > *	cdt,
		Array< SiteInfo< T > > &	sites,
		int	start,
		int	end,
		SymEdge< T > **	r_le,
		SymEdge< T > **	r_re )

Delaunay triangulate sites[start} to sites[end-1]. Assume sites are lexicographically sorted by coordinate. Return SymEdge of CCW convex hull at left-most point in *r_le and that of right-most point of cw convex null in *r_re.

Definition at line 1224 of file delaunay_2d.cc.

References blender::meshintersect::CDTArrangement< T >::add_diagonal(), blender::meshintersect::CDTArrangement< T >::add_edge(), blender::meshintersect::CDTArrangement< T >::add_vert_to_symedge_edge(), BLI_assert, cdt_draw(), blender::meshintersect::CDTVert< T >::co, blender::meshintersect::CDTArrangement< T >::connect_separate_parts(), dc_tri(), dc_tri_valid(), blender::meshintersect::CDTArrangement< T >::delete_edge(), blender::meshintersect::SymEdge< T >::face, filtered_incircle(), filtered_orient2d(), blender::meshintersect::SymEdge< T >::next, next, blender::meshintersect::CDTArrangement< T >::outer_face, blender::meshintersect::SymEdge< T >::rot, sym(), blender::meshintersect::CDTEdge< T >::symedges, v2, blender::meshintersect::SymEdge< T >::vert, vert_left_of_symedge(), and vert_right_of_symedge().

Referenced by dc_tri(), and dc_triangulate().

dc_tri_valid()

template<typename T>

bool blender::meshintersect::dc_tri_valid ( SymEdge< T > * se, SymEdge< T > * basel, SymEdge< T > * basel_sym )

inline

Definition at line 1212 of file delaunay_2d.cc.

References filtered_orient2d(), blender::meshintersect::SymEdge< T >::next, and blender::meshintersect::SymEdge< T >::vert.

Referenced by dc_tri().

dc_triangulate()

template<typename T>

void blender::meshintersect::dc_triangulate	(	CDTArrangement< T > *	cdt,
		Array< SiteInfo< T > > &	sites )

Definition at line 1427 of file delaunay_2d.cc.

References dc_tri(), i, and v.

Referenced by initial_triangulation().

delaunay_2d_calc()

blender::meshintersect::CDT_result< double > blender::meshintersect::delaunay_2d_calc	(	const CDT_input< double > &	input,
		CDT_output_type	output_type )

Definition at line 2778 of file delaunay_2d.cc.

References delaunay_2d_calc(), delaunay_calc(), and input.

Referenced by delaunay_2d_calc(), empty_test(), blender::io::obj::fixup_invalid_face(), M_Geometry_delaunay_2d_cdt(), and onept_test().

delaunay_calc()

template<typename T>

CDT_result< T > blender::meshintersect::delaunay_calc	(	const CDT_input< T > &	input,
		CDT_output_type	output_type )

Definition at line 2761 of file delaunay_2d.cc.

References add_edge_constraints(), add_face_constraints(), add_input_verts(), blender::meshintersect::CDT_state< T >::cdt, CDT_CONSTRAINTS, CDT_FULL, CDT_INSIDE, delaunay_calc(), ELEM, get_cdt_output(), initial_triangulation(), and input.

Referenced by delaunay_2d_calc(), and delaunay_calc().

detect_holes()

template<typename T>

void blender::meshintersect::detect_holes

(

CDT_state< T > *

cdt_state

)

Set the hole member of each CDTFace to true for each face that is detected to be part of a hole. A hole face is define as one for which, when a ray is shot from a point inside the face to infinity, it crosses an even number of constraint edges. We'll choose a ray direction that is extremely unlikely to exactly superimpose some edge, so avoiding the need to be careful about such overlaps.

To improve performance, we gather together faces that should have the same winding number, and only shoot rays once.

Definition at line 2482 of file delaunay_2d.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::meshintersect::CDT_state< T >::cdt, blender::meshintersect::CDTFace< T >::deleted, blender::meshintersect::SymEdge< T >::edge, blender::meshintersect::CDTArrangement< T >::edges, blender::meshintersect::FatCo< T >::exact, blender::meshintersect::CDTArrangement< T >::faces, i, blender::Vector< T, InlineBufferCapacity, Allocator >::index_range(), is_constrained_edge(), blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, blender::threading::parallel_for(), blender::Vector< T, InlineBufferCapacity, Allocator >::pop_last(), sym(), blender::meshintersect::CDTFace< T >::symedge, blender::meshintersect::CDT_state< T >::visit_count, and blender::meshintersect::CDTFace< T >::visit_index.

Referenced by prepare_cdt_for_output().

diamondcross_test()

template<typename T>

void blender::meshintersect::diamondcross_test

(

)

Definition at line 751 of file BLI_delaunay_2d_test.cc.

References CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, DO_DRAW, and in.

diamondinsquare_test()

template<typename T>

void blender::meshintersect::diamondinsquare_test

(

)

Definition at line 1081 of file BLI_delaunay_2d_test.cc.

References out.

diamondinsquarewire_test()

template<typename T>

void blender::meshintersect::diamondinsquarewire_test

(

)

Definition at line 1095 of file BLI_delaunay_2d_test.cc.

References out.

dissolve_symedge()

template<typename T>

void blender::meshintersect::dissolve_symedge	(	CDT_state< T > *	cdt_state,
		SymEdge< T > *	se )

Definition at line 2265 of file delaunay_2d.cc.

References blender::meshintersect::CDT_state< T >::cdt, blender::meshintersect::CDTArrangement< T >::delete_edge(), ELEM, blender::meshintersect::SymEdge< T >::face, blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, and sym().

Referenced by remove_non_constraint_edges(), remove_non_constraint_edges_leave_valid_bmesh(), and remove_outer_edges_until_constraints().

dump_crossings()

template<typename T>

void blender::meshintersect::dump_crossings

(

const Span< CrossData< T > >

crossings

)

Definition at line 1839 of file delaunay_2d.cc.

References i, blender::meshintersect::CrossData< T >::in, blender::meshintersect::CrossData< T >::lambda, blender::meshintersect::CrossData< T >::out, short_se_dump(), and blender::meshintersect::CrossData< T >::vert.

Referenced by add_edge_constraint().

empty_test()

template<typename T>

void blender::meshintersect::empty_test

(

)

Definition at line 406 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, delaunay_2d_calc(), EXPECT_EQ(), in, and out.

exists_edge()

template<typename T>

bool blender::meshintersect::exists_edge ( const CDTVert< T > * v1, const CDTVert< T > * v2 )

inline

Is there already an edge between a and b?

Definition at line 944 of file delaunay_2d.cc.

References find_symedge_between_verts(), and v2.

Referenced by re_delaunay_triangulate().

expect_coord_near()

template<typename T>

void blender::meshintersect::expect_coord_near	(	const VecBase< T, 2 > &	testco,
		const VecBase< T, 2 > &	refco )

Referenced by onept_test().

expect_coord_near< double >()

template<>

void blender::meshintersect::expect_coord_near< double >	(	const double2 &	testco,
		const double2 &	refco )

Definition at line 398 of file BLI_delaunay_2d_test.cc.

References e.

fill_crossdata_for_intersect()

template<typename T>

void blender::meshintersect::fill_crossdata_for_intersect	(	const FatCo< T > &	curco,
		const CDTVert< T > *	v2,
		SymEdge< T > *	t,
		CrossData< T > *	cd,
		CrossData< T > *	cd_next,
		const T	epsilon )

As part of finding crossings, we found a case where orient tests say that the next crossing is on the SymEdge t, while intersecting with the ray from curco to v2. Find the intersection point and fill in the CrossData for that point. It may turn out that when doing the intersection, we get an answer that says that this case is better handled as through-vertex case instead, so we may do that. In the latter case, we want to avoid a situation where the current crossing is on an edge and the next will be an endpoint of the same edge. When that happens, we "rewrite history" and turn the current crossing into a vert one, and then extend from there.

We cannot fill cd_next's 'out' edge yet, in the case that the next one ends up being a vert case. We need to fill in cd's 'out' edge if it was a vert case.

Definition at line 1665 of file delaunay_2d.cc.

References BLI_assert, blender::meshintersect::CDTVert< T >::co, blender::math::distance(), blender::math::distance_squared(), blender::meshintersect::FatCo< T >::exact, fill_crossdata_for_through_vert(), blender::math::isect_seg_seg(), blender::meshintersect::CrossData< T >::lambda, blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CrossData< T >::out, sym(), T, UNUSED_VARS_NDEBUG, v2, and blender::meshintersect::SymEdge< T >::vert.

Referenced by get_next_crossing_from_edge(), and get_next_crossing_from_vert().

fill_crossdata_for_through_vert()

template<typename T>

void blender::meshintersect::fill_crossdata_for_through_vert	(	CDTVert< T > *	v,
		SymEdge< T > *	cd_out,
		CrossData< T > *	cd,
		CrossData< T > *	cd_next )

As part of finding crossings, we found a case where the next crossing goes through vert v. If it came from a previous vert in cd, then cd_out is the edge that leads from that to v. Else cd_out can be null, because it won't be used. Set *cd_next to indicate this. We can set 'in' but not 'out'. We can set the 'out' of the current cd.

Definition at line 1623 of file delaunay_2d.cc.

References BLI_assert, blender::meshintersect::CrossData< T >::in, blender::meshintersect::CrossData< T >::lambda, blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CrossData< T >::out, sym(), T, v, blender::meshintersect::CrossData< T >::vert, and blender::meshintersect::SymEdge< T >::vert.

Referenced by fill_crossdata_for_intersect(), and get_next_crossing_from_vert().

fill_input_from_string()

template<typename T>

CDT_input< T > blender::meshintersect::fill_input_from_string

(

const char *

spec

)

Definition at line 37 of file BLI_delaunay_2d_test.cc.

References blender::meshintersect::CDT_input< T >::edge, blender::meshintersect::CDT_input< T >::epsilon, blender::meshintersect::CDT_input< T >::face, faces, i, T, v, blender::meshintersect::CDT_input< T >::vert, and verts.

Referenced by onept_test(), and twosquaresoverlap_test().

filtered_incircle()

template<typename T>

int blender::meshintersect::filtered_incircle ( const FatCo< T > & a, const FatCo< T > & b, const FatCo< T > & c, const FatCo< T > & d )

static

A filtered version of incircle.

References b.

Referenced by dc_tri(), and re_delaunay_triangulate().

filtered_incircle< double >()

template<>

int blender::meshintersect::filtered_incircle< double >	(	const FatCo< double > &	a,
		const FatCo< double > &	b,
		const FatCo< double > &	c,
		const FatCo< double > &	d )

Definition at line 720 of file delaunay_2d.cc.

References blender::meshintersect::FatCo< T >::approx, b, and blender::incircle().

filtered_orient2d()

template<typename T>

int blender::meshintersect::filtered_orient2d ( const FatCo< T > & a, const FatCo< T > & b, const FatCo< T > & c )

static

A filtered version of orient2d, which will usually be much faster when using exact arithmetic. See EXACT GEOMETRIC COMPUTATION USING CASCADING, by Burnikel, Funke, and Seel.

References b.

Referenced by dc_tri(), dc_tri_valid(), get_next_crossing_from_edge(), get_next_crossing_from_vert(), tri_orient(), vert_left_of_symedge(), and vert_right_of_symedge().

filtered_orient2d< double >()

template<>

int blender::meshintersect::filtered_orient2d< double >	(	const FatCo< double > &	a,
		const FatCo< double > &	b,
		const FatCo< double > &	c )

Definition at line 653 of file delaunay_2d.cc.

References blender::meshintersect::FatCo< T >::approx, b, and blender::orient2d().

find_site_merges()

template<typename T>

void blender::meshintersect::find_site_merges

(

Array< SiteInfo< T > > &

sites

)

Find series of equal vertices in the sorted sites array and use the vertices merge_to_index to indicate that all vertices after the first merge to the first.

Definition at line 1185 of file delaunay_2d.cc.

References i, and v.

Referenced by initial_triangulation().

find_symedge_between_verts()

template<typename T>

SymEdge< T > * blender::meshintersect::find_symedge_between_verts	(	const CDTVert< T > *	v1,
		const CDTVert< T > *	v2 )

Return the SymEdge that goes from v1 to v2, if it exists, else return nullptr.

Definition at line 914 of file delaunay_2d.cc.

References blender::meshintersect::SymEdge< T >::next, blender::meshintersect::SymEdge< T >::rot, blender::meshintersect::CDTVert< T >::symedge, and v2.

Referenced by add_edge_constraint(), and exists_edge().

find_symedge_with_face()

template<typename T>

SymEdge< T > * blender::meshintersect::find_symedge_with_face	(	const CDTVert< T > *	v,
		const CDTFace< T > *	f )

Return the SymEdge attached to v that has face f, if it exists, else return nullptr.

Definition at line 929 of file delaunay_2d.cc.

References blender::meshintersect::SymEdge< T >::face, blender::meshintersect::SymEdge< T >::rot, and v.

Referenced by add_edge_constraint().

get_cdt_output()

template<typename T>

CDT_result< T > blender::meshintersect::get_cdt_output	(	CDT_state< T > *	cdt_state,
		const CDT_input< T >	,
		CDT_output_type	output_type )

Definition at line 2633 of file delaunay_2d.cc.

References add_to_input_ids(), BLI_assert, blender::meshintersect::CDT_state< T >::cdt, blender::meshintersect::CDTFace< T >::deleted, e, blender::meshintersect::CDTArrangement< T >::edges, blender::meshintersect::CDT_state< T >::face_edge_offset, blender::meshintersect::CDTArrangement< T >::faces, get_cdt_output(), i, blender::meshintersect::CDTFace< T >::input_ids, is_deleted_edge(), blender::meshintersect::CDT_state< T >::need_ids, blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, prepare_cdt_for_output(), result, blender::meshintersect::CDTFace< T >::symedge, v, blender::meshintersect::SymEdge< T >::vert, and blender::meshintersect::CDTArrangement< T >::verts.

Referenced by delaunay_calc(), and get_cdt_output().

get_next_crossing_from_edge()

template<typename T>

void blender::meshintersect::get_next_crossing_from_edge	(	CrossData< T > *	cd,
		CrossData< T > *	cd_next,
		const CDTVert< T > *	v2,
		const T	epsilon )

As part of finding the crossings of a ray to v2, find the next crossing after 'cd', assuming 'cd' represents a crossing that goes through a an edge, not at either end of that edge.

We have the triangle vb-va-vc, where va and vb are the split edge and vc is the third vertex on that new side of the edge (should be closer to v2). The next crossing should be through vc or intersecting vb-vc or va-vc.

Definition at line 1816 of file delaunay_2d.cc.

References blender::meshintersect::CDTVert< T >::co, fill_crossdata_for_intersect(), filtered_orient2d(), blender::meshintersect::CrossData< T >::in, blender::math::interpolate(), blender::meshintersect::CrossData< T >::lambda, blender::meshintersect::SymEdge< T >::next, sym(), T, and v2.

Referenced by add_edge_constraint().

get_next_crossing_from_vert()

template<typename T>

bool blender::meshintersect::get_next_crossing_from_vert	(	CDT_state< T > *	cdt_state,
		CrossData< T > *	cd,
		CrossData< T > *	cd_next,
		const CDTVert< T > *	v2 )

As part of finding the crossings of a ray to v2, find the next crossing after 'cd', assuming 'cd' represents a crossing that goes through a vertex.

We do a rotational scan around cd's vertex, looking for the triangle where the ray from cd->vert to v2 goes between the two arms from cd->vert, or where it goes along one of the edges.

Definition at line 1765 of file delaunay_2d.cc.

References BLI_assert, blender::meshintersect::CDT_state< T >::cdt, blender::meshintersect::CDTVert< T >::co, blender::meshintersect::CDT_state< T >::epsilon, blender::meshintersect::SymEdge< T >::face, fill_crossdata_for_intersect(), fill_crossdata_for_through_vert(), filtered_orient2d(), in_line(), blender::meshintersect::SymEdge< T >::next, blender::meshintersect::SymEdge< T >::rot, tri_orient(), v2, blender::meshintersect::CrossData< T >::vert, and blender::meshintersect::SymEdge< T >::vert.

Referenced by add_edge_constraint().

get_orig_index()

int blender::meshintersect::get_orig_index ( const Span< Vector< int > > out_to_orig, int orig_index )

static

Definition at line 98 of file BLI_delaunay_2d_test.cc.

References i.

Referenced by TEST().

get_output_edge_index()

template<typename T>

int blender::meshintersect::get_output_edge_index	(	const CDT_result< T > &	out,
		int	out_index_1,
		int	out_index_2 )

Definition at line 161 of file BLI_delaunay_2d_test.cc.

References i, and out.

get_output_face_index()

template<typename T>

int blender::meshintersect::get_output_face_index	(	const CDT_result< T > &	out,
		const Array< int > &	poly )

Definition at line 184 of file BLI_delaunay_2d_test.cc.

References out, and blender::Array< T, InlineBufferCapacity, Allocator >::size().

Referenced by get_output_tri_index().

get_output_tri_index()

template<typename T>

int blender::meshintersect::get_output_tri_index	(	const CDT_result< T > &	out,
		int	out_index_1,
		int	out_index_2,
		int	out_index_3 )

Definition at line 208 of file BLI_delaunay_2d_test.cc.

References get_output_face_index(), and out.

get_vertex_by_coord()

template<typename T>

int blender::meshintersect::get_vertex_by_coord	(	const CDT_result< T > &	out,
		double	x,
		double	y )

Definition at line 146 of file BLI_delaunay_2d_test.cc.

References e, fabs(), i, math_to_double(), out, x, and y.

graph_draw()

template<typename T>

void blender::meshintersect::graph_draw	(	const std::string &	label,
		const Span< VecBase< T, 2 > >	verts,
		const Span< std::pair< int, int > >	edges,
		const Span< Vector< int > >	faces )

Definition at line 266 of file BLI_delaunay_2d_test.cc.

References draw_append, e, faces, i, math_to_double(), blender::math::scale(), SX, SY, v, and verts.

Referenced by TEST(), TEST(), and threept_test().

id_range_in_list()

bool blender::meshintersect::id_range_in_list ( const blender::Set< int > & id_list, int range_start, int range_end )

static

Definition at line 868 of file delaunay_2d.cc.

Referenced by add_face_ids().

in_line()

template<typename T>

bool blender::meshintersect::in_line ( const FatCo< T > & a, const FatCo< T > & b, const FatCo< T > & c )

static

Return true if a -- b -- c are in that order, assuming they are on a straight line according to orient2d and we know the order is either abc or bac. This means ab . ac and bc . ac must both be non-negative. Use filtering to speed this up when using exact arithmetic.

References b.

Referenced by get_next_crossing_from_vert().

in_line< double >()

template<>

bool blender::meshintersect::in_line< double >	(	const FatCo< double > &	a,
		const FatCo< double > &	b,
		const FatCo< double > &	c )

Definition at line 772 of file delaunay_2d.cc.

References blender::meshintersect::FatCo< T >::approx, b, and blender::math::dot().

initial_triangulation()

template<typename T>

void blender::meshintersect::initial_triangulation

(

CDTArrangement< T > *

cdt

)

Do a Delaunay Triangulation of the points in cdt.verts. This is only a first step in the Constrained Delaunay triangulation, because it doesn't yet deal with the segment constraints. The algorithm used is the Divide & Conquer algorithm from the Guibas-Stolfi "Primitives for the Manipulation of General Subdivision and the Computation of Voronoi Diagrams" paper. The data structure here is similar to but not exactly the same as the quad-edge structure described in that paper. If T is not exact arithmetic, incircle and CCW tests are done using Shewchuk's exact primitives, so that this routine is robust.

As a preprocessing step, we want to merge all vertices that the same. This is accomplished by lexicographically sorting the coordinates first (which is needed anyway for the D&C algorithm). The CDTVerts with merge_to_index not equal to -1 are after this regarded as having been merged into the vertex with the corresponding index.

Definition at line 1467 of file delaunay_2d.cc.

References blender::Array< T, InlineBufferCapacity, Allocator >::begin(), dc_triangulate(), blender::Array< T, InlineBufferCapacity, Allocator >::end(), find_site_merges(), i, site_lexicographic_sort(), and blender::meshintersect::CDTArrangement< T >::verts.

Referenced by delaunay_calc().

is_border_edge()

template<typename T>

bool blender::meshintersect::is_border_edge ( const CDTEdge< T > * e, const CDT_state< T > * cdt )

inline

Definition at line 890 of file delaunay_2d.cc.

References e.

is_constrained_edge()

template<typename T>

bool blender::meshintersect::is_constrained_edge ( const CDTEdge< T > * e )

inline

Definition at line 895 of file delaunay_2d.cc.

References e.

Referenced by add_edge_constraint(), detect_holes(), remove_faces_in_holes(), remove_non_constraint_edges(), remove_non_constraint_edges_leave_valid_bmesh(), and remove_outer_edges_until_constraints().

is_deleted_edge()

template<typename T>

bool blender::meshintersect::is_deleted_edge ( const CDTEdge< T > * e )

inline

Definition at line 900 of file delaunay_2d.cc.

References e.

Referenced by get_cdt_output(), prepare_cdt_for_output(), remove_non_constraint_edges(), and remove_non_constraint_edges_leave_valid_bmesh().

is_original_vert()

template<typename T>

bool blender::meshintersect::is_original_vert ( const CDTVert< T > * v, CDT_state< T > * cdt )

inline

Definition at line 905 of file delaunay_2d.cc.

References blender::meshintersect::CDT_state< T >::input_vert_num, and v.

lineholeinsquare_test()

template<typename T>

void blender::meshintersect::lineholeinsquare_test

(

)

Definition at line 616 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, DO_DRAW, in, and out.

lineinsquare_test()

template<typename T>

void blender::meshintersect::lineinsquare_test

(

)

Definition at line 585 of file BLI_delaunay_2d_test.cc.

manycross_test()

template<typename T>

void blender::meshintersect::manycross_test

(

)

Definition at line 805 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, in, and out.

math_abs() [1/3]

template<>

double blender::meshintersect::math_abs

(

const double

v

)

Definition at line 138 of file BLI_delaunay_2d_test.cc.

References fabs(), and v.

math_abs() [2/3]

template<typename T>

T blender::meshintersect::math_abs

(

const T

v

)

Definition at line 32 of file delaunay_2d.cc.

References T, and v.

math_abs() [3/3]

template<typename T>

T blender::meshintersect::math_abs ( const T v )

static

Definition at line 32 of file delaunay_2d.cc.

References T, and v.

math_abs< double >()

template<>

double blender::meshintersect::math_abs< double >

(

const double

v

)

Definition at line 44 of file delaunay_2d.cc.

References fabs(), and v.

math_to_double() [1/2]

template<typename T>

double blender::meshintersect::math_to_double

(

const T

)

Definition at line 49 of file delaunay_2d.cc.

References BLI_assert, and T.

Referenced by get_vertex_by_coord(), and graph_draw().

math_to_double() [2/2]

template<typename T>

double blender::meshintersect::math_to_double ( const T )

static

Definition at line 111 of file BLI_delaunay_2d_test.cc.

References BLI_assert, and T.

math_to_double< double >() [1/2]

template<>

double blender::meshintersect::math_to_double< double >

(

const double

v

)

Definition at line 62 of file delaunay_2d.cc.

References v.

math_to_double< double >() [2/2]

template<>

double blender::meshintersect::math_to_double< double >

(

const double

v

)

Definition at line 117 of file BLI_delaunay_2d_test.cc.

References v.

mixedpts_test()

template<typename T>

void blender::meshintersect::mixedpts_test

(

)

Definition at line 484 of file BLI_delaunay_2d_test.cc.

References DO_DRAW, and out.

nestedholes_test()

template<typename T>

void blender::meshintersect::nestedholes_test

(

)

Definition at line 647 of file BLI_delaunay_2d_test.cc.

References CDT_CONSTRAINTS, DO_DRAW, and in.

onept_test()

template<typename T>

void blender::meshintersect::onept_test

(

)

Definition at line 419 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, delaunay_2d_calc(), expect_coord_near(), EXPECT_EQ(), fill_input_from_string(), in, and out.

operator<<() [1/5]

template<typename T>

std::ostream & blender::meshintersect::operator<<	(	std::ostream &	os,
		const CDT_result< T > &	r )

Definition at line 225 of file BLI_delaunay_2d_test.cc.

References blender::meshintersect::CDT_result< T >::edge, blender::meshintersect::CDT_result< T >::edge_orig, blender::meshintersect::CDT_result< T >::face, blender::meshintersect::CDT_result< T >::face_orig, Array< T, InlineBufferCapacity, Allocator >::first(), i, Array< T, InlineBufferCapacity, Allocator >::index_range(), Array< T, InlineBufferCapacity, Allocator >::size(), blender::meshintersect::CDT_result< T >::vert, and blender::meshintersect::CDT_result< T >::vert_orig.

operator<<() [2/5]

template<typename T>

std::ostream & blender::meshintersect::operator<<	(	std::ostream &	os,
		const CDT_state< T > &	cdt_state )

Definition at line 406 of file delaunay_2d.cc.

References blender::meshintersect::CDT_state< T >::cdt, count, blender::meshintersect::CDTFace< T >::deleted, e, blender::meshintersect::SymEdge< T >::edge, blender::meshintersect::SymEdge< T >::face, i, blender::meshintersect::SymEdge< T >::next, blender::meshintersect::SymEdge< T >::rot, sym(), blender::meshintersect::CDTFace< T >::symedge, trunc_ptr(), v, blender::meshintersect::SymEdge< T >::vert, and vertname().

operator<<() [3/5]

template<typename T>

std::ostream & blender::meshintersect::operator<<	(	std::ostream &	os,
		const SymEdge< T > &	se )

Definition at line 379 of file delaunay_2d.cc.

References blender::meshintersect::SymEdge< T >::next, blender::meshintersect::SymEdge< T >::vert, and vertname().

operator<<() [4/5]

template<typename T>

std::ostream & blender::meshintersect::operator<<	(	std::ostream &	os,
		const SymEdge< T > *	se )

Definition at line 391 of file delaunay_2d.cc.

operator<<() [5/5]

template<typename T>

std::ostream & blender::meshintersect::operator<<	(	std::ostream &	stream,
		const FatCo< T > &	co )

Definition at line 173 of file delaunay_2d.cc.

References blender::meshintersect::FatCo< T >::approx.

output_edge_has_input_id()

template<typename T>

bool blender::meshintersect::output_edge_has_input_id	(	const CDT_result< T > &	out,
		int	out_edge_index,
		int	in_edge_index )

Definition at line 175 of file BLI_delaunay_2d_test.cc.

References out.

output_face_has_input_id()

template<typename T>

bool blender::meshintersect::output_face_has_input_id	(	const CDT_result< T > &	out,
		int	out_face_index,
		int	in_face_index )

Definition at line 218 of file BLI_delaunay_2d_test.cc.

References out.

overlapfaces_test()

template<typename T>

void blender::meshintersect::overlapfaces_test

(

)

Definition at line 923 of file BLI_delaunay_2d_test.cc.

References out.

power_of_10_greater_equal_to()

int blender::meshintersect::power_of_10_greater_equal_to ( int x )

static

Definition at line 2164 of file delaunay_2d.cc.

References BLI_assert, and x.

Referenced by add_face_constraints().

prepare_cdt_for_output()

template<typename T>

void blender::meshintersect::prepare_cdt_for_output	(	CDT_state< T > *	cdt_state,
		const CDT_output_type	output_type )

Remove edges and merge faces to get desired output, as per options.

Note

the cdt cannot be further changed after this.

Definition at line 2586 of file delaunay_2d.cc.

References blender::meshintersect::CDT_state< T >::cdt, CDT_CONSTRAINTS, CDT_CONSTRAINTS_VALID_BMESH, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, CDT_INSIDE, CDT_INSIDE_WITH_HOLES, detect_holes(), e, blender::meshintersect::CDTArrangement< T >::edges, is_deleted_edge(), prepare_cdt_for_output(), remove_faces_in_holes(), remove_non_constraint_edges(), remove_non_constraint_edges_leave_valid_bmesh(), and remove_outer_edges_until_constraints().

Referenced by get_cdt_output(), and prepare_cdt_for_output().

prev()

template<typename T>

SymEdge< T > * blender::meshintersect::prev ( const SymEdge< T > * se )

inline

Return SymEdge whose next is se.

Definition at line 106 of file delaunay_2d.cc.

References blender::meshintersect::SymEdge< T >::rot.

Referenced by blender::meshintersect::CDTArrangement< T >::add_diagonal(), blender::meshintersect::CDTArrangement< T >::delete_edge(), and blender::meshintersect::CDTArrangement< T >::split_edge().

quad0_test()

template<typename T>

void blender::meshintersect::quad0_test

(

)

Definition at line 510 of file BLI_delaunay_2d_test.cc.

References DO_DRAW, and out.

quad1_test()

template<typename T>

void blender::meshintersect::quad1_test

(

)

Definition at line 525 of file BLI_delaunay_2d_test.cc.

quad2_test()

template<typename T>

void blender::meshintersect::quad2_test

(

)

Definition at line 540 of file BLI_delaunay_2d_test.cc.

References DO_DRAW, and out.

quad3_test()

template<typename T>

void blender::meshintersect::quad3_test

(

)

Definition at line 555 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, DO_DRAW, in, and out.

quad4_test()

template<typename T>

void blender::meshintersect::quad4_test

(

)

Definition at line 570 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, DO_DRAW, in, and out.

re_delaunay_triangulate()

template<typename T>

void blender::meshintersect::re_delaunay_triangulate ( CDTArrangement< T > * cdt, SymEdge< T > * se )

static

Re-triangulates, assuring constrained delaunay condition, the pseudo-polygon that cycles from se. "pseudo" because a vertex may be repeated. See Anglada paper, "An Improved incremental algorithm for constructing restricted Delaunay triangulations".

Definition at line 1490 of file delaunay_2d.cc.

References blender::meshintersect::CDTArrangement< T >::add_diagonal(), b, blender::meshintersect::CDTVert< T >::co, count, exists_edge(), blender::meshintersect::SymEdge< T >::face, filtered_incircle(), blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, re_delaunay_triangulate(), sym(), blender::meshintersect::CDTEdge< T >::symedges, v, and blender::meshintersect::SymEdge< T >::vert.

Referenced by add_edge_constraint(), and re_delaunay_triangulate().

remove_faces_in_holes()

template<typename T>

void blender::meshintersect::remove_faces_in_holes

(

CDT_state< T > *

cdt_state

)

Definition at line 2448 of file delaunay_2d.cc.

References BLI_assert, blender::meshintersect::CDT_state< T >::cdt, blender::meshintersect::CDTFace< T >::deleted, blender::meshintersect::SymEdge< T >::edge, blender::meshintersect::CDTArrangement< T >::faces, blender::meshintersect::CDTFace< T >::hole, i, is_constrained_edge(), blender::meshintersect::SymEdge< T >::next, and blender::meshintersect::CDTFace< T >::symedge.

Referenced by prepare_cdt_for_output().

remove_non_constraint_edges()

template<typename T>

void blender::meshintersect::remove_non_constraint_edges

(

CDT_state< T > *

cdt_state

)

Remove all non-constraint edges.

Definition at line 2296 of file delaunay_2d.cc.

References blender::meshintersect::CDT_state< T >::cdt, dissolve_symedge(), e, is_constrained_edge(), and is_deleted_edge().

Referenced by prepare_cdt_for_output().

remove_non_constraint_edges_leave_valid_bmesh()

template<typename T>

void blender::meshintersect::remove_non_constraint_edges_leave_valid_bmesh

(

CDT_state< T > *

cdt_state

)

Definition at line 2347 of file delaunay_2d.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), b, blender::Vector< T, InlineBufferCapacity, Allocator >::begin(), blender::meshintersect::CDT_state< T >::cdt, dissolve_symedge(), blender::math::distance_squared(), e, blender::meshintersect::CDTArrangement< T >::edges, blender::Vector< T, InlineBufferCapacity, Allocator >::end(), blender::meshintersect::SymEdge< T >::face, i, blender::meshintersect::CDTFace< T >::input_ids, is_constrained_edge(), is_deleted_edge(), blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, blender::Vector< T, InlineBufferCapacity, Allocator >::reserve(), Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::size(), sym(), and vert_touches_face().

Referenced by prepare_cdt_for_output().

remove_outer_edges_until_constraints()

template<typename T>

void blender::meshintersect::remove_outer_edges_until_constraints

(

CDT_state< T > *

cdt_state

)

Definition at line 2398 of file delaunay_2d.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_assert, BLI_linklist_pop(), BLI_linklist_prepend(), blender::meshintersect::CDT_state< T >::cdt, dissolve_symedge(), blender::meshintersect::SymEdge< T >::edge, is_constrained_edge(), blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), blender::meshintersect::SymEdge< T >::next, blender::Vector< T, InlineBufferCapacity, Allocator >::pop_last(), sym(), blender::meshintersect::CDTFace< T >::symedge, blender::meshintersect::CDT_state< T >::visit_count, and blender::meshintersect::CDTFace< T >::visit_index.

Referenced by prepare_cdt_for_output().

repeatedge_test()

template<typename T>

void blender::meshintersect::repeatedge_test

(

)

Definition at line 1109 of file BLI_delaunay_2d_test.cc.

References out.

repeattri_test()

template<typename T>

void blender::meshintersect::repeattri_test

(

)

Definition at line 1121 of file BLI_delaunay_2d_test.cc.

sename()

template<typename T>

std::string blender::meshintersect::sename

(

const SymEdge< T > *

se

)

Definition at line 372 of file delaunay_2d.cc.

References trunc_ptr().

Referenced by cdt_draw().

short_se_dump()

template<typename T>

std::string blender::meshintersect::short_se_dump

(

const SymEdge< T > *

se

)

Definition at line 397 of file delaunay_2d.cc.

References blender::meshintersect::SymEdge< T >::next, blender::meshintersect::SymEdge< T >::vert, and vertname().

Referenced by dump_crossings().

site_lexicographic_sort()

template<typename T>

bool blender::meshintersect::site_lexicographic_sort	(	const SiteInfo< T > &	a,
		const SiteInfo< T > &	b )

Compare function for lexicographic sort: x, then y, then index.

Definition at line 1161 of file delaunay_2d.cc.

References b, blender::meshintersect::SiteInfo< T >::orig_index, and blender::meshintersect::SiteInfo< T >::v.

Referenced by initial_triangulation().

square_o_test()

template<typename T>

void blender::meshintersect::square_o_test

(

)

Definition at line 1136 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, i, in, and out.

sym()

template<typename T>

SymEdge< T > * blender::meshintersect::sym ( const SymEdge< T > * se )

inline

Return other SymEdge for same CDTEdge as se.

Definition at line 100 of file delaunay_2d.cc.

References blender::meshintersect::SymEdge< T >::next.

Referenced by blender::meshintersect::CDTArrangement< T >::add_diagonal(), add_edge_constraint(), add_face_ids(), blender::meshintersect::CDTArrangement< T >::add_vert_to_symedge_edge(), blender::meshintersect::CDTArrangement< T >::connect_separate_parts(), dc_tri(), blender::meshintersect::CDTArrangement< T >::delete_edge(), detect_holes(), dissolve_symedge(), fill_crossdata_for_intersect(), fill_crossdata_for_through_vert(), get_next_crossing_from_edge(), operator<<(), re_delaunay_triangulate(), remove_non_constraint_edges_leave_valid_bmesh(), remove_outer_edges_until_constraints(), and blender::meshintersect::CDTArrangement< T >::split_edge().

TEST() [1/29]

blender::meshintersect::TEST	(	delaunay_d	,
		CrossSegs	)

Definition at line 1218 of file BLI_delaunay_2d_test.cc.

TEST() [2/29]

blender::meshintersect::TEST	(	delaunay_d	,
		CutAcrossTri	)

Definition at line 1223 of file BLI_delaunay_2d_test.cc.

TEST() [3/29]

blender::meshintersect::TEST	(	delaunay_d	,
		DiamondCross	)

Definition at line 1228 of file BLI_delaunay_2d_test.cc.

References CDT_CONSTRAINTS_VALID_BMESH, in, and out.

TEST() [4/29]

blender::meshintersect::TEST	(	delaunay_d	,
		DiamondInSquare	)

Definition at line 1273 of file BLI_delaunay_2d_test.cc.

References out.

TEST() [5/29]

blender::meshintersect::TEST	(	delaunay_d	,
		DiamondInSquareWire	)

Definition at line 1278 of file BLI_delaunay_2d_test.cc.

References out.

TEST() [6/29]

blender::meshintersect::TEST	(	delaunay_d	,
		Empty	)

Definition at line 1153 of file BLI_delaunay_2d_test.cc.

References in, out, T, and x.

TEST() [7/29]

blender::meshintersect::TEST	(	delaunay_d	,
		LineHoleInSquare	)

Definition at line 1208 of file BLI_delaunay_2d_test.cc.

References DO_DRAW.

TEST() [8/29]

blender::meshintersect::TEST	(	delaunay_d	,
		LineInSquare	)

Definition at line 1203 of file BLI_delaunay_2d_test.cc.

References DO_DRAW, and graph_draw().

TEST() [9/29]

blender::meshintersect::TEST	(	delaunay_d	,
		ManyCross	)

Definition at line 1238 of file BLI_delaunay_2d_test.cc.

TEST() [10/29]

blender::meshintersect::TEST	(	delaunay_d	,
		MixedPts	)

Definition at line 1173 of file BLI_delaunay_2d_test.cc.

TEST() [11/29]

blender::meshintersect::TEST	(	delaunay_d	,
		NestedHoles	)

Definition at line 1213 of file BLI_delaunay_2d_test.cc.

TEST() [12/29]

blender::meshintersect::TEST	(	delaunay_d	,
		OnePt	)

Definition at line 1158 of file BLI_delaunay_2d_test.cc.

TEST() [13/29]

blender::meshintersect::TEST	(	delaunay_d	,
		OverlapFaces	)

Definition at line 1253 of file BLI_delaunay_2d_test.cc.

References CDT_CONSTRAINTS, in, and out.

TEST() [14/29]

blender::meshintersect::TEST	(	delaunay_d	,
		Quad0	)

Definition at line 1178 of file BLI_delaunay_2d_test.cc.

References DO_DRAW, graph_draw(), and out.

TEST() [15/29]

blender::meshintersect::TEST	(	delaunay_d	,
		Quad1	)

Definition at line 1183 of file BLI_delaunay_2d_test.cc.

References CDT_INSIDE, DO_DRAW, and in.

TEST() [16/29]

blender::meshintersect::TEST	(	delaunay_d	,
		Quad2	)

Definition at line 1188 of file BLI_delaunay_2d_test.cc.

References CDT_INSIDE_WITH_HOLES, DO_DRAW, and in.

TEST() [17/29]

blender::meshintersect::TEST	(	delaunay_d	,
		Quad3	)

Definition at line 1193 of file BLI_delaunay_2d_test.cc.

TEST() [18/29]

blender::meshintersect::TEST	(	delaunay_d	,
		Quad4	)

Definition at line 1198 of file BLI_delaunay_2d_test.cc.

TEST() [19/29]

blender::meshintersect::TEST	(	delaunay_d	,
		RepeatEdge	)

Definition at line 1283 of file BLI_delaunay_2d_test.cc.

References out.

TEST() [20/29]

blender::meshintersect::TEST	(	delaunay_d	,
		RepeatTri	)

Definition at line 1288 of file BLI_delaunay_2d_test.cc.

References out.

TEST() [21/29]

blender::meshintersect::TEST	(	delaunay_d	,
		SquareO	)

Definition at line 1293 of file BLI_delaunay_2d_test.cc.

References out.

TEST() [22/29]

blender::meshintersect::TEST	(	delaunay_d	,
		ThreePt	)

Definition at line 1168 of file BLI_delaunay_2d_test.cc.

References out.

TEST() [23/29]

blender::meshintersect::TEST	(	delaunay_d	,
		TriInTri	)

Definition at line 1268 of file BLI_delaunay_2d_test.cc.

References out.

TEST() [24/29]

blender::meshintersect::TEST	(	delaunay_d	,
		TwoDiamondsCross	)

Definition at line 1233 of file BLI_delaunay_2d_test.cc.

References DO_DRAW, and out.

TEST() [25/29]

blender::meshintersect::TEST	(	delaunay_d	,
		TwoFace	)

Definition at line 1243 of file BLI_delaunay_2d_test.cc.

TEST() [26/29]

blender::meshintersect::TEST	(	delaunay_d	,
		TwoFace2	)

Definition at line 1248 of file BLI_delaunay_2d_test.cc.

References in.

TEST() [27/29]

blender::meshintersect::TEST	(	delaunay_d	,
		TwoFaceEdgeOverlap	)

Definition at line 1263 of file BLI_delaunay_2d_test.cc.

References i.

TEST() [28/29]

blender::meshintersect::TEST	(	delaunay_d	,
		TwoPt	)

Definition at line 1163 of file BLI_delaunay_2d_test.cc.

References out.

TEST() [29/29]

blender::meshintersect::TEST	(	delaunay_d	,
		TwoSquaresOverlap	)

Definition at line 1258 of file BLI_delaunay_2d_test.cc.

References get_orig_index(), i, and out.

threept_test()

template<typename T>

void blender::meshintersect::threept_test

(

)

Definition at line 458 of file BLI_delaunay_2d_test.cc.

References DO_DRAW, graph_draw(), and out.

tri_orient()

template<typename T>

int blender::meshintersect::tri_orient ( const SymEdge< T > * t )

inline

Definition at line 1536 of file delaunay_2d.cc.

References filtered_orient2d(), blender::meshintersect::SymEdge< T >::next, and blender::meshintersect::SymEdge< T >::vert.

Referenced by get_next_crossing_from_vert().

triintri_test()

template<typename T>

void blender::meshintersect::triintri_test

(

)

Definition at line 1067 of file BLI_delaunay_2d_test.cc.

trunc_ptr()

std::string blender::meshintersect::trunc_ptr ( const void * p )

static

Definition at line 364 of file delaunay_2d.cc.

References POINTER_AS_INT.

Referenced by cdt_draw(), operator<<(), and sename().

twodiamondscross_test()

template<typename T>

void blender::meshintersect::twodiamondscross_test

(

)

Definition at line 766 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, i, in, and out.

twoface2_test()

template<typename T>

void blender::meshintersect::twoface2_test

(

)

Definition at line 856 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, DO_DRAW, in, and out.

twoface_test()

template<typename T>

void blender::meshintersect::twoface_test

(

)

Definition at line 820 of file BLI_delaunay_2d_test.cc.

References out.

twofaceedgeoverlap_test()

template<typename T>

void blender::meshintersect::twofaceedgeoverlap_test

(

)

Definition at line 1014 of file BLI_delaunay_2d_test.cc.

References CDT_FULL, i, in, and out.

twopt_test()

template<typename T>

void blender::meshintersect::twopt_test

(

)

Definition at line 433 of file BLI_delaunay_2d_test.cc.

twosquaresoverlap_test()

template<typename T>

void blender::meshintersect::twosquaresoverlap_test

(

)

Definition at line 1000 of file BLI_delaunay_2d_test.cc.

References fill_input_from_string(), and in.

vert_left_of_symedge()

template<typename T>

bool blender::meshintersect::vert_left_of_symedge ( CDTVert< T > * v, SymEdge< T > * se )

inline

Definition at line 1200 of file delaunay_2d.cc.

References filtered_orient2d(), blender::meshintersect::SymEdge< T >::next, v, and blender::meshintersect::SymEdge< T >::vert.

Referenced by dc_tri().

vert_right_of_symedge()

template<typename T>

bool blender::meshintersect::vert_right_of_symedge ( CDTVert< T > * v, SymEdge< T > * se )

inline

Definition at line 1205 of file delaunay_2d.cc.

References filtered_orient2d(), blender::meshintersect::SymEdge< T >::next, v, and blender::meshintersect::SymEdge< T >::vert.

Referenced by dc_tri().

vert_touches_face()

template<typename T>

bool blender::meshintersect::vert_touches_face	(	const CDTVert< T > *	v,
		const CDTFace< T > *	f )

Is the vertex v incident on face f?

Definition at line 952 of file delaunay_2d.cc.

References blender::meshintersect::SymEdge< T >::face, blender::meshintersect::SymEdge< T >::rot, and v.

Referenced by remove_non_constraint_edges_leave_valid_bmesh().

vertname()

template<typename T>

std::string blender::meshintersect::vertname

(

const CDTVert< T > *

v

)

Definition at line 356 of file delaunay_2d.cc.

References v.

Referenced by add_edge_constraint(), cdt_draw(), operator<<(), operator<<(), and short_se_dump().

Variable Documentation

DO_DRAW

bool blender::meshintersect::DO_DRAW = false

constexpr

Definition at line 385 of file BLI_delaunay_2d_test.cc.

Referenced by crosssegs_test(), diamondcross_test(), lineholeinsquare_test(), mixedpts_test(), nestedholes_test(), quad0_test(), quad2_test(), quad3_test(), quad4_test(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), threept_test(), and twoface2_test().

draw_append

bool blender::meshintersect::draw_append = false

static

Definition at line 263 of file BLI_delaunay_2d_test.cc.

Referenced by graph_draw().