Class for computing approximate geodesic distances on a mesh. More...

#include <geodesic.h>

Classes
struct	DIJKDist

struct	FaceDist

class	GeodData

struct	pred

struct	VertDist

Public Types
typedef MeshType::VertexType	VertexType

typedef MeshType::VertexIterator	VertexIterator

typedef MeshType::VertexPointer	VertexPointer

typedef MeshType::FacePointer	FacePointer

typedef MeshType::FaceType	FaceType

typedef MeshType::CoordType	CoordType

typedef MeshType::ScalarType	ScalarType

Static Public Member Functions
template<class DistanceFunctor >
static ScalarType	GeoDistance (DistanceFunctor &distFunc, const VertexPointer &pw, const VertexPointer &pw1, const VertexPointer &curr, const ScalarType &d_pw1, const ScalarType &d_curr)

template<class DistanceFunctor >
static VertexPointer	Visit (MeshType &m, std::vector< VertDist > &seedVec, DistanceFunctor &distFunc, ScalarType distance_threshold=std::numeric_limits< ScalarType >::max(), typename MeshType::template PerVertexAttributeHandle< VertexPointer > vertSource=NULL, typename MeshType::template PerVertexAttributeHandle< VertexPointer > vertParent=NULL, std::vector< VertexPointer > *InInterval=NULL)

static bool	Compute (MeshType &m, const std::vector< VertexPointer > &seedVec)
	High-level wrapper: compute approximate geodesic distances from seeds.

template<class DistanceFunctor >
static bool	Compute (MeshType &m, const std::vector< VertexPointer > &seedVec, DistanceFunctor &distFunc, ScalarType maxDistanceThr=std::numeric_limits< ScalarType >::max(), std::vector< VertexPointer > withinDistanceVec=NULL, typename MeshType::template PerVertexAttributeHandle< VertexPointer > sourceSeed=NULL, typename MeshType::template PerVertexAttributeHandle< VertexPointer > *parentSeed=NULL)

static bool	DistanceFromBorder (MeshType &m, typename MeshType::template PerVertexAttributeHandle< VertexPointer > *sources=NULL)

static bool	ConvertPerVertexSeedToPerFaceSeed (MeshType &m, const std::vector< VertexPointer > &vertexSeedVec, std::vector< FacePointer > &faceSeedVec)

static std::string	sourcesAttributeName (void)

static std::string	parentsAttributeName (void)

template<class DistanceFunctor >
static void	PerFaceDijkstraCompute (MeshType &m, const std::vector< FacePointer > &seedVec, DistanceFunctor &distFunc, ScalarType maxDistanceThr=std::numeric_limits< ScalarType >::max(), std::vector< FacePointer > *InInterval=NULL, FacePointer FaceTarget=NULL, bool avoid_selected=false)

template<class DistanceFunctor >
static void	PerVertexDijkstraCompute (MeshType &m, const std::vector< VertexPointer > &seedVec, DistanceFunctor &distFunc, ScalarType maxDistanceThr=std::numeric_limits< ScalarType >::max(), std::vector< VertexPointer > InInterval=NULL, typename MeshType::template PerVertexAttributeHandle< VertexPointer > sourceHandle=NULL, typename MeshType::template PerVertexAttributeHandle< VertexPointer > *parentHandle=NULL, bool avoid_selected=false, VertexPointer target=NULL)

Detailed Description

template<class MeshType>
class vcg::tri::Geodesic< MeshType >

Class for computing approximate geodesic distances on a mesh.

This class implements approximate geodesic distance computations (vertex- and face-based) using Dijkstra-like propagation combined with a local triangle update (see GeoDistance) for improved accuracy across faces.

The implementation uses a mailbox-style marking strategy (see GeodData) to avoid a linear per-vertex reinitialization between multiple runs. Thanks to this approach repeated geodesic computations avoid full linear initialization of per-vertex data and the practical cost is proportional to the number of visited vertices (i.e. O(output) plus heap costs) rather than always being strictly linear in the mesh size.

