# MPI-I-92-102

## Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

### Lenhof, Hans-Peter and Smid, Michiel

**MPI-I-92-102**. January** **1992, 16 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

We investigate 3D visibility problems for scenes that consist of

$n$ non-intersecting spheres. The

viewing point $v$ moves on a flightpath that

is part of a ``circle at infinity'' given by

a plane $P$ and a range of angles $\{\alpha(t)|t\in [0:1]\}\subset

[0:2\pi]$. At

``time'' $t$, the lines of sight are parallel to the ray $r(t)$ in the

plane $P$, which starts in the origin of $P$ and represents the angle

$\alpha(t)$ (orthographic views of the scene).

We describe algorithms that compute the visibility graph at the

start of the flight, all time parameters $t$ at which

the topology of the scene changes, and the corresponding topology

changes.

We present an algorithm with running time

$O((n+k+p)\log n)$, where $n$ is the number of spheres in the scene;

$p$ is the number of transparent topology changes (the number of

different scene topologies visible along the flightpath, assuming that

all spheres are transparent); and $k$ denotes the number of

vertices (conflicts)

which are in the (transparent) visibility graph at the start

and do not disappear during the flight.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

92-102.pdf | 45769 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1992-102

**BibTeX**
`@TECHREPORT{``LenhofSmid92a``,`

` AUTHOR = {Lenhof, Hans-Peter and Smid, Michiel},`

` TITLE = {Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-92-102},`

` MONTH = {January},`

` YEAR = {1992},`

` ISSN = {0946-011X},`

`}`