BLI_delaunay_2d.hh File Reference

#include "BLI_array.hh"
#include "BLI_math_mpq.hh"
#include "BLI_math_vector_mpq_types.hh"
#include "BLI_math_vector_types.hh"
#include "BLI_vector.hh"

Go to the source code of this file.

Classes
class	blender::meshintersect::CDT_input< T >
class	blender::meshintersect::CDT_result< T >

Namespaces
namespace	blender
namespace	blender::meshintersect

Enumerations
enum	CDT_output_type {   CDT_FULL , CDT_INSIDE , CDT_INSIDE_WITH_HOLES , CDT_CONSTRAINTS ,   CDT_CONSTRAINTS_VALID_BMESH , CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES }

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

Detailed Description

This header file contains both a C interface and a C++ interface to the 2D Constrained Delaunay Triangulation library routine.

Definition in file BLI_delaunay_2d.hh.

Enumeration Type Documentation

CDT_output_type

enum CDT_output_type

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. What triangles and edges of CDT are desired when getting output?

Enumerator
CDT_FULL	All triangles, outer boundary is convex hull.
CDT_INSIDE	All triangles fully enclosed by constraint edges or faces.
CDT_INSIDE_WITH_HOLES	Like previous, but detect holes and omit those from output.
CDT_CONSTRAINTS	Only point, edge, and face constraints, and their intersections.
CDT_CONSTRAINTS_VALID_BMESH	Like CDT_CONSTRAINTS, but keep enough edges so that any output faces that came from input faces can be made as valid BMesh faces in Blender: that is, no vertex appears more than once and no isolated holes in faces.
CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES	Like previous, but detect holes and omit those from output.

Definition at line 54 of file BLI_delaunay_2d.hh.