# Line - Shape Collisions

64 replies to this topic

### #1 Tepi

Tepi

GMC Member

• Global Moderators
• 4201 posts
• Version:GM8.1

Posted 17 January 2009 - 05:26 PM

These scripts are meant to check if a line collides with various GM's pre-defined shapes.

The shape is defined with the same arguments as the one in its draw code (x1,y1,z1,x2,y2,z2). The line is defined by point (x0,y0,z0) and vector (dx,dy,dz), where the point is any point on the line, and the vector is the line's direction vector. For example, a line going through points (x3,y3,z3) and (x4,y4,z4), the point would be (x3,y3,z3) and the vector (x4-x3,y4-y3,z4-z3).

The scripts automatically transform the line into a ray. The difference between these is that the line continues to the opposite side of the vector. In order to transform this back to checking for lines, delete the line in the script that says "This line makes it a ray".

Now there are also available additional codes that will find the point of intersection and the surface normal at that. See post #21.

Now you can also download and import all the scripts at the same time in the form of this gmres file. The scripts have their additional code for the point of intersection and surface normal in them by default.

If you have problems using these scripts, you can check out This example. It explains how to use the scripts.

Line - block:
`///////////////////////////////////////////////////////////////////////////// Description: This script returns true if the line intersects the block.//// arguments: (x1, y1, z1, x2, y2, z2, x0, y0, z0, dx, dy, dz)// The line is given in form (x0 + dxt, y0 + dyt, z0 + dzt), t is any real.//////////////////////////////// ~ Tepi  //////////////////////////////////{    var  a, b, c, xx, yy, zz, Dx, Dy, Dz, d;    a  = abs(argument3 - argument0)/2;    b  = abs(argument4 - argument1)/2;    c  = abs(argument5 - argument2)/2;    xx = (argument3 + argument0)/2 - argument6;    yy = (argument4 + argument1)/2 - argument7;    zz = (argument5 + argument2)/2 - argument8;    Dx = argument9;     if (Dx == 0)  {Dx = .000001;}    Dy = argument10;    if (Dy == 0)  {Dy = .000001;}    Dz = argument11;    if (Dz == 0)  {Dz = .000001;}    d  = sqrt(Dx*Dx + Dy*Dy + Dz*Dz); //The direction vector's magnitude    Dx /= d;    Dy /= d;    Dz /= d;  //Normalizing the direction vector    return  (       (abs(yy - Dy * (xx + a) / Dx) <= b    &&  abs(zz - Dz * (xx + a) / Dx) <= c)    || (abs(yy - Dy * (xx - a) / Dx) <= b    &&  abs(zz - Dz * (xx - a) / Dx) <= c)    || (abs(xx - Dx * (yy + b) / Dy) <= a    &&  abs(zz - Dz * (yy + b) / Dy) <= c)    || (abs(xx - Dx * (yy - b) / Dy) <= a    &&  abs(zz - Dz * (yy - b) / Dy) <= c)    || (abs(xx - Dx * (zz + c) / Dz) <= a    &&  abs(yy - Dy * (zz + c) / Dz) <= b)    || (abs(xx - Dx * (zz - c) / Dz) <= a    &&  abs(yy - Dy * (zz - c) / Dz) <= b)    && (xx*Dx + yy*Dy + zz*Dz >= 0)        //This line makes it a ray    )}`

Line - ellipsoid:
`///////////////////////////////////////////////////////////////////////////// Description: This script returns true if the line intersects ellipsoid.//// arguments: (x1, y1, z1, x2, y2, z2, x0, y0, z0, dx, dy, dz)// The line is given in form (x0 + dxt, y0 + dyt, z0 + dzt), t is any real.//////////////////////////////// ~ Tepi  //////////////////////////////////{    var  a, b, c, Dx, Dy, Dz, A, B, C, x0, y0, z0, d;    a  = sqr(argument3 - argument0)/4;    b  = sqr(argument4 - argument1)/4;    c  = sqr(argument5 - argument2)/4;    x0 = argument6 - (argument3 + argument0)/2;    y0 = argument7 - (argument4 + argument1)/2;    z0 = argument8 - (argument5 + argument2)/2;    Dx = argument9;    if (Dx == 0) Dx = .000001;    Dy = argument10;   if (Dy == 0) Dy = .000001;    Dz = argument11;   if (Dz == 0) Dz = .000001;        d  = sqrt(Dx*Dx + Dy*Dy + Dz*Dz);  //The direction vector's magnitude    Dx /= d;    Dy /= d;    Dz /= d;   //Normalizing the direction vector     A = Dx * Dx / a  +  Dy * Dy / b  +  Dz * Dz / c;    B = Dx * x0 / a  +  Dy * y0 / b  +  Dz * z0 / c;    C = x0 * x0 / a  +  y0 * y0 / b  +  z0 * z0 / c - 1;    C = B * B  -  A * C;    if  (C < 0)  {return 0;}    //<point of intersection and normal finding code goes here>    if  (sqrt(C ) + B)/A  >= 0  {return 0;}   //This line makes it a ray        return 1;    }`