Requirements:

Vertex-face adjacency (VF) for vertex-based routines and face-face (FF) adjacency for face-based routines.
Per-vertex or per-face Quality is used to store computed distances.

See individual method documentation for more detail on parameters and optional per-vertex/per-face attributes (e.g. sources, parent, geod).

See also: trimesh_geodesic.cpp

Member Function Documentation

◆ Compute()

template<class MeshType >

static bool vcg::tri::Geodesic< MeshType >::Compute	(	MeshType &	m,
		const std::vector< VertexPointer > &	seedVec
	)

inlinestatic

High-level wrapper: compute approximate geodesic distances from seeds.

Given a mesh and a vector of seed vertex pointers, this wrapper computes the approximated geodesic distance from the supplied sources to all mesh vertices within maxDistanceThr. Computed distances are stored in the vertex Quality component unless withinDistanceVec is supplied (in which case only the vertices pushed into withinDistanceVec will have their Quality updated).

Optional outputs:

sourceSeed: per-vertex handle that, if supplied, will be filled with the closest seed for each visited vertex.
parentSeed: per-vertex handle that, if supplied, will be filled with the parent in the shortest-path tree (best-effort; see notes in code).

Example attribute allocation:

typename MeshType::template PerVertexAttributeHandle<VertexPointer> sourcesHandle;
sourcesHandle = tri::Allocator<MeshType>::AddPerVertexAttribute<MeshType::VertexPointer>(m, "sources");
 
typename MeshType::template PerVertexAttributeHandle<VertexPointer> parentHandle;
parentHandle = tri::Allocator<MeshType>::AddPerVertexAttribute<MeshType::VertexPointer>(m, "parent");

Requirements:

VF adjacency relations and per-vertex Quality (the routine will write distances into Quality).

Performance note:

Older versions of this code always performed a linear-time reinitialization of per-vertex data. The current implementation uses the GeodData mailbox-marking approach to avoid full clears between runs, so repeated calls are effectively proportional to the number of visited vertices (plus heap overhead), i.e. O(output) in practice.

Returns: true if seed vector is non-empty and the operation was started.

◆ Visit()

template<class MeshType >

template<class DistanceFunctor >

static VertexPointer vcg::tri::Geodesic< MeshType >::Visit	(	MeshType &	m,
		std::vector< VertDist > &	seedVec,
		DistanceFunctor &	distFunc,
		ScalarType	distance_threshold = `std::numeric_limits<ScalarType>::max()`,
		typename MeshType::template PerVertexAttributeHandle< VertexPointer > *	vertSource = `NULL`,
		typename MeshType::template PerVertexAttributeHandle< VertexPointer > *	vertParent = `NULL`,
		std::vector< VertexPointer > *	InInterval = `NULL`
	)

inlinestatic

Low-level geodesic propagation routine.

Starting from a set of seed vertices (with initial distances provided in seedVec), this routine propagates approximate geodesic distances across the mesh and assigns a distance value to each visited vertex. The distance stored for a vertex is an approximation of the geodesic distance to the closest seed.

Notes:

distFunc is used to compute the (possibly anisotropic) cost between vertices; several functors are provided (e.g. EuclideanDistance, IsotropicDistance, AnisotropicDistance).
If vertSource/vertParent attribute handles are supplied, the routine will set them to the closest source and parent in the shortest-path tree.
If InInterval is supplied, it will be filled with the list of vertices reached within distance_threshold.
The per-vertex geod attribute is used together with the mailbox (GeodData) mechanism to avoid a full O(n) reinitialization between subsequent calls; this makes repeated runs cost roughly proportional to the number of visited vertices plus heap overhead.

Requirements:

VF adjacency and per-vertex Quality (the routine writes distances into the Quality field unless InInterval is provided).

For a simpler front-end use the Compute wrappers below.

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

vcg/complex/algorithms/geodesic.h

Classes

Public Types

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ Compute()

◆ Visit()