Sample positions in screen space

Due Date

Mon Feb 8th, 11:59pm

Overview

In this project, you will implement a simple software rasterizer that draws points, lines, triangles, and bitmap images. When you are done, you will have a viewer that supports the basic features of the Scalable Vector Graphics (SVG) format that is now widely used on the internet.

Getting started

We will be distributing assignments with git. You can find the repository for this assignment at http://462cmu.github.io/asst1_drawsvg/. If you are unfamiliar with git, here is what you need to do to get the starter code:

$ git clone https://github.com/462cmu/asst1_drawsvg.git

This will create a asst1_drawsvg folder with all the source files.

Build Instructions

In order to ease the process of running on different platforms, we will be using CMake for our assignments. You will need a CMake installation of version 2.8+ to build the code for this assignment. The GHC 5xxx cluster machines have all the packages required to build the project. It should also be relatively easy to build the assignment and work locally on your OSX or Linux. Building on Windows is currently not supported, but the project can be run by SSH'ing through Andrew Linux using MobaXterm.

If you are working on OS X and do not have CMake installed, we recommend installing it through Macports:

sudo port install cmake

Or Homebrew:

brew install cmake

To build your code for this assignment:

$ cd p1 && mkdir build && cd build
$ cmake ../src
$ make
$ make install

Using the Mini-SVG Viewer App

When you have successfully built your code, you will get an executable named drawsvg. The drawsvg executable takes exactly one argument from the command line. You may load a single SVG file by specifying its path. For example, to load the example file svg/basic/test1.svg :

./drawsvg ../svg/basic/test1.svg

When you first run the application, you will see a picture of a flower made of a bunch of blue points. The starter code that you must modify is drawing these points. Now press the R key to toggle display to the staff's reference solution to this assignment. You'll see that the reference differs from "your solution" in that it has a black rectangle around the flower. (This is because you haven't implemented line drawing yet!)

While looking at the reference solution, hold down your primary mouse button (left button) and drag the cursor to pan the view. You can also use scroll wheel to zoom the view. (You can always hit SPACE to reset the viewport to the default view conditions). You can also compare the output of your implementation with that of the reference implementation. To toggle the diff view, press D. We have also provided you with a "pixel-inspector" view to examine pixel-level details of the currently displayed implementation more clearly. The pixel inspector is toggled with the Z key.

For convenience, drawsvg can also accept a path to a directory that contains multiple SVG files. To load files from svg/basic:

./drawsvg ../svg/basic

The application will load up to nine files from that path and each file will be loaded into a tab. You can switch to a specific tab using keys 1 through 9.

Summary of Viewer Controls

A table of all the keyboard controls in the draw application is provided below.

Command Key
Go to tab 1 ~ 9
Switch to hw renderer H
Switch to sw renderer S
Toggle sw renderer impl (student soln/ref soln) R
Regenerate mipmaps for current tab (student soln) ;
Regenerate mipmaps for current tab (ref soln) '
Increase samples per pixel =
Decrease samples per pixel -
Toggle text overlay `
Toggle pixel inspector view Z
Toggle image diff view D
Reset viewport to default position SPACE

What You Need to Do

The assignment is divided into eight major tasks, which are described below in the order the course staff suggests you attempt them. You are of course allowed to do the assignment in any order you choose. Although you have nearly 2.5 weeks to complete this assignment, the assignment involves significant implementation effort. Also, be advised that meeting the requirements of later tasks may involve restructuring code that you implemented in earlier ones. In short: you are highly advised to aim to compete the first three tasks in the first week of the assignment.

NOTE: Tasks 4-6 depend on concepts that will be discussed in Lectures 4 and 5, so it is not expected that you understand those requirements at the time this assignment is released.

Getting Acquainted with the Starter Code

Before you start, here are some basic information on the structure of the starter code.

Most of your work will be constrained to implementing part of the class SoftwareRendererImp in software_renderer.cpp. The most important method is draw_svg which (not surprisingly) accepts an SVG object to draw. An SVG file defines its canvas (which defines a 2D coordinate space), and specifies a list of shape elements (such as points, lines, triangles, and images) that should be drawn on that canvas. Each shape element is has a number of style parameters (e.g., color) as well as a modeling transform used to determine the element's position on the canvas. You can find the definition of the SVG class (and all the associated SVGElements) in svg.h. Notice that one type of SVGElement is a group that itself contains child elements. Therefore, you should think of an SVG file as defining a tree of shape elements. (Interior nodes of the tree are groups, and leaves are shapes.)

Another important method on the SoftwareRendererImp class is set_render_target(), which provides your code a buffer corresponding to the output image (it also provides width and height of the buffer in pixels, which are stored locally as target_w and target_h). This buffer is often called the "render target" in many applications, since it is the "target" of rendering commands. We use the term pixel here on purpose because the values in this buffer are the values that will be displayed on screen. Pixel values are stored in row-major format, and each pixel is an 8-bit RGBA value (32 bits in total). Your implementation needs to fill in the contents of this buffer when it is asked to draw an SVG file.

set_render_target() is called whenever the user resizes the application window.

A Simple Example: Drawing Points

You are given starter code that already implements drawing of 2D points. To see how this works, begin by taking a look at draw_svg() software_renderer.cpp. The method accepts an SVG file, and draws all elements in the SVG file via a sequence of calls to draw_element(). For each element draw_element() inspects the type of the element, and then calls the appropriate draw function. In the case of points, that function is draw_point().

The position of each point is defined in a local coordinate frame, so draw_point() first transforms the input point into its screen-space position (see line p_screen = transform(p)). This transform is set at the beginning of draw_svg(). In the starter code, this transform converts from the svg canvas' coordinate system to screen coordinates. You will need to handle more complex transforms to support more complex SVG files and implement mouse viewing controls later in the assignment.

The function rasterize_point() is responsible for actually drawing the point. In this assignment we define screen space for an output image of size (target_w, target_h) as follows:

Sample positions in screen space

To rasterize points, we adopt the following rule: a point covers at most one screen sample: the closest sample to the point in screen space. This is implemented as follows, assuming (x, y) is the screen-space location of a point.

int sx = (int) floor(x);
int sy = (int) floor(y);

Of course, the code should not attempt to modify the render target buffer at invalid pixel locations.

if ( sx < 0 || sx > target_w ) return;
if ( sy < 0 || sy > target_h ) return;

If the points happen to be on screen, we fill in the pixel with the RGBA color associated with the point.

  render_target[4 * (sx + sy * target_w)    ] = (uint8_t) (color.r * 255);
  render_target[4 * (sx + sy * target_w) + 1] = (uint8_t) (color.g * 255);
  render_target[4 * (sx + sy * target_w) + 2] = (uint8_t) (color.b * 255);
  render_target[4 * (sx + sy * target_w) + 3] = (uint8_t) (color.a * 255);

At this time the starter code does not correctly handle transparent points. We'll come back to this later.

Now that you understand the basics of drawing elements, let's get to work actually drawing more interesting elements than points!

Task 1 : Warm Up: Drawing Lines

In this task you will add line drawing functionality by implementing the function rasterize_line() in software_renderer.cpp.

In Lecture 2, we discussed a few ways to think about rasterizing a line. (Recall we talked about possible rules for what samples are considered to be "covered" by the line, and we discussed algorithms for efficiently determining what samples meet that criteria. Since line drawing is very well documented on the web (and this is just a warm up exercise), you may consult the web and use any algorithm you wish. However, your solution should:

We encourage you to start with an implementation of Bresenham's algorithm and then, if you wish, continue on with implementations that improve quality (e.g., draw smooth lines) or optimize drawing performance.

When you are done, your solution should be able to correctly render basic/test2.svg.

Possible Extra Credit Extensions:

Task 2: Drawing Triangles

In this task, you will implement rasterize_triangle() in software_renderer.cpp.

Your implementation should:

Once you have successfully implemented triangle drawing, you will able to draw a large number of examples. When loading an SVG, the provided code triangulates convex polyhedra into a list of triangles for you, so by implementing support for rasterizing triangles, the viewer now supports drawing any of these shapes as well. (When parsing the SVG, we convert rectangles and polygons specified in the file into lists of triangles.)

When you are done, you should be able to draw basic/test3.svg, basic/test4.svg, and basic/test5.svg.

Possible extra credit extensions:

Task 3: Anti-Aliasing Using Supersampling

This part of the assignment requires only knowledge of concepts from Lectures 1, 2, and 3.

In this task, you will extend your rasterizer to anti-alias triangle edges via supersampling. In response to the user changing the screen sampling rate (the = and - keys), the application will call set_sample_rate() . The parameter sample_rate defines the sampling rate in each dimension, so a value of 2 would correspond to a sample density of 4 samples per pixel. In this case, the samples lying within the top-left pixel of the screen would be located at locations (0.25, 0.25), (0.75, 0.25), (0.25, 0.75), and (0.75, 0.75).

Super-sampling: sample positions in screen space

It's reasonable to think of supersampled rendering as rendering an image that is sample_rate times larger than the actual output image in each dimension, then resampling the larger rendered output down to the screen sampling rate after rendering is complete. To help you out, here is a sketch of an implementation. Note: If you implemented your triangle rasterizer in terms of sampling coverage in screen-space coordinates (and not in terms of pixels), then the code changes to support supersampling should be fairly simple for triangles:

When you are done, try increasing the supersampling rate in the viewer, and bask in the glory of having much smoother triangle edges.

Also observe that after enabling supersampled rendering, something might have gone very wrong with the rasterization of points and lines. (Hint: they probably appear to get thinner!) Please modify your implementation of rasterizing points and lines so that supersampled rendering of these primitives preserves their thickness across different supersampling rates. (A solution that does not anti-alias points and lines is acceptable.)

Possible Extra Credit Extensions:

Task 4: Implementing Modeling and Viewing Transforms

Part 1: Modeling Transforms

This part of the assignment assumes knowledge of concepts in Lecture 4.

In Lecture 3 and Lecture 4 we discussed how it is common (and often very useful) to describe objects and shapes in their own local coordinate spaces and then build up more complicated objects by positioning many individual components in a single coordinate space. In this task you will extend the renderer to properly interpret the hierarchy of modeling transforms expressed in SVG files.

Recall that an SVG object consists of a hierarchy of shape elements. Each element in an SVG is associated with a modeling transform (see SVGElement.transform in svg.h) that defines the relationship between the object's local coordinate space and the parent element's coordinate space. At present, the implementation of draw_element() ignores these modeling transforms, so the only SVG objects your renderer has been able to correctly draw were objects that contained only identity modeling transforms.

Please modify draw_svg() and draw_element() to implement the hierarchy of transforms specified in the SVG object. (Yes, this is a simple task that should involve no more than a few lines of code.)

When you are done, you should be able to draw basic/test6.svg.

Part 2: Viewing Transform

Notice the staff reference solution supports image pan and zoom behavior (drag the mouse to pan, use the scroll wheel to zoom). To implement this functionality in your solution, you will need to implement ViewportImp::set_viewbox() in viewport.cpp.

A viewport defines a region of the SVG canvas that is visible in the app. When the application initially launches, the entire canvas is in view. For example, if the SVG canvas is of size 400x300, then the viewport will initially be centered on the center of the canvas, and have a vertical field of view that spans the entire canvas. Specifically, the member values of the Viewport class will be: x=200, y=150, span=150.

When user actions require the viewport be changed, the application will call update_viewbox() with the appropriate parameters. Given this change in view parameters, you should implement set_viewbox() to compute a transform canvas_to_norm based on the new view parameters. This transform should map the SVG canvas coordinate space to a normalized space where the top left of the viewport region maps to (0,0) and the bottom right maps to (1, 1). For example, for the values x=200,y=150, span=10, then SVG canvas coordinate (190, 140) transforms to normalized coordinate (0, 0) and canvas coordinate (210, 160) transforms to (1, 1).

Once you have correctly implemented set_viewbox(), your solution will respond to mouse controls in the same way as the reference implementation.

Task 5: Drawing Scaled Images

This part of the assignment requires knowledge of concepts in Lecture 5.

In this task, you will implement rasterize_image() in software_renderer.cpp.

To keep things very simple, we are going to constrain this problem to rasterizing image elements that are positioned on the SVG canvas via translations and scaling, but not rotations. Therefore, rasterize_image() should render the specified image into an axis-aligned rectangle on screen whose top-level coordinate is (x0, y0) and whose bottom-right coordinate is (x1, y1). Your implementation should adhere to the following specification:

When you are done, you should be able to draw basic/test7.svg.

Task 6: Anti-Aliasing Image Elements Using Trilinear Filtering

This part of the assignment requires knowledge of concepts in Lecture 5.

In this task you will improve your anti-aliasing of image elements by adding trilinear filtering. This will involve generating mipmaps for image elements at SVG load time and then modifying your sampling code from Task 5 to implement trilinear filtering using the mipmap. Your implementation is only required to work for images that have power-of-two dimensions in each direction.

At this point, zooming in and out of your image should produce nicely filtered results!

Task 7: Alpha Compositing

Up until this point your renderer was not able to properly draw semi-transparent elements. Therefore, your last programming task in this assignment is to modify your code to implement Simple Alpha Blending in the SVG specification.

While the application will always clear the render target buffer to the canvas color at the beginning of a frame to opaque white ((255,255,255,255) in RGBA) before drawing any SVG element, your transparency implementation should make no assumptions about the state of the target at the beginning of a frame.

When you are done, you should be able to correctly draw the tests in /alpha.

Task 8: Draw Something!!!

Now that you have implemented a few basic features of the SVG format, it is time to get creative and draw something! You can create an SVG file in popular design tools like Adobe Illustrator or Inkscape and export SVG files. However, be aware that our starter code and your renderer implementation only support a subset of the features defined in the SVG specification, and these applications may not always encode shapes with the primitives we support. (You may need to convert complicated paths to the basic primitives in these tools.) Also, it is not very hard to write SVG files directly since they are just XML files.

Going Further: Tasks that May Potentially Win You Extra Credit:

Implement More Advanced Shapes

We have provided you with a couple of examples of subdividing complex, smooth complex shapes into much simpler triangles in /subdiv. Subdivision is something you will dig into in great detail in the next assignment. You can see subdivision in action as you step though the test files we provided.

In addition to what you have implemented already, the SVG Basic Shapes also include circles and ellipses. We may support these features by converting them to triangulated polygons. But if we zoom in on the edges, there will be a point at which the approximation breaks down and the image no longer will look like a smooth curve. Triangulating more finely can be costly as a large number of triangles may be necessary to get a good approximation. Is there a better way to sample these shapes? For example, implement drawEllipse in drawsvg.cpp

Improving Performance

Achieving high performance is critical in many graphics applications. The staff is very interested in who can generate the fastest renderer in the class! Using multi-core or SIMD parallelism is absolutely fair game.

Grading

Your code must run on the GHC 5xxxx cluster machines as we will grade on those machines. Do not wait until the submission deadline to test your code on the cluster machines. Keep in mind that there is no perfect way to run on arbitrary platforms. If you experience trouble building on your computer, while the staff may be able to help, but the GHC 5xxx machines will always work and we recommend you work on them.

Each task will be graded on the basis of correctness. You are not expected to completely reproduce the reference solution pixel-by-pixel as slight differences in implementation strategy or even the order of floating point arithmetic will causes differences, but your solution should not be very far off. (While we provide a diff view in the application to help you debug, we will mostly be using it as a reference when we grade your code.) If you have any questions about whether your implementation is "sufficiently correct", just ask.

The assignment consists of a total of 100 pts. The point breakdown is as follows:

Handin Instructions

Your handin directory is on AFS under:

/afs/cs/academic/class/15462-s16-users/ANDREWID/asst1/ 
or 
/afs/cs/academic/class/15662-s16-users/ANDREWID/asst1/

Note that you may need to create the asst1 directory yourself. All your files should be placed there. Please make sure you have a directory and are able to write to it well before the deadline; we are not responsible if you wait until 10 minutes before the deadline and run into trouble. Also, you may need to run aklog cs.cmu.edu after you login in order to read from/write to your submission directory.

You should submit all files needed to build your project, this include:

Please do not include:

You should include a README file (plaintext or pdf) if you have implemented any of the extra credit features. In your REAME file, clearly indicate which extra credit features you have implemented. You should also briefly state anything that you think the grader should be aware of.

Do not add levels of indirection when submitting. And please use the same arrangement as the handout. We will enter your handin directory, and run:

cd build && rm -rf * && cmake ../src && make

and your code should build correctly. The code must compile and run on the GHC 5xxx cluster machines. Be sure to check to make sure you submit all files and that your code builds correctly.

Friendly Advice from your TAs

Resources and Notes