Reconstructing visible regions from visible segments |
| |
Authors: | W Randolph Franklin Varol Akman |
| |
Institution: | (1) Electrical, Computer, and Systems Engineering Department, Rensselaer Polytechnic Institute, 12180 Troy, New York, USA;(2) Department of Computer Science, University of Utrecht, Budapestlaan 6, P.O. Box 80.012, 3508 TA Utrecht, the Netherlands |
| |
Abstract: | An algorithm is presented for reconstructing visible regions from visible edge segments in object space. This has applications in hidden surface algorithms operating on polyhedral scenes and in cartography. A special case of reconstruction can be formulated as a graph problem: Determine the faces of a straight-edge planar graph given in terms of its edges. This is accomplished inO(n logn) time using linear space for a graph withn edges, and is worst-case optimal. The graph may have separate components but the components must not contain each other. The general problem of reconstruction is then solved by applying our algorithm to each component in the containment relation.Research of this author is supported by the National Science Foundation under grant no. ECS-8351942, and by the Schlumberger-Doll Research Labs, Ridgefield, Connecticut. |
| |
Keywords: | I 3 5 I 3 7 F 2 2 |
本文献已被 SpringerLink 等数据库收录! |
|