×

A succinct 3D visibility skeleton. (English) Zbl 1211.68472

Summary: The 3D visibility skeleton is a data structure that encodes the global visibility information of a set of 3D objects. While it is useful in answering global visibility queries, its large size often limits its practical use. In this paper, we address this issue by proposing a subset of the visibility skeleton, which is empirically about 25% to 50% of the whole set. We show that the rest of the data structure can be recovered from the subset as needed, partially or completely. The running time complexity, which we analyze in terms of output size, is efficient. We also prove that the subset is minimal in the sense that the complexity bound ceases to hold if the subset is restricted further.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1137/S0097539793244368 · Zbl 0843.68116
[2] DOI: 10.1137/S0097539705447116 · Zbl 1138.65019
[3] DOI: 10.1007/s00454-005-1183-1 · Zbl 1083.52003
[4] DOI: 10.1145/318009.318012
[5] DOI: 10.1145/508357.508362 · Zbl 05457286
[6] DOI: 10.1121/1.1641020
[7] DOI: 10.1111/j.1467-8659.2003.00722.x · Zbl 02180298
[8] He T., IEEE Trans. Vis. Comput. Graphics 7 pp 333–
[9] DOI: 10.1007/BF00365595 · Zbl 0338.92002
[10] DOI: 10.1017/CBO9780511804120 · Zbl 0912.68201
[11] DOI: 10.1007/BF01187036 · Zbl 0767.68097
[12] Zhang L., Lecture Notes in Computer Science 5193 pp 805– (2008) · Zbl 05373310
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.