Thursday, September 30, 2010

Multithreaded Occlusion Culling

One of my personal projects was this optimized occlusion culling engine from Multicore Programming in Spring 2010. I worked on this project with Damon Rocco and Zachary Meister. Zach was the primary author of the paper, I wrote most of the rendering and parallelization code, and Damon took care of most of the geometric algorithms. Our results are detailed in a rather interesting paper found here: Occlusion Culling Paper

This project was interesting because it took a relatively small kernel of functionality, cell-portal culling and BVH culling, and focused intensely on optimizing out all bottlenecks. We attacked the problem on algorithmic, parallel, and micro-architectural fronts.

We used Intel TBB Tasks as our basic method of breaking off units of work. Combined with a recursive formulation of the problem this gave us a natural and efficient way to decompose our parallel work. Tuning of our inner "work" loops also brought insight into the performance considerations of small loops, memory alignment, and vector arithmetic. Interestingly, we were also able to make algorithmic improvements by exploiting temporal coherence between consecutive frames.

Besides the work discussed in the paper, I also took some effort to make the renderer efficient, which resulted in a roughly %50 speedup over a naive approach. Besides instancing of the models, we did an initial rendering pass that only drew depth. This enabled us to avoid unnecessary fill on pixels that would later be covered. In addition, to avoid unnecessary fill even earlier, we also performed a coarse depth-sort by dividing the world into octants and rendered front-to-back.

A demonstration video of our work is embedded below:

PennApps 2010

A very cool thing that happened recently was my team's victory at the PennApps development competition. This was a 48-hour judged hack-a-thon with the goal of "improving the student experience". At the end of the competition, each team gave a 2-minute pitch and product demonstration showcasing their work, to a wide panel of guests and industry representatives.

Our team, consisting of Lauren Frazier, Ryan Gormley, Sam Applebaum, and myself, developed a productivity app that allows students to print documents to our school's networked printers directly from an Android phone. This is very useful for printing the one-off bureacratic forms, homework assignments, and research papers that crop up in student life.

Android's "Intent" notification systems allows us to print documents from anywhere on the phone, including mail, downloads, or filesystem; you don't need to launch a separate application. Because we use existing Linux command-line print functionality under the hood, the user doesn't need any special permissions or drivers to install the application. Use of OpenOffice on the backend allows us to print even Microsoft Office documents, as well as PDF's, images, and web pages.

After our pitch and demonstration, our team won the $2500 Grand Prize. The application is available for free as SEASPrint on the Android market, and the source code is available at SEASPrint under GPLv2.

Below, I embedded a cute little promotional video our team put together:

Monday, September 20, 2010

Dynamically Reloaded Shaders

I first saw this technique from a brilliant engineer I worked with at LucasArts, Dominic Hamon.




Shaders are small programs that describe the lighting calculations for a surface. Due to their small size and the diverse array of potential graphics hardware, shaders are usually compiled and targeted at run-time, rather than statically. Most software I've seen takes little advantage of that fact.

Because shaders often have to be tuned to get exactly the right visual effect, many small changes occur during development. In addition, since step-through debugging and inspection of variable values usually isn't possible, one of the easiest ways to debug shaders is to visualize their calculations by outputting temporary values as surface color. Both of these lead to small frequent changes in shader files.

Since most software I have used or developed simply loads the shader on launch, this means that each small change to a shader requires an application restart to refresh. However, because the shaders can be loaded and compiled dynamically, there is no reason that changes can't be detected and incorporated while the application is running.

My implementation of this uses Windows file change notifications to track source files. When a shader is created, all references to it are tracked, and its source files are added to a registry of tracked files. If a change notification is received for a tracked file, we reload it, recompile all shaders depending on it, and replace all references to the previous version with references to the new.

My next plans for this include polishing the Windows interface (the guts are solid), implementing Mac and Linux version, and using this as a framework for the shader assignments in CIS 665, a class I help teach on GPUs. I feel like this could substantially increase student productivity.

Interactive Rendering of Large Fluid Simulations

I thought I'd start off this blog with a link-back to my last blog, that I maintained for Senior Design at Penn.

This project developed new techniques for visualizing large-scale fluid simulations using. We used a ray-casting technique to extract isosurfaces of a potential function, giving the surface its blob-by appearance. This technique is well suited to rendering particles simulations interpreted as fluids or gases.

To accelerate this rendering, we perform each pixel in parallel and accelerate our ray collision queries using a spatial data structure. A grid data structure in perspective space makes traversal a very regular and efficient operation, and is well suited for uniformly distributed irregular data. To support dynamic simulations, we rebuild this data structure from scratch each frame.

This project is currently stalled, but I may pick it back up in the next month.

Interactive Rendering of Large-Scale Fluid Simulations



Sunday, September 19, 2010

Welcome.

My name is Jon McCaffrey, and welcome to my personal software development blog. This site will showcase my projects, problems I encounter, and interesting technical tid-bits that come my way.

I'm a Masters student in Computer Science at the University of Pennsylvania. I studied computer graphics at Penn as an undergraduate, and worked for LucasArts last summer as a Core Engineering intern. My interests include graphics, parallel programming, systems, and mobile applications. Besides my studies, projects, and work, I help teach GPU Programming and Operating Systems here at Penn.

Thank you for visiting, and enjoy your stay.

Jon McCaffrey