Math - Random numbers and splines

I came across my old favourite website on random number generation today whilst browsing so that inspired this post.

Random numbers are a key component to so many things, from generating interesting textures, to selecting chromosome pairs for a genetic algorithm optimization problem. I've found the choice of random number generator can have a massive impact on some GAs.

Here is a list of Linear congruential generator (LCG) random number generators with spectral analysis, discussions and properties. It's a fantastic resource.


iq of rgba has a great article on small and fast random number generators for floating point numbers.

Splines are another great mathematical tool for any programmers bag of tricks. They are used in animating characters to robot control systems. The GDC 2009 maths tutorial has a great introduction to splines. Cubic provide a good introduction with pseudo-code for Hermite (the best) splines.

A really interesting find today was Time constant splines. I'm a bit skeptical about it on how it works (re-interpolating and re-fitting splines to get 'smooth' interpolation steps) but the author claims good results, and I'm sure it would be good enough for camera paths etc.

University Rankings

Having lead a relatively academic life so far and being involved with lots of teaching people often ask me what the good universities are. It's hard to come up with something on the spot that you can really stand by.

Often people are considering traveling and living somewhere at great expense - you don't want this time, effort and money to go to waste. Luckily I have come up with a relatively fool-proof way of answering this question.

Any university with 20+ nobel prize laureates is probably quite decent. If your studying a nice solid established field then this should be the guide you use. If your in a new field (CS) then perhaps pay a bit of attention to the Academic Ranking of World Universities compiled by Shanghai Jiao Tong University. This ranking I believe acts as a bit of a 'predictor' for future nobel-success, since the nobel prizes seem to lag a bit behind the times, regardless of their original intention.

Without further ado, here's the list:
University of Cambridge (4th Academic Ranking 2008 - SJTU)
University of Chicago (9th Academic Ranking 2008 - SJTU)
Columbia University (7th Academic Ranking 2008 - SJTU)
Massachusetts Institute of Technology (5th Academic Ranking 2008 - SJTU)
University of Paris
University of Oxford (10th Academic Ranking 2008 - SJTU)
Stanford University (2nd Academic Ranking 2008 - SJTU)
University of California, Berkeley (3rd Academic Ranking 2008 - SJTU)
Georg August University of Göttingen
Harvard University (1st Academic Ranking 2008 - SJTU)
Cornell University
Ludwig Maximilians University of Munich
Yale University
New York University
Princeton University (8th Academic Ranking 2008 - SJTU)
Johns Hopkins University
California Institute of Technology (aka CALTECH) (6th Academic Ranking 2008 - SJTU)
ETH Zurich
University of Heidelberg
Humboldt University Berlin
University of Illinois at Urbana-Champaign
University of Manchester
Washington University in St. Louis
University of Zurich
University of Pennsylvania
Technical University of Munich
University of London
...
Noteable CS-strong sub-20's:

Carnegie Mellon University (17)
University of California, San Diego (17)
Uppsala University (15)
Imperial College London(14)
University of California, Los Angeles (10)
University of Texas at Austin (9) + Dallas (3)
University of Tokyo (9)
University of Vienna (9)
University of North Carolina, Chapel Hill (7)

Australian Universities:
University of Melbourne (6)
University of Adelaide (6)
The Australian National University (3)
University of Sydney (3)
University of Western Australia (2)

Of course, if your interested in a specific area, eg: GPGPU's you can look further down the list (eg: Georgia Institute of Technology (aka GATECH) (2)). CS is usually one of the more tricky ones since Maths/CS/etc don't get any nobel prizes. But that doesn't make Cambridge, MIT, and Stanford any less good...

Multithreading

Multithreading is often a difficult concept to explain, but I've seen this excellent explanation over on gamasutra, "OMG, Multi-Threading is Easier Than Networking".



Finally a good use for cats.

Of course, anyone who wants some quick boosts from multithreading should take a closer look at OpenMP. This technology is seriously under-rated. And since MSVC supports it out of the box now, there really isn't any good reason to not use it.

Intel pushes their Threaded Building Blocks pretty hard, but I don't much see the point of it. I don't want my applications to scale so much anyway (the only real benefit as far as I can see). At some point MPI just makes more sense. And of course OpenCL if it lives up to its promises..

