GSOC has finally come to a close. It seems like yesterday when I was blogging on here, young and foolish about the complexity of my project. What you see above are my modest results. Pretty as it might look, this fluid is most definitely code-name O(n^2), and that's not really a good thing! Let me explain the name in the three major aspects of my project.

Realism

It's one thing to implement a smoothed particle hydrodynamics paper in STEP, that was basically done by the midterm, but how can you make it... well, physical? In an SPH system, there are several parameters that must be adjusted to achieve that. Namely, the temperature dependent gas constant, the rest density, the smoothing kernel length, the surface tension coefficient, the viscosity constant, and the universal bounciness of object-object interactions. With the exception of the surface tension and bounciness, I was able to determine a number of these constants for a working fluid using trial and error.

Most significant for computation was the adjustment of the smoothing kernel length. This is the radius around each fluid particle at which the effects of the particle are spread out. According to the SPH algorithm I implemented, at each time step we compute the pressures at each fluid particle based on the density of all fluid particles within the smoothing kernel radius. That being said, at each time-step I made O(n^2) distance to fluid particle comparisons, and in the limit of an infinitely large smoothing kernel there would be O(n^2) arithmetic operations. Among some other issues I will discuss, I found this to be a limiting factor for the number of fluid particles I could use. 

Unfortunately, this prevented me from testing an important aspect of fluids, surface tension. By adding some additional fake surface tension forces outlined in Muller 2003, my fluid would be calmer and perhaps even support the weight of a boat at it's surface. Additionally, the addition of bounciness would allow gravity to act realistically on the fluid and have density collect at the bottom of a jar.

So, how can one improve on this brute-force enumeration of all pairs of particles? My expert mentor Vladimir suggested a new data structure might be the best approach. Since both fluids and gases benefit from a large number of particles, it would be advantageous to implement a Axis-Aligned Bounding Box data structure. Not only would this help for collision detection between any Step objects but this would provide a way to only calculate pressure forces for neighboring fluid particles. This works because we store a sorted list of boxes about both our X an Y axes and keep track of box overlaps. Unfortunately, my mentor and I did not have enough time to implement this complex rehaul to StepCore.

Measurement

Step is about education. For educational purposes, at the very least, it would be great to be able to know the average density and pressure within a region of the fluid. Despite my fluid being somewhat artificial and hacked together with strange internal values, I managed to achieve this. However, the computational complexity is, once again, not pretty. 

The calculation of pressure at a particle point in the World was already used for the dynamics of the fluid. I merely had to generalize it for discrete area elements of Step's "measurement rectangle". By moving the rectangle and resizing it within the Fluid, each time-step I am sliced the area into a grid, calculated the pressure and density at the center of each area, and then added it all together.

The trouble with that is probably quite clear. If you have a very large measurement rectangle you may want a widely spaced grid and for a small measurement rectangle you may want a closely spaced grid. A grid dependent on the size of the rectangle and the smoothing kernel radius is also a difficult value to fine tune.

In the future,  It would be ideal for the user to be able to select the precision of the pressure and density calculation at their own discretion, and have the variance values adjust accordingly. I was unable to implement variance calculations for these measurements, but that may also be an expensive calculation!

Visualization

Finally, the Pièce de résistance. The jaw-dropping visuals that all fluids deserve. As you can see above, there's lots of room for improvement. Visualization can be done in two ways. Muller 2003, the paper I was following for this SPH implementation, suggests a fancy isosurface calculation. That is, determine the normal to the fluid particle density field at every point. If this value is greater than some threshold, it's safe to say it's a surface particle and it could be used to draw a sexy looking surface. 

However, with a deadline looming, my mentor suggested a simpler approach. I would simply calculate density at each point in a grid and then paint a particle there with opacity based on the density. As seen above, these opacity calculations weren't quite calibrated, since we don't see much variation in blue except at the edges of the fluid. 

I had a problem though. Where should I "draw the line" for drawing the dots? I can't very well calculate the density at each point in the observable screen area. It would take forever to get a smooth fluid. The solution is to calculate the minimum bounding box for the fluid and use a cut-off value in-case one fluid particle flies away off the screen. This ended up being quite challenging for some reason, so I decided to only render the fluid within the "measurement rectangle".

I had an issue with converting between coordinate systems that still remains unsolved. I needed to draw my fluid about the origin of the WorldScene or else my fluid would render in the incorrect location. This is likely due to a simple mapping problem that I intend to figure out soon.

End

