Date: Tue, 4 Jun 96 16:49:24 EDT From: Paul.Heckbert@HOSTESS.GRAPHICS.CS.CMU.EDU To: rusin@math.niu.edu Subject: points uniformly distributed on a sphere Cc: njas@RESEARCH.ATT.COM Dave and Neil: Here's something I posted to sci.math last week after seeing your interesting web pages on the topic. I figured you would be interested. =============================== begin excerpts Newsgroups: sci.math,comp.graphics.algorithms Subject: points uniformly distributed on a sphere Followup-To: sci.math Organization: School of Computer Science, Carnegie Mellon Date: Thu, 30 May 96 13:37:55 EDT From: ph@HOSTESS.GRAPHICS.CS.CMU.EDU Occasionally the following question comes up, how do I distribute n points on a sphere as uniformly as possible? There are various ways to quantify uniformity, and differing quality standards. In most cases, a solution that is close to optimal that can can be computed fast is preferred. There is a nice FAQ on this topic at [update -- djr:] index/spheres.html with pointers to Sloane's collection of best known arrangements for small n, but what is one to do for large n? Here's one way to do it: Andy Witkin and I developed an algorithm for distributing points approximately uniformly on an implicit surface (a surface of the form f(x,y,z)=0). Our method, in a nutshell: user sets desired spacing between particles on surface start with a single particle on each iteration for each particle adjust particle's position using first order Gaussian repulsion (this can be done in O(1) with good spatial data structures) if local density around particle is too low, fission the particle else if local density around particle is too high, suicide The population of particles starts out low and grows very fast and tends to settle down into good local minima of our energy function. It does not always find the global minimum, but in practice it seems to come quite close. Our implementation does not allow direct control over the number of particles you get, but that could be done. On an SGI Indy (150 MHz) we can distribute 1000 points on a sphere in about 10 seconds. With n=10000, each of the iterations above takes about 1 second. For our paper, an MPEG demo, and some pretty postscript pictures of thousands of points distributed on spheres and other surfaces, see http://www.cs.cmu.edu/~ph under Using Particles to Sample and Control Implicit Surfaces, Andy Witkin and Paul Heckbert, SIGGRAPH '94 Similar methods can also be used for mesh generation, packing circles or ellipses of variable size inside 2-D boundaries. See Anisotropic Mesh Generation with Particles, Frank Bossen, CMU-CS-96-134, CS Dept, Carnegie Mellon Univ., May 1996. on the same web page. Paul Heckbert ph@cs.cmu.edu Computer Science Dept., Carnegie Mellon University 5000 Forbes Ave, Pittsburgh PA 15213-3891, USA World Wide Web: http://www.cs.cmu.edu/~ph [after some followups where other people thought I meant uniform random points on a sphere, I clarified:] From: ph+@cs.cmu.edu (Paul Heckbert) Newsgroups: sci.math Subject: Re: points uniformly distributed on a sphere Date: 4 Jun 1996 14:11:04 GMT In article <4opvvu$8lr@sleepy.inch.com>, John McGowan wrote about how to generate uniform random points on the sphere. In my original posting, I was assuming a stricter definition of "uniform", more like "all points approximately equally spaced", but looser than "all points equally spaced". Imagine that you want a golf ball with n dimples, for any n. How do you arrange the dimples? That's the problem I was addressing. This is also sometimes called the moon base problem. Platonic solids and geodesic-dome designs will cover a few values of n well, but what about the rest? =============================== end excerpts Are you familiar with Martin Gardner's Mathematical Games column on this topic, which he called the "moon base" problem? I remember it from when I was in high school. Martin Gardner had an excellent column on recreational mathematics in Scientific American for many years. I don't know the exact date, but it was probably some time between 1971 and 1976, if you want to find it. In his article he had nice pictures of solutions for n=2, 3, 4, 5, 6, and some other small values, probably up to 20 or so. -Paul Paul Heckbert ph@cs.cmu.edu Computer Science Dept., Carnegie Mellon University 5000 Forbes Ave, Pittsburgh PA 15213-3891, USA World Wide Web: http://www.cs.cmu.edu/~ph