COS 426 / Assignment 3
An exercise in drawing circles
Due 11:59 PM, Tuesday, October 24, 1995
This assignment will allow you to explore a variety of
different approaches to the drawing of circles.
In so doing, we will reinforce the class lectures
on scan conversion.
As in the previous assignment, we will provide
a user interface and you will be asked to plug in your
circle drawing algorithms.
Once the assignment is completed, you'll be asked to answer some questions
about the comparative aesthetics (and speed) of the various drawing
methods.
We will consider 4 methods of drawing circles.
- This is the standard Bresenham method described in class
and in the textbook. It is based on the DDA approach and uses
symmetries to consider only points in one octant, plotting each
point 8 times symmetrically.
- This is an approximation to the circle via a regular polygon
of N sides. You will first need to implement Bresenham's algorithm
for drawing line segments. Then, you will compute the vertices of a
regular N-gon of appropriate radius and center. Finally, these
vertices will be joined by line segments to form the polygon that
approximates the circle.
- This is an approximation to the circle by cubic spline curves.
You are to implement the Bezier method discussed in class
for drawing a curve from 4 control points. Having done so,
you must then find values and derivatives for points around the
circle. These data will be used to create sets of control points
to be used as input to your Bezier routines. The output of
your Bezier routines will then be patched together to form a circle.
The user supplies the number of patches, from which you can find
the starting and ending point of each patch.
- This is an approximation to the circle by sampling. What you
are to do is to choose k points in each pixel. For each
point, determine if it intersects the circle boundary. Record
which fraction of the sample points intersect the boundary.
Color the pixel in this fraction. Begin with k = 1 and color
pixels either black or white. Then, extend to larger values of k
and do gray scale coloring. Typically, you want k to
be a perfect square so it's reasonable to choose the sequence 1,4,9, ...
In order for this method to work, you need to
thicken the circle boundary. You can do so
testing sample points to see if they are within .5 unit of
the boundary (why?). For reasons of efficiency, you will
want to identify those pixels that need not be tested and
focus your attention on those that might be relevant.
Once you have all the circle routines working, you are required to experiment
with them for circles of varying radius. When doing so, notice which
routines are faster and which slower. You are to create a file
called WhatIveLearned that you submit with your code.
This file should contain your conclusions about the tradeoffs in
circle drawing.
To see a fully working example program, run this:
/u/cs426/bin/circles
The circle drawing functions are implemented as:
bresenham_circle(int cx, int cy, int radius),
ngon_circle(int cx, int cy, int radius, int nr_vertices),
bezier_circle(int cx, int cy, int radius, int nr_patches),
sample_circle(int cx, int cy, int radius, int nr_samples, float
boundary_width).
Your job will
be to write code for these functions.
You will also need to fill in code
for bresenham_line(int x1, int y1, int x2, int y2), which
is used by ngon_circle.
Copy the directory
/u/cs426/Examples/Circles
You'll find files bresenham.c, ngon.c, bezier.c, and
sample.c, which contain empty functions that you'll have
to fill in.
Whenever you see the string WORK HERE, you
will have some work to do.
When you type make, you'll be building a program called
cirwish. The wish script for cirwish is circles.
Some general issues:
- In the file
common.c you'll find the function
plot(int x, int y) which you should use as your
plotting function.
- In the demo program, press the left mouse button to draw a
circle, press the middle button to clear the screen. You
may increase or decrease a slider value by one by clicking
in the empty area to the right or left of the slider button.
- The demo program draws the circles in the back buffer, swaps
the buffers, and draws the same circle again in the
back buffer. This is done so we won't give too much away about
how the circles are drawn. Your program will simply use one
buffer.
- Furthermore, the demo program contains random delay loops,
so it won't be obvious which method is fast or slow. Note that
this causes the program to be painstakingly slow at times,
especially when drawing concentric circles. So it is safe to
say that your program generally should execute faster.
- We'll grade this assignment not just by seeing if it all works,
but we'll also look at:
- Efficiency
- Quality of coding
- A program you may find useful is
/usr/demos/bin/snoop
It allows you to examine your circle from up close.
- Note that your program should not have any "off by one" errors.
This includes the error of writing the same pixel twice.
When you're done, please submit:
- All .c and .h files
- Makefile
- circles
- a README file with your name, make instructions etc.
- a WhatIveLearned file with your conclusions about the tradeoffs
in circle drawing