FSubOctree.hpp 25.2 KB
Newer Older
1
// ===================================================================================
2
// Copyright ScalFmm 2011 INRIA, Olivier Coulaud, Berenger Bramas, Matthias Messner
3
4
5
6
// olivier.coulaud@inria.fr, berenger.bramas@inria.fr
// This software is a computer program whose purpose is to compute the FMM.
//
// This software is governed by the CeCILL-C and LGPL licenses and
7
8
// abiding by the rules of distribution of free software.
//
9
10
11
12
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public and CeCILL-C Licenses for more details.
13
// "http://www.cecill.info".
14
// "http://www.gnu.org/licenses".
15
// ===================================================================================
16
17
#ifndef FSUBOCTREE_HPP
#define FSUBOCTREE_HPP
18

19
20

#include "../Utils/FGlobal.hpp"
BRAMAS Berenger's avatar
BRAMAS Berenger committed
21
#include "../Utils/FPoint.hpp"
BRAMAS Berenger's avatar
BRAMAS Berenger committed
22
#include "../Utils/FAssert.hpp"
23
24
25
26
27
28
29
30
31
32
33
34
#include "../Utils/FMath.hpp"

#include "FTreeCoordinate.hpp"


/**
 * @author Berenger Bramas (berenger.bramas@inria.fr)
 * @class FAbstractSubOctree
 * Please read the license
 *
 * This class is a sub-octree container.
 * This class is the main component of the octree.
35
 *
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 * This class does not have a main root. In fact, the root
 * is contained in the parent sub-octree.
 *
 * If the sub-octree is a middle suboctree, the leaf level is pointers
 * on other suboctrees.
 *
 * If the sub-octree is a bottom subtree then the leaf level is pointers on
 * lists<particle>
 *
 * This two situations are implemented in two different classes that inherite of FAbstractSubOctree.
 *
 * Please refere to testOctree.cpp to see an example
 * @warning Give the particleClass & cellClass
 */
BRAMAS Berenger's avatar
BRAMAS Berenger committed
50
template< class CellClass , class ContainerClass, class LeafClass, class CellAllocatorClass>
BRAMAS Berenger's avatar
BRAMAS Berenger committed
51
class FAbstractSubOctree {
52
53
54
55
56
protected:

    CellClass*** cells;		            //< Potential cells, cells are allocated only if needed
    FAbstractSubOctree* const parent;       //< Parent suboctree (null for root)

57
    const int indexInParent;                //< This is the index of the current octree in the parent's array
58

59
60
    int leftLeafIndex;                      //< The leaf at the left position (this is the array index to start when iterate)
    int rightLeafIndex;                     //< The leaf at the right position (this is the last array index when iterate)
61
62
63
64

    const int subOctreeHeight;              //< Height of this suboctree
    const int subOctreePosition;	    //< Level of the current suboctree in the global tree (0 if node)

65
66
    const bool isLeafSubtree;               //< To know if a subtree is leaf or not (we prefere that to a virtual method)

BRAMAS Berenger's avatar
BRAMAS Berenger committed
67
    CellAllocatorClass cellAllocator;
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

    /**
     * This function compute the morton index for the last level of this suboctree.
     * suppose we have an index like : 000.010.111.001.101.110
     * and now considere that suboctree's height is 2, the morton index have to be cut as :
     * [000.010].[111.001].[101.110] each part correspond to a morton index a leaf level for the
     * different suboctrees.
     * This is why depending on the level of the octree we need to remove extra part on the left and
     * on the right.
     */
    MortonIndex getLeafIndex(const MortonIndex index, const int inTreeHeight) const {
        // Remove right useless part - used by child
        const MortonIndex fullIndex = index >> (3 * (inTreeHeight - (this->subOctreeHeight + this->subOctreePosition) ) );
        // Remove left extra data part - used by parent
        const MortonIndex treeLeafMask = ~(~0x00LL << (3 *  this->subOctreeHeight ));
        return treeLeafMask & fullIndex;
    }

