Browse the notebook

Category: graphics algorithms

Distance Render

var verts:Vector.<Number> = new Vector.<Number>();
var pVerts:Vector.<Number> = new Vector.<Number>();
var uvts:Vector.<Number> = new Vector.<Number>();

var hs:Number = 2.3;
var step:Number = 0.04;

var tVerts:Vector.<Number> = new Vector.<Number>();
var rVerts:Vector.<Number> = new Vector.<Number>();
var matrix:Matrix3D = new Matrix3D();
matrix.identity();
matrix.appendRotation(45,Vector3D.Y_AXIS);
matrix.appendRotation(45,Vector3D.X_AXIS);
var inc:int = 0;
var i:Number, j:Number, k:Number;
i = hs;
while( i > -hs){
	j = hs;
	while(j > -hs){
		k = hs;
		while(k > -hs){
			tVerts[inc] = -i;
			inc++
			tVerts[inc] = -j;
			inc++
			tVerts[inc] = -k;
			inc++
			k -= step;
		}
		j -= step;
	}
	i -= step;
}

matrix.transformVectors(tVerts, rVerts);
 
var vinc:int = 0;
inc = 0
var R:Number = 1.5;
var r:Number = .5;
for (i= -hs; i<hs; i+=step){
	for (j = -hs; j<hs; j+=step){
		for (k = -hs; k<hs; k+=step){
			var vx:Number = rVerts[inc] ;
			inc++
			var vy:Number = rVerts[inc]  ;
			inc++
			var vz:Number=  rVerts[inc] ;
			inc++
			var s:Number = Math.pow(vx  * vx  + vy * vy + vz * vz + R*R - r * r, 2) - 4 * (R * R)*(vx * vx + vy * vy); 
			if (s <0 && s > -.5){ 
				verts[vinc] = (i * 50);
				vinc++
				verts[vinc] = (j * 50);
				vinc++
				verts[vinc] = (k * 50);
				vinc++
				  inc += int((hs - k) / step) * 3;
				  k = hs;
			 }
		}
	}
}

var canvas:BitmapData = new BitmapData(400,400,false, 0x000000);
addChild(new Bitmap(canvas));
render();
function render():void{
	matrix.identity();
    matrix.appendTranslation(200, 200, 0);
	Utils3D.projectVectors(matrix, verts, pVerts, uvts);
	canvas.lock();
	canvas.fillRect(canvas.rect, 0x000000);
	var inc:int = 2;
	var c:int = 0;
	var r:Rectangle = new Rectangle();
	r.width = r.height = 2;
	for (var i:int = 0; i<pVerts.length; i+=2){
		  r.x = pVerts[i];
		  r.y = pVerts[i + 1];
		  c = Math.max(0,100 - verts[inc]);
		  canvas.fillRect(r, c << 16 | c << 8 | c);
		  inc += 3; 
	}
	canvas.unlock();
}

This snippet uses some of the techniques from the last few posts to create a distance render – this renders the implicit equation for a torus.

Read snippet: Distance Render

Parametric UV Surface

var matrix:Matrix3D = new Matrix3D();
var verts:Vector.<Number> = new Vector.<Number>();
var pVerts:Vector.<Number> = new Vector.<Number>();
var uvts:Vector.<Number> = new Vector.<Number>();
var sqrt2:Number = Math.sqrt(2)
var pi:Number = Math.PI;
var pi23:Number= 2 * Math.PI / 3;
var step:Number= pi / 50;
for (var u:Number = -pi; u<pi; u+=step) {
	for (var v:Number = -pi; v<pi; v+=step) {
		// from here http://local.wasp.uwa.edu.au/~pbourke/geometry/hexatorus/
		var px = Math.sin(u) / Math.abs(sqrt2+ Math.cos(v))
        var py = Math.sin(u+pi23) / Math.abs(sqrt2 +Math.cos(v + pi23))
        var pz = Math.cos(u-pi23) / Math.abs(sqrt2 +Math.cos(v - pi23))
		verts.push(px * 50);
		verts.push(py * 50);
		verts.push(pz * 50);
	}
}
var brush:BitmapData=new BitmapData(3,2,true,0x41FFFFFF);
var canvas:BitmapData=new BitmapData(400,400,false,0x000000);
addChild(new Bitmap(canvas));
var dx:Number=0;
var dy:Number=0;
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
	dx += (mouseX - dx)/4;
	dy += (mouseY - dy)/4;
	matrix.identity();
	matrix.appendRotation(dy,Vector3D.X_AXIS);
	matrix.appendRotation(dx,Vector3D.Y_AXIS);
	matrix.appendTranslation(200, 200, 0);
	Utils3D.projectVectors(matrix, verts, pVerts, uvts);
	canvas.lock();
	canvas.fillRect(canvas.rect, 0x000000);
	var p = new Point();
	for (var i:int = 0; i<pVerts.length; i+=2) {
		p.x = pVerts[i];
		p.y = pVerts[i+1];
		canvas.copyPixels(brush, brush.rect, p, null, null, true);
	}
	canvas.unlock();
}

