/Users/craigcornelius/Projects/SPRING Mac Release 0.2/boundingbox.cpp

Go to the documentation of this file.

// $Id: boundingbox.cpp,v 1.9 2006/05/24 16:52:40 sean Exp $
// $Copyright: (c)2001 National Biocomputation Center, Stanford University $

#include <list.h>
#include <GLUT/glut.h>

#include "boundingbox.h"
#include "facearray.h"
#include "object.h"


//*** BoundingBox ***

// constructor for BoundingBox superclass
BoundingBox::BoundingBox(BoundingBox *parent_)
{
    parent = parent_;
}

// destructor for BoundingBox superclass
BoundingBox::~BoundingBox()
{
    parent = NULL;
        object = NULL;
    min = Point3D(0, 0, 0);
    max = Point3D(-1, -1, -1);
}

// Creates a tree from a given object
BoundingBox* BoundingBox::createTree(Object* object) {
        int i;

        // Build list of faces
        List<BoundingBoxLeaf*> bbList;
        if (object->getCollisionFaces().NumElements() > 0) {
                // build tree with only collision faces
                for (i = 0; i < object->getCollisionFaces().NumElements(); i++) {
                        bbList.Append(new BoundingBoxLeaf(object->getCollisionFaces()[i]));
                }
        }
        else {
                // take all faces
                FaceArray* faceArray = object->getFaceArray();
                int numFaces = faceArray->getNumFaces();
                for (i = 0; i < numFaces; i++) {
                        bbList.Append(new BoundingBoxLeaf(faceArray->getFace(i)));
                }
        }

        // Return the tree
        return createTree(bbList);
}

// Creates a tree from a list of bounding box leafes
BoundingBox* BoundingBox::createTree(List<BoundingBoxLeaf*> &bbList) {
        int i;

        if (bbList.NumElements() == 0) {
                // no elements, return null!
                return NULL;
        }
        else if (bbList.NumElements() == 1) {
                // one element, return the single leaf itself!
                return bbList[0];
        }
        else {
                // Find min and max
                const double LARGE = 1e10;
                double min[3] = { LARGE, LARGE, LARGE };
                double max[3] = { -LARGE, -LARGE, -LARGE };

                for (i = 0; i < bbList.NumElements(); i++) {
                        BoundingBoxLeaf* leaf = bbList[i];
                        if (min[0] > leaf->min.x) {
                                min[0] = leaf->min.x;
                        }
                        if (max[0] < leaf->max.x) {
                                max[0] = leaf->max.x;
                        }
                        if (min[1] > leaf->min.y) {
                                min[1] = leaf->min.y;
                        }
                        if (max[1] < leaf->max.y) {
                                max[1] = leaf->max.y;
                        }
                        if (min[2] > leaf->min.z) {
                                min[2] = leaf->min.z;
                        }
                        if (max[2] < leaf->max.z) {
                                max[2] = leaf->max.z;
                        }
                }

                // Find axis (x, y -OR- z) where to split & middle
                int splitAxis = 0;
                if ((max[1] - min[1]) > (max[splitAxis] - min[splitAxis])) {
                        splitAxis = 1;
                }
                if ((max[2] - min[2]) > (max[splitAxis] - min[splitAxis])) {
                        splitAxis = 2;
                }
                double middle = (min[splitAxis] + max[splitAxis]) / 2;

                // split into two lists
                List<BoundingBoxLeaf*> bbListLeft;
                List<BoundingBoxLeaf*> bbListRight;
                for (i = 0; i < bbList.NumElements(); i++) {
                        BoundingBoxLeaf* leaf = bbList[i];
                        switch (splitAxis) {
                                case 0:
                                        if (leaf->getFace()->getCenter().x < middle) {
                                                bbListLeft.Append(leaf);
                                        }
                                        else {
                                                bbListRight.Append(leaf);
                                        }
                                        break;
                                case 1:
                                        if (leaf->getFace()->getCenter().y < middle) {
                                                bbListLeft.Append(leaf);
                                        }
                                        else {
                                                bbListRight.Append(leaf);
                                        }
                                        break;
                                case 2:
                                        if (leaf->getFace()->getCenter().z < middle) {
                                                bbListLeft.Append(leaf);
                                        }
                                        else {
                                                bbListRight.Append(leaf);
                                        }
                                        break;
                        }
                }

                // if one list empty, move one element
                if (bbListLeft.NumElements() == 0) {
                        bbListLeft.Append(bbListRight[0]);
                        bbListRight.DeleteElement(bbListRight[0]);
                }
                else if (bbListRight.NumElements() == 0) {
                        bbListRight.Append(bbListLeft[0]);
                        bbListLeft.DeleteElement(bbListLeft[0]);
                }

                // build tree
                BoundingBox* bbTreeLeft = createTree(bbListLeft);
                BoundingBox* bbTreeRight = createTree(bbListRight);

                // return tree
                BoundingBoxNode* bbTree = new BoundingBoxNode(bbTreeLeft, bbTreeRight);
                return bbTree;
        }
}

// draw bounding box for min and max
void BoundingBox::draw()
{
    // and draw myself (2x glVertext3f = One Line)
        if (hasMarker()) {
                // draw marker in purpule
                glColor3f(1.0, 0.0, 1.0);
        }
        else {
                // no marker -> gray translucent color
                glColor4f(0.8f, 0.8f, 0.8f, 0.6f);
        }

        // draw lines
        glBegin(GL_LINES);
                 glVertex3f(min.x, min.y, min.z);   
                 glVertex3f(max.x, min.y, min.z);   
                 glVertex3f(min.x, min.y, min.z);   
                 glVertex3f(min.x, max.y, min.z);   
                 glVertex3f(min.x, min.y, min.z);   
                 glVertex3f(min.x, min.y, max.z);   
                 
                 glVertex3f(min.x, max.y, max.z);
                 glVertex3f(max.x, max.y, max.z);
                 glVertex3f(min.x, max.y, max.z);
                 glVertex3f(min.x, min.y, max.z);
                 glVertex3f(min.x, max.y, max.z);
                 glVertex3f(min.x, max.y, min.z);

                 glVertex3f(max.x, min.y, max.z);
                 glVertex3f(max.x, max.y, max.z);
                 glVertex3f(max.x, min.y, max.z);
                 glVertex3f(min.x, min.y, max.z);
                 glVertex3f(max.x, min.y, max.z);
                 glVertex3f(max.x, min.y, min.z);

                 glVertex3f(max.x, max.y, min.z);
                 glVertex3f(max.x, max.y, max.z);
                 glVertex3f(max.x, max.y, min.z);
                 glVertex3f(min.x, max.y, min.z);
                 glVertex3f(max.x, max.y, min.z);
                 glVertex3f(max.x, min.y, min.z);
        glEnd();
}

// Returns true if boxes overlap, false otherwise
bool BoundingBox::overlap(BoundingBox* boundingBox) {
        Point3D otherMin = boundingBox->getMin();
        Point3D otherMax = boundingBox->getMax();

        if ((otherMin.x < max.x) && (otherMax.x > min.x) &&
                (otherMin.y < max.y) && (otherMax.y > min.y) &&
                (otherMin.z < max.z) && (otherMax.z > min.z)) {
                // yipee! there's an overlap
                return true;
        }
        else {
                // nope, no overlap
                return false;
        }
}

// Returns the center of the bounding box
Point3D BoundingBox::center() {
        Point3D center;
        center.x = (min.x + max.x) / 2;
        center.y = (min.y + max.y) / 2;
        center.z = (min.z + max.z) / 2;
        return center;
}

//*** BoundingBoxNode ***

// Constructor for node
BoundingBoxNode::BoundingBoxNode(BoundingBox *left_, 
                                 BoundingBox *right_, 
                                                                 BoundingBox *parent_) : BoundingBox(parent_)
{
    left = left_;
    right = right_;
        marker = false;

    if (left) {
        left->parent = this;
                object = left->getObject();
    }
    if (right) {
        right->parent = this;
                object = right->getObject();
    }

        // non-recursive update 
        internalUpdate();
}

// node destructor, recursively deletes its subtree
BoundingBoxNode::~BoundingBoxNode()
{
    if (left) {
                delete left;
        }
        if (right) {
                delete right;
        }

    left = NULL;
    right = NULL;
}

// draw all the boxes
void BoundingBoxNode::draw()
{
    // recurse
    if (left) {
        left->draw();
        }
    if (right) {
        right->draw();
        }

        // draw myself
        BoundingBox::draw();
}

// update bounding box positions
void BoundingBoxNode::update() 
{
        // update left and right min maxes first (recursive)
        left->update();
        right->update();

        // non-recursive self-update
        internalUpdate();
}

