Tag Archives: 3d

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 2: Ray Tracing Part 1

Download Project Source/Scenes/Mac-Binaries: Program2.tar.gz

Overview

I’ve read about ray tracing a few times in the past, but this assignment gave me a dramatically new perspective on the topic. Two things really struck me about ray tracing. First, what I understood to be ray tracing was actually just ray casting. I didn’t know this while I was implementing the diffuse shaders (pure Lambertian, Blinn-Phong, and Blinn-Phong with Ambience), and so I was rather impressed with the results. However, as soon as I implemented specular reflection via recursion, I started to realize that ray tracing is indeed a much more significant step over ray casting in terms of realism.

My second dramatic realization was just how expensive ray tracing is. Every feature that I added would drive my render times up. And this was compounded by framebuffer resolution, sampling grid size, number of lights, and number of scene primitives. I found myself switching between implementing new features and then going back and implementing various optimizations just to make the render times tolerable.

Features

For part one of this ray tracer program, I used the COMP 575 assignment as a guideline on features to add beyond the minimum in the COMP 770 assignment. I kept going, adding feature after feature, unaware of whether or not these “extra features” would actually be required for the second part of the assignment or not.

Basic

  • Resizable View Rect Dimensions
  • Fully Configurable Camera (position, rotate, FOV)
  • Multiple, Colored Light Support
  • Configurable Background Color
  • Output to PNG
  • Supports both Ray Casting and Ray Tracing
  • Specular Reflection
  • Dielectric Reflection and Transmission w/ Refraction

Shaders

  • Lambertian
  • Blinn-Phong
  • Blinn-Phong with Ambient

Super Sampling

  • Configurable Sample Count for Regular, Jittered, and Adaptive
  • Basic
  • Regular
  • Jittered

Optimizations

  • Multi-Processing Support with OpenMP
  • Simplified Scene Intersection Calculations with Normalized Direction Vectors
  • Tracks recursive contribution of color calculations for early recursion termination
  • Adaptive [Jittered] Sampling

Miscellaneous

  • Timing Instrumentation
  • Can build without OpenGL, OpenMP, and libpng for benchmarking on embedded systems

Building and Usage

I’ve provided a Makefile with the following targets. It has been tested on Mac OSX, Linux (Ubuntu) and Android for ARM.

NOTICE: By default, I build on a system with OpenGL, OpenMP (libgomp), and libpng. If you don’t have those on your system, then use the NO_GL=1, NO_OMP=1, and NO_PNG=1 settings when running make.

Build Targets/Options

  • make – Builds release.
  • make debug – Builds debug.
  • make clean – Cleans src directory and removes objdir directories.
  • make NO_OMP=1 – Won’t attempt to compile using OpenMP. Handy if the system doesn’t have support. Can be used with other NO_*.
  • make NO_PNG=1 – Won’t attempt to compile using libpng. Handy if the system doesn’t have support. Can be used with other NO_*.
  • make NO_GL=1 – Won’t attempt to compile using OpenGL. Handy if the system doesn’t have support. Can be used with other NO_*.

Usage

Usage: raytracer [-shader ] [-sampling ] [-samples ] [-background <0xRRGGBBAA>] [-window  ] [-timing] [-noparallel] [-norecursion] [-nodisplay] [-output ] 

  -shader 
       Sets the shader used. Each one builds upon the previous shader. Default = reflective
  -sampling 
       Chooses which sampling method to use. Default = adaptive
  -samples 
       Specifies n x n grid of samples to collect. Ignored for basic sampling. Default = 5
  -background <0xRRGGBBAA>
       Sets the background color. Default = 0x000000ff
  -window  
       Sets the window size to the specified width and height. Default = 500 x 500
  -timing
       This switch turns on timing output on the console. Default = off
  -noparallel
       This switch turns off multiprocessing. Default = on
  -norecursion
       This switch turns off recursive ray tracing resulting in simple ray casting. Default = on
  -nodisplay
       This switch turns the output to the display. Default = on
  -output 
       This switch causes the ray tracer to output a png image of the renderer scene.

Image Results

spheres3.xml

Once I started working on support for dielectrics, I wanted to create a reasonably familiar scene so that I could interpret the results better. I placed a large, mostly transparent, smoke-gray sphere in front of the camera. The ground sphere is still somewhat reflective, but the two colored spheres in the background are non-reflective. When viewing this scene, it’s best to use a white background (-background 0xffffffff) in order to see the distortion at the perimeter of the sphere.

<scene>
	
	<!-- camera at (0,2,-12) pointed towards the origin -->
	<camera x="0.0" y="2.0" z="-8.0" fov="90.0"
			lookAtX="0.0" lookAtY="2.0" lookAtZ="0.0"
			upX="0.0" upY="1.0" upZ="0.0"/>
	
	<!-- smoked sphere -->
	<sphere radius="2.0" x="0.0" y="1.75" z="-3.0">
		<color r="0.3" g="0.3" b="0.3" a="0.3"/>
		<material reflectance="0.0" refraction="1.5" phongExponent="0.0"/>
	</sphere>
	
	<!-- blue sphere -->
	<sphere radius="1.25" x="-4.0" y="2.0" z="2.0">
		<color r="0.0" g="0.0" b="1.0" a="1.0"/>
		<material reflectance="0.0" refraction="1.0" phongExponent="16.0"/>
	</sphere>
	
	<!-- green sphere -->
	<sphere radius="1.25" x="4.0" y="2.0" z="2.0">
		<color r="0.0" g="1.0" b="0.0" a="1.0"/>
		<material reflectance="0.0" refraction="1.0" phongExponent="16.0"/>
	</sphere>
	
	<!-- white overhead light -->
	<light x="0.0" y="5.0" z="0.0" ambient="0.25">
		<color r="1.0" g="1.0" b="1.0" a="1.0"/>
	</light>
	
	<!-- "ground" sphere -->
	<sphere radius="50.0" x="0.0" y="-50.0" z="0.0">
		<color r="0.75" g="0.75" b="0.75" a="1.0"/>
		<material reflectance="0.3" refraction="1.5" phongExponent="32.0"/>
	</sphere>
	
</scene>

Optimizations

Of the various optimizations that I implemented, none provided the immediate results that the parallelism through OpenMP. I was definitely embarrassed that I didn’t think of it before the COMP 575 professor mentioned it. I fully anticipated that I would have to refactor my code to be multi-threaded. I was pleasantly surprised to find OpenMP. I had used a similar compiler extension on some Cell Processor development years ago, but OpenMP is much further along in terms of ease-of-use and compiler support. I was so thrilled when I discovered it, that I blogged about it here. With one line in my Makefile and two lines of code, I gained a nearly 75% increase.

Development Challenges

  • Viewing Rect
  • Floating Point Error When Intersecting Light Ray
  • Transparency + Ray Casting = Does Not Compute
  • Floating Point Error Part Deux

Overall, development went really smooth on this project. I was definitely making a lot of hand-gestures while trying to visualize where my cross products would be aiming as I was trying to generate the viewing rect. I didn’t know how to correlate the up vector of the camera with the vector from the camera position to the lookAt point, especially when they weren’t perpendicular. Finally I decided to use the up vector and assume that the camera was looking straight forward, along it’s z axis. Without this assumption, I felt like I would have to be dealing with an oblique projection, which I wasn’t ready for.

I struggled a little when I was trying to calculate intersections with the scene for the light vector from the visible point back to the light source. Initially I tried to throw out intersections with the primitive that the visible point was on. Of course, that didn’t yield results, so I finally settled on throwing out all intersections that were closer to the visible point than a particular threshold, lambda. The next lecture, the same strategy was mentioned as a solution to that problem.

The next significant problem that I phased was how to deal with transparency. Again, I was unlucky enough to be a little early to implement this feature. Two lectures later, we discussed ray tracing vs. ray casting. Recursive ray tracing, makes reflection and transmission with refraction nearly trivial. For a while, I was a little confused between specular reflection and dielectric reflection, but I finally differentiated the two and accepted the fact that an object can be a dielectric and also have specular reflective material properties. The last part of ray tracing that was really challenging, was the calculation of the “a” constant when determining the filtering of light when it is transmitted through a dielectric. The textbook described how the Beer-Lambert Law determined how much light is transmitted, but they said that a constant for each color channel is chosen and that the natural logs from the formula are rolled into that. Furthermore, they mentioned that developer’s often tune this parameter by eye. I settled on a calculation for “a” that took each color channel of the intersected primitive and multiplied it with (1 – alpha) for that color. Visually, I found the results to be satisfactory.

The last hurdle that I faced was again related to detecting intersections that are too close to the visible point. This time, the rays in question were the transmitted/refracted rays. I was still using the threshold from before to eliminate intersections that were too close to the ray origin. However, the threshold value that I was using was very small. I found that several of the refraction calculations involved a lot of floating point math errors that had built up through the multiple calculations and amplified by the recursion. I just relaxed the threshold and the noise was eliminated.