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

From Algorithm Wiki
Revision as of 07:52, 10 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


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.


$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