Use in Computer Graphics
Space partitioning is heavily used in ray tracing. A typical scene may contain millions of polygons. Performing a ray/polygon intersection test with each would be a very computationally expensive task. The use of a proper space partitioning data structure (kd-tree or BVH for example) can reduce the number of intersection test to just a few per primary ray, yielding a logarithmic time complexity with respect to the number of polygons.
Space partitioning is also often used in scanline algorithms to eliminate the polygons out of the camera's viewing frustum, limiting the number of polygons processed by the pipeline.
Read more about this topic: Space Partitioning
Famous quotes containing the word computer:
“The computer takes up where psychoanalysis left off. It takes the ideas of a decentered self and makes it more concrete by modeling mind as a multiprocessing machine.”
—Sherry Turkle (b. 1948)