00001 /*************************************************************************** 00002 octant.h - description 00003 ------------------- 00004 begin : Wed Feb 25 2004 00005 copyright : (C) 2004 by Roman Geus 00006 email : roman.geus@psi.ch 00007 ***************************************************************************/ 00008 00009 /*************************************************************************** 00010 * * 00011 * This program is free software; you can redistribute it and/or modify * 00012 * it under the terms of the GNU General Public License as published by * 00013 * the Free Software Foundation; either version 2 of the License, or * 00014 * (at your option) any later version. * 00015 * * 00016 ***************************************************************************/ 00017 00018 #ifndef OCTANT_H 00019 #define OCTANT_H 00020 00021 #include <vector> 00022 #include <ostream> 00023 #include "vector3.h" 00024 00025 namespace mesh { 00026 00032 template <typename NodeType> 00033 class Octant { 00034 public: 00037 Octant(const Vector3& center, double length); 00040 Octant(Octant* parent, int idx); 00043 ~Octant(); 00046 int get_child_index_for_point(const Vector3& node_center); 00049 void add_node(NodeType* node); 00052 void dump(std::ostream& str); 00053 00055 Vector3 _center; 00057 double _length; 00059 Octant* _parent; 00061 Octant* _children[8]; 00063 std::vector<NodeType *> _nodes; 00064 }; 00065 00066 template <typename NodeType> 00067 Octant<NodeType>::Octant(const Vector3& center, double length) 00068 : _parent(0) 00069 { 00070 // initialize all children to null. 00071 for (int i = 0; i < 8; i ++) 00072 _children[i] = 0; 00073 // set bounding box 00074 _center = center; 00075 _length = length; 00076 } 00077 00078 template <typename NodeType> 00079 Octant<NodeType>::Octant(Octant* parent, int idx) 00080 : _parent(parent) 00081 { 00082 // initialize all children to null. 00083 for (int i = 0; i < 8; i ++) 00084 _children[i] = 0; 00085 // set bounding box 00086 _length = 0.5 * parent->_length; 00087 for (int i = 0; i < 3; i ++) 00088 if (idx & (0x1 << i)) 00089 _center[i] = parent->_center[i] + _length; 00090 else 00091 _center[i] = parent->_center[i] - _length; 00092 } 00093 00094 template <typename NodeType> 00095 Octant<NodeType>::~Octant() { 00096 for (int i = 0; i < 8; i ++) 00097 delete _children[i]; 00098 _parent = 0; 00099 } 00100 00101 template <typename NodeType> 00102 int Octant<NodeType>::get_child_index_for_point(const Vector3& point) { 00103 int child_idx = 0; 00104 Vector3 disp = point - _center; 00105 if ( disp.x > 0 ) 00106 child_idx += 1; 00107 if ( disp.y > 0 ) 00108 child_idx += 2; 00109 if ( disp.z > 0 ) 00110 child_idx += 4; 00111 return child_idx; 00112 } 00113 00114 template <typename NodeType> 00115 void Octant<NodeType>::add_node(NodeType* node) { 00116 _nodes.push_back(node); 00117 } 00118 00119 template <typename NodeType> 00120 void Octant<NodeType>::dump(std::ostream& str) { 00121 Octant* octant = this; 00122 00123 do { 00124 str << "Octant([" 00125 << octant->_center.x << "," 00126 << octant->_center.y << "," 00127 << octant->_center.z << "," 00128 << "], " << octant->_length << ")\n"; 00129 octant = octant->_parent; 00130 } while (octant != 0); 00131 } 00132 00133 } // namespace mesh 00134 00135 #endif