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.
Implementation
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!
