Román Cortés

1k Rose

6 de Febrero del 2012

Rose

I’ve participated in the love themed 4th edition of js1k. My submission is a static image, a procedurally generated 3d rose. You can take a look of it here.

It is made by Monte Carlo sampling of explicit piecewise 3d surfaces. I’m going to try to explain all a bit in this article.

A short note on Monte Carlo methods

Monte Carlo methods are incredible powerful tools. I use them all the time, for a lot of kinds of function optimization and sampling problems, and they are almost like magic when you have more CPU time than time for designing and coding algorithms. In the case of the rose, it was very useful for code size optimization.

If you don’t know much about Monte Carlo methods, you could read about them in this excellent Wikipedia article.

Explicit surfaces and sampling/drawing

To define the shape of the rose I’m using multiple explicit-defined surfaces. I use a total of 31 surfaces: 24 petals, 4 sepals (the thin leaves around the petals), 2 leaves and 1 for the rose stick.

So, how they work these explicit surfaces? It is easy, I’m going to provide a 2d example:

First I define the explicit surface function:

function surface(a, b) {  // I'm using a and b as parameters ranging from 0 to 1.
    return {
        x: a*50,
        y: b*50
    };
    // this surface will be a square of 50x50 units of size
}

Then, the code for drawing it:

var canvas = document.body.appendChild(document.createElement("canvas")),
    context = canvas.getContext("2d"),
    a, b, position;

// Now I'm going to sample the surface at .1 intervals for a and b parameters:

for (a = 0; a < 1; a += .1) {
    for (b = 0; b < 1; b += .1) {
        position = surface(a, b);
        context.fillRect(position.x, position.y, 1, 1);
    }
}

The result:

Now, lets try more dense sampling intervals (littler intervals = more dense sampling):

As you can see, as you sample more and more dense, points get closer and closer, up to the density when the distance from a point to their neighbours is littler than a pixel, and the surface is fully filled on screen (see 0.01). After that, making it more dense doesn’t cause much visual difference, as you will be just drawing on top of areas that are already filled (compare results of 0.01 and 0.001).

Ok, now lets redefine the surface function to draw a circle. There are multiple ways to do it, but I will use this formula: (x-x0)^2 + (y-y0)^2 < radius^2 where (x0, y0) is the center of the circle:

function surface(a, b) {
    var x = a * 100,
        y = b * 100,
        radius = 50,
        x0 = 50,
        y0 = 50;

    if ((x - x0) * (x - x0) + (y - y0) * (y - y0) < radius * radius) {
        // inside the circle
        return {
            x: x,
            y: y
        };
    } else {
        // outside the circle
        return null;
    }
}

As I’m rejecting the points outside the circle, I should add a conditional in the sampling:

if (position = surface(a, b)) {
    context.fillRect(position.x, position.y, 1, 1);
}

Result:

As I said, there are different ways to define a circle, and some of them doesn’t need rejection in the sampling. I’m going to show one way, but just as a note; I will not keep using it later in the article:

function surface(a, b) {
    // Circle using polar coordinates
    var angle = a * Math.PI * 2,
        radius = 50,
        x0 = 50,
        y0 = 50;

    return {
        x: Math.cos(angle) * radius * b + x0,
        y: Math.sin(angle) * radius * b + y0
    };
}

(this method requires a denser sampling to fill the circle than the previous one)

Ok, now lets deform the circle so it looks more like a petal:

function surface(a, b) {
    var x = a * 100,
        y = b * 100,
        radius = 50,
        x0 = 50,
        y0 = 50;

    if ((x - x0) * (x - x0) + (y - y0) * (y - y0) < radius * radius) {
        return {
            x: x,
            y: y * (1 + b) / 2 // deformation
        };
    } else {
        return null;
    }
}

Result:

Ok, now this looks much more like the shape of a petal of a rose. I suggest you to play a bit with deformations. You can use any imaginable math function you want, add, subtract, multiply, divide, sin, cos, pow… anything. Just experiment a bit modifying the function, and lots of shapes will appear (some more interesting, some less).

Now I want to add some color to it, so I’m going to add color data to the surface:

function surface(a, b) {
    var x = a * 100,
        y = b * 100,
        radius = 50,
        x0 = 50,
        y0 = 50;

    if ((x - x0) * (x - x0) + (y - y0) * (y - y0) < radius * radius) {
        return {
            x: x,
            y: y * (1 + b) / 2,
            r: 100 + Math.floor((1 - b) * 155), // this will add a gradient
            g: 50,
            b: 50
        };
    } else {
        return null;
    }
}

for (a = 0; a < 1; a += .01) {
    for (b = 0; b < 1; b += .001) {
        if (point = surface(a, b)) {
            context.fillStyle = "rgb(" + point.r + "," + point.g + "," + point.b + ")";
            context.fillRect(point.x, point.y, 1, 1);
        }
    }
}

Result:

And here it is, a petal with color!

3D surfaces and perspective projection

Defining 3d surfaces is straightforward: just add a z property to the surface function. As an example, I’m going to define a tube/cylinder:

function surface(a, b) {
    var angle = a * Math.PI * 2,
        radius = 100,
        length = 400;

    return {
        x: Math.cos(angle) * radius,
        y: Math.sin(angle) * radius,
        z: b * length - length / 2, // by subtracting length/2 I have centered the tube at (0, 0, 0)
        r: 0,
        g: Math.floor(b * 255),
        b: 0
    };
}

