gsHDomain< d, Z > Class Template Reference

Detailed Description

template<short_t d, class Z = index_t>
class gismo::gsHDomain< d, Z >

Class with a hierarchical domain structure represented by a box k-d-tree.

The hierarchical domain structure represets a sequence of domains \(\Omega^\ell \subset \Omega\) which are nested in the sense that

\[ \Omega = \Omega^0 \supset \Omega^1 \supset \Omega^2 \supset \ldots \supset \Omega^N \supset \Omega^{N+1} = \emptyset \]

Each subdomain \(\Omega^\ell\) is a (not necessarily connected) collection of axis-aligned elements/cells.

Remarks

In the context of HB-splines and THB-splines, these elements/cells are the knot spans of the tensor-product mesh at the respective level.

The information on the hierarchical domains is stored in a k-d-tree, where each leaf represents an axis-aligned box \(\omega \subseteq \Omega\), such that \(\omega \subseteq \Omega^\ell \land \omega \cap \Omega^{\ell+1} = \emptyset\) (i.e., each leaf of the tree can be assiciated with exactly one level of the hierarchy).

The implementation is, up to some technical differences, based on the technique described in the following publication

• G. Kiss, C. Giannelli, and B. Juettler. Algorithms and data structures for truncated hierarchical B-splines. In M. Floater et al., editors, Mathematical Methods for Curves and Surfaces, volume 8177, pages 304-323. Lecture Notes in Computer Science, 2014.

also available as a technical report

• G. Kiss, C. Giannelli, and B. Juettler. Algorithms and Data Structures for Truncated Hierarchical B-splines DK-Report No. 2012-14, Doctoral Program Computational Mathematics: Numerical Anaylsis and Symbolic Computation, 2012.

Regarding the mentioned technical differences: A binary tree is used instead of a quad-tree (which was discussed in the above-mentioned publications). Also, the domains are not necessarily split at their middle, but according to the position of the domain of the next level.

Template parameters

Parameters

d	is the dimension
Z	is the box-index type

Collaboration diagram for gsHDomain< d, Z >:

Classes
struct	get_cell_visitor
	Returns an cell/element box of a requested level. More...
struct	levelDown_visitor
	Decreases the level by 1 for all leaves. More...
struct	levelUp_visitor
	Increases the level by 1 for all leaves. More...
struct	liftCoordsOneLevel_visitor
	Multiplies everything by 2. More...
struct	maxLevel_visitor
	Decreases the level by 1 for all leaves. More...
struct	numLeaves_visitor
	Counts number of nodes in the tree. More...
struct	numNodes_visitor
	Counts number of nodes in the tree. More...
struct	printLeaves_visitor
	Counts number of nodes in the tree. More...
struct	reduceCoordsOneLevel_visitor
	Multiplies everything by 2. More...

Public Member Functions
void	clearBox (point const &lower, point const &upper, int lvl)
	The clear function which clears box defined by points lower and upper to level lvl. More...
gsHDomain *	clone () const
	Clones the object.
void	decrementLevel ()
	Decrement the level index globally.
void	divideByTwo ()
	Divide all coordinates by two.
void	getBoxes (gsMatrix< Z > &b1, gsMatrix< Z > &b2, gsVector< Z > &level) const
	Returns the boxes which make up the hierarchical domain and the respective levels. More...
void	getBoxesInLevelIndex (gsMatrix< Z > &b1, gsMatrix< Z > &b2, gsVector< index_t > &level) const
void	getBoxesOnSide (boundary::side s, gsMatrix< Z > &b1, gsMatrix< Z > &b2, gsVector< Z > &level) const
	Returns the boxes which make up the hierarchical domain and the respective levels touching side s. More...
std::vector< std::vector < std::vector< std::vector< Z > > > >	getPolylines () const
	gsHDomain (const gsHDomain &o)
	Copy constructor (makes a deep copy)
void	incrementLevel ()
	Increment the level index globally.
void	init (point const &upp, unsigned index_level)
	Initialize the tree.
void	init (point const &upp)
	Initialize the tree with computing the index_level.
void	insertBox (point const &lower, point const &upper, node *_node, int lvl)
	The insert function which insert box defined by points lower and upper to level lvl. More...
void	insertBox (point const &lower, point const &upper, int lvl)
	The insert function which insert box defined by points lower and upper to level lvl. More...
void	internalIndex (point const &point_idx, int lvl, point &internal_idx)
	Returns the internal coordinates of point point_idx of level lvl.
int	leafSize () const
	Returns the number of leaves in the tree.
int	levelOf (point const &p, int level) const
	Returns the level of the point p.
std::pair< int, int >	minMaxPath () const
	Returns the minimim and maximum path length in the tree.
void	multiplyByTwo ()
	Multiply all coordinates by two.
int	numBreaks (int lvl, int k) const
	Returns the number of distinct knots in direction k of level lvl.
gsHDomain &	operator= (const gsHDomain &o)
	Assignment operator (makes a deep copy)
void	printLeaves () const
	Prints out the leaves of the kd-tree.
bool	query1 (point const &lower, point const &upper, int level, node *_node) const
	Returns true if the box defined by lower and upper is completely contained in level and does not overlap with any higher level. More...
bool	query1 (point const &lower, point const &upper, int level) const
	Returns true if the box defined by lower and upper is completely contained in level and does not overlap with any higher level. More...
bool	query2 (point const &lower, point const &upper, int level, node *_node) const
	Returns true if the box defined by lower and upper is contained in a domain with a higher level than level. More...
bool	query2 (point const &lower, point const &upper, int level) const
	Returns true if the box defined by lower and upper is completely contained in a Om-domain with a level different to level. More...
int	query3 (point const &k1, point const &k2, int level, node *_node) const
int	query3 (point const &lower, point const &upper, int level) const
	Returns the lowest level \(\ell\) s.t. \(\omega \subseteq \Omega^\ell \land \omega \cap \Omega^{\ell+1} = \emptyset \). More...
int	query4 (point const &lower, point const &upper, int level, node *_node) const
int	query4 (point const &lower, point const &upper, int level) const
	Returns the highest level with which the box defined by lower and upper overlaps. More...
void	sinkBox (point const &lower, point const &upper, int lvl)
	Sinks the box defined by points lower and upper to one level higher. More...
int	size () const
	Returns the number of nodes in the tree.
const point &	upperCorner () const
	Accessor for gsHDomain::m_upperIndex.
const point	upperCornerIndex () const
	Return the upper corner of the tree in level 0.
	~gsHDomain ()
	Destructor deletes the whole tree.

Private Member Functions
template<typename visitor >
visitor::return_type	boxSearch (point const &k1, point const &k2, int level, node *_node) const
void	connect_Boxes (std::vector< std::vector< Z > > &boxes) const
	connect the boxes returned from quadtree getBoxes_vec() More...
void	getBoxes_vec (std::vector< std::vector< Z >> &boxes) const
	Represents boxes of the tree in a big vector. More...
void	getRidOfOverlaps (std::list< std::list< gsVSegment< Z > > > &vert_seg_lists) const
template<typename visitor >
visitor::return_type	leafSearch () const
template<typename visitor >
visitor::return_type	nodeSearch () const
node *	pointSearch (const point &p, int level, node *_node) const
void	setIndexLevel (int) const
	Adds nlevels new index levels in the tree.
void	sweeplineConnectAndMerge (std::vector< std::vector< std::vector< Z > > > &result, std::list< std::list< gsVSegment< Z > > > &vert_seg_lists) const
	Sweepline algorithm.

Static Private Member Functions
static bool	haveOverlap (box const &box1, box const &box2)
static bool	isContained (box const &box1, box const &box2)
	Returns true if box1 is contained in box2.
static bool	isDegenerate (box const &someBox)
	Returns true if the box is degenerate (has zero volume)
static std::pair< point, point >	select_part (point const &k1, point const &k2, point const &k3, point const &k4)
static void	setLevel (node *_node, int lvl)

Private Attributes
EIGEN_MAKE_ALIGNED_OPERATOR_NEW unsigned	m_indexLevel
	The level of the box representation (global indices)
unsigned	m_maxInsLevel
	Maximum level present in the tree.
node *	m_root
	Pointer to the root node of the tree.
point	m_upperIndex
	Keeps the highest upper indices (at level gsHDomain::m_indexLevel)

Member Function Documentation

visitor::return_type boxSearch ( point const &  k1, point const &  k2, int  level, node *  _node  ) const

private

Iterates on the leafs of the tree and applies \ visitor. The visitor controls the return type and the update of the result type at every leaf node

void clearBox	(	point const &	lower,
		point const &	upper,
		int	lvl
	)

The clear function which clears box defined by points lower and upper to level lvl.

[lower, upper] are given by unique knot indices of level lvl.

Parameters

lower	the lower left corner of the box given in lvl representation
upper	the upper right corner of the box given in lvl representation
lvl	the desired level

void connect_Boxes ( std::vector< std::vector< Z > > &  boxes ) const

private

connect the boxes returned from quadtree getBoxes_vec()

If two neighbouring boxes could be represented by a single box (i.e., if the union of two axis-aligned boxes is again an axis-aligned box), then these two are merged into a single box.

Parameters

[in,out]

boxes

Format as of getBoxes_vec(), i.e., each box is represented as vector of size 2*d + 1 containing [ [lower corner],[upper corner], Level ], where the corners are defined by the knot indices on level gsHDomain::m_maxInsLevel.

void getBoxes	(	gsMatrix< Z > &	b1,
		gsMatrix< Z > &	b2,
		gsVector< Z > &	level
	)		const

Returns the boxes which make up the hierarchical domain and the respective levels.

Returns a list of boxes defined by left-bottom (b1) and right-top (b2) corners for the splitting in B-spline patches together with the corresponding levelOf()

The boxes b1 and b2 are given as matrices of size n x d, where d is the dimension of the domain, and where n is the number of boxes of the gsHDomain.
The numbers in b1 and b2 are given as unique knot indices of gsHDomain::m_maxInsLevel

Parameters

[out]	b1	n x d-matrix, left bottom corners of boxes
[out]	b2	n x d-matrix, right upper corners of boxes
[out]	level	vector of length n, corresponding levels

void getBoxes_vec ( std::vector< std::vector< Z >> &  boxes ) const

private

Represents boxes of the tree in a big vector.

Parameters

[out]

boxes

Each item corresponds to a box and is represented by a vector of unsigned ints. First the coordinates of the lower left, then the coordinates of the upper right corner, and then the level of this box (i.e., for each i, the size of boxes[i] is 2d+1, where d is the dimension of the domain). All indexing is in terms of level gsHDomain::m_maxInsLevel.

void getBoxesInLevelIndex	(	gsMatrix< Z > &	b1,
		gsMatrix< Z > &	b2,
		gsVector< index_t > &	level
	)		const

Returns a list of boxes defined by left-bottom (b1) and right-top (b2) corners for the splitting in B-spline patches together with the corresponding levelOf b1 and b2 are indexing in the corresponding level indices

Parameters

b1	left bottom corners of boxes
b2	right upper corners of boxs
level	corresponding levels

void getBoxesOnSide	(	boundary::side	s,
		gsMatrix< Z > &	b1,
		gsMatrix< Z > &	b2,
		gsVector< Z > &	level
	)		const

Returns the boxes which make up the hierarchical domain and the respective levels touching side s.

Similar to getBoxes() with additional input of the side s. Returns only those boxes which touch the side s of the domain.

Parameters

[in]	s	Side (as in boundary::side) specifying the side of the domain
[out]	b1	n x d-matrix, left bottom corners of boxes
[out]	b2	n x d-matrix, right upper corners of boxes
[out]	level	vector of length n, corresponding levels

std::vector< std::vector< std::vector< std::vector< Z > > > > getPolylines

(

)

const

return a list of polylines- boundaries of each connected component for all levels in the parameter space

void getRidOfOverlaps ( std::list< std::list< gsVSegment< Z > > > &  vert_seg_lists ) const

private

For each x-coordinate delete repeated parts of vertical segments. vert_seg_lists list, where for each x coordinate (sorted increasingly) a list of vertical segments with that coordinate is saved.

bool haveOverlap ( box const &  box1, box const &  box2  )

inlinestaticprivate

Returns true if the boxes overlap

Parameters

box1
box2

Returns

true if the boxes overlap

void insertBox	(	point const &	lower,
		point const &	upper,
		node *	_node,
		int	lvl
	)

The insert function which insert box defined by points lower and upper to level lvl.

[lower, upper] are given by unique knot indices of level lvl

Parameters

lower	the lower left corner of the box
upper	the upper right corner of the box
*_node	the current node
lvl	the desired level

Remarks

This function should only be called by the other query1(). It will return an incorrect result, if the box corresponds to a leaf which is in a branch of the tree that cannot be reached from _node.

void insertBox ( point const &  lower, point const &  upper, int  lvl  )

inline

The insert function which insert box defined by points lower and upper to level lvl.

[lower, upper] are given by unique knot indices of level lvl.

Parameters

lower	the lower left corner of the box given in lvl representation
upper	the upper right corner of the box given in lvl representation
lvl	the desired level

visitor::return_type leafSearch ( ) const

private

Iterates on the leafs of the tree and applies \ visitor. The visitor controls the operation to be performed

visitor::return_type nodeSearch ( ) const

private

Iterates on all the nodes of the tree and applies \ visitor. The visitor controls the operation to be performed

gsHDomain< d, Z >::node * pointSearch ( const point &  p, int  level, node *  _node  ) const

private

Returns the leaf node of the subtree starting at _node that contains the input point p. The cells in the tree are considered half-open, i.e. in 2D they are of the form [a_1,b_1) x [a_2,b_2)

bool query1	(	point const &	lower,
		point const &	upper,
		int	level,
		node *	_node
	)		const

Returns true if the box defined by lower and upper is completely contained in level and does not overlap with any higher level.

This query is called by the other query1() (the one without _node as input parameter) and starts checking at node _node of the k-d-tree.

Parameters

lower	the lower left corner of the box
upper	the upper right corner of the box
level	the level to be checked against
_node	node of the k-d-tree where the search starts.

Remarks

This function should only be called by the other query1(). It will return an incorrect result, if the box corresponds to a leaf which is in a branch of the tree that cannot be reached from _node.

bool query1	(	point const &	lower,
		point const &	upper,
		int	level
	)		const

Returns true if the box defined by lower and upper is completely contained in level and does not overlap with any higher level.

More mathematically, returns true, if \(\omega \subseteq \Omega^{\mathsf{level}} \land \omega \cap \Omega^{\mathsf{level}+1} = \emptyset \), where \(\omega\) is the box defined by lower and upper.

Todo:

Specify input format of lower and upper.

Example: in two dimensons, let
\(\Omega^4 = (0.1,0.9)\times(0.2,0.7)\),
\(\Omega^5 = (0.4,0.8)\times(0.3,0.6) \subset \Omega^4\),
\(\Omega^6 = \emptyset \subset \Omega^5\).

Testing the box \( (0.1,0.4)\times(0.3,0.5)\), contained in \(\Omega^4 \setminus \Omega^5\), returns:
query1( [0.1,0.4], [0.3,0.5], 4 ) = true
query1( [0.1,0.4], [0.3,0.5], 5 ) = false

Testing the box \( (0.3,0.5)\times(0.4,0.5)\), partly overlapping \(\Omega^5\), returns:
query1( [0.3,0.4], [0.5,0.5], 4 ) = false
query1( [0.3,0.4], [0.5,0.5], 5 ) = false

Testing the box \( (0.6,0.8)\times(0.4,0.5) \subset \Omega^5\) returns:
query1( [0.6,0.4], [0.8,0.5], 4 ) = false
query1( [0.6,0.4], [0.8,0.5], 5 ) = true

Parameters

lower	the lower left corner of the box
upper	the upper right corner of the box
level	the level to be checked against

Returns

True, if \(\omega \subseteq \Omega^{\mathsf{level}} \land \omega \cap \Omega^{\mathsf{level}+1} = \emptyset \), where \(\omega\) is the box defined by lower and upper.

bool query2	(	point const &	lower,
		point const &	upper,
		int	level,
		node *	_node
	)		const

Returns true if the box defined by lower and upper is contained in a domain with a higher level than level.

Parameters

lower	lower left corner of the cube [k1,k2]
upper	upper right corner of the cube [k1,k2]
level	current level
_node	node of the k-d-tree where the search starts.

Remarks

This function should only be called by the other query2(). It will return an incorrect result, if the box corresponds to a leaf which is in a branch of the tree that cannot be reached from _node.

bool query2	(	point const &	lower,
		point const &	upper,
		int	level
	)		const

Returns true if the box defined by lower and upper is completely contained in a Om-domain with a level different to level.

Parameters

lower	the lower left corner of the box
upper	the upper right corner of the box
level	the level \( \ell_0 \) to be checked against

Returns

True, if there exists a level \(\ell \neq \ell_0 \), such that \(\omega \subseteq \Omega^\ell \land \omega \cap \Omega^{\ell+1} = \emptyset\), where \(\omega\) is the box defined by lower and upper.

int query3	(	point const &	k1,
		point const &	k2,
		int	level,
		node *	_node
	)		const

query3 is used if both query1 and query2 are false to decide if the coresponding basis function is active or not. it returns the smallest level in which [k1,k2] is completely contained and not completely overlaped by higher omega structure. The idea is the same as in case of query1 and query2 but instead of returning a true or false value we remember the lowest level, which is returned at the end.

int query3	(	point const &	lower,
		point const &	upper,
		int	level
	)		const

Returns the lowest level \(\ell\) s.t. \(\omega \subseteq \Omega^\ell \land \omega \cap \Omega^{\ell+1} = \emptyset \).

...where \(\omega\) is the box defined by lower and upper.

Parameters

lower	the lower left corner of the box
upper	the upper right corner of the box
level	specifies which level lower and upper refer to.

int query4	(	point const &	lower,
		point const &	upper,
		int	level,
		node *	_node
	)		const

query4 returns the highest level with which box [k1, k2] overlaps

int query4	(	point const &	lower,
		point const &	upper,
		int	level
	)		const

Returns the highest level with which the box defined by lower and upper overlaps.

Parameters

lower	the lower left corner of the box
upper	the upper right corner of the box
level	specifies which level lower and upper refer to.

std::pair< typename gsHDomain< d, Z >::point, typename gsHDomain< d, Z >::point > select_part ( point const &  k1, point const &  k2, point const &  k3, point const &  k4  )

staticprivate

Returns two point- upper left and lower right corner of the overlaping part of [k1,k2] and [k3,k4]

Parameters

k1	the lower left corner of the first box
k2	the upper right corner of the first box
k3	the lower left corner of the second box
k4	the upper right corner of the second box

void setLevel ( node *  _node, int  lvl  )

staticprivate

Sets the level of all descendents of the node _node to level lvl if the level of the node is smaller then lvl. Otherwise the level of node is not changed

Parameters

*_node	the node whose descendents are to be set their levels
lvl	the new level for the descendents

void sinkBox	(	point const &	lower,
		point const &	upper,
		int	lvl
	)

Sinks the box defined by points lower and upper to one level higher.

[lower, upper] are given by unique knot indices of level lvl.

Parameters

lower	the lower left corner of the box
upper	the upper right corner of the box
lvl	the level in which lower and upper are defined