Tag Archives: graphics

COMP 770 Program 4: 3D Rasterizer

Download the source (c++ w/ XCode project): Program4.tar.gz
Download the binary (Intel Mac OS X): rasterizer.gz

I know this is a naive thing to say type, but after finishing this program I kind of feel like I just implemented OpenGL minus shaders. :) My approach was to get the scene parsing implemented first and then to get the GL Preview feature working. This allowed me to very quickly setup my light and camera and then to see my goal. Then I started in on my raster pipeline.

Features

Here’s a quick list of the features for my Raster Pipeline:

  • Moveable camera
  • Moveable light
  • Orthographic Projection
  • Perspective Projection
  • Per-Vertex Color
  • Wireframe
  • Flat Shading
  • Gouraud Shading
  • Phong Shading
  • Use full Phong lighting with light intensity falloff
  • Configurable (on/off) backface culling
  • Configurable (on/off) cheap clipping
  • Efficient span-based triangle fill
  • z-buffer with epsilon for z-fighing resolution
  • Timing instrumentation
  • PNG output

And here are the features support in the OpenGL Preview mode:

  • Moveable camera
  • Moveable light
  • Orthographic Projection
  • Perspective Projection
  • Per-Vertex Color
  • Wireframe
  • Flat Shading
  • Smooth (Gouraud?) Shading

Shading

After doing two raytracing assignments, I really doubted that rasterizing would hold a candle in terms of aesthetics. I was stunned when I saw how good the OpenGL preview looked, so I really wanted to dive into shading. I ended up implementing wireframes, flat shading, Gouraud shading and Phong shading.

Challenges

I then started in on my own raster pipeline. As I stumbled through a myriad of problems with my transformations. In particular, the projection transformations were troublesome. I tried to implement them in a way similar to the class notes, but I was getting the results that I was looking for…or any results. I kept segfaulting. I turned to the text, and found that they did a great job explaining both orthographic and projection transformations.

Clamping and normals were also a problem for me. Interestingly enough, once you fix one clamping or normal bug, you tend to clamp and normalize everything. The clamping problem was worst with my color calculations. Specular highlights produce some very illuminated pixels. I ended up bleeding past 1.0 on several of the channels which caused several rainbow effects. Additionally, when I was calculating barycentric coordinate, floating pointer errors led to scenarios where the coordinates were being returned beyond [0.0,1.0]. Normally this would mean that the point was off of the triangle, but I was attempting to calculate for pixels that were known to be on the triangle.

Normals were by far the most difficult problem. At least it was the toughest one I had to solve. My specular highlights were causing a grid pattern along the edges of triangles. I fought it for two days. My problem resulted from normals interpolated between to vertices on the edges. The were not unit length, and so they increased the effect of the specular highlights when I calculated the dot product with the half viewing vector. Normalizing these fixed the problem.

Optimizations

Backface culling was a really straight-forward optimization to make. To implement it, I added a check right before the viewing and projection transformations. The check involved computing the dot product of each of the normals with the viewing vector. If none of those normals were visible, then the entire triangle is back facing and was culled. It yielded a significant speedup on Andrew’s dragon model.

rasterizer –projection persp -0.1 0.1 -0.0 0.2 3.0 7.0 –camera 0 0 5 0 1 0 –light 0.1 0.1 0.1 –nocull scenes/dragon.txt
Render scene: 1287.702000 ms

versus

rasterizer –projection persp -0.1 0.1 -0.0 0.2 3.0 7.0 –camera 0 0 5 0 1 0 –light 0.1 0.1 0.1 scenes/dragon.txt
Render scene: 708.403000 ms

I really wanted to implement full clipping, but I found out that “cheap clipping” is pretty effective by itself. The first step is to add a check if a pixel is in the viewport before calculating the color for it. Calculating color is pretty expensive, so this eliminated a lot of cost. Then next step was to use Cohen-Sutherland clipping to determine when a line or triangle was completely outside of the viewport. I didn’t do a thorough test either. I did the simple bit-wise and operation on the bit codes for each point and rejected the triangle if it was not zero. This means that some of the corner cases were missed.

By cheating like this, I was able to avoid a lot of triangles without having to implement the clipping of individual triangles into separate polygons. This meant that I was still rasterizing parts of triangle that were outside of the viewport, but at least with my check above I wasn’t calculating the color for them. The results were rather satisfactory, especially compared to the cost of implementing it.

rasterizer –camera 0 0 5 0 1 0 –projection persp -0.1 0.1 -0.1 0.1 3.0 7.0 //zoom_in –noclip scenes/beethoven.txt
Render scene: 414.369000 ms

was reduced to

rasterizer –camera 0 0 5 0 1 0 –projection persp -0.1 0.1 -0.1 0.1 3.0 7.0 //zoom_in –output img/beethven_clipped.png scenes/beethoven.txt
Render scene: 310.444000 ms

Although a span-based triangle fill was pointed out as an opportunity for extra credit, it was really the most straightforward way to implement this for triangles, since they’re convex. At one point in my career, I did a lot of 2D raster graphics work for J2ME cellphones. Most of our displays were optimized to send data to the display in rows. So I attacked this problem the same way. I found the top most pixel. I then started drawing each leg using the midpoint line algorithm. Each time I placed a pixel which changed y, I added it to an edge list. When I reached the end of a leg, I switched to the third segment…unless that leg was already horizontal. I then went back and drew horizontal lines from one edge map to the other. Since this was the only triangle fill algorithm I used, I didn’t get any timing numbers for comparison.

The use of a Z-Buffer to determine the rendering order is so genius in its simplicity, that I didn’t even consider any other ways to implement it. So this is another scenario where I didn’t try to implement another method for comparison. However, I was able to throw in a small improvement that resolve the z-fighting example that I threw at it. When determining when to paint over another pixel, I checked that the new pixel was closer to the camera by a margin, epsilon. I set epsilon to 0.000001. It resolve my test model without causing any visible changes to the other models. My testing certainly wasn’t extensive, and so I’m sure that it would fail on scenarios where a camera with a very narrow FOV caused massive magnification. Perhaps in that situation, I could use a dynamic epsilon that is calculated based on the camera’s FOV.

Remaining Images

Here are the remaining rendering of the models provided, including Andrew’s dragon model from the Stanford 3D Scan Repository.

COMP 770 Program 1: Image Processing

Download Entire Project: Image_cpp.tar.gz
Download image.cpp only: image.cpp.tar.gz
Download extra sample image results: lena.tar.gz

Overview

This assignment was a blast. It basically required us to implement just about every worthwhile image processing filter out there. Here’s a quick list of them:

  • Brighten
  • Add Random Noise
  • Crop
  • Extract Channel
  • Adjust Contrast
  • Sharpen
  • Blur
  • Quantize
  • Dither (Random, Ordered, Floyd-Steinberg)
  • Scale
  • Rotate
  • Fun (Swirl)
  • Nonphotorealism (Toon/Comic Shading)

A skeleton of the project was provided with helpful WBMP code as well as classes for Image and Pixel. The Image::Image (const Image& src) was busted, but other than that everything worked perfectly. For reference, here’s my modifications to the copy contructor:

Image::Image (const Image& src)
{
  
  bmpImg = new BMP();
	
  width           = src.width;
  height          = src.height;
  num_pixels      = width * height;
  sampling_method = src.sampling_method;
  
  if (!bmpImg->SetSize(width, height)){
    printf("Error allocating image.");
    exit(-1);
  }
	
  pixels = new Pixel[num_pixels];
  memcpy(pixels, src.pixels, num_pixels * sizeof(Pixel));

  assert(pixels != NULL);
}

Getting The Code

The various image filters were implemented as methods of the Image class and can be viewed in the image.cpp file. Further details of the implementation are explained in the comments.

Download Entire Project: Image_cpp.tar.gz
Download image.cpp only: image.cpp.tar.gz

Building

The project should build on any system with c++ compiler, stdlibc++ library, and make. I did my development on Linux and Mac OSX. I don’t anticipate any problems building in windows, but please let me know if it does.

Untar the project it in a convenient directory and run make to build:

$ tar -xzf Image_cpp.tar.gz
$ cd Image_cpp
$ make

The debug and clean targets work as well:

$ make debug
$ make clean

Run the program with no parameters to get usage:

