IRREGULAR SPATIAL ENUMERATION

Question 1

What is Spatial cohesion

Answer 1

the idea that things often clump together in the real world
Thus
This effect makes the octree more effective than the gridcell
The octree cannot however take into account that things are not spread evenly

Question 2

What are Hierarchical Bounding Volumes

Answer 2

Start with objects and wrap them increasingly bigger spaces - like the opposite of octrees
idea is that we use a simple shape to encapsulate a more complex one
- if we miss the bounding shape we cannot have hit the object within
However we may get a false positive hitting the bounding shape but not the object

Question 3

Cons of hierarchical bounding volumes

Answer 3

The actual shape is not the same as the bounding shape
higher chance of false positive
lot of empty space inside the bounding shape

Question 4

Bounding boxes as a hierarchical tree

Answer 4

Given a scene
We can place each object in a bounding box
Then the close bounding boxes in larger bounding boxes until eventually the whole scene has a big bounding box
This means we can send a ray and know if it has not even hit the scene
If it has we have a hierarchical tree to test which object (box) it is hitting

Question 5

What is binary space partitioning

Answer 5

Splits space into 2
starts with a horizontal separation
we can build a binary tree along with the recursive separations
Each ‘split in 2’ does not necessarily result in equal halves, the line will split to try and separate objects (but not always)

Question 6

Axis aligned binary partitioning

Answer 6

a simple type of Binary partitioning where the world axis is used to split the spaces in two (perpendicular lines)
The advantage of this approach is that it preserves the relative positions of objects in different regions (Eg left and right) so by traversing the tree we can find an objects relative position

Question 7

What is the space and time complexity for grid based enumeration

Answer 7

space: O(N)
time: O(1)

Question 8

What is the space and time complexity for quadtree enumeration

Answer 8

space: O(N)
time: O(N) or O(N+K)

Question 9

What is the space and time complexity for octree enumeration

Answer 9

space: O(N)
time: O(N) for unbalanced

Question 10

What is the space and time complexity for binary space partitioning (BSP) enumeration

Answer 10

space: O(N)
time: O(log N) or O(N) for unbalances