Object boundries.



  • 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.



  • 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


Log in to reply