CS 631 Final Project
6 May 1998
Jiesang Song and Stephanie Weirich
Modern computer games, such as the games Myst and Riven, strive to immerse the player in virtual, mythical worlds. Aiming for realism, the models which comprise these worlds are necessarily very detailed. However, because these models are so complicated, they must be rendered during game production instead of game play, as these games must run on a personal computer. Unfortunately, offline rendering forces these games to offer only fixed views for the player, who see the world in a discontinuous fashion. These discontinuities can be disorienting and go against the total immersion that the game designers seek.
A partial solution to this is to precompute an image from a certain camera location, but not fix the direction of view. The game engine would then take this precomputed image and produce, in real time, perspective images of the scene as if they were created via a standard rendering model. This would allow the user to look from a stationary position. After beginning this project we found an example of this form of user interface in the game "Journeyman project 3". As this game is still new to the market, unfortunately no discussion of its implementation has been made available.
However, the Omnicamera of Shree Nayar at Columbia University has given us an inspiration on how to solve this problem [Nay97]. This camera (see picture left) is capable of viewing all directions within a hemisphere, with the aid of a parabolic shaped mirror. A CCD camera faces the mirror a few inches away and produces a circular image of the reflection. This resulting circular image can then be converted into a normal view in any direction.
The basic solution is therefore twofold. First we model the Omnicamera in our initial rendering of a scene, to create an "intermediate" circular image. During game play, the engine will then use this image to compute perspective views of the scene. In order to have a full range of vision, we do this twice, creating circular images for both the top and bottom hemispheres.
For the first part, to create the hemispherical view, we use the freely available rendering package POV-ray. To create a virtual Omnicamera, we include in the scene a parabolic mirror, and position the camera directly below it. In the scene shown below, the camera is at the center of the image (the origin in model coordinates) looking straight up (the y-axis). The mirror is the suspended floating egg shaped object, described in the model by the equation:
Setting up the parabolic mirror
Circular image produced
Now, once the circular image has been rendered, the game engine must produce an image which imitates a perspective projection of the model from a given direction. The model of perspective projection, derived from the optics of a pinhole camera, is shown below. In this model, the image is formed by the intersections of rays from the view point to an object with a viewplane. The pixels at the intersection take their color from the object, and the plane forms the output of the renderer. Though not noted in the diagram, the viewplane must be perpendicular to the direction of view.
In order to simulate the optics of this model, to determine the value of pixel Q in the output image, we need to find the pixel Q' in the circular image which is the image of the ray from the viewpoint through the location of Q in the model. So, given the direction of view, in spherical coordinates (r, ρ1,θ1 ), the first task is to compute the coordinates in the model of each pixel in the output plane. The angular components of the coordinates of the Q, (call longitude ρ and latitude θ), specify the ray from the viewpoint through Q.
In the diagram on the left, the viewpoint is at the origin and C is the point at the center of the viewplane. The ray from the origin to C is the direction of view, at polar coordinates (r, ρ1, θ1). For simplicity, we will assume r = 1. We wish to compute the angular parts of the coordinates (ρ and θ) of the point Q also on the viewplane, at pixel position (x,y). Summarizing the geometry, we first let .
Then, and .
From these θ and ρ we can compute the corresponding pixel Q' in the circular image (in polar coordinates (r',θ')) that this ray is mapped to. The rotational angle, θ', is just ρ. However, r' depends on thelatitude, θ. As the parabolic mirror is rotationally symmetric, we can consider the two dimensional view; on the right is the model in terms of y and x. If this model is spun about the y axis, we get the original 3d model, so x represents the radial distance r'. The value we want is the x coordinate of the intersection of the ray () and the parabola (). We can solve these equations to get a formula for r in terms of θ:
Finally, we repeat this process for every pixel. Once we have values for each point, we can create the output images:
Since we are computing in a virtual world, we are not limited by physical laws. Though it is quite convenient in the case of a parabolic mirror that the angle of incidence equals the angle of reflection, we are not bound by this. In fact, we can use the intersection model which does not rely on reflection to hypothesize other shapes which would give us different functions f. Though mirrors in these shapes would not reflect the light rays to an infinite observer, (as is the case in the parabolic mirror), we are not building them.
For example, we can speed up computation of r if f was a linear function of θ. This is similar to images produced by some fisheye lenses. The equation of a shape to with this function f is:
While different functions f will not distort the output, they will affect the resolution at different latitudes. The fisheye lens treats all latitude angles equally, while the paraboloid devotes more pixels to the center of the image (the zenith). For comparison, we have also implemented the mode of the fisheye lens. In the images below, the text "CS 631" has been placed very close to the horizon. While the difference is not great, it is apparent that the letters are more distinct in the image produced by the parabolic mirror.
Below are the graphs for various functions for f (top half) and their derivatives with respect to θ (bottom half). The horizon is at θ equals 0 while π/2 is the zenith. The circular image has higher resolution at values of θ where the derivative is most negative. Notice for example that the parabolic mirror emphasizes the horizon, while the fisheye lens is constant at all latitudes.
Our program takes two circular images in PPM files corresponding to the upper and lower hemispheres of the surroundings and generates a rectangular viewing window, which can be rotated around. The user moves the mouse to see different parts of the surroundings. For each mouse movement, the algorithm described above is used to calculate a new rectangular images with the matching offset. The images are stored in memory as 24-bit Device Independent Bitmaps (DIBs), which can be copied into Microsoft DirectDraw® surfaces. A DirectDraw surface stores the image directly in video memory so it can be displayed quickly.
The program takes about 1 to 3 seconds to generate 640 by 480 pixel images on a Pentium 200 Mhz, running Windows 95. It takes a while because for every mouse movement, each pixel must be calculated again (unlike shifting a cylindrical image where the rows or columns can be moved without recalculation). However this does not depend on the complexity of the image. Even a photograph should not take any longer. Additionally the performance can probably be improved by optimizing the implementation.
As early as 1978, Jeffery R. Charles of Versacorp started developing cameras for taking 360 degree panoramas. His first prototypes captured images in circles similar to the ones created by the Omnicamera, though they involved two mirrors instead of one to make the apparatus holding the mirrors invisible. He first employed the pointed half of a Chrome L'eggs "Sheer Energy" hose egg for the parabolic mirror. He also developed a darkroom technique for converting the circular image to a rectangular one.
Others interest in panoramic cameras has been in the mobile robot community. Because their interest was in collision avoidance rather than image creation, their first experiments did not seek to satisfy the single viewpoint constraint. Early models include a rotating camera, a conic shaped mirror, and a spherical mirror. Recently, two groups ([YYY93] and [SPH97]) have started to experiment with a hyperboloidal shaped mirror.
Currently there are several products on the market which turn a series of photographs into a panoramic image, which may be rotated and zoomed with the vendor's engine. The most prevalent of these is Apple's Quicktime VR, but other competitors include Interactive Pictures, Live Picture, Black Diamond, or eVox. Most of these companies use a cylindrical projection for their images. Basically, a rectangular image is formed by rotating a camera around a vertical axis. Translating this to a "normal" viewpoint is very fast, but the user has only limited ability to look up or down. An example of this type can be found http://www.evox.com/partners_surround_pano.html. Of all of these companies, only Interactive Pictures (IPIX) provides a full spherical view as we do. Their process relies on two back-to-back images taken with an 8mm fisheye lens. They have a patent on this technology, forcing competitors to only support narrow lenses in panorama construction.
On the rendering side, Wyvill and McNaughton [WM90] describe optical models to express the way in which the output image relates to the three dimensional model. They lay out the model of the fisheye lens which was used in the POV-ray implementation. They also note that any function of θ may be used for the radial distance, although their interest is in creating unusual images, and do not consider other applications of it.
For the game engine in this project, we created two models, the parabolic mirror and the fisheye lens. For production, I would use the fisheye lens as it is faster, and more uniform with respect to the scene. Furthermore, in this set up, the parabolic mirror is an actual object in the rendered scene and so casts a shadow and appears in reflective surfaces. The fisheye lens is involved only in the creation of initial rays, and so does not cause any additional effects. Future work might be to consider other models as suggested in the generalization section.
Also, in this version of the game engine, we used perspective projection to create the output image from the circular image. However, while perspective projection is the standard projection model, Fleck points out that it is not well suited for wide-angle views (greater than 90 degrees) [Fle94]. As humans can see close to 180 degrees horizontally, in order for a game to more closely mimic human experience, a different model of projection might be desired.
[Anz96] Rainer Anzbock. Quicktime VR technical overview. http://www.cg.tuwien.ac.at/studentworck/Bratislava96/qtvr/qtroot.html
[Fle94] Margaret Fleck. Perspective projection: the wrong imaging model. University of Iowa, Tech Report no. 95-01.
[Nay97] Shree Nayer. Catadioptric omnidirectional camera. In International Conference on Computer Vision and Pattern Recognition 1997, pages 482-488. IEEE Computer Society Press, June 1997.
[WN90] Geoff Wyvill and Craig McNaughton, Optical Models. CG International '90, Springer, 1990, p. 83-93.
[SPH97] Tomas Svoboda, Tomas Pajdla, Vaclav Hlavac. Central Panoramic Cameras: Geometry and Design. Czech Technical University, Tech report no. K335/97/147.
[YYY93] Kazumasa Yamazawa, Yasushi Yagi, and Masahiko Yachida. Omnidirectional Imaging with Hyperboloidal Projection. In Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1029-1034. IEEE Computer Society Press, July 1993.