sofa::component::collision::ContinuousTriangleIntersection Class Reference

#include <ContinuousTriangleIntersection.h>

Collaboration diagram for sofa::component::collision::ContinuousTriangleIntersection:


Public Member Functions
	ContinuousTriangleIntersection (Triangle &t1, Triangle &t2)
	~ContinuousTriangleIntersection (void)
core::componentmodel::collision::DetectionOutput *	computeDetectionOutput (void)
bool	isCollision (void)
Private Member Functions
int	intersectPointTriangle (SReal &t, SReal &u, SReal &v, const Vector3 &p0, const Vector3 &v0, const Vector3 &p1, const Vector3 &v1, const Vector3 &p2, const Vector3 &v2, const Vector3 &p3, const Vector3 &v3, double dt)
	Method for calculating point-vertex collision Given: Point p0 moving at velocity v0 intersecting with Triangle (p1, p2, p3) moving at velocity (v1, v2, v3) Returns: 0 <= t <= 1 is the time of collision, actual time is tdt 0 <= u, v <= 1, u+v <= 1 are the triangle barycentric coordinates Collision point: p0 + tdtv0 = u(p1 + tdtv1) + v(p2 + tdtv2) + (1-u-v)(p3 + tdtv3).
int	intersectEdgeEdge (SReal &t, SReal &u, SReal &v, const Vector3 &p1, const Vector3 &p2, const Vector3 &v1, const Vector3 &v2, const Vector3 &p3, const Vector3 &p4, const Vector3 &v3, const Vector3 &v4, double dt)
	Method for calculating edge-edge collision Given: edge (p1, p2) moving at velocity (v1, v2) intersecting with edge (p3, p4) moving at velocity (v3, v4) dt is time step (in seconds) Returns: 0 <= t <= 1 is the time of collision, actual time is tdt 0 <= u, v <= 1 are the edge barycentric coordinates Collision point: (1-u)(p1 + tdtv1) + u(p2 + tdtv2) = or (1-v)(p3 + tdtv3) + v(p4 + tdt*v4).
int	solveCubic (Vector3 &s, SReal c[4])
	Method used internally Solves cubic equation: c[0] + c[1]x + c[2]x^2 + c[3]*x^3 = 0 upto three possible solution, make sure c[3] is non-zero Ref Graphics Gems I, Schwarze, Jochen, Cubic and Quartic Roots, p.
int	solveQuadratic (SReal &t1, SReal &t2, const SReal &a, const SReal &b, const SReal &c)
	Method used internally Solves quadratic equation: aX + bX + c = 0 x1 = q/a; x2 = c/q; where q = -1/2[b + sgn(b)*sqrt(b^2 -4ac)] Ref.
bool	checkValidRoots (SReal &validRoot, const int &numRoots, const Vector3 &roots, const SReal &rootMin, const SReal &rootMax)
	Method used internally method computes valid root within range of [rootMin, rootMax] returns the smallest root if there are more than one valid root.
bool	checkRange (const SReal &val, const SReal &min, const SReal &max)
	returns true of value lies within the range
SReal	getMinVal (const SReal &val0, const SReal &val1)
	returns the smallest of the two values
SReal	getMinVal (const SReal &val0, const SReal &val1, const SReal &val2)
	returns the smallest of the three values
void	setTolerance (const SReal &tol)
	sets tolerance for boundary check [-tol, 1+tol]
Private Attributes
Triangle &	tr1
Triangle &	tr2
SReal	m_tolerance
SReal	m_tolmin
SReal	m_tolmax

Detailed Description

Definition at line 49 of file ContinuousTriangleIntersection.h.

Constructor & Destructor Documentation

sofa::component::collision::ContinuousTriangleIntersection::ContinuousTriangleIntersection	(	Triangle &	t1,
		Triangle &	t2
	)

Definition at line 182 of file ContinuousTriangleIntersection.cpp.

References m_tolerance, m_tolmax, and m_tolmin.

sofa::component::collision::ContinuousTriangleIntersection::~ContinuousTriangleIntersection ( void )

Definition at line 189 of file ContinuousTriangleIntersection.cpp.

Member Function Documentation

bool sofa::component::collision::ContinuousTriangleIntersection::checkRange	(	const SReal &	val,
		const SReal &	min,
		const SReal &	max
	)			`[inline, private]`

