A simple output-sensitive algorithm for hidden surface removal
A simple output-sensitive algorithm for hidden surface removal
复制标题
一种简单的输出敏感隐藏表面去除算法
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
M. Overmars
中科院分区：
文献类型：
--
作者：
M. Sharir;M. Overmars
我们推导出一种简单的对输出敏感的算法，用于去除空间中\(n\)个三角形集合中的隐藏面，对于这些三角形已知（部分）深度顺序。如果\(k\)是输出的可见性映射的组合复杂度，该方法的运行时间为\(O(n\sqrt{k}\log n)\)。该方法也被扩展以适用于其他类别的对象，有时甚至具有更优的时间界限。例如，我们得到一种算法，它能在时间\(O(n^{3/2}\log n + k)\)内对\(n\)个（不相交的）球体进行隐藏面去除。
We derive a simple output-sensitive algorithm for hidden surfaceremoval in a collection of <?Pub Fmt italic>n<?Pub Fmt /italic>triangles in space for which a (partial) depth order is known. If<?Pub Fmt italic>k<?Pub Fmt /italic> is the combinatorial complexity ofthe output <?Pub Fmt italic>visibility map<?Pub Fmt /italic>, the methodruns in time <inline-equation><f>O<fen lp="par">n<rad><rcd>k</rcd></rad><hsp sp="0.167"><rf>log</rf>n<rp post="par"></fen></f></inline-equation>. The method is extended to work for other classes ofobjects as well, sometimes with even improved time bounds. For example,we obtain an algorithm that performs hidden surface removal for<?Pub Fmt italic>n<?Pub Fmt /italic> (nonintersecting) balls in time<inline-equation><f>O<fen lp="par">n<sup>3/2</sup><rf>log</rf>n+k<rp post="par"></fen></f></inline-equation>.<?Pub Caret>