Link Search Menu Expand Document

Delaunay 2D

PCGEx | Cluster : Delaunay 2D

Outputs a 2D Delaunay triangulation.

The Delaunay 2D node outputs a 2D Delaunay triangulation with options like Urquhart graph, hull identification, and projection settings.

In
Points clouds that will be triangulated
Vtx
Endpoints of the output Edges
Edges
Edges associated with the output Vtxs
Sites
Delaunay Sites

★ See Example Project @ EdgesAndGraphs/PCGEx_Graph_Delaunay-2D

Table of content

This node creates a 2D Delaunay graph from the input points. If you’d like to know more about Delaunay intrinsic properties, check out the Wikipedia article!
It has very very interesting properties, and this node also offers the ability to output the Urquhart alternative; which is even more fascinating.

details/diagrams/diagrams-delaunay-2d-lead.png

Properties


Property Description
Settings  
Urquhart If enabled, the node will output the Urquhart version of the Delaunay graph.
This enables additional options for site output.
Hull Attribute Name
Boolean 		If enabled, will flag output Vtx points that lie on the convex hull of the graph.
Mark Edge on Touch If enabled, edges that have at least a point on the Hull as marked as being on the hull; as opposed to only be marked as hull edges if both endpoints are on the hull.

Sites


details/diagrams/diagrams-delaunay-2d-sites.png

Output Sites If enabled, the node will output the Delaunay Sites.
Each site is the centroid of a Delaunay triangle.
Site Hull Attribute Name
Boolean 		If enabled, will flag output site points that have at least an edge that lie on the convex hull of the graph.
Urquhart Sites Merge Defines if and how Delaunay Sites should be merged when they are part of a single “Urquhart” cell.

Urquhart Sites Merge

Mode  
details/diagrams/enum-sitemerge-none.png None
Outputs canon Delaunay sites.
details/diagrams/enum-sitemerge-sites.png Merge Sites
The output site is the average of all the canon Delaunay sites that are abstracted by the Urquhart pass.
details/diagrams/enum-sitemerge-edges.png Merge Edges
The output site is the average of all the edges removed by the Urquhart pass.

Which merge mode to use, if any, depends on your final intent. If your goal is find the contours of an Urquhart “cell”, then Merge Edges offer usually more interesting sites positions.

Projection Settings


Property Description
Target Distance Target Distance reference..
Whether to consider point bounds, and if so, how.
Fuse Method Lets you choose the method for finding neighbors & collocated points
Voxel Grid Offset Offset the voxelized grid by an constant amount.
By default the center of the grid is 0,0,0, which may look like an undersirable offset. That offset can be manually compensated using this parameter.
Inline Insertion Using the Octree fuse method is not deterministic by default.
Enabling inlined insertion will make it so, at the cost of speed.
Source Distance Source Distance reference.
Whether to consider point bounds, and if so, how.
Tolerance  
Component Wise Tolerance If enabled, lets you set individual tolerance in world space for each X, Y and Z axis.
Tolerance Uniform tolerance. This represent the radius within which elements will be considered in fuse range.
Tolerances If enabled, represent individual axis’ radius within which elements will be considered in fuse range.
Local Tolerance If enabled, lets your use per-point tolerance value.
NOT IMPLEMENTED
Property Description
Enable Self Intersection If enabled, a cluster will test if intersection exists against itself. Otherwise, only check against other clusters.
Fuse Details  
Source Distance Source Distance reference.
Whether to consider point bounds, and if so, how.
Component Wise Tolerance If enabled, lets you set individual tolerance in world space for each X, Y and Z axis.
Tolerance Uniform tolerance. This represent the radius within which elements will be considered in fuse range.
Tolerances If enabled, represent individual axis’ radius within which elements will be considered in fuse range.
Local Tolerance If enabled, lets your use per-point tolerance value.
NOT IMPLEMENTED
Outputs  
Snap on Edge If enabled, snap the intersection position onto the original edge, as opposed to the reverse.
Intersector Attribute Name
bool 		If enabled, flag the points that intersected with an edge.

The projection settings control how the point position is translated to a 2D space before the graph is computed; and how this projection will translate back to the original space, if relevant.

Property Description
Projection Normal Normal vector of the plane used for projection.
By default, the projection plan normal is Up; so the graph is computed over the X Y plane.
Local Projection Normal If enabled, uses a per-point projection vector.
Local Normal Attribute ti read normal from,

Local projection normal is very powerful but can also be very clunky to use – it’s very easy to end up with singularities that will prevent the graph from being properly computed.

Cluster Output Settings

See Working with Clusters - Cluster Output Settings.

Tips

The delaunay algorithm creates a convex hull of very, very long edges, so you’ll often need to remove them to “clean” the graph. There are multiple approaches to to that, the two most straighfoward approaches being:

Hull pruning

  • Simply enable the Hull mark, filter these Vtx out and sanitize the cluster afterward.

details/diagrams/diagrams-delaunay-2d-hull-pruning.png

Prune by Length

  • Use Prune edges by Length to remove outliers. This is a more conversative approach compared to the one above, as it will keep the smaller hull edges.

details/diagrams/diagrams-delaunay-2d-hull-pruning2.png