node.h
Go to the documentation of this file.
00001 #ifndef MEGATREE_NODE_H
00002 #define MEGATREE_NODE_H
00003 
00004 #include <megatree/long_id.h>
00005 #include <megatree/tree_common.h>
00006 #include <megatree/node_geometry.h>
00007 #include <sstream>
00008 #include <vector>
00009 
00010 
00011 namespace megatree
00012 {
00013 
00014 class NodeFile;
00015 
00016   static const double BITS_D = 65536.0;
00017   static const double BITS_2_D = 32768.0;
00018   static const uint64_t BITS = 65536;
00019   static const uint64_t BITS_2 = 32768;
00020 
00021 
00022 // Node
00023 class Node
00024 {
00025 // nodefile gets access to private variables to easily construct a node
00026 friend class NodeFile;
00027 friend class NodeHandle;
00028 
00029 
00030 public:
00031   Node()
00032     :count(0), children(0)
00033   {
00034     point[0] = point[1] = point[2] = 0;
00035     color[0] = color[1] = color[2] = 0;
00036   }
00037 
00038 
00039   bool isEmpty() const
00040   {
00041     return count == 0;
00042   }
00043 
00044 
00045   Count getCount() const
00046   {
00047     return count;
00048   }
00049 
00050 
00051   bool isLeaf() const
00052   {
00053     return children == 0;
00054   }
00055 
00056 
00057   bool hasChild(uint8_t i) const
00058   {
00059     assert(i < 8);
00060     return (children >> i) & 1;
00061   }
00062 
00063   void setChild(uint8_t i)
00064   {
00065     assert(i < 8);
00066     children |= (1 << i);
00067   }
00068 
00069 
00070   void copyFromChildNodes(Node* child_nodes[8]) 
00071   {
00072     children = 0;
00073     count = 0;
00074     uint64_t sum_point[3] = {0,0,0};
00075     uint64_t sum_color[3] = {0,0,0};
00076 
00077     for (unsigned int i = 0; i < 8; i++)
00078     {
00079       if (child_nodes[i])
00080       {
00081         children += (1 << i);
00082         //printf("using %s\n", child_nodes[i]->toString().c_str());
00083 
00084         const Count& child_cnt = child_nodes[i]->count;
00085         Point* child_pnt = child_nodes[i]->point;
00086         Color* child_col = child_nodes[i]->color;
00087         
00088         uint64_t child_offset[3];
00089         getChildBitOffset(i, child_offset);
00090 
00091         sum_point[0] += child_cnt * (child_pnt[0] + child_offset[0]);
00092         sum_point[1] += child_cnt * (child_pnt[1] + child_offset[1]);
00093         sum_point[2] += child_cnt * (child_pnt[2] + child_offset[2]);
00094 
00095         sum_color[0] += child_cnt * child_col[0];
00096         sum_color[1] += child_cnt * child_col[1];
00097         sum_color[2] += child_cnt * child_col[2];
00098 
00099         // TODO: sum will overflow at some point.
00100         count += child_cnt;
00101       }
00102     }
00103 
00104     //we need to shift back down because we go up a level higher than we store
00105     //things to compute the average, getChildBitOffset holds the shifts that
00106     //bump things up, perhaps that should change at some point
00107     point[0] = (sum_point[0] / count) >> 1;
00108     point[1] = (sum_point[1] / count) >> 1;
00109     point[2] = (sum_point[2] / count) >> 1;
00110 
00111     color[0] = sum_color[0] / count;
00112     color[1] = sum_color[1] / count;
00113     color[2] = sum_color[2] / count;
00114 
00115     //printf("result %s\n", toString().c_str());
00116   }
00117 
00118 
00119   uint8_t getChildForNodePoint()
00120   {
00121     return  (point[0] >= BITS_2) << X_BIT | 
00122             (point[1] >= BITS_2) << Y_BIT | 
00123             (point[2] >= BITS_2) << Z_BIT;
00124   }
00125 
00126 
00127 
00128   void copyToChildNode(uint8_t child, Node* child_node) const
00129   {
00130     if (child & (1 << X_BIT))
00131       assert(point[0] >= BITS_2);
00132     else
00133       assert(point[0] < BITS_2);
00134     if (child & (1 << Y_BIT))
00135       assert(point[1] >= BITS_2);
00136     else
00137       assert(point[1] < BITS_2);
00138     if (child & (1 << Z_BIT))
00139       assert(point[2] >= BITS_2);
00140     else
00141       assert(point[2] < BITS_2);
00142 
00143     //just drop the most significant bit to drop the point down from the parent
00144     //to child bucket
00145     child_node->point[0] = point[0] << 1;
00146     child_node->point[1] = point[1] << 1;
00147     child_node->point[2] = point[2] << 1;
00148 
00149     child_node->color[0] = color[0];
00150     child_node->color[1] = color[1];
00151     child_node->color[2] = color[2];
00152     child_node->count = count;
00153 
00154     /*
00155     printf("Copied node %d %d %d into child %d: %d %d %d\n",
00156            (unsigned)(point[0]), (unsigned)(point[1]), (unsigned)(point[2]),
00157            child, (unsigned)(child_node->point[0]), (unsigned)(child_node->point[1]), (unsigned)(child_node->point[2]));
00158     */
00159   }
00160 
00161 
00162 
00163   void getChildBitOffset(uint8_t child, double* child_position) const
00164   {
00165     child_position[0] = (child & (1 << X_BIT)) ? BITS_D : 0;
00166     child_position[1] = (child & (1 << Y_BIT)) ? BITS_D : 0;
00167     child_position[2] = (child & (1 << Z_BIT)) ? BITS_D : 0;
00168   }
00169 
00170   void getChildBitOffset(uint8_t child, uint64_t* child_position) const
00171   {
00172     child_position[0] = (child & (1 << X_BIT)) ? BITS : 0;
00173     child_position[1] = (child & (1 << Y_BIT)) ? BITS : 0;
00174     child_position[2] = (child & (1 << Z_BIT)) ? BITS : 0;
00175   }
00176 
00177 
00178   double* getPoint(const NodeGeometry& ng, double pnt[3]) const
00179   {
00180     fixed_to_float(ng, point, pnt);
00181     return pnt;
00182   }
00183 
00184 
00185   double* getColor(double col[3]) const
00186   {
00187     col[0] = (double)color[0];
00188     col[1] = (double)color[1];
00189     col[2] = (double)color[2];
00190 
00191     return col;
00192   }
00193 
00194   float* getColor(float col[3]) const
00195   {
00196     col[0] = (float)color[0];
00197     col[1] = (float)color[1];
00198     col[2] = (float)color[2];
00199 
00200     return col;
00201   }
00202 
00203   void addPoint(const NodeGeometry& ng, const double* pt_float, const double* col)
00204   {
00205     assert(ng.contains(pt_float));
00206 
00207     // Converts to internal fixed-precision representation.
00208     Point pt[3];
00209     float_to_fixed(ng, pt_float, pt);
00210 
00211     // Computes the moving average.  Note that the points are discretized, so this computation is somewhat incorrect.
00212     count++;
00213     double f = 1.0 / (double)count;
00214     point[0] = (1.0 - f) * (double)(point[0])  + f * (double)(pt[0]);
00215     point[1] = (1.0 - f) * (double)(point[1])  + f * (double)(pt[1]);
00216     point[2] = (1.0 - f) * (double)(point[2])  + f * (double)(pt[2]);
00217     color[0] = (1.0 - f) * (double)(color[0])  + f * col[0];
00218     color[1] = (1.0 - f) * (double)(color[1])  + f * col[1];
00219     color[2] = (1.0 - f) * (double)(color[2])  + f * col[2];
00220 
00221   }
00222 
00223 
00224   void setPoint(const NodeGeometry& ng, const double* pt, const double* col, Count cnt=1)
00225   {
00226     if (!ng.contains(pt))
00227     {
00228       fprintf(stderr, "Node::setPoint()  Point (%lf, %lf, %lf) is not inside the geometry "
00229               "(%lf, %lf, %lf)--(%lf, %lf, %lf)\n", pt[0], pt[1], pt[2],
00230               ng.getLo(0), ng.getLo(1), ng.getLo(2), ng.getHi(0), ng.getHi(1), ng.getHi(2));
00231       abort();
00232     }
00233 
00234     count = cnt;
00235     float_to_fixed(ng, pt, point);
00236     color[0] = col[0];
00237     color[1] = col[1];
00238     color[2] = col[2];
00239   }
00240 
00241   bool operator==(const Node& n) const
00242   {
00243     return point[0] == n.point[0] &&
00244            point[1] == n.point[1] &&
00245            point[2] == n.point[2] &&
00246            color[1] == n.color[0] &&
00247            color[1] == n.color[1] &&
00248            color[2] == n.color[2] &&
00249            count == n.count &&
00250            children == n.children;
00251   }
00252   
00253   void reset()
00254   {
00255     count = 0;
00256     children = 0;
00257   }
00258 
00259   Node& operator =(const Node& n)
00260   {
00261     count = n.count;
00262     point[0] = n.point[0];  point[1] = n.point[1];  point[2] = n.point[2];
00263     color[0] = n.color[0];  color[1] = n.color[1];  color[2] = n.color[2];
00264     children = n.children;
00265     
00266     return *this;
00267   }
00268 
00269   friend class NodeCache;
00270 private:
00271   Count count;
00272   Point point[3];
00273   Color color[3];
00274   
00275   // which children exist
00276   uint8_t children;
00277 
00278 
00279   // Conversions between external floating point representation and
00280   // internal fixed precision representation.
00281   void float_to_fixed(const NodeGeometry &ng, const double pt_float[3], Point pt_fixed[3]) const
00282   {
00283     // Scales to [0,1), then to [0,BITS_D), then truncates to the integral type.
00284     //                   |<--               [0, BITS_D)                                 -->|
00285     //                             |<--     [0, 1)                                      -->|
00286     //                             |<--     [0, hi-lo)    -->|
00287     pt_fixed[0] = (Point)(BITS_D * (pt_float[0] - ng.getLo(0)) / (ng.getHi(0) - ng.getLo(0)));
00288     pt_fixed[1] = (Point)(BITS_D * (pt_float[1] - ng.getLo(1)) / (ng.getHi(1) - ng.getLo(1)));
00289     pt_fixed[2] = (Point)(BITS_D * (pt_float[2] - ng.getLo(2)) / (ng.getHi(2) - ng.getLo(2)));
00290   }
00291   void fixed_to_float(const NodeGeometry &ng, const Point pt_fixed[3], double pt_float[3]) const
00292   {
00293     // Scales from [0, BITS_D) to [0, 1) to [lo, hi)
00294     //                           |<--   [0, 1)  (shifted by 0.5)  -->|
00295     //                          |<--    [0, hi-lo)                                              -->| 
00296     pt_float[0] = ng.getLo(0) + ((double(pt_fixed[0]) + 0.5) / BITS_D) * (ng.getHi(0) - ng.getLo(0));
00297     pt_float[1] = ng.getLo(1) + ((double(pt_fixed[1]) + 0.5) / BITS_D) * (ng.getHi(1) - ng.getLo(1));
00298     pt_float[2] = ng.getLo(2) + ((double(pt_fixed[2]) + 0.5) / BITS_D) * (ng.getHi(2) - ng.getLo(2));
00299   }
00300 };
00301 
00302 
00303 }
00304 #endif


megatree_cpp
Author(s): Stuart Glaser
autogenerated on Thu Nov 28 2013 11:30:34