Line - cone:
`///////////////////////////////////////////////////////////////////////////// Description: This script returns true if the line intersects the cone.//// arguments: (x1, y1, z1, x2, y2, z2, x0, y0, z0, dx, dy, dz)// The line is given in form (x0 + dxt, y0 + dyt, z0 + dzt), t is any real.//////////////////////////////// ~ Tepi  //////////////////////////////////{    var  a, b, c, Dx, Dy, Dz, A, B, C, x0, y0, z0, d;    a  =  sqr(argument3 - argument0)/4;    b  =  sqr(argument4 - argument1)/4;    c  =     (argument5 - argument2);    x0 = argument6 - (argument3 + argument0)/2;    y0 = argument7 - (argument4 + argument1)/2;    z0 = argument8 -  argument5;    Dx = argument9;    if (Dx == 0) Dx = .000001;    Dy = argument10;   if (Dy == 0) Dy = .000001;    Dz = argument11;   if (Dz == 0) Dz = .000001;        d  = sqrt(Dx*Dx + Dy*Dy + Dz*Dz); //The direction vector's magnitude    Dx /= d;    Dy /= d;    Dz /= d;  //Normalizing the direction vector     A = Dx * Dx / a  +  Dy * Dy / b  -  Dz * Dz / c / c;    B = Dx * x0 / a  +  Dy * y0 / b  -  Dz * z0 / c / c;    C = x0 * x0 / a  +  y0 * y0 / b  -  z0 * z0 / c / c;    C = B*B - A*C;    if  (C < 0)  {return 0;}    //<point of intersection and normal finding code goes here>            if  (z0/c + 1 <= 0) {A = (-B + sqrt( C))/A;} else {A = (-B - sqrt( C))/A;}    if  (A < 0)   {return 0;}          //This line makes it a ray        return  (abs( 0.5 + (A * Dz + z0)/c ) <=  0.5);    }`

Line - cylinder:
`///////////////////////////////////////////////////////////////////////////// Description: This script returns true if the line intersects cylinder.//// arguments: (x1, y1, z1, x2, y2, z2, x0, y0, z0, dx, dy, dz)// The line is given in form (x0 + dxt, y0 + dyt, z0 + dzt), t is any real.//////////////////////////////// ~ Tepi  //////////////////////////////////{    var  a, b, c, Dx, Dy, Dz, A, B, C, x0, y0, z0, d;    a  =  sqr(argument3 - argument0)/4;    b  =  sqr(argument4 - argument1)/4;    c  =     (argument5 - argument2)/2;    x0 = argument6 - (argument3 + argument0)/2;    y0 = argument7 - (argument4 + argument1)/2;    z0 = argument8 -  argument5;    Dx = argument9;    if (Dx == 0) Dx = .000001;    Dy = argument10;   if (Dy == 0) Dy = .000001;    Dz = argument11;   if (Dz == 0) Dz = .000001;        d  = sqrt(Dx*Dx + Dy*Dy + Dz*Dz); //The direction vector's magnitude    Dx /= d;    Dy /= d;    Dz /= d;  //Normalizing the direction vector     A = Dx * Dx / a  +  Dy * Dy / b;    B = Dx * x0 / a  +  Dy * y0 / b;    C = x0 * x0 / a  +  y0 * y0 / b  -  1;    C = B*B - A*C;    if  (C < 0)  {return 0;}    if  (z0/c + 2 <= 0) {x0 = (-B + sqrt( C))/A;} else {x0 = (-B - sqrt( C))/A;}    if  (z0/c >= 0)     {y0 = (-B + sqrt( C))/A;} else {y0 = (-B - sqrt( C))/A;}    if  (x0 < 0)   {return 0;}        //This line makes it a ray    //<point of intersection and normal finding code goes here>        return  ((x0 * Dz + z0)/c >= -2                     &&  (y0 * Dz + z0)/c <= 0);                     }`
Line - floor
`///////////////////////////////////////////////////////////////////////////// Description: This script returns true if the line intersects a floor.//// arguments: (x1, y1, z1, x2, y2, z2, x0, y0, z0, dx, dy, dz)// The line is given in form (x0 + dxt, y0 + dyt, z0 + dzt), t is any real.//////////////////////////////// ~ Tepi  //////////////////////////////////{    var  xx, yy, zz, Dx, Dy, Dz, x0, y0, z0, d;    xx = argument3 - argument0;    yy = argument4 - argument1;    zz = argument5 - argument2;    x0 = argument6 - argument0;    y0 = argument7 - argument1;    z0 = argument8 - argument2;    Dx = argument9;    if (Dx == 0) Dx = .000001;    Dy = argument10;   if (Dy == 0) Dy = .000001;    Dz = argument11;   if (Dz == 0) Dz = .000001;        d  = sqrt(Dx*Dx + Dy*Dy + Dz*Dz); //The direction vector's magnitude    Dx /= d;    Dy /= d;    Dz /= d;  //Normalizing the direction vector     d = (zz * Dx  -  xx * Dz);    if  (d == 0)   return 0;    d = (xx * z0  -  zz * x0)/d;    if  (d <= 0)   return 0;          //This line makes it a ray    //<point of intersection and normal finding code goes here>    return  ((abs(2*(x0 + Dx*d) - xx) <= abs(xx)  || abs(xx) < .001)    &&        abs(2*(y0 + Dy*d) - yy) <= abs(yy)    &&       (abs(2*(z0 + Dz*d) - zz) <= abs(zz)  || abs(zz) < .001));}`
Line - wall
`///////////////////////////////////////////////////////////////////////////// Description: This script returns true if the line intersects a wall.//// arguments: (x1, y1, z1, x2, y2, z2, x0, y0, z0, dx, dy, dz)// The line is given in form (x0 + dxt, y0 + dyt, z0 + dzt), t is any real.//////////////////////////////// ~ Tepi  //////////////////////////////////{    var  xx, yy, zz, Dx, Dy, Dz, x0, y0, z0, d;    xx = argument3 - argument0;    yy = argument4 - argument1;    zz = argument5 - argument2;    x0 = argument6 - argument0;    y0 = argument7 - argument1;    z0 = argument8 - argument2;    Dx = argument9;             if (Dx == 0) Dx = .000001;    Dy = argument10;            if (Dy == 0) Dy = .000001;    Dz = argument11;            if (Dz == 0) Dz = .000001;        d  = sqrt(Dx*Dx + Dy*Dy + Dz*Dz); //The direction vector's magnitude    Dx /= d;    Dy /= d;    Dz /= d;  //Normalizing the direction vector     d = (yy * Dx  -  xx * Dy);    if  (d == 0)   return 0;    d = (xx * y0  -  yy * x0)/d;    if  (d <= 0)   return 0;          //This line makes it a ray    //<point of intersection and normal finding code goes here>    return  ((abs(2*(x0 + Dx*d) - xx) <= abs(xx)  || abs(xx) < .001)    &&       (abs(2*(y0 + Dy*d) - yy) <= abs(yy)  || abs(yy) < .001)    &&        abs(2*(z0 + Dz*d) - zz) <= abs(zz));}`

The technique behind the block - line was to represent the block and the line algebrally*; as block=(|{center}-{point}| <= {axis}) and line=({point} = {linepoint}+{vector}*t), where t is any number. When solved for t, three (for x,y and z) possible intervals of t are found, and the satisfying values of t are obviously in the intersection of all those. In any case, atleast one of the interval 'endpoints' is inside that region. And those are the only t values that need to be checked. The values are integrated in the expressions for efficiency.

*"algebrally" is a new word I found. It makes this topic come as the first results of Google search for "algebrally", so it makes this topic unique. Well... in reality it is an equivalent to algebraically. Lol.

All the other ones were done in same algebral way, but for these I needed to yield shape equations I didn't know of. A great example of this is cone. Luckily the ellipse's equation was there to help to make some assumptions.

I don't think that I'll add line - wall or line - floor because those are rather obvious. Line - wall and Line - floor -collisions are added. The specific values of .001 to compare are precision limits in order of magnitude in my gm6 tests. Any smaller value differences between point coordinates result in unstable precision. Because of this change, most if not all floors and walls approximately parallel to x-y-plane or y-z-plane will not cause problems.

EDIT: I noticed a significant problem in Line - cone and Line - cylinder -scripts. They were only working in certain values of z1 and z2. However, now this problem is fixed.

EDIT2: Fixed another variable cc bug in Line - cone. All users are adviced to update their copies to these newly edited ones.

If you have any ideas to improve these by optimization or such, let me know. You could also let me know if you find important use for them. Have fun.

Edited by Tepi, 25 June 2012 - 04:20 PM.

• 5

### #2 flexaplex

flexaplex

GMC Member

• Global Moderators
• 4809 posts
• Version:GM8

Posted 17 January 2009 - 06:53 PM

Do you not want to do the non-zero check before the d calculation so d will also not be 0? Also you can just return that statement outcome straight instead of using an if statement:

PRE
```{
var  a, b, c, xx, yy, zz, Dx, Dy, Dz;

a  = abs(argument3 - argument0)/2;
b  = abs(argument4 - argument1)/2;
c  = abs(argument5 - argument2)/2;
xx = (argument3 + argument0)/2 - argument6;
yy = (argument4 + argument1)/2 - argument7;
zz = (argument5 + argument2)/2 - argument8;
Dx = argument9;     if (Dx == 0)  {Dx = .000001;}
Dy = argument10;    if (Dy == 0)  {Dy = .000001;}
Dz = argument11;    if (Dz == 0)  {Dz = .000001;}

d  = sqrt(Dx*Dx + Dy*Dy + Dz*Dz); //The direction vector's magnitude
Dx /= d;    Dy /= d;    Dz /= d;  //Normalizing the direction vector

return
(abs(yy - Dy * (xx + a) / Dx) <= b &&  abs(zz - Dz * (xx + a) / Dx) <= c)
|| (abs(yy - Dy * (xx - a) / Dx) <= b &&  abs(zz - Dz * (xx - a) / Dx) <= c)
|| (abs(xx - Dx * (yy + b) / Dy) <= a &&  abs(zz - Dz * (yy + b) / Dy) <= c)
|| (abs(xx - Dx * (yy - b) / Dy) <= a &&  abs(zz - Dz * (yy - b) / Dy) <= c)
|| (abs(xx - Dx * (zz + c) / Dz) <= a &&  abs(yy - Dy * (zz + c) / Dz) <= b)
|| (abs(xx - Dx * (zz - c) / Dz) <= a &&  abs(yy - Dy * (zz - c) / Dz) <= b)
&& (xx*Dx + yy*Dy + zz*Dz >= 0)        //This line makes it a ray
}```

ps when was the copy/pasting issue with the PRE tag fixed?? I've only just noticed.

Edited by flexaplex, 17 January 2009 - 07:07 PM.

• 1

### #3 Tepi

Tepi

GMC Member

• Global Moderators
• 4201 posts
• Version:GM8.1

Posted 17 January 2009 - 11:41 PM

Thanks flexaplex, I didn't come to think it like that.

I think I won't do a non-zero check for d. The line is fully user-defined, and if the user has defined it by a null vector, it's not a line at all. It's his error, not the script's.

I think I'll transform this topic into a collection of line - shape collisions with all gm's pre-defined shapes. It was easy enough for ellipsoid, cylinder and cone, so I worked out the formulas ready an hour ago. I might then post an example with using all of them. This is especially useful for instant shooting, checking whether the mouse hovers on an object or checking whether it's realistic to draw a lens flare.

The time of checking these with for-loops is over!
• 1

### #4 slayer 64

slayer 64

GMC Member

• GMC Member
• 3278 posts
• Version:GM8.1

Posted 18 January 2009 - 12:35 AM

that example will be great. nice code.
• 0

### #5 Tepi

Tepi

GMC Member

• Global Moderators
• 4201 posts
• Version:GM8.1

Posted 20 January 2009 - 09:15 PM

that example will be great. nice code.

Thanks.

The topic is edited. I now have scripts for all line - shape -collisions for blocks, cylinders, cones and ellipsoids. The scripts are tested, but if you come across any problems, let me know.

P.s. Don't expect an example though, I might be too lazy to make that. These are relatively easy to use.
• 0

### #6 Pie Person!

Pie Person!

GM 6+ Lover

• GMC Member
• 1973 posts

Posted 20 January 2009 - 10:35 PM

Sweet Tepi. Good work!
• 0

### #7 Tepi

Tepi

GMC Member

• Global Moderators
• 4201 posts
• Version:GM8.1

Posted 26 January 2009 - 02:17 PM

I just noticed an old topic asking for mouse collisions to walls. So I ask you guys, should I actually make scripts for checking line - wall and line - floor also? Are they needed?

Sweet Tepi. Good work!

Thanks.
• 0

### #8 IamCalle

IamCalle

GMC Member

• GMC Member
• 444 posts

Posted 30 January 2009 - 09:58 PM

Yes you should, because you have included the other shapes, and I think line - wall and line - floor will come in handy for several users through out time. :]
I think they are needed, yes.

