$29
Assignment 1: Rasterizer Solution
In this assignment you will implement a simple rasterizer, including features like supersampling, hierarchical transforms, and texture mapping with antialiasing. At the end, you'll have a functional vector graphics renderer that can take in modified SVG (Scalable Vector Graphics) files, which are widely used on the internet.
Logistics
Deadline
First 3 parts are due on Monday, September 23rd at 11:55pm.
Entire Assignment 1 is due on Monday, September 30th at 11:55pm.
Assignments which are turned in after 11:55pm are a full day late -- there are no late minutes or late hours.
Getting started
You can either download the zipped assignment straight to your computer or clone it from GitHub using the command
https://md2pdf.netlify.com 1/26
9/22/2019 md2pdf - Markdown to PDF
git clone git@github.com:mabdullah13/CG-PA1
Building the assignment
We will be using CMake to build the assignments. If you don't have CMake (version >= 2.8) on your personal computer, you can install it using apt-get on Linux or Macports/Homebrew on OS X. Alternatively, you can download it directly from the CMake website.
To build the code, start in the folder that GitHub made or that was created when you unzipped the download. Run
mkdir build
to create a build directory, followed by
cd build
to enter the build directory. Then
cmake ..
to have CMake generate the appropriate Makefiles for your system, then
make
to make the executable, which will be deposited in the build directory.
Don't forget to run make every time you make changes to your files.
What you will turn in
You will need to zip your src folder (located in your main directory) and submit it on LMS.
Using the GUI
You can run the executable with the command
./draw ../svg/basic/test1.svg
After finishing Part 3, you will be able to change the viewpoint by dragging your mouse to pan around or scrolling to zoom in and out. Here are all the keyboard shortcuts available (some depend on you
https://md2pdf.netlify.com 2/26
9/22/2019
md2pdf - Markdown to PDF
implementing various parts of the assignment):
Key
Action
' '
return to original viewpoint
'-'
decrease sample rate
'='
increase sample rate
'Z'
toggle the pixel inspector
'P'
switch between texture filtering methods on pixels
'L'
toggle scanLine
'S'
save a png screenshot in the current directory
'1'-'9'
switch between svg files in the loaded directory
The argument passed to draw can either be a single file or a directory containing multiple svg files, as in
./draw ../svg/basic/
If you load a directory with up to 9 files, you can switch between them using the number keys 1-9 on your keyboard.
Project structure
Section I: Rasterization
Part 1: Rasterizing single-color triangles
Part 2: Antialiasing triangles
Part 3: Transforms
Section II: Sampling
Part 4: Barycentric coordinates
Part 5: "Pixel sampling" for texture mapping
Section III: Scan Line
Part 6: Scan Line
There is a fair amount of code in the CGL library, which we will be using for future assignments. The relevant header files for this assignment are vector2D.h, matrix3x3.h, color.h, and renderer.h.
https://md2pdf.netlify.com 3/26
9/22/2019 md2pdf - Markdown to PDF
Here is a very brief sketch of what happens when you launch draw : An SVGParser (in svgparser.*) reads in the input svg file(s), launches a OpenGL Viewer containing a DrawRend renderer, which enters an infinite loop and waits for input from the mouse and keyboard. DrawRend (drawrend.*) contains various callback functions hooked up to these events, but its main job happens inside the DrawRend::redraw() function. The high-level drawing work is done by the various SVGElement child classes (svg.*), which then pass their low-level point, line, and triangle rasterization data back to the three DrawRend rasterization functions.
Here are the files you will be modifying throughout the project:
1. drawrend.cpp
2. texture.cpp
3. transforms.cpp
4. svg.cpp
In addition to modifying these, you will need to reference some of the other source and header files as you work through the project.
Section I: Rasterization
Part 1: Rasterizing single-color triangles
Triangle rasterization is a core function in the graphics pipeline to convert input triangles into framebuffer pixel values. In Part 1, you will implement triangle rasterization using the methods
discussed in lecture 2 to fill in the function in drawrend.cpp.
Notes:
It is recommended that you implement SampleBuffer::fill_color() function first, so that you can see rasterized points and lines for some SVGs.
Remember to do point-in-triangle tests with the point exactly at the center of the pixel, not the corner. Your coordinates should be equal to some integer point plus (.5,.5).
For now, ignore the Triangle *tri input argument to the function. We will come back to this in Part 4.
You are encouraged but not required to implement the edge rules for samples lying exactly on an edge.
Make sure the performance of your algorithm is no worse than one that checks each sample within the bounding box of the triangle.
When finished, you should be able to render many more test files, including those with rectangles and polygons, since we have provided the code to break these up into triangles for you. In particular, basic/test3.svg, basic/test4.svg, and basic/test5.svg should all render correctly.
For convenience, here is a list of functions you will need to modify:
https://md2pdf.netlify.com 4/26
9/22/2019 md2pdf - Markdown to PDF
1. SampleBuffer::fill_color located in src/drawrend.h
2. DrawRend::rasterize_triangle located in src/drawrend.cpp
Extra Credit: Make your triangle rasterizer super fast (e.g., by factoring redundant arithmetic operations out of loops, minimizing memory access, and not checking every sample in the bounding box). Write about the optimizations you used.
Execute following command in build directory. Cycle through different SVG files by pressing 1-9.
./draw ../svg/basic/
Once you have implemented SampleBuffer::fill_color(), you will be able to render the following
SVGs:
https://md2pdf.netlify.com 5/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 6/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 7/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 8/26
9/22/2019 md2pdf - Markdown to PDF
After implementing DrawRend::rasterize_triangle:
https://md2pdf.netlify.com 9/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 10/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 11/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 12/26
9/22/2019 md2pdf - Markdown to PDF
If you encounter some partially filled stars or a disconnected circle, then there was something wrong with your implementation, consider fixing it before submission.
https://md2pdf.netlify.com 13/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 14/26
9/22/2019 md2pdf - Markdown to PDF
Part 2: Antialiasing triangles
Use supersampling to antialias your triangles. The sample_rate parameter in DrawRend (adjusted using the - and = keys) tells you how many samples to use per pixel.
The image below shows how sampling four times per pixel produces a better result than just sampling once, since some of the supersampled pixels are partially covered and will yield a smoother edge.
To do supersampling, each pixel is now divided into sqrt(sample_rate) * sqrt(sample_rate) sub-pixels. In other words, you still need to keep track of height * width pixels, but now each pixel has sqrt(sample_rate) * sqrt(sample_rate) sampled colors. You will need to do point-in-triangle tests at the center of each of these sub-pixel squares.
We provide a SampleBuffer class to store the sub-pixels. Each samplebuffer instance stores one pixel. Your task is to fill every sub-pixel with its correctly sampled color for every samplebuffer, and average all sub-pixels' colors within a samplebuffer to get a pixel's color. Since you've finished Part 1,
you can use function to write color to a sub-pixel.
Your triangle edges should be noticeably smoother when using > 1 sample per pixel! You can examine the differences closely using the pixel inspector. Also note that, it may take several seconds to switch to a higher sampling rate.
For convenience, here is a list of functions you will need to modify:
https://md2pdf.netlify.com 15/26
9/22/2019 md2pdf - Markdown to PDF
1. DrawRend::rasterize_triangle
2. SampleBuffer::get_pixel_color
Extra Credit: Implement an alternative sampling pattern, such as jittered or low-discrepancy sampling.
Adjust your samples per pixel by using the - and = keys.
https://md2pdf.netlify.com 16/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 17/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 18/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 19/26
9/22/2019 md2pdf - Markdown to PDF
Part 3: Transforms
Implement the three transforms in the transforms.cpp file according to the SVG spec. The matrices are 3x3 because they operate in homogeneous coordinates -- you can see how they will be used on instances of Vector2D by looking at the way the * operator is overloaded in the same file.
For convenience, here is a list of functions you will need to modify:
1. translate
2. scale
3. rotate
located in src/transforms.cpp
Once you've implemented these transforms, svg/transforms/robot.svg should render correctly, as follows:
Section II: Sampling
Part 4: Barycentric coordinates
https://md2pdf.netlify.com 20/26
9/22/2019 md2pdf - Markdown to PDF
Familiarize yourself with the ColorTri struct in svg.h. Modify your implementation of
DrawRend::rasterize_triangle(...) so that if a non-NULL Triangle *tri pointer is passed in, it computes barycentric coordinates of each sample hit and passes them to tri->color(...) to request the appropriate color.
Implement the ColorTri::color(...) function in svg.cpp so that it interpolates the color at the point p_bary . p0_col , p1_col , p2_col represent colors at points p0 , p1 , p2 , respectively, use them to calculate color at point p0 using p_bary and return it.
You may use Vector2D and vector3D datastructures to make calculations easier, a few have been declared for you.
For convenience, here is a list of functions you will need to modify:
1. DrawRend::rasterize_triangle located in src/drawrend.cpp
2. ColorTri::color located in src/svg.cpp
After implementing this part, instead of a black circle, you will be able to view the colour wheel:
./draw ../svg/basic/test7.svg
https://md2pdf.netlify.com 21/26
9/22/2019 md2pdf - Markdown to PDF
Part 5: "Pixel sampling" for texture mapping
Familiarize yourself with the TexTri struct in svg.h. This is the primitive that implements texture mapping. For each vertex, you are given corresponding uv coordinates that index into the Texture pointed to by *tex .
To implement texture mapping, DrawRend::rasterize_triangle , you should fill in the psm member of a SampleParams struct and pass it to tri->color(...) . Then TexTri::color(...) should fill in the correct uv coordinates in the SampleParams struct, and pass it on to tex->sample(...) . Then
should examine the SampleParams to determine the correct sampling
The GUI toggles DrawRend 's PixelSampleMethod variable psm using the 'P' key, Use it to alternate between sample_nearest and sample_bilinear
For convenience, here is a list of functions you will need to modify:
1. DrawRend::rasterize_triangle located in src/drawrend.cpp
2. TexTri::color located in src/svg.cpp
3. Texture::sample located in src/texture.cpp
4. Texture::sample_nearest located in src/texture.cpp
5. Texture::sample_bilinear located in src/texture.cpp
Execute following command in build directory. Cycle through different texmap files by pressing 1-6.
./draw ../svg/texmap/
https://md2pdf.netlify.com 22/26
9/22/2019 md2pdf - Markdown to PDF
https://md2pdf.netlify.com 23/26
9/22/2019 md2pdf - Markdown to PDF
Section III: Scan Line
Part 6: Implement Scan Line
Scan Line is an effecient algorithm to determine if a point lies within a polygon. Hence, in comparison to our implementation in part 1, it should be less sluggish.
For convenience, here is what you will need to modify:
In src/drawrend.cpp, at the end of DrawRend::rasterize_triangle add this code:
cout<<"Scanline"<<endl; //To check if its works Coord vert[3];
float y[] = {y0,y1,y2,y0};
float x[] = {x0,x1,x2,x0};
//TRIANGLE
for( int i=0; i<3; i++){
vert[i].yMax = max(y[i],y[i+1]);
vert[i].yMin = min(y[i],y[i+1]);
if(min(y[i],y[i+1])==y[i]){
vert[i].xMin = x[i];
vert[i].xMax = x[i+1];
}
else{
vert[i].xMin = x[i+1];
vert[i].xMax = x[i];
}
• e0.invSlope = (e0.xMax-e0.xMin)/(e0.yMax-e0.yMin); vert[i].invSlope = (x[i+1]-x[i])/(y[i+1]-y[i]);
}
scanLine(vert,3, color);
In src/drawrend.cpp, in the fucntion DrawRend::rasterize_scanline erase what's already written (including function declaration) and add this code:
(This is the function where you have to use your thinking and fill in the missing parts)
void DrawRend::scanLine(Coord *verticess, int nVertices, Color c){ std::vector<Coord> ET,AET;
• You code start here /////////////
int ymin = verticess[0].yMin; int ymax = verticess[0].yMax;
//Populate Edge Table
for (int i = 0; i < nVertices; ++i){
//INSERT CODE HERE
}
https://md2pdf.netlify.com 24/26
9/22/2019 md2pdf - Markdown to PDF
int i,j;
BubbleSort(ET,0);
//For each scanline Update ET and AET
for (int y = ymin; y<=ymax; ++y){
i = ET.size()-1;
while(i >= 0){
//insert records in AET
//INSERT CODE HERE
}
BubbleSort(AET,1);
if(AET.size() > 1){
for (j = 1; j < AET.size(); j=j+2){
rasterize_line(AET[j-1].x,AET[j-1].y,AET[j].x,AET[j].y,c);
}
j = AET.size()-1;
while (j >= 0){
//update AET
//INSERT CODE HERE
}
}
}
// You code end here /////////////
}
In src/drawrend.cpp, add this function after DrawRend::rasterize_triangle:
void DrawRend::BubbleSort(vector<Coord> &arr,bool set){ if (arr.size() < 2)
return;
int i, j, flag = 1;
Coord temp;
int len = arr.size();
if (!set) //sort w.r.t y
for(i = 1; (i < len) && flag; i++){
flag = 0;
for (j=0; j < (len -1); j++){
if (arr[j].yMin < arr[j+1].yMin){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = 1;
}
else if (arr[j].yMin == arr[j+1].yMin){
if (arr[j].yMax < arr[j+1].yMax){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = 1;
}
}
https://md2pdf.netlify.com 25/26
9/22/2019 md2pdf - Markdown to PDF
}
}
else //sort w.r.t x
for(i = 1; (i < len) && flag; i++){
flag = 0;
for (j=0; j < (len -1); j++){
if (arr[j].x > arr[j+1].x){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = 1;
}
}
}
}
In src/drawrend.h, add this declaration:
void BubbleSort(vector<Coord> &arr,bool set);
To check whether your implementation is correct or not, comment out the code you've added in parts 5 and 6 (in src/drawrend.cpp), add then run the same command as for part 1:
./draw ../svg/basic/
This assignment is adapted from UC Berkeley CS184 (https://cs184.eecs.berkeley.edu/article/3).
https://md2pdf.netlify.com 26/26