    /**
87
     * This function creates all the intermediates cells between
88
89
90
91
92
     * a leaf and the root.
     * It is used after inserting a new leaf to have cells from leaf to root
     * when computing
     * @param arrayIndex the index at the leaf index of the new element
     */
93
    void createPreviousCells(MortonIndex arrayIndex, MortonIndex inLeafCellIndex, const FTreeCoordinate& treePosition){
94
        int indexLevel = this->subOctreeHeight - 1;
95
        int bottomToTop = 0;
96
        while(indexLevel >= 0 && !this->cells[indexLevel][arrayIndex]){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
97
            CellClass* const newNode = cellAllocator.newObject();//new CellClass();
98
            newNode->setMortonIndex(inLeafCellIndex);
99

100
            newNode->setCoordinate(treePosition.getX() >> bottomToTop,
101
102
                                   treePosition.getY() >> bottomToTop,
                                   treePosition.getZ() >> bottomToTop);
103

104
105
            this->cells[indexLevel][arrayIndex] = newNode;

106
            --indexLevel;
107
            ++bottomToTop;
108
109
110
111
112
113
114
115
116
117
118

            arrayIndex >>= 3;
            inLeafCellIndex >>= 3;
        }
    }

    /**
      * This function is initializing variables when a new leaf is inserted in the tree
      * for example it updates the leaf array marges and calls createPreviousCells()
      * @param arrayIndex the position of the new leaf in the leafs array
      */
119
120
    void newLeafInserted(const int arrayIndex, const MortonIndex inLeafCellIndex,  const FTreeCoordinate& host){
        createPreviousCells(arrayIndex,inLeafCellIndex, host);
121
122
123
124
125
        // Update if this is the bottom left
        if(arrayIndex < this->leftLeafIndex) this->leftLeafIndex = arrayIndex;
        if(arrayIndex > this->rightLeafIndex) this->rightLeafIndex = arrayIndex;
    }

126
127
128
129
130
131
    /** Remove every cells from the array index
      * the leaf cell is removed, then we go upper and test,
      * does the upper cell do no have any more child, if tree remove
      * this cell too and go upper, etc.
      * @return true if there is no more cells in this tree
      */
132
    bool removeCellsFromLeaf( int arrayIndex ){
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
        // last array index
        int indexLevel = this->subOctreeHeight - 1;

        // Manage border limits
        if(arrayIndex == this->leftLeafIndex && arrayIndex == this->rightLeafIndex){
            // only one cells, return true
            return true;
        }
        else if(arrayIndex == this->leftLeafIndex){
            while( !this->cells[indexLevel][++this->leftLeafIndex] );
        }
        else if(arrayIndex == this->rightLeafIndex){
            while( !this->cells[indexLevel][--this->rightLeafIndex] );
        }

        // remove the last cells
BRAMAS Berenger's avatar
BRAMAS Berenger committed
149
        cellAllocator.deleteObject(this->cells[indexLevel][arrayIndex]);
150
        this->cells[indexLevel][arrayIndex] =nullptr;
151
152
153
154
155
156
157
158
159
160
        // progress upper
        --indexLevel;
        arrayIndex >>= 3;

        // to test if 8 child are empty
        CellClass* emptyArray[8];
        memset(emptyArray , 0, sizeof(CellClass*) * 8);

        // continue while we are not in the last level and our child are empty
        while(indexLevel >= 0 && memcmp(&this->cells[indexLevel+1][arrayIndex<<3], emptyArray, 8 * sizeof(CellClass*)) == 0 ){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
161
            cellAllocator.deleteObject( this->cells[indexLevel][arrayIndex] );
162
            this->cells[indexLevel][arrayIndex] = nullptr;
163
164
165
166
167
168
169
170

            --indexLevel;
            arrayIndex >>= 3;
        }
        // return true if there is no more child == 0 cell at level 0
        return memcmp(this->cells[0], emptyArray, 8 * sizeof(CellClass*)) == 0;
    }

171
172
173
174
175
176
177
178
179
180
181
182
183
    /** Disable copy */
private:
    FAbstractSubOctree(const FAbstractSubOctree&){}
    FAbstractSubOctree& operator=(const FAbstractSubOctree&){return *this;}

public:
    /**
    * Constructor
    * Allocate the cells arrays to be able to create every potential cells
    * @param inParent the SubOctree parent (0 if node)
    * @param inSubOctreeHeight Height of this suboctree
    * @param inSubOctreePosition Level of the current suboctree in the global tree (1 if upper tree)
    */
184
    FAbstractSubOctree(FAbstractSubOctree* const inParent, const int inIndexInParent,
185
                       const int inSubOctreeHeight, const int inSubOctreePosition, const bool inIsLeafSubtree) :
186
                        cells(nullptr), parent( inParent ), indexInParent(inIndexInParent), leftLeafIndex(1 << (3 * inSubOctreeHeight)), rightLeafIndex(-1),
187
                        subOctreeHeight( inSubOctreeHeight ), subOctreePosition( inSubOctreePosition ), isLeafSubtree(inIsLeafSubtree) {
188
189

        this->cells = new CellClass**[this->subOctreeHeight];
BRAMAS Berenger's avatar
BRAMAS Berenger committed
190
        FAssertLF(this->cells, "Allocation failled");
191

berenger-bramas's avatar
berenger-bramas committed
192
193
        memset(this->cells, 0, sizeof(CellClass**) * subOctreeHeight);

194
        // We start at a sub-level - 8^1
195
        int cellsAtlevel = 8;
196
197
        for( int indexLevel = 0 ; indexLevel < this->subOctreeHeight ; ++indexLevel ){
            this->cells[indexLevel] = new CellClass*[cellsAtlevel];
BRAMAS Berenger's avatar
BRAMAS Berenger committed
198
            FAssertLF(this->cells[indexLevel], "Allocation failled");
199

berenger-bramas's avatar
berenger-bramas committed
200
            memset(this->cells[indexLevel], 0, sizeof(CellClass*) * cellsAtlevel);
201
202
203
204
205
206
207
208
209
210

            cellsAtlevel <<= 3; // => * 8 >> 8^indexLevel
        }
    }

