 |
Blender V4.3
|
|
Blender V4.3
|
#include <algorithm>#include <atomic>#include <fstream>#include <iostream>#include <sstream>#include "BLI_array.hh"#include "BLI_linklist.h"#include "BLI_math_boolean.hh"#include "BLI_math_mpq.hh"#include "BLI_math_vector_mpq_types.hh"#include "BLI_set.hh"#include "BLI_task.hh"#include "BLI_vector.hh"#include "BLI_delaunay_2d.hh"Go to the source code of this file.
Classes | |
| struct | blender::meshintersect::SymEdge< T > |
| struct | blender::meshintersect::FatCo< T > |
| struct | blender::meshintersect::FatCo< double > |
| struct | blender::meshintersect::CDTVert< T > |
| struct | blender::meshintersect::CDTEdge< T > |
| struct | blender::meshintersect::CDTFace< T > |
| struct | blender::meshintersect::CDTArrangement< T > |
| class | blender::meshintersect::CDT_state< T > |
| class | SiteInfo< T > |
| class | CrossData< T > |
| struct | EdgeToSort< T > |
Namespaces | |
| namespace | blender |
| namespace | blender::meshintersect |
Macros | |
| #define | DEBUG_CDT |
| #define | SX(x) (((x)-minx) * scale) |
| #define | SY(y) ((maxy - (y)) * scale) |
Functions | |
| template<typename T > | |
| T | blender::meshintersect::math_abs (const T v) |
| template<> | |
| double | blender::meshintersect::math_abs< double > (const double v) |
| template<typename T > | |
| double | blender::meshintersect::math_to_double (const T) |
| template<> | |
| double | blender::meshintersect::math_to_double< double > (const double v) |
| template<typename T > | |
| SymEdge< T > * | blender::meshintersect::sym (const SymEdge< T > *se) |
| template<typename T > | |
| SymEdge< T > * | blender::meshintersect::prev (const SymEdge< T > *se) |
| template<typename T > | |
| std::ostream & | blender::meshintersect::operator<< (std::ostream &stream, const FatCo< T > &co) |
| template<typename T > | |
| std::string | blender::meshintersect::vertname (const CDTVert< T > *v) |
| static std::string | blender::meshintersect::trunc_ptr (const void *p) |
| template<typename T > | |
| std::string | blender::meshintersect::sename (const SymEdge< T > *se) |
| template<typename T > | |
| std::ostream & | blender::meshintersect::operator<< (std::ostream &os, const SymEdge< T > &se) |
| template<typename T > | |
| std::ostream & | blender::meshintersect::operator<< (std::ostream &os, const SymEdge< T > *se) |
| template<typename T > | |
| std::string | blender::meshintersect::short_se_dump (const SymEdge< T > *se) |
| template<typename T > | |
| std::ostream & | blender::meshintersect::operator<< (std::ostream &os, const CDT_state< T > &cdt_state) |
| template<typename T > | |
| void | blender::meshintersect::cdt_draw (const std::string &label, const CDTArrangement< T > &cdt) |
| if (draw_face_labels) | |
| template<typename T > | |
| static int | filtered_orient2d (const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c) |
| template<> | |
| int | filtered_orient2d< double > (const FatCo< double > &a, const FatCo< double > &b, const FatCo< double > &c) |
| template<typename T > | |
| static int | filtered_incircle (const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c, const FatCo< T > &d) |
| template<> | |
| int | filtered_incircle< double > (const FatCo< double > &a, const FatCo< double > &b, const FatCo< double > &c, const FatCo< double > &d) |
| template<typename T > | |
| static bool | in_line (const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c) |
| template<> | |
| bool | in_line< double > (const FatCo< double > &a, const FatCo< double > &b, const FatCo< double > &c) |
| static bool | id_range_in_list (const blender::Set< int > &id_list, int range_start, int range_end) |
| static void | add_to_input_ids (blender::Set< int > &dst, int input_id) |
| static void | add_list_to_input_ids (blender::Set< int > &dst, const blender::Set< int > &src) |
| template<typename T > | |
| bool | is_border_edge (const CDTEdge< T > *e, const CDT_state< T > *cdt) |
| template<typename T > | |
| bool | is_constrained_edge (const CDTEdge< T > *e) |
| template<typename T > | |
| bool | is_deleted_edge (const CDTEdge< T > *e) |
| template<typename T > | |
| bool | is_original_vert (const CDTVert< T > *v, CDT_state< T > *cdt) |
| template<typename T > | |
| SymEdge< T > * | find_symedge_between_verts (const CDTVert< T > *v1, const CDTVert< T > *v2) |
| template<typename T > | |
| SymEdge< T > * | find_symedge_with_face (const CDTVert< T > *v, const CDTFace< T > *f) |
| template<typename T > | |
| bool | exists_edge (const CDTVert< T > *v1, const CDTVert< T > *v2) |
| template<typename T > | |
| bool | vert_touches_face (const CDTVert< T > *v, const CDTFace< T > *f) |
| template<typename T > | |
| bool | site_lexicographic_sort (const SiteInfo< T > &a, const SiteInfo< T > &b) |
| template<typename T > | |
| void | find_site_merges (Array< SiteInfo< T > > &sites) |
| template<typename T > | |
| bool | vert_left_of_symedge (CDTVert< T > *v, SymEdge< T > *se) |
| template<typename T > | |
| bool | vert_right_of_symedge (CDTVert< T > *v, SymEdge< T > *se) |
| template<typename T > | |
| bool | dc_tri_valid (SymEdge< T > *se, SymEdge< T > *basel, SymEdge< T > *basel_sym) |
| template<typename T > | |
| void | dc_tri (CDTArrangement< T > *cdt, Array< SiteInfo< T > > &sites, int start, int end, SymEdge< T > **r_le, SymEdge< T > **r_re) |
| template<typename T > | |
| void | dc_triangulate (CDTArrangement< T > *cdt, Array< SiteInfo< T > > &sites) |
| template<typename T > | |
| void | initial_triangulation (CDTArrangement< T > *cdt) |
| template<typename T > | |
| static void | re_delaunay_triangulate (CDTArrangement< T > *cdt, SymEdge< T > *se) |
| template<typename T > | |
| int | tri_orient (const SymEdge< T > *t) |
| template<typename T > | |
| bool | get_next_crossing_from_vert (CDT_state< T > *cdt_state, CrossData< T > *cd, CrossData< T > *cd_next, const CDTVert< T > *v2) |
| template<typename T > | |
| void | fill_crossdata_for_through_vert (CDTVert< T > *v, SymEdge< T > *cd_out, CrossData< T > *cd, CrossData< T > *cd_next) |
| template<typename T > | |
| void | fill_crossdata_for_intersect (const FatCo< T > &curco, const CDTVert< T > *v2, SymEdge< T > *t, CrossData< T > *cd, CrossData< T > *cd_next, const T epsilon) |
| template<typename T > | |
| void | get_next_crossing_from_edge (CrossData< T > *cd, CrossData< T > *cd_next, const CDTVert< T > *v2, const T epsilon) |
| template<typename T > | |
| void | dump_crossings (const Span< CrossData< T > > crossings) |
| template<typename T > | |
| void | add_edge_constraint (CDT_state< T > *cdt_state, CDTVert< T > *v1, CDTVert< T > *v2, int input_id, LinkNode **r_edges) |
| template<typename T > | |
| void | add_edge_constraints (CDT_state< T > *cdt_state, const CDT_input< T > &input) |
| template<typename T > | |
| void | add_face_ids (CDT_state< T > *cdt_state, SymEdge< T > *face_symedge, int face_id, int fedge_start, int fedge_end) |
| static int | power_of_10_greater_equal_to (int x) |
| template<typename T > | |
| int | add_face_constraints (CDT_state< T > *cdt_state, const CDT_input< T > &input, CDT_output_type output_type) |
| template<typename T > | |
| void | dissolve_symedge (CDT_state< T > *cdt_state, SymEdge< T > *se) |
| template<typename T > | |
| void | remove_non_constraint_edges (CDT_state< T > *cdt_state) |
| template<typename T > | |
| void | remove_non_constraint_edges_leave_valid_bmesh (CDT_state< T > *cdt_state) |
| template<typename T > | |
| void | remove_outer_edges_until_constraints (CDT_state< T > *cdt_state) |
| template<typename T > | |
| void | remove_faces_in_holes (CDT_state< T > *cdt_state) |
| template<typename T > | |
| void | detect_holes (CDT_state< T > *cdt_state) |
| template<typename T > | |
| void | prepare_cdt_for_output (CDT_state< T > *cdt_state, const CDT_output_type output_type) |
| template<typename T > | |
| CDT_result< T > | get_cdt_output (CDT_state< T > *cdt_state, const CDT_input< T >, CDT_output_type output_type) |
| template<typename T > | |
| void | add_input_verts (CDT_state< T > *cdt_state, const CDT_input< T > &input) |
| template<typename T > | |
| CDT_result< T > | delaunay_calc (const CDT_input< T > &input, CDT_output_type output_type) |
| blender::meshintersect::CDT_result< double > | delaunay_2d_calc (const CDT_input< double > &input, CDT_output_type output_type) |
Variables | |
| append = true | |
| #define DEBUG_CDT |
Definition at line 354 of file delaunay_2d.cc.
| #define SX | ( | x | ) | (((x)-minx) * scale) |
Referenced by blender::meshintersect::cdt_draw(), blender::meshintersect::graph_draw(), and if().
| #define SY | ( | y | ) | ((maxy - (y)) * scale) |
Referenced by blender::meshintersect::cdt_draw(), blender::meshintersect::graph_draw(), and if().
| void add_edge_constraint | ( | CDT_state< T > * | cdt_state, |
| CDTVert< T > * | v1, | ||
| CDTVert< T > * | v2, | ||
| int | input_id, | ||
| LinkNode ** | r_edges ) |
Add a constrained edge between v1 and v2 to cdt structure. This may result in a number of #CDTEdges created, due to intersections and partial overlaps with existing cdt vertices and edges. Each created #CDTEdge will have input_id added to its input_ids list.
If r_edges is not null, the #CDTEdges generated or found that go from v1 to v2 are put into that linked list, in order.
Assumes that #blender_constrained_delaunay_get_output has not been called yet.
Definition at line 1872 of file delaunay_2d.cc.
References add_to_input_ids(), BLI_assert, BLI_linklist_append(), dump_crossings(), find_symedge_between_verts(), find_symedge_with_face(), get_next_crossing_from_edge(), get_next_crossing_from_vert(), CrossData< T >::in, is_constrained_edge(), CrossData< T >::lambda, LinkNodePair::list, CrossData< T >::out, re_delaunay_triangulate(), blender::meshintersect::sym(), T, v, v2, CrossData< T >::vert, and blender::meshintersect::vertname().
Referenced by add_edge_constraints(), and add_face_constraints().
| void 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 2097 of file delaunay_2d.cc.
References add_edge_constraint(), and v2.
Referenced by delaunay_calc().
| int add_face_constraints | ( | CDT_state< T > * | cdt_state, |
| const CDT_input< T > & | input, | ||
| CDT_output_type | output_type ) |
Incrementally each edge of each input face as an edge constraint. The code will ensure that the #CDTEdge's created will have ids that tie them back to the original face edge (using a numbering system for those edges that starts with cdt->face_edge_offset, and continues with the edges in order around each face in turn. And then the next face starts at cdt->face_edge_offset beyond the start for the previous face. Return the number of faces added, which may be less than input.face.size() in the case that some faces have less than 3 sides.
Definition at line 2189 of file delaunay_2d.cc.
References add_edge_constraint(), add_face_ids(), BLI_assert, BLI_linklist_free(), CDT_CONSTRAINTS_VALID_BMESH, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, ELEM, blender::Span< T >::index_range(), LinkNode::link, power_of_10_greater_equal_to(), blender::Span< T >::size(), size(), and v2.
Referenced by delaunay_calc().
| void add_face_ids | ( | CDT_state< T > * | cdt_state, |
| SymEdge< T > * | face_symedge, | ||
| int | face_id, | ||
| int | fedge_start, | ||
| int | fedge_end ) |
Add face_id to the input_ids lists of all #CDTFace's on the interior of the input face with that id. face_symedge is on edge of the boundary of the input face, with assumption that interior is on the left of that #SymEdge.
The algorithm is: starting from the #CDTFace for face_symedge, add the face_id and then process all adjacent faces where the adjacency isn't across an edge that was a constraint added for the boundary of the input face. fedge_start..fedge_end is the inclusive range of edge input ids that are for the given face.
NOTE: if the input face is not CCW oriented, we'll be labeling the outside, not the inside. Note 2: if the boundary has self-crossings, this method will arbitrarily pick one of the contiguous set of faces enclosed by parts of the boundary, leaving the other such un-tagged. This may be a feature instead of a bug if the first contiguous section is most of the face and the others are tiny self-crossing triangles at some parts of the boundary. On the other hand, if decide we want to handle these in full generality, then will need a more complicated algorithm (using "inside" tests and a parity rule) to decide on the interior.
Definition at line 2135 of file delaunay_2d.cc.
References add_to_input_ids(), id_range_in_list(), and blender::meshintersect::sym().
Referenced by add_face_constraints().
| void 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 2755 of file delaunay_2d.cc.
Referenced by delaunay_calc().
|
static |
Definition at line 884 of file delaunay_2d.cc.
References blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add().
Referenced by blender::meshintersect::CDTArrangement< T >::add_diagonal(), and blender::meshintersect::CDTArrangement< T >::split_edge().
|
static |
Definition at line 879 of file delaunay_2d.cc.
References blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add().
Referenced by add_edge_constraint(), add_face_ids(), and get_cdt_output().
| void 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 1225 of file delaunay_2d.cc.
References BLI_assert, blender::meshintersect::cdt_draw(), BMVert::co, dc_tri(), dc_tri_valid(), filtered_incircle(), filtered_orient2d(), next, blender::meshintersect::sym(), v2, vert_left_of_symedge(), and vert_right_of_symedge().
Referenced by dc_tri(), and dc_triangulate().
|
inline |
Definition at line 1213 of file delaunay_2d.cc.
References filtered_orient2d().
Referenced by dc_tri().
| void dc_triangulate | ( | CDTArrangement< T > * | cdt, |
| Array< SiteInfo< T > > & | sites ) |
Definition at line 1428 of file delaunay_2d.cc.
Referenced by initial_triangulation().
| blender::meshintersect::CDT_result< double > delaunay_2d_calc | ( | const CDT_input< double > & | input, |
| CDT_output_type | output_type ) |
Definition at line 2780 of file delaunay_2d.cc.
References delaunay_calc().
Referenced by blender::nodes::node_geo_curve_fill_cc::do_cdt_with_mask(), and blender::io::obj::fixup_invalid_face().
| CDT_result< T > delaunay_calc | ( | const CDT_input< T > & | input, |
| CDT_output_type | output_type ) |
Definition at line 2763 of file delaunay_2d.cc.
References add_edge_constraints(), add_face_constraints(), add_input_verts(), CDT_CONSTRAINTS, CDT_FULL, CDT_INSIDE, ELEM, get_cdt_output(), and initial_triangulation().
Referenced by delaunay_2d_calc().
Set the hole member of each CDTFace to true for each face that is detected to be part of a hole. A hole face is define as one for which, when a ray is shot from a point inside the face to infinity, it crosses an even number of constraint edges. We'll choose a ray direction that is extremely unlikely to exactly superimpose some edge, so avoiding the need to be careful about such overlaps.
To improve performance, we gather together faces that should have the same winding number, and only shoot rays once.
Definition at line 2484 of file delaunay_2d.cc.
References blender::meshintersect::CDTArrangement< T >::faces, is_constrained_edge(), blender::threading::parallel_for(), and blender::meshintersect::sym().
Referenced by prepare_cdt_for_output().
Definition at line 2266 of file delaunay_2d.cc.
References ELEM, and blender::meshintersect::sym().
Referenced by remove_non_constraint_edges(), remove_non_constraint_edges_leave_valid_bmesh(), and remove_outer_edges_until_constraints().
Definition at line 1840 of file delaunay_2d.cc.
References CrossData< T >::in, CrossData< T >::lambda, CrossData< T >::out, blender::meshintersect::short_se_dump(), and CrossData< T >::vert.
Referenced by add_edge_constraint().
Is there already an edge between a and b?
Definition at line 945 of file delaunay_2d.cc.
References find_symedge_between_verts(), and v2.
Referenced by re_delaunay_triangulate().
| 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 ) |
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 1666 of file delaunay_2d.cc.
References BLI_assert, BMVert::co, blender::math::distance(), blender::math::distance_squared(), fill_crossdata_for_through_vert(), blender::math::isect_seg_seg(), CrossData< T >::lambda, CrossData< T >::out, blender::meshintersect::sym(), UNUSED_VARS_NDEBUG, and v2.
Referenced by get_next_crossing_from_edge(), and get_next_crossing_from_vert().
| void 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 1624 of file delaunay_2d.cc.
References BLI_assert, CrossData< T >::in, CrossData< T >::lambda, CrossData< T >::out, blender::meshintersect::sym(), T, v, and CrossData< T >::vert.
Referenced by fill_crossdata_for_intersect(), and get_next_crossing_from_vert().
|
static |
A filtered version of incircle.
Referenced by dc_tri(), and re_delaunay_triangulate().
| int filtered_incircle< double > | ( | const FatCo< double > & | a, |
| const FatCo< double > & | b, | ||
| const FatCo< double > & | c, | ||
| const FatCo< double > & | d ) |
Definition at line 721 of file delaunay_2d.cc.
References b, 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.
Referenced by dc_tri(), dc_tri_valid(), get_next_crossing_from_edge(), get_next_crossing_from_vert(), tri_orient(), vert_left_of_symedge(), and vert_right_of_symedge().
| int filtered_orient2d< double > | ( | const FatCo< double > & | a, |
| const FatCo< double > & | b, | ||
| const FatCo< double > & | c ) |
Definition at line 654 of file delaunay_2d.cc.
References b, and blender::orient2d().
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 1186 of file delaunay_2d.cc.
References BMVert::co, and v.
Referenced by initial_triangulation().
| SymEdge< T > * 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 915 of file delaunay_2d.cc.
References v2.
Referenced by add_edge_constraint(), and exists_edge().
| SymEdge< T > * 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 930 of file delaunay_2d.cc.
References v.
Referenced by add_edge_constraint().
| CDT_result< T > get_cdt_output | ( | CDT_state< T > * | cdt_state, |
| const CDT_input< T > | , | ||
| CDT_output_type | output_type ) |
Definition at line 2635 of file delaunay_2d.cc.
References add_to_input_ids(), BLI_assert, BMVert::co, e, is_deleted_edge(), prepare_cdt_for_output(), result, v, and blender::meshintersect::CDTArrangement< T >::verts.
Referenced by delaunay_calc().
| void 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 1817 of file delaunay_2d.cc.
References BMVert::co, fill_crossdata_for_intersect(), filtered_orient2d(), CrossData< T >::in, blender::math::interpolate(), CrossData< T >::lambda, blender::meshintersect::sym(), and v2.
Referenced by add_edge_constraint().
| bool 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 1766 of file delaunay_2d.cc.
References BLI_assert, BMVert::co, fill_crossdata_for_intersect(), fill_crossdata_for_through_vert(), filtered_orient2d(), in_line(), tri_orient(), v2, and CrossData< T >::vert.
Referenced by add_edge_constraint().
|
static |
Definition at line 869 of file delaunay_2d.cc.
Referenced by add_face_ids().
| if | ( | draw_face_labels | ) |
Definition at line 573 of file delaunay_2d.cc.
References double(), e, blender::meshintersect::CDTArrangement< T >::edges, blender::meshintersect::CDTArrangement< T >::faces, blender::meshintersect::CDTArrangement< T >::outer_face, SX, SY, and blender::meshintersect::trunc_ptr().
|
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().
| bool in_line< double > | ( | const FatCo< double > & | a, |
| const FatCo< double > & | b, | ||
| const FatCo< double > & | c ) |
Definition at line 773 of file delaunay_2d.cc.
References b.
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 1468 of file delaunay_2d.cc.
References blender::Array< T, InlineBufferCapacity, Allocator >::begin(), dc_triangulate(), blender::Array< T, InlineBufferCapacity, Allocator >::end(), find_site_merges(), and site_lexicographic_sort().
Referenced by delaunay_calc().
|
inline |
Definition at line 891 of file delaunay_2d.cc.
References e.
Definition at line 896 of file delaunay_2d.cc.
References e.
Referenced by add_edge_constraint(), detect_holes(), remove_faces_in_holes(), remove_non_constraint_edges(), remove_non_constraint_edges_leave_valid_bmesh(), and remove_outer_edges_until_constraints().
Definition at line 901 of file delaunay_2d.cc.
References e.
Referenced by get_cdt_output(), prepare_cdt_for_output(), remove_non_constraint_edges(), and remove_non_constraint_edges_leave_valid_bmesh().
Definition at line 906 of file delaunay_2d.cc.
References v.
Definition at line 2165 of file delaunay_2d.cc.
References BLI_assert.
Referenced by add_face_constraints().
| void 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 2588 of file delaunay_2d.cc.
References CDT_CONSTRAINTS, CDT_CONSTRAINTS_VALID_BMESH, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, CDT_INSIDE, CDT_INSIDE_WITH_HOLES, detect_holes(), e, is_deleted_edge(), 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().
|
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 1491 of file delaunay_2d.cc.
References b, BMVert::co, count, exists_edge(), filtered_incircle(), re_delaunay_triangulate(), blender::meshintersect::sym(), and v.
Referenced by add_edge_constraint(), and re_delaunay_triangulate().
Definition at line 2449 of file delaunay_2d.cc.
References BLI_assert, blender::meshintersect::CDTArrangement< T >::faces, and is_constrained_edge().
Referenced by prepare_cdt_for_output().
Remove all non-constraint edges.
Definition at line 2297 of file delaunay_2d.cc.
References dissolve_symedge(), e, is_constrained_edge(), and is_deleted_edge().
Referenced by prepare_cdt_for_output().
| void remove_non_constraint_edges_leave_valid_bmesh | ( | CDT_state< T > * | cdt_state | ) |
Definition at line 2348 of file delaunay_2d.cc.
References b, BMVert::co, dissolve_symedge(), blender::math::distance_squared(), BMVert::e, e, blender::meshintersect::CDTArrangement< T >::edges, is_constrained_edge(), is_deleted_edge(), blender::meshintersect::sym(), and vert_touches_face().
Referenced by prepare_cdt_for_output().
Definition at line 2399 of file delaunay_2d.cc.
References BLI_assert, BLI_linklist_pop(), BLI_linklist_prepend(), dissolve_symedge(), is_constrained_edge(), and blender::meshintersect::sym().
Referenced by prepare_cdt_for_output().
| bool site_lexicographic_sort | ( | const SiteInfo< T > & | a, |
| const SiteInfo< T > & | b ) |
Compare function for lexicographic sort: x, then y, then index.
Definition at line 1162 of file delaunay_2d.cc.
References b.
Referenced by initial_triangulation().
Definition at line 1537 of file delaunay_2d.cc.
References filtered_orient2d().
Referenced by get_next_crossing_from_vert().
Definition at line 1201 of file delaunay_2d.cc.
References BMVert::co, filtered_orient2d(), and v.
Referenced by dc_tri().
Definition at line 1206 of file delaunay_2d.cc.
References BMVert::co, filtered_orient2d(), and v.
Referenced by dc_tri().
Is the vertex v incident on face f?
Definition at line 953 of file delaunay_2d.cc.
References v.
Referenced by remove_non_constraint_edges_leave_valid_bmesh().
| append = true |
Definition at line 621 of file delaunay_2d.cc.
Referenced by blender::draw::overlay::LinePrimitiveBuf::append(), blender::draw::overlay::PointPrimitiveBuf::append(), MD5Hash::append(), blender::io::serialize::ArrayValue::append_array(), blender::io::serialize::DictionaryValue::append_array(), blender::io::serialize::ArrayValue::append_bool(), blender::io::serialize::ArrayValue::append_dict(), blender::io::serialize::DictionaryValue::append_dict(), blender::io::serialize::ArrayValue::append_double(), blender::io::serialize::DictionaryValue::append_double(), MD5Hash::append_file(), blender::io::serialize::ArrayValue::append_int(), blender::io::serialize::DictionaryValue::append_int(), blender::Vector< T, InlineBufferCapacity, Allocator >::append_non_duplicates(), blender::io::serialize::ArrayValue::append_null(), blender::io::serialize::ArrayValue::append_str(), blender::io::serialize::DictionaryValue::append_str(), blender::ed::object::apply_grease_pencil_for_modifier_all_keyframes(), blender::meshintersect::cdt_draw(), DeformableContactConstraint::DeformableContactConstraint(), EPA< btConvexTemplate >::Evaluate(), gjkepa2_impl::EPA::Evaluate(), EPA< btConvexTemplate >::expand(), gjkepa2_impl::EPA::expand(), blender::draw::StorageVectorBuffer< T, len >::extend(), blender::GVectorArray::extend(), blender::bke::pbvh::uv_islands::UVIsland::extend_border(), MD5Hash::finish(), EPA< btConvexTemplate >::Initialize(), gjkepa2_impl::EPA::Initialize(), EPA< btConvexTemplate >::newface(), gjkepa2_impl::EPA::newface(), blender::bke::pbvh::pixels::NonManifoldUVEdges::NonManifoldUVEdges(), blender::draw::overlay::Cameras::object_sync(), blender::gpu::GLSources::operator=(), blender::bke::pbvh::pixels::PixelNodesTileData::PixelNodesTileData(), and DeformableContactConstraint::replace().