Physsim::CompGeom Class Reference

Class for performing assorted computational geometry functions. More...

#include <CompGeom.h>

List of all members.

Public Types
enum	SegSegIntersectType { SegSegNoIntersect, SegSegIntersect, SegSegVertex, SegSegEdge }
enum	SegTriIntersectType {   SegTriNoIntersect, SegTriInclFace, SegTriInclVertex, SegTriInclEdge,   SegTriInside, SegTriVertex, SegTriEdge, SegTriFace,   SegTriEdgeOverlap, SegTriPlanarIntersect }
enum	SegPlaneIntersectType {   SegPlaneInPlane, SegPlaneToSide, SegPlaneFirst, SegPlaneSecond,   SegPlaneOtherIntersect }
enum	PolygonLocation { PolygonInside, PolygonOutside, PolygonOnVertex, PolygonOnEdge }
enum	SegBoxIntersectType {   SegBoxNoIntersect, SegBoxFullyInside, SegBoxPartiallyInside, SegBoxSurfaceIntersect,   SegBoxPointIntersect, SegBoxPassThrough }
Static Public Member Functions
static Vector3	generate_point_on_plane (const Vector3 &normal, Real d)
	Generates a point on a plane.
static SegBoxIntersectType	intersect_seg_box (const Vector3 &lo, const Vector3 &hi, const std::pair< Vector3, Vector3 > &seg, Vector3 &isect1, Vector3 &isect2)
	Intersects a line segment with a box.
static bool	is_convex_polygon (const std::list< Vector3 > &polygon, const Vector3 &normal)
	Determines whether a polygon is convex.
static std::list< TrianglePtr >	triangulate_convex_polygon (const std::list< Vector3 > &polygon)
	Triangulates a convex polygon in O(n).
static bool	intersect_noncoplanar_tris (const Triangle &t1, const Triangle &t2, Vector3 &p1, Vector3 &p2)
	Intersects two non-coplanar triangles in 3D and returns the line of intersection.
static boost::shared_ptr< std::list< Vector3 > >	intersect_tris (const Triangle &t1, const Triangle &t2)
	Intersects two triangles in 3D and returns the points of intersection.
static Real	fit_plane (const std::list< Vector3 > &points, Vector3 &normal, Real &d)
	Attempts to fit a plane to a set of points.
static SegTriIntersectType	intersect_seg_tri (const Triangle &t, const std::pair< Vector3, Vector3 > &seg, Vector3 &isect, Vector3 &isect2)
	Determines the intersection between a line segment and triangle in 3D.
static SegSegIntersectType	intersect_segs_3D (const std::pair< Vector3, Vector3 > &s1, const std::pair< Vector3, Vector3 > &s2, Vector3 &isect, Vector3 &isect2)
	Determines whether two line segments in 3D intersect.
static SegPlaneIntersectType	intersect_seg_plane (const Triangle &tri, const std::pair< Vector3, Vector3 > &seg, Vector3 &isect, unsigned int &big_dim)
	Determines the intersection between a line segment and a plane in 3D.
static boost::shared_ptr< std::list< Vector3 > >	calc_convex_hull_2D (const std::list< Vector3 > &points, const VectorN &normal)
	Calculates the convex hull of a set of points that lie on a 2D manifold using quickhull.
static PolyhedronPtr	calc_convex_hull_3D (const std::list< Vector3 > &points)
	Calculates the convex hull of points in 3D using quickhull.
static boost::shared_ptr< std::list< Vector3 > >	intersect_coplanar_tris (const Triangle &t1, const Triangle &t2, const Vector3 &normal, Real d)
	Intersects two coplanar triangles.
static SegSegIntersectType	intersect_segs_2D (const std::pair< Vector2, Vector2 > &s1, const std::pair< Vector2, Vector2 > &s2, Vector2 &isect, Vector2 &isect2)
	Determines whether two line segments in 2D intersect.
static PolygonLocation	polygon_location (const std::list< Vector2 > &polygon, const Vector2 &point)
	Determines whether a 2D point is inside a polygon.
static bool	collinear (const Vector3 &a, const Vector3 &b, const Vector3 &c)
	Determines whether three points are collinear.
static bool	collinear (const Vector2 &a, const Vector2 &b, const Vector2 &c)
	Determines whether three points are collinear.
static LongReal	volume (const Vector3 &a, const Vector3 &b, const Vector3 &c, const Vector3 &d)
	Gets the volume of a tetrahedron composed of vertices a, b, c, d.
