PDA

View Full Version : Ray and convex polygon intersection

User137
20-01-2013, 05:54 PM
Does anyone have code for ray and convex polygon intersection? I have ray-triangle, but the code goes a little over my head partially.

We can assume a few things...

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.

Dan
20-01-2013, 06:19 PM
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).

User137
20-01-2013, 08:11 PM
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.

Carver413
20-01-2013, 10:26 PM
look in the maths.pas there might be something useful

phibermon
20-01-2013, 10:59 PM
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.

User137
21-01-2013, 02:31 AM
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.

look in the maths.pas there might be something useful
That code went with the "easy way" for checking polygon as triangles.

Dan
21-01-2013, 03:47 AM
- 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:

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

User137
21-01-2013, 12:23 PM
Thanks, hope you don't mind if i include this in nxPascal? :) It works great, see:
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
21-01-2013, 12:35 PM
that demo looks nice. I am not sure though why you would want to use flat polygons instead of triangles.

User137
21-01-2013, 12:58 PM
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
21-01-2013, 02:33 PM
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
21-01-2013, 04:26 PM
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
21-01-2013, 05:09 PM
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
21-01-2013, 06:50 PM
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.