1k Rose
6 de Febrero del 2012I’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.
Where is the +100000?? I loved the demo, but I love this post much more. Brilliant! congratulations for such delightful mix of these old techniques and thanks for sharing! :)
Fantastic post, thanks for sharing!
Wow!
Double wow for image and fine tutorial.
LRP
Great!!
Thats awesome and great explanation as well.
[…] “CRITEO-300×250″, 300, 250); 1 meneos menéalo 1k Rose (explicación de Román Cortés) [ENG] http://www.romancortes.com/blog/1k-rose/ por anacard el 08:51 […]
Brilliant!
Thank you for sharing…
Amazing work - very classy and the maths is totally beyond me - impressive.
[…] Cortés (he of 1k christmas tree and CSS coke can fame) explains to us how he made a 3d representation of a rose in just 1k of JavaScript, using Monte Carlo sampling. Beautiful stuff! Tags: a rose by any other […]
[…] Román Cortés » 1k Rose. […]
it’s an impressive use of javascript and a nicely written and illustrated tutorial.
but: why the heck would anybody use js if all he wants in the end is a drawing of a rose? looks to me like if someone decided to use chopsticks to eat a soup: it certainly can be done somehow, but it’s heck of a lot more difficult and takes much more time than with a spoon (or just drinking it). iow: it just doesn’t make any sense apart from the technical challenge and the entertainment.
in this case, the spoon would probably be to use svg instead (a w3c standard that doesn’t even require js to be enabled, allows the drawing to be saved, scaled etc.). or better (for the receiver of your love message): use a photograph of a rose, i.e. a plain jpg or png file. or even better: invite her over for a candle-light dinner and give her a real rose. saves you a lot of time and the outcome will be 100x better, believe me.
Yes, you did succeed in piquing my interest in computer graphics! Wow!
Thank you so much.
It’s amazing what one can do with JS these days!
“why the heck would anybody use js if all he wants in the end is a drawing of a rose? looks to me like if someone decided to use chopsticks to eat a soup”
Interesting analogy!
When my father’s Chinese teacher taught him to use chopsticks, she got him to transfer single grains of uncooked rice from one container - and I did the same.
The point of such exercises is to _master_ your tools by doing things that are _deliberately difficult._ Without such exercises as this, you will simply never become a master.
Gracias por el articulo muy interessante!
[…] of this year’s most jaw-dropping efforts to date is developer Román Cortés 3D rendering of a rose. Relying on Monte Carlo methods to keep the code size down, Cortés’ code draws a very nicely […]
[…] A canvas rose in 1k! and an explanation by the author […]
Very good!
Where can I find the complete non-obfuscated source code?
I’m sorry Eduardo, but when I code for js1k, I usually do it very obfuscated directly, so there is no source code other than the one you see. It helps me a lot to know a good approximation of the space it is going to be without the need to use minimizers. Also, if I write it trying to make it size optimized from the start, I don’t need to optimize it after, so it saves some steps and time.
[…] of this year’s most jaw-dropping efforts to date is developer Román Cortés 3-D rendering of a rose. Relying on Monte Carlo methods to keep the code size down, Cortés’ code draws a very nicely […]
I cried. The world needs more programmers like you, dear Sir. It’s stunning.
this post blew my mind.
wow.
Great post and a great test of compatibility - if she isn’t appreciative of the gesture once you’ve finished the explanation, you’re with the wrong girl. Happy V day.
danillo, perhaps you didn’t realise that this is for JS1K a competition to see if you can do something pretty in only 1k bytes of Javascript code?
Sean
even more impressed by this detailed post: congratulations for the demo
Hi!
I have somehow reverse-engineered your code and now I’m even more amazed!
Do you mind if I publish it with due credits?
Sure, do it and don’t forget to send a comment so I can link to it!
I have just published the reverse-engineered code in GitHub:
https://github.com/erdavila/1k-rose
Thanks, and good luck with the contest!
You are welcome Eduardo! And thanks to you too!
very nice work. Give what software and tools you use for the mc analysis.
I just code the algorithms. If I need a good speed, I code in C and use the Mersenne Twister as random generator or Sobol sequences. If I need even more speed, I use Nvidia’s CUDA, but for the same purpose openCL or any other language able to use the power of the GPU should be equally valid
awesome! ideal virtual gift on Valentine’s Day
This is cool. The final pass takes a while to load but the fact that you can render a flower through JS is awesome
@Sean: I’m totally aware of the fact that this was an entry of a 1k JS competition. And as I said: It’s technically impressive and all, no doubt. But to stick with my analogy: It’s as if we had competitions how to eat soup with chopsticks the fastest! “Cheers to the winner! He managed to eat the soup with little spoilage within just 2 hours! That’s fantastic, given he used chopsticks!”. Sadly, such a competition still doesn’t make any sense at all, though. OK, you’re a master of using chopsticks to eat soup now. And you’re probably quite efficient now at using chopsticks for other tasks too (not necessarily though). But wouldn’t it make more sense to use the chopsticks for the purpose they were invented and intended for, in the first place? Instead of trying to use them to accomplish things that can’t ever be the optimal solution for a given task as spoons will always be more natural, more efficient and more effective, for this task? And supposed you nonetheless really wanted to practice in handling chopsticks - wouldn’t it make much more sense to do this in their natural domain, e.g. with a nice dish of Chinese food?
The intention behind Javascript was never to “code” static drawings (the rose’s fade-in effect doesn’t really change this as it looks poor compared to some nice alpha blending as possible with flash for ages). Javascript was invented for dynamic stuff on web pages (not as a replacement for flash either, though).
[…] 原文在此:http://www.romancortes.com/blog/1k-rose/ […]
[…] http://www.romancortes.com/blog/1k-rose/ RedditBufferShareEmailPrintFacebookDiggStumbleUpon […]
Great write-up of your techniques. The picture was lovely but your article is even more impressive. I would have never thought to use Monte Carlo sampling in this way much less with JavaScript. As far as I know, it’s usually used for ray tracing and volumetric rendering. My impression was that it was a slow and difficult to use. But your article shows quite nicely that Monte Carlo can be a useful and efficient solution.
Hope to see more of your work in future.
[…] Román Cortés » 1k Rose […]
[…] 想了解这段代码的工作原理的朋友请访问这里。 […]
[…] some excellent entries, including this canvas rose by Román Cortés, with a blog post detailing how he did it. You may remember Román as the guy who made the awesome 3D canvas […]
[…] 英文原址:romancortes.com 这篇文章发表于:技术文章 标签:javascript by feshine. 原文:链接. […]
[…] Rose is a Rose : Une rose en seulement 1018 octets ! Et puis, autant en profiter, l’auteur a écrit un billet sur la façon dont il a fait la rose, y compris toutes les techniques de rendu et plus. Un must […]
[…] Román Cortés) Ce contenu a été publié dans Informatique, Maths par olafleur. Mettez-le en favori avec son […]
Impressive work. Excellent explanation. I will definitely keep following your work.
太棒了,great!
还有文章写的也非常好,讲解的很细致,步步深入。
[…] Román Cortés » 1k Rose […]
Loved it! Thanks for the explanation.
Awesome post. Thank you for pointing out Monte Carlo and Euler angles!
[…] 英文原址:romancortes.com 分享到: QQ空间 新浪微博 人人网 开心网 更多 Tags: javascript 前端开发 3 comments […]
[…] liked Roman Cortes’ short note on Monte Carlo methods: […]
[…] 原文地址 […]
Espléndido, genialmente explicado. Este comentario va especialmente para expresar mi admiración por la parte didáctica. Pena que no haya más, pero la escasez se compensa por la calidad. Espero tus posts en mi RSS aggregator como agua de mayo.
But I thought it had to be under 1k. And it shows up at 1018 bytes. Very cool though.
Chris, js1k rules talk about 1 kibibyte = 1,024 bytes. The prefix kibi- is very recent (only around a decade ago was standardized), and just in the few last years it has been started to be used mainstream. Until people get used to it (and it can take a lot of years yet), you will see very often 1 kilobyte used with the traditional meaning in computer science of 1,024 bytes instead of 1,000 bytes.
In my personal case, I will continue calling kilobyte to 1,024 bytes, just by tradition. And I will continue calling Pluto a planet (a major one).
[…] Montecarlo sampling of surface equations tuned until reaching the rose shapes shown. Check also previous static version here and how is made on his blog also. […]
[…] my favorite things about JS1k is all the learning and sharing that goes on. Román has written a fantastic blog post about how he made the rose, including all the rendering techniques and more. Definitely a must […]
Once again great post, thank you for taking the time to write it. ;)
[…] }; // this surface will be a square of 50×50 units of size }…http://www.romancortes.com/blog/…Comment Loading… • Post • Insert a dynamic date here Add […]
brilliant!
mathemagic~!