Visibility ComputationsVisible Surface DeterminationSlide 3Use of SortingObject Space AlgorithmsImage Space AlgorithmsVisibility: Too Bloody Difficult [Whitted’93]Secondary Visibility [Whitted’93]Visibility Partitioning Preprocess [Whitted’93]Cookie Cutter AlgorithmsArea Visibility or Global VisibilityVisibility Culling01/26/09 Dinesh Manocha, 770Visibility Computations•Visible Surface Determination•Global Visibility Computations•Visibility CullingDinesh Manocha, COMP236Visible Surface DeterminationGiven a set of 3D objects and a viewing specification, determine the lines or surfaces of the object that are visible•Hidder-line or hidden-surface elimination•Visible-line or visible-surface determinationDinesh Manocha, COMP236Visible Surface DeterminationNo best solution•Fast algorithms for interactive computer graphics •Detailed realistic solutions: shadows, transparency and texture effects•Computer animation: reflections and refractions Trade-off between speed and detailDinesh Manocha, COMP236Use of SortingAll visible surface algorithms involve sorting [Sutherland et al.74]•Sort based on the geometric distance of a volume, edge or surface from the viewpoint•Use of coherence to improve its efficiency: the tendency for the characteristics of a scene to be locally constant.Dinesh Manocha, COMP236Object Space AlgorithmsImplemented in the physical coordinate system in which the objects are describedfor each object in the world dobegindetermine those parts of the object whose view is unobstructed by other parts of it or any or any other object;draw those parts in the appropriate colorendDinesh Manocha, COMP236Image Space AlgorithmsImplemented in the screen coordinate system in which the objects are viewedfor each pixel in the image dobegindetermine the object closest to the viewer that is pierced by the projector through the pixel;draw the pixel in the appropriate colorendDinesh Manocha, COMP236Visibility: Too Bloody Difficult [Whitted’93]A difference classification of visibility•Back-end accumulator (e.g. Z-buffer)•Middle-end accumulator (scan-line conversion)•Front-end accumulator (e.g. ray tracing)Dinesh Manocha, COMP236Secondary Visibility [Whitted’93] •Shadows•Environment Mapping•Ray Tracing•RadiosityDinesh Manocha, COMP236Visibility Partitioning Preprocess [Whitted’93] •Is a very expensive process•Only limited to static scenes–Things have changed with faster hardwareDinesh Manocha, COMP236Cookie Cutter AlgorithmsGeneral object space approaches that involve geometric partitioning•Sutherland 1971-72•Weiler/Atherton 1977•Abram 1986Dinesh Manocha, COMP236Area Visibility or Global VisibilityVisibility from a region or space•Cohen et al. 1986•Teller et al. 1991, 93•Heckbert 199101/26/09 Dinesh Manocha, 770Visibility CullingEliminate a subset of the model not visible from the current viewpoint•View-frustum culling•Backface culling•Occlusion