Geometry

Files
file	Conversions.h
	3D geometry conversion routines.
file	ConvexHull2D.h
	2-D convex hull routines
file	geometry/primitives.h
	Contains ordering primitives used in geometry computations.
file	rayprimitives.h
	Contains primitives that allow rays to be represented as points at infinity.

Namespaces
	Geometry
	Contains all definitions in the Geometry package.

Classes
class	Geometry::Arrangement1D
	An arrangement of 1-D intervals. Intervals identified by an integer ID. More...
class	Geometry::CollisionMesh
	A triangle mesh along with PQP bounding volume structures that enable fast collision and other proximity queries. More...
class	Geometry::CollisionMeshQuery
	A general-purpose distance querying class. More...
class	Geometry::Grid
	A gridding of n-dimensional space. More...
class	Geometry::GridHash3D
	A grid containing objects (referenced by void pointers) More...
class	Geometry::GridSubdivision3D
	A grid with a list of arbitrary objects (given by void pointers) More...
class	Geometry::GridHash
	An ND grid containing objects (referenced by void pointers) More...
class	Geometry::GridSubdivision
	An ND grid with a list of arbitrary objects (given by void pointers) More...
class	Geometry::GridTable< T >
	A table with entry T on a gridding of n-dimensional space. More...
class	Geometry::KDTree
	A kd-tree or a node of one. More...
struct	Geometry::XMonotoneChain
	A polyline with vertices ordered in nondecreasing order. More...
class	Geometry::ApproximatePenetrationDepth
	Uses a propagation method to calculate an approximate penetration distance of mesh m1 inside m2. More...
struct	Geometry::Angular2DOrdering
struct	Geometry::PointRay2D
	A 2D point or infinite ray. Note: rays should be normalized unit vectors. More...
struct	Geometry::PointRay3D
	A 3D point or infinite ray. Note: rays should be normalized unit vectors. More...
class	Geometry::SegmentOverlay
	Computes the overlay of a set of segments using a sweep line algorithm. More...
class	Geometry::DenseTSDFReconstruction
	Performs a kinect-fusion-like dense TSDF reconstruction. More...
class	Geometry::SparseTSDFReconstruction
	Performs a kinect-fusion-like sparse TSDF reconstruction. A hash grid is used to build multiple TSDFs across an infinite domain. More...

Functions
void	Geometry::MeshToPointCloud (const Meshing::TriMesh &mesh, Meshing::PointCloud3D &pc, Real maxDispersion=Inf, bool wantNormals=false)
	Places points on the vertices of a mesh. If any triangle has vertices farther away than maxDispersion, the triangle is subdivided until all triangles are covered by balls of radius maxDispersion.
void	Geometry::PointCloudToMesh (const Meshing::PointCloud3D &pc, Meshing::TriMesh &mesh, Real depthDiscontinuity=Inf)
	If a point cloud is structured, this creates a uniform mesh out of it. If depthDiscontinuity is provided, the mesh is split at the points where the relative depth of adjacent points is greater than depthDiscontinuity * average depth. (A decent value is 0.02 for typical depth sensors.)
void	Geometry::PointCloudToMesh (const Meshing::PointCloud3D &pc, Meshing::TriMesh &mesh, GLDraw::GeometryAppearance &appearance, Real depthDiscontinuity=Inf)
	Same as normal PointCloudToMesh, but colors and UV coordinates are extracted.
void	Geometry::PrimitiveToMesh (const GeometricPrimitive3D &primitive, Meshing::TriMesh &mesh, int numDivs)
	Creates a mesh for a geometric primitive. If the primitive has curved surfaces, they are split into numDivs strips.
void	Geometry::PrimitiveToImplicitSurface (const GeometricPrimitive3D &primitive, Meshing::VolumeGrid &grid, Real resolution, Real expansion=0)
	Creates an implicit surface for a geometric primitive. The grid has resolution no more than resolution on each axis.
void	Geometry::MeshToImplicitSurface_FMM (const CollisionMesh &mesh, Meshing::VolumeGrid &grid, Real resolution)
	Creates an implicit surface for a mesh using a Fast Marching Method. More...
void	Geometry::MeshToImplicitSurface_SpaceCarving (const CollisionMesh &mesh, Meshing::VolumeGrid &grid, Real resolution, int numViews=20)
	Creates an implicit surface for a mesh using a space-carving technique. The grid has resolution no less than resolution on each axis. numViews views (6 orthographic, numViews-6 random) are taken of the mesh to create the space carving. More...
void	Geometry::ImplicitSurfaceToMesh (const Meshing::VolumeGrid &grid, Meshing::TriMesh &mesh)
	Creates a mesh from an implicit surface via Marching Cubes. This assumes the values of the grid are defined at the cell centers, unlike the methods in MarchingCubes.h which assume the array defines values at the cell corners... this performs the necessary correction.
int	Geometry::ConvexHull2D_Chain (const Point2D P[], int n, Point2D H[])
	Compute the convex hull of a set of sorted points (or point-rays) More...
int	Geometry::ConvexHull2D_Chain (const PointRay2D P[], int n, PointRay2D H[])
int	Geometry::ConvexHull2D_Chain (const Point2D P[], int n, Point2D H[], int Hindex[])
int	Geometry::ConvexHull2D_Chain (const PointRay2D P[], int n, PointRay2D H[], int Hindex[])
int	Geometry::ConvexHull2D_Chain_Unsorted (Point2D P[], int n, Point2D H[])
	Same as above, but unsorted input. Upon exit, the contents of P are rearranged in lexicographical order.
int	Geometry::ConvexHull2D_Chain_Unsorted (PointRay2D P[], int n, PointRay2D H[])
int	Geometry::ConvexHull2D_Chain_Unsorted (Point2D P[], int n, Point2D H[], int Hindex[])
int	Geometry::ConvexHull2D_Chain_Unsorted (PointRay2D P[], int n, PointRay2D H[], int Hindex[])
void	Geometry::Point2DListToPlanes (const Point2D P[], int n, Plane2D H[])
	Given a list of points on a convex hull, return a list of planes along edges with normals pointing outward. More...
int	Geometry::Point2DListToPlanes (const PointRay2D P[], int n, Plane2D H[])
bool	Geometry::Lexical2DOrder (const Point2D &p1, const Point2D &p2)
	Lexical < order on 2D points.
bool	Geometry::Lexical3DOrder (const Point3D &p1, const Point3D &p2)
	Lexical < order on 3D points.
Real	Geometry::Orient2D (const Point2D &p0, const Point2D &p1, const Point2D &p2)
	Orientation of p2 relative to p1, relative to p0. More...
Real	Geometry::HomogeneousCmp (Real a, bool awZero, Real b, bool bwZero)
	Comparison of 1D points in homogeneous coordinates. More...
Real	Geometry::HomogeneousSub (Real a, bool awZero, Real b, bool bwZero)
	Subtraction of 1D points in homogeneous coordinates.
bool	Geometry::LexicalRay2DOrder (const PointRay2D &p1, const PointRay2D &p2)
bool	Geometry::LexicalRay3DOrder (const PointRay3D &p1, const PointRay3D &p2)
Real	Geometry::OrientRay2D (const PointRay2D &p0, const PointRay2D &p1, const PointRay2D &p2)
ostream &	std::operator<< (ostream &out, const Geometry::PointRay2D &pt)

Variables
bool	Geometry::PointRay2D::isRay
bool	Geometry::PointRay3D::isRay

Detailed Description

Function Documentation

int Geometry::ConvexHull2D_Chain	(	const Point2D	P[],
		int	n,
		Point2D	H[]
	)

Compute the convex hull of a set of sorted points (or point-rays)

Uses Andrew's monotone chain algorithm which is O(n).

Parameters

P	an array of 2D points presorted by increasing x- and y-coordinates
n	the number of points in P[]
H	an array of the convex hull vertices (max is n+1) (NOTE THAT THE SIZE OF H SHOULD BE n+1, NOT n)
HIndex	(optional) for each convex hull vertex, the index of the original vertex in P

Returns

the number of points in H

References ConvexHull2D_Chain(), Orient2D(), and OrientRay2D().

Referenced by ConvexHull2D_Chain(), and ConvexHull2D_Chain_Unsorted().

Real Geometry::HomogeneousCmp ( Real  a, bool  awZero, Real  b, bool  bwZero  )

inline

Comparison of 1D points in homogeneous coordinates.

The 1D points are given in homogeneous coordinates a/aw, b/bw

Returns

< 0 if a < b = 0 if a = b

0 if a > b

bool Geometry::LexicalRay2DOrder ( const PointRay2D &  p1, const PointRay2D &  p2  )

inline

Lexical < order on 2D point/rays

See also

Lexical2DOrder

Referenced by ConvexHull2D_Chain_Unsorted().

bool Geometry::LexicalRay3DOrder ( const PointRay3D &  p1, const PointRay3D &  p2  )

inline

Lexical < order on 3D point/rays

See also

Lexical3DOrder

void Geometry::MeshToImplicitSurface_FMM	(	const CollisionMesh &	mesh,
		Meshing::VolumeGrid &	grid,
		Real	resolution
	)

Creates an implicit surface for a mesh using a Fast Marching Method.

Note: the mesh's current transform is NOT taken into account (i.e., the resulting grid is in local coordinates)

References Meshing::FastMarchingMethod_Fill().

Referenced by Geometry::AnyCollisionGeometry3D::Convert().

void Geometry::MeshToImplicitSurface_SpaceCarving	(	const CollisionMesh &	mesh,
		Meshing::VolumeGrid &	grid,
		Real	resolution,
		int	numViews = 20
	)

Creates an implicit surface for a mesh using a space-carving technique. The grid has resolution no less than resolution on each axis. numViews views (6 orthographic, numViews-6 random) are taken of the mesh to create the space carving.

Note: the mesh's current transform is NOT taken into account (i.e., the resulting grid is in local coordinates)

References Math3D::GetCanonicalBasis(), Math::SampleSphere(), and Meshing::VolumeGridTemplate< T >::TrilinearInterpolate().

Real Geometry::Orient2D ( const Point2D &  p0, const Point2D &  p1, const Point2D &  p2  )

inline

Orientation of p2 relative to p1, relative to p0.

Returns

>0 for p2 left of the line through p0 and p1 =0 for p2 on the line <0 for p2 right of the line

Referenced by ConvexHull2D_Chain().

Real Geometry::OrientRay2D ( const PointRay2D &  p0, const PointRay2D &  p1, const PointRay2D &  p2  )

inline

Orientation of p2 relative to p1, relative to p0.

See also

Orient2D

Referenced by ConvexHull2D_Chain(), and ConvexHull2D_Chain_Unsorted().

void Geometry::Point2DListToPlanes	(	const Point2D	P[],
		int	n,
		Plane2D	H[]
	)

Given a list of points on a convex hull, return a list of planes along edges with normals pointing outward.

H must have storage for n planes. For the PointRay version, the number of returned planes may be less than n.

Returns

The number of planes.

References HomogeneousSub(), and Point2DListToPlanes().

Referenced by Geometry::UnboundedPolytope2D::CalcPlanes(), and Point2DListToPlanes().