More 3D shapes inspired by (taken from) Paul Bourke’s website. I figured I should probably add a parametric 3D surface to this set of posts – so I chose to plot the Triaxial Hexatorus. It’s important to note that U and V go from -PI to PI.

I googled Triaxial Hexatorus and stumbled upon a great papervision demo that creates meshes using parametric equations – it also morphs between shapes.

I also noticed that I don’t need to populate the uvts or pVerts Vectors with zeros – seems to work fine without doing that.

Read snippet: Parametric UV Surface

Wormhole

var matrix:Matrix3D = new Matrix3D();
var verts:Vector.<Number> = new Vector.<Number>();
var pVerts:Vector.<Number> = new Vector.<Number>();
var uvts:Vector.<Number> = new Vector.<Number>();
for (var i:Number = -10; i<10; i+=.04) {
	for (var j:Number = -5; j<8; j+=.04) {
		for (var k:Number = -10; k<10; k+=.04) {
			var s:Number =  i * i * j + j * k * k;
			if (s <10 && s > 9.95) {
				verts.push(i * 20);
				verts.push(j * 20);
				verts.push(k * 20);
				pVerts.push(0),pVerts.push(0);
				uvts.push(0),uvts.push(0),uvts.push(0);
			}
		}
	}
}
var brush:BitmapData=new BitmapData(3,2,true,0x41FFFFFF);
var canvas:BitmapData=new BitmapData(400,400,false,0x000000);
addChild(new Bitmap(canvas));
var dx:Number=0;
var dy:Number=0;
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
	dx += (mouseX - dx)/4;
	dy += (mouseY - dy)/4;
	matrix.identity();
	matrix.appendRotation(dy,Vector3D.X_AXIS);
	matrix.appendRotation(dx,Vector3D.Y_AXIS);
	matrix.appendTranslation(200, 200, 0);
	Utils3D.projectVectors(matrix, verts, pVerts, uvts);
	canvas.lock();
	canvas.fillRect(canvas.rect, 0x000000);
	var p = new Point();
	for (var i:int = 0; i<pVerts.length; i+=2) {
		p.x = pVerts[i];
		p.y = pVerts[i+1];
		canvas.copyPixels(brush, brush.rect, p, null, null, true);
	}
	canvas.unlock();
}

Yet another variation on the post from the last two days. This one plots something resembling a wormhole – I was randomly tweaking the equation for a sphere and stumbled upon this…

Read snippet: Wormhole

Kusner-Schmitt (Tetrahedral Implicit Surface)

var matrix:Matrix3D = new Matrix3D();
var verts:Vector.<Number> = new Vector.<Number>();
var pVerts:Vector.<Number> = new Vector.<Number>();
var uvts:Vector.<Number> = new Vector.<Number>();
for (var i:Number = -2; i<2; i+=.02) {
	for (var j:Number = -2; j<2; j+=.02) {
		for (var k:Number = -2; k<2; k+=.02) {
            var s:Number = (i * i + 3) * (j * j + 3) * (k * k + 3) - 32 * (i *j *k + 1);
			if (s<0&&s>-.2) {
				verts.push(i * 100);
				verts.push(j * 100);
				verts.push(k * 100);
				pVerts.push(0),pVerts.push(0);
				uvts.push(0),uvts.push(0),uvts.push(0);
			}
		}
	}
}
var brush:BitmapData=new BitmapData(3,2,true,0x41FFFFFF);
var canvas:BitmapData=new BitmapData(400,400,false,0x000000);
addChild(new Bitmap(canvas));
var dx:Number=0;
var dy:Number=0;
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
	dx += (mouseX - dx)/4;
	dy += (mouseY - dy)/4;
	matrix.identity();
	matrix.appendRotation(dy,Vector3D.X_AXIS);
	matrix.appendRotation(dx,Vector3D.Y_AXIS);
	matrix.appendTranslation(200, 200, 0);
	Utils3D.projectVectors(matrix, verts, pVerts, uvts);
	canvas.lock();
	canvas.fillRect(canvas.rect, 0x000000);
	var p = new Point();
	for (var i:int = 0; i<pVerts.length; i+=2) {
		p.x = pVerts[i];
		p.y = pVerts[i+1];
		canvas.copyPixels(brush, brush.rect, p, null, null, true);
	}
	canvas.unlock();
}

