TreeBH.h

Go to the documentation of this file.

/*--------------------------------*- VM2D -*-----------------*---------------*\
| ##  ## ##   ##  ####  #####   |                            | Version 1.14   |
| ##  ## ### ### ##  ## ##  ##  |  VM2D: Vortex Method       | 2026/03/06     |
| ##  ## ## # ##    ##  ##  ##  |  for 2D Flow Simulation    *----------------*
|  ####  ##   ##   ##   ##  ##  |  Open Source Code                           |
|   ##   ##   ## ###### #####   |  https://www.github.com/vortexmethods/VM2D  |
|                                                                             |
| Copyright (C) 2017-2026 I. Marchevsky, K. Sokol, E. Ryatina, A. Kolganova   |
*-----------------------------------------------------------------------------*
| File name: TreeBH.h                                                         |
| Info: Source code of VM2D                                                   |
|                                                                             |
| This file is part of VM2D.                                                  |
| VM2D is free software: you can redistribute it and/or modify it             |
| under the terms of the GNU General Public License as published by           |
| the Free Software Foundation, either version 3 of the License, or           |
| (at your option) any later version.                                         |
|                                                                             |
| VM2D 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 License       |
| for more details.                                                           |
|                                                                             |
| You should have received a copy of the GNU General Public License           |
| along with VM2D.  If not, see <http://www.gnu.org/licenses/>.               |
\*---------------------------------------------------------------------------*/
 
#ifndef TREEBH_H
#define TREEBH_H
 
 
#include <memory>
 
#include "defsBH.h"
 
 
namespace BH
{
    extern long long op;
 
    struct TParticleCode
    {
        unsigned int key;
 
        int originNumber;
 
        Point2D r;
 
        double g;
    };
 
 
    struct treeCellT
    {
        int parent;
 
        numvector<int, 2> child;
 
        numvector<int, 2> range; 
 
        bool particle; 
 
        bool leaf;     
 
        Point2D size;   
 
        Point2D center;
 
        int level;   
 
        std::vector<Point2D> mom;
 
        std::vector<Point2D> E;
 
        std::vector<int> closeCells;
 
        //габариты ячейки
        Point2D minx_miny, maxx_maxy;
 
        //посчитан или нет габаритный прямоугольник
        bool hasGabs;
    };
 
 
    class MortonTree
    {
    private:
        const params& prm;
 
        std::vector<PointsCopy>& pointsCopy;
 
    public:
        std::vector<TParticleCode> mortonCodes;
 
    private:
        double iQuadSideVar;
 
        Point2D lowLeft;
 
        int Delta(int i, int j) const;
 
        int PrefixLength(int cell) const;
 
        std::pair<unsigned int, int> Prefix(int cell) const;
        
        void SetCellGeometry(int cell);
 
        void BuildInternalTreeCell(int i);
        
        static unsigned int ExpandBits(unsigned int v);
 
        static unsigned int Morton2D(const Point2D& r);
 
        static std::pair<Point2D, Point2D> FindEnclosingRectangleOld(const std::vector<PointsCopy>& points);
        
        //Поиск габаритного прямоугольника системы точек
        //работает под OpenMP 4.0
        //static std::pair<Point2D, Point2D> FindEnclosingRectangle(const std::vector<PointsCopy>& points);
 
        void RSort_Node3(TParticleCode* m, TParticleCode* m_temp, unsigned int n);
 
        inline void RSort_step3(TParticleCode* source, TParticleCode* dest, unsigned int n, unsigned int* offset, unsigned char sortable_bit);
        
        inline void RSort_Parallel(TParticleCode* m, TParticleCode* m_temp, unsigned int n, unsigned int* s);
 
    public:
 
        std::vector<double> iFact;
 
        std::vector<double> binomCft;
 
        const int maxTreeLevel;
 
        void getStatistics(int& numParticles, int& treshold, std::pair<int, int>& partLevel, std::pair<int, int>& leafsLevel, int& lowLevelCells) const;
 
        double& getBinom(int n, int k)
        {
            return binomCft[n * (prm.order + 1) + k];
        }
                
        //Конструктор
        MortonTree(const params& prm_, int maxTreeLevel_, std::vector<PointsCopy>& points);
        
        std::vector<int> mortonLowCells;
        //std::vector<std::vector<int>> mortonLowCells;
 
        std::vector<treeCellT> mortonTree;
 
        void MakeRootMortonTree();
 
        void BuildMortonInternalTree();
 
        void BuildMortonParticlesTree();
 
        // Два варианта заполнения списка нижних вершин: 
        // первый рекурсивный, быстро работает в последовательном варианте
        // второй нерекурсивный, хорошо распараллеливается, но неэффективен в последовательном варианте
        void FillMortonLowCells(int cell = 0);
        void FillMortonLowCellsA();
 
        void CalculateMortonTreeParams(int cell, int omplevel);
        
        void CalcLocalCoeffToLowLevel(int lowCell, std::unique_ptr<MortonTree>& treeInf, int fromWho, bool calcCloseTrees);
        
        void CalcVeloBiotSavart(int lowCell, std::unique_ptr<MortonTree>& treeInf);//, bool calcRadius);
        
                
        void CalcVeloTaylorExpansion(int lowCell);
 
        void AddVelo(int lowCell);
 
 
        //спускается до листьев рекурсивно и запускает расчет габаритного прямоугольника
        void MinMaxCellsSearch(int numCell);
 
        //расчет габаритного прямоугольника
        void MinMaxCellsCalc(BH::treeCellT& cell);
 
        //расчет габаритных прямоугольников при подъеме от листов к корню
        void GabsPyr(int numCell);
 
        //
        void ShareGabs(int numCell/*, Point2D& minx_miny, Point2D& maxx_maxy*/);
 
    };
       
}//namespace BH
 
 
#endif