Blender  V3.3
Public Attributes | List of all members
CDT_input Struct Reference

#include <BLI_delaunay_2d.h>

Public Attributes

int verts_len
 
int edges_len
 
int faces_len
 
float(* vert_coords )[2]
 
int(* edges )[2]
 
int * faces
 
int * faces_start_table
 
int * faces_len_table
 
float epsilon
 
bool need_ids
 

Detailed Description

Interface for Constrained Delaunay Triangulation (CDT) in 2D.

The input is a set of vertices, edges between those vertices, and faces using those vertices. Those inputs are called "constraints". The output must contain those constraints, or at least edges, points, and vertices that may be pieced together to form the constraints. Part of the work of doing the CDT is to detect intersections and mergers among the input elements, so these routines are also useful for doing 2D intersection.

The output is a triangulation of the plane that includes the constraints in the above sense, and also satisfies the "Delaunay condition" as modified to take into account that the constraints must be there: for every non-constrained edge in the output, there is a circle through the endpoints that does not contain any of the vertices directly connected to those endpoints. What this means in practice is that as much as possible the triangles look "nice" – not too long and skinny.

Optionally, the output can be a subset of the triangulation (but still containing all of the constraints), to get the effect of 2D intersection.

The underlying method is incremental, but we need to know beforehand a bounding box for all of the constraints. This code can be extended in the future to allow for deletion of constraints, if there is a use in Blender for dynamically maintaining a triangulation. Input to Constrained Delaunay Triangulation. There are verts_len vertices, whose coordinates are given by vert_coords. For the rest of the input, vertices are referred to by indices into that array. Edges and Faces are optional. If provided, they will appear in the output triangulation ("constraints"). One can provide faces and not edges – the edges implied by the faces will be inferred.

The edges are given by pairs of vertex indices. The faces are given in a triple (faces, faces_start_table, faces_len_table) to represent a list-of-lists as follows: the vertex indices for a counterclockwise traversal of face number i starts at faces_start_table[i] and has faces_len_table[i] elements.

The edges implied by the faces are automatically added and need not be put in the edges array, which is intended as a way to specify edges that are not part of any face.

Some notes about some special cases and how they are handled:

Epsilon is used for "is it near enough" distance calculations. If zero is supplied for epsilon, an internal value of 1e-8 used instead, since this code will not work correctly if it is not allowed to merge "too near" vertices.

Normally the output will contain mappings from outputs to inputs. If this is not needed, set need_ids to false and the execution may be much faster in some circumstances.

Definition at line 104 of file BLI_delaunay_2d.h.

Member Data Documentation

◆ edges

int(* CDT_input::edges)[2]

Definition at line 109 of file BLI_delaunay_2d.h.

◆ edges_len

int CDT_input::edges_len

Definition at line 106 of file BLI_delaunay_2d.h.

◆ epsilon

float CDT_input::epsilon

Definition at line 113 of file BLI_delaunay_2d.h.

◆ faces

int* CDT_input::faces

Definition at line 110 of file BLI_delaunay_2d.h.

◆ faces_len

int CDT_input::faces_len

Definition at line 107 of file BLI_delaunay_2d.h.

◆ faces_len_table

int* CDT_input::faces_len_table

Definition at line 112 of file BLI_delaunay_2d.h.

◆ faces_start_table

int* CDT_input::faces_start_table

Definition at line 111 of file BLI_delaunay_2d.h.

◆ need_ids

bool CDT_input::need_ids

Definition at line 114 of file BLI_delaunay_2d.h.

◆ vert_coords

float(* CDT_input::vert_coords)[2]

Definition at line 108 of file BLI_delaunay_2d.h.

◆ verts_len

int CDT_input::verts_len

Definition at line 105 of file BLI_delaunay_2d.h.


The documentation for this struct was generated from the following file: