Abstract
We present an efficient and robust algorithm for computing continuous visibility for two- or three-dimensional shapes whose boundaries are NURBS curves or surfaces by lifting the problem into a higher dimensional parameter space. This higher dimensional formulation enables solving for the visible regions over all view directions in the domain simultaneously, therefore providing a reliable and fast computation of the visibility chart, a structure which simultaneously encodes the visible part of the shape’s boundary from every view in the domain. In this framework, visible parts of planar curves are computed by solving two polynomial equations in three variables (t and r for curve parameters and θ for a view direction). Since one of the two equations is an inequality constraint, this formulation yields two-manifold surfaces as a zero-set in a 3-D parameter space. Considering a projection of the two-manifolds onto the tθ-plane, a curve’s location is invisible if its corresponding parameter belongs to the projected region. The problem of computing hidden curve removal is then reduced to that of computing the projected region of the zero-set in the tθ-domain. We recast the problem of computing boundary curves of the projected regions into that of solving three polynomial constraints in three variables, one of which is an inequality constraint. A topological structure of the visibility chart is analyzed in the same framework, which provides a reliable solution to the hidden curve removal problem. Our approach has also been extended to the surface case where we have two degrees of freedom for a view direction and two for the model parameter. The effectiveness of our approach is demonstrated with several experimental results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Appel, A.: The Notion of quantitative Invisibility and the Machine Rendering of Solids. In: Proceedings ACM National Conference (1967)
Bouknight, W.J.: A procedure for Generation of Three-Dimensional Half-toned Computer Graphics Representations. CACM 13(9) (1969)
Bowyer, K., Dyer, C.: Aspect graphs: An introduction and survey of recent results. In: Proc. SPIE Conf. on Close Range Photogrammetry Meets Machine Vision, vol. 1395, pp. 200–208 (1990)
Catmull, E.: A Subdivision Algorithm for Computer Display of Curved Surfaces. Ph.D Thesis, Report UTEC-CSc-74-133, Computer Science Department, University of Utah, Salt Lake City, UT (1974)
Elber, G., Kim, M.S.: Geometric Constraint Solver Using Multivariate Rational Spline Functions. In: Proc. of International Conference on Shape Modeling and Applications, pp. 216–225. MIT Press, USA (2005)
Elber, G., Sayegh, R., Barequet, G., Martin, R.: Two-Dimensional Visibility Charts for Continuous Curves. In: Proc. of ACM Symposium on Solid Modeling and Applications, Ann Arbor, MI, June 4-8 (2001)
Elber, G., Cohen, E.: Hidden curve removal for free form surfaces. Computer Graphics 24(4), 95–104 (1990)
Foley, J., Van Dam, A., Hughes, J., Feiner, S.: Computer Graphics: Principles and Practice. Addison Wesley, Reading (1990)
Galimberti, R., Montanari, U.: An algorithm for Hidden Line Elimination. CACM 12(4), 206–211 (1969)
Hornung, C.: A Method for Solving the Visibility Problem. CG&A, 26–33 (July 1984)
Hornung, C., Lellek, W., Pehwald, P., Strasser, W.: An Area-Oriented Analytical Visibility Method for Displaying Parameterically Defined Tensor-Product Surfaces. Computer Aided Geometric Design 2, 197–205 (1985)
IRIT 9.0 User’s Manual (October 2000), Technion: http://www.cs.technion.ac.il/~irit
Ju, T., Losasso, F., Schaefer, S., Warren, J.: Dual Contouring of Hermite Data. In: Proceedings of SIGGRAPH 2002, pp. 339–346 (2002)
Kamada, T., Kawai, S.: An Enhanced Treatment of Hidden Lines. ACM Transaction on Graphics 6(4), 308–323 (1987)
Kim, M.S., Elber, G.: Problem Reduction to Parameter Space. In: The Mathematics of Surface IX (Proc. of the Ninth IMA Conference), London, pp. 82–98 (2000)
Krishnan, S., Manocha, D.: Global Visibility and Hidden Surface Algorithms for Free Form Surfaces. Technical Report: TR94-063, University of North Carolina (1994)
Li, L.: Hidden-line algorithm for curved surfaces. Computer-Aided Design 20(8), 466–470 (1988)
Loutrel, P.: A Solution to the Hidden-line Problem for Computer Drawn Polyhedra. IEEE Transactions on Computers C-19(3), 205–213 (1970)
Mckenna, M.: Worst-Case Optimal Hidden-Surface Removal. ACM Transaction on Graphics 6(1), 19–28 (1987)
Mulmuley, M.: An efficient algorithm for hidden surface removal. Computer Graphics 23(3), 379–388 (1989)
Nishita, T., Takita, S., Nakamae, E.: Hidden Curve Elimination of Trimmed Surfaces Using Bezier Clipping. In: Proc. of the 10th International Conference of the Computer Graphics on Visual Computing, Tokyo, Japan, pp. 599–619 (1992)
Ohno, Y.: A Hidden Line Elimination Method for Curved Surfaces. Computer-Aided Design 15(4), 209–216 (1983)
Seong, J.K., Elber, G., Kim, M.S.: Contouring 1- and 2-Manifolds in Arbitrary Dimensions. In: Proc. of International Conference on Shape Modeling and Applications, pp. 216–225. MIT, USA (2005)
Sutherland, I., Sproull, R., Schumacker, R.: A Characterization of ten Hidden-Surface Algorithms. Computer Surveys 6(1), 1–55 (1974)
Weiler, K., Atherton, P.: Hidden Surface Removal Using Polygon Area Sorting. In: SIGGRAPH 1977, pp. 214–222 (1977)
Whitted, T.: An Improved Illumination Model for Shaded Display. ACAM 23(6), 343–349 (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Seong, JK., Elber, G., Cohen, E. (2006). Simultaneous Precise Solutions to the Visibility Problem of Sculptured Models. In: Kim, MS., Shimada, K. (eds) Geometric Modeling and Processing - GMP 2006. GMP 2006. Lecture Notes in Computer Science, vol 4077. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11802914_32
Download citation
DOI: https://doi.org/10.1007/11802914_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36711-6
Online ISBN: 978-3-540-36865-6
eBook Packages: Computer ScienceComputer Science (R0)