Edited by IamCalle, 31 January 2009 - 12:20 AM.

• 0

### #9 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14392 posts
• Version:GM:Studio

Posted 31 January 2009 - 05:43 AM

I just noticed an old topic asking for mouse collisions to walls. So I ask you guys, should I actually make scripts for checking line - wall and line - floor also? Are they needed?

Sweet Tepi. Good work!

Thanks.

Yes, both are needed... Is there a way to include rotation of the object in your scripts?

How about a range so to turn it into a ray trace so I can check for a floor below my feet (from my head to my feet) or check if a lazer hits a wall at a maximum of 200 units...

Setting cross_product global variables and point of intersect x,y,z would be nice too,
• 0

### #10 Tepi

Tepi

GMC Member

• Global Moderators
• 4201 posts
• Version:GM8.1

Posted 31 January 2009 - 09:03 PM

Yes you should, because you have included the other shapes, and I think line - wall and line - floor will come in handy for several users through out time. :]
I think they are needed, yes.

Ok. Well line - floor is done (yet not posted) and I'm working on line - wall.

Is there a way to include rotation of the object in your scripts?

Yes, but it's better to do that by actually rotating the line, rather than the shape. That is easy if you know how to rotate a vector. The rotated vector (x,y) around angle is ( cos(angle)*x - sin(angle)*y, sin(angle)*x + cos(angle)*y ). Therefore the line (x0+dx*t, y0+dy*t, z0+dz*t) to be used would become (x0n+dxn*t, y0n+dyn*t, z0n+dzn*t), where:
```x0n = cos(angle)*x0 - sin(angle)*y0;
y0n = sin(angle)*x0 + cos(angle)*y0;
dxn = cos(angle)*dx - sin(angle)*dy;
dyn = sin(angle)*dx + cos(angle)*dy;```
This is for a rotation about z-axis. Other rotations can be done by using other axes in the place of x- and y-axes. For example for y-rotation (around x-z-plane) you'd use (x,y) as (x-z): in other words, change all y's to z's.

How about a range so to turn it into a ray trace so I can check for a floor below my feet (from my head to my feet) or check if a lazer hits a wall at a maximum of 200 units...

I'm not sure if I'm getting you here. Checking for the shortest distance from the shape is rather difficult, so I thinnk I won't add that factor.

Setting cross_product global variables and point of intersect x,y,z would be nice too,

Cross-product? Where can you see a cross-product? Anyway, the point of intersection is there already hidden. For block it is more difficult to find, but for all the others it's (-B - C)/A and (-B + C)/A.
• 1

### #11 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14392 posts
• Version:GM:Studio

Posted 31 January 2009 - 10:49 PM

Setting cross_product global variables and point of intersect x,y,z would be nice too,

Cross-product? Where can you see a cross-product? Anyway, the point of intersection is there already hidden. For block it is more difficult to find, but for all the others it's (-B - C)/A and (-B + C)/A.

If you do a line collision with a box, you could tell me the vector of the face(t) the line intersects. With a sphere (you don't have one) or cone, you could "guestimate a vector" these would be used to smooth walk arround the obstacle... Or climb a cone smooth walk around a block...

As for the distance, I guess i'm really asking for the x,y,z of the intersect point

So, basically, I suggest your script set a few variable (global or local) to help use along here

__x,__y__z coord of the intersect point and a
__dx,__dy,__dz direction vector of the "facet" I intersect

I can always normalise the vectors

You could also provide a helper script to flip the line's x,y,z,dx,dy,dz so to indirectly support object rotation, as your suggested... Rotation has many variations so I guess a few scripts would be needed there... rx,ry,rz... rz,rx,ry are the 2 I have seen thus far...

You can't provide these nice scripts while excluding these basic requirements right . I figured how to find a facet on a model in my GMModelFix but I swear I was praying the math gods to help me figure the right x,y,z dx,dy,dz... Thank god the model was always centered on 0,0,0 though.
• 0

### #12 Tepi

Tepi

GMC Member

• Global Moderators
• 4201 posts
• Version:GM8.1

Posted 01 February 2009 - 08:37 PM

Setting cross_product global variables and point of intersect x,y,z would be nice too,

Cross-product? Where can you see a cross-product? Anyway, the point of intersection is there already hidden. For block it is more difficult to find, but for all the others it's (-B - C)/A and (-B + C)/A.

If you do a line collision with a box, you could tell me the vector of the face(t) the line intersects. With a sphere (you don't have one) or cone, you could "guestimate a vector" these would be used to smooth walk arround the obstacle... Or climb a cone smooth walk around a block...

That's actually quite useful idea. You could of course figure out the normal (yeah, normal is what you mean) from the point of intersection though. But I'll add that functionality when I get few things clear...

There are at most two solutions for both point of intersection and normal. This is obviously because the line crosses one surface when it goes inside the shape and another one when it exits the shape. So the question is: if and when there are two solutions, should I return both or only the one that's nearest to the camera?

By the way, there's no need for 'guestimating' the normal with ellipsoids, or any other shapes at all. It just requires some differential calculus.

You could also provide a helper script to flip the line's x,y,z,dx,dy,dz so to indirectly support object rotation, as your suggested... Rotation has many variations so I guess a few scripts would be needed there... rx,ry,rz... rz,rx,ry are the 2 I have seen thus far...

Hmm... I hope I'll find a way to program vector rotation for d3d_transform_add_rotation_axis(), because then only one script would be needed. I failed for some reason in my previous try.

You can't provide these nice scripts while excluding these basic requirements right . I figured how to find a facet on a model in my GMModelFix but I swear I was praying the math gods to help me figure the right x,y,z dx,dy,dz... Thank god the model was always centered on 0,0,0 though.

True. The normal and point of intesection were something that I was having in my mind to implent when I was thinking about making an example about this. I can believe that doing the same operations to blind triangle meshes can be a bit exhausting even for the machine.
• 0

### #13 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14392 posts
• Version:GM:Studio

Posted 02 February 2009 - 03:25 AM

There are at most two solutions for both point of intersection and normal. This is obviously because the line crosses one surface when it goes inside the shape and another one when it exits the shape. So the question is: if and when there are two solutions, should I return both or only the one that's nearest to the camera?

On a model, there could many facets intersecting. I use that other script you helped debug BTW... It giving the x,y,z (model world relative) of the intersection point on the facet plane. I simply resoved ithis prob by using a point_direction_3d() with the resulting x,y,z and the origin of the line... The closest would win. that is what I would return.

So closest to the camera... I mean closest to the start of the line because this is not camera relative...
• 0

### #14 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14392 posts
• Version:GM:Studio

Posted 02 February 2009 - 05:31 AM

Not meaning to bump/double post, but bumping in all likelyhood you've read my previous post...

I think you should add a wedge script too (slope) even if it's not a standard GM shape, I see those used all the time for ramps and stairs...

Edited by icuurd12b42, 02 February 2009 - 05:32 AM.

• 0

### #15 Tepi

Tepi

GMC Member

• Global Moderators
• 4201 posts
• Version:GM8.1

Posted 02 February 2009 - 01:28 PM

So closest to the camera... I mean closest to the start of the line because this is not camera relative...

Oh, silly me, yeah the closest one to the start of the line. I'll do it.

I think you should add a wedge script too (slope) even if it's not a standard GM shape, I see those used all the time for ramps and stairs...

Isn't that just the floor? If it isn't, it needs more parameters than the six (nx,ny,nz for its normal, x1,y1,z1 for its starting point, ax,ay,az for the clipping axis of the plane; and how would one draw that?).

I'll add line - floor and line - wall very soon.
• 0

### #16 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14392 posts
• Version:GM:Studio

Posted 02 February 2009 - 11:48 PM

So closest to the camera... I mean closest to the start of the line because this is not camera relative...

Oh, silly me, yeah the closest one to the start of the line. I'll do it.

I think you should add a wedge script too (slope) even if it's not a standard GM shape, I see those used all the time for ramps and stairs...

Isn't that just the floor? If it isn't, it needs more parameters than the six (nx,ny,nz for its normal, x1,y1,z1 for its starting point, ax,ay,az for the clipping axis of the plane; and how would one draw that?).

I'll add line - floor and line - wall very soon.

A ramp/wedge is like a floor but it also has 2 triangle walls on the side, 1 rectangle wall at the back. The wallking surface is a slanted floor. and finally there is a bottom rectangle to close it. In short, it's a right angled triangle with depth. A halph block. I can hit any of the slope faces while walking (slant and the 3 walls) an I can hit the bottom of the slant if I jump and hit my head, in our game...

ramp 0,0,0 to 0,10,10

that would make a ramp from 0,0 to 0,10 on the xyplane with a slope from 0 to 10 on the z.

ramp 0,0,10 to 0,10,0 is a ramp in the opposite direction.

I have a model to draw it myself morphing the points accordingly.

Video

As you can see I can hit any sides including the bottom. The slope was one of the very first requirements which I think people making 3d game will realise they'll need from the very begining.
• 0

### #17 Tepi

Tepi

GMC Member

• Global Moderators
• 4201 posts
• Version:GM8.1

Posted 09 February 2009 - 04:55 PM

<snip>

Ok I made a script for checking a ramp collision for a line:

`{    var  a, b, c, xx, yy, zz, Dx, Dy, Dz, T, T2;    a  = abs(argument3 - argument0)/2;    b  = abs(argument4 - argument1)/2;    c  = abs(argument5 - argument2)/2;    xx = (argument3 + argument0)/2 - argument6;    yy = (argument4 + argument1)/2 - argument7;    zz = (argument5 + argument2)/2 - argument8;    Dx = argument9;    if (Dx == 0) Dx = .000001;    Dy = argument10;   if (Dy == 0) Dy = .000001;    Dz = argument11;   if (Dz == 0) Dz = .000001;        T  = sqrt(Dx*Dx + Dy*Dy + Dz*Dz); //The direction vector's magnitude    Dx /= T;    Dy /= T;    Dz /= T;  //Normalizing the direction vector    T = 10000;   T2 = 0;    if  abs(yy - Dy * (xx + a) / Dx) <= b    &&  abs(zz - Dz * (xx + a) / Dx) <= c    {T = min(T,(xx + a) / Dx);    T2 = max(T2,(xx + a) / Dx);}    if  abs(yy - Dy * (xx - a) / Dx) <= b    &&  abs(zz - Dz * (xx - a) / Dx) <= c    {T = min(T,(xx - a) / Dx);    T2 = max(T2,(xx - a) / Dx);}    if  abs(xx - Dx * (yy + b) / Dy) <= a    &&  abs(zz - Dz * (yy + b) / Dy) <= c    {T = min(T,(yy + b) / Dy);    T2 = max(T2,(yy + b) / Dy);}    if  abs(xx - Dx * (yy - b) / Dy) <= a    &&  abs(zz - Dz * (yy - b) / Dy) <= c    {T = min(T,(yy - b) / Dy);    T2 = max(T2,(yy - b) / Dy);}    if  abs(xx - Dx * (zz + c) / Dz) <= a    &&  abs(yy - Dy * (zz + c) / Dz) <= b    {T = min(T,(zz + c) / Dz);    T2 = max(T2,(zz + c) / Dz);}    if  abs(xx - Dx * (zz - c) / Dz) <= a    &&  abs(yy - Dy * (zz - c) / Dz) <= b    {T = min(T,(zz - c) / Dz);    T2 = max(T2,(zz - c) / Dz);}    if  (T == 10000 || T < 0)  return 0;     global.XX  = argument6 + Dx * T;       global.ddx = 0;    global.YY  = argument7 + Dy * T;       global.ddy = 0;    global.ZZ  = argument8 + Dz * T;       global.ddz = 0;    if abs(global.XX-xx-argument6)/a == 1  global.ddx = sign(Dx * T - xx);    if abs(global.YY-yy-argument7)/b == 1  global.ddy = sign(Dy * T - yy);    if abs(global.ZZ-zz-argument8)/c == 1  global.ddz = sign(Dz * T - zz);    xx = argument2 - argument5;  // Here we'll use the old variables xx,    yy = argument3 - argument0;  // yy and zz for making some room. The old    zz = argument6 - argument0;  // names don't reflect their new functions.    b  = point_distance(0, 0, xx, yy); //This is the plane's normal's length.    if global.ZZ <= -xx/yy*(global.XX - argument3) + argument5 T=1; else T=0;    if argument8 <= -xx/yy*(zz - yy) + argument5   &&   T      {return 1;}    if argument8 <= -xx/yy*(zz - yy + Dx*T2) + argument5-Dz*T2  &&  !T {    global.XX = argument6-Dx*(xx*zz+yy*(argument8-argument2))/(xx*Dx+yy*Dz);    global.YY = argument7-Dy*(xx*zz+yy*(argument8-argument2))/(xx*Dx+yy*Dz);    global.ZZ = argument8-Dz*(xx*zz+yy*(argument8-argument2))/(xx*Dx+yy*Dz);    global.ddx = xx / b;    global.ddy = 0;    global.ddz = yy / b;    return 1;}     }`
As you can see, this is far less beautiful than the other ones. It's mostly because I didn't want to use too many variables in it and didn't want the script to be thicker than the default script window. (global.XX,global.YY,global.ZZ) is the nearest point of intersection and (global.ddx,global.ddy,global.ddz) is the normalized surface normal at the collision point, just as asked. I hope you like it. Of course, the global variables will likely get values even when there's no collision; it's your job to decide what to do with them.

As for the other points of intersection and surface normals, they are under construction. For block, ellipsoid and cone they are ready for the final touch, and others I haven't had much time to think. However, those should be easy, so expect the change to be made soon. They will not be changes in the original scripts, but separate pieces of code that will be optionally added in between the script.

The rotation I haven't yet thought about.
• 1

### #18 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14392 posts
• Version:GM:Studio

Posted 09 February 2009 - 08:14 PM

Neeto!!

Your line collision system will be part of my upcomming 3d map/room maker in the included basic engine once the rotation fns are in.

Maybe you can add line-facet collision to your group of scripts while you are at it.

The only thing left that would be cool (And I'm not asking for this because it's not <that> doable in GML (too slow)) would be line model collision... But with line_facet collision, I'm sure I can implement one real quick
• 1

### #19 Tepi

Tepi

GMC Member

• Global Moderators
• 4201 posts
• Version:GM8.1

Posted 09 February 2009 - 10:01 PM

Neeto!!

Your line collision system will be part of my upcomming 3d map/room maker in the included basic engine once the rotation fns are in.

Maybe you can add line-facet collision to your group of scripts while you are at it.

The only thing left that would be cool (And I'm not asking for this because it's not <that> doable in GML (too slow)) would be line model collision... But with line_facet collision, I'm sure I can implement one real quick

You can't represent a triangle algebrally in any good way, so I'm pretty sure that the line - triangle -collision you had in that topic of yours is the best way to do it. That comparing-cross-product-directions -method was the only sensible that I had come up with earlier, and back then I wasn't even aware that anyone had put it into practise. That alone tells that if there is a better way, it's not nearly as apparent. Triangle-by-triangle is also pretty much the only way of doing mesh collisions too, as you can't represent a set of triangles any better algebrally than one triangle.

It wasn't long ago that I came up with a pretty excellent idea of calculating the long-wanted bullet holes on any GM simple shape. With these, you can instantly find the bullet's collision point, and with the surface normal given, you can draw a small triangle with a hole texture facing into that normal's direction, from the point of intersection translated a bit to the normals direction. If I find the time to make the example, that'd be one top feature, alongside with some other applications that have come to my mind lately. I will find use for these in my future games too. Thank you for your ideas.
• 1

### #20 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14392 posts
• Version:GM:Studio

Posted 09 February 2009 - 10:39 PM

Neeto!!

Your line collision system will be part of my upcomming 3d map/room maker in the included basic engine once the rotation fns are in.

Maybe you can add line-facet collision to your group of scripts while you are at it.

The only thing left that would be cool (And I'm not asking for this because it's not <that> doable in GML (too slow)) would be line model collision... But with line_facet collision, I'm sure I can implement one real quick

You can't represent a triangle algebrally in any good way, so I'm pretty sure that the line - triangle -collision you had in that topic of yours is the best way to do it. That comparing-cross-product-directions -method was the only sensible that I had come up with earlier, and back then I wasn't even aware that anyone had put it into practise. That alone tells that if there is a better way, it's not nearly as apparent. Triangle-by-triangle is also pretty much the only way of doing mesh collisions too, as you can't represent a set of triangles any better algebrally than one triangle.

It wasn't long ago that I came up with a pretty excellent idea of calculating the long-wanted bullet holes on any GM simple shape. With these, you can instantly find the bullet's collision point, and with the surface normal given, you can draw a small triangle with a hole texture facing into that normal's direction, from the point of intersection translated a bit to the normals direction. If I find the time to make the example, that'd be one top feature, alongside with some other applications that have come to my mind lately. I will find use for these in my future games too. Thank you for your ideas.

I only intend to add walking on models or hitting them from the player perspective, no mesh to mesh; if I ever add in the line-facet and expand it to line-model collision in the engine anything more will be way too costly and there are dlls for that.

As for returning the x,y,z and normals of the intersecting facet, working with gmbullet and andna, that requirement (pos and vns) came in pretty early once I really started to use it. For the reason you mention, adding an effect in the right orientation and position for one, even "riqocheing" bullets. But mainly it's for appropriate walking on top of an object or sliding alongside a wall, the vn is essential for that. A ray trace down gives you the z for height. But you need the vns too to move in the right direction otherwise you constantly penetrate the object and then reset the position which makes for an unrealistic climb up a slope or down a slope or alongside a wall. When you enter 3d object sometimes, with the camera cliping at it's near value, it causes facets to flicker on and off. The only way arround that it to make sure you don't penetrate it in the first place.

Keep it up.
• 1

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users