SPATIAL ENUMERATION

Question 1

What is spatial enumeration used for

Answer 1

used to partition space so that common computer calculations can be done more quickly

in higher level data structures - lower level is done in the hardware already

Question 2

What is a gridcell

Answer 2

What we use to store data in volume rendering
value = voxel[x][y][z]

Question 3

Using gridcell for spatial enumeration

Answer 3

If we have objects in space, we can use a gridcell to divide up these objects
We can get value at a pixel with a single lookup O(1)
Storage wise, this is bad, takes up n^3 cells

Question 4

What is an octree

Answer 4

Start with one big cube covering our space
-recursively split this down into smaller cubes but only where there are more objects that exist in that quadrant

We decide of a maximum threshold for objects in a square
Eg, where there are >2 objects in a cell, split it further
the data structure adapts to the objects in the space

Question 5

complexity of octrees

Answer 5

we have created a hierarchical tree structure for searching
We will not know how far we will have to traverse the tree until we get there - although we do know there is a maximum of 2 branches in this case

But Assuming we have a lot of empty spaces, we are saving a lot of memory by using an octree

well-balanced binary tree - O(logn)
worst case, unbalanced binary - O(n)