Program The rantings of a lunatic Scientist

Archived Posts for July 2013

Voxel Rendering

Graphics Java

So today I thought I’d try my hand at Voxel rendering. Rather than existing in a 2D image plane with an X & Y coordinate Voxels exist in 3D space with a position in the X, Y, & Z axes. A prime example of the use of voxels in rendering is the popular game Minecraft. In Minecraft randomly generated terrain is modelled as large fields of voxels with each voxel rendered as a textured cube. Because the terrain is not just a surface coated in triangles but rather a volume with internal data, the terrain in minecraft can be modified and changed during runtime with little effect on performance.

Voxels are useful for displaying other kinds of volume data too. CT Scans are medical images which capture 3D density plots of a patient’s body. By capturing density at each location throughout the scanned tissue the data can be replayed using a computer to literally look inside the body and see where possible irregularities and illness may reside.

2nd year CT Scan coursework
2nd year CT Scan coursework

In my second year at university I was given a Computer Graphics coursework to read in and display the data for a CT Scan. It was very low resolution, only 256 * 256 * 113 voxels in size but it worked well for the purposes of the coursework which was simply to demonstrate the ability to parse the volume data into usable slices (not that hard). There were several bonus sections to the project such as histogram equalization and density bounding to eliminate tissue we didn’t care about. Another one of the bonuses was for rendering the volume data in 3D with a hint of using trilinear interpolation. At the time the work load we were under was horrendous due to the year long group engineering project, so while I eagerly completed all of the other bonuses I just didn’t have time to get 3D working. Until now.

It’s not pretty, and in fact it’s really not pretty when you make it 3D due to the low input resolution of the scan. But there it is! The same CT Scan now rendered in 3D in OpenGL. I used the Java bindings for OpenGL (JOGL) so I could use the same loader code I wrote in 2nd year to parse the binary CT file into a 3D array of shorts.

A note on Programming vs Software Engineering

L2Program Rant

Oh yes, gather round for another classic Joss rant explanation of common development myths and theories.

Today’s story comes to us from another reddit post, this time asking about why there is (in general) a stigma towards sites like Code Academy who aim to make programming excessible and easy for the masses.

I think a big thing here that just needs to be stated is that Programming is not the same as Software Engineering.

Anyone can go online and learn a programming language, the syntax is relatively easy and sites like Code Academy do a pretty good job of teaching that most of the time. But they teach two things, “syntax” and the very very very basics of “program structuring.”

Developers give sites like Code Academy a bad rep because they actively (if not always intentionally) promote the idea that coding is the same as building a piece of software. They say…

Anyone can do <it>! <It's> easy! Come here today and learn <it>! <It> only takes an hour or two…

<It> being to write lines of code in a text editor and run it, but implied to mean you can start the next facebook.

Software Development is barely connected to coding. The code and the language are just how you write it down and give it to the computer. Yes, there is a lot of coding, sometimes millions of lines of it in a large system. But that pales in comparison to what those lines of code represent.

When you design software you build based on design patterns. Not every pattern is perfect for every situation which is why you need to know a lot of them so you can use the best one for each job. Similarly within those patterns you will be using data structures (arrays, hash tables, linked lists, databases, ect). Again, not one of them works perfectly for every use case. You need to know how they work and which is the best to use for each situation.

Anyone can learn to write int[] a = new int[10]; or HashMap<String, Object> t = new HashMap<>(); in five minutes. It takes a lot longer to learn how they work and when to use them.

That is the difference between “programming” and “software engineering”, and that is why so much of the development community look down on sites like code academy. They paint a false image of the industry and the profession that many of us have devoted many years of our lives and education to.

Now. This is not to say we all know everything and what is best. This is a constantly evolving and changing field and we all are constantly learning and reworking the way we approach the problems presented to us.

I don’t mean to sound discouraging, if I have appeared that way thus far then please have my apologies. That was not my intention. My intent was show why the when the entire world has the ability and accessibility to learn to program and the attitude that they can master web developement and start the next instagram and that it will all be easy because computers are so good these days, that we will still be the same industry we had before they all learned and we will still be the “valued” workforce that we are.

Because you just can’t learn everything we’ve learned by doing tutorials online. Yes we too do online tutorials, watch lecture videos from conferences, go to seminars and master classes.. Yes we do those things too. But we have also been actually doing this work for years, learning from real-life projects, and directly from colleagues who had been doing this far longer than us. Many of us went to university and exclusively studied Computer Science, and algorithms, and software engineering, and project management and lots of other things we use every single day on the job.

