CS559 Fall 2004: Project 2

Maze Visibility and Rendering

Due Date: 5pm Monday, November 22

Your task in this project is to implement a maze rendering program, not too far removed from those used in computer games of the first-person variety. Read this entire document carefully before beginning, as it provides details of the required implementation and various tips.

This project requires that you understand and achieve several of the tasks discussed in lecture: viewing transformations, clipping, projection, and visibility. It is also your first, very limited, introduction to OpenGL.

Mazes

A maze consists of rectangular cells separated by edges. The edges may be either transparent or opaque. The viewer is supposed to see through transparent edges into the neighboring cells, and they should not see through opaque edges. Each edge is assigned a color (which is meaningless for transparent edges).

The maze is described as a 2D structure assumed to lie in the XY plane. You are responsible for making the maze 3D. Do this by extruding each edge vertically from the floor to the ceiling to make a wall. The floor is at z=0 and the ceiling is at z=2. Each wall should be drawn with its assigned color.

Associated with the maze is a viewer. The viewer has an (x,y,z) location, a viewing direction, and a horizontal field of view. The view direction is measured in degrees of rotation counter-clockwise about the positive z axis. The horizontal field of view is also measured in degrees.

For the project, the viewer is always looking horizontally, never upward or downward (or, always parallel to the floor or ceiling). This means that, after perspective projection, the left and right edges of walls are always vertical. In turn, this allows you to do all the visibility working with lines in 2D, before you extrude the walls.

The maze file format consists of the following information (also look at one of the example mazes):

• The number of vertices in the maze, n_v. Each edge joins two vertices.
• The location of each vertex, specified as it x and y coordinates. The vertices are assumed to be numbered from 0 to n_v - 1.
• The number of edges in the maze, n_e. Remember, there is an edge between every cell, even if that edge is transparent.
• The data for each edge: the index of its start vertex, the index of its end vertex, the index of the cell to the left, the index of the cell to the right, a 1 if the edge is opaque, or 0 if transparent, and an RGB triple for the color. The left side of an edge is the side that would appear to be on your left if you stood at the start of the edge and looked toward to end. If there is no cell to the left or right, an index of -1 is used. The edges are assumed to be numbered from 0 to n_e - 1.
• The number of cells in the maze, n_c.
• The data for each cell, which consists of the four indices for the edges of the cell. The indices are given in counter-clockwise order around the cell.
• The view data, consisting of the (x, y, z) viewer location, viewing direction and the horizontal field of view.

Software Provided

Source code can be found in the src directory.

Several classes have been provided. Together they build two programs. The first program creates mazes in a certain format. The second is a skeleton maze renderer. The code is reasonably well documented, but part of the project is figuring out how the given code works and how to integrate your code into it. The programs are described below.

There is only one Visual Studio project file, but it contains information for multiple Build Configurations. Each build configuration corresponds to a different program. To build the program you want, set it as the current build configuration on the taskbar at the top of the window. There are both Debug and Release versions of the RunMaze program. Only use the Debug version. For reasons we cannot explain, the Release version causes bugs.

BuildMaze

The BuildMaze program provides a simple user interface for building mazes. The user specifies the following parameters:

The Build Maze button builds a maze with the given parameters and displays it. The Save Maze button requests a file name then saves the maze to that file. The Load Maze button requests a maze file to load and display. Quit should be obvious.

RunMaze

The RunMaze program provides a skeleton for the maze walkthrough that you will implement. As provided, it displays both a map of the maze and an OpenGL window in which to render the maze from the viewer's point of view. On the map is a red frustum indicating the current viewer location, viewing direction and field of view. The map is intended to help you debug your program by indicating what the viewer should be able to see.

To move the viewer, hold down a mouse button and drag in the OpenGL window. Mouse motion up or down is translated as forward or reverse motion of the viewer. Left and right mouse motion changes the direction of view. As the skeleton exists now, the viewer will move in the map window to reflect the mouse motion.

The system performs collision detection between the wall and the viewer to prevent the viewer from passing through opaque walls. You should examine the code that does that to see an implementation of clipping that clips a line segment to an edge using an approach similar to Liang-Barsky clipping. The RunMaze program also keeps track of which cell the viewer is currently in, which is essential information for the cell-portal visibility algorithm you must implement.

You should pay particular attention to the function draw in MazeWindow.cpp that sets up the OpenGL context for the window. As you will read later, all of the drawing you do in this project must be in 2D, so the window is set up as an orthogonal projection using the special OpenGL utility function gluOrtho2D. The draw function also draws the projection of the ceiling and the floor of the maze. You should be able to reason as to why is it safe to treat the floor and ceiling as infinite planes (hint: the maze is closed), and why those planes project to two rectangles covering the bottom and top half of the window. You do not need to change this function.

C++ Classes

This document will not go into details of the C++ classes provided. You should spend a considerable amount of time perusing them to figure out how everything works, and too look for little functions that will be useful in your implementation, such as functions to convert degrees to radians and back again (recall that all the C++ trigonometry functions take radians).

Your Task

Produce the viewer's view of the maze. You must extend the function Maze::Draw_View to draw what the viewer would see given the maze and the current viewing parameters. Note that the function is passed the focal distance for Basic Perspective Projection, and you also have access to the horizontal field of view. Your implementation must have the following properties.

• You must use the Cell and Portal visibility algorithm to achieve exact visibility. In other words, apart from drawing over the floor and ceiling, no pixel should be drawn more than once (almost no pixel - do not worry about pixels on the edges of polygons). The algorithm is given in psuedocode below.

  Draw_Cell(cell C frustum F)
     for each cell edge E
        if E is opaque
           E' = clip E to F
           draw E'
        if E is transparent
           E' = clip E to F
           F' = F restricted to E'
           Draw_Cell(neighbor(C,E),F')
  

  The function Draw_Cell(C, F) is initially called with the cell containing the viewer, and the full view frustum. The neighbor(C,E) function returns the cell's neighbor across the edge. Note that drawing a 2D edge means drawing a wall in 3D.
• You are only allowed to use OpenGL 2D drawing commands. In other words, any vertices you specify should use glVertex2f, glVertex2fv, glVertex2d or glVertex2dv only. You should use glBegin(GL_QUADS) to draw polygons, and glColor3f or glColor3fv to specify the polygon color. We will check for other OpenGL calls when we grade.
• As an side effect of the 2D restriction, you must do your own viewing transformation. That is, you must take points specified in world space (where you will do the visibility) and transform them all the way into screen space (where you will draw them.) The transformation will consist of a translation and rotation to take the points from world to view space (with the origin at the viewer's location) and then a perspective division to take the view space points into screen space. Note that you are given the focal distance to make things easier, but you must still take care of several small details. Note that you can do all the transformations using basic transformation matrices followed by simple perspective. That is, you are in the Basic Perspective Projection case from the lecture notes. You DO NOT need to construct general purpose viewing transformation matrices.

Helpful Tips

• The visibility algorithm is a 2D algorithm in this case, because all the walls are vertical and the viewer is looking horizontally. That also means that all the pieces of wall that you draw will have vertical left and right edges. They will not have horizontal top and bottom edges due to perspective effects.
• Your code will begin in the Maze::Draw_View(...) but you can then call any function you like, create any new classes you like, and any new files you like. In fact, you should create some new classes and files.
• Implement a Frustum class that stores information about a viewing frustum, and has a method for computing the frustum that passes through a portal (equivalent to clipping the portal edge to the current view frustum and using the clipped endpoints to define the new frustum). The easiest way to represent a frustum is as a point for the viewer's location, and two edges for the left and right "clipping lines" of the frustum. There is no near and far clip lines in this project.
• Implement a function in the Edge class or the LineSeg class that clips an edge to a given view frustum. You will have to work out a way to compute the intersection point of a line segment with an infinite line in 2D space. Start by writing out the equations of the lines in parametric coordinates. There is a function in the LineSeg class that may help get you started, but it does not do everything you want.
• It is easiest to begin with a 1 by 1 maze, in which case there is no recursive step. That gives you the opportunity to debug the transformations and projection before getting into the details of manipulating view frustums. Even more, you can start by just drawing edge 0 of the 1 cell maze. Then you should be seeing only one wall and there will be no chance of confusing the effects of different walls.
• To do the projection, first translate the point so that the viewer is at the origin (subtract the viewer's location from the point.) Then undo the viewer's rotation direction by rotating the point. Then do the perspective divide (using the simple perspective projection from the notes, suitably modified.)
• Note that in OpenGL 2D drawing, x is to the right and y is up. When you do the transformation above, you end up with y to the left, z up and x into the screen. You have to deal with this.
• You are not required to clip to the top and bottom of the window. Let OpenGL take care of it.
• In the past, a common error has been specifying the vertices of a quad in the wrong order. OpenGL requires the vertices in a consistent (preferably counter-clockwise) order.
• To use OpenGL in a file, include "FL/gl.h" from the FLTK library, NOT "GL/gl.h" which will cause errors.
• We have seen some Visual Studio problems with this project in the past. One is the loss of settings such as the build configurations. In this case you have to reconstruct them yourself - we can help. Another problem is an error message about writing temporary files. This appears to be caused by a lack of disk space, or compiling in your personal (u:) account. Try copying to the desktop and then compiling, but be sure to copy back later.

It cannot be stressed enough: This project can be completed in somewhere between one hundred and three hundred lines of code. Spend a lot of time thinking about what you are trying to do with each piece of code. And spend a lot of time looking at the code you are given. Start with pen and paper, because there are a lot of small pieces of math that you need to work out.

Grading and Submission

The project will be graded out of 50. You get:

• 20 points for projecting a wall onto the screen with perspective projection and drawing it.
• 10 more points for correctly clipping walls to the view, for a single cell maze.
• 20 more points for doing the recursive visibility.

Submission will work similar to project 1. Hand in all your .cpp files, all your .h files, and your .sln and .vcproj files. Grading of this project may be by demo in a series of face-to-face grading sessions, or we may have to forgo the demos due to resource constraints. We will send out information about this as the project due date nears.

You must work alone for this project.