So, what's next for Fluids, Step, and Me? The realism, measurement, and visualization issues outlined above will continue to be worked on by Vladimir and I. After some of the fundamental problems are addressed, I forsee a very liquidy Step in the near future. Me? I'm starting a MSc. in Physics at University of Waterloo this Fall, but I had a lot of fun on this project and hope to continue making Step a richly featured open-source physics simulator!

It's about time I popped this bubble of silence.

I've been working hard on two programming projects this summer, namely my Google Summer of Code project and a fancy upgrade to some molecular dynamics software. In my previous posts, I looked at the back-end of Step and some of the mathematics of smoothed particle hydrodynamics. There are still plenty of outstanding problems in those areas but I'll address those gradually in the coming weeks. For this post, I'll give an overview of all the GUI/user interactivity stuff that i'll have to tackle on my quest to implement fast fluid simulation.

I'll just enumerate the ways the user can interact with a fluid and trace through exactly what is going on behind the scenes. I know, KDevelop/IDEs are pretty fancy, but I'm oldschool so I tend to just follow the code execution manually. It's kind of like a grep-based treasure hunt! So, I'll just give some running commentary with bonus screenshots from the current Gas classes. I doubt many readers of this blog will find this interesting, but my dream is that this post series may someday be useful for a new Step developer =P 

Oh, if you're a Qt newbie just remember that any class with a Q is a Qt class, and don't forget your slots and signals.

Read the rest of this entry »

I went to the Sharcnet GPU and Cell Computing Symposium at my university last week. One of the keynote speakers, Dr. Paul Woodward, pretty much blew my weak and feeble mind. He used Roadrunner, a.k.a. the faster supercomputer in the world, to compute some impressive fluid dynamics. You know your research group is on the right track when you have a Wallpapers section on your web site.

Back on planet earth, us computational plebs don't have such luxurious resources at our finger tips. To start with, you don't have a lot of options when you feel like simulating fluids on a computer. Things get even more depressing when you want fluid flow computed in real time. In video games, or maybe just in old video games, accurate water simulation ends up being avoided all together with some elaborate ruse to keep computation costs down. Why do fluids have such a bad rep? To paraphrase Wikipedia: "We suck at solving systems of non-linear partial differential equations, here's a million dollars if you figure it out, good luck lol".

I find this whole water simulation extra-depressing because the universe computes the solution to these problems instantly and literally rubs it in our face whenever the wind blows (via turbulence). Just imagine with me what life would be like if we had an exact solution for fluid flow. Picture weather forecasts that actually forecast, reliable message-in-a-bottle delivery using ocean currents, and aerodynamic everything.

Wow, nice introduction. This post is actually about my fluid simulation project for Google Summer of Code. To achieve real-time fluid simulation in Step, I intend to follow the Smoothed Particle Hydrodynamics (SPH) algorithm outlined by Muller et al. in "Particle-Based Fluid Simulation for Interactive Applications". This method works by breaking up a large fluid body into discrete chunks and using these chunks to create smoothed out fields. In fluids, the stuff we care about are pressure, density, and velocity fields. SPH is just a fancy way of figuring out the forces that act on your fluid by taking these fields into account.

Without going into all the mathematical detail presented by Muller et al., we can begin to define our fluid particles class in StepCore, the mathematical back-end of Step. Note that all of this is pretty fuzzy right now since I haven't started coding anything. Many important properties of FluidParticle already exist the base class Particle in Step as depicted below. Nothing too special here, just get and set methods for the particle member variables. One thing to note is that FluidParticle has a specific radius that defines the core radius of each particle. However, at this point it is unlikely that the radius of each particle will vary. I'll talk about Errors in a separate post also.

Now that the FluidParticle is defined we can look at the collective group, the Fluid. All "bodies and forces" in Step are derived from the root class Item. A Fluid is simply a group of FluidParticle items in a handy "Item Group". The main purpose of this group is to extract macroscopic features of our fluid particles that exists within a rectangle drawn in the GUI.

This rectangular data inquiry box was designed for use with the Gas class where determining the number of particles, the kinetic energy, and the temperature are meaningful quantities for statistical mechanics. However, I'm not really sure how well the physics of statistical mechanics translates to the mathematics of a fluid. For instance, I may know the velocities of all my fluid chunks but is it correct to use these velocities to determine the so-called "temperature" of my fluid? I suppose so... but I have to do a bit more research.