The same as yesterdays with a different plot from Paul Bourke’s website.

Read snippet: Kusner-Schmitt (Tetrahedral Implicit Surface)

Implicit 3D Plot

var matrix:Matrix3D = new Matrix3D();
var verts:Vector.<Number> = new Vector.<Number>();
var pVerts:Vector.<Number> = new Vector.<Number>();
var uvts:Vector.<Number> = new Vector.<Number>();
for (var i:Number = -2; i<2; i+=.04) {
	for (var j:Number = -2; j<2; j+=.04) {
		for (var k:Number = -2; k<2; k+=.04) {
			// blobby, from here www.iiit.net/techreports/ImplicitTR.pdf
var s:Number=i*i+j*j+k*k+Math.sin(4*i)-Math.cos(4*j)+Math.sin(4*k)-1;
			if (s<0&&s>-.2) {
				verts.push(i * 60);
				verts.push(j * 60);
				verts.push(k * 60);
				pVerts.push(0),pVerts.push(0);
				uvts.push(0),uvts.push(0),uvts.push(0);
			}
		}
	}
}
var brush:BitmapData=new BitmapData(3,2,true,0x41FFFFFF);
var canvas:BitmapData=new BitmapData(400,400,false,0x000000);
addChild(new Bitmap(canvas));
var dx:Number=0;
var dy:Number=0;
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
	dx += (mouseX - dx)/4;
	dy += (mouseY - dy)/4;
	matrix.identity();
	matrix.appendRotation(dy,Vector3D.X_AXIS);
	matrix.appendRotation(dx,Vector3D.Y_AXIS);
	matrix.appendTranslation(200, 200, 0);
	Utils3D.projectVectors(matrix, verts, pVerts, uvts);
	canvas.lock();
	canvas.fillRect(canvas.rect, 0x000000);
	var p = new Point();
	for (var i:int = 0; i<pVerts.length; i+=2) {
		p.x = pVerts[i];
		p.y = pVerts[i+1];
		canvas.copyPixels(brush, brush.rect, p, null, null, true);
	}
	canvas.unlock();
}

I was looking at some equations for implicit 3D surfaces in this pdf about raytracing… anyway, I realized I could just modify the Utils3D.projectVectors() code (that I wrote a little while ago) to easily render any of the implicit equations mentioned in the pdf. I also did some experimentation with fake lighting and distance rendering which I may post in the future.

(check out the swf on wonderfl.net)

Here are some stills of the above snippet:

Read snippet: Implicit 3D Plot

Point in Polygon

// function found here:
// http://www.alienryderflex.com/polygon/
function pointInPolygon(x:Number, y:Number, polyX:Array, polyY:Array):Boolean{
	var j:int = polyX.length - 1;
	var oddNodes:Boolean = false;
	for (var i:int=0; i < polyX.length; i++) {
    if (polyY[i] < y && polyY[j] >= y ||  polyY[j] < y && polyY[i] >= y) {

      if (polyX[i] + (y - polyY[i]) / (polyY[j] - polyY[i]) * (polyX[j] - polyX[i]) < x) {
        oddNodes = !oddNodes; 
      }
    }
    j = i; 
  }
  return  oddNodes;
}

// draw an overly complex poly and store all  x y coords
var pX:Array= new Array();
var pY:Array = new Array();
graphics.beginFill(0xCC0000);
for (var i:int = 0; i<60; i++){
	pX[i] = Math.random()*stage.stageWidth;
	pY[i] =Math.random()*stage.stageHeight;
	if (i == 0){
		graphics.moveTo(pX[i], pY[i]);
	}else{
		graphics.lineTo(pX[i], pY[i]);
	}
}
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
	   alpha = 1;
       if (pointInPolygon(mouseX, mouseY, pX, pY)){
		    alpha = .5;
	   }
}

This snippet shows how to test to see if a point is inside a polygon. This may not really be useful as hitTestPoint() is likely faster – however this could be modified for other purposes such as polygon to polygon collision. This algorithm works nicely on all kinds of polygons … convex, concave etc…

I found this algorithm in an article by Darel Rex Finley … here.

I’ve used this function in Processing a few times…

Read snippet: Point in Polygon

Supershapes / Superformula

// Superformula (equations from):
// http://www.geniaal.be/downloads/AMJBOT.pdf
// http://en.wikipedia.org/wiki/Superformula
const TWO_PI:Number = Math.PI * 2;
function superShape(a:Number, b:Number, m:Number, n1:Number, n2:Number, n3:Number, pnt:Point, scale:Number):void{
	var r:Number = 0
	var p:Number = 0;
	var xp:Number = 0, yp:Number = 0;
	while(p <= TWO_PI){
		var ang:Number = m * p / 4;
		with(Math){
			r = pow(pow(abs(cos(ang) / a), n2) + pow(abs(sin(ang) / b), n3),-1/n1);
			xp = r * cos(p);
			yp = r * sin(p);
		}
		p += .01;
		canvas.setPixel(pnt.x + xp *scale, pnt.y + yp * scale,  0xFFFFFF);
	 }
}
// test it out:
var canvas:BitmapData = new BitmapData(700,600,false, 0x000000);
addChild(new Bitmap(canvas, "auto", true));
 
superShape(1, 1, 5, 23, 23, 23, new Point(100,80), 30);
superShape(1, 1, 5, 13, 13, 3, new Point(200,80), 30);
superShape(1, 1, 8, 3, 13, 3, new Point(300,80), 30);
superShape(10,8, 16, 30, 13, 3, new Point(450,80), 30);
superShape(1,1, 1, .5, .5, .5, new Point(100,190), 100);

for (var i:int = 0; i <150; i++){
  superShape(1,1, 2, 1+i/800, 4, 8-i * .1, new Point(550,350), 50);
}
for (i = 0; i <20; i++){
  superShape(1.1,1.2, 6, 2 + i , 4, 9 - i, new Point(200,350), 50);
}

The above snippet demos a function that will draw Supershapes using the Superformula…

From wikipedia:
The Superformula appeared in a work by Johan Gielis. It was obtained by generalizing the superellipse, named and popularized by Piet Hein…

Here is the result of the above code:


You can read more about the Superformula here in the original paper by Gielis.

wikipedia entry…

3d Supershapes by Paul Bourke

Read snippet: Supershapes / Superformula

Closed Catmull-Rom

var canvas:BitmapData = new BitmapData(400,400,false, 0x000000);
addChild(new Bitmap(canvas));

var pnts:Array = new Array();
// make control points
for (var i:int = 0; i<5; i++){
	var t:Number = i * 72 * Math.PI /180;
	pnts.push(dot(200 + 100 * Math.cos(t),200 +100 * Math.sin(t)));   
}

addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
	canvas.lock();
	canvas.fillRect(canvas.rect, 0x000000);
	curve(pnts);
	canvas.unlock();
}

function tangent(pk1:Sprite, pk_1:Sprite){
	return new Point((pk1.x - pk_1.x) / 2, (pk1.y - pk_1.y) / 2);
}

// all math from http://en.wikipedia.org/wiki/Cubic_Hermite_spline
function curve(p:Array, res:Number=.03):void{
	var px:Number = 0;
    var py:Number = 0;
	var pIter:int = p.length - 1;
	var m:Array = [];
	
	m[0] = tangent(p[1] ,  p[pIter]);
	for (var i:int = 1; i<pIter; i++){
		m[i] = tangent(p[i + 1], p[i - 1]);
	}
	m[pIter] = tangent(p[0],p[pIter-1]);
	
	for (var t:Number = 0; t < 1; t+=res){
		 var t_2:Number = t * t;
		 var _1_t:Number = 1 - t;
		 var _2t:Number = 2 * t;
		 
		 var h00:Number =  (1 + _2t) * (_1_t) * (_1_t);
		 var h10:Number =  t  * (_1_t) * (_1_t);
		 var h01:Number =  t_2 * (3 - _2t);
		 var h11:Number =  t_2 * (t - 1);
		 
		 for (var k:int = 0; k < pIter; k++){
			 var k1:int = k + 1;
			 var pk:Sprite = p[k];
			 var pk1:Sprite = p[k1];
			 var mk:Point = m[k];
			 var mk1:Point = m[k1];
			 px = h00 * pk.x + h10 * mk.x + h01 * pk1.x + h11 * mk1.x;
			 py = h00 * pk.y + h10 * mk.y + h01 * pk1.y + h11 * mk1.y;
			 canvas.setPixel(px, py, 0xFFFFFF);
		 }
		  pk = p[k];
		  pk1 = p[0];
		  mk = m[k];
		  mk1= m[0];
		 
		  px = h00 * pk.x + h10 * mk.x + h01 * pk1.x + h11 * mk1.x;
		  py = h00 * pk.y + h10 * mk.y + h01 * pk1.y + h11 * mk1.y;
		  canvas.setPixel(px, py, 0xFFFFFF);
	}
}

