Template Class C_Octree

• Defined in File Octree.hpp

Class Documentation

template<typename BaseVecT, typename BoxT, typename T_CellData>
class C_Octree

An octree implementation using techniques described in

“Simple and efficient traversal methods for quadtrees and octrees”, Sarah F. Frisken, Ronald N. Perry Journal of Graphics Tools, 7(3):1&#8212;11, 2002

memory

LocCode m_rootLevel

Root level.

size_t m_nextFreeBlock

Pointer to the next free block (garbage collection)

CellHandle m_PickedCell

The handle of the picked octree cell.

int m_NumberOfGeneratedCells

Number of octree cells generated; this counter is adjusted in the split routine only.

LocCode m_ExtractionLevel

Level of the cells to be treated as leafs during surface extraction.

std::vector<T_CellData> m_OctreeCell

Vector containing the cells.

inline void reserve(unsigned int _size)

inline void resize(unsigned int _size)

inline void initialize(int _max_octree_level)

Initializing the octree with maximal level = root level (leafs have level 0)

inline void clear()

inline int cell(int _i) const

inline void set_cell(int _i, int _cell)

inline CellHandle traverse(CellHandle _ch, LocCode _loc_x, LocCode _loc_y, LocCode _loc_z) const

inline CellHandle traverse_to_level(CellHandle _ch, LocCode _loc_x, LocCode _loc_y, LocCode _loc_z, LocCode _level) const

inline CellHandle get_common_ancestor(CellHandle _ch, LocCode _diff) const

inline CellHandle get_common_ancestor(CellHandle _ch, LocCode _diff0, LocCode _diff1) const

inline CellHandle get_common_ancestor(CellHandle _ch, LocCode _diff0, LocCode _diff1, LocCode _diff2) const

cell

inline bool is_leaf(CellHandle _ch) const

inline bool is_extraction_leaf(CellHandle _ch) const

inline bool is_root(CellHandle _ch) const

inline int level(CellHandle _ch) const

inline int depth(CellHandle _ch) const

inline bool is_inner_boundary(CellHandle _ch) const

int getChildIndex(BaseVecT center, coord<float> *point)

\param center The center of a cell in real world coordinates
\param point Point for to check it's position relative to the cell center

INDICES:

000 left down behind 001 right down behind 010 left top behind 011 right top behind 100 left down front 101 right down front 110 left top front 111 right top front

int getChildIndex(BaseVecT center, BaseVecT point)

void split(CellHandle _ch, const bool bGarbageCollectionOnTheFly = false)

Split the cell, i.e. create eight children.

The following method simply splits an octree cell and generates 8 children cells. Depending on the value of bGarbageCollectionOnTheFly EITHER (false; default value) the new cells are simply pushed back in the vector(s) OR (true) we fill the next free block with the new cells, i.e. that the pointer to the next free block “m_nextFreeBlock” must not pointer to the end of the vector(s).

Parameters:

• _parent – The cell handle of the parent cell

• bGarbageCollectionOnTheFly – true, if garbage collection should be done

inline void SetPickedCell(CellHandle _ch)

Set the cell handle of the picked cell.

inline void ResetPickedCell()

Reset the cell handle of the picked cell.

inline bool PickParentCell()

Pick the parent cell of the currently picked cell.

inline bool PickChildCell(int _idx)

Pick the child cell of the currently picked cell.

inline void ResetNumberOfGeneratedCells()

Reset the number of generated cells.

inline LocCode SetExtractionLevel(LocCode _level)

Set the level to be treated as leaf level.

iterators

inline CellHandle root() const

inline CellHandle end() const

navigation

inline CellHandle parent(CellHandle _ch) const

inline CellHandle child(CellHandle _ch, int _idx) const

inline CellHandle face_neighbor(CellHandle _ch, int _idx) const

inline CellHandle edge_neighbor(CellHandle _ch, int _idx) const

inline std::pair<std::vector<CellHandle>, std::vector<uint>> all_corner_neighbors(CellHandle _ch, int _idx) const

inline CellHandle corner_neighbor(CellHandle _ch, int _idx) const

void MovePickedCell(int _key, double *_mvm)

Moving the picked cell, i.e. picking one of the neighbouring cells (if possible)

The rows of the current modelview matrix correspond to the camera axes in the world space. We use here the maximal components of the x- and y-axis as “guides” in which direction to move in the octree. This approach works only because the octree cells are world-axis-aligned!

Parameters:

• _direction – Direction of the movement

• _mvm – The current modelview matrix needed for estimating the plane of movement

void MovePickedCellLeft(double *_mvm)

void MovePickedCellRight(double *_mvm)

void MovePickedCellUp(double *_mvm)

void MovePickedCellDown(double *_mvm)

query

inline int size() const

inline int nr_cells() const

inline BaseVecT cell_corner(CellHandle _ch, int _idx) const

inline void cell_corner(CellHandle _ch, Scalar &_x, Scalar &_y, Scalar &_z, Scalar &_size) const

inline void cell_corner(CellHandle _ch, int _idx, Scalar &_x, Scalar &_y, Scalar &_z) const

inline void cell_corner(CellHandle _ch, int _idx, Scalar &_x, Scalar &_y, Scalar &_z, Scalar &_size) const

inline BaseVecT cell_center(CellHandle _ch) const

inline void cell_center(CellHandle _ch, Scalar &_x, Scalar &_y, Scalar &_z) const

inline void cell_center(CellHandle _ch, Scalar &_x, Scalar &_y, Scalar &_z, Scalar &_size) const

inline Scalar cell_size(CellHandle _ch) const

inline Location &location(CellHandle _h)

inline const Location &location(CellHandle _h) const

inline CellHandle cell(Scalar _x, Scalar _y, Scalar _z) const

inline CellHandle GetPickedCell() const

Get the handle of the picked cell.

inline int GetNumberOfGeneratedCells() const

Get number of generated cells.

inline LocCode GetExtractionLevel() const

Get the level to be treated as leaf level.

inline C_Octree<BaseVecT, BoxT, T_CellData> *copy()

Public Types

typedef Location::LocCode LocCode

typedef float Scalar

Public Functions

inline C_Octree()

inline ~C_Octree()

Public Static Attributes

static const int MAX_ROOT_LEVEL = sizeof(LocCode) * 8 - 1

Maximal root level defined by size of data type of the cell coordinates (leafs have side length 1)