2D collision detection of random shapes using p5.js

Introduction

This week, I started playing around with p5.js, the JavaScript equivalent to Processing. My first goal was to find a flexible way to draw random objects on the canvas in a way they wouldn't collide, so that I could make a nice looking banner for this blog.

I started looking for a straight-forward way to do this in p5.js but could only find p5.collide2D, a library which does not appear to support collision detection with random shapes. It does a good job at detecting collisions between for example polygons and lines, but there is no support for collision detection on random shapes (for example a circle, text and bezier curves), so I started investigating a custom implementation.

Approach

The approach I took is very basic (and computationally not the best), and allows me to prevent randomly generated and placed objects from colliding. The principle behind the technique is simple and goes as following:

You generate an object an you place it on a blank canvas. Then, you can calculate the total number of pixels in the random shape by iterating over all pixels in the canvas and checking if the pixel is white or not. After having done this, you place the new shape on the existing canvas (which can already contain a series of non-colliding objects), for which you also know how many non-white pixels there are (since you can just count them). Then finally, you check if the sum of the pixels in the new shape plus the number of pixels in the original shape are equal to the number of pixels in the canvas containing the existing objects and the new object. If there is a difference between both numbers, it means that at least 1 pixel overlapped, and we have to generate a new object again (that hopefully won't collide)!

Below is the pseudo-algorithm explaining the same principle in a bit more detail:

  1. Store a snapshot of the state of the canvas in a variable (pixels1 array). This will most likely be a white canvas, but it can also be a canvas with some elements (such as text, see below) already present.
  2. Count the total number of non-white pixels in pixels and store it in num1.
  3. Clear all objects from the canvas.
  4. Generate a random object (for example, ellipse(int(random(10),int(random(10),5).
  5. Draw that object on the blank canvas.
  6. Store a snapshot of the state of the canvas in a variable (pixels2 array).
  7. Count the total number of non-white pixels in pixels2 and store it in num2.
  8. Draw all objects from the pixels1 array and place it onto the canvas.
  9. Draw all objects from the pixels2 array and place it onto the canvas.
  10. Count the total number of non-white pixels in the canvas and store it in num3.
  11. If num1 + num2 != num3 then there was a collision. In this case, restore all pixels from pixels1. If there was no collision, leave everything as-is.
  12. Go back to step 1.

After having implemented this in p5.js, I could start playing around with placing random objects on a canvas. For my header, I wanted my name (Daan Raman) to become visible through the use of "negative space", where the random shapes would be auto-generated to fill up all the space on the canvas that was not text. For this step, I cheated a bit: since putting a white text on a white background would not result in a collision being detected using the above algorithm, I set instead a color which is almost identical to white as the font color. Difficult for a human to distinguish with white, but enough for the algorithm to treat the text as being not white:

function drawText(){  
  ...
  fill(254);
  noStroke(0);
  ...
}

I also applied a few optimisations in the source code to avoid collisions as much as possible, resulting in the canvas being filled with new random objects more quickly. One of these optimisations simply checks if the start X and Y coordinates of the randomly generated shape already land on a coloured pixel. If this is the case, we are sure we have a collision already, and we can just jump back to step 1 in the algorithm above.

function Shape(){  
    // Generate x and y position, until we have a start coordinate that does not collide with existing pixels
    collidesWithExistingCanvas=true;

    while(existingPixels.length > 0 && collidesWithExistingCanvas){
        xPos = int(random(0, windowWidth));
        yPos = int(random(0, windowHeight));

        // Check if pixel at that position is colored or not
        index = (xPos + yPos * windowWidth) * 4;

        r = existingPixels[index + 0];
        g = existingPixels[index + 1];
        b = existingPixels[index + 2];
        a = existingPixels[index + 3];

        if (!((r+g+b) < 765 && (r+g+b) > 0)) {
            collidesWithExistingCanvas = false;
            this.x = xPos;
            this.y = yPos;
        }
    }

It was time to give the algorithm a spin, and quickly some nice results came out! I could basically generate any shape on the canvas, put the colour to almost white, and then let the algorithm fill all the remaining real white space with randomly generated objects. A few live examples below.

source code

In the previous example, random bezier vertices are being placed on the canvas. We can also combine multiple shapes. For example, we can place text on the canvas and let the algorithm draw random shapes in the white space around it:

source code

If we then put the same text at fill value 253 (almost white, so the algorithm doesn't draw over the text), we can play with negative space, as in the example below, and in the header of this article:

The longer you wait, the denser the image will become, as more randomly generated objects fit the remaining whitespace:

There are some optimisations you can use to fill the canvas quicker by reducing the number of random objects that will collide (and be dismissed) with existing pixels on the canvas:

  • Immediately regenerate objects which have X and Y start coordinate overlapping existing pixels on the canvas (do this in step 4 above);
  • Reduce the maximum size of new objects over time to avoid a very high number of consequent colliding objects in case the canvas becomes more and more dense, with less and less whitespace available to fill. This can be done for example by linearly reducing the maximum object size (i.e. length of a vortex or diameter of a circle) with the number of consequent collisions.

Conclusion

The described approach can be used to place an arbitrary number of non-colliding random objects on a canvas using p5.js, without any limitation on the size or shape the random objects will be. The downside of this brute-force approach, as opposed to mathematical collision detection models, is the (very) high and inefficient use of processing power. However, if you wait long enough, the canvas will eventually be filled!