Your browser does not seem to support JavaScript. As a result, your viewing experience will be diminished, and you have been placed in read-only mode.
Please download a browser that supports JavaScript, or enable it if it's disabled (i.e. NoScript).
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
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.
On 19/05/2010 at 06:25, xxxxxxxx wrote:
great .. thanks for the info robert. Nice to see you again!
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
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); }
On 19/05/2010 at 12:04, xxxxxxxx wrote:
awesome.. you are the man. Thanks again.
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.
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)); }
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?
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.
On 19/05/2010 at 17:45, xxxxxxxx wrote:
Great.. that will help a lot. Thanks again Robert.
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
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.
On 19/05/2010 at 19:16, xxxxxxxx wrote:
lol.. thanks.. I guess 1 question turned in to 5.. HAHA