(3-Dimensional, i.e. project onto a 2D plane): Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:(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 == <pre>n: number of polygons p: number of pixel...") |
No edit summary |
||
(One intermediate revision by the same user not shown) | |||
Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
$n$: number of polygons | |||
p: number of pixels in viewport | |||
$p$: number of pixels in viewport | |||
== Table of Algorithms == | == Table of Algorithms == |
Latest revision as of 08:52, 10 April 2023
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 |