(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 |
||
| 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 == | ||
Revision as of 13:02, 15 February 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 |