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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
W. R. Franklin,Combinatorics of hidden surface algorithms, Ph.D. dissertation and report TR-12-78, Harvard University, Center for Research in Computing Technology, Cambridge, Mass. (1978).
W. R. Franklin,A linear time exact hidden surface algorithm, ACM Computer Graphics 14(3), pp. 117–123 (1980).
W. R. Franklin,A simplified map overlap algorithm, Proc. Harvard Computer Graphics Conf., Cambridge, Mass., (1983).
W. R. Franklin,Adaptive grids for geometric operations, Proc. Sixth International Symp. on Automated Cartography 2, pp. 230–239, Ottawa, Canada, (1983).
W. R. Franklin,Cartographic errors symptomatic of underlying algebra problems, Proc. International Symp. on Spatial Data Handling 1, pp. 190–208, Zurich, Switzerland, (1984).
W. R. Franklin,Computational geometry and Prolog, pp. 737–749, inFundamental Algorithms for Computer Graphics', Ed. R. A. Earnshaw, Springer-Verlag, Heidelberg (1985).
W. R. Franklin and V. Akman,Reconstructing visible regions from visible segments, University of Utrecht, Dept. of Computer Science, report RUU-CS-86-5, Utrecht, the Netherlands (March 1986).
W. R. Franklin and V. Akman,Adaptive grid for polyhedral visibility in object space: An implementation, University of Utrecht, Dept. of Computer Science, report RUU-CS-86-4, Utrecht, the Netherlands (March 1986).
H. Fuchs, Z. M. Kedem and B. F. Naylor,On visible surface generation by a priori tree structures, ACM Computer Graphics 14, pp. 124–133 (1980).
J. C. Gonzales, M. H. Williams and I. E. Aitchison,Evaluation of the effectiveness of Prolog for a CAD application.IEEE Computer Graphics and Applications 4(3), pp. 67–75 (1984).
J. G. Griffiths,Bibliography of hidden line and hidden surface algorithms, Computer Aided Design 10(3), pp. 203–206 (1979).
P. P. Loutrel,A solution to the hidden line problem for computer drawn polyhedra, IEEE Transactions on Computers 19(3), pp. 205–213 (1970).
D. E. Muller and F. P. Preparata,Finding the intersection of two convex polyhedra, Theoretical Computer Science 7, pp. 217–236 (1978).
J. Nievergelt and F. P. Preparata,Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM 25(10), pp. 739–747 (October 1982).
O. Nurmi,A fast line-sweep algorithm for hidden line elimination, BIT 25, pp. 466–472 (1985).
T. Ottmann and P. Widmayer,Solving visibility problems by using skeleton structures, Proc. 11th Symp. on the Mathematical Foundations of Computer Science, pp. 459–470, Springer-Verlag, (1984).
A. Schmitt,Time and space bounds for hidden line and hidden surface algorithms, Proc. Eurographics-81, North-Holland, Amsterdam, (1981).
S. Sechrest and D. P. Greenberg,A visible polygon reconstruction algorithm, ACM Transactions on Graphics 1(1), pp. 25–42 (1982).
I. E. Sutherland, R. F. Sproull and R. Schumacker,A characterization of ten hidden surface algorithms, ACM Computing Surveys 6(1), pp. 1–55 (1974).
P. S. G. Swinson,Logic programming: A computing tool for the architect of the future, Computer Aided Design 14(2), pp. 97–104 (1982).
K. Weiler and P. Atherton,Hidden surface removal using polygon area sorting, ACM Computer Graphics 11(2), pp. 214–222 (1977).
F. F. Yao,On the priority approach to hidden surface algorithms, Proc. 21st Annual IEEE Symp. on the Foundations of Computer Science, pp. 301–307, Potsdam, NY, (1980).
Author information
Authors and Affiliations
Additional information
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.
Rights and permissions
About this article
Cite this article
Franklin, W.R., Akman, V. Reconstructing visible regions from visible segments. BIT 26, 430–441 (1986). https://doi.org/10.1007/BF01935050
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/BF01935050