Procedurally-Generated Sphere
The most common way to obtain the geometry of a 3D model is from a file output from a modeling package like 3D Studio Max, Maya, or Blender, but it’s not the only way. In the case of simpler forms of geometry it is practical to generate it yourself using AS3 code. When you do this you eliminate the needed download and gain the flexibility to scale up or down the complexity of the model on a whim. Today’s article shows some AS3 code to generate spheres for all kinds of uses: planets in space simulators, placeholders for debugging physics simulations, and whatever else you can dream up.
The process of procedurally generating a sphere into triangles for rendering via Stage3D
is known as tessellation. The goal is to approximate the sphere and provide a parameter for the trade-off between more smoothness (quality) and more triangles to render (slow). The way I’ve gone about this is to split the sphere into three parts:
- The middle: a ring of rectangles
- The top: a triangle fan from the top point of the sphere to the top of the “middle”
- The bottom: a triangle fan from the bottom point of the sphere to the bottom of the “middle”
There are two parameters controlling the smoothness of the sphere:
- Slices: number of vertical slices through the sphere determining the number of columns of rectangles that are in the “middle” and how many triangles are in each triangle fan of the “top” and “bottom”
- Stacks: number of horizontal slices through the sphere determining the number of rows of rectangles that are in the “middle”
For casual usage, you can simply pass the same value for both. There is a minimum of three slices and stacks in order to get a valid (e.g. fully enclosed) shape and that will use a scant 54 triangles. The quality increases quickly and you’re only limited by the Context3D
maximum triangle count as far as pushing the number of slices and stacks goes. Here are some sample screenshots at different numbers of slices and stacks:
3 slices, 3 stacks:
4 slices, 4 stacks:
5 slices, 5 stacks:
6 slices, 6 stacks:
7 slices, 7 stacks:
20 slices, 20 stacks:
Here’s the code for the Sphere3D
class that does the procedural generation:
package { import flash.geom.Matrix3D; import flash.display3D.IndexBuffer3D; import flash.display3D.VertexBuffer3D; import flash.display3D.Context3D; /** * A procedurally-generated sphere * @author Jackson Dunstan */ public class Sphere3D { /** Minimum number of horizontal slices any sphere can have */ public static const MIN_SLICES:uint = 3; /** Minimum number of vertical stacks any sphere can have */ public static const MIN_STACKS:uint = 3; /** Positions of the vertices of the sphere */ public var positions:VertexBuffer3D; /** Texture coordinates of the vertices of the sphere */ public var texCoords:VertexBuffer3D; /** Triangles of the sphere */ public var tris:IndexBuffer3D; /** Matrix transforming the sphere from model space to world space */ public var modelToWorld:Matrix3D; /** * Procedurally generate the sphere * @param context 3D context to generate the sphere in * @param slices Number of vertical slices around the sphere. Clamped to at least * MIN_SLICES. Increasing this will increase the smoothness of the sphere at * the cost of generating more vertices and triangles. * @param stacks Number of horizontal slices around the sphere. Clamped to at least * MIN_STACKS. Increasing this will increase the smoothness of the sphere at * the cost of generating more vertices and triangles. */ public function Sphere3D( context:Context3D, slices:uint, stacks:uint, posX:Number=0, posY:Number=0, posZ:Number=0, scaleX:Number=1, scaleY:Number=1, scaleZ:Number=1 ) { // Make the model->world transformation matrix to position and scale the sphere modelToWorld = new Matrix3D( new <Number>[ scaleX, 0, 0, posX, 0, scaleY, 0, posY, 0, 0, scaleZ, posZ, 0, 0, 0, 1 ] ); // Cap parameters if (slices < MIN_SLICES) { slices = MIN_SLICES; } if (stacks < MIN_STACKS) { stacks = MIN_STACKS; } // Data we will later upload to the GPU var positions:Vector.<Number>; var texCoords:Vector.<Number>; var tris:Vector.<uint>; // Pre-compute many constants used in tesselation const stepTheta:Number = (2.0*Math.PI) / slices; const stepPhi:Number = Math.PI / stacks; const stepU:Number = 1.0 / slices; const stepV:Number = 1.0 / stacks; const verticesPerStack:uint = slices + 1; const numVertices:uint = verticesPerStack * (stacks+1); // Allocate the vectors of data to tesselate into positions = new Vector.<Number>(numVertices*3); texCoords = new Vector.<Number>(numVertices*2); tris = new Vector.<uint>(slices*stacks*6); // Pre-compute half the sin/cos of thetas var halfCosThetas:Vector.<Number> = new Vector.<Number>(verticesPerStack); var halfSinThetas:Vector.<Number> = new Vector.<Number>(verticesPerStack); var curTheta:Number = 0; for (var slice:uint; slice < verticesPerStack; ++slice) { halfCosThetas[slice] = Math.cos(curTheta) * 0.5; halfSinThetas[slice] = Math.sin(curTheta) * 0.5; curTheta += stepTheta; } // Generate positions and texture coordinates var curV:Number = 1.0; var curPhi:Number = Math.PI; var posIndex:uint; var texCoordIndex:uint; for (var stack:uint = 0; stack < stacks+1; ++stack) { var curU:Number = 1.0; var curY:Number = Math.cos(curPhi) * 0.5; var sinCurPhi:Number = Math.sin(curPhi); for (slice = 0; slice < verticesPerStack; ++slice) { positions[posIndex++] = halfCosThetas[slice]*sinCurPhi; positions[posIndex++] = curY; positions[posIndex++] = halfSinThetas[slice] * sinCurPhi; texCoords[texCoordIndex++] = curU; texCoords[texCoordIndex++] = curV; curU -= stepU; } curV -= stepV; curPhi -= stepPhi; } // Generate tris var lastStackFirstVertexIndex:uint = 0; var curStackFirstVertexIndex:uint = verticesPerStack; var triIndex:uint; for (stack = 0; stack < stacks; ++stack) { for (slice = 0; slice < slices; ++slice) { // Bottom tri of the quad tris[triIndex++] = lastStackFirstVertexIndex + slice + 1; tris[triIndex++] = curStackFirstVertexIndex + slice; tris[triIndex++] = lastStackFirstVertexIndex + slice; // Top tri of the quad tris[triIndex++] = lastStackFirstVertexIndex + slice + 1; tris[triIndex++] = curStackFirstVertexIndex + slice + 1; tris[triIndex++] = curStackFirstVertexIndex + slice; } lastStackFirstVertexIndex += verticesPerStack; curStackFirstVertexIndex += verticesPerStack; } // Create vertex and index buffers this.positions = context.createVertexBuffer(positions.length/3, 3); this.positions.uploadFromVector(positions, 0, positions.length/3); this.texCoords = context.createVertexBuffer(texCoords.length/2, 2); this.texCoords.uploadFromVector(texCoords, 0, texCoords.length/2); this.tris = context.createIndexBuffer(tris.length); this.tris.uploadFromVector(tris, 0, tris.length); } public static function computeNumTris(slices:uint, stacks:uint): uint { if (slices < MIN_SLICES) { slices = MIN_SLICES; } if (stacks < MIN_STACKS) { stacks = MIN_STACKS; } return slices*stacks*6; } public function dispose(): void { this.positions.dispose(); this.texCoords.dispose(); this.tris.dispose(); } } }
And here is a little app to try out the spheres:
package { import com.adobe.utils.*; import flash.display.*; import flash.display3D.*; import flash.display3D.textures.*; import flash.events.*; import flash.geom.*; import flash.text.*; import flash.utils.*; public class ProceduralSphere extends Sprite { /** Number of degrees to rotate per millisecond */ private static const ROTATION_SPEED:Number = 1; /** Axis to rotate about */ private static const ROTATION_AXIS:Vector3D = new Vector3D(0, 1, 0); /** UI Padding */ private static const PAD:Number = 5; /** Distance between spheres */ private static const SPHERE_SPACING:Number = 1.5; [Embed(source="earth.jpg")] private static const TEXTURE:Class; /** Temporary matrix to avoid allocation during drawing */ private static const TEMP_DRAW_MATRIX:Matrix3D = new Matrix3D(); /** 3D context to draw with */ private var context3D:Context3D; /** Shader program to draw with */ private var program:Program3D; /** Texture of all spheres */ private var texture:Texture; /** Camera viewing the 3D scene */ private var camera:Camera3D; /** Spheres to draw */ private var spheres:Vector.<Sphere3D> = new Vector.<Sphere3D>(); /** Current rotation of all spheres (degrees) */ private var rotationDegrees:Number = 0; /** Number of rows of spheres */ private var rows:uint = 1; /** Number of columns of spheres */ private var cols:uint = 2; /** Number of layers of spheres */ private var layers:uint = 3; /** Smoothness of a sphere */ private var smoothness:uint = 10; /** Framerate display */ private var fps:TextField = new TextField(); /** Last time the framerate display was updated */ private var lastFPSUpdateTime:uint; /** Time when the last frame happened */ private var lastFrameTime:uint; /** Number of frames since the framerate display was updated */ private var frameCount:uint; /** 3D rendering driver display */ private var driver:TextField = new TextField(); /** Simulation statistics display */ private var stats:TextField = new TextField(); /** * Entry point */ public function ProceduralSphere() { stage.align = StageAlign.TOP_LEFT; stage.scaleMode = StageScaleMode.NO_SCALE; stage.frameRate = 60; var stage3D:Stage3D = stage.stage3Ds[0]; stage3D.addEventListener(Event.CONTEXT3D_CREATE, onContextCreated); stage3D.requestContext3D(Context3DRenderMode.AUTO); } protected function onContextCreated(ev:Event): void { // Setup context var stage3D:Stage3D = stage.stage3Ds[0]; stage3D.removeEventListener(Event.CONTEXT3D_CREATE, onContextCreated); context3D = stage3D.context3D; context3D.configureBackBuffer( stage.stageWidth, stage.stageHeight, 0, true ); // Setup camera camera = new Camera3D( 0.1, // near 100, // far stage.stageWidth / stage.stageHeight, // aspect ratio 40*(Math.PI/180), // vFOV 0, 2, 5, // position 0, 0, 0, // target 0, 1, 0 // up dir ); // Setup UI fps.background = true; fps.backgroundColor = 0xffffffff; fps.autoSize = TextFieldAutoSize.LEFT; fps.text = "Getting FPS..."; addChild(fps); driver.background = true; driver.backgroundColor = 0xffffffff; driver.text = "Driver: " + context3D.driverInfo; driver.autoSize = TextFieldAutoSize.LEFT; driver.y = fps.height; addChild(driver); stats.background = true; stats.backgroundColor = 0xffffffff; stats.text = "Getting stats..."; stats.autoSize = TextFieldAutoSize.LEFT; stats.y = driver.y + driver.height; addChild(stats); makeButtons( "Move Forward", "Move Backward", null, "Move Left", "Move Right", null, "Move Up", "Move Down", null, "Yaw Left", "Yaw Right", null, "Pitch Up", "Pitch Down", null, "Roll Left", "Roll Right", null, null, "-Rows", "+Rows", null, "-Cols", "+Cols", null, "-Layers", "+Layers", null, "-Smoothness", "+Smoothness" ); var assembler:AGALMiniAssembler = new AGALMiniAssembler(); // Vertex shader var vertSource:String = "m44 op, va0, vc0\nmov v0, va1\n"; assembler.assemble(Context3DProgramType.VERTEX, vertSource); var vertexShaderAGAL:ByteArray = assembler.agalcode; // Fragment shader var fragSource:String = "tex oc, v0, fs0 <2d,linear,mipnone>"; assembler.assemble(Context3DProgramType.FRAGMENT, fragSource); var fragmentShaderAGAL:ByteArray = assembler.agalcode; // Shader program program = context3D.createProgram(); program.upload(vertexShaderAGAL, fragmentShaderAGAL); // Setup textures var bmd:BitmapData = (new TEXTURE() as Bitmap).bitmapData; texture = context3D.createTexture( bmd.width, bmd.height, Context3DTextureFormat.BGRA, true ); texture.uploadFromBitmapData(bmd); makeSpheres(); // Start the simulation addEventListener(Event.ENTER_FRAME, onEnterFrame); } private function makeSpheres(): void { for each (var sphere:Sphere3D in spheres) { sphere.dispose(); } spheres.length = 0; var beforeTime:int = getTimer(); for (var row:int = 0; row < rows; ++row) { for (var col:int = 0; col < cols; ++col) { for (var layer:int = 0; layer < layers; ++layer) { spheres.push( new Sphere3D( context3D, smoothness, smoothness, col*SPHERE_SPACING, row*SPHERE_SPACING, -layer*SPHERE_SPACING ) ); } } } var afterTime:int = getTimer(); var totalTime:int = afterTime - beforeTime; var trisEach:uint = Sphere3D.computeNumTris(smoothness, smoothness); var numSpheres:uint = rows*cols*layers; stats.text = "Spheres: (rows=" + rows + ", cols=" + cols + ", layers=" + layers + ", total=" + numSpheres + ")" + "\n" + "Tris: (each=" + trisEach + ", total=" + (trisEach*numSpheres) + ")" + "\n" + "Generation Time: (each=" + (Number(totalTime)/numSpheres).toFixed(3) + ", total=" + totalTime + ") ms."; } private function makeButtons(...labels): Number { var curX:Number = PAD; var curY:Number = stage.stageHeight - PAD; for each (var label:String in labels) { if (label == null) { curX = PAD; curY -= button.height + PAD; continue; } var tf:TextField = new TextField(); tf.mouseEnabled = false; tf.selectable = false; tf.defaultTextFormat = new TextFormat("_sans"); tf.autoSize = TextFieldAutoSize.LEFT; tf.text = label; tf.name = "lbl"; var button:Sprite = new Sprite(); button.buttonMode = true; button.graphics.beginFill(0xF5F5F5); button.graphics.drawRect(0, 0, tf.width+PAD, tf.height+PAD); button.graphics.endFill(); button.graphics.lineStyle(1); button.graphics.drawRect(0, 0, tf.width+PAD, tf.height+PAD); button.addChild(tf); button.addEventListener(MouseEvent.CLICK, onButton); if (curX + button.width > stage.stageWidth - PAD) { curX = PAD; curY -= button.height + PAD; } button.x = curX; button.y = curY - button.height; addChild(button); curX += button.width + PAD; } return curY - button.height; } public static function makeCheckBox( label:String, checked:Boolean, callback:Function, labelFormat:TextFormat=null): Sprite { var sprite:Sprite = new Sprite(); var tf:TextField = new TextField(); tf.autoSize = TextFieldAutoSize.LEFT; tf.text = label; tf.background = true; tf.backgroundColor = 0xffffff; tf.selectable = false; tf.mouseEnabled = false; tf.setTextFormat(labelFormat || new TextFormat("_sans")); sprite.addChild(tf); var size:Number = tf.height; var background:Shape = new Shape(); background.graphics.beginFill(0xffffff); background.graphics.drawRect(0, 0, size, size); background.x = tf.width + PAD; sprite.addChild(background); var border:Shape = new Shape(); border.graphics.lineStyle(1, 0x000000); border.graphics.drawRect(0, 0, size, size); border.x = background.x; sprite.addChild(border); var check:Shape = new Shape(); check.graphics.lineStyle(1, 0x000000); check.graphics.moveTo(0, 0); check.graphics.lineTo(size, size); check.graphics.moveTo(size, 0); check.graphics.lineTo(0, size); check.x = background.x; check.visible = checked; sprite.addChild(check); sprite.addEventListener( MouseEvent.CLICK, function(ev:MouseEvent): void { checked = !checked; check.visible = checked; callback(checked); } ); return sprite; } private function onButton(ev:MouseEvent): void { var mode:String = ev.target.getChildByName("lbl").text; switch (mode) { case "Move Forward": camera.moveForward(1); break; case "Move Backward": camera.moveBackward(1); break; case "Move Left": camera.moveLeft(1); break; case "Move Right": camera.moveRight(1); break; case "Move Up": camera.moveUp(1); break; case "Move Down": camera.moveDown(1); break; case "Yaw Left": camera.yaw(-10); break; case "Yaw Right": camera.yaw(10); break; case "Pitch Up": camera.pitch(-10); break; case "Pitch Down": camera.pitch(10); break; case "Roll Left": camera.roll(10); break; case "Roll Right": camera.roll(-10); break; case "-Rows": if (rows > 1) { rows--; makeSpheres(); } break; case "+Rows": rows++; makeSpheres(); break; case "-Cols": if (cols > 1) { cols--; makeSpheres(); } break; case "+Cols": cols++; makeSpheres(); break; case "-Layers": if (layers > 1) { layers--; makeSpheres(); } break; case "+Layers": layers++; makeSpheres(); break; case "-Smoothness": if (smoothness > Math.max(Sphere3D.MIN_SLICES, Sphere3D.MIN_STACKS)) { smoothness--; makeSpheres(); } break; case "+Smoothness": smoothness++; makeSpheres(); break; } } private function onEnterFrame(ev:Event): void { // Set up rendering context3D.setProgram(program); context3D.setTextureAt(0, texture); context3D.clear(0.5, 0.5, 0.5); // Draw spheres var worldToClip:Matrix3D = camera.worldToClipMatrix; var drawMatrix:Matrix3D = TEMP_DRAW_MATRIX; for each (var sphere:Sphere3D in spheres) { context3D.setVertexBufferAt(0, sphere.positions, 0, Context3DVertexBufferFormat.FLOAT_3); context3D.setVertexBufferAt(1, sphere.texCoords, 0, Context3DVertexBufferFormat.FLOAT_2); sphere.modelToWorld.copyToMatrix3D(drawMatrix); drawMatrix.appendRotation(rotationDegrees, ROTATION_AXIS); drawMatrix.prepend(worldToClip); context3D.setProgramConstantsFromMatrix( Context3DProgramType.VERTEX, 0, drawMatrix, false ); context3D.drawTriangles(sphere.tris); } context3D.present(); rotationDegrees += ROTATION_SPEED; // Update stat displays frameCount++; var now:int = getTimer(); var elapsed:int = now - lastFPSUpdateTime; if (elapsed > 1000) { var framerateValue:Number = 1000 / (elapsed / frameCount); fps.text = "FPS: " + framerateValue.toFixed(1); lastFPSUpdateTime = now; frameCount = 0; } lastFrameTime = now; } } }
Here’s the test earth texture:
Spot a bug? Have a question or suggestion? Post a comment!
#1 by orion elenzil on July 10th, 2012 ·
nice.
on a slightly different topic,
sometimes you want to generate spheres of randomly-placed points, where the distribution is ‘even’ or ‘uniform’,
without the concentration of points at the poles which the above approach yields.
(this can be useful in particle systems, ray-tracing, calculating ambient occlusion, etc)
i discuss a way to do this in O(N) here: http://elenzil.com/progs/randompoints .
#2 by Deepak on July 18th, 2016 ·
hi
great class and algorithm.
I am having some difficulties in adopting your algorithm of sphere generation into my code as my previous code was giving little bit distorted uv at some places.
I need to just allocate and fill some texture,vertex and index arrays so did little bit modifications to your code and I am doing as below :
public void Sphere3D(//context:Context3D,
int slices,
int stacks)
// double posX, double posY,double posZ,
// double scaleX, double scaleY,double scaleZ)
{
// Make the model->world transformation matrix to position and scale the sphere
// Cap parameters
if (slices < MIN_SLICES)
{
slices = MIN_SLICES;
}
if (stacks < MIN_STACKS)
{
stacks = MIN_STACKS;
}
// Data we will later upload to the GPU
//var positions:Vector.;
//var texCoords:Vector.;
//var tris:Vector.;
// Pre-compute many constants used in tesselation
final double stepTheta = (2.0*Math.PI) / slices;
final double stepPhi = Math.PI / stacks;
final double stepU = 1.0 / slices;
final double stepV = 1.0 / stacks;
final int verticesPerStack = slices + 1;
final int numVertices = verticesPerStack * (stacks+1)*2;
// Allocate the vectors of data to tesselate into
//positions = new Vector.(numVertices*3);
mVertices=new float[numVertices*3];
//texCoords = new Vector.(numVertices*2);
mTexture=new float[numVertices*2];
//tris = new Vector.(slices*stacks*6);
mIndexes= new short[slices*stacks*6];
// Pre-compute half the sin/cos of thetas
double halfCosThetas[] = new double[verticesPerStack];
double halfSinThetas[] = new double[verticesPerStack];
int curTheta= 0;
for (int slice=0; slice < verticesPerStack; ++slice)
{
halfCosThetas[slice] = Math.cos(curTheta) * 0.5;
halfSinThetas[slice] = Math.sin(curTheta) * 0.5;
curTheta += stepTheta;
}
// Generate positions and texture coordinates
double curV = 1.0;
double curPhi = Math.PI;
int posIndex=0;
int texCoordIndex=0;
for (int stack = 0; stack < stacks+1; ++stack)
{
double curU = 1.0;
double curY = Math.cos(curPhi) * 0.5;
double sinCurPhi = Math.sin(curPhi);
for (int slice = 0; slice < verticesPerStack; ++slice)
{
mVertices[posIndex++] = (float)(halfCosThetas[slice]*sinCurPhi);
mVertices[posIndex++] =(float) curY;
mVertices[posIndex++] = (float)(halfSinThetas[slice] * sinCurPhi);
mTexture[texCoordIndex++] = (float)curU;
mTexture[texCoordIndex++] = (float)curV;
curU -= stepU;
}
curV -= stepV;
curPhi -= stepPhi;
}
// Generate tris
int lastStackFirstVertexIndex= 0;
int curStackFirstVertexIndex = verticesPerStack;
int triIndex=0;
for (int stack = 0; stack < stacks; ++stack)
{
for (int slice = 0; slice < slices; ++slice)
{
// Bottom tri of the quad
mIndexes[triIndex++] = (short)(lastStackFirstVertexIndex + slice + 1);
mIndexes[triIndex++] = (short)(curStackFirstVertexIndex + slice);
mIndexes[triIndex++] = (short)(lastStackFirstVertexIndex + slice);
// Top tri of the quad
mIndexes[triIndex++] =(short)( lastStackFirstVertexIndex + slice + 1);
mIndexes[triIndex++] =(short)( curStackFirstVertexIndex + slice + 1);
mIndexes[triIndex++] =(short)( curStackFirstVertexIndex + slice);
}
lastStackFirstVertexIndex += verticesPerStack;
curStackFirstVertexIndex += verticesPerStack;
}
I am getting half the sphere in right side with correct texture map and missing left half :-(
please help me….