Raytracing + Pixel Shifting

Home --> Programming Projects --> Raytracing --> Raytracing + Pixel Shifting

Basic Idea

Consider rendering a first person computer game. Every cycle the entire screen is being redrawn (it would be strange not to do this!). When the player turns his head, for instance, the entire screen is likely to change. Imagine that the cost of determining the color of each pixel on the screen each frame is high. If we could somehow "move" the pixels on the screen everytime the player turns his head or walks, we would partially construct the next frame to be rendered. Of course, there will be holes and all sorts of bizzare artifacts. The goal is, however, to partially remove these artifacts by selectively rerendering part of the screen (rendering only a small portion of the pixels on the screen can be accomplished by raytracing). I call this algorithm (that moves pixels on the screen from one frame to next frame leaving holes that need to be filled) Pixel Shifting.

Thus, we want to be able to freely alow the user to move through a world while only computing the color of a fraction of all the pixels on the screen per frame. The paridigm is to keep track of what information is already on the screen and what information is being added (sort of like in video compressing). Many scenes are too dynamic for this method to work. However, static scenes (scenes where nothing is moving except the camera) with diffuse surfaces (surfaces whose lighting looks the same when being viewed from any angle) may be animated with this method.

Why Raytracing?

The point of this method is that only part of the pixels on the screen need to be redetermined from the world. With raytracing, we can cast a ray into the world for each pixel that we are unsure about. The amount of computations being done would be proportional to the number of rays being cast into the world. Rasterizing, on the other hand, would not be doing work proportional to the small number of pixels needing to be refreshed (because rasterizing is designed to refresh the entire screen so it would be doing extra work). Again, the premise is that only a relatively small number of pixels on the screen need to be refreshed each frame.


I wrote a computer program to perform this algorithm for a Computer Vision class final project. Note: the teacher was a little mad because it is really not computer vision. The algorithm loosely falls into the category of image based rendering (but with way more information (depth information) than what most image based rendering algorithms are allowed to use!) It might be that this algorithm already exists but with a different name, but I was unable to find it in the literature (maybe Computer Vision isn't the right place to look!)

Here is the final project paper that describes the algorithm that I worked out. The algorithm is not very complicated. It is not exactly "pixels" that are stored but "points in 3d space". Points have various information associated with them such as 1) position in 3d space, 2) color and 3) when was the point added. These points are then used to determine the color of each pixel in the frame to be rendered by using bilinear filtering. These points are stored in buckets (one bucket per pixel), and points are thrown away when there are too many points per bucket (always throwing away the oldets points so errors do not accumulate). Of course, points could be stored in some other fashion (such as in buckets that correspond to different longitudes and latitudes of a sphere surrounding the camera). It is tempting to "merge" points together combining all their attributes, but this leads to horrible artifacts! Parts of the screen that have the least of information (which is determined by counting the number of points per bucket) are candidates for where rays are shot into the world for raytracing.

The above left picture shows a frame being rendered normally, and the right picture shows the frame that is rendered only by shifting pixels from the first frame according to how the camera was moved.

This algorithm (and its implementation) is far from complete. For starters, the algorithm needs to be better at temporarily filling in holes in the image to be rendered. Secondly, the algorithm really needs to implemented on a GPU! The latter seems plausible, as the alrogithm is really quite simple.

Interesting Benefit

One very useful aspect of this algorithm is that rays can be cast into the world on a remote machine and this pixel information can be sent to the user's machine. Even if the information arrives late, the updated pixel can just be "moved" according to how the user's camera moved from when the pixel should have arrived to the present. This is a neat feature of the algorithm.

Potential Use Case

Consider a first person online game where users can view vast amounts of information in the distance. We can assume that all the moving objects in the distance will be too small to view. The scene in some reasonable radius of the user can be rasterized normally, whereas everything beyond this radius is treated as a background that is rendering using the Pixel Shifting algorithm. As the user moves from area to area, the background gradually changes (remember that the algorithm throws out the oldest points). With this method, "low level of detail" versions of far away objects are not needed.

Moving Objects in the Scene?

One can imagine extending this algorithm to work in more general situations, but that is really pushing it to the limit! For example, if the scene has moving objects, then pixels being stored on the screen can be "associated" with those objects; those pixels are moved not only according to how the user moves, but also according to how the object moves. A much greater problem, however, is caused by the shadows that are created by moving objects. A moment's thought is enough to see that this is an unmanageable situation!