Collision detection - why not working properly?

djevazi

PeasyCam library is required.

I'm trying to detect a point-triangle collision using this tutorial: http://www.jeffreythompson.org/collision-detection/tri-point.php . But my sketch is 3d, so I translating a 3d coorinates in 2d using screenX() and screenY(). The problem is that when my mouse is inside of triangle, sometimes the resulting "hit" color is blinking and I have "no hit" message. Can't understand why the collision is not working properly, it must be "hit" all the time my mouse is inside of thiangle. Any suggestions? Thanks.

import peasy.*;
PeasyCam jcam;

ArrayList <Point> points = new ArrayList <Point>();
ArrayList <Triangle> triangles = new ArrayList <Triangle>();

void setup()
{
  size(800, 800, P3D);
  smooth();
  jcam = new PeasyCam(this, 200);

  color tempColore=color(255, 255, 255);

  PVector v1= new PVector(0, 0, 0);
  Point pt1 = new Point(v1, tempColore);
  points.add(pt1);

  PVector v2= new PVector(100, 0, 0);
  Point pt2 = new Point(v2, tempColore);
  points.add(pt2);

  PVector v3= new PVector(0, 100, 0);
  Point pt3 = new Point(v3, tempColore);
  points.add(pt3);

  PVector v4= new PVector(100, 0, 0);
  Point pt4 = new Point(v4, tempColore);
  points.add(pt4);  

  PVector v5= new PVector(100, 100, 0);
  Point pt5 = new Point(v5, tempColore);
  points.add(pt5);

  PVector v6= new PVector(0, 100, 0);
  Point pt6 = new Point(v6, tempColore);
  points.add(pt6);


  //triangles initialize
  for (int i=0; i<points.size(); i=i+3)
  {
    Triangle tr = new Triangle(points.get(i).pos, points.get(i+1).pos, points.get(i+2).pos);
    triangles.add(tr);
  }

}

boolean triPoint(float x1, float y1, float x2, float y2, float x3, float y3,float mx, float my) 
  {
    // get the area of the triangle
    float areaOrig = abs( (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1) );

    // get the area of 3 triangles made between the point
    // and the corners of the triangle
    float area1 =    abs( (x1-mx)*(y2-my) - (x2-mx)*(y1-my) );
    float area2 =    abs( (x2-mx)*(y3-my) - (x3-mx)*(y2-my) );
    float area3 =    abs( (x3-mx)*(y1-my) - (x1-mx)*(y3-my) );

    // if the sum of the three areas equals the original,
    // we're inside the triangle!
    if (area1 + area2 + area3 == areaOrig) 
    {
      return true;
    }
    return false;
  }


void draw()
{
  background(150);

  for (int i = triangles.size ()-1; i >= 0; i--)
  { 
    color tempColore=0;

    float ax = screenX(triangles.get(i).A.x,triangles.get(i).A.y);
    float ay = screenY(triangles.get(i).A.x,triangles.get(i).A.y);
    float bx = screenX(triangles.get(i).B.x,triangles.get(i).B.y);
    float by = screenY(triangles.get(i).B.x,triangles.get(i).B.y);
    float cx = screenX(triangles.get(i).C.x,triangles.get(i).C.y);
    float cy = screenY(triangles.get(i).C.x,triangles.get(i).C.y);
    float mx = mouseX;
    float my = mouseY;

    boolean hit = triPoint(ax,ay,bx,by,cx,cy,mx,my);

    if(hit==true)
    {
      tempColore = #A57066;
      println("hit");
    }
    else
    {
      tempColore = #CEBE9A;
      println("no hit");
    }
    triangles.get(i).display(tempColore);
  }


  for (int i = points.size ()-1; i >= 0; i--)
  { 
    points.get(i).display();
  }

}


class Point
{
  PVector pos;
  color colore;


  Point(PVector posIn, color coloreIn)
  {
    pos = posIn;
    colore=coloreIn;
  }

  void display()
  {
    colorMode(RGB);
    noStroke();
    fill(colore);
    pushMatrix();
    translate(pos.x,pos.y,pos.z);
    box(1);
    popMatrix(); 
  }
}


class Triangle
{
  PVector A, B, C;
  color colore;

  Triangle (PVector Ain, PVector Bin, PVector Cin)
  {
    A=Ain;
    B=Bin;
    C=Cin;
  }

  void display(color coloreIn)
  {
    colore = coloreIn;
    fill(colore);
    beginShape(TRIANGLE);
    stroke(255,20);
    strokeWeight(2);
    vertex(A.x,A.y,A.z);
    vertex(B.x,B.y,B.z);
    vertex(C.x,C.y,C.z);
    endShape();
  }
}

djevazi

Please, help! Don't know what to do with this issue.

kfrajer

Hi @djevazi

For debugging your code, you could disable peasyCam by commenting any reference to it. Then more people will be able to run your code.

I have changed your code a bit. You can check the changes but you don't have to stick to them. You will see the problem can be solved by changing one line in your code which I explain below. The main change I did in your code was to migrate the tripoint() function to your Triangle class. The second big change was to introduce a smart printing tool for your case. I call it verbose and it works like this. When you want to get information, you press the space key. The space key will call the tripoint function associated to each triangle and in turn, it will print the areas involved in the calculation.

