THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 11/05/2010 at 15:27, xxxxxxxx wrote:
User Information:
Cinema 4D Version: 11.5
Platform: Windows ;
Language(s) : C++ ;
---------
How would I determine if a point in space is within the boundaries of an object?
Any help with this would be greatly appreciated. Thanks.
~Shawn
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 06:08, xxxxxxxx wrote:
Use a Ray-Triangle Intersection test. Problem is that it needs to test all polygons against the point and treat each non-triangular polygon as two or more triangles.
To make the elimination process faster, start with spherical bounding test then a oriented-bounding-box (OBB) test. This will tell you quickly whether the point is even near enough to the object to consider the ray-triangle testing (which is more intensive). You might also want to look into B-trees or Oct-trees.
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 06:25, xxxxxxxx wrote:
great .. thanks for the info robert. Nice to see you again!
~Shawn
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 10:03, xxxxxxxx wrote:
Hey Robert,
Is this the type of thing I should be looking for?
http://wiki.cgsociety.org/index.php?title=Ray_Triangle_Intersection&redirect=no
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 11:56, xxxxxxxx wrote:
Optimized code is faster. 
////////////////////////////////////////////////////////////////
// DIRayCollider.h
////////////////////////////////////////////////////////////////
// Drop It! Pro Ray-TrianglularMesh Intersection Class include
////////////////////////////////////////////////////////////////
// V0.8 2006.01.03 Robert Templeton
////////////////////////////////////////////////////////////////
#ifndef _DIRAYCOLLIDER_H_
#define _DIRAYCOLLIDER_H_
// CLASS: DIRayCollider
class DIRayCollider
{
private:
Vector* points;
CPolygon* poly;
CPolygon* lastPoly;
Matrix gmat;
LVector hitpos;
// Triangle
Vector v0;
Vector v1;
Vector v2;
// Ray
LVector p0;
LVector p1;
public:
DIRayCollider();
~DIRayCollider();
void Init(BaseObject* goal);
Bool Intersect(const Vector& ray_p0, const Vector& ray_p1, Real* distance);
//Bool IntersectNearPoint(const Vector& ray_p0, const Vector& ray_p1, Vector* point);
//Bool IntersectFarPoint(const Vector& ray_p0, const Vector& ray_p1, Vector* point);
CHAR intersect_RayTriangle(const LVector& lv0, const LVector& lv1, const LVector& lv2);
static DIRayCollider* Alloc();
static void Free(DIRayCollider*& data);
};
#endif //_DIRAYCOLLIDER_H_
////////////////////////////////////////////////////////////////
// DIRayCollider.cpp
////////////////////////////////////////////////////////////////
// Drop It! Pro Ray-TriangularMesh Intersection Class include
////////////////////////////////////////////////////////////////
// V0.8 2006.01.03 Robert Templeton
////////////////////////////////////////////////////////////////
// Includes
#include "general.h"
#include "DIRayCollider.h"
// METHODS: DIRayCollider ==================================================================================================
// Constructor
//*---------------------------------------------------------------------------*
DIRayCollider::DIRayCollider()
//*---------------------------------------------------------------------------*
{
}
// Destructor
//*---------------------------------------------------------------------------*
DIRayCollider::~DIRayCollider()
//*---------------------------------------------------------------------------*
{
}
// DIRayCollider.Init
//*---------------------------------------------------------------------------*
void DIRayCollider::Init(BaseObject* goal)
//*---------------------------------------------------------------------------*
{
PolygonObject* pobj = (PolygonObject* )goal;
#ifdef C4D_R11
points = pobj->GetPointW();
poly = pobj->GetPolygonW();
#else
points = pobj->GetPoint();
poly = pobj->GetPolygon();
#endif
lastPoly = poly + pobj->GetPolygonCount();
gmat = pobj->GetMg();
}
// DIRayCollider.Intersect
// - Returns the nearest distance intersection
//*---------------------------------------------------------------------------*
Bool DIRayCollider::Intersect(const Vector& ray_p0, const Vector& ray_p1, Real* distance)
//*---------------------------------------------------------------------------*
{
p0 = LVector(ray_p0.x, ray_p0.y, ray_p0.z);
p1 = LVector(ray_p1.x, ray_p1.y, ray_p1.z);
*distance = MAXREAL;
UCHAR res;
Bool intersection = FALSE;
Real dist;
// Get intersections, if any, and retain nearest
for (CPolygon* p = poly; p != lastPoly; ++p)
{
v0 = gmat*points[p->a];
v1 = gmat*points[p->b];
v2 = gmat*points[p->c];
res = intersect_RayTriangle(LVector(v0.x, v0.y, v0.z), LVector(v1.x, v1.y, v1.z), LVector(v2.x, v2.y, v2.z));
if (res < 1) continue;
if (res == 1)
{
intersection = TRUE;
dist = LDistance(p0, hitpos);
if (dist < *distance) *distance = dist;
}
else if (res == 2)
{
*distance = 0.0f;
return TRUE;
}
}
return intersection;
}
// DIRayCollider.Intersect
// anything that avoids division overflow
#define SMALL_NUM 0.00000001f
//*---------------------------------------------------------------------------*
CHAR DIRayCollider::intersect_RayTriangle(const LVector& lv0, const LVector& lv1, const LVector& lv2)
//*---------------------------------------------------------------------------*
{
LVector u, v, n; // triangle vectors
// get triangle edge vectors and plane normal
u = lv1 - lv0;
v = lv2 - lv0;
n = u % v; // cross product
// triangle is degenerate
if (n == (LVector)0)
return -1; // do not deal with this case
LVector dir, w0; // ray vectors
dir = p1 - p0; // ray direction vector
w0 = p0 - lv0;
LReal a, b; // params to calc ray-plane intersect
a = -(n * w0);
b = n * dir;
// ray is parallel to triangle plane
if (fabs(b) < SMALL_NUM)
{
// ray lies in triangle plane
if (a == 0) return 2;
// ray disjoint from plane
else return 0;
}
// get intersect point of ray with triangle plane
LReal r;
r = a / b;
// ray goes away from triangle
if (r < 0.0) return 0; // => no intersect
// for a segment, also test if (r > 1.0) => no intersect
// intersect point of ray and plane
hitpos = p0 + r * dir;
// is I inside T?
LVector w;
LReal uu, uv, vv, wu, wv, D;
uu = u * u;
uv = u * v;
vv = v * v;
w = hitpos - lv0;
wu = w * u;
wv = w * v;
D = 1.0 / (uv * uv - uu * vv);
// get and test parametric coords
a = (uv * wv - vv * wu) * D;
// I is outside T
if ((a < 0.0) || (a > 1.0)) return 0;
b = (uv * wu - uu * wv) * D;
// I is outside T
if ((b < 0.0) || ((a + b) > 1.0)) return 0;
// I is in T
return 1;
}
// Static Allocator
//*---------------------------------------------------------------------------*
DIRayCollider* DIRayCollider::Alloc()
//*---------------------------------------------------------------------------*
{
return gNew DIRayCollider;
}
// Static Deallocator
//*---------------------------------------------------------------------------*
void DIRayCollider::Free(DIRayCollider*& data)
//*---------------------------------------------------------------------------*
{
gDelete(data);
}
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 12:04, xxxxxxxx wrote:
awesome.. you are the man. Thanks again.
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 16:13, xxxxxxxx wrote:
Hey Robert, I am trying to build an example based on the code you provided. All is going well except I notice you include "general.h" in your code.
I am assuming that in the line:
dist = LDistance(p0, hitpos);
LDistance is defined in general.h?
would you mind telling me what LDistance is defined as?
Can this be replaced with Len(p-p)?
Thanks a lot.
~Shawn
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 16:58, xxxxxxxx wrote:
Sorry about that. It is just a 3D point-point distance calculation:
// Return Real distance between two LVectors
//*---------------------------------------------------------------------------*
Real LDistance(LVector v1, LVector v2)
//*---------------------------------------------------------------------------*
{
Real x;
Real y;
Real z;
x = v2.x - v1.x;
y = v2.y - v1.y;
z = v2.z - v1.z;
return (Real)Sqrt((x*x) + (y*y) + (z*z));
}
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 17:07, xxxxxxxx wrote:
So if I want to check if a point has intersected with the triangle I call intersect_RayTriangle
and pass it the points of the triangle in question?
~Shawn
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 17:31, xxxxxxxx wrote:
My routines are set to be initiated with a polygon object to test against but you can certainly alter it to take a point instead. In your case, I'd alter it to take the point and send the polygon object's triangles one at a time in which you want to test. Lemme see if I can attach the appropriate source file to a message.
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 17:45, xxxxxxxx wrote:
Great.. that will help a lot. Thanks again Robert.
~Shawn
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 17:54, xxxxxxxx wrote:
I have one more question.
So the first step is to call init(MyObjectThatThepoint will collide with)?
Then I want to call Intersection () and pass it the point and the vector that determines the ray, what is the distance variable?
and by calling Intersection, that then calls intersect_RayTriangle to see if the intersection has happened?
and then returns the bool as to whether it has happened or not?
thanks,
Shawn
so that intersection can then call
THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 19/05/2010 at 19:06, xxxxxxxx wrote:
Yes.
Yes.
Distance is what is returned. In my case, I'm seeking intersection of two objects so the distance counts. In your case, you should be looking to see whether 'penetration' exists - the point is inside the object.
Yes.
Yes.