Wayback Machinekoobas.hobune.stream
May JUN Jul
Previous capture 13 Next capture
2021 2022 2023
1 capture
13 Jun 22 - 13 Jun 22
sparklines
Close Help
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
avatar image
0
Question by Avash · Jan 10, 2015 at 05:12 PM · c#arraymath

A problem with intersection detection

 using UnityEngine;
 using System;
 using System.Collections;
 using System.Collections.Generic;
 using System.Linq;
 
 public class intersectiontest : MonoBehaviour {
 
     // Use this for initialization
     void Start () {
     
     }
     
     // Update is called once per frame
     void Update () {
         bool isFree = true;
         Collider[] hitColliders = Physics.OverlapSphere(this.transform.position, this.collider.bounds.extents.magnitude);
         List<GameObject> h1tGame0bjects = new List<GameObject>(); 
         foreach(Collider currentCollider in hitColliders){
             h1tGame0bjects.Add(currentCollider.gameObject);
         }
         foreach(GameObject currentGameObject in h1tGame0bjects){
             if(this.collider.bounds.Intersects(currentGameObject.collider.bounds) && currentGameObject.collider.GetType() != typeof(CharacterController)){
                 int[] thisTriangles = this.transform.GetComponent<MeshFilter>().mesh.triangles;
                 int[] otherTriangles = currentGameObject.GetComponent<MeshFilter>().mesh.triangles; 
                 Vector3[] thisVertices = this.transform.GetComponent<MeshFilter>().mesh.vertices;
                 Vector3[] otherVertices = currentGameObject.transform.GetComponent<MeshFilter>().mesh.vertices; 
                 int adjustedTriangleCount = thisTriangles.Length / 3;
                 int otherAdjustedTriangleCount = otherTriangles.Length / 3;
                 for(int i = 1; i < adjustedTriangleCount; i ++){    // For every triangle in this...
                     for(int ib = 1; ib < otherAdjustedTriangleCount; ib ++){    // For every triangle in other object...
                         int[] aPoints = new int[3];
                         aPoints[0] = thisTriangles[(i - 1)*3 + 0];
                         aPoints[1] = thisTriangles[(i - 1)*3 + 1];
                         aPoints[2] = thisTriangles[(i - 1)*3 + 2];
                         Vector3 a1 = this.transform.TransformPoint(thisVertices[aPoints[0]]);
                         Vector3 a2 = this.transform.TransformPoint(thisVertices[aPoints[1]]);
                         Vector3 a3 = this.transform.TransformPoint(thisVertices[aPoints[2]]);
                         int[] bPoints = new int[3];
                         bPoints[0] = otherTriangles[(ib - 1)*3 + 0];
                         bPoints[1] = otherTriangles[(ib - 1)*3 + 1];
                         bPoints[2] = otherTriangles[(ib - 1)*3 + 2];
                         Vector3 b1 = currentGameObject.transform.TransformPoint(otherVertices[aPoints[0]]);
                         Vector3 b2 = currentGameObject.transform.TransformPoint(otherVertices[aPoints[1]]);
                         Vector3 b3 = currentGameObject.transform.TransformPoint(otherVertices[aPoints[2]]);
                         if(TriTriOverlap.TriTriIntersect(a1, a2, a3, b1, b2, b3)){
                             isFree = false;
                         } 
                     }
                 }
             }
         } 
         Debug.Log (isFree);
     }
 }
   

I'm doing this because OnTriggerStay cannot be used multiple times in one frame. I'm pretty sure that TriTriIntersection works so why the bool IsFree is always false?

