Article

Efficient perspective-accurate silhouette computation and applications

Authors:

Christian Duncan,

Michael Goodrich,

Subodh KumarAuthors Info & Claims

SCG '01: Proceedings of the seventeenth annual symposium on Computational geometry

Pages 60 - 68

https://doi.org/10.1145/378583.378618

Published: 01 June 2001 Publication History

Abstract

Silhouettes are perceptually and geometrically salient features of geo metric models. Hence a number of graphics and visualization applications need to find them to aid further processing. The efficient computation of silhouettes, especially in the context of perspective projection, is known to be difficult. This paper presents a novel efficient and practical algorithm to compute silhouettes from a sequence of viewpoints under perspective projection. Parallel projection is a special case of this algorithm. Our approach is based on a point-plane duality in three dimensions, which allows an efficient computation of the \emph{changes} in the silhouette of a polygonal model between consecutive frames. In addition, we present several applications of our technique to problems from computer graphics and medical visualization. We also provide experimental data that show the efficiency of our approach.

References

[1]

P.K. Agarwal and M. Sharir, Applications of a new space-partitioning technique, Discrete & Computational Geometry, 9 (1993), 11-38.

Digital Library

[2]

G. Barequet, C.A. Duncan, M.T. Goodrich, W. Huang, S. Kumar, and M. Pop, Efficient perspective-accurate silhouette computation, Proc. 4th CGC workshop on Computational Geometry, Baltimore, MD, 1999.

Digital Library

[3]

F. Benichou and G. Elber, Output sensitive extraction of silhouettes from polygonal geometry, Proc. 7th Pacific Graphics Conference, Seoul, Korea, 60-69, 1999.

Digital Library

[4]

W. Bouma and G. Vanecek, Velocity-based collision detection, in Graphics Gems V (A. Paeth, ed.), 380-385, Academic Press, 1995.

[5]

J.W. Buchanan and M.C. Sousa, The edge buffer: A data structure for easy silhouette rendering, Proc. 1st Int. Symp. on Non Photorealistic Animation and Rendering, Annecy, France, 39-42, 2000.

Digital Library

[6]

B. Chazelle, A functional approach to data structures and its use in multidimensional searching, SIAM Journal of Computing, 17 (1988), 427-462.

Digital Library

[7]

B. Chazelle, M. Sharir, and E. Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Algorithmica, 8 (1992), 407-429.

Digital Library

[8]

F. Crow, Shadow algorithms for computer graphics, ACM Computer Graphics, 11 (1977), 342-248.

Digital Library

[9]

C.A. Duncan, M.T. Goodrich, and S. Kobourov, Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees, J. of Algorithms, 38 (2001), 303-333.

Digital Library

[10]

H. Edelsbrunner, M.H. Overmars, and R. Seidel, Some methods of computational geometry applied to computer graphics, Computer vision, graphics, and image processing, 28 (1984), 92-108.

[11]

A. Efrat, L.J. Guibas, and O.A. Hall-Holt and L. Zhang, On incremental rendering of silhouette maps of a polyhedral scene, Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, San Francisco, CA, 910-917, 2000.

Digital Library

[12]

B. Gooch, P.J. Sloan, A. Gooch, P. Shirley, and R. Riesenfeld, Interactive technical illustration, Proc. ACM Symp. on 3D Interactive Graphics, Atlanta, GA, 31-38, 1999.

Digital Library

[13]

G. Gornowicz and L. Williams, Snap to it Automatic 3D object and silhouette registration, Proc. ACM SIGGRAPH Technical Sketch, 258, 2000.

[14]

A. Hertzmann and D. Zorin, Illustrating smooth surfaces, Proc. ACM SIGGRAPH, 517-526, 2000.

Digital Library

[15]

H. Hoppe, View dependent refinement of progressive meshes, Proc. ACM SIGGRAPH, 189-198, 1997.

Digital Library

[16]

H. Hoppe, Efficient implementation of progressive meshes, Technical Report MSR-TR-98-02, Microsoft Research, 1998.

[17]

L. Kettner and E. Welzl, Contour edge analysis for polyhedron projections, in Geometric Modeling: Theory and Practice (W. Strasser, R. Klein, and R. Rau, eds.), 379-394, Springer-Verlag, 1997.

[18]

S.K. Kim, Parallel algorithms for the segment dragging problem, Information Processing Letters, 36 (1990), 323-327.

Digital Library

[19]

L. Kobbelt, S. Campagna, and H.P. Seidel, A general framework for mesh decimation, Proc. of Graphics Interface, 43-50, 1998.

[20]

S. Kumar, D. Manocha, W. Garrett, and M. Lin, Hierarchical back-face culling, Computers and Graphics, 23 (1999), 681-692.

[21]

S. Lavallee, R. Szeliski, and L. Brunie, Anatomy-based registration of three-dimensional medical images, range images, X-ray projections, and three-dimensional models using octree-splines, in Computer-Integrated Surgery (R.H. Taylor, S. Lavallee, G.C. Burdea, and R. M.osges, eds.), MIT Press, 1995.

[22]

D. Luebke and C. Erikson, View-dependent simplification of arbitrary polygonal environments, Proc. ACM SIGGRAPH, 199-208, 1997.

Digital Library

[23]

L. Markosian, M. Kowalski, S. Trychin, L. Bourdev, D. Goldstein, and J. Hughes, Real-time nonphotorealistic rendering, Proc. ACM SIGGRAPH, 415-420, 1997.

Digital Library

[24]

J. Matousek, Range searching with efficient hierarchical cuttings, Discrete & Computational Geometry, 10 (1993), 157-182.

Digital Library

[25]

W. Matusik, C. Buehler, S. Gortler, R. Raskar, and L. McMillan, Image based visual hulls, Proc. ACM SIGGRAPH, 369-374, 2000.

Digital Library

[26]

M. Pop, Exploiting coherence in spatial database queries, Ph.D. Thesis, Johns Hopkins University, Baltimore, MD, 2000.

Digital Library

[27]

F.P. Preparata and M.I. Shamos, Computational Geometry, Springer-Verlag, New York, 1985.

Digital Library

[28]

R. Raskar and M. Cohen, Image precision silhouette edges, Proc. Symp. on Interactive 3D Graphics, Atlanta, GA, 135-140, 1999.

Digital Library

[29]

P. Sander, S. Gortler, H. Hoppe, and J. Snyder, Silhouette clipping, Proc. ACM SIGGRAPH, 327-334, 2000.

Digital Library

[30]

J.C. Xia and A. Varshney, Dynamic view-dependent simplification for polygonal models, Proc. IEEE Conf. on Visualization, 327-334, 1996.

Digital Library

[31]

H. Zhang and K. Hoff, Backface culling using normal masks, Proc. Symp. on Interactive 3D Graphics, Providence, RI, 103-106, 1997.

Digital Library

Cited By

Tsiapkolis PBénard P(2024)Patch Decomposition for Efficient Mesh Contours ExtractionComputer Graphics Forum10.1111/cgf.1515443:4Online publication date: 24-Jul-2024
https://doi.org/10.1111/cgf.15154
Lawonn KViola IPreim BIsenberg T(2018)A Survey of Surface‐Based Illustrative Rendering for VisualizationComputer Graphics Forum10.1111/cgf.1332237:6(205-234)Online publication date: 22-Jan-2018
https://doi.org/10.1111/cgf.13322
Company PVarley PPlumed RStanco FGiachetti APingi P(2017)Perimeter detection in sketched drawings of polyhedral shapesProceedings of the Conference on Smart Tools and Applications in Computer Graphics10.2312/stag.20171223(23-29)Online publication date: 11-Sep-2017
https://dl.acm.org/doi/10.2312/stag.20171223
Show More Cited By

Index Terms

Efficient perspective-accurate silhouette computation and applications

Recommendations

Shadow silhouette maps