static int	volume_sign (const Vector3 &a, const Vector3 &b, const Vector3 &c, const Vector3 &d)
	Gets the sign of the volume of a tetrahedron composed of vertices a, b, c, d.
static Vector3	calc_centroid_2D (const std::list< Vector3 > &poly, const Vector3 &normal)
	Computes the 3D (2D) centroid of points on a plane.
static void	project_plane (std::list< Vector3 > &points, const Vector3 &normal, Real d)
	Projects a set of points onto a plane.
static bool	coplanar (const Triangle &t1, const Triangle &t2)
	Determines whether two triangles are coplanar.
static Real	calc_area (const std::list< Vector3 > &poly, const Vector3 &normal)
	Computes the area of points on a plane.
static Vector3	to_3D (const Vector2 &v)
	Converts a 2D vector to a 3D vector.
static Vector3	to_3D (const Vector2 &v, Real d)
	Converts a 2D vector to a 3D vector.
static Vector2	to_2D (const Vector3 &v)
	Converts a 3D vector to a 2D vector.
static void	det_line_endpoints (std::list< Vector3 > &points, std::pair< Vector3, Vector3 > &endpoints)
	Determines the two endpoints of a set of colinear points (in time n lg n).
static void	det_line_endpoints (std::list< Vector2 > &points, std::pair< Vector2, Vector2 > &endpoints)
	Determines the two endpoints of a set of colinear points (in time n lg n).
static bool	query_intersect_tri_tri (const Triangle &t1, const Triangle &t2)
template<class ForwardIterator>
static bool	collinear (ForwardIterator first, ForwardIterator last)
	Determines whether a set of points is collinear.
template<class ForwardIterator>
static PolyhedronPtr	calc_convex_hull_3D (ForwardIterator first, ForwardIterator last)
	Computes the 3D convex hull of a set of points.
template<class ForwardIterator>
static Vector3	calc_centroid (ForwardIterator first, ForwardIterator last)
	Computes the centroid of a set of facets.

---

Detailed Description

Class for performing assorted computational geometry functions.

---

Member Function Documentation

CompGeom::SegBoxIntersectType CompGeom::intersect_seg_box	(	const Vector3 &	lo,
		const Vector3 &	hi,
		const std::pair< Vector3, Vector3 > &	seg,
		Vector3 &	isect1,
		Vector3 &	isect2
	)			[static]

Intersects a line segment with a box.

Parameters:

	lo	the lower corner of the box
	hi	the upper corner of the box
	seg	the line segment to query
	isect1	the first point of intersection (if not SegBoxNoIntersect)
	isect2	the second point of intersection (if SegBoxPartiallyInside, SegBoxFullyInside, SegBoxPassThrough, or SegBoxSurfaceIntersect)

Returns:

SegBoxIntersect if the two do not intersect, SegBoxFullyInside if the line segment is fully contained within the box, SegBoxPartiallyInside if the line segment is partially contained within the box (one endpoint is inside the box), SegBoxSurfaceIntersect if the line segment intersects on the surface of the box at infinite points, SegBoxPointIntersect if the line segment intersects on the surface of the box at a single point, or SegBoxPassThrough if the segment intersects the surface of the box at exactly two points.

Todo:

test this function

std::list< TrianglePtr > CompGeom::triangulate_convex_polygon

(

const std::list< Vector3 > &

polygon

)

[static]

Triangulates a convex polygon in O(n).

Parameters:

polygon

a connected, counter-clockwise oriented, convex polygon; additionally, the first point is assumed to be connected to the last)

bool CompGeom::intersect_noncoplanar_tris	(	const Triangle &	t1,
		const Triangle &	t2,
		Vector3 &	p1,
		Vector3 &	p2
	)			[static]

Intersects two non-coplanar triangles in 3D and returns the line of intersection.

Parameters:

	t1	the first triangle
	t2	the second triangle
	p1	an endpoint of the line of intersection (on return)
	p2	an endpoint of the line of intersection (on return)

Returns:

true if the triangles intersect, false if they don't intersect or are coplanar

boost::shared_ptr< std::list< Vector3 > > CompGeom::intersect_tris	(	const Triangle &	t1,
		const Triangle &	t2
	)			[static]

Intersects two triangles in 3D and returns the points of intersection.

Note:

up to five points can be returned

Real CompGeom::fit_plane	(	const std::list< Vector3 > &	points,
		Vector3 &	normal,
		Real &	d
	)			[static]

Attempts to fit a plane to a set of points.

The singular value decomposition is used to determine the plane that fits the points best in a least-squares sense.

Parameters:

	points	the set of points (in 3D)
	normal	contains the "best" normal, on return

Returns:

the maximum deviation from the plane

CompGeom::SegTriIntersectType CompGeom::intersect_seg_tri	(	const Triangle &	t,
		const std::pair< Vector3, Vector3 > &	seg,
		Vector3 &	isect,
		Vector3 &	isect2
	)			[static]

Determines the intersection between a line segment and triangle in 3D.

Adapted from O'Rourke, p. 238.

Parameters:

	t	a triangle in 3D
	seg	a line segment in 3D
	isect	contains the point of intersection, if any (on return)
	isect2	contains a second point of intersect, if the intersection type is seg_tri_inside, seg_tri_edge_overlap, or seg_tri_planar_intersect (on return)

Returns:

SegTriInside (if the segment lies wholly within the plane of the triangle), SegTriVertex (if an endpoint of the segment coincides with a vertex of the triangle), SegTriEdge (if an endpoint of the segment is in the relative interior of an edge of the triangle), SegTriFace (if an endpoint of the segment is in the relative interior of the face of the triangle), SegTriInclVertex (if the open segment includes a vertex of the triangle), SegTriInclEdge (if the open segment includes a point in the relative interior of an edge of the triangle), SegTriInclFace (if the open segment includes a point in the relative interior of a face of the triangle), SegTriEdgeOverlap (if the segment overlaps one edge of the triangle [or vice versa]), SegTriPlanarIntersect (if the segment lies partially within the face of the triangle), or SegTriNoIntersect (if there is no intersection).

CompGeom::SegSegIntersectType CompGeom::intersect_segs_3D	(	const std::pair< Vector3, Vector3 > &	s1,
		const std::pair< Vector3, Vector3 > &	s2,
		Vector3 &	isect,
		Vector3 &	isect2
	)			[static]

Determines whether two line segments in 3D intersect.

Parameters:

	s1	the points of the first line segment
	s2	the points of the second line segment
	isect	the point of intersection (if any)
	isect2	the second point of intersection (for edge intersection)

Returns:

the intersection type (edge, vertex, true_intersect, no_intersect); an edge intersection indicates that the segments collinearly overlap; vertex intersection indicates that an endpoint of one segment is on the other segment, but edge intersection does not hold; true_intersect indicates that the segments intersect at a single point.

CompGeom::SegPlaneIntersectType CompGeom::intersect_seg_plane	(	const Triangle &	tri,
		const std::pair< Vector3, Vector3 > &	seg,
		Vector3 &	isect,
		unsigned int &	big_dim
	)			[static]

Determines the intersection between a line segment and a plane in 3D.

Parameters:

	tri	a 3D triangle that is fully contained in the plane to be intersected
	seg	a 3D line segment
	isect	the point of intersection (on return)
	big_dim	the dimension of the largest component (on return)
	NEAR_ZERO	the tolerance to test for zero

Returns:

the intersection type: SegPlaneInPlane (segment lies wholly within the plane), SegPlaneFirst (first vertex of segment is on the plane, but not the second), SegPlaneSecond (second vertex of segment is on the plane, but not the first), SegPlaneToSide (the segment lies strictly to one side or the other of the plane), or SegPlaneOtherIntersect (segment intersects the plane, and in-plane, first, and second do not hold).

boost::shared_ptr< std::list< Vector3 > > CompGeom::calc_convex_hull_2D	(	const std::list< Vector3 > &	points,
		const VectorN &	normal
	)			[static]

Calculates the convex hull of a set of points that lie on a 2D manifold using quickhull.

Parameters:

	points	the set of points in 3D
	normal	the (optional) normal of the points; this will be computed using SVD if not provided

Returns:

the convex hull of the points (ordered counter-clockwise)

boost::shared_ptr< std::list< Vector3 > > CompGeom::intersect_coplanar_tris	(	const Triangle &	t1,
		const Triangle &	t2,
		const Vector3 &	normal,
		Real	d
	)			[static]

Intersects two coplanar triangles.

Parameters:

	normal	a normal to both triangles
	d	the plane intercept for the plane equation that contains both triangles

Returns:

a counter-clockwise oriented polygon (in 3D) describing the intersection; the orientation is with respect to the given normal

CompGeom::SegSegIntersectType CompGeom::intersect_segs_2D	(	const std::pair< Vector2, Vector2 > &	s1,
		const std::pair< Vector2, Vector2 > &	s2,
		Vector2 &	isect,
		Vector2 &	isect2
	)			[static]

Determines whether two line segments in 2D intersect.

Taken from O'Rourke, p. 224.

Parameters:

	s1	the points of the first line segment
	s2	the points of the second line segment
	isect	the point of intersection (if any)
	isect2	the second point of intersection (for edge intersection)

