Blender V5.3
blender::meshintersect Namespace Reference

Classes

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

Functions

template<typename T>
CDT_result< T > delaunay_2d_calc (const CDT_input< T > &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)
static bool output_uses_evenodd_holes (const CDT_output_type output_type)
static bool output_uses_nonzero_holes (const CDT_output_type output_type)
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 VectorSet< uint32_t > &id_list, uint32_t range_start, uint32_t range_end)
static void add_to_input_ids (VectorSet< uint32_t > &dst, uint32_t input_id)
static void add_list_to_input_ids (VectorSet< uint32_t > &dst, const VectorSet< uint32_t > &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, uint32_t 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, uint32_t face_id, uint32_t fedge_start, uint32_t fedge_end)
static uint32_t power_of_10_greater_equal_to (uint32_t x)
template<typename T>
int add_face_constraints (CDT_state< T > *cdt_state, const CDT_input< T > &input, CDT_output_type output_type, const bool need_winding)
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, const bool use_hole_status)
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 Value, typename CombineFn>
void flood_fill_region_values (const Map< int2, Value > &region_pair_value, MutableSpan< Value > region_value, const Value unset_value, CombineFn combine)
template<typename T>
void detect_holes_with_fillrule_even_odd (CDT_state< T > *cdt_state)
template<typename T>
void detect_holes_with_fillrule_nonzero (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, 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 CDT_result< double > delaunay_2d_calc (const CDT_input< double > &, CDT_output_type)
template<typename T>
CDT_input< T > fill_input_from_string (const char *spec, InputStorage< T > &r_storage)
static int get_orig_index (const Span< Vector< uint32_t > > 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_vert_is_intersection_and_has_edge_input_ids (const CDT_result< T > &out, int out_vert_index, int in_edge1_index, int in_edge2_index)
template<typename T>
bool output_edge_has_input_id (const CDT_result< T > &out, int out_edge_index, uint32_t 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, uint32_t 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< int2 > 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 even_odd_nested_holes_deep_test ()
template<typename T>
void even_odd_boundary_disagreement_test ()
template<typename T>
void even_odd_coincident_polygons_needed_ids_stable_test ()
template<typename T>
void cw_orig_face_ids_test ()
template<typename T>
void looping_back_2x_test ()
template<typename T>
void looping_back_3x_test ()
template<typename T>
void looping_back_hole_2x_test ()
template<typename T>
void looping_back_hole_3x_test ()
template<typename T>
void disjoint_polys_in_large_hull_test ()
template<typename T>
void nonzero_winding_test ()
template<typename T>
void nonzero_winding_nested_test ()
template<typename T>
void nonzero_winding_nested_union_test ()
template<typename T>
void nonzero_winding_multi_face_edge_test ()
template<typename T>
void nonzero_winding_multi_face_edge_mixed_test ()
template<typename T>
void nonzero_winding_cancel_to_zero_test ()
template<typename T>
void nonzero_winding_high_count_test ()
template<typename T>
void nonzero_winding_fan_test ()
template<typename T>
void nonzero_winding_edge_split_test ()
template<typename T>
void nonzero_winding_self_intersect_test ()
template<typename T>
void nonzero_winding_deep_nest_test ()
template<typename T>
void nonzero_winding_shared_subsegment_test ()
template<typename T>
void nonzero_winding_island_in_hole_test ()
template<typename T>
void nonzero_winding_coincident_verts_test ()
template<typename T>
void nonzero_winding_many_crossings_test ()
template<typename T>
void nonzero_winding_negative_only_test ()
template<typename T>
void nonzero_winding_tjunction_test ()
template<typename T>
void nonzero_winding_exact_shared_edge_test ()
template<typename T>
void nonzero_winding_concave_outer_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 shared_split_boundary_test ()
template<typename T>
void square_o_test ()
template<typename T>
void fill_curve_letter_b_test ()
template<typename T>
void fill_curve_degenerate_interior_faces_test ()
template<typename T>
void dissolve_pendant_edge_face_test ()
template<typename T>
void stale_symedge_before_remove_faces_in_holes_test ()
template<typename T>
void fuzz_repro_minimize_test1 ()
template<typename T>
void fuzz_repro_minimize_test2 ()
template<typename T>
void intersection_simple_edge_ids_test ()
template<typename T>
void intersection_squares_edge_ids_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, EvenOddNestedHolesDeep)
 TEST (delaunay_d, EvenOddBoundaryDisagreement)
 TEST (delaunay_d, EvenOddCoincidentPolygonsNeedIdsStable)
 TEST (delaunay_d, CwOrigFaceIds)
 TEST (delaunay_d, NonZeroWinding)
 TEST (delaunay_d, NonZeroWindingNested)
 TEST (delaunay_d, NonZeroWindingNestedUnion)
 TEST (delaunay_d, NonZeroWindingMultiFaceEdge)
 TEST (delaunay_d, NonZeroWindingMultiFaceEdgeMixed)
 TEST (delaunay_d, NonZeroWindingCancelToZero)
 TEST (delaunay_d, NonZeroWindingHighCount)
 TEST (delaunay_d, NonZeroWindingFan)
 TEST (delaunay_d, NonZeroWindingEdgeSplit)
 TEST (delaunay_d, NonZeroWindingSelfIntersect)
 TEST (delaunay_d, NonZeroWindingDeepNest)
 TEST (delaunay_d, NonZeroWindingSharedSubsegment)
 TEST (delaunay_d, NonZeroWindingIslandInHole)
 TEST (delaunay_d, NonZeroWindingCoincidentVerts)
 TEST (delaunay_d, NonZeroWindingManyCrossings)
 TEST (delaunay_d, NonZeroWindingNegativeOnly)
 TEST (delaunay_d, NonZeroWindingTJunction)
 TEST (delaunay_d, NonZeroWindingExactSharedEdge)
 TEST (delaunay_d, NonZeroWindingConcaveOuter)
 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, LoopingBack2x)
 TEST (delaunay_d, LoopingBack3x)
 TEST (delaunay_d, LoopingBackHole2x)
 TEST (delaunay_d, LoopingBackHole3x)
 TEST (delaunay_d, DisjointPolysInLargeHull)
 TEST (delaunay_d, RepeatEdge)
 TEST (delaunay_d, RepeatTri)
 TEST (delaunay_d, SharedSplitBoundary)
 TEST (delaunay_d, SquareO)
 TEST (delaunay_d, FillCurveLetterB)
 TEST (delaunay_d, FillCurveDegenerateInteriorFaces)
 TEST (delaunay_d, DissolvePendantEdgeFace)
 TEST (delaunay_d, StaleSymedgeBeforeRemoveFacesInHoles)
 TEST (delaunay_d, FuzzReproMinimize1)
 TEST (delaunay_d, FuzzReproMinimize2)
 TEST (delaunay_d, IntersectionSimpleEdgeIds)
 TEST (delaunay_d, IntersectionSquaresEdgeIds)

Variables

static constexpr bool USE_POW10_FACE_EDGE_OFFSET_ROUND_UP = false
static constexpr int VISIT_INDEX_UNVISITED = -1
static constexpr int VISIT_INDEX_OUTER_FACE = -2
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,
uint32_t 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 2029 of file delaunay_2d.cc.

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

Referenced by add_edge_constraint(), 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 2266 of file delaunay_2d.cc.

References add_edge_constraint(), add_edge_constraints(), blender::meshintersect::CDT_state< T >::cdt, blender::CDT_INTERSECTED_EDGES, blender::CDT_ORIG_EDGES, blender::Core, blender::meshintersect::CDT_input< T >::edge, blender::meshintersect::CDT_state< T >::face_edge_offset, blender::meshintersect::CDT_state< T >::needed_ids, PRF_scope, blender::v2, and blender::meshintersect::CDT_input< T >::vert.

Referenced by add_edge_constraints(), and 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,
const bool need_winding )

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 2368 of file delaunay_2d.cc.

