Ray and convex polygon intersection

[User137]

Thanks, hope you don't mind if i include this in nxPascal? It works great, see:
https://docs.google.com/file/d/0B7FI...RwQVFMWDg/edit
I temporarily modified the model demo to use TPolyModel class, and this change will not remain in the actual demo. Not best example though, because the model consists only of triangles. But because that function treats triangles and polygons same way, i don't doubt that it wouldn't work.

I had to make a few changes to adapt the code to nxPascal and parameters. Also made sure it's compilable on fpc and delphi:

// Credits to Dan (PascalGameDev forums)
function TPolyModel.RayPolyIntersect(const rayStart,
  rayDirection: TVector; const vi: PWordArray; Count: integer;
  BothSided: boolean; intersect: PVector;
  intersectNormal: PVector): Boolean;
var d: Single; i: Integer;
    Hit, nn, vx, vy: TVector;
    pi, pj: PVector;
    Hit2, pi2, pj2: TVector2f;
begin
  Result:=False;
  if Count<3 then Exit; //no need to proceed if we have less than 3 points.
  vx:=Norm(VectorSub(va[vi[1]], va[vi[0]]));
  nn:=Norm(CrossProduct(vx, VectorSub(va[vi[2]], va[vi[0]])));
  // Exit if ray is coming from behind the triangle
  if (not BothSided) and (Dot(nn, rayDirection)>0) then exit;
  d:=RayPlaneIntersect(rayStart, rayDirection, va[vi[0]], nn,
     intersect);
  if d>=0 then Hit:=VectorAdd(rayStart, nxMath3D.Scale(rayDirection, d))
  else Exit; // the ray is parallel to the polygons plane. quit
  vy:=CrossProduct(nn, vx); // Don't need to norm(), length is 1
  // vx and vy are the 2d space projection vectors.
  Hit2:=Vector2f(Dot(vx, Hit), -Dot(vy, Hit));
  // and that's how you project a point to 2d space
  // and finally we're checking if the intersection point is inside the polygon.
  pj:=@va[vi[Count - 1]];
  pj2:=Vector2f(Dot(vx, pj^), -Dot(vy, pj^));
  for i := 0 to Count - 1 do begin
    pi := @va[vi[i]];
    pi2:=Vector2f(Dot(vx, pi^), -Dot(vy, pi^));
    if ( ((pi2.y<=Hit2.y) and (Hit2.y<pj2.y)) or
         ((pj2.y<=Hit2.y) and (Hit2.y<pi2.y)) ) and (
       Hit2.x < (pj2.x-pi2.x)*(Hit2.y-pi2.y)/(pj2.y-pi2.y)+pi2.x
       ) then
    Result:=not Result;
    pj:=pi;
    pj2:=Vector2f(Dot(vx, pj^), -Dot(vy, pj^));
  end;
  if intersectNormal<>nil then intersectNormal^:=nn;
end;

[Dan]

that demo looks nice. I am not sure though why you would want to use flat polygons instead of triangles.

[User137]

It's just for the modelling program mainly. All models are converted to triangles when it comes to games, for shaders and consistency. But while editing models, it is often times more effortless to deal with less faces. For example when editing a cube, i only need to deal with 6 faces instead of 12. Easier to do texturemapping, smoothing, extrude and so on.

[User137]

1 other optimization that i'm adding, is approximating the face normal better. It is possible that polygon is not entirely flat. (See attached image) I will be using the method on right. These indices can be count like:

p0 = 0
p1 = 1+Count div 5
p2 = Count-1-Count div 5

I figured that 5 vertex polygon is smallest one to benefit from this change. It is possible that 3 periodic vertices are in line formation too, and in that case, the left side method (0, 1, 2) would make a really bad normal approximation.

[Dan]

why not do this:
p0 = 0;
p1 = Count div 3;
p2 = Count * 2 div 3;
this will give you an even spread of plane base points across the entire polygon.
btw in your example this will give you exactly the same points as you have on the right picture.

[User137]

You're really good at math, and thanks again It wasn't straightforward to come up with pattern that cover all polygon sizes, including triangles.

The function works fine with triangles still, and it's now in use in the editor too. I hope the (0, 1, 2) vertices weren't necessary somehow for your projection formula, would guess no. Regards to projection, what did it actually do? It transforms vertices to plane of face normal's space? (that sounded weird) It's cool idea, and i noticed immediately how few calculations it's doing. Definitely much much faster than if dealing with normal way like 3D ray-triangle. Kind of genious.

[Dan]

yes that's pretty much how it works. all the vertices of the polygon and the intersection point are on the same plane, so project them and work with 2d instead of 3d.