printer version

Introduction to Computer Graphics

Fall 2008

Graphics is a flourishing field within computer science. Driven by the tremendous increase in speed and quality of hardware and software, it has rapidly gained popularity among a wide variety of users. With applications as far-reaching as special effects, synthetic content, interactive TV, graphical user interfaces, information visualization, interactive art, industrial design, education, computer games ranging from Doom 3 to The Sims, virtual reality, and the Internet, computer graphics plays an increasingly important role in our lives, both practically and culturally. This course is aimed to be a comprehensive introduction to basic concepts and algorithms in this field, and topics covered will include the fundamentals of scan conversion of geometric primitives, 2D and 3D transformations, 3D viewing and projection, color, hidden surface removal, simple illumination models, modeling, animation, and user interfaces.

The Brown University Computer Science Department is a great place to learn about computer graphics, as a strong percentage of our faculty are dedicated to the field. Most of your work will be done in the new Linux lab. Each of the roughly 80 computers in the lab have 2GB of memory, two 2.1GHz Athlon 64 processors, and a GeForce graphics card. We are now running Debian GNU/Linux on these machines. The advanced graphics features of the workstations will be used often in this class, as you will be building a functional 3D modeler/renderer from scratch.

1 :: Staff

The professor for CS123 is Andries "Andy" van Dam (avd). Additional lectures may be given by John "Spike" Hughes, Anne Morgan Spalter, Barbara Meier, and Jeff Beall of PDI DreamWorks. The Head TA this year is Chris Maloney (cmo). The other TAs are (in alphabetical order by login). Jeffrey Cohen (jscohen), Marshall Agnew (maagnew), Nong Li (nli), Stephen Barlow (sbarlow), and Travis Fischer (tfischer). All TAs have taken the course within the last two years.

2 :: Structure

You will start with a warm-up assignment, Brush, that is designed to be a gentle introduction to the kind of C++ coding you will be doing for this class. Next, you will start a series of assignments that are an important part of the 3D rendering pipeline. You will first write a tessellation engine in the Shapes assignment. You will move on to write a linear algebra package used by your transformation engine and a camera model in the Transform/Camera assignment. In the next assignment, Sceneview, you will display hierarchal objects defined in a text-based scenefile format. We will then make a short digression from 3D, and you will implement some cool image processing filters in the Filter assignment. The course will end with you writing a working 3D modeler/renderer using the code you have written in the previous assignments.

You should note that each assignment builds on the others, and you are expected to reuse what you wrote in previous programs.

Hence, design your programs in as modular a fashion as possible, allowing for extensibility. It should be clear that falling behind is not a good idea for this course, so start early. If part of a program is broken, you may need to fix it before you can continue in order for the next program to work. Why did we decide to make the assignments build upon one another like this? Because you couldn't finish the last assignments in two weeks, so we give you [your own] code as support. This is also a perhaps painfully realistic development situation, where good design early on will pay for itself many times over when extended. An interactive 3D modeler, the culmination of your work, is a complex application (and is really neat to play with). By the time you're done with 123, you will have built and will know each component piece of the modeler backwards and forwards, and will be using no support code (save for some very thin wrappers around OpenGL and Motif).

Grading for CS123 will include interactive grading sessions. Basically, this means you will have an option to be present when TAs grade your program.

Each assignment will include a separate written algorithm component. The algorithm will be a paper handin you will need to submit a few days after the assignment is given out. In the algorithm handin, you will answer questions that are designed to lead you through the tricky portions of the given assignment. It is in your best interest to fully understand the answers before you try writing any code.

3 :: Textbooks

The primary text for this course (and for CS224) is Computer Graphics: Principles and Practice, Second Edition in C, by Foley, van Dam, Feiner, and Hughes (about $70.00 at the Brown Bookstore). This book is not required, but is highly recommended, especially if you intend to go beyond CS123 in graphics, and will be referenced in the lecture notes. We also recommend Anne Spalter's book, The Computer in the Visual Arts, especially for students with an interest in the visual arts. Her book can be purchased through amazon.com. There may also be some copies available in the Brown Bookstore.

