Just to clarify - the bulk of the work here is done in GLSL shaders on the GPU, not with matrices in JavaScript.
All that matrix code you see in the source here is basically just the minimum prerequisite for doing 3D graphics, it would be the same if you just wanted to get a spinning cube with some camera control.
The real magic happens in the shaders which compute water mesh displacement, normals and shading directly on the GPU (21 simulation passes + 1 rendering pass + 1 initialization pass, using several floating point textures, seems like stateful simulation with ping-ponging, basically using graphics rendering pipeline to do GPGPU without a need for OpenCL / CUDA).
this is magic? isn't this precisely what the hardware was designed for? i wouldn't call this GPGPU personally - this is very much graphics.
GPGPU is more about e.g. doing multi-precision integer arithmetic on the GPU - where the processors are used for something which doesn't fit the 'streaming processor being fed vectors' pattern which the architecture was made for (of which this demo is a very good example) - quite literally 'general purpose'.
actually this is exactly what everyone thought when this hardware was new 10 years ago... and even before that we were thinking about it. look at rendering demos from that time that leveraged the shader - this was the dumbass obvious thing that almost everyone did.
this is not physical simulation - not even close. the navier-stokes equations are still really quite difficult to do anything real-time with unless you make some serious compromises.
i will conceded that this is very loosely based on physical reality. but actually, you can do a lot, /lot/ better with clever hacks.
as an example of one of the much, much better solutions which approximate reality than this - the old school 2d 'water' effect created from feedback and a clever 3x3 convolution filter shaped as a ring with a hole in the middle, for instance is visually much more impressive and computationally simpler - and it actually is a solution to a discretised wave equation. render this old effect as greyscale into a buffer than use it as a height/displacement-map style texture - with this solution implementing real-time ripples and fluid like response to objects entering the liquid comes down to rendering the outline into that buffer and these kinds of waves simply fall out rather than requiring maintenance or trig calls...
simulation of fluids is huge in computer graphics and the GPU is completely necessary for anything close to real time. Physics engines are built to process on the GPU.
I was at one point perusing a PhD in Computer Graphics and I studied many papers ranging from haptic devices w/ liquid simulations (great paper on making pancakes which change properties as they cook [1]) to research from our lab on volume rendered simulations to prevent temperature shock in introducing cool water (relatively) to prevent a meltdown of a nuclear power plant.
> ust to clarify - the bulk of the work here is done in GLSL shaders on the GPU, not with matrices in JavaScript.
I noticed that, which I thought was pretty cool. I was playing with it in Chrome on OS X when I realized that it wasn't doing too much to my CPU, even when I cranked the simulation up to max.
>basically using graphics rendering pipeline to do GPGPU without need for OpenCL / CUDA
It would be really cool to see a project that would make that easier to do in JS more generally. Basically a similar idea to Parakeet or Numba, but with GLSL as a target.
> >basically using graphics rendering pipeline to do GPGPU without need for OpenCL / CUDA
> It would be really cool to see a project that would make that easier to do in JS more generally. Basically a similar idea to Parakeet or Numba, but with GLSL as a target.
The problem with doing this on WebGL (which is essentially GLES2) is that the internal precision of the pipeline is not required to be a full 32 bit float. There are 10 bit integers and 20 bit floating point numbers and all sorts of funny number formats in the hardware. When most scientific/numeric computation is done in 64 bit double precision, going to less than 32 bits is a problem.
Of course it still could be done in WebGL, the problem is that running it on different hardware would yield different results. If this is acceptable (e.g. image processing where bit-accurate results are not required), then why not.
That seems to me actually further than just writing the GLSL shaders yourself. I suppose the MVP would be a library that simply eases getting data in and out of webgl.
I'm not sure how I'd feel about a repost to jsfiddle without my permission if I were the original author. How is this any different than reposting xkcd or other webcomics on alternate hosting without the author's permission?
I'd hardly call him the original author - A. it's based off Jerry Tessendorf's seminal Ocean Wave simulation paper from Siggraph 2001, and B. the code's very similar to Keith Lantz's non FFT version here, just in JS and WebGL shaders instead of C++:
Because you can see the code does not mean you have the right to distribute it. With your argument you mean it is ok to record music from some music service and post this wherever you like just because it is possible?
Ability to do something does not mean it is ok to do it.
I'd argue that it WOULD be okay to repost sound files. Just because someone was the first to string together a set of information means that nobody else is allowed to share it?
Please look up copyright. I know the concept of magical numbers that nobody is allowed to duplicate is grating, but this is what business and life is built on.
As a musician, if I posted a piece of music to a site that permitted it to be played in their Flash player on the site, this does NOT mean I want it to be distributed does it? Unless I explicitly stated that it was alright to distribute it.
EDIT: I didn't mean this to come across as snappily as it did btw!
Great demo, well written code. Though reading through it also highlights that JS is not a great language for linear algebra. But I don't think anyone is really suggesting otherwise.
"JS is not a great language for linear algebra." what does that even mean? It's a general purpose language. It all boils down to how you want to use it, like any other general purpose language. A lot of times in cases like this, people choose not to make it look pretty and easy to read to gain performance. This simulation is very CPU intensive, trying to have pretty code and speed is going to be tough.
Or look at Python/Numpy. General purpose language with a sufficiently advanced library that doing linear alg stuff becomes a very pleasant experience. Way, way, way nicer than spelling it all out like this JS code has to.
Then again, I might be biased there since I've spent a decent chunk of time porting MATLAB/Octave code to Python/Numpy so that we could get it into production in a robust way..
I actually like python/numpy, mostly b/c I'm very comfortable in the python stack. Numpy has come a long way, such that it has sufficiently shaved the squared off corners of the square peg, so it pretty much fits into the round hole.
To me, Numpy/SciPy are Pythons "killer apps". I would say the plurality of times I have decided to use Python in the past two or three years, it was because of them.
JS is fine; in the same way that is fine to use a sandbox shovel to dig the foundation of a house. Languages are designed for a purpose, though they can be used for all sorts of things.
There is a larger upfront cost to learning the right language for the right job. However, many people opt to try to fit a square peg into a round hole.
Not only tough but ultimately impossible; like C it is nice that people can stretch JS to maximize performance - a developer can always maintain separate file with "nicely" formulated calculations but at the end of the day what matters is the end user's experience of speed in the final app.
It's worth pointing out that you should rarely, if ever, use exact formulas since there are a lot of problems with numerical stability amongst other things. Often it is faster to just numerically solve the system.
For example, in your case you are solving Ax=b which you can easily solve by a simple LU decomposition. Plus if your A changes, your exact formula is wrong, so using an LU decomposition just makes sense. Plus your code will look way cleaner as well. And way easier to debug.
The conventional wisdom (in scientific computing) that you seldom need to compute an inverse of a matrix does not apply to computer graphics. 4x4 matrix inverse is one of the most useful functions in computer graphics and is used a lot.
It is most often used as a hand rolled 4x4 matrix inversion function, not a generic NxN matrix inversion.
In case that the exact formulas for this solution would be numerically unstable, why would the LU decomposition improve the numerical stability? Also, why should it be faster?
Well, to be fair, in that example, if the compiler does those `pow(x2 - x1, 3.)` calls multiple times, this would not be optimal, but otherwise, it should be ok.
I did this because I will probably never ever change the matrix A here and I wanted to make that code very fast. Otherwise, it's of course a good idea to use some more generic solution.
I'm not implying yours are not unstable, it's just there is a chance it might be. Typically exact formulas exhibit such properties.
LU decomposition is numerically stable, for the most part. You can run into problems with floating point arithmetic if you're not careful. This just has to do with the way you solve the problem. By breaking up the matrix into an upper and lower triangular part and solving the resulting triangular system, you often avoid things like powers or square roots and just reduce everything to basic addition and multiplication which tend to have more stable numerical properties.
As for speed, well in this small case of N=4 there is probably very little speed increase since LU is O(N^{3}), although this can be improved depending on symmetries of the matrix. Maybe for N=5 I might write out the exact formulas but beyond that I would just a LU solver since the amount of code for an LU solver is fairly compact.
But, as you correctly point out, if you are never changing the matrix A then you are probably safe with writing it out this way.
I just come from a numerical fluids background so seeing exact formulas makes me uneasy. And in my work since the number of grid points N tends to be variable so general formulas are not available. Plus I've noticed a lot of programmers tend to not know numerical algorithms. In fairness, I don't blame them. All the numerical computations courses I've taken and TAed are very boring and don't make you do anything fun and numerical analysis has this reputation of being dry. If you actually made them write stuff like a Navier-Stokes solver, you would get them interested.
By the way if you want to learn more about numerical linear algebra, which is the cornerstone of most scientific and high performance computing, I personally enjoy Trefethen and Bau's book. Although it's aimed at a mathematical audience and assumes such.
Wait, no, LU decomposition is not stable unless you're doing pivoting. And if you're doing pivoting, then it very much stops looking like an "exact formula", because it'll get filled up by ifs and variable renamings, etc.
There's plenty of cases in graphics and simulation where solving even a 4x4 matrix needs careful numeric consideration (see this paper about tetrahedral mesh simplification, section III.D, page 7: http://www.sci.utah.edu/~hvo/papers/tetstream.pdf)
If you care about accuracy at all, do not use the straightforward "exact formulas" like Cramer's rule. That's just asking for trouble.
You are quite correct about stability but I didn't want to get into technical details. And indeed you bring up correctly that such numerical issues mustn’t be treated lightly. I don't do computer graphics and the matrices I deal with are well conditioned such that problems of stability that arise due to linear algebra routines are negligible. In my simulations, instability arises due to the wrong time-stepping scheme, which is a completely different issue.
And good recommendation by Strang. I believe he has some fantastic MIT OpenCourse lectures on numerical linear algebra as well.
> I wonder if it was all handwritten. Esp. functions like invertMatrix or premultiplyMatrix. Or what he used to generate the code.
Yes, it probably is hand written. Or more likely, copied from some well known resource such as MESA.
Computer graphics deals extensively with 4x4 matrices, so there are hand written implementations of elementary operations such as matrix inverse, all unrolled and precomputed so that there's no loops or anything. (NOTE: this isn't really basic loop unrolling, these are not simple loops to begin with).
I'm using the onboard/ondie Intel HD4000 and it works. You might have a driver that is blacklisted. Chrome and I think other browsers have a list of drivers known to allow execution of dangerous shader code and block WebGL in those cases.
Honestly very impressive, idea: if made into fullscreen (i.e. without edges visible) and with an added horizon and an emulated sun-rise/sun-set this would make for totally enthralling watching - the "live'ness" of it makes it a thousand times more interesting to the eye than images or pre-recorded video material.
A dream/stretch goal would be some sort of a vessel (fishing boat?) that allowed me to recreate the 'perfect storm' and WASD around while trying stay afloat.
Just calculate the boat's water displayment via some very approximate measure. Then use that to determine buoyancy relative to boat weight and just integrate that overtime and add some dampening to represent friction/inertia.
But there is a better way of doing interactive waves from a boat, wave particles:
Yeah, love that one too. Insanely great. But it's raytracing the sphere and raymarching the water distance-fields per fragment, right? Not gonna fly realtime any longer (or at all) if you ever wanted to use it with additional polygonal art. ;)
I'd suggest a good book over Wikipedia articles, most math articles are particularly useless for learning stuff IMO.
I learned quite a lot from "Mathematics and Physics for Programmers", although I wouldn't call it perfect. I'm also quite interested in "Essential Mathematics for Games and Interactive Applications".
It's true, once you've got linear algebra figured out you can do a whole lot in the simulation/games space, but it helped me to learn the more advanced stuff in terms of games and simulations.
I've alluded to this in other comments but a lot of the mathematics is linear algebra. As gaius mentions, check out the wikipedia article. There are plenty of linear algebra books out there. Recently I've really enjoyed the book by Meyer which is free although it does get quite advanced and is mostly theorem / proof-style. It's also free so who can complain.
I've take a quick look through it and it seems pretty good. It introduces many of the most important ideas of solving PDEs. Obviously there are huge tomes on various techniques to solve the Navier-Stokes equations but this link, I think, does a pretty good elementary introduction. A more comprehensive treatment would require a more thorough background in mathematics (e.g. I wrote a 2D NS solver using the vorticity formulation and FFTs but to understand the equivalence requires a greater background).
As for the cool visualisation, I cannot help you. I don't know any fancy graphics programming since I normally use the built-in plotting tools of Python and Matlab.
I'd love to see it with different ocean floors to be able to see how waves break in different locations based on certain conditions. Someone please make this happen! :D
It's heavily based on Jerry Tessendorf's "Simulating Ocean Water" paper, so it only does open water: interaction of water and wind using Phillips' Spectrum.
So it doesn't model the interaction with land in any way.
Hitting ctrl-+/ctrl-- on chrome leads to interesting results :) Impressive demo, kept staring at it for a while pondering the exciting future the web platform has in it.
I am surprised how this runs smoothly even on lower end PCs.
I was able to view it perfectly smooth on a old Dual Core, integrated graphics and 2GB RAM linux box.
I remember seeing this run smoothly on a P2 after a very small executable download in late 90's. How far we've come in a big, stupid circle back where we started.
Now instead of a small executable, we need a large executable to sit on top of a large API on top of the CPU before even touching the GPU, and a network connection to download all the dependant APIs and libraries every time the page is loaded.
The only impressive thing about this demo is how many YCombinator readers are impressed with blinkenlights
Yes. Makes me smile when I hear the word "demo" being thrown around. I always thought the point of a demo was to come up with something impressive with very limited resources.
Remember 64k demos? http://www.youtube.com/watch?v=Qv7y3eKyVUo
Sure, for varying values of "works" and "different" and "no install step".
I'm going to go out on a limb here and state that a DOS executable from the 90's will run on more machines in the world than this demo, given "platforms" similarly to what this demo takes as a given.
Sure, for varying values of "works" and "different" and "no install step".
You could say the same thing about anything related to web browsers. What's your point?
I'm going to go out on a limb here and state that a DOS executable from the 90's will run on more machines in the world than this demo
Right... except a user has to trust you enough to download and execute your DOS binary rather than just execute a javascript file in a browser sandbox.
until someone comes up with a way to determine what is bad versus good then that is perhaps the best there is. I use companies to do all sorts of things for me - watching software is just one more thing.
computers have now become so powerful that this stuff is easy. you can implement it in a way which, aside from platform, is really quite naive and wasteful - and still get applause.
most programmers can come up with a much better solution to this problem if removed from google and forbidden access to gpu gems.
this is at least well presented though...
its a shame the code has been posted. whilst i normally assume that demos like this are unlikely to be smart or impressive these days - this time i know for sure. its actually a good deal worse than i ever would have imagined.
i'm still quite torn whether all this horsepower is a good thing or not.... on the one had we get a demo like this without much in the way of understanding or resourcefulness. on the other hand we have hundreds of man hours being wasted at dev studios because clever efficiency is rapidly becoming a thing of the past...
"most programmers can come up with a much better solution to this problem if removed from google and forbidden access to gpu gems."
I doubt I could come up with such a solution even with access to google and gpu gems. I am not a particularly good programmer, but I know for certain that most programmers wouldn’t even know where to begin to implement something like this.
don't be so doubtful. i started out down this path without google and the internet so its especially easy for me to see, but consider: do you even want to make this?
if you did i'd bet you'd find a way - google, wikipedia and free copies of gpu gems make it stupidly easy. the amount of understanding required to produce a demo like this is no more than is required to copy someone else's code or algorithm in any other discipline.
even without those, if you wanted to make this i bet you could come up with something pretty good on a first attempt. even now i bet that somewhere in there you have a pretty good idea of an approach - you might think its dumb, inefficient or must have a flaw in it - you might have no idea about what you need to feed the rendering pipeline - but i'd bet its pretty good - probably a lot better than you'd give it credit for.
If anyone is interested in playing around with it, I threw it up at JSFiddle here: http://jsfiddle.net/zyAzg/
Excellent demo.