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

Jump to navigation
Jump to search

## 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 |