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. Read the rest of this entry »

A game being played in the Google AI Challenge 2010

Well, the google AI challenge is over and my bot finished 1143th out of 4617. That’s a bit of an underwhelming finish, I agree, but there’s more to tell. Given the game the bots were to play and the severe time restrictions the bots had to choose a move each turn, the challenge was dominated by, what I call, tactics bots. That is, they rely on hand-coded tactics based on the programmers expertise on the game. The design cycle goes a bit like this:

1. Designer reflects on how they play the game and thinks up a way to codify a way to choose good moves
2. Implement the idea
3. Play the bot against others and see how it does
4. Reflect again and think of new information to consider when choosing good moves and how it can be integrated with the previous ideas
5. Goto step 2

I don’t mean to denigrate this approach,  it is the basic premise of every bot AI from a commercial video game, that I’ve seen the code for. This approach often yields a bot that scores very well on the (very technical) goodness vs. time per move metric.

Read the rest of this entry »

This blog has been quiet the over the past year. With this post I’m officially putting the Sanguis project out to pasture indefinitely. I have not worked on the project this past year and I do not expect to come back to it. That said, I’ve been very busy on other projects (and university) and some projects that began as university projects. I had been hesitant to write about my other projects here, because they weren’t Cutthroat Studios projects (in other words, they weren’t Sanguis related). But with the realisation that I won’t be coming back to Sanguis, Cutthroat Studios needs a new project. And I have a few just waiting in line.

Games and graphics are what brought me to programming. They’re what brought me to computers. I still have a deep interest in graphics, and that interest shows in the projects I’ve chosen to take on recently. That said, my interests have expanded as I’ve been introduced to more facets of computer science. Read the rest of this entry »

Engadget reports on a clock that runs on energy derived from digesting insects that it captures. They incidentally mention a Japanese project that worked on fuel cells that run on blood. The intended use was for embedded medical technology (think pacemakers) where the concept of a non-toxic fuel cell that runs on you makes a lot of sense, but I can’t help thinking of that terrible war of the worlds remake with Tom Cruise where the tripods go around harvesting people to fill their tanks full of blood.

Creepy huh? At least Skynet was solar powered.

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

Read the rest of this entry »

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. Read the rest of this entry »

As my regular readers have already noticed, there’s been a bit of a slowdown in my writing lately. There’s been a slowdown in work on Sanguis and Ashes as well. I’ve returned to school to finish my degree in computer science. Wish me luck! I have my fingers crossed hoping that when I get out, degree in hand, there will still be an economy left in which to use it!

American english has a serious deficiency of truly shocking expletives. Perhaps it is the paradoxical climate of verbal permissiveness where almost any profane utterance makes frequent appearances in popular media that has desensitized us, and thereby rendered our expletives impotent. When an american wants to use an expletive powerful enough to startle old ladies and make mothers hide their babies, there is really only one option these days. It is unfortunate that when american culture diverged from british culture, certain expletives were left behind. Words like bloody became mundane rather than profane. When we hear them used as utterances of frustration or anger, they sound more quaint than shocking. If it were not for religion, the only expletives we would have would be base remarks about excrement or improper sex.

People of the United States, use your expletives sparingly! Save them for when you truly need them or before long they may be about as shocking as exclamations from a 50′s sit com. Or better yet, invent your own horrifying epithets.

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?

Read the rest of this entry »

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.

Read the rest of this entry »