src/meshTools/octree/octree.C

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 2011 OpenFOAM Foundation
   6      \\/     M anipulation  |
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of OpenFOAM.
  10
  11     OpenFOAM is free software: you can redistribute it and/or modify it
  12     under the terms of the GNU General Public License as published by
  13     the Free Software Foundation, either version 3 of the License, or
  14     (at your option) any later version.
  15
  16     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
  17     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19     for more details.
  20
  21     You should have received a copy of the GNU General Public License
  22     along with OpenFOAM.  If not, see <http://www.gnu.org/licenses/>.
  23
  24 \*---------------------------------------------------------------------------*/
  25
  26 #include "octree.H"
  27 #include "treeLeaf.H"
  28 #include "treeNode.H"
  29 #include "long.H"
  30 #include "cpuTime.H"
  31 #include "linePointRef.H"
  32 #include "pointIndexHit.H"
  33
  34 // * * * * * * * * * * * * * * Static Data Members * * * * * * * * * * * * * //
  35
  36 template <class Type>
  37 Foam::string Foam::octree<Type>::volType(const label type)
  38 {
  39     if (type == UNKNOWN)
  40     {
  41         return "unknown";
  42     }
  43     else if (type == MIXED)
  44     {
  45         return "mixed";
  46     }
  47     else if (type == INSIDE)
  48     {
  49         return "inside";
  50     }
  51     else if (type == OUTSIDE)
  52     {
  53         return "outside";
  54     }
  55     else
  56     {
  57         FatalErrorIn("volType(const label)") << "type:" << type
  58             << " unknown." << abort(FatalError);
  59
  60         return "dummy";
  61     }
  62 }
  63
  64
  65 // Determine inside/outside status of vector compared to geometry-based normal
  66 template <class Type>
  67 Foam::label Foam::octree<Type>::getVolType
  68 (
  69     const vector& geomNormal,
  70     const vector& vec
  71 )
  72 {
  73     scalar sign = geomNormal & vec;
  74
  75     if (sign >= 0)
  76     {
  77         return octree<Type>::OUTSIDE;
  78     }
  79     else
  80     {
  81         return octree<Type>::INSIDE;
  82     }
  83 }
  84
  85
  86 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
  87
  88 template <class Type>
  89 Foam::octree<Type>::octree
  90 (
  91     const treeBoundBox& octreeBb,
  92     const Type& shapes,
  93     const label minNLevels,
  94     const scalar maxLeafRatio,
  95     const scalar maxShapeRatio
  96 )
  97 :
  98     topNode_(new treeNode<Type>(octreeBb)),
  99     shapes_(shapes),
 100     octreeBb_(octreeBb),
 101     maxLeafRatio_(maxLeafRatio),
 102     maxShapeRatio_(maxShapeRatio),
 103     minNLevels_(minNLevels),
 104     deepestLevel_(0),
 105     nEntries_(0),
 106     nNodes_(0),
 107     nLeaves_(0),
 108     endIter_(*this, -1),
 109     endConstIter_(*this, -1)
 110 {
 111     cpuTime timer;
 112
 113     setNodes(nNodes() + 1);
 114
 115     const label nShapes = shapes_.size();
 116
 117     labelList indices(nShapes);
 118     for (label i = 0; i < nShapes; i++)
 119     {
 120         indices[i] = i;
 121     }
 122
 123     // Create initial level (0) of subLeaves
 124     if (debug & 1)
 125     {
 126         Pout<< "octree : --- Start of Level " << deepestLevel_
 127             << " ----" << endl;
 128     }
 129     topNode_->distribute(0, *this, shapes_, indices);
 130
 131     if (debug & 1)
 132     {
 133         printStats(Pout);
 134         Pout<< "octree : --- End of Level " << deepestLevel_
 135             << " ----" << endl;
 136     }
 137
 138     // Breadth first creation of tree
 139     // Stop if: - level above minlevel and
 140     //                - less than so many cells per endpoint
 141     //                  (so bottom level is fine enough)
 142     //                - every shape mentioned in only so many
 143     //                  leaves. (if shape bb quite big it will end up
 144     //                  in lots of leaves).
 145     //          - no change in number of leaves
 146     //            (happens if leafs fine enough)
 147     // This guarantees that tree
 148     //  - is fine enough (if minLevel > 0)
 149     //  - has some guaranteed maximum size (maxShapeRatio)
 150
 151     label oldNLeaves = -1;  // make test below pass first time.
 152     label oldNNodes  = -1;
 153     deepestLevel_ = 1;
 154     while
 155     (
 156         (deepestLevel_ <= minNLevels_)
 157      || (
 158             (nEntries() > maxLeafRatio * nLeaves())    // shapes per leaf
 159          && (nEntries() < maxShapeRatio * nShapes)     // entries per shape
 160         )
 161     )
 162     {
 163         if (deepestLevel_ >= maxNLevels)
 164         {
 165             if (debug & 1)
 166             {
 167                 Pout<< "octree : exiting since maxNLevels "
 168                     << maxNLevels << " reached" << endl;
 169             }
 170             break;
 171         }
 172
 173         if ((oldNLeaves == nLeaves()) && (oldNNodes == nNodes()))
 174         {
 175             if (debug & 1)
 176             {
 177                 Pout<< "octree : exiting since nLeaves and nNodes do not change"
 178                     << endl;
 179             }
 180             break;
 181         }
 182         if (debug & 1)
 183         {
 184             Pout<< "octree : --- Start of Level " << deepestLevel_
 185                 << " ----" << endl;
 186         }
 187
 188         oldNLeaves = nLeaves();
 189         oldNNodes  = nNodes();
 190
 191         topNode_->redistribute
 192         (
 193             1,
 194             *this,
 195             shapes_,
 196             deepestLevel_
 197         );
 198
 199         if (debug & 1)
 200         {
 201             printStats(Pout);
 202
 203             Pout<< "octree : --- End of Level " << deepestLevel_
 204                 << " ----" << endl;
 205         }
 206
 207         deepestLevel_++;
 208     }
 209
 210
 211     if (debug & 1)
 212     {
 213         Pout<< "octree : Constructed octree in = "
 214         << timer.cpuTimeIncrement()
 215         << " s\n" << endl << endl;
 216     }
 217
 218     // Set volume type of non-treeleaf nodes.
 219     topNode_->setSubNodeType(0, *this, shapes_);
 220
 221     if (debug & 1)
 222     {
 223         Pout<< "octree : Added node information to octree in  = "
 224         << timer.cpuTimeIncrement()
 225         << " s\n" << endl << endl;
 226     }
 227 }
 228
 229
 230 // * * * * * * * * * * * * * * * * Destructor  * * * * * * * * * * * * * * * //
 231
 232 template <class Type>
 233 Foam::octree<Type>::~octree()
 234 {
 235     delete topNode_;
 236 }
 237
 238
 239 // * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
 240
 241 template <class Type>
 242 Foam::label Foam::octree<Type>::getSampleType(const point& sample) const
 243 {
 244     return topNode_->getSampleType(0, *this, shapes_, sample);
 245 }
 246
 247
 248 template <class Type>
 249 Foam::label Foam::octree<Type>::find(const point& sample) const
 250 {
 251     return topNode_->find(shapes_, sample);
 252 }
 253
 254
 255 template <class Type>
 256 bool Foam::octree<Type>::findTightest
 257 (
 258     const point& sample,
 259     treeBoundBox& tightest
 260 ) const
 261 {
 262     return topNode_->findTightest
 263     (
 264         shapes_,
 265         sample,
 266         tightest
 267     );
 268 }
 269
 270
 271 template <class Type>
 272 Foam::label Foam::octree<Type>::findNearest
 273 (
 274     const point& sample,
 275     treeBoundBox& tightest,
 276     scalar& tightestDist
 277 ) const
 278 {
 279     label tightestI = -1;
 280
 281     if (debug & 4)
 282     {
 283         Pout<< "octree::findNearest : searching for nearest for "
 284             << "sample:" << sample
 285             << "  tightest:" << tightest << endl;
 286     }
 287
 288     topNode_->findNearest
 289     (
 290         shapes_,
 291         sample,
 292         tightest,
 293         tightestI,
 294         tightestDist
 295     );
 296
 297     if (debug & 4)
 298     {
 299         Pout<< "octree::findNearest : found nearest for "
 300             << "sample:" << sample << " with "
 301             << "  tightestI:" << tightestI
 302             << "  tightest:" << tightest
 303             << "  tightestDist:" << tightestDist
 304             << endl;
 305     }
 306
 307     return tightestI;
 308 }
 309
 310
 311 template <class Type>
 312 Foam::label Foam::octree<Type>::findNearest
 313 (
 314     const linePointRef& ln,
 315     treeBoundBox& tightest,
 316     point& linePoint,
 317     point& shapePoint
 318 ) const
 319 {
 320     // Start off from miss with points at large distance apart.
 321     label tightestI = -1;
 322     linePoint = point(-GREAT, -GREAT, -GREAT);
 323     shapePoint = point(GREAT, GREAT, GREAT);
 324
 325     topNode_->findNearest
 326     (
 327         shapes_,
 328         ln,
 329         tightest,
 330         tightestI,
 331         linePoint,
 332         shapePoint
 333     );
 334
 335     return tightestI;
 336 }
 337
 338
 339 template <class Type>
 340 Foam::labelList Foam::octree<Type>::findBox(const boundBox& bb) const
 341 {
 342     // Storage for labels of shapes inside bb. Size estimate.
 343     labelHashSet elements(100);
 344
 345     topNode_->findBox(shapes_, bb, elements);
 346
 347     return elements.toc();
 348 }
 349
 350
 351 template <class Type>
 352 Foam::pointIndexHit Foam::octree<Type>::findLine
 353 (
 354     const point& treeStart,
 355     const point& treeEnd
 356 ) const
 357 {
 358     // Initialize to a miss
 359     pointIndexHit hitInfo(false, treeStart, -1);
 360
 361     const vector dir(treeEnd - treeStart);
 362
 363     // Current line segment to search
 364     point start(treeStart);
 365     point end(treeEnd);
 366
 367     while (true)
 368     {
 369         // Find nearest treeLeaf intersected by line
 370         point leafIntPoint;
 371
 372         const treeLeaf<Type>* leafPtr = findLeafLine
 373         (
 374             start,
 375             end,
 376             leafIntPoint
 377         );
 378
 379         if (!leafPtr)
 380         {
 381             // Reached end of string of treeLeaves to be searched. Return
 382             // whatever we have found so far.
 383             break;
 384         }
 385
 386         // Inside treeLeaf find nearest intersection
 387         scalar minS = GREAT;
 388
 389         const labelList& indices = leafPtr->indices();
 390
 391         forAll(indices, elemI)
 392         {
 393             label index = indices[elemI];
 394
 395             point pt;
 396             bool hit = shapes().intersects(index, start, end, pt);
 397
 398             if (hit)
 399             {
 400                 // Check whether intersection nearer p
 401                 scalar s = (pt - treeStart) & dir;
 402
 403                 if (s < minS)
 404                 {
 405                     minS = s;
 406
 407                     // Update hit info
 408                     hitInfo.setHit();
 409                     hitInfo.setPoint(pt);
 410                     hitInfo.setIndex(index);
 411
 412                     // Update segment to search
 413                     end = pt;
 414                 }
 415             }
 416         }
 417
 418         if (hitInfo.hit())
 419         {
 420             // Found intersected shape.
 421             break;
 422         }
 423
 424         // Start from end of current leaf
 425         start = leafIntPoint;
 426     }
 427
 428     return hitInfo;
 429 }
 430
 431
 432 template <class Type>
 433 Foam::pointIndexHit Foam::octree<Type>::findLineAny
 434 (
 435     const point& start,
 436     const point& end
 437 ) const
 438 {
 439     // Initialize to a miss
 440     pointIndexHit hitInfo(false, start, -1);
 441
 442     // Start of segment in current treeNode.
 443     point p(start);
 444     while (true)
 445     {
 446         // Find treeLeaf intersected by line
 447         point leafIntPoint;
 448
 449         const treeLeaf<Type>* leafPtr = findLeafLine(p, end, leafIntPoint);
 450
 451         if (!leafPtr)
 452         {
 453             // Reached end of string of treeLeaves to be searched. Return
 454             // whatever we have found so far.
 455             break;
 456         }
 457
 458         // Inside treeLeaf find any intersection
 459
 460         // Vector from endPoint to entry point of leaf.
 461         const vector edgeVec(end - p);
 462
 463         const labelList& indices = leafPtr->indices();
 464
 465         forAll(indices, elemI)
 466         {
 467             label index = indices[elemI];
 468
 469             point pt;
 470             bool hit = shapes().intersects
 471             (
 472                 index,
 473                 p,
 474                 end,
 475                 pt
 476             );
 477
 478             if (hit)
 479             {
 480                 hitInfo.setHit();
 481                 hitInfo.setPoint(pt);
 482                 hitInfo.setIndex(index);
 483
 484                 break;
 485             }
 486         }
 487
 488         if (hitInfo.hit())
 489         {
 490             // Found intersected shape.
 491             break;
 492         }
 493
 494         // Start from end of current leaf
 495         p = leafIntPoint;
 496     }
 497
 498     return hitInfo;
 499 }
 500
 501
 502 template <class Type>
 503 const Foam::treeLeaf<Type>* Foam::octree<Type>::findLeafLine
 504 (
 505     const point& start,
 506     const point& end,
 507     point& leafIntPoint
 508 ) const
 509 {
 510     // returns first found cube along line
 511
 512     if (debug & 2)
 513     {
 514         Pout<< "octree::findLeafLine : searching for shapes on line "
 515             << "start:" << start
 516             << "  end:" << end << endl;
 517     }
 518
 519     // If start is outside project onto top cube
 520     if (octreeBb_.contains(start))
 521     {
 522         leafIntPoint = start;
 523     }
 524     else
 525     {
 526         if (!octreeBb_.intersects(start, end, leafIntPoint))
 527         {
 528             if (debug & 2)
 529             {
 530                 Pout<< "octree::findLeafLine : start outside domain but does"
 531                     << " not intersect : start:"
 532                     << start << endl;
 533             }
 534             return NULL;
 535         }
 536
 537         if (debug & 2)
 538         {
 539             Pout<< "octree::findLeafLine : start propagated to inside"
 540                    " domain : "
 541                 << leafIntPoint << endl;
 542         }
 543     }
 544
 545     // Normal action: find next intersection along line
 546     const treeLeaf<Type>* leafPtr = topNode_->findLeafLine
 547     (
 548         0,
 549         shapes_,
 550         leafIntPoint,
 551         end
 552     );
 553
 554     if (debug & 2)
 555     {
 556         Pout<< "returning from octree::findLeafLine with "
 557             << "leafIntersection:" << leafIntPoint
 558             << "  leafPtr:" << long(leafPtr) << endl;
 559     }
 560
 561     return leafPtr;
 562 }
 563
 564
 565 template <class Type>
 566 void Foam::octree<Type>::writeOBJ
 567 (
 568     Ostream& os,
 569     label& vertNo
 570 ) const
 571 {
 572     scalar minx = octreeBb_.min().x();
 573     scalar miny = octreeBb_.min().y();
 574     scalar minz = octreeBb_.min().z();
 575
 576     scalar maxx = octreeBb_.max().x();
 577     scalar maxy = octreeBb_.max().y();
 578     scalar maxz = octreeBb_.max().z();
 579
 580     os << "v " << minx << " " << miny << " " << minz << endl;
 581     os << "v " << maxx << " " << miny << " " << minz << endl;
 582     os << "v " << maxx << " " << maxy << " " << minz << endl;
 583     os << "v " << minx << " " << maxy << " " << minz << endl;
 584
 585     os << "v " << minx << " " << miny << " " << maxz << endl;
 586     os << "v " << maxx << " " << miny << " " << maxz << endl;
 587     os << "v " << maxx << " " << maxy << " " << maxz << endl;
 588     os << "v " << minx << " " << maxy << " " << maxz << endl;
 589
 590     // Bottom face
 591     os << "l " << vertNo + 1 << " " << vertNo + 2 << endl;
 592     os << "l " << vertNo + 2 << " " << vertNo + 3 << endl;
 593     os << "l " << vertNo + 3 << " " << vertNo + 4 << endl;
 594     os << "l " << vertNo + 4 << " " << vertNo + 1 << endl;
 595
 596     // Top face
 597     os << "l " << vertNo + 5 << " " << vertNo + 6 << endl;
 598     os << "l " << vertNo + 6 << " " << vertNo + 7 << endl;
 599     os << "l " << vertNo + 7 << " " << vertNo + 8 << endl;
 600     os << "l " << vertNo + 8 << " " << vertNo + 5 << endl;
 601
 602     // Edges from bottom to top face
 603     os << "l " << vertNo + 1 << " " << vertNo + 5 << endl;
 604     os << "l " << vertNo + 2 << " " << vertNo + 6 << endl;
 605     os << "l " << vertNo + 3 << " " << vertNo + 7 << endl;
 606     os << "l " << vertNo + 4 << " " << vertNo + 8 << endl;
 607
 608     vertNo += 8;
 609
 610     topNode_->writeOBJ(os, 1, vertNo);
 611 }
 612
 613
 614 template <class Type>
 615 void Foam::octree<Type>::printStats(Ostream& os) const
 616 {
 617     os  << "Statistics after iteration " << deepestLevel() << ':' << endl
 618         << "  nShapes  :" << shapes().size() << endl
 619         << "  nNodes   :" << nNodes() << endl
 620         << "  nLeaves  :" << nLeaves() << endl
 621         << "  nEntries :" << nEntries() << endl;
 622
 623     if (nLeaves() && shapes().size())
 624     {
 625         os
 626             << "  Cells per leaf :"
 627             << scalar(nEntries())/nLeaves()
 628             << nl
 629             << "  Every cell in  :"
 630             << scalar(nEntries())/shapes().size() << " cubes"
 631             << endl;
 632     }
 633 }
 634
 635
 636 // * * * * * * * * * * * * * * * STL iterator  * * * * * * * * * * * * * * * //
 637
 638 // Construct from a octree. Set index at end.
 639 template <class Type>
 640 Foam::octree<Type>::iterator::iterator(octree<Type>& oc)
 641 :
 642     octree_(oc),
 643     curLeaf_(oc.nLeaves())
 644 {
 645     leaves_.setSize(0);
 646 }
 647
 648
 649 // Construct from octree. Set index.
 650 template <class Type>
 651 Foam::octree<Type>::iterator::iterator(octree<Type>& oc, label index)
 652 :
 653     octree_(oc),
 654     curLeaf_(index)
 655 {
 656     if (index >= 0)
 657     {
 658         leaves_.setSize(oc.nLeaves());
 659
 660         label leafIndex = 0;
 661         octree_.topNode()->findLeaves(leaves_, leafIndex);
 662
 663         if (leafIndex != oc.nLeaves())
 664         {
 665             FatalErrorIn
 666             (
 667                 "octree::iterator::iterator"
 668                 "(octree&, label)"
 669             )
 670             << "Traversal of tree returns : " << leafIndex << endl
 671             << "Statistics of octree say  : " << oc.nLeaves() << endl
 672             << abort(FatalError);
 673         }
 674     }
 675 }
 676
 677
 678 template <class Type>
 679 void Foam::octree<Type>::iterator::operator=(const iterator& iter)
 680 {
 681     if ((curLeaf_ < 0) && (iter.curLeaf_ >= 0))
 682     {
 683         FatalErrorIn
 684         (
 685             "octree::iterator::operator="
 686             "(const iterator&)"
 687         )
 688         << "lhs : " << curLeaf_ << endl
 689         << "rhs : " << iter.curLeaf_ << endl
 690         << abort(FatalError);
 691     }
 692     curLeaf_ = iter.curLeaf_;
 693 }
 694
 695
 696 template <class Type>
 697 bool Foam::octree<Type>::iterator::operator==(const iterator& iter) const
 698 {
 699     label index1 =
 700         (curLeaf_ >= 0 ? curLeaf_ : octree_.nLeaves());
 701     label index2 =
 702         (iter.curLeaf_ >= 0 ? iter.curLeaf_ : iter.octree_.nLeaves());
 703
 704     return index1 == index2;
 705 }
 706
 707
 708 template <class Type>
 709 bool Foam::octree<Type>::iterator::operator!=(const iterator& iter) const
 710 {
 711     return !(iterator::operator==(iter));
 712 }
 713
 714
 715 template <class Type>
 716 Foam::treeLeaf<Type>& Foam::octree<Type>::iterator::operator*()
 717 {
 718     return *leaves_[curLeaf_];
 719 }
 720
 721
 722 template <class Type>
 723 typename Foam::octree<Type>::iterator&
 724 Foam::octree<Type>::iterator::operator++()
 725 {
 726     curLeaf_++;
 727     return *this;
 728 }
 729
 730
 731 template <class Type>
 732 typename Foam::octree<Type>::iterator
 733 Foam::octree<Type>::iterator::operator++(int)
 734 {
 735     iterator tmp = *this;
 736     ++*this;
 737     return tmp;
 738 }
 739
 740
 741 template <class Type>
 742 typename Foam::octree<Type>::iterator
 743 Foam::octree<Type>::begin()
 744 {
 745     return iterator(*this, 0);
 746 }
 747
 748
 749 template <class Type>
 750 const typename Foam::octree<Type>::iterator&
 751 Foam::octree<Type>::end()
 752 {
 753     return octree<Type>::endIter_;
 754 }
 755
 756
 757 // * * * * * * * * * * * * * * STL const_iterator  * * * * * * * * * * * * * //
 758
 759 // Construct for a given octree
 760 template <class Type>
 761 Foam::octree<Type>::const_iterator::const_iterator(const octree<Type>& oc)
 762 :
 763     octree_(oc),
 764     curLeaf_(oc.nLeaves())
 765 {
 766     leaves_.setSize(oc.nLeaves());
 767 }
 768
 769
 770 // Construct for a given octree
 771 template <class Type>
 772 Foam::octree<Type>::const_iterator::const_iterator
 773 (
 774     const octree<Type>& oc,
 775     label index
 776 )
 777 :
 778     octree_(oc),
 779     curLeaf_(index)
 780 {
 781     if (index >= 0)
 782     {
 783         leaves_.setSize(oc.nLeaves());
 784
 785         label leafIndex = 0;
 786         octree_.topNode()->findLeaves(leaves_, leafIndex);
 787
 788         if (leafIndex != oc.nLeaves())
 789         {
 790             FatalErrorIn
 791             (
 792                 "octree::const_iterator::const_iterator"
 793                 "(octree&, label)"
 794             )
 795             << "Traversal of tree returns : " << leafIndex << endl
 796             << "Statistics of octree say  : " << oc.nLeaves() << endl
 797             << abort(FatalError);
 798         }
 799     }
 800 }
 801
 802
 803 template <class Type>
 804 void Foam::octree<Type>::const_iterator::operator=(const const_iterator& iter)
 805 {
 806     if ((curLeaf_ < 0) && (iter.curLeaf_ >= 0))
 807     {
 808         FatalErrorIn
 809         (
 810             "octree::const_iterator::operator="
 811             "(const const_iterator&)"
 812         )
 813         << "lhs : " << curLeaf_ << endl
 814         << "rhs : " << iter.curLeaf_ << endl
 815         << abort(FatalError);
 816     }
 817     curLeaf_ = iter.curLeaf_;
 818     curLeaf_ = iter.curLeaf_;
 819 }
 820
 821
 822 template <class Type>
 823 bool Foam::octree<Type>::const_iterator::operator==
 824 (
 825     const const_iterator& iter
 826 ) const
 827 {
 828     label index1 =
 829         (curLeaf_ >= 0 ? curLeaf_ : octree_.nLeaves());
 830     label index2 =
 831         (iter.curLeaf_ >= 0 ? iter.curLeaf_ : iter.octree_.nLeaves());
 832
 833     return index1 == index2;
 834 }
 835
 836
 837 template <class Type>
 838 bool Foam::octree<Type>::const_iterator::operator!=
 839 (
 840     const const_iterator& iter
 841 ) const
 842 {
 843     return !(const_iterator::operator==(iter));
 844 }
 845
 846
 847 template <class Type>
 848 const Foam::treeLeaf<Type>& Foam::octree<Type>::const_iterator::operator*()
 849 {
 850     return *leaves_[curLeaf_];
 851 }
 852
 853
 854 template <class Type>
 855 typename Foam::octree<Type>::const_iterator&
 856 Foam::octree<Type>::const_iterator::operator++()
 857 {
 858     curLeaf_++;
 859     return *this;
 860 }
 861
 862
 863 template <class Type>
 864 typename Foam::octree<Type>::const_iterator
 865 Foam::octree<Type>::const_iterator::operator++(int)
 866 {
 867     const_iterator tmp = *this;
 868     ++*this;
 869     return tmp;
 870 }
 871
 872
 873 template <class Type>
 874 typename Foam::octree<Type>::const_iterator
 875 Foam::octree<Type>::begin() const
 876 {
 877     return const_iterator(*this, 0);
 878 }
 879
 880
 881 template <class Type>
 882 typename Foam::octree<Type>::const_iterator
 883 Foam::octree<Type>::cbegin() const
 884 {
 885     return const_iterator(*this, 0);
 886 }
 887
 888
 889 template <class Type>
 890 const typename Foam::octree<Type>::const_iterator&
 891 Foam::octree<Type>::end() const
 892 {
 893     return octree<Type>::endConstIter_;
 894 }
 895
 896
 897 template <class Type>
 898 const typename Foam::octree<Type>::const_iterator&
 899 Foam::octree<Type>::cend() const
 900 {
 901     return octree<Type>::endConstIter_;
 902 }
 903
 904
 905 // * * * * * * * * * * * * * * * Friend Operators  * * * * * * * * * * * * * //
 906
 907 template <class Type>
 908 Foam::Ostream& Foam::operator<<(Ostream& os, const octree<Type>& oc)
 909 {
 910     return os << token::BEGIN_LIST
 911         //<< token::SPACE << oc.shapes_
 912         << token::SPACE << oc.octreeBb_
 913         << token::SPACE << oc.maxLeafRatio_
 914         << token::SPACE << oc.maxShapeRatio_
 915         << token::SPACE << oc.minNLevels_
 916         << token::SPACE << oc.deepestLevel_
 917         << token::SPACE << oc.nEntries_
 918         << token::SPACE << oc.nNodes_
 919         << token::SPACE << oc.nLeaves_
 920         << token::SPACE << *oc.topNode_
 921         << token::SPACE << token::END_LIST;
 922 }
 923
 924
 925 // ************************************************************************* //