Contents:
We're working from FVD (Foley & van Dam's text) chapter 1. Some key words:
Scope of the Course
Basic History of CG Concepts
At the outset, hardware was very expensive; even a memory word per pixel was out of the question. So we developed techniques that were based on rather abstract images (line drawings) when possible. These were originally inspired by output-to-paper plotter systems, and are referred to as vector systems.
Typical commands might look like
Lineto(200,300)
-which would mean "move the plotter pen from wherever it is, to location 200,300 on the plotter."
vector (calligraphic) displays are rather easy to understand; in fact let's describe one now. A stored list of data might contain codes like the following display list. We use a standard Cartesian coordinate system (Y up, X to the right.)
| Location | Command | X coordinate | Y coordinate |
| 1 | Moveto | 100 | 100 |
| 2 | Pencolor | 3 | empty |
| 3 | Drawto | 200 | 100 |
| 4 | Drawto | 200 | 200 |
| 5 | Drawto | 100 | 200 |
| 6 | Drawto | 100 | 100 |
| 7 | Goto | 2 | empty |
As you can see, this set of commands would draw a square on the screen. In fact the screen doesn't have to remember the square because the code in location 7 would force it to redraw over and over. Such vector-refresh displays were common in early CG systems in the 1960's. Later, special CRT displays were developed that could store the line images directly in the tubes' phosphor, making the refresh cycle unnecessary.
Even though vector displays are now archaic, the basic concept of the display list lies behind everything we will do in this course.
Raster displays began to appear once the cost of memory came down to the point where individual pixels could be assigned at least one bit of memory. A television set's scanning pattern is called a raster. When you are using a digital computers to make rasters, you quickly find yourself assigning a piece of memory to discrete locations on the screen called pixels (picture elements.)
Calligraphic displays were in principle capable of drawing smooth lines; they didn't generally need or use pixels. However the endpoints of the lines had to occupy discrete points on a grid, because they were specified in digital numbers.
The appearance of the pixel made many things possible - solid objects, nice shaded and illuminated images, textured surfaces. But they also caused many new problems - the "jaggies", called aliasing. In fact, aliasing denotes any distortion of an image caused by the way the image is rendered. We'll spend some time talking about how to minimize aliasing.
Input devices are essential for interactive graphics. Light pens and graphics tablets ae old news. Mice are by now, also pretty old news. Three dimensional tracking equipment, as used in Virtual Reality systems, are rapidly developing.
Interaction Techniques have moved through "menu" concept, to the infamous "desktop metaphor" developed at Xerox, popularized by Macintosh and made universal by Microsoft Windows. (Blind people still prefer DOS.) However, the desktop metaphor is now stale, causing as many problems as it solves. I believe that somewhere out there in this classroom, there is a person who could come up with the next paradigm shift in use interaction techniques. Go for it!
Graphics Standards have been attempted many times. X Windows from MIT is the first successful 2d standard, and it is far from universally available. GL ("Graphics Library") from Silicon Graphics is the first 3d geometric standard that has been developed during a time of adequate hardware; prior attempts including Siggraph CORE, GKS and PHIGS all imposed too much performance penalty for their elegance to be appreciated or used.
Today the standards to pay attention to are rapidly changing and becoming more abstract and powerful. In this course we'll discuss OpenGL, a public domain version of GL; VRML = "Virtual Reality Modeling Language", an Internet derivative of one of GL's children; and a few other systems that are not yet standardized.
My diagram differs slightly from that in the text (page 17).
As can be seen, there are seven elements. Each of them will be subject of substantial study in this course.
So, let's get on with it. We're moving to Chapter 2 of FVD, to look at the "Simple Raster Graphics Package" (SRGP) as a means of introducing more specific commands and ideas.
We won't actually be using the (obsolete) "Simple Raster Graphics Package" from the FVD text, but it's useful to introduce some more concepts.
Screen Coordinates can be thought of a "hardware coordinates". A two-dimensional integer cartesian grid of pixels with (0,0) in the lower left corner, or occasionally in the upper left corner. The aspect ratio of width to height of most computer screens is 4:3, as in 640:480.
Primitives are the visible items that the software can directly draw. For SRGP these are pixels, lines, polygons, circles, ellipses and text.
SRGP Procedures look like this: (Pascal syntax)
procedure SRGP_lineCoord(x1,y1,x2,y2:integer);
To draw a line from (0,10) to (100,200) we would call
SRGP_lineCoord(0,10,100,200)
Data Abstraction means making more complex objects, so
that there are fewer of them to worry about. For instance, SRGP
defines a two dimensional point as a structured record:
type
point = record
x,y:integer
end;
A procedure is also provided which produces points from integers.
(However it is not a "constructor" in the object-oriented
sense because it doesn't allocate memory for the new variable.)
procedure SRGP_defPoint(x,y:integer; var pt:point);
Now we can use points instead of separate (x,y) coordinates, in
another procedure.
SRGP_line(pt1, pt2:point);
But we don't stop there.. we can also aggregate points into an
array of points called a polyline. (That's like a polygon
except it doesn't have to close: go back where it started.
It turns out that SRGP refers to vertexList rather than
to Polyline, for some reason.
procedure SRGP_polyLine(vertexCount:integer; vertices:vertexList)
This pattern of having a procedure defined on coordinates, and another defined on a more complex object, continues with the definitions of
SRGP_rectangleCoord, SRGP_rectangle, SRGP_marker, SRGP_polygon,
SRGP_ellipseArc, etc.
Attributes are properties of primitives, such as line style
(continuous, dashed, dotted), line width (an integer), and color.
Filled Primitives. You can construct ellipses (including circles) or polygons that are filled, or outlined. The filled ones do not have outlined borders; so you'd have to call both procedures if you wanted an outlined figure. The fill pattern and fill style are specifiable.
Fill Styles includes opaque, which completely overlays what was below it; transparent, in which some color is designated to let the previous color show through; and texture-map, in which a stored array of color values is used to "tile" the region being filled.
Text has many attributes including font, appearance (bold, italic, underlined), size (72 points per inch. Why 72? Divisible by 2,3,4,6,12. The Mac screen is usually 72 dots/inch, with square pixels, because it was designed for typography.
Interaction Handling
We will talk more about user interface guidelines, in later
lessons. Here are a few essentials.
All these are standard parts of the WYSIWIG programming interface but are WAY TOO OFTEN omitted from student programs, because they're hard to provide. If you are using Windows' own built-in tools, many of these come for free.
Sampling versus Event Driven Processing. If your computer were under the complete control of your program, and the program's flow of control was always explicit (you can see "who calls whom" in every case) then the only way to get input from an i/o device would be to repeatedly read the device (call a testing-procedure.) If it weren't ready, you could do something else and come back; or just wait for data.
This simple style of programming has been largely replaced by Event-Driven programming. In this model, your code is not in total control of the computer. Rather, your code consists of a collection of procedures which you provide to an event manager (such as is provided by Windows, or Unix.)
Your program constructs one or more windows, then goes to a wait-state. When a mouse-click occurs in some window (or some other event like a keystroke occurs), the event manager puts these events into a queue, tagged with the name of the window that was in control. It then pulls events off the queue and sends them to "event handler" procedures that you provided.
Using hardware interrupts, the CPU can do other things when your program is in a wait-state. Among the things it does are update the system clock 60 times a second, run other tasks like a Netscape download; or schedule file-maintenance if it's Win95.
Pick Correlation. Within your own program, it is often necessary to be able to figure out which of several objects are being pointed to by a mouse. One way to do that would be to scan through all the objects (polygons, polylines, etc.) and find the one whose area includes the mouse location.
This is easy for rectangles and circles, and quite non-trivial
for other shapes.
(that A means ASSIGNMENT:)
REQUIRED: (1) Assume that a rectangle r=(ul, lr) is
defined by two points showing its upper left and lower right corner.
A point p=(px,py) is defined by two integers. A circle c=(p,r)
is defined by a point and an integer radius. Write pseudocode
procedures
IN_RECT(r:rectangle, p:point)
and
IN_CIRCLE(r:integer; c, p:point)
which return TRUE if the point p is inside rectangle, or
inside the circle centered at c with radius r. Points on the border
are considered inside.
(2) Write pseudocode for a routine
CLOSEST_POINT(L:vertexList; p:point)
which returns the point in the vertexList that is closest
to p.
OPTIONAL: Write
pseudocode procedure IN_POLYGON(L:vertexList, p:point) which returns
TRUE if the point is inside the polygon defined by the vertex
list. You may make the simplifying assumption that the polygon
is convex if you cannot
figure out how to make a general inclusion-test routine.
(Convex polygons are those for which no two successive edges
form an angle pointing INTO the closed region. Others are called
concave. A way to remember
this is that concave polygons have a "cave" (a cavity)
on their outer surface.)
NOTE: You are allowed to work together on these problems.
However, you must understand your solution well enough to present
it to the class if you are called on. If you don't understand
it, I expect to see you in office hours!
HINT for polygon inclusion: you need to know how to form
the equation of a line in a plane. Vector operations such as cross
product and dot product are also helpful.
A Canvas is a screen image, that can be saved. Sometimes we want to "paint" our primitives into pixels and then save the pixels rather than (or in addition to) the primitives.
Many programs call a pixel-image a paint image, and the stored primitives a draw image. You can always construct a paint image from a draw image, but the reverse operation is not always possible.
Clipping means getting rid of drawing effects outside of a given region. Clipping is essential for window management. The "brute force" way to do it is simply to render the whole primitive and then, at the pixel level, scissors the output. That is, test every pixel and if it's outside the window, don't draw it. This wastes much CPU power, however.
Smarter clipping algorithms exist and will be described when we
return to Chapter 3, later in the course. In a typical high powered
graphics system, almost as much hardware power is devoted to clipping
as is devoted to rendering the primitives!
In his keynote speech at Siggraph '95, Doug Adams (of Hitchhiker's Guide to the Galaxy) told a story about the successive discovery that "the computer is a calculator!, no, a typewriter! no, a television! and ultimately, when the Web was created, "a BROCHURE!" But in fact, what the computer is, is a simulator. It can simulate all those things and more we haven't thought of yet.
Simulation is not easy to do if you think of programs as single-threaded entities where all control moves along a pathway of calls to procedures, one at a time. This fact led to the invention of languages such as SIMULA back in the 1960's, and to SmallTalk and the full-fledged Object Oriented movement in the 1970's.
Quick Review of Object Oriented Software. Object Orientation is really a re-thinking of the relationship between code and data. Previously we thought of code as the "real structure" of a program, with data tacked on as needed. For instance, what are the big chunks of most C programs? Procedures.
With OO, we reverse that thinking. The main elements are OBJECTS, which are bundles containing both data describing that object, and behaviors that can transform the data. I like to tell the story of self-heating field rations for the army, as a real-world Object Oriented Object. You just twist the bottom of the can, and the "heat method" applies itself to the "food data" to transform it into "lunch data."
Objects are most economically described as instances of a class. Thus you can have thousands of objects that are structurally identical but which vary in the values of their data elements. Classes, in turn, can be derived from other classes via inheritance.
Now, about Simulation? Well, if we wanted to simulate a car, we would like for it to have a control panel including brake and gas pedals, steering wheel, gearshift, and instrument panels. All these objects would also interact with an object called the drivetrain, which would interact with the road.
When the user wanted to push any control, the simulation should immediately notice. But the programmer doesn't want to have to write code that scans all the possible control-clicks. That should be manageable by the software support system (e. g. SIMULA, or Smalltalk, or Windows.)
So, that means that there has to be some way for the simulation control system to map (mouse-click at 300,300) to produce a specific message to a specific object (e. g. the steering wheel object.) and to tell that object which of several actions (turn left, turn right, honk horn) the user selected.
It is usually convenient to pass the message first to a higher level object called CAR_CONTROLS, and also provide the information that the user clicked on the STEERING_WHEEL object. This way, if there are any actions that the overall control set should be taking before it notifies the steering wheel, it can do so. For instance, maybe there is a control on the steering wheel that moves it up (for fat folks to get underneath.) Then this is really a message to the CAR_CONTROLS class, from "inside" the steering wheel, to relocate the wheel itself (and redraw the other underlying objects.)
Thus, simulation toolkits need in general to provide an "anybody calls anybody" capability, a kind of telephone system (or maybe more like a post office system) so that objects can send messages to one another. This is done via hardware interrupt handlers. When a mouse movement or click occurs, Windows immediately starts classifying the incoming data and deciding if any resources (buttons, menus, etc.) have been triggered. If so, it looks in the resource object to see what message should be sent to what software object, to respond to the user's actions.
Well, obviously, an important kind of an object will be a window. Windows have two kinds of messages associated with them: messages they send out to their associated callback functions (called EVENTS), and messages that can be sent to the windows to tell them to do things.
Other objects are constructed from parts belonging to various classes. The DIALOG object class includes several subclasses. Once you choose one (like a dialog box or a menu item) you can then begin to fill it up with other objects. You can, for instance, make a dialog box which when clicked opens a whole other window that might include its own pulldown menus.)
This Part-whole hierarchy is very powerful, and it is distinct from the class hierarchy. An essential distinction is between is-a (class) hierarchies and has-a(part-whole) hierarchies. You create the part-whole hierarchy by using the ClassWizard tool-set to add pieces to the various windows that you build. You create the class hierarchy (actually you extend the existing class hierarchy) when you write the code that is attached to the widgets.
C++ uses non-standard terminology for object oriented concepts, as you will see.
Classes are groups of objects with identical structure and behavior. The data in one of the objects in a class is called (in C++) the object's data members. Since all objects in a class are identical, we declare the data members of the class, then create objects as instances of the class.
Anything that can be done to that object, has to be done "by itself" - not by other objects. The built-in procedures of the object are called its methods, or (in C++) its member functions.
Here's the declaration of a simple class. It will be followed by the definition of the class. We follow a convention of always starting class names with a C, and data-member names with m_.
// This is the program called Circle.CPP
#include <iostream.h>
/////////////////////
// Declare the Ccircle class
/////////////////////
class CCircle
// This class doesn't actually draw circles; it just computs
// trivial facts about circles, for purposes of illustration.
// Borrowed from Gurewich & Gurewich: Master Visual
C++2, which is
// a good book you should consider buying.
{
public:
Ccircle(int r); // prototypes of member functions. This
is the CONSTRUCTOR
void SetRadius(int r); // these are ACCESSOR Functions
int GetRadius(void);
void DisplayArea(void);
~CCircle(); // and this is the DESTRUCTOR function. Note:
TILDE~, not MINUS
private:
float CalculateArea(void);
int m_Radius; // data members
int m_Color;
};
/////////////////////
//Now DEFINE the Ccircle class
/////////////////////
// CONSTRUCTOR
CCircle::CCircle (int r)
{
// Just set the radius. The dynamic creation of a ccircle
// is automatically provided, because the name matches the
// class name and it was properly declared as the constructor
function.
m_Radius=r;
}
//DESTRUCTOR
Ccircle::~CCircle ()
{ // You don't have to do anything when destroying one of
these objects.
// In other cases you might have some clean-up to do, if
other
// objects depended on this one.
}
//DISPLAY FUNCTION
void CCircle::DisplayArea (void)
{
float fArea;
fArea = CalculateArea (); // Calls one of Ccircle's member
functions.
cout << "The area of the circle is: " <<
fArea;
}
//PRIVATE Calculation Function
float Ccircle:: CalculateArea (void)
{
float f;
f = (float) (3.14 * m_Radius * m_Radius);
return f; // This illustrates how the member data is shared
by all
// member functions of the class.
}
//////////////// AND at last, the Main Program
void main (void)
// Create an object of class Ccircle, with radius equal
to 10 units.
CCircle MyCircle (10);
// Display the area of the first circle.
MyCircle.DisplayArea(); cout << "\n"; //
get a new line.
// Now create another circle and display its area.
CCircle YourCircle (20);
YourCircle.DisplayArea(); cout << "\n";
} // The destructor function is automatically executed when
the program terminates.
With that brief reminder of C++ syntax, we must now move on into the Visual C++ working environment.
5. The Visual C++ Work Environment
A "project" is a subdirectory or folder containing all the stuff associated with a program. Closely associated with each project is a "mak file" (pronounced "make file"). This guides the compilation and linking of the code modules. You need to use your C++ reference materials to learn how to construct and execute the programs; we're discussing the data structures here.
The main reason that project management is needed, is that a whole bunch of built-in classes from MFC (Microsoft Foundation Classes) are about to land on our heads! We need to be able to look at their declarations, make sure we have access to them - but we don't want to have to write 100 pages of code. So VC++ handles it for us.
The AppWizard gives you a series of menus, to decide if you want various features such as an About dialog box (tells who wrote the program, copyright info, etc.); whether to use 3 dimensional-looking controls, etc. It then provides those classes automatically by stuffing the right files into your project folder, into the MAK file for your project, and into the skeleton-code for your actual program. Into that prototype program, the AppWizard will put the needed #includes, to get the header files it set up for you in the project folder.
For a trivial "Say" program, in which one dialog box is provided with two buttons, the project directory looks like this. Actually MVCC displays the contents of Say.mac, in this form, AS THOUGH the directories were so organized. Usually it's a simplification. Italics, obviously, stand for subdirectories.
Win32 Debug
Source Files
readme.txt
say.cpp
say.rc
saydlg.cpp
stdafx.cpp
dependencies
Resource file. Say.rc
lists several kinds of resources: Dialog, Icon, String Table and
Version. MVCC again displays these as a file hierarchy:
Say.rc
Dialog
Icon
String Table
Version
These "resources" contain references to the classes
you need for buttons, windows, menus, icons, etc. One would use
WYSIWIG editors on one of the resources (a dialog box); and that
tool would automatically modify Say.rc so that it then contains
proper instances of the classes, to go with your program.
The program Say.cpp will then be modified to contain the
program code that you want to use to interact with the screen
objects you created. Going back to the event-handling concept,
the Say.cpp program is establishing "bindings" between
objects (which it also creates, when it first runs.) These bindings
are in the form of callback functions.
When you edit a button, for instance, in a dialog box, here
is what you are asked.
Dialog
IDD_ABOUTBOX
IDD_SAY_DIALOG
You are being offered a chance to edit either the "About
box" or the "Dialog Box" you requested from the
Wizard. When you click on IDD_SAY_DIALOG, you get a picture of
the "default dialog box". You will be offered chances
to edit the features in the box (buttons, etc.), to name the button
and specify the messages sent by the button, and to what method
of the associated class.
I'd like to tell you more but I'm out of time for writing
these notes!
A2
1. Get Microsoft Visual C++ working on your computer. Use
the tutorials that come with it to get familiar with basic application
building.
2. Go to the MESA web site described above, down-load MESA
for your Windows environment and construct a "hello world"
application which draws a square box in the center of the screen.
How to proceed? Get a tutorial book on Visual C++ and WORK FAST! We have only allocated two weeks for you to get Visual C++ running and MESA installed in it. Take maximum advantage of your classmates' knowledge. We will pair you up with a guide-person if needed.