Article | SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden | Fast and Tight Fitting Bounding Spheres

Title:
Fast and Tight Fitting Bounding Spheres
Author:
Thomas Larsson: School of Innovation, Design and Engineering, Mälardalen University, Sweden
Download:
Full text (pdf)
Year:
2008
Conference:
SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden
Issue:
034
Article no.:
009
Pages:
27-30
No. of pages:
4
Publication type:
Abstract and Fulltext
Published:
2008-11-27
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press; Linköpings universitet


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

Keywords: Bounding sphere; enclosing ball; extremal points; computational geometry; computer graphics

SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden

Author:
Thomas Larsson
Title:
Fast and Tight Fitting Bounding Spheres
References:

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.

SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden

Author:
Thomas Larsson
Title:
Fast and Tight Fitting Bounding Spheres
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment