|
Blender V5.3
|
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 > ®ion_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 |
| 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().
| 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().
| 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().
| 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().
| 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().
|
static |
Definition at line 980 of file delaunay_2d.cc.
References add_list_to_input_ids(), blender::VectorSet< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add_multiple(), and blender::VectorSet< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::as_span().
Referenced by blender::meshintersect::CDTArrangement< T >::add_diagonal(), add_list_to_input_ids(), and blender::meshintersect::CDTArrangement< T >::split_edge().
|
static |
Definition at line 974 of file delaunay_2d.cc.
References blender::VectorSet< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add(), add_to_input_ids(), blender::Core, and PRF_scope.
Referenced by add_edge_constraint(), add_face_ids(), add_to_input_ids(), and get_cdt_output().
| void blender::meshintersect::cdt_draw | ( | const std::string & | label, |
| const CDTArrangement< T > & | cdt ) |
Definition at line 556 of file delaunay_2d.cc.
References cdt_draw(), blender::BMVert::co, blender::meshintersect::CDTVert< T >::co, blender::meshintersect::CDTFace< T >::deleted, blender::e, blender::meshintersect::CDTArrangement< T >::edges, blender::meshintersect::SymEdge< T >::face, blender::meshintersect::CDTArrangement< T >::faces, blender::meshintersect::CDTFace< T >::input_ids, blender::math::min_max(), blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, scale(), sename(), blender::VectorSet< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::size(), SX, SY, trunc_ptr(), blender::v, blender::meshintersect::SymEdge< T >::vert, vertname(), and blender::meshintersect::CDTArrangement< T >::verts.
Referenced by cdt_draw(), and dc_tri().
| void blender::meshintersect::crosssegs_test | ( | ) |
Definition at line 2252 of file BLI_delaunay_2d_test.cc.
References nonzero_winding_island_in_hole_test().
| void blender::meshintersect::cutacrosstri_test | ( | ) |
Definition at line 2284 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.
| 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().
| 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 1376 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(), blender::BLI_assert(), cdt_draw(), blender::BMVert::co, blender::meshintersect::CDTVert< T >::co, blender::meshintersect::CDTArrangement< T >::connect_separate_parts(), blender::Core, 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, blender::meshintersect::CDTArrangement< T >::outer_face, PRF_scope, blender::meshintersect::SymEdge< T >::rot, sym(), blender::meshintersect::CDTEdge< T >::symedges, blender::v2, blender::meshintersect::SymEdge< T >::vert, vert_left_of_symedge(), and vert_right_of_symedge().
Referenced by dc_tri(), and dc_triangulate().
|
inline |
Definition at line 1364 of file delaunay_2d.cc.
References dc_tri_valid(), filtered_orient2d(), blender::meshintersect::SymEdge< T >::next, and blender::meshintersect::SymEdge< T >::vert.
Referenced by dc_tri(), and dc_tri_valid().
| 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().
| template CDT_result< double > blender::meshintersect::delaunay_2d_calc | ( | const CDT_input< double > & | , |
| CDT_output_type | ) |
References delaunay_2d_calc().
| CDT_result< T > blender::meshintersect::delaunay_2d_calc | ( | const CDT_input< T > & | input, |
| CDT_output_type | output_type ) |
Definition at line 3406 of file delaunay_2d.cc.
References delaunay_2d_calc(), and delaunay_calc().
Referenced by cutacrosstri_test(), delaunay_2d_calc(), delaunay_2d_calc(), disjoint_polys_in_large_hull_test(), blender::displist_fill_cdt_process_group(), empty_test(), even_odd_coincident_polygons_needed_ids_stable_test(), fill_curve_degenerate_interior_faces_test(), blender::io::obj::fixup_invalid_face(), fuzz_repro_minimize_test1(), intersection_simple_edge_ids_test(), lineholeinsquare_test(), looping_back_2x_test(), blender::M_Geometry_delaunay_2d_cdt(), blender::maskrasterize_layer_init_cdt(), nestedholes_test(), nonzero_winding_coincident_verts_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(), TEST(), TEST(), triintri_test(), twodiamondscross_test(), twoface2_test(), and twosquaresoverlap_test().
| CDT_result< T > blender::meshintersect::delaunay_calc | ( | const CDT_input< T > & | input, |
| CDT_output_type | output_type ) |
Definition at line 3368 of file delaunay_2d.cc.
References add_edge_constraints(), add_face_constraints(), add_input_verts(), blender::BLI_assert(), blender::meshintersect::CDT_state< T >::cdt, blender::CDT_CONSTRAINTS, blender::CDT_FULL, blender::CDT_INSIDE, blender::Core, delaunay_calc(), blender::meshintersect::CDT_input< T >::edge, blender::meshintersect::CDT_state< T >::edge_winding_map, ELEM, blender::meshintersect::CDT_input< T >::epsilon, blender::meshintersect::CDT_input< T >::face_offsets, get_cdt_output(), initial_triangulation(), blender::meshintersect::CDT_input< T >::needed_ids, output_uses_evenodd_holes(), output_uses_nonzero_holes(), blender::meshintersect::CDT_state< T >::polygon_boundary_count_map, PRF_scope, and blender::meshintersect::CDT_input< T >::vert.
Referenced by delaunay_2d_calc(), and delaunay_calc().
| 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().
| 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().
| void blender::meshintersect::diamondcross_test | ( | ) |
Definition at line 2329 of file BLI_delaunay_2d_test.cc.
References nonzero_winding_coincident_verts_test().
| void blender::meshintersect::diamondinsquare_test | ( | ) |
Definition at line 2659 of file BLI_delaunay_2d_test.cc.
Referenced by TEST().
| void blender::meshintersect::diamondinsquarewire_test | ( | ) |
Definition at line 2673 of file BLI_delaunay_2d_test.cc.
References EXPECT_LT.
Referenced by TEST().
| void blender::meshintersect::disjoint_polys_in_large_hull_test | ( | ) |
Definition at line 970 of file BLI_delaunay_2d_test.cc.
References blender::CDT_INSIDE_WITH_HOLES, blender::CDT_INSIDE_WITH_HOLES_NONZERO, blender::CDT_NO_ORIG_IDS, blender::CDT_ORIG_FACES, delaunay_2d_calc(), DO_DRAW, blender::EXPECT_EQ(), fill_input_from_string(), and graph_draw().
| 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.
| void blender::meshintersect::dissolve_symedge | ( | CDT_state< T > * | cdt_state, |
| SymEdge< T > * | se ) |
Definition at line 2504 of file delaunay_2d.cc.
References blender::meshintersect::CDT_state< T >::cdt, blender::meshintersect::CDTArrangement< T >::delete_edge(), dissolve_symedge(), ELEM, blender::meshintersect::SymEdge< T >::face, blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, prev(), and sym().
Referenced by dissolve_symedge(), remove_non_constraint_edges(), remove_non_constraint_edges_leave_valid_bmesh(), and remove_outer_edges_until_constraints().
| void blender::meshintersect::dump_crossings | ( | const Span< CrossData< T > > | crossings | ) |
Definition at line 1997 of file delaunay_2d.cc.
References dump_crossings(), 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(), and dump_crossings().
| void blender::meshintersect::empty_test | ( | ) |
Definition at line 432 of file BLI_delaunay_2d_test.cc.
References blender::CDT_FULL, delaunay_2d_calc(), empty_test(), blender::EXPECT_EQ(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
Referenced by empty_test().
| void blender::meshintersect::even_odd_boundary_disagreement_test | ( | ) |
Definition at line 784 of file BLI_delaunay_2d_test.cc.
References EXPECT_TRUE, get_output_tri_index(), and output_face_has_input_id().
| void blender::meshintersect::even_odd_coincident_polygons_needed_ids_stable_test | ( | ) |
Definition at line 837 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.
| void blender::meshintersect::even_odd_nested_holes_deep_test | ( | ) |
Definition at line 729 of file BLI_delaunay_2d_test.cc.
|
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().
| void blender::meshintersect::expect_coord_near | ( | const VecBase< T, 2 > & | testco, |
| const VecBase< T, 2 > & | refco ) |
References expect_coord_near(), and blender::EXPECT_EQ().
Referenced by expect_coord_near(), expect_coord_near< double >(), onept_test(), and TEST().
| 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.
| 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().
| 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().
| 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.
| 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.
| 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().
|
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().
| 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 808 of file delaunay_2d.cc.
References blender::meshintersect::FatCo< T >::approx, b, filtered_incircle(), and blender::incircle().
|
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().
| int blender::meshintersect::filtered_orient2d< double > | ( | const FatCo< double > & | a, |
| const FatCo< double > & | b, | ||
| const FatCo< double > & | c ) |
Definition at line 741 of file delaunay_2d.cc.
References blender::meshintersect::FatCo< T >::approx, b, filtered_orient2d(), and blender::orient2d().
| 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().
| 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 1009 of file delaunay_2d.cc.
References find_symedge_between_verts(), blender::meshintersect::SymEdge< T >::next, blender::meshintersect::SymEdge< T >::rot, blender::meshintersect::CDTVert< T >::symedge, and blender::v2.
Referenced by add_edge_constraint(), exists_edge(), and find_symedge_between_verts().
| 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().
| 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().
| void blender::meshintersect::fuzz_repro_minimize_test1 | ( | ) |
Minimized test case found by fuzzing a fix for: #160787.
Definition at line 2948 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.
| 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.
| CDT_result< T > blender::meshintersect::get_cdt_output | ( | CDT_state< T > * | cdt_state, |
| CDT_output_type | output_type ) |
Definition at line 3241 of file delaunay_2d.cc.
References add_to_input_ids(), blender::Array< T, InlineBufferCapacity, Allocator >::Array(), blender::VectorSet< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::as_span(), blender::BLI_assert(), blender::meshintersect::CDT_state< T >::cdt, blender::CDT_INTERSECTED_EDGES, blender::CDT_ORIG_EDGES, blender::CDT_ORIG_FACES, blender::CDT_ORIG_VERTS, blender::BMVert::co, blender::Core, blender::meshintersect::CDTFace< T >::deleted, blender::e, blender::meshintersect::CDTArrangement< T >::edges, blender::meshintersect::CDT_state< T >::face_edge_offset, blender::meshintersect::CDTArrangement< T >::faces, get_cdt_output(), blender::meshintersect::CDTFace< T >::input_ids, is_deleted_edge(), blender::meshintersect::CDT_state< T >::needed_ids, blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, prepare_cdt_for_output(), PRF_scope, blender::result, blender::meshintersect::CDTFace< T >::symedge, blender::v, blender::meshintersect::SymEdge< T >::vert, and blender::meshintersect::CDTArrangement< T >::verts.
Referenced by delaunay_calc(), and get_cdt_output().
| 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().
| 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().
|
static |
Definition at line 112 of file BLI_delaunay_2d_test.cc.
References get_orig_index().
Referenced by even_odd_coincident_polygons_needed_ids_stable_test(), fill_curve_letter_b_test(), get_orig_index(), intersection_simple_edge_ids_test(), nonzero_winding_nested_union_test(), quad0_test(), square_o_test(), TEST(), TEST(), and TEST().
| int blender::meshintersect::get_output_edge_index | ( | const CDT_result< T > & | out, |
| int | out_index_1, | ||
| int | out_index_2 ) |
Definition at line 175 of file BLI_delaunay_2d_test.cc.
References get_output_edge_index(), and blender::gpu::shader::metadata::out.
Referenced by fill_curve_letter_b_test(), get_output_edge_index(), lineholeinsquare_test(), quad0_test(), quad2_test(), quad3_test(), quad4_test(), square_o_test(), TEST(), TEST(), and TEST().
| int blender::meshintersect::get_output_face_index | ( | const CDT_result< T > & | out, |
| const Array< int > & | poly ) |
Definition at line 210 of file BLI_delaunay_2d_test.cc.
References get_output_face_index(), blender::gpu::shader::metadata::out, and blender::Array< T, InlineBufferCapacity, Allocator >::size().
Referenced by get_output_face_index(), and get_output_tri_index().
| 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 234 of file BLI_delaunay_2d_test.cc.
References get_output_face_index(), get_output_tri_index(), and blender::gpu::shader::metadata::out.
Referenced by even_odd_boundary_disagreement_test(), get_output_tri_index(), mixedpts_test(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().
| int blender::meshintersect::get_vertex_by_coord | ( | const CDT_result< T > & | out, |
| double | x, | ||
| double | y ) |
Definition at line 160 of file BLI_delaunay_2d_test.cc.
References blender::e, fabs(), get_vertex_by_coord(), math_to_double(), blender::gpu::shader::metadata::out, blender::x, and y.
Referenced by get_vertex_by_coord(), TEST(), and TEST().
| void blender::meshintersect::graph_draw | ( | const std::string & | label, |
| const Span< VecBase< T, 2 > > | verts, | ||
| const Span< int2 > | edges, | ||
| const Span< Vector< int > > | faces ) |
Definition at line 292 of file BLI_delaunay_2d_test.cc.
References draw_append, blender::e, graph_draw(), math_to_double(), scale(), SX, SY, and blender::v.
Referenced by cutacrosstri_test(), disjoint_polys_in_large_hull_test(), fill_curve_degenerate_interior_faces_test(), fuzz_repro_minimize_test1(), graph_draw(), lineholeinsquare_test(), mixedpts_test(), nestedholes_test(), nonzero_winding_coincident_verts_test(), nonzero_winding_deep_nest_test(), nonzero_winding_edge_split_test(), nonzero_winding_exact_shared_edge_test(), nonzero_winding_fan_test(), nonzero_winding_island_in_hole_test(), nonzero_winding_many_crossings_test(), nonzero_winding_self_intersect_test(), nonzero_winding_tjunction_test(), overlapfaces_test(), quad0_test(), quad2_test(), quad3_test(), quad4_test(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), threept_test(), triintri_test(), twodiamondscross_test(), twoface2_test(), and twosquaresoverlap_test().
|
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().
|
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.
Referenced by get_next_crossing_from_vert(), in_line(), and in_line< double >().
| 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().
| 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().
| void blender::meshintersect::intersection_simple_edge_ids_test | ( | ) |
Definition at line 2971 of file BLI_delaunay_2d_test.cc.
References blender::CDT_FULL, delaunay_2d_calc(), blender::EXPECT_EQ(), fill_input_from_string(), get_orig_index(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| void blender::meshintersect::intersection_squares_edge_ids_test | ( | ) |
Definition at line 2985 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE.
|
inline |
Definition at line 985 of file delaunay_2d.cc.
References blender::e, and is_border_edge().
Referenced by is_border_edge().
|
inline |
Definition at line 990 of file delaunay_2d.cc.
References blender::e, and is_constrained_edge().
Referenced by add_edge_constraint(), detect_holes_with_fillrule_even_odd(), detect_holes_with_fillrule_nonzero(), is_constrained_edge(), remove_faces_in_holes(), remove_non_constraint_edges(), remove_non_constraint_edges_leave_valid_bmesh(), and remove_outer_edges_until_constraints().
Definition at line 995 of file delaunay_2d.cc.
References blender::e, and is_deleted_edge().
Referenced by detect_holes_with_fillrule_even_odd(), detect_holes_with_fillrule_nonzero(), get_cdt_output(), is_deleted_edge(), prepare_cdt_for_output(), remove_non_constraint_edges(), and remove_non_constraint_edges_leave_valid_bmesh().
|
inline |
Definition at line 1000 of file delaunay_2d.cc.
References blender::meshintersect::CDT_state< T >::input_vert_num, is_original_vert(), and blender::v.
Referenced by is_original_vert().
| void blender::meshintersect::lineholeinsquare_test | ( | ) |
Definition at line 642 of file BLI_delaunay_2d_test.cc.
References blender::CDT_FULL, delaunay_2d_calc(), DO_DRAW, blender::EXPECT_EQ(), EXPECT_NE, fill_input_from_string(), get_output_edge_index(), graph_draw(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| void blender::meshintersect::lineinsquare_test | ( | ) |
Definition at line 611 of file BLI_delaunay_2d_test.cc.
| 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.
| 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().
| 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.
| 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.
| void blender::meshintersect::manycross_test | ( | ) |
Definition at line 2383 of file BLI_delaunay_2d_test.cc.
| 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.
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().
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().
| 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.
Definition at line 62 of file delaunay_2d.cc.
References blender::BLI_assert(), math_to_double(), and T.
Referenced by get_vertex_by_coord(), graph_draw(), math_to_double(), and math_to_double< double >().
Definition at line 125 of file BLI_delaunay_2d_test.cc.
References blender::BLI_assert(), math_to_double(), and T.
| 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.
| 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.
| void blender::meshintersect::mixedpts_test | ( | ) |
Definition at line 510 of file BLI_delaunay_2d_test.cc.
References DO_DRAW, blender::EXPECT_EQ(), EXPECT_TRUE, get_output_tri_index(), graph_draw(), and blender::gpu::shader::metadata::out.
| void blender::meshintersect::nestedholes_test | ( | ) |
Definition at line 673 of file BLI_delaunay_2d_test.cc.
References blender::CDT_CONSTRAINTS, delaunay_2d_calc(), DO_DRAW, blender::EXPECT_EQ(), graph_draw(), and blender::gpu::shader::metadata::in.
| 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.
Winding by y-band:
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):
Definition at line 1431 of file BLI_delaunay_2d_test.cc.
References blender::EXPECT_EQ().
Referenced by nonzero_winding_self_intersect_test().
| 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.
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().
| 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().
| void blender::meshintersect::nonzero_winding_deep_nest_test | ( | ) |
Stress test: deeply nested shapes with alternating winding. Tests winding accumulation through many nesting levels.
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().
| 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.
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().
| 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.
Edge 0->1 is used by all 3 faces:
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.
| 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.
Faces (all CCW):
Each edge from center is shared by 2 adjacent faces with opposite traversal:
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.
| 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.
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().
| 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.
Winding:
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().
| 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.
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().
| 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).
Edge windings:
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().
| 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.
Faces (all CCW):
Shared edges with winding contributions:
Regions by y-band:
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.
| 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).
Winding by y-band (all negative):
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().
| void blender::meshintersect::nonzero_winding_nested_test | ( | ) |
Definition at line 1054 of file BLI_delaunay_2d_test.cc.
References blender::CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, blender::CDT_NO_ORIG_IDS, delaunay_2d_calc(), blender::EXPECT_EQ(), fill_input_from_string(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| 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.
Winding by region:
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.
| 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.
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.
| 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.
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.
| void blender::meshintersect::nonzero_winding_test | ( | ) |
Definition at line 1010 of file BLI_delaunay_2d_test.cc.
References blender::CDT_CW_ORIG_FACES, blender::CDT_INSIDE_WITH_HOLES, blender::CDT_ORIG_FACES, cw_orig_face_ids_test(), delaunay_2d_calc(), blender::EXPECT_EQ(), EXPECT_FALSE, EXPECT_TRUE, blender::meshintersect::CDT_result< T >::face, fill_input_from_string(), blender::meshintersect::CDT_input< T >::needed_ids, and output_face_has_input_id().
| 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.
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.
| void blender::meshintersect::onept_test | ( | ) |
Definition at line 445 of file BLI_delaunay_2d_test.cc.
References blender::CDT_FULL, delaunay_2d_calc(), expect_coord_near(), blender::EXPECT_EQ(), fill_input_from_string(), blender::gpu::shader::metadata::in, onept_test(), and blender::gpu::shader::metadata::out.
Referenced by onept_test().
| std::ostream & blender::meshintersect::operator<< | ( | std::ostream & | os, |
| const CDT_result< T > & | r ) |
Definition at line 251 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, operator<<(), blender::meshintersect::CDT_result< T >::vert, and blender::meshintersect::CDT_result< T >::vert_orig.
| std::ostream & blender::meshintersect::operator<< | ( | std::ostream & | os, |
| const CDT_state< T > & | cdt_state ) |
Definition at line 494 of file delaunay_2d.cc.
References blender::meshintersect::CDT_state< T >::cdt, blender::BMVert::co, blender::meshintersect::CDTFace< T >::deleted, blender::e, blender::meshintersect::SymEdge< T >::edge, blender::meshintersect::SymEdge< T >::face, blender::meshintersect::SymEdge< T >::next, operator<<(), blender::meshintersect::SymEdge< T >::rot, sym(), blender::meshintersect::CDTFace< T >::symedge, trunc_ptr(), blender::v, blender::meshintersect::SymEdge< T >::vert, and vertname().
| std::ostream & blender::meshintersect::operator<< | ( | std::ostream & | os, |
| const SymEdge< T > & | se ) |
Definition at line 467 of file delaunay_2d.cc.
References blender::meshintersect::SymEdge< T >::next, operator<<(), blender::meshintersect::SymEdge< T >::vert, and vertname().
| std::ostream & blender::meshintersect::operator<< | ( | std::ostream & | os, |
| const SymEdge< T > * | se ) |
Definition at line 479 of file delaunay_2d.cc.
References operator<<().
| std::ostream & blender::meshintersect::operator<< | ( | std::ostream & | stream, |
| const FatCo< T > & | co ) |
Definition at line 186 of file delaunay_2d.cc.
References blender::meshintersect::FatCo< T >::approx, and operator<<().
Referenced by operator<<(), operator<<(), operator<<(), operator<<(), and operator<<().
| bool blender::meshintersect::output_edge_has_input_id | ( | const CDT_result< T > & | out, |
| int | out_edge_index, | ||
| uint32_t | in_edge_index ) |
Definition at line 201 of file BLI_delaunay_2d_test.cc.
References blender::gpu::shader::metadata::out, and output_edge_has_input_id().
Referenced by output_edge_has_input_id(), quad0_test(), TEST(), TEST(), and TEST().
| bool blender::meshintersect::output_face_has_input_id | ( | const CDT_result< T > & | out, |
| int | out_face_index, | ||
| uint32_t | in_face_index ) |
Definition at line 244 of file BLI_delaunay_2d_test.cc.
References blender::gpu::shader::metadata::out, and output_face_has_input_id().
Referenced by even_odd_boundary_disagreement_test(), looping_back_3x_test(), nonzero_winding_test(), output_face_has_input_id(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().
|
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().
|
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().
| 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 ) |
Definition at line 189 of file BLI_delaunay_2d_test.cc.
References blender::gpu::shader::metadata::out, and output_vert_is_intersection_and_has_edge_input_ids().
Referenced by output_vert_is_intersection_and_has_edge_input_ids().
| void blender::meshintersect::overlapfaces_test | ( | ) |
Definition at line 2501 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.
Definition at line 2344 of file delaunay_2d.cc.
References blender::BLI_assert(), power_of_10_greater_equal_to(), and blender::x.
Referenced by add_face_constraints(), and power_of_10_greater_equal_to().
| 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.
Definition at line 3189 of file delaunay_2d.cc.
References blender::meshintersect::CDT_state< T >::cdt, blender::CDT_CONSTRAINTS, blender::CDT_CONSTRAINTS_VALID_BMESH, blender::CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, blender::CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES_NONZERO, blender::CDT_INSIDE, blender::CDT_INSIDE_WITH_HOLES, blender::CDT_INSIDE_WITH_HOLES_NONZERO, blender::Core, detect_holes_with_fillrule_even_odd(), detect_holes_with_fillrule_nonzero(), blender::e, blender::meshintersect::CDTArrangement< T >::edges, ELEM, is_deleted_edge(), output_uses_evenodd_holes(), output_uses_nonzero_holes(), prepare_cdt_for_output(), PRF_scope, 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().
Return SymEdge whose next is se.
Definition at line 119 of file delaunay_2d.cc.
References prev(), and blender::meshintersect::SymEdge< T >::rot.
Referenced by blender::meshintersect::CDTArrangement< T >::add_diagonal(), blender::meshintersect::CDTArrangement< T >::delete_edge(), dissolve_symedge(), prev(), and blender::meshintersect::CDTArrangement< T >::split_edge().
| void blender::meshintersect::quad0_test | ( | ) |
Definition at line 536 of file BLI_delaunay_2d_test.cc.
References DO_DRAW, EXPECT_TRUE, get_orig_index(), get_output_edge_index(), graph_draw(), blender::gpu::shader::metadata::out, and output_edge_has_input_id().
| void blender::meshintersect::quad1_test | ( | ) |
Definition at line 551 of file BLI_delaunay_2d_test.cc.
| void blender::meshintersect::quad2_test | ( | ) |
Definition at line 566 of file BLI_delaunay_2d_test.cc.
References DO_DRAW, EXPECT_NE, get_output_edge_index(), graph_draw(), and blender::gpu::shader::metadata::out.
| void blender::meshintersect::quad3_test | ( | ) |
Definition at line 581 of file BLI_delaunay_2d_test.cc.
References blender::CDT_FULL, delaunay_2d_calc(), DO_DRAW, blender::EXPECT_EQ(), EXPECT_NE, fill_input_from_string(), get_output_edge_index(), graph_draw(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| void blender::meshintersect::quad4_test | ( | ) |
Definition at line 596 of file BLI_delaunay_2d_test.cc.
References blender::CDT_FULL, delaunay_2d_calc(), DO_DRAW, blender::EXPECT_EQ(), EXPECT_NE, fill_input_from_string(), get_output_edge_index(), graph_draw(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
|
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().
| void blender::meshintersect::remove_faces_in_holes | ( | CDT_state< T > * | cdt_state | ) |
Definition at line 2723 of file delaunay_2d.cc.
References blender::BLI_assert(), blender::meshintersect::CDT_state< T >::cdt, blender::Core, blender::meshintersect::CDTFace< T >::deleted, blender::meshintersect::SymEdge< T >::edge, blender::meshintersect::CDTArrangement< T >::faces, blender::meshintersect::CDTFace< T >::hole, is_constrained_edge(), blender::meshintersect::SymEdge< T >::next, PRF_scope, remove_faces_in_holes(), and blender::meshintersect::CDTFace< T >::symedge.
Referenced by prepare_cdt_for_output(), and remove_faces_in_holes().
| void blender::meshintersect::remove_non_constraint_edges | ( | CDT_state< T > * | cdt_state | ) |
Remove all non-constraint edges.
Definition at line 2545 of file delaunay_2d.cc.
References blender::meshintersect::CDT_state< T >::cdt, blender::Core, dissolve_symedge(), blender::e, is_constrained_edge(), is_deleted_edge(), PRF_scope, and remove_non_constraint_edges().
Referenced by prepare_cdt_for_output(), and remove_non_constraint_edges().
| void blender::meshintersect::remove_non_constraint_edges_leave_valid_bmesh | ( | CDT_state< T > * | cdt_state, |
| const bool | use_hole_status ) |
| use_hole_status | Use the hole status instead of original face ids to decide which faces must remain valid. Face ids aren't reliable for outputs with holes, add_face_ids labels the outside of CW faces (which the hole rules accept) and only one region of self-touching faces. Requires hole detection to have run. |
Definition at line 2605 of file delaunay_2d.cc.
References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), b, blender::meshintersect::CDT_state< T >::cdt, blender::BMVert::co, blender::Core, dissolve_symedge(), distance_squared(), blender::BMVert::e, blender::e, blender::meshintersect::EdgeToSort< T >::e, blender::meshintersect::CDTArrangement< T >::edges, blender::meshintersect::SymEdge< T >::face, is_constrained_edge(), is_deleted_edge(), blender::meshintersect::EdgeToSort< T >::len_squared, blender::meshintersect::SymEdge< T >::next, blender::meshintersect::CDTArrangement< T >::outer_face, PRF_scope, remove_non_constraint_edges_leave_valid_bmesh(), blender::Vector< T, InlineBufferCapacity, Allocator >::reserve(), sym(), and vert_touches_face().
Referenced by prepare_cdt_for_output(), and remove_non_constraint_edges_leave_valid_bmesh().
| void blender::meshintersect::remove_outer_edges_until_constraints | ( | CDT_state< T > * | cdt_state | ) |
Definition at line 2672 of file delaunay_2d.cc.
References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::BLI_assert(), blender::BLI_linklist_pop(), blender::BLI_linklist_prepend(), blender::meshintersect::CDT_state< T >::cdt, blender::Core, 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(), PRF_scope, remove_outer_edges_until_constraints(), 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(), and remove_outer_edges_until_constraints().
| void blender::meshintersect::repeatedge_test | ( | ) |
Definition at line 2687 of file BLI_delaunay_2d_test.cc.
References nonzero_winding_concave_outer_test().
| void blender::meshintersect::repeattri_test | ( | ) |
Definition at line 2699 of file BLI_delaunay_2d_test.cc.
References blender::CDT_INSIDE_WITH_HOLES, blender::CDT_INSIDE_WITH_HOLES_NONZERO, delaunay_2d_calc(), blender::EXPECT_EQ(), fill_input_from_string(), and blender::gpu::shader::metadata::in.
Definition at line 460 of file delaunay_2d.cc.
References sename(), and trunc_ptr().
Referenced by cdt_draw(), and sename().
| void blender::meshintersect::shared_split_boundary_test | ( | ) |
Definition at line 2738 of file BLI_delaunay_2d_test.cc.
References ELEM, blender::EXPECT_EQ(), EXPECT_TRUE, and blender::gpu::shader::metadata::out.
Definition at line 485 of file delaunay_2d.cc.
References blender::meshintersect::SymEdge< T >::next, short_se_dump(), blender::meshintersect::SymEdge< T >::vert, and vertname().
Referenced by dump_crossings(), and short_se_dump().
| 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().
| void blender::meshintersect::square_o_test | ( | ) |
Definition at line 2762 of file BLI_delaunay_2d_test.cc.
References blender::CDT_FULL, delaunay_2d_calc(), blender::EXPECT_EQ(), EXPECT_NE, EXPECT_TRUE, fill_input_from_string(), get_orig_index(), get_output_edge_index(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| 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.
Return other SymEdge for same CDTEdge as se.
Definition at line 113 of file delaunay_2d.cc.
References blender::meshintersect::SymEdge< T >::next, and sym().
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_with_fillrule_even_odd(), detect_holes_with_fillrule_nonzero(), 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(), blender::meshintersect::CDTArrangement< T >::split_edge(), and sym().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| CrossSegs | ) |
Definition at line 3182 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| CutAcrossTri | ) |
Definition at line 3187 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| CwOrigFaceIds | ) |
Definition at line 3082 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| DiamondCross | ) |
Definition at line 3192 of file BLI_delaunay_2d_test.cc.
References blender::CDT_CONSTRAINTS_VALID_BMESH, delaunay_2d_calc(), blender::EXPECT_EQ(), fill_input_from_string(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| DiamondInSquare | ) |
Definition at line 3237 of file BLI_delaunay_2d_test.cc.
References EXPECT_TRUE, get_output_edge_index(), blender::gpu::shader::metadata::out, and output_edge_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| DiamondInSquareWire | ) |
Definition at line 3242 of file BLI_delaunay_2d_test.cc.
References EXPECT_TRUE, get_output_edge_index(), get_output_tri_index(), blender::gpu::shader::metadata::out, and output_edge_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| DisjointPolysInLargeHull | ) |
Definition at line 3267 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| DissolvePendantEdgeFace | ) |
Definition at line 3302 of file BLI_delaunay_2d_test.cc.
References blender::CDT_CONSTRAINTS_VALID_BMESH, delaunay_2d_calc(), blender::EXPECT_EQ(), fill_input_from_string(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| Empty | ) |
Definition at line 3002 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| EvenOddBoundaryDisagreement | ) |
Definition at line 3072 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| EvenOddCoincidentPolygonsNeedIdsStable | ) |
Definition at line 3077 of file BLI_delaunay_2d_test.cc.
References EXPECT_TRUE, blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| EvenOddNestedHolesDeep | ) |
Definition at line 3067 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| FillCurveDegenerateInteriorFaces | ) |
Definition at line 3297 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| FillCurveLetterB | ) |
Definition at line 3292 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| FuzzReproMinimize1 | ) |
Definition at line 3312 of file BLI_delaunay_2d_test.cc.
References diamondinsquarewire_test().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| FuzzReproMinimize2 | ) |
Definition at line 3317 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| IntersectionSimpleEdgeIds | ) |
Definition at line 3322 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| IntersectionSquaresEdgeIds | ) |
Definition at line 3327 of file BLI_delaunay_2d_test.cc.
References blender::CDT_CONSTRAINTS, 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.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| LineHoleInSquare | ) |
Definition at line 3057 of file BLI_delaunay_2d_test.cc.
References EXPECT_FALSE, EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| LineInSquare | ) |
Definition at line 3052 of file BLI_delaunay_2d_test.cc.
References EXPECT_FALSE, EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| LoopingBack2x | ) |
Definition at line 3247 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| LoopingBack3x | ) |
Definition at line 3252 of file BLI_delaunay_2d_test.cc.
References EXPECT_FALSE, EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| LoopingBackHole2x | ) |
Definition at line 3257 of file BLI_delaunay_2d_test.cc.
References EXPECT_FALSE, blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| LoopingBackHole3x | ) |
Definition at line 3262 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| ManyCross | ) |
Definition at line 3202 of file BLI_delaunay_2d_test.cc.
References twofaceedgeoverlap_test().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| MixedPts | ) |
Definition at line 3022 of file BLI_delaunay_2d_test.cc.
References blender::CDT_INSIDE, delaunay_2d_calc(), blender::EXPECT_EQ(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NestedHoles | ) |
Definition at line 3062 of file BLI_delaunay_2d_test.cc.
References EXPECT_FALSE, EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWinding | ) |
Definition at line 3087 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingCancelToZero | ) |
Definition at line 3112 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE, get_orig_index(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingCoincidentVerts | ) |
Definition at line 3152 of file BLI_delaunay_2d_test.cc.
References blender::CDT_INSIDE_WITH_HOLES, delaunay_2d_calc(), DO_DRAW, blender::EXPECT_EQ(), graph_draw(), and blender::gpu::shader::metadata::in.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingConcaveOuter | ) |
Definition at line 3177 of file BLI_delaunay_2d_test.cc.
References twosquaresoverlap_test().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingDeepNest | ) |
Definition at line 3137 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE, EXPECT_TRUE, blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingEdgeSplit | ) |
Definition at line 3127 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingExactSharedEdge | ) |
Definition at line 3172 of file BLI_delaunay_2d_test.cc.
References DO_DRAW, and graph_draw().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingFan | ) |
Definition at line 3122 of file BLI_delaunay_2d_test.cc.
References expect_coord_near(), blender::EXPECT_EQ(), get_output_tri_index(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingHighCount | ) |
Definition at line 3117 of file BLI_delaunay_2d_test.cc.
References blender::gpu::shader::metadata::in, math_abs(), blender::gpu::shader::metadata::out, T, and blender::x.
| 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().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingManyCrossings | ) |
Definition at line 3157 of file BLI_delaunay_2d_test.cc.
References blender::CDT_CONSTRAINTS, delaunay_2d_calc(), DO_DRAW, blender::EXPECT_EQ(), graph_draw(), and blender::gpu::shader::metadata::in.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingMultiFaceEdge | ) |
Definition at line 3102 of file BLI_delaunay_2d_test.cc.
References blender::CDT_FULL, delaunay_2d_calc(), blender::EXPECT_EQ(), fill_input_from_string(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingMultiFaceEdgeMixed | ) |
Definition at line 3107 of file BLI_delaunay_2d_test.cc.
References blender::EXPECT_EQ(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingNegativeOnly | ) |
Definition at line 3162 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingNested | ) |
Definition at line 3092 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingNestedUnion | ) |
Definition at line 3097 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingSelfIntersect | ) |
Definition at line 3132 of file BLI_delaunay_2d_test.cc.
References EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| 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.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| NonZeroWindingTJunction | ) |
Definition at line 3167 of file BLI_delaunay_2d_test.cc.
References graph_draw().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| OnePt | ) |
Definition at line 3007 of file BLI_delaunay_2d_test.cc.
References twoface2_test().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| OverlapFaces | ) |
Definition at line 3217 of file BLI_delaunay_2d_test.cc.
References blender::EXPECT_EQ(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| Quad0 | ) |
Definition at line 3027 of file BLI_delaunay_2d_test.cc.
References blender::EXPECT_EQ(), get_orig_index(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| Quad1 | ) |
Definition at line 3032 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE, get_vertex_by_coord(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| Quad2 | ) |
Definition at line 3037 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE, get_output_tri_index(), get_vertex_by_coord(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| Quad3 | ) |
Definition at line 3042 of file BLI_delaunay_2d_test.cc.
References EXPECT_FALSE, EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| Quad4 | ) |
Definition at line 3047 of file BLI_delaunay_2d_test.cc.
References EXPECT_FALSE, EXPECT_NE, EXPECT_TRUE, get_output_tri_index(), blender::gpu::shader::metadata::out, and output_face_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| RepeatEdge | ) |
Definition at line 3272 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| RepeatTri | ) |
Definition at line 3277 of file BLI_delaunay_2d_test.cc.
References blender::CDT_CONSTRAINTS_VALID_BMESH, delaunay_2d_calc(), blender::EXPECT_EQ(), fill_input_from_string(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| SharedSplitBoundary | ) |
Definition at line 3282 of file BLI_delaunay_2d_test.cc.
References DO_DRAW, graph_draw(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| SquareO | ) |
Definition at line 3287 of file BLI_delaunay_2d_test.cc.
References diamondinsquare_test().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| StaleSymedgeBeforeRemoveFacesInHoles | ) |
Definition at line 3307 of file BLI_delaunay_2d_test.cc.
References DO_DRAW, graph_draw(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| ThreePt | ) |
Definition at line 3017 of file BLI_delaunay_2d_test.cc.
References fill_input_from_string(), and blender::gpu::shader::metadata::in.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| TriInTri | ) |
Definition at line 3232 of file BLI_delaunay_2d_test.cc.
References EXPECT_TRUE, get_output_edge_index(), blender::gpu::shader::metadata::out, and output_edge_has_input_id().
| blender::meshintersect::TEST | ( | delaunay_d | , |
| TwoDiamondsCross | ) |
Definition at line 3197 of file BLI_delaunay_2d_test.cc.
References DO_DRAW, graph_draw(), and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| TwoFace | ) |
Definition at line 3207 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| TwoFace2 | ) |
Definition at line 3212 of file BLI_delaunay_2d_test.cc.
References blender::CDT_CONSTRAINTS, delaunay_2d_calc(), fill_input_from_string(), blender::gpu::shader::metadata::in, and blender::gpu::shader::metadata::out.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| TwoFaceEdgeOverlap | ) |
Definition at line 3227 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| TwoPt | ) |
Definition at line 3012 of file BLI_delaunay_2d_test.cc.
| blender::meshintersect::TEST | ( | delaunay_d | , |
| TwoSquaresOverlap | ) |
Definition at line 3222 of file BLI_delaunay_2d_test.cc.
References EXPECT_NE, get_orig_index(), and blender::gpu::shader::metadata::out.
| void blender::meshintersect::threept_test | ( | ) |
Definition at line 484 of file BLI_delaunay_2d_test.cc.
References DO_DRAW, graph_draw(), and blender::gpu::shader::metadata::out.
Definition at line 1691 of file delaunay_2d.cc.
References filtered_orient2d(), blender::meshintersect::SymEdge< T >::next, tri_orient(), and blender::meshintersect::SymEdge< T >::vert.
Referenced by get_next_crossing_from_vert(), and tri_orient().
| void blender::meshintersect::triintri_test | ( | ) |
Definition at line 2645 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.
|
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().
| void blender::meshintersect::twodiamondscross_test | ( | ) |
Definition at line 2344 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, and blender::meshintersect::CDT_result< T >::vert.
| void blender::meshintersect::twoface2_test | ( | ) |
Definition at line 2434 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 TEST().
| void blender::meshintersect::twoface_test | ( | ) |
Definition at line 2398 of file BLI_delaunay_2d_test.cc.
References nonzero_winding_many_crossings_test().
| void blender::meshintersect::twofaceedgeoverlap_test | ( | ) |
Definition at line 2592 of file BLI_delaunay_2d_test.cc.
Referenced by TEST().
| void blender::meshintersect::twopt_test | ( | ) |
Definition at line 459 of file BLI_delaunay_2d_test.cc.
| void blender::meshintersect::twosquaresoverlap_test | ( | ) |
Definition at line 2578 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 TEST().
|
inline |
Definition at line 1352 of file delaunay_2d.cc.
References blender::BMVert::co, filtered_orient2d(), blender::meshintersect::SymEdge< T >::next, blender::v, blender::meshintersect::SymEdge< T >::vert, and vert_left_of_symedge().
Referenced by dc_tri(), and vert_left_of_symedge().
|
inline |
Definition at line 1357 of file delaunay_2d.cc.
References blender::BMVert::co, filtered_orient2d(), blender::meshintersect::SymEdge< T >::next, blender::v, blender::meshintersect::SymEdge< T >::vert, and vert_right_of_symedge().
Referenced by dc_tri(), and vert_right_of_symedge().
| 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 1047 of file delaunay_2d.cc.
References blender::meshintersect::SymEdge< T >::face, blender::meshintersect::SymEdge< T >::rot, blender::v, and vert_touches_face().
Referenced by remove_non_constraint_edges_leave_valid_bmesh(), and vert_touches_face().
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().
|
constexpr |
Definition at line 411 of file BLI_delaunay_2d_test.cc.
Referenced by cutacrosstri_test(), disjoint_polys_in_large_hull_test(), fill_curve_degenerate_interior_faces_test(), fuzz_repro_minimize_test1(), lineholeinsquare_test(), mixedpts_test(), nestedholes_test(), nonzero_winding_coincident_verts_test(), nonzero_winding_deep_nest_test(), nonzero_winding_exact_shared_edge_test(), nonzero_winding_fan_test(), nonzero_winding_many_crossings_test(), nonzero_winding_self_intersect_test(), nonzero_winding_tjunction_test(), overlapfaces_test(), quad0_test(), quad2_test(), quad3_test(), quad4_test(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), threept_test(), triintri_test(), twodiamondscross_test(), twoface2_test(), and twosquaresoverlap_test().
|
static |
Definition at line 289 of file BLI_delaunay_2d_test.cc.
Referenced by graph_draw().
|
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().
|
staticconstexpr |
Definition at line 2754 of file delaunay_2d.cc.
Referenced by detect_holes_with_fillrule_even_odd(), and detect_holes_with_fillrule_nonzero().
|
staticconstexpr |
Definition at line 2753 of file delaunay_2d.cc.
Referenced by detect_holes_with_fillrule_even_odd(), and detect_holes_with_fillrule_nonzero().