Nonetheless, for now I'll just use the rectPressure(), rectVelocity() and rectDensity(). I'd like to be able to use these methods to not just calculate the average pressure, velocity, and density by looping over the values stored in each fluid chunk but averaging over the entire field created by the fluid chunks. I'm not sure how computationally demanding this calculation will be, but if I discretized space within the fluid into some sort of grid this may be possible. 

So now we have a Fluid that is composed of individual FluidParticles. Where does the physics come in? We need to look at the FluidForce class for that. The purpose of the FluidForce class is to do the work of applying the inter-fluid forces to each particle in our item group by means of the calcForce method that allows you to calculate the variances based on a boolean flag. In the process of calculating the forces on each fluid particle, I'll have to use the helper method calcPressureDensity() as well.

You'll notice that the only member variable for the fluidForce is a cutoff value and FluidErrors (which I will elaborate on later). This value represents a limiting distance for which the force contribution from a distant particle would be so small that it's not worth calculating. In the current Gas implementation in Step, calcForce requires O(n^2) comparisons, as we have to loop through all pairs of particles to determine if they have a distance less than the cutoff value. As mentioned briefly in Muller et al., a potential speed-up over this approach might be to place our fluid particles on a grid and only calculate the force contribution from particles attached to neighboring grid cells to our particle of interest. I'll address performance issues later in my project.

I've already overlooked a few critical issues that may require the modification of these classes. A fundamental characteristic of a fluid is viscosity, which is defined as resistance of a fluid to shear and stress forces. Obviously, my GSOC project will not be complete unless I can simulate some delicious sticky honey. At this stage, for simplicity, I'll probably just hard code some viscosity values. The second critical issue will be collisions. My mentor and I both agree that collision handling may get tricky. If you've ever been stuck in a wall or a tree when playing a video game you'll know what I mean.

I'll address that problem eventually but next I'll briefly discuss the Error classes associated with the fluid objects. The calculation of errors/variances is one of the cool features that makes Step unique!

After that, I'll explore the Qt and GUI side of Step. I'll connect the classes I've defined above to user interactions. Once I do that, things should get a lot clearer in terms of how the FluidForce, Fluid and FluidParticles work in conjunction with the World.

Step is a 2D open-source physics simulator that was recently added to the KDE Education project.

Vladimir, the original developer and former Google Summer of Code student, posted up a few ideas to improve Step for this years Google Summer of Code. He included one about improving fluid simulation and, being a computational physicist (TM), I decided to go for it. I wrote up a fancy proposal a few weeks ago and I'm happy to say that it was accepted.

A lot of GSOC projects are strictly geeking out behind-the-scenes, but this one is fun, visual, and physics-based. It's perfect for me.

Compared to Vladimir's original summer of code, spent designing Step in it's entirety, my proposal seems like a pretty modest addition. However, fluids are traditionally a very messy subject in the world of physics simulators. If you aren't convinced, read this thread on the Box2D forums from only a month ago. To quote ElectroDruid on page 9:

"I gave up with having the particles be handled by Box2D, and one of the main reasons was because of the amount of pairs generated. You can up the maximum limits, but eventually you just run out of storage space for the numbers of pairs that can be needed in certain cases. Box2D is great for rigid bodies, but for fluids where you need a lot of particles which interact with each other in close proximity all the time, it's easy to push the limits to breaking point."

I'm sure I will have to deal with similar problems encountered in that thread, but I'm optimistic that such issues can be resolved. Throughout the summer I'll be blogging my progress on the project here, so stay tuned.

Click the thumbnail above to catch a glimpse of a single-sided slice of beauty. I cranked it out for my condensed matter physics final tomorrow morning.

Arguably a waste of potential "comprehension-intensive" study time, preparing an excessive formula sheet always puts me at ease (at least until moments before the exam when classmates are chatting about some obscure textbook chapters).

I usually insert inspirational messages into my formula sheets just in case I need that bonus motivation, but this time... see if you can find Waldo!

P.S., I can't wait until I can take care of this blog again after my finals.

I heard Sir Roger Penrose give a talk at the Perimeter Institute, Grand Opening 4 years ago. Finally, just last week, the esteemed Oxford physicist and I were re-united at last. Free tickets sold out almost instantly, but there's no chance I could let such a celebrity parade across my front lawn without witnessing it first hand. Especially since it's good blog material, and Jacks of Science is essentially the Perez Hilton of Science (slogan trademark pending).

Penrose spoke overtime on the nature of our universe before the Big Bang. I like to think of the lecture as an hour and a half of supplementary material to Leon Lederman's 10 second hand-wavey answer to the very same question in Street Corner Science Part 1.

