src/meshTools/octree/treeNode.H

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