VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z > Class Template Reference

Provides general functions for VRS Vectors. More...

#include <vrs/algorithm.h>

List of all members.

Public Types

enum LineSection {
SCR_BEFORE_A, SCR_AT_A, SCR_BETWEEN_AB, SCR_AT_B,
SCR_AFTER_B
}

Given a line section (a,b) and a point p, the following method checks the location of p (or the projection of p onto the line <(a,b)>) relative to the section (a,b). More...

Static Public Member Functions

static SO< PolygonSet > convexHull3D (SO< Iterator< Vector > > points)

static SO< Iterator< Vector > > convexHull2D (SO< Iterator< Vector > > points)

static SO< Iterator< Vector > > convexHull2D (SO< Iterator< Vector > > points, const Vector &planeNormal, const Vector &onPlane=Vector::origin)

static Vector projectOntoPlane (const Vector &point, const Vector &planeNormal, const Vector &onPlane=Vector(0, 0, 0))

static SO< Iterator< Vector > > projectOntoPlane (SO< Iterator< Vector > > points, const Vector &planeNormal, const Vector &onPlane=Vector(0, 0, 0))

static bool intersectPlanes (const Vector &planeNormal1, const Vector &onPlane1, const Vector &planeNormal2, const Vector &onPlane2, const Vector &planeNormal3, const Vector &onPlane3, Vector &intersectionPoint)

static bool linePlaneIntersection (const Vector &planeNormal, const Vector &onPlane, const Vector &a, const Vector &b, Vector &intersectionPoint, bool checkSection=true)

static bool rayTriangleIntersection (const Ray &ray, const Vector &t1, const Vector &t2, const Vector &t3, Vector &intersectionPoint)

static double signedDistance (const Vector &planeNormal, const Vector &onPlane, const Vector &p)

static SO< Iterator< Vector > > transform (SO< Iterator< Vector > > points, const Matrix &matrix)

static SO< PackedVertexIterator > translate (SO< Iterator< Vector > > vertices, const Vector &offset)

static Bounds boundingBox (SO< Iterator< Vector > > vertices)

static bool pointInPolygon (SO< Iterator< Vector > > polygon, const Vector &p)

static bool polygonInPolygon (SO< Iterator< Vector > > polygon1, SO< Iterator< Vector > > polygon2)

static Vector projectOntoLine (const Vector &p, const Vector &a, const Vector &b, double edgeLengthHint=-1.0)

static Vector nearestPointOnSegment (const Vector &p, const Vector &a, const Vector &b, double edgeLengthHint=-1.0)

static double pointLineDistance (const Vector &p, const Vector &a, const Vector &b, double edgeLengthHint=-1.0)

static bool collinear (const Vector &a1, const Vector &b1, const Vector &a2, const Vector &b2, double errorTolerance=1.e-10)

static bool parallel (const Vector &a1, const Vector &b1, const Vector &a2, const Vector &b2, double cosMaxAngle=1.-1.e-10)

static Vector normal (SO< Iterator< Vector > > polygon)

static double signedArea (SO< Iterator< Vector > > polygon)

static bool counterclockwise (SO< Iterator< Vector > > polygon)

static SO< Iterator< Vector > > orientLoop (SO< Iterator< Vector > > loop, bool ccw=true)

static Vector bisectorRay (const Vector &a, const Vector &b, const Vector &c)

static bool intersectLines (const Vector &a1, const Vector &b1, const Vector &a2, const Vector &b2, Vector &intersectionPoint, bool ignoreSection=true, double cosMaxAngle=1.-1.e-10)

static LineSection CheckLineSection (const Vector &a, const Vector &b, const Vector &p, double tolerance=-1.0)

static double calculateAngleCCW (const Vector &a, const Vector &b, const Vector &c)

static double calculateAngleCCW (const Vector &a, const Vector &b)

Given two vectors a and b, this method computes the angle alpha in such a way that a ccw rotation around the origin maps the direction of a to the direction of b.

static Vector rotateCCW (const Vector &a, double angle)

Rotates a 2D vector around the origin in ccw direction.

static double forceAngleToRange (double angle)

