Am I inside a volume? (without colliders)

Question

Hey guys!

Interesting, can one tell if a point in space is inside a given mesh without any kind of colliders? It get's harder once it's not a cube, but for example a pyramid, especially if we are using the x-y-z coordinate-bound approach, comparing all 3 coordinate components of vertexes against ours.

Can I use c# to actually see that my position is inside a specified volume using some function?

Many thanks!

Answer 1

Best Answer

Answer by Bunny83 · Jan 08, 2014 at 07:48 PM

It's quite simple but you have to iterate over all triangles of course. Also it the volume isn't closed you might get wrong results since the volume doesn't have a clear boundary.

All you have to do is check if the point is behind all plane which are defined by all triangles.

You can use Unity's Plane class for this:

 //C#
 public static class MeshExtension
 {
     public static bool IsPointInside(this Mesh aMesh, Vector3 aLocalPoint)
     {
         var verts = aMesh.vertices;
         var tris = aMesh.triangles;
         int triangleCount = tris.Length / 3;
         for (int i = 0; i < triangleCount; i++)
         {
             var V1 = verts[ tris[ i*3     ] ];
             var V2 = verts[ tris[ i*3 + 1 ] ];
             var V3 = verts[ tris[ i*3 + 2 ] ];
             var P = new Plane(V1,V2,V3);
             if (P.GetSide(aLocalPoint))
                 return false;
         }
         return true;
     }
 }

The documentation of GetSide is not very clear, so you might have to invert the result ( if (!P.GetSide(aLocalPoint)) )

To use this extension method, just put this class somewhere in your project and use it like this:

 if (someMesh.IsPointInside(meshTransform.InverseTransformPoint(yourPoint)))
     // "yourPoint" is inside "someMesh".

edit
important: This method only works for convex meshes! Concave meshes aren't that easy.

Add comment · Show 2 · Share

IgorAherne · Jan 08, 2014 at 09:23 PM 0

Share

damn, I need convex ones as well ! :<

Bunny83 · Jan 08, 2014 at 09:39 PM 0

Share

I guess you mean concave, right?

In that case i would suggest to implement your own raycasting solution which checks the intersection with each triangle manually and implement the raycasting algorithm. This works the same for 3d. This is basically what the above mentioned algorithm does optimised for 2d, however it's way more complicated for 3d.

Answer 2

Here is a fast method to find whether a point is within the bounding sphere of a mesh. I have made this as an extension method to the Mesh class.

 using System;
 using UnityEngine;
 
 public static class MeshExtension
 {
     public static bool PointIsWithinBoundingSphere(this Mesh mesh, Vector3 point)
     {
         if (!mesh.bounds.Contains(point))
             return false;
         
         // Get the point relative to the mesh center.
         var p = point - mesh.bounds.center;
         Func<float, float> getSide = vector => vector < 0f ? -1f : 1f;
         var sideFlip = new Vector3(getSide(p.x), getSide(p.y), getSide(p.z));
         float pointDist = p.sqrMagnitude;
         foreach (var vert in mesh.vertices)
         {
             // Get the vertice relative to the mesh center.
             var v = vert - mesh.bounds.center;
             // Is vertice on other side of mesh center than the target point?
             if (v.x * sideFlip.x < 0f || v.y * sideFlip.y < 0f || v.z * sideFlip.z < 0f)
                 continue;
             float vectorDist = v.sqrMagnitude;
             if (vectorDist > pointDist)
                 return true;
         }
         return false;
     }
 }

If the point is found to be within the bounding sphere, you can then use this much more accurate but vastly slower method to find if the point is within the mesh.

 using System;
 using UnityEngine;
 
 public static class MeshExtension
 {
     /// <summary>
     /// Decide whether a point is within a mesh, in a good yet simplistic way.
     /// It works best with convex meshes, whereas a concave mesh is simply
     /// treated as a convex mesh and so it will not be totally exact.
     /// (For a torus/donut mesh it will be like it didn't have a hole.)
     /// </summary>
     public static bool PointIsWithin(this Mesh mesh, Vector3 point)
     {
         Vector3 p = point - mesh.bounds.center;
         
         for (int i = 0; i < mesh.vertices.Length; i += 3)
         {
             Vector3 a = mesh.vertices[i] - mesh.bounds.center;
             Vector3 b = mesh.vertices[i + 1] - mesh.bounds.center;
             Vector3 c = mesh.vertices[i + 2] - mesh.bounds.center;
             if (RayWithinTriangle(p, a, b, c))
                 return true;
         }
         return false;
     }

     /// <summary>
     /// Radiate out from the origin through the given point to see whether
     /// the ray would hit the triangle and the point is closer to the origin than the triangle.
     /// The triangle is specified by v0, v1 and v2.
     /// </summary>
     private static bool RayWithinTriangle(Vector3 point, Vector3 v0, Vector3 v1, Vector3 v2)
     {
         Vector3 intersectionPoint;
         if (RayIntersectsTriangle(point, v0, v1, v2, out intersectionPoint))
         {
             float pointDist = point.sqrMagnitude;
             float intersectionDist = intersectionPoint.sqrMagnitude;
             return (pointDist < intersectionDist);
         }
         return false;
     }
     
     /// <summary>
     /// Radiate out from the origin through the given point to see whether
     /// the ray would hit the triangle.
     /// The triangle is specified by v0, v1 and v2.
     /// </summary>
     private static bool RayIntersectsTriangle(Vector3 direction, Vector3 v0, Vector3 v1, Vector3 v2, out Vector3 intersectionPoint)
     {
         intersectionPoint = new Vector3();
         
         Vector3 e1 = v1 - v0;
         Vector3 e2 = v2 - v0;
         
         Vector3 h = Vector3.Cross(direction, e2);
         float a = Vector3.Dot(e1, h);
         
         if (a > -0.00001 && a < 0.00001)
             return false;
         
         float f = 1 / a;
         Vector3 s = Vector3.zero - v0;
         float u = f * Vector3.Dot(s, h);
         
         if (u < 0.0 || u > 1.0)
             return false;
         
         Vector3 q = Vector3.Cross(s, e1);
         float v = f * Vector3.Dot(direction, q);
         
         if (v < 0.0 || u + v > 1.0)
             return false;
         
         // At this stage we can compute t to find out where
         // the intersection point is on the line.
         float t = f * Vector3.Dot(e2, q);
         
         if (t > 0.00001) // ray intersection
         {
             intersectionPoint[0] = direction[0] * t;
             intersectionPoint[1] = direction[1] * t;
             intersectionPoint[2] = direction[2] * t;
             return true;
         }
         
         // At this point there is a line intersection
         // but not a ray intersection.
         return false;
     }
 }

The RayIntersectsTriangle method was taken from this site:

http://www.lighthouse3d.com/tutorials/maths/ray-triangle-intersection/

Answer 3

Answer by yoonitee · Jun 12, 2016 at 04:38 AM

Actually its not too hard. Here's the pseudo code:

Set N=0; For each triangle form tetrahedron with one point at the origin. If point is in this tetrahedron N++;

If at the end N%2==1 then the point is inside the mesh.

Now, to test if a point is inside a tetrahedron requires testing if it is within 4 planes.

Add comment · Share

Am I inside a volume? (without colliders)

3 Replies

Your answer

Follow this Question

Related Questions