From: leech@cs.unc.edu (Jon Leech) Newsgroups: comp.graphics.algorithms,comp.graphics.visualization,sci.math,comp.lang.tcl Subject: ANNOUNCE: Point repulsion / sphere tesselation code available Date: 11 Feb 1996 22:09:56 -0500 Please do *not* follow up this post without trimming the Newsgroups: line to include at most one of sci.math, comp.lang.tcl, comp.graphics.algorithms, and c.g.visualization. It is highly unlikely that a fruitful thread could ensue between the 4 groups this announcement is posted to. ---- Since the ever-popular "how do I evenly distribute N points on a sphere" and "how do I tesselate a sphere" threads have flared up again on comp.graphics.algorithms, and since related discussion seems to be taking place on sci.math, I polished up some old code implementing the point-repulsion algorithm for people who want to play with it. It also generates VRML files containing sphere tesselations based on the point distributions. It's in ftp://ftp.cs.unc.edu/pub/users/leech/points.tar.gz Thanks to Dave Watson for his convex hull generation code, to the Tcl/Tk and [incr Tcl] teams for their great tools, and to Sloane et al at Bell Labs for making the question pointless (so to speak) for less than 133 samples. Happy repulsiveness (and Joseph, about that c.g.a FAQ entry - perhaps you could just make it a pointer to the Rusin FAQ mentioned below, with another pointer to my code if you're so inclined?) Jon (leech@cs.unc.edu) __@/ ---- From the release notes: INTRODUCTION Points and distribute are programs that attempt to answer the comp.graphics.algorithms FAQs "How do I evenly distribute N points on a sphere?" and "How do I tesselate a sphere?". Both programs are written in C++. Distribute is non-interactive and has a command-line interface; it should run on almost any system with a decent C++ compiler. Points is interactive and fun to play with. It uses the Tk GUI, Tcl interpreter, and [incr Tcl] OOP libraries, which are available for Unix, Microsoft Windows, and MacOS. While it should be straightforward to get these programs working under Windows and MacOS, I haven't done so. The supplied Makefile only works for Unix systems and the code has only been tested under HP-UX. ... DEFINING "EVENLY DISTRIBUTED" It doesn't have a single definition. From a mathematical point of view, this turns out to be a moderatedly complicated subject. And this topic happens to be a FAQ on sci.math as well as on comp.graphics.algorithms; a much more extensive and rigorous discussion written by Dave Rusin can be found at http://www.math.niu.edu/~rusin/papers/known-math/index/spheres.html [URL updated 1999/01 -- djr] ... SOME SAMPLE FILES The subdirectory "samples" contains files in the format read and written by these programs, with extremely good energy-minimizing distributions. A file named e.g. '42' will contain the distribution for 42 points in the format used by my point-repulsion codes. These distributions were generated by R. H. Hardin, N. J. A. Sloane and W. D. Smith of AT&T Bell Labs; I simply converted them to the format my programs use. Their original data and discussions thereof may be found at URL ftp://netlib.att.com/netlib/att/math/sloane/electrons/ ============================================================================== From: Vladimir Bulatov Newsgroups: comp.graphics.algorithms,sci.math Subject: Re: ANNOUNCE: Point repulsion / sphere tesselation code available Date: 12 Feb 1996 12:45:28 GMT leech@cs.unc.edu (Jon Leech) wrote: > > Since the ever-popular "how do I evenly distribute N points on a sphere" >and "how do I tesselate a sphere" threads have flared up again on >comp.graphics.algorithms, and since related discussion seems to be taking >place on sci.math, I polished up some old code implementing the >point-repulsion algorithm for people who want to play with it. It also >generates VRML files containing sphere tesselations based on the point >distributions. It's in > > ftp://ftp.cs.unc.edu/pub/users/leech/points.tar.gz > I have decided to join discussion of sphere tesseleration (don't understand though, why it is so important ;-)) with my peace of code, which I wrote yesterday to solve the problem (may be in another way, don't know, because file points.tar.gz is still beeing transferred (more than an hour :-) now ) Here is my "solution", usually it works, not too fast though, because rude force algorithm was used. Don't blame me for code posting. It is small enough. FILE points_on_sphere.cc --------------------------------------------------------------------------------- #include #include #include #include typedef double vec3[3]; double frand(void){return ((rand()-(RAND_MAX/2))/(RAND_MAX/2.));} double dot(vec3 v1,vec3 v2){ return v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2];} double length(vec3 v){ return sqrt(v[0]*v[0]+v[1]*v[1]+v[2]*v[2]); } double length(vec3 v1,vec3 v2) { vec3 v; v[0] = v2[0] - v1[0]; v[1] = v2[1] - v1[1]; v[2] = v2[2] - v1[2]; return length(v); } double get_coulomb_energy(int N,vec3 p[]) { double e = 0; for(int i = 0;i \n"); fprintf(stderr,"output is printed in VRML format to stdout\n"); fprintf(stderr,"example of usage: points_on_sphere 10 1000 > dist10.wrl \n"); fprintf(stderr,"\nAuthor: V.Bulatov@ic.ac.uk \n\n"); exit(-1); } N = atoi(argv[1]); if(argc > 2) Nstep = atoi(argv[2]); vec3 *p0 = new vec3[N]; vec3 *p1 = new vec3[N]; vec3 *f = new vec3[N]; int i,k; vec3 *pp0 = p0, *pp1 = p1; srand(time(NULL)); for(i = 0; i= e0){ // not successfull step step /= 2; if(step < minimal_step) break; continue; } else { // successfull step vec3 *t = pp0; pp0 = pp1; pp1 = t; e0 = e; step*=2; } fprintf(stderr,"\rn: %5d, e = %18.8f step = %12.10f",k,e,step); fflush(stderr); } fprintf(stdout,"#VRML V1.0 ascii\n"); fprintf(stdout,"Separator {\n"); fprintf(stdout,"Material {diffuseColor 1 1 0 specularColor 1 1 1}\n"); for(i = 0;i