Poor man's 3D Collision Detection

Title: Poor man's 3D Collision Detection Author: mgarcia Date: 2019-11-10 19:54 +1100 Tags: 2019, 3DS, Pics, GameDev, Blog Comments: Open

Poor man's 3D Collision Detection

Note: I have scripted a text to speech (TTS) MP3 download of this blog (in the top right menu), it reads this out aloud for you in a horrible and highly compressed voice! so retro!

Click to view original image: 713kb

Size: 1.19 MB

It's been a while since I've updated my gamedev blog on my actual game, I've been focused on other things mostly, and also figuring out a quick and dirty way of doing 3D collision detection was really taking me a while, and to be honest I still don't think it's 100% correct either!

Anyway, if you don't know, my engine uses quads for everything, (well because it's less memory hungry then triangles! obviously :P ) and then sends 2 triangles to the hardware in a polygon soup. It currently runs on Linux (my desktop) and Nintendo 3DS (which I can't show you!). So after applying the new direction and speed, via this code:

<code>

f32 s = ( SIN( rotY_yaw ) )*g_box.speed;
f32 c = ( COS( rotY_yaw ) )*g_box.speed;
f32 worldPosX = g_box.dir_loc[3][0]+(s*5);
f32 worldPosZ = g_box.dir_loc[3][2]+(c*5);

</code>

I times the directional speed by 5 (projected further) to cover the 2D sprite and avoid the 'catching' of wrong edges, it's hacky I know! that aside, I check that worlPos is in a quad. I used this inside triangle check, my code looks like this:

<code>

inline s32 isInside( u16 x, u16 y, u16 x1, u16 y1, u16 x2, u16 y2, u16 x3, u16 y3 )
{
s32 l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1),
l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2),
l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
return (l1>0 && l2>0 && l3>0) || (l1<0 && l2<0 && l3<0);
}

</code>

I have two layers (actually objects) in Blender, one is a textured quads for rendering, the second is untextured quads for collision (the top of the 'buildings'). When loading it, I sort the collision layer the minimum X position in the quad (to find a collision faster) and store it in this format:

<code>

X_TL, Z_TL = Top Left X & Z values
X_TR, Z_TR = Top Right X & Z values
X_BR, Z_BR = Bottom Right X & Z values
X_BL, Z_BL = Bottom Left X & Z values

</code>

Collision is mostly 2D based and there's no overlapping, positions are mostly in short int's and very simple, don't ask, games on the original 3DS can only uses a single 260Mhz CPU core!

So, I loop over the collision list, based on the new worldPosX and work up through the list, starting at the minimum, I store their quad corners as described above into local variables and test if it's inside.

<code>

if( isInside( worldPosX, worldPosZ, X_TR, Z_TR, X_BL, Z_BL, X_TL, Z_TL) )
{
goto ISINSIDE_SET;
}

if( isInside( worldPosX, worldPosZ, X_TR, Z_TR, X_BL, Z_BL, X_BR, Z_BR) )
{
goto ISINSIDE_SET;
}

</code>

Ohhh the two evil goto statement.. ohhh soo evil! Nah it's okay, it's in a complicated loop, besides this whole thing is a fun hack, really!

If it's inside, I get the quad's normal, get the height of the worldPos and check if it's higher then 200 (centimeters I guess, which is 2 meters). If under 200, it uses the normal and applies a gravity slide, but if it's too high, it's treated as a wall and so it does a wall slide. That all sounds simple to do, but not for me! Applying gravity, is pretty simple, just using the plain equation.

<code>

f32 height = ( (Z_TL-worldPosZ )*nNormalZ + (X_TL-worldPosX)*nNormalX + Y_TL*nNormalY )/ nNormalY;

</code>

You minus the corners from the actual position to get the true corner heights, not the world height. Anyway, if it's over 200, it's a wall, which again, is also pretty simple to do, and I know how to do the math, the hardest thing for me is getting the correct edge! gaaarrrhh!
So this is the madness I have to do, I find the closest point of the quad, that's easy:

<code>

#define dis2D(aX, aZ,bX, bZ) ( ( ((aX) - (bX)) * (((aX) - (bX))) ) + ( ((aZ) - (bZ)) * (((aZ) - (bZ))) ))

u16 xx = g_box.dir_loc[3][0]; get the original X pos
u16 zz = g_box.dir_loc[3][2]; get the original Z pos

// find the closes point of the quad to the original pos
u32 TL_Pivot = dis2D(xx, zz, X_TL, Z_TL);
u32 TR_Pivot = dis2D(xx, zz, X_TR, Z_TR);
u32 BR_Pivot = dis2D(xx, zz, X_BR, Z_BR);
u32 BL_Pivot = dis2D(xx, zz, X_BL, Z_BL);

</code>

But the closest point doesn't mean the closest edge, so I check each point for the shortest one using if statements like

<code>

if( TL_Pivot < TR_Pivot && TL_Pivot < BL_Pivot && TL_Pivot < BR_Pivot) // TL corner is the closest

</code>

If that's true, it's either the top edge or the left edge, next I then make sure xx and zz (which is the current position) are with in the 'triangle of that top edge'. What I mean is the edge could be flat (-), or slanted, like the Top Left corner could be higher (in Z axis) then the Top Right (\) or visa versa (/).

<code>

if(xx < X_TL && xx > X_TR && ( ( zz > Z_TL-10 && zz < Z_TR+10) || ( zz < Z_TL+10 && zz > Z_TR-10) ) )
{
LOG_GROUND_COL_TEST("\n intersected with TL TR = TOP line");
v1[0] = X_TL;
v1[2] = Z_TL;
v2[0] = X_TR;
v2[2] = Z_TR;
}
else
{
LOG_GROUND_COL_TEST("\n intersected with TL BL = LEFT line" );
v1[0] = X_TL;
v1[2] = Z_TL;
v2[0] = X_BL;
v2[2] = Z_BL;
}

</code>

Basically, I do this another 3 times, for the remaining corners. The vectors v1 and v2 are then used to make the wall normal to calculate the wall slide.

Originally I was getting a lot of "catching" on wrong edges, but pushing the new direction and speed by five times, it solved it:

Collision detection getting stuck and fixed

In the left video, the quad catches on the edges as it leaves the quads, the middle video the test is projected out further, 2 times, the right video it's a 5 times and works fine.

Anyway, here is a more complex map, working okay, at the end I rotated the map to test it and it gets stuck here and there, but a problem for another time:

Poor man's 3D Collision Detection

---UPDATE-- 2020 FEB 20th

The code above is still the same.. I check for three positions, front and left and right, and rotated based on new direction, in this video you can see where the collisions are checked.

Poor man's 3D Collision Detection

If any of the positions is inside a triangle, then I check which line it crossed using the "lines_intersect" algo from from the Graphics Gems 2 book "xlines.c" by Mukesh Prasad.

Collision Detection working with sprites cycling

Which, as explained above, is used as a wall normal for sliding.

Algos from: Point in Tri: https://stackoverflow.com/posts/43528699/revisions

Line line intersect: https://github.com/erich666/GraphicsGems/blob/master/gemsii/xlines.c

Thanks for reading, feel free to post any comments below.
Mike.