386 lines
13 KiB
C++
386 lines
13 KiB
C++
//////////////////////////////////////////////////////////////////////
|
|
//
|
|
// Crytek Common Source code
|
|
//
|
|
// File:Cry_GeoIntersect.h
|
|
// Description: Common intersection-tests
|
|
//
|
|
// History:
|
|
// -March 15,2003: Created by Ivo Herzeg
|
|
//
|
|
//////////////////////////////////////////////////////////////////////
|
|
|
|
#ifndef CRYINTERSECTION_H
|
|
#define CRYINTERSECTION_H
|
|
|
|
|
|
#if _MSC_VER > 1000
|
|
# pragma once
|
|
#endif
|
|
|
|
#include <Cry_Geo.h>
|
|
|
|
namespace Intersect {
|
|
|
|
|
|
|
|
inline bool Ray_Plane(const Ray &ray, const Plane &plane, Vec3 &output ) {
|
|
float numer = plane|ray.origin;
|
|
float cosine = plane.n|ray.direction;
|
|
//REJECTION 1: if "line-direction" is perpendicular to "plane-normal", an intersection is not possible!
|
|
//REJECTION 2: we deal with single-sided planes.
|
|
// if "line-direction" is pointing in the same direction as "the plane-normal",
|
|
// an intersection is not possible!
|
|
if (cosine > 0) return 0; //normal is orthogonal to vector, cant intersect
|
|
output = ray.origin+(ray.direction*(-numer/cosine));
|
|
//skip, if cutting-point is "behind" ray.origin
|
|
if (((output-ray.origin)|ray.direction)<0) return 0;
|
|
return 1; //intersection occured
|
|
}
|
|
|
|
inline bool Line_Plane(const Line &line, const Plane &plane, Vec3 &output ) {
|
|
double perpdist = plane|line.pointonline;
|
|
double cosine = plane.n|line.direction;
|
|
//REJECTION 1: if "line-direction" is perpendicular to "plane-normal", an intersection is not possible!
|
|
//REJECTION 2: we deal with single-sided planes.
|
|
// if "line-direction" is pointing in the same direction as "the plane-normal",
|
|
// an intersection is not possible!
|
|
if (cosine > 0) return 0;
|
|
//an intersection is possible: calculate the exact point!
|
|
float pd_c = (float)(-perpdist/cosine);
|
|
output = line.pointonline+(line.direction*pd_c);
|
|
return 1; //intersection occured
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/*
|
|
* calculates intersection between a line and a triangle.
|
|
* IMPORTANT: this is a single-sided intersection test. That means its not enough
|
|
* that the triangle and line overlap, its also important that the triangle
|
|
* is "visible" when you are looking along the line-direction.
|
|
*
|
|
* If you need a double-sided test, you'll have to call this function twice with
|
|
* reversed order of triangle vertices.
|
|
*
|
|
* return values
|
|
* if there is an intertection the functions return "true" and stores the
|
|
* 3d-intersection point in "output". if the function returns "false" the value in
|
|
* "output" is undefined
|
|
*
|
|
*/
|
|
inline bool Line_Triangle( const Line &line, const Vec3 &v0, const Vec3 &v1, const Vec3 &v2, Vec3 &output ) {
|
|
//find vectors for two edges sharing v0
|
|
Vec3 edge_1 = v1-v0;
|
|
Vec3 edge_2 = v2-v0;
|
|
//begin calculating determinant - also used to calculate U parameter
|
|
Vec3 pvec = line.direction % edge_1;
|
|
//if determinat is near zero, ray lies in plane of triangel
|
|
float det = edge_2 | pvec;
|
|
if (det<=0) return 0;
|
|
//calculate distance from v0 to ray origin
|
|
Vec3 tvec=line.pointonline-v0;
|
|
//calculate U parameter and test bounds
|
|
float u=tvec | pvec;
|
|
if (u<0.0f || u>det) return 0;
|
|
//prepare to test V parameter
|
|
Vec3 qvec=tvec % edge_2;
|
|
//calculate V parameter and test bounds
|
|
float v= (line.direction | qvec);
|
|
if ( v<0.0f || (u+v)>det) return 0;
|
|
//------------------------------------------------------
|
|
//we have an intersection and now we can calculate t
|
|
float t = (edge_1 | qvec) / det;
|
|
//we use t als a scale parameter, to get the 3D-intersection point
|
|
output = (line.direction*t)+line.pointonline;
|
|
return 1;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/*
|
|
* calculates intersection between a ray and a triangle.
|
|
* IMPORTANT: this is a single-sided intersection test. That means its not sufficient
|
|
* that the triangle and rayt overlap, its also important that the triangle
|
|
* is "visible" when you from the origin along the ray-direction.
|
|
*
|
|
* If you need a double-sided test, you'll have to call this function twice with
|
|
* reversed order of triangle vertices.
|
|
*
|
|
* return values
|
|
* if there is an intertection the functions return "true" and stores the
|
|
* 3d-intersection point in "output". if the function returns "false" the value in
|
|
* "output" is undefined
|
|
*/
|
|
inline bool Ray_Triangle( const Ray &ray, const Vec3 &v0, const Vec3 &v1, const Vec3 &v2, Vec3 &output ) {
|
|
//find vectors for two edges sharing v0
|
|
Vec3 edge_1 = v1-v0;
|
|
Vec3 edge_2 = v2-v0;
|
|
//begin calculating determinant - also used to calculate U parameter
|
|
Vec3 pvec = ray.direction % edge_1;
|
|
//if determinat is near zero, ray lies in plane of triangle
|
|
float det = edge_2 | pvec;
|
|
if (det<=0) return 0;
|
|
//calculate distance from v0 to ray origin
|
|
Vec3 tvec=ray.origin-v0;
|
|
//calculate U parameter and test bounds
|
|
float u=tvec | pvec;
|
|
if (u<0.0f || u>det) return 0;
|
|
//prepare to test V parameter
|
|
Vec3 qvec=tvec % edge_2;
|
|
//calculate V parameter and test bounds
|
|
float v= (ray.direction | qvec);
|
|
if ( v<0.0f || (u+v)>det) return 0;
|
|
//------------------------------------------------------
|
|
//We have an intersection and we can calculate t
|
|
float t = (edge_1 | qvec) / det;
|
|
//we use t als a scale parameter, to get the 3D-intersection point
|
|
output = (ray.direction*t)+ray.origin;
|
|
//skip, if cutting-point is "behind" ray.origin
|
|
if (((output-ray.origin)|ray.direction)<0) return 0;
|
|
return 1;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/*!
|
|
*
|
|
* calculates intersection between a line-segment and a triangle.
|
|
* IMPORTANT: this is a single-sided intersection test. That means its not sufficient
|
|
* that the triangle and line-segment overlap, its also important that the triangle
|
|
* is "visible" when you are looking along the linesegment from "start" to "end".
|
|
*
|
|
* If you need a double-sided test, you'll have to call this function twice with
|
|
* reversed order of triangle vertices.
|
|
*
|
|
* return values
|
|
* if there is an intertection the the functions return "true" and stores the
|
|
* 3d-intersection point in "output". if the function returns "false" the value in
|
|
* "output" is undefined
|
|
*
|
|
*/
|
|
inline bool Lineseg_Triangle( const Lineseg &lineseg, const Vec3 &v0, const Vec3 &v1, const Vec3 &v2, Vec3 &output ) {
|
|
//find vectors for two edges sharing v0
|
|
Vec3 edge_1 = v1-v0;
|
|
Vec3 edge_2 = v2-v0;
|
|
//direction of lineseg. normalizing is not necessary
|
|
Vec3 direction=(lineseg.end-lineseg.start);
|
|
//begin calculating determinant - also used to calculate U parameter
|
|
Vec3 pvec = direction % edge_1;
|
|
//if determinat is near zero, ray lies in plane of triangle
|
|
float det = edge_2 | pvec;
|
|
if (det<=0) return 0;
|
|
//calculate distance from v0 to ray origin
|
|
Vec3 tvec=lineseg.start-v0;
|
|
//calculate U parameter and test bounds
|
|
float u=tvec | pvec;
|
|
if (u<0.0f || u>det) return 0;
|
|
//prepare to test V parameter
|
|
Vec3 qvec=tvec % edge_2;
|
|
//calculate V parameter and test bounds
|
|
float v= (direction | qvec);
|
|
if ( v<0.0f || (u+v)>det) return 0;
|
|
//------------------------------------------------------
|
|
//If we ignore the limitations of linesegment, then we have an intersection and we calcultate t
|
|
float t = (edge_1 | qvec) / det;
|
|
//we use t als a scale parameter, to get the 3D-intersection point
|
|
output = (direction*t)+lineseg.start;
|
|
//skip, if lineseg and triangle are not overlapping
|
|
if (((output-lineseg.start)|direction)<0) return 0;
|
|
if (((output-lineseg.end)|direction)>0) return 0;
|
|
return 1;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
//----------------------------------------------------------------------------------
|
|
//--- 0x00 = no intersection --------------------------
|
|
//--- 0x01 = not possible --
|
|
//--- 0x02 = not possible --
|
|
//--- 0x03 = two intersection, lineseg has ENTRY and EXIT point --
|
|
//----------------------------------------------------------------------------------
|
|
|
|
inline unsigned char Line_Sphere( const Line &line, const Sphere &s, Vec3 &i0, Vec3 &i1 ) {
|
|
|
|
Vec3 end=line.pointonline+line.direction;
|
|
|
|
float a = line.direction|line.direction;
|
|
float b = (line.direction|(line.pointonline-s.center))*2.0f;
|
|
float c = ((line.pointonline-s.center)|(line.pointonline-s.center)) - (s.radius*s.radius);
|
|
|
|
float desc = (b*b) - (4 * a *c);
|
|
|
|
unsigned char intersection=0;
|
|
if (desc >= 0.0f)
|
|
{
|
|
float lamba0 = (-b - cry_sqrtf(desc)) / (2.0f * a);
|
|
//_stprintf(d3dApp.token,"lamba0: %20.12f",lamba0);
|
|
//d3dApp.m_pFont->DrawText( 2, d3dApp.PrintY, D3DCOLOR_ARGB(255,255,255,0), d3dApp.token ); d3dApp.PrintY+=20;
|
|
i0 = line.pointonline + ((end-line.pointonline)*lamba0);
|
|
intersection=1;
|
|
|
|
float lamba1 = (-b + cry_sqrtf(desc))/(2.0f*a);
|
|
//_stprintf(d3dApp.token,"lamba1: %20.12f",lamba1);
|
|
//d3dApp.m_pFont->DrawText( 2, d3dApp.PrintY, D3DCOLOR_ARGB(255,255,255,0), d3dApp.token ); d3dApp.PrintY+=20;
|
|
i1 = line.pointonline + ((end-line.pointonline)*lamba1);
|
|
intersection|=2;
|
|
}
|
|
|
|
return intersection;
|
|
}
|
|
|
|
|
|
|
|
//----------------------------------------------------------------------------------
|
|
//--- 0x00 = no intersection --------------------------
|
|
//--- 0x01 = not possible --
|
|
//--- 0x02 = one intersection, lineseg has just an EXIT point but no ENTRY point (ls.start is inside the sphere) --
|
|
//--- 0x03 = two intersection, lineseg has ENTRY and EXIT point --
|
|
//----------------------------------------------------------------------------------
|
|
|
|
inline unsigned char Ray_Sphere( const Ray &ray, const Sphere &s, Vec3 &i0, Vec3 &i1 ) {
|
|
Vec3 end=ray.origin+ray.direction;
|
|
float a = ray.direction|ray.direction;
|
|
float b = (ray.direction|(ray.origin-s.center))*2.0f;
|
|
float c = ((ray.origin-s.center)|(ray.origin-s.center)) - (s.radius*s.radius);
|
|
|
|
float desc = (b*b) - (4 * a *c);
|
|
|
|
unsigned char intersection=0;
|
|
if (desc >= 0.0f)
|
|
{
|
|
float lamba0 = (-b - cry_sqrtf(desc)) / (2.0f * a);
|
|
// _stprintf(d3dApp.token,"lamba0: %20.12f",lamba0);
|
|
// d3dApp.m_pFont->DrawText( 2, d3dApp.PrintY, D3DCOLOR_ARGB(255,255,255,0), d3dApp.token ); d3dApp.PrintY+=20;
|
|
if (lamba0>0.0f) {
|
|
i0 = ray.origin + ((end-ray.origin)*lamba0);
|
|
intersection=1;
|
|
}
|
|
|
|
float lamba1 = (-b + cry_sqrtf(desc))/(2.0f*a);
|
|
// _stprintf(d3dApp.token,"lamba1: %20.12f",lamba1);
|
|
// d3dApp.m_pFont->DrawText( 2, d3dApp.PrintY, D3DCOLOR_ARGB(255,255,255,0), d3dApp.token ); d3dApp.PrintY+=20;
|
|
if (lamba1>0.0f) {
|
|
i1 = ray.origin + ((end-ray.origin)*lamba1);
|
|
intersection|=2;
|
|
}
|
|
}
|
|
return intersection;
|
|
}
|
|
|
|
inline bool Ray_SphereFirst( const Ray &ray, const Sphere &s, Vec3 &intPoint )
|
|
{
|
|
Vec3 p2;
|
|
unsigned char res = Ray_Sphere( ray,s,intPoint,p2 );
|
|
if (res == 2) { intPoint = p2; }
|
|
if (res > 1) return true;
|
|
return false;
|
|
}
|
|
|
|
|
|
|
|
//----------------------------------------------------------------------------------
|
|
//--- 0x00 = no intersection --------------------------
|
|
//--- 0x01 = one intersection, lineseg has just an ENTRY point but no EXIT point (ls.end is inside the sphere) --
|
|
//--- 0x02 = one intersection, lineseg has just an EXIT point but no ENTRY point (ls.start is inside the sphere) --
|
|
//--- 0x03 = two intersection, lineseg has ENTRY and EXIT point --
|
|
//----------------------------------------------------------------------------------
|
|
inline unsigned char Lineseg_Sphere( const Lineseg &ls, const Sphere &s, Vec3 &i0, Vec3 &i1 ) {
|
|
|
|
Vec3 dir = (ls.end - ls.start);
|
|
|
|
float a = dir|dir;
|
|
float b = (dir|(ls.start-s.center))*2.0f;
|
|
float c = ((ls.start-s.center)|(ls.start-s.center)) - (s.radius*s.radius);
|
|
float desc = (b*b) - (4 * a *c);
|
|
|
|
unsigned char intersection=0;
|
|
if (desc >= 0.0f) {
|
|
|
|
float lamba0 = (-b - cry_sqrtf(desc)) / (2.0f * a);
|
|
//_stprintf(d3dApp.token,"lamba0: %20.12f",lamba0);
|
|
//d3dApp.m_pFont->DrawText( 2, d3dApp.PrintY, D3DCOLOR_ARGB(255,255,255,0), d3dApp.token ); d3dApp.PrintY+=20;
|
|
if (lamba0 >0.0f) {
|
|
i0 = ls.start + ((ls.end-ls.start)*lamba0);
|
|
//skip, if 1st cutting-point is "in front" of ls.end
|
|
if (((i0-ls.end)|dir)>0) return 0;
|
|
intersection=0x01;
|
|
}
|
|
|
|
float lamba1 = (-b + cry_sqrtf(desc)) / (2.0f * a);
|
|
//_stprintf(d3dApp.token,"lamba1: %20.12f",lamba1);
|
|
//d3dApp.m_pFont->DrawText( 2, d3dApp.PrintY, D3DCOLOR_ARGB(255,255,255,0), d3dApp.token ); d3dApp.PrintY+=20;
|
|
if ( lamba1 > 0.0f) {
|
|
i1 = ls.start + ((ls.end-ls.start)*lamba1);
|
|
//skip, if 2nd cutting-point is "in front" of ls.end (=ls.end is inside sphere)
|
|
if (((i1-ls.end)|dir)>0) return intersection;
|
|
intersection|=0x02;
|
|
}
|
|
}
|
|
return intersection;
|
|
}
|
|
|
|
|
|
|
|
// line/sphere-intersection
|
|
// p1: 1st point of line
|
|
// p2: 2nd point of line
|
|
// p3: center of sphere
|
|
// r: radius of sphere
|
|
// i1: 1st intersection point
|
|
// i2: 2nd intersection point
|
|
// return number of intersections
|
|
inline int Lineseg_Sphere(Vec3 p1, Vec3 p2, Vec3 p3, float r, Vec3 &i1, Vec3 i2)
|
|
{
|
|
float dx=p2.x-p1.x;
|
|
float dy=p2.y-p1.y;
|
|
float dz=p2.z-p1.z;
|
|
float a=dx*dx+dy*dy+dz*dz;
|
|
float b=2.0f*(dx*(p1.x-p3.x)+dy*(p1.y-p3.y)+dz*(p1.z-p3.z));
|
|
float c=p3.Dot(p3)+p2.Dot(p2)-2.0f*(p3.x*p1.x+p3.y*p1.y+p3.z-p1.z)-r*r;
|
|
float d=b*b-4.0f*a*c;
|
|
if (d<0.0f)
|
|
return 0;
|
|
float u;
|
|
u=(-b+(float)sqrt((double)d))/a*a;
|
|
i1=p1+((p2-p1)*u);
|
|
if (d==0.0)
|
|
return 1;
|
|
u=(-b-(float)sqrt((double)d))/a*a;
|
|
i2=p1+((p2-p1)*u);
|
|
return 2;
|
|
}
|
|
|
|
|
|
}; //CIntersect
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#endif //vector
|