Returns:

the intersection type (edge, vertex, true_intersect, no_intersect); an edge intersection indicates that the segments collinearly overlap; vertex intersection indicates that an endpoint of one segment is on the other segment, but edge intersection does not hold; true_intersect indicates that the segments intersect at a single point.

CompGeom::PolygonLocation CompGeom::polygon_location	(	const std::list< Vector2 > &	polygon,
		const Vector2 &	point
	)			[static]

Determines whether a 2D point is inside a polygon.

Adapted from O'Rourke, p. 244.

Parameters:

	polygon	a vector of points that describe a polygon (orientation irrelevant); each successive vertex in the vector is connected to the previous vector to make the polygon (polygon.front() and polygon.back() are connected as well)
	point	the point to test

Returns:

inside_poly if point is inside the polygon, on_vertex if the point coincides with a vertex, on_edge if the point lies on an edge of the polygon (but not a vertex), or outside_poly if the point is outside of the polygon

int CompGeom::volume_sign	(	const Vector3 &	a,
		const Vector3 &	b,
		const Vector3 &	c,
		const Vector3 &	d
	)			[static]

Gets the sign of the volume of a tetrahedron composed of vertices a, b, c, d.

Returns:

-1 if d is "visible" from the plane of (a,b,c); 0 if the a,b,c, and d are coplanar, and +1 otherwise

Vector3 CompGeom::calc_centroid_2D	(	const std::list< Vector3 > &	poly,
		const Vector3 &	normal
	)			[static]

Computes the 3D (2D) centroid of points on a plane.

Parameters:

	poly	a counter-clockwise oriented polygon in 3D
	normal	a vector normal to the plane that contains the points

void CompGeom::project_plane	(	std::list< Vector3 > &	points,
		const Vector3 &	normal,
		Real	d
	)			[static]

Projects a set of points onto a plane.

This method is intended to be used with fit_plane() to project the set of points exactly onto a plane; note that this method is unnecessary if the points fit a plane exactly.

Real CompGeom::calc_area	(	const std::list< Vector3 > &	poly,
		const Vector3 &	normal
	)			[static]

Computes the area of points on a plane.

Parameters:

	poly	a counter-clockwise oriented polygon in 3D
	normal	a vector normal to the plane that contains the points

Vector3 CompGeom::to_3D

(

const Vector2 &

v

)

[static]

Converts a 2D vector to a 3D vector.

Note:

the last dimension is set to zero

Vector3 CompGeom::to_3D	(	const Vector2 &	v,
		Real	d
	)			[static]

Converts a 2D vector to a 3D vector.

Note:

the last dimension is set to d

Vector2 CompGeom::to_2D

(

const Vector3 &

v

)

[static]

Converts a 3D vector to a 2D vector.

Note:

the last dimension is stripped

void CompGeom::det_line_endpoints	(	std::list< Vector3 > &	points,
		std::pair< Vector3, Vector3 > &	endpoints
	)			[static]

Determines the two endpoints of a set of colinear points (in time n lg n).

Parameters:

	points	a set of points; this set will be sorted on return
	endpoints	the endpoints of the line will be placed here on return

void CompGeom::det_line_endpoints	(	std::list< Vector2 > &	points,
		std::pair< Vector2, Vector2 > &	endpoints
	)			[static]

Determines the two endpoints of a set of colinear points (in time n lg n).

Parameters:

	points	a set of points; this set will be sorted on return
	endpoints	the endpoints of the line will be placed here on return

bool CompGeom::query_intersect_tri_tri	(	const Triangle &	t1,
		const Triangle &	t2
	)			[static]

Determines whether two triangles intersect.

Returns:

true if the triangles intersect

template<class ForwardIterator>

PolyhedronPtr Physsim::CompGeom::calc_convex_hull_3D	(	ForwardIterator	first,
		ForwardIterator	last
	)			[static]

Computes the 3D convex hull of a set of points.

Parameters:

	first	a forward iterator for type Vector3
	last	a forward iterator for type Vector3

Returns:

a pointer to the newly created polyhedron

template<class ForwardIterator>

Vector3 Physsim::CompGeom::calc_centroid	(	ForwardIterator	first,
		ForwardIterator	last
	)			[static]

Computes the centroid of a set of facets.

The facets may represent a polygon, a polyhedron, or even an open polyhedron. However, the facets may not intersect.

---

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

• /home/drumwrig/Physsim/include/Physsim/CompGeom.h
• /home/drumwrig/Physsim/src/CompGeom.cpp

---