opbox.cpp

Go to the documentation of this file.

/*
    Copyright (C) 1998 by Jorrit Tyberghein
    Largely rewritten by Ivan Avramovic <ivan@avramovic.com>
  
    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.
  
    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.
  
    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#include <math.h>
#include "cmd/collide2/opcodesysdef.h"
#include "opbox.h"

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

// We have a coordinate system around our box which is
// divided into 27 regions. The center region at coordinate (1,1,1)
// is the node itself. Every one of the 26 remaining regions
// defines an number of vertices which are the convex outline
// as seen from a camera view point in that region.
// The numbers inside the outlines table are indices from 0 to
// 7 which describe the 8 vertices outlining the node:
//  0: left/down/front vertex
//  1: left/down/back
//  2: left/up/front
//  3: left/up/back
//  4: right/down/front
//  5: right/down/back
//  6: right/up/front
//  7: right/up/back
// This table also contains an array of sides visible from that region.
struct Outline
{
  int num;
  int vertices[7];
  int num_sides;
  int sides[3];
};
static Outline outlines[27] =
{
  { 7, {3,2,6,4,5,1,0},        3, {BOX_SIDE_x,BOX_SIDE_y,BOX_SIDE_z} }, // 0,0,0
  { 6, {3,2,0,4,5,1,-1},       2, {BOX_SIDE_x,BOX_SIDE_y,-1} },     // 0,0,1
  { 7, {7,3,2,0,4,5,1},        3, {BOX_SIDE_x,BOX_SIDE_y,BOX_SIDE_Z} }, // 0,0,2
  { 6, {3,2,6,4,0,1,-1},       2, {BOX_SIDE_x,BOX_SIDE_z,-1} },     // 0,1,0
  { 4, {3,2,0,1,-1,-1,-1},     1, {BOX_SIDE_x,-1,-1} },         // 0,1,1
  { 6, {7,3,2,0,1,5,-1},       2, {BOX_SIDE_x,BOX_SIDE_Z,-1} },     // 0,1,2
  { 7, {3,7,6,4,0,1,2},        3, {BOX_SIDE_x,BOX_SIDE_Y,BOX_SIDE_z} }, // 0,2,0
  { 6, {3,7,6,2,0,1,-1},       2, {BOX_SIDE_x,BOX_SIDE_Y,-1} },     // 0,2,1
  { 7, {7,6,2,0,1,5,3},        3, {BOX_SIDE_x,BOX_SIDE_Y,BOX_SIDE_Z} }, // 0,2,2
  { 6, {2,6,4,5,1,0,-1},       2, {BOX_SIDE_y,BOX_SIDE_z,-1} },     // 1,0,0
  { 4, {0,4,5,1,-1,-1,-1},     1, {BOX_SIDE_y,-1,-1} },         // 1,0,1
  { 6, {3,1,0,4,5,7,-1},       2, {BOX_SIDE_y,BOX_SIDE_Z,-1} },     // 1,0,2
  { 4, {2,6,4,0,-1,-1,-1},     1, {BOX_SIDE_z,-1,-1} },         // 1,1,0
  { 0, {-1,-1,-1,-1,-1,-1,-1}, 0, {-1,-1,-1} },             // 1,1,1
  { 4, {7,3,1,5,-1,-1,-1},     1, {BOX_SIDE_Z,-1,-1} },         // 1,1,2
  { 6, {3,7,6,4,0,2,-1},       2, {BOX_SIDE_Y,BOX_SIDE_z,-1} },     // 1,2,0
  { 4, {3,7,6,2,-1,-1,-1},     1, {BOX_SIDE_Y,-1,-1} },         // 1,2,1
  { 6, {2,3,1,5,7,6,-1},       2, {BOX_SIDE_Y,BOX_SIDE_Z,-1} },     // 1,2,2
  { 7, {2,6,7,5,1,0,4},        3, {BOX_SIDE_X,BOX_SIDE_y,BOX_SIDE_z} }, // 2,0,0
  { 6, {6,7,5,1,0,4,-1},       2, {BOX_SIDE_X,BOX_SIDE_y,-1} },     // 2,0,1
  { 7, {6,7,3,1,0,4,5},        3, {BOX_SIDE_X,BOX_SIDE_y,BOX_SIDE_Z} }, // 2,0,2
  { 6, {2,6,7,5,4,0,-1},       2, {BOX_SIDE_X,BOX_SIDE_z,-1} },     // 2,1,0
  { 4, {6,7,5,4,-1,-1,-1},     1, {BOX_SIDE_X,-1,-1} },         // 2,1,1
  { 6, {6,7,3,1,5,4,-1},       2, {BOX_SIDE_X,BOX_SIDE_Z,-1} },     // 2,1,2
  { 7, {2,3,7,5,4,0,6},        3, {BOX_SIDE_X,BOX_SIDE_Y,BOX_SIDE_z} }, // 2,2,0
  { 6, {2,3,7,5,4,6,-1},       2, {BOX_SIDE_X,BOX_SIDE_Y,-1} },     // 2,2,1
  { 7, {6,2,3,1,5,4,7},        3, {BOX_SIDE_X,BOX_SIDE_Y,BOX_SIDE_Z} }  // 2,2,2
};

csBox3::bEdge csBox3::edges[24] =
  {
    { BOX_CORNER_Xyz, BOX_CORNER_xyz, BOX_SIDE_y, BOX_SIDE_z },
    { BOX_CORNER_xyz, BOX_CORNER_Xyz, BOX_SIDE_z, BOX_SIDE_y },
    { BOX_CORNER_xyz, BOX_CORNER_xYz, BOX_SIDE_x, BOX_SIDE_z },
    { BOX_CORNER_xYz, BOX_CORNER_xyz, BOX_SIDE_z, BOX_SIDE_x },
    { BOX_CORNER_xYz, BOX_CORNER_XYz, BOX_SIDE_Y, BOX_SIDE_z },
    { BOX_CORNER_XYz, BOX_CORNER_xYz, BOX_SIDE_z, BOX_SIDE_Y },
    { BOX_CORNER_XYz, BOX_CORNER_Xyz, BOX_SIDE_X, BOX_SIDE_z },
    { BOX_CORNER_Xyz, BOX_CORNER_XYz, BOX_SIDE_z, BOX_SIDE_X },

    { BOX_CORNER_Xyz, BOX_CORNER_XyZ, BOX_SIDE_X, BOX_SIDE_y },
    { BOX_CORNER_XyZ, BOX_CORNER_Xyz, BOX_SIDE_y, BOX_SIDE_X },
    { BOX_CORNER_XyZ, BOX_CORNER_XYZ, BOX_SIDE_X, BOX_SIDE_Z },
    { BOX_CORNER_XYZ, BOX_CORNER_XyZ, BOX_SIDE_Z, BOX_SIDE_X },
    { BOX_CORNER_XYZ, BOX_CORNER_XYz, BOX_SIDE_X, BOX_SIDE_Y },
    { BOX_CORNER_XYz, BOX_CORNER_XYZ, BOX_SIDE_Y, BOX_SIDE_X },
    { BOX_CORNER_XYZ, BOX_CORNER_xYZ, BOX_SIDE_Y, BOX_SIDE_Z },
    { BOX_CORNER_xYZ, BOX_CORNER_XYZ, BOX_SIDE_Z, BOX_SIDE_Y },

    { BOX_CORNER_xYZ, BOX_CORNER_xYz, BOX_SIDE_Y, BOX_SIDE_x },
    { BOX_CORNER_xYz, BOX_CORNER_xYZ, BOX_SIDE_x, BOX_SIDE_Y },
    { BOX_CORNER_xYZ, BOX_CORNER_xyZ, BOX_SIDE_x, BOX_SIDE_Z },
    { BOX_CORNER_xyZ, BOX_CORNER_xYZ, BOX_SIDE_Z, BOX_SIDE_x },
    { BOX_CORNER_xyZ, BOX_CORNER_xyz, BOX_SIDE_x, BOX_SIDE_y },
    { BOX_CORNER_xyz, BOX_CORNER_xyZ, BOX_SIDE_y, BOX_SIDE_x },
    { BOX_CORNER_xyZ, BOX_CORNER_XyZ, BOX_SIDE_y, BOX_SIDE_Z },
    { BOX_CORNER_XyZ, BOX_CORNER_xyZ, BOX_SIDE_Z, BOX_SIDE_y }
  };
// Index by BOX_SIDE_? number.
csBox3::bFace csBox3::faces[6] =
  {
    { BOX_EDGE_xyz_xyZ, BOX_EDGE_xyZ_xYZ, BOX_EDGE_xYZ_xYz, BOX_EDGE_xYz_xyz },
    { BOX_EDGE_XYz_XYZ, BOX_EDGE_XYZ_XyZ, BOX_EDGE_XyZ_Xyz, BOX_EDGE_Xyz_XYz },
    { BOX_EDGE_xyz_Xyz, BOX_EDGE_Xyz_XyZ, BOX_EDGE_XyZ_xyZ, BOX_EDGE_xyZ_xyz },
    { BOX_EDGE_xYZ_XYZ, BOX_EDGE_XYZ_XYz, BOX_EDGE_XYz_xYz, BOX_EDGE_xYz_xYZ },
    { BOX_EDGE_xYz_XYz, BOX_EDGE_XYz_Xyz, BOX_EDGE_Xyz_xyz, BOX_EDGE_xyz_xYz },
    { BOX_EDGE_XYZ_xYZ, BOX_EDGE_xYZ_xyZ, BOX_EDGE_xyZ_XyZ, BOX_EDGE_XyZ_XYZ }
  };

csVector3 csBox3::GetCorner (int corner) const
{
  switch (corner)
  {
    case BOX_CORNER_xyz: return Min ();
    case BOX_CORNER_xyZ: return csVector3 (MinX (), MinY (), MaxZ ());
    case BOX_CORNER_xYz: return csVector3 (MinX (), MaxY (), MinZ ());
    case BOX_CORNER_xYZ: return csVector3 (MinX (), MaxY (), MaxZ ());
    case BOX_CORNER_Xyz: return csVector3 (MaxX (), MinY (), MinZ ());
    case BOX_CORNER_XyZ: return csVector3 (MaxX (), MinY (), MaxZ ());
    case BOX_CORNER_XYz: return csVector3 (MaxX (), MaxY (), MinZ ());
    case BOX_CORNER_XYZ: return Max ();
  }
  return csVector3 (0, 0, 0);
}

void csBox3::SetCenter (const csVector3& c)
{
  csVector3 move = c-GetCenter ();
  minbox += move;
  maxbox += move;
}

void csBox3::SetSize (const csVector3& s)
{
  csVector3 center = GetCenter ();
  minbox = center - s*(float).5;
  maxbox = center + s*(float).5;
}


bool csBox3::AdjacentX (const csBox3& other) const
{
  if (ABS (other.MinX () - MaxX ()) < SMALL_EPSILON ||
      ABS (other.MaxX () - MinX ()) < SMALL_EPSILON)
  {
    if (MaxY () < other.MinY () || MinY () > other.MaxY ()) return false;
    if (MaxZ () < other.MinZ () || MinZ () > other.MaxZ ()) return false;
    return true;
  }
  return false;
}

bool csBox3::AdjacentY (const csBox3& other) const
{
  if (ABS (other.MinY () - MaxY ()) < SMALL_EPSILON ||
      ABS (other.MaxY () - MinY ()) < SMALL_EPSILON)
  {
    if (MaxX () < other.MinX () || MinX () > other.MaxX ()) return false;
    if (MaxZ () < other.MinZ () || MinZ () > other.MaxZ ()) return false;
    return true;
  }
  return false;
}

bool csBox3::AdjacentZ (const csBox3& other) const
{
  if (ABS (other.MinZ () - MaxZ ()) < SMALL_EPSILON ||
      ABS (other.MaxZ () - MinZ ()) < SMALL_EPSILON)
  {
    if (MaxX () < other.MinX () || MinX () > other.MaxX ()) return false;
    if (MaxY () < other.MinY () || MinY () > other.MaxY ()) return false;
    return true;
  }
  return false;
}

int csBox3::Adjacent (const csBox3& other) const
{
  if (AdjacentX (other))
  {
    if (other.MaxX () > MaxX ()) return BOX_SIDE_X;
    else return BOX_SIDE_x;
  }
  if (AdjacentY (other))
  {
    if (other.MaxY () > MaxY ()) return BOX_SIDE_Y;
    else return BOX_SIDE_y;
  }
  if (AdjacentZ (other))
  {
    if (other.MaxZ () > MaxZ ()) return BOX_SIDE_Z;
    else return BOX_SIDE_z;
  }
  return -1;
}

int csBox3::GetVisibleSides (const csVector3& pos, int* visible_sides) const
{
  const csVector3& bmin = Min ();
  const csVector3& bmax = Max ();
  int idx;
  // First select x part of coordinate.
  if (pos.x < bmin.x)       idx = 0*9;
  else if (pos.x > bmax.x)  idx = 2*9;
  else              idx = 1*9;
  // Then y part.
  if (pos.y < bmin.y)       idx += 0*3;
  else if (pos.y > bmax.y)  idx += 2*3;
  else              idx += 1*3;
  // Then z part.
  if (pos.z < bmin.z)       idx += 0;
  else if (pos.z > bmax.z)  idx += 2;
  else              idx += 1;
  const Outline& ol = outlines[idx];
  int num_array = ol.num_sides;
  int i;
  for (i = 0 ; i < num_array ; i++)
    visible_sides[i] = ol.sides[i];
  return num_array;
}

void csBox3::GetConvexOutline (const csVector3& pos,
    csVector3* ar, int& num_array, bool bVisible) const
{
  const csVector3& bmin = Min ();
  const csVector3& bmax = Max ();
  int idx;
  // First select x part of coordinate.
  if (pos.x < bmin.x)       idx = 0*9;
  else if (pos.x > bmax.x)  idx = 2*9;
  else              idx = 1*9;
  // Then y part.
  if (pos.y < bmin.y)       idx += 0*3;
  else if (pos.y > bmax.y)  idx += 2*3;
  else              idx += 1*3;
  // Then z part.
  if (pos.z < bmin.z)       idx += 0;
  else if (pos.z > bmax.z)  idx += 2;
  else              idx += 1;

  const Outline& ol = outlines[idx];
  num_array = (bVisible ? ol.num : MIN (ol.num, 6));
  int i;
  for (i = 0 ; i < num_array ; i++)
  {
    switch (ol.vertices[i])
    {
      case 0: ar[i].x = bmin.x; ar[i].y = bmin.y; ar[i].z = bmin.z; break;
      case 1: ar[i].x = bmin.x; ar[i].y = bmin.y; ar[i].z = bmax.z; break;
      case 2: ar[i].x = bmin.x; ar[i].y = bmax.y; ar[i].z = bmin.z; break;
      case 3: ar[i].x = bmin.x; ar[i].y = bmax.y; ar[i].z = bmax.z; break;
      case 4: ar[i].x = bmax.x; ar[i].y = bmin.y; ar[i].z = bmin.z; break;
      case 5: ar[i].x = bmax.x; ar[i].y = bmin.y; ar[i].z = bmax.z; break;
      case 6: ar[i].x = bmax.x; ar[i].y = bmax.y; ar[i].z = bmin.z; break;
      case 7: ar[i].x = bmax.x; ar[i].y = bmax.y; ar[i].z = bmax.z; break;
    }
  }
}

bool csBox3::Between (const csBox3& box1, const csBox3& box2) const
{
  // First the trival test to see if the coordinates are
  // at least within the right intervals.
  if (((maxbox.x >= box1.minbox.x && minbox.x <= box2.maxbox.x) ||
       (maxbox.x >= box2.minbox.x && minbox.x <= box1.maxbox.x)) &&
      ((maxbox.y >= box1.minbox.y && minbox.y <= box2.maxbox.y) ||
       (maxbox.y >= box2.minbox.y && minbox.y <= box1.maxbox.y)) &&
      ((maxbox.z >= box1.minbox.z && minbox.z <= box2.maxbox.z) ||
       (maxbox.z >= box2.minbox.z && minbox.z <= box1.maxbox.z)))
  {
    // @@@ Ok, let's just return true here. Maybe this test is already
    // enough? We could have used the planes as well.
    return true;
  }
  return false;
}

void csBox3::ManhattanDistance (const csBox3& other, csVector3& dist) const
{
  if (other.MinX () >= MaxX ()) dist.x = other.MinX () - MaxX ();
  else if (MinX () >= other.MaxX ()) dist.x = MinX () - other.MaxX ();
  else dist.x = 0;
  if (other.MinY () >= MaxY ()) dist.y = other.MinY () - MaxY ();
  else if (MinY () >= other.MaxY ()) dist.y = MinY () - other.MaxY ();
  else dist.y = 0;
  if (other.MinZ () >= MaxZ ()) dist.z = other.MinZ () - MaxZ ();
  else if (MinZ () >= other.MaxZ ()) dist.z = MinZ () - other.MaxZ ();
  else dist.z = 0;
}


float csBox3::SquaredOriginDist () const
{
  // Thanks to Ivan Avramovic for the original.
  // Adapted by Norman Kramer, Jorrit Tyberghein and Wouter Wijngaards.
  float res = 0;
  if (minbox.x > 0) res = minbox.x*minbox.x;
  else if (maxbox.x < 0) res = maxbox.x*maxbox.x;
  if (minbox.y > 0) res += minbox.y*minbox.y;
  else if (maxbox.y < 0) res += maxbox.y*maxbox.y;
  if (minbox.z > 0) res += minbox.z*minbox.z;
  else if (maxbox.z < 0) res += maxbox.z*maxbox.z;;
  return res;
}

float csBox3::SquaredOriginMaxDist () const
{
  // Thanks to Ivan Avramovic for the original.
  // Adapted by Norman Kramer, Jorrit Tyberghein and Wouter Wijngaards.
  float res;
  if (minbox.x > 0) res = maxbox.x*maxbox.x;
  else if (maxbox.x < 0) res = minbox.x*minbox.x;
  else res = MAX (maxbox.x*maxbox.x, minbox.x*minbox.x);
  if (minbox.y > 0) res += maxbox.y*maxbox.y;
  else if (maxbox.y < 0) res += minbox.y*minbox.y;
  else res += MAX (maxbox.y*maxbox.y, minbox.y*minbox.y);
  if (minbox.z > 0) res += maxbox.z*maxbox.z;
  else if (maxbox.z < 0) res += minbox.z*minbox.z;
  else res += MAX (maxbox.z*maxbox.z, minbox.z*minbox.z);
  return res;
}


csBox3& csBox3::operator+= (const csBox3& box)
{
  if (box.minbox.x < minbox.x) minbox.x = box.minbox.x;
  if (box.minbox.y < minbox.y) minbox.y = box.minbox.y;
  if (box.minbox.z < minbox.z) minbox.z = box.minbox.z;
  if (box.maxbox.x > maxbox.x) maxbox.x = box.maxbox.x;
  if (box.maxbox.y > maxbox.y) maxbox.y = box.maxbox.y;
  if (box.maxbox.z > maxbox.z) maxbox.z = box.maxbox.z;
  return *this;
}

csBox3& csBox3::operator+= (const csVector3& point)
{
  if (point.x < minbox.x) minbox.x = point.x;
  if (point.x > maxbox.x) maxbox.x = point.x;
  if (point.y < minbox.y) minbox.y = point.y;
  if (point.y > maxbox.y) maxbox.y = point.y;
  if (point.z < minbox.z) minbox.z = point.z;
  if (point.z > maxbox.z) maxbox.z = point.z;
  return *this;
}

csBox3& csBox3::operator*= (const csBox3& box)
{
  if (box.minbox.x > minbox.x) minbox.x = box.minbox.x;
  if (box.minbox.y > minbox.y) minbox.y = box.minbox.y;
  if (box.minbox.z > minbox.z) minbox.z = box.minbox.z;
  if (box.maxbox.x < maxbox.x) maxbox.x = box.maxbox.x;
  if (box.maxbox.y < maxbox.y) maxbox.y = box.maxbox.y;
  if (box.maxbox.z < maxbox.z) maxbox.z = box.maxbox.z;
  return *this;
}

csBox3 operator+ (const csBox3& box1, const csBox3& box2)
{
  return csBox3(
    MIN(box1.minbox.x,box2.minbox.x),
    MIN(box1.minbox.y,box2.minbox.y),
    MIN(box1.minbox.z,box2.minbox.z),
    MAX(box1.maxbox.x,box2.maxbox.x),
    MAX(box1.maxbox.y,box2.maxbox.y),
    MAX(box1.maxbox.z,box2.maxbox.z) );
}

csBox3 operator+ (const csBox3& box, const csVector3& point)
{
  return csBox3(
    MIN(box.minbox.x,point.x),
    MIN(box.minbox.y,point.y),
    MIN(box.minbox.z,point.z),
    MAX(box.maxbox.x,point.x),
    MAX(box.maxbox.y,point.y),
    MAX(box.maxbox.z,point.z) );
}

csBox3 operator* (const csBox3& box1, const csBox3& box2)
{
  return csBox3(
    MAX(box1.minbox.x,box2.minbox.x),
    MAX(box1.minbox.y,box2.minbox.y),
    MAX(box1.minbox.z,box2.minbox.z),
    MIN(box1.maxbox.x,box2.maxbox.x),
    MIN(box1.maxbox.y,box2.maxbox.y),
    MIN(box1.maxbox.z,box2.maxbox.z));
}

bool operator== (const csBox3& box1, const csBox3& box2)
{
  return ( (box1.minbox.x == box2.minbox.x)
    && (box1.minbox.y == box2.minbox.y)
    && (box1.minbox.z == box2.minbox.z)
    && (box1.maxbox.x == box2.maxbox.x)
    && (box1.maxbox.y == box2.maxbox.y)
    && (box1.maxbox.z == box2.maxbox.z) );
}

bool operator!= (const csBox3& box1, const csBox3& box2)
{
  return ( (box1.minbox.x != box2.minbox.x)
    || (box1.minbox.y != box2.minbox.y)
    || (box1.minbox.z != box2.minbox.z)
    || (box1.maxbox.x != box2.maxbox.x)
    || (box1.maxbox.y != box2.maxbox.y)
    || (box1.maxbox.z != box2.maxbox.z) );
}

bool operator< (const csBox3& box1, const csBox3& box2)
{
  return ( (box1.minbox.x >= box2.minbox.x)
    && (box1.minbox.y >= box2.minbox.y)
    && (box1.minbox.z >= box2.minbox.z)
    && (box1.maxbox.x <= box2.maxbox.x)
    && (box1.maxbox.y <= box2.maxbox.y)
    && (box1.maxbox.z <= box2.maxbox.z) );
}

bool operator> (const csBox3& box1, const csBox3& box2)
{
  return ( (box2.minbox.x >= box1.minbox.x)
    && (box2.minbox.y >= box1.minbox.y)
    && (box2.minbox.z >= box1.minbox.z)
    && (box2.maxbox.x <= box1.maxbox.x)
    && (box2.maxbox.y <= box1.maxbox.y)
    && (box2.maxbox.z <= box1.maxbox.z) );
}

bool operator< (const csVector3& point, const csBox3& box)
{
  return ( (point.x >= box.minbox.x)
    && (point.x <= box.maxbox.x)
    && (point.y >= box.minbox.y)
    && (point.y <= box.maxbox.y)
    && (point.z >= box.minbox.z)
    && (point.z <= box.maxbox.z) );
}

//---------------------------------------------------------------------------