CS 184: Computer Graphics and Imaging, Spring 2017
Oliver O'Donnell, CS184-agh
Graphics concepts are fascinating! The project brought together many different math concepts (mostly linear algebra) to answer questions like "how do you map a texture to a surface?" and "how do video games efficiently render textures that are far away?". For this project, I dipped my toe into a very large (and at times, confusing) codebase and was able to fill in skeleton code to do very cool things. It gives me real appreciation for those who developed the first graphics engines without prior code.
A triangle is defined by 3 points in the x-y plane and by the color(s) inside it. Given a triangle defined in that way, my task was to go through and draw those colors onto the appropriate pixels in the
samplebuffer. Note: The
samplebuffer is a 2-d array containing the color values for each pixel or sub-pixel on the canvas.
Iterating through all x-y values and then checking whether those values fell inside the triangle would have worked, but would have been inefficient. Therefore I only iterated through the subset of x-y values inside the triangle's bounding box. (shown below, figure from Sunshine2k.com)
I used the edge vectors of the triangle to test whether an (x, y) point was inside or outside of it.
We can find out whether a point is to the left or right of, or exactly on one of the sides of the triangle by projecting it onto the norm of that side. We do this for each edge, and if the sign matches for all three, then the point is inside the triangle.
Finally, if the point (x,y) is inside the triangle we place the relevant color into
samplebuffer[x][y] using the method
Here is a png screenshot of basic/test4.svg with the default viewing parameters and with the pixel inspector centered on an interesting part of the scene.
I implemented supersampling by further subdividing my for-loop from part 1.
I modified the rasterization pipeline in two places:
sample_ratesub-pixels inside (x,y). The only change for this step was to iterate through sub-pixels for every (x,y) location. I achieved this by nesting another for-loop inside the for-loop that iterates through every (x,y) pair.
SampleBuffer::get_pixel_colorretrieved colors. It now had to take the average the color of all sub-pixels (but not the alpha, as I learned the hard way!).
I used supersampling to antialias my triangles by taking the average of 4, 9, 16, or more samples rather than just the center of the screen pixel.
Here are screenshots of basic/test4.svg with the default viewing parameters and sample rates 1, 4, and 16 to compare them side-by-side.
I have created an updated version of
svg/transforms/robot.svg with cubeman doing something more interesting:
#003262and California Gold:
Barycentric coordinates describe the location of a point in relation to a triangle's three points. Usually the location of the three points are denoted by
C. So we can say
(x,y) = uA + vX + wC. Using this coodinate system makes interpolating values much more straightforward as you can just do a weighted sum. For example, given three colors corresponding to A, B, and C respectively, we can say that the point
u*A redness and
Pixel sampling can be applied to the texture plane rather intuitively. Given a triangle in (u,v) coordinates, and a texture in (u, v) coordinates, you can still retrieve a color for your given (x,y) coordinates. You simply convert to barycentric coordinates as before, and see what values of (u,v) you end up with. The challenge comes in deciding which pixel, say (55.2758, 88.412), corresponds to.
Here is an image for which bilinear sampling clearly defeats nearest sampling. From top-left to bottom left, the images are:
The differences are that lower sampling rates create more "jaggies" and other frequency-related distortions, and that bilinear sampling can further mitigate frequency-related distortions, at the risk of undesired blurriness.
There will be a large difference between nearest-pixel and bilinear sample when "jaggies" and other frequency-related distortions are most prominent. By averaging between 4 pixels, bilinear sampling avoids missing out on data where the texture is a higher frequency than the sample rate. Of course, the only true way to miss out on no data would be for your texture frequency to exactly match what your screen's pixels can show.
Level sampling involves sampling from mipmap levels rather than the original texture. The point is to use appropriately-sized versions of the same texture in order to save computation and to avoid frequency-related distortions.
I implemented it by seeing how far away (x+1,y) and (x, y+1) end up being in the texture plane. A larger maximum distance corresponds to a higher (smaller and more blurry) mipmap level. Then that mipmap level is passed to the functions for pixel interpolation, rather than the full-scale texture.
But the output of the
get_level function is usually in between two levels. So you can either round to the nearest level, or in the case of bilinear level sampling, calculate the color from both levels and take the linearly interpolated average.
I have applied my code to a custom png. From top-left to bottom left, the images are:
The tradeoffs are as follows:
There is nothing like creating something practical to cement your understanding of concepts. Now that I have finished project 1, I feel that I have a much deeper understanding of the graphics pipeline and of efficiency issues in C++ and graphics code in general.