The most popular techniques for interactive rendering of hard shadows are shadow maps and shadow volumes. Shadow maps work well in regions that are completely in light or in shadow but result in objectionable artifacts near shadow boundaries. In ...
Silhouette texture
EGSR '06: Proceedings of the 17th Eurographics conference on Rendering Techniques

Using coarse meshes with textures and/or normal maps to represent detailed meshes often results in poor visual quality along silhouettes. To tackle this problem, we introduce silhouette texture, a new data structure for capturing and reconstructing the ...
Shadow silhouette maps
SIGGRAPH '03: ACM SIGGRAPH 2003 Papers

The most popular techniques for interactive rendering of hard shadows are shadow maps and shadow volumes. Shadow maps work well in regions that are completely in light or in shadow but result in objectionable artifacts near shadow boundaries. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '01: Proceedings of the seventeenth annual symposium on Computational geometry

June 2001

326 pages

ISBN:158113357X

DOI:10.1145/378583

Editor:
Diane L. Souvaine
Tufts Univ.

Copyright © 2001 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG01

Sponsor:

SoCG01: ACM Symposium on Computational Geometry

Massachusetts, Medford, USA

Acceptance Rates

SCG '01 Paper Acceptance Rate 39 of 106 submissions, 37%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
680
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tsiapkolis PBénard P(2024)Patch Decomposition for Efficient Mesh Contours ExtractionComputer Graphics Forum10.1111/cgf.1515443:4Online publication date: 24-Jul-2024
https://doi.org/10.1111/cgf.15154
Lawonn KViola IPreim BIsenberg T(2018)A Survey of Surface‐Based Illustrative Rendering for VisualizationComputer Graphics Forum10.1111/cgf.1332237:6(205-234)Online publication date: 22-Jan-2018
https://doi.org/10.1111/cgf.13322
Company PVarley PPlumed RStanco FGiachetti APingi P(2017)Perimeter detection in sketched drawings of polyhedral shapesProceedings of the Conference on Smart Tools and Applications in Computer Graphics10.2312/stag.20171223(23-29)Online publication date: 11-Sep-2017
https://dl.acm.org/doi/10.2312/stag.20171223
Biedl THasan MLópez-Ortiz A(2011)Efficient view point selection for silhouettes of convex polyhedraComputational Geometry: Theory and Applications10.1016/j.comgeo.2011.04.00144:8(399-408)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1016/j.comgeo.2011.04.001
Olson MZhang H(2009)Tangential Distance Fields for Mesh Silhouette ProblemsComputer Graphics Forum10.1111/j.1467-8659.2008.01306.x28:1(84-100)Online publication date: 23-Feb-2009
https://doi.org/10.1111/j.1467-8659.2008.01306.x
Wang LTu CWang WMeng XChan BYan D(2008)Silhouette Smoothing for Real-Time Rendering of Mesh SurfacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2008.814:3(640-652)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1109/TVCG.2008.8
Efrat AGuibas LHall-Holt OZhang L(2007)On incremental rendering of silhouette maps of a polyhedral sceneComputational Geometry: Theory and Applications10.1016/j.comgeo.2006.12.00338:3(129-138)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1016/j.comgeo.2006.12.003
Ruan XZhang HYong J(2006)Visible region extraction from a sequence of rational Bézier surfacesJournal of Zhejiang University-SCIENCE A10.1631/jzus.2006.A12337:7(1233-1240)Online publication date: 1-Jul-2006
https://doi.org/10.1631/jzus.2006.A1233
Olson MZhang H(2006)Silhouette Extraction in Hough SpaceComputer Graphics Forum10.1111/j.1467-8659.2006.00946.x25:3(273-282)Online publication date: 7-Dec-2006
https://doi.org/10.1111/j.1467-8659.2006.00946.x
Khardekar RBurton GMcMains S(2006)Finding feasible mold parting directions using graphics hardwareComputer-Aided Design10.1016/j.cad.2006.01.00838:4(327-341)Online publication date: 1-Apr-2006
https://dl.acm.org/doi/10.1016/j.cad.2006.01.008
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten