Fast Marching algorithm (front propagation) More...

#include <FastMarching.h>

Inheritance diagram for CCCoreLib::FastMarching:

Collaboration diagram for CCCoreLib::FastMarching:

[legend]

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

Public Member Functions
	FastMarching ()
	Default constructor.

virtual	~FastMarching ()
	Destructor.

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)
	Intializes the grid as a snapshot of an octree structure at a given subdivision level. More...

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

virtual int	initOther ()
	Intializes other dimension-related variables and finishes the initialization job.

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.

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.

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

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

bool	m_initialized
	Specifiies whether structure is initialized or not.

unsigned	m_dx
	Grid size along the X dimension.

unsigned	m_dy
	Grid size along the Y dimension.

unsigned	m_dz
	Grid size along the Z dimension.

unsigned	m_rowSize
	Shift for cell access acceleration (Y dimension)

unsigned	m_sliceSize
	Shift for cell access acceleration (Z dimension)

unsigned	m_indexShift
	First index of innerbound grid.

unsigned	m_gridSize
	Grid size.

Cell **	m_theGrid
	Grid used to process Fast Marching.

DgmOctree *	m_octree
	Associated octree.

unsigned char	m_gridLevel
	Equivalent octree subdivision level.

float	m_cellSize
	Octree cell size at equivalent subdivision level.

Tuple3i	m_minFillIndexes
	Octree min fill indexes at 'm_gridLevel'.

unsigned	m_numberOfNeighbours
	Current number of neighbours (6 or 26)

int	m_neighboursIndexShift [CC_FM_MAX_NUMBER_OF_NEIGHBOURS]
	Neighbours coordinates shifts in grid.

float	m_neighboursDistance [CC_FM_MAX_NUMBER_OF_NEIGHBOURS]
	Neighbours distance weight.

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).

Member Function Documentation

◆ addActiveCell()

void FastMarching::addActiveCell ( unsigned index )

protectedvirtual

Add a cell to the ACTIVE cells list.

Parameters

index index of the cell

◆ addIgnoredCell()

void FastMarching::addIgnoredCell ( unsigned index )

protectedvirtual

Add a cell to the IGNORED cells list.

Parameters

index index of the cell

◆ addTrialCell()

void FastMarching::addTrialCell ( unsigned index )

protectedvirtual

Add a cell to the TRIAL cells list.

Parameters

index index of the cell

◆ 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).

◆ 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

◆ computeTCoefApprox()

virtual float CCCoreLib::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 CCCoreLib::FastMarchingForPropagation.

◆ 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)

◆ 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

◆ 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

◆ 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

◆ initTrialCells()

void FastMarching::initTrialCells ( )

protectedvirtual

Initializes the TRIAL cells list.

See the Fast Marching algorithm theory for more information

◆ instantiateGrid()

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

protectedpure virtual

Instantiates grid in memory.

Grid is also filled with zeros.

Parameters

size grid size

Returns: success

Implemented in CCCoreLib::FastMarchingForPropagation.

◆ propagate()

virtual int CCCoreLib::FastMarching::propagate ( )

pure virtual

Propagates the front.

The seeds should have already been initialized

Returns: propagation result (errors = negative values)

Implemented in CCCoreLib::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!

◆ setExtendedConnectivity()

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

inlinevirtual

Sets extended connectivity mode.

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

◆ 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

◆ step()

virtual int CCCoreLib::FastMarching::step ( )

protectedpure virtual

Propagates the front (one step)

Returns: a negative value if a problem occurred

Implemented in CCCoreLib::FastMarchingForPropagation.

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

FastMarching.h
FastMarching.cpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ addActiveCell()

◆ addIgnoredCell()

◆ addTrialCell()

◆ cleanLastPropagation()

◆ computeT()

◆ computeTCoefApprox()

◆ getNearestTrialCell()

◆ getTime()

◆ initGrid()

◆ initGridWithOctree()

◆ initTrialCells()

◆ instantiateGrid()

◆ propagate()

◆ resetCells()

◆ setExtendedConnectivity()

◆ setSeedCell()

◆ step()