returns true of value lies within the range

Definition at line 84 of file ContinuousTriangleIntersection.h.

Referenced by checkValidRoots().

bool sofa::component::collision::ContinuousTriangleIntersection::checkValidRoots	(	SReal &	validRoot,
		const int &	numRoots,
		const Vector3 &	roots,
		const SReal &	rootMin,
		const SReal &	rootMax
	)			`[private]`

Method used internally method computes valid root within range of [rootMin, rootMax] returns the smallest root if there are more than one valid root.

when numRoots equals 1

when numRoots equals 2

when numRoots equals 3

Definition at line 542 of file ContinuousTriangleIntersection.cpp.

References checkRange(), and getMinVal().

Referenced by intersectEdgeEdge(), and intersectPointTriangle().

core::componentmodel::collision::DetectionOutput * sofa::component::collision::ContinuousTriangleIntersection::computeDetectionOutput ( void )

Definition at line 139 of file ContinuousTriangleIntersection.cpp.

References intersectEdgeEdge(), intersectPointTriangle(), sofa::component::collision::Triangle::p1(), sofa::component::collision::Triangle::p2(), sofa::component::collision::Triangle::p3(), tr1, tr2, sofa::component::collision::Triangle::v1(), sofa::component::collision::Triangle::v2(), and sofa::component::collision::Triangle::v3().

Referenced by sofa::component::collision::ContinuousIntersection::computeIntersection().

SReal sofa::component::collision::ContinuousTriangleIntersection::getMinVal	(	const SReal &	val0,
		const SReal &	val1,
		const SReal &	val2
	)			`[inline, private]`

returns the smallest of the three values

Definition at line 100 of file ContinuousTriangleIntersection.h.

SReal sofa::component::collision::ContinuousTriangleIntersection::getMinVal	(	const SReal &	val0,
		const SReal &	val1
	)			`[inline, private]`

returns the smallest of the two values

Definition at line 93 of file ContinuousTriangleIntersection.h.

Referenced by checkValidRoots().

int sofa::component::collision::ContinuousTriangleIntersection::intersectEdgeEdge	(	SReal &	t,
		SReal &	u,
		SReal &	v,
		const Vector3 &	p1,
		const Vector3 &	p2,
		const Vector3 &	v1,
		const Vector3 &	v2,
		const Vector3 &	p3,
		const Vector3 &	p4,
		const Vector3 &	v3,
		const Vector3 &	v4,
		double	dt
	)			`[private]`

Method for calculating edge-edge collision Given: edge (p1, p2) moving at velocity (v1, v2) intersecting with edge (p3, p4) moving at velocity (v3, v4) dt is time step (in seconds) Returns: 0 <= t <= 1 is the time of collision, actual time is t*dt 0 <= u, v <= 1 are the edge barycentric coordinates Collision point: (1-u)*(p1 + t*dt*v1) + u*(p2 + t*dt*v2) = or (1-v)*(p3 + t*dt*v3) + v*(p4 + t*dt*v4).

Step1: Cross product x12(t) x x34(t) this represents the normal of triangle at t N(t) (x12 + t*dt*v12) x (x34 + t*dt*v34) Result: Quadratic equation in 't' in matrix form Vector N(t) { N3x + N2x*t + N1x*t*t, N3y + N2y*t + N1y*t*t, N3z + N2z*t + N1z*t*t}

Step 2: Compute the dot product with p01 [N(t) . (p13 + t*dt*v13)] = 0 compute coefficients of the resulting cubic equation C[0] + C[1]*t + C[2]*t*t + C[3]*t*t*t = 0

Step 3: Determine roots of the cubic equation (for non-zero cubic term)

problem reduces to quadratic or linear (zero cubic term)

determing the valid root t [0,1] from upto three possible solutions

Step 4: determine exact points of collision within segments condition for intersection (1-u).x1(t) + u.x2(t) = (1-v).x3(t) + v.x4(t)

refer Bridson 2002 for calculating edge-edge

Definition at line 203 of file ContinuousTriangleIntersection.cpp.

References checkValidRoots(), dot(), EPSILON, m_tolmax, m_tolmin, solveCubic(), and solveQuadratic().

Referenced by computeDetectionOutput(), and isCollision().

