Abstract
It is a widely observed phenomenon in computer graphics that the size of the silhouette of a polyhedron is much smaller than the size of the whole polyhedron. This paper provides, for the first time, theoretical evidence supporting this for a large class of objects, namely for polyhedra or, more generally, tessellated surfaces that approximate surfaces in some reasonable way. The approximated surfaces are two-manifolds that may be nonconvex and nondifferentiable and may have boundaries. The tessellated surfaces should, roughly speaking, have no short edges, have fat faces, and the distance between the mesh and the surface it approximates should never be too large. We prove that such tessellated surfaces of complexity n have silhouettes of expected size \(O(\sqrt{n}),\) where the average is taken over all points of view. The viewpoints can be chosen at random at infinity or at random in a bounded region.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alt, H., Glisse, M., Goaoc, X.: On the worst-case complexity of the silhouette of a polytope. In: 15th Canadian Conference on Computational Geometry—CCCG’03, pp. 51–55 (2003)
Boissonnat, J.-D., Oudot, S.: Provably good sampling and meshing of surfaces. Graph. Models Special Issue Solid Model. 67(5), 405–451 (2005)
DeCarlo, D., Finkelstein, A., Rusinkiewicz, S., Santella, A.: Suggestive contours for conveying shape. ACM Trans. Graph. 22(3), 848–855 (2003)
Duguet, F.: Shadow computations using robust epsilon visibility. Research Report 5167, INRIA (2004)
Duguet, F., Drettakis, G.: Robust epsilon visibility. In: Hughes, J. (ed.) Proceedings of ACM SIGGRAPH 2002, pp. 567–575. ACM Press/ACM SIGGRAPH, New York (2002)
Efrat, A., Guibas, L.J., Hall-Holt, O.A., Zhang, L.: On incremental rendering of silhouette maps of polyhedral scene. In: SODA ’00: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 910–917. Society for Industrial and Applied Mathematics, Philadelphia (2000)
Isenberg, T., Freudenberg, B., Halper, N., Schlechtweg, S., Strothotte, T.: A developer’s guide to silhouette algorithms for polygonal models. IEEE Comput. Graph. Appl. 23(4), 28–37 (2003)
Judd, T., Durand, F., Adelson, E.H.: Apparent ridges for line drawing. ACM Trans. Graph. 26(3), 19 (2007)
Kettner, L., Welzl, E.: Contour edge analysis for polyhedron projections. In: Geometric Modeling: Theory and Practice, pp. 379–394. Springer, Berlin (1997)
McGuire, M.: Observations on silhouette sizes. J. Graph. Tools 9(1), 1–12 (2004)
Sander, P.V., Gu, X., Gortler, S.J., Hoppe, H., Snyder, J.: Silhouette clipping. In: SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pp. 327–334. ACM Press/Addison–Wesley, New York (2000)
Schwarz, H.A.: Sur une définition erronée de l’aire d’une surface courbe. In: Gesammelte Mathematische Abhandlungen, vol. 1, pp. 309–311. Springer, Berlin (1890)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Glisse, M., Lazard, S. An Upper Bound on the Average Size of Silhouettes. Discrete Comput Geom 40, 241–257 (2008). https://doi.org/10.1007/s00454-008-9089-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9089-3