(3-Dimensional, i.e. project onto a 2D plane) (Shown Surface Determination)

Description

This is the process of identifying what surfaces and parts of surfaces can be seen from a particular viewing angle. Given a set of obstacles in the Euclidean space, two points in the space are said to be visible to each other, if the line segment that joins them does not intersect any obstacles.

Parameters

$n$: number of polygons

$p$: number of pixels in viewport

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Painter's algorithm/Newell's algorithm	1972	$O(n*log(n)$+np)	$O(p+n)$	Exact	Deterministic	Time
Warnock's algorithm	1969	$O(np)$	$O(p+n)$?	Exact	Deterministic	Time
Ray tracing	1982	$O(np)$	$O(p+n)$?	Exact	Deterministic
Binary space partitioning (BSP)	1969	$O(n^{2}+p)$? (previously said $O(n^{2}logn)$	$O(n^{2}+p)$?	Exact	Deterministic	Time
Z-buffering	1974	$O(np)$	$O(p+n)$	Exact	Deterministic	Time & Space
S-buffer/Scanline Rendering	1980	$O(E+p)$?	$O(p+n)$?	Exact	Deterministic