Torrents and Vivaldi

Downloading torrents is always a good way to churn bandwidth. My favourite client is uTorrent, but Vuze will often be a better cross-platform solution. Of course, for the ocasional rare download the Opera browser will do a fantastic job as an all-in-one (web, email, news, torrent, irc, WOW!)

One way to preserve your download quota is through using local peers, you can do this via these handy
IP addresses for Australian peer networks (eg: WAIX).

Another alternative is to use something like Vivaldi (paper includes pseudo-code). Bittorrent clients normally choose the highest bandwidth connection over lower-latency (ie: closer) connections. Ono is another option/plugin for Vuze that will let you prefer closer clients.

The algorithms are quite straight foward although computationally intensive. A good choice for GPGPU?

GPGPU Workshops

So some big news, finally nVidia released OpenCL, you can apply to become a developer:
http://www.nvidia.com/opencl

Some news locally:

Next thursday, 7th of May, "GPU Computing Workshop" at UWA, all day.
Talks from nVidia, UWA, Xenon about a range of topics.

Next friday, 8th of May, "GPU Computing Tutorial" at WASP at UWA, 9am - 1pm.
A hands on session from nVidia.

More info at UWA WASP news.

nVidia has sent over Mark Harris (founder of GPGPU.org) for the two events.

Should be good!

AMD GDC09 Presentations

The AMD/ATI GDC09 presentations are up now, it is interesting to see that ATI is slowly becoming more open source / open tech friendly, I think the AMD merger helped in this respect. Since then a lot of good low level tech from ATI has been opened up including AMCL GPU.

A few articles caught my eye, the AMD Stream Physics sounded interesting, but was an empty presentation, more or less saying 'We also think OpenCL is neat'. At least AMD and Intel are both quite committed to OpenCL so it ought to be a success.

The most interesting presentations were ones that covered new DX functionality like "GDC2009: Shader Model 5.0 and Compute Shader". Other good ones covered applying old techniques to new GPU capabilities such as "GDC2009: D3D11 Tessellation" (bezier patches for tessellation, what a great idea, why didn't I think of that?), and "GDC2009: Authoring for Real-Time Tessellation and Displacement Mapping" covers the technical artists side of this.

"GDC2009: The A to Z of DX10 Performance" is an interesting read as it comes from ATI and nVidia together and cover some interesting performance aspects. Apparently rendering a single screen tri is faster than a single screen quad, and dynamic branches are preferable now. News to me!

My favorite was "High Quality Direct3D 10.0 & 10.1 Accelerated Techniques". Mostly because of the real world examples of modern (HD) SSAO. One of my favorite tools. Mind you, it would be interesting to see how this stack up against Accumulative SSAO...

Soft Bodies

Since Bullet physics engine added soft body support that brings the number of publicly freely available physics engines that have soft body support to 3. PhysX, OpenTissue and Bullet. So that seemed like enough to justify adding softbody support to PAL.

PAL now supports cloth/patch based soft bodies, and tetrahedral deformable bodies.

Bullet has basically designed the softbody system as completely separate from the rigid body system, so this makes it a great system to abstract since it will make it possible to implement a softbody system that does not directly rely on the underlying physisc engine, bringing softbodies to ODE, Newton, and friends that do not have it yet. Same plan is for the SPH fluid code I've written, but those are both still on the TODO list to integrate to PAL.

Of course, the remaining issue is how to generate the tetrahedral descriptions.


Some options I've investigated:

• The PhysXViewer should be able to do it.
  
• Apparently Qhull can generate tetrahedron (how convenient!) using the 'qhull d QJ i' option. This would be a good option since Qhull is a widely employed library.
  
• TetGen, seems to be a rather large library, given its special purpose nature (generating tetrahedron), but says it is optimized for finite volume/element methods.
  
• GNU Triangulated Surface Library says it can create tetrahedra, but I'm not sure if this is only for isosurfaces.
  
• NETGEN claims to create tetrahedral meshes from CSG
  
• Cubit is a massive library from sandia that claims to generate tetrahedral meshes.
  
• libmesh can work with tet4, but I've not investigated what inputs it can take.
  

And during my googling I came across SLFFEA an open source finite element analysis tool. Cool!