Now, the problem of your code is in this line area1 + area2 + area3 == areaOrig. If we were doing the calculations on paper, this will work all the time. The problem is rounding. You will see that when the mouse is inside the triangle, your comparison can be off by 1/1000 and this is enough to throw your calculations off. Most of the time, rounding off errors comes from divisions. Calculating your areas do not involve division! I believe the rounding error comes from using screenX() and screenY() functions. Ok, so now the solution is what I quoted as VERSION 2 below in the code. I changed the comparison to abs(area1 + area2 + area3 - areaOrig) < epsilon. This statement performs the same comparison as before. However, this time, it allows for an error in the comparison. How big of an error is ok? As big as defined by the value of epsilon. I chose epsilon to be 0.01 You will notice that and epsilon of probably 0.005 or even 0.002 (aka. 5 times smaller) is enough when peasyCam is disabled. However, when peasyCam is enabled, you will see that the error in the comparison increases because panning/zooming/rotations of your perspective affects the screenX/Y() functions. From my test, I can see that 0.01 could not be enough for you. You might have to allow for a larger error. Notice than increasing epsilon can remove your blinking problem inside your triangle completely. But there is a side effect. When the mouse pointer is closer to the triangle but not inside, it can be detected as a hit. So there is a trade off and that is for you to explore.

Kf

    import peasy.*;
    PeasyCam jcam;
    boolean verbose=false;

    ArrayList <Point> points = new ArrayList <Point>();
    ArrayList <Triangle> triangles = new ArrayList <Triangle>();

    void setup()
    {
      size(800, 800, P3D);
      smooth();
      //jcam = new PeasyCam(this, 200);

      color tempColore=color(255, 255, 255);

      PVector v1= new PVector(0, 0, 0);
      Point pt1 = new Point(v1, tempColore);
      points.add(pt1);

      PVector v2= new PVector(100, 0, 0);
      Point pt2 = new Point(v2, tempColore);
      points.add(pt2);

      PVector v3= new PVector(0, 100, 0);
      Point pt3 = new Point(v3, tempColore);
      points.add(pt3);

      PVector v4= new PVector(100, 0, 0);
      Point pt4 = new Point(v4, tempColore);
      points.add(pt4);  

      PVector v5= new PVector(100, 100, 0);
      Point pt5 = new Point(v5, tempColore);
      points.add(pt5);

      PVector v6= new PVector(0, 100, 0);
      Point pt6 = new Point(v6, tempColore);
      points.add(pt6);


      //triangles initialize
      for (int i=0; i<points.size(); i=i+3)
      {
        Triangle tr = new Triangle(points.get(i).pos, points.get(i+1).pos, points.get(i+2).pos);
        triangles.add(tr);
      }
    }




    void draw()
    {
      background(150);

      for (Triangle tria : triangles)
      { 
        color tempColore=0;



        boolean hit = tria.triPoint(mouseX, mouseY);

        if (hit==true)
        {
          tempColore = #A57066;
          //println("hit");
        } else
        {
          tempColore = #CEBE9A;
          //println("no hit");
        }
        tria.display(tempColore);
      }


      for (int i = points.size ()-1; i >= 0; i--)
      { 
        points.get(i).display();
      }
    }

    void keyPressed() {
      if (key==' ')
        verbose=!verbose;

      if (verbose==true) {

        for (Triangle tria : triangles)
         tria.triPoint(mouseX, mouseY);
         println("........");

          verbose=false;
        }
      }


      class Point
      {
        PVector pos;
        color colore;


        Point(PVector posIn, color coloreIn)
        {
          pos = posIn;
          colore=coloreIn;
        }

        void display()
        {
          colorMode(RGB);
          noStroke();
          fill(colore);
          pushMatrix();
          translate(pos.x, pos.y, pos.z);
          box(1);
          popMatrix();
        }
      }


      class Triangle
      {
        PVector A, B, C;
        color colore;

        Triangle (PVector Ain, PVector Bin, PVector Cin)
        {
          A=Ain;
          B=Bin;
          C=Cin;
        }

        void display(color coloreIn)
        {
          colore = coloreIn;
          fill(colore);
          beginShape(TRIANGLE);
          stroke(255, 20);
          strokeWeight(2);
          vertex(A.x, A.y, A.z);
          vertex(B.x, B.y, B.z);
          vertex(C.x, C.y, C.z);
          endShape();
        }

        private boolean triPoint(float x1, float y1, float x2, float y2, float x3, float y3, float mx, float my) 
        {
          // get the area of the triangle
          float areaOrig = abs( (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1) );

          // get the area of 3 triangles made between the point
          // and the corners of the triangle
          float area1 =    abs( (x1-mx)*(y2-my) - (x2-mx)*(y1-my) );
          float area2 =    abs( (x2-mx)*(y3-my) - (x3-mx)*(y2-my) );
          float area3 =    abs( (x3-mx)*(y1-my) - (x1-mx)*(y3-my) );

          if (verbose==true) println("Check " +(area1 + area2 + area3 == areaOrig) + " left "+(area1 + area2 + area3)+" right="+areaOrig);

          // if the sum of the three areas equals the original,
          // we're inside the triangle!
          boolean point_inside_triangle_check=area1 + area2 + area3 == areaOrig;  //VERSION ONE

          float epsilon=0.01;
          point_inside_triangle_check = abs(area1 + area2 + area3 - areaOrig)<epsilon;  //VERSION TWO


          if (point_inside_triangle_check) 
          {
            return true;
          }
          return false;
        }

        boolean triPoint(int _mx, int _my) {

          float ax = screenX(A.x, A.y);
          float ay = screenY(A.x, A.y);
          float bx = screenX(B.x, B.y);
          float by = screenY(B.x, B.y);
          float cx = screenX(C.x, C.y);
          float cy = screenY(C.x, C.y);


          return triPoint(ax, ay, bx, by, cx, cy, _mx, _my);
        }
      }

djevazi

Very Big Thanks for your help! Works perfectly with epsilon value 0.1 . I'm happy : )