src/meshTools/octree/octree.C

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