Poor man's 3D Collision Detection
November 10, 2019, at 07:54 PM (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!
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:
- f32 s = ( SIN( rotY_yaw ) )*g_box.speed;
f32 c = ( COS( rotY_yaw ) )*g_box.speed;
f32 worldPosX = g_box.dir_loc+(s*5);
f32 worldPosZ = g_box.dir_loc+(c*5);
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:
- 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);
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:
- 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
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.
- if( isInside( worldPosX, worldPosZ, X_TR, Z_TR, X_BL, Z_BL, X_TL, Z_TL) )
if( isInside( worldPosX, worldPosZ, X_TR, Z_TR, X_BL, Z_BL, X_BR, Z_BR) )
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.
- f32 height = ( (Z_TL-worldPosZ )*nNormalZ + (X_TL-worldPosX)*nNormalX + Y_TL*nNormalY )/ nNormalY;
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:
- #define dis2D(aX, aZ,bX, bZ) ( ( ((aX) - (bX)) * (((aX) - (bX))) ) + ( ((aZ) - (bZ)) * (((aZ) - (bZ))) ))
u16 xx = g_box.dir_loc; get the original X pos
u16 zz = g_box.dir_loc; 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);
But the closest point doesn't mean the closest edge, so I check each point for the shortest one using if statements like
- if( TL_Pivot < TR_Pivot && TL_Pivot < BL_Pivot && TL_Pivot < BR_Pivot) // TL corner is the closest
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 (/).
- 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 = X_TL;
v1 = Z_TL;
v2 = X_TR;
v2 = Z_TR;
LOG_GROUND_COL_TEST("\n intersected with TL BL = LEFT line" );
v1 = X_TL;
v1 = Z_TL;
v2 = X_BL;
v2 = Z_BL;
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:
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:
Thanks for reading, feel free to post any comments below.
2 comments on "Poor man's 3D Collision Detection"
- owen: 2019-11-10 23:30 +1100 Seems like you are doing morework that a simple aabb without any benefits. If you do a 3d test that is 5 lines its better that a 2d test that is 15 lines of kungfu
- mgarcia: 2019-11-11 08:08 +1100 Thanks Owen, I did look into AABB, but I figured because the Axis (my quad corners in this case) aren't aligned, I couldn't use it, I'll have a better look at it again, thanks again.
Comments are open.