DGtal::DigitalSetByOctree< Space > Class Template Reference

A DigitalSet that stores voxels as an octree, or a DAG. More...

#include <DGtal/kernel/sets/DigitalSetByOctree.h>

Inheritance diagram for DGtal::DigitalSetByOctree< Space >:

Data Structures
struct	Node
	Node for octree. More...
struct	ComputationCacheKey
	Helper struct for computing local estimators. More...
struct	TraversalMemory
	Helper struct to store traversal and go to next leaf. More...
struct	OctreeIterator
	Iterator over the octree. More...

Public Types
using	DimIndex = std::uint8_t
using	CellIndex = typename Space::UnsignedInteger
using	Size = size_t
using	Domain = HyperRectDomain<Space>
using	Point = typename Domain::Point
using	Value = void
using	Iterator = OctreeIterator
using	ConstIterator = OctreeIterator

Public Member Functions
	DigitalSetByOctree (const Domain &d)
	Constructor from a domain.
const Domain &	domain () const
	Returns the domain of the digital set.
CowPtr< Domain >	domainPointer () const
	Returns the domain of the voxels.
void	insert (const Point &p)
	Inserts a new point in the octree.
void	insertNew (const Point &p)
	Inserts a new point in the octree.
bool	operator() (const Point &p) const
	Check if a voxel is set or not.
Iterator	find (const Point &p) const
	Finds a point within the Octree.
size_t	size () const
	Returns the number of voxel in the set.
bool	empty () const
	Check if the octree is empty or not.
size_t	memoryFootprint () const
	Returns the memory occupied by node storage in bytes.
void	clear ()
	Removes all nodes from the octree.
size_t	erase (const Iterator &it)
	Remove a voxel from the octree.
size_t	erase (Iterator begin, Iterator end)
	Removes a range of voxels.
size_t	erase (const Point &p)
	Removes a voxel from the octree.
void	shrinkToFit ()
	Shrinks storage to reduce memory usage.
DigitalSetByOctree &	operator+= (const DigitalSetByOctree &other)
	Appends an octree to another.
template<typename It>
void	computeComplement (It out) const
	Computes the complement of the octree.
template<class DSet>
void	assignFromComplement (const DSet &other)
	Assigns the octree as the complement of another set.
void	computeBoundingBox (Point &lb, Point &ub) const
	Computes the bounding box of stored points.
Iterator	begin () const
	Returns an iterator to the begining of the octree.
Iterator	begin ()
	Returns an iterator to the begining of the octree.
Iterator	end ()
	Returns an iterator to the end of the octree.
Iterator	end () const
	Returns an iterator to the end of the octree.
void	convertToDAG ()
	Converts the octree to DAG.
template<class Func>
auto	computeFunction (OctreeIterator start, OctreeIterator end, CellIndex range, const Func &f)
void	dumpOctree () const
	Dumps the octree to std out.

Static Public Attributes
static constexpr DGtal::Dimension	D = Space::dimension
static constexpr DGtal::Dimension	dimension = Space::dimension
static constexpr CellIndex	CELL_COUNT = (1 << D)
static constexpr CellIndex	INVALID_IDX = std::numeric_limits<CellIndex>::max()
static constexpr std::array< std::array< DimIndex, D >, CELL_COUNT >	SIDES_FROM_INDEX

Private Types
enum class	State { OCTREE = 1 , DAG = 2 }
	The state the container is in. More...

Static Private Member Functions
static Domain	splitDomain (const Domain &domain, const DimIndex *sides)
	Helper function to split and select among 2^D subdomains.

Private Attributes
CowPtr< Domain >	myAdmissibleDomain
CowPtr< Domain >	myDomain
State	myState = State::OCTREE
size_t	mySize
std::vector< std::vector< Node > >	myNodes

Friends
template<class>
class	SVOWriter
template<class>
class	SVOReader

Detailed Description

template<class Space>
class DGtal::DigitalSetByOctree< Space >

A DigitalSet that stores voxels as an octree, or a DAG.

This class allows for a compact representation of voxel as a sparse voxel octree (SVO). Optionally, this can be further compressed as a Sparse Voxel Directed Acyclic Graph where nodes are shared when they share a common structure.

Leaves are never explicitly stored to further reduce memory usage.

Common operation complexity: (L = depth of the tree computed with domain size, N = number of voxels)

• Insertion: O(log(L))
• Erase: O(N * log(L))
• find: O(log(L))
• Iterator next: O(log(L))
• Listing all voxels: O(N * log(L))
• Memory usage (octree): O(N * log(L))

When converted to a DAG, the digital set can not be modified anymore (neither insertion, or erase).

References: [77] [61]

Definition at line 69 of file DigitalSetByOctree.h.

Member Typedef Documentation

CellIndex

template<class Space>

using DGtal::DigitalSetByOctree< Space >::CellIndex = typename Space::UnsignedInteger

Definition at line 78 of file DigitalSetByOctree.h.

ConstIterator

template<class Space>

using DGtal::DigitalSetByOctree< Space >::ConstIterator = OctreeIterator

Definition at line 282 of file DigitalSetByOctree.h.

DimIndex

template<class Space>

using DGtal::DigitalSetByOctree< Space >::DimIndex = std::uint8_t

Definition at line 77 of file DigitalSetByOctree.h.

Domain

template<class Space>

using DGtal::DigitalSetByOctree< Space >::Domain = HyperRectDomain<Space>

Definition at line 82 of file DigitalSetByOctree.h.

Iterator

template<class Space>

using DGtal::DigitalSetByOctree< Space >::Iterator = OctreeIterator

Definition at line 281 of file DigitalSetByOctree.h.

Point

template<class Space>

using DGtal::DigitalSetByOctree< Space >::Point = typename Domain::Point

Definition at line 83 of file DigitalSetByOctree.h.

Size

template<class Space>

using DGtal::DigitalSetByOctree< Space >::Size = size_t

Definition at line 79 of file DigitalSetByOctree.h.

Value

template<class Space>

using DGtal::DigitalSetByOctree< Space >::Value = void

Definition at line 87 of file DigitalSetByOctree.h.

Member Enumeration Documentation

State

template<class Space>

enum class DGtal::DigitalSetByOctree::State

strongprivate

The state the container is in.

After the octree is converted to a DAG, it is not possible to insert or remove nodes.

Enumerator
OCTREE
DAG

Definition at line 581 of file DigitalSetByOctree.h.

        {
          OCTREE = 1, 
          DAG    = 2
        };

Constructor & Destructor Documentation

DigitalSetByOctree()

template<class Space>

DGtal::DigitalSetByOctree< Space >::DigitalSetByOctree

(

const Domain &

d

)

Constructor from a domain.

Only HyperRectDomains are supported for octrees.

The given domain will be extended to ensure it is an hyper cube with sides that is a power of 2

Parameters

d	The domain

Member Function Documentation

assignFromComplement()

template<class Space>

template<class DSet>

void DGtal::DigitalSetByOctree< Space >::assignFromComplement ( const DSet & other )

inline

Assigns the octree as the complement of another set.

This is equivalent to looping through a set and inserting every node

Parameters

other

The digital set to compute complement of

Definition at line 484 of file DigitalSetByOctree.h.

        {
          if (myState == State::OCTREE) 
          {
            clear();
            for (auto it = myDomain->begin(); it != myDomain->end(); ++it) 
            {
              if (!other(*it)) 
                  insert(*it);
            }
          }
        }

begin() [1/2]

template<class Space>

Iterator DGtal::DigitalSetByOctree< Space >::begin ( )

inline

Returns an iterator to the begining of the octree.

Definition at line 538 of file DigitalSetByOctree.h.

{ return static_cast<const DigitalSetByOctree&>(*this).begin(); }

begin() [2/2]

template<class Space>

Iterator DGtal::DigitalSetByOctree< Space >::begin ( ) const

inline

Returns an iterator to the begining of the octree.

Definition at line 524 of file DigitalSetByOctree.h.

        {
          TraversalMemory mem;
          mem.domain = *myDomain;
          mem.lvl = 0;
          mem.idx = 0;
          mem.currentChildIdx = INVALID_IDX;
          
          return Iterator(this, mem);
        }

Referenced by DGtal::DigitalSetByOctree< Z3i::Space >::computeBoundingBox(), DGtal::DigitalSetByOctree< Z3i::Space >::operator+=(), and TEST_CASE_METHOD().

clear()

template<class Space>

void DGtal::DigitalSetByOctree< Space >::clear ( )

inline

Removes all nodes from the octree.

Note: if the octree has been converted to a dag, this function reset the flag and insertion is available afterwards.

Definition at line 379 of file DigitalSetByOctree.h.

        {
          myNodes.clear();
          myState = State::OCTREE;
        }

Referenced by DGtal::DigitalSetByOctree< Z3i::Space >::assignFromComplement().

computeBoundingBox()

template<class Space>

void DGtal::DigitalSetByOctree< Space >::computeBoundingBox ( Point & lb, Point & ub ) const

inline

Computes the bounding box of stored points.

This functions runs in O(N log(L)).

Parameters

lb	Output lower bound
ub	Output upper bound

Definition at line 505 of file DigitalSetByOctree.h.

        {
          lb = myDomain->upperBound();
          ub = myDomain->lowerBound();
 
          for (auto it = begin(); it != end(); ++it) 
          {
            const auto p = *it;
            for (DimIndex d = 0; d < D; d++) 
            {
              lb[d] = std::min(lb[d], p[d]);
              ub[d] = std::max(ub[d], p[d]);
            }
          }
        }

computeComplement()

template<class Space>

template<typename It>

void DGtal::DigitalSetByOctree< Space >::computeComplement ( It out ) const

inline

Computes the complement of the octree.

This is equivalent to looping through an octree and inserting

Parameters

out	The output iterator

Definition at line 462 of file DigitalSetByOctree.h.

        {
          DigitalSetByOctree complement(*myDomain);
          for (auto it = myDomain->begin(); it != myDomain->end(); ++it) 
          {
            if (!this->operator()(*it)) 
            {
              *out = *it;
              ++out;
            }
          }
        }

computeFunction()

template<class Space>

template<class Func>

auto DGtal::DigitalSetByOctree< Space >::computeFunction	(	OctreeIterator	start,
		OctreeIterator	end,
		CellIndex	range,
		const Func &	f )

convertToDAG()

template<class Space>

void DGtal::DigitalSetByOctree< Space >::convertToDAG

(

)

Converts the octree to DAG.

Referenced by TEST_CASE_METHOD().

domain()

template<class Space>

const Domain & DGtal::DigitalSetByOctree< Space >::domain ( ) const

inline

Returns the domain of the digital set.

Definition at line 299 of file DigitalSetByOctree.h.

{ return *myAdmissibleDomain; }

Referenced by TEST_CASE_METHOD().

domainPointer()

template<class Space>

CowPtr< Domain > DGtal::DigitalSetByOctree< Space >::domainPointer ( ) const

inline

Returns the domain of the voxels.

Definition at line 304 of file DigitalSetByOctree.h.

{ return myAdmissibleDomain; }

dumpOctree()

template<class Space>

void DGtal::DigitalSetByOctree< Space >::dumpOctree

(

)

const

Dumps the octree to std out.

Note: This function is meant for debug purposes only

empty()

template<class Space>

bool DGtal::DigitalSetByOctree< Space >::empty ( ) const

inline

Check if the octree is empty or not.

Definition at line 357 of file DigitalSetByOctree.h.

{ return size() == 0; }

end() [1/2]

template<class Space>

Iterator DGtal::DigitalSetByOctree< Space >::end ( )

inline

Returns an iterator to the end of the octree.

Definition at line 543 of file DigitalSetByOctree.h.

{ return Iterator(this); }

Referenced by DGtal::DigitalSetByOctree< Z3i::Space >::computeBoundingBox(), DGtal::DigitalSetByOctree< Z3i::Space >::operator()(), DGtal::DigitalSetByOctree< Z3i::Space >::operator+=(), and TEST_CASE_METHOD().

end() [2/2]

template<class Space>

Iterator DGtal::DigitalSetByOctree< Space >::end ( ) const

inline

Returns an iterator to the end of the octree.

Definition at line 548 of file DigitalSetByOctree.h.

{ return Iterator(this); }

erase() [1/3]

template<class Space>

size_t DGtal::DigitalSetByOctree< Space >::erase

(

const Iterator &

it

)

Remove a voxel from the octree.

This functions is undefined behavior if the Iterator is invalid.

Parameters

it	The iterator pointing to the voxel to remove

Referenced by DGtal::DigitalSetByOctree< Z3i::Space >::erase(), DGtal::DigitalSetByOctree< Z3i::Space >::erase(), and TEST_CASE_METHOD().

erase() [2/3]

template<class Space>

size_t DGtal::DigitalSetByOctree< Space >::erase ( const Point & p )

inline

Removes a voxel from the octree.

Parameters

p	The point to remove

Definition at line 414 of file DigitalSetByOctree.h.

        {
          return erase(find(p));
        }

erase() [3/3]

template<class Space>

size_t DGtal::DigitalSetByOctree< Space >::erase ( Iterator begin, Iterator end )

inline

Removes a range of voxels.

Parameters

begin	The begining of the range
end	The end of the range

Definition at line 401 of file DigitalSetByOctree.h.

        {
          size_t count = 0;
          for (; begin != end; ++begin) 
            count += erase(begin);
          return count;
        }

find()

template<class Space>

Iterator DGtal::DigitalSetByOctree< Space >::find

(

const Point &

p

)

const

Finds a point within the Octree.

Parameters

p	The point to find

Returns

An iterator to the point if possible otherwise end()

Referenced by DGtal::DigitalSetByOctree< Z3i::Space >::erase(), and DGtal::DigitalSetByOctree< Z3i::Space >::operator()().

insert()

template<class Space>

void DGtal::DigitalSetByOctree< Space >::insert

(

const Point &

p

)

Inserts a new point in the octree.

This function can be called multiple times with the same point without any risk.

If the point is not in bounds or the octree has been converted to a DAG, this function does nothing.

Parameters

p	The point to insert

Referenced by DGtal::DigitalSetByOctree< Z3i::Space >::assignFromComplement(), DGtal::DigitalSetByOctree< Z3i::Space >::insertNew(), DGtal::DigitalSetByOctree< Z3i::Space >::operator+=(), and TEST_CASE_METHOD().

insertNew()

template<class Space>

void DGtal::DigitalSetByOctree< Space >::insertNew ( const Point & p )

inline

Inserts a new point in the octree.

This function can be called multiple times with the same point without any risk.

If the point is not in bounds or the octree has been converted to a DAG, this function does nothing.

Parameters

p	The point to insert

See also

insert

Definition at line 331 of file DigitalSetByOctree.h.

{ insert(p); }

memoryFootprint()

template<class Space>

size_t DGtal::DigitalSetByOctree< Space >::memoryFootprint ( ) const

inline

Returns the memory occupied by node storage in bytes.

See also

shrink

Definition at line 364 of file DigitalSetByOctree.h.

        {
          size_t count = 0;
          for (CellIndex i = 0; i < myNodes.size(); ++i) 
            count += myNodes[i].capacity() * sizeof(Node);
          return count;
        }

operator()()

template<class Space>

bool DGtal::DigitalSetByOctree< Space >::operator() ( const Point & p ) const

inline

Check if a voxel is set or not.

Parameters

p	The point to check for

See also

find

Definition at line 339 of file DigitalSetByOctree.h.

{ return find(p) != end(); }

operator+=()

template<class Space>

DigitalSetByOctree & DGtal::DigitalSetByOctree< Space >::operator+= ( const DigitalSetByOctree< Space > & other )

inline

Appends an octree to another.

This is equivalent to looping through an octree and inserting every node into another

Parameters

other

The octree to append

Definition at line 444 of file DigitalSetByOctree.h.

        {
          if (myState == State::OCTREE) 
          {
            for (auto it = other.begin(); it != other.end(); ++it) 
              insert(*it);
          }
          return *this;
        }

shrinkToFit()

template<class Space>

void DGtal::DigitalSetByOctree< Space >::shrinkToFit ( )

inline

Shrinks storage to reduce memory usage.

This function removes extra capacity added for faster insertion with vector and can free some memory once insertion phase is over.

This function is called automatically by convertToDAG.

See also

memoryFootprint

Definition at line 430 of file DigitalSetByOctree.h.

        {
          for (CellIndex i = 0; i < myNodes.size(); ++i) 
            myNodes[i].shrink_to_fit();
        }

size()

template<class Space>

size_t DGtal::DigitalSetByOctree< Space >::size ( ) const

inline

Returns the number of voxel in the set.

Definition at line 352 of file DigitalSetByOctree.h.

{ return mySize; }

Referenced by DGtal::DigitalSetByOctree< Z3i::Space >::empty(), and TEST_CASE_METHOD().

splitDomain()

template<class Space>

Domain DGtal::DigitalSetByOctree< Space >::splitDomain ( const Domain & domain, const DimIndex * sides )

staticprivate

Helper function to split and select among 2^D subdomains.

Parameters

domain	The domain to split
sides	Selection between left or right subdomain for each dimension

Referenced by DGtal::DigitalSetByOctree< Space >::OctreeIterator::operator*().

Friends And Related Symbol Documentation

SVOReader

template<class Space>

template<class>

friend class SVOReader

friend

Definition at line 75 of file DigitalSetByOctree.h.

SVOWriter

template<class Space>

template<class>

friend class SVOWriter

friend

Definition at line 73 of file DigitalSetByOctree.h.

Field Documentation

CELL_COUNT

template<class Space>

CellIndex DGtal::DigitalSetByOctree< Space >::CELL_COUNT = (1 << D)

staticconstexpr

Definition at line 92 of file DigitalSetByOctree.h.

Referenced by DGtal::DigitalSetByOctree< Space >::Node::Node().

D

template<class Space>

DGtal::Dimension DGtal::DigitalSetByOctree< Space >::D = Space::dimension

staticconstexpr

Definition at line 89 of file DigitalSetByOctree.h.

dimension

template<class Space>

DGtal::Dimension DGtal::DigitalSetByOctree< Space >::dimension = Space::dimension

staticconstexpr

Definition at line 90 of file DigitalSetByOctree.h.

INVALID_IDX

template<class Space>

CellIndex DGtal::DigitalSetByOctree< Space >::INVALID_IDX = std::numeric_limits<CellIndex>::max()

staticconstexpr

Definition at line 93 of file DigitalSetByOctree.h.

Referenced by DGtal::DigitalSetByOctree< Space >::Node::Node().

myAdmissibleDomain

template<class Space>

CowPtr<Domain> DGtal::DigitalSetByOctree< Space >::myAdmissibleDomain

private

Definition at line 596 of file DigitalSetByOctree.h.

myDomain

template<class Space>

CowPtr<Domain> DGtal::DigitalSetByOctree< Space >::myDomain

private

Definition at line 597 of file DigitalSetByOctree.h.

myNodes

template<class Space>

std::vector<std::vector<Node> > DGtal::DigitalSetByOctree< Space >::myNodes

private

Definition at line 601 of file DigitalSetByOctree.h.

mySize

template<class Space>

size_t DGtal::DigitalSetByOctree< Space >::mySize

private

Definition at line 600 of file DigitalSetByOctree.h.

myState

template<class Space>

State DGtal::DigitalSetByOctree< Space >::myState = State::OCTREE

private

Definition at line 598 of file DigitalSetByOctree.h.

SIDES_FROM_INDEX

template<class Space>

std::array<std::array<DimIndex, D>, CELL_COUNT> DGtal::DigitalSetByOctree< Space >::SIDES_FROM_INDEX

staticconstexpr

Initial value:

= []()
        {
         std::array<std::array<DimIndex, D>, CELL_COUNT> sides_from_index{};
         for (CellIndex i = 0; i < CELL_COUNT; ++i) 
         {
           CellIndex coord = i;
           for (DimIndex d = 0; d < D; ++d) 
           {
             sides_from_index[i][d] = coord % 2;
             coord /= 2;
           }
         }
 
         return sides_from_index;
        }()

Definition at line 96 of file DigitalSetByOctree.h.

        {
         std::array<std::array<DimIndex, D>, CELL_COUNT> sides_from_index{};
         for (CellIndex i = 0; i < CELL_COUNT; ++i) 
         {
           CellIndex coord = i;
           for (DimIndex d = 0; d < D; ++d) 
           {
             sides_from_index[i][d] = coord % 2;
             coord /= 2;
           }
         }
 
         return sides_from_index;
        }();

Referenced by DGtal::DigitalSetByOctree< Space >::OctreeIterator::operator*().

---

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

• DigitalSetByOctree.h