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:
“What, then, is the basic difference between today’s computer and an intelligent being? It is that the computer can be made to see but not to perceive. What matters here is not that the computer is without consciousness but that thus far it is incapable of the spontaneous grasp of pattern—a capacity essential to perception and intelligence.”
—Rudolf Arnheim (b. 1904)