In essence, Code Academy and everything it stands for only seeks to invalidate and deprecate everything that gives our experience and our industry value. Even if they did it under the best possible intentions.

A note about GPGPU for the masses

C/C++ GPGPU L2Program Rant

A note about the growing trend towards GPGPU for the masses. This is my response to a Reddit post I saw about a new GPU language, I felt I should copy it here.

As someone who does a lot of development using the GPU a new language is the last thing I want. Programming for the GPU is complicated, it just is, and it should be because what you are running your program on is a very complicated piece of hardware. You have to treat it right and you have to structure your programs and algorithms in a specific way which is not common to other architectures.

All these attempts lately to make GPU programming easy and doable for everyone (the LISP and Haskell libraries come to mind) completely miss the mark. They work under the premise that if you make it easier, everyone can make everything GPU accelerated, and that that will be better. It won’t.

Half the problem with current libraries that make CPU concurrency easier is that people start parallelizing too early. They don’t fully and completely optimize something they already have, they don’t go in and profile it, they don’t notice long system calls and work in a bit of assembly which will reduce the latency. No. Instead they will just chuck some threads in there, because threads make things faster… It’s just not true.

This problem is even more volatile on the GPU. It’s a delicate balance and not every job is suited to the GPU just as not every job is suited to multi threading on the CPU. Giving people (the uninformed people at least) the power of the GPU for every conceivable task is just daft.

When you structure programs for the GPU you need to have full and complete control over everything it does and when it does it. Languages like OpenCL and CUDA may be complicated but your kernels do what they say they do. It’s exactly why writing good C is complicated because you are right on the hardware level with very low abstraction. OpenCL and CUDA don’t try to optimize what you wrote (past a few compile time optimizations which are to be expected) they translate your commands onto the hardware nearly directly. The downside of that is it means you need to fully and completely understand your algorithm and how the hardware will react to each stage of it, the benefit is incredible performance and massively parallel execution.

TL:DR GPU programming is hard for a reason and giving everyone an easy way to do it completely misses the point. It’s like trying to make everyones car into a supercar by handing out nitrous injectors.

A better Bi-Directional Path Tracer

Graphics Java

So I’m back to working on this again.. It’s a lot better than before but it’s not perfect. I’m still using unweighted samples during path generation and I am still generating a fresh path (highly randomized in path traced -> light traced construction) for every sample. Because of this the noise that still persists in the image above will never feasibly go away. Today I plan to look at “Multiple Importance Sampling” a lot more in depth.

Lego 3D Printer: XY Carriages nearly complete

3D Printing

This morning I was neck deep in code writing a Bi-Directional Path Tracer and this evening I’m building a 3D Printer out of Lego… If only I had the attention span and patience to actually finish a project before starting another. Oh well.

Continuing on from my previous post, in the end I actually trudged down the garden to the shed and pulled all my old Lego Technic out of storage. A quick session of sorting out what kind of bits I had and then thinking about how I could adapt the designs I had bad in CAD to work within the limitations of those parts I decided to just delve in and see what I could make. I was surprised at how much Lego I actually had, but then again my family was always really into Lego & Meccano; and I was quite fond of Knex too come to think of it.

As it turns out the amount of Lego Technic I do have is more than enough to build the frame and mechanics for the first two axes of the Printer. There are some crucial areas however, where I have ran out of very important bits needed for this specific application. For instance the flat toothed strips used to make the tracks for the carriages to walk on were in short supply. I managed to place them on the top carriage such that the X axis gondola can fully utilize them with no waste. However after laying the X axis track there were only four of the tooth strips left; meaning that for now each side of the Y axis tracks only has two toothed segments. I’ll need to get more of them to finish the Y axis along with some gears and extra chain for connecting the cross axle to the walking gears.

It was possible to make some improvements to the initial design during this first build step. Namely the Y axis walker which holds the X axis and gondola is considerably thinner than in the original design, however the gondola still has nearly the same amount of movement. This was achieved partly by making the two connections to the Y axis tracks thinner than their originals, which allows the gondola to travel much closer to the ends of the track. The condensed size also keeps the frame more rigid than a wider variant would have been.

Lets build a 3D Printer

3D Printing

A month or so before I found out I would be starting my PhD in October I was still under the impression that I would be doing an MEng and with it another dreaded dissertation project. This time however, the project would be to do with a software engineering problem, as opposed to last years which could be either industrial, research based, or software engineering.

