Blender
V3.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_vec_mpq_types.hh"
#include "BLI_set.hh"
#include "BLI_task.hh"
#include "BLI_vector.hh"
#include "BLI_delaunay_2d.h"
Go to the source code of this file.
Classes | |
struct | blender::meshintersect::SymEdge< Arith_t > |
struct | blender::meshintersect::FatCo< T > |
struct | blender::meshintersect::FatCo< double > |
struct | blender::meshintersect::CDTVert< T > |
struct | blender::meshintersect::CDTEdge< Arith_t > |
struct | blender::meshintersect::CDTFace< Arith_t > |
struct | blender::meshintersect::CDTArrangement< Arith_t > |
class | blender::meshintersect::CDT_state< T > |
class | SiteInfo< T > |
class | CrossData< T > |
struct | EdgeToSort< T > |
Namespaces | |
blender | |
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 UNUSED(v)) |
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) |
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 Vector< CrossData< T >, inline_crossings_size > &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 > UNUSED(input), 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) |
::CDT_result * | BLI_delaunay_2d_cdt_calc (const ::CDT_input *input, const CDT_output_type output_type) |
void | BLI_delaunay_2d_cdt_free (::CDT_result *result) |
Variables | |
constexpr int | inline_crossings_size = 128 |
#define DEBUG_CDT |
Definition at line 360 of file delaunay_2d.cc.
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 1885 of file delaunay_2d.cc.
References add_to_input_ids(), BLI_assert, BLI_linklist_append(), dump_crossings(), blender::meshintersect::SymEdge< Arith_t >::edge, blender::meshintersect::SymEdge< Arith_t >::face, find_symedge_between_verts(), find_symedge_with_face(), get_next_crossing_from_vert(), CrossData< T >::in, inline_crossings_size, is_constrained_edge(), CrossData< T >::lambda, LinkNodePair::list, blender::meshintersect::SymEdge< Arith_t >::next, CrossData< T >::out, re_delaunay_triangulate(), blender::meshintersect::sym(), T, t, v, v1, v2, blender::meshintersect::SymEdge< Arith_t >::vert, 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 2109 of file delaunay_2d.cc.
References add_edge_constraint(), input, v1, 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 2201 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, input, LinkNode::link, max_ii(), power_of_10_greater_equal_to(), v1, 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 2147 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 2767 of file delaunay_2d.cc.
References input.
Referenced by delaunay_calc().
|
static |
Definition at line 898 of file delaunay_2d.cc.
References blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add(), and src.
|
static |
Definition at line 893 of file delaunay_2d.cc.
References blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add().
Referenced by add_edge_constraint(), add_face_ids(), and get_cdt_output().
::CDT_result* BLI_delaunay_2d_cdt_calc | ( | const ::CDT_input * | input, |
const CDT_output_type | output_type | ||
) |
This function uses the double version of #CDT::delaunay_calc. Almost all of the work here is to convert between C++ #Arrays<Vector<int>> and a C version that linearizes all the elements and uses a "start" and "len" array to say where the individual vectors start and how long they are.
Definition at line 2817 of file delaunay_2d.cc.
References delaunay_2d_calc(), e, input, MEM_malloc_arrayN, MEM_mallocN, output, v, x, and y.
void BLI_delaunay_2d_cdt_free | ( | ::CDT_result * | result | ) |
Definition at line 2952 of file delaunay_2d.cc.
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 1239 of file delaunay_2d.cc.
References BLI_assert, blender::meshintersect::cdt_draw(), BMVert::co, dc_tri_valid(), blender::meshintersect::SymEdge< Arith_t >::face, filtered_incircle(), filtered_orient2d(), blender::meshintersect::SymEdge< Arith_t >::next, next, blender::meshintersect::SymEdge< Arith_t >::rot, blender::meshintersect::sym(), t, std::to_string(), v1, v2, vert_left_of_symedge(), and vert_right_of_symedge().
Referenced by dc_triangulate().
|
inline |
Definition at line 1227 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 1439 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 2792 of file delaunay_2d.cc.
References delaunay_calc(), and input.
Referenced by BLI_delaunay_2d_cdt_calc(), blender::nodes::node_geo_curve_fill_cc::do_cdt(), and blender::io::obj::fixup_invalid_polygon().
CDT_result<T> delaunay_calc | ( | const CDT_input< T > & | input, |
CDT_output_type | output_type | ||
) |
Definition at line 2775 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(), initial_triangulation(), and input.
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 2496 of file delaunay_2d.cc.
References blender::meshintersect::SymEdge< Arith_t >::face, is_constrained_edge(), blender::threading::parallel_for(), and blender::meshintersect::sym().
Referenced by prepare_cdt_for_output().
Definition at line 2278 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().
void dump_crossings | ( | const Vector< CrossData< T >, inline_crossings_size > & | crossings | ) |
Definition at line 1853 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 959 of file delaunay_2d.cc.
References find_symedge_between_verts(), v1, 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 1679 of file delaunay_2d.cc.
References BLI_assert, BMVert::co, blender::math::distance(), blender::math::distance_squared(), blender::robust_pred::epsilon, fill_crossdata_for_through_vert(), blender::math::isect_seg_seg(), CrossData< T >::lambda, CrossData< T >::out, blender::meshintersect::sym(), T, t, 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 1637 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 735 of file delaunay_2d.cc.
References Freestyle::a, usdtokens::b(), Freestyle::c, 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 668 of file delaunay_2d.cc.
References Freestyle::a, usdtokens::b(), Freestyle::c, 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 1200 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 929 of file delaunay_2d.cc.
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 944 of file delaunay_2d.cc.
Referenced by add_edge_constraint().
CDT_result<T> get_cdt_output | ( | CDT_state< T > * | cdt_state, |
const CDT_input< T > | UNUSEDinput, | ||
CDT_output_type | output_type | ||
) |
Definition at line 2647 of file delaunay_2d.cc.
References add_to_input_ids(), BLI_assert, BMVert::co, e, is_deleted_edge(), prepare_cdt_for_output(), result, and v.
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 1828 of file delaunay_2d.cc.
References BMVert::co, blender::robust_pred::epsilon, fill_crossdata_for_intersect(), filtered_orient2d(), CrossData< T >::in, blender::length_parameterize::interpolate(), CrossData< T >::lambda, blender::meshintersect::SymEdge< Arith_t >::next, blender::meshintersect::sym(), v2, and blender::meshintersect::SymEdge< Arith_t >::vert.
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 1777 of file delaunay_2d.cc.
References BLI_assert, BMVert::co, fill_crossdata_for_intersect(), fill_crossdata_for_through_vert(), filtered_orient2d(), t, tri_orient(), v2, and CrossData< T >::vert.
Referenced by add_edge_constraint().
|
static |
Definition at line 883 of file delaunay_2d.cc.
Referenced by add_face_ids().
|
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.
bool in_line< double > | ( | const FatCo< double > & | a, |
const FatCo< double > & | b, | ||
const FatCo< double > & | c | ||
) |
Definition at line 787 of file delaunay_2d.cc.
References Freestyle::a, usdtokens::b(), Freestyle::c, and blender::math::dot().
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 1479 of file delaunay_2d.cc.
References dc_triangulate(), find_site_merges(), and sort().
Referenced by delaunay_calc().
|
inline |
Definition at line 905 of file delaunay_2d.cc.
References e.
Definition at line 910 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 915 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 920 of file delaunay_2d.cc.
References v.
|
static |
Definition at line 2177 of file delaunay_2d.cc.
References BLI_assert, and x.
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 2600 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 1502 of file delaunay_2d.cc.
References Freestyle::a, usdtokens::b(), Freestyle::c, BMVert::co, count, exists_edge(), filtered_incircle(), blender::meshintersect::sym(), and v.
Referenced by add_edge_constraint().
Definition at line 2461 of file delaunay_2d.cc.
References BLI_assert, and is_constrained_edge().
Referenced by prepare_cdt_for_output().
Remove all non-constraint edges.
Definition at line 2309 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 2362 of file delaunay_2d.cc.
References Freestyle::a, usdtokens::b(), BMVert::co, dissolve_symedge(), blender::math::distance_squared(), BMVert::e, e, blender::meshintersect::SymEdge< Arith_t >::face, is_constrained_edge(), is_deleted_edge(), sort(), blender::meshintersect::sym(), and vert_touches_face().
Referenced by prepare_cdt_for_output().
Definition at line 2411 of file delaunay_2d.cc.
References BLI_assert, BLI_linklist_pop(), BLI_linklist_prepend(), dissolve_symedge(), blender::meshintersect::SymEdge< Arith_t >::face, 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 1176 of file delaunay_2d.cc.
References Freestyle::a, and usdtokens::b().
|
inline |
Definition at line 1548 of file delaunay_2d.cc.
References filtered_orient2d(), and t.
Referenced by get_next_crossing_from_vert().
Definition at line 1215 of file delaunay_2d.cc.
References BMVert::co, filtered_orient2d(), and v.
Referenced by dc_tri().
Definition at line 1220 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 967 of file delaunay_2d.cc.
References v.
Referenced by remove_non_constraint_edges_leave_valid_bmesh().
|
constexpr |
Definition at line 1851 of file delaunay_2d.cc.
Referenced by add_edge_constraint().