Page 1 of 2 12 LastLast
Results 1 to 10 of 14

Thread: Ray and convex polygon intersection

  1. #1

    Ray and convex polygon intersection

    Does anyone have code for ray and convex polygon intersection? I have ray-triangle, but the code goes a little over my head partially.
    http://code.google.com/p/nxpascal/so...Math3D.pas#428

    We can assume a few things...
    Header:
    Code:
      TWordArray = array[0..0] of word;
      PWordArray = ^TWordArray;
    
    function RayPolyIntersect(const rayStart, rayDirection: TVector;
      const vi: PWordArray; Count: integer; BothSided: boolean;
      intersect: PVector; intersectNormal: PVector): Boolean;
    - vi[] is index array to face vertices.
    - Polygon is flat. If it's really not, it will still be treated as flat. Function can estimate it close enough.
    - Polygon is convex. It is the only type of polygon you will see on 3D-models, ever.

    On little theory, i would assume it go like this:
    - We can get the intersection point, something like ray-plane intersect.
    - Then somehow with crossproduct and dotproduct, we would determine if intersection point is outside the polygon.
    Last edited by User137; 20-01-2013 at 06:11 PM.

  2. #2
    I can think of a couple of solutions right away:
    1 - triangulate the polygon (not very easy), then look for intersection with each triangle.
    2 - find the plane of the polygon (you can use any 3 points of the polygon to do that). find the intersection with that plane (easy enough). now the intersection point and the polygon are all on the same plane. project the intersection point and the polygon onto the 2d plane. find if the intersection point is inside the polygon in 2d space (easy enough).

  3. #3
    1. It would be very easy. I just use vertex 0 as common point, and then radially go through the polygon edges. (0,2,1), (0,3,2), .. (0,n-1,n-2). I thought i might do this for testing purpose, but it would be slower than optimized function.
    2. I don't know how to do the projection, and even so, wouldn't it use the same vector math as 3D? I don't imagine we would need to go for angles with this problem at least.

  4. #4
    PGDCE Developer Carver413's Avatar
    Join Date
    Jun 2010
    Location
    Spokane,WA,Usa
    Posts
    206
    http://chiselapp.com/user/badsector/...y/rtworld/home
    look in the maths.pas there might be something useful

  5. #5
    PGD Staff / News Reporter phibermon's Avatar
    Join Date
    Sep 2009
    Location
    England
    Posts
    524
    Are you working in 2D or 3D? your statement that models only include convex polygons is incorrect, at the highest order a triangle is convex in flat euclidean space but concave in curved space in comparison.

    Anyway, a model can be made up of concave elements including individual concave faces, And that's not even going into curved manifolds.

    Because *most* hardware is only suitable for rendering 3 sided polytope (triangles) 3D data will normally be tessellated into triangles, either by a 3rd party process (export from/function in from your favorite modeler) or in your engine before the resultant data is uploaded to graphics memory.

    Now the distinction between the data and it's representation here is that you may want to retain faces with more than 3 sides (like a professional modeler would) but need to tessellate in order to display.

    If you're not bothered about loosing information then tessellate and be done with it.

    As you'd want to know exactly where on the model your ray would intersect, you're going to have to test against all the front facing polygons (from the rays origin) as these will most likely be triangles, your problem has now become 'Ray - Triangle Intersection' which you'll find in any basic maths textbook.

    Such tests should be optimized by performing a bounding volume check on the given model first (or bounding volume on some tree nodes etc whatever makes sence with the data you're rendering) and further optimized by using some form of spatial partitioning (oct-tree/bsp etc) and their corresponding ray-cast optimizations, if you have many separate elements to test against.

    Obviously, you'll need to ensure that your vertex winding is the same for all faces on a model otherwise you'll run into problems fast. (this should be be the case anyway from any half serious 3D modeling application)

    And then you just itterate thru the faces and test every single one.

    Some modeling programs employ spatial partitioning with the vertices/faces of the model itself, such applications include BSP map editors where the geometry is sparse and can benefit from such optimizations. Also programs like Z-Brush which deal with highly complex models also use partitioning schemes to speed up operations.

    But from the 3D game, models and maps kind of setup, it's rare that you'll see partitioning used past the 'map' paradigm.

    There exists screen-space solutions to collision detection as well, some people use OpenGL picking for example, rendering individual polygons with different unique colours to some off-screen buffer then sampling the pixel at projected screen coordinates of the ray. Then by taking the colour value, determine the polygon. This is a perfectly viable method but becomes increasingly uneconomical from a pre-processing perspective the more data you wish to operate on and doesn't instantly provide you with information such as the normal of the face the ray hits.

    So I'd recommend classic ray-triangle intersection, optimized with spatial partitioning and testing only front facing polygons.
    When the moon hits your eye like a big pizza pie - that's an extinction level impact event.

  6. #6
    Quote Originally Posted by phibermon View Post
    Are you working in 2D or 3D? your statement that models only include convex polygons is incorrect, at the highest order a triangle is convex in flat euclidean space but concave in curved space in comparison.
    I'm building new version of my 3D-modelling software. As far as polygons go, it uses GL_POLYGON for rendering. That often looks bugged with concave. Well, simply put i will never support concaves, nor should anyone. If i want to make a "+" sign (hospital mark), i will build the front face from 5 quads.

    I'm not ready to go for pixel color testing at this point, it would need much more work, and i wouldn't get intersection and normal data (i will need it). Also if i'd use ray-triangle for this, there would always be 1 or 2 unneeded test on the internal edges. So it's slower. The function is also counting intersection, normal and culling check with each triangle... So i'd still need to make unique ray-triangle algorithm for polygon only. I could also calculate the face normal once, and use that for all the edges crossproduct math together. All in all, it would be much more optimal to make a real ray-poly function.

    Quote Originally Posted by Carver413 View Post
    http://chiselapp.com/user/badsector/...y/rtworld/home
    look in the maths.pas there might be something useful
    That code went with the "easy way" for checking polygon as triangles.
    Last edited by User137; 21-01-2013 at 02:39 AM.

  7. #7
    - Polygon is convex. It is the only type of polygon you will see on 3D-models, ever.
    sorry I missed that point. so yes it would be very easy to triangulate the polygon then. but I still think that 2d projection would be faster especially for a polygon with a large number of edges.
    I played around with it for a few minutes and here's what I came up with:

    Code:
    function RayVsFlayPoly3D(const r: TG2Ray; const v0: PG2Vec3; const vc: Integer; const Intersection: PG2Vec3): Boolean;
      var Hit: TG2Vec3;
      var va: PG2Vec3Array;
      var Plane: TG2Plane;
      var d: Single;
      var vx, vy: TG2Vec3;
      var pi, pj: PG2Vec3;
      var Hit2, v2, pi2, pj2: TG2Vec2;
      var i: Integer;
    begin
      Result := False;
      if vc < 3 then Exit; //no need to proceed if we have less than 3 points.
      va := PG2Vec3Array(v0);
      Plane.SetPlane(va^[0], va^[1], va^[2]);
      //params: 
      //0 - plane to find intersection with; 
      //1 - check both sides of the plane; 
      //2 - returns the distance form the origin of the ray to the point of intersection
      if r.IntersectPlane(Plane, True, d) then 
      Hit := r.Origin + r.Dir * d
      else
      Exit; // the ray is parallel to the polygons plane. quit
      vx := (va^[1] - va^[0]).Normalized;
      vy := Plane.N.Cross(vx).Normalized;
      // vx and vy are the 2d space projection vectors.
      Hit2.SetValue(vx.Dot(Hit), -vy.Dot(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^[vc - 1];
      pj2.SetValue(vx.Dot(pj^), -vy.Dot(pj^));
      for i := 0 to vc - 1 do
      begin
        pi := @va^[i];
        pi2.SetValue(vx.Dot(pi^), -vy.Dot(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.SetValue(vx.Dot(pj^), -vy.Dot(pj^));
      end;
      if Result and (Intersection <> nil) then
      Intersection^ := Hit;
    end;
    it uses some types and functions from my math library but nothing too complicated, let me know if you need help with that.

    it even works with non convex polygons. here's the proof http://gen2gdk.com/files/RayVsFlatPoly3D.rar =)
    Last edited by Dan; 21-01-2013 at 10:41 AM.

  8. #8
    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:
    Code:
    // 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;
    Last edited by User137; 21-01-2013 at 12:53 PM. Reason: Optimized code

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

  10. #10
    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.

Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •