JavaScript metaballs optimization

Question

I created this basic metaball visualization in JavaScript. While it does look nice, it is very slow if you increase number of balls and/or make drawing area larger. I think that the performance is so bad because it iterates through every pixel every time the frame is updated but I cannot think anyway how I could update only those pixels where something has actually happened.

Here's the code:

// canvas

var c = document.getElementById("canvas");
width = c.width = /*window.innerWidth;*/1280;
height = c.height = /*window.innerHeight;*/720;
var ctx = c.getContext("2d");

// imagedata

var imageData = ctx.createImageData(width,height);
var data = imageData.data;

// array for balls

var balls = [];
var num = 20;

// random number generation

function random(min, max){
	var num = Math.floor(Math.random()*(max-min+1)+min);
	return num;	
}

// metaball

function ball() {
	this.posX = random(0, width);
	this.posY = random(0, height);
	this.dx = random(-4,4);
	this.dy = random(-4,4);
	this.radius = random(10, 100);
}

// ball movement

ball.prototype.move = function() {

	if (this.posX > width || this.posX < 0) { // change direction if edge is encountered, x-axis
		this.dx = -(this.dx);
	}

	if (this.posY > height || this.posY < 0 ) { // change direction if edge is encountered, y-axis
		this.dy = -(this.dy);
	}

	this.posX += this.dx; // move balls, x-axis
	this.posY += this.dy; // move balls, y-axis 

}

// create balls and put them into an array

for (i=0; i<num;i++) {
	var metaball = new ball();
	balls.push(metaball);
}

// draw and move metaballs

function Loop(){

	for (var y=0; y<height; y++) {		// loop through draw area pixels, height
		for (var x=0; x<width; x++) {	// loop through draw area pixels, width
			var index = (x+y*width)*4;	// pixel index
			var color = 0;				// pixel color

			for (i=0; i<balls.length; i++) {
				color += balls[i].radius * 10000 / (Math.pow((x - balls[i].posX),2) + Math.pow((y - balls[i].posY),2)); // metaball calculation formula
			}
			
				// assign color to pixel based on previous formula
				data[index+0] = color*1.05;	// r 
				data[index+1] = color;		// g 
				data[index+2] = color*1.4;	// b 
				data[index+3] = 255;		// a
			}
	}

	// move balls

	for (i=0; i<balls.length; i++) {
		balls[i].move();
	}

	// put imagedata on canvas

	ctx.putImageData(imageData, 0,0);

	// animate

	requestAnimationFrame(Loop);
}

// call loop function

Loop();

<!DOCTYPE html>
<html>
<head>
	<title>metaballs</title>

<style type="text/css">

	body {
		padding: 0px;
		margin: 0px;
	}



</style>

</head>
<body>

<div>
	<canvas id="canvas">
	</canvas>
</div>

<script type="text/javascript" src="metaballs.js">
</script>

</body>
</html>

Is there anything I can do to optimize this?

Since I'm a total beginner in JavaScript and programming in general, I would be very happy to hear if there are better practices than what I've used here :)

le_m · Accepted Answer · 2017-04-14 13:25:25Z

Performance optimizations: Retrieving and updating the canvas's imageData each frame is costly. It is far more efficient to precompute the individual balls on "offline" canvases and copy them each frame to your visible canvas via canvas.drawImage. To reproduce the metaball effect, you just need to chose an additive color blending mode by setting context.globalCompositeOperation = "lighter". Limiting the infinite "glow" of the metaballs to a fixed diameter reduces the memory impact.

Keep things local and decoupled: Your ball.prototype.move function requires knowledge about the global width and height parameters. A better solution is to let a dedicated "physics engine" update the positions by integrating their velocities over time and handling barrier collisions. This would also allow you to e.g. add forces between balls and handle ball - ball collisions.

Similarly, the canvas's context should be passed as a parameter instead of being assigned to a global variable. Drawing the balls could be a local method of each ball or being handled by a dedicated "graphics engine". The later allows you to better manage the context's global state - such as context.globalCompositeOperation - and reduce the number of state changes. This would also allow you to e.g. apply global graphic effects or handle occlusion and so on.

Improved code: Featuring 50 textured particles aka "metaballs":

