Article

Free access

An exact interactive time visibility ordering algorithm for polyhedral cell complexes

Authors:

Cláudio T. Silva,

Joseph S. B. Mitchell,

Peter L. WilliamsAuthors Info & Claims

VVS '98: Proceedings of the 1998 IEEE symposium on Volume visualization

Pages 87 - 94

https://doi.org/10.1145/288126.288170

Published: 01 October 1998 Publication History

PDF eReader

References

[1]

E K. Agam~ and J. Matou~k. Ray shooting and parametric seare_h. S/AM J. Comput., 22(4):794--806, 1993.]]

Digital Library

Google Scholar

[2]

E K. Agam,al and k Matou~ek. On range searching with semialgebraic sets. Discrete Comput. Geom., 11:.393-418, 1994.]]

Google Scholar

[3]

L L Balaban. An optimal algorithm for finding ~ent intersections. In Pro~ l lth Annv. ACM S3wzpos. CompuL Geo~, pages 211-219, 1995.]]

Digital Library

Google Scholar

[4]

B. Chazclle and H. FAelsbmnnen An optimal algorithm for intersecting line segments in the plane. J. ACM, 39:1-54, 1992.]]

Digital Library

Google Scholar

[5]

B. ChazeLte, H. Edelsbnmner, L. J. Gm'bas, 1L Pollack, R. Seidel, M. Shark, and J. Snoeb~d~ Counting and cutting c3'eles of lines and ro~ in space. Comput. Geom. Theory AppL, 1".305-323, 1992.]]

Digital Library

Google Scholar

[6]

M. de Berg. Ray Shooting. Depth Orders and H'_uldan Surface Removal, ~'olume 703 of Lecture Notes Comput. Sci. Springer- Verlag, Berlin, Germany, 1993.]]

Digital Library

Google Scholar

[7]

M. de Berg, L. J. Gm'bas, and D. Halpefin. Vertical decompositions for triangles in 3-space. Discrete Comput. Geora., 15".35- 61, 1996.]]

Google Scholar

[8]

M. de Berg, D. Halperin, M. Overmars, j. Snoe35ak, and M. van Kreveld. Efficient my shooting and hidden surface removal. AlgorithrMca, 12:30-53, 1994.]]

Crossref

Google Scholar

[9]

1~ de Berg, 1~ Overmars, and O. Sehwarzkopf. Computing and verifying depth orders. SIAM Journal on Computing, 23:437- 446, 1994.]]

Digital Library

Google Scholar

[10]

M. de Berg,/~ x~m Kreveld, ~ Ovennars, and O. Sehwarzkopf. Computan'onal Geometo," Algorithms and Applications. Springer-Verlag, Berlin, 199%]]

Google Scholar

[11]

L. Carpenter, "The A-buffer, an antialiased hidden star-ace method," Computer Graphics, vol. 18, no. 3, pp. 103-108, 1984.]]

Digital Library

Google Scholar

[12]

D. P. Dobldn and M. J. Laszlo. Primitia.es for the manipulation ofthree-dimensional subdivisions. Algorithmica, 4"_'3--32, 1989.]]

Google Scholar

[13]

H. Edelsbmnner. An aeyelieity theorem for cell complexes in d dimensions. Combinatorica, 10".251-260, 1990.]]

Google Scholar

[14]

H. Edelsbamner and ~ P. Mfieke. Simulation of simplicity: a technique to cope with degenerate eases in geo~e algorithms. ACAf Trans. Graph., 9:66-104, 1990.]]

Digital Library

Google Scholar

[15]

H. Fuchs, Z. M. Kedem, and B. Naylor_ On visible surface generation by a priori tree strueanes. Comput Graph., 14(3):124- 133, 19{;0. Proe. SIGGRAPH '80.]]

Digital Library

Google Scholar

[16]

h~ P. Gar6b- "RayWa~g ~ Volume Data," Computer Grapt'dcs (San Diego Workshop on Volume Hsualiz~'on), vol. 24, pp. 35--40, Nov. 1990.]]

Google Scholar

[17]

C. Giertsen, "Volume Visualization of Sparse In-egular Meshes," IEEE Computer Graphics and Applications, vol. 12, no. 2, pp. 49--48, March 1992.]]

Digital Library

Google Scholar

[18]

M. GooSn'eh and 1L Tamassia. D37mmic trees and dynamic point location. In Pro~ 23rd Annu. ACM S)Tnpos. Theory Comput, pages 523-533, 1991.]]

