SelectorQuadTree Class Reference

Implements the QuadTree based object selection. More...

#include <selectorQuadTree.hpp>

Inheritance diagram for SelectorQuadTree:

Classes
class	Node

Public Member Functions
	SelectorQuadTree (const std::string &name, Scene *scene)
	~SelectorQuadTree ()
void	changeMode ()
	debug, nothing More...
void	update (double deltaT)
	build up quadtree More...
void	pickObject (const glm::ivec2 &mouse)
	select closest object to mouse More...
Public Member Functions inherited from SelectorBase
	SelectorBase (const std::string &name, Scene *scene)
	~SelectorBase ()
void	reset ()
	set up EffectObject More...
void	draw () const
	draw selectable object ids into a texture More...
int	getBufferWidth () const
int	getBufferHeight () const
size_t	getLastSelected () const
size_t	getLastDistance () const
Public Member Functions inherited from SceneObject
	SceneObject (std::shared_ptr< SceneObject > &effectParent, const glm::mat4 &modelMatrix=glm::mat4(1))
	SceneObject (const std::string &name, Scene *scene=0, Model *model=0, const glm::mat4 &modelMatrix=glm::mat4(1))
virtual	~SceneObject ()
Model *	getModel () const
Shader *	getShader () const
glm::mat4	getModelMatrix () const
glm::mat4	getGlobalModelMatrix () const
std::string	getName () const
std::shared_ptr< SceneObject >	getParent () const
void	setAnimationTime (double time)
bool	setAnimation (const Animation &anim)
bool	delChild (size_t idx)
bool	getChild (size_t idx, std::shared_ptr< SceneObject > &child) const
bool	addChild (std::shared_ptr< SceneObject > &child)
bool	remEffect (const std::string &name)
SceneObject *	getEffect (const std::string &name) const
bool	addEffect (const std::string &name, std::unique_ptr< SceneObject > &effect)
bool	doNotRender ()
bool	getIsVolSun ()
virtual bool	animate (double time)
virtual void	setShader (Shader *val)

Private Attributes
int	maskBit
	2^maskbit = treeSize More...
int	treeSize
	size of tree More...
std::vector< Node >	nodes
	container to store quadtree nodes More...
std::vector< GLshort >	screen
	buffer to store the pick buffer More...

Additional Inherited Members
Public Types inherited from SceneObject
typedef std::vector< std::pair< double, glm::mat4 > >	Animation
Protected Attributes inherited from SelectorBase
int	width
	width of screen More...
int	height
	height of screen More...
GLuint	idBuffer
	frame buffer More...
GLuint	idTexture
	texture of rendered object indices More...
size_t	lastDistance
	distance after pickObject() call More...
size_t	lastSelected
	selected object id after pickObject() call More...
Protected Attributes inherited from SceneObject
GLuint	vao
Scene *	scene
Model *	model
Shader *	shader
glm::mat4	modelMatrix
std::string	name
std::weak_ptr< SceneObject >	parent
std::vector< std::shared_ptr< SceneObject > >	childs
std::map< std::string, std::unique_ptr< SceneObject > >	effectChilds
size_t	animIDX
Animation	animation
bool	norender
bool	isVolSun

Detailed Description

Implements the QuadTree based object selection.

The SelectorQuadTree class implements a quadtree based approach based on http://dl.acm.org/citation.cfm?id=1375714.1375755 . In the scene there are objects that can be selected. These objects are rendered, in screen space, into a texture, which holds the semantic information. The datatype of this texture is 16bit integer, to store the render id of the objects. After rendering with the draw() function, the quadtree is built up by the update() function. In the first step, the complete texture is copied from GPU to CPU. Then each pixel, which contains an object id, is used to build up a quadtree. The quadtree is selected to be a fix size of 2048*2048 pixels. The SelectorQuadTree::Node objects store the childs as indices of the SelectorQuadTree::nodes vector container. The tree is built up from top to bottom, where an occupied pixel will be present in the bottom level. The following pseudocode demonstrates the build up process:

//the build up process of the quadtree

for(y to screensize.y)
 for(x to screensize.x)
  id = texture[x, y]
  if(id == 0)
   continue

  //size = 2048
  shift = 10
  bitmask = 0x400
  node = root;
  do
   //decide in which child the pixel should be placed to
   //example: Assume x is 1024, then it's bitsample is 0x400.
   //         In the top level it is masked with 0x400 and the result will be 0x400,
   //         which is then shifted with 10 bits and will be 1, so the high child will be selected in the X axis.
   //         At level 9 it is masked with 0x200 and it will be zero, then the low child is selected.
   //         In this example all the lower levels will be placed in the low child.
   childX = (x & bitmask) >> shift
   childY = (y & bitmask) >> shift
   child = node.child(childX, childY)

   if child not in container
    create new child and add to nodes

   child.id = id
   child.updateBB(x, y)

   //move one level down
   node = child
   shift = shift - 1
   bitmask = bitmask >> 1
  while(bitmask != 0)

Since the scene contains only static objects, it is sufficient to build up the tree only when the camera is moved. The quadtree then enables the fast selection of these static objects using the pickObject() function. The following pseudocode demonstrates the travelsal of the quadtree:

//find closest object to mouse in quadtree

//initialization
id = 0xFFFF
minD = maxD = FLOAT_MAX
nextLevelQueue.push(ROOT)

while(!nextLevelQueue.empty())
 //prepare loop on one level
 queue = nextLevelQueue
 nextLevelQueue.clear()
 minD = maxD = FLOAT_MAX

 while(!queue.empty())
  Node = queue.pop();

  for i 1..4
   if(!node.hasChild(i))
    continue

   //get minimum and maxmimum distance between child node and mouse
   //the distance is computed from the four corner points of the bounding box
   [nodeMin nodeMax] = node.child[i].getDistance(mouse)

   //minimum distance of node is larger then smallest maximum distance of this level
   if(maxD < nodeMin)
    continue;

   //add child to next level loop
   nextLevelQueue.push(node.child[i])
   //update minimum distance
   minD = std::min(nodeMin, minD);
   //update smallest maximum distance
   maxD = std::min(nodeMax, maxD);
   //store id
   if minD is updated
    id = node.id

Author

Adam

Constructor & Destructor Documentation

SelectorQuadTree::SelectorQuadTree	(	const std::string &	name,
		Scene *	scene
	)

SelectorQuadTree::~SelectorQuadTree

(

)

Member Function Documentation

void SelectorQuadTree::changeMode ( )

virtual

debug, nothing

Implements SelectorBase.

void SelectorQuadTree::pickObject ( const glm::ivec2 &  mouse )

virtual

select closest object to mouse

Implements SelectorBase.

void SelectorQuadTree::update ( double  deltaT )

virtual

build up quadtree

Reimplemented from SelectorBase.

Member Data Documentation

int SelectorQuadTree::maskBit

private

2^maskbit = treeSize

std::vector<Node> SelectorQuadTree::nodes

private

container to store quadtree nodes

std::vector<GLshort> SelectorQuadTree::screen

private

buffer to store the pick buffer

int SelectorQuadTree::treeSize

private

size of tree

---

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

• C:/Users/FLx/Selektron/include/selectorQuadTree.hpp
• C:/Users/FLx/Selektron/src/selectorQuadTree.cpp