After much deliberation looking at the shockling short list of projects I decided that I didn’t particularly want to spend a year working on any of them. Not that they were all bad per say, just that if you’re going to spend a whole year working on a single project you best be sure you care about it.

One thing that did interest me about the projects however, a few of them involved using Arduino and embedded systems. This got me thinking, what could I do with Arduino that I could propose as my own project idea? Inspiration didn’t take long, that night I stumbled across this gem while watching random videos on Youtube.

I loved it straight off, to use Lego Technic and Mindstorm NXT to create a working CNC machine! Perhaps this would make a good masters project?

Alas the the project is very much closed source and even the designs for the machine are not available.

I have however, been able to reproduce the design of the machine and it’s mechanics in 3D using Lego’s 3D Autocad software, Lego Digital Designer. This was a long and painstaking process of taking screenshots of the above video and blowing them up to see the finer details (thank god for 1080p Youtube streaming) and mixing this with my methodology for how I would build this machine if I was given an unlimited set of lego. The result of my reconstruction can be seen below. While it is not a complete build (I omitted the static Y-Axis track that the carriage pictured would ride on), it is the technical majority of the machine.

I believe that this design can even be further improved upon to use less lego while allowing for a larger and more stable device to be constructed. The main limitation with increasing the track size of the device in it’s current configuration is finding a way to proportionally increase the size of the Z-Axis (vertical). Currently this axis uses two Lego Technic linear actuators to move the tool carriage up and down. However, the actuators have a fixed and limited range of climb which cannot be altered. A difference approach might be to use a threaded bar configuration to make a track which moves up and down instead with a small tensioning system to remove vibration and slack from the printing.

Bi-Directional Path Tracing

Graphics Java PhD

After a minor crisis that I am horribly unprepared to start my PhD in October I thought I’d try to delve back into the world of graphics with something simple (ha). I decided to try and extend my Java Path Tracer to support a rendering mode for Bi-Directional Path Tracing. Something which I now realize is easier said than done. Ideally if I had had the time I would have introduced Bi-Directional Path Tracing (BDPT) to my dissertation project last year; however, I simply never had the time to wrap my head around all the mathematics so I left it out.

The image above was rendered at 640 x 480 but I have downsampled the image here to 320 x 240 to make up for the fact I was only able to render 100 samples before my computer BSOD’d. That’s right, because if you can make a Java program cause a BSOD then you know something is terribly amiss. My theory is that it’s simply too much recursion for the JVM. Even though I am running the 64bit version with an increased memory quota the stack for function calls is still (annoyingly) a memory limited 32bit stack. And seeing as this is just a toy project I am working on whenever I start to panic about next year it doesn’t seem worth spending the time to convert the whole thing to an iterative renderer from a recursive one.

From Graduand to Graduate

PhD University

And to think, the caller only mispronounced my name three times in a row.

Josh… Jose… John.. … Fred?

No idea how he could do all the foreign names but he couldn’t say ‘Joss’ properly.

Now begins the long (and somewhat painful, I’m led to believe) journey to getting my PhD.

Sine Mesh using OpenCL + OpenGL Interop

C/C++ GPGPU Graphics

I’ve been meaning to do it for a while but I have finally gotten around to making a Template for OpenCL & OpenGL Projects in Visual Studio 2012.

The host application is written in C++ using GLew and freeGLUT to interface with OpenGL, and the Amd APP SDK to interface with OpenCL as I am running a ATI 5850 GPU. Building upon the template is fast and easy and really comes down to just a few core functions which differ for each program. Below is a simplified version of the functions each program must implement.

Using this frame as a base to build off of I was able to quickly and easily get a demo running. The program in the video above and the images below generates a 1000 * 1000 (1 million) vertex triangular mesh and displays an exponential sine function over it. At each frame OpenCL computes the 3D location of all 1,000,000 points in the mesh which OpenGL then renders. Due to the massively paralleled nature of the OpenCL update code frame rates exceeding 100 frames per second are achieved! (In the video Fraps capped the frame rate at 30fps for smooth capture)

Below is a simplified version of the SineMesh Demo, most of the work is performed in the initialization phase to create the 1000 * 1000 mesh and link the triangles together. The program could be made a lot more efficient if the triangle linking phase was done such that it creates a Triangle Strip as opposed to the current Triangle List. A strip has the benefit of chaining touching triangles together to save the number of vertices which need to be stored in the linking array.

The OpenCL Kernel

The (simplified) Host Program