modules/quadTree.cpp

   1 #include "quadTree.h"
   2 #include "../fileUtil.h"
   3
   4 using namespace std;
   5
   6 /** Struct for computing (acts as a functor) and storing max.\ and min.\
   7  *      levels of leaf range blocks */
   8 struct MQuadTree::NodeExtremes {
   9         int min, max;
  10
  11         NodeExtremes()
  12         : min( numeric_limits<int>::max() ), max( numeric_limits<int>::min() ) {}
  13         void operator()(const MQuadTree::RangeNode *node) {
  14                 int now= node->level;
  15                 if (now<min)
  16                         min= now;
  17                 if (now>max)
  18                         max= now;
  19         }
  20 };
  21
  22
  23 void MQuadTree::encode(const PlaneBlock &toEncode) {
  24         ASSERT( !root && fringe.empty() && toEncode.ranges==this && toEncode.isReady() );
  25         DEBUG_ONLY( planeBlock= &toEncode; )
  26         zoom= 0;
  27 //      if allowed, prepare accelerators for heuristic dividing
  28         if ( heuristicAllowed() )
  29                 toEncode.summers_makeValid();
  30 //      create a new root, encode it via a recursive routine
  31         root= new Node( Block(0,0,toEncode.width,toEncode.height) );
  32         root->encode(toEncode);
  33 //      generate the fringe, let the encoder process it
  34         root->getHilbertList(fringe);
  35         toEncode.encoder->finishEncoding();
  36 }
  37
  38 void MQuadTree::writeData(ostream &file) {
  39         ASSERT( !fringe.empty() && root );
  40 //      put in the stream the minimal and the maximal used level
  41         NodeExtremes extremes= for_each( fringe, NodeExtremes() );
  42         put<Uchar>(file,extremes.min-zoom);
  43         put<Uchar>(file,extremes.max-zoom);
  44 //      put the tree structure in the stream
  45         BitWriter bitWriter(file);
  46         root->toFile(bitWriter,extremes);
  47 }
  48
  49 void MQuadTree::readData_buildRanges(istream &file,const PlaneBlock &block) {
  50         ASSERT( fringe.empty() && !root );
  51         DEBUG_ONLY( planeBlock= &block; )
  52         zoom= block.settings->zoom;
  53 //      get from the stream the minimal and the maximal used level
  54         NodeExtremes extremes;
  55         extremes.min= get<Uchar>(file)+zoom;
  56         extremes.max= get<Uchar>(file)+zoom;
  57 //      build the range tree
  58         BitReader bitReader(file);
  59         root= new Node( Block(0,0,block.width,block.height) );
  60         root->fromFile(bitReader,extremes);
  61 //      generate the fringe of the range tree
  62         root->getHilbertList(fringe);
  63 }
  64
  65
  66 ////    MQuadTree::Node class
  67
  68 void MQuadTree::Node::disconnect() {
  69 //      disconnects itself from its brothers in the circle
  70         if ( father->son == this )
  71                 father->son= ( brother==this ? 0 : brother );
  72         Node *prev= this;
  73         while (prev->brother != this)
  74                 prev= prev->brother;
  75         prev->brother= this->brother;
  76 }
  77
  78 void MQuadTree::Node::deleteSons() {
  79 //      delete all sons
  80         if (!son)
  81         return;
  82     Node *now= son;
  83     do {
  84         Node *next= now->brother;
  85         delete now;
  86         now= next;
  87     } while (now!=son);
  88     son= 0;
  89 }
  90
  91 void MQuadTree::Node::divide() {
  92 //      check against dividing already divided self
  93         ASSERT(!son);
  94         short size= powers[level-1];
  95         short xmid= min<short>( x0+size, xend );
  96         short ymid= min<short>( y0+size, yend );
  97 //  top-left (don't know the brother yet, using 0)
  98     son= new Node( Block(x0,y0,xmid,ymid), this, 0 );
  99     Node *last= son;
 100 //  top-right
 101     if (xmid < xend) {
 102         last= new Node( Block(xmid,y0,xend,ymid), this, last );
 103 //  bottom-right
 104         if (ymid < yend)
 105             last= new Node( Block(xmid,ymid,xend,yend), this, last );
 106     }
 107 //  bottom-left
 108     if (ymid < yend)
 109         last= new Node( Block(x0,ymid,xmid,yend), this, last );
 110 //  son finish
 111         son->brother= last;
 112 }
 113
 114 void MQuadTree::Node::getHilbertList(RangeList &list,char start,char cw) {
 115         if (!son) {
 116                 list.push_back(this);
 117                 return;
 118         }
 119         Node *now= son
 120         , *sons[4]= {0,0,0,0};
 121 //      categorize sons by their position into sons[0-3] - clockwise from top-left
 122         do {
 123                 int pos= 0;
 124                 if ( now->x0 > x0 )
 125                         ++pos;
 126                 if ( now->y0 > y0 )
 127                         pos= 3-pos;
 128                 sons[pos]= now;
 129         } while ( (now=now->brother) != son );
 130 //      recurse on the son that is the first on the Hilbert curve (if it's present)
 131         int pos= (start%= 4);
 132         if (sons[pos])
 133                 sons[pos]->getHilbertList(list,start,-cw);
 134 //      recurse on the second and the third son
 135         for (int i=0; i<2; ++i) {
 136                 pos= (pos+4+cw)%4;
 137                 if (sons[pos])
 138                         sons[pos]->getHilbertList(list,start,cw);
 139         }
 140 //      recurse on the last son
 141         pos= (pos+4+cw)%4;
 142         if (sons[pos])
 143                 sons[pos]->getHilbertList(list,start+2,-cw);
 144 }
 145
 146 int MQuadTree::Node::getSonCount() const {
 147         if (!son)
 148                 return 0;
 149         Node *now= son->brother;
 150         int count= 1;
 151         while (now!=son) {
 152                 now= now->brother;
 153                 ++count;
 154         }
 155         return count;
 156 }
 157
 158 bool MQuadTree::Node::encode(const PlaneBlock &toEncode) {
 159         if (*toEncode.settings->updateInfo.terminate)
 160                 throw exception();
 161
 162         MQuadTree *mod= debugCast<MQuadTree*>(toEncode.ranges);
 163         ASSERT( mod && level>=mod->minLevel() );
 164         const IColorTransformer::PlaneSettings &plSet= *toEncode.settings;
 165         int pixCount= size();
 166 //      check for minimal level -> cannot be divided, find the best domain
 167         if ( level == mod->minLevel() ) {
 168         //      try to find the best mapping, not restricting the max.\ SE and exit
 169                 toEncode.encoder->findBestSE(*this,true);
 170                 plSet.updateInfo.incProgress(pixCount);
 171                 return false;
 172         }
 173
 174 ///     \todo regular ranges optimization
 175         float maxSE= plSet.moduleQ2SE->rangeSE( plSet.quality, pixCount );
 176         bool tryEncode= true;
 177
 178         if ( level > mod->maxLevel() )
 179                 tryEncode= false;
 180         else {
 181         //      if heuirstic dividing is allowed and signals dividing, don't try to encode
 182                 if ( mod->heuristicAllowed() ) {
 183                         Real rSum, r2Sum;
 184                         toEncode.getSums(*this).unpack(rSum,r2Sum);
 185                         if ( estimateSE(rSum,r2Sum,pixCount,level) > maxSE )
 186                                 tryEncode= false;
 187                 }
 188         //      if we decided to try to encode, do it and return if the quality is sufficient
 189                 if ( tryEncode && toEncode.encoder->findBestSE(*this) <= maxSE ) {
 190                         plSet.updateInfo.incProgress(pixCount);
 191                         return false;
 192                 }
 193                 #ifndef NDEBUG
 194                 else // tried to encode, but unsuccessfully and forced to be divided
 195                         ++debugCast<MQuadTree*>(toEncode.ranges)->badTries;
 196                 #endif
 197         }
 198 //      the range needs to be divided, try to encode the sons
 199         divide();
 200         bool aSonDivided= false;
 201         Node *now= son;
 202         do {// if any of the sons is divided, set tryEncode to true
 203                 bool divided= now->encode(toEncode);
 204                 aSonDivided= aSonDivided || divided;
 205         } while ( (now=now->brother) != son );
 206 //      if (I unsuccessfully tried to encode or a son was divided) or (I have too big level), return
 207         if ( aSonDivided || tryEncode || level > mod->maxLevel() )
 208                 return true;
 209 //      this range still has a chance, try to encode it
 210         if ( toEncode.encoder->findBestSE(*this) <= maxSE ) {
 211                 #ifndef NDEBUG
 212                         ++debugCast<MQuadTree*>(toEncode.ranges)->badDivides;
 213                 #endif
 214                 deleteSons();
 215                 return false;
 216         } else {
 217                 #ifndef NDEBUG
 218                         ++debugCast<MQuadTree*>(toEncode.ranges)->triedMerges;
 219                 #endif
 220                 return true;
 221         }
 222 }
 223
 224 void MQuadTree::Node::toFile(BitWriter &file,NodeExtremes extremes) {
 225         if (son) {
 226         //  Node is divided
 227                 if (level<=extremes.max)
 228                         file.putBits(1,1);
 229         //      recurse
 230                 Node *now= son;
 231                 do
 232                         now->toFile(file,extremes);
 233                 while ( (now= now->brother) != son );
 234         } else
 235         //  Node isn't divided
 236                 if (level>extremes.min)
 237                         file.putBits(0,1);
 238 }
 239
 240 void MQuadTree::Node::fromFile(BitReader &file,NodeExtremes extremes) {
 241 //      should I be divided ?
 242         bool div= level>extremes.max || ( level>extremes.min && file.getBits(1) ) ;
 243         if (div) {
 244                 divide();
 245                 Node *now= son;
 246                 do
 247                         now->fromFile(file,extremes);
 248                 while ( (now=now->brother) != son );
 249         }
 250 }