/Users/craigcornelius/Projects/SPRING Mac Release 0.2/boundingsphere.h

Go to the documentation of this file.

// $Id: boundingsphere.h,v 1.23 2006/05/25 22:08:39 craig Exp $
// $Copyright: (c)2001 National Biocomputation Center, Stanford University $

#ifndef BoundingSphere_Header
#define BoundingSphere_Header

#ifdef _WIN32
#pragma warning ( push )
#pragma warning ( disable : 4786 )
#endif 


#include <assert.h>

#include "list.h"
#include "set.h"

// uses comparison function to keep in order
template <class T> class Priority_queue {
#ifdef NOT_YET
    void push(T& item) {}
    void pop() {}
    T& top() {}
    int empty() { return(1); }
#endif
};

#include "point3d.h"

const double SMALL = 1e-10;
const double LARGE = 1e10;

class BoundingSphere;
class BoundingSphereLeaf;
class Tetra;
class Face;
class Edge;
class Node;
class Object;
#ifndef _WIN32
//template <class T, class Sequence, class Compare> class priority_queue;
#endif

struct scompare {
    bool operator() (const BoundingSphere* s1, const BoundingSphere* s2) const;
};


// used to store instances of sphere leaf objects
typedef List<BoundingSphere*> BSlist;

// used to put sphere leafs in a set
typedef Set<BoundingSphereLeaf*> BSLset;

// used to put sphere leafs in a queue
typedef Priority_queue<BoundingSphere *> BSqueue;

typedef enum {tetra_ptr, face_ptr, edge_ptr, node_ptr} Feature_type;

typedef union {
    Tetra* tetra;
    Face* face;
    Edge* edge;
    Node* node;
} Feature_ptr;

class BoundingSphereNode;
class BoundingSphereLeaf;

// generic class 
class BoundingSphere {
    friend class BoundingSphereNode;
    friend class BoundingSphereLeaf;
    friend struct scompare;
public:
    BoundingSphere(BoundingSphere* parent);
    virtual ~BoundingSphere();
    
    static const char* rcsid;
    static int debug;
    static int return_first_collision_only;             // defaults to 0
    
    // handy helper functions
    inline Point3D getCenter() {return(center);}
    inline double getRadius() {return(radius);}
 
    inline  BoundingSphere* getParent() { return parent;}
    inline  void setParent(BoundingSphere* p) { parent = p;}
    inline int getLevel() { return (level); }
    int numLeafs();
    int getDepth();
    int hasAncestor(BoundingSphere* b);
    BoundingSphereNode* findCommonAncestor(BoundingSphere* b[], int num);
    
    bool remainsValid(Point3D newCenter, double newRadius, double threshold);
    virtual bool isLeaf() = 0;
    
    // for collision detection
    static Node* findClosestNode(BoundingSphere *s, Point3D pt,
        double *thresh);
    
    static int dist(BoundingSphere *sa, BoundingSphere *sb, double error = 0,
        double init = LARGE);
    
    // for dynamically adding to tree
    static int addLeaf(BoundingSphereLeaf* sa, BoundingSphere* sb);
    static int removeLeaf(BoundingSphereLeaf* sa);
    
    // for increasing performance
    int enabled;
    int numEnabledLeafs();
    void markTreeEnabled(int enabled);
    void propEnabled(int enabled);
    
    // for updating the tree
    virtual bool procChange() = 0;
    inline virtual void propChange()
    {if (procChange() && (parent != NULL)) parent->propChange();}
    
protected:
    BoundingSphere* parent;
    Point3D        center;
    double         radius;
    int            level;
    bool           inQueue;
private:
    static BSqueue spherePQ;
};


// root of a tree 
class BoundingSphereNode : public BoundingSphere {
public:
    BoundingSphereNode(BoundingSphere *left_ = NULL, 
        BoundingSphere *right_ = NULL, 
        BoundingSphere *parent_ = NULL);
    BoundingSphereNode(BSlist &sphereList, BoundingSphere *parent_ = NULL);
    virtual ~BoundingSphereNode();
    
    bool isLeaf() {return(false);}
    void drawSubtree();
    
    Node *findClosestNode(Point3D pt, double *thresh);
    static int dist(BoundingSphereNode *sa, BoundingSphere *sb, 
        double error = 0, double init = LARGE);
    
    bool procChange();
    
    BoundingSphere* getLeft() {return left;}
    BoundingSphere* getRight() {return right;}
    
    void setLeft(BoundingSphere* lt) {left = lt;}
    void setRight(BoundingSphere* rt) {right = rt;}
    
private: 
    BoundingSphere *left, *right;
};


// leaf nodes in a tree 
class BoundingSphereLeaf : public BoundingSphere {
public:
    // note: you could make another contructor that taken in edges,
    // for edge tests, steve had it read in primatives
    BoundingSphereLeaf(Tetra *tetra_, BoundingSphere *parent_ = NULL);
    BoundingSphereLeaf(Face *face_, BoundingSphere *parent_ = NULL);
    BoundingSphereLeaf(Edge *edge_, BoundingSphere *parent_ = NULL);
    BoundingSphereLeaf(Node *node_, BoundingSphere *parent_ = NULL);
    virtual ~BoundingSphereLeaf();
    
    bool isLeaf()       {return(true);}
    void draw();
    
    Node *findClosestNode(Point3D pt, double *thresh);
    //int dist(BoundingSphere *other, double error = 0, double init = LARGE);
    static int dist(BoundingSphereLeaf *sa, BoundingSphereLeaf *sb, 
        double error = 0, double init = LARGE);
    
    void insertInUpdateList();
    
    bool procChange();
    static void processUpdate();
    
    inline Feature_type getFeatureType() {return(feature_type);}
    inline Feature_ptr getFeaturePtr() {return(feature_ptr);}
    Object* getFeatureObject();
    int getFeatureIndex();
    
    inline Tetra* getTetra() {return(feature_ptr.tetra);}               
    inline Face* getFace() {return(feature_ptr.face);}
    inline Edge* getEdge() {return(feature_ptr.edge);}
    inline Node* getNode() {return(feature_ptr.node);}
    
    void setRadiusAndCenterFromFeature();
    
private:
    Feature_type feature_type;
    Feature_ptr feature_ptr;
    
    static BSLset sphereLeafSet; // each leaf knows about the set
};

#ifdef _WIN32
#pragma warning (pop)
#endif

#endif

---