CS40: Computer Graphics, Lab 5

A Hierarchical Modeling System

By Jeff Kaufman

In this lab I extended the graphics library I started in lab 2 by adding a framework for modeling complex scenes with objects within objects. I also wrote aditional ability for the reading of modules from plain text description files.

Hierarchical Modeling

The modeling system here is divided up into modules. A module holds onto a list of elements, which can be primitives (points, lines, polygons, and polylines), transformation matricies, colors, or pointers to other modules. When it comes time to draw the module, we go down the list and each primitive is first transformed by the matricies before it in the list and then drawn.

This means that if we have a module in which we added, in order:

  1. A vertical line l
  2. A translation by 3 in X
  3. Another vertical line l'
  4. A rotation of 45 degrees around the Z axis
  5. A third vertical line l''
Then when we draw it we will get three lines on the screen, one for each of l, l', l''. The first will be unaffected by any transformations and show up purely vertical. The next line will be just like the previous, but three pixels to the right. The third line will be affected by both the translation and the rotation, and so will cross the scene at an angle.

This is implemented by holding onto three matricies:

  1. A local matrix, which is the product of all the transformations that have been requested since the module was created or it was last reset with the Matrix_identity command.
  2. A global matirx, which is the product of all the transformations that happend on higher layers of the hierarchy, before we got into this module. Calls to Matrix_identity do not affect this matrix. When a submodule is drawn, the global matrix used is the product of the parent's global and local matricies.
  3. A view matrix, responsible for moving the image to the center of the screen, scaling it properly, perhaps doing some projection. This is passed along from module to submodule unaltered and used to modify points right before they are drawn.

API Info

Most of the functions I implemented were exactly as laid out in the Graphics Specification. The only additonal external functionality I implemented was the function
Module* Module_fromFile(char* fname)
which reads a module from a file, loading submodules from other files as appropriate.

Module file format

This file format was designed primarily for ease of parsing. The commands allowed in the format generally have direct analogs with Module_addX or Module_transformation2D functions. There is not much spiffy recursion or even named colors, not because I don't think these are good and useful but because they would have taken a long time to implement and that wasn't the real focus of the project.

One exception to this general simplicity rule was the additon of the command "circle2D [x] [y] : [radius] : [resolution]". There were enough times when I wanted circles that this made a lot of sense to implement.

Comments are indicated with semicolons, and everything from the semicolon on is ignored. Each line may contain one command and each command is one line, with the exception of the Polyline and Polygon insertion commands which use a line for each point in addition to an introductory line.

The sample file below should illustrate the format: 

     ; An example module, defined in the file example.mod
     ; this is a comment
     ; (blank lines are allowed)
     
     point 5 -2 2.2         ; we can add points
     line  1 2 4 : -3 2 5   ; lines as well

     polygon 7              ; the number (7) is the number of verticies in the polygon
       1 1 1
       1 1 3
       1 3 3
       3 3 3
       3 3 1
       3 1 1
       3 1 3
     
    polyline 4              ; polylines are just like polygons
       2 2 1
       1 2 2
       -2.3 4 5
       7 1 2

    translate2D 3 2         ; shift following things by 3 in X and 2 in Y
    scale2D     2 4         ; make following things twice as tall and four times as wide
    rotateZ     0.866025 .5 ; rotate following things by 30 degrees (the numbers are the cos and sin)
    shear2D     3 4         ; shear by 3 in X and 4 in Y

    color 255 0 128         ; make the following things reddish purple

    line  1 2 4 : -3 2 5    ; insert a line so we can see what the previous things did
   
    loadmod h helper.mod    ; load the module from helper.mod and call it "h".  Don't insert it, though
  
    module h                ; now insert the module we just loaded
    translate 1 0           ; move over
    module h                ; insert another copy.

    identity                ; reset the matricies to get a clean slate
    line 0 1 0 : 2 3 3      ; put in a line, unaffected by the matricies above.
    circle2D 3 4 : 4 : 50   ; make a circle-like polygon at <3,4> with 50 segments and a radius of 4
This format is pretty useful, and is nearly as powerful as hardcoding things. The main drawback is that we can't have variables anymore. This is more than offset, though, by no longer having to recompile for changes or deal with the ugly mixing of code and scene data that the other approach gives. We also now have modules that can be easily reused, being defined in their own files. Support for variables with a preprocessor would also not be difficult.

To show the power of this system I've converted the test scene into this format and generated the image below:

If you compare this to the test image with the lead fighter at 30 degrees, no movement accross the screen, and shots 5 away from the shooting fighter, you can see they're the same:

I also tested this system by creating a model of a teddy bear:

The nice layered structure of the bear model is below.

Additions

This format will get updated in lab 6 to support 3D transformations.

Artifacts

There are artifacts in the above images. This is sad. They mostly come from border cases in my polygon fill algorithm from lab 3.


Jeff Kaufman : 2006
cbr at sccs dot swarthmore dot spam edu. Remove spam.

main page