The National Post does a great job of treading past the physics into theological no-man's land. Thankfully, to help clear up some of the physics details, I jotted down some key quotes from the lecture:

• "General Relativity makes light cones 'Higgily-Piggily'
• "Unpleasant tiny black-hole explosions"
• "Rogue electrons, I hope they dissapear"
• "Universe loses track of time"

Yeah, the notes were pretty brief.. but the whole talk should be available online at some point. It was a great lecture. Penrose's colorful overhead transparencies have already inspired some sort of grassroots movement among my classmates.

Personally, I found that I could appreciate a lot more of the mathematical details this time around. You see, I've learned a lot in the past 4 years. I am much wiser. This time around I didn't forget to get an autograph!

If Penrose wins a Nobel Prize today, I'll be rich!

I'm basically the worst science blogger! I went to a week of great lectures at the Science in the 21st Century conference last month and Jacks of Science has been in complete silence for weeks. How embarrassing!

Unfortunately, I had an unhealthy amount of class/general burdens of life during the week of the conference so I had to keep a low profile. I mostly just snuck around when people weren't looking and ate unhealthy amounts of snacks/nanaimo bars in between the lectures.

However, just a few days ago, I was recently reminded of the rapidly approaching future of science when I read the syllabus of Quantum Theory (AM473) taught by Robin Blume-Kohout at U. Waterloo this semester. I'm not currently enrolled in it, but simply hearing about it from my classmates, I could tell it was dripping with the 21st century:

1. The course web-page makes use of Garrett Lisi's LaTeX hacked TiddlyWiki (downloadable here). Lecture notes are included, so there is a whole lot of potential for adding depth to lectures.
2. The mark breakdown for the course includes 10% for participation, which specifically encourages wiki contributions! You can either add to the course wiki or submit improvements to the math and quantum physics articles on Wikipedia.
3. Class projects suggest critically analyizing open-access papers on arXiv and presenting them to the class.
4. Assignments must be submitted electronically and LaTex typeset assignments receive 10% extra credit. Environmentally friendly!

As an aside, I have heard that the workload of the class is far too heavy, but it's definitely a step in the right direction. I have never heard of an undergraduate course which is so integrated with online resources. Even in Waterloo's prestigeous Computer Science department...

Death to the "PDF repository" course webpage!

People who read books are suckers. Why put yours eyes through hours of tortuous labour when you can trade the horrible noise pollution of the city for a beautifully read audiobook? My latest audatory book digestion was Christopher Hitchen's tirade on the big G in God Is Not Great.

In the book, Hitchens shares a fond memory of his grade school teacher informing the class that God made all the trees and grass the colour green because it was most relaxing to the human eye. For brevity's sake, Hitchens clarifies that “eyes were adjusted to nature, not the other way around” but it's really a fantastic question. Why is the grass green?

Colour mostly boils down to the absorption spectrum of a particular chemical element in an object. Flowers have evolved enticing colours to attract pollinators, birds/humans have evolved sexy tailfeathers to attract mates, but sometimes nature throws you a color you didn't expect. Especially with stuff that I expect would be either black or white.

Why are plants not black?

Plants are green because they are packed with the photoreceptor chlorophyll.  This pigment is used to capture energy from the sun to fuel the chronic plant craving for sugars. So if plants evolved to be truly efficient, why the heck are they wasting all that green light and reflecting it at us?

This post by Todd Holland at University of Illinois explains that plants get all they need from the sun in the blue and red portions of sunlight. In different sunlight conditions, astrobiologists theorize that plants may be completely black!

Why is the sun not white?

The surface of the sun is like 6000K. The emission spectrum of a black-body is definitely in the white area, so why does the sun look yellow and even orange at sunsets?

The sun is yellow for the same reason that the sky is blue. The molecules in our atmosphere scatter sunlight like nobodies business and since blue and violet light is scattered easiest, we are left with a red/orange/yellow looking sun. The sun is orangiest when light has to pass through more atmosphere when we observe it at dusk/dawn.

Why is the moon white?

Now that I've explained why the sun is yellow, why the heck isn't the moon also yellow? It's the same light as the sun and it travels through the same amount of atmosphere. Damn you science you make no sense!

The reason the moon appears white is because the light is too dim! Our eyes are too crappy at night time because we only use the rods in the back of our eyes which don't provide very good color information.

Why is space not white?

If there are 70 sextillion stars in the visible universe, why isn't space completely white? Dudes in the 1800's were all over this problem and it's known as Olbers' Paradox. I wish I had a paradox named after me... Anyway, Wikipedia gives the "mainstream" explanation as follows:

1. The speed of light is finite so a lot of starlight hasn't reached us yet.
2. The age of the universe is finite due to the Big Bang so beyond a certain point there aren't any stars at all.
3. Space is expanding so visible light gets shifted into the UV and microwave spectrum which explains that snazzy cosmic microwave background radiation.

Why are black holes black?

It seems obvious that photons cannot escape the super strong black hole gravity, but why? Photons have zero rest mass and equation for a gravitational force has mass in it...  so you should be saying "i dont c what u did there".

Turns out that Einstein came up with this crazy thing called General Relativity says that the geometry of space time can be curved, which in turn, can alter the trajectory of photons.

Why is snow snow white?

Tap water is clear, ice cubes are clear, and Dasani is the clearest of all since it costs extra. Snowflake whiteness comes from the complexity and imperfections of the snowflake structure. Light gets scattered all over the place and makes for the best Christmas ever.

What a pleasure it was to witness Sylvester Gates' gentlemanly afro today. Check out his 53 page CV here [pdf]. The famed physicist and Elegant Universe TV star gave a talk to the students of Notre Dame and to think I never even got my copy of Elegant Universe signed! I guess that will have to wait until next week?

Preceding the lecture was a room with multiple fruit, cracker, donut, and cookie platters giving physics majors ample opportunity to anti-socialize. Obviously the room was packed. Upon escaping several dead-end conversations and a laborious explanation of where Toronto was in respect to its closest state I found an engaging group of students. They explained that they received extra credit for attending this talk. America is corrupt like that!

There's no doubt it was the most enjoyable credits these students have ever earned because Dr. Gates knew exactly how to entertain. It was interesting to hear that his PhD thesis on supersymmetry was a topic unfamiliar to his adviser or anyone at MIT at the time. He likened his defense, in choosing a topic no one was familiar with, to James T. Kirk's reprogramming of the Kobayashi-Maru combat simulation to beat the system! Well put.

The talk was uncomfortably compressed from 1 hour and 45 minutes to just an hour, but thanks to many futuristic 3D animations of feynman diagrams, that had been developed for the Superstring Theory: DNA of Reality teaching company series, a lot of information was conveyed.

In typical theorist fashion, Gates gave the prediction of the positron by the Dirac equation as an example where the math came before the experimental result. Analogous to this in his own field would be the predicted Higgs Boson which will be tested next month thanks to a certain 7 billion dollar experiment.

I was especially happy to hear Gates promoting the LHC rap which proves that normal people other than bloggers really do use the internet. To wrap things up, he closed by praising the physicists working on LHC as 'Lords of the Ring'. Someone in the front immediately asked who Frodo was but I couldn't catch the name he replied! To be honest, I'm a little more concerned about the possibility of ring wraiths...

Jacks of Science is a bit of an experiment.

I hypothesized that the site would become a flourishing group science blog as far back as 2006.

To observe this desired blog state I devised a simple theory. I would mix a solution from a staff of student bloggers in different fields such as Physics, Biology, Geology, and Chemistry.

Would I be able to find reactants that formed a homogeneous mixture or a highly reactive substance on the brink of explosion?! Even if I found writers that worked coherently together, would I continue to get decent results over time? 

I figured that the greatness of Jacks of Science would be directly correlated with post diversity. Many authors would lead to diversity in post subject matter, writing style, humor, complexity, geekiness, and length. However, in theory, things are much different than in experiment. As you may have noticed, this diversity of authors ended up just being a diverse range of posts authored by me. I didn't follow through on my original plan of finding other writers since I was busy trying to become a better blogger myself.

The original intention of the site has been lost but, 102 posts later, as my domain renewal date draws nearer, you're looking at the results of the Jacks of Science experiment. Full of random art doodled on my class notes (which now includes my 1st and 2nd year!), to pro-piracy open science discussion, to science DJ mixes, to my most popular article: Science Valentines.

So I'm trying to draw some conclusions about the data so far. As far as the traffic indicates the site is growing in popularity but I'm just not sure if things are working out. Blogging is a lot of fun, but the Jacks of Science initiative, as originally imagined, has been stagnant for some time. It doesn't seem to be going anywhere for a variety of reasons off the top of my head.

• No clear audience that I'm writing for!
• No incentive for new writers to be part of the site!
• I can only post once a week by myself (quality over quantity)!
• Science is boring (and thus cannot reach a wide enough audience)!
• My single column blog theme is too narrow!