flipcode - Moving Sphere VS Triangle Collision

Moving Sphere VS Triangle Collision
Submitted by

In today's real time application, one of the most useful features when starting to speak about collision detection is maybe the ability to collide a simple primitive such as a box or sphere VS a polygon soup. As surprising as it could seem, there are not tons of tutorials or source code over there. Of course there is the Nettle/Telemachos approach but, unfortunately, their algorithm is not mathematically accurate (see archives on news group, mailing-list etc. for more details). Different documentations can sometimes be a little too theoretic and lack concrete examples. The purpose of this COTD is to show a pretty easy way to calculate the moment of collision between a moving sphere and a triangle if collision occurs. You just need to pass the needed parameters (triangle coordinates, sphere position/velocity, etc.) to the function testIntersectionTriSphere(). A boolean value simply indicates if a collision occurs and if yes, when. You can use this function everywhere. It works for a simple camera ride (spectator mode ala Quake) or to represent a full character in a 3D environement. The algorithm here uses a "continuous collision detection". It means you can move your sphere at any speed, a collision will never be missed. However, this is only about narrow collision detection. You should use before your own geometric hierarchy such as BSP, octree or whatever to limit the amount of tested polygons as much as possible in a broad phase. The source code also contains dependent algorithms such as line/line or sphere/line intersections that you could find interesting to investigate. Note there are optimizations I voluntarily removed from the code for the sake of clarity (this is a COTD and its first purpose is educational). You can use this code or portion of code at your will for both commercial or non-commercial project. I would just appreciate to be informed via e-mail of its usage. Also don't hesitate to contact me for any constructive remark.

Igor Kravtchenko
Programmer @ OBRAZ Studio, Paris
http://www.obrazstudio.com

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/plane.cpp] - (458 bytes)


#include "stdafx.h"

void Plane::fromPoints(const Vec3f &_p0, const Vec3f &_p1, const Vec3f &_p2)
{
	Vec3f v0(_p0 - _p1);
	Vec3f v1(_p2 - _p1);
	Vec3f n = v1 | v0;
	n.normalize();
	a = n.x;
	b = n.y;
	c = n.z;
	d = -(_p0.x * a + _p0.y * b + _p0.z * c);
}

void Plane::fromPointAndNormal(const Vec3f &_p, const Vec3f &_n)
{
	Vec3f nn = _n;
	nn.normalize();
	a = nn.x;
	b = nn.y;
	c = nn.z;
	d = -(_p.x * a + _p.y * b + _p.z * c);
}

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/vec2f.h] - (2,604 bytes)


/***********************************************************************************
	FileName: 	vec2f.h
	Author:		Igor Kravtchenko
	
	Info:		
************************************************************************************/

#ifndef OZMATH_VEC2F_H
#define OZMATH_VEC2F_H

class Vec2f {
public:

	ozinline Vec2f()
	{
	}

	ozinline Vec2f(float _x, float _y) : x(_x), y(_y)
	{
	}

	ozinline Vec2f operator - () const
	{
		return Vec2f(-x, -y);
	}

	ozinline void operator -= (const Vec2f &_v)
	{
		x -= _v.x;
		y -= _v.y;
	}

	ozinline void operator += (const Vec2f &_v)
	{
		x += _v.x;
		y += _v.y;
	}

	ozinline void operator *= (float _mul)
	{
		x *= _mul;
		y *= _mul;
	}

	ozinline void operator *= (const Vec2f &_v)
	{
		x *= _v.x;
		y *= _v.y;
	}

	ozinline void operator /= (float _div)
	{
		float mul = 1.0f / _div;
		x *= mul;
		y *= mul;
	}

	ozinline Vec2f operator - (const Vec2f &_v) const
	{
		return Vec2f(x - _v.x, y - _v.y);
	}

	ozinline Vec2f operator + (const Vec2f &_v) const
	{
		return Vec2f(x + _v.x, y + _v.y);
	}
	
	ozinline Vec2f operator * (const Vec2f &_v) const
	{
		return Vec2f(x * _v.x, y * _v.y);
	}
	
