Page 1 of 1

ConvexShape point testing

Posted: Tue Jun 25, 2013 7:02 pm
by Earthmark
I am attempting to find out if a point lies inside or outside of a given ConvexShape, however I can't seem to find a good method for doing it.

A few methods I can think of but can't find a good test case:
A RayTest from inside the shape, if that test returns true if it is inside (length of zero would be used then).
Using GetExtremePoint, but I am confused as to what kind of direction vector (is it a unit pointing out from the center, or a world position representing the point to test towards).

If you have done this, or have any ideas please do help.

Re: ConvexShape point testing

Posted: Tue Jun 25, 2013 7:22 pm
by Norbo
A RayTest from inside the shape, if that test returns true if it is inside (length of zero would be used then).
A ray test can indeed be used, and it would be a pretty effective method of checking containment. It would make use of per-shape special cases which would be beneficial for performance. The test would look like this:

Code: Select all

        public bool IsPointInShape(Vector3 pointToTestForContainment, ConvexShape convexShape, RigidTransform shapeTransform)
        {
            //Send a ray from the point to test to the center of the shape.
            Ray ray = new Ray(pointToTestForContainment, shapeTransform.Position - pointToTestForContainment);
            RayHit hit;
            if (convexShape.RayTest(ref ray, ref shapeTransform, 1, out hit))
            {
                //While ray test should always return true by construction, it's still wrapped in a protective if to avoid numerical corner cases.

                //If the hit T is 0, then we're inside the shape; otherwise, we're outside the shape:
                return hit.T == 0;
            }
            return false;
        }
There are also some general helpers which can do something similar. For example:

Code: Select all

         RigidTransform.TransformByInverse(ref pointToTestForContainment, ref shapeTransform, out localPoint);
            return MPRToolbox.SweptShapeContainsPoint(shape, ref Toolbox.ZeroVector, ref localPoint);
This one will resort to using MPR for all shape types, though. That may not be optimal for simpler shapes like Sphere or Box which have very direct special case ray tests.
Using GetExtremePoint, but I am confused as to what kind of direction vector (is it a unit pointing out from the center, or a world position representing the point to test towards).
The GetExtremePoint function takes a direction, not a point to test towards. However, a single call to GetExtremePoint is not guaranteed to tell you that the point is in the shape. You would actually need to implement some searching algorithm. GetExtremePoint is used in such algorithms- MPR and GJK, specifically.


Another option would be to create a tiny/zero-radius SphereShape to represent the point. Then, you could call a relevant MPRToolbox or GJKToolbox function for boolean testing. However, you once again lose special case support.

For simplicity and capacity for speed, I would recommend just going with the first RayTest approach.

Edit: I didn't actually run, compile, or really thoroughly proofread the above code snippets; beware of typos :)

Re: ConvexShape point testing

Posted: Tue Jun 25, 2013 8:34 pm
by Earthmark
Thank you.