From: s047@SAND.SICS.BU.OZ.AU (Jeremy Lee)
Newsgroups: comp.graphics
Subject: Re: Distributing Points on a Sphere
Date: 18 Apr 92 08:15:37 GMT


	I did this once, with the added complication that I was generating
a fractal planet.
	Begin with a tetrahedron, which is basically a four-sided pyramid
with four vertices and six lines.
	Keep two arrays, one array of points (could be a linked list if
you really want) and another array of triangular facets. Each of the
three entries in the array of facets simply points to a co-ordinate
entry.
	To begin.. You have four points and four facets defined. The
four points have to be equi-distant from the origin if you want to
eventually get a circle.
	To iterate, you start a loop for each facet, which will look
like this:
				*
			       / \
			      /   \
			     /     \
			    *-------*
	Now, you want to divide this into four facets.
This will involve generating three more points, each one is the "midpoint"
of each of the edges of the facet. Calculate this by first, taking the
real 3D midpoint of the two vertices (eg, for the x co-ordinate, add the
x co-ord of the first vertex to the x co-ord of the second and divide
by two, similar for the y & z) so that you have a new vector. Now, if
you are specifically after a sphere, you can first of all normalise this
into a unit vector (by individualy dividing the x,y,z by the length of
the vector =SQR(x*x+y*y+z*z). Then, if you are after a sphere, then
multiply that unit vector by the radius. If (like me) you were not
after a sphere, then multiply it by the average of the lengths of the
two vectors of the vertices that it came from. *whew*
	Anyway, after that, you now have three more point that
lie on the surface of the sphere. Looks like this:
				*
			       / \
			  new *   * new
			     /     \
			    *---*---*
			       new
	Now, here is the tricky bit. Each edge is shared by two facets,
so once you have the new points, then do a linear search through your
array of points to see that it's not already there (if your clever, you
will only check the points that have been generated this iteration. work
out why..) If they are not already there, then add them. If they ae
already there, then remember where. so, now you have the locations in
the array of the three points. You are going to now generate three new
facates, and modify the old one, so that you now have:
				*
			       / \
			      *---*
			     / \ / \
			    *---*---*
	Replace the original facet with the vertices of the top new
facet, and add facets to the array for each of the three bottom ones.
	Do this for every facet that was there originally. You will have
added 3 times the original number of facets but only 1.5 times the
original number of vertices.
	Re-iterate for the number of times you want to.
	If you want to generate fractal planets, then here are a few
hints: 
	After (NOT during) each iteration, perturb each vertex by a random
amount that decreaces each iteration. (If you do this during the
iteration, then common edge midpoints will not match, and things will
begin to go wrong.)
	Make whether you divide up a facet random. You will end up with
a sphere that has some parts which have been subdivided to a greater
degree than others, giving the impression of (triangular) oceans, and
places which appear to be cities.
	If you have a large number of facets, then you can just plot the
verticies as single points. (only the ones with a positive z value, to
simulate hidden point removal)
	You can then animate it by rotation. Looks very effective. My
record is 25 frames per second for 20,000 points (realtime) on my
Archimedes A310.

***********************************************************************
*    . Jeremy Lee s047@sand.sics.bu.oz.au    Student of Everything    *
*   /|            "Where the naked spotless intelect is without       *
*  /_|              center or circumference. Look to the light,       *
* /  |rchimedes      Leland, look to the light" - Dale Cooper         *
***********************************************************************
Newsgroups: comp.graphics