Here's tritrioverlap.

 using UnityEngine;
  using System.Collections;
  
  /// <summary>
  /// Tri/Tri intersection. Implementation of Tomas Moller, 1997.
  /// See article "A Fast Triangle-Triangle Intersection Test", Journal of Graphics Tools, 2(2), 1997.
  /// </summary>
  public static class TriTriOverlap
  {
      private static void Sort(Vector2 v)
      {
          if (v.x > v.y)
          {
              float c;
              c = v.x;
              v.x = v.y;
              v.y = c;
          }
      }
      
      /// <summary>
      /// This edge to edge test is based on Franlin Antonio's gem: "Faster Line Segment Intersection", in Graphics Gems III, pp. 199-202 
      /// </summary>
      private static bool EdgeEdgeTest(Vector3 v0, Vector3 v1, Vector3 u0, Vector3 u1, int i0, int i1)
      {
          float Ax, Ay, Bx, By, Cx, Cy, e, d, f;
          Ax = v1[i0] - v0[i0];
          Ay = v1[i1] - v0[i1];
  
          Bx = u0[i0] - u1[i0];
          By = u0[i1] - u1[i1];
          Cx = v0[i0] - u0[i0];
          Cy = v0[i1] - u0[i1];
          f = Ay * Bx - Ax * By;
          d = By * Cx - Bx * Cy;
          if ((f > 0 && d >= 0 && d <= f) || (f < 0 && d <= 0 && d >= f))
          {
              e = Ax * Cy - Ay * Cx;
              if (f > 0)
              {
                  if (e >= 0 && e <= f) { return true; }
              }
              else
              {
                  if (e <= 0 && e >= f) { return true; }
              }
          }
  
          return false;
      }
  
      private static bool EdgeAgainstTriEdges(Vector3 v0, Vector3 v1, Vector3 u0, Vector3 u1, Vector3 u2, short i0, short i1)
      {
          // test edge u0,u1 against v0,v1
          if (EdgeEdgeTest(v0, v1, u0, u1, i0, i1)) { return true; }
  
          // test edge u1,u2 against v0,v1 
          if (EdgeEdgeTest(v0, v1, u1, u2, i0, i1)) { return true; }
  
          // test edge u2,u1 against v0,v1 
          if (EdgeEdgeTest(v0, v1, u2, u0, i0, i1)) { return true; }
  
          return false;
      }
  
      private static bool PointInTri(Vector3 v0, Vector3 u0, Vector3 u1, Vector3 u2, short i0, short i1)
      {
          float a, b, c, d0, d1, d2;
  
          // is T1 completly inside T2?
          // check if v0 is inside tri(u0,u1,u2)
          a = u1[i1] - u0[i1];
          b = -(u1[i0] - u0[i0]);
          c = -a * u0[i0] - b * u0[i1];
          d0 = a * v0[i0] + b * v0[i1] + c;
  
          a = u2[i1] - u1[i1];
          b = -(u2[i0] - u1[i0]);
          c = -a * u1[i0] - b * u1[i1];
          d1 = a * v0[i0] + b * v0[i1] + c;
  
          a = u0[i1] - u2[i1];
          b = -(u0[i0] - u2[i0]);
          c = -a * u2[i0] - b * u2[i1];
          d2 = a * v0[i0] + b * v0[i1] + c;
  
          if (d0 * d1 > 0.0f)
          {
              if (d0 * d2 > 0.0f) { return true; }
          }
  
          return false;
      }
  
      private static bool TriTriCoplanar(Vector3 N, Vector3 v0, Vector3 v1, Vector3 v2, Vector3 u0, Vector3 u1, Vector3 u2)
      {
          float[] A = new float[3];
          short i0, i1;
  
          // first project onto an axis-aligned plane, that maximizes the area
          // of the triangles, compute indices: i0,i1. 
          A[0] = Mathf.Abs(N[0]);
          A[1] = Mathf.Abs(N[1]);
          A[2] = Mathf.Abs(N[2]);
          if (A[0] > A[1])
          {
              if (A[0] > A[2])
              {
                  // A[0] is greatest
                  i0 = 1;      
                  i1 = 2;
              }
              else
              {
                  // A[2] is greatest
                  i0 = 0;      
                  i1 = 1;
              }
          }
          else  
          {
              if (A[2] > A[1])
              {
                  // A[2] is greatest 
                  i0 = 0;      
                  i1 = 1;
              }
              else
              {
                  // A[1] is greatest 
                  i0 = 0;      
                  i1 = 2;
              }
          }
  
          // test all edges of triangle 1 against the edges of triangle 2 
          if (EdgeAgainstTriEdges(v0, v1, u0, u1, u2, i0, i1)) { return true; }
          if (EdgeAgainstTriEdges(v1, v2, u0, u1, u2, i0, i1)) { return true; }
          if (EdgeAgainstTriEdges(v2, v0, u0, u1, u2, i0, i1)) { return true; }
  
          // finally, test if tri1 is totally contained in tri2 or vice versa 
          if (PointInTri(v0, u0, u1, u2, i0, i1)) { return true; }
          if (PointInTri(u0, v0, v1, v2, i0, i1)) { return true; }
  
          return false;
      }
  
  
  
      private static bool ComputeIntervals(float VV0, float VV1, float VV2,
                                float D0, float D1, float D2, float D0D1, float D0D2,
                                ref float A, ref float B, ref float C, ref float X0, ref float X1)
      {
          if (D0D1 > 0.0f)
          {
              // here we know that D0D2<=0.0 
              // that is D0, D1 are on the same side, D2 on the other or on the plane 
              A = VV2; B = (VV0 - VV2) * D2; C = (VV1 - VV2) * D2; X0 = D2 - D0; X1 = D2 - D1;
          }
          else if (D0D2 > 0.0f)
          {
              // here we know that d0d1<=0.0 
              A = VV1; B = (VV0 - VV1) * D1; C = (VV2 - VV1) * D1; X0 = D1 - D0; X1 = D1 - D2;
          }
          else if (D1 * D2 > 0.0f || D0 != 0.0f)
          {
              // here we know that d0d1<=0.0 or that D0!=0.0 
              A = VV0; B = (VV1 - VV0) * D0; C = (VV2 - VV0) * D0; X0 = D0 - D1; X1 = D0 - D2;
          }
          else if (D1 != 0.0f)
          {
              A = VV1; B = (VV0 - VV1) * D1; C = (VV2 - VV1) * D1; X0 = D1 - D0; X1 = D1 - D2;
          }
          else if (D2 != 0.0f)
          {
              A = VV2; B = (VV0 - VV2) * D2; C = (VV1 - VV2) * D2; X0 = D2 - D0; X1 = D2 - D1;
          }
          else
          {
              return true;
          }
  
          return false;
      }
  
      /// <summary>
      /// Checks if the triangle V(v0, v1, v2) intersects the triangle U(u0, u1, u2).
      /// </summary>
      /// <param name="v0">Vertex 0 of V</param>
      /// <param name="v1">Vertex 1 of V</param>
      /// <param name="v2">Vertex 2 of V</param>
      /// <param name="u0">Vertex 0 of U</param>
      /// <param name="u1">Vertex 1 of U</param>
      /// <param name="u2">Vertex 2 of U</param>
      /// <returns>Returns <c>true</c> if V intersects U, otherwise <c>false</c></returns>
      public static bool TriTriIntersect(Vector3 v0, Vector3 v1, Vector3 v2, Vector3 u0, Vector3 u1, Vector3 u2)
      {
          Vector3 e1, e2;
          Vector3 n1, n2;    
          Vector3 dd;
          Vector2 isect1 = Vector2.zero, isect2 = Vector2.zero;
  
          float du0, du1, du2, dv0, dv1, dv2, d1, d2;
          float du0du1, du0du2, dv0dv1, dv0dv2;
          float vp0, vp1, vp2;
          float up0, up1, up2;
          float bb, cc, max;
  
          short index;
  
          // compute plane equation of triangle(v0,v1,v2) 
          e1 = v1 - v0;
          e2 = v2 - v0;
          n1 = Vector3.Cross(e1, e2);
          d1 = -Vector3.Dot(n1, v0);
          // plane equation 1: N1.X+d1=0 */
  
          // put u0,u1,u2 into plane equation 1 to compute signed distances to the plane
          du0 = Vector3.Dot(n1, u0) + d1;
          du1 = Vector3.Dot(n1, u1) + d1;
          du2 = Vector3.Dot(n1, u2) + d1;
  
          // coplanarity robustness check 
          if (Mathf.Abs(du0) < Mathf.Epsilon) { du0 = 0.0f; }
          if (Mathf.Abs(du1) < Mathf.Epsilon) { du1 = 0.0f; }
          if (Mathf.Abs(du2) < Mathf.Epsilon) { du2 = 0.0f; }
  
          du0du1 = du0 * du1;
          du0du2 = du0 * du2;
  
          // same sign on all of them + not equal 0 ? 
          if (du0du1 > 0.0f && du0du2 > 0.0f)
          {
              // no intersection occurs
              return false;                    
          }
  
          // compute plane of triangle (u0,u1,u2)
          e1 = u1 - u0;
          e2 = u2 - u0;
          n2 = Vector3.Cross(e1, e2);
          d2 = -Vector3.Dot(n2, u0);
  
          // plane equation 2: N2.X+d2=0 
          // put v0,v1,v2 into plane equation 2
          dv0 = Vector3.Dot(n2, v0) + d2;
          dv1 = Vector3.Dot(n2, v1) + d2;
          dv2 = Vector3.Dot(n2, v2) + d2;
  
          if (Mathf.Abs(dv0) < Mathf.Epsilon) { dv0 = 0.0f; }
          if (Mathf.Abs(dv1) < Mathf.Epsilon) { dv1 = 0.0f; }
          if (Mathf.Abs(dv2) < Mathf.Epsilon) { dv2 = 0.0f; }
  
  
          dv0dv1 = dv0 * dv1;
          dv0dv2 = dv0 * dv2;
  
          // same sign on all of them + not equal 0 ? 
          if (dv0dv1 > 0.0f && dv0dv2 > 0.0f)
          {
              // no intersection occurs
              return false;                    
          }
  
          // compute direction of intersection line 
          dd = Vector3.Cross(n1, n2);
  
          // compute and index to the largest component of D 
          max = (float)Mathf.Abs(dd[0]);
          index = 0;
          bb = (float)Mathf.Abs(dd[1]);
          cc = (float)Mathf.Abs(dd[2]);
          if (bb > max) { max = bb; index = 1; }
          if (cc > max) { max = cc; index = 2; }
  
          // this is the simplified projection onto L
          vp0 = v0[index];
          vp1 = v1[index];
          vp2 = v2[index];
  
          up0 = u0[index];
          up1 = u1[index];
          up2 = u2[index];
  
          // compute interval for triangle 1 
          float a = 0, b = 0, c = 0, x0 = 0, x1 = 0;
          if (ComputeIntervals(vp0, vp1, vp2, dv0, dv1, dv2, dv0dv1, dv0dv2, ref a, ref b, ref c, ref x0, ref x1)) 
          { 
              return TriTriCoplanar(n1, v0, v1, v2, u0, u1, u2); 
          }
  
          // compute interval for triangle 2 
          float d = 0, e = 0, f = 0, y0 = 0, y1 = 0;
          if (ComputeIntervals(up0, up1, up2, du0, du1, du2, du0du1, du0du2, ref d, ref e, ref f, ref y0, ref y1)) 
          { 
              return TriTriCoplanar(n1, v0, v1, v2, u0, u1, u2); 
          }
  
          float xx, yy, xxyy, tmp;
          xx = x0 * x1;
          yy = y0 * y1;
          xxyy = xx * yy;
  
          tmp = a * xxyy;
          isect1[0] = tmp + b * x1 * yy;
          isect1[1] = tmp + c * x0 * yy;
  
          tmp = d * xxyy;
          isect2[0] = tmp + e * xx * y1;
          isect2[1] = tmp + f * xx * y0;
  
          Sort(isect1);
          Sort(isect2);
  
          return !(isect1[1] < isect2[0] || isect2[1] < isect1[0]);
      }
  }
