Code-dump - Bounding Boxes

[mh]

The next release of DirectQ will have per-frame bounding boxes for MDLs (in the renderer only) and corrected bounding boxes for all entities (again, renderer only), also with proper rotation correction (instead of the clumsy "if (rotated)" thing in ID Quake which just expands the bounding box out to the entity radius in all directions).

Because there are still bugs elsewhere (hello multiple conflicting standards for entity alpha!) that I need to resolve I'm giving a code-dump of the most relevant part here. Much of this was adapted from Quake II, and it should be clear enough what to do with it.

Per-frame bounding boxes for MDLs are easy to construct; you already have what you need in the old aliasbboxmins/aliasbboxmaxs thing, so just adapt it to a per-frame level.

For brush models it's a simple matter of walking through the vertexes in the model's surfaces and constructing the bounding box from those using the same principle. Don't trust the mins and maxs stored in BSP files. QBSP does quite evil things with these; if you ever implement showing bounding boxes in your renderer you'll see what I mean.

These should be kept separate from the server-side bounding boxes and the regular ent->model->mins and ent->model->maxs as otherwise you'll be incurring a gameplay change. Just declare two more mins and maxs members in the entity_t struct (preferred as using per-frame means that different entities using the same model can have different bounding boxes).

Finally, my SetupAliasFrame thing doesn't call the model drawing function; this should be really done before the R_CullBox check and as a separate pass through the visedicts list (I've implemented an "AddVisedict" function which gets called for both static and server entities which calls it; you can do whatever you want). Also my trueorigin and bboxscale members are just for making things easier for other parts of my code and are not really essential.

Finally finally - this has a dependency on origin and angles interpolation having already been run. I do mine in CL_RelinkEntities.

Enough talk; here's the code.

Code: Select all

void D3DMain_BBoxForEnt (entity_t *ent)
{
   if (!ent->model) return;

   float mins[3];
   float maxs[3];
   float angles[3];
   vec3_t bbox[8];
   vec3_t vectors[3];

   if (ent->model->type == mod_alias)
   {
      // use per-frame bboxes for entities
      int *poses = ent->lerppose;
      float *blends = ent->aliasstate.blend;
      aliasbbox_t *bboxes = ent->model->aliashdr->bboxes;

      // set up interpolation here to ensure that we get all entities
      // this also keeps interpolation frames valid even if the model has been culled away (bonus!)
      D3DAlias_SetupAliasFrame (ent, ent->model->aliashdr);

      // use per-frame interpolated bboxes
      mins[0] = bboxes[poses[LERP_CURR]].mins[0] * blends[LERP_CURR] + bboxes[poses[LERP_LAST]].mins[0] * blends[LERP_LAST];
      mins[1] = bboxes[poses[LERP_CURR]].mins[1] * blends[LERP_CURR] + bboxes[poses[LERP_LAST]].mins[1] * blends[LERP_LAST];
      mins[2] = bboxes[poses[LERP_CURR]].mins[2] * blends[LERP_CURR] + bboxes[poses[LERP_LAST]].mins[2] * blends[LERP_LAST];
      maxs[0] = bboxes[poses[LERP_CURR]].maxs[0] * blends[LERP_CURR] + bboxes[poses[LERP_LAST]].maxs[0] * blends[LERP_LAST];
      maxs[1] = bboxes[poses[LERP_CURR]].maxs[1] * blends[LERP_CURR] + bboxes[poses[LERP_LAST]].maxs[1] * blends[LERP_LAST];
      maxs[2] = bboxes[poses[LERP_CURR]].maxs[2] * blends[LERP_CURR] + bboxes[poses[LERP_LAST]].maxs[2] * blends[LERP_LAST];
   }
   else if (ent->model->type == mod_brush)
   {
      VectorCopy (ent->model->brushhdr->bmins, mins);
      VectorCopy (ent->model->brushhdr->bmaxs, maxs);
   }
   else
   {
      VectorCopy (ent->model->mins, mins);
      VectorCopy (ent->model->maxs, maxs);
   }

   // compute a full bounding box
   for (int i = 0; i < 8; i++)
   {
      // the bounding box is expanded by 1 unit in each direction so
      // that it won't z-fight with the model (if it's a tight box)
      bbox[i][0] = (i & 1) ? mins[0] - 1.0f : maxs[0] + 1.0f;
      bbox[i][1] = (i & 2) ? mins[1] - 1.0f : maxs[1] + 1.0f;
      bbox[i][2] = (i & 4) ? mins[2] - 1.0f : maxs[2] + 1.0f;
   }

   // these factors hold valid for both MDLs and brush models; tested brush models with rmq rotate test
   // and ne_tower; tested alias models by assigning bobjrotate to angles 0/1/2 and observing the result
   // i guess that ID just left out angles[2] because it never really happened in the original game
   if (ent->model->type == mod_brush)
   {
      angles[0] = -ent->angles[0];
      angles[1] = -ent->angles[1];
      angles[2] = -ent->angles[2];
   }
   else
   {
      angles[0] = ent->angles[0];
      angles[1] = -ent->angles[1];
      angles[2] = -ent->angles[2];
   }

   // derive forward/right/up vectors from the angles
   AngleVectors (angles, vectors[0], vectors[1], vectors[2]);

   // compute the rotated bbox corners
   mins[0] = mins[1] = mins[2] = 9999999;
   maxs[0] = maxs[1] = maxs[2] = -9999999;

   // and rotate the bounding box
   for (int i = 0; i < 8; i++)
   {
      vec3_t tmp;

      VectorCopy (bbox[i], tmp);

      bbox[i][0] = DotProduct (vectors[0], tmp);
      bbox[i][1] = -DotProduct (vectors[1], tmp);
      bbox[i][2] = DotProduct (vectors[2], tmp);

      // and convert them to mins and maxs
      for (int j = 0; j < 3; j++)
      {
         if (bbox[i][j] < mins[j]) mins[j] = bbox[i][j];
         if (bbox[i][j] > maxs[j]) maxs[j] = bbox[i][j];
      }
   }

   // compute scaling factors
   ent->bboxscale[0] = (maxs[0] - mins[0]) * 0.5f;
   ent->bboxscale[1] = (maxs[1] - mins[1]) * 0.5f;
   ent->bboxscale[2] = (maxs[2] - mins[2]) * 0.5f;

   // translate the bbox to it's final position at the entity origin
   VectorAdd (ent->origin, mins, ent->mins);
   VectorAdd (ent->origin, maxs, ent->maxs);

   // true origin of entity is at bbox center point (needed for bmodels
   // where the origin could be at (0, 0, 0) or at a corner)
   ent->trueorigin[0] = ent->mins[0] + (ent->maxs[0] - ent->mins[0]) * 0.5f;
   ent->trueorigin[1] = ent->mins[1] + (ent->maxs[1] - ent->mins[1]) * 0.5f;
   ent->trueorigin[2] = ent->mins[2] + (ent->maxs[2] - ent->mins[2]) * 0.5f;
}

[Baker]

Nice work. Yes the shared bounding boxes is a bad way to do things, as I got to learn firsthand last year in a surprise and initially frustrating "missing keys" bug. (Fortunately, it was one of only 3 changes I had made and it was quickly identified, but initially very aggravating to the max.)