Simple Collision Thoughts

[Baker]

Not for a Quake engine per se, but fleshing out the beginnings of simplified movement with an uncompiled .MAP.

1. Build a list of models, brushes and so forth.
2. Calculate the extreme XYZ mins and XYZ maxes for each object.
3. Build a list of solids:

Code: Select all

typedef   float      vec3_t[3];
typedef   float      boxspace_t[2][3];


static boxspace_t solid_spaces[32768];
const int max_solid_spaces = sizeof(solid_spaces) / sizeof(solid_spaces[0]);
int num_solid_spaces = 0;

static qbool Point_Is_In_Space (const vec3_t myPoint, const boxspace_t myBox)
{
   static const int x = 0, y = 1, z = 2, mins = 0, maxs = 1;

   if (myPoint[x] < myBox[mins][x] || myPoint[y] < myBox[mins][y] || myPoint[z] < myBox[mins][z]) return false;
   if (myPoint[x] > myBox[maxs][x] || myPoint[y] > myBox[maxs][y] || myPoint[z] > myBox[maxs][z]) return false;
 
   return true;
}

static qbool Boxes_Do_Collide (const boxspace_t myBox1, const boxspace_t myBox2)
{
   // 8 points define a box.  Compare each of 8 corners of Box1 to see if they intrude into the space of Box2
   for (int x = 0; x < 1; x++)
      for (int y = 0; y < 1; y++)
         for (int z = 0; z < 1; z++)
         {
            vec3_t myCornerBox1 = { myBox1[x][0], myBox1[y][1], myBox1[z][2] }
            if ( Point_Is_In_Space (myCornerBox1, myBox2) return true;
         }
   
   // Now we have to check for Box2 corners in Box 1.  Because Box2 could entirely be contained in Box1
   for (int x = 0; x < 1; x++)
      for (int y = 0; y < 1; y++)
         for (int z = 0; z < 1; z++)
         {
            vec3_t myCornerBox2 = { myBox2[x][0], myBox2[y][1], myBox2[z][2] }
            if ( Point_Is_In_Space (myCornerBox1, myBox1) return true;
         }

   // Note: We are overlooking the case that the corners of each box may not overlap at all yet the spaces intersect
   //             *************
   //             *           *                       
   //*******************************************
   //*            *           *                *
   //*            *           *                *
   //*            *           *                *
   //*            *           *                *
   //*******************************************
   //             *           *                       
   //             *************



   // I feel like there is a more efficient way to to avoid some of this, like some automatic exclusion that the boxes cannot intersect
   // by mins and maxes.  And it is ok that we are not doing this.

}



So to do: Accurately check for any space intersection between the boxes. Then later ... add in motion and turn all of this interaction into lines of movement and calculate a collision point. Then start to get into a more precise form of collision using faces or triangles and such.

I want to step by step evolve this rather than take something existing. Taking something existing is a cop-out.

As an example, I've modified tons of Quake engine code in places where I didn't understand how something worked completely, yet didn't make any mistakes with even modifying it because I could work within the framework of what I did understand. I might even be able to describe rather accurately what that section of code does and why it does it.

But I am weaker in 3D math than I want to be and if I don't develop a personal understanding of each inch of what I am doing, then I am avoiding 3D math ... not learning it.

[Baker]

To get to a box versus box test in axis-aligned space, first need to go through line versus box (cuboid) collision test.

Parameters:

1. Need an origin point XYZ.
2. Need an end point (XYZ) using ...
2. ... line slope XYZ.
3. Need bounding box mins (X LEFT, Y TOP, Z NEAR)
4. Need bounding box macs (X RIGHT, Y BOTTOM, Z FAR)

A bounding box is define by 6 planes, each plane with a slope. In axis-aligned space (no angles for cuboid) ...

1. Front face. X left, Y top through X right, Y bottom. Z Near. Check to make sure LINE origin Z <= ZNEAR <= Line end Z (if not, cannot have hit. Collision = False). Calculate LINE at Z Near. Call result Point_At_Plane. If X Left <= Point_At_Plane (X) =< X Right and Y Bottom <= Point_At_Plane (Y) <= Y Bottom. We have collision. Collision point is Point_At_Plane (X) and Point_At_Plane (Y).

2. Blah
3. Blah
4. Blah
5. Blah again? Yes
6. Guess what? Answer is blah. Surprised? No.

In fact, any cuboid can be pulled into axis-aligned space as long as you do the same calc on the line slope.

[I guess after writing this code, the next step is plane versus cube. Quake has entities move in turn, so there is no need for a cube versus cube test for motion. It is plane versus plane. But a plane moving is a cuboid in a way with a Z depth of the motion length. And not really a plane. Looks like GNU.org might have some of this already worked out. I still want to work through the calks myself step by step, but I don't want to step up to the eventual matrix maths without being able to code the simpler axis-aligned stuff myself.]

Maybe only 16 steps away from being able to write the Worldcraft "carve" tool function. Sigh ..