// draggable dot
function dot(xp:Number, yp:Number, col:uint = 0xFF0000, rad:Number=4):Sprite {
	var s:Sprite = Sprite(addChild(new Sprite));
	s.x = xp;
	s.y = yp;
	with(s.graphics) beginFill(col), drawCircle(0,0,rad);
	s.buttonMode = true;
	s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
	return s;
}
function onDrag(evt:MouseEvent):void {
	evt.currentTarget.startDrag()
}
stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
function onUp(evt:MouseEvent):void{
	stopDrag();
}

This a variation on a post from a few days ago. This shows how to create a closed Catmull Rom spline.

See the other Catmull-Rom related Posts

Read snippet: Closed Catmull-Rom

k-th Order Catmull-Rom Spline

var canvas:BitmapData = new BitmapData(400,400,false, 0x000000);
addChild(new Bitmap(canvas));
var pnts:Array = new Array();
// make 8 control points
for (var i:int = 0; i<8; i++){
	pnts.push(dot(50 + i * (30 + Math.random()*10),
							 50 + i * (30 + Math.random()*10)));
}
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
	canvas.lock();
	canvas.fillRect(canvas.rect, 0x000000);
	curve(pnts);
	canvas.unlock();
}
function tangent(pk1:Sprite, pk_1:Sprite){
	return new Point((pk1.x - pk_1.x) / 2, (pk1.y - pk_1.y) / 2);
}
// all math from http://en.wikipedia.org/wiki/Cubic_Hermite_spline
function curve(p:Array, res:Number=.03):void{
	var px:Number = 0;
	var py:Number = 0;
	var pIter:int = p.length - 1;
	var m:Array = [];
	m[0] = tangent(p[1], p[0]);
	for (var i:int = 1; i<pIter; i++){
		m[i] = tangent(p[i + 1], p[i - 1]);
	}
	m[pIter] = tangent(p[pIter], p[pIter - 1]);
	for (var t:Number = 0; t <1; t+=res){
		 var t_2:Number = t * t;
		 var _1_t:Number = 1 - t;
		 var _2t:Number = 2 * t;
		 var h00:Number =  (1 + _2t) * (_1_t) * (_1_t);
		 var h10:Number =  t  * (_1_t) * (_1_t);
		 var h01:Number =  t_2 * (3 - _2t);
		 var h11:Number =  t_2 * (t - 1);
		 for (var k:int = 0; k <pIter; k++){
			 var k1:int = k + 1;
			 var pk:Sprite = p[k];
			 var pk1:Sprite = p[k1];
			 var mk:Point = m[k];
			 var mk1:Point = m[k1];
			 px = h00 * pk.x + h10 * mk.x + h01 * pk1.x + h11 * mk1.x;
			 py = h00 * pk.y + h10 * mk.y + h01 * pk1.y + h11 * mk1.y;
			 canvas.setPixel(px, py, 0xFFFFFF);
		 }
	}
}
// draggable dot
function dot(xp:Number, yp:Number, col:uint = 0xFF0000, rad:Number=4):Sprite {
	var s:Sprite = Sprite(addChild(new Sprite));
	s.x = xp;
	s.y = yp;
	with(s.graphics) beginFill(col), drawCircle(0,0,rad);
	s.buttonMode = true;
	s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
	return s;
}
function onDrag(evt:MouseEvent):void {
	evt.currentTarget.startDrag()
}
stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
function onUp(evt:MouseEvent):void{
	stopDrag();
}

More Catmull-Rom stuff. This one can have any number of control points:


Check it out here:

Read snippet: k-th Order Catmull-Rom Spline