Given an angle in degrees within an arbitray range, this method projects this angle to [0,360.0[.

static bool anglesAreCCWOrdered (double alpha, double beta, double gamma)

Given three angles in degrees, this method checks whether the angle order describes a counterclockwise order.

static Vector findPerpendicularVector (const Vector &v)

static SO< Iterator< Vector > > boundingRectangle (SO< Iterator< Vector > > polygon)

static SO< Iterator< Vector > > boundingRectangle (const Vector &a, const Vector &b, const Vector &c)

static SO< Iterator< SO
< Iterator< SO< Iterator
< Vector > > > > > > clipPolygons (SO< Iterator< SO< Iterator< Vector > > > > sp, SO< Iterator< SO< Iterator< Vector > > > > cp)

static SO< Iterator< Vector > > clipConvexPolygons (SO< Iterator< Vector > > poly1, SO< Iterator< Vector > > poly2)

Clips the given convex polygon poly1 against the given convex polygon poly2.

static Vector nearestPoint (const Vector &point, const Bounds &bounds)

Computes the point inside 'bounds' with the smallest distance to 'point'.

static Vector furthestPoint (const Vector &point, const Bounds &bounds)

Computes the point inside 'bounds' with the largest distance to 'point'.

static SO< Iterator< Vector > > expandLoop (SO< Iterator< Vector > > loop, double delta)

Moves each edge 'e' of a vertex loop by a fixed length 'delta' to the direction of the outside normal of 'e'.

static Vector centerOfLoop (SO< Iterator< Vector > > loop)

Computes the weighted center point of a given loop in the XZ plane.

static Matrix quadrilateralToQuadTransform (const Vector &t0, const Vector &t1, const Vector &t2, const Vector &t3, const Vector &min=Vector(-1.0,-1.0), const Vector &max=Vector(1.0, 1.0))

Calculates the transformation matrix for mapping the quadrilateral (t0, t1, t2, t3) to the quad given by (min, max), i.e., the vertices are mapped in this manner: t0 => (min[0], min[1]) t1 => (max[0], min[1]) t2 => (max[0], max[1]) t3 => (min[0], max[1]) NOTE: only the x and y coordinates are used (z coordinate is ignored)! see: http://www.comp.nus.edu.sg/~tants/tsm/TSM_recipe.html.

static Matrix rotateToXZPlane (const Vector &planeNormal)

Computes a matrix that rotates a given plane in such a way that the result is parallel to the x-z plane.

static Vector getEdgeNormal (const Vector &a, const Vector &b, const Vector &c, bool xyPlane, bool normalized=true)

computes the normal vector of the (a,b) pointing outside the triangle (a,b,c).

static void growTriangle (Vector &a, Vector &b, Vector &c, int pixels, int atlasSize, bool xyPlane)

increases the size of a texture space triangle by a given number of pixels.

static bool intersectionTest (const Vector &a1, const Vector &b1, const Vector &c1, const Vector &a2, const Vector &b2, const Vector &c2, bool xyPlane)

Returns true if two triangles in the xy plane (or optionally xz plane) are intersecting.

static bool computeVertexTf (const Vector &a1, const Vector &a2, const Vector &a3, const Vector &b1, const Vector &b2, const Vector &b3, Matrix &result)

Given two triangles, this method computes the homogenous transformation that maps a to be.

static Vector polar2Cartesian (const Vector &p, const Vector &up=Vector(0, 1, 0))

conversion between cartesian and polar coordinates, according to a given up-vector.

static Vector cartesian2Polar (const Vector &p, const Vector &up=Vector(0, 1, 0))

static SO< Iterator< Vector > > generatePoissonDiskDistribution (SO< Facet > polygon, double radius)

generates a random seed of points within the given polygon.

static SO< Iterator< Vector > > generatePoissonDiskDistribution (const Bounds &bounds, double radius, bool tiling=false)

static SO< Iterator< Vector > > singleStepPoissonDiskDistribution (SO< Facet > polygon, double radius, bool clear=false)

static SO< Iterator< Vector > > singleStepPoissonDiskDistribution (const Bounds &bounds, double radius, bool tiling, bool clear=false)

static bool IntersectCircles (const VRS::Vector &m0, double radius0, const VRS::Vector &m1, double radius1, VRS::Vector &firstIntersection, VRS::Vector &secondIntersection)

Given two circles by means of midpoint and radius, this method computes the two intersection points or returns 'false' if no intersection exists.

static bool LineSphereIntersection (const Vector &m, double r, const Vector &a, const Vector &b, Vector &firstIntersection, Vector &secondIntersection)

Intersection of a circle or sphere with a line spanned by two vertices (a,b).

Detailed Description

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>
class VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >

Provides general functions for VRS Vectors.

Member Enumeration Documentation

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

enum VRS::AlgorithmImpl::LineSection

Given a line section (a,b) and a point p, the following method checks the location of p (or the projection of p onto the line <(a,b)>) relative to the section (a,b).

The equality is determined within a given tolerance. Setting this tolerance to a negative value activates the default value of segmentLength / 1000.0.

Enumerator:

SCR_BEFORE_A
SCR_AT_A
SCR_BETWEEN_AB
SCR_AT_B
SCR_AFTER_B

Member Function Documentation

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<PolygonSet> VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::convexHull3D ( SO< Iterator< Vector > > points ) [static]

< The function for computing the convex hull are based on the qhull library. See the COPYING.txt in the qhull folder for further information about qhull.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::convexHull2D ( SO< Iterator< Vector > > points ) [static]

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::convexHull2D	(	SO< Iterator< Vector > >	points,
		const Vector &	planeNormal,
		const Vector &	onPlane = `Vector::origin`
	)			`[static]`

The return value of this function is the sequence of vertices of the convex hull of the points specified by "points". They are ordered counterclockwise.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::projectOntoPlane	(	const Vector &	point,
		const Vector &	planeNormal,
		const Vector &	onPlane = `Vector(0, 0, 0)`
	)			`[static]`

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::projectOntoPlane	(	SO< Iterator< Vector > >	points,
		const Vector &	planeNormal,
		const Vector &	onPlane = `Vector(0, 0, 0)`
	)			`[static]`

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::intersectPlanes	(	const Vector &	planeNormal1,
		const Vector &	onPlane1,
		const Vector &	planeNormal2,
		const Vector &	onPlane2,
		const Vector &	planeNormal3,
		const Vector &	onPlane3,
		Vector &	intersectionPoint
	)			`[static]`

Returns the intersection point of three planes, which are specified by a plane normal and a point on the plane. If there is a unique intersection point, the method returns true and stores the result in 'intersectionPoint'. Otherwise false is returned and intersectionPoint is left unchanged. Caution: All normals must be normalized, otherwise the method aborts with an assertion!

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::linePlaneIntersection	(	const Vector &	planeNormal,
		const Vector &	onPlane,
		const Vector &	a,
		const Vector &	b,
		Vector &	intersectionPoint,
		bool	checkSection = `true`
	)			`[static]`

Returns the intersection Point of a line section [a,b] with a plane. The parameters 'a' and 'b' specify the line section. By default an intersection point p on a line L passing through 'a' and 'b' is ignored if p lies outside the line section [a,b] on L. Set 'checkSection' to 'false' if it does'nt matter whether p lies inside the section [a,b] or not.

If a==b the method aborts with return value false. See above (method intersectionPlanes) for further information about parameters and return value. Caution: n must be normalized, otherwise the method aborts with an assertion!

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::rayTriangleIntersection	(	const Ray &	ray,
		const Vector &	t1,
		const Vector &	t2,
		const Vector &	t3,
		Vector &	intersectionPoint
	)			`[static]`

Calculates the intersection point of a ray with a triangle. Returns true, if such an intersection point exists.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static double VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::signedDistance	(	const Vector &	planeNormal,
		const Vector &	onPlane,
		const Vector &	p
	)			`[static]`

Returns the signed distance of a point 'p' from a given plane. planeNormal must be normalized.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::transform	(	SO< Iterator< Vector > >	points,
		const Matrix &	matrix
	)			`[static]`

Creates a copy of a given input sequence, where each vector is multiplied with 'matrix'.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<PackedVertexIterator> VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::translate	(	SO< Iterator< Vector > >	vertices,
		const Vector &	offset
	)			`[static]`

Returns a packed vertex iterator with all input vertices translated by the given offset. NOTE: if the given iterator is already of type PackedVertexIterator the vertex data is not copied!

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Bounds VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::boundingBox ( SO< Iterator< Vector > > vertices ) [static]

Returns the bounding box for the given set of vertices.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::pointInPolygon	(	SO< Iterator< Vector > >	polygon,
		const Vector &	p
	)			`[static]`

Checks if p lies inside a polygon, given by a single outer loop. Note: This method ignores z-coordinate.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::polygonInPolygon	(	SO< Iterator< Vector > >	polygon1,
		SO< Iterator< Vector > >	polygon2
	)			`[static]`

Checks if polygon2 is completely enclosed by polygon1, given by a single outer loop. That means that all points of polygon2 lie inside of polygon1. Note: This method currently works only for polygons in the xz-plane.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::projectOntoLine	(	const Vector &	p,
		const Vector &	a,
		const Vector &	b,
		double	edgeLengthHint = `-1.0`
	)			`[static]`

Projects a point p onto a line defined by a and b. a and b must not be (approximately) equal. Otherwise a warning is caused and the results can be imprecise or undefined. If 'edgeLength' is set, it must be (b-a).abs() and is used to avoid the sqrt op.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::nearestPointOnSegment	(	const Vector &	p,
		const Vector &	a,
		const Vector &	b,
		double	edgeLengthHint = `-1.0`
	)			`[static]`

Calculates the nearest point on the segment a and b for the given point p. a and b must not be (approximately) equal. Otherwise a warning is caused and the results can be imprecise or undefined.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static double VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::pointLineDistance	(	const Vector &	p,
		const Vector &	a,
		const Vector &	b,
		double	edgeLengthHint = `-1.0`
	)			`[static]`

Computes the distance of p from the line spanned by (a,b). a and b must not be (approximately) equal. Otherwise a warning is caused and the results can be imprecise or undefined.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::collinear	(	const Vector &	a1,
		const Vector &	b1,
		const Vector &	a2,
		const Vector &	b2,
		double	errorTolerance = `1.e-10`
	)			`[static]`

Checks the edges (a1,b1) and (a2,b2) for collinearity. The edges are accepted to be collinear, if the distance of a2 and b2 from the line spanned by (a1,b1) is less or equal errorTolerance. The edges should not be degenerated. Otherwise a warning is produced and the results can be imprecise or undefined.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::parallel	(	const Vector &	a1,
		const Vector &	b1,
		const Vector &	a2,
		const Vector &	b2,
		double	cosMaxAngle = `1.-1.e-10`
	)			`[static]`

Checks the edges (a1,b1) and (a2,b2) for being parallel. The edges are accepted to be parallel if the angle formed by b1-a1 and b2-a2 are less or equal an angle threshold. For better performance the cosine of the angle is specified instead.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::normal ( SO< Iterator< Vector > > polygon ) [static]

Calculates the polygon normal. The direction of the normal is chosen so that it points into the half space from which the outer loop appears counterclockwise.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static double VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::signedArea ( SO< Iterator< Vector > > polygon ) [static]

Given a polygon in the xz-plane (note: y-values are ignored) this method obtains the area of a simple (but possibly non-convex) polygon given by a vector iterator. If the sign is positive the vertices are ordered counterclockwise. If the result is 0, the polygon is degenerate.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::counterclockwise ( SO< Iterator< Vector > > polygon ) [static]

Returns true if the given simple polygon in the xz-plane is ordered counterclockwise.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::orientLoop	(	SO< Iterator< Vector > >	loop,
		bool	ccw = `true`
	)			`[static]`

Given a loop in the xz-plane orientLoop ensures a certain orientation (per default counterclockwise, clockwise for 'ccw' = false). If the orientation is already correct, the loop original loop pointer is returned. Otherwise the iterator is copied and the order is inverted. Note: The result is NULL for degenerated loops.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::bisectorRay	(	const Vector &	a,
		const Vector &	b,
		const Vector &	c
	)			`[static]`

Given a triangle in the xz-plane bisectorRay() computes the direction of the bisector ray of the angle formed by (a,b,c) at the vertex b. If (a,b,c) are ordered counterclockwise, the returned vector points into the triangle, otherwise it points to outside. So if (a,b,c) are subsequent vertices of a counterclockwise ordered concave polygon, the result of bisectorRay() always points inside the polygon.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::intersectLines	(	const Vector &	a1,
		const Vector &	b1,
		const Vector &	a2,
		const Vector &	b2,
		Vector &	intersectionPoint,
		bool	ignoreSection = `true`,
		double	cosMaxAngle = `1.-1.e-10`
	)			`[static]`

Given two lines in the xz-plane (y-component is ignored) the intersection point is calculated. If no intersection point exists, 'false' is returned. Otherwise it returns 'true' and uses 'intersectionPoint' to store the result. If 'ignoreSection' is false, only the line sections are checked for intersection, otherwise the lines spanned by the sections are used for the intersection test. 'cosMaxAngle' specifies the tolerance for the check of the lines for being parallel (using the parallel() method).

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static LineSection VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::CheckLineSection	(	const Vector &	a,
		const Vector &	b,
		const Vector &	p,
		double	tolerance = `-1.0`
	)			`[static]`

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static double VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::calculateAngleCCW	(	const Vector &	a,
		const Vector &	b,
		const Vector &	c
	)			`[static]`

Computes the angle in degrees formed by the edges (a,b) and (b,c) at b. The result is in [0,360[. The vertices a,b,c are assumed to lie in the xz-plane!

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static double VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::calculateAngleCCW	(	const Vector &	a,
		const Vector &	b
	)			`[static]`

Given two vectors a and b, this method computes the angle alpha in such a way that a ccw rotation around the origin maps the direction of a to the direction of b.

The angle is returned in degrees within the range [0, 360[.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::rotateCCW	(	const Vector &	a,
		double	angle
	)			`[static]`

Rotates a 2D vector around the origin in ccw direction.

This method matches the 2-parameter calculateAngleCCW() method, i.e., rotateCCW(a, calculateAngleCCW(a,b)) will return b.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static double VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::forceAngleToRange ( double angle ) [static]

Given an angle in degrees within an arbitray range, this method projects this angle to [0,360.0[.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::anglesAreCCWOrdered	(	double	alpha,
		double	beta,
		double	gamma
	)			`[static]`

Given three angles in degrees, this method checks whether the angle order describes a counterclockwise order.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::findPerpendicularVector ( const Vector & v ) [static]

Calculates an arbitrary vector w that is perpendicular to v. If v is approximately (0,0,0), the result is undefined.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::boundingRectangle ( SO< Iterator< Vector > > polygon ) [static]

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::boundingRectangle	(	const Vector &	a,
		const Vector &	b,
		const Vector &	c
	)			`[static]`

Given a polygon in the xz-plane boundingRectangle() calculates the minimum area rectangle that contains (the convex hull of) the polygon. It returns an iterator with the 4 rectangle vertices ordered counterclockwise. The second variant is a simpler and faster implementation specialized for triangles. Note: The y-coords of the results will be 0.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<SO<Iterator<SO<Iterator<Vector > > > > > > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::clipPolygons	(	SO< Iterator< SO< Iterator< Vector > > > >	sp,
		SO< Iterator< SO< Iterator< Vector > > > >	cp
	)			`[static]`

Returns the result of clipping the subject polygon (sp) agains the clip polygon (cp) in the xz-plane (y-values are ignored). 'sp' and 'cp' are sets of loops. The first loop describes the polygon outline vertices and has to be ordered clockwise. All other loops describe polygon "holes" and have to be ordered counterclockwise. It returns an iterator of polygons with the same structure. Uses the Weiler-Atherton 2D-clipping algorithm.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::clipConvexPolygons	(	SO< Iterator< Vector > >	poly1,
		SO< Iterator< Vector > >	poly2
	)			`[static]`

Clips the given convex polygon poly1 against the given convex polygon poly2.

Both polygons have to be ordered in clockwise order. Clipping is done in the xz-plane (y-coords are ignored). The implementation is based on the Sutherland-Hodgman algorithm.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::nearestPoint	(	const Vector &	point,
		const Bounds &	bounds
	)			`[static]`

Computes the point inside 'bounds' with the smallest distance to 'point'.

'bounds' must be defined.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::furthestPoint	(	const Vector &	point,
		const Bounds &	bounds
	)			`[static]`

Computes the point inside 'bounds' with the largest distance to 'point'.

'bounds' must be defined.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::expandLoop	(	SO< Iterator< Vector > >	loop,
		double	delta
	)			`[static]`

Moves each edge 'e' of a vertex loop by a fixed length 'delta' to the direction of the outside normal of 'e'.

'loop' is expected to lie within the xz-plane. Note: It is a simple implementation and does not explicitly avoid self-intersections.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::centerOfLoop ( SO< Iterator< Vector > > loop ) [static]

Computes the weighted center point of a given loop in the XZ plane.

Note: Checks for proper vert order and adjusts if necsessary.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Matrix VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::quadrilateralToQuadTransform	(	const Vector &	t0,
		const Vector &	t1,
		const Vector &	t2,
		const Vector &	t3,
		const Vector &	min = `Vector(-1.0,-1.0)`,
		const Vector &	max = `Vector(1.0, 1.0)`
	)			`[static]`

Calculates the transformation matrix for mapping the quadrilateral (t0, t1, t2, t3) to the quad given by (min, max), i.e., the vertices are mapped in this manner: t0 => (min[0], min[1]) t1 => (max[0], min[1]) t2 => (max[0], max[1]) t3 => (min[0], max[1]) NOTE: only the x and y coordinates are used (z coordinate is ignored)! see: http://www.comp.nus.edu.sg/~tants/tsm/TSM_recipe.html.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Matrix VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::rotateToXZPlane ( const Vector & planeNormal ) [static]

Computes a matrix that rotates a given plane in such a way that the result is parallel to the x-z plane.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::getEdgeNormal	(	const Vector &	a,
		const Vector &	b,
		const Vector &	c,
		bool	xyPlane,
		bool	normalized = `true`
	)			`[static]`

computes the normal vector of the (a,b) pointing outside the triangle (a,b,c).

Note: The method works either in the xz plane or the xy plane (depending on the flag) The remaining coord is ignored. Setting 'normalized' to false skips the final normalization (faster)

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static void VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::growTriangle	(	Vector &	a,
		Vector &	b,
		Vector &	c,
		int	pixels,
		int	atlasSize,
		bool	xyPlane
	)			`[static]`

increases the size of a texture space triangle by a given number of pixels.

It works either in the xz plane or xy, depending on the flag. The result is written back into (a,b,c)

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::intersectionTest	(	const Vector &	a1,
		const Vector &	b1,
		const Vector &	c1,
		const Vector &	a2,
		const Vector &	b2,
		const Vector &	c2,
		bool	xyPlane
	)			`[static]`

Returns true if two triangles in the xy plane (or optionally xz plane) are intersecting.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::computeVertexTf	(	const Vector &	a1,
		const Vector &	a2,
		const Vector &	a3,
		const Vector &	b1,
		const Vector &	b2,
		const Vector &	b3,
		Matrix &	result
	)			`[static]`

Given two triangles, this method computes the homogenous transformation that maps a to be.

The computation may fail if triangle 1 is degenerate. In this case, the return value is 'false' and the result matrix is left unchanged.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::polar2Cartesian	(	const Vector &	p,
		const Vector &	up = `Vector(0, 1, 0)`
	)			`[static]`

conversion between cartesian and polar coordinates, according to a given up-vector.

The polar coordinate vector specifies (latitude, altitude, radius), whereby latitude and altitude are given in degrees and the radius corresponds to the length of the vector in cartesian coordinates. Note that the latitude and longitutde are undetermined for cartesian2Polar(p, up) they are approximately equal.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static Vector VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::cartesian2Polar	(	const Vector &	p,
		const Vector &	up = `Vector(0, 1, 0)`
	)			`[static]`

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::generatePoissonDiskDistribution	(	SO< Facet >	polygon,
		double	radius
	)			`[static]`

generates a random seed of points within the given polygon.

the set of points fulfills the poisson-disc property, that is, two points' distance will never go below a certain threshold that is given by 'radius'. the polygon's orientation is not constrained, it may be concave and even have holes. This function implements the Boundary Sampling algorithm by Dunbar & Humphreys ("Using scalloped Sectors to Generate Poisson-Disk Sampling Patterns", section 3) the Bounds-version of this function will first analyze the bounds and find the axis with the smalles extent. if values are equal, x is preferred before y and y before z. the rectangle orthogonal to this particular axis lying in the box's center will be used as the bounding rectangle. if 'tiling' is true, the algorithm will generate a pointset that will regard the poisson-disc property across opposite boundary edges. the singleStep-functions generate only one point within the given bounds. subsequent calls to these functions will add another point to the set, generated with previous calls. the algotithm will continue using the same values for 'bounds', 'radius' and 'tiling', until the 'clear'-flag is set to true.

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::generatePoissonDiskDistribution	(	const Bounds &	bounds,
		double	radius,
		bool	tiling = `false`
	)			`[static]`

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::singleStepPoissonDiskDistribution	(	SO< Facet >	polygon,
		double	radius,
		bool	clear = `false`
	)			`[static]`

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static SO<Iterator<Vector> > VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::singleStepPoissonDiskDistribution	(	const Bounds &	bounds,
		double	radius,
		bool	tiling,
		bool	clear = `false`
	)			`[static]`

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::IntersectCircles	(	const VRS::Vector &	m0,
		double	radius0,
		const VRS::Vector &	m1,
		double	radius1,
		VRS::Vector &	firstIntersection,
		VRS::Vector &	secondIntersection
	)			`[static]`

Given two circles by means of midpoint and radius, this method computes the two intersection points or returns 'false' if no intersection exists.

Note that the intersection points are approximately equal if and only if the midpoint distance is close to (radius0 + radius1).

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>

static bool VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >::LineSphereIntersection	(	const Vector &	m,
		double	r,
		const Vector &	a,
		const Vector &	b,
		Vector &	firstIntersection,
		Vector &	secondIntersection
	)			`[static]`

Intersection of a circle or sphere with a line spanned by two vertices (a,b).

If the line touches the sphere, both intersections are equal. The intersection points are ordered according to the line orientation implied by (a,b).

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

algorithm.h


Public Types
enum	LineSection { SCR_BEFORE_A, SCR_AT_A, SCR_BETWEEN_AB, SCR_AT_B, SCR_AFTER_B }
	Given a line section (a,b) and a point p, the following method checks the location of p (or the projection of p onto the line <(a,b)>) relative to the section (a,b). More...
Static Public Member Functions
static SO< PolygonSet >	convexHull3D (SO< Iterator< Vector > > points)
static SO< Iterator< Vector > >	convexHull2D (SO< Iterator< Vector > > points)
static SO< Iterator< Vector > >	convexHull2D (SO< Iterator< Vector > > points, const Vector &planeNormal, const Vector &onPlane=Vector::origin)
static Vector	projectOntoPlane (const Vector &point, const Vector &planeNormal, const Vector &onPlane=Vector(0, 0, 0))
static SO< Iterator< Vector > >	projectOntoPlane (SO< Iterator< Vector > > points, const Vector &planeNormal, const Vector &onPlane=Vector(0, 0, 0))
static bool	intersectPlanes (const Vector &planeNormal1, const Vector &onPlane1, const Vector &planeNormal2, const Vector &onPlane2, const Vector &planeNormal3, const Vector &onPlane3, Vector &intersectionPoint)
static bool	linePlaneIntersection (const Vector &planeNormal, const Vector &onPlane, const Vector &a, const Vector &b, Vector &intersectionPoint, bool checkSection=true)
static bool	rayTriangleIntersection (const Ray &ray, const Vector &t1, const Vector &t2, const Vector &t3, Vector &intersectionPoint)
static double	signedDistance (const Vector &planeNormal, const Vector &onPlane, const Vector &p)
static SO< Iterator< Vector > >	transform (SO< Iterator< Vector > > points, const Matrix &matrix)
static SO< PackedVertexIterator >	translate (SO< Iterator< Vector > > vertices, const Vector &offset)
static Bounds	boundingBox (SO< Iterator< Vector > > vertices)
static bool	pointInPolygon (SO< Iterator< Vector > > polygon, const Vector &p)
static bool	polygonInPolygon (SO< Iterator< Vector > > polygon1, SO< Iterator< Vector > > polygon2)
static Vector	projectOntoLine (const Vector &p, const Vector &a, const Vector &b, double edgeLengthHint=-1.0)
static Vector	nearestPointOnSegment (const Vector &p, const Vector &a, const Vector &b, double edgeLengthHint=-1.0)
static double	pointLineDistance (const Vector &p, const Vector &a, const Vector &b, double edgeLengthHint=-1.0)
static bool	collinear (const Vector &a1, const Vector &b1, const Vector &a2, const Vector &b2, double errorTolerance=1.e-10)
static bool	parallel (const Vector &a1, const Vector &b1, const Vector &a2, const Vector &b2, double cosMaxAngle=1.-1.e-10)
static Vector	normal (SO< Iterator< Vector > > polygon)
static double	signedArea (SO< Iterator< Vector > > polygon)
static bool	counterclockwise (SO< Iterator< Vector > > polygon)
static SO< Iterator< Vector > >	orientLoop (SO< Iterator< Vector > > loop, bool ccw=true)
static Vector	bisectorRay (const Vector &a, const Vector &b, const Vector &c)
static bool	intersectLines (const Vector &a1, const Vector &b1, const Vector &a2, const Vector &b2, Vector &intersectionPoint, bool ignoreSection=true, double cosMaxAngle=1.-1.e-10)
static LineSection	CheckLineSection (const Vector &a, const Vector &b, const Vector &p, double tolerance=-1.0)
static double	calculateAngleCCW (const Vector &a, const Vector &b, const Vector &c)
static double	calculateAngleCCW (const Vector &a, const Vector &b)
	Given two vectors a and b, this method computes the angle alpha in such a way that a ccw rotation around the origin maps the direction of a to the direction of b.
static Vector	rotateCCW (const Vector &a, double angle)
	Rotates a 2D vector around the origin in ccw direction.
static double	forceAngleToRange (double angle)
	Given an angle in degrees within an arbitray range, this method projects this angle to [0,360.0[.
static bool	anglesAreCCWOrdered (double alpha, double beta, double gamma)
	Given three angles in degrees, this method checks whether the angle order describes a counterclockwise order.
static Vector	findPerpendicularVector (const Vector &v)
static SO< Iterator< Vector > >	boundingRectangle (SO< Iterator< Vector > > polygon)
static SO< Iterator< Vector > >	boundingRectangle (const Vector &a, const Vector &b, const Vector &c)
static SO< Iterator< SO < Iterator< SO< Iterator < Vector > > > > > >	clipPolygons (SO< Iterator< SO< Iterator< Vector > > > > sp, SO< Iterator< SO< Iterator< Vector > > > > cp)
static SO< Iterator< Vector > >	clipConvexPolygons (SO< Iterator< Vector > > poly1, SO< Iterator< Vector > > poly2)
	Clips the given convex polygon poly1 against the given convex polygon poly2.
static Vector	nearestPoint (const Vector &point, const Bounds &bounds)
	Computes the point inside 'bounds' with the smallest distance to 'point'.
static Vector	furthestPoint (const Vector &point, const Bounds &bounds)
	Computes the point inside 'bounds' with the largest distance to 'point'.
static SO< Iterator< Vector > >	expandLoop (SO< Iterator< Vector > > loop, double delta)
	Moves each edge 'e' of a vertex loop by a fixed length 'delta' to the direction of the outside normal of 'e'.
static Vector	centerOfLoop (SO< Iterator< Vector > > loop)
	Computes the weighted center point of a given loop in the XZ plane.
static Matrix	quadrilateralToQuadTransform (const Vector &t0, const Vector &t1, const Vector &t2, const Vector &t3, const Vector &min=Vector(-1.0,-1.0), const Vector &max=Vector(1.0, 1.0))
	Calculates the transformation matrix for mapping the quadrilateral (t0, t1, t2, t3) to the quad given by (min, max), i.e., the vertices are mapped in this manner: t0 => (min[0], min[1]) t1 => (max[0], min[1]) t2 => (max[0], max[1]) t3 => (min[0], max[1]) NOTE: only the x and y coordinates are used (z coordinate is ignored)! see: http://www.comp.nus.edu.sg/~tants/tsm/TSM_recipe.html.
static Matrix	rotateToXZPlane (const Vector &planeNormal)
	Computes a matrix that rotates a given plane in such a way that the result is parallel to the x-z plane.
static Vector	getEdgeNormal (const Vector &a, const Vector &b, const Vector &c, bool xyPlane, bool normalized=true)
	computes the normal vector of the (a,b) pointing outside the triangle (a,b,c).
static void	growTriangle (Vector &a, Vector &b, Vector &c, int pixels, int atlasSize, bool xyPlane)
	increases the size of a texture space triangle by a given number of pixels.
static bool	intersectionTest (const Vector &a1, const Vector &b1, const Vector &c1, const Vector &a2, const Vector &b2, const Vector &c2, bool xyPlane)
	Returns true if two triangles in the xy plane (or optionally xz plane) are intersecting.
static bool	computeVertexTf (const Vector &a1, const Vector &a2, const Vector &a3, const Vector &b1, const Vector &b2, const Vector &b3, Matrix &result)
	Given two triangles, this method computes the homogenous transformation that maps a to be.
static Vector	polar2Cartesian (const Vector &p, const Vector &up=Vector(0, 1, 0))
	conversion between cartesian and polar coordinates, according to a given up-vector.
static Vector	cartesian2Polar (const Vector &p, const Vector &up=Vector(0, 1, 0))
static SO< Iterator< Vector > >	generatePoissonDiskDistribution (SO< Facet > polygon, double radius)
	generates a random seed of points within the given polygon.
static SO< Iterator< Vector > >	generatePoissonDiskDistribution (const Bounds &bounds, double radius, bool tiling=false)
static SO< Iterator< Vector > >	singleStepPoissonDiskDistribution (SO< Facet > polygon, double radius, bool clear=false)
static SO< Iterator< Vector > >	singleStepPoissonDiskDistribution (const Bounds &bounds, double radius, bool tiling, bool clear=false)
static bool	IntersectCircles (const VRS::Vector &m0, double radius0, const VRS::Vector &m1, double radius1, VRS::Vector &firstIntersection, VRS::Vector &secondIntersection)
	Given two circles by means of midpoint and radius, this method computes the two intersection points or returns 'false' if no intersection exists.
static bool	LineSphereIntersection (const Vector &m, double r, const Vector &a, const Vector &b, Vector &firstIntersection, Vector &secondIntersection)
	Intersection of a circle or sphere with a line spanned by two vertices (a,b).

VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z > Class Template Reference

Public Types

Static Public Member Functions

Detailed Description

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z> class VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >

Member Enumeration Documentation

Member Function Documentation

template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>
class VRS::AlgorithmImpl< DIM_X, DIM_Y, DIM_Z >