Digital Library

Google Scholar

[19]

M. S. Karasick, D. Lieber, L. R. Naehnan, and V. T. Rajah. Visualization of three-dimensioaal Delannay meshes. Algorithrrdca, 19(1-2):114-128, Sept. 199%]]

Google Scholar

[20]

N. Max, P. Hanmhan, and R. Cra~a'is. Area and volnme cohere.nee for efficient ~Sstm/izafion of 3d scalar functions. Comput Graph., 24(5):27-33, 1990.]]

Digital Library

Google Scholar

[21]

J.S.B. l~qtchell, D. M. Mount, and S. Suri. Query-sensitive ray shooting. In Proc. lOth Annu. ACM S)Tnpos. Comput. Geom., pag~ 359-368, 1994.]]

Digital Library

Google Scholar

[22]

M. NeweU, R. Newell and T. Sancha, "Solution to the hidden surface problem" Proc ACM National Conference, 1972, pp. 443-450.]]

Digital Library

Google Scholar

[23]

M. Newell, "The utilization of procedure models in digital image synthesis:' Ph.D. Thesis, University of Utah, 1974 CtJTEC-CSe- 76-218 and NTIS AD/A 039 008/LL).]]

Digital Library

Google Scholar

[24]

O. Nurmi. On translating a set of objects in two- and threedimensional spaces. Comput. Vision Graph. Image Process., 36:42-52, 1986.]]

Digital Library

Google Scholar

[25]

M.S. Paterson and E E Yao. Efficient binary space partitions for hidden-surface removal and solid modeling. Discrete Comput. Geom., 5:485-503, 1990.]]

Digital Library

Google Scholar

[26]

M. Pellegrini. Ray shooting on triangles in 3-space. Algorithm~ca, 9:471--494, 1993.]]

Crossref

Google Scholar

[27]

E P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, NY, 1985.]]

Digital Library

Google Scholar

[28]

O. Sehwarzkopf and M. Shark. Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications. Discrete Comput. Geom., 18:269-288, 1997.]]

Crossref

Google Scholar

[29]

M. Shark and P. K. Agarwal. Davenport.Schinzel Sequences and Their Geometn'c Applications. Cambridge University Press, New York, 1995.]]

Digital Library

Google Scholar

[30]

P. Shirley and A. Tuehman, "A Polygonal Approximation to Direct Scalar Volume Rendering," Computer Graphics (San Diego Workshop on Volume Vtsualization), vol. 24, pp. 63--70, Nov. 1990.]]

Digital Library

Google Scholar

[31]

C. T. Silva and J. S. B. Mitchell. The lazy sweep my casting algorithm for rendering irregular grids. IEEE Trans. Visualizat. Comput. Graph., 3(2):142-157, Apr. 1997.]]

Digital Library

Google Scholar

[32]

C. Stein, B. Beeker, and N. Max, "Sorting and Hardware Assisted Rendering for Volume Visualization," Symposium on Volume Vtsualization, pp. 83-90, October 1994.]]

Digital Library

Google Scholar

[33]

P. W'dliams, "Visibility Ordering Meshed Polyhedra,'" ACM Transactions on Graphics, vol. 11, no. 2, 1992.]]

Digital Library

Google Scholar

[34]

P.L. Williams, N. Max, and C. Stein, "A high accuracy volume renderer for unstructured data," IEEE Trans. on Visualization and Computer Graphz'cs, vol. 4, no. 1, pp. 1-18, March 1998.]]

Digital Library

Google Scholar

[35]

R. Yagel, D. Reed, A. Law, P-W. Shill, and N. Shareef, "Hardware Assisted Volume Rendering of Unstructured Grids by Incremental Slicing:' IEEE-ACM Volume Visualization Symposium, pp. 55--62, Nov. 1996.]]

Digital Library

Google Scholar

Cited By

View all

Li XLiu X(2015)Multi-segment and multi-stage projected tetrahedraJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-015-0271-17:5(639-648)Online publication date: 15-Mar-2015
https://doi.org/10.1007/s12652-015-0271-1
Maximo AMarroquim RFarias R(2010)Hardware-assisted projected tetrahedraProceedings of the 12th Eurographics / IEEE - VGTC conference on Visualization10.1111/j.1467-8659.2009.01673.x(903-912)Online publication date: 9-Jun-2010
https://dl.acm.org/doi/10.1111/j.1467-8659.2009.01673.x
Muigg PHadwiger MDoleisch HHauser H(2007)Scalable Hybrid Unstructured and Structured Grid RaycastingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2007.7058813:6(1592-1599)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1109/TVCG.2007.70588
Show More Cited By

Recommendations

Visibility-ordering meshed polyhedra

A visibility-ordering of a set of objects from some viewpoint is an ordering such that if object a obstructs object b, then b precedes a in the ordering. An algorithm is presented that generates a visibility-ordering of an acyclic convex set of meshed ...
Image-Space Visibility Ordering for Cell Projection Volume Rendering of Unstructured Data

Projection methods for volume rendering unstructured data work by projecting, in visibility order, the polyhedral cells of the mesh onto the image plane, and incrementally compositing each cell's color and opacity into the final image. Normally, such ...
Polygon visibility ordering via Voronoi diagrams
Abstract
Visibility determination is one of the oldest problems in computer graphics. The visibility, in terms of back-to-front polygon visibility ordering, is determined by updating a priority list as the viewpoint moves. A new list-priority algorithm, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

VVS '98: Proceedings of the 1998 IEEE symposium on Volume visualization

October 1998

178 pages

ISBN:1581131054

DOI:10.1145/288126

Chairmen:
Arie Kaufman
State Univ. of New York at Stony Brook
,
Roni Yagel
Biomedicom and The Ohio State Univ.
,
William E. Lorensen
GE Corporate Research and Development

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

VolVis98

Sponsor:

SIGGRAPH
IEEE-CS

VolVis98: 1998 IEEE Volume Visualization Symposium

October 19 - 20, 1998

North Carolina, Research Triangle Park, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
291
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)17

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li XLiu X(2015)Multi-segment and multi-stage projected tetrahedraJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-015-0271-17:5(639-648)Online publication date: 15-Mar-2015
https://doi.org/10.1007/s12652-015-0271-1
Maximo AMarroquim RFarias R(2010)Hardware-assisted projected tetrahedraProceedings of the 12th Eurographics / IEEE - VGTC conference on Visualization10.1111/j.1467-8659.2009.01673.x(903-912)Online publication date: 9-Jun-2010
https://dl.acm.org/doi/10.1111/j.1467-8659.2009.01673.x
Muigg PHadwiger MDoleisch HHauser H(2007)Scalable Hybrid Unstructured and Structured Grid RaycastingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2007.7058813:6(1592-1599)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1109/TVCG.2007.70588
Georgii JWestermann R(2006)A Generic and Scalable Pipeline for GPU Tetrahedral Grid RenderingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2006.11012:5(1345-1352)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/TVCG.2006.110
Comba JMitchell JSilva C(2006)On the Convexification of Unstructured Grids from a Scientific Visualization PerspectiveScientific Visualization: The Visual Extraction of Knowledge from Data10.1007/3-540-30790-7_2(17-34)Online publication date: 2006
https://doi.org/10.1007/3-540-30790-7_2
Govindaraju NHenson MLin MManocha DLastra AOlano MLuebke DPfister H(2005)Interactive visibility ordering and transparency computations among geometric primitives in complex environmentsProceedings of the 2005 symposium on Interactive 3D graphics and games10.1145/1053427.1053435(49-56)Online publication date: 3-Apr-2005
https://dl.acm.org/doi/10.1145/1053427.1053435
Callahan SIkits MComba JSilva C(2005)Hardware-Assisted Visibility Sorting for Unstructured Volume RenderingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2005.4611:3(285-295)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1109/TVCG.2005.46
Moreland KAngel E(2004)A Fast High Accuracy Volume Renderer for Unstructured DataProceedings of the 2004 IEEE Symposium on Volume Visualization and Graphics10.5555/1038266.1039016(9-16)Online publication date: 11-Oct-2004
https://dl.acm.org/doi/10.5555/1038266.1039016
Cook RMax NSilva CWilliams P(2004)Image-Space Visibility Ordering for Cell Projection Volume Rendering of Unstructured DataIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2004.4510:6(695-707)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1109/TVCG.2004.45
Mello VVelho LCavalcanti PSilva C(2003)A Generic Programming Approach to Multiresolution Spatial DecompositionsVisualization and Mathematics III10.1007/978-3-662-05105-4_18(337-360)Online publication date: 2003
https://doi.org/10.1007/978-3-662-05105-4_18
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Visibility-ordering meshed polyhedra

Image-Space Visibility Ordering for Cell Projection Volume Rendering of Unstructured Data

Polygon visibility ordering via Voronoi diagrams