# Poor man's 3D Collision Detection

November 10, 2019, at 09:54 AM (2 comments)

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

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*get the original Z pos

u16 zz = g_box.dir_loc[3][2];

// 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.

**Comments are open.**

β
An IndieWeb Webring πΈπ
β

2 comments on "Poor man's 3D Collision Detection"owen: 2019-11-10 23:30 +1100mgarcia: 2019-11-11 08:08 +1100Mike.