00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #ifndef _OCTREE_HPP_
00025 #define _OCTREE_HPP_
00026
00027 #include <boost/format.hpp>
00028 #include <boost/utility.hpp>
00029 #include <vector>
00030 #include <iostream>
00031 #include <deque>
00032 #include <stdint.h>
00033
00034 namespace mapnik {
00035
00036 typedef uint8_t byte ;
00037 struct rgb
00038 {
00039 byte r;
00040 byte g;
00041 byte b;
00042 rgb(byte r_, byte b_, byte g_)
00043 : r(r_), g(g_), b(b_) {}
00044 };
00045
00046 struct RGBPolicy
00047 {
00048 const static unsigned MAX_LEVELS = 6;
00049 inline static unsigned index_from_level(unsigned level, rgb const& c)
00050 {
00051 unsigned shift = (MAX_LEVELS + 1) - level;
00052 return (((c.r >> shift) & 1) << 2)
00053 | (((c.g >> shift) & 1) << 1)
00054 | ((c.b >> shift) & 1);
00055 }
00056 };
00057
00058 template <typename T, typename InsertPolicy = RGBPolicy >
00059 class octree : private boost::noncopyable
00060 {
00061 struct node
00062 {
00063 node ()
00064 : reds(0),
00065 greens(0),
00066 blues(0),
00067 count(0),
00068 index(0)
00069 {
00070 memset(&children_[0],0,sizeof(children_));
00071 }
00072
00073 ~node ()
00074 {
00075 for (unsigned i = 0;i < 8; ++i) {
00076 if (children_[i] != 0) delete children_[i],children_[i]=0;
00077 }
00078 }
00079
00080 bool is_leaf() const { return count == 0; }
00081 node * children_[8];
00082 unsigned reds;
00083 unsigned greens;
00084 unsigned blues;
00085 unsigned count;
00086 uint8_t index;
00087 };
00088 struct node_cmp
00089 {
00090 bool operator() ( const node * lhs,const node* rhs) const
00091 {
00092 unsigned left_total=0;
00093 unsigned right_total=0;
00094 for (unsigned i=0; i<8;++i)
00095 {
00096 if (lhs->children_[i]) left_total+=lhs->children_[i]->count;
00097 if (rhs->children_[i]) right_total+=rhs->children_[i]->count;
00098 }
00099 return left_total < right_total;
00100 }
00101 };
00102
00103 std::deque<node*> reducible_[InsertPolicy::MAX_LEVELS];
00104 unsigned max_colors_;
00105 unsigned colors_;
00106 unsigned leaf_level_;
00107
00108 public:
00109 explicit octree(unsigned max_colors=256)
00110 : max_colors_(max_colors),
00111 colors_(0),
00112 leaf_level_(InsertPolicy::MAX_LEVELS),
00113 root_(new node())
00114 {}
00115
00116 ~octree() { delete root_;}
00117
00118 void insert(T const& data)
00119 {
00120 unsigned level = 0;
00121 node * cur_node = root_;
00122 while (true) {
00123
00124 if ( cur_node->count > 0 || level == leaf_level_)
00125 {
00126 cur_node->reds += data.r;
00127 cur_node->greens += data.g;
00128 cur_node->blues += data.b;
00129 cur_node->count += 1;
00130 if (cur_node->count == 1) ++colors_;
00131
00132
00133 break;
00134 }
00135
00136 unsigned idx = InsertPolicy::index_from_level(level,data);
00137 if (cur_node->children_[idx] == 0) {
00138 cur_node->children_[idx] = new node();
00139 if (level < leaf_level_-1)
00140 {
00141 reducible_[level+1].push_back(cur_node->children_[idx]);
00142 }
00143 }
00144 cur_node = cur_node->children_[idx];
00145 ++level;
00146 }
00147 }
00148
00149 int quantize(rgb const& c) const
00150 {
00151 unsigned level = 0;
00152 node * cur_node = root_;
00153 while (cur_node)
00154 {
00155 if (cur_node->count != 0) return cur_node->index;
00156 unsigned idx = InsertPolicy::index_from_level(level,c);
00157 cur_node = cur_node->children_[idx];
00158 ++level;
00159 }
00160 return -1;
00161 }
00162
00163 void create_palette(std::vector<rgb> & palette)
00164 {
00165 reduce();
00166 palette.reserve(colors_);
00167 create_palette(palette, root_);
00168 }
00169
00170 void reduce()
00171 {
00172
00173 for (unsigned i=0;i<InsertPolicy::MAX_LEVELS;++i)
00174 {
00175 std::sort(reducible_[i].begin(), reducible_[i].end(),node_cmp());
00176 }
00177
00178 while ( colors_ >= max_colors_ - 1)
00179 {
00180 while (leaf_level_ >0 && reducible_[leaf_level_-1].size() == 0)
00181 {
00182 --leaf_level_;
00183 }
00184
00185 if (leaf_level_ < 1) continue;
00186
00187 if ( reducible_[leaf_level_-1].size() == 0) return;
00188
00189 typename std::deque<node*>::iterator pos = reducible_[leaf_level_-1].begin();
00190 node * cur_node = *pos;
00191 unsigned num_children = 0;
00192 for (unsigned idx=0; idx < 8; ++idx)
00193 {
00194 if (cur_node->children_[idx] != 0)
00195 {
00196 ++num_children;
00197 cur_node->reds += cur_node->children_[idx]->reds;
00198 cur_node->greens += cur_node->children_[idx]->greens;
00199 cur_node->blues += cur_node->children_[idx]->blues;
00200 cur_node->count += cur_node->children_[idx]->count;
00201 delete cur_node->children_[idx], cur_node->children_[idx]=0;
00202 }
00203 }
00204
00205 reducible_[leaf_level_-1].erase(pos);
00206 if (num_children > 0 )
00207 {
00208 colors_ -= (num_children - 1);
00209 }
00210 }
00211 }
00212
00213 void create_palette(std::vector<rgb> & palette, node * itr) const
00214 {
00215 if (itr->count != 0)
00216 {
00217 unsigned count = itr->count;
00218 palette.push_back(rgb(uint8_t(itr->reds/float(count)),
00219 uint8_t(itr->greens/float(count)),
00220 uint8_t(itr->blues/float(count))));
00221 itr->index = palette.size() - 1;
00222 }
00223 for (unsigned i=0; i < 8 ;++i)
00224 {
00225 if (itr->children_[i] != 0)
00226 create_palette(palette, itr->children_[i]);
00227 }
00228 }
00229 private:
00230 node * root_;
00231 };
00232 }
00233
00234 #endif