libgenua
Basic Geometry, Numerical Algorithms and Interfaces
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Groups Pages
Classes | Functions
Geometry

This module defines basic geometric primitives for topology operations, such as simple classes which can be used to efficiently compute element and node connectivity tables for various types of meshes. More...

Classes

class  BasicEdge
 Basic two-vertex edge object. More...
 
class  BasicTriangle
 Basic linear triangle object. More...
 
class  BndRect
 Axis-oriented Rectangle. More...
 
class  BndBox
 Bounding box. More...
 
class  CgMesh
 Mesh container for visualization. More...
 
class  CgStrip
 Index container for triangle/line/quad strips/fans. More...
 
class  HavelHerout< FloatType >
 Triangle-ray intersection according to Havel & Herout. More...
 
class  ImplicitTree
 Balanced binary tree using implicit references to content. More...
 
class  DopBase< Type, N >
 Discrete oriented polytopes. More...
 
class  Dop2d2< Type >
 2D axis-aligned 2D bounding box expressed as a k-DOP. More...
 
class  Dop3d3< Type >
 Axis-aligned 3D bounding box expressed as a k-DOP. More...
 
class  Dop3d4< Type >
 Octahedral bounding volume in 3D. More...
 
class  Dop4d4< Type >
 Axis-aligned 4D bounding box expressed as a k-DOP. More...
 
class  Dop3d9< Type >
 9-plane discrete polytope in 3D. More...
 
class  Line< N >
 Line in euclidian space. More...
 
class  NDPointTree< ND, FloatType >
 Balanced binary tree for N-dimensional points. More...
 
class  Plane
 A plane in three dimensions. More...
 
class  PointGrid< N, Type >
 Points on a rectangular grid. More...
 
struct  point_less< N, Type, C >
 Comparator to sort points by coordinate. More...
 
class  PointList< N, Type >
 Contiguously stored array of n-d points. More...
 
class  TrafoTpl< FloatType >
 Geometric transformations. More...
 

Functions

template<typename FloatType , uint ND>
bool qr_segment_nearest (const SVector< ND, FloatType > sa[], const SVector< ND, FloatType > sb[], SVector< 2, FloatType > &tab)
 Parameters that minimize the distance between two segments. More...
 
template<typename FloatType >
bool qr_project_point (const SVector< 3, FloatType > tri[], const SVector< 3, FloatType > &p, SVector< 2, FloatType > &uv)
 Projection of a point onto a triangle. More...
 
template<typename FloatType >
FloatType qr_sqdistance (const SVector< 3, FloatType > tri[], const SVector< 3, FloatType > &p)
 Minimum distance of a point from triangle. More...
 
template<typename FloatType >
FloatType qr_tritri_sqdistance (const SVector< 3, FloatType > t1[], const SVector< 3, FloatType > t2[], FloatType sqlimit=FloatType(0))
 Minimum distance between two triangles. More...
 
template<typename FloatType >
bool adp_project_point (const SVector< 3, FloatType > tri[], const SVector< 3, FloatType > &p, SVector< 2, FloatType > &uv)
 Project point on triangle. More...
 
template<typename FloatType >
FloatType adp_sqdistance (const SVector< 3, FloatType > tri[], const SVector< 3, FloatType > &p)
 Minimum distance of a point from triangle. More...
 
template<bool test_in_line, typename FloatType >
bool mt_line_triangle (const FloatType lineOrigin[3], const FloatType lineDirection[3], const FloatType tri0[3], const FloatType tri1[3], const FloatType tri2[3], FloatType &t, FloatType &u, FloatType &v)
 Line-triangle intersection computation (Möller-Trumbore) More...
 
template<bool test_in_line, typename FloatType >
bool mt_line_triangle (const FloatType lineOrigin[3], const FloatType lineDirection[3], const FloatType tri0[3], const FloatType tri1[3], const FloatType tri2[3])
 Pure triangle-line intersection test. More...
 
template<typename FloatType >
bool segura_line_triangle (const FloatType lineP1[], const FloatType lineP2[], const FloatType triP1[], const FloatType triP2[], const FloatType triP3[])
 Test one line against multiple triangles at once. More...
 
template<class FloatType >
bool point_in_polygon (int nv, const FloatType poly[], const FloatType p[])
 Determine whether a point is inside a polygon. More...
 
template<typename FloatType >
void rxyz_slerp (const FloatType ra[], const FloatType rb[], FloatType s, FloatType rs[])
 Shortest-path spherical linear interpolation (SLERP). More...
 
template<uint N, typename FloatType >
void radial_repldup (const PointList< N, FloatType > &pts, Indices &repl, Indices &keep, FloatType threshold=gmepsilon)
 Radial sorting for point de-duplication. More...
 

Detailed Description

This module defines basic geometric primitives for topology operations, such as simple classes which can be used to efficiently compute element and node connectivity tables for various types of meshes.

Furthermore, a collection of basic intersection tests on triangles and lines is implemented.

A second class of objects is used to implement efficient bounding-volume hierarchies such as k-DOP trees in various dimensions. Many of the corresponding algorithms and containers have been used for a long time and have therefore seen relatively extensive optimization (and therefore allow, for example, to create low-overhead representations such as implicit binary trees defined by storage order).

To support visualization applications, containers for typical triangle-only meshes (including triangle strips and fans) are available.

Function Documentation

template<typename FloatType >
bool adp_project_point ( const SVector< 3, FloatType >  tri[],
const SVector< 3, FloatType > &  p,
SVector< 2, FloatType > &  uv 
)