// Create a canvas with given 'width' and 'height':
function createCanvas(width, height) {
  let canvas = document.createElement("canvas");
  canvas.width = width;
  canvas.height = height;
  return canvas;
}

// Draw a "metaball" with diameter 'size': 
function drawBall(ctx, size) {
  let imageData = ctx.getImageData(0, 0, size, size),
    data = imageData.data,
    center = size >> 1,
    radius = size * size;
  for (let x = 0; x < size; ++x) {
    for (let y = 0; y < size; ++y) {
      let dsqr = (x - center) * (x - center) + (y - center) * (y - center),
        color = radius / dsqr - Math.sqrt(dsqr) / size * 10,
        i = (x + y * size) << 2;
      data[i + 0] = color * 1.05;
      data[i + 1] = color;
      data[i + 2] = color * 1.4;
      data[i + 3] = 255;
    }
  }
  ctx.putImageData(imageData, 0, 0);
}

// Create a "metaball" texture with dimensions 'size' x 'size':
function createBallTexture(size) {
  let canvas = createCanvas(size, size),
    ctx = canvas.getContext("2d");
  drawBall(ctx, size);
  return canvas;
}

// A textured particle with position and velocity:
function Particle(texture, x, y, vx = 0, vy = 0) {
  this.texture = texture;
  this.x = x;
  this.y = y;
  this.vx = vx;
  this.vy = vy;
}

// A particle engine holding particles:
function Engine(width = 300, height = 150) {
  this.particles = [];
  this.width = width;
  this.height = height;
}

Engine.prototype.update = function(dt) {
  for (let particle of this.particles) {
    particle.x += particle.vx * dt;
    particle.y += particle.vy * dt;

    if (particle.x > this.width) {
      particle.x = this.width;
      particle.vx = -particle.vx;
    } else if (particle.x < 0) {
      particle.x = 0;
      particle.vx = -particle.vx;
    }

    if (particle.y > this.height) {
      particle.y = this.height;
      particle.vy = -particle.vy;
    } else if (particle.y < 0) {
      particle.y = 0;
      particle.vy = -particle.vy;
    }
  }
}

Engine.prototype.draw = function(ctx) {
  let compositeOperation = ctx.globalCompositeOperation;
  ctx.globalCompositeOperation = "lighter";
  for (let particle of this.particles) {
    ctx.drawImage(
      particle.texture, particle.x - (particle.texture.width >> 1),
      particle.y - (particle.texture.height >> 1)
    );
  }
  ctx.globalCompositeOperation = compositeOperation;
}

// Create particles and their textures:
let canvas = document.getElementById("canvas"),
  ctx = canvas.getContext("2d"),
  engine = new Engine(canvas.width, canvas.height),
  textures = {},
  numParticles = 50;

for (let i = 0; i < numParticles; ++i) {
  let size = Math.pow(2, 8 + Math.random() * 3 | 0);
  textures[size] = textures[size] || createBallTexture(size);
  
  engine.particles.push(new Particle(
    textures[size],
    Math.random() * engine.width,
    Math.random() * engine.height,
    Math.random() - .5,
    Math.random() - .5
  ));
}

// Main loop:
let last = performance.now();
function frame(time) {
  requestAnimationFrame(frame);
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  engine.update(time - last);
  engine.draw(ctx);
  last = time;
}
requestAnimationFrame(frame);

body {
  padding: 0px;
  margin: 0px;
}

#canvas {
  background-color: black;
}

<canvas id="canvas" width="1280" height="720"></canvas>

A few optional micro-optimizations which improve performance of some hotspots that above code incorporates:

Avoid divisions, e.g. write x * .5 instead of x / 2
Use bitwise 32-bit operations on integers, e.g. write x >> 1 instead of Math.floor(x * .5) or x | 0 instead of Math.floor(x).

Further optimization might be possible by computing the meta balls via fragment shaders using a 3D context.

Reducing the canvas's resolution gives you another performance boost at the cost of rendering quality.

Your implementation really is way faster. How about if I wanted, for whatever reason, to do this without using canvas blending modes? In that case, I guess I would have to check if particles are close to each other or overlap and add color values together. Would it be feasible and would it perform as well? — Kilipukki, Commented May 3, 2017 at 18:02
@Kilipukki You could get the canvas image data via ctx.getImageData once at the beginning, manually add the metaballs and put the image data back to the context on each frame (manual implementation of the lighter blend mode). This is much slower. If you can't use blending modes but webgl, I recommend the shader approach. — le_m, Commented May 3, 2017 at 20:32