	ozinline Vec2f operator * (float _m) const
	{
		return Vec2f(x * _m, y * _m);
	}

	ozinline Vec2f operator / (const Vec2f &_v) const
	{
		return Vec2f(x / _v.x, y / _v.y);
	}

	ozinline Vec2f operator / (float _d) const
	{
		float m = 1.0f / _d;
		return Vec2f(x * m, y * m);
	}

	ozinline Vec2f operator | (const Vec2f &_d) const
	{
		return Vec2f(y * _d.y - x * _d.y, // FIXME!
			y * _d.x - x * _d.y);
	}

	ozinline ozbool operator == (const Vec2f &_v) const
	{
		if (x == _v.x && y == _v.y)
			return OZTRUE;
		return OZFALSE;
	}

	ozinline ozbool operator != (const Vec2f &_v) const
	{
		if (x != _v.x || y != _v.y)
			return OZTRUE;
		return OZFALSE;
	}

	ozinline float operator [] (int _i) const
	{
		const float *val = &x;
		return val[_i];
	}

	ozinline float len() const
	{
		float len = x * x + y * y;
		return (float) sqrt(len);
	}

	ozinline float lenSq() const
	{
		return x * x + y * y;
	}

	ozinline float dot(const Vec2f &_v) const
	{
		return x * _v.x + y * _v.y;
	}

	ozinline void normalize()
	{
		float ln = len();
		if (!ln)
			return;
		float div = 1.0f / ln;
		x *= div;
		y *= div;
	}

	ozinline void positive()
	{
		if (x < 0) x = -x;
		if (y < 0) y = -y;
	}

	float x, y;
};

ozinline Vec2f operator * (float _m, const Vec2f &_v)
{
	return Vec2f(_v.x * _m, _v.y * _m);
}

#endif

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/plane.h] - (1,708 bytes)


/***********************************************************************************
	FileName: 	plane.h
	Author:		Igor Kravtchenko
	
	Info:		
************************************************************************************/

#ifndef OZMATH_PLANE_H
#define OZMATH_PLANE_H

#include "vec3f.h"

enum PLANE {
	LEFT_PLANE, RIGHT_PLANE,
	BOTTOM_PLANE, TOP_PLANE,
	NEAR_PLANE, FAR_PLANE
};

class Plane {
public:

	Plane() { };
	Plane(float _a, float _b, float _c, float _d) : a(_a), b(_b), c(_c), d(_d) { };

	void fromPoints(const Vec3f &p_0, const Vec3f &_p1, const Vec3f &_p2);
	void fromPointAndNormal(const Vec3f &_p, const Vec3f &_n);

	ozinline float dot(const Vec3f &_p) const
	{
		return a * _p.x + b * _p.y + c * _p.z;
	}

	ozinline float dist(const Vec3f &_p) const
	{
		return a * _p.x + b * _p.y + c * _p.z + d;
	}

	ozinline Vec3f reflect(const Vec3f &_vec)
	{
		float d = dist(_vec);
		return _vec + 2 * Vec3f(-a, -b, -c) * d;
	}

	ozinline Vec3f project(const Vec3f &_p)
	{
		float h = dist(_p);
		return Vec3f(_p.x - a * h,
					 _p.y - b * h,
					 _p.z - c * h);
	}

	ozinline ozbool isOnPlane(const Vec3f &_p, float _threshold = 0.001f)
	{
		float d = dist(_p);
		if (d < _threshold && d > -_threshold)
			return OZTRUE;
		return OZFALSE;
	}

	// Calcul the intersection between this plane and a line
	// If the plane and the line are parallel, OZFALSE is returned
	ozinline ozbool intersectWithLine(const Vec3f &_p0, const Vec3f &_p1, float &_t)
	{
		Vec3f dir = _p1 - _p0;
		float div = dot(dir);
		if (div == 0)
			return OZFALSE;

		_t = -dist(_p0) / div;
		return OZTRUE;
	}

	float a, b, c, d;
};

