A scene rendered by ZeroRay illustrating reflection and refraction. The glass orbs both reflect and transmit light through them.

ZeroRay began its life as a ray tracer. Building a ray tracer from scratch was one of the large projects for a graduate level computer science course I took called Image Computation. I ended up using ZeroRay in a lot of other projects and it has evolved into a ray tracer/computer vision (CV) toolkit with a suite of deep applications that are both interesting, and illustrate how to use ZeroRay.

I have released ZeroRay as open source software, under the BSD license. The BSD License is pretty much the most liberal open source license. The basic jist is that you can use the code for anything you want, be it open or closed source, commercial or non-commercial. All you have to do is give the author credit for using their library. You can visit the ZeroRay project page at sourceforge. At the time of this writing, I haven’t prepared any convenient downloadable packages so you will have to check the code out of the svn repository. To do so click Develop on the project page and follow the instructions there.

If you’re wondering, “What’s a Ray Tracer?” check out my previous article What is Ray Tracing?

Back to what exactly ZeroRay is. ZeroRay is a software library (or more precisely a set of software libraries). That means it is a set of tools that are used by programmers to create applications. A simple application could be one that, when executed, draws a pre-set picture and saves it to an image file. A more complex application could be a program that allows you to set up a 3D scene by dragging objects into it a low quality rendering of the scene and then invokes the ZeroRay ray tracer to generate a high quality version of the image. As a bit of an aside: ray tracing is a way to generate very high quality computer graphics, however it is significantly more computationally intensive than the techniques used in real-time renderers, like the sort that are used in video games. To make the ZeroRay ray tracer widely useful to computer artists (who generally are not programmers), it would need an application similar to the second example. But ZeroRay is more than a ray tracer. (more…)

An image of the statute of Athena rendered by ZeroRay.

There are two approaches to the computer graphics problem:

1. For each object in a scene, project it onto the screen, then color in all the pixels that it covers.
2. For each pixel on the screen figure out which object in the scene it points at, then color the pixel the color of that object.

The first approach is the one used by mainstream, real-time graphics toolkits like OpenGL and DirectX. The second approach is ray tracing. This may seem like a fine distinction, but this choice determines what sort of things end up being hard or easy later. (more…)

An example of a background/foreground segmentation from Janusz Konrad at Boston University.

After working for quite a while on the “motion detection” algorithms described in my last article, I was clued in to background subtraction. Or rather, it finally hit me why, when explaining what I was working on, people kept saying, “Oh, you’re doing background subtraction.”

Background subtraction is the keyword for a relatively well explored nook of computer vision. The motivation for background subtraction research is that, in an image, there is usually a part of the image that you care about (the foreground), and a part that you don’t care about (the background) and it would be nice to focus only on the parts that we care about. There are many justifiable ways to divide a single image into foreground and background sections if we use the criteria that the foreground is “things we care about” and the background is “things we don’t care about.” The colloquial distinction is that the foreground is usually closer to the camera, in focus, and more interesting than the background. The last is where subjectivity enters the equation. In the field of background subtraction and in the context of video, the consensus is that the background is the part of the image that does not belong to a sizable moving object. This is still a big vague but different algorithms have different ideas about what constitutes a background. (more…)

Videndo Aedificare is a project I’ve been working on as a part of my coursework for CS612, Advanced Topics in Computer Vision. The name means “By seeing, to build” (according to Google translate) and that is exactly what it attempts. The goal of the project is to build a rudimentary system that takes a real time webcam feed and builds a 3D model of the viewed scene.

Introduction

The project was inspired by a paper by Pan, Reitmayr and Drummond called ProFORMA: Probabilistic Feature-based On-line Rapid Model Acquisition. Actually, it might be more honest to say that the project was inspired by the video that the ProFORMA authors posted on YouTube.

For a discussion of ProFORMA and feature based approaches see my article, Feature Based Approaches: ProFORMA.

Videndo Aedificare (VA) does not use a feature based approach. I had wanted to at first, but decided that implementing a state of the art structure from motion system is beyond what is feasible in a semester project for a one person team (read: was talked down by my professor). Videndo Aedificare is built on my 3D graphics/computer vision toolkit, ZeroRay (which is a topic on my article todo list for this blog that keeps getting put off!). Its primary goal is to present a framework for exploring real time structure from motion algorithms. It provides a neat API to subscribe listeners to a connected webcam and classes to display results, either 2D images (which may be intermediate results for debugging), or 3D scenes. Videndo Aedificare uses the Ogre open source rendering engine to provide 3D views. Camera listeners implement a receiveFrame method, by which they are passed the current camera frame, and given time to operate on it. Often camera listeners have their own views to display results side by side with the raw camera feed.

Simple Builder

VA's Simple Builder. The webcam video stream picturing my monitor wearing a festive hat (left) beside the 3D rendering of the model constructed from the scene (right).

As a proof of concept, and to test my framework, I implemented the most naive scene reconstruction algorithm I could think of. It assumed that the intensity of a pixel was inversely proportional to the distance of that point to the camera. In other words, bright pixels are close to the camera, dark ones are far away. Simple Builder generates a polygonal mesh from each frame by first making the image greyscale and then interpreting it as a height map. The maximum and minimum heights are parameters and the greyscale values are interpreted between them. The visual effect is rather interesting. (more…)

I’ve decided to release a few classes that I think would be of general use under the MIT liscence.

JWCommon 2009-02-04 focuses on classes for storing, recalling, and grouping options. Options can be any named value that can be represented by a string. I had application preferences in mind when I wrote the code but there is no reason the code is limited to that use.

Features:

• OptionsManager – Store and lookup options by name and group
• OptionsFileManager – Save or load all the options directly to or from a file 
• Ini file format implementation provided, easy to add your own file format implementation.
• String conversion/parsing utility methods
• Clean object oriented design
• No dependencies on other libraries (other than the c standard library)

Download Source Package

Download MSVC2005 binaries

(more…)

The fundamental goal of a game AI system is to make the non player characters appear smart. Well, that may be over reaching a touch; making the non player characters appear not stupid is a high enough bar for my AI ambitions on this project. The problem is that it is very difficult to make an AI that can compete in a wide array of situations with even the most developmentally handicapped elementary school student.

There are a few impressive applications of AI concepts that have been developed but they all apply only to a very specific, or a set of very specific situations, and usually they have a lot of help. By a lot of help, I mean, autonomous vehicle systems that work splendidly as long as they are given gps waypoints every couple meters or warehouse management robots that read barcodes off the floor to determine where they are and are fed the locations of every other robot in the warehouse so they don’t collide. I certainly don’t mean to demean either of the two systems that I mention, but to my childhood-sci-fi idea of artificial intelligence, they seem like cheating. They would also fail to follow instructions that our hypothetical kindergartener could perform with ease, such as: “walk to school,” or “find all the red things in the warehouse.”

Well, if those seem like cheating, game AI will seem like reading the answer out of the back of the book. Or, in the case of my Pathfinding AI system, precalculating every answer, then just looking up the one that we need this time. (more…)

There are two basic shadowing techniques that are commonly used in real time rendering: stencil shadows and texture shadows. The stencil shadow technique (also called shadow volumes) works directly on the geometry to project shadow volumes through the scene. The texture shadow technique works by rendering the scene to a texture (jargon that simply means image) from the light’s point of view and using that texture to determine where shadows fall during the rendering process of the output image (what you see on the screen). Both methods have distinct advantages and disadvantages and the myriad array of sub-techniques and specialisations of these two umbrella techniques makes choosing a shadowing technique suited to ones own uses a bit of a task. Describing, or even enumerating all of the sub-techniques that have been used or proposed is outside the scope of this article (read: outside the scope of my evening). I may write some articles in the future about the sub-techniques that I think are wonderfully clever (and some of them are deliciously clever) but for now, the basics. How does anyone get any shadows on the screen in the first place?

(more…)

I remember the first time I started looking into shadows. It was back when I first started working with 3D graphics and I had this naive idea that 3D graphics were so awesome because they were simulating nature. Learning about real time shadow rendering techniques quickly killed that idea. Learning about other aspects of real time 3D rendering like geometry and lighting I suspended the realization that it is all just smoke and mirrors, by imagining that if my computer were just faster, I might be able to take into account enough detail to actually be simulating how light works, rather than just making a nice picture with a pseudo-approximation of how light works. But when it comes to shadows, that rationalisation rolls over and dies. The methods used to create the appearance of shadows in real time rendering (and as far as I’ve researched, in offline rendering as well) are far removed from the real world physics that create shadows.

(more…)

The cloud system has come a long way since I first posted about it. I suppose technically, it has come a long way since yesterday when I started working on it again, but that didn’t sound as dramatic. After a long while working on other aspects of the game, the Toolset GUI for one, but many other bits that I haven’t mentioned, I came back to the cloud system with a fresh eye and took it in a different direction than I had been imagining.

(more…)

I have a habit of taking a screenshot or two every night after I finish working. I often find myself looking back on a week and feeling like I didn’t actually accomplish anything. Thanks to my screenshotting habit, I now know that this empty, unfulfilled feeling is just because I’ve forgotten everything that I did all week. By the time the weekend comes around, all the little bugs I fixed, features I implemented and puzzles I solved are gone from my mind. Well, it’s more that they’re in my mind somewhere, but I’m not sure where. It’s a case of, “I haven’t lost my car keys, they’re here somewhere! I just.. don’t know where” syndrome. Looking back on the screenshots I’ve taken each day reminds me of what I accomplished and all those little bugs I fixed, features I implemented and puzzles I solved come flooding back into my mind. This fosters a Sense of Accomplishment, which not only feels nice, but is necessary to maintain momentum and stave off burn out.

(more…)