Joseph · Accepted Answer · 2017-04-06 23:17:27Z

JavaScript metaballs optimization

I read that as "JavaScript meatballs optimization" :D

First optimization I would do is... code organization. Slow-looking code will be slow code, since it takes you an extraordinary amount of time working with it. So keep your code tidy. Use proper indentation, name variables properly, organize code in a coherent fashion.

Nested loops become a problem, fast. Avoid nested loops as much as possible. In the case of looping through canvas pixels, instead of using a nested loop to traverse horizontally and vertically, you can simply use one loop and skip by fours. That will give you the same pixel-traversing effect.

But isn't it the same amount of iterations? Yes, but here's the thing. Loops are a dead end in terms of optimization. If you get your x and y that way, that's it. However, if you do the 1d loop and do math to get your x and y, you still have a chance at optimization since math can be optimized (bitwise operations) and values can be cached easily.

Another perf killer is property access. It's negligible alone, but if you're operating at 3M pixels per frame, it becomes very visible. Cache values as much as possible, and avoid property accesses.

One optimization you could do is heuristics. I you know a pixel is far enough from any ball, you can just color it black without calculation. Same goes for pixels within a ball. If it's within a ball, it will be white regardless of overlapping balls. Also, if a pixel is already white, you can just skip calculation of the other balls since there's no way it could darken.

Another trick you could do is just use a smaller canvas and upscale it with CSS scale transform. To the script, the number of pixels on the canvas is lesser which means lesser iterations. But from the viewing perspective, the animation is about the same as the full-scale version.

Here's my take on it. Slightly faster due to skipping and upscaling.

const c = document.getElementById("canvas");
const width = c.width = 640;
const height = c.height = 360;
const ctx = c.getContext("2d");
const imageData = ctx.createImageData(width, height);
const data = imageData.data;
const dataLength = data.length;
const num = 20;
const balls = Array(num).fill().map(_ => new Ball());

function random(min, max) {
  var num = Math.floor(Math.random() * (max - min + 1) + min);
  return num;
}

function Ball() {
  this.posX = random(0, width);
  this.posY = random(0, height);
  this.dx = random(-4, 4);
  this.dy = random(-4, 4);
  this.radius = random(2, 25);
}

Ball.prototype.move = function() {
  if (this.posX > width || this.posX < 0) this.dx = -(this.dx);
  if (this.posY > height || this.posY < 0) this.dy = -(this.dy);
  this.posX += this.dx;
  this.posY += this.dy; 
}

function updateBalls() {
  for (var i = balls.length; i--;) balls[i].move();
}

function renderBalls() {

  for (var sp = 0; sp < dataLength; sp += 4) {
    const index = sp / 4;
    const y = index / width | 0;
    const x = index % width | 0;
    var color = 0;

    for (var i = balls.length; i--;) {
      const ball = balls[i];
      const radius = ball.radius;
      const posX = ball.posX;
      const posY = ball.posY;

      color += radius * 2500 / (Math.pow((x - posX), 2) + Math.pow((y - posY), 2));
      
      if(color >= 255) break;
    }

    data[sp + 0] = color * 1.05;
    data[sp + 1] = color;
    data[sp + 2] = color * 1.4;
    data[sp + 3] = 255;
  }

  ctx.putImageData(imageData, 0, 0);
}


;(function loop() {
  requestAnimationFrame(loop);
  updateBalls();
  renderBalls();
})();

body {
  padding: 0px;
  margin: 0px;
}

canvas{
  transform: scale(4);
}

<canvas id="canvas"></canvas>

Nested loops are likely to be problematic for performance, but be careful about throwing around terms like "exponential". In most cases, it's still polynomial. — 200_success, Commented Apr 6, 2017 at 20:19

Stack Exchange Network

JavaScript metaballs optimization

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged
javascript
performance
beginner
animation
canvas
or ask your own question.

Hot Network Questions

JavaScript metaballs optimization

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged javascriptperformancebeginneranimationcanvas or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
javascript
performance
beginner
animation
canvas
or ask your own question.