Week 10 - Spatial Enumeration Flashcards
What do Spatial Enumeration / Spatial partitioning techniques intend to do?
Organise space so that the kinds of calculations used mostly commonly in graphics can be done more quickly
(not low level vector / matrix calculations, those are done fast in hardware by the GPU nowadays, talking more about high level datastructures)
What are the costs and gains of indexing a table?
Using more memory, lookup / sorted ordering is faster
Have to update the pointers when the table is updated
What common queries might we ask a graphical scene?
Does a given point in space, intersect with any of the objects in the scene.
Raycasting, trace part of a path, raytree, marching through a volume. Find the closest object we clicked on / shot with an object.
Finding which objects are to one side or the other of a plane (essentially an extension to the other ones)
Given a linked list structure pointing to all the objects in the scene, how much time will it take to find the objects a point is in given n objects in the scene?
O(n)
List the methods of spatial enumeration
Gridcell
Octree / Adapted Gridcell (focusing on populated cells with an Octree)
Hierarchical bounding volume
Binary space partitioning
Explain the gridcell method
Store the scene in voxels, index into the array to find what objects are at a given position - this is O(1) - memory usage is worse at O(n^3) for each cell in the scene.
Can reduce the memory usage / space complexity by using fewer bigger cells (voxels) to fill the space, but that has implications.
Need to update pointers as the objects in the scene are updated, moving, being created or deleted
How can we adapt the gridcell method to use less memory?
Start with one big cube, recursively split that into smaller cubes, but only where we need to.
Decide a threshold for the maximum number of objects in a square (e.g. 2 objects)
We start with one big cube, and (if there are more objects than the threshold) split it into 8 smaller cubes of equal size, we keep doing this for all of the cubes that contain more objects than the threshold amount, until that is not longer true for any of them.
Every leaf node in the octree points to the objects that are contained within it, every other node points to it’s 8 children.
This does increase the time complexity though, to find an object at a point in space I need to find out which of the nodes in the tree structure represents the point in the tree I am interested in, I won’t know how far down the tree to go until I get there.
Saving significant amount of memory with this, assuming the space isn’t crammed with objects / we have a lot of empty space
What makes a spatial enumeration method “regular”?
They split space into regular, equal sized, chunks.
(With Octree, all the cells at any given level are the same size, so it is also regular)
What is spatial cohesion?
The idea that often things clump together in space in the real world. This is the thing that makes the OcTree more spatially efficient than the gricell. Most scenes consist of clumps of things separated by empty space.
But, it’s not evenly spread over evenly sized cubes.
Hierarchical Bounding Volumes
HBVs start with objects and wrap those in increasingly bigger spaces (bounding boxes) until you’ve covered the whole scene. (bounding boxes containing bounding boxes, using a hierarchical tree that improves memory space due to spatial cohesion)
What is a bounding volume?
A simple shape that encapsulates a a more complicated one. The point being that if you do an intersection test with a more simple shape and get a negative result, then you can be certain it’s not worth doing the intersection test with any of the more complicated expensive things inside that bounding shape.
If we get a positive hit on the bound, we then need to do a more complicated test on the inner structure
What is the simplest bounding shape to represent with an equation?
A sphere
What is binary space paritioning?
It partitions space into two sections, recursively (in 3D uses a plane instead of a line)
Keep dividing (alternating vertically, the horizontally for axis-aligned binary space partitioning) until there is no more than a predetermined number of objects (threshold) in each space.
