FastMarching.h

Go to the documentation of this file.

// ----------------------------------------------------------------------------
// -                        CloudViewer: www.cloudViewer.org                  -
// ----------------------------------------------------------------------------
// Copyright (c) 2018-2024 www.cloudViewer.org
// SPDX-License-Identifier: MIT
// ----------------------------------------------------------------------------
 
#pragma once
 
// Local
#include "CVConst.h"
#include "CVGeom.h"
 
// system
#include <cfloat>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
 
namespace cloudViewer {
 
class DgmOctree;
 
// Maximum number of neighbors
#define CC_FM_MAX_NUMBER_OF_NEIGHBOURS 26
 
const int c_FastMarchingNeighbourPosShift[] = {  // 6  common faces
        0, -1, 0, 1, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, -1, 0, 0, 1,
        // 20 other neighbors
        -1, -1, -1, -1, -1, 0, -1, -1, 1, -1, 0, -1, -1, 0, 1, -1, 1, -1, -1, 1,
        0, -1, 1, 1, 0, -1, -1, 0, -1, 1, 0, 1, -1, 0, 1, 1, 1, -1, -1, 1, -1,
        0, 1, -1, 1, 1, 0, -1, 1, 0, 1, 1, 1, -1, 1, 1, 0, 1, 1, 1};
 
 
class CV_CORE_LIB_API FastMarching {
public:
    FastMarching();
 
    virtual ~FastMarching();
 
 
    virtual bool setSeedCell(const Tuple3i& pos);
 
 
    virtual int propagate() = 0;
 
    virtual void cleanLastPropagation();
 
 
    virtual float getTime(Tuple3i& pos, bool absoluteCoordinates = false) const;
 
 
    virtual void setExtendedConnectivity(bool state) {
        m_numberOfNeighbours = state ? 26 : 6;
    }
 
protected:
    // Macro: cell position [i,j,k] to table (3D grid) index
    inline unsigned pos2index(const Tuple3i& pos) const {
        return static_cast<unsigned>(pos.x - m_minFillIndexes.x) +
               static_cast<unsigned>(pos.y - m_minFillIndexes.y) * m_rowSize +
               static_cast<unsigned>(pos.z - m_minFillIndexes.z) * m_sliceSize +
               m_indexShift;
    }
 
    class Cell {
    public:
        inline static float T_INF() { return FLT_MAX; }
 
        enum STATE {
            EMPTY_CELL = 0,
            FAR_CELL = 1,
            TRIAL_CELL = 2,
            ACTIVE_CELL = 3
        };
 
        Cell() : state(FAR_CELL), T(T_INF()) {}
 
        virtual ~Cell() = default;
 
        STATE state;
 
        float T;
    };
 
 
    virtual int initGridWithOctree(DgmOctree* octree, unsigned char gridLevel);
 
 
    virtual int initGrid(float step, unsigned dim[3]);
 
    virtual int initOther();
 
 
    virtual float computeT(unsigned index);
 
 
    virtual float computeTCoefApprox(Cell* currentCell,
                                     Cell* neighbourCell) const = 0;
 
 
    virtual int step() = 0;
 
 
    virtual void initTrialCells();
 
 
    virtual bool instantiateGrid(unsigned size) = 0;
 
    template <class T>
    bool instantiateGridTpl(unsigned size) {
        if (m_theGrid) return false;
 
        T** grid = new T*[size];
        if (!grid) return false;
        memset(grid, 0, size * sizeof(T*));
 
        m_theGrid = reinterpret_cast<Cell**>(grid);
 
        return true;
    }
 
 
    virtual void addTrialCell(unsigned index);
 
 
    virtual void addActiveCell(unsigned index);
 
 
    virtual void addIgnoredCell(unsigned index);
 
 
    virtual unsigned getNearestTrialCell();
 
 
    void resetCells(std::vector<unsigned>& list);
 
    std::vector<unsigned> m_activeCells;
    std::vector<unsigned> m_trialCells;
    std::vector<unsigned> m_ignoredCells;
 
    bool m_initialized;
    unsigned m_dx;
    unsigned m_dy;
    unsigned m_dz;
    unsigned m_rowSize;
    unsigned m_sliceSize;
    unsigned m_indexShift;
    unsigned m_gridSize;
    Cell** m_theGrid;
 
    DgmOctree* m_octree;
    unsigned char m_gridLevel;
    float m_cellSize;
    Tuple3i m_minFillIndexes;
 
    unsigned m_numberOfNeighbours;
    int m_neighboursIndexShift[CC_FM_MAX_NUMBER_OF_NEIGHBOURS];
    float m_neighboursDistance[CC_FM_MAX_NUMBER_OF_NEIGHBOURS];
};
 
}  // namespace cloudViewer