FSubOctree.hpp 24.7 KB
Newer Older
1
// See LICENCE file at project root
2
3
#ifndef FSUBOCTREE_HPP
#define FSUBOCTREE_HPP
4

5
6

#include "../Utils/FGlobal.hpp"
BRAMAS Berenger's avatar
BRAMAS Berenger committed
7
#include "../Utils/FPoint.hpp"
BRAMAS Berenger's avatar
BRAMAS Berenger committed
8
#include "../Utils/FAssert.hpp"
9
10
11
12
13
14
15
16
17
18
19
20
#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.
21
 *
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 * 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
 */
36
template<class FReal, class CellClass , class ContainerClass, class LeafClass, class CellAllocatorClass>
BRAMAS Berenger's avatar
BRAMAS Berenger committed
37
class FAbstractSubOctree {
38
39
protected:

PIACIBELLO Cyrille's avatar
PIACIBELLO Cyrille committed
40
    CellClass*** cells;                     //< Potential cells, cells are allocated only if needed
41
42
    FAbstractSubOctree* const parent;       //< Parent suboctree (null for root)

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

45
46
    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)
47
48

    const int subOctreeHeight;              //< Height of this suboctree
PIACIBELLO Cyrille's avatar
PIACIBELLO Cyrille committed
49
    const int subOctreePosition;            //< Level of the current suboctree in the global tree (0 if node)
50

51
52
    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
53
    CellAllocatorClass cellAllocator;
54
55
56
57
58
59
60
61
62
63
64
65
66
67

    /**
     * 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
ESTERIE Pierre's avatar
ESTERIE Pierre committed
68
        const MortonIndex treeLeafMask = ~(~0ULL << (3 *  this->subOctreeHeight ));
69
70
71
72
        return treeLeafMask & fullIndex;
    }

    /**
73
     * This function creates all the intermediates cells between
74
75
76
77
78
     * 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
     */
79
    void createPreviousCells(MortonIndex arrayIndex, MortonIndex inLeafCellIndex, const FTreeCoordinate& treePosition){
80
        int indexLevel = this->subOctreeHeight - 1;
81
        int bottomToTop = 0;
82
        while(indexLevel >= 0 && !this->cells[indexLevel][arrayIndex]){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
83
            CellClass* const newNode = cellAllocator.newObject();//new CellClass();
84
            newNode->setMortonIndex(inLeafCellIndex);
85

86
            newNode->setCoordinate(treePosition.getX() >> bottomToTop,
87
88
                                   treePosition.getY() >> bottomToTop,
                                   treePosition.getZ() >> bottomToTop);
89

90
91
            newNode->setLevel(this->subOctreePosition + indexLevel);

92
93
            this->cells[indexLevel][arrayIndex] = newNode;

94
            --indexLevel;
95
            ++bottomToTop;
96
97
98
99
100
101
102
103
104
105
106

            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
      */
107
108
    void newLeafInserted(const int arrayIndex, const MortonIndex inLeafCellIndex,  const FTreeCoordinate& host){
        createPreviousCells(arrayIndex,inLeafCellIndex, host);
109
110
111
112
113
        // Update if this is the bottom left
        if(arrayIndex < this->leftLeafIndex) this->leftLeafIndex = arrayIndex;
        if(arrayIndex > this->rightLeafIndex) this->rightLeafIndex = arrayIndex;
    }

114
115
116
117
118
119
    /** 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
      */
120
    bool removeCellsFromLeaf( int arrayIndex ){
121
122
123
124
125
        // last array index
        int indexLevel = this->subOctreeHeight - 1;

        // Manage border limits
        if(arrayIndex == this->leftLeafIndex && arrayIndex == this->rightLeafIndex){
PIACIBELLO Cyrille's avatar
PIACIBELLO Cyrille committed
126
            this->rightLeafIndex = -1;
127
128
129
130
131
132
133
134
135
136
            // only one cells, 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
137
        cellAllocator.deleteObject(this->cells[indexLevel][arrayIndex]);
138
        this->cells[indexLevel][arrayIndex] =nullptr;
139
140
141
142
143
144
145
146
147
148
        // 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
149
            cellAllocator.deleteObject( this->cells[indexLevel][arrayIndex] );
150
            this->cells[indexLevel][arrayIndex] = nullptr;
151
152
153
154
155
156
157
158

            --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;
    }

159
160
161
162
163
164
165
166
167
168
169
170
171
    /** 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)
    */
172
    FAbstractSubOctree(FAbstractSubOctree* const inParent, const int inIndexInParent,
173
                       const int inSubOctreeHeight, const int inSubOctreePosition, const bool inIsLeafSubtree) :
174
                        cells(nullptr), parent( inParent ), indexInParent(inIndexInParent), leftLeafIndex(1 << (3 * inSubOctreeHeight)), rightLeafIndex(-1),
175
                        subOctreeHeight( inSubOctreeHeight ), subOctreePosition( inSubOctreePosition ), isLeafSubtree(inIsLeafSubtree) {
176
177

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

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

182
        // We start at a sub-level - 8^1
183
        int cellsAtlevel = 8;
184
185
        for( int indexLevel = 0 ; indexLevel < this->subOctreeHeight ; ++indexLevel ){
            this->cells[indexLevel] = new CellClass*[cellsAtlevel];
BRAMAS Berenger's avatar
BRAMAS Berenger committed
186
            FAssertLF(this->cells[indexLevel], "Allocation failled");
187

berenger-bramas's avatar
berenger-bramas committed
188
            memset(this->cells[indexLevel], 0, sizeof(CellClass*) * cellsAtlevel);
189
190
191
192
193
194
195
196
197
198

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

    /**
    * Destructor
    * Delete cells arrays and allocated cells
    */
    virtual ~FAbstractSubOctree(){
199
200
        int mostRight = rightLeafIndex;
        int mostLeft = leftLeafIndex;
201
202

        for( int indexLevel = this->subOctreeHeight - 1 ; indexLevel >= 0 ; --indexLevel ){
203
            for( int indexCells = mostLeft ; indexCells <= mostRight ; ++indexCells ){
204
                if(this->cells[indexLevel][indexCells]){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
205
                    cellAllocator.deleteObject( this->cells[indexLevel][indexCells] );
206
207
208
209
                }
            }

            delete [] this->cells[indexLevel];
210
211
            mostLeft  >>= 3;
            mostRight >>= 3;
212
213
214
215
216
217
218
219
        }

        delete [] this->cells;
    }


    /**
    * Insert a particle on the subtree
220
221
    * @param index the Morton index of the particle to insert
    * @param inParticle the particle to insert (must inherit from FAbstractParticle)
222
223
    * @param inParticle the inTreeHeight the height of the tree
    */
224
    /*template<typename... Args>
225
    void insert(const MortonIndex index, const FTreeCoordinate& host, const int inTreeHeight, const FPoint<FReal>& inParticlePosition,
226
227
                        Args... args){
    }*/
228

229
230
231
232
233
234
    /**
      * 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;

235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
    ///////////////////////////////////////
    // 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 */
254
    int getLeftLeafIndex() const {
255
256
257
258
259
260
        return leftLeafIndex;
    }

    /** Return the more right leaf index
      * the biggest index on the leafs array
      * @return rightLeafIndex */
261
    int getRightLeafIndex() const {
262
263
264
265
266
267
268
        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
269
        FAssertLF(level < subOctreeHeight, "Level out of memory");
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
        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 */
295
    int getIndexInParent() const{
296
297
        return indexInParent;
    }
298
299
300
301
302
303
304
305

    /** 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;
    }
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
};



/////////////////////////////////////////////////////////////////////////////////////
// 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
 */
326
327
template< class FReal, class CellClass , class ContainerClass, class LeafClass, class CellAllocatorClass>
class FSubOctreeWithLeafs : public FAbstractSubOctree<FReal, CellClass,ContainerClass,LeafClass, CellAllocatorClass> {
328
private:
329
    typedef FAbstractSubOctree<FReal, CellClass,ContainerClass,LeafClass, CellAllocatorClass> Parent;
330

berenger-bramas's avatar
berenger-bramas committed
331
    LeafClass** leafs;            //< Leafs array
332

333
public:
334
    FSubOctreeWithLeafs(const FSubOctreeWithLeafs&)                  = delete;
335
    FSubOctreeWithLeafs& operator=(const FSubOctreeWithLeafs&) = delete;
336
337
338
339
340
341
342
343

    /**
    * 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)
    */
344
    FSubOctreeWithLeafs(FAbstractSubOctree<FReal,CellClass,ContainerClass,LeafClass,CellAllocatorClass>* const inParent, const int inIndexInParent,
345
                        const int inSubOctreeHeight, const int inSubOctreePosition) :
346
                        FAbstractSubOctree<FReal,CellClass,ContainerClass,LeafClass,CellAllocatorClass>(inParent, inIndexInParent, inSubOctreeHeight, inSubOctreePosition, true) {
347

348
        const int cellsAtLeafLevel = 1 << (3 * inSubOctreeHeight);
349

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

berenger-bramas's avatar
berenger-bramas committed
353
        memset(leafs, 0, sizeof(LeafClass*) * cellsAtLeafLevel);
354
355
356
357
358
359
    }

    /**
    * Destructor dealloc all leafs & the leaf array
    */
    virtual ~FSubOctreeWithLeafs(){
berenger-bramas's avatar
berenger-bramas committed
360
        for( int indexLeaf = Parent::leftLeafIndex ; indexLeaf <= Parent::rightLeafIndex ; ++indexLeaf ){
361
362
363
364
365
366
367
368
369
370
            if(this->leafs[indexLeaf]){
                delete this->leafs[indexLeaf];
            }
        }
        delete [] this->leafs;
    }

    /**
    * Refer to FAbstractSubOctree::insert
    */
371
    template<typename... Args>
372
    void insert(const MortonIndex index, const FTreeCoordinate& host, const int inTreeHeight, const FPoint<FReal>& inParticlePosition,
373
                        Args... args){
374
        // Get the morton index for the leaf level
berenger-bramas's avatar
berenger-bramas committed
375
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
376
377
        // is there already a leaf?
        if( !this->leafs[arrayIndex] ){
berenger-bramas's avatar
berenger-bramas committed
378
            this->leafs[arrayIndex] = new LeafClass();
379

berenger-bramas's avatar
berenger-bramas committed
380
            Parent::newLeafInserted( int(arrayIndex) , index, host);
381
382
        }
        // add particle to leaf list
383
384
385
386
387
388
389
390
391
392
393
394
395
396
        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];
397
398
    }

399
400
401
402
403
    /**
      * 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
404
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
405
406
407
        if( this->leafs[arrayIndex] ){
            // remove container
            delete this->leafs[arrayIndex];
408
            this->leafs[arrayIndex] = nullptr;
409

berenger-bramas's avatar
berenger-bramas committed
410
            return Parent::removeCellsFromLeaf( int(arrayIndex) );
411
412
413
414
        }
        return false;
    }

415
416
417
    /** 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
418
419
    ContainerClass* getLeafSrc(const int index){
        LeafClass* const leaf = this->leafs[index];
420
        return (leaf ? leaf->getSrc(): nullptr);
421
422
423
424
425
    }

    /** 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
426
427
    ContainerClass* getLeafTargets(const int index){
        LeafClass* const leaf = this->leafs[index];
428
        return (leaf ? leaf->getTargets(): nullptr);
429
430
431
432
433
    }

    /** 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
434
435
    const ContainerClass* getLeafSrc(const int index) const {
        LeafClass* const leaf = this->leafs[index];
436
        return (leaf ? leaf->getSrc(): nullptr);
437
438
439
440
441
    }

    /** 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
442
443
    const ContainerClass* getLeafTargets(const int index) const {
        LeafClass* const leaf = this->leafs[index];
444
        return (leaf ? leaf->getTargets() : nullptr);
445
446
    }

447
448
449
    LeafClass* getLeaf(const int index){
        return this->leafs[index];
    }
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
};



/////////////////////////////////////////////////////////////////////////////////////
// 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
 */
471
472
template<class FReal, class CellClass , class ContainerClass, class LeafClass, class CellAllocatorClass>
class FSubOctree : public FAbstractSubOctree<FReal, CellClass,ContainerClass,LeafClass, CellAllocatorClass> {
473
private:
474
475
    typedef FAbstractSubOctree<FReal, CellClass,ContainerClass,LeafClass,CellAllocatorClass> Parent;
    typedef FSubOctreeWithLeafs<FReal, CellClass,ContainerClass,LeafClass,CellAllocatorClass> SubOctreeWithLeaf;
berenger-bramas's avatar
berenger-bramas committed
476
477

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

479
480
481
482
public:

    FSubOctree(const FSubOctree&) = delete;
    FSubOctree& operator=(const FSubOctree&) = delete;
483
484
485
486
487
488
489
490

    /**
    * 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)
    */
491
    FSubOctree(FAbstractSubOctree<FReal, CellClass,ContainerClass,LeafClass,CellAllocatorClass>* const inParent,  const int inIndexInParent,
492
               const int inSubOctreeHeight, const int inSubOctreePosition) :
493
            FAbstractSubOctree<FReal, CellClass,ContainerClass,LeafClass,CellAllocatorClass>(inParent, inIndexInParent, inSubOctreeHeight, inSubOctreePosition, false) {
494

495
        const int cellsAtLeafLevel = 1 << (3 * inSubOctreeHeight);
berenger-bramas's avatar
berenger-bramas committed
496
497

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

berenger-bramas's avatar
berenger-bramas committed
500
        memset(subleafs, 0, sizeof(Parent**) * cellsAtLeafLevel);
501
502
503
504
505
506
    }

    /**
    * Destructor dealloc all suboctrees leafs & leafs array
    */
    virtual ~FSubOctree(){
berenger-bramas's avatar
berenger-bramas committed
507
        for( int indexLeaf = Parent::leftLeafIndex ; indexLeaf <= Parent::rightLeafIndex ; ++indexLeaf ){
508
509
510
511
512
            if(this->subleafs[indexLeaf]) delete this->subleafs[indexLeaf];
        }
        delete [] this->subleafs;
    }

513
514

    template<typename... Args>
515
    void insert(const MortonIndex index, const FTreeCoordinate& host, const int inTreeHeight, const FPoint<FReal>& inParticlePosition,
516
517
518
519
520
521
522
523
524
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
                        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){
553
554
        // 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
555
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
556
557
558
559
560
561
562
563
        // 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){
564
                this->subleafs[arrayIndex] = new FSubOctree(this,int(arrayIndex),nextSubOctreeHeight,nextSubOctreePosition);
565
566
567
            }
            // Or next suboctree contains the reail leaf!
            else{
568
                this->subleafs[arrayIndex] = new SubOctreeWithLeaf(this,int(arrayIndex),nextSubOctreeHeight,nextSubOctreePosition);
569
570
            }

571
572
573
574
575
            const FTreeCoordinate hostAtLevel(
                        host.getX() >> (inTreeHeight - nextSubOctreePosition ),
                        host.getY() >> (inTreeHeight - nextSubOctreePosition ),
                        host.getZ() >> (inTreeHeight - nextSubOctreePosition ));

576
            // We need to inform parent class
berenger-bramas's avatar
berenger-bramas committed
577
            Parent::newLeafInserted( int(arrayIndex), index >> (3 * (inTreeHeight-nextSubOctreePosition) ), hostAtLevel);
578
579
        }
        // Ask next suboctree to insert the particle
580
581
582
583
584
585
        if(this->subleafs[arrayIndex]->isLeafPart()){
            return ((SubOctreeWithLeaf*)this->subleafs[arrayIndex])->createLeaf( index, host, inTreeHeight );
        }
        else{
            return ((FSubOctree*)this->subleafs[arrayIndex])->createLeaf( index, host, inTreeHeight );
        }
586
587
    }

588
589
590
591
592
    /**
      * 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
593
        const MortonIndex arrayIndex = Parent::getLeafIndex(index,inTreeHeight);
594
595
596
        if( this->subleafs[arrayIndex]->removeLeaf(index, inTreeHeight) ){
            // remove container
            delete this->subleafs[arrayIndex];
597
            this->subleafs[arrayIndex] = nullptr;
598

berenger-bramas's avatar
berenger-bramas committed
599
            return Parent::removeCellsFromLeaf( int(arrayIndex) );
600
601
602
603
        }
        return false;
    }

604
605
606
    /** 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
607
    FAbstractSubOctree<FReal,CellClass,ContainerClass,LeafClass,CellAllocatorClass>* leafs(const size_t index) {
608
609
610
611
612
613
        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
614
    const FAbstractSubOctree<FReal,CellClass,ContainerClass,LeafClass,CellAllocatorClass>* leafs(const size_t index) const {
615
616
617
618
619
620
        return this->subleafs[index];
    }
};


#endif //FSUBOCTREE_HPP