$ objdir-release/image
Usage: image -input  [-option [arg ...] ...] -output 
-help
-input 
-output 
-noise 
-brightness 
-contrast 
-saturation 
-crop    
-extractChannel 
-quantize 
-randomDither 
-blur 
-sharpen 
-edgeDetect
-orderedDither 
-FloydSteinbergDither 
-scale  
-rotate 
-fun
-sampling 
-toon

Sample Images
The following are screen shots of the results of the various image processing filters. The command lines that were used are displayed as captions beneath the images. You can read more details about how they work after the gallery.

Noise, Brightness, Contrast, Saturation
This group of image filters all use interpolation at their core. Specifically:

  • Noise – Interpolation with an image of random noise
  • Brightness – Interpolation with a black image
  • Contrast – Interpolation with constant gray image with luminance equal to the average luminance of the source image
  • Saturation – Interpolation with a grayscale version of the source image

Crop

Cropping is a simple blit of the specified pixel region no a new image with the region’s dimensions.

Extract Channel

The specified channel was extracted by setting the other channels to zero for each pixel in the source image.

Quantize, Random Dither, Ordered Dither, Floyd-Steinberg Dither

This groups of image filters reduces the bits per channel to the number specified by the input parameter. The Quantize algoritm is the simplest, as it just reduces each channel of each pixel. This produces dramatic Intensity Quantization errors.

Random Dithering breaks up the color boundaries in the image by adding noise to the source image first. It isn’t simply added though; instead the source image is interpolated with a random noise image. When the resulting image is Quantized the color boundaries look dramatically better, but the introduced noise negatively affects the image quality.

Ordered Dithering improves the color boundaries by moving the rounding errors when choosing one pixel over the next. Instead of simply rounding, the most significant of the dropped bits is compared to a value in a bayer matrix chosen based on the pixel’s coordinates. The pixel’s color is rounded up or down if the error is greater or lesser than that error. More details can be found in this Wikipedia article. This produces visual quality much higher than random dithering, but a noticeable repeating pattern emerges in the image based on the size of the matrix used.

Floyd-Steinberg Dithering deals with the rounding errors differently. Portions of the error are distributed, through additions/subtractions, to the pixels around the pixel being rounded. The resulting images shows dithering quality better than ordered dithering without any repeating patterns.

Scale, Rotate, and Fun (Swirl)

These image processing filters use transformation to move the pixels from the source image to new coordinates in the destination image. Instead of using calculations that transform the source pixels to the destination pixels, the reverse calculations are used. This is particularly important when scaling to a larger dimension, for instance.

The calculations in these reverse transformations often result in real numbers instead of discrete coordinates in the source image. Therefore the image needs to be resampled in order to approximate what the value should be at the given real coordinates. Point Sampling finds the nearest pixel and uses that value. It produces heavily aliasing in the destination image. Bilinear Sampling interpolates between the four nearest pixels based on the the real coordinates distance from those pixels. Gaussian Sampling uses a gaussian filter, producing a mild blurring effect that can be controlled with the right radius.

Blur/ Sharpen

Blur uses a Gaussian filter. I implemented it using a one-dimensional kernel, taking advantage of the separability of the Gaussian filter. The size of the kernel is passed as the parameter on the command line. The size is radius * 2 of the Gaussian curve used to generate the real values in the kernel. I calculated the optimal standard deviation for the equation so that the blurring effect would grow as the radius grew.

Sharpening removes the blurriness of a source image by extrapolating the source image from a blurred version of the same image.

Edge Detect

Edge Detect works similar to the Gaussian filter, but it uses a specific edge detection kernel. I implemented it with a two-dimensional kernel because I wasn’t sure if it was separable and it wasn’t too costly to implement due to the small size of the kernel (3×3).

Toon

Perhaps inspired by all of those “Comic book” yourself applications out there, I attempted to create a “Toon” filter. I built upon the image filters created already and added an alpha blender. I started the process by creating the “color layer”. First the image was saturated and brightened a little. Then it was quantized.

The “ink layer” is built by edge detecting the color layer and then desaturating completely. Then each pixel of the ink layer is analyzed. If its near white, then it is made completely white (for debugging) and completely transparent. The other pixels make up the ink, and so they are made completely black and opaque.

Finally the ink layer is composited over the color layer and the results is blurred a little for effect.