References add_edge_constraint(), add_face_constraints(), add_face_ids(), blender::BLI_assert(), blender::BLI_linklist_free(), blender::meshintersect::CDT_state< T >::cdt, blender::CDT_CONSTRAINTS_VALID_BMESH, blender::CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, blender::CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES_NONZERO, blender::CDT_CW_ORIG_FACES, blender::CDT_ORIG_FACES, blender::BMVert::co, blender::meshintersect::CDTVert< T >::co, blender::Core, blender::math::cross(), blender::e, blender::meshintersect::CDT_state< T >::edge_winding_map, ELEM, blender::meshintersect::CDT_state< T >::face_edge_offset, blender::meshintersect::CDT_input< T >::face_offsets, blender::meshintersect::CDT_input< T >::face_vert_indices, blender::meshintersect::CDTArrangement< T >::get_vert_resolve_merge(), blender::offset_indices::GroupedSpan< T >::index_range(), blender::Span< T >::index_range(), blender::offset_indices::GroupedSpan< T >::is_empty(), blender::LinkNode::link, blender::meshintersect::CDT_state< T >::needed_ids, blender::LinkNode::next, blender::meshintersect::CDT_state< T >::polygon_boundary_count_map, power_of_10_greater_equal_to(), PRF_scope, blender::offset_indices::GroupedSpan< T >::size(), blender::Span< T >::size(), blender::meshintersect::CDTEdge< T >::symedges, USE_POW10_FACE_EDGE_OFFSET_ROUND_UP, blender::v2, and blender::meshintersect::CDT_input< T >::vert.

Referenced by add_face_constraints(), and delaunay_calc().

◆ add_face_ids()

template<typename T>
void blender::meshintersect::add_face_ids ( CDT_state< T > * cdt_state,
SymEdge< T > * face_symedge,
uint32_t face_id,
uint32_t fedge_start,
uint32_t 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 would be labeling the outside, not the inside. There will be another surrounding set of faces and those are the ones whose original faces should be propagated, not the hole face ids. So we'll skip the flood fill for CW faces. If the boundary has self crossings then it is a mixture of CCW and CW; by using the signed area we find the "dominant" direction and hopefully that's what the user intended. (In current usage throughout Blender, the only code that cares about original face id propagation is the mesh_intersect code used in the exact boolean code. And that code guarantees only CCW faces coming in.

Definition at line 2308 of file delaunay_2d.cc.

References add_face_ids(), add_to_input_ids(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::Core, 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(), PRF_scope, sym(), blender::meshintersect::CDT_state< T >::visit_count, and blender::meshintersect::CDTFace< T >::visit_index.

Referenced by add_face_constraints(), and add_face_ids().

◆ 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 3360 of file delaunay_2d.cc.

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

Referenced by add_input_verts(), and delaunay_calc().

◆ add_list_to_input_ids()

◆ add_to_input_ids()

◆ cdt_draw()

◆ crosssegs_test()

template<typename T>
void blender::meshintersect::crosssegs_test ( )

Definition at line 2252 of file BLI_delaunay_2d_test.cc.

References nonzero_winding_island_in_hole_test().

◆ cutacrosstri_test()

template<typename T>
void blender::meshintersect::cutacrosstri_test ( )

◆ cw_orig_face_ids_test()

template<typename T>
void blender::meshintersect::cw_orig_face_ids_test ( )

A CCW square with a CW square inside it, where CDT_CW_ORIG_FACES decides whether the CW face propagates its id. The flag has no effect on the *_VALID_BMESH* outputs, which propagate CW ids either way.

Definition at line 881 of file BLI_delaunay_2d_test.cc.

Referenced by nonzero_winding_test().

◆ dc_tri()

◆ dc_tri_valid()

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

◆ dc_triangulate()

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

Definition at line 1580 of file delaunay_2d.cc.

References blender::Core, dc_tri(), dc_triangulate(), PRF_scope, and blender::v.

Referenced by dc_triangulate(), and initial_triangulation().

◆ delaunay_2d_calc() [1/2]

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

References delaunay_2d_calc().

◆ delaunay_2d_calc() [2/2]

◆ delaunay_calc()

◆ detect_holes_with_fillrule_even_odd()

template<typename T>
void blender::meshintersect::detect_holes_with_fillrule_even_odd ( CDT_state< T > * cdt_state)

Detect holes using the even-odd fill rule.

A hole face is one whose region has even parity, accumulated from input polygon boundaries crossed walking from outer_face into the region (or is unreachable from outer_face through constrained edges).

Definition at line 2836 of file delaunay_2d.cc.

References blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::BLI_assert(), blender::meshintersect::CDT_state< T >::cdt, blender::Core, blender::meshintersect::CDTFace< T >::deleted, detect_holes_with_fillrule_even_odd(), blender::e, blender::meshintersect::SymEdge< T >::edge, blender::meshintersect::CDTArrangement< T >::edges, blender::meshintersect::CDTArrangement< T >::faces, flood_fill_region_values(), blender::meshintersect::CDTFace< T >::hole, is_constrained_edge(), is_deleted_edge(), blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::lookup_default(), blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, blender::meshintersect::CDT_state< T >::polygon_boundary_count_map, blender::Vector< T, InlineBufferCapacity, Allocator >::pop_last(), PRF_scope, blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::reserve(), blender::Vector< T, InlineBufferCapacity, Allocator >::reserve(), sym(), blender::meshintersect::CDTFace< T >::symedge, blender::meshintersect::CDT_state< T >::visit_count, blender::meshintersect::CDTFace< T >::visit_index, VISIT_INDEX_OUTER_FACE, and VISIT_INDEX_UNVISITED.

Referenced by detect_holes_with_fillrule_even_odd(), and prepare_cdt_for_output().

◆ detect_holes_with_fillrule_nonzero()

template<typename T>
void blender::meshintersect::detect_holes_with_fillrule_nonzero ( CDT_state< T > * cdt_state)

Detect holes using the non-zero winding fill rule.

A hole face is one whose region has zero winding, accumulated from signed boundary crossings walking from outer_face into the region (or is unreachable from outer_face through constrained edges).

Definition at line 2999 of file delaunay_2d.cc.

References blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::BLI_assert(), blender::meshintersect::CDT_state< T >::cdt, blender::Core, blender::meshintersect::CDTFace< T >::deleted, detect_holes_with_fillrule_nonzero(), blender::e, blender::meshintersect::SymEdge< T >::edge, blender::meshintersect::CDT_state< T >::edge_winding_map, blender::meshintersect::CDTArrangement< T >::edges, ELEM, blender::meshintersect::CDTArrangement< T >::faces, blender::Array< T, InlineBufferCapacity, Allocator >::fill(), flood_fill_region_values(), blender::meshintersect::CDTFace< T >::hole, is_constrained_edge(), is_deleted_edge(), blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, blender::Vector< T, InlineBufferCapacity, Allocator >::pop_last(), PRF_scope, blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::reserve(), blender::Vector< T, InlineBufferCapacity, Allocator >::reserve(), sym(), blender::meshintersect::CDTFace< T >::symedge, blender::meshintersect::CDT_state< T >::visit_count, blender::meshintersect::CDTFace< T >::visit_index, VISIT_INDEX_OUTER_FACE, and VISIT_INDEX_UNVISITED.

Referenced by detect_holes_with_fillrule_nonzero(), and prepare_cdt_for_output().

◆ diamondcross_test()

template<typename T>
void blender::meshintersect::diamondcross_test ( )

Definition at line 2329 of file BLI_delaunay_2d_test.cc.

References nonzero_winding_coincident_verts_test().

◆ diamondinsquare_test()

template<typename T>
void blender::meshintersect::diamondinsquare_test ( )

Definition at line 2659 of file BLI_delaunay_2d_test.cc.

Referenced by TEST().

◆ diamondinsquarewire_test()

template<typename T>
void blender::meshintersect::diamondinsquarewire_test ( )

Definition at line 2673 of file BLI_delaunay_2d_test.cc.

References EXPECT_LT.

Referenced by TEST().

◆ disjoint_polys_in_large_hull_test()

template<typename T>
void blender::meshintersect::disjoint_polys_in_large_hull_test ( )

◆ dissolve_pendant_edge_face_test()

template<typename T>
void blender::meshintersect::dissolve_pendant_edge_face_test ( )

A single hexagon face plus two points that aren't part of any face, with needed_ids = 0 and CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES (as used by the "Fill Curve" node). The stray points force triangulation edges that never represent an input face. Dissolving those in remove_non_constraint_edges_leave_valid_bmesh could reduce a face to a single dangling edge, or delete a pendant edge leaving CDTFace::symedge pointing at a just-deleted SymEdge, crashing get_cdt_output when walking the boundary.

The counts below only record current behavior, what matters is that it doesn't crash.

Reduced from a self-intersecting curve that crashed the "Fill Curve" node in "N-gons" mode, see: #160787.

Definition at line 2909 of file BLI_delaunay_2d_test.cc.

◆ dissolve_symedge()

◆ dump_crossings()

◆ empty_test()

template<typename T>
void blender::meshintersect::empty_test ( )

◆ even_odd_boundary_disagreement_test()

template<typename T>
void blender::meshintersect::even_odd_boundary_disagreement_test ( )

◆ even_odd_coincident_polygons_needed_ids_stable_test()

template<typename T>
void blender::meshintersect::even_odd_coincident_polygons_needed_ids_stable_test ( )

◆ even_odd_nested_holes_deep_test()

template<typename T>
void blender::meshintersect::even_odd_nested_holes_deep_test ( )

Definition at line 729 of file BLI_delaunay_2d_test.cc.

◆ 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 1039 of file delaunay_2d.cc.

References exists_edge(), find_symedge_between_verts(), and blender::v2.

Referenced by exists_edge(), and 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 )

◆ expect_coord_near< double >()

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

Definition at line 424 of file BLI_delaunay_2d_test.cc.

References blender::e, expect_coord_near(), and EXPECT_NEAR.

◆ 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 1820 of file delaunay_2d.cc.

References blender::BLI_assert(), blender::BMVert::co, blender::meshintersect::CDTVert< T >::co, blender::Core, blender::meshintersect::CrossData< T >::CrossData(), distance(), distance_squared(), blender::meshintersect::FatCo< T >::exact, fill_crossdata_for_intersect(), 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, PRF_scope, sym(), T, UNUSED_VARS_NDEBUG, blender::v2, and blender::meshintersect::SymEdge< T >::vert.

Referenced by fill_crossdata_for_intersect(), 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 1778 of file delaunay_2d.cc.

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

Referenced by fill_crossdata_for_intersect(), fill_crossdata_for_through_vert(), and get_next_crossing_from_vert().

◆ fill_curve_degenerate_interior_faces_test()

template<typename T>
void blender::meshintersect::fill_curve_degenerate_interior_faces_test ( )

A square boundary filled with a grid of degenerate (two vertex) interior faces. Stress test for the crash in #160787.

The counts below only record current behavior, what matters is that it doesn't crash.

Definition at line 2822 of file BLI_delaunay_2d_test.cc.

References blender::CDT_FULL, delaunay_2d_calc(), DO_DRAW, blender::EXPECT_EQ(), fill_input_from_string(), graph_draw(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.

◆ fill_curve_letter_b_test()

template<typename T>
void blender::meshintersect::fill_curve_letter_b_test ( )

A letter "B": an outer boundary with two holes, wound as font glyphs are (CW outline, CCW counters), filled as the "Fill Curve" node fills text in "N-gons" mode using the even-odd rule.

This test ensures even-odd filling does not depend on the polygon winding, see: #163256.

Definition at line 2788 of file BLI_delaunay_2d_test.cc.

References blender::EXPECT_EQ(), EXPECT_NE, EXPECT_TRUE, get_orig_index(), get_output_edge_index(), and blender::gpu::shader::metadata::out.

◆ fill_input_from_string()

template<typename T>
CDT_input< T > blender::meshintersect::fill_input_from_string ( const char * spec,
InputStorage< T > & r_storage )

Definition at line 45 of file BLI_delaunay_2d_test.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::Array< T, InlineBufferCapacity, Allocator >::as_span(), blender::CDT_ORIG_EDGES, blender::CDT_ORIG_FACES, blender::CDT_ORIG_VERTS, blender::meshintersect::CDT_input< T >::edge, blender::meshintersect::InputStorage< T >::edge, blender::meshintersect::CDT_input< T >::epsilon, blender::meshintersect::CDT_input< T >::face_offsets, blender::meshintersect::InputStorage< T >::face_offsets, blender::meshintersect::CDT_input< T >::face_vert_indices, blender::meshintersect::InputStorage< T >::face_vert_indices, fill_input_from_string(), blender::Array< T, InlineBufferCapacity, Allocator >::last(), blender::meshintersect::CDT_input< T >::needed_ids, blender::Array< T, InlineBufferCapacity, Allocator >::reinitialize(), blender::Vector< T, InlineBufferCapacity, Allocator >::size(), T, blender::v, blender::meshintersect::CDT_input< T >::vert, and blender::meshintersect::InputStorage< T >::vert.

Referenced by cutacrosstri_test(), disjoint_polys_in_large_hull_test(), even_odd_coincident_polygons_needed_ids_stable_test(), fill_curve_degenerate_interior_faces_test(), fill_input_from_string(), fuzz_repro_minimize_test1(), intersection_simple_edge_ids_test(), lineholeinsquare_test(), looping_back_2x_test(), nonzero_winding_deep_nest_test(), nonzero_winding_exact_shared_edge_test(), nonzero_winding_fan_test(), nonzero_winding_many_crossings_test(), nonzero_winding_nested_test(), nonzero_winding_nested_union_test(), nonzero_winding_self_intersect_test(), nonzero_winding_test(), nonzero_winding_tjunction_test(), onept_test(), overlapfaces_test(), quad3_test(), quad4_test(), repeattri_test(), square_o_test(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), triintri_test(), twodiamondscross_test(), twoface2_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, fabs(), and filtered_incircle().

Referenced by dc_tri(), filtered_incircle(), filtered_incircle< double >(), 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 )

◆ 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, fabs(), and filtered_orient2d().

Referenced by dc_tri(), dc_tri_valid(), filtered_orient2d(), filtered_orient2d< double >(), 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 )

◆ 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 1337 of file delaunay_2d.cc.

References blender::BMVert::co, find_site_merges(), and blender::v.

Referenced by find_site_merges(), and 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 )

