Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

A solution for accurate raycasting without mesh colliders

Discussion in 'Scripting' started by gvaughan, May 2, 2012.

  1. gvaughan

    gvaughan

    Joined:
    Jan 28, 2010
    Posts:
    32
    I ran into a problem with how Unity implements raycasting recently while developing an interactive anatomy browser.

    Our model consists of about 600 individual meshes, with a total of around 350,000 triangles. The physics system took about 1.5 minutes to load these colliders on the iPad2, making our loading time skyrocket to a point where users became fed up. These meshes are completely layered on each other and penetrating (which may have been part of the problem)

    In most other situations we could just approximate the shape using primitives, but this just wouldn't work because we need the high fidelity that the mesh colliders offer. We also tried reducing the poly count on a separate set of collider meshes, but this took a huge toll on memory. So instead, I i spent a week and implemented a new raycasting method that provides 100% accurate object clicking and uses no colliders. In doing so I was able to get the load time of the scene down to about 30 seconds from the minute and a half of the built in system, and still get the results I need.

    Here's what it does:

    Build an object dictionary that holds all of the scene's gameObjects and the triangles they're comprised of.
    Sort these triangles into an octree
    Raycast through the tree grabbing the triangles contained in the bounds which the ray passes
    Check if the ray passes through these triangles
    Return the triangle/object back.

    Here are the classes:

    APAObjectDictionary.cs
    This holds the instance of the octree, builds, and populates that tree.
    Code (csharp):
    1.  
    2. public class APAObjectDictionary : MonoBehaviour {
    3.     public APAOctree octree;
    4.     public static APAObjectDictionary singleton;
    5.     private int octreeDepth = 3;
    6.     private int objectsPerChunk = 1000;
    7.     public delegate void CallbackMethod();
    8.    
    9.     void Awake(){
    10.         singleton = this;  
    11.     }
    12.    
    13.     public void Init (CallbackMethod del, Bounds bounds)
    14.     {      
    15.         octree = new APAOctree(bounds, octreeDepth);   
    16.         StartCoroutine(PopulateOctree (del));      
    17.     }
    18.    
    19.     IEnumerator PopulateOctree (CallbackMethod del)
    20.     {
    21.         GameObject[] gameObjects = GameObject.FindObjectsOfType (typeof(GameObject)) as GameObject[];
    22.        
    23.         GameObject curGO;
    24.         Triangle[] curTris = new Triangle[] {};
    25.         MeshFilter curMeshFilter = null;
    26.         APAOctree finalNode;
    27.         for (int i = 0; i < gameObjects.Length; i++) {
    28.             curGO = gameObjects [i];
    29.             if (curGO == null) continue;
    30.             curMeshFilter = curGO.GetComponent<MeshFilter>();
    31.             if (!curMeshFilter) continue;
    32.             curTris = new Triangle[] {};
    33.             curTris = GetTriangles(curGO);
    34.             for (int k = 0; k < curTris.Length; k++){
    35.                 finalNode = octree.IndexTriangle(curTris[k]);
    36.                 finalNode.AddTriangle(curTris[k]); 
    37.             }
    38.            
    39.             if (i % objectsPerChunk == 1){
    40.                 yield return 0;
    41.             }
    42.         }
    43.        
    44.         del();
    45.         Debug.Log("Created Database");
    46.         Debug.Log("Total Indexed Triangles: " + GetTriangleCount(octree));
    47.    
    48.     }
    49.    
    50.     int GetTriangleCount(APAOctree o){
    51.         int count = 0;
    52.         count = o.triangles.Count;
    53.         foreach(APAOctree oct in o.m_children){
    54.             count += GetTriangleCount(oct) ;
    55.         }
    56.         return count;
    57.     }
    58.  
    59.     Triangle[] GetTriangles(GameObject go){
    60.         Mesh mesh = go.GetComponent<MeshFilter>().sharedMesh;
    61.         int[] vIndex = mesh.triangles;
    62.         Vector3[] verts = mesh.vertices;
    63.         Vector2[] uvs = mesh.uv;
    64.         List<Triangle> triangleList = new List<Triangle>();
    65.         int i = 0;
    66.         while (i < vIndex.Length){
    67.             triangleList.Add(
    68.                 new Triangle(
    69.                 verts[vIndex[i + 0]],
    70.                 verts[vIndex[i + 1]],
    71.                 verts[vIndex[i + 2]],
    72.                 uvs[vIndex[i + 0]],
    73.                 uvs[vIndex[i + 1]],
    74.                 uvs[vIndex[i + 2]],
    75.                 go.transform));
    76.             i += 3;
    77.         }
    78.         return triangleList.ToArray();
    79.     }
    80.        
    81.     void OnDrawGizmos(){
    82.         DrawOctree(octree);
    83.     }
    84.    
    85.     //This is slow and really not necessary, just a nice visual
    86.     void DrawOctree(APAOctree oct){
    87.         Gizmos.DrawWireCube(oct.bounds.center, oct.bounds.size);
    88.        
    89.         foreach(APAOctree o in oct.m_children){
    90.             DrawOctree(o); 
    91.         }
    92.     }
    93.    
    94.     public static APAOctree GetOctree(){
    95.         return singleton.octree;
    96.     }
    97.    
    98.     //Get an approximation of memory usage out of the garbage collector while purposely clearing out the tree
    99.     void OnDestroy(){
    100.         Debug.Log("Mem Before Clear: " + System.GC.GetTotalMemory(true) / 1024f / 1024f);
    101.         octree.Clear();
    102.         octree = null;
    103.         Destroy(singleton);
    104.         Debug.Log("Mem After Clear: " + System.GC.GetTotalMemory(true) / 1024f / 1024f);
    105.     }
    106. }
    107.  
    APAOctree.cs
    This is the tree itself. Normally, octrees and kdtrees (anything like that) hold a single point. However, I need to know if the tree node holds an entire triangle, not just one of it's verts. We start with the largest box and test each triangle fits in it, and if so, checks its children, etc.
    Code (csharp):
    1.  
    2. public class APAOctree {
    3.     public List<APAOctree> m_children;
    4.     public APAOctree parent;
    5.     public Bounds bounds;
    6.     public List<Triangle> triangles;
    7.    
    8.     public APAOctree(){
    9.         this.m_children = new List<APAOctree>();
    10.         this.triangles = new List<Triangle>();
    11.         this.parent = null;
    12.     }
    13.     public APAOctree(Bounds parentBounds, int generations){
    14.         this.bounds = parentBounds;
    15.         this.m_children = new List<APAOctree>();
    16.         this.triangles = new List<Triangle>();
    17.         this.parent = null;
    18.         CreateChildren(this, generations);
    19.     }
    20.    
    21.     protected void CreateChildren(APAOctree parent, int generations){
    22.         m_children = new List<APAOctree>();
    23.         Vector3 c = parent.bounds.center;
    24.         float u = parent.bounds.extents.x * 0.5f;
    25.         float v = parent.bounds.extents.y * 0.5f;
    26.         float w = parent.bounds.extents.z * 0.5f;
    27.         Vector3 childrenSize = parent.bounds.extents;
    28.         Vector3[] childrenCenters = {
    29.             new Vector3(c.x + u, c.y + v, c.z + w),
    30.             new Vector3(c.x + u, c.y + v, c.z - w),
    31.             new Vector3(c.x + u, c.y - v, c.z + w),
    32.             new Vector3(c.x + u, c.y - v, c.z - w),
    33.             new Vector3(c.x - u, c.y + v, c.z + w),
    34.             new Vector3(c.x - u, c.y + v, c.z - w),
    35.             new Vector3(c.x - u, c.y - v, c.z + w),
    36.             new Vector3(c.x - u, c.y - v, c.z - w)
    37.         };
    38.        
    39.         for (int i = 0; i < childrenCenters.Length; i++){
    40.             APAOctree o = new APAOctree();
    41.             o.parent = parent;
    42.             o.bounds = new Bounds(childrenCenters[i], childrenSize);
    43.             m_children.Add(o);
    44.             if (generations > 0){
    45.                 o.CreateChildren(o, generations - 1);
    46.             }
    47.         }
    48.     }
    49.    
    50.    
    51.     public APAOctree IndexTriangle(Triangle triangle){
    52.         return IndexTriangle(this, triangle);  
    53.     }
    54.    
    55.     //SOMETHING INTERESTING:
    56.     //This function is further proof that for loops are significantly faster than foreach.  Before switching to foreach, this
    57.     //function took approximately 270 seconds (on my machine, not the ipad) for 350,000 tris.  It now takes about 15 (still slow, but better)
    58.     public APAOctree IndexTriangle(APAOctree parentNode, Triangle triangle){
    59.         APAOctree finalNode = parentNode;
    60.         if (this.ContainsTriangle(triangle)){
    61.             finalNode = this;
    62.             for (int i = 0; i < m_children.Count; i++){
    63.                 finalNode = m_children[i].IndexTriangle(this, triangle);
    64.                 if (finalNode != this) return finalNode;
    65.             }
    66.             return finalNode;
    67.         }
    68.         return finalNode;
    69.     }
    70.    
    71.     public bool AddTriangle(Triangle t){
    72.         triangles.Add(t);
    73.         return true;
    74.     }
    75.    
    76.     public bool ContainsTriangle(Triangle triangle){
    77.         return  bounds.Contains(triangle.pt0)
    78.                 bounds.Contains(triangle.pt1)  
    79.                 bounds.Contains(triangle.pt2);
    80.     }
    81.    
    82.     public void Clear(){
    83.         int total = ClearOctree(this);
    84.         Debug.Log("Total Nodes Cleared: " + total);
    85.     }
    86.    
    87.     protected int ClearOctree(APAOctree o){
    88.         int count = 0;
    89.         for (int i = 0; i < o.m_children.Count; i++){
    90.             count += ClearOctree(o.m_children[i]);
    91.         }
    92.         o.triangles.Clear();
    93.         o.triangles.TrimExcess();
    94.         o.parent = null;
    95.         o.m_children.Clear();
    96.         o.m_children.TrimExcess();
    97.         count ++;
    98.         return count;
    99.     }
    100.  
    101. }
    102.  
    APARaycast.cs
    Here I tried to emulate unity's RaycastHit class as close as possible to slip the new classes into the existing code.
    Code (csharp):
    1.  
    2. public class APARaycastHit{
    3.     public float distance;
    4.     public Transform transform;
    5.     public Vector2 barycentricCoordinate;
    6.     public Vector2 textureCoord;
    7.     public Vector3 point;
    8.    
    9.     public APARaycastHit(){
    10.         this.distance = 0f;
    11.         this.transform = null;
    12.         this.textureCoord = Vector2.zero;
    13.         this.barycentricCoordinate = Vector2.zero;
    14.         this.point = Vector3.zero;
    15.     }
    16.    
    17.     public APARaycastHit(Transform transform, float distance, Vector2 barycentricCoordinate){
    18.         this.distance = distance;
    19.         this.transform = transform;
    20.         this.barycentricCoordinate = barycentricCoordinate;
    21.         this.textureCoord = Vector2.zero;
    22.         this.point = Vector3.zero;
    23.     }
    24. }
    This class then does the raycasting, sorting of hits, and intersection testing
    Code (csharp):
    1.  
    2. public class APARaycast : MonoBehaviour {
    3.    
    4.     static Vector3 edge1 = new Vector3();
    5.     static Vector3 edge2 = new Vector3();
    6.     static Vector3 tVec = new Vector3();
    7.     static Vector3 pVec = new Vector3();
    8.     static Vector3 qVec = new Vector3();
    9.    
    10.     static float det = 0;
    11.     static float invDet = 0;
    12.     static float u = 0;
    13.     static float v = 0;
    14.    
    15.     static float epsilon = 0.0001f;
    16.    
    17.     static System.Diagnostics.Stopwatch stopWatch;
    18.    
    19.     public static bool Raycast (Ray ray, out APARaycastHit hit)
    20.     {  
    21.         hit = new APARaycastHit();
    22.         List<APARaycastHit> hits = new List<APARaycastHit>();
    23.    
    24.         hits = INTERNAL_RaycastAll(ray);
    25.        
    26.         hits = SortResults(hits);
    27.         if (hits.Count > 0){
    28.             hit = hits[0];
    29.             return true;
    30.         }
    31.         return false;
    32.     }
    33.    
    34.     public static APARaycastHit[] RaycastAll(Ray ray)
    35.     {
    36.         return INTERNAL_RaycastAll(ray).ToArray();
    37.     }
    38.    
    39.     public static APARaycastHit[] RaycastAll(Ray ray, float dist, LayerMask mask){
    40.         List<APARaycastHit> hits = INTERNAL_RaycastAll(ray);
    41.         for (int i = 0; i < hits.Count; i++){
    42.             if (hits[i].distance > dist) hits.RemoveAt(i);
    43.             if ((1 << hits[i].transform.gameObject.layer  mask.value) != 1 << hits[i].transform.gameObject.layer){
    44.                 hits.RemoveAt(i);
    45.             }
    46.         }
    47.         return hits.ToArray();
    48.     }
    49.    
    50.     static List<APARaycastHit> INTERNAL_RaycastAll(Ray ray)
    51.     {
    52.        
    53.         stopWatch = new System.Diagnostics.Stopwatch();
    54.         stopWatch.Start();
    55.         List<APARaycastHit> hits = new List<APARaycastHit>();
    56.         APAOctree octree = APAObjectDictionary.GetOctree();
    57.        
    58.         if (octree.bounds.IntersectRay(ray)){
    59.             hits = RecurseOctreeBounds(octree, ray);   
    60.         }
    61.        
    62.         hits = SortResults(hits);
    63.         stopWatch.Stop();
    64.         Debug.Log("Search Time: " + stopWatch.ElapsedMilliseconds + " ms");
    65.         return hits;
    66.     }
    67.    
    68.     static bool INTERNAL_Raycast (Ray ray, out APARaycastHit hit)
    69.     {  
    70.         hit = new APARaycastHit();
    71.         List<APARaycastHit> hits = new List<APARaycastHit>();
    72.    
    73.         APAOctree octree = APAObjectDictionary.GetOctree();
    74.        
    75.         if (octree.bounds.IntersectRay(ray)){
    76.             hits = RecurseOctreeBounds(octree, ray);   
    77.         }
    78.        
    79.         hits = SortResults(hits);
    80.         if (hits.Count > 0){
    81.             hit = hits[0]; 
    82.         }
    83.         return hits.Count > 0;
    84.     }
    85.    
    86.     static List<APARaycastHit> RecurseOctreeBounds(APAOctree octree, Ray ray){
    87.         List<APARaycastHit> hits = new List<APARaycastHit>();
    88.         float dist = 0f;
    89.         Vector2 baryCoord = new Vector2();
    90.         for (int i = 0; i < octree.m_children.Count; i++){
    91.             if (octree.m_children[i].bounds.IntersectRay(ray)){
    92.                 for (int k = 0; k < octree.m_children[i].triangles.Count; k++){
    93.                     if (TestIntersection(octree.m_children[i].triangles[k], ray, out dist, out baryCoord)){
    94.                         hits.Add(BuildRaycastHit(octree.m_children[i].triangles[k], dist, baryCoord));
    95.                     }
    96.                 }
    97.                 hits.AddRange(RecurseOctreeBounds(octree.m_children[i], ray)); 
    98.             }
    99.         }
    100.         return hits;
    101.     }
    102.    
    103.     static APARaycastHit BuildRaycastHit(Triangle hitTriangle, float distance, Vector2 barycentricCoordinate){
    104.         APARaycastHit returnedHit = new APARaycastHit(hitTriangle.trans, distance, barycentricCoordinate);
    105.         returnedHit.textureCoord = hitTriangle.uv_pt0 + ((hitTriangle.uv_pt1 - hitTriangle.uv_pt0) * barycentricCoordinate.x) + ((hitTriangle.uv_pt2 - hitTriangle.uv_pt0) * barycentricCoordinate.y);
    106.  
    107. //HACK:  Below only returns the center of the hit triangle.  A close approximate, but not accurate.  
    108.         returnedHit.point = hitTriangle.trans.position + (hitTriangle.pt0 + hitTriangle.pt1 + hitTriangle.pt2) / 3;
    109.         return returnedHit;
    110.        
    111.     }
    112.    
    113.     /// <summary>
    114.     /// Tests the intersection.
    115.     /// Implementation of the Moller/Trumbore intersection algorithm
    116.     /// </summary>
    117.     /// <returns>
    118.     /// Bool if the ray does intersect
    119.     /// out dist - the distance along the ray at the intersection point
    120.     /// out hitPoint -
    121.     /// </returns>
    122.     /// <param name='triangle'>
    123.     /// If set to <c>true</c> triangle.
    124.     /// </param>
    125.     /// <param name='ray'>
    126.     /// If set to <c>true</c> ray.
    127.     /// </param>
    128.     /// <param name='dist'>
    129.     /// If set to <c>true</c> dist.
    130.     /// </param>
    131.     /// <param name='baryCoord'>
    132.     /// If set to <c>true</c> barycentric coordinate of the intersection point.
    133.     /// </param>
    134.     /// http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf
    135.     static bool TestIntersection(Triangle triangle, Ray ray, out float dist, out Vector2 baryCoord){
    136.         baryCoord = Vector2.zero;
    137.         dist = Mathf.Infinity;
    138.         edge1 = triangle.pt1 - triangle.pt0;
    139.         edge2 = triangle.pt2 - triangle.pt0;
    140.        
    141.         pVec = Vector3.Cross (ray.direction, edge2);
    142.         det = Vector3.Dot ( edge1, pVec);
    143.         if (det < epsilon) {
    144.             return false;  
    145.         }
    146.         tVec = ray.origin - triangle.pt0;
    147.         u = Vector3.Dot (tVec, pVec);
    148.         if (u < 0 || u > det) {
    149.             return false;  
    150.         }
    151.         qVec = Vector3.Cross (tVec, edge1);
    152.         v = Vector3.Dot (ray.direction, qVec);
    153.         if (v < 0 || u + v > det) {
    154.             return false;  
    155.         }
    156.         dist = Vector3.Dot(edge2, qVec);
    157.         invDet = 1 / det;
    158.         dist *= invDet;
    159.         baryCoord.x = u * invDet;
    160.         baryCoord.y = v * invDet;
    161.         return true;
    162.     }
    163.    
    164.     static List<APARaycastHit> SortResults(List<APARaycastHit> input){
    165.        
    166.         APARaycastHit a = new APARaycastHit();
    167.         APARaycastHit b = new APARaycastHit();
    168.         bool swapped = true;
    169.         while (swapped){
    170.             swapped = false;
    171.             for(int i = 1; i < input.Count; i++){
    172.                 if (input[i-1].distance > input[i].distance){
    173.                     a = input[i-1];
    174.                     b = input[i];
    175.                     input[i-1] = b;
    176.                     input[i] = a;
    177.                     swapped = true;
    178.                 }
    179.             }
    180.         }
    181.        
    182.         return input;
    183.     }
    184.    
    185.  
    186. }
    187.  
    Triangle.cs
    This is just to hold the triangle information.
    Code (csharp):
    1.  
    2. public class Triangle
    3. {
    4.     public Vector3 pt0;
    5.     public Vector3 pt1;
    6.     public Vector3 pt2;
    7.    
    8.     public Vector2 uv_pt0;
    9.     public Vector2 uv_pt1;
    10.     public Vector2 uv_pt2;
    11.     public Transform trans;
    12.    
    13.     public Triangle (Vector3 pt0, Vector3 pt1, Vector3 pt2, Vector2 uv_pt0, Vector2 uv_pt1, Vector2 uv_pt2, Transform trans)
    14.     {
    15.         this.pt0 = pt0;
    16.         this.pt1 = pt1;
    17.         this.pt2 = pt2;
    18.         this.uv_pt0 = uv_pt0;
    19.         this.uv_pt1 = uv_pt1;
    20.         this.uv_pt2 = uv_pt2;
    21.         this.trans = trans;
    22.         UpdateVerts();
    23.     }
    24.    
    25.     public void UpdateVerts(){
    26.         pt0 = trans.TransformPoint(pt0);
    27.         pt1 = trans.TransformPoint(pt1);
    28.         pt2 = trans.TransformPoint(pt2);
    29.     }
    30. }
    31.  
    Problems:
    Yes, this is still slow, and it doesn't work for all use cases - but it did work for us. One major fault is that there is currently no functionality to update the octree if an object moves. This wasn't an issue for our project as the model is static and only the camera moves.

    There is room for improvement, but I know this has been a problem for others and I though I'd share. I've attached a project showing it in use. The public bool useStandardColliders on the ColliderTest object switches between the internal and replaced raycast. Please note that these snippets are covered by the MIT license (job stuff).

    I hope you find it useful.
     

    Attached Files:

    luizero00, NotaNaN, dimtreo and 3 others like this.
  2. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
  3. greay

    greay

    Joined:
    Mar 23, 2011
    Posts:
    88
    Seriously, thank you so much for this.
     
  4. JeanSimonet

    JeanSimonet

    Joined:
    Nov 23, 2012
    Posts:
    31
    I ran across the same problem recently, and used this solution to solve my problem. Thanks a lot!
    I did have the chance to optimize the code a bit, mainly with the IndexTriangle() method, so I thought I'd share the updated code. The optimization takes advantage of the fact that once you know the bounds of a triangle, you can almost immediately know which subnode of the octree it will fit in. That is: if the triangle crosses any of the mid-planes of the current node, then it won't fit in a child node, but if it doesn't, then which side of each mid-plane it sits on will tell you what child to test next. See code below.
    In my test it cut the indexing time by 3.

    Code (csharp):
    1.  
    2. public APAOctree IndexTriangle(APAOctree parentNode, Triangle triangle) {
    3.  
    4.     // Compute triangle bounds (not using the param version of Mathf.Min() to avoid array allocation)
    5.     float minX = Mathf.Min(triangle.pt0.x, Mathf.Min(triangle.pt1.x, triangle.pt2.x));
    6.     float minY = Mathf.Min(triangle.pt0.y, Mathf.Min(triangle.pt1.y, triangle.pt2.y));
    7.     float minZ = Mathf.Min(triangle.pt0.z, Mathf.Min(triangle.pt1.z, triangle.pt2.z));
    8.  
    9.     float maxX = Mathf.Max(triangle.pt0.x, Mathf.Max(triangle.pt1.x, triangle.pt2.x));
    10.     float maxY = Mathf.Max(triangle.pt0.y, Mathf.Max(triangle.pt1.y, triangle.pt2.y));
    11.     float maxZ = Mathf.Max(triangle.pt0.z, Mathf.Max(triangle.pt1.z, triangle.pt2.z));
    12.  
    13.     APAOctree finalNode = null;
    14.     APAOctree currentNode = parentNode;
    15.     while (currentNode != null  finalNode == null) {
    16.         float boundsCenterX = currentNode._Bounds.center.x;
    17.         float boundsCenterY = currentNode._Bounds.center.y;
    18.         float boundsCenterZ = currentNode._Bounds.center.z;
    19.  
    20.         // Test if the triangle crosses any of the mid planes of the node
    21.         if ((minX < boundsCenterX  maxX >= boundsCenterX) || (minY < boundsCenterY  maxY >= boundsCenterY) || (minZ < boundsCenterZ  maxZ >= boundsCenterZ)) {
    22.             // The triangle must be in the current node
    23.             finalNode = currentNode;
    24.         } else {
    25.             // The triangle can be inside one of our children, if we have any
    26.             if (currentNode.m_children != null  currentNode.m_children.Count > 0) {
    27.                 // Figure out which child based on which side of each mid plane the triangle sits on
    28.                 int childIndex = 0;
    29.                 if (minX < boundsCenterX)
    30.                     childIndex |= 4;
    31.                 if (minY < boundsCenterY)
    32.                     childIndex |= 2;
    33.                 if (minZ < boundsCenterZ)
    34.                     childIndex |= 1;
    35.  
    36.                 // Continue iteration with the child node that contains the triangle
    37.                 currentNode = currentNode.m_children[childIndex];
    38.             } else {
    39.                 // Since we don't have children, even though the triangle *would* fit in one of our potential child,
    40.                 // we're the node that has to own the triangle.
    41.                 // Arguably, if you hit this code a lot, you could benefit from using more depth in your octree...
    42.                 finalNode = currentNode;
    43.             }
    44.         }
    45.     }
    46.  
    47.     return finalNode;
    48. }
    49.  
     
    Last edited: Apr 11, 2013
    luizero00 likes this.
  5. joshimoo

    joshimoo

    Joined:
    Jun 23, 2011
    Posts:
    266
    Interesting thread.
    Thanks for sharing.
     
  6. gvaughan

    gvaughan

    Joined:
    Jan 28, 2010
    Posts:
    32
    Hi Jean,

    I can't express how happy I am that you were able to make use of this, and the fact that you improved it is icing on the cake! I'll actually be working on the project that this originated from again soon, so I can't wait to incorporate it and test it myself.

    :)

    Thanks!
     
  7. JeanSimonet

    JeanSimonet

    Joined:
    Nov 23, 2012
    Posts:
    31
    You're welcome, I think it's only fair!

    This reminds me: there is one other thing that you might care about. I noticed the comment in this method:
    Code (csharp):
    1.  
    2.     APARaycastHit BuildRaycastHit(Triangle hitTriangle, float distance, Vector2 barycentricCoordinate){
    3.         APARaycastHit returnedHit = new APARaycastHit(hitTriangle.mesh, hitTriangle.index, hitTriangle.trans, distance, barycentricCoordinate);
    4.        
    5.         returnedHit.textureCoord = hitTriangle.uv_pt0 + ((hitTriangle.uv_pt1 - hitTriangle.uv_pt0) * barycentricCoordinate.x) + ((hitTriangle.uv_pt2 - hitTriangle.uv_pt0) * barycentricCoordinate.y);
    6. //HACK:  This only returns the center of the hit triangle.  A close approximate, but not accurate.  
    7.         returnedHit.point = hitTriangle.trans.position + (hitTriangle.pt0 + hitTriangle.pt1 + hitTriangle.pt2) / 3;
    8.         return returnedHit;
    9.        
    10.     }
    11.  
    Now I don't need to know the intersection point, but if you do, you can figure it out from the initial raycast ray and hit distance, like this:
    Code (csharp):
    1.  
    2. // This point will turn out to be exactly ON the hit triangle
    3. Vector3 hitLocation = ray.origin + ray.direction * returnedHit.distance;
    4.  
    You will need to modify your code around a little bit (since right now BuildRaycastHit() doesn't know about the ray), but that shouldn't be a problem.
    Good luck with your project!
     
  8. DanJC

    DanJC

    Joined:
    Feb 18, 2013
    Posts:
    15
    I've had a go at this but I don't seem to be able to get a basic test working right.

    My test script simply draws 2 lines to show what's happening:

    Code (csharp):
    1. using UnityEngine;
    2. using System.Collections;
    3.  
    4. public class MyTest : MonoBehaviour
    5. {
    6.     void Start ()
    7.     {
    8.         APAObjectDictionary.singleton.Init(Callback, new Bounds(new Vector3(0f,0f,0f), new Vector3(10f,10f,10f)));
    9.     }
    10.  
    11.     public void Callback()
    12.     {
    13.         Debug.Log("Completed Dictionary Build and Object Generation.");
    14.     }
    15.  
    16.     void Update ()
    17.     {
    18.         Ray ray = new Ray(transform.position, transform.up);
    19.         Debug.DrawRay(transform.position, 100 * transform.up, Color.green);
    20.  
    21.         APARaycastHit hit;
    22.  
    23.         if (APARaycast.Raycast(ray, out hit))
    24.             Debug.DrawRay(hit.point, 100 * Vector3.up, Color.cyan);
    25.     }
    26.  
    27. }

    But I'm getting results like these:

    $RayMiss.png

    $RayMiss2.png

    $RayMiss3.png

    $RayMiss4.png


    I loaded the test scene already provided, removed the ColliderTest object and put in a new empty and a primitive sphere. I put the test script on the empty.

    The only code I changed was to comment out the recursive calls to DrawOctree() in APAObjectDictionary:

    $RayMiss5.png


    I guess I'm missing something obvious?
     
  9. gvaughan

    gvaughan

    Joined:
    Jan 28, 2010
    Posts:
    32
    Hey,

    I guess I don't really know what your script is trying to do here. It looks like it's creating a ray that shoots directly up from whatever gameobject this script was added to, so unless the object your checking for is located directly above this, it won't work. If you're moving this object around and trying to line it up, it should work just fine though. It looks like you were going to attach screenshots, but I don't see them.


    Are the meshes somewhere between 0,0,0 and 10, 10, 10 though? This is the extents of the octree, and if the transform isn't located somewhere in that range it won't get included in the triangle index.

    Also, the recursion is likely necessary to get anything meaningful out of the raycast. The triangles are packed in the smallest level of the octree they'll fit in, so unless all of the triangles of the mesh you're trying to use are bounded at 10, 10, 10, they won't be included in the top level of the octree, and a search of it will return nothing. If you want to cut down on recursion, lower the octreeDepth int in the APAObjectDictionary (though this leads to higher search times and lower accuracy)
     
  10. DanJC

    DanJC

    Joined:
    Feb 18, 2013
    Posts:
    15
    Yeah the screens are uploaded, but they seem to be a bit temperamental loading for me too. Hammer refresh a little.. they should appear.

    But you're correct; the script simply shoots a ray up from whatever it's attached to, and I've been moving and rotating it to check things out.(The screens make it obvious.) Green line = raycast. Blue line = vertical from hitpoint (or triangle centre in this case). That's the intention anyway - the two should meet but they either don't meet, or the blue doesn't appear.

    The meshes are in -5 to 5 in all dimensions; they are the bounds I set in my test above.

    What I said about the recursion only applies to DrawOctree(). No actual octree functionality.


    Confusing behaviour aside, many thanks for the work you have put into this, by the way.
     
    Last edited: May 4, 2013
  11. gvaughan

    gvaughan

    Joined:
    Jan 28, 2010
    Posts:
    32
    Ahh I see.

    The problem is that the point is being offset by the transform position of the mesh's owner. I'm guessing that the object I tested with was always at 0,0,0, and I assumed that the triangle vert positions were local to the transform. Turns out they're world space coords.

    So in APARaycast.cs, replace the function


    Code (csharp):
    1.  
    2. static APARaycastHit BuildRaycastHit(Triangle hitTriangle, float distance, Vector2 barycentricCoordinate){
    3.         APARaycastHit returnedHit = new APARaycastHit(hitTriangle.trans, distance, barycentricCoordinate);
    4.        
    5.         returnedHit.textureCoord = hitTriangle.uv_pt0 + ((hitTriangle.uv_pt1 - hitTriangle.uv_pt0) * barycentricCoordinate.x) + ((hitTriangle.uv_pt2 - hitTriangle.uv_pt0) * barycentricCoordinate.y);
    6. //HACK:  This only returns the center of the hit triangle.  A close approximate, but not accurate.  
    7.         returnedHit.point = hitTriangle.trans.position + (hitTriangle.pt0 + hitTriangle.pt1 + hitTriangle.pt2) / 3;
    8.         return returnedHit;
    9.        
    10.     }
    11.  
    with

    Code (csharp):
    1.  
    2. static APARaycastHit BuildRaycastHit(Triangle hitTriangle, float distance, Vector2 barycentricCoordinate)
    3. APARaycastHit returnedHit = new APARaycastHit(hitTriangle.trans, distance, barycentricCoordinate);
    4. returnedHit.textureCoord = hitTriangle.uv_pt0 + ((hitTriangle.uv_pt1 - hitTriangle.uv_pt0) * barycentricCoordinate.x) + ((hitTriangle.uv_pt2 - hitTriangle.uv_pt0) * barycentricCoordinate.y);
    5. //HACK:  This only returns the center of the hit triangle.  A close approximate, but not accurate.  
    6. returnedHit.point = (hitTriangle.pt0 + hitTriangle.pt1 + hitTriangle.pt2) / 3;
    7. return returnedHit;
    8.  
    Just removing the addition of the hitTriangle.trans.position.

    Looking back on this now, there's lots of code coupling left. I pretty much directly cut it out of the project, so lots of junk code remains.

    For example, APAObjectDictionary, line 75, will skip any meshes that contain the string "Combined Mesh"..... So, watch out for that I guess :)
     
  12. DanJC

    DanJC

    Joined:
    Feb 18, 2013
    Posts:
    15
    lol

    Well the change has solved one third of the issue, but only one third I'm afraid. It no longer reports a hit as coming from anywhere but on the mesh itself, however I'm still getting quite a few misses that shouldn't be, perhaps around 50% depending on where I position the raycasting "marker".

    I'm also getting a few "backwards" hits, as if the ray stretches in both directions. I was getting a similar result with the Moller Trumbore algorithm earlier, but what's strange is that sometimes I can flip the ray 180º and get a different result, or slide along the raycasting marker's forward for different results, and sometimes the backwards hit is not on the first surface it would have come across.

    Just to be sure, I double checked with only a primitive sphere in the scene. Same thing. :/
     
    Last edited: May 5, 2013
  13. ACZ

    ACZ

    Joined:
    Feb 7, 2013
    Posts:
    3
    Hey,

    This raycast solution is exactly what I needed! Thanks! My use case is a little different - this direct raycast works on different threads, unlike physics.raycast, which allows me to move a lot of the computation work away from the main thread. Huge improvement in my mobile game!

    The good news:

    You can remove that 'hack' line with:

    Code (csharp):
    1.         returnedHit.point = hitTriangle.pt0 + ((hitTriangle.pt1 - hitTriangle.pt0) * barycentricCoordinate.x) + ((hitTriangle.pt2 - hitTriangle.pt0) * barycentricCoordinate.y);
    2.  
    The bad news is that I'm also getting some errors with 'misses'. I've tracked the misses down to two different causes:

    First: I've connected the Moller/Trumbore TestIntersection() directly to an external ray and brute force iteration through all the triangles in my mesh. This works 99% of the time, except for a particular area of my mesh around Y == 0. My mesh is effectively the interior half of a torus, so the Y == 0 part is also the zone where the surfaces approach vertical. Moving the mesh does not move the error - which means it may be more surface rotation related. I've tried changing the epsilon value and I tried implementing the non-culled version of the Moller/Trumbore example - no help on either.

    Second: When using the raycast directly, it works about 95% of the time. Almost flawlessly, except it seems to always miss a triangle that intersects with X == 0 or Y == 0. (I've also seen Z == 0 fail, but in my isolated test case I don't have this). When I move the mesh before testing (within the Octree bounds), the zones of failure stay relative to the world. I don't know enough about Octree navigation, but its looking like there is a failure within these very particular zones.

    I feel like I'm really close to getting this working, but I've reached the limit of my expertise trying to debug this... any ideas?

    Really appreciate any support!

    Edit:

    Further testing got interesting... I increased the size of the octree, and moved my whole scene (the torus) up to within a quadrant instead of centered on zero. As a result:

    - Crossing the X == 0 or Z == 0 lines are no longer an issue (or perhaps crossing the center lines on the octree bounds). This is a hacky workaround, but it helps confirm my earlier findings.
    - Crossing Y == 0 is really interesting... instead of just getting a miss, my raycast places the hit on the opposite side of the torus. Which means that the miss was probably a crossing Y == 0 issue (not unlike the X or Y problem), and the 'error' in the triangle intersection is actually just returning the hit from 'above' where my ray starts... which makes intuitive sense, but looking at the code my understanding was that the ray's origin was taken into account? Regardless, a simple dot product check against the ray origin seems to solve this issue well.
     
    Last edited: Sep 16, 2013
  14. gvaughan

    gvaughan

    Joined:
    Jan 28, 2010
    Posts:
    32
    Hi DanJC and ACZ,

    Sorry for not keeping up with this thread. It's been a very long time since I worked with this stuff, and to be honest, it was hacked together pretty quickly anyway.

    It seems that you both are experiencing issues with hits being reversed depending on location. What's strange is that I'm having problems replicating that. :/

    I'm attaching an updated package with some of the improvements suggested in this thread included. The test scene now draws a dot at the hit point, and any errors in the test intersection are available through APARaycast.intersectionErrorType.

    Test it out with this and let me know where it seems to be failing. I'm initially thinking it's some rounding error in Unity's Dot and Cross functions, so those might need to be written by hand to fix this?!?!



    View attachment $RaycastReplacement_9-17-2013.unitypackage
     
  15. ACZ

    ACZ

    Joined:
    Feb 7, 2013
    Posts:
    3
    Hey, thanks for the reply! I've got some stuff to take care of tonight, but I'll take a look as soon as I can.

    We noticed a subtle error in the accuracy of Unity's ray / bounds calculation check as well. This is very small though, so I really wonder if its the case or just something else entirely.

    After lots of testing, its very clear the error (for me at least) is any triangle intersecting the origin 'planes' of the top level Octree. No similar errors on the child nodes. (also, I implemented the non-culled version of the intersection test, so it doesn't look like I'm erroneously hitting backsides... its really as if those triangles don't exist).

    I'll let you know as soon as I find something else - thanks again!

    EDIT:

    Ok, so its hard to try and isolate the bad intersections in my test case, but it looks like either one of two things:

    a) it might be failure of dot 2 against the triangle it _should_ be hitting
    b) it much more seems seems like its failing to find the triangle at all - perhaps something bad in the Octree traversal?

    The correct number of triangles is indexed. Weird.

    Anyways, have to run - but I'll do some deeper testing tomorrow.
     
    Last edited: Sep 19, 2013
  16. erictang

    erictang

    Joined:
    Jul 28, 2012
    Posts:
    15
    gameobject hidden at runtime
    How to update the corresponding data quickly ?
     
  17. Andrey-Kondakov

    Andrey-Kondakov

    Joined:
    Oct 22, 2014
    Posts:
    1
    Hello everybody! Sorry for necroposting but I had to do it. I've run into the same problem: got an enormous runtime-generated model with 100k triangles so I can't use colliders, but I need rather accurate raycasting. I implemented gvaughan's method and it is very useful but still misses some of triangles. Did anyone resolved this problem at last or may be used some other solutions? I will be very greatful for any help in this direction!
     
  18. bellicapax

    bellicapax

    Joined:
    Oct 5, 2016
    Posts:
    14
    Apologies for necroing this, but in case anyone actually needs this solution, I wanted to post one fix that was making it unusable for me:

    If your bounds is only big enough to house some of the triangles in the top level octree (and not any of its children), then you need this fix to actually check the top level octree in RecurseOctreeBounds() in APARaycast.cs


    Code (CSharp):
    1.     static List<APARaycastHit> RecurseOctreeBounds(APAOctree octree, Ray ray){
    2.         List<APARaycastHit> hits = new List<APARaycastHit>();
    3.         float dist = 0f;
    4.         Vector2 baryCoord = new Vector2();
    5.         if (octree.bounds.IntersectRay(ray))
    6.         {
    7.             for (int i = 0; i < octree.triangles.Count; i++)
    8.             {
    9.                 if (TestIntersection(octree.triangles[i], ray, out dist, out baryCoord))
    10.                 {
    11.                     hits.Add(BuildRaycastHit(octree.triangles[i], dist, baryCoord));
    12.                 }
    13.             }
    14.         }
    15.         for (int i = 0; i < octree.m_children.Count; i++){
    16.             hits.AddRange(RecurseOctreeBounds(octree.m_children[i], ray));  
    17.         }
    18.         return hits;
    19.     }
     
  19. K-a-i

    K-a-i

    Joined:
    Oct 10, 2015
    Posts:
    8
    Hi guys, anyone able to share a simple working project of this. Raycast a cube or sphere or any model without colliders would be great!
     
    divinesol likes this.
  20. divinesol

    divinesol

    Joined:
    Mar 28, 2017
    Posts:
    1
    I would also appreciate if anyone has a working project for this!
     
  21. cfloutier

    cfloutier

    Joined:
    Jul 30, 2009
    Posts:
    34
    I'll try to create one and post it here
     
  22. ml785

    ml785

    Joined:
    Dec 20, 2018
    Posts:
    119
    Bump... Is there an updated version?