Blender  V3.3
Classes | Namespaces | Macros | Functions | Variables
delaunay_2d.cc File Reference
#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< Tget_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< Tdelaunay_calc (const CDT_input< T > &input, CDT_output_type output_type)
 
blender::meshintersect::CDT_result< doubledelaunay_2d_calc (const CDT_input< double > &input, CDT_output_type output_type)
 
::CDT_resultBLI_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
 

Macro Definition Documentation

◆ DEBUG_CDT

#define DEBUG_CDT

Definition at line 360 of file delaunay_2d.cc.

◆ SX

#define SX (   x)    (((x)-minx) * scale)

◆ SY

#define SY (   y)    ((maxy - (y)) * scale)

Function Documentation

◆ add_edge_constraint()

template<typename T >
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().

◆ add_edge_constraints()

template<typename T >
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().

◆ add_face_constraints()

template<typename T >
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().

◆ add_face_ids()

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 
)

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().

◆ add_input_verts()

template<typename T >
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().

◆ add_list_to_input_ids()

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

◆ add_to_input_ids()

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

◆ BLI_delaunay_2d_cdt_calc()

::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.

◆ BLI_delaunay_2d_cdt_free()

void BLI_delaunay_2d_cdt_free ( ::CDT_result result)

Definition at line 2952 of file delaunay_2d.cc.

References MEM_freeN, and result.

◆ dc_tri()

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 
)

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().

◆ dc_tri_valid()

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

Definition at line 1227 of file delaunay_2d.cc.

References filtered_orient2d().

Referenced by dc_tri().

◆ dc_triangulate()

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

Definition at line 1439 of file delaunay_2d.cc.

References dc_tri(), and v.

Referenced by initial_triangulation().

◆ delaunay_2d_calc()

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

◆ delaunay_calc()

template<typename T >
CDT_result<T> delaunay_calc ( const CDT_input< T > &  input,
CDT_output_type  output_type 
)

◆ detect_holes()

template<typename T >
void detect_holes ( CDT_state< T > *  cdt_state)

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

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

Definition at line 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().

◆ dissolve_symedge()

template<typename T >
void dissolve_symedge ( CDT_state< T > *  cdt_state,
SymEdge< T > *  se 
)

◆ dump_crossings()

template<typename T >
void dump_crossings ( const Vector< CrossData< T >, inline_crossings_size > &  crossings)

◆ exists_edge()

template<typename T >
bool exists_edge ( const CDTVert< T > *  v1,
const CDTVert< T > *  v2 
)
inline

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().

◆ fill_crossdata_for_intersect()

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 
)

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().

◆ fill_crossdata_for_through_vert()

template<typename T >
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().

◆ filtered_incircle()

template<typename T >
static int filtered_incircle ( const FatCo< T > &  a,
const FatCo< T > &  b,
const FatCo< T > &  c,
const FatCo< T > &  d 
)
static

A filtered version of incircle.

Referenced by dc_tri(), and re_delaunay_triangulate().

◆ filtered_incircle< double >()

template<>
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().

◆ filtered_orient2d()

template<typename T >
static int filtered_orient2d ( const FatCo< T > &  a,
const FatCo< T > &  b,
const FatCo< T > &  c 
)
static

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

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

◆ filtered_orient2d< double >()

template<>
int 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_site_merges()

template<typename T >
void 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 1200 of file delaunay_2d.cc.

References BMVert::co, and v.

Referenced by initial_triangulation().

◆ find_symedge_between_verts()

template<typename T >
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.

References t, v1, and v2.

Referenced by add_edge_constraint(), and exists_edge().

◆ find_symedge_with_face()

template<typename T >
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.

References t, and v.

Referenced by add_edge_constraint().

◆ get_cdt_output()

template<typename T >
CDT_result<T> get_cdt_output ( CDT_state< T > *  cdt_state,
const CDT_input< T >   UNUSEDinput,
CDT_output_type  output_type 
)

◆ get_next_crossing_from_edge()

template<typename T >
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.

◆ get_next_crossing_from_vert()

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 
)

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().

◆ id_range_in_list()

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

Definition at line 883 of file delaunay_2d.cc.

Referenced by add_face_ids().

◆ in_line()

template<typename T >
static bool in_line ( const FatCo< T > &  a,
const FatCo< T > &  b,
const FatCo< T > &  c 
)
static

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

◆ in_line< double >()

template<>
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().

◆ initial_triangulation()

template<typename T >
void 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 1479 of file delaunay_2d.cc.

References dc_triangulate(), find_site_merges(), and sort().

Referenced by delaunay_calc().

◆ is_border_edge()

template<typename T >
bool is_border_edge ( const CDTEdge< T > *  e,
const CDT_state< T > *  cdt 
)
inline

Definition at line 905 of file delaunay_2d.cc.

References e.

◆ is_constrained_edge()

template<typename T >
bool is_constrained_edge ( const CDTEdge< T > *  e)
inline

◆ is_deleted_edge()

template<typename T >
bool is_deleted_edge ( const CDTEdge< T > *  e)
inline

◆ is_original_vert()

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

Definition at line 920 of file delaunay_2d.cc.

References v.

◆ power_of_10_greater_equal_to()

static int power_of_10_greater_equal_to ( int  x)
static

Definition at line 2177 of file delaunay_2d.cc.

References BLI_assert, and x.

Referenced by add_face_constraints().

◆ prepare_cdt_for_output()

template<typename T >
void prepare_cdt_for_output ( CDT_state< T > *  cdt_state,
const CDT_output_type  output_type 
)

◆ re_delaunay_triangulate()

template<typename T >
static void re_delaunay_triangulate ( CDTArrangement< T > *  cdt,
SymEdge< T > *  se 
)
static

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

Definition at line 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().

◆ remove_faces_in_holes()

template<typename T >
void remove_faces_in_holes ( CDT_state< T > *  cdt_state)

Definition at line 2461 of file delaunay_2d.cc.

References BLI_assert, and is_constrained_edge().

Referenced by prepare_cdt_for_output().

◆ remove_non_constraint_edges()

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

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().

◆ remove_non_constraint_edges_leave_valid_bmesh()

template<typename T >
void remove_non_constraint_edges_leave_valid_bmesh ( CDT_state< T > *  cdt_state)

◆ remove_outer_edges_until_constraints()

template<typename T >
void remove_outer_edges_until_constraints ( CDT_state< T > *  cdt_state)

◆ site_lexicographic_sort()

template<typename T >
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().

◆ tri_orient()

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

Definition at line 1548 of file delaunay_2d.cc.

References filtered_orient2d(), and t.

Referenced by get_next_crossing_from_vert().

◆ vert_left_of_symedge()

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

Definition at line 1215 of file delaunay_2d.cc.

References BMVert::co, filtered_orient2d(), and v.

Referenced by dc_tri().

◆ vert_right_of_symedge()

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

Definition at line 1220 of file delaunay_2d.cc.

References BMVert::co, filtered_orient2d(), and v.

Referenced by dc_tri().

◆ vert_touches_face()

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

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().

Variable Documentation

◆ inline_crossings_size

constexpr int inline_crossings_size = 128
constexpr

Definition at line 1851 of file delaunay_2d.cc.

Referenced by add_edge_constraint().