    /**
    * Destructor
    * Delete cells arrays and allocated cells
    */
    virtual ~FAbstractSubOctree(){
211
212
        int mostRight = rightLeafIndex;
        int mostLeft = leftLeafIndex;
213
214

        for( int indexLevel = this->subOctreeHeight - 1 ; indexLevel >= 0 ; --indexLevel ){
215
            for( int indexCells = mostLeft ; indexCells <= mostRight ; ++indexCells ){
216
                if(this->cells[indexLevel][indexCells]){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
217
                    cellAllocator.deleteObject( this->cells[indexLevel][indexCells] );
218
219
220
221
                }
            }

            delete [] this->cells[indexLevel];
222
223
            mostLeft  >>= 3;
            mostRight >>= 3;
224
225
226
227
228
229
230
231
        }

        delete [] this->cells;
    }


    /**
    * Insert a particle on the subtree
232
233
    * @param index the Morton index of the particle to insert
    * @param inParticle the particle to insert (must inherit from FAbstractParticle)
234
235
    * @param inParticle the inTreeHeight the height of the tree
    */
236
237
238
239
    /*template<typename... Args>
    void insert(const MortonIndex index, const FTreeCoordinate& host, const int inTreeHeight, const FPoint& inParticlePosition,
                        Args... args){
    }*/
240

241
242
243
244
245
246
    /**
      * Remove a leaf and every cells if needed
      * @return true if the subtree does not contains any more cells
      */
    virtual bool removeLeaf(const MortonIndex index, const int inTreeHeight) = 0;

247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
    ///////////////////////////////////////
    // This is the FOctree::Iterator Part
    ///////////////////////////////////////

    /** Suboctree height accessor (leaf level + 1)
      * @return subOctreeHeight */
    int getSubOctreeHeight() const{
        return subOctreeHeight;
    }

    /** Suboctree position in the real tree
      * @return subOctreePosition */
    int getSubOctreePosition() const {
        return subOctreePosition;
    }

    /** Return the more left leaf index
      * the smallest index on the leafs array
      * @return leftLeafIndex */
266
    int getLeftLeafIndex() const {
267
268
269
270
271
272
        return leftLeafIndex;
    }

    /** Return the more right leaf index
      * the biggest index on the leafs array
      * @return rightLeafIndex */
273
    int getRightLeafIndex() const {
274
275
276
277
278
279
280
        return rightLeafIndex;
    }

    /** Return the array of cells at a specious index
      * @param level the level to access cells array (must be < subOctreeHeight)
      * @return cells[level] */
    CellClass** cellsAt(const int level) const{
BRAMAS Berenger's avatar
BRAMAS Berenger committed
281
        FAssertLF(level < subOctreeHeight, "Level out of memory");
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
        return cells[level];
    }

    /** To know if it is the root suboctree
      * @return true if has parent otherwise return false */
    bool hasParent() const {
        return parent;
    }

    /** To get access to the parent suboctree
      * @return parent */
    FAbstractSubOctree* getParent(){
        return parent;
    }

    /** To get access to the parent suboctree (const version)
      * @return parent */
    const FAbstractSubOctree* getParent() const{
        return parent;
    }

    /** To get the index of the current suboctree in the parent leafs array
      * This index can is part of the morton index of the cells contains
      * in this suboctree
      * @return indexInParent */
307
    int getIndexInParent() const{
308
309
        return indexInParent;
    }
310
311
312
313
314
315
316
317

    /** To know if this class has been inherited by a leaf subtree or middle subtree
      * Of course we can do a virtual method to do that but virtual method are slower
      * if we point to parent class to call the method
      */
    bool isLeafPart() const{
        return this->isLeafSubtree;
    }
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
};



/////////////////////////////////////////////////////////////////////////////////////
// Last level sub octree
/////////////////////////////////////////////////////////////////////////////////////

/**
 * @author Berenger Bramas (berenger.bramas@inria.fr)
 * @class FSubOctreeWithLeafs
 * Please read the license
 *
 * This class is an sub-octree container.
 * But this is the specialized bottom part, in fact the last level is composed by
 * a cells array (managing by abstract class) and lists of particles.
 *
 * Please refere to testOctree.cpp to see an example.
 * @warning Give the particleClass & cellClass
 */
BRAMAS Berenger's avatar
BRAMAS Berenger committed
338
339
template< class CellClass , class ContainerClass, class LeafClass, class CellAllocatorClass>
class FSubOctreeWithLeafs : public FAbstractSubOctree<CellClass,ContainerClass,LeafClass, CellAllocatorClass> {
340
private:
BRAMAS Berenger's avatar
BRAMAS Berenger committed
341
    typedef FAbstractSubOctree<CellClass,ContainerClass,LeafClass, CellAllocatorClass> Parent;
342

berenger-bramas's avatar
berenger-bramas committed
343
    LeafClass** leafs;            //< Leafs array
344

345
public:
346
    FSubOctreeWithLeafs(const FSubOctreeWithLeafs&)                  = delete;
347
    FSubOctreeWithLeafs& operator=(const FSubOctreeWithLeafs&) = delete;
348
349
350
351
352
353
354
355

    /**
    * Constructor
    * Allocate the leafs array
    * @param inParent the SubOctree parent (0 if node)
    * @param inSubOctreeHeight Height of this suboctree
    * @param inSubOctreePosition Level of the current suboctree in the global tree (1 if upper tree)
    */
BRAMAS Berenger's avatar
BRAMAS Berenger committed
356
    FSubOctreeWithLeafs(FAbstractSubOctree<CellClass,ContainerClass,LeafClass,CellAllocatorClass>* const inParent, const int inIndexInParent,
357
                        const int inSubOctreeHeight, const int inSubOctreePosition) :
BRAMAS Berenger's avatar
BRAMAS Berenger committed
358
                        FAbstractSubOctree<CellClass,ContainerClass,LeafClass,CellAllocatorClass>(inParent, inIndexInParent, inSubOctreeHeight, inSubOctreePosition, true) {
359

360
        const int cellsAtLeafLevel = 1 << (3 * inSubOctreeHeight);
361

berenger-bramas's avatar
berenger-bramas committed
362
        this->leafs = new LeafClass*[cellsAtLeafLevel];
BRAMAS Berenger's avatar
BRAMAS Berenger committed
363
        FAssertLF(this->leafs, "Allocation failled");
364

berenger-bramas's avatar
berenger-bramas committed
365
        memset(leafs, 0, sizeof(LeafClass*) * cellsAtLeafLevel);
366
367
368
369
370
371
    }

    /**
    * Destructor dealloc all leafs & the leaf array
    */
    virtual ~FSubOctreeWithLeafs(){
berenger-bramas's avatar
berenger-bramas committed
372
        for( int indexLeaf = Parent::leftLeafIndex ; indexLeaf <= Parent::rightLeafIndex ; ++indexLeaf ){
373
374
375
376
377
378
379
380
381
382
            if(this->leafs[indexLeaf]){
                delete this->leafs[indexLeaf];
            }
        }
        delete [] this->leafs;
    }

    /**
    * Refer to FAbstractSubOctree::insert
    */
383
384
385
    template<typename... Args>
    void insert(const MortonIndex index, const FTreeCoordinate& host, const int inTreeHeight, const FPoint& inParticlePosition,
                        Args... args){
386
        // Get the morton index for the leaf level
berenger-bramas's avatar
berenger-bramas committed
387
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
388
389
        // is there already a leaf?
        if( !this->leafs[arrayIndex] ){
berenger-bramas's avatar
berenger-bramas committed
390
            this->leafs[arrayIndex] = new LeafClass();
391

berenger-bramas's avatar
berenger-bramas committed
392
            Parent::newLeafInserted( int(arrayIndex) , index, host);
393
394
        }
        // add particle to leaf list
395
396
397
398
399
400
401
402
403
404
405
406
407
408
        this->leafs[arrayIndex]->push(inParticlePosition, args... );
    }

    LeafClass* createLeaf(const MortonIndex index, const FTreeCoordinate& host, const int inTreeHeight){
        // Get the morton index for the leaf level
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
        // is there already a leaf?
        if( !this->leafs[arrayIndex] ){
            this->leafs[arrayIndex] = new LeafClass();

            Parent::newLeafInserted( int(arrayIndex) , index, host);
        }
        // add particle to leaf list
        return this->leafs[arrayIndex];
409
410
    }

411
412
413
414
415
    /**
      * Remove a leaf and every cells if needed
      */
    bool removeLeaf(const MortonIndex index, const int inTreeHeight) {
        // Get the morton index for the leaf level
berenger-bramas's avatar
berenger-bramas committed
416
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
417
418
419
        if( this->leafs[arrayIndex] ){
            // remove container
            delete this->leafs[arrayIndex];
420
            this->leafs[arrayIndex] = nullptr;
421

berenger-bramas's avatar
berenger-bramas committed
422
            return Parent::removeCellsFromLeaf( int(arrayIndex) );
423
424
425
426
        }
        return false;
    }

427
428
429
    /** To get access to leafs elements
      * @param index the position of the leaf
      * @return the list of particles at this index */
berenger-bramas's avatar
berenger-bramas committed
430
431
    ContainerClass* getLeafSrc(const int index){
        LeafClass* const leaf = this->leafs[index];
432
        return (leaf ? leaf->getSrc(): nullptr);
433
434
435
436
437
    }

    /** To get access to leafs elements
      * @param index the position of the leaf
      * @return the list of particles at this index */
berenger-bramas's avatar
berenger-bramas committed
438
439
    ContainerClass* getLeafTargets(const int index){
        LeafClass* const leaf = this->leafs[index];
440
        return (leaf ? leaf->getTargets(): nullptr);
441
442
443
444
445
    }

    /** To get access to leafs elements
      * @param index the position of the leaf
      * @return the list of particles at this index */
berenger-bramas's avatar
berenger-bramas committed
446
447
    const ContainerClass* getLeafSrc(const int index) const {
        LeafClass* const leaf = this->leafs[index];
448
        return (leaf ? leaf->getSrc(): nullptr);
449
450
451
452
453
    }

    /** To get access to leafs elements
      * @param index the position of the leaf
      * @return the list of particles at this index */
berenger-bramas's avatar
berenger-bramas committed
454
455
    const ContainerClass* getLeafTargets(const int index) const {
        LeafClass* const leaf = this->leafs[index];
456
        return (leaf ? leaf->getTargets() : nullptr);
457
458
    }

459
460
461
    LeafClass* getLeaf(const int index){
        return this->leafs[index];
    }
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
};



/////////////////////////////////////////////////////////////////////////////////////
// Middle level sub octree
/////////////////////////////////////////////////////////////////////////////////////

/**
 * @author Berenger Bramas (berenger.bramas@inria.fr)
 * @class FSubOctree
 * Please read the license
 *
 * This class is an sub-octree container.
 * This is the middle level specialized suboctree, it means that it does not contain
 * leaf but pointers to other suboctree.
 * These suboctrees at the last level can be FSubOctree of FSubOctreeWithLeafs depending
 * if they are at the bottom of the tree or not
 *
 * @warning Give the particleClass & cellClass
 */
BRAMAS Berenger's avatar
BRAMAS Berenger committed
483
484
template< class CellClass , class ContainerClass, class LeafClass, class CellAllocatorClass>
class FSubOctree : public FAbstractSubOctree<CellClass,ContainerClass,LeafClass, CellAllocatorClass> {
485
private:
BRAMAS Berenger's avatar
BRAMAS Berenger committed
486
487
    typedef FAbstractSubOctree<CellClass,ContainerClass,LeafClass,CellAllocatorClass> Parent;
    typedef FSubOctreeWithLeafs<CellClass,ContainerClass,LeafClass,CellAllocatorClass> SubOctreeWithLeaf;
berenger-bramas's avatar
berenger-bramas committed
488
489

    Parent** subleafs;    //< Last levels is composed of suboctree
490

491
492
493
494
public:

    FSubOctree(const FSubOctree&) = delete;
    FSubOctree& operator=(const FSubOctree&) = delete;
495
496
497
498
499
500
501
502

    /**
    * Constructor
    * Allocate the subleafs array
    * @param inParent the SubOctree parent (0 if node)
    * @param inSubOctreeHeight Height of this suboctree
    * @param inSubOctreePosition Level of the current suboctree in the global tree (0 if upper tree)
    */
BRAMAS Berenger's avatar
BRAMAS Berenger committed
503
    FSubOctree(FAbstractSubOctree<CellClass,ContainerClass,LeafClass,CellAllocatorClass>* const inParent,  const int inIndexInParent,
504
               const int inSubOctreeHeight, const int inSubOctreePosition) :
BRAMAS Berenger's avatar
BRAMAS Berenger committed
505
            FAbstractSubOctree<CellClass,ContainerClass,LeafClass,CellAllocatorClass>(inParent, inIndexInParent, inSubOctreeHeight, inSubOctreePosition, false) {
506

507
        const int cellsAtLeafLevel = 1 << (3 * inSubOctreeHeight);
berenger-bramas's avatar
berenger-bramas committed
508
509

        this->subleafs = new Parent*[cellsAtLeafLevel];
BRAMAS Berenger's avatar
BRAMAS Berenger committed
510
        FAssertLF(this->subleafs, "Allocation failled");
511

berenger-bramas's avatar
berenger-bramas committed
512
        memset(subleafs, 0, sizeof(Parent**) * cellsAtLeafLevel);
513
514
515
516
517
518
    }

    /**
    * Destructor dealloc all suboctrees leafs & leafs array
    */
    virtual ~FSubOctree(){
berenger-bramas's avatar
berenger-bramas committed
519
        for( int indexLeaf = Parent::leftLeafIndex ; indexLeaf <= Parent::rightLeafIndex ; ++indexLeaf ){
520
521
522
523
524
            if(this->subleafs[indexLeaf]) delete this->subleafs[indexLeaf];
        }
        delete [] this->subleafs;
    }

525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564

    template<typename... Args>
    void insert(const MortonIndex index, const FTreeCoordinate& host, const int inTreeHeight, const FPoint& inParticlePosition,
                        Args... args){
        // We need the morton index at the bottom level of this sub octree
        // so we remove the right side
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
        // Is there already a leaf?
        if( !this->subleafs[arrayIndex] ){
            // We need to create leaf sub octree
            const int nextSubOctreePosition = this->subOctreePosition + this->subOctreeHeight;
            const int nextSubOctreeHeight = FMath::Min(inTreeHeight - nextSubOctreePosition, this->subOctreeHeight);

            // Next suboctree is a middle suboctree
            if(inTreeHeight > nextSubOctreeHeight + nextSubOctreePosition){
                this->subleafs[arrayIndex] = new FSubOctree(this,int(arrayIndex),nextSubOctreeHeight,nextSubOctreePosition);
            }
            // Or next suboctree contains the reail leaf!
            else{
                this->subleafs[arrayIndex] = new SubOctreeWithLeaf(this,int(arrayIndex),nextSubOctreeHeight,nextSubOctreePosition);
            }

            const FTreeCoordinate hostAtLevel(
                        host.getX() >> (inTreeHeight - nextSubOctreePosition ),
                        host.getY() >> (inTreeHeight - nextSubOctreePosition ),
                        host.getZ() >> (inTreeHeight - nextSubOctreePosition ));

            // We need to inform parent class
            Parent::newLeafInserted( int(arrayIndex), index >> (3 * (inTreeHeight-nextSubOctreePosition) ), hostAtLevel);
        }
        // Ask next suboctree to insert the particle
        if(this->subleafs[arrayIndex]->isLeafPart()){
            ((SubOctreeWithLeaf*)this->subleafs[arrayIndex])->insert( index, host, inTreeHeight, inParticlePosition, args... );
        }
        else{
            ((FSubOctree*)this->subleafs[arrayIndex])->insert( index, host, inTreeHeight, inParticlePosition, args... );
        }
    }

    LeafClass* createLeaf(const MortonIndex index, const FTreeCoordinate& host, const int inTreeHeight){
565
566
        // We need the morton index at the bottom level of this sub octree
        // so we remove the right side
berenger-bramas's avatar
berenger-bramas committed
567
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
568
569
570
571
572
573
574
575
        // Is there already a leaf?
        if( !this->subleafs[arrayIndex] ){
            // We need to create leaf sub octree
            const int nextSubOctreePosition = this->subOctreePosition + this->subOctreeHeight;
            const int nextSubOctreeHeight = FMath::Min(inTreeHeight - nextSubOctreePosition, this->subOctreeHeight);

            // Next suboctree is a middle suboctree
            if(inTreeHeight > nextSubOctreeHeight + nextSubOctreePosition){
576
                this->subleafs[arrayIndex] = new FSubOctree(this,int(arrayIndex),nextSubOctreeHeight,nextSubOctreePosition);
577
578
579
            }
            // Or next suboctree contains the reail leaf!
            else{
580
                this->subleafs[arrayIndex] = new SubOctreeWithLeaf(this,int(arrayIndex),nextSubOctreeHeight,nextSubOctreePosition);
581
582
            }

583
584
585
586
587
            const FTreeCoordinate hostAtLevel(
                        host.getX() >> (inTreeHeight - nextSubOctreePosition ),
                        host.getY() >> (inTreeHeight - nextSubOctreePosition ),
                        host.getZ() >> (inTreeHeight - nextSubOctreePosition ));

588
            // We need to inform parent class
berenger-bramas's avatar
berenger-bramas committed
589
            Parent::newLeafInserted( int(arrayIndex), index >> (3 * (inTreeHeight-nextSubOctreePosition) ), hostAtLevel);
590
591
        }
        // Ask next suboctree to insert the particle
592
593
594
595
596
597
        if(this->subleafs[arrayIndex]->isLeafPart()){
            return ((SubOctreeWithLeaf*)this->subleafs[arrayIndex])->createLeaf( index, host, inTreeHeight );
        }
        else{
            return ((FSubOctree*)this->subleafs[arrayIndex])->createLeaf( index, host, inTreeHeight );
        }
598
599
    }

600
601
602
603
604
    /**
      * Remove a leaf and every cells if needed
      */
    bool removeLeaf(const MortonIndex index, const int inTreeHeight) {
        // Get the morton index for the leaf level
berenger-bramas's avatar
berenger-bramas committed
605
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
606
607
608
        if( this->subleafs[arrayIndex]->removeLeaf(index, inTreeHeight) ){
            // remove container
            delete this->subleafs[arrayIndex];
609
            this->subleafs[arrayIndex] = nullptr;
610

berenger-bramas's avatar
berenger-bramas committed
611
            return Parent::removeCellsFromLeaf( int(arrayIndex) );
612
613
614
615
        }
        return false;
    }

616
617
618
    /** To get access to leafs elements (child suboctree)
      * @param index the position of the leaf/child suboctree
      * @return child at this index */
BRAMAS Berenger's avatar
BRAMAS Berenger committed
619
    FAbstractSubOctree<CellClass,ContainerClass,LeafClass,CellAllocatorClass>* leafs(const int index) {
620
621
622
623
624
625
        return this->subleafs[index];
    }

    /** To get access to leafs elements (child suboctree)
      * @param index the position of the leaf/child suboctree
      * @return child at this index */
BRAMAS Berenger's avatar
BRAMAS Berenger committed
626
    const FAbstractSubOctree<CellClass,ContainerClass,LeafClass,CellAllocatorClass>* leafs(const int index) const {
627
628
629
630
631
632
        return this->subleafs[index];
    }
};


#endif //FSUBOCTREE_HPP
633