All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GQ_StraightSkeleton Class Reference

#include <GQ_StraightSkeleton.h>

Public Types

 How to determine inside/outside from the input graph. More...
enum  OffsetGeoType { OFFSET_CURVES = 0, OFFSET_SURFACES = 1 }

Public Member Functions

 GQ_StraightSkeleton ()
virtual ~GQ_StraightSkeleton ()
void setPlane (const UT_Vector3 &normal, fpreal distance)
 Set the plane where triangulation happens. More...
bool fitPlane (const GU_Detail *gdp, const GA_PointGroup *pointGroup=0, UT_Vector3 *outNormal=0, fpreal *outDistance=0)
 Fit a plane to the input points. Returns true if it succeeded. More...
void setInOutType (InOutType type)
InOutType getInOutType () const
void setInsideWeightAttrib (const char *attrib)
const UT_StringHoldergetInsideWeightAttrib () const
void setOutsideWeightAttrib (const char *attrib)
const UT_StringHoldergetOutsideWeightAttrib () const
void setDistanceTol (fpreal64 tol)
fpreal64 getDistanceTol () const
void setParallelismTol (fpreal64 tol)
fpreal64 getParallelismTol () const
void computeSkeleton (GU_Detail *gdp, const GA_PrimitiveGroup *prim_group)
UT_ErrorSeverity getSkeletonComputationErrorSeverity ()
void getSkeletonComputationErrors (UT_ErrorManager &errors)
void buildOffsetGeometry (GU_Detail *gdp, OffsetGeoType type, fpreal64 distance, int ndivs, bool inside, bool outside, bool keep_input, const GA_PrimitiveGroup *input_group, GA_PrimitiveGroup *inside_group, GA_PrimitiveGroup *outside_group, bool split_curves_to_omit_end_caps, const char *edge_dist_attrib_name, const char *edge_speed_attrib_name, bool updatePointNormals=true)
UT_Vector2 make2D (const UT_Vector3 &pos) const
 Project 3D point onto plane. More...
UT_Vector3 make3D (const UT_Vector2 &pos) const

Detailed Description

Straight skeleton computation for general polygonal figures in a 2D plane.

The algorithm used is a kinetic triangulation, originally described by Aichholzer, Aurenhammer in "Straight Skeletons for General Polygonal Figures in the Plane", with some implementation details filled in by Palfrader, Held and Huber in "On Computing Straight Skeletons by Means of Kinetic Triangulations".

We use GQ_PolyDelaunay internally for the initial triangulation.

Definition at line 50 of file GQ_StraightSkeleton.h.

Member Enumeration Documentation

How to determine inside/outside from the input graph.


The vertex order of any primitives referencing an edge determines which side of the edge is considered the inside or the outside.

NB: This is the fallback method if any of the other ones fail.


Outermost edge loops, if any, separate the outside region from the inside(s).


A nested separation of the plane into outside and inside regions.


A nested separation of the plane into outside and inside regions with inside regions extending through shared edges.

Definition at line 68 of file GQ_StraightSkeleton.h.


Definition at line 124 of file GQ_StraightSkeleton.h.

Constructor & Destructor Documentation

GQ_StraightSkeleton::GQ_StraightSkeleton ( )

Some local typedefs for our helper classes to avoid having to fully qualify the names everywhere.

virtual GQ_StraightSkeleton::~GQ_StraightSkeleton ( )

Member Function Documentation

void GQ_StraightSkeleton::buildOffsetGeometry ( GU_Detail gdp,
OffsetGeoType  type,
fpreal64  distance,
int  ndivs,
bool  inside,
bool  outside,
bool  keep_input,
const GA_PrimitiveGroup input_group,
GA_PrimitiveGroup inside_group,
GA_PrimitiveGroup outside_group,
bool  split_curves_to_omit_end_caps,
const char *  edge_dist_attrib_name,
const char *  edge_speed_attrib_name,
bool  updatePointNormals = true 

The distance parameter is actually interpreted as the time during the wavefront propagation. This is the same thing for skeletons computed without local edge weights and, for skeletons with local edge weights, where our interest really lies.

void GQ_StraightSkeleton::computeSkeleton ( GU_Detail gdp,
const GA_PrimitiveGroup prim_group 
bool GQ_StraightSkeleton::fitPlane ( const GU_Detail gdp,
const GA_PointGroup pointGroup = 0,
UT_Vector3 outNormal = 0,
fpreal outDistance = 0 

Fit a plane to the input points. Returns true if it succeeded.

fpreal64 GQ_StraightSkeleton::getDistanceTol ( ) const

Definition at line 110 of file GQ_StraightSkeleton.h.

InOutType GQ_StraightSkeleton::getInOutType ( ) const

Definition at line 89 of file GQ_StraightSkeleton.h.

const UT_StringHolder& GQ_StraightSkeleton::getInsideWeightAttrib ( ) const

Definition at line 100 of file GQ_StraightSkeleton.h.

const UT_StringHolder& GQ_StraightSkeleton::getOutsideWeightAttrib ( ) const

Definition at line 104 of file GQ_StraightSkeleton.h.

fpreal64 GQ_StraightSkeleton::getParallelismTol ( ) const

Definition at line 117 of file GQ_StraightSkeleton.h.

void GQ_StraightSkeleton::getSkeletonComputationErrors ( UT_ErrorManager errors)
UT_ErrorSeverity GQ_StraightSkeleton::getSkeletonComputationErrorSeverity ( )
UT_Vector2 GQ_StraightSkeleton::make2D ( const UT_Vector3 pos) const

Project 3D point onto plane.

UT_Vector3 GQ_StraightSkeleton::make3D ( const UT_Vector2 pos) const
void GQ_StraightSkeleton::setDistanceTol ( fpreal64  tol)

The tolerance used to identify coincident points during triangle collapses.

void GQ_StraightSkeleton::setInOutType ( InOutType  type)

Definition at line 88 of file GQ_StraightSkeleton.h.

void GQ_StraightSkeleton::setInsideWeightAttrib ( const char *  attrib)

Assigning attributes to use for edge weights turns this into a weighted straight skeleton. We only support positive weighted straight skeletons, ignoring any zero or negative edge weights and replacing them with a weight of 1.

Edge weights can be queried from a vertex, point, or primitive attribute, in that order of priority.

Definition at line 98 of file GQ_StraightSkeleton.h.

void GQ_StraightSkeleton::setOutsideWeightAttrib ( const char *  attrib)

Definition at line 102 of file GQ_StraightSkeleton.h.

void GQ_StraightSkeleton::setParallelismTol ( fpreal64  tol)

The tolerance used to identify parallel edges to detect infinitely fast moving wavefront points during triangle collapsed. Bisectors of edges with angles (in radians) less than this will be considered infinitely fast.

void GQ_StraightSkeleton::setPlane ( const UT_Vector3 normal,
fpreal  distance 

Set the plane where triangulation happens.

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