Now, to add perspective projection, first we have to define a camera:

I will place my camera at (0, 0, cameraZ), I will call “perspective” to the distance from the camera to the canvas. I will consider my canvas is in the x/y plane, centered at (0, 0, cameraZ + perspective). Now, each sampled point will be projected into the canvas:

var pX, pY,  // projected on canvas x and y coordinates
    perspective = 350,
    halfHeight = canvas.height / 2,
    halfWidth = canvas.width / 2,
    cameraZ = -700;

for (a = 0; a < 1; a += .001) {
    for (b = 0; b < 1; b += .01) {
        if (point = surface(a, b)) {
            pX = (point.x * perspective) / (point.z - cameraZ) + halfWidth;
            pY = (point.y * perspective) / (point.z - cameraZ) + halfHeight;
            context.fillStyle = "rgb(" + point.r + "," + point.g + "," + point.b + ")";
            context.fillRect(pX, pY, 1, 1);
        }
    }
}

This results in:

Z-buffer

A z-buffer is a pretty common technique in computer graphics, useful to paint points closer to the camera on top of points that have been painted further to it. It works by maintaining an array with the closer z drawn per pixel of an image.

This is the visualized z-buffer of the rose, with black as far to the camera, white close to it.

The implementation:

var zBuffer = [],
    zBufferIndex;

for (a = 0; a < 1; a += .001) {
    for (b = 0; b < 1; b += .01) {
        if (point = surface(a, b)) {
            pX = Math.floor((point.x * perspective) / (point.z - cameraZ) + halfWidth);
            pY = Math.floor((point.y * perspective) / (point.z - cameraZ) + halfHeight);
            zBufferIndex = pY * canvas.width + pX;
            if ((typeof zBuffer[zBufferIndex] === "undefined") || (point.z < zBuffer[zBufferIndex])) {
                zBuffer[zBufferIndex] = point.z;
                context.fillStyle = "rgb(" + point.r + "," + point.g + "," + point.b + ")";
                context.fillRect(pX, pY, 1, 1);
            }
        }
    }
}

Let’s rotate the cylinder

You can use any vector rotation method. In the case of the rose I used Euler rotations. Let’s implement a rotation around the Y axis:

function surface(a, b) {
    var angle = a * Math.PI * 2,
        radius = 100,
        length = 400,
        x = Math.cos(angle) * radius,
        y = Math.sin(angle) * radius,
        z = b * length - length / 2,
        yAxisRotationAngle = -.4, // in radians!
        rotatedX = x * Math.cos(yAxisRotationAngle) + z * Math.sin(yAxisRotationAngle),
        rotatedZ = x * -Math.sin(yAxisRotationAngle) + z * Math.cos(yAxisRotationAngle);

    return {
        x: rotatedX,
        y: y,
        z: rotatedZ,
        r: 0,
        g: Math.floor(b * 255),
        b: 0
    };
}

Result:

Monte Carlo sampling

I’ve been using during the article interval based sampling. It requires the setting of a proper interval for each surface. If the interval is big, it render fast but it can end with holes in the surface that has not been filled. On the other hand, if the interval is too little, the time for rendering increments up to prohibitive quantities.

So, let’s switch to Monte Carlo sampling:

var i;

window.setInterval(function () {
    for (i = 0; i < 10000; i++) {
        if (point = surface(Math.random(), Math.random())) {
            pX = Math.floor((point.x * perspective) / (point.z - cameraZ) + halfWidth);
            pY = Math.floor((point.y * perspective) / (point.z - cameraZ) + halfHeight);
            zBufferIndex = pY * canvas.width + pX;
            if ((typeof zBuffer[zBufferIndex] === "undefined") || (point.z < zBuffer[zBufferIndex])) {
                zBuffer[zBufferIndex] = point.z;
                context.fillStyle = "rgb(" + point.r + "," + point.g + "," + point.b + ")";
                context.fillRect(pX, pY, 1, 1);
            }
        }
    }
}, 0);

Now, a and b parameters are set as 2 random values. Sampling enough points, the surface will be complete filled this way. I’m drawing 10,000 points each time and then letting the screen update thanks to the interval.

As a side note, the full filling of a surface is only ensured if the pseudorandom number generator is of good quality. In some browsers, Math.random is implemented with a linear congruential generator, and this may lead to problems with some surfaces. If you are in the need of a good PRNG for sampling, you can use high quality ones like Mersenne Twister (there are JS implementations for it), or the cryptographic random generators available in some browsers. It is also very advisable to use low-discrepancy sequences.

Final notes

To complete the rose, each part of the rose, each surface, is rendered at the same time. I added a third parameter for the function that selects the part of the rose to return a point from. Mathematically it is a piecewise function, where each piece represents a part of the rose. In the case of the petals, I used rotations and streching/deformation to create all the petals. Everything is done with by mixing the concepts exposed in the article.

While sampling explicit surfaces by sampling is a very well known method, and one of the oldest methods for 3d graphics, my approach of piecewise/Monte Carlo/z-buffer has been probably very few times used for artistical purposes the way I did. Not exactly very innovative, and not useful in real life scenarios, but it fits very good in the context of js1k where simplicity and minimal size are desirable.

With this article I really hope to inspire readers interested in computer graphics to experiment and have fun with different rendering methods. There is a whole world in graphics, and it is amazing to research and play on it.

54 Comentarios RSS

Comentar