(3-Dimensional, i.e. project onto a 2D plane) (Shown Surface Determination)
Revision as of 10:21, 15 February 2023 by Admin (talk | contribs) (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...")
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 |