Homework 7
22C:151 Introduction to Computer Graphics
Due Thursday, Nov. 13, 2008
1. (8 points) Show details of tracing the execution of the midpoint circle algorithm (given
in class on 11/4) on a circle of radius 12. Include a picture showing
which pixels are illuminated (for at least for the first quadrant, i.e. upper right
quarter, of the circle.) By details, I mean, you should show at each step the
values of d, incr_E, incr_SE, etc.
2. (17 points) Implement BSP-tree (binary space partition tree) construction and drawing
algorithms and use them to render scenes of convex texture-mapped polygons.
Your program should take a file name as input. The file will contain a description of a
set of convex polygons to render (see below for format details).
Your program should allow interactive viewing of the set of colored polygons.
Only the proper visible portions of the polygons should be drawn
and this should be accomplished via BSP-tree traversal rather
than use of OpenGL's depth buffering capabilities.
Interactive viewing may be accomplished using view manipluation
code you write (e.g. you could reuse your HW3 viewing code) or
code provided for you README (documentation for hw7viewing.c),
hw7viewing.c. Three test files are also available:
test.txt, test2.txt,
test3.txt.
Thus, the basic steps are:
- read the polygon scene file
- construct a BSP tree for the scene. You do not have to
use any techniques that attempt to construct a "good" BSP tree.
Any correct BSP tree will be fine.
- As the user changes viewpoint, the polygons should be
properly rendered.
Based on the current viewpoint and the
BSP tree, traverse the BSP tree, generating OpenGL polygon
drawing commands as you go.
Input file format:
The first line of the input file will contain an integer indicating
the number of polygons described in the file. The rest of the file
will describe the individual polygons.
A polygon with n vertices will be described in n+1 lines in the file.
The first line of a polygon description will contain 1 integer, indicating
the number of vertices in the polygin,
and the name of the texture file to use for texture mapping this
polygon. The remaining n lines will each contain three
floating point numbers giving the world x, y, and z coordinates
of each vertex of the polygon.
The vertices will be listed in counterclockwise order.
For example, the following describes 2 polygons:
2
4
1.0 1.0 1.0
2.0 1.0 1.0
2.0 1.0 0.0
1.0 1.0 0.0
3
-1.0 0.0 0.0
-1.0 0.0 2.0
-0.5 3.0 1.0