Project point on triangle.

This function does exactly the same as qr_project_point(), but tries to compute the solution from the normal equations, which is a much less stable problem. If that fails, switches to the QR algorithm. Do not use this version if cancellation errors are a concern.

See Also
qr_project_point
template<typename FloatType >
FloatType adp_sqdistance ( const SVector< 3, FloatType >  tri[],
const SVector< 3, FloatType > &  p 
)

Minimum distance of a point from triangle.

Returns the squared distance of p from tri, by means of the solution of the normal equations when possible, otherwise using qr_sqdistance.

See Also
qr_sqdistance
template<bool test_in_line, typename FloatType >
bool mt_line_triangle ( const FloatType  lineOrigin[3],
const FloatType  lineDirection[3],
const FloatType  tri0[3],
const FloatType  tri1[3],
const FloatType  tri2[3],
FloatType &  t,
FloatType &  u,
FloatType &  v 
)

Line-triangle intersection computation (Möller-Trumbore)

The boolean template argument determines whether intersections outside the line parameter range are rejected (segment-triangle test) or not (ray-triangle test). Due to the early exit conditions, settings this to 'true' is faster, but not always what you need.

Tomas Möller and Ben Trumbore: "Fast, Minimum Storage Ray-Triangle Intersection", journal of graphics, gpu, and game tools, 2(1),21-28,1997

template<bool test_in_line, typename FloatType >
bool mt_line_triangle ( const FloatType  lineOrigin[3],
const FloatType  lineDirection[3],
const FloatType  tri0[3],
const FloatType  tri1[3],
const FloatType  tri2[3] 
)

Pure triangle-line intersection test.

This function checks for triangle-line intersection and does not actually compute the intersection point; returns only an intersection indication.

template<class FloatType >
bool point_in_polygon ( int  nv,
const FloatType  poly[],
const FloatType  p[] 
)

Determine whether a point is inside a polygon.

This is the low-level implementation; the version acting on a PointList is likely more useful in practice.

See Also
PointList
template<typename FloatType >
bool qr_project_point ( const SVector< 3, FloatType >  tri[],
const SVector< 3, FloatType > &  p,
SVector< 2, FloatType > &  uv 
)

Projection of a point onto a triangle.

Uses numerically stable, but expensive QR-factorization to determine the barycentric coordinates (u,v) of the point on tri closest to p. Returns false if the problem is ill-posed, eg. for a degenerate triangle with identical vertices, or if the point projection is outside the triangle boundaries.

See Also
adp_project_point
template<typename FloatType , uint ND>
bool qr_segment_nearest ( const SVector< ND, FloatType >  sa[],
const SVector< ND, FloatType >  sb[],
SVector< 2, FloatType > &  tab 
)
inline

Parameters that minimize the distance between two segments.

For two line segments a and b in ND-space, compute the line parameters which minimize the distance between the segments. Returns true if the point of least distance lies within [0,1] for both segments.

template<typename FloatType >
FloatType qr_sqdistance ( const SVector< 3, FloatType >  tri[],
const SVector< 3, FloatType > &  p 
)

Minimum distance of a point from triangle.

Returns the squared distance of p from tri. Projects p onto tri; if the projection is inside the triangle, returns the distance from p. Otherwise, computes the distance from the nearest triangle edge.

See Also
adp_sqdistance
template<typename FloatType >
FloatType qr_tritri_sqdistance ( const SVector< 3, FloatType >  t1[],
const SVector< 3, FloatType >  t2[],
FloatType  sqlimit = FloatType(0) 
)

Minimum distance between two triangles.

Tests the squared distance of all points in t1 against t2 and vice versa. Returns prematurely if any distance found smaller than the threshold value passed as argument.

See Also
qr_sqdistance
template<uint N, typename FloatType >
void radial_repldup ( const PointList< N, FloatType > &  pts,
Indices &  repl,
Indices &  keep,
FloatType  threshold = gmepsilon 
)

Radial sorting for point de-duplication.

This free function can be used to identify and replace duplicate points in a set. It is meant as an alternative for NDPointTree which provides the same functionality, albeit with significantly higher memory overhead. If nearest neighbor or radius queries are not required, this function can be useful.

See Also
NDPointTree
template<typename FloatType >
void rxyz_slerp ( const FloatType  ra[],
const FloatType  rb[],
FloatType  s,
FloatType  rs[] 
)

Shortest-path spherical linear interpolation (SLERP).

Interpolate between rotation ra and rb, both expressed as angles for the rotation sequence Rx-Ry-Rz (x-y'-z'') at parameter 0 <= s <= 1. The result is returned in the array rs containing the angular representation (Rx-Ry-Rz) of the interpolated rotation. Note that the angles in rs are not necessarily bounded by the values in ra and rb.

template<typename FloatType >
bool segura_line_triangle ( const FloatType  lineP1[],
const FloatType  lineP2[],
const FloatType  triP1[],
const FloatType  triP2[],
const FloatType  triP3[] 
)

Test one line against multiple triangles at once.

Alternative line-triangle intersection test.

This is an alternative test which, according to the comparison paper below, is faster than the Möller-Trumbore function. Profiling shows that that is not the case today.

Rafael J. Segura and Francisco R. Feito: "ALGORITHMS TO TEST RAY-TRIANGLE INTERSECTION -- COMPARATIVE STUDY"

See Also
mt_line_triangle