◆ 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 1024 of file delaunay_2d.cc.

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

Referenced by add_edge_constraint(), and find_symedge_with_face().

◆ flood_fill_region_values()

template<typename Value, typename CombineFn>
void blender::meshintersect::flood_fill_region_values ( const Map< int2, Value > & region_pair_value,
MutableSpan< Value > region_value,
const Value unset_value,
CombineFn combine )

Flood-fill per-region values (parity for even-odd, winding for non-zero) from seeded regions outward through the region-adjacency graph, building CSR adjacency from a region-pair map for the traversal.

region_pair_value is a Map keyed by (region_src, region_dst). Callers are expected to insert both directions for each undirected edge (with value flipped if needed for the domain - e.g. negated for signed winding deltas, unchanged for symmetric XOR parity). Map::add ignores subsequent inserts for an existing key, so first-edge-wins is free.

region_value is both input and output. On entry, regions whose value is not unset_value are treated as roots. On exit, regions reachable from a root hold combine(parent_value, edge_value_in_traversed_direction). Unreachable regions are left at unset_value.

Order of traversal does not affect the result for self-consistent inputs - each region is assigned exactly once on first reach. For inconsistent inputs (region-graph cycles whose combine-deltas don't close), the first value wins; later visits via a different path that would compute a different value are silently ignored.

Definition at line 2777 of file delaunay_2d.cc.

References blender::offset_indices::accumulate_counts_to_offsets(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), flood_fill_region_values(), blender::MutableSpan< T >::index_range(), blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::items(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::keys(), blender::Vector< T, InlineBufferCapacity, Allocator >::pop_last(), blender::Vector< T, InlineBufferCapacity, Allocator >::reserve(), blender::MutableSpan< T >::size(), and blender::offset_indices::OffsetIndices< T >::total_size().

Referenced by detect_holes_with_fillrule_even_odd(), detect_holes_with_fillrule_nonzero(), and flood_fill_region_values().

◆ fuzz_repro_minimize_test1()

template<typename T>
void blender::meshintersect::fuzz_repro_minimize_test1 ( )

◆ fuzz_repro_minimize_test2()

template<typename T>
void blender::meshintersect::fuzz_repro_minimize_test2 ( )

Minimized test case found by fuzzing a fix for: #160787.

Definition at line 2961 of file BLI_delaunay_2d_test.cc.

◆ 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 1973 of file delaunay_2d.cc.

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

Referenced by add_edge_constraint(), and get_next_crossing_from_edge().

◆ 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 1921 of file delaunay_2d.cc.

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

Referenced by add_edge_constraint(), and get_next_crossing_from_vert().

◆ get_orig_index()

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

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

◆ get_output_face_index()

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

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

◆ get_vertex_by_coord()

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

◆ graph_draw()

◆ id_range_in_list()

bool blender::meshintersect::id_range_in_list ( const VectorSet< uint32_t > & id_list,
uint32_t range_start,
uint32_t range_end )
static

Definition at line 961 of file delaunay_2d.cc.

References blender::Core, id_range_in_list(), and PRF_scope.

Referenced by add_face_ids(), and id_range_in_list().

◆ 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, and in_line().

Referenced by get_next_crossing_from_vert(), in_line(), and in_line< double >().

◆ 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 860 of file delaunay_2d.cc.

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

◆ 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 1621 of file delaunay_2d.cc.

References blender::Core, dc_triangulate(), find_site_merges(), initial_triangulation(), PRF_scope, site_lexicographic_sort(), and blender::meshintersect::CDTArrangement< T >::verts.

Referenced by delaunay_calc(), and initial_triangulation().

◆ intersection_simple_edge_ids_test()

template<typename T>
void blender::meshintersect::intersection_simple_edge_ids_test ( )

◆ intersection_squares_edge_ids_test()

template<typename T>
void blender::meshintersect::intersection_squares_edge_ids_test ( )

Definition at line 2985 of file BLI_delaunay_2d_test.cc.

References EXPECT_NE.

◆ 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 985 of file delaunay_2d.cc.

References blender::e, and is_border_edge().

Referenced by is_border_edge().

◆ is_constrained_edge()

◆ is_deleted_edge()

◆ is_original_vert()

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

◆ lineholeinsquare_test()

◆ lineinsquare_test()

template<typename T>
void blender::meshintersect::lineinsquare_test ( )

Definition at line 611 of file BLI_delaunay_2d_test.cc.

◆ looping_back_2x_test()

template<typename T>
void blender::meshintersect::looping_back_2x_test ( )

A hexagon whose face walks its own vertices twice. Even-odd counts every traversal of a boundary edge, so the second lap cancels the first and nothing is filled.

Definition at line 912 of file BLI_delaunay_2d_test.cc.

References blender::CDT_INSIDE_WITH_HOLES, delaunay_2d_calc(), fill_input_from_string(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.

◆ looping_back_3x_test()

template<typename T>
void blender::meshintersect::looping_back_3x_test ( )

As looping_back_2x_test with a third lap, back to odd parity so the hexagon fills.

Definition at line 927 of file BLI_delaunay_2d_test.cc.

References blender::EXPECT_EQ(), EXPECT_FALSE, EXPECT_TRUE, blender::gpu::shader::metadata::out, and output_face_has_input_id().

◆ looping_back_hole_2x_test()

template<typename T>
void blender::meshintersect::looping_back_hole_2x_test ( )

A quad around a hexagon that walks its own vertices twice. The hexagon's edges cancel, so it isn't a hole and the quad fills across it.

Definition at line 943 of file BLI_delaunay_2d_test.cc.

◆ looping_back_hole_3x_test()

template<typename T>
void blender::meshintersect::looping_back_hole_3x_test ( )

As looping_back_hole_2x_test with a third lap, so the hexagon is a hole in the quad.

Definition at line 958 of file BLI_delaunay_2d_test.cc.

◆ manycross_test()

template<typename T>
void blender::meshintersect::manycross_test ( )

Definition at line 2383 of file BLI_delaunay_2d_test.cc.

◆ math_abs() [1/3]

template<>
double blender::meshintersect::math_abs ( const double v)

Definition at line 152 of file BLI_delaunay_2d_test.cc.

References fabs(), math_abs(), and blender::v.

◆ math_abs() [2/3]

template<typename T>
T blender::meshintersect::math_abs ( const T v)

Definition at line 45 of file delaunay_2d.cc.

References math_abs(), T, and blender::v.

Referenced by math_abs(), math_abs(), math_abs< double >(), and TEST().

◆ math_abs() [3/3]

template<typename T>
T blender::meshintersect::math_abs ( const T v)
static

Definition at line 45 of file delaunay_2d.cc.

References math_abs(), T, and blender::v.

Referenced by math_abs(), math_abs(), math_abs< double >(), and TEST().

◆ math_abs< double >()

template<>
double blender::meshintersect::math_abs< double > ( const double v)

Definition at line 57 of file delaunay_2d.cc.

References fabs(), math_abs(), and blender::v.

◆ math_to_double() [1/2]

template<typename T>
double blender::meshintersect::math_to_double ( const T )

◆ math_to_double() [2/2]

template<typename T>
double blender::meshintersect::math_to_double ( const T )
static

Definition at line 125 of file BLI_delaunay_2d_test.cc.

References blender::BLI_assert(), math_to_double(), and T.

◆ math_to_double< double >() [1/2]

template<>
double blender::meshintersect::math_to_double< double > ( const double v)

Definition at line 75 of file delaunay_2d.cc.

References math_to_double(), and blender::v.

◆ math_to_double< double >() [2/2]

template<>
double blender::meshintersect::math_to_double< double > ( const double v)

Definition at line 131 of file BLI_delaunay_2d_test.cc.

References math_to_double(), and blender::v.

◆ mixedpts_test()

template<typename T>
void blender::meshintersect::mixedpts_test ( )

◆ nestedholes_test()

template<typename T>
void blender::meshintersect::nestedholes_test ( )

◆ nonzero_winding_cancel_to_zero_test()

template<typename T>
void blender::meshintersect::nonzero_winding_cancel_to_zero_test ( )

Stress test: winding contributions that cancel exactly to zero. Four faces share the same bottom edge with windings: CCW, CCW, CW, CW. Net winding on shared edge: +1 + 1 - 1 - 1 = 0.

This tests that zero-winding regions correctly become holes in non-zero mode.

Geometry (4 overlapping rectangles, all sharing bottom edge at y=0):
9---------8 y=4 Face 3 (CW, -1)
| |
7---------6 y=3 Face 2 (CW, -1)
| |
5---------4 y=2 Face 1 (CCW, +1)
| |
3---------2 y=1 Face 0 (CCW, +1)
| |
0---------1 y=0
x=0,3
  • Face 0: (0,0)-(3,1) CCW (+1).
  • Face 1: (0,0)-(3,2) CCW (+1).
  • Face 2: (0,0)-(3,3) CW (-1).
  • Face 3: (0,0)-(3,4) CW (-1).

Winding by y-band:

  • [0,1]: All 4 faces overlap giving +1+1-1-1 = 0 (HOLE - this is correct).
  • [1,2]: Faces 1,2,3 overlap giving +1-1-1 = -1 (filled).
  • [2,3]: Faces 2,3 overlap giving -1-1 = -2 (filled).
  • [3,4]: Only face 3 giving -1 (filled).

EXPECTED RESULT for non-zero: bottom band [0,1] is empty, top 3 bands filled. This looks unusual but is correct - the bottom band has winding=0 because two CCW faces (+1+1) and two CW faces (-1-1) cancel out exactly.

Even-odd by y-band (for comparison):

  • [0,1]: 4 crossings means outside (hole).
  • [1,2]: 3 crossings means inside (filled).
  • [2,3]: 2 crossings means outside (hole).
  • [3,4]: 1 crossing means inside (filled).

Definition at line 1431 of file BLI_delaunay_2d_test.cc.

References blender::EXPECT_EQ().

Referenced by nonzero_winding_self_intersect_test().

◆ nonzero_winding_coincident_verts_test()

template<typename T>
void blender::meshintersect::nonzero_winding_coincident_verts_test ( )

Stress test: coincident edges from separate faces with different vertices. Tests vertex merging combined with winding accumulation.

Geometry:
2 (1,1)
/ \ Face 0 (CCW, +1)
/ \
/ \
0,3---------1,4 y=0 (shared edge, vertices merged)
\ /
\ /
\ / Face 1 (CW, -1)
5 (1,-1)
  • Face 0: Triangle with base (0,0)-(2,0), apex at (1,1), CCW, uses vertices 0,1,2.
  • Face 1: Triangle with base (0,0)-(2,0), apex at (1,-1), CW, uses vertices 3,4,5.
  • Vertices 0,3 are coincident (both at 0,0).
  • Vertices 1,4 are coincident (both at 2,0).

The shared edge (0,0)-(2,0) comes from two different vertex pairs that get merged by CDT. Face 0 is CCW (+1), Face 1 is CW (-1). The shared edge has winding +1-1 = 0.

This tests that winding is correctly accumulated when vertex merging creates shared edges, even when the faces have opposite orientations.

Definition at line 1952 of file BLI_delaunay_2d_test.cc.

References blender::CDT_INSIDE_WITH_HOLES_NONZERO, delaunay_2d_calc(), DO_DRAW, graph_draw(), and blender::gpu::shader::metadata::in.

Referenced by diamondcross_test().

◆ nonzero_winding_concave_outer_test()

template<typename T>
void blender::meshintersect::nonzero_winding_concave_outer_test ( )

Concave polygon where no polygon edge lies on the convex hull. Three corners form a triangle, three midpoints are slightly inside each edge. The convex hull uses only the corners, so the CDT has no constrained edges adjacent to the outer face.

Regression test: non-zero winding hole detection must treat unconstrained edges to the outer face as boundary regions with winding 0. This simple polygon should triangulate to exactly 4 faces under both rules; the broken path produced 0 faces for the non-zero case.

Definition at line 2238 of file BLI_delaunay_2d_test.cc.

Referenced by repeatedge_test().

◆ nonzero_winding_deep_nest_test()

template<typename T>
void blender::meshintersect::nonzero_winding_deep_nest_test ( )

Stress test: deeply nested shapes with alternating winding. Tests winding accumulation through many nesting levels.

Geometry (5 nested squares, alternating CCW/CW):
+-------------------+ Square 0 (CCW, +1)
| +---------------+ | Square 1 (CW, -1)
| | +-----------+ | | Square 2 (CCW, +1)
| | | +-------+ | | | Square 3 (CW, -1)
| | | | +---+ | | | | Square 4 (CCW, +1)
| | | | | | | | | |
| | | | +---+ | | | |
| | | +-------+ | | |
| | +-----------+ | |
| +---------------+ |
+-------------------+
  • Square 0: (0,0)-(10,10) CCW (+1).
  • Square 1: (1,1)-(9,9) CW (-1).
  • Square 2: (2,2)-(8,8) CCW (+1).
  • Square 3: (3,3)-(7,7) CW (-1).
  • Square 4: (4,4)-(6,6) CCW (+1).

Winding at innermost region: +1-1+1-1+1 = +1 (inside).

Even-odd: alternating inside/outside (5 crossings = inside). Non-zero: all layers with non-zero winding are inside.

Definition at line 1768 of file BLI_delaunay_2d_test.cc.

References blender::CDT_INSIDE_WITH_HOLES, blender::CDT_INSIDE_WITH_HOLES_NONZERO, delaunay_2d_calc(), DO_DRAW, blender::meshintersect::CDT_result< T >::edge, blender::EXPECT_EQ(), blender::meshintersect::CDT_result< T >::face, fill_input_from_string(), graph_draw(), blender::gpu::shader::metadata::in, nonzero_winding_high_count_test(), and blender::meshintersect::CDT_result< T >::vert.

Referenced by nonzero_winding_negative_only_test().

◆ nonzero_winding_edge_split_test()

template<typename T>
void blender::meshintersect::nonzero_winding_edge_split_test ( )

Stress test: edge split propagation. Tests that winding is correctly propagated when edges are split by intersection points.

Geometry: Two overlapping rectangles where one edge crosses through
the middle of another's edge, forcing edge splits.
4-------5 y=2
| |
0---+-------+---1 y=1
| | | |
| | | |
3---+-------+---2 y=-1
| |
7-------6 y=-2

Face 0: (0,1)-(2,1)-(2,-1)-(0,-1) - wide rectangle, CCW Face 1: (0.5,2)-(1.5,2)-(1.5,-2)-(0.5,-2) - tall rectangle, CCW

The edges of face 1 cross through face 0's top and bottom edges, causing splits at the + marks. Winding must propagate correctly through splits.

Definition at line 1610 of file BLI_delaunay_2d_test.cc.

References graph_draw().

◆ nonzero_winding_exact_shared_edge_test()

template<typename T>
void blender::meshintersect::nonzero_winding_exact_shared_edge_test ( )

Stress test: exactly shared edge used by 3 triangles. Three triangles that literally use the same two vertex indices (0,1) for one edge.

Geometry:
2 (1,2)
/ \
/ \
/ 4 \ 4=(1,1) inside upper triangle
/ (1,1) \
0---------1 0=(0,0), 1=(2,0)
\ /
\ /
\ /
\ /
3 (1,-2)
  • Face 0: 0,1,2 is the large triangle apex up, CCW.
  • Face 1: 0,1,4 is the small triangle apex up (inside face 0), CCW.
  • Face 2: 0,1,3 is the triangle apex down, CCW.

Edge 0->1 is used by all 3 faces:

  • Face 0: 0->1 in CCW order gives +1.
  • Face 1: 0->1 in CCW order gives +1.
  • Face 2: 0->1 in CCW order gives +1. Total winding on edge 0->1 is +3.

Faces 0 and 1 overlap (1 is inside 0), face 2 is separate.

Definition at line 2189 of file BLI_delaunay_2d_test.cc.

References blender::CDT_INSIDE_WITH_HOLES, delaunay_2d_calc(), DO_DRAW, fill_input_from_string(), graph_draw(), and blender::gpu::shader::metadata::in.

◆ nonzero_winding_fan_test()

template<typename T>
void blender::meshintersect::nonzero_winding_fan_test ( )

Stress test: fan of triangles around a central vertex. Tests complex topology where multiple edges radiate from a single point.

Geometry (4 triangles in a fan, all sharing center vertex 0):
2
/|\
/ | \
/ | \
3---0---1
\ | /
\ | /
\|/
4

Faces (all CCW):

  • Face 0: 0,1,2 (right-top).
  • Face 1: 0,2,3 (left-top).
  • Face 2: 0,3,4 (left-bottom).
  • Face 3: 0,4,1 (right-bottom).

Each edge from center is shared by 2 adjacent faces with opposite traversal:

  • Edge 0-1: Face 0 (0->1, +1), Face 3 (1->0, -1) gives net 0.
  • Edge 0-2: Face 1 (0->2, +1), Face 0 (2->0, -1) gives net 0.
  • And so on for other edges.

This creates interesting winding behavior where the center edges have zero net winding because adjacent triangles traverse them oppositely.

Definition at line 1557 of file BLI_delaunay_2d_test.cc.

References blender::CDT_INSIDE_WITH_HOLES, blender::CDT_INSIDE_WITH_HOLES_NONZERO, delaunay_2d_calc(), DO_DRAW, blender::meshintersect::CDT_result< T >::edge, blender::meshintersect::CDT_result< T >::face, fill_input_from_string(), graph_draw(), blender::gpu::shader::metadata::in, nonzero_winding_multi_face_edge_mixed_test(), and blender::meshintersect::CDT_result< T >::vert.

◆ nonzero_winding_high_count_test()

template<typename T>
void blender::meshintersect::nonzero_winding_high_count_test ( )

Stress test: high winding count with 6 faces sharing an edge. Tests that winding accumulation handles large values correctly.

Geometry (6 stacked rectangles, all CCW):
13--------12 y=6 Face 5
| |
11--------10 y=5 Face 4
| |
9---------8 y=4 Face 3
| |
7---------6 y=3 Face 2
| |
5---------4 y=2 Face 1
| |
3---------2 y=1 Face 0
| |
0---------1 y=0
x=0,3

The bottom edge (0,0)->(3,0) has winding = +6.

Winding by y-band (all positive, all inside for non-zero): bands [0,1]: 6, [1,2]: 5, [2,3]: 4, [3,4]: 3, [4,5]: 2, [5,6]: 1.

Even-odd: alternating inside/outside (odd crossings = inside).

Definition at line 1494 of file BLI_delaunay_2d_test.cc.

Referenced by nonzero_winding_deep_nest_test().

◆ nonzero_winding_island_in_hole_test()

template<typename T>
void blender::meshintersect::nonzero_winding_island_in_hole_test ( )

Stress test: opposing faces creating an island inside a hole. Tests winding cancellation and re-addition.

Geometry:
3-----------------------2 Face 0 (CCW, outer)
| |
| 4---------------7 | Face 1 (CW, hole)
| | | |
| | 8-------9 | | Face 2 (CCW, island)
| | | | | |
| | 11------10 | |
| | | |
| 5---------------6 |
| |
0-----------------------1
  • Face 0: (0,0)-(6,0)-(6,6)-(0,6) CCW is the outer boundary.
  • Face 1: (1,1)-(1,5)-(5,5)-(5,1) CW is the hole (cancels outer).
  • Face 2: (2,2)-(4,2)-(4,4)-(2,4) CCW is the island inside hole (re-adds winding).

Winding:

  • Outer band has winding +1 (inside).
  • Hole band has winding +1-1 = 0 (outside).
  • Island has winding +1-1+1 = +1 (inside).

This pattern is common in font glyphs with counter-shapes.

Definition at line 1888 of file BLI_delaunay_2d_test.cc.

References graph_draw().

Referenced by crosssegs_test().

◆ nonzero_winding_many_crossings_test()

template<typename T>
void blender::meshintersect::nonzero_winding_many_crossings_test ( )

Stress test: ray casting through many constrained edges. Tests the ray-casting accumulation in detect_holes() with many edge crossings.

Geometry: 5 separate non-overlapping vertical strips.
A horizontal ray must cross multiple constrained edges.
Strip 0 Strip 1 Strip 2 Strip 3 Strip 4
+--+ +--+ +--+ +--+ +--+
| | | | | | | | | |
| | | | | | | | | |
+--+ +--+ +--+ +--+ +--+
x=0-1 x=2-3 x=4-5 x=6-7 x=8-9
CCW CW CCW CW CCW

Strips have alternating CCW/CW orientation due to vertex ordering. Since they don't overlap, each strip is independently "inside" for both even-odd and non-zero rules (winding +/-1 != 0). Tests that ray casting correctly handles many separate regions.

Definition at line 2007 of file BLI_delaunay_2d_test.cc.

References blender::CDT_INSIDE_WITH_HOLES, delaunay_2d_calc(), DO_DRAW, fill_input_from_string(), graph_draw(), and blender::gpu::shader::metadata::in.

Referenced by twoface_test().

◆ nonzero_winding_multi_face_edge_mixed_test()

template<typename T>
void blender::meshintersect::nonzero_winding_multi_face_edge_mixed_test ( )

Same geometry as MultiFaceEdge but with mixed winding directions to test cancellation. Face 0: CCW (+1), Face 1: CW (-1), Face 2: CCW (+1).

Geometry (same as MultiFaceEdge):
7---------6 y=3 Face 2 (CCW)
| |
5---------4 y=2 Face 1 (CW - reversed!)
| |
3---------2 y=1 Face 0 (CCW)
| |
0---------1 y=0
x=0,3

Edge windings:

  • Bottom (0,0)->(3,0): +1 - 1 + 1 = +1.
  • Edge (3,0)->(3,1): +1 - 1 + 1 = +1.
  • Edge (3,1)->(3,2): -1 + 1 = 0 (key difference).
  • Edge (3,2)->(3,3): +1.

With mixed winding, the middle band [1,2] has edges with zero net winding, so it behaves differently than the all-CCW case. This tests that winding accumulation correctly handles cancellation from opposite-wound faces.

Definition at line 1322 of file BLI_delaunay_2d_test.cc.

Referenced by nonzero_winding_fan_test().

◆ nonzero_winding_multi_face_edge_test()

template<typename T>
void blender::meshintersect::nonzero_winding_multi_face_edge_test ( )

Stress test for non-zero winding with edges explicitly shared by 3+ faces. Three overlapping rectangles that share bottom edge and overlapping side edges.

Geometry:
7---------6 y=3
| |
5---------4 y=2
| |
3---------2 y=1
| |
0---------1 y=0
x=0,3

Faces (all CCW):

  • Face 0: 0,1,2,3 is the bottom rectangle with height 1.
  • Face 1: 0,1,4,5 is the middle rectangle with height 2.
  • Face 2: 0,1,6,7 is the tall rectangle with height 3.

Shared edges with winding contributions:

  • Edge (0,0)->(3,0) [bottom]: Faces 0,1,2 all traverse left->right giving winding +3.
  • Edge (3,0)->(3,1): Faces 0,1,2 all traverse up giving winding +3.
  • Edge (3,1)->(3,2): Faces 1,2 traverse up giving winding +2.
  • Edge (3,2)->(3,3): Only face 2 traverses this edge giving winding +1.
  • Similarly for left edges going down.

Regions by y-band:

  • [0,1]: All 3 faces overlap.
  • [1,2]: Faces 1,2 overlap.
  • [2,3]: Only face 2.

Even-odd rule: [0,1]=3 crossings=inside, [1,2]=2=outside, [2,3]=1=inside Non-zero rule: all regions have winding>0, all inside

Definition at line 1226 of file BLI_delaunay_2d_test.cc.

◆ nonzero_winding_negative_only_test()

template<typename T>
void blender::meshintersect::nonzero_winding_negative_only_test ( )

Stress test: all faces with negative winding (all CW). Tests that negative winding values are correctly treated as "inside" by the non-zero rule (any non-zero winding = inside).

Geometry: 3 overlapping rectangles, all CW (clockwise).
7---------6 y=3 Face 2 (CW, -1)
| |
5---------4 y=2 Face 1 (CW, -1)
| |
3---------2 y=1 Face 0 (CW, -1)
| |
0---------1 y=0
x=0,3
  • Face 0: (0,0)-(3,1) CW gives winding -1.
  • Face 1: (0,0)-(3,2) CW gives winding -1.
  • Face 2: (0,0)-(3,3) CW gives winding -1.

Winding by y-band (all negative):

  • [0,1]: -3 (all 3 overlap).
  • [1,2]: -2 (faces 1,2 overlap).
  • [2,3]: -1 (face 2 only).

Non-zero rule: all bands have winding != 0, so all are inside. Even-odd rule: alternating inside/outside.

Definition at line 2069 of file BLI_delaunay_2d_test.cc.

References nonzero_winding_deep_nest_test().

◆ nonzero_winding_nested_test()

◆ nonzero_winding_nested_union_test()

template<typename T>
void blender::meshintersect::nonzero_winding_nested_union_test ( )

Outer square with a hole, and two overlapping filled squares inside the hole. Tests union behavior: the two inner CCW squares should union together.

Geometry:
3---------------------------------2 y=4
| |
| 5-------------------------6 | y=3.5
| | | |
| | 15-----------14 | | y=3
| | | | | |
| | 11---+-------10 | | | y=2.5
| | | | overlap| | | |
| | | 12-------+---13 | | y=1.5
| | | | | |
| | 8------------9 | | y=1
| | | |
| 4-------------------------7 | y=0.5
| |
0---------------------------------1 y=0
x=0 .5 1 1.5 2.5 3 3.5 4
  • Face 0 (verts 0,1,2,3): Outer boundary (0,0)-(4,4) CCW gives winding +1.
  • Face 1 (verts 4,5,6,7): Hole (0.5,0.5)-(3.5,3.5) CW gives winding -1.
  • Face 2 (verts 8,9,10,11): Inner1 (1,1)-(2.5,2.5) CCW gives winding +1.
  • Face 3 (verts 12,13,14,15): Inner2 (1.5,1.5)-(3,3) CCW gives winding +1.

Winding by region:

  • Outer band (between face 0 and face 1): +1 (filled).
  • Hole band (inside face 1, outside inners): +1-1 = 0 (empty).
  • Inner1 only region: +1-1+1 = +1 (filled).
  • Inner2 only region: +1-1+1 = +1 (filled).
  • Overlap region (both inners): +1-1+1+1 = +2 (filled for non-zero, hole for even-odd).

Even-odd: overlap has 4 crossings (outer, hole, inner1, inner2) which is outside. Non-zero: overlap has winding +2 which is inside, so inner squares union together.

Definition at line 1157 of file BLI_delaunay_2d_test.cc.

References blender::CDT_INSIDE_WITH_HOLES, delaunay_2d_calc(), blender::EXPECT_EQ(), EXPECT_NE, fill_input_from_string(), get_orig_index(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.

◆ nonzero_winding_self_intersect_test()

template<typename T>
void blender::meshintersect::nonzero_winding_self_intersect_test ( )

Stress test: self-intersecting polygon (figure-8 / bow-tie shape). Tests how winding is computed for a single face that crosses itself.

Geometry (bowtie/figure-8 shape):
2-----------1
\ /
\ /
\ /
\ /
\ /
X (self-intersection at origin)
/ \
/ \
/ \
/ \
/ \
0-----------3

Face 0: 0,1,2,3 forming a bow-tie where edges 0->1 and 2->3 cross. Vertices: 0=(-1,-1), 1=(1,1), 2=(-1,1), 3=(1,-1) Edge 0->1: (-1,-1) to (1,1) - diagonal up-right Edge 2->3: (-1,1) to (1,-1) - diagonal down-right, crosses edge 0->1

The self-intersection creates two triangular regions.

Definition at line 1671 of file BLI_delaunay_2d_test.cc.

References blender::CDT_INSIDE_WITH_HOLES, blender::CDT_INSIDE_WITH_HOLES_NONZERO, delaunay_2d_calc(), DO_DRAW, blender::meshintersect::CDT_result< T >::edge, blender::EXPECT_EQ(), EXPECT_LT, blender::meshintersect::CDT_result< T >::face, fill_input_from_string(), graph_draw(), blender::gpu::shader::metadata::in, nonzero_winding_cancel_to_zero_test(), and blender::meshintersect::CDT_result< T >::vert.

◆ nonzero_winding_shared_subsegment_test()

template<typename T>
void blender::meshintersect::nonzero_winding_shared_subsegment_test ( )

Stress test: partial overlap with shared subsegment. Tests winding on a subsegment of larger edges after intersection splitting.

Geometry (3 overlapping rectangles):
7-------------6 y=2
| |
3------+------11-----+------2------10 y=1
| | | | | |
0------4------8------5------1------9 y=0
x=0 x=1 x=2 x=3 x=4 x=5
Face 0 (verts 0,1,2,3): x=0 to x=4, y=0 to y=1
Face 1 (verts 4,5,6,7): x=1 to x=3, y=0 to y=2
Face 2 (verts 8,9,10,11): x=2 to x=5, y=0 to y=1
  • Face 0: (0,0)-(4,0)-(4,1)-(0,1) is a wide rectangle.
  • Face 1: (1,0)-(3,0)-(3,2)-(1,2) is a tall rectangle that shares part of bottom edge.
  • Face 2: (2,0)-(5,0)-(5,1)-(2,1) is a wide rectangle that shares part of bottom edge.

The segment (2,0)-(3,0) is part of all 3 faces' bottom edges. After CDT processes intersections, this subsegment should have winding +3.

Definition at line 1824 of file BLI_delaunay_2d_test.cc.

References blender::EXPECT_EQ(), and EXPECT_LT.

◆ nonzero_winding_test()

◆ nonzero_winding_tjunction_test()

template<typename T>
void blender::meshintersect::nonzero_winding_tjunction_test ( )

Stress test: overlapping rectangles with shared collinear edge segment. Tests winding when one face's edge is a sub-segment of another's edge.

Geometry:
Face 0: Large rectangle (0,0)-(4,2) CCW - vertices 0,1,2,3
Face 1: Small rectangle (1,0)-(3,1) CCW - vertices 4,5,6,7
0-----------------1 y=2
| |
| 4-----5 | y=1
| | | |
3-----7-----6-----2 y=0
^ ^
(1,0) (3,0)

Face 1's bottom edge (1,0)-(3,0) lies on Face 0's bottom edge (0,0)-(4,0). This creates shared collinear segments where Face 0's edge is split. Face 1 is entirely inside Face 0, creating an overlap region (1,0)-(3,1).

Definition at line 2124 of file BLI_delaunay_2d_test.cc.

References blender::CDT_INSIDE_WITH_HOLES, delaunay_2d_calc(), DO_DRAW, fill_input_from_string(), graph_draw(), and blender::gpu::shader::metadata::in.

◆ onept_test()

◆ operator<<() [1/5]

◆ operator<<() [2/5]

◆ operator<<() [3/5]

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

◆ operator<<() [4/5]

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

Definition at line 479 of file delaunay_2d.cc.

References operator<<().

◆ operator<<() [5/5]

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

◆ 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,
uint32_t in_edge_index )

◆ 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,
uint32_t in_face_index )

◆ output_uses_evenodd_holes()

bool blender::meshintersect::output_uses_evenodd_holes ( const CDT_output_type output_type)
inlinestatic

Output types that use the even-odd hole detector.

Definition at line 426 of file delaunay_2d.cc.

References blender::CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, blender::CDT_INSIDE_WITH_HOLES, ELEM, and output_uses_evenodd_holes().

Referenced by delaunay_calc(), output_uses_evenodd_holes(), and prepare_cdt_for_output().

◆ output_uses_nonzero_holes()

bool blender::meshintersect::output_uses_nonzero_holes ( const CDT_output_type output_type)
inlinestatic

Output types that use the non-zero winding hole detector, requiring edge_winding_map to be populated during construction.

Definition at line 435 of file delaunay_2d.cc.

References blender::CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES_NONZERO, blender::CDT_INSIDE_WITH_HOLES_NONZERO, ELEM, and output_uses_nonzero_holes().

Referenced by delaunay_calc(), output_uses_nonzero_holes(), and prepare_cdt_for_output().

◆ output_vert_is_intersection_and_has_edge_input_ids()

template<typename T>
bool blender::meshintersect::output_vert_is_intersection_and_has_edge_input_ids ( const CDT_result< T > & out,
int out_vert_index,
int in_edge1_index,
int in_edge2_index )

◆ overlapfaces_test()

template<typename T>
void blender::meshintersect::overlapfaces_test ( )

◆ power_of_10_greater_equal_to()

uint32_t blender::meshintersect::power_of_10_greater_equal_to ( uint32_t x)
static

◆ prepare_cdt_for_output()

◆ prev()

◆ quad0_test()

template<typename T>
void blender::meshintersect::quad0_test ( )

◆ quad1_test()

template<typename T>
void blender::meshintersect::quad1_test ( )

Definition at line 551 of file BLI_delaunay_2d_test.cc.

◆ quad2_test()

template<typename T>
void blender::meshintersect::quad2_test ( )

◆ quad3_test()

◆ quad4_test()

◆ 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 1645 of file delaunay_2d.cc.

References blender::meshintersect::CDTArrangement< T >::add_diagonal(), b, blender::BMVert::co, blender::meshintersect::CDTVert< T >::co, 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, blender::v, and blender::meshintersect::SymEdge< T >::vert.

Referenced by add_edge_constraint(), and re_delaunay_triangulate().

◆ remove_faces_in_holes()

◆ remove_non_constraint_edges()

template<typename T>
void blender::meshintersect::remove_non_constraint_edges ( CDT_state< T > * cdt_state)

◆ 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,
const bool use_hole_status )

◆ remove_outer_edges_until_constraints()

◆ repeatedge_test()

template<typename T>
void blender::meshintersect::repeatedge_test ( )

Definition at line 2687 of file BLI_delaunay_2d_test.cc.

References nonzero_winding_concave_outer_test().

◆ repeattri_test()

◆ sename()

template<typename T>
std::string blender::meshintersect::sename ( const SymEdge< T > * se)

Definition at line 460 of file delaunay_2d.cc.

References sename(), and trunc_ptr().

Referenced by cdt_draw(), and sename().

◆ shared_split_boundary_test()

template<typename T>
void blender::meshintersect::shared_split_boundary_test ( )

◆ short_se_dump()

template<typename T>
std::string blender::meshintersect::short_se_dump ( const SymEdge< T > * se)

◆ 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 1313 of file delaunay_2d.cc.

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

Referenced by initial_triangulation(), and site_lexicographic_sort().

◆ square_o_test()

◆ stale_symedge_before_remove_faces_in_holes_test()

template<typename T>
void blender::meshintersect::stale_symedge_before_remove_faces_in_holes_test ( )

A single self-intersecting 7-sided polygon (one repeated vertex) plus two stray points that don't belong to a face, needed_ids = 0, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES. remove_faces_in_holes crashed on a symedge invalidated by an earlier dissolve pass, see: #160787.

Definition at line 2930 of file BLI_delaunay_2d_test.cc.

◆ sym()

◆ TEST() [1/66]

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

Definition at line 3182 of file BLI_delaunay_2d_test.cc.

◆ TEST() [2/66]

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

Definition at line 3187 of file BLI_delaunay_2d_test.cc.

◆ TEST() [3/66]

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

Definition at line 3082 of file BLI_delaunay_2d_test.cc.

◆ TEST() [4/66]

◆ TEST() [5/66]

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

◆ TEST() [6/66]

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

◆ TEST() [7/66]

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

Definition at line 3267 of file BLI_delaunay_2d_test.cc.

◆ TEST() [8/66]

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

◆ TEST() [9/66]

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

Definition at line 3002 of file BLI_delaunay_2d_test.cc.

◆ TEST() [10/66]

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

◆ TEST() [11/66]

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

◆ TEST() [12/66]

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

◆ TEST() [13/66]

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

Definition at line 3297 of file BLI_delaunay_2d_test.cc.

◆ TEST() [14/66]

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

Definition at line 3292 of file BLI_delaunay_2d_test.cc.

◆ TEST() [15/66]

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

Definition at line 3312 of file BLI_delaunay_2d_test.cc.

References diamondinsquarewire_test().

◆ TEST() [16/66]

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

Definition at line 3317 of file BLI_delaunay_2d_test.cc.

◆ TEST() [17/66]

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

Definition at line 3322 of file BLI_delaunay_2d_test.cc.

◆ TEST() [18/66]

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

◆ TEST() [19/66]

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

◆ TEST() [20/66]

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

◆ TEST() [21/66]

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

◆ TEST() [22/66]

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

◆ TEST() [23/66]

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

◆ TEST() [24/66]

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

Definition at line 3262 of file BLI_delaunay_2d_test.cc.

◆ TEST() [25/66]

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

Definition at line 3202 of file BLI_delaunay_2d_test.cc.

References twofaceedgeoverlap_test().

◆ TEST() [26/66]

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

◆ TEST() [27/66]

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

◆ TEST() [28/66]

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

Definition at line 3087 of file BLI_delaunay_2d_test.cc.

◆ TEST() [29/66]

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

◆ TEST() [30/66]

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

◆ TEST() [31/66]

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

Definition at line 3177 of file BLI_delaunay_2d_test.cc.

References twosquaresoverlap_test().

◆ TEST() [32/66]

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

◆ TEST() [33/66]

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

◆ TEST() [34/66]

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

Definition at line 3172 of file BLI_delaunay_2d_test.cc.

References DO_DRAW, and graph_draw().

◆ TEST() [35/66]

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

◆ TEST() [36/66]

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

◆ TEST() [37/66]

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

Definition at line 3147 of file BLI_delaunay_2d_test.cc.

References DO_DRAW, blender::EXPECT_EQ(), and graph_draw().

◆ TEST() [38/66]

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

◆ TEST() [39/66]

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

◆ TEST() [40/66]

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

◆ TEST() [41/66]

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

Definition at line 3162 of file BLI_delaunay_2d_test.cc.

◆ TEST() [42/66]

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

Definition at line 3092 of file BLI_delaunay_2d_test.cc.

◆ TEST() [43/66]

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

Definition at line 3097 of file BLI_delaunay_2d_test.cc.

◆ TEST() [44/66]

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

◆ TEST() [45/66]

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

Definition at line 3142 of file BLI_delaunay_2d_test.cc.

References graph_draw(), and blender::gpu::shader::metadata::out.

◆ TEST() [46/66]

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

Definition at line 3167 of file BLI_delaunay_2d_test.cc.

References graph_draw().

◆ TEST() [47/66]

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

Definition at line 3007 of file BLI_delaunay_2d_test.cc.

References twoface2_test().

◆ TEST() [48/66]

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

◆ TEST() [49/66]

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

◆ TEST() [50/66]

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

◆ TEST() [51/66]

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

◆ TEST() [52/66]

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

◆ TEST() [53/66]

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

◆ TEST() [54/66]

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

Definition at line 3272 of file BLI_delaunay_2d_test.cc.

◆ TEST() [55/66]

◆ TEST() [56/66]

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

◆ TEST() [57/66]

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

Definition at line 3287 of file BLI_delaunay_2d_test.cc.

References diamondinsquare_test().

◆ TEST() [58/66]

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

◆ TEST() [59/66]

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

◆ TEST() [60/66]

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

◆ TEST() [61/66]

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

◆ TEST() [62/66]

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

Definition at line 3207 of file BLI_delaunay_2d_test.cc.

◆ TEST() [63/66]

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

◆ TEST() [64/66]

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

Definition at line 3227 of file BLI_delaunay_2d_test.cc.

◆ TEST() [65/66]

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

Definition at line 3012 of file BLI_delaunay_2d_test.cc.

◆ TEST() [66/66]

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

◆ threept_test()

template<typename T>
void blender::meshintersect::threept_test ( )

◆ tri_orient()

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

◆ triintri_test()

template<typename T>
void blender::meshintersect::triintri_test ( )

◆ trunc_ptr()

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

Definition at line 452 of file delaunay_2d.cc.

References POINTER_AS_INT, and trunc_ptr().

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

◆ twodiamondscross_test()

◆ twoface2_test()

template<typename T>
void blender::meshintersect::twoface2_test ( )

◆ twoface_test()

template<typename T>
void blender::meshintersect::twoface_test ( )

Definition at line 2398 of file BLI_delaunay_2d_test.cc.

References nonzero_winding_many_crossings_test().

◆ twofaceedgeoverlap_test()

template<typename T>
void blender::meshintersect::twofaceedgeoverlap_test ( )

Definition at line 2592 of file BLI_delaunay_2d_test.cc.

Referenced by TEST().

◆ twopt_test()

template<typename T>
void blender::meshintersect::twopt_test ( )

Definition at line 459 of file BLI_delaunay_2d_test.cc.

◆ twosquaresoverlap_test()

template<typename T>
void blender::meshintersect::twosquaresoverlap_test ( )

◆ vert_left_of_symedge()

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

◆ vert_right_of_symedge()

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

◆ vert_touches_face()

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

◆ vertname()

template<typename T>
std::string blender::meshintersect::vertname ( const CDTVert< T > * v)

Definition at line 444 of file delaunay_2d.cc.

References blender::v, and vertname().

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

Variable Documentation

◆ DO_DRAW

◆ draw_append

bool blender::meshintersect::draw_append = false
static

Definition at line 289 of file BLI_delaunay_2d_test.cc.

Referenced by graph_draw().

◆ USE_POW10_FACE_EDGE_OFFSET_ROUND_UP

bool blender::meshintersect::USE_POW10_FACE_EDGE_OFFSET_ROUND_UP = false
staticconstexpr

Use a power of 10 for the face_edge_offset for easier debugging of encoded edge IDs. Disabled because rounding up can add considerable overhead to the per-face encoding space, reducing the number of faces that fit before overflow (see #153708).

Definition at line 40 of file delaunay_2d.cc.

Referenced by add_face_constraints().

◆ VISIT_INDEX_OUTER_FACE

int blender::meshintersect::VISIT_INDEX_OUTER_FACE = -2
staticconstexpr

◆ VISIT_INDEX_UNVISITED

int blender::meshintersect::VISIT_INDEX_UNVISITED = -1
staticconstexpr