CS 426 Exercises
  Solids

  1. What is a voxel grid? Give a simple example.
  2. What is the storage requirements for a uniform voxel grid with 512 voxels on each side of the cube and 24 bits of data in each voxel?
  3. What is the computational complexity of tracing a ray through a voxel grid with N^3 voxels: a) O(1), b) O(logN), c) O(N), d) O(NlogN), e) O(N^2), f) O(N^3).
  4. Which of the following are true for voxels: a) fast iso-surface rendering, b) easy to test intersections, c) hard to describe complex shapes, d) affine invariant?
  5. What is a quadtree? an octree? Give a simple example. What is an advantage of such a representation compared to uniform voxels? a disadvantage?
  6. What is the computational complexity of tracing a ray through an octree with at most N^3 cells: a) O(1), b) O(logN), c) O(N), d) O(NlogN), e) O(N^2), f) O(N^3). Is the expected complexity less? Under what conditions?
  7. What is a binary space partition (BSP)? Give a simple example. What is an advantage of such a representation compared to an octree? a disadvantage?
  8. Which of the following are true for a BSP: a) all leaf cells are convex, b) finding which cell contains a point takes expected-case O(logN) time using a BSP with N leaf cells, c) the largest number of cells possibly resulting from a BSP constructed by N splits has O(N) leaf cells.
  9. Describe the visibility ordering algorithm used when drawing BSPs. Explain why it is guaranteed to produce a front-to-back (or back-to-front) ordering.
  10. What is the computational complexity of tracing a ray through a balacned BSP with N leaf cells: a) O(1), b) O(logN), c) O(N), d) O(NlogN), e) O(N^2), f) O(N^3). Is the expected complexity less? Under what conditions?
  11. What is constructive solid geometry? Give a simple example. What is an advantage of such a representation compared to other solid representations? a disadvantage? <\li>
  12. Draw a CSG tree for a coffee cup. <\li>
  13. Give an algorithm to draw an image of the surface of a CSG object. <\li>
  14. For each of the following properties, list the solid representations (voxels, octrees, BSPs, CGS) that provide it best and worst: a) high accuracy, b) conciseness, c) guaranteed validity, d) efficient boolean operations, e) efficient display.