The paper gives some examples of how techniques from Computational Geometry can be applied to Computer Graphics. The authors concentrate on the windowing problem: given a large picture, built out of nonintersecting line segments, compute that part of the picture visible in a axis-parallel rectangle. The authors show how to store the picture in a kind of two-dimensional data structure such that for each given window, they can efficiently determine what part of the picture is visible in the window. This is particularly useful when the pictures are large (compared to the size of the window) and do not change often. The paper is organized as follows. First the authors recall some known results from computational geometry. Next they apply these to the windowing. In the final section they give some extensions.
展开▼