- 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 =)
Bookmarks