Object boundries.

Helper

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.

Helper

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

Helper

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

Helper

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);  
}

Helper

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.

Helper

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

Helper

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));  
}

Helper

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

Helper

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.

Helper

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

Helper

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

Helper

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.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 19/05/2010 at 19:16, xxxxxxxx wrote:

lol.. thanks.. I guess 1 question turned in to 5.. HAHA

~Shawn