Thomas Larsson
School of Innovation, Design and Engineering, Mälardalen University, Sweden
Ladda ner artikel
Ingår i: SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden
Linköping Electronic Conference Proceedings 34:9, s. 27-30
Publicerad: 2008-11-27
ISBN:
ISSN: 1650-3686 (tryckt), 1650-3740 (online)
Bounding spheres are utilized frequently in many computer graphics and visualization applications; and it is not unusual that the computation of the spheres has to be done during run-time at real-time rates. In this paper; an attractive algorithm for computing bounding spheres under such conditions is proposed. The method is based on selecting a set of k extremal points along s = k/2 input directions. In general; the method is able to compute better fitting spheres than Ritter’s algorithm at roughly the same speed. Furthermore; the algorithm computes almost optimal spheres significantly faster than the best known smallest enclosing ball methods. Experimental evidence is provided which illustrates the qualities of the approach as compared to five other competing methods. Also; the experimental result gives insight into how the parameter s affects the tightness of fit and computation speed.
CR Categories: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems—Geometrical problems and computations; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Bounding sphere; enclosing ball; extremal points; computational geometry; computer graphics
B ˆADOIU; M.; AND CLARKSON; K. L. 2003. Smaller core-sets for balls. In SODA ’03: Proceedings of the fourteenth annual ACMSIAM symposium on Discrete algorithms; Society for Industrial and Applied Mathematics; Philadelphia; PA; USA; 801–802.
B ?ADOIU; M.; AND CLARKSON; K. L. 2008. Optimal core-sets for balls. Computational Geometry: Theory and Applications 40; 1; 14–22.
EBERLY; D. H. 2007. 3D Game Engine Design: A Practical Approach to Real-Time Computer Graphics; Second Edition. Morgan Kaufmann.
ERICSON; C. 2005. Real-Time Collision Detection. Morgan Kaufmann.
FISCHER; K.; AND G ¨ARTNER; B. 2003. The smallest enclosing ball of balls: combinatorial structure and algorithms. In SCG ’03: Proceedings of the nineteenth annual symposium on Computational geometry; ACM; New York; NY; USA; 292–301.
G¨ARTNER; B. 1999. Fast and robust smallest enclosing balls. In ESA ’99: Proceedings of the 7th Annual European Symposium on Algorithms; Springer-Verlag; London; UK; 325–338.
KUMAR; P.; MITCHELL; J. S. B.; AND YILDIRIM; E. A. 2003. Approximate minimum enclosing balls in high dimensions using core-sets. Journal of Experimental Algorithmics 8.
MEGIDDO; N. 1983. Linear-time algorithms for linear programming in R3 and related problems. SIAM Journal on Computing 12; 759–776.
RITTER; J. 1990. An efficient bounding sphere. In Graphics Gems; A. Glassner; Ed. Academic Press; 301–303.
WELZL; E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and Trends in Computer Science; Lecture Notes in Computer Science 555; H. Maurer; Ed. Springer; 359–370.
WU; X. 1992. A linear-time simple bounding volume algorithm. In Graphics Gems III; D. Kirk; Ed. Academic Press; 301–306.