#endif

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/intr_sphereline.h] - (708 bytes)


/***********************************************************************************
	FileName: 	intr_sphereline.h
	Author:		Igor Kravtchenko
	
	Info:		
************************************************************************************/

#ifndef OZOSMATH_INTR_SPHERELINE_H
#define OZOSMATH_INTR_SPHERELINE_H

#include "sphere.h"

// Test the intersection between a sphere and a line
// The implementation uses standard quadratic solver and so, is not especially optimized
ozbool testIntersectionSphereLine(const Sphere &,
								  const Vec3f &pt0,
								  const Vec3f &pt1,
								  int *nbInter = NULL,
								  float *inter1 = NULL,
								  float *inter2 = NULL);

#endif

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/dist_pointline.cpp] - (583 bytes)


#include "stdafx.h"

float sqrDistancePointToLine(const Vec3f &_point,
							 const Vec3f &_pt0,
							 const Vec3f &_pt1,
							 Vec3f *_linePt)
{
	Vec3f v = _point - _pt0;
	Vec3f s = _pt1 - _pt0;
	float lenSq = s.lenSq();
	float dot = v.dot(s) / lenSq;
	Vec3f disp = s * dot;
	if (_linePt)
		*_linePt = _pt0 + disp;
	v -= disp;
	return v.lenSq();
}

float distancePointToLine(const Vec3f &_point,
						  const Vec3f &_pt0,
						  const Vec3f &_pt1,
						  Vec3f *_linePt)
{
	return sqrtf( sqrDistancePointToLine(_point, _pt0, _pt1, _linePt) );
}

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/vec3f.h] - (2,940 bytes)


/***********************************************************************************
	FileName: 	vec3f.h
	Author:		Igor Kravtchenko
	
	Info:		
************************************************************************************/

#ifndef OZOSMATH_VEC3F_H
#define OZOSMATH_VEC3F_H

#define ZEROVEC3F Vec3f(0, 0, 0)
#define UNITVEC3F Vec3f(1, 1, 1)

class Vec3f {
public:

	ozinline Vec3f()
	{
	}

	ozinline Vec3f(float _x, float _y, float _z) : x(_x), y(_y), z(_z)
	{
	}

	ozinline Vec3f operator - () const
	{
		return Vec3f(-x, -y, -z);
	}

	ozinline void operator -= (const Vec3f &_v)
	{
		x -= _v.x;
		y -= _v.y;
		z -= _v.z;
	}

	ozinline void operator += (const Vec3f &_v)
	{
		x += _v.x;
		y += _v.y;
		z += _v.z;
	}

	ozinline void operator *= (float _mul)
	{
		x *= _mul;
		y *= _mul;
		z *= _mul;
	}

	ozinline void operator *= (const Vec3f &_v)
	{
		x *= _v.x;
		y *= _v.y;
		z *= _v.z;
	}

	ozinline void operator /= (float _div)
	{
		float mul = 1.0f / _div;
		x *= mul;
		y *= mul;
		z *= mul;
	}

	ozinline Vec3f operator - (const Vec3f &_v) const
	{
		return Vec3f(x - _v.x, y - _v.y, z - _v.z);
	}

	ozinline Vec3f operator + (const Vec3f &_v) const
	{
		return Vec3f(x + _v.x, y + _v.y, z + _v.z);
	}
	
	ozinline Vec3f operator * (const Vec3f &_v) const
	{
		return Vec3f(x * _v.x, y * _v.y, z * _v.z);
	}
	
	ozinline Vec3f operator * (float _m) const
	{
		return Vec3f(x * _m, y * _m, z * _m);
	}

	ozinline Vec3f operator / (const Vec3f &_v) const
	{
		return Vec3f(x / _v.x, y / _v.y, z / _v.z);
	}

	ozinline Vec3f operator / (float _d) const
	{
		float m = 1.0f / _d;
		return Vec3f(x * m, y * m, z * m);
	}

	ozinline Vec3f operator | (const Vec3f &_d) const
	{
		return Vec3f(y * _d.z - z * _d.y,
			z * _d.x - x * _d.z,
			x * _d.y - y * _d.x);
	}

	ozinline ozbool operator == (const Vec3f &_v) const
	{
		if (x == _v.x && y == _v.y && z == _v.z)
			return OZTRUE;
		return OZFALSE;
	}

	ozinline ozbool operator != (const Vec3f &_v) const
	{
		if (x != _v.x || y != _v.y || z != _v.z)
			return OZTRUE;
		return OZFALSE;
	}

	ozinline float operator [] (int _i) const
	{
		const float *val = &x;
		return val[_i];
	}

	ozinline float len() const
	{
		float len = x * x + y * y + z * z;
		return (float) sqrt(len);
	}

	ozinline float lenSq() const
	{
		return x * x + y * y + z * z;
	}

	ozinline float dot(const Vec3f &_v) const
	{
		return x * _v.x + y * _v.y + z * _v.z;
	}

	ozinline void normalize()
	{
		float ln = len();
		if (!ln)
			return;
		float div = 1.0f / ln;
		x *= div;
		y *= div;
		z *= div;
	}

	ozinline void positive()
	{
		if (x < 0) x = -x;
		if (y < 0) y = -y;
		if (z < 0) z = -z;
	}

	float x, y, z;
};

ozinline Vec3f operator * (float _m, const Vec3f &_v)
{
	return Vec3f(_v.x * _m, _v.y * _m, _v.z * _m);
}

#endif

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/sphere.h] - (878 bytes)


/***********************************************************************************
	FileName: 	sphere.h
	Author:		Igor Kravtchenko
	
	Info:		
************************************************************************************/

#ifndef OZMATH_SPHERE_H
#define OZMATH_SPHERE_H

#include "vec3f.h"

class Sphere {

public:
	Sphere() { };
	Sphere(const Vec3f &_center, float _radius) : center(_center), radius(_radius) { };

	ozinline ozbool isCollide(const Sphere &_s) const 
	{
		Vec3f diff = _s.center - center;
		float sqDist = diff.lenSq();
		float r = _s.radius + radius;
		if (sqDist <= r * r)
			return OZTRUE;
		return OZFALSE;
	}

	ozinline ozbool isPointInside(const Vec3f &_pt) const
	{
		float dist = (_pt - center).lenSq();
		return dist < (radius * radius) ? OZTRUE : OZFALSE;
	}

	Vec3f center;
	float radius;
};

#endif

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/intr_lineline.h] - (590 bytes)


/***********************************************************************************
	FileName: 	intr_lineline.h
	Author:		Igor Kravtchenko
	
	Info:		
************************************************************************************/

#ifndef OZOSMATH_INTR_LINELINE_H
#define OZOSMATH_INTR_LINELINE_H

#include "vec2f.h"

// test if two 2D lines (p0, p1) and (p2, p3) intersect
// if they do OZTRUE is returned, OZFALSE otherwhise
ozbool testIntersectionLineLine(const Vec2f &p1, const Vec2f &p2,
								const Vec2f &p3, const Vec2f &p4,
								float *t);

#endif

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/StdAfx.cpp] - (299 bytes)

// stdafx.cpp : source file that includes just the standard includes
//	swept_sphere.pch will be the pre-compiled header
//	stdafx.obj will contain the pre-compiled type information

#include "stdafx.h"

// TODO: reference any additional headers you need in STDAFX.H
// and not in this file

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/dist_pointline.h] - (626 bytes)


/***********************************************************************************
	FileName: 	dist_pointline.h
	Author:		Igor Kravtchenko
	
	Info:		
************************************************************************************/

#ifndef OZOSMATH_DIST_POINTLINE_H
#define OZOSMATH_DIST_POINTLINE_H

#include "vec3f.h"

float sqrDistancePointToLine(const Vec3f &point,
						     const Vec3f &pt0,
							 const Vec3f &pt1,
							 Vec3f *linePt = NULL);

float distancePointToLine(const Vec3f &point,
						  const Vec3f &pt0,
						  const Vec3f &pt1,
						  Vec3f *linePt = NULL);

#endif

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/intr_tripoint.h] - (677 bytes)


/***********************************************************************************
	FileName: 	intr_tripoint.h
	Author:		Igor Kravtchenko
	
	Info:		
************************************************************************************/

#ifndef OZMATH_INTR_TRIPOINT_H
#define OZMATH_INTR_TRIPOINT_H

#include "vec3f.h"

// Test if a point is inside a triangle (in a pretty speedy way) given three points.

ozbool isPointInsideTriangle(const Vec3f &vertex0,
							 const Vec3f &vertex1,
							 const Vec3f &vertex2,
							 const Vec3f &pt);

ozbool isPointInsidePolygon(int nbVertices,
						    const Vec3f *pnts,
							const Vec3f &pt);

#endif

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/intr_spheretri.cpp] - (3,318 bytes)


#include "stdafx.h"

ozbool testIntersectionTriSphere(const Vec3f *_triPts[3],
								 const Vec3f &_triNormal,
								 const Sphere &_sphere,
								 const Vec3f &_sphereVel,
								 float &_distTravel,
								 Vec3f *_reaction)
{
	int i;
	Vec3f nvelo = _sphereVel;
	nvelo.normalize();

	if (_triNormal.dot(nvelo) > -0.001f)
		return OZFALSE;

	float minDist = FLT_MAX;
	Vec3f reaction;
	int col = -1;
	_distTravel = FLT_MAX;

	Plane plane;
	plane.fromPointAndNormal(*_triPts[0], _triNormal);

	// pass1: sphere VS plane
	float h = plane.dist( _sphere.center );
	if (h < -_sphere.radius)
		return OZFALSE;

	if (h > _sphere.radius) {
		h -= _sphere.radius;
		float dot = _triNormal.dot(nvelo);
		if (dot != 0) {
			float t = -h / dot;
			Vec3f onPlane = _sphere.center + nvelo * t;
			if (isPointInsideTriangle( *_triPts[0], *_triPts[1], *_triPts[2], onPlane)) {
				if (t < _distTravel) {
					_distTravel = t;
					if (_reaction)
						*_reaction = _triNormal;
					col = 0;
				}
			}
		}
	}

	// pass2: sphere VS triangle vertices
	for (i = 0; i < 3; i++) {
		Vec3f seg_pt0 = *_triPts[i];
		Vec3f seg_pt1 = seg_pt0 - nvelo;
		Vec3f v = seg_pt1 - seg_pt0;

		float inter1=FLT_MAX, inter2=FLT_MAX;
		int nbInter;
		ozbool res = testIntersectionSphereLine(_sphere, seg_pt0, seg_pt1, &nbInter, &inter1, &inter2);
		if (res == OZFALSE)
			continue;

		float t = inter1;
		if (inter2 < t)
			t = inter2;

		if (t < 0)
			continue;

		if (t < _distTravel) {
			_distTravel = t;
			Vec3f onSphere = seg_pt0 + v * t;
			if (_reaction)
				*_reaction = _sphere.center - onSphere;
			col = 1;
		}
	}

	// pass3: sphere VS triangle edges
	for (i = 0; i < 3; i++) {
		Vec3f edge0 = *_triPts[i];
		int j = i + 1;
		if (j == 3)
			j = 0;
		Vec3f edge1 = *_triPts[j];

		Plane plane;
		plane.fromPoints(edge0, edge1, edge1 - nvelo);
		float d = plane.dist(_sphere.center);
		if (d > _sphere.radius || d < -_sphere.radius)
			continue;

		float srr = _sphere.radius * _sphere.radius;
		float r = sqrtf(srr - d*d);

		Vec3f pt0 = plane.project(_sphere.center); // center of the sphere slice (a circle)

		Vec3f onLine;
		float h = distancePointToLine(pt0, edge0, edge1, &onLine);
		Vec3f v = onLine - pt0;
		v.normalize();
		Vec3f pt1 = v * r + pt0; // point on the sphere that will maybe collide with the edge

		int a0 = 0, a1 = 1;
		float pl_x = fabsf(plane.a);
		float pl_y = fabsf(plane.b);
		float pl_z = fabsf(plane.c);
		if (pl_x > pl_y && pl_x > pl_z) {
			a0 = 1;
			a1 = 2;
		}
		else {
			if (pl_y > pl_z) {
				a0 = 0;
				a1 = 2;
			}
		}

		Vec3f vv = pt1 + nvelo;

		float t;
		ozbool res = testIntersectionLineLine(  Vec2f(pt1[a0], pt1[a1]),
												Vec2f(vv[a0], vv[a1]),
												Vec2f(edge0[a0], edge0[a1]),
												Vec2f(edge1[a0], edge1[a1]),
												&t);
		if (!res || t < 0)
			continue;

		Vec3f inter = pt1 + nvelo * t;

		Vec3f r1 = edge0 - inter;
		Vec3f r2 = edge1 - inter;
		if (r1.dot(r2) > 0)
			continue;

		if (t > _distTravel)
			continue;

		_distTravel = t;
		if (_reaction)
			*_reaction = _sphere.center - pt1;
		col = 2;
	}

	if (_reaction && col != -1)
		_reaction->normalize();

	return col == -1 ? OZFALSE : OZTRUE;
}

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/swept_sphere.cpp] - (240 bytes)


// dummy main() function just to test the compilation
// see "intr_spheretri.h" for the real function
//
// Igor Kravtchenko for Flipcode's COTD, 23/10/2003

#include "stdafx.h"

int main(int argc, char* argv[])
{
	return 0;
}

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/intr_spheretri.h] - (1,169 bytes)


/***********************************************************************************
	FileName: 	intr_spheretri.h
	Author:		Igor Kravtchenko
	
	Info:		
************************************************************************************/

#ifndef OZMATH_INTERSECTION_SPHERETRI_H
#define OZMATH_INTERSECTION_SPHERETRI_H

#include "vec3f.h"
#include "plane.h"
#include "sphere.h"

// Test if a moving sphere intersects with a static triangle
//
// [in] triPts				an array of three pointers to point to define the triangle
// [in] triNormal			precalculated normal of the triangle
// [in] sphere				the moving sphere
// [in] sphereVel			sphere's velocity
// [out] distTravel			if a collision occurs, distance to travel before being in collision
// [out] reaction			optional, reaction vector if a collision occurs to handle some physic event
// [return]					OZTRUE if the sphere and triangle intersect, OZFALSE otherwhise
ozbool testIntersectionTriSphere(const Vec3f *triPts[3],
								 const Vec3f &triNormal,
								 const Sphere &sphere,
								 const Vec3f &sphereVel,
								 float &distTravel,
								 Vec3f *reaction);


#endif

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/intr_lineline.cpp] - (416 bytes)


#include "stdafx.h"

ozbool testIntersectionLineLine(const Vec2f &_p1, const Vec2f &_p2,
								const Vec2f &_p3, const Vec2f &_p4,
								float *_t)
{
	Vec2f d1 = _p2 - _p1;
	Vec2f d2 = _p3 - _p4;

	float denom = d2.y*d1.x - d2.x*d1.y;
	if (!denom)
		return OZFALSE;

	if (_t) {
		float dist = d2.x*(_p1.y-_p3.y) - d2.y*(_p1.x-_p3.x);
		dist /= denom;
		*_t = dist;
	}

	return OZTRUE;
}

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/StdAfx.h] - (1,062 bytes)

// stdafx.h : include file for standard system include files,
//  or project specific include files that are used frequently, but
//      are changed infrequently
//

#if !defined(AFX_STDAFX_H__B43F411A_77B6_4B6A_88FC_86AFAE0B0E60__INCLUDED_)
#define AFX_STDAFX_H__B43F411A_77B6_4B6A_88FC_86AFAE0B0E60__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define WIN32_LEAN_AND_MEAN		// Exclude rarely-used stuff from Windows headers

#define ozinline _inline
#define ozbool bool

#define OZTRUE true
#define OZFALSE false

#include <float.h>
#include <math.h>
#include <stdio.h>

#include "dist_pointline.h"
#include "intr_lineline.h"
#include "intr_sphereline.h"
#include "intr_spheretri.h"
#include "intr_tripoint.h"
#include "plane.h"
#include "sphere.h"
#include "vec2f.h"
#include "vec3f.h"

//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif // !defined(AFX_STDAFX_H__B43F411A_77B6_4B6A_88FC_86AFAE0B0E60__INCLUDED_)

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/intr_tripoint.cpp] - (1,047 bytes)


#include "stdafx.h"

// This function uses the Dan Sunday's algorithm.

ozbool isPointInsideTriangle(const Vec3f &vertex0,
							 const Vec3f &vertex1,
							 const Vec3f &vertex2,
							 const Vec3f &pt)
{
	Vec3f u = vertex1 - vertex0;
	Vec3f v = vertex2 - vertex0;
	Vec3f w = pt - vertex0;

	float uu = u.dot(u);
	float uv = u.dot(v);
	float vv = v.dot(v);
	float wu = w.dot(u);
	float wv = w.dot(v);
	float d = uv * uv - uu * vv;

	float invD = 1 / d;
	float s = (uv * wv - vv * wu) * invD;
	if (s < 0 || s > 1)
		return OZFALSE;
	float t = (uv * wu - uu * wv) * invD;
	if (t < 0 || (s + t) > 1)
		return OZFALSE;

	return OZTRUE;
}

ozbool isPointInsidePolygon(int nbVertices,
							const Vec3f *pnts,
							const Vec3f &pt)
{
	int nbTriangles = nbVertices - 2;
	for (int i = 0; i < nbTriangles; i++) {
		const Vec3f &pt0 = pnts[0];
		const Vec3f &pt1 = pnts[i + 1];
		const Vec3f &pt2 = pnts[i + 2];
		if (isPointInsideTriangle(pt0, pt1, pt2, pt))
			return OZTRUE;
	}
	return OZFALSE;
}

Currently browsing [swept_sphere.zip] (11,696 bytes) - [swept_sphere/intr_sphereline.cpp] - (1,165 bytes)


#include "stdafx.h"

#define square(a) ((a)*(a))

ozbool testIntersectionSphereLine(const Sphere &_sphere,
								  const Vec3f &_pt0,
								  const Vec3f &_pt1,
								  int *_nbInter,
								  float *_inter1,
								  float *_inter2)
{
	float a, b, c, i;

	a = square(_pt1.x - _pt0.x) + square(_pt1.y - _pt0.y) + square(_pt1.z - _pt0.z);
	b =  2 * ( (_pt1.x - _pt0.x) * (_pt0.x - _sphere.center.x)
		+ (_pt1.y - _pt0.y) * (_pt0.y - _sphere.center.y)
		+ (_pt1.z - _pt0.z) * (_pt0.z - _sphere.center.z) ) ;
	c = square(_sphere.center.x) + square(_sphere.center.y) +
		square(_sphere.center.z) + square(_pt0.x) +
		square(_pt0.y) + square(_pt0.z) -
		2 * ( _sphere.center.x * _pt0.x + _sphere.center.y * _pt0.y + _sphere.center.z * _pt0.z ) - square(_sphere.radius) ;
	i =  b * b - 4 * a * c;

	if (i < 0)
		return OZFALSE;

	if (i == 0) {
		if (_nbInter) *_nbInter = 1;
		if (_inter1) *_inter1 = -b / (2 * a);
	}
	else {
		if (_nbInter) *_nbInter = 2;
		if (_inter1) *_inter1 = (-b + sqrtf( square(b) - 4*a*c )) / (2 * a);
		if (_inter2) *_inter2 = (-b - sqrtf( square(b) - 4*a*c )) / (2 * a);
	}

	return OZTRUE;
}

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.