4 :: Lectures

Class will meet on Tuesdays and Thursdays from 10:30 to 11:50 in Lubrano Conference Room (4th floor CIT). Lecture slides will be available for viewing and/or printing on-line from the CS123 Web page.

5 :: Help Sessions

The TAs will arrange help sessions for each of the assignments and more difficult topics, if necessary; these will be announced on the CS123 Web page (http://www.cs.brown.edu/courses/cs123/). Stay tuned! If you feel a help session would be useful to clarify a topic, feel free to contact the Head TA by mailing cs123headtas@cs.brown.edu. Assignment-based help sessions will take place around the algorithm handin deadline, in order help you think about and work out the design issues. Help sessions will be question-driven, so be sure to write down any questions you have and bring them with you. For some assignments, there will be an interactive component to learning the concepts necessary to complete the current assignment. You will be using interactive educational java applets ("exploratories") specifically designed for CS123 and implemented mostly by undergraduates.

6 :: Programming

6.1 :: Java and C++

For many years, CS123 has been offered exclusively in C++. Knowledge of the principles of object-oriented programming (OOP) is a prerequisite for this course. If you are unfamiliar with OOP, CS123 may not yet be the course for you.

A note to those of you who don't yet know C++: highly motivated and capable students are allowed to take the course without knowing C++ or C. However, you must spend extra time at the beginning of the course teaching yourself C++. A Java to C++ transition document as well as a list of recommended C++ books are available on-line on the CS123 home page. Also, there will be a C++ mini-course running early in the semester. Check the website for times and location. If you don't have C++ experience, attendance at the mini-course is mandatory.

While the TAs are willing to answer a few C++ language questions, TA hours are a valuable student resource that we have to devote to teaching graphics, not teaching languages. There will be no special provisions built into the curriculum for students learning C++. Programs will be due at the same time for everyone as well as graded on the same scale.

6.2 :: Programming Environment

CS123 does not support any integrated development environment. We expect that you will be writing, compiling, and testing your programs using emacs, make, and a debugger, or whatever your favorite tools happen to be. For those of you coming straight out of CS16, the consultants will be offering mini-courses on the use of the standard tools in the beginning of the semester. You will find the details of building projects much less confusing if Makefiles and compiler semantics are comfortable territory. It is a worthwhile thing to spend several hours understanding.

All assignments for the course must run on the department's Linux workstations. It is possible to work at home using either Exceed3D for windows, or, preferably, a bona fide X Server on a Linux or BSD installation of your own. However, this is not supported by the TA staff and the programs must still run as expected on the lab computers if you want them to be graded.

7 :: Assignments

7.1 :: Brush

The first assignment is designed to get your feet wet in the world of graphics programming. In this assignment, you will be implementing various different airbrushes, similar to ones found in many commercial painting programs such as Adobe's Photoshop. This assignment should give you a good introduction to the kind of C++ programming you will be doing in this course, as well as gently familiarize you with the basic conventions of the support code.

7.2 :: Shapes

This assignment covers one of the earliest steps in the 3D rendering pipeline: object tessellation. For this assignment you will be constructing simple 3D objects (e.g., spheres and cylinders) out of triangles and then displaying them on the screen. All you need to do for this assignment is compute and store the necessary triangles; OpenGL handles the task of drawing them for you. The code written in this assignment will be integral to the success of the assignments that follow.

7.3 :: Transform/Camera

In previous years, the Transform and Camera assignments were separate entities. But now, in the interests of time, they have been combined into one assignment. Students tended to find this part of the course extremely easy in past years, which is great; however, they were often equally overwhelmed later on. By allotting less time for transform and camera, or "camtrans" as they are now known, you are likely to have a more reasonable schedule as cs123 progresses towards the largest assignments.

This assignment first involves writing your own linear algebra package. Once completed, you will be able to easily manipulate points, vectors, and transformation matrices. If you don't know what that means, you'll also be learning a thing or two about linear algebra. After using the TA-supplied tester to check your work, you'll get to move on to crafting your own virtual camera. Essentially, this camera will use information about the eye point, viewing direction, et cetera, and produce a transformation matrix to display 3d graphics on our 2d output devices. Once again, the code written in this assignment is absolutely essential to the proper function of later assignments.

7.4 :: Sceneview

At this point you will have the ability to display, transform and view 3D objects. The next step is for you to put these tools together to view a scene consisting of arbitrarily positioned objects from an equally arbitrary location. In this assignment, you will build your own viewer for moderately complicated scenes. In past years this process has involved tedious and often time-consuming file parsing. We have written a clean C++ interface to the file format and moved the actual parsing into the support code this year. The assignment should be simpler as a result, and the time saved here will make November less stressful. The code written in this assignment will be integral to the success of the assignments that follow. Design extensibly!

7.5 :: Filter

Ever wonder how paint programs like Adobe Photoshop generate all those cool special effects? Well, this assignment represents a subset of the functionality that Photoshop has. It is designed to teach you the basics of image processing and anti-aliasing. You will implement different image manipulation operations like edge detection, blur, and image scaling.

In previous years, there has been a particularly long and complicated algorithm worksheet for filter. Since it was important, it's been kept (in spirit), but since it had little to do with implementing the program, it has been separated into an actual written homework on image processing. This homework will go out a few days before the filter programming assignment. The actual algorithm worksheet for filter is now easier and more relevant in turn.

7.6 :: Intersect

In this assignment you will develop classes that you can use to compute intersections between the common objects you tessellated in shapes, and a ray (presumably of light). You will then use these classes to create somewhat photorealistic images of scenes. The code written in this assignment will be integral to the success of the assignments that follow.

7.7 :: Ray

Ray tracing is a method for rendering realistic pictures of geometric objects using available information about lighting and optical effects like light reflection and refraction. It may sound complicated, but it is a relatively simple technique, and the cool pictures you get are well worth it! You will essentially be taking your classes from Intersect, adding in the ability to illuminate the objects, and applying a texture from a 2D image to them.

7.8 :: Modeler

Lastly, you will be writing a 3D modeling program which will allow you to interactively construct and preview a three dimensional scene made up of spheres, cubes, cones, and cylinders. This assignment is an exercise in the tricky topics of 3D interaction and user interfaces, and will get you thinking about some of the interaction research done here at Brown. This program will be the culmination of all your hard work in which the programs you have worked on all semester will be combined into one integrated application.

Now that we have fancy new hardware in the lab, we've added a programmable hardware section to the modeler assignment. You will use nvidia's high level shader language, Cg, to write vertex shaders that allow you to customize how triangles are lit and shaded. Programmable graphics hardware is the future and you'll gain practical experience with it!

7.9 :: Algorithm Worksheets

In addition, we will be requiring a paper algorithm handin with each assignment. It will be due at the beginning of class on the day of the algorithm handin deadline. If there is no class or you cannot make it to class on the appropriate day, your handin should be placed in the handin bin marked for CS123 on the second floor of the CIT before 10:30am. Algorithms not due on a class day are due sometime in the early afternoon.

7.10 :: Handing In

You will be expected to hand in all your source code on-line and your algorithm on paper. Your working source code should be handed in on-line by 11:59 PM on the due date, or the deadline announced; exact handin procedure will be in the assignment handout. Algos should be handed into the CS123 bin in room 242 on the second floor of the CIT.

8 :: Grades

Grades will be determined based on the programming assignments and the algorithm handins. There will be no quizzes, midterm, or final exam. However, to get credit for the course, you must complete all the assignments (see Section 10). As in all other computer science courses at Brown, you have to hand in a working solution to all programming assignments in order to be eligible for a passing grade. Please note the adjective working: if you receive a grade of NC (no credit) on any of the assignments (before late penalties are deducted), you will be expected to revise your program and hand in an acceptable version if you want to pass the course. Also note that the reverse implication is not intended: handing in all assignments does not guarantee that you will pass the course; your accumulated points will determine that. And as an example, handing everything in on the last day of classes will not be looked upon favorably.

Andy doesn't use a curve, and would be delighted to hand out A's to the entire class. Indeed the majority of students traditionally have worked hard and gotten A's. For borderline cases, Andy will take attendance and class participation into account as well as perceived effort and dedication.

Sometimes you may think that you have been graded unfairly. Please take this up with the TA who graded your assignment; if you are not satisfied with their explanation, talk to Chris (the Head TA). If there is still a problem, Andy is the final word in grading and will be happy to hear what you have to say. Also, once the grades have gone out, you will only be given two weeks to lodge a protest. In the past, students have tried to get points back on all of their assignments in the last week of classes, and though we would like to promote fair grading, we would like to dismiss malintentioned hassling. Our first priority is fairness (both to us and to you), so please do complain about grades if you don't agree with them.

8.1 :: Algorithm Handins

The algorithm handins are one way for the TAs to know that you have spent time thinking about your programming assignments. For each assignment there will be a sheet with specific questions for you to answer. The algorithm question sheet will be attached to the assignment handout. You should write your responses to the questions in the space provided on the algorithm handout (neat writing please!) or feel free to type up answers. Algorithms will not be graded if they cannot be read. Hand in the completed handout to the CS123 handin bin located next to the TA room. As mentioned above, the algorithm handin will constitute 10% of the corresponding assignment's grade.

Algorithm answers should be clear and succinct. Don't just start writing. Think about it first. The intention of the algorithms is to give students a place to clearly describe the concepts. If we have to stop and try to figure out what you're saying, you're not saying it clearly enough. If we ask you to describe a section of code, you should probably go with a description, or pseudocode, rather than actual C++ (unless there are parts that are incredibly simple, such as loops, which are almost easier to read in actual code).

We highly recommend that you make a copy of this handin for yourself to reference when you actually start coding. You cannot apply any late days to these handins, since the solutions will be handed out immediately after the deadline. If you are sick or have another legitimate excuse approved by the department, your assignment grade will be purely based on your program. No other exceptions will be made.

8.2 :: Interactive Grading Session

We will be offering students the option of having their assignments graded interactively with a TA. Once each assinment has been handed in, each TA will hold grading hours during which students will be able to sign up to be graded. We highly recommend that you show up to observe and answer questions although it is not mandatory (it will only work in your favor). The TAs will then grade the program in front of you. At the end of the session you will have your grade. To avoid misunderstanding and to ensure swift, painless grading, the following rules will be strictly enforced:

1. During the session, students should only answer questions asked by the TA. Students will be given the opportunity to volunteer information in the beginning and at the end of the grading session.
2. If there is a disagreement between the student and the TA regarding a point deduction, the argument should wait until the end of the grading session. If the disagreement cannot be settled, then the student may choose to contact the Head TA. If the student still disagrees with the Head TA's judgment, an appeal can be made to Andy directly.
3. TAs will explain why each deduction is made verbally as they grade.
4. TAs may ask any questions regarding the assignment.
5. All grading is based largely on functionality, but TAs may choose to look at any of your code.
6. Students are encouraged to bring printed source code with them so that they may answer questions more effectively.
7. You cannot change which TA grades your assignment.

If you cannot make a particular TA's grading hours, your assignment will be graded normally.

8.3 :: Software Engineering Practices

We expect that at this point you have all had a thorough grounding in the principles of good software design. Most of the programs are relatively small, and shouldn't require hours and hours of design work. When grading, we will be looking mostly at the functionality, stability, and speed of your implementation. However, if a program is clearly poorly designed, it will affect your grade. But for the most part we are trusting your maturity as software engineers. The things we care the most about are that you 1) avoid repeated code by doing good class design in advance, and 2) don't do anything grossly inefficient. These engineering concepts are very basic.

8.4 :: Relative Weights

Here are the relative weights of the assignments, subject to change with notice on the CS123 home page:

All algorithms are worth 10% of the project grades.

8.5 :: Extra Credit

There is ample room for bells, whistles, and other credit-garnering efforts on the part of ambitious programmers. You are invited to get creative, as long as it does not make you late. Rewarding bells and whistles with extra credit is left to the discretion of the TAs, so we strongly encourage you to discuss your creative plans with a TA before you forge ahead to make sure that they are considered appropriate for credit. Also, keep in mind that bells and whistles should only be done after the standard assignment is fully working since they won't count in lieu of missing or buggy features! CS123 is a great vehicle for extra credit: if you finish a program a little early, seek appropriate inspiration and add something fancy.

8.6 :: Workload

This set of assignments probably looks like a burden, but in fact, if approached sensibly (i.e., working steadily), you will have sufficient time for each and every one. The normal load is about 15 hours per week. By the time you take CS123 you are expected to be a competent OOP programmer in C++, with good design and debugging habits, and able to turn assignments in on time. Good time management will make this course much more enjoyable.

8.7 :: Late Policy

Your TAs realize that sometimes you may have schedule conflicts -- an exam on the day your program is due, etc. Unfortunately, we can't give extensions for academic overload, but you do have the option of handing your program in late. Everything must be handed in by the super-deadline 12/11/2006.

8.7.1 :: Late Penalties

If you are forced to hand an assignment in after the due date, your grade will then be subject to a penalty, depending on the lateness of your handin. A percentage of the score you received will be deducted as follows:

The above are guidelines. Consult your assignment handouts and/or the CS 123 web pages for specific deadlines for each assignment; they may be different for each assignment. And please be aware that these deadlines are strict: a handin that's ten minutes late is still late. Plan accordingly, especially when the lab is full and the server is heavily loaded.

Algorithms are graded and returned soon after the handin date along with the answers. Therefore, they cannot be accepted late.

8.7.2 :: Extensions

Extensions can be granted for medical reasons if you present the Head TA with a note from Health Services, or for other reasons with a note from a dean. Other extensions will be granted extremely rarely and only at the discretion of the Head TA or Andy.

8.7.3 :: Late Days

You have three late days which you can use over the course of the semester to accommodate schedule crunches. Your late days will be optimally assigned by us at the end of the semester.

9 :: Getting Your Questions Answered

There are two ways of getting questions answered and problems solved. You can talk to a TA during TA hours or send questions to the mailing list. You may not ask TAs questions when they are not on hours or call the TAs at home. Also, you should not e-mail the TAs with questions specific to your implementation of the assignment -- those kind of questions should be brought to a TA on hours. However, if there are no TA hours which you can attend, let the Head TA know about this and we will try our best to accommodate you. The mailing list will be set up in the first few weeks of class.

9.1 :: TA Hours

The TA hour listing will be available from the CS123 home page and TA hours will be held in the TA room or the moonlab (CIT227). When TA hours are rescheduled or exceptions are made, these will be announced in the CS123 web page or on the mailing list. Do not expect TAs to bring up your code on screen and help you debug. This is left up to their discretion, and is not part of their job description.

9.2 :: Sending mail to the TAs

If you have a graphics question that won't be of interest to the class at large, you can mail the TAs about it by sending mail to the cs123tas@cs.brown.edu alias. Please use good judgment when doing this and consider how urgent your problem is so that the TAs won't be swamped. If it's not that urgent, try the mailing list first. In general, the TAs will read their mail daily and will respond as soon as their schedule allows.

If you have administrative questions, or if you disagree with a TA's grading, discuss this with the Head TA. You can either show up for TA hours or email cs123headtas@cs.brown.edu.

9.3 :: The CS123 web page

The CS123 web pages (http://www.cs.brown.edu/courses/cs123/) are a great source of on-line course material. A wide variety of things like lectures, handouts, the syllabus, TA hours, and software guides can be found on this page.

10 :: Collaboration Policy

Before any of your work is graded, you will be required to sign a collaboration policy, described as follows.

We believe that too strict a collaboration policy allows virtually no cooperation or discussion between students, and stifles the learning process to some extent. Consequently, CS123 has a more liberal, honor-system based policy that depends on the maturity of the students to know what work should be their own and what they can share with their peers. We stick to Brown's basic Academic Code, interpreted as follows:

All written work must be your own.

The basic premise is that you should do your own thinking, your own design, and your own coding. You're allowed to talk to other students about the content of the lectures and of the textbook, and about high level problems and concepts. A written record should never be made. If you can come to understand a challenging concept with the assistance of a peer, then you should be able to work through it again on your own. You can answer questions from other students about packages used for assignments, as long as the problem is a technical issue and not a question that concerns the problem-solving process at large. We realize that C++ (and associated tools and concepts such as gdb and memory management) is going to be new to some of you. You are allowed to assist another student in learning to use C++ and related tools, but mailing-list-like rules apply to what you can and cannot discuss.

On a general level, what is not allowed is that you let yourself be led by another student, to the extent that your task becomes significantly less challenging because of your discussion with him or her. In conversation with other students, be sure not to venture into design and coding specifics. In particular, don't sit down with someone else before you've analyzed the problem in-depth on your own.

Specifically, you should do your own problem solving, do your own program design and decomposition, and design your own algorithms and data structures. If you are discussing what algorithms or functions you wrote to solve the problem, or describing header files or specific lines of code, then you are breaking the Non-Collaboration rule.

The most blatant violation that can occur is code-copying, and this will absolutely not be tolerated. We reserve the right to do a "wire-pull test" (i.e., ask you to explain any aspect of your program), and we will be routinely comparing your code to that of other students for undue similarity. To do this, we use an automated system known as MOSS (Methods of Software Similarity). We use this to compare not only all assignments from this year, but also those from previous years.

In order to circumvent this problem, we require that all students maintain appropriate permissions on their coursework. Other students should not be able to access, view, or copy your files. Use the 'chmod' command to set appropriate permissions. If you don't know how to do this, ask a consultant or see a TA. Alternatively, type 'man chmod' in a shell. If another student copies your work, you will be held accountable for negligence.

We believe that this policy is explicit enough to guide your judgment and that we have not left you much gray area. If you are ever in doubt about the legality of your actions, be sure to clear them with a TA, even after the event has already occurred. When we confront a student with a case of suspected violation, an answer of "I didn't know that this is wrong" will not be met with sympathy. Suspected cases of disallowed collaboration will be referred to the Deans and typically result in a directed NC on your transcript and parental notification.

Again, note that you are expected always to initially approach a problem on your own, and seriously attempt to find a solution. You are honor-bound to preserve your independence of thought. And remember that the TAs should always be your first resource when you have a question or problem.

11 :: Special Accommodations

Students requiring special accommodations should see Andy or the Head TA at the beginning of the semester to make arrangements.

12 :: Finally...

As we mentioned before, CS123 is a continually evolving course which has been updated again this year. Most of the changes were made in response to comments from last year's students. As such we are bound to have our own `bugs' hiding in the corners. Please read everything we hand out very carefully. If there is something which you do not understand, or which is not stated very clearly, please let us know so we can fix it right away.

This applies to the material discussed in lecture as well. Give us constructive criticism on all aspects of the course. The more feedback there is, the better we can make this course for you as the semester progresses, and the better we can make it for the next twenty-five years of Brown computer graphics students!

We just went through a lot of heavy talk. Please take all of it seriously, but also remember that we're not trying to scare you: the TAs are here to help you! We're just clearing preliminaries and establishing the ground rules. With that done, we hope you'll have as much fun as we did in CS123.