int sofa::component::collision::ContinuousTriangleIntersection::intersectPointTriangle	(	SReal &	t,
		SReal &	u,
		SReal &	v,
		const Vector3 &	p0,
		const Vector3 &	v0,
		const Vector3 &	p1,
		const Vector3 &	v1,
		const Vector3 &	p2,
		const Vector3 &	v2,
		const Vector3 &	p3,
		const Vector3 &	v3,
		double	dt
	)			`[private]`

Method for calculating point-vertex collision Given: Point p0 moving at velocity v0 intersecting with Triangle (p1, p2, p3) moving at velocity (v1, v2, v3) Returns: 0 <= t <= 1 is the time of collision, actual time is t*dt 0 <= u, v <= 1, u+v <= 1 are the triangle barycentric coordinates Collision point: p0 + t*dt*v0 = u*(p1 + t*dt*v1) + v*(p2 + t*dt*v2) + (1-u-v)*(p3 + t*dt*v3).

Step 1: Compute the cross product p12 x p13 this represents the normal of triangle at t N(t) (p12 + t*dt*v12) x (p13 + t*dt*v13) Result: Quadratic equation in 't' in matrix form Vector N(t) { N3x + N2x*t + N1x*t*t, N3y + N2y*t + N1y*t*t, N3z + N2z*t + N1z*t*t}

Step 2: Compute the dot product with p01 [N(t) . (p01 + t*v01)] = 0 compute coefficients of the resulting cubic equation C[0] + C[1]*t + C[2]*t*t + C[3]*t*t*t = 0

Step 3: determine roots of the cubic equation (for non-zero cubic term)

problem reduces to quadratic or linear (zero cubic term)

determing the valid root t [0,1] from upto three possible solutions

Step 4: determine exact points of collision within segments condition for intersection p0 + t*dt*v0 = u*(p1 + t*dt*v1) + v*(p2 + t*dt*v2) + (1-u-v)*(p3 + t*dt*v3)

Ref. Bridson 2002

find valid barycentric parameters

Definition at line 310 of file ContinuousTriangleIntersection.cpp.

References checkValidRoots(), dot(), EPSILON, m_tolmax, m_tolmin, solveCubic(), and solveQuadratic().

Referenced by computeDetectionOutput(), and isCollision().

bool sofa::component::collision::ContinuousTriangleIntersection::isCollision ( void )

Definition at line 37 of file ContinuousTriangleIntersection.cpp.

References intersectEdgeEdge(), intersectPointTriangle(), sofa::component::collision::Triangle::p1(), sofa::component::collision::Triangle::p2(), sofa::component::collision::Triangle::p3(), tr1, tr2, sofa::component::collision::Triangle::v1(), sofa::component::collision::Triangle::v2(), and sofa::component::collision::Triangle::v3().

Referenced by sofa::component::collision::ContinuousIntersection::testIntersection().

void sofa::component::collision::ContinuousTriangleIntersection::setTolerance ( const SReal & tol ) [inline, private]

sets tolerance for boundary check [-tol, 1+tol]

Definition at line 116 of file ContinuousTriangleIntersection.h.

References m_tolerance, m_tolmax, and m_tolmin.

int sofa::component::collision::ContinuousTriangleIntersection::solveCubic	(	Vector3 &	s,
		SReal	c[4]
	)			`[private]`

Method used internally Solves cubic equation: c[0] + c[1]*x + c[2]*x^2 + c[3]*x^3 = 0 upto three possible solution, make sure c[3] is non-zero Ref Graphics Gems I, Schwarze, Jochen, Cubic and Quartic Roots, p.

404-407

normal form: x^3 + Ax^2 + Bx + C = 0

substitute x = y - A/3 to eliminate quadric term: x^3 +px + q = 0

use Cardano's formula

one triple solution

one single and one SReal solution

Casus irreducibilis: three SReal solutions

one SReal solution

resubstitute

Definition at line 423 of file ContinuousTriangleIntersection.cpp.

References cbrt, IsZero, and R_PI.

Referenced by intersectEdgeEdge(), and intersectPointTriangle().

int sofa::component::collision::ContinuousTriangleIntersection::solveQuadratic	(	SReal &	t1,
		SReal &	t2,
		const SReal &	a,
		const SReal &	b,
		const SReal &	c
	)			`[private]`