Page 1 of 1

Raycast

Posted: Sun Mar 08, 2009 4:55 pm
by Kjell
8)

For those that don't want to wait for BeRo's physics implementation .. a basic Raycast ( Ray VS Triangle ) Library. Use in combination with the Matrix Library when dealing with rotated objects.

*Since ZGE rounds off values with more then 3 decimals, 0.001 is the lowest Epsilon you can use .. ( otherwise you'd want to go with something like 0.00001 ).

*Returns the collision state / bool, so you have to pull out the variables to calculate the intersection point / normal yourself.

Code: Select all

void Sub(int K,
         float X1, float Y1, float Z1,
         float X2, float Y2, float Z2)
{
  Vector[K,0] = X1-X2;
  Vector[K,1] = Y1-Y2;
  Vector[K,2] = Z1-Z2;
}

//

void Cross(int K,
           float X1, float Y1, float Z1,
           float X2, float Y2, float Z2)
{
  Vector[K,0] = Y1*Z2-Z1*Y2;
  Vector[K,1] = Z1*X2-X1*Z2;
  Vector[K,2] = X1*Y2-Y1*X2;
}

//

float Dot(float X1, float Y1, float Z1,
          float X2, float Y2, float Z2)
{
  return X1*X2+Y1*Y2+Z1*Z2;
}

//

int RayTriangle(float OX, float OY, float OZ,
                float DX, float DY, float DZ,
                float X1, float Y1, float Z1,
                float X2, float Y2, float Z2,
                float X3, float Y3, float Z3)
{
  float R, S, T, U, V;

  Sub(1,X2,Y2,Z2,X1,Y1,Z1);
  Sub(2,X3,Y3,Z3,X1,Y1,Z1);
  
  Cross(3,DX,DY,DZ,Vector[2,0],Vector[2,1],Vector[2,2]);

  R = Dot(Vector[1,0],Vector[1,1],Vector[1,2],Vector[3,0],Vector[3,1],Vector[3,2]);

  Sub(4,OX,OY,OZ,X1,Y1,Z1);
  S = 1/R;
  
  Cross(5,Vector[4,0],Vector[4,1],Vector[4,2],Vector[1,0],Vector[1,1],Vector[1,2]);
  
  if(R <= Epsilon && R >= Epsilon*-1)
  {
    return 0;
  }
  else
  {
    if(R > Epsilon)
    {
      Debug = U;
      U = Dot(Vector[4,0],Vector[4,1],Vector[4,2],Vector[3,0],Vector[3,1],Vector[3,2]);
      if(U < 0 || U > R)
      {
        return 0;
      }

      V = Dot(DX,DY,DZ,Vector[5,0],Vector[5,1],Vector[5,2]);
      if(V < 0 || U+V > R)
      {
        return 0;
      }
    }

    if(R < Epsilon*-1)
    {
      U = Dot(Vector[4,0],Vector[4,1],Vector[4,2],Vector[3,0],Vector[3,1],Vector[3,2]);
      if(U > 0 || U < R)
      {
        return 0;
      }

      V = Dot(DX,DY,DZ,Vector[5,0],Vector[5,1],Vector[5,2]);
      if(V > 0 || U+V < R)
      {
        return 0;
      }
    }
  }
  
  T = Dot(Vector[2,0],Vector[2,1],Vector[2,2],Vector[5,0],Vector[5,1],Vector[5,2]);
  U *= S;
  V *= S;
  
  return 1;
}
Attached is a simple example.

K

Posted: Tue Mar 10, 2009 2:32 pm
by jph_wacheski
these look very interesiting,. Unfortunatly I am far from understanding how to use this tech.,. the Matrix one does not run here, so I am not sure what to even try there,. and this one runs and I see a ray oscilating back and forth cast through a triangle,. however looking at the code it appears that it is supposed to turn red when it intersects however it does not?

Perhaps with a bit more explanation and practical example or two, myself and others could find this very usefull,. . this is a prime candidate for being encapsilated into a component!

Thanks for posting it,. when I have the time/mental energy I will have a go at figuring out how to make use of it,. I am using this;

Code: Select all

if(this.Vertex.X > 0)
{
  this.Vertex.X = 1;
  this.Vertex.Y = 0;
}
to make trangles for my vector game when stuff shaters,. ;) it's the simple things that amuse me eh,.

Posted: Tue Mar 10, 2009 3:07 pm
by Kjell
Hmm,

Strange .. I've attached a zip containing builds of both the Matrix and Raycast examples, can you check if those do work? Matrix should show a Quad rotating over all 3 axes with a indicator following one of the corners. Raycast shows a Ray oscillating over the X axis, pointing up ( Y ), changing length and turning red when it intersects the triangle positioned above.

The Raycast example is a bit of a hack actually, because you really want to use that function in combination with a Array of vertices ( but since this adds another layer of passing around variables, I thought it would be best to keep the example as simple as possible ).

*It's not that difficult to use though, the RayTriangle takes 15 arguments as you can see.

- Ray Origin X, Y, Z
- Ray Direction X, Y, Z
- Triangle Vertex 1 X, Y, Z
- Triangle Vertex 2 X, Y, Z
- Triangle Vertex 3 X, Y, Z

*Make sure to use counterclockwise direction.

K

Posted: Tue Mar 10, 2009 3:30 pm
by VilleK
Jph, also remember to use latest ZGE-release because Kjell found a couple of bugs in the script parser while working on this. The raycast-projects works here and the triangle turns red.

Posted: Tue Mar 10, 2009 9:26 pm
by jph_wacheski
Ahh, that is it then I should update my ZGE! cool,. see I was just quickly looking is all., . thanks for the extra info Kj I may get to understand it when I have a bit of time to mess around with it,. . looks quite useable really.

Posted: Thu Mar 12, 2009 5:29 pm
by kattle87
Can I ask you if you got it from somewhere, or what?
Since I tried to make one triangle-vs-ray collision today and I came up with the same exact code! :P The only different thing I came up with is tweaking the code to do a convex-polygon VS ray detection.

Posted: Thu Mar 12, 2009 6:28 pm
by Kjell
Hi Francesco,

Can't remember what references I used exactly, but this site ( pretty sure I posted this one before ) has links to information on all basic intersections. There are only a handful techniques you can use to pull of a Ray VS Tri intersection, so it's not strange that you ended up with the same solution :)

I tried to make this Library as basic / simple / understandable as possible. So once someone gets the hang of it, they can expand it to detect convex / concave sets of polygons, or ( something I do personally ) use a array containing a triangle list / strip / fan to pull all the data from ( and only pass the range of cells instead of individual vertices ) etc.

K

Posted: Mon Apr 20, 2009 1:06 pm
by jph_wacheski
Just sticking this link here for posterity,. I will try to figure a way to use Kjells code eventually,. just notice this version and wanted to link it here in case anyone is interested,. .

http://www.cs.lth.se/home/Tomas_Akenine ... i/raytri.c

Posted: Mon Apr 20, 2009 1:48 pm
by Kjell
:)

That's actually one of the examples I looked at when writing the library :wink:

K