C S 314 Chapter Notes - Chapter 9: Hidden Surface Determination, Quadtree, Sparse Matrix
14 Dec 2016
School
Department
Course
Professor
Document Summary
Quadtrees a and b can be efficiently intersected: If a = 0 or b = 0, the result is 0. If a = 1, the result is b. If b = 1, the result is a. Otherwise, make a new interior node whose values are corresponding intersections of children of a and b. Notice that the intersection can often reuse parts of the input trees. A quadtree node can hold aggregate data about the area covered by the node: Addition, averaging, statistics: each node can aggregate the data of its children. Color: a node can average the color of its children. Updating: aggregate data can be kept up-to-date in o(log n) time. Spatial indexing: o(log n) lookup of data values by spatial position, while using less storage than an array. Numerical algorithms: spatial algorithms can be much more efficient by using lower-resolution data for interactions that are far apart. Graphics: reduce resolution except where user is looking.