// internal update without recursion
void BoundingBoxNode::internalUpdate() {
        // based on new left and right bounding box, calculate new
        Point3D minLeft = left->getMin();
        Point3D maxLeft = left->getMax();
        Point3D minRight = right->getMin();
        Point3D maxRight = right->getMax();

        min.x = (minLeft.x < minRight.x) ? minLeft.x : minRight.x;
        min.y = (minLeft.y < minRight.y) ? minLeft.y : minRight.y;
        min.z = (minLeft.z < minRight.z) ? minLeft.z : minRight.z;
        max.x = (maxLeft.x > maxRight.x) ? maxLeft.x : maxRight.x;
        max.y = (maxLeft.y > maxRight.y) ? maxLeft.y : maxRight.y;
        max.z = (maxLeft.z > maxRight.z) ? maxLeft.z : maxRight.z;

        // adjust normal vector
        normal = left->getNormal() + right->getNormal();
        normal.Normalize();
}

// detect collisions
void BoundingBoxNode::detectCollisions(BoundingBox* boundingBox, int myLevel, int otherLevel,
                                                                           ReallocableArray<CollisionBoxPair>* collisionPairs)
{
        if (overlap(boundingBox)) {
                if (boundingBox->isLeaf()) {
                        if (myLevel > 0) {
                                // recursively detect collisions
                                myLevel--;
                                left->detectCollisions(boundingBox, myLevel, otherLevel, collisionPairs);
                                right->detectCollisions(boundingBox, myLevel, otherLevel, collisionPairs);
                        }
                        else {
                                // just add current solution as collision pair (approximation)
                                Face* otherFace = ((BoundingBoxLeaf*)boundingBox)->getFace();
                                if (otherFace->intersectsBox(&min, &max)) {
                                        CollisionBoxPair collisionPair;
                                        collisionPair.myCollisionBox = this;
                                        collisionPair.otherCollisionBox = boundingBox;
                                        collisionPairs->Append(collisionPair);
                                }
                        }
                }
                else {
                        if ((myLevel > 0) && (otherLevel > 0)) {
                                if (getVolume() > boundingBox->getVolume()) {
                                        // recursively detect collisions
                                        otherLevel--;
                                        detectCollisions(((BoundingBoxNode*)boundingBox)->getLeft(), 
                                                             myLevel, otherLevel, collisionPairs);
                                        detectCollisions(((BoundingBoxNode*)boundingBox)->getRight(), 
                                                             myLevel, otherLevel, collisionPairs);
                                }
                                else {
                                        // recursively detect collisions
                                        myLevel--;
                                        left->detectCollisions(boundingBox, myLevel, otherLevel, collisionPairs);
                                        right->detectCollisions(boundingBox, myLevel, otherLevel, collisionPairs);
                                }
                        }
                        else if ((myLevel <= 0) && (otherLevel <= 0)) {
                                // just add current solution as collision pair (approximation)
                                CollisionBoxPair collisionPair;
                                collisionPair.myCollisionBox = this;
                                collisionPair.otherCollisionBox = boundingBox;
                                collisionPairs->Append(collisionPair);
                        }
                        else if (myLevel > 0) {
                                // recursively detect collisions
                                myLevel--;
                                left->detectCollisions(boundingBox, myLevel, otherLevel, collisionPairs);
                                right->detectCollisions(boundingBox, myLevel, otherLevel, collisionPairs);
                        }
                        else {
                                // recursively detect collisions
                                otherLevel--;
                                detectCollisions(((BoundingBoxNode*)boundingBox)->getLeft(), 
                                                         myLevel, otherLevel, collisionPairs);
                                detectCollisions(((BoundingBoxNode*)boundingBox)->getRight(), 
                                                         myLevel, otherLevel, collisionPairs);
                        }
                }
        }
}

// Returns the depth of the collision
double BoundingBoxNode::collisionDepth(BoundingBox* boundingBox) {
        if (boundingBox->isLeaf()) {
                // 1. we calculate the distance from triangle to center of bounding box
                Face* otherFace = ((BoundingBoxLeaf*)boundingBox)->getFace();
                Point3D bbCenter = center();
                double distance = otherFace->PlaneDistanceToPoint(bbCenter);

                // 2. we subtract the length of bounding box center to one of its nodes
                Point3D bbVector = bbCenter - min;
                double length = bbVector.Length();

                return distance - length;
        }
        else {
                // compare depth of two bounding boxes
                Point3D otherMin = boundingBox->getMin();
                Point3D otherMax = boundingBox->getMax();

                double xDepth = min.x - otherMin.x;
                if (xDepth < 0) {
                        xDepth = -xDepth;
                }
                xDepth = xDepth - (getWidth() / 2) - (boundingBox->getWidth() / 2);
                if (xDepth > 0) {
                        xDepth = 0;
                }

                double yDepth = min.y - otherMin.y;
                if (yDepth < 0) {
                        yDepth = -yDepth;
                }
                yDepth = yDepth - (getHeight() / 2) - (boundingBox->getHeight() / 2);
                if (yDepth > 0) {
                        yDepth = 0;
                }

                double zDepth = min.z - otherMin.z;
                if (zDepth < 0) {
                        zDepth = -zDepth;
                }
                zDepth = zDepth - (getDepth() / 2) - (boundingBox->getDepth() / 2);
                if (zDepth > 0) {
                        zDepth = 0;
                }

                return xDepth + yDepth + zDepth;
        }
}



//*** BoundingBoxLeaf ***

// Constructor for leaf
BoundingBoxLeaf::BoundingBoxLeaf(Face *face_, BoundingBox *parent_) : BoundingBox(parent_)
{
    face = face_;
        object = face->getFaceArray()->getObject();

        // update min max
        update();
}

// leaf destructor
BoundingBoxLeaf::~BoundingBoxLeaf()
{
    face = NULL;
}

// update bounding box positions
void BoundingBoxLeaf::update() 
{
        // get min and max
        const double LARGE = 1e10;
        min = Point3D(LARGE, LARGE, LARGE);
        max = Point3D(-LARGE, -LARGE, -LARGE);
        for (int i = 0; i < 3; i++) {
                Node* node = face->getNodeLink(i);
                if (node->p.x < min.x) {
                        min.x = node->p.x;
                }
                if (node->p.x > max.x) {
                        max.x = node->p.x;
                }
                if (node->p.y < min.y) {
                        min.y = node->p.y;
                }
                if (node->p.y > max.y) {
                        max.y = node->p.y;
                }
                if (node->p.z < min.z) {
                        min.z = node->p.z;
                }
                if (node->p.z > max.z) {
                        max.z = node->p.z;
                }
        }

        // adjust normal
        normal = face->getNormal();
}

// detect collisions
void BoundingBoxLeaf::detectCollisions(BoundingBox* boundingBox, int myLevel, int otherLevel,
                                                                           ReallocableArray<CollisionBoxPair>* collisionPairs)
{
        if (overlap(boundingBox)) {
                if (boundingBox->isLeaf()) {
                        // check if faces intersect
                        Face* otherFace = ((BoundingBoxLeaf*)boundingBox)->getFace();
                        if (face->intersectsFace(otherFace)) {
                                // if overlap, add as collision pair
                                CollisionBoxPair collisionPair;
                                collisionPair.myCollisionBox = this;
                                collisionPair.otherCollisionBox = boundingBox;
                                collisionPairs->Append(collisionPair);
                        }
                }
                else {
                        // recursively detect collisions
                        if (otherLevel > 0) {
                                // need to go further down
                                otherLevel--;
                                detectCollisions(((BoundingBoxNode*)boundingBox)->getLeft(), 
                                                     myLevel, otherLevel, collisionPairs);
                                detectCollisions(((BoundingBoxNode*)boundingBox)->getRight(), 
                                                     myLevel, otherLevel, collisionPairs);
                        }
                        else {
                                // just add current solution as collision pair (approximation)
                                if (face->intersectsBox(&boundingBox->getMin(), &boundingBox->getMax())) {
                                        CollisionBoxPair collisionPair;
                                        collisionPair.myCollisionBox = this;
                                        collisionPair.otherCollisionBox = boundingBox;
                                        collisionPairs->Append(collisionPair);
                                }
                        }
                }
        }
}

// Returns the depth of the collision (=0 is no collision / <0 is collision depth)
double BoundingBoxLeaf::collisionDepth(BoundingBox* boundingBox) {
        if (boundingBox->isLeaf()) {
                // find deepest node in other triangle
                Face* otherFace = ((BoundingBoxLeaf*)boundingBox)->getFace();
                double minDistance = 0;
                for (int i = 0; i < 3; i++) {
                        Node* node = face->getNodeLink(i);
                        double currentDistance = otherFace->PlaneDistanceToPoint(node->p);
                        if (currentDistance < minDistance) { 
                                minDistance = currentDistance; 
                        }
                }
                return minDistance;
        }
        else {
                // 1. we calculate the distance from triangle to center of bounding box 
                Point3D bbCenter = boundingBox->center();
                double distance = face->PlaneDistanceToPoint(bbCenter);

                // 2. we subtract the length of bounding box center to one of its nodes
                Point3D bbVector = bbCenter - boundingBox->getMin();
                double length = bbVector.Length();

                return distance - length;
        }
}

---