Comment
Add comment · Show 13
10 |3000 characters needed characters left characters exceeded
â–¼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image Avash · Jan 11, 2015 at 01:46 PM 0
Share

Help me please.

avatar image incorrect · Jan 11, 2015 at 01:58 PM 0
Share

Just a moment, I'm reading. :)

avatar image Cheese_Gaming · Jan 11, 2015 at 03:26 PM 0
Share

Yeah... let me just uhhh... sip some red bull while i start to read this :3

avatar image Avash · Jan 11, 2015 at 03:30 PM 0
Share

This is part of my grid snapping system and I have been working on it for almost a year now.

avatar image incorrect · Jan 11, 2015 at 04:21 PM 0
Share

So what's 'TriTriOverlap' and how it's 'TriTriIntersect' method works?

Btw, do you know why physics is not calculated every frame? And have you had a look on Gilbert–Johnson–$$anonymous$$eerthi distance algorithm?

Show more comments

1 Reply

· Add your reply
  • Sort: 
avatar image
1
Best Answer

Answer by incorrect · Jan 11, 2015 at 05:46 PM

It's an algorithm that checks is triangle a1 a2 a3 intersecting with b1 b2 b3.

So how can we tell you what's wrong with your script if you don't show us how it works? Please, add 'TriTriOverlap' class to original post.

Is it possible to update physics multiple times per frame? And no, I haven't.

Well... I can't answer this question, found nothing about. Why would you need to update physics faster then your framerate is? In most games it does not makes sense.

Can I check with it are two objects intersecting? What does it return if they are, a negative number?

Was that a question about Gilbert–Johnson–Keerthi distance algorithm? This algorithm is used for calculation of objects' intersection, so probably that's what you need. Look here.

Comment
Add comment · Share
10 |3000 characters needed characters left characters exceeded
â–¼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Follow this Question

Answers Answers and Comments

27 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image

Related Questions

Picking a Random Order for Levers 1 Answer

Array index out of range error 1 Answer

Few problems with arrays 1 Answer

What's a more efficient way to sort an array into multiple groups? 1 Answer

A problem with arrays 1 Answer


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges