I'm working on polygonal collision and need to find the point of intersection between a ray and a plane, and then whether it lies in a triangle.

If I were doing this in C++ it wouldn't be too hard since, if you include the correct libraries, you can have datatypes like "Vector" which store <x,y,z> and do functions such as DotProduct. Unfortunately, since Game Maker only has "real" and "string" it is much harder. I looked up tutorials on Google and found some but they all assume that you can store variables as <x,y,z>.

I need some help with going about this in Game Maker. I've written a script to convert the plane coordinates to Ax+By+Cz+D = 0 format, and save A, B, C, and D so that they don't have to be re-calculated each time the plane is needed. I've also written a script to check whether a point lies on, behind, or in front of a plane. But I'm stuck on converting r(t) = p + tD (plane to ray check) to something Game Maker can use. Also, I need some help with a script for checking whether the point lies in a triangle.

Any help?

# Ray To Plane Intersection

Started by Gumgo, Jan 21 2007 05:09 AM

3 replies to this topic

### #2

Posted 21 January 2007 - 10:24 PM

You can "make" your own data types by grouping the native data structures. For example, you could have a ds_list, with index 0 being a ds_queue and 1 a stack, and so forth. It's tedious, but efficent (afaik)

For the point-in-triangle check, this should do the trick

[codebox]/*

Checks whether a point is inside a triangle

inside_triangle(x0,y0,x1,y1,x2,y2,x3,y3)

arguments0-1: coordinates of the point

arguments2-7: coordinates of the triangle

Returns true if so, false if not

*/

return (abs(abs((argument2-argument0)*(argument5-argument1)-(argument4-argument0)*(argument3-argument1)) + abs((argument4-argument0)*(argument7-argument1)-(argument6-argument0)*(argument5-argument1)) + abs((argument6-argument0)*(argument3-argument1)-(argument2-argument0)*(argument7-argument1)) - abs((argument4-argument2)*(argument7-argument3)-(argument6-argument2)*(argument5-argument3))) <= 1 / 256);[/codebox]

For the point-in-triangle check, this should do the trick

[codebox]/*

Checks whether a point is inside a triangle

inside_triangle(x0,y0,x1,y1,x2,y2,x3,y3)

arguments0-1: coordinates of the point

arguments2-7: coordinates of the triangle

Returns true if so, false if not

*/

return (abs(abs((argument2-argument0)*(argument5-argument1)-(argument4-argument0)*(argument3-argument1)) + abs((argument4-argument0)*(argument7-argument1)-(argument6-argument0)*(argument5-argument1)) + abs((argument6-argument0)*(argument3-argument1)-(argument2-argument0)*(argument7-argument1)) - abs((argument4-argument2)*(argument7-argument3)-(argument6-argument2)*(argument5-argument3))) <= 1 / 256);[/codebox]

### #3

Posted 21 January 2007 - 11:08 PM

I think that's the longest line of code I've ever seen...

I don't quite understand what that would do... and every time you used the "variable" you'd have to use ds_list functions, and also that still doesn't solve the problem of defining what operators do to different data types.

Anyways... I need to return the point of intersection as well. Does it seriously take that much code just to write out r(t) = p + tD just using reals?

EDIT: I forgot to mention I made a script for dot product, anything needing that can just be written Dot(vx1,vy1,vz1,vx2,vy2,vz2).

EDIT2: Ok, I've figured out how to do the ray-to-plane part, here it is:

Now all I need is code to detect whether it actually hits the plane, because this gives coordinates no matter what, but I think I already have that. Now what I need is a script for whether the coordinates are in a triangle... or even better, the ray hits the triangle, because I can imagine that if I used coordinates, the script would always return false because of the limited accuracy on computers.

You can "make" your own data types by grouping the native data structures. For example, you could have a ds_list, with index 0 being a ds_queue and 1 a stack, and so forth. It's tedious, but efficent (afaik)

I don't quite understand what that would do... and every time you used the "variable" you'd have to use ds_list functions, and also that still doesn't solve the problem of defining what operators do to different data types.

Anyways... I need to return the point of intersection as well. Does it seriously take that much code just to write out r(t) = p + tD just using reals?

EDIT: I forgot to mention I made a script for dot product, anything needing that can just be written Dot(vx1,vy1,vz1,vx2,vy2,vz2).

EDIT2: Ok, I've figured out how to do the ray-to-plane part, here it is:

// arg0-2 = point on plane // arg3-5 = plane normal // arg6-8 = origin of ray // arg9-11 = line vector px = argument0; py = argument1; pz = argument2; nx = argument3; ny = argument4; nz = argument5; ox = argument6; oy = argument7; oz = argument8; dx = argument9; dy = argument10; dz = argument11; /* t = -((<ox,oy,oz> - <px,py,pz>) . <nx,ny,nz>)/(<dx,dy,dz> . <nx,ny,nz>) <pntx,pnty,pntz> = <ox,oy,oz> + t*<dx,dy,dz> */ t = -(Dot(ox-px,oy-py,oz-pz,nx,ny,nz)/Dot(dx,dy,dz,nx,ny,nz)); pX = ox + t*dx; pY = oy + t*dy; pZ = oz + t*dz;

Now all I need is code to detect whether it actually hits the plane, because this gives coordinates no matter what, but I think I already have that. Now what I need is a script for whether the coordinates are in a triangle... or even better, the ray hits the triangle, because I can imagine that if I used coordinates, the script would always return false because of the limited accuracy on computers.

**Edited by Gumgo, 22 January 2007 - 02:31 AM.**

### #4

Posted 22 January 2007 - 11:23 AM

If you have your ray-plane intersection working, the point-in-triangle test already posted is all you need. Even though it is two dimensional, you can still use it. Either use the screen coordinates of the points, or simply throw out one of the dimensions, x, y, or z. Usually you'd toss out the one with the smallest extent.

For instance:

extentX = max(x1,x2,x3)-min(x1,x2,x3);

extentY = max(y1,y2,y3)-min(y1,y2,y3);

extentZ = max(z1,z2,z3)-min(z1,z2,z3);

The dimension you should ignore is indicated by whichever of extentX, extentY, extentZ is the smallest.

For instance:

extentX = max(x1,x2,x3)-min(x1,x2,x3);

extentY = max(y1,y2,y3)-min(y1,y2,y3);

extentZ = max(z1,z2,z3)-min(z1,z2,z3);

The dimension you should ignore is indicated by whichever of extentX, extentY, extentZ is the smallest.

**Edited by xot, 22 January 2007 - 11:52 AM.**

GMLscripts.com, rise from your grave!

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.