Point Cube Collision Detection
Home -->
Programming Projects -->
Block Engine -->
Point Cube Collision Detection
What this does
Recall that here
we discussed now to move a cylinder (the smallest amount possible)
so that it no longer intersects a solid block.
This allowed for modeling the player's body as a cylinder.
We moved the cylinder 0.1 units through the world,
then "corrected" it so that it no longer intersected any
solid blocks.
Then we moved the cylinder another 0.1 units, etc
(a block is 1.0 wide).
In this page we do something similar but with a point.
We move a point 0.4 units, then move it so that it is no longer
inside any solid block.
We then move the point another 0.4 units and repeat.
This 0.4 number is important.
It certainly cannot be greater than 0.5, because then a point could
completely move through a solid block
(it could get more than half way through, and then it would
be corrected to be positioned on the other side).
The algorithm in this page is different from the
cylinder algorithm because here we move the point
to one of the 26 surrounding block positions
that is not solid.
This code can be used to have a monster move through the world
but be unable to move through blocks.
That is, the center of the monster is a point and we
repeatedly move that point so it is not inside any solid block.
This allows for monsters to slide along surfaces.
Note that just like we said for the cylinder block correction
algorithm, the probably more proper and faster way to
accomplish the same thing is to do the following:
First calculate the line segment
that is the line of travel of the entity through the world.
Then intersect that line segment with the surface of the world.
In the result of an intersection,
the velocity of the entity will be updated to be parallel
to the surface.
The Code
lp stands for "level position".
It is simply the position of the point.
A block position (BlockPos) is a triple (x,y,z) of integers.
If e is set to 0.0, then the point will be moved just to the
surface of the solid block.
If e > 0.0, then the point will be moved that much away
from the solid block.
Note that a block is 1.0 wide.
The end_pos is set to where the point should be moved to.
MaxF simply takes the maximum of two floating point numbers.
Without using handicaps we get a strange artifact.
We need handicaps because we are using the L_infinity norm
for distances instead of the L_1 or L_2 norms.
IsSolidPhysically returns whether on not a given
block position is solid.
//This is C++ code.
void CollisionCorrectPointFromBlock(
const Vector & lp, //start pos
const BlockPos & bp,
float e, //Extra add.
Vector & end_pos)
{
float min_x = (float)bp.x;
float min_y = (float)bp.y;
float min_z = (float)bp.z;
float max_x = min_x + 1.0f;
float max_y = min_y + 1.0f;
float max_z = min_z + 1.0f;
//
float d_x_min = lp.x - min_x;
float d_y_min = lp.y - min_y;
float d_z_min = lp.z - min_z;
float d_x_max = max_x - lp.x;
float d_y_max = max_y - lp.y;
float d_z_max = max_z - lp.z;
//The var d_xyz refers to the distance
//to one of the surrounding 26 blocks
//(in the L_infinity metric).
//Each of x,y,z goes from 0 to 2 inclusive.
//"1" is in the middle, and "0" and "2"
//are one either side.
float d[3][3][3];
//Blocks with z == bp.z
d[1][1][1] = 100.0f; //Does not matter.
d[0][1][1] = d_x_min;
d[2][1][1] = d_x_max;
d[1][0][1] = d_y_min;
d[1][2][1] = d_y_max;
d[0][0][1] = MaxF(d_x_min, d_y_min);
d[2][0][1] = MaxF(d_x_max, d_y_min);
d[0][2][1] = MaxF(d_x_min, d_y_max);
d[2][2][1] = MaxF(d_x_max, d_y_max);
//Blocks with z == bp.z-1
d[1][1][0] = d_z_min;
d[0][1][0] = MaxF(d[0][1][1], d_z_min);
d[2][1][0] = MaxF(d[2][1][1], d_z_min);
d[1][0][0] = MaxF(d[1][0][1], d_z_min);
d[1][2][0] = MaxF(d[1][2][1], d_z_min);
d[0][0][0] = MaxF(d[0][0][1], d_z_min);
d[2][0][0] = MaxF(d[2][0][1], d_z_min);
d[0][2][0] = MaxF(d[0][2][1], d_z_min);
d[2][2][0] = MaxF(d[2][2][1], d_z_min);
//Blocks with z == bp.z+1
d[1][1][2] = d_z_max;
d[0][1][2] = MaxF(d[0][1][1], d_z_max);
d[2][1][2] = MaxF(d[2][1][1], d_z_max);
d[1][0][2] = MaxF(d[1][0][1], d_z_max);
d[1][2][2] = MaxF(d[1][2][1], d_z_max);
d[0][0][2] = MaxF(d[0][0][1], d_z_max);
d[2][0][2] = MaxF(d[2][0][1], d_z_max);
d[0][2][2] = MaxF(d[0][2][1], d_z_max);
d[2][2][2] = MaxF(d[2][2][1], d_z_max);
//Adding handicaps.
//In the case of a tie, we want
//it to be shorter to go directly to
//a side instead of going to an edge
//or a corner.
//Also, we want it to be shorter to
//go to an edge than to go to a corner.
float hcap = 0.01f;
float hcap2 = hcap + hcap;
//Edges.
//xy plane.
d[0][0][1] += hcap;
d[0][2][1] += hcap;
d[2][0][1] += hcap;
d[2][2][1] += hcap;
//xz plane.
d[0][1][0] += hcap;
d[0][1][2] += hcap;
d[2][1][0] += hcap;
d[2][1][2] += hcap;
//yz plane.
d[1][0][0] += hcap;
d[1][0][2] += hcap;
d[1][2][0] += hcap;
d[1][2][2] += hcap;
//Corners.
d[0][0][0] += hcap2;
d[0][0][2] += hcap2;
d[0][2][0] += hcap2;
d[0][2][2] += hcap2;
d[2][0][0] += hcap2;
d[2][0][2] += hcap2;
d[2][2][0] += hcap2;
d[2][2][2] += hcap2;
//Finding the smallest d.
float smallest_d = 100.0f;
//(s_x, s_y, s_z) is the smallest triple.
int s_x = -1;
int s_y = -1;
int s_z = -1;
for(int xi = 0; xi <= 2; ++xi) {
for(int yi = 0; yi <= 2; ++yi) {
for(int zi = 0; zi <= 2; ++zi) {
if( d[xi][yi][zi] < smallest_d &&
IsSolidPhysically(bp + BP(xi-1,yi-1,zi-1)) )
{
smallest_d = d[xi][yi][zi];
s_x = xi;
s_y = yi;
s_z = zi;
}
}}}
end_pos = lp; //Going to modify.
if( s_x == 0 ) end_pos.x = min_x - e;
if( s_x == 2 ) end_pos.x = max_x + e;
if( s_y == 0 ) end_pos.y = min_y - e;
if( s_y == 2 ) end_pos.y = max_y + e;
if( s_z == 0 ) end_pos.z = min_z - e;
if( s_z == 2 ) end_pos.z = max_z + e;
}