src/meshTools/octree/treeNode.H

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 2004-2010 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
  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 Class
  25     Foam::treeNode
  26
  27 Description
  28     Class to implement octree.
  29
  30     Holds the pointers to sub-octants. These are either other treeNodes or
  31     treeLeafs. The treeLeafs hold the actual data as a list of indices into
  32     octreeData.
  33
  34 Note
  35     To prevent calculation errors all bounding boxes used in octrees are
  36     calculated only once.
  37
  38     The pointers to either treeNode/treeLeaf are implemented 'by hand'
  39     (explicitly marking type) instead of using a proper virtual mechanism
  40     to save some space in the treeLeaves.
  41
  42 SourceFiles
  43     treeNode.C
  44
  45 \*---------------------------------------------------------------------------*/
  46
  47 #ifndef treeNode_H
  48 #define treeNode_H
  49
  50 #include "treeBoundBoxList.H"
  51 #include "treeElem.H"
  52 #include "linePointRef.H"
  53 #include "HashSet.H"
  54
  55 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
  56
  57 namespace Foam
  58 {
  59
  60 // class intersection;
  61
  62 template<class Type> class octree;
  63 template<class Type> class treeLeaf;
  64 template<class Type> class treeNode;
  65
  66 // Forward declaration of friend functions and operators
  67
  68 template<class Type> Istream& operator>>(Istream&, treeNode<Type>&);
  69 template<class Type> Ostream& operator<<(Ostream&, const treeNode<Type>&);
  70
  71
  72 /*---------------------------------------------------------------------------*\
  73                         Class treeNodeName Declaration
  74 \*---------------------------------------------------------------------------*/
  75
  76 TemplateName(treeNode);
  77
  78
  79 /*---------------------------------------------------------------------------*\
  80                           Class treeNode Declaration
  81 \*---------------------------------------------------------------------------*/
  82
  83 template <class Type>
  84 class treeNode
  85 :
  86     public treeElem<Type>,
  87     public treeNodeName
  88 {
  89     // Private data
  90
  91         //- Position of the midpoint
  92         const point mid_;
  93
  94         //- Type stored in subNodes_
  95         unsigned char subNodeTypes_;
  96
  97         //- Pointers to sub treeNode or treeLeaf
  98         treeElem<Type>* subNodes_[8];
  99
 100         //- Constant valid for whole subNode/leaf
 101         label volType_;
 102
 103     // Static data members
 104
 105         //- leaf offset for octant index
 106         static const label leafOffset;
 107
 108
 109     // Private Member Functions
 110
 111         //- mark pointer to subnode as being a treeNode*
 112         void setAsNode(const label octant);
 113
 114         //- mark pointer to subnode as being a treeLeaf*
 115         void setAsLeaf(const label octant);
 116
 117         //- Set pointer to sub node
 118         void setNodePtr(const label octant, treeElem<Type>* treeNodePtr);
 119
 120         //- Set pointer to sub leaf
 121         void setLeafPtr(const label octant, treeElem<Type>* treeLeafPtr);
 122
 123         //- Set type of octant
 124         void setVolType(const label octant, const label type);
 125
 126         //- Get type of octant
 127         inline label getVolType(const label octant) const;
 128
 129         //- Find first leaf on line start-end. Updates start.
 130         const treeLeaf<Type>* findLeafLineOctant
 131         (
 132             const int level,
 133             const Type& shapes,
 134             const label octant,
 135             const vector& direction,
 136             point& start,
 137             const point& end
 138         ) const;
 139
 140
 141         //- Print spaces
 142         static void space(Ostream&, const label);
 143
 144         //- Disallow default bitwise copy construct
 145         treeNode(const treeNode&);
 146
 147         //- Disallow default bitwise assignment
 148         void operator=(const treeNode&);
 149
 150
 151 public:
 152
 153     // Constructors
 154
 155         //- Construct from components
 156         treeNode(const treeBoundBox&);
 157
 158         //- Construct from Istream
 159         treeNode(Istream&);
 160
 161
 162     //- Destructor
 163     ~treeNode();
 164
 165
 166     // Member Functions
 167
 168         // Access
 169
 170             //- The midpoint position
 171             inline const point& midpoint() const;
 172
 173             //- array of 8 subNodes/leaves
 174             inline treeElem<Type>* const* subNodes() const;
 175
 176             //- octant contains pointer to treeNode(1) or treeLeaf(0)
 177             inline label isNode(const label octant) const;
 178
 179             //- Get pointer to sub node
 180             inline treeNode<Type>* getNodePtr(const label octant) const;
 181
 182             //- Get pointer to sub leaf
 183             inline treeLeaf<Type>* getLeafPtr(const label octant) const;
 184
 185         // Edit
 186
 187             //- Take list of shapes and distribute over the 8 octants
 188             void distribute
 189             (
 190                 const label,
 191                 octree<Type>&,
 192                 const Type& shapes,
 193                 const labelList&
 194             );
 195
 196             //- Distribute at certain level only
 197             void redistribute
 198             (
 199                 const label,
 200                 octree<Type>&,
 201                 const Type& shapes,
 202                 const label
 203             );
 204
 205             //- Set type of subnodes
 206             label setSubNodeType
 207             (
 208                 const label level,
 209                 octree<Type>& top,
 210                 const Type& shapes
 211             );
 212
 213         // Search
 214
 215             //- Find type of node sample is in. Used for inside/outside
 216             //  determination
 217             label getSampleType
 218             (
 219                 const label level,
 220                 const octree<Type>& top,
 221                 const Type& shapes,
 222                 const point& sample
 223             ) const;
 224
 225             //- Find index of shape containing sample.
 226             label find
 227             (
 228                 const Type& shapes,
 229                 const point& sample
 230             ) const;
 231
 232             //- Find tightest bounding box around sample which is guaranteed
 233             //  to hold at least one cell.
 234             //  Current best bb in tightest,
 235             //  returns true if newTightest has changed, 0 otherwise.
 236             bool findTightest
 237             (
 238                 const Type& shapes,
 239                 const point& sample,
 240                 treeBoundBox& tightest
 241             ) const;
 242
 243             //- Find nearest shape to sample
 244             //  Returns true if found nearer shape and updates
 245             //  tightest, tightestI, tightestDist
 246             bool findNearest
 247             (
 248                 const Type& shapes,
 249                 const point& sample,
 250                 treeBoundBox& tightest,
 251                 label& tightestI,
 252                 scalar& tightestDist
 253             ) const;
 254
 255             //- Find nearest shape to line
 256             //  Returns true if found nearer shape and updates nearest and
 257             //  tightest
 258             bool findNearest
 259             (
 260                 const Type& shapes,
 261                 const linePointRef& ln,
 262                 treeBoundBox& tightest,
 263                 label& tightestI,   // index of nearest shape
 264                 point& linePoint,   // nearest point on line
 265                 point& shapePoint   // nearest point on shape
 266             ) const;
 267
 268             //- Find shapes not outside box. Return true if anything found.
 269             bool findBox
 270             (
 271                 const Type& shapes,
 272                 const boundBox& bb,
 273                 labelHashSet& elements
 274             ) const;
 275
 276             //- Find treeLeaves intersecting line segment [start..end]
 277             //  Updates: start
 278             const treeLeaf<Type>* findLeafLine
 279             (
 280                 const label level,
 281                 const Type& shapes,
 282                 point& start,
 283                 const point& end
 284             ) const;
 285
 286
 287             //- Collect all treeLeafs in leafArray. leafIndex points to first
 288             //  empty slot in leafArray and gets updated.
 289             void findLeaves
 290             (
 291                 List<treeLeaf<Type>*>& leafArray,
 292                 label& leafIndex
 293             ) const;
 294
 295             //- Same but for const.
 296             void findLeaves
 297             (
 298                 List<const treeLeaf<Type>*>& leafArray,
 299                 label& leafIndex
 300             ) const;
 301
 302
 303         // Write
 304
 305             //- Print contents of node.
 306             void printNode
 307             (
 308                 Ostream& os,
 309                 const label level
 310             ) const;
 311
 312             //- Write subleafs in OBJ format.
 313             void writeOBJ
 314             (
 315                 Ostream& os,
 316                 const label level,
 317                 label& vertNo
 318             ) const;
 319
 320
 321     // IOstream Operators
 322
 323         friend Istream& operator>> <Type> (Istream&, treeNode<Type>&);
 324         friend Ostream& operator<< <Type> (Ostream&, const treeNode<Type>&);
 325 };
 326
 327
 328 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 329
 330 } // End namespace Foam
 331
 332
 333 #include "treeNodeI.H"
 334
 335 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 336
 337 #ifdef NoRepository
 338 #   include "treeNode.C"
 339 #endif
 340
 341 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 342
 343 #endif
 344
 345 // ************************************************************************* //