Fast Marching algorithm (front propagation) More...

#include <FastMarching.h>

Inheritance diagram for cloudViewer::FastMarching:

[legend]

Collaboration diagram for cloudViewer::FastMarching:

[legend]

Classes
class	Cell
	A generic Fast Marching grid cell. More...

Public Member Functions
	FastMarching ()
	Default constructor. More...

virtual	~FastMarching ()
	Destructor. More...

virtual bool	setSeedCell (const Tuple3i &pos)
	Sets a given cell as "seed". More...

virtual int	propagate ()=0
	Propagates the front. More...

virtual void	cleanLastPropagation ()

virtual float	getTime (Tuple3i &pos, bool absoluteCoordinates=false) const
	Returns the front arrival time at a given cell. More...

virtual void	setExtendedConnectivity (bool state)
	Sets extended connectivity mode. More...

Protected Member Functions
unsigned	pos2index (const Tuple3i &pos) const

virtual int	initGridWithOctree (DgmOctree *octree, unsigned char gridLevel)

virtual int	initGrid (float step, unsigned dim[3])
	Intializes the grid with a given step and dimensions. More...

virtual int	initOther ()

virtual float	computeT (unsigned index)
	Computes the front arrival time at a given cell. More...

virtual float	computeTCoefApprox (Cell currentCell, Cell neighbourCell) const =0
	Computes the front acceleration between two cells. More...

virtual int	step ()=0
	Propagates the front (one step) More...

virtual void	initTrialCells ()
	Initializes the TRIAL cells list. More...

virtual bool	instantiateGrid (unsigned size)=0
	Instantiates grid in memory. More...

template<class T >
bool	instantiateGridTpl (unsigned size)
	Grid instantiation helper. More...

virtual void	addTrialCell (unsigned index)
	Add a cell to the TRIAL cells list. More...

virtual void	addActiveCell (unsigned index)
	Add a cell to the ACTIVE cells list. More...

virtual void	addIgnoredCell (unsigned index)
	Add a cell to the IGNORED cells list. More...

virtual unsigned	getNearestTrialCell ()
	Returns the TRIAL cell with the smallest front arrival time. More...

void	resetCells (std::vector< unsigned > &list)
	Resets the state of cells in a given list. More...

Protected Attributes
std::vector< unsigned >	m_activeCells
	ACTIVE cells list. More...

std::vector< unsigned >	m_trialCells
	TRIAL cells list. More...

std::vector< unsigned >	m_ignoredCells
	IGNORED cells lits. More...

bool	m_initialized
	Specifiies whether structure is initialized or not. More...

unsigned	m_dx
	Grid size along the X dimension. More...

unsigned	m_dy
	Grid size along the Y dimension. More...

unsigned	m_dz
	Grid size along the Z dimension. More...

unsigned	m_rowSize
	Shift for cell access acceleration (Y dimension) More...

unsigned	m_sliceSize
	Shift for cell access acceleration (Z dimension) More...

unsigned	m_indexShift
	First index of innerbound grid. More...

unsigned	m_gridSize
	Grid size. More...

Cell **	m_theGrid
	Grid used to process Fast Marching. More...

DgmOctree *	m_octree
	Associated octree. More...

unsigned char	m_gridLevel
	Equivalent octree subdivision level. More...

float	m_cellSize
	Octree cell size at equivalent subdivision level. More...

Tuple3i	m_minFillIndexes
	Octree min fill indexes at 'm_gridLevel'. More...

unsigned	m_numberOfNeighbours
	Current number of neighbours (6 or 26) More...

int	m_neighboursIndexShift [26]
	Neighbours coordinates shifts in grid. More...

float	m_neighboursDistance [26]
	Neighbours distance weight. More...

Detailed Description

Fast Marching algorithm (front propagation)

Implementation of the Fast Marching algorithm [Sethian 1996]. Inspired from the "vtkFastMarching" class of the "Slicer" project (http://www.slicer.org).

Definition at line 41 of file FastMarching.h.

Constructor & Destructor Documentation

◆ FastMarching()

FastMarching::FastMarching ( )

Default constructor.

Definition at line 15 of file FastMarching.cpp.

References CC_FM_MAX_NUMBER_OF_NEIGHBOURS, m_neighboursDistance, and m_neighboursIndexShift.

◆ ~FastMarching()

FastMarching::~FastMarching ( )

virtual

Destructor.

Definition at line 36 of file FastMarching.cpp.

References m_gridSize, and m_theGrid.

Member Function Documentation

◆ addActiveCell()

void FastMarching::addActiveCell ( unsigned index )

protectedvirtual

Add a cell to the ACTIVE cells list.

Parameters

index index of the cell

Definition at line 196 of file FastMarching.cpp.

References cloudViewer::FastMarching::Cell::ACTIVE_CELL, m_activeCells, m_theGrid, and cloudViewer::FastMarching::Cell::state.

Referenced by cloudViewer::FastMarchingForPropagation::findPeaks(), setSeedCell(), cloudViewer::FastMarchingForPropagation::step(), and FastMarchingForFacetExtraction::step().

◆ addIgnoredCell()

void FastMarching::addIgnoredCell ( unsigned index )

protectedvirtual

Add a cell to the IGNORED cells list.

Parameters

index index of the cell

Definition at line 201 of file FastMarching.cpp.

References cloudViewer::FastMarching::Cell::EMPTY_CELL, m_ignoredCells, m_theGrid, and cloudViewer::FastMarching::Cell::state.

Referenced by cloudViewer::FastMarchingForPropagation::step(), and FastMarchingForFacetExtraction::step().

◆ addTrialCell()

void FastMarching::addTrialCell ( unsigned index )

protectedvirtual

Add a cell to the TRIAL cells list.

Parameters

index index of the cell

Definition at line 191 of file FastMarching.cpp.

References m_theGrid, m_trialCells, cloudViewer::FastMarching::Cell::state, and cloudViewer::FastMarching::Cell::TRIAL_CELL.

Referenced by initTrialCells(), FastMarchingForFacetExtraction::initTrialCells(), cloudViewer::FastMarchingForPropagation::step(), and FastMarchingForFacetExtraction::step().

◆ cleanLastPropagation()

void FastMarching::cleanLastPropagation ( )

virtual

Finalizes an iteration process Resets the different lists and the grid. This method should be called after each propagation (before starting a new one).

Definition at line 143 of file FastMarching.cpp.

References m_activeCells, m_ignoredCells, m_trialCells, and resetCells().

Referenced by define_FastMarching(), FastMarchingForFacetExtraction::ExtractPlanarFacets(), and cloudViewer::AutoSegmentationTools::frontPropagationBasedSegmentation().

◆ computeT()

float FastMarching::computeT ( unsigned index )

protectedvirtual

Computes the front arrival time at a given cell.

the cell is represented by its index in the cell list

Parameters

index the cell index

Returns: the computed front arrival time

Definition at line 234 of file FastMarching.cpp.

References cloudViewer::FastMarching::Cell::ACTIVE_CELL, cloudViewer::c_FastMarchingNeighbourPosShift, CC_FM_MAX_NUMBER_OF_NEIGHBOURS, computeTCoefApprox(), m_neighboursDistance, m_neighboursIndexShift, m_numberOfNeighbours, m_theGrid, cloudViewer::FastMarching::Cell::state, cloudViewer::FastMarching::Cell::T, cloudViewer::FastMarching::Cell::T_INF(), and cloudViewer::FastMarching::Cell::TRIAL_CELL.

Referenced by cloudViewer::FastMarchingForPropagation::step(), and FastMarchingForFacetExtraction::step().

◆ computeTCoefApprox()

virtual float cloudViewer::FastMarching::computeTCoefApprox	(	Cell *	currentCell,
		Cell *	neighbourCell
	)		const

protectedpure virtual

Computes the front acceleration between two cells.

Parameters

currentCell	the "central" cell
neighbourCell	the other cell

Returns: the front acceleration

Implemented in FastMarchingForFacetExtraction, ccFastMarchingForNormsDirection, and cloudViewer::FastMarchingForPropagation.

Referenced by computeT(), and initTrialCells().

◆ getNearestTrialCell()

unsigned FastMarching::getNearestTrialCell ( )

protectedvirtual

Returns the TRIAL cell with the smallest front arrival time.

Returns: the index of the "earliest" TRIAL cell (or 0 in case of error)

Definition at line 206 of file FastMarching.cpp.

References m_theGrid, m_trialCells, and cloudViewer::FastMarching::Cell::T.

Referenced by cloudViewer::FastMarchingForPropagation::step(), and FastMarchingForFacetExtraction::step().

◆ getTime()

float FastMarching::getTime	(	Tuple3i &	pos,
		bool	absoluteCoordinates = `false`
	)		const

virtual

Returns the front arrival time at a given cell.

This method should only be called after the propagation succeeded. The coordinates of the cell can be absolute (i.e. expressed relatively to the octree borders) or relative (i.e. expressed relatively to the Fast Marching grid).

Parameters

pos	the cell position (3 integer coordinates)
absoluteCoordinates	whether the cell coordinates are absolute or relative

Definition at line 49 of file FastMarching.cpp.

References m_rowSize, m_sliceSize, m_theGrid, pos2index(), cloudViewer::FastMarching::Cell::T, Tuple3Tpl< Type >::x, Tuple3Tpl< Type >::y, and Tuple3Tpl< Type >::z.

Referenced by define_FastMarching().

◆ initGrid()

int FastMarching::initGrid	(	float	step,
		unsigned	dim[3]
	)

protectedvirtual

Intializes the grid with a given step and dimensions.

Parameters

step	grid step
dim	grid dimensions in 3D

Returns: a negative value if a problem occurred

Definition at line 65 of file FastMarching.cpp.

References initOther(), m_cellSize, m_dx, m_dy, m_dz, m_gridLevel, m_minFillIndexes, m_octree, and step().

◆ initGridWithOctree()

int FastMarching::initGridWithOctree	(	DgmOctree *	octree,
		unsigned char	gridLevel
	)

protectedvirtual

Intializes the grid as a snapshot of an octree structure at a given subdivision level

Parameters

octree	input octree
gridLevel	subdivision level

Returns: a negative value if a problem occurred

Definition at line 78 of file FastMarching.cpp.

References cloudViewer::DgmOctree::getCellSize(), cloudViewer::DgmOctree::getMaxFillIndexes(), cloudViewer::DgmOctree::getMinFillIndexes(), initOther(), m_cellSize, m_dx, m_dy, m_dz, m_gridLevel, m_minFillIndexes, m_octree, cloudViewer::DgmOctree::MAX_OCTREE_LEVEL, octree, Tuple3Tpl< Type >::x, Tuple3Tpl< Type >::y, and Tuple3Tpl< Type >::z.

Referenced by FastMarchingForFacetExtraction::init(), and cloudViewer::FastMarchingForPropagation::init().

◆ initOther()

int FastMarching::initOther ( )

protectedvirtual

Intializes other dimension-related variables and finishes the initialization job

Definition at line 99 of file FastMarching.cpp.

References cloudViewer::c_FastMarchingNeighbourPosShift, CC_FM_MAX_NUMBER_OF_NEIGHBOURS, instantiateGrid(), m_activeCells, m_cellSize, m_dx, m_dy, m_dz, m_gridSize, m_ignoredCells, m_indexShift, m_neighboursDistance, m_neighboursIndexShift, m_rowSize, m_sliceSize, and m_trialCells.

Referenced by initGrid(), and initGridWithOctree().

◆ initTrialCells()

void FastMarching::initTrialCells ( )

protectedvirtual

Initializes the TRIAL cells list.

See the Fast Marching algorithm theory for more information

Reimplemented in FastMarchingForFacetExtraction, and ccFastMarchingForNormsDirection.

Definition at line 168 of file FastMarching.cpp.

References addTrialCell(), computeTCoefApprox(), cloudViewer::FastMarching::Cell::FAR_CELL, m_activeCells, m_neighboursDistance, m_neighboursIndexShift, m_numberOfNeighbours, m_theGrid, cloudViewer::FastMarching::Cell::state, and cloudViewer::FastMarching::Cell::T.

Referenced by cloudViewer::FastMarchingForPropagation::propagate().

◆ instantiateGrid()

virtual bool cloudViewer::FastMarching::instantiateGrid ( unsigned size )

protectedpure virtual

Instantiates grid in memory.

Grid is also filled with zeros.

Parameters

size grid size

Returns: success

Implemented in FastMarchingForFacetExtraction, ccFastMarchingForNormsDirection, and cloudViewer::FastMarchingForPropagation.

Referenced by initOther().

◆ instantiateGridTpl()

template<class T >

bool cloudViewer::FastMarching::instantiateGridTpl ( unsigned size )

inlineprotected

Grid instantiation helper.

Definition at line 174 of file FastMarching.h.

References size.

◆ pos2index()

unsigned cloudViewer::FastMarching::pos2index ( const Tuple3i & pos ) const

inlineprotected

Definition at line 87 of file FastMarching.h.

References Tuple3Tpl< Type >::x, Tuple3Tpl< Type >::y, and Tuple3Tpl< Type >::z.

Referenced by getTime(), FastMarchingForFacetExtraction::init(), cloudViewer::FastMarchingForPropagation::init(), setSeedCell(), and FastMarchingForFacetExtraction::setSeedCell().

◆ propagate()

virtual int cloudViewer::FastMarching::propagate ( )

pure virtual

Propagates the front.

The seeds should have already been initialized

Returns: propagation result (errors = negative values)

Implemented in FastMarchingForFacetExtraction, ccFastMarchingForNormsDirection, and cloudViewer::FastMarchingForPropagation.

◆ resetCells()

void FastMarching::resetCells ( std::vector< unsigned > & list )

protected

Resets the state of cells in a given list.

Warning: the list will be cleared!

Definition at line 132 of file FastMarching.cpp.

References cloudViewer::FastMarching::Cell::FAR_CELL, m_theGrid, cloudViewer::FastMarching::Cell::state, cloudViewer::FastMarching::Cell::T, and cloudViewer::FastMarching::Cell::T_INF().

Referenced by cleanLastPropagation().

◆ setExtendedConnectivity()

virtual void cloudViewer::FastMarching::setExtendedConnectivity ( bool state )

inlinevirtual

Sets extended connectivity mode.

To use common edges instead of common faces (much slower)

Definition at line 81 of file FastMarching.h.

Referenced by define_FastMarching().

◆ setSeedCell()

bool FastMarching::setSeedCell ( const Tuple3i & pos )

virtual

Sets a given cell as "seed".

Parameters

pos	the cell position in the grid (3 integer coordinates)

Returns: whether the cell could be set as a seed or not

Reimplemented in FastMarchingForFacetExtraction.

Definition at line 150 of file FastMarching.cpp.

References cloudViewer::FastMarching::Cell::ACTIVE_CELL, addActiveCell(), m_gridSize, m_theGrid, pos2index(), cloudViewer::FastMarching::Cell::state, and cloudViewer::FastMarching::Cell::T.

Referenced by cloudViewer::DistanceComputationTools::computeGeodesicDistances(), define_FastMarching(), cloudViewer::AutoSegmentationTools::frontPropagationBasedSegmentation(), and FastMarchingForFacetExtraction::setSeedCell().

◆ step()

virtual int cloudViewer::FastMarching::step ( )

protectedpure virtual

Propagates the front (one step)

Returns: a negative value if a problem occurred

Implemented in FastMarchingForFacetExtraction, ccFastMarchingForNormsDirection, and cloudViewer::FastMarchingForPropagation.

Referenced by initGrid().

Member Data Documentation

◆ m_activeCells

std::vector<unsigned> cloudViewer::FastMarching::m_activeCells

protected

ACTIVE cells list.

Definition at line 212 of file FastMarching.h.

Referenced by addActiveCell(), cleanLastPropagation(), cloudViewer::FastMarchingForPropagation::extractPropagatedPoints(), initOther(), initTrialCells(), FastMarchingForFacetExtraction::initTrialCells(), cloudViewer::FastMarchingForPropagation::setPropagationTimingsAsDistances(), cloudViewer::FastMarchingForPropagation::step(), and FastMarchingForFacetExtraction::updateFlagsTable().

◆ m_cellSize

float cloudViewer::FastMarching::m_cellSize

protected

Octree cell size at equivalent subdivision level.

Definition at line 242 of file FastMarching.h.

Referenced by initGrid(), initGridWithOctree(), initOther(), and cloudViewer::FastMarchingForPropagation::step().

◆ m_dx

unsigned cloudViewer::FastMarching::m_dx

protected

Grid size along the X dimension.

Definition at line 221 of file FastMarching.h.

Referenced by cloudViewer::FastMarchingForPropagation::findPeaks(), initGrid(), initGridWithOctree(), and initOther().

◆ m_dy

unsigned cloudViewer::FastMarching::m_dy

protected

Grid size along the Y dimension.

Definition at line 223 of file FastMarching.h.

Referenced by cloudViewer::FastMarchingForPropagation::findPeaks(), initGrid(), initGridWithOctree(), and initOther().

◆ m_dz

unsigned cloudViewer::FastMarching::m_dz

protected

Grid size along the Z dimension.

Definition at line 225 of file FastMarching.h.

Referenced by cloudViewer::FastMarchingForPropagation::findPeaks(), initGrid(), initGridWithOctree(), and initOther().

◆ m_gridLevel

unsigned char cloudViewer::FastMarching::m_gridLevel

protected

Equivalent octree subdivision level.

Definition at line 240 of file FastMarching.h.

Referenced by FastMarchingForFacetExtraction::addCellToCurrentFacet(), FastMarchingForFacetExtraction::computeTCoefApprox(), cloudViewer::FastMarchingForPropagation::extractPropagatedPoints(), initGrid(), initGridWithOctree(), cloudViewer::FastMarchingForPropagation::setPropagationTimingsAsDistances(), and FastMarchingForFacetExtraction::updateFlagsTable().

◆ m_gridSize

unsigned cloudViewer::FastMarching::m_gridSize

protected

Grid size.

Definition at line 233 of file FastMarching.h.

Referenced by initOther(), setSeedCell(), and ~FastMarching().

◆ m_ignoredCells

std::vector<unsigned> cloudViewer::FastMarching::m_ignoredCells

protected

IGNORED cells lits.

Definition at line 216 of file FastMarching.h.

Referenced by addIgnoredCell(), cleanLastPropagation(), and initOther().

◆ m_indexShift

unsigned cloudViewer::FastMarching::m_indexShift

protected

First index of innerbound grid.

Definition at line 231 of file FastMarching.h.

Referenced by initOther().

◆ m_initialized

bool cloudViewer::FastMarching::m_initialized

protected

Specifiies whether structure is initialized or not.

Definition at line 219 of file FastMarching.h.

Referenced by FastMarchingForFacetExtraction::addCellToCurrentFacet(), cloudViewer::FastMarchingForPropagation::extractPropagatedPoints(), cloudViewer::FastMarchingForPropagation::findPeaks(), FastMarchingForFacetExtraction::init(), cloudViewer::FastMarchingForPropagation::init(), cloudViewer::FastMarchingForPropagation::setPropagationTimingsAsDistances(), cloudViewer::FastMarchingForPropagation::step(), FastMarchingForFacetExtraction::step(), and FastMarchingForFacetExtraction::updateFlagsTable().

◆ m_minFillIndexes

Tuple3i cloudViewer::FastMarching::m_minFillIndexes

protected

Octree min fill indexes at 'm_gridLevel'.

Definition at line 244 of file FastMarching.h.

Referenced by initGrid(), and initGridWithOctree().

◆ m_neighboursDistance

float cloudViewer::FastMarching::m_neighboursDistance[26]

protected

Neighbours distance weight.

Definition at line 251 of file FastMarching.h.

Referenced by computeT(), FastMarching(), initOther(), initTrialCells(), and FastMarchingForFacetExtraction::initTrialCells().

◆ m_neighboursIndexShift

int cloudViewer::FastMarching::m_neighboursIndexShift[26]

protected

Neighbours coordinates shifts in grid.

Definition at line 249 of file FastMarching.h.

Referenced by computeT(), FastMarching(), cloudViewer::FastMarchingForPropagation::findPeaks(), initOther(), initTrialCells(), FastMarchingForFacetExtraction::initTrialCells(), cloudViewer::FastMarchingForPropagation::step(), and FastMarchingForFacetExtraction::step().

◆ m_numberOfNeighbours

unsigned cloudViewer::FastMarching::m_numberOfNeighbours

protected

Current number of neighbours (6 or 26)

Definition at line 247 of file FastMarching.h.

Referenced by computeT(), initTrialCells(), FastMarchingForFacetExtraction::initTrialCells(), cloudViewer::FastMarchingForPropagation::step(), and FastMarchingForFacetExtraction::step().

◆ m_octree

DgmOctree* cloudViewer::FastMarching::m_octree

protected

Associated octree.

Definition at line 238 of file FastMarching.h.

Referenced by FastMarchingForFacetExtraction::addCellToCurrentFacet(), FastMarchingForFacetExtraction::computeTCoefApprox(), cloudViewer::FastMarchingForPropagation::extractPropagatedPoints(), initGrid(), initGridWithOctree(), cloudViewer::FastMarchingForPropagation::setPropagationTimingsAsDistances(), FastMarchingForFacetExtraction::setSeedCell(), and FastMarchingForFacetExtraction::updateFlagsTable().

◆ m_rowSize

unsigned cloudViewer::FastMarching::m_rowSize

protected

Shift for cell access acceleration (Y dimension)

Definition at line 227 of file FastMarching.h.

Referenced by cloudViewer::FastMarchingForPropagation::findPeaks(), getTime(), and initOther().

◆ m_sliceSize

unsigned cloudViewer::FastMarching::m_sliceSize

protected

Shift for cell access acceleration (Z dimension)

Definition at line 229 of file FastMarching.h.

Referenced by cloudViewer::FastMarchingForPropagation::findPeaks(), getTime(), and initOther().

◆ m_theGrid

Cell** cloudViewer::FastMarching::m_theGrid

protected

◆ m_trialCells

std::vector<unsigned> cloudViewer::FastMarching::m_trialCells

protected

TRIAL cells list.

Definition at line 214 of file FastMarching.h.

Referenced by addTrialCell(), cleanLastPropagation(), getNearestTrialCell(), and initOther().

The documentation for this class was generated from the following files:

/root/ACloudViewer/core/include/FastMarching.h
/root/ACloudViewer/core/src/FastMarching.cpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ FastMarching()

◆ ~FastMarching()

Member Function Documentation

◆ addActiveCell()

◆ addIgnoredCell()

◆ addTrialCell()

◆ cleanLastPropagation()

◆ computeT()

◆ computeTCoefApprox()

◆ getNearestTrialCell()

◆ getTime()

◆ initGrid()

◆ initGridWithOctree()

◆ initOther()

◆ initTrialCells()

◆ instantiateGrid()

◆ instantiateGridTpl()

◆ pos2index()

◆ propagate()

◆ resetCells()

◆ setExtendedConnectivity()

◆ setSeedCell()

◆ step()

Member Data Documentation

◆ m_activeCells

◆ m_cellSize

◆ m_dx

◆ m_dy

◆ m_dz

◆ m_gridLevel

◆ m_gridSize

◆ m_ignoredCells

◆ m_indexShift

◆ m_initialized

◆ m_minFillIndexes

◆ m_neighboursDistance

◆ m_neighboursIndexShift

◆ m_numberOfNeighbours

◆ m_octree

◆ m_rowSize

◆ m_sliceSize

◆ m_theGrid

◆ m_trialCells