Clipping Space

Upgrage to Ubuntu 11

2011-10-24T20:16:00.000-07:00

Broken Upgrade Dialog - Bad Omen
With the release 11.10, my previous version of Ubuntu started receiving popup dialogs urging me to upgrade to the latest and greatest. Options: "Don't Ask Again", "Ask Me Later", and "Upgrade Now" (more or less). I had postponed the upgrade several times because I'm usually wary to upgrade since Ubuntu seems to have had many rough edges as of late. I noticed "Ask Me Later" did nothing, not even close the dialog, so I had simply killed it myself. Bad omen, I guess. In the dialog I also saw some type of web-based page with some of the new features offered. Much of it was cropped off in the little dialog. Not only was the dialog non-resizeable so I couldn't expand this small page to see the new features, my mouse wheel didn't respect it so I had to use the painful overlay scrollbars that came out in 11.04 (more on that later).

Dash Improvements
There have been several improvements on the dash including expanded right-click support. Some tasks have more functionality like the terminal button can open new windows and the CD/DVD button has standard options you'd expect like "Eject" or "Open". Still a little confused about what options come from where. I can't create new windows for chrome, but can for firefox. Not sure what the distinction is besides some internal setting allowing firefox to do this. Seems like if there were a default, it would be to allow the user to have as many sessions opened of whatever as they want.

The workspace icon still has no options to change the number of workspaces (at least via right-click). I like to have around ten. I'm told I can install compiz to configure this, but why don't I just get the option via right-click to bring up a properties dialog. If it's important enough to be on the Dash by default, why doesn't it get custom options?

Global Menu
The global menu is still a little rough. As mentioned on several other sites, LibreOffice isn't configured correctly to use this menu, which isn't a big deal. The bigger problem lies with multi-window programs like gimp, which are incredibly annoying to deal with. If the main window is not selected, the global menu defaults to... nothing. That means if I change a layer or select a tool, I have to go back and select the main window to access the menu options at the top of the screen. To me, this seems to be a bug in Unity. On the other hand, how should it behave if the subwindow has its own menu? In the short couple of days using 11.10, this has been an extreme annoyance using gimp. I don't like how the menu is even hidden until mouseover, but that's another direction the Ubuntu team has taken up as a design goal (more on that later). I don't care how familiar one gets with the menu layout in your applet of choice. The fact of the matter is menu items are now harder to find because one has to move the mouse up the the menubar, wait for the menu to appear, and then move over to it. I'm convinced this will slow down every single trip to the menu and I'm hoping the designers of this feature go crazy over it and disable the hiding in the next release. While it doesn't make any sense to copy Apple's design decisions for the sake of copying Apple's design decisions, the fact that they don't do this should merit some serious thought as to why they didn't. It's slower to use. Period.

can just use default scroll bars

main window selected - main menu accessible

secondary window selected - no menu for you :(

Speaking of the menubar at the top, I've caught myself dragging windows close to the top of the screen and accidentally maximized them. The double-click still works, so I don't know why a user would need a secondary option that potentially isn't what they really want to do. I have multiple windows up side by side all the time and this just makes resizing them all the more annoying. I can work around this issue by being more careful, but its a pointless feature that does nothing but increase the possibility of the desktop manager doing something other than intended.

Overlay Scrollbars
While some of the features I've discussed were introduced in 11.04, I'm seeing them now as I've finally moved away from the classic interface, and committed myself to becoming comfortable with this new version. One feature that's appeared (or disappeared) in Ubuntu 11 is the scrollbars as many know and love.

The goal is to help people immerse themselves in their stuff, without being burdened with large amounts of widgetry which isn’t relevant to the thing they are trying to concentrate on. And when it comes to widgetry, there are few things left which take up more space than scrollbars. --Mark Shuttleworth

As mentioned earlier, Ubuntu designers have publicly stated the design goal to reduce the amount of "widgetry" on the page. Mark Shuttleworth actually has a lengthy blog post on this topic and delves into great description of this new scrollbar design.

one overlay scrollbar among many

People are usually resistant to change and I certainly have to work as hard as most to take things in with an open mind. At first I felt they had a webpage-javascript-menu feel to them, but I'm starting to tolerate them. Unlike Mac OS X Lion, which has also recently removed the scrollbar in a similar fashion (to the dismay of some much frustrated users), Ubuntu at least keeps a small sliver of bar on the screen at all times to give an idea of where the user is on the page.

Ignoring the pomp and circumstance the Ubuntu design team seems to have made over the rollout of this feature (almost to a ridiculous level of pride), I really think it is a rather useless and even problematic problem for several reasons.

First, the display of these overlay scrollbars is application dependent. As shown in the picture above, only one window in this particular screenshot uses this feature. Since most of the time I'm in a web browser or my own IDE, I won't see this new feature they seem so proud of. Having multiple types of scrollbars on the page seems to go against years of work Linux developers have done to get a consistent visual style across applications using different libraries, yet Ubuntu obviously felt reducing widgetry on a few of their applications was more important. While this isn't a terrible problem for me, it also makes it harder to get used to as I'm now using normal scrollbars 95% of the time and the overlay scrollbars when I open up one of their Ubuntu-based apps. I have to remember that the lack of scrollbar doesn't mean there's nothing to scroll. So while Ubuntu is very proud of this feature, it just creates unneeded variation between windows at very little benefit except for making Ubuntu-related screenshots prettier.

Second, when innovating new design features, it's really important (to me at least), to justify the change. Christian Giordano, one of the main implementers of the design, actually has a lengthy post, Introducing Overlay Scrollbars in Unity, discussing the overall design goals of the project. He notes that removing "widgetry"--something they've obviously succeeded at--is one of the motivations to "provide a more immersive experience". That's a nice way of saying prettier. Regaining screenspace is hardly a problem given the 15-pixel-wide widget is a sliver on a one-to-two-thousand-pixel-wide screen. He also adds an seemlingly ignored prerequisite in that it "shouldn’t conflict with the window resizing functionalities". I think this has been brushed over by many critics.

shown in red, these are the areas of the border I
must now use to resize that side of the window

As shown above, resizing has indeed been affected. The amount of content off page determines how much border real estate one has to resize the window. The designers added a feature so if one mouses over the overlay for a certain amount of time (~3 seconds), it will dissolve out and one can resize using the full border. I'm not interested in waiting to resize my window. I have a feeling this will annoy many who mouse over the scrollbar while reading to get ready to move down the page only to click and find the scrollbar has since evaporated.

Why not just use a scroll wheel, one might ask? Well, I have a scroll wheel so this doesn't greatly affect me (except in certain cases as described in the beginning where Ubuntu has overlay scrollbars, but doesn't respect the scroll wheel). However, many users out there still don't have scroll wheels on their mouse. 70% of Apple computers sold have built-in touchpads, and all iMacs come with Apple's smart mouse with a built-in trackpad of sorts as the base mouse. I do not expect similar numbers for Ubuntu Linux users--many of whom are probably using outdated lab machines without any scroll wheel on the keyboard or mouse.

Despite all my whining, it is apparently possible to disable the feature, but again, why put it in there in the first place? While Ubuntu has been a pleasure over the last few years as a stable and user-friendly operating system, the new UI-drive championed by Shuttleworth has made for a rockier transition between iterations and bugs have become more and more common during upgrades. While I'll probably continue with Ubuntu for awhile, I'm hoping they'll change their focus to something that will really improve my desktop experience... like building device drivers.

Update
I got a bit of feedback from a few sources regarding my closing comment on device drivers--one in particular angrily commenting that it's device manufacturers' responsibility to create Linux drivers. I try not to go into debates online as I feel like one can argue online with a stranger for hours, with whom I might find some quick concensus in person. I've seen this phenomenon even with family members, where online arguments seem to flair over otherwise menial things.

Anyway, despite my preference for Linux, I'm of the mind that a manufacturer has little moral or ethical obligation to write Linux drivers. While driver availability for certain products has certainly improved a lot in the last ten years, its still in a very poor, incomplete state. Saying manufacturers "should" write their own drivers for non-profitable platforms is a little idealistic, simply shown by the fact that so many new and popular devices don't support Linux. As such, I was just stating that Ubuntu's engineers would do better in my opinion joining the ranks of many other Linux-advocating contributors by coordinating, creating, and polishing Linux drivers. And that's all I have to say about that.

Single-Pass Wireframe Rendering Explained and Extended

2011-09-11T08:10:00.000-07:00

I got a pretty good followup in my previous post with how to implement "Single-Pass Wireframe Rendering". I thought I'd take a second to briefly explain how the edge detection actually worked.

As I said before, the basic idea is that we want each fragment to know about how far it is from any given edge so we can color it appropriately. First, we have to remember that OpenGL is an interpolation engine and it is very good at that. When some attribute is assigned to a vertex and the triangle is rasterized, fragments created inside that triangle get some interpolated value of that attribute depending on how far it is from the surrounding vertices.

Shown below, a triangle has a three-channel attribute assigned to each vertex. In the fragment shader, those values will be some mixture of the three channels. You'll notice, for example that the triangle in the image below gets less red from left to right. The first RGB channel starts at 1, but as one moves towards that channel goes to zero.

That's the basic gist of the attribute interpolation. The nice thing about modern GPUs is it lets us put anything we want in these attributes. They may be used in the fragment shader as colors, normals, texture coordinates, etc. but OpenGL doesn't really care about how you plan on using these attributes as they all get interpolated the same way. In the fragment shader, we can decide how to make sense of the interpolated values.

Finding Edges Programmatically
Notice the pixel values along the top-left area of the triangle above have a low green value because the left and top vertices have no green in them, so pixels moving towards that edge have less and less green. Similarly, the right side of the triangle has pretty much no red in it, because the values in the vertices above and below it have no red. The same holds true for the bottom edge of the triangle having no blue. The insight to be gained here and which is used in "Single-Pass Wireframe Rendering" is that values along the edges of the triangle will have a very low value in at least one of the three channels. If ANY of the channels is close to zero, that fragment is sitting on or very near an edge.

images taken from nVidia's Solid Wireframe paper

We could just assign similar values as here and just render edges if the value is below some threshold. The problem, though, is that these values aren't in viewport space and we probably want to measure our line thickness in terms of pixels. Otherwise the edge thickness on our screen would change depending on the size of the triangle (maybe you want that, whatever).

As shown in the picture above, we calculate the altitudes of each vertex in screen space and store them in some vertex attribute. In the fragment shader, the value (d0,d1,d2) will be somewhere between the three vertex attributes. As described above, if any of these channels d0, d1 or d2 is close to zero, that means we're sitting on an edge.

nVidia has an excellent paper called Solid Wireframe, which goes into a bit more detail how this works and provides some really great illustrations.

Excluding Edges on polygons
While rendering edges is nice, I may not want every edge of a given triangle to be rendered. For example, if I have some five-sided polygon concave polygon that I break into triangles using some technique like ear clipping (pdf), I may not want the interior edges inside the polygon to be rendered.

A simple way to exclude an edge of a given polygon is to make sure that that value never goes to zero by setting the channels of the other vertices to some high amount Q. This Q can be any value higher than your maximum edge-width. In my program, I set it to 100 since I'll probably never be drawing edges thicker than that.

If Q is relatively high, fragments along that edge will not have low values in any channel

Designating which edges to exclude requires an additional vertex attribute sent down from the program. I attach a float to each vertex with a 0 or 1 whether or not I want to exclude that edge from being rendered. I then update my geometry shader accordingly.

my updated vertex shader...


#version 120
#extension GL_EXT_gpu_shader4 : enable
in vec3 vertex;
in vec4 color;
in vec3 normal;
in float excludeEdge;
varying vec3 vertWorldPos;
varying vec3 vertWorldNormal;
varying float vertExcludeEdge;
uniform mat4 objToWorld;
uniform mat4 cameraPV;
uniform mat4 normalToWorld;
void main() {
vertWorldPos = (objToWorld * vec4(vertex,1.0)).xyz;
vertWorldNormal = (normalToWorld * vec4(normal,1.0)).xyz;
gl_Position = cameraPV * objToWorld * vec4(vertex,1.0);
vertExcludeEdge = excludeEdge;
gl_FrontColor = color;
}

and my updated geometry shader...


#version 120
#extension GL_EXT_gpu_shader4 : enable
#extension GL_EXT_geometry_shader4 : enable
varying in vec3 vertWorldPos[3];
varying in vec3 vertWorldNormal[3];
varying in float vertExcludeEdge[3];
varying out vec3 worldNormal;
varying out vec3 worldPos;
uniform vec2 WIN_SCALE;
noperspective varying vec3 dist;
void main(void)
{
float MEW = 100.0; // max edge width
// adapted from 'Single-Pass Wireframe Rendering'
vec2 p0 = WIN_SCALE * gl_PositionIn[0].xy/gl_PositionIn[0].w;
vec2 p1 = WIN_SCALE * gl_PositionIn[1].xy/gl_PositionIn[1].w;
vec2 p2 = WIN_SCALE * gl_PositionIn[2].xy/gl_PositionIn[2].w;
vec2 v0 = p2-p1;
vec2 v1 = p2-p0;
vec2 v2 = p1-p0;
float area = abs(v1.x*v2.y - v1.y * v2.x);
dist = vec3(area/length(v0),vertExcludeEdge[1]*MEW,vertExcludeEdge[2]*MEW);
worldPos = vertWorldPos[0];
worldNormal = vertWorldNormal[0];
gl_Position = gl_PositionIn[0];
EmitVertex();
dist = vec3(vertExcludeEdge[0]*MEW,area/length(v1),vertExcludeEdge[2]*MEW);
worldPos = vertWorldPos[1];
worldNormal = vertWorldNormal[1];
gl_Position = gl_PositionIn[1];
EmitVertex();
dist = vec3(vertExcludeEdge[0]*MEW,vertExcludeEdge[1]*MEW,area/length(v2));
worldPos = vertWorldPos[2];
worldNormal = vertWorldNormal[2];
gl_Position = gl_PositionIn[2];
EmitVertex();
EndPrimitive();
}

Without edge removal, each triangle has its own edge

Triangle mesh rendered excluding certain edges

Single-Pass Wireframe Rendering

2011-09-10T08:20:00.000-07:00

It came time for me to add a wireframe to my mesh and just when I was about to do the standard two-pass approach of rendering out my mesh faces and then rendering my wireframe with GL_LINES over that, I came across Single-Pass Wireframe Rendering, a simple idea for rendering my faces and lines in just one pass. The idea, to put it simply, is to add some smarts to the fragment code so when it's rendering fragments close to the sides of a face, it blends in an edge color. The paper gives several reasons why this is a better approach including better performance and some really cool added abilities. The best part is it's very easy to add to existing code without much modification.

Adding the Geometry Shader
My code already had a basic vertex/fragment shader for doing some basic lighting and I just needed to add geometry shader in between that could add an attribute to each vertex specifying how far the fragment would be from the edge in screen space.

Here's the geometry shader taken almost straight from their full paper off their site...


#version 120
#extension GL_EXT_gpu_shader4 : enable
#extension GL_EXT_geometry_shader4 : enable
varying in vec3 vertWorldPos[3];
varying in vec3 vertWorldNormal[3];
varying out vec3 worldNormal;
varying out vec3 worldPos;
uniform vec2 WIN_SCALE;
noperspective varying vec3 dist;
void main(void)
{
  // taken from 'Single-Pass Wireframe Rendering'
  vec2 p0 = WIN_SCALE * gl_PositionIn[0].xy/gl_PositionIn[0].w;
  vec2 p1 = WIN_SCALE * gl_PositionIn[1].xy/gl_PositionIn[1].w;
  vec2 p2 = WIN_SCALE * gl_PositionIn[2].xy/gl_PositionIn[2].w;
  vec2 v0 = p2-p1;
  vec2 v1 = p2-p0;
  vec2 v2 = p1-p0;
  float area = abs(v1.x*v2.y - v1.y * v2.x);

  dist = vec3(area/length(v0),0,0);
  worldPos = vertWorldPos[0];
  worldNormal = vertWorldNormal[0];
  gl_Position = gl_PositionIn[0];
  EmitVertex();
  dist = vec3(0,area/length(v1),0);
  worldPos = vertWorldPos[1];
  worldNormal = vertWorldNormal[1];
  gl_Position = gl_PositionIn[1];
  EmitVertex();
  dist = vec3(0,0,area/length(v2));
  worldPos = vertWorldPos[2];
  worldNormal = vertWorldNormal[2];
  gl_Position = gl_PositionIn[2];
  EmitVertex();
  EndPrimitive();
}

If you're already familiar with the vertex/fragment shader pipeline, which has been around quite a few years longer than the geometry shader, you'll recognize nothing is too out of the ordinary. It takes a world position and normal, which is basically just passed off to the fragment shader for lighting purposes. Although I've done quite a bit of GLSL, this was my first attempt at using a geometry shader, and once I learned the basic idea, I found it pretty intuitive.

First, there are varying inputs from the vertex shader that come in as arrays--one element for each vertex. The names have to match up, so for the in vec3 vertWorldPos[3] attribute, there must be a corresponding out vec3 vertWorldPos designated in the vertex shader. The exception to this is predefined variables like gl_Position, which comes in as gl_PositionIn[]. Not sure why the OpenGL designers decided to add those two letters, but whatever.

WIN_SCALE is the screen size, which we multiply be the vertex position XY. This takes our vertex positions in viewport space and converts them to screen space since we want to measure our distances in pixels in the fragment shader. That's followed by some basic trig to calculate the area of the triangle, which is used to find the altitude of each vertex (the closest distance to the opposing edge). Because the altitude is already in screen space, the noperspective keyword is added to disable perspective correction.

The geometry shader is responsible for actually creating the primitives via the EmitVertex() and EndPrimitive() functions. When EmitVertex() function is called, it sends a vertex down the pipeline with attributes based on whatever the out attributes happen to be set to at the time. EndPrimitive() just tells OpenGL that the vertices already sent down are ready to be rasterized as a primitive.

The geometry shader can actually create additional geometry on the fly, but it comes with some caveats. We must designate in our C++ code an upper bound of how many vertices we might want to create. This geometry shader doesn't create any additional geometry, but it's still useful as it provides knowledge of the neighboring vertices to calculate the outgoing vertex altitudes.

Setting Up the Geometry Shader
Using Qt, the geometry shader is compiled just like the vertex and fragment shader.


QGLShader* vertShader = new QGLShader(QGLShader::Vertex);
vertShader->compileSourceCode(vertSource);

QGLShader* geomShader = new QGLShader(QGLShader::Geometry);
geomShader->compileSourceCode(geomSource);

QGLShader* fragShader = new QGLShader(QGLShader::Fragment);
fragShader->compileSourceCode(fragSource);

QGLShaderProgramP program = QGLShaderProgramP(new QGLShaderProgram(parent));
program->addShader(vertShader);
    program->addShader(geomShader);
program->addShader(fragShader);

The only other adjustment is when we bind our shader. Because the geometry shader can create more geometry than inputted, it requires giving OpenGL a heads up of how much geometry you might create. You don't necessarily have to create all the vertices you allocate, but it's just a heads up for OpenGL. You can all also configure the geometry shader to output a different type of primitive than inputted like creating GL_POINTS from GL_TRIANGLES. Because this geometry shader is just taking a triangle in and outputting a triangle, we can just set the number of outgoing vertices to the number going in. GL_GEOMETRY_INPUT_TYPE, GL_GEOMETRY_OUTPUT_TYPE, and GL_GEOMETRY_VERTICES_OUT need to be specified prior to linking the shader.


QGLShaderProgram* meshShader = panel->getShader();

// geometry-shader attributes must be applied prior to linking
meshShader->setGeometryInputType(GL_TRIANGLES);
meshShader->setGeometryOutputType(GL_TRIANGLES);
meshShader->setGeometryOutputVertexCount(numTriangles*3);
meshShader->bind();
meshShader->setUniformValue("WIN_SCALE", QVector2D(panel->width(),panel->height()));
meshShader->setUniformValue("objToWorld", objToWorld);
meshShader->setUniformValue("normalToWorld", normalToWorld);
meshShader->setUniformValue("cameraPV", cameraProjViewM);
meshShader->setUniformValue("cameraPos", camera->eye());
meshShader->setUniformValue("lightDir", -camera->lookDir().normalized());

We also need to modify the fragment shader to take this distance variable into account to see if our fragment is close to the edge.


#version 120
#extension GL_EXT_gpu_shader4 : enable
varying vec3 worldPos;
varying vec3 worldNormal;
noperspective varying vec3 dist;
uniform vec3 cameraPos;
uniform vec3 lightDir;
uniform vec4 singleColor;
uniform float isSingleColor;
void main() {
// determine frag distance to closest edge
float nearD = min(min(dist[0],dist[1]),dist[2]);
float edgeIntensity = exp2(-1.0*nearD*nearD);
vec3 L = lightDir;
vec3 V = normalize(cameraPos - worldPos);
vec3 N = normalize(worldNormal);
vec3 H = normalize(L+V);
vec4 color = isSingleColor*singleColor + (1.0-isSingleColor)*gl_Color;
float amb = 0.6;
vec4 ambient = color * amb;
vec4 diffuse = color * (1.0 - amb) * max(dot(L, N), 0.0);
vec4 specular = vec4(0.0);
edgeIntensity = 0.0;

// blend between edge color and normal lighting color
gl_FragColor = (edgeIntensity * vec4(0.1,0.1,0.1,1.0)) + ((1.0-edgeIntensity) * vec4(ambient + diffuse + specular));
}

And that's it! It takes a bit more work to get it working with quads, but once done you can do some pretty wild and awesome tricks as shown on the author's wireframe site.

Before

After

And here's the vertex shader for reference, but as you can see it's quite simple because a bit of the processing it's did has been moved to the geometry shader. Nothing here really even has to do with the edge rendering.


#version 120
#extension GL_EXT_gpu_shader4 : enable
in vec3 vertex;
in vec4 color;
in vec3 normal;
varying vec3 vertWorldPos;
varying vec3 vertWorldNormal;
uniform mat4 objToWorld;
uniform mat4 cameraPV;
uniform mat4 normalToWorld;
void main() {
  vertWorldPos = (objToWorld * vec4(vertex,1.0)).xyz;
  vertWorldNormal = (normalToWorld * vec4(normal,1.0)).xyz;
  gl_Position = cameraPV * objToWorld * vec4(vertex,1.0);
  gl_FrontColor = color;
}

Sunshine: Fixed Normals

2011-09-07T06:02:00.000-07:00

I'm finally starting to make some noticeable headway in my Sunshine app. It feels like everything I do has such a little impact on the UI, but then I tell myself it's all "infrastructure" and soon I'll be able to start adding features like crazy. I'm probably lying to myself.

Imported lamp OBJ with calculated normals

Infrastructure - boost::python bindings
After a lot of help from the boost::python mailing list, I've managed to expose my Scene object to python. Although there isn't a lot of the C++ code exposed, the "infrastructure" for it is there so I can expose classes and individual functions quickly on a need-to-expose basis. Right now I have a python script, which compiles to a Qt resource in the binary and use it to import OBJs. Although it's fairly generic (lacks material support, ignores normals/UVs), it would be plenty trivial to import other geometry types with very little effort.

Fixed Normals
As I mentioned, I'm ignoring the normals provided in the lamp OBJ for now and recompute the normals per face (no smoothing). I've had a bug in the fragment shader for the longest time that I've ignored until I started moving the cube mesh away from the origin. Looking at the GLSL, it looks like I was transforming my incoming normal by my object-to-world. That made the translation factor muck up the vector. I ended up adding a normal object-to-world matrix that right now just consists of the model rotation matrix. It looks a lot better!

Basic Features
Import OBJs
Write python-based mesh importers
Tumble around scene in Maya-like camera
Render "test" to aqsis window

Next Step
Add a face mode and some tools (?in python?)
Send scene to aqsis
Make render settings (resolution at least) adjustable

Download
https://github.com/strattonbrazil/Sunshine

Adding Python Support using Boost::Python

2011-09-03T09:05:00.000-07:00

Choosing an Embedded Language
In my multi-year toy project, I decided it would be useful to incorporate an embedded programming language into the app to make adding features a little easier. It basically came down to three possible languages that I thought would be appropriate: python, javascript, and lua. Lua is known for being light-weight and fast, and is used in many games like World of Warcraft to provide scripting to the user. Javascript itself seems to have had a bit of a resurgence in recent years in terms of stepping outside of web development. Both languages have a variety of implementations that seemed workable including luabind for lua and V8 (produced by Google) for javascript specificially for embedding into an application. Both provide a reasonable interface for mapping C++ classes.

Although both languages seemed appealing, I wasn't really satisfied with how the mappings were written to expose the C++ classes. Also, I have much more experience with python, so I had to decide if I wanted to learn how to bind a scripting engine to my application AND learn a new scripting language. I've done quite a bit of javascript, but never for a large application and wasn't sure how well things would map between it and C++, as both lua and javascript don't technically support objects the same way as python. I finally decided just to go with python. Although not as fast or light-weight as lua or javascript, I felt it provided a better one-to-one mapping of my classes, and figured users might be more comfortable with a more C-like language for application scripting.

Which Python Binding?
I ended up trying several different libraries to embed python into my app. PythonQt seemed like a good candidate as I was writing my app using the Qt libraries, but I encountered a few strange bugs and the community seemed to be stagnating--unfortunate as the API seemed really intuitive. Both SIP and SWIG are popular for binding, but both require a special syntax in external files, and I wanted to modify my qmake build as little as possible and didn't want to learn a new syntax. After finally experimenting with boost::python, I found the library allowed me to write my mappings inside C++ without learning any new syntax or much with my build system.

Using boost::python
I had a Scene class, which naturally handles everything in my scene, which I wanted to expose to python. boost::python has a special function called BOOST_PYTHON_MODULE, which puts a class into a particular module, which is imported into python. Once wrapping my Scene class with the class_ function, I could then import the Scene class into python from the "scene" module. The boost::noncopyable is an optional argument that notes not to pass the Scene object to python by value, since my scene might be rather large in memory and I didn't want multiple copies. This is more of a compiler rule as I still have to make sure I'm not passing the scene by value, but with that I get a compiler error if I try.

BOOST_PYTHON_MODULE(scene)
{
class_<Scene, boost::noncopyable>("Scene");
}

I have also been trying to use smart pointers for heap-allocated objects. I started out using QSharedPointer, but boost::shared_ptr is already supported by boost, so I ended up switching my smart pointers over to boost's.
typedef boost::shared_ptr SceneP;

Sending Yourself to Python
Once that is setup, I could then pass my Scene object over to python. I immediately hit a snag. In particular to my Scene class, the Scene actually contained my python engine and called the python code.

object ignored = exec(EXAMPLE_PY_FUNCTION, pyMainNamespace);
object processFileFunc = pyMainModule.attr("Foo").attr("processFile");
processFileFunc(this, "test.txt"); // "this" being the Scene object

Although I created the scene in a smart pointer outside the class, I didn't have access to that smart pointer inside member functions to pass to python unless I passed it into the function, which seemed unnecessary to pass a Scene member function a smart pointer to itself. I couldn't use "this" inside the member function as boost::python wouldn't know by default how to keep that in memory since other boost pointers were already pointing to my Scene object. I couldn't just create a shared_ptr in the function either, because I didn't want my Scene deleted when the shared pointer goes out of scope when the function returns.

I was actually getting this error because boost didn't know how to deal with the this pointer without passing it by value (which I explicitly said I didn't want copied, right?).

Error in Python: : No to_python
(by-value) converter found for C++ type: Scene

It turns out boost::python has a special way to do deal with this situation using a special class called boost::enable_shared_from_this, which my Scene class can inherit from.

class Scene : public boost::enable_shared_from_this<Scene>

boost::enable_shared_from_this provides two functions that allow the Scene object to create shared pointers inside member functions by calling shared_from_this(), which is inherited from boost::enable_shared_from_this.

object ignored = exec(EXAMPLE_PY_FUNCTION, pyMainNamespace);
object processFileFunc = pyMainModule.attr("Foo").attr("processFile");
// pass the python function a shared pointer instead of "this"
processFileFunc(shared_from_this(), "test.txt"); // can't use boost::shared_ptr(this) either

After updating the member function, the error went away and I could then send my Scene object to python inside and outside of the member function. Python now has access to my scene object and I can start exposing some more functions and variables inside my Scene class.

Below is a short working example of sending a shared pointer to python inside and outside of a member function (or you can look here). Special thanks to the boost::python mailing list, which was very helpful in getting me going.

#include <iostream>

#include <boost/python.hpp>

#include <boost/python/class.hpp>

#include <boost/python/module.hpp>

#include <boost/python/def.hpp>

#include <boost/enable_shared_from_this.hpp>

using namespace boost::python;

object pyMainModule;

object pyMainNamespace;

#define EXAMPLE_PY_FUNCTION \\

\"from scene import Scene\\n\" \\

\"class Foo(object):\\n\" \\

\" @staticmethod\\n\" \\

\" def processFile(scene, filename):\\n\" \\

\" print(\'here\')\\n\"

std::string parse_python_exception();

class Scene : public boost::enable_shared_from_this<Scene>

{

public:

void sendYourselfToPython()

{

try {

object ignored = exec(EXAMPLE_PY_FUNCTION, pyMainNamespace);

object processFileFunc = pyMainModule.attr(\"Foo\").attr(\"processFile\");

processFileFunc(shared_from_this(), \"test.txt\");

} catch (boost::python::error_already_set const &) {

std::string perror = parse_python_exception();

std::cerr << \"Error in Python: \" << perror << std::endl;

}

};

typedef boost::shared_ptr<Scene> SceneP;

BOOST_PYTHON_MODULE(scene)

{

class_<Scene, boost::noncopyable>(\"Scene\");

}

main(int argc, char**argv)

{

std::cout << \"starting program...\" << std::endl;

Py_Initialize();

pyMainModule = import(\"__main__\");

pyMainNamespace = pyMainModule.attr(\"__dict__\");

boost::python::register_ptr_to_python< boost::shared_ptr<Scene> >();

PyImport_AppendInittab(\"scene\", &initscene);

SceneP scene(new Scene());

// sending Scene object to python inside member function

scene->sendYourselfToPython();

try {

object ignored = exec(EXAMPLE_PY_FUNCTION, pyMainNamespace);

object processFileFunc = pyMainModule.attr(\"Foo\").attr(\"processFile\");

// send Scene object to python using smart pointer

processFileFunc(scene, \"test.txt\");

} catch (boost::python::error_already_set const &) {

std::string perror = parse_python_exception();

std::cerr << \"Error in Python: \" << perror << std::endl;

}

// taken from http://thejosephturner.com/blog/2011/06/15/embedding-python-in-c-applications-with-boostpython-part-2/

namespace py = boost::python;

std::string parse_python_exception() {

PyObject *type_ptr = NULL, *value_ptr = NULL, *traceback_ptr = NULL;

PyErr_Fetch(&type_ptr, &value_ptr, &traceback_ptr);

std::string ret(\"Unfetchable Python error\");

if (type_ptr != NULL) {

py::handle<> h_type(type_ptr);

py::str type_pstr(h_type);

py::extract<std::string> e_type_pstr(type_pstr);

if(e_type_pstr.check())

ret = e_type_pstr();

else

ret = \"Unknown exception type\";

}

if (value_ptr != NULL) {

py::handle<> h_val(value_ptr);

py::str a(h_val);

py::extract<std::string> returned(a);

if(returned.check())

ret += \": \" + returned();

else

ret += std::string(\": Unparseable Python error: \");

}

if (traceback_ptr != NULL) {

py::handle<> h_tb(traceback_ptr);

py::object tb(py::import(\"traceback\"));

py::object fmt_tb(tb.attr(\"format_tb\"));

py::object tb_list(fmt_tb(h_tb));

py::object tb_str(py::str(\"\\n\").join(tb_list));

py::extract<std::string> returned(tb_str);

if(returned.check())

ret += \": \" + returned();

else

ret += std::string(\": Unparseable Python traceback\");

}

return ret;

}

Compiling the Code
To compile the code, I used python-config to get the includes and flags. python-config is a simple utility that queries the path of your python headers and libs depending on which version of python is installed and designated on you system. It's a useful utility as I usually have several versions of python on my machine at a time. It's especially nice not having to hard code your application's build system to a particular version of python.

python-config --includes
python-config --libs

g++ test.cpp -I/usr/include/python2.7 -I/usr/include/python2.7 -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O2 -Wall -Wstrict-prototypes -lpthread -ldl -lutil -lm -lpython2.7 -lboost_python

Performance Gains in Jython 2.5.2

2011-08-07T05:41:00.000-07:00

Jython, the java implementation of the python language, has long been slower than it's cpython counterpart. I've personally seen some simple benchmarks from years past such as this, where jython would actually run 3-10 times slower. Benchmarks between the two implementations can be tricky, as I'm sure there are are some things one does better than the other depending on each developer's design decisions. jython 2.5.2 was released this last March and has noted several performance improvements on its updated features.

I wanted to do a quick test just to compare the latest performance improvements implemented by jython's development team. I had a simple ray tracer lying around (link) from when I was learning python at my current employer. This is a very simple script that renders the scene at 512x512 resolution in about half a minute. The scene has no acceleration structures to speak of and no texturing, so it's just a series of brute force calculations and pretty much zero to cache compared to a more complex scene.

Scene consisting of a procedurally-checkered sphere, a reflective sphere, and a Lambertian plane lit from above by a point light.

Graphing

I repeatedly ran the script using each implementation and averaged each result. I reran the cpython implementation a couple more times to make sure a jump for one run was a fluke. Apparently it was.

cpython 2.7.1 - 34s, 38s, 33s, 32s, 33s
jython 2.5.1 - 37s, 37s, 36s
jython 2.5.2 - 26s, 27s, 26s

Just a few thoughts and comments:

jython 2.5.2 seems to definitely have some noticeable performance increases over 2.5.1
jython may now be faster than cpython in certain situations (like the script above)
jvm startup time was not taken into account as timing was done inside python
for both jythons, JIT seemed to consistently kick in at around 10% of the run (I'm assuming it was JIT), where the script started to run faster

Although I use cpython for pretty much all my work, I'm pretty happy with the results and am excited to see jython make a bit a progess. While one implementation may be faster than another in different circumstances, I think this shows jython's performance is at least similar to cpython for certain tasks. Maybe future decisions to use one over the other will now depend on which libraries are more appropriate for a given project. Of course, that may also change as I see importing cmodules on the jython TODO list.

update:

In response to a handful of commenters, they asked for pypy to be included with the test. I downloaded the latest x86 build for my system and reran the script three times--all three runs completing in eleven seconds.

Someone also mentioned if I had tried the new Java 7 build, which is the answer is yes. I orginally downloaded java 7 to compare jython 2.5.2 against the newer version of java (which led to this benchmark). I've heard a couple of features in particular slated for Java 7 would provide huge performance gains over Java 6 for the JVM scripting languages. After running the two JVMs, however, I couldn't see much of a difference in performance. Because of the newness of Java 7, I'm going to do some more investigating to make sure I had everything setup correctly to take advantage of these improvements.

Graphing

My thoughts on Ubuntu Unity

2011-05-03T06:03:00.000-07:00

Over the weekend, I made the painful mistake of upgrading to Natty Narwhal 11.04, the newest release of Ubuntu Linux. I was previously running 10.04 and realized I was stuck with Qt 4.6 and I desperately needed a feature in 4.7. After starting the upgrade process, I realized I actually had missed the last upgrade 10.10, which was required before upgrading to 11.04. I installed that and realized it contained Qt 4.7. I could have stopped there and be content, but I didn't.

I love Ubuntu for various reasons but mostly for its usability. I can do okay on other distributions, but as my life gets busier and busier, I need my operating system to "just work". Sometimes I'm tempted to upgrade my distribution instantly when a new one comes out, but I usually regret it getting bit by stupid bugs and such. Jumping to Natty Narwhal 11.04 was no different. I had read several negative reviews on Natty Narwhal and wanted desperately to believe they were wrong, but I sadly had to change back to the classic interface. And it only took me a few days.

Here are a few of the hurdles I hit--all of which having to do with Ubuntu's new Unity system.

Restarting my machine, I couldn't log into X. I found that my nvidia driver module wasn't being built for the upgraded kernel. Somehow installing a package and skipping a seemingly-required module is totally okay. To me, though, it continually hung on the Ubunutu "five-dot" splash screen. I had to actually go get the linux-headers package for my kernel and then reinstall the nvidia-current package, which rebuilt the module correctly. Couldn't the former be a dependency of the latter?
Unity's "taskbar" is a little buggy. I'm not sure the rules for it staying out or autohiding, but it certainly wasn't consistent
I don't consider myself a power user, but I like to have widgets like workspace tracking and the CPU histogram
I missed all my icons at the top of the screen. I open multiple terminals all the time for programming. With the Unity taskbar, when I click on the terminal icon, it will either create one terminal, or take me to the workspace where my terminal is already opened. I just want a new terminal window
It's hard seeing what's on the screen without the traditional taskbar. Windows got buried under each other and I didn't know where they were (the taskbar in Unity doesn't help, while the more classic taskbar shows me exactly what's running on this workspace). Also, how do I change the number of workspaces? I had ten--and I used every one--and now I have four
This is a minor complaint that I can get used to, but Unity uses the "Universal Menubar" style ala Mac OS X, where the focused application has it's menubar at the top of the screen. This isn't necessarily bad, but it hides all the menus until you mouse over the bar. Why?
I actually had some random bugs including loading windows that appeared with no border and certain programs not receiving mouse input after I returned from a different workspace

To me Unity was like Knight and Day with Tom Cruise. I sat down to watch it and I really, really wanted to like it despite all the negative reviews. But it just didn't work. Like this mediocre movie, it wasn't a horrible premise (besides a cliche hacker and a mystical power source the size of a AA battery), but it just wasn't executed correctly. I believe most of these issues are fixable, but I'm afraid this new desktop has left a bad taste in a lot of people's mouths.

Integrating Sunflow

2011-04-24T13:52:00.000-07:00

I've been playing around with some utilities for moving lights around a scene and rendering it in Sunflow for years. I've done so much rewriting just to destroy it over and over again, I decided to just take much smaller bites and try doing something very tiny with the program.

import a PLY object (buggy)
add an attentuated spotlight
camera controls (incomplete)
adjust basic global illumination

My silly toy

no bounces

Using jQuery UI's date picker on all django forms

2011-03-26T14:27:00.000-07:00

After getting over the initial learning curves of django's forms, I've begun to really appreciate the level of customizability the developers have incorporated into the API. By default, when sending a model to a form, any DateField members are converted to form DateField instances, which translates to a simple textfield. This isn't very attractive and quickly leads to formatting complaints from users (and supervisors). There's another widget django provides for picking dates--three comboboxes for month, date, and year--but it's not a very elegant solution. I thought it would be nice if, by default, all my forms could use jQuery UI's datepicker. Here's what I did.

First, after some searching online, it seemed several people have experienced similar issues. I happened to run across this answer on stackoverflow for customizing widgets for all forms.

Here's my final code.

def make_custom_datefield(f):
   formfield = f.formfield()
   if isinstance(f, models.DateField):
   formfield.widget.format = '%m/%d/%Y'
   formfield.widget.attrs.update({'class':'datePicker', 'readonly':'true'})
   return formfield

class ProjectForm(ModelForm):
   formfield_callback = make_custom_datefield
   class Meta:
   model = Project

First, on ProjectForm I specify a custom callback function for handling form fields. This is actually really nice as I can apply this code to any form I want instead of marking individual fields for a form or applying the entire fix to every single model.

In make_custom_datefield I do a quick check to see if it's a model DateField instance. If it is, I do some modifying. First, I change the format of the widget so incoming data from the model match jQuery's format. It might be possible to modify jQuery to match Django, but whatever. Then I add on two custom attributes to the widget. Both of these directly map to html attributes of the input tag.

<input class="datePicker" readonly="true" type="text" id="id_dateDue" />

The datePicker class is important so I can mark this input as a jQuery calendar in the browser. I also mark it as readonly so users can't modify the date with bad formats. Marking the input as read-only is a double-edged sword as it also prevents users from quickly entering dates months or years away.

Once that is working, I just need to add some code to my page that will mark all datePicker instances in javascript as being datepicker widgets.

// on page load

$(function() {
$( ".datePicker" ).datepicker();
});

And that's it! I can now make jQuery UI datepickers the default widget on any django form I choose.

PHP vs Python: A followup

2011-02-05T08:41:00.000-08:00

I received a lot more commentary for my previous post than I anticipated, so I thought I'd followup with some comments and feedback I received.

PHP not dead, just out of use
First, the title of my previous post included the phrase "dead to me". I in no way wanted to imply PHP was worthless to anyone and its large community was going away. I honestly don't care if PHP sticks around forever. My point is that as templating libraries for the web have gotten so good, much of the code is outside the template and the small benefit of embedding PHP directly into html is much less useful than it used to be. www.php.net's first description for those who might be new to the language are immediately shown, "PHP is a widely-used general-purpose scripting language that is especially suited for Web development and can be embedded into HTML." Within the first sentence they advertise PHP as being html-embeddable. My point is, big woop.

PHP's gotten boring
Many people have commented on other forums about leaving PHP, because its gotten too boring. And vice versa, leaving another language like python because it too got old and went back to PHP. Whatever floats your boat, I guess. In some ways arguing about the pleasure of programming in PHP over python is like arguing the merits of Spanish over German. Clearly, German is superior.

People tend to have relatively strong opinions over rather mundane things ranging from favorite foods to their preferred brand of socks. Programmers similarly can have very strong opinions over their languages of choice when sometimes it's their our to express themselves. Reading blogs comparing lines of python to lines of ruby tend to put me to sleep. Some comments on this subject included the ugliness of php or python. Ugliness, of course, is a very subjective word.

Years ago I encountered a site railing against the java language. I found most of the author's points, however, to be mostly an issue of taste. One issue he mentioned was the case-sensitive nature java required/assumed. This perplexed me seriously as almost every language I've ever used in my life was case sensitive. Indeed, jumping over to TIOBE, it looks like the top ten languages all have case-sensitive syntax. To OO developers, this style is often used to easily distinguish between class and object. Calling java ugly for using a industry standard? That's like calling a girl ugly because she's not a blonde asian. My point is what exactly is ugly about python? To me calling a programming language ugly demonstrates an inability to express one's possibly valid thoughts on a language. For example, some perl I might considered "ugly" for its compact, symbol-based syntax and parameter passing. Some find python ugly simply for lacking the C-style angle brackets between blocks--are they by contract considered beautiful? One might call java ugly for its extreme use of compositing just do simple file I/O. Or are these people literally calling some language visually displeasing?

So beautiful...

PHP's Community
One of PHP's biggest strengths is its availability across a large range of hosting providers. PHP currently is the standard web language any hosting service must provide. Hosts providing alternatives such as python and ruby-on-rails usually are a little harder to come by, which is a boon for PHP. One commenter strongly disagreed with my statement of the python community's size compared to php. The community can mean different things, so I'll admit it my mistake. Again, looking at the TIOBE data, PHP is shown to be more popular than python (though the latter looks to overtake it next year). Or you can simply google "php community" and see it garners more than 77 times the hits as "python community". Maybe python programmers are anti-social...

Long live templating engines!
Concluding with my previous post's title, templating engines have replaced my "need" of PHP. PHP isn't horrible by any means, but with capable templating engines in so many languages, anyone can just program in _insert_favorite_language_here_. In this case, PHP is just another scripting language. I thought about porting blocks of PHP code to python for readers to compare, but after a brief perusal I found the endeavor totally pointless considering the relatively little changes I'd make between them. So instead of ending with a quip, I'll end with a question: Supposing a script-savvy developer was entering web development, what are some motivations for using PHP I haven't mentioned?

php to python: Why PHP is now dead to me

2011-02-02T19:56:00.000-08:00

PHP started in 1995 and was a well-known web language by the time I was getting into web development around 2001. At that time I had just picked up perl--yes, perl, which at the time seemed like the end-all, be-all sexiest language ever. The only thing I liked about PHP, which I admit was a very big draw was the seemless fusion of content and code. With PHP's delimiters, one could easily blend between the content and wiring. Almost ten years later, though, PHP is starting to show serious age to the point of being a deprecated tool in the toolbox (like no one making Phillips screws anymore).

PHP as a web language
My first grudge against PHP is it's not a very generic language. People have successfully written non-web-based PHP applications, but this seems to be more of a PHP programmer, who doesn't want to learn a more robust language. After a brief scan of various PHP support sites, PHP development outside the realm of web development is basically negligible. I see no reason, in fact, besides some amazing library I might not be aware of, for me to use PHP for a non-web-based application.

PHP is a widely-used general-purpose scripting language that is especially suited for Web development and can be embedded into HTML. -http://www.php.net/

The syntax is ugly, in my opinion: requred semi-colons, arrows instead of periods to reference data, global functions to manage things like arrays instead of a more object-oriented approach, etc. After several iterations of the language, features seem tacked on to the early implementations. With python being faster and providing a larger development community, what motivates me to use PHP?

The MVC architecture
The MVC architecture is a design philosophy of separating the application into three sections: the models, which manage the data of the application; the views, which typically represent the user interface of the application; and the controllers, which handle a lot of the management between the views and models. While this design can be strictly conceptual to a programmer separating out functionality, various frameworks like Qt and CodeIgniter strictly separate these entities. Here's where I believe php has lost it's magic.

The main allure of PHP that stole a lot of perl's magic was putting the controller elements doing the processing directly into the html. Instead of managing large perl files mixed with html, people could make a mostly html-based file with a little PHP, which was much cleaner to read. In that sense, all the view implementation was usually separated from the model and controller. This seemed great at the time, but as MVC has gotten more prevalent, more and more PHP frameworks remove model/controller components from the html leaving small bits and pieces in its place. In my experience, and what seems to be the practice now in PHP, large controllers and models are created completely separate to the actual html. This creates a more coherent architecture, but it raises the question: now that we've moved so much PHP code away from html, why are we still using PHP?

The rise of templates
Templating libraries have been around for many, many years-even before PHP was popular. However, since some programming language had to drive the application anyway, I believe, there was no reason to use one if one had to do his/her coding in C/C++ or perl still. Now, however, many new languages have emerged such as ruby and python that provide a very small and more robust scripting experience. Because they are so general purpose, many more examples exist outside of web development. This is important as web applications have continually provided more and more functionality than just serving up semi-static web pages. The little bits of php code that was once in my html files are now easily replaced with some templating library like mako or genshi, and I can program in a more general-purpose language, whose techniques will apply to non-web-development tasks as well. Again, now that PHP has been moved outside of html, why should I use it over python or ruby?

Things I'll miss
Alas, PHP, I hardly knew thee. One thing I'll slightly miss, though, is the startup time in PHP. Almost every apache configuration on Linux typically comes with PHP configured. After opening up a .php file and typing a few lines, I can access the file directly in my web browser and I'm immediately seeing the results. With python, I have to do a little bit more typically to get things running via apache. This requires setting up a cgi-bin, creating a proper script alias, etc. Newer python frameworks like web.py and turbogears now come with a mini-web-server included, however, so I can hold off on configurations until I'm farther in to production.

I'll also miss PHP's documentation, which I believe is generally more accessible than python's. Many of PHP's functions get an entire page dedicated to them like explode(). The page features the basics you'd expect from an API doc--parameters, description, and return value--but includes a huge swath of examples of how to use the function. It's like an entire programming cookbook dedicated to that function. I find a lot of python docs to be a little too wordy (ex. datetime and difficult to browse to a particular function--especially if I'm searching by functionality and not name. If I'm unfamiliar with a language, I'd like to know what functions are available for a given class before treading through each and every description. The function name should typically provide sufficient description to investigate it further. Anyway, the PHP wiki/comment style of documentation is something I hope more languages adopt. Wikis are already prevalent on many projects, but it seems people are much more willing to contribute through a brief comment box instead of stepping into an entire editing mode. Is it fear? Laziness? Regardless, it seems more accessible to contribute something beneficial to the doc.

Anyway, PHP. Thanks for everything. It was fun while it lasted.

Using Redbean with Code Igniter 1.7.3

2011-01-08T10:22:00.000-08:00

I started playing around with codeigniter for a quick project, and wanted a simple ORM for manipulating databases quickly. After looking briefly at RedbeanPHP, I decided to give it a spin. Boris Strahija had actually shown how to do it last year in the forums, but I just wanted to post my files for reference. This assumes the database.php file in your config dir is already pointing to a valid database. I was using mysql.

Download RedbeanPHP and drop the two files (._rb.php and rb.php) in system/application/libraries
Create a library class called Redbean.php with the contents shown below, and drop it in the same directory
Use it in your controller

Redbean.php

ci =& get_instance();

// Include database configuration
include(APPPATH.'/config/database.php');

// Include required files
include(APPPATH.'/libraries/rb.php');

// Database data
$hostname     = $db[$active_group]['hostname'];
$username     = $db[$active_group]['username'];
$password     = $db[$active_group]['password'];
$database     = $db[$active_group]['database'];

// Create RedBean instance
$toolbox = RedBean_Setup::kickstartDev('mysql:host='.$hostname.';dbname='.$database, $username, $password);
$this->ci->rb = $toolbox->getRedBean(); 
    }
}

Using it somewhere in your controller

// example code of creating a 'post' table
$post = $this->rb->dispense("post");
$post->title = 'My first post from CodeIgniter';
$post->body ='Lorem ipsum dolor sit amet, consectetur adipisicing elit....';
$post->created = time();
$id = $this->rb->store($post);

After running this controller, you should see a 'post' table created. Done!

What you should see in phpMyAdmin

Incorporating scala, java, sbt, JOGL, Qt, and Ruby/Python

2010-10-10T10:06:00.000-07:00

For several years now, I've been iterating on a small project that allows the user to build a Sunflow scene file. When starting it, I tried to effectively design the program with the write technologies for the task.

The language of choice
First, Sunflow is written in java and as such runs on the JVM. Not only do I want to be able to build a Sunflow file, but I want to render it interactively using Sunflow's libraries. There are many langauges available on the JVM right now, but only a few sparked my interest. First, I had done everything in Java previously, which was okay but was at times a little tedious. The languages I looked at as possible replacements were scala and clojure. Although I was very interested in clojure, I thought at the time of starting that it was too foreign to me and I would end up doing something extremely naive in my design.

Scala is a statically-typed language that can at times closely matches the java language. Scala has built a large type-system, which includes many data structures that are both mutable or immutable depending on what you're using them for (functional programming, for example, would probably favor the immutable structures). Scala treats it's functions as first-class citizens, so they're easily passed around to other functions. I can even make large anonymous functions that fit right within another function call. It's syntax is also slightly less verbose than java, and it provides an excellent getter/setter infrastructure that's extremely clean.

Scala isn't all roses, however. First, scala seems to be growing faster than my app, so as I tried to stay up to date with the latest scala features, it's often broken compatibility in significant ways, which has been a bit of a distraction fixing. Second, some of the code is illegible to me. It has a complicated type system and weird language symbols sometimes that seem to pull from esoteric languages for the sake of it instead of creating a simpler style. My scala is probably pretty java-like, so it's fairly easy to read.

Building with scala
Another advantages of scala is its ability to cross-compile with java. I was previously using ant, which was my foray into a java build system. First, I don't like work in XML for a myriad of reasons. After the ant scala compiler tool started throwing bogus errors, I was advised to move over to the simple-build-tool or sbt.

After adding a launcher to my class path, sbt allowed me to quickly setup a new project, whose project file is written in scala, a much more preferred way to configure my app. I simply put all my scala code in ./src/scala and all my java code in ./src/java and sbt combines them. Although it took a moderate amount of time to setup my project, in the end it's been a joy to work with sbt.

JOGL
The JVM requires JOGL to do OpenGL rendering. This can be tedious to setup as I'm used to just tossing a jar onto the classpath and having my build system include it. Because JOGL requires native libraries, which need to be included separately to the java library path. This took a while for me to figure out, but ended up being a simple setup in the end.

import sbt._
import java.io.File

class SunshineProject(info:ProjectInfo) extends DefaultProject(info)
{
  // tells sbt which class to run
  override def mainClass:Option[String] = Some("com.googlecode.sunshine.Sunshine")

  def nativeJOGL:String = {
    var os = System.getProperty("os.name").toLowerCase
    var arch = System.getProperty("os.arch").toLowerCase

    // this is to match the JOGL builds
    if (arch.matches("i386")) arch = "i586"

    if (os.contains("windows")) {
      os = "windows"
      arch = "i586"
    }
    println("OS: %s".format(os))
    println("JOGL Path: %s".format("./lib/jogl-2.0-%s-%s".format(os, arch)))

    "./lib/jogl-2.0-%s-%s".format(os, arch)
  }

  override def fork = forkRun("-Djava.library.path=%s".format(nativeJOGL) :: Nil)

All this basically does is query the OS and architecture from the JVM and adds it's respective JOGL directory to the library path. This required me to fork the JVM, as adding paths to the current JVM doesn't seem to work. Notice I just had to override the fork command and sbt knows I want to fork. Overriding the run command won't fork the JVM when starting. I did something similar in ant, but it was much longer and more difficult to read.

Using Qt
Java Swing is usually an okay GUI library for my small java projects, but it's slightly cumbersome when trying to do something complex. Trolltech's Qt is a very popular framework that has continually gained popularity over the years for it's great documentation, intuitive API, and it's event handling system.

QtJambi is the java binding for using the Qt libraries. A few months ago Trolltech dropped support of QtJambi, but pushed it off to the community to continue updating. So far, they seem to be doing a decent job, although they have been continually asking for help.

sbt supports automatic library manage via Apache Ivy. Instead of shipping every build of Qt for a given architecture, I can setup Qt as a managed library. By pointing sbt to the QtJambi servers, sbt will automatically fetch them during compilation.

val qtDepSnapshots = "Qt Maven2 Snapshots Repository" at "http://qtjambi.sourceforge.net/maven2/"
val qtDep = "net.sf.qtjambi" % "qtjambi" % "4.5.2_01"
val qtjambiBase = "net.sf.qtjambi" % "qtjambi-base-linux32" % "4.5.2_01"
val qtjambiPlatform = "net.sf.qtjambi" % "qtjambi-platform-linux32" % "4.5.2_01"

Right now, I'm only fetching Linux x86 libraries as that's what I'm working off of. Adding the block above directly into my build class will tell sbt to grab them for me. There's a bit of magic going on here for me as I don't understand how sbt knows these variables are library dependencies or just values I've created in my program. Regardless, it's enough to get Qt downloaded and onto the classpath.

Incorporating a scripting language
At this point, I could just start coding my application, but since I'm doing a lot of designing on the fly, it takes a long time to compile my application to see a small change. I wanted to incorporate a scripting language that lets me make changes to the interface quickly without existing the program.

As much as I complain about python, I use it a lot at work and am fairly productive programming in it. The jython project provides a python implementation that runs on the JVM. I've used this library before a year ago, but had to scrap it as it was too slow latency-wise. I've heard it's gotten significantly faster recently, so I gave it another shot and found it to be much faster. Working with Qt, however, seemed to turn up a bug blocker.

[error] Exception caught after invoking slot
[error] Traceback (most recent call last):
[error]   File "", line 15, in 
[error]   File "", line 9, in __init__
[error] TypeError: Proxy instance reused

I was initially wondering if working with Qt from a scripting language was not stable, however, this seemed to be only a jython issue. I reported it to the jython team, which seems to be resolving the issue right now for their upcoming build.

In the mean time, I thought I would give ruby a spin. I'm rather unfamiliar with the Ruby language, although I haven't been oblivious to the huge success it has garnered in web community with Ruby on Rails. I've also heard great things about JRuby, the Ruby implementation on the JVM. At one point it was actually faster than the C++ build of Ruby, although I'm not sure this is necessarily true anymore.

The ruby language seems to be something between python and perl, although that's another comment that will possibly get me shot by a Ruby developer. It's a purely object-oriented language--more so than python--and provides a bit more syntax flexibility than python (for better or for worse) including some parsing syntax from perl.

val factory = new ScriptEngineManager()
val ruby = factory.getEngineByName("jruby")

val urlFile = "clear_scene.rb"
val url = getClass().getResource(urlFile)

ruby.eval(new InputStreamReader(url.openStream()))

With my main scala code, I open a Qt main window. Then hand things over to jruby. My ruby code clears out the window and fills the UI programmatically. I can add menus and event handlers as I go and when I'm ready to see the change, I simply restart the ruby evaluator and my UI rebuilt instantly with no recompilation. I literally see no latency continually reloading my ruby code and seeing my interface changes change on the fly. I plan to do most of my designing in ruby and gradually move the classes I create over to the scala-side once they become stable for a performance boost.

I like to keep one terminal open running sbt with the "~copy-resources" action continually copying my ruby changes over to the build path, while the other terminal compiles and runs my app as I go through the code changes in scala/ruby.

I've just barely started with it, but I've been enjoying ruby for the most part. A ruby developer would probably say I'm programming like a python programmer (a scala developer would probably say my scala looks like java). Anyway, I haven't had any road blocks importing the various Qt or scala classes besides two minor inconviences.

scala hashmaps
The classes I've built in scala are compiled to byte code and I've been able to read them from java and jruby without any problem. However, I use a few hashmaps in scala and I'd like to be able to iterate through them in my ruby code. JRuby provides some hooks to iterate through java collections, but not for scala, so I made a simple wrapper for my scala hashmaps so I can iterate through them in ruby normally.

class ScalaHashMap
  def initialize(hash)
    @hash = hash
  end

  def each
    @hash.size().times{|key| yield key,@hash.get(key).get}
  end
end

Getting QtJambi to see the JOGL Context
JOGL provides some useful widgets that directly tie into java swing. These widgets don't exist in JOGL for Qt. As such, it was slightly confusing trying to find documentation on getting a GL3 context from JOGL while inside a QGLWidget.

class PanelGL < QGLWidget   
  def initialize(parent = nil)     
    super     
    @camera = Register.cameras.get(0).get      
    profile = GLProfile.get(GLProfile::GL3)     
    glCaps = GLCapabilities.new(profile)     
    glCaps.setPBuffer true     
    @pBuffer = GLDrawableFactory.getFactory(profile).createGLPbuffer(glCaps,DefaultGLCapabilitiesChooser.new(),       1, 1, nil)   
  end   
  attr_reader :camera    

  def initializeGL     
    @ctx = @pBuffer.getContext()   
  end   
  attr_reader :gl    

  def resizeGL(width,height)     
    @ctx.makeCurrent() # this line isn't required for the JOGL Swing components     
    gl = @pBuffer.getContext().getGL.getGL3     
    gl.glViewport(0,0,width,height)   
  end    

  def paintGL     
    @gl = @pBuffer.getContext().getGL.getGL3     
    @gl.glClearColor(0.3, 0.3, 0.3, 0.0)     
    @gl.glClear(GL.GL_COLOR_BUFFER_BIT | GL.GL_DEPTH_BUFFER_BIT)                  
    @gl.glEnable(GL.GL_DEPTH_TEST)      

    ...      

    @gl.glDisable(GL.GL_DEPTH_TEST)   
  end 
end

I first create an pBuffer, so I can use it's context across GL widgets and share things like display lists and VBOs. The big difference in the Qt code is having to call makeCurrent() in the first GL callback that my program executes, which happens to be resizeGL. Calling makeCurrent() there beforehand makes sure the GL context is running on the same thread as the Qt GUI (or vice versa, I guess).

Conclusion
That's my basic setup and now I've got a lot of coding to do.

Example of Cache Coherency

2010-01-26T12:41:00.000-08:00

In my almost popular article The State of Ray Tracing in Games, I've frequently mentioned the coherency of rasterization being much better than ray tracing, which is pretty incoherent in many respects. I think programmers often address algorithms in a very high-level manner focusing on the big-O, which is important, but I wanted to present how coherency can directly and significantly affect run-time performance.

First, what is coherency? Coherency is defined by one dictionary as being logically or aesthetically ordered or integrated. The word comes up frequently when someone hears a disorganized speech or discussion, where the speaker jumps back and forth between topics. No one sentence or idea is wrong per se, but as a listener it's easier to bundle ideas together on a topic instead of having to jump around.

Cache coherency diagram I stole from wikipedia

Processors are incredibly complex now a days, but generally speaking there are registers which do the operations, the memory which holds the data and the program, and the cache, which sits in between. One purpose of the cache is to provide a buffer of surrounding data, so I don't have to go all the way back to system memory to get it. That trip might seem relatively fast, but it's pretty slow compared to just looking in the cache.

The Diligent Secretary Example
Imagine I was typing at my office desk and wanted to know the names on a numbered list down the hall. I send my secretary down the hall to pull the name off the list and come back with it. I use the name. I move on to the next name. This trip down the hall is relatively slow since I'm waiting for the secretary to come back. It doesn't make sense for him/her to go all the way down and come back with just one name--even if at that moment I just want one name. My secretary being the witty person that he/she is, goes and writes down ten names on this long list and comes back. I ask for the requested name and he/she gives it to me. I ask for the next name and the secretary instantly gives it to me without going down the hall again. This happens eight more times before he/she has to go down the hall to get more names off the list, but he/she has saved both of us lots of time just by grabbing the names around what I wanted. This is coherency. Because I was asking for names in order down the list, my secretary could easily cache extra names to save the trip down there. It didn't work every time, but when it did it was significantly faster.

Now, what happens if I asked for the names in an incoherent manner? My secretary comes back with the first group of names. I ask for name #3, which he/she quickly gives me. I then ask for name #47. My secretary sees he/she only has 1-10 on his/her list, so he/she needs to make another trip. This time my secretary remembers the names 40-49 and comes back. I then ask him/her for number #212. Once again the secretary has to go back to the list down the hall. I'm not asking anything more complex. I'm just asking in a seemingly incoherent order. This same phenomenon is easily presentable in a real-world example.

Real Example
Just as the secretary grabs the numbers around what I asked for with the possibility of not making another trip down the hall, processors will often pull out blocks or pages of memory around what the program requested hoping not to make the trip to system memory again. If I ask for data close (in terms of memory layout) to what I previously requested, there's a possible chance the cache will already have it and provide it faster.

Here's a really simple python script that tries to add up a bunch of integers in a coherent and incoherent manner. In the coherent function, the numbers are added up sequentially based on their order in memory. In the incoherent function, the numbers are pulled randomly from memory. Both functions provide the exact same result, but with a noticeable difference in performance. Let's see how the two compare for different sizes of data.

import random, time

n = 10000000

# make an array of coherent and incoherent indices
coherentIndices = [number for number in xrange(0,n)]
incoherentIndices = [number for number in xrange(0,n)]
random.shuffle(incoherentIndices)

def print_timing(func):
    def wrapper(*arg):
        t1 = time.time()
        res = func(*arg)
        t2 = time.time()
        print '%s took %0.3f ms' % (func.func_name, (t2-t1)*1000.0)
        return res
    return wrapper

# create some random values
values = []
for i in xrange(0,n):
    values.append(random.randint(-10,10))


# add up all the numbers coherently
@print_timing
def coherentAdding():
    total = 0
    for i in xrange(0,n):
        total += values[coherentIndices[i]]

# add up all the numbers incoherently
@print_timing
def incoherentAdding():
    total = 0
    for i in xrange(0,n):
        total += values[incoherentIndices[i]]

coherentAdding()
incoherentAdding()

Results

With a quick graph using Many Eyes, you can see the performance differences. For small numbers, the performance between the coherent and incoherent data is neglible. In the secretary example, this would be the equivalent of the secretary having all the names in his/her head so regardless of the order I ask them, no extra trips down the hall are necessary.

As the problem scales, however, the memory fetching becomes less and less efficient. For the largest test I did, incoherent access is almost 13 seconds longer than the 8 seconds it took for coherent access. In this simple example where both functions are running at O(n), it's easy to see coherency makes a huge difference.

Relevance to Ray Tracing
From a memory perspective, ray tracing is incredibly incoherent. Firing a ray from the camera to shade a pixel, the next ray over might hit a different geometry requiring different textures and instructions to be fetched. That's bad geometry and texture coherency. Plus ray tracing is touted for it's secondary effects like reflections and refractions. These rays are extremely incoherent. One ray might self-intersect the object being shaded while another ray next to it might fly off into the distant corners of the scene. Rasterization on the other hand is extremely coherent. A model is pulled in once for every pass and thrown out again. When rasterizing textured surfaces, the texture cache can grab large chunks of texture because there's good chance the next fragment being rendered is going to be in that cache. In fact the biggest reason rasterization is probably so much faster than ray tracing is its coherency. It makes hardware extremely easy and cheap to build.

ngons: Are they really that evil?

2009-12-27T11:36:00.000-08:00

Playing around with polygons and trying to code them, I've seen a variety problems that can occur working with polygonal geometry. More than once I've hit a snag in my program and I scratch my head and think, "How do the big guys handle that?" Then I crack open Maya, build the same topology and see it break there as well. What I've come to find is different modeling applications handle polygons in different ways--some are deficiencies and some are just design choices.

Problem with Tris and Quads
A polygon as most people know requires at least three points. This of course makes a triangle. A triangle is an ideal planar figure as the three points--assuming they all don't lie on the same line--form a plane. No matter where you move the points, they will always form a plane. Interpolating attributes between the points is easy. Triangles are simple to rasterize, ray trace, and are pretty much universal across modeling applications.

In geometry a polygon (pronounced /ˈpɒlɪɡɒn/) is traditionally a plane figure that is bounded by a closed path or circuit, composed of a finite sequence of straight line segments (i.e., by a closed polygonal chain). -http://en.wikipedia.org/wiki/Polygon

Stepping up to four points already begins to create problems with modeling applications. This is because unlike a triangle, not all four points have to lie on the same plane. The modeler can be restrictive to the user requiring all points to lie on the same plane (making it extremely difficult for an artist), or it can make certain assumptions about how to render a non-planar quad. Sometimes this may or may not be what the artist wants. There's not really a set definition of how to manipulate/render a non-planar polygon.

Take a look at the examples below. In the first two images, the user grabs two vertices at opposite ends of the cube and pulls down forming what looks like a roof. For many people, this maybe what they expect as the program--Blender in this case--just treats the quad as two triangles with the long edge going across the two unselected vertices. This may seem perfectly acceptable, but look at the second example. Now we grab the other two vertices and pull down. One might look at the first example and now assume that it will also form the house, but instead it forms some kind of double-steeple with a rain gutter in between.

Pulling down to opposite vertices

Pulling down the other two vertices

What's going on? Well, Blender just knows it has to render this quad face, so it looks at the first vertex on the face and says, "Okay, let's render these as triangles since rendering non-planar quads doesn't make sense and a planar quad is just two triangles anyway." So it looks at the next two vertices around the face--the one that was pulled down and the opposite unselected vertex and says, "That's three" and renders a nice roof. If you pull the other two vertices down like in the second example, Blender starts rendering at the same vertex as before, but goes up to the unselected vertex, and then back down to the other selected vertex forming that steeple/trench.

Here's the question. Which one is correct? If you pick one and assume that's what the program should always do, you've restricted the artist to never being able to make that other shape easily. You may think Blender's not very smart not knowing how to render non-planar polygons, but that wouldn't be fair. There's no rule. If some program makes a certain decision about how to render that, it's just how they want to deal with it. It doesn't make their solution correct, or Blender's solution incorrect.

You may be thinking, "Hrmm, I bet I could write an algorithm that changes around the order of the rendering to guess what the artist wants...". It's been done. If you go into Maya and try doing this example, you can actually get the model to "pop" in between these two examples as Maya tries to figure out by some threshold what you're trying to do. Is Maya right and Blender wrong? Like I said there's no rule for handling non-planar polygons. If you really want to bend a quad into a two triangles with guaranteed results, just make the two triangles before you bend them (as shown below). Now there's no ambiguity at all. The computer doesn't have to make any decisions about bending anything. You're just moving the points on the triangle, and it knows how to do that no questions asked.

Not only do quads introduce problems like these when they're non-planar, but happens when the quad is not convex? In the example below, I have pulled a vertex over to so the resulting polygon is concave. If I grabbed a different vertex, the renderer might have done what you expencted rendering two nice triangles inside the quad. But because I grabbed that vertex, the renderer made a triangle where it shouldn't have and you see visual tearing, where one triangle is sitting on top of another.

Here you might say, "Well, if the Blender programmers made their modeler smarter, they could just look at that quad, see that it's concave, and render it with the correct triangles". That's certainly a valid point, but that takes processor time to figure out. Assuming the polygon is planar, which as I already stated is iffy, the algorithm has to look at the quad and see how to best divide it up without going outside the polygon. Maya does this and it may seem like a great idea, but that's processing power that could be doing other things like rendering larger meshes. Which would you prefer?

No standards across programs
Not only does the designers have to decide and implement these rules, but what happens when the model leaves the program? Bending a quad may give you what you want in the modeler, but there's no guarantee the program where you're sending that quad handles it the exact same way. Take a ray tracer, for instance. I've never seen an ray intersection that handles a generic four-sided polygon. It will usually divide it up into triangles as would a rasterizer. There's no "correct" way to do handle non-planar polygons or concave polygons, so when you decide you want to model that way, you might get bitten later on. Some programs might handle these issues better than others, but they are just making an arbitrary decision.

N-gons are evil
I have shown that just by moving from a triangle to a quad opens up a whole set of problems--one little extra vertex now allows an artist to create non-planar, concave polygons. "Yuck!", I hope you are saying to yourself. What about ngons? ngons are typically what people call polygons with five or more sides. They have all the same problems as quads, except with infinitely more bad situations. For someone whose never used ngons, he/she may ask, "Well, why don't see just stay far away from ngons to avoid the problems?". This is yet another design decision. Here are a somes reasons why ngons should or should not be included in a modeler.

ngons are good

"clean" topology - when working with a polygons that are going to be planar anyway, ngons don't display a bunch of edges across it, which makes the model look a little cleaner
nice cuts - some tools create n-sided polygons. Although they may create poor geometry, they can be extremely convenient
power to the artist - allowing ngons in modelers gives the artist a chance to work more efficiently even though it may screw him/her up later. Plus, once they're ready to export, they can always clean the mesh up afterwards (some artists prefer this workflow)

An image I stole from the Blender forums. The extrude-vertex tool creates two visible ngons I've marked with a red dot. These ngons are very "clean" in the sense that they are planar, convex, and thus will break down to triangles without any funky results

Two images I stole from blender3darchitect.com. The artist has replaced the distracting quads over the arches with a simple concave ngon. It is debatable whether it is more pleasing to the eye--the former to me looks like keystones. The artist will probably have to clean that up somehow (like triangulating it) before exporting the model

ngons are bad

no standards - there are no guarantees that ngons will import/export as expected. I have read that Cinema 4D, for example, supports ngons, but triangulates ngons on import
subdivision - working in realtime subdivion is very popular now a days, but how do you subdivide an ngon? Most algorithms require very strict rules for mesh topology like the popular Catmull-Clark subdivision, that requires all quads. People have implemented/published additions to these algorithms to make them more robust, but it's up to the designer to pick which one is best for them
tool support - ngons require more complex data structures than quads or triangles meaning tools that work with the polygon have to be smarter--some tools just break or don't handle ngons
processing power - nothing is for free and at some point the program has to decide how to render the ngons to the screen. If it's a concave polygon, the program has to divide it into triangles that are contained in the original polygon. Would the artist rather be spending this processing power on something else?

What's the conclusion?
I can't take sides with how important or useful ngons are. I've heard several times that once an artist models with ngons, it's hard to go without them. I'm not sure if that's a good thing or not. ngons seem to make things easier at certain stages of modeling, while they often need to be cleaned up later in the pipeline. Working with just triangles and quads can be extremely difficult in many situations, but several powerful tools like loop cut and loop select only work because of the special nature of quad loops, which is why some artists try to keep the model as quads as long as possible.

Below is a screenshot from CGSociety, which has a wiki comparing the various modeling programs. It's apparent that nearly every application now supports ngons. zBrush is excused since I'm sure it has insane data structures to handle what only zBrush can handle, and Blender supposedly has ngon support on the way, so regardless of whether an artist needs it or should use it, support for them is/will be pretty much standard.

Table of modeling applications that provide ngon support taken from CGSociety's wiki

Next-Gen 3D Rendering Technology: Voxel Ray Casting

2009-10-21T20:21:00.000-07:00

Tom's Hardware recently did a follow up to their ray tracing article specifically on Voxel Ray Casting. I thought it was a good review of the technology and did a good job presenting the pros and cons associated with it.

One of the most critical bottlenecks in any rendering technique is managing coherency. The scene in a typical game may contain gigabytes of geometry and textures and it is important most of the time isn't wasted pulling the data in and out of the cache.

No graphics article/post would be complete without at least one comment in the discussion section referencing the Matrix and how it's so close to becoming a reality. I guess that's optimistic considering we can't even predict the weather or have self-driving cars. I did see a few other comments, which I thought deserved a bit more follow up.

kikireeki 10/21/2009 7:28 PM
What happened to Normal Mapping?

Normal mapping is used when one wants to render limited geometry but apply a variety of normals the the otherwise flat surface giving the illusion of detail. The point of this is to use really high amounts of geometry to do the job. Normal mapping can't fix jagged silhouettes, for instance. Each corner of a voxel has a stored normal value, and since these voxels will be less than a pixel when evaluated, the interpolated normal between these eight points is satisfactory.

spiketheaardvark 10/21/2009 8:43 PM
I wish the article discussed how such a system would handle transparent objects and refracted light sources, such as an image of a glass of water.

It doesn't. Big disappointment, I guess. If it could, it would be sparse-voxel ray tracing, wouldn't it? The idea of ray casting is you only fire rays from the camera directly into the scene. No secondary rays. A big reason ray tracing is so slow is when secondary rays are fired to other parts of the scene for things like transparency, reflection, and shadows, you have to go get that geometry to intersect against and shade (including fetching the associated textures). This is really difficult when rays are shooting off at random directions requiring everything to be paged in just to render a metallic sphere. If you have multiple reflections around the scene, there's going to be a lot of paging going on. Don't fire off enough rays for something like color bleeding and you get something like this:

Ray casting like rasterization is very coherent. With rasterization the applicaition streams in geometry piece by piece and hopefully only has to do it one time. With ray casting, part of the octree that fits in a given area of the screen can be paged in, ray casted, and paged out of memory. If you want to add secondary effects, many secondary rays leave the paged in part of the octree and need the geometry for that part of the scene brought it. And another secondary ray from the next pixel might shoot into a different part of the scene requiring another geometry fetch. That's why voxelized octrees won't get us any closer to ray-tracing-style secondary effects. It's just to give us more geometry. It's just to give us more geometry! IT'S JUST TO GIVE US MORE GEOMETRY! I'm happy enough with that. Even if it is only static geometry.

Here's Jon Olick's demo video from Siggraph 2008. If you're wondering what those funky blocks are, those are the individual blocks of the octree paged in and out of memory.

Adroid 10/22/2009 1:32 AM
Great Article. Its an interesting point that about 10 years ago the whole market went to polygons instead of voxels. Who knows where we would be if the industry went that direction. Nowadays processors are becoming more and more capable of such a feat.

I think the sweet spot is finding a mix of both... Maximizing both processor and GPU use in games. Its a heck of alot of programming, but thats why they get paid the big bucks to make games we love right?

If the whole industry went this way 10 years ago we'd be playing a lot more beautiful chess games and fewer 1st-person shooters. I was at the conference when Jon Olick was presenting. Of course, someone had to ask the question, "How do you handle animations and rebuild your octree?". He simply replied that they're not out to solve a problem ray tracing researchers have been investigating for years. This only works on static geometry. This only works for static geometry! THIS ONLY WORKS FOR STATIC GEOMETRY! To get these voxels, they model in polygons, then sample them into voxels. To do this in a game with animations, they'd have to animate the character in polygons, voxelize, and render again to get all the data back. And from what Jon Olick has mentioned, voxelizing is too slow for real time and has to be precomputed.

The idea certainly is to find the sweet spot. Rasterize animated geometry and ray cast static geometry. Developers can still model and rig everything with polygons and the engine can voxelize anything declared static. Voxelized objects lose the ability to deform, but are rendered faster. They can use the same surface shaders and even the same shadow maps, too. It can be completely transparent to the developer using the engine besides choosing what's static and what's dynamic. If the guys excitedly pushing this say it's not going to completely replace rasterization, they have no reason to lie, right? I personally still think the GPU is still best suited for rendering as most games now like Crysis are CPU-limited already doing other things like AI, physics, etc.

Here's the full pdf of Jon Olick's slides. They're pretty complex and don't have many shiny pictures, but it was a great presentation. The best part of all this is the technology is available now on current hardware and will get more prominent as more and more developers become proficient in it.

Step into Interactive Ray Tracing

2009-08-15T14:55:00.000-07:00

I overheard someone commenting recently that ray tracing was the next logical step in interactive rendering. Although this is surely a popular idea, he continued that switching to a ray tracer soon before secondary effects (like reflections and refractions) were practical would be worthwhile. His argument was that since ray tracers can use the same graphical "hacks" like environment maps and shadow maps to match rasterization, when more performance comes down the road the developers could just swap out a given hack with the physically-accurate equivalent. Why not, right? Well, that's a tough pill to swallow.

Games are bottlenecking
The fact of the matter is that interactive rendering--especially in games--is a very performance-intensive medium. As opposed to most applications like a word processor or database, every AAA game title is developed to suck every last drop of performance out of the CPU and GPU. If the developers are only getting 50% CPU/GPU utilitization, they naturally would tweak the game to get more visual quality out of the system. This is natural considering most game players aren't multi-tasking between applicationss while running these programs and can dedicate the hardware to that one game.

This is the problem with transitioning to ray tracing. To move to ray tracing while providing the same quality effects adds more work to an already bottle-necked system. Ray tracing interactive scenes is inherently slower for the same perceptive quality. Optics, BRDFs, and light-transport-related topics have been researched for hundreds of years. Today's ray tracing researchers are focused on speed. Problems include rebuilding dynamic acceleration structures, corralling rays into coherent packets, and getting all the operations to march in lock step on these SIMD-plentiful architectures. It's all about performance. The only time games will implement ray tracing is when they can do the same important effects as efficiently as rasterization. Using rasterization techniques in ray tracers is still slower then rasterization: one still has to build acceleration structures, one still has to do crazy optimizations, and one still has to deal the incoherent texture and geometry accesses inherent in ray tracing. So why on Earth would any developer opt for a ray tracer with half the performance for the same graphics just so fifty years down the road, it's easier to add secondary effects? Blah.

Rasterization's Bang for the Buck
I've stated this before, but many production companies still use rasterization because they care about visual quality. Pixar and Dreamworks, for example, still rasterize the scene first before adding any secondary effects. After all these years these companies are still using basic shadow maps to shade direct illumination. And it's their business to make pretty pictures! The only people saying ray-traced games can do soft shadows interactively are ray tracing researchers and marketers. I could write a rasterizer to do physically-accurate shadows, but it wouldn't be interactive either. That's why I don't brag about it.

With the current growth of processing power, I am guessing that sometime in my life I will see ray tracing become the normal rendering technique in interactive computer graphics, but I doubt it will be in the next thirty years. Rasterization will only fall behind the second it fails to keep improving.

Five-Years Difference
Rasterization is moving at an incredible rate. In a separate article, I compared a screenshot of two games only five years apart: Battlefield 1942 released in 2002, and Crysis released only five years later. This is what ray tracing is competing with. A rapid, cut-throat industry where GPUs are getting more and more powerful and developers are creating more and more dazzling hacks. Years from now when a ray tracer can produce images comparable Crysis, we'll be looking back wondering how we ever tolerated such mediocre graphics.

What's coming down the pipeline?
Interactive rasterization certainly hasn't stopped moving and will continue to provide a lot of one-sided competition for ray tracers in games.

Here are some things coming down the pipeline that we can look forward to that will continue to choke up interactive ray tracers:

Highly-tesselated subdivision surfaces
Movie-quality anti-aliasing
Realistic hair
Interactive deforming

Shortest Ray Tracer In the World (not really)

2009-08-13T15:34:00.000-07:00

I saw Andrew Kensler's newest back-of-a-business-card ray tracer. It's some pretty short and simple code to render his initials in reflective spheres. I'm not sure he could find the way to shorten the code even more, without losing any kind of coherence.

This took 2 minutes on my workstation

And here's the code (butchered by my browser)


#include    // card > aek.ppm

#include 

#include 

typedef int i;typedef float f;struct v{

f x,y,z;v operator+(v r){return v(x+r.x

,y+r.y,z+r.z);}v operator*(f r){return

v(x*r,y*r,z*r);}f operator%(v r){return

x*r.x+y*r.y+z*r.z;}v(){}v operator^(v r

){return v(y*r.z-z*r.y,z*r.x-x*r.z,x*r.

y-y*r.x);}v(f a,f b,f c){x=a;y=b;z=c;}v

operator!(){return*this*(1/sqrt(*this%*

this));}};i G[]={247570,280596,280600,

249748,18578,18577,231184,16,16};f R(){

return(f)rand()/RAND_MAX;}i T(v o,v d,f

&t,v&n){t=1e9;i m=0;f p=-o.z/d.z;if(.01

for(i j=9;j--;)if(G[j]&1<,0,-j-4);f b=p%d,c=p%p-1,q=b*b-c;if(q>0

){f s=-b-sqrt(q);if(s.01)t=s,n=!(

p+d*t),m=2;}}return m;}v S(v o,v d){f t

;v n;i m=T(o,d,t,n);if(!m)return v(.7,

.6,1)*pow(1-d.z,4);v h=o+d*t,l=!(v(9+R(

),9+R(),16)+h*-1),r=d+n*(n%d*-2);f b=l%

n;if(b<0||T(h,l,t,n))b=0;f p=pow(l%r*(b

>0),99);if(m&1){h=h*.2;return((i)(ceil(

h.x)+ceil(h.y))&1?v(3,1,1):v(3,3,3))*(b

*.2+.1);}return v(p,p,p)+S(h,r)*.5;}i

main(){printf("P6 512 512 255 ");v g=!v

(-6,-16,0),a=!(v(0,0,1)^g)*.002,b=!(g^a

)*.002,c=(a+b)*-256+g;for(i y=512;y--;)

for(i x=512;x--;){v p(13,13,13);for(i r

=64;r--;){v t=a*(R()-.5)*99+b*(R()-.5)*

99;p=S(v(17,16,8)+t,!(t*-1+(a*(R()+x)+b

*(y+R())+c)*16))*3.5+p;}printf("%c%c%c"

,(i)p.x,(i)p.y,(i)p.z);}}

I'm still waiting for his back-of-a-napkin photon mapper.

Scala Review: Quite Refreshing

2009-06-13T23:28:00.000-07:00

Since my first programming course in college, I've been told to use the right programming tool for the job. This was back in the day where perl was the ideal CGI and scripting language. I think even without python, perl was still the wrong tool for the job.

Regardless, I have used java many times for testing any idea floating around in my head. It had the relative speed of C++ and came with many more libraries than C++ making it a lot easier to perform some arbitrary task like load an image without having to find a special C++ library like libpng.

It's hard being number 2
Java sure has its faults. It certainly isn't the sexy language it was ten years ago, but it sometimes gets flak it really doesn't deserve. It is always criticized for being slower than C++, while no one mentions it being faster than most other languages. I guess it's hard being the number 2 in performance.

Java is a relatively simple language in the sense that it's pretty easy to understand what the code is doing. C++ trivia questions abound that make you ask yourself, "Why?! Why?! Why?! That must be a compiler bug!" until you see it in a C++ specification. Java dropped function passing, pointers, multiple inheritance, operating overloading, and a lot of other features to create a language one might call dumbed down.

This, in my opinion, is one of Java's main complaints. It's a simple language. Usually when someone will start listing examples, it's them lamenting that Java can't do it their way like designing classes with multiple inheritance--sure, it means you have to rethink your problem, or you may have to type a bit more for a given problem, but I think deep down the person just wants to be different.

Scala building off of Java's success
For many tasks, Java is everything I need it to be

The built-in packaging is much better than many other languages. Those who refer to it as "jar hell" are just bitter C++ developers
It is a relatively fast language. Java is usually not at the top on many language performance benchmarks, but it often comes as a close second.
Java comes with some great libraries. Some have gone as far as to criticize Java for having too many libraries, but these are just bitter C++ developers. It's not like one library is obscuring another by popularity. If I need java networking, an image library isn't going to throw me off the trail to find it
It has tons of examples. I can't even count how many times I want to do some mundane task and a google takes me to an EXACT example in the java almanac

Now, as much as I like Java, it will never displace all the other tools in my toolbox. It's just a really handy tool I'm glad to have there. Yet despite all the bonuses of Java as a language, there were always some features I didn't need or know I wanted, but when I found Scala, it literally opened my eyes. Well, maybe not literally...

Adding some nice features
It's hard to summarize from a global perspective why I enjoy Scala, so here are a few small features that stood out to me.

Scala compiles to java byte code, so it has access to all java libraries ever written. Java code can even use compiled scala code
In many tests I've seen, it is comparatively fast to java
Scala allows function passing, but in a better way than python. An entire function block can be written inside a function call, which is a lot more powerful than python's lambda
Fun match ability, which many refer to as a switch statement on steroids. I recently learned it is an easy way to do type checking
Syntax-supported singleton objects, lazy evaluation of members, ...
The package system syntax is more flexible than java, where multiple public classes can be in the same file. I believe even several classes from different packages can be stored in the same file
Tuples! I never appreciated tuples until I started working in python. Going back to java and having to write a separate class just to return two or three values is incredibly frustrating. Java wants them; Scala has them
Scala is strongly-typed. Some people may loathe this, but I actually prefer it. When writing difficult code, I have never met a developer whose bottleneck is having to decide what type a variable should be. It's writing code the compiler can heavily optimize, which is easier in a strongly-typed language and shows a lot of the problems at compile time instead of run time

A note on syntax
One of the Scala complaints I feel I must address is the syntax. Some people would have preferred Scala to have a C-like syntax like so many other popular languages. Now I myself also look at a language and sometimes cringe at the lack of curly-brace-separated blocks or not passing functions with parenthesis, but Scala is actually very simple to get used to. Here are a few little differences that come to my head.


object SingletonThing {
   def display(name:String) { 
      println("I'm ready to work")
      println("Thank you for calling me, " + name)
   }
}

Here's a singleton object. It's very similar to the static methods one would put inside a class in java. To make a singleton, just use the object keyword instead of class. Also functions begin with the keyword def. I was adamantly resistant to this syntax for about ten minutes. Also, parameter strings reverse the C++ order of types and variables. I actually prefer this order now.


class GiveMeAFunction(someNumber:int) {
   println("This is part of the GiveMeAFunction constructor")
   val anotherNumber = someNumber + 5

   def doSomethingWithTheNumbers(someFunctionYouGiveMe:(int,int) => Unit) {
      someFunctionYouGiveMe(someNumber, anotherNumber)
   }
}

This example gives a few more insights into scala basics. First, scala classes are declared with a default constructor parameter string and its constructor code trickles into the body. It is possible to have secondary constructors, but I haven't needed them yet.

Second, you'll notice the val keyword with member declared. The two main ways to store a reference is with val meaning that that value will remain constant, and var meaning it is a variable. Using val supposedly allows the compiler to make certain optimizations, but it is more useful as a quick way to not accidentally mess up the value you have stored in it. This syntax is somewhere in between C++ and python. You can declare a value as variable or constant like C++, yet you don't have to manually retype the type similar to python. I consider Scala's implementation superior to python's as once you declare a variable, it will remain that type where python will let you put whatever you want into it at any time. This has been a headache for me when coding in python and I'll accidentally put a function into a variable instead the function's return value, which it won't complain about until somewhere later in execution.

And lastly is the function passing. I created a method which takes a function someFunctionYouGiveMe, which has to take two integers as parameters with Unit (means void) return type. I can then call that function or save it off to be used later. I have grown to love this syntax.

Other than that, there are only minor differences to Java. if statements must be on the same line as their code if one doesn't used a code block. Semi-colons aren't needed unless you really want to put two commands on the same line. Also, importing is a little more robust than Java.

Scala is what Java should have been
I encourage any person who enjoys Java or wants a little experience to toy around in Scala. It's a functional/object-oriented hybrid that has been a really fun transition from Java.

A question I might be asked is if Scala is really so cool, why would I ever use Java again? Well, the only reason I use Java now is to take advantage of Netbean's GUI-building forms. Other than that, I will probably use Scala for everything else. Some may consider Scala a fad, but I think with it's added features and friendly play with the Java language, it will be around as long as the JVM will be.

Ray Tracing Simpler than Rasterizing?

2009-04-27T13:27:00.000-07:00

In one short word... depends.

I would definitely agree that someone can sit down and bust out a simple ray tracer. When I was learning python, I hacked a 500-line script to render a simple scene. It has shadows, reflective materials, and a couple of primitives that would have to be discretized into triangles to render with a rasterizer. The only real library I used was an image library to actually put the image into a window.

For handling reflections, I just reflect the ray direction off the surface and send it out again
When shading something, I fire a ray towards the light source and if I hit something before I get there, I shadow the surface
I added a procedural checker material with only a few lines of code based on the surface position

In my opinion, it's some pretty simple code to implement these rather significant features. If I wanted to add more complicated features like shade trees, it would have been a relatively simple addition. Not only was this script straight forward, but I implemented it right off the top of my head. I don't have the best of memory, so I'd like to reinforce these concepts are quite intuitive to remember.

Simple python ray tracer featuring procedural shading, Lambertian and reflective materials, and simple shadows

(source code)

Same work with a rasterizer
Now, let's imagine that I had to write the same kind of functionality in a simple scanline rasterizer.

the procedural geometry is out--both the plane and the sphere have to be broken up into triangles, which isn't complicated, but surely not as elegant as some vector algebra
I would need to implement or find a matrix library to handle all my projections, and since I don't have the projection matrix memorized, I'd need to go get a reference of that
I would also need to implement the actual scanline algorithm to sweep through these polygons and implement a simple depth map
For shadows, I'd need to render a shadow map making sure the objects casting the shadows are in the light frustum
For reflections, I'd have to render an environment map, which would involve texture lookups and alignments, etc.
The procedural checker material would probably be the easiest thing to implement, but I would have to interpolate the vertex attributes to the different pixels

I certainly can't elegantly fit all that in under 500 lines of code. It's pretty evident that implementing a few basic visual effects is obviously much simpler with ray tracing.

Where is Rasterization Simpler?
Ray tracing models light transport in a very physically-realistic manner. It handles pretty much any "effect" rasterization can do, but it comes at a big cost--mostly performance. Most ray tracing research currently is all about making the algorithm faster, which requires some very complex code to be written.

First, ray tracing pretty much requires the entire the scene including textures to fit into local memory. For example, if you fire a ray into the scene above and it hits the ball, that ball needs to know about the plane below it and the ball to the left of it to do a reflection. That's simple enough in this case, but what happens if your scene is five gigabytes and you have four gigabytes of RAM? You have to go through the incredibly slow process of getting that primitive from the hard drive and load it into memory. That's a ridiculously slow. And the very next ray may require another hard drive swap if it hits something not in memory.

One easy solution is to break your scene up into manageable layers and composite them, but then you have to start keeping track of what layer needs what. Like if you have a lake reflecting the far off mountains, both need to be in the same layer.

What's with these acceleration structures?
And what of these acceleration structures? Ray tracing is often touted as being able to push more geometry than rasterization as an acceleration structure typically allows the ray to prune large groups of primitives and avoid costly intersections. That's certainly nice if you happen to have one, but where do these structures come from? You build it yourself! And if you happen to be playing a game that requires any kind of deforming animation (almost any 3D game now a days), you have to rebuild these structures every frame.

Despite the research in this field, it's still expensive to maintain them as the scene changes. State of the Art in Ray Tracing Animated Scenes discusses some of the more recent techniques to speed up this process, but as Dr. Wald says, "There's no silver bullet.". You have to pick which acceleration structure to use in a given situation, and then you have to efficiently implement them.

With a rasterizer, you have to linearly go through your entire list of geometry. But if we're animating and deforming that geometry anyway, that's fine. With a ray tracer, animation means having to rebuild your acceleration structures. Why does ray tracing make animation so complicated when it should be so simple?

Ray Tracing Incoherency
Ray tracing is inherently incoherent in many ways. Firing a ray (or rays) through every pixel makes it difficult to know what object the renderer will want in the cache. For example, if one pixel hits a blade of grass, that geometry needs to be loaded into the cache. If the very next pixel is another piece of geometry, that blade may need to be swapped out again. For visibility rays you can optimize this a little bit, but with secondary rays (the entire purpose of ray tracing) these rays are going all over the place. Many elaborate schemes have been developed to attack this problem, but it's a difficult property that comes with ray tracing and won't be solved any time soon.

A rasterizer is inherently coherent. When you load a gigabyte-sized model into RAM and bring its gigabyte of textures, you render the entire scene, you're working with that one model until you need the next one. When doing a texture lookup, there's a really good chance that chunk of texture is still in your cache since the pixel before probably used an adjacent texture lookup. And when this model is completely rendered, you can throw it away and move onto the next one and let the depth buffer take care of the overlaps. Doesn't the depth buffer rock?

Both are Complex
In general, there's nothing really simple about production-quality ray tracing. It basically trades "graphics hacks" for system optimization hacks. David Luebke said in Siggraph 2008, "Rasterization is fast, but needs cleverness to support complex visual effects. Ray tracing supports complex visual effects, but needs cleverness to be fast". Every scene is bottlenecked by time and trying to get ray tracing working in that time isn't always "simple".

nVidia's Interactive Ray Tracing with CUDA presentation

Rasterization: King of Anti-Aliasing?

2009-04-20T18:41:00.000-07:00

With the ongoing marketing of interactive ray tracing, I have continued to evaluate why rasterization will continue to be the dominant rendering method in games for quite some time. Ray tracing is considered by many as the end-all-be-all in computer graphics and some people seem to simply turn their brain off when it comes time to discuss its disadvantages. While conversing with an old colleague on that note, I realized I've never met a rasterization fanatic that insists everything has to be rasterized. Wouldn't it make more since to use them in areas they excelled in? As you read the next part, keep telling yourself rasterization still dominates the movie industry for good reasons and why those same principles apply in games.

Rasterization: King (or Queen) of Anti-Aliasing
It's pretty much undisputed (to sane individuals) that rasterization trumps ray tracing in terms of anti-aliasing. When Pixar's REYES renderer was being developed, one of their primary goals was providing high-quality anti-aliasing. This is one of rasterization's biggest advantages and one of the principal reasons off-line renderers still use rasterization for visibility rays. This has to do with the basic difference between ray tracers and rasterizes. With a ray tracer, one ray is fired per pixel and an intersection is computed for that ray. With anti-aliasing, more rays are fired into the scene per pixel. Thus if you want n samples, you fire n rays and do n intersections. These intersections are in 3D and are relatively expensive to compute. Rasterization, on the other hand, does a lot of work to get a primitive onto the screen. Once it's there, however, it can be sampled efficiently in 2D. So, rasterizers project geometry into 2D, and we'd like to sample in 2D since we're making a 2D image anyways. How convenient.

Once the primitive is on the screen, rasterizers can crank out the samples

Imagine a pixel on screen as you see above and one desires to perform nine samples instead of one to provide a more alias-free image. With ray tracing, each sample is an expensive intersection test. With rasterization, the renderer simply has to decide, "Does this sample lie inside the primitive or outside?" Hrmm, which one seems simpler? That that may seem trite since a computer is doing all the work, but it's the difference between solving a complex 3D intersection or a 2D region test. With ray tracing, firing n-times more rays is n-times slower. With rasterization, the brunt of the work is getting it on the screen. Once it's projected into 2D, samples are dirt cheap.

Who cares about anti-aliasing?
The topic of anti-aliasing certainly isn't sexy. It doesn't require secondary rays, funky texture maps, or any complex data structure. It's usually just more work. But it's one thing we haven't seen really pushed on GPUs--more settled on. A modern video card can do 16x full screen anti-aliasing and certainly could do much more.

Look at the image below. There's nothing really complicated in this scene. Certainly nothing that would require a ray tracer--mirrored reflections, simple smoke, some large textures, and a lot of little details. For all I know this image could have been ray traced--probably considering every modeler comes with some kind of ray tracer--but it screams for a rasterizer. You'll see games soon turning this stuff out in real time.

Anti-aliasing in games
With production studios sometimes requiring more than 64x samples per pixel, it's no wonder why companies are still rasterizing away. With current graphics cards easily performing 8x sampling per pixel while ray tracers chug away on beastly machines to compete, it would take very little for GPUs to flex their anti-aliasing muscle with even more samples. Anti-aliasing right now is pretty good and it's only getting better. Movie quality anti-aliasing in a game? Woo hoo!

PC to PS3 (Little Big Planet, Orange Box, etc.)

2008-12-28T22:47:00.000-08:00

Accepting console gaming
I have run Linux for several years now. It is a great operating system--yeah, I know it's really a kernel. I can always brag to my Windows and Mac friends of the ease of pulling down development libraries, packages, and files within seconds without having to scour the web.

I am a gamer, however, and have always wanted to play games without any hassle; to own a game and have everything just work. WINE has come a long way and has run World of Warcraft for me just fine, but with many other games I'm forced to tweak settings, use sub-par graphics, or worst-case scenario boot into Windows. To solve my woe, I decided to get a console. Hence, the PS3 sitting on my cabinet. I'm also looking forward to buying used games at discount, which is pretty much unavailable for PC gamers.

Configuring the PS3
Having not owned a console since the Sega Genesis--I had Resident Evil 4 and a Gamecube for a few months--I've fallen a little behind on the console world. The PS3 video snapped into my monitor via HDMI and I plugged the component audio cables into an old surround sound receiver. On starting the system, I passed through a brief configuration menu. One screen asked, "Do you want video and audio to go through HDMI?". Well, technically no, I just want HDMI for the video. So I answered no and my screen went black. I restarted the PS3 and answered yes to get video and setup audio afterwards, but I thought it was a funny question to ask if you're going to make a user's screen go black.

The PS3 menu is pretty sleek. It's a long horizontal bar of menus, where each focused menu will display vertical submenus of options. It works well and although I got used to it quickly, I don't see it as replacing a typical vertical menu.

Pleasant graphics
Both the PS3 and XBox 360 have had many consumer complaints in reference to the resolution many games and videos run at. For example, a game might render at 720p and be stretched to 1080 on the actual display. Although this is noticeable, all the games and videos that do it still look decent.

I had a chance to play a few demos and realized the incredible difference in graphical quality between video games. The aliasing in Mirror's Edge, for example, is horrible. The game looks well enough and has cool-colored art direction, but I can't help wonder if they couldn't at least do some post-process anti-aliasing. I've heard Microsoft actually has a stricter policy on anti-aliasing, but I can't reference that. I have been having fun with features and like having such quick access to all the different playable demos. It has been a lot of fun to download these demos and see if they're worthy of my wish list.

Orange Box
I enjoyed Half-Life 2 and always wanted to see how the first and second episodes turned out. The graphics are starting to show their age and the textures appear a bit blander than I'm used to compared to my PC. I'm still surprised how bad the loading times are in this game. Dying can take what feels like a minute to reload a level even if I died a few feet from the last load. What is the system paging in and out? Portal is a refreshing change. It satisfies that little first-person-shooter-puzzle-genre craving I never knew I had.

Although I haven't gotten into Team Fortress 2 to its full degree, I have seen it in action and have been very impressed with the graphics this game puts out. Some people were disappointed that Valve didn't attempt a realistic rendering system like everyone else in the industry. Their loss, I guess, because the game looks great. They have a great presentation, Illustrative Rendering in Team Fortress 2, that really showcases the art direction to make such a great looking game. Here's the high-quality video. If you like art direction or new shader designs, I highly recommend reading their slides and technical article.

Ratchet and Clank: Tools of Destruction
I played parts of the full version at a friend's house and downloaded the demo on my home machine. This is one the best looking games I have ever seen. The animations are smooth, the palettes are nicely colored, and everything is supremely sharp. The draw distances are incredible. Insomniac does Playstation exclusives and has always done a great job pushing a system. It also handles really well and is just fun to whack things with a wrench. I have included a couple screenshots stolen from Insomniac's site. The game looks even better in motion.

Folklore
This game got polar reviews with reviewers conflicted between its poor gameplay and great art direction. The game features about three art styles sometimes jumping between 2D and 3D cutscenes and looks great. It's a unique genre, but the first "boss battle" had me constantly fighting with the camera just to keep the enemy on my screen. I stopped after completing that section fearing the rest of the game would include the same tedious and frustrating camera coordination.

Playstation Home
Playstation Home got terrible reviews days before I received my PS3. I wasn't excited to enter this online world, so I was ambivalent to these postings. I was a little curious though, and gave it a quick pass through. I can add to other statements that there is no reason why anyone should use Playstation Home.

After a boring session of creating a customizable character, I ran around the courtyard waiting for other characters' skins to load on my machine while an empty shell of a person modeled their movements. Moving into new buildings required additional downloads. While I realize this happens only once, it is still annoying for the first visit to this online world.

Entering the theater, I sat down in an available chair and waited for the video to play. Many people were standing up in front of the screen talking to each other, while others sitting in the audience with me were calling those in front to stop being duchebags and sit down. I realized then that Playstation Home is the 3D visualization of all the people on the internet I try to avoid put in the same room as me.

There is nothing redeeming about it and although it's in beta, I can see no reason for anyone to use it. I believe a product should enter beta to work out bugs and get customers excited, but I believe most people like me will get a glance at it be extremely reluctant to return. Home might one day be a really excellent product, but it's going to take some extreme makeovers to make it such.

Little Big Planet
I have heard complaints about this game lacking game and being more of a tech demo. I must say that this game is amazing. I have always enjoyed platformers, and this game is a great platformer by itself. It features a zany story, where players can pass through levels in coop (either offline or online) with up to three others. Most levels can be completed alone, but it's funner to play with a friend(s).

The graphics looks sharp and feature crisp textures, HDR effects like bloom, and decent camera work. Every once and a while the camera will zoom too far in or out, but it's tolerable most of the time. Smoke and fire effects aren't perfect, but they're pleasant to watch.

The gameplay implements a simple jump and grab mechanic so the controls are easy to master. Like most platformers, the characters are required to do a lot of jumping, but this game includes a simple grab mechanic where the player can grab certain objects if they have a "grab-able" material like sponge instead of stone. This is used for hanging, swinging, pulling boxes and levers, etc. There's also a depth or layer component where players can move closer or farther from the camera. This is usually done automatically such that a player jumping from a depth of say 3 will naturally move forward to land on a platform of depth 2. The mechanic isn't perfect and sometimes causes problems (like totally unfair deaths) but is forgivable since it generally works well.

The gameplay is somewhat forgiving. There are frequent save points littered throughout the game that allow players to restart there after dying--this only works a few times before the save point runs out of lives and the players must restart the level. Also, objects that can kill the player by squishing or burning him/her usually give the player the benefit of the doubt by squeezing him/her through the crack or lightly singeing the player.

The real innovation of Little Big Planet is the excellent use of physics in the game. Each object has its own material with corresponding properties like friction coefficient, mass, texture, etc. It is fun to see your avatar catapulted over a wall or balancing on a teeter-totter-style platform.

The best thing about LBP is the level design. The game has been in production for quite some and the developers have mastered the engine creating many beautiful and crazy levels. I have seen almost every non-combative platforming mechanic put into these levels as well as new components that add new challegnes using physics, requiring teamwork with cooperative players, and just some new creative puzzles. Some levels require two, three, or even four players to pass certain puzzles. These are usually optional off-the-route treks to obtain additional collectibles.

It's hard to find good cooperative games these days so it's gratifying to see one that has really done such a great job nailing so many features. I haven't any gotten to the level editor, but it's on the to-do list. I can't imagine a video-game playing PS3 owner not purchasing this game unless they adamantly hate platformers.

Conclusion
My first few days using a console have been very satisfying. That feeling of running a game I own and not having to fight the system to get it to play is most pleasant and I urge other Linux users to consider having a separate machine like the PS3 to handle most of the their gaming needs. It's also a great Bluray player.

Ray Tracing Basics

2008-12-11T13:41:00.000-08:00

Dr. Steve Parker, who's academic team has done much to advance the field of ray tracing--specifically interactive ray tracing has allowed me host his lecture slides on my blog. Dr. Parker left the University of Utah earlier this year with Dr. Peter Shirley and several students to join nVidia in the hopes to produce high-quality, interactive ray tracing for consumers. Some have sourced Dr. Parker as writing the first "interactive" ray tracer, which he implemented years ago on some SGI computers.

These slides are taken from his CS 6620 - Introduction to Computer Graphics II course. It was basically all about writing fast and efficient ray tracers. The slides contain a lot of C++, but start with basic vector math. The slides have been compressed by me using Multivalent so they're quite a bit smaller than the originals.

The first lesson is a typical introduction to the course with pictures of ray-traced images and why ray tracing is useful. Those wishing to skip these details can probably jump into the second slide. They also include student project images including mine--the chess set. Most of these competition images lost a lot of quality for some reason--even uncompressed. You can see my image in an earlier post to see its original size and quality.

Also, if you use these slides, please keep the reference to Dr. Parker and his course.
Lesson 01 - Introduction to Ray Tracing
Lesson 02 - Geometry for Graphics
Lesson 03 - The Ray Tracing Algorithm
Lesson 04 - Ray Tracing Software
Lesson 05 - Ray Tracing Software
Lesson 06 - Ray-Object Intersections
Lesson 07 - Triangles and Materials
Lesson 08 - Materials
Lesson 09 - Materials II
Lesson 10 - Materials II
Lesson 11 - Materials
Lesson 12 - Heightfields
Lesson 13 - Sampling I
Lesson 14 - Sampling II
Lesson 15 - Color Theory
Lesson 16 - Texturing I
Lesson 17 - Texturing II
Lesson 18 - Displacement, Bump, and Volumes
Lesson 19 - Acceleration Structures
Lesson 20 - Acceleration Structures II
Lesson 21 - Acceleration Structures III
Lesson 22 - Acceleration Structures 4 Instances
Lesson 23 - Monte Carlo I
Lesson 24 - Monte Carlo II
Lesson 25 - Monte Carlo III

Language Shootout

2008-12-11T10:55:00.001-08:00

I program quite a bit in my free time on various projects. I try to make sure I'm using the right tool for the job (quote the hammer and screw analogy here). Despite the range of programming tasks I've undertaken, I have only a handful of languages I use frequently: C\C++, Java, Python, and PHP. I like all these languages, but I try to make sure I choose the right one for the task. While sometimes I have to use a specific one when I absolutely need a 3rd party library, I have a few flexible ideas of when to use a given language.

C\C++ were the first two languages I learned, and they can do quite a bit. I usually choose this language when I absolutely need the fastest option available and I have the time to do the optimizations necessary to make it faster than Java--like SIMD operations.

I find Java to be a great prototyping language. By prototyping, I do not mean a prototype-based language, but a language that I can quickly develop a prototype for an idea I am playing around with. Java comes with a good GUI library, is faster than scripting languages, and has a good range of libraries to work with. I always hated doing something in C++ and realizing I needed to go hunt down a image library just to load a PNG file.

Despite what some people say, it is fast and has even beaten C\C++ on occasions--mostly where there are a lot of allocations and deallocations and the program isn't starting up and closing frequently. The Computer Language Benchmarks Game provides some performance analysis of several tests against many languages and Java is usually only ~10% slower. It is faster in some cases such as their binary-tree demo. I mentioned Chris Kulla's Sunflow ray tracer earlier, which is written in Java. He states his would be 20% faster if ported to C++, but I think his implementation is currently faster than most people's ray tracers for providing similar features.

I don't use Python much, but it's usually great for writing little scripts. I prefer this to Java as it provides faster programming for simple tasks. Although it is quite a bit slower than Java, it has a much faster init time so if I'm running the script frequently, it beats loading Java's large VM every time. Maybe that's a moot point.

PHP is only useful for writing web applications. Although this heavily limits its usefulness, nothing comes close to PHP's simplicity, ability to integrate with HTML, and huge list of useful functions. I always use PHP for anything related to dynamic web content.

I'm sure many will disagree with my criteria for languages. Some people insist ADA is the most useful language (like the creator of ADA). To each his own, but these languages have been good to me.

Reply to Comment #1
I received a comment on the "The Computer Language Benchmarks Game" link where I mentioned the test where Java beat C\C++ telling me to "note" that the Java program used a large heap, only beat C++ on one architecture, and that other C++ implementations were tested that were faster.

Language benchmarks will always lead to arguments about implementations, architectures, etc. I do not think Java is always faster than C++. I do not think Java is as fast as C++. But I do think they can be close. My point was Java beat C++ in one benchmark so to say "Java is slower" is a little unfair.

As I stated earlier, you can always make C++ faster than Java if you have the time and if speed is a concern. Chris Kulla's Sunflow ray tracer is fast--not fast for a Java ray tracer but fast for a ray tracer. I'm sure it could be much faster if he switched to C\C++, but he said it allowed faster development time at the cost of maybe 20% performance. To me, I'd rather take a performance hit like that if I had more time to make it a more feature-rich application.

Dreamworks Interview

2008-12-10T19:12:00.000-08:00

After being on the job hunt a certain amount of time and seeing my carefully chosen list of possible employers start to dwindle, I started sending on tens of unsolicited resumes hoping someone would bite. One such company was Dreamworks Animation.

After putting together an impressive resume and cover that fit me as their ideal candidate, I sent it off. Seconds later, I received an automated response "The following addresses had permanent fatal errors". That sounded really bad. Not only were the errors fatal, but they were permanent and would remain so for the rest of time. I sent off another e-mail to the webmaster asking if my application was in fact received. That responded with another automated response claiming the mail server itself was down. I took it as a sign that working at this company was not meant to be. I received a phone call a few days later.

The conversation was typical for a first call--verified my information, my interests, what job they were trying to fill. Even though I applied for a programming position, they wanted to interview me for technical director. Since it was an interview, I accepted.

The Dreamworks interview process was actually quite simple for me. They scheduled a video conference and sent me down to a local FedEx Kinkos. In a large conference room filled only by myself and a TV/camera stand, I sat at the end of the table while I was grilled by Dreamworks employees.

The employees interviewed me in pairs or teams. The first team was "Team Oddball" as they called it, which asked trivia-like questions. Unlike my interviews at Intel, they actually remembered the answers to the trivia questions, which made the quiz a much more pleasant experience. One question, for example, was "If you have a three-gallon and a five-gallon bucket with unlimited water, how do you measure out four gallons?". The other questions ranged in difficulty. Most of them were pretty fun and allowed me to think and explain how I would do it.

The next pair asked more technical questions related to graphics, but it was a pretty simple interview. Subjects ranged from 2D intersections to level-of-detail. Every person that interviewed me was a technical director, which I really appreciated. I used the Q & A time to ask them about a typical day, what they liked, challenges, etc.

I was supposed to have an interview with the director of technical directors, Mark McGuire, who oversees all TDs on all movies, but he wasn't available that day. To make up for it, he called me the next day. He mostly wanted to make sure, as everyone had, that I had a very clear idea of what this position entailed. I always found that a difficult question to answer as I don't think I can ever understand a position unless it's a common profession or I spend a day doing it.

A few days later I received an actual offer from the company. The hiring manager explained compensation, the benefits like provided breakfast and lunch, etc. He worked hard to sell me on it. Even though I asked for more time to complete the hiring process with some other companies I was interviewing with at the time, I ended up accepting the offer. I start on the 5th of January. Although I didn't want to live in California, I'm excited to start at what appears to be a fun and dynamic company. By the way, if you haven't seen Kung Fu Panda, the humor alone sells it. The art direction is just more bang for your buck.

FBO Multisampling

2008-11-20T15:46:00.000-08:00

I was using pBuffers in OpenGL when FBOs were coming around. Moving to FBOs seemed like a huge increase in simplicity and functionality. I started using them all the time. However, I have always wanted to add a little bit of anti-aliasing, but never quite knew how.

Sometimes googling for OpenGL functions returns pages of garbage and spec files don't always provide clear examples to use. Well, I have found a web page of someone who has had the same problems and has posted his solution including the setup, blitting, etc.

Normally I wouldn't post a blog on a code snippet, but I think this deserves another link so more people will run across this little OpenGL gem.

Thanks, Stefan!

(click here) for multisampling in an FBO.

Sunflow - A Java ray tracer

2008-11-07T07:50:00.000-08:00

After all the posts and articles I've written on why I don't think interactive ray tracing is the future of games, I have always said ray tracing has its place. One ray tracer I have become acquainted with a bit ago was Sunflow, a really neat Java ray tracer written by Chris Kulla.

Ajax model rendered in Sunflow by Tartiflette

First of all, this guy knows ray tracing. He's a programmer at Sony Imageworks and has created a very robust ray tracer with a very intuitive code base. Some may wonder why someone would write a ray tracer in Java when C++ is clearly faster. It's true, most C++ code runs faster than Java if its written by a competent programmer (which he is), and even Chris admits this. However, he notes that in his experience C++ is only about 20% faster and for a non-interactive renderer, this isn't much of an issue. Especially since writing it in Java would make network rendering much simpler (see project Helios). If you are familiar with ray tracers, you can open up the source code and easily navigate around and see what is going on.

The Sunflow project is a couple years old now and has a host of features including caustics, normal mapping, photon mapping, multi-threading, and a shader API that allows you to write your own materials in Java. Many people have provided exporters from Maya, Blender, XSI, and a few other modeling programs.

Although it's only version 0.07.2, it is stable and supports many features that most artists will be satisfied with. So check out the website or at least look at the gallery.

Pixar Interview

2008-10-02T08:42:00.000-07:00

Everyone knows Pixar would be a great place to work. At Siggraph it seemed aspiring animators and modelers were lining up with their reels and portfolios eager for a internship or residency at such a production house.

Yesterday I went up to Seattle to interview with the Pixar team in charge of the Renderman products. This office does not handle production. Instead it deals with the actual technology that the artists use for rendering, shading, and distributing the work among computers.

Having spent eight years in the northwest, it was a great feeling to be back. I had a couple of hours to walk around downtown Seattle before my interview. If you've never been to Seattle, it's a great city. The cityscape has a huge variety of architecture; each one has a unique and pleasing style. Pixar's office is currently located in Smith Tower, the oldest skyscraper in Seattle. For a moment I thought I had the wrong building until I asked the clerk. Upon entering, you walk down a narrow hall with an array of shiny golden elevators to your right. Stepping into these golden boxes, a liftman manually shuts the door and turns a lever for a given level. The Pixar office itself was fronted by a reddish office door with the old-style blurry glass and PIXAR in big black letters like you'd see in a detective's office. The door was cracked open slightly and I could feel the awesomeness vibes pulsating from the interior. How do people work in such extreme conditions?

The interview process was more involved than I expected. The actual interviews lasted about 3 hours. During that time, developers, engineers, prospective bosses, etc. were shuffled in and out. The interviews were quite casual and they seemed to focus more on my experience than on-the-fly technical quizzes you hear about at some firms. Most of the technical questions related to something on my resume to the regard of "Why did you do it that way?". The developers came in pairs of two and I had the chance to meet some really cool people.

One pair of developers that came in were Per H. Christensen and George Harker. I quoted something I heard from a ray tracing symposium a few years ago in reference to Renderman's code length. Per replied, "I said that". I felt a little silly. Maybe he was flattered. I also told them I've played around with Pixie, a Renderman-compliant renderer. I felt even sillier after George replied, "Yeah, I wrote that." Oops again. Need to do a better job keeping track of these things. After arriving back in Salt Lake and doing some homework, I realized I had actually heard Per's presentation at Siggraph on Practical Global Illumination with Irradiance Caching. Triple oops. I need to pay more attention to people who may one day interview me. They could be anywhere... The entire team seemed very talented.

After the interviews, I returned to the streets of Seattle. They recommended a good dinner location at a nearby pub. Brian Saunders told me I could get sweet potato fries if I asked for them. Out of curiosity I did. Sadly, a break down in communication happened and I was rendered sweet-potato fryless, so to speak. I sat at the bar and ordered, to which the bartender turned to a red head and said, "One burger and sweet potato fries". She asked how to cook the meat and went off. Thirty minutes later, I was getting anxious to get to the airport and still no food. I asked the red head the status of my burger. After coming back she said, "The guy you talked to didn't actually order it, so we'll give you a burger that was going to someone else". I was thinking, "Didn't he tell you to do it?". I didn't say anything. The burger and normal fries arrived and were delicious, so all turned out well. If I get the job or happen to return to Seattle, I'll have to go back and try the sweet potato fries. If so, expect a blog post.

Job Hunting

2008-09-28T07:11:00.001-07:00

I'm finally leaving academia and searching for a career that provides satisfaction and a real salary. I've applied to a lot of big names and gotten fairly decent results.

Pixar has interviewed me over the phone and is flying me out next week to their Seattle Renderman team. Although I don't have a ton of experience in film production, I'm hoping any job they offer me will lead to a full-time development position on one of their rendering products. They didn't ask any technical interview questions besides what I've done, so I expect I'll get some of that face to face.

Intel's Visual Computing Group is flying me out to Hillsboro, OR next week for an interview on their driver development team for Larrabee GPU designing the DirectX driver. I was under the impression that most of this work had been done considering that they provided performance benchmarks for many games like Gears of War in their paper. The interviewer said he couldn't specify how complete the implementation was when I asked him, he did say that with Microsoft's active development of the DirectX API, there will always be new additions to the driver. I've heard working at Intel can be a little intense and they push there employees relatively hard, a couple of people who have worked there say that they actually like that about Intel. I don't know DirectX very well, but from what I understand, it's a lot easier for driver development than OpenGL for several reasons. Hrmm, I guess that means I won't be working on a Linux/FreeBSD machine...

I also had a phone interview with a couple of developers from Google. I applied to Google without a clear idea what I'd be doing there and just assuming it would be a great place to work. The first developer to call me was Sean Pidgin, one of the project leads for Pidgin (formerly GAIM) and the project head for Google Talk. They started out talking a little about my background, but did have several casual technical questions about threading and networking as well as some formal coding I did over a Google Docs document we shared. I'm still not used to coding on the fly especially over the phone, but I think I did alright. I always get nervous when at the end they ask me, "Can this be more efficient?". Of course it can, but the first thing I say doesn't mean it's the best thing I can do. Can I writer talk out a scene with the same finesse he/she publishes a work? They asked questions about things like race conditions with threads, binary tree searches, etc. Like I said, I still don't have a clear idea what I'd do at Google given that there job descriptions require knowledge of everything, but in a way that's pretty cool.

In general I'm fairly content with the interviews I've been able to receive. I've only been looking for a couple weeks and already have a few flights scheduled for on-site interviews. We'll see where I finally end up.

State of Rasterization

2008-09-28T06:26:00.000-07:00

I was down at Siggraph when the new OpenGL 3.0 specification was released. I was excited for the OpenGL BoF later that week to see all the specified updates they had promised. Monday of that same week, I read a slashdot article that kind of broke the news to me that the original enhancements to the specification like the object model were butchered. I was a little shocked, but was sincerely hoping it was like many slashdot articles, where the commenters simply read the summary and didn't bother reading the article. I had some naive hope that the webmaster accidentally posted the old specification up using the new file name, but after scanning the entire specification, I can see that wasn't the case. Many people were angry that they were left in the dark so long about the drop in features and the news that Khronos would drop the ball like ARB has done. Although I think Khronos screwed up, I still think a much-needed object model will is still on the road map and through these frequent "updates", I can see more state-friendly API. nVidia already released a new extension that provides texture building with binding that texture. Even though it's just an extension, I hope to eventually see many other functions go down that road.

nvidia has done a good job supporting OpenGL in various ways including graphics demos, presentations, APIs, etc. Although I don't see much use with some of the new additions to the pipeline--nvidia itself has told developers NOT to use the geometry shader--I do like some of the things presented in this new API.

nvidia's slides on OpenGL features on the GeForce 8 architecture. I'm linking them straight from the nvidia page until they tell me I can't

One of the cooler additions to the rendering pipeline IMHO is the transform feedback buffer. Basically when you send vertex data down the pipeline and it gets transformed by various matrices in the vertex shader, you don't really have an idea of what those vertices actually get transformed to. You could do some GPGPU thing where you print the vertex information to the screen and read it back, but this is tedious to implement and debug. A better solution would just be to store these transformations in the rendering API. One of the pesky things about shadow volumes is you have to compute the edge silhouettes. This has been solved in a respect in "Shadow Volumes on Programmable Graphics Hardware" by Brabec et al., and now can be implemented trivially using this new transform feedback buffer. Other work has been down to use silhouettes to provide some effect, so I can see Brabec's implementation applied to a whole slew of visual effects that require light or camera silhouette information. In their presentation, they use the geometry shader for silhouette detection, which I think is a mistake. Much like Barnes and Noble dedicating a section to Vampire Romance might be considered a mistake. Maybe that's a stretch.

Another exciting extension is the EXT_direct_state_access. Although this isn't the "object model" many people were expecting, I believe this kind of extension will generally lead into the state-friendly programming model we all wanted. How many times have we not known the state of OpenGL coming into a given function and changing the state would possibly break the assumptions a proceeding function would have? Once again kudos to nvidia for a great support and presentations.

Rasterization versus Ray Tracing

2008-09-15T08:38:00.000-07:00

"Real-Time Ray Tracing: Holy Grail or Fool's Errand?" is an older article, but I think it's short, simple, and to the point, which you don't see every day. The author Dean Calver gives a very brief comparison of rasterization and ray tracing then summarizes some of the problems with ray tracing--specifically aliasing, dynamic scenes, and global illumination.

I've written about problems with dynamic scenes in the past. Although many people prefer ray tracing for its simplicity, it requires acceleration structures to run quickly. In David Luebke's presentation he made an excellent statement that I think described the rasterization-versus-ray-tracing debate rather well.

"Rasterization is fast, but needs cleverness to support complex visual effects. Ray tracing supports complex visual effects, but needs cleverness to be fast."

Another problem I think isn't discussed much is texture locality. Although I don't consider this as big of a problem for ray tracing as dynamic scenes, it's a performance penalty. The problem involves ray tracing being an image-based algorithm. If you shoot a ray into the scene and it hits a textured object, you need to fetch the texture into the cache. If the next pixel uses a different texture, a new texture chunk must be fetched. This is in contrast to an object-based technique, where adjacent fragments on the object usually use adjacent texels. A worst case scenario for ray traced scene might be tracing textured grass against a textured wall. Every couple of pixels, you'd need to refetch the another texture block. Although this is a generalization since caches are big and the entire texture doesn't need to be fetched, it's still an issue and today's textures are getting rather large. With rasterization, the wall would be drawn with the texture, then the grass would be drawn with the other possibly creating no duplicate cache misses. If you read the original REYES paper by Cook et al., you'll see that spend a good chunk of the paper talking about texture locality, because it can severely impact performance.

I think nvidia isn't concerned whether ray tracing takes over the rendering pipeline as long as it's done on the GPU. Luebke and Parker's presentation goal was to show what nvidia hardware could do, and allow developer to decide what was best for them. More options kind of thing. Although I didn't care too much for the ray tracing portion of the demo, I did think he had compelling screenshots of what rasterization is currently capable of rendering.

Both presentations conclude that a hybrid algorithm is the future. Calver likes the idea of rasterizing the visible portion of the screen and using that information to ray trace secondary rays. Frankly, I don't think this idea is very promising. Rasterization is great for the visible rendering of the screen, but if you're doing secondary rays, you'll need the acceleration structures that you didn't want to build in the first place. If this wasn't an issue problem, then you could just ray trace everything. Ray tracing is very fast for primary rays if the acceleration structures are already built. You have tons of coherency assumptions. David Luebke's idea seems more plausible, where scene assets are sorted into ray-traced and rasterized passes. You can rasterize animated objects like people without having to build an acceleration structure and ray trace other objects that require effects reflections. But once again, what are you intersecting you're secondary rays with? In my diagram below, I have a sample scene using a ray-traced reflective sphere and a rasterized animated person. It's crude, but I'm trying to give a simple example.

The ray-traced sphere needs an updated acceleration structure to perform accurate reflections on the animated, rasterized figure

You rasterize the person just like you would in current games. Then you ray trace the sphere. The ray hits the sphere and you want to calculate the intersection of it with the person. But the person doesn't have an acceleration structure because it's being animated. If we had the acceleration structure built, we would have just ray traced it. I'm trying to say that I don't see how ray tracing secondary rays will ever play nice with rasterized, dynamic geometry.

Jon Olick's presentation used ray casting for static geometry, which I think provides more immediate benefits. Most games already have special rendering techniques for static geometry like lightmaps for all the floors and walls, so having special rendering "cheats" for static geometry isn't new. Although this doesn't provide higher-order effects like ray tracing does, it will significantly increase geometric complexity of static portions of the scene. Furthermore, this technique is relatively easy to incorporate into existing pipelines at relatively no cost.

Although I still don't like the current marketing push towards ray tracing including Intel's, I am mildly excited for Intel's Larrabee. As long as it rasterizes competitively fast, it could allow developers to easily add new features and extensions to the pipeline faster than current GPU hardwares are able.

Oh, and though I don't have anything to say about the other presentations, kudos to nvidia for always doing a good job posting their presentations. I did see Sarah Tariq's hair presentation and think we're getting close to seeing scenes with characters with animated, beautiful, frothy, tangly, wavy, shiny hair. Check it out.

Siggraph 2008

2008-09-03T08:52:00.000-07:00

Well, I went to Siggraph for the first time. It was an interesting experience. The convention consisted mostly of presentations/lectures, an exhibition hall of company booths, and the "Art Festival".

The presentations were fairly interesting. Nothing earth-shattering. A saw a few random posters that showed some novel work. Blue Sky Studios gave an amazing presentation of the art direction creating Horton Hears a Who. I didn't see the movie when it came out. I guess Cat in the Hat left a bad taste in my mouth for Suess-movie conversions. However, this movie looked fantastic. The speaker discussed several artistic approaches to modeling a Suess-like world of asymmetric trees, heavy, blobby, saggy objects, and color palettes for different scenes. From the clips I saw the movie looked amazing and was pretty hilarious.

Jon Olick from id gave a really good presentation. He has done a lot of level-of-detail work on games like Ratchet and Clank: Tools of Destruction. Although I've never played the game, many reviews I've read have commented on the amazing draw distance Insomniac achieved. I believe some of the implementations involved geomorphing, which he discussed. Jon finished the talk discussing the sparse-voxel octree for static geometry that John Carmack has proposed. I must state this proposal is only for STATIC geometry as the octree isn't rebuilt dynamically. This question was raised at the presentation and Jon quickly stated he wasn't attempting to solve dynamic octree construction that everyone has been working on for years. Although it only works for static geometry, it should provide a big leap in geometry resolution at comparable storage or traditional triangular meshes--these sparse octrees can be streamed in by the amount of screen footprint supposedly allowing extremely detailed assets. Furthermore, it should be easily combined to current pipelines that raster dynamic geometry. And even though ray tracing nuts (not researchers--just enthusiasts) supposed that this was a huge step towards full ray tracing, this method only works for ray casting so one still needs things like shadow maps for global illumination effects (like shadows). Overall I thought he gave the best presentation--mind he actually gave a demo of the proposal, which makes it much more convincing.

Intel gave several presentations on the Larrabee architecture and how it will not suck. They repeatedly stated how they weren't showing any benchmarks since there's no product for another couple years, so it's hard for me to really get excited about it. Larry Seiler gave the first presentation even though he's not actually on the Larrabee architecture paper. Weird as it seems, the guy seemed very cool. I stopped him in the hallway to ask him a few questions. He set his bag down and started chatting away happily. Another time I saw him sitting in a corner with a couple of young geeks with their laptops flipped open asking him questions. For a mid-50s guy from Intel to just sit on the ground and field questions seemed pretty cool to me. Although I don't have a lot of confidence that Larrabee will be a competitive GPU, I thought they picked a great spokesman. He said he was chosen specifically for his past experience with GPU architectures.

nVidia gave its ray tracing demo of a car flying through the city. I saw it first hand sitting on the front row while my old professor Steve Parker explained the technology. Although I think he's brilliant programmer, I wasn't very impressed with the whole demo. The scene was a cityscape with a car driving through it. I've expressed my concerns with ray tracing in previous posts like problems with texture coherency. The demo had very bland textures and for running on four nvidia quadroplexes, it really wasn't very impressive visually. They even mentioned a "canyon" shader, which gave the buildings a more realistic look. From what he explained, the shader was a linear ramp from dark to light just how canyons are typically darker at the bottom. When a linear luminance ramp is a topic of interest in 2008, I think the demo has failed. They zoomed in on the headlamps to show 7 bounces of ray tracing, which I guess is really important, but to me it just looked very noisy. I know it got a lot of people excited, but with the hardware they were running it on, I'd have rather seen a rasterized scene running at 128x anti-aliasing and per-fragment environment mapping. The demo was basically glorified ray tracing with accurate reflections. If they want accurate reflections, why didn't they just implement Jen Krueger's GPU Rendering of Secondary Effects. Sure, 3rd or 4th bounces have less accuracy, but if you saw the demo, the tertiary rays really didn't contribute much to the image quality. Like I said, I'd rather have seen a rasterized demo running on that beastly hardware. The talk itself wasn't too bad. David Luebke talked about effects that developers are eager to use and how nVidia's working to provide them with it--things like better soft shadow, depth of field, caustics, etc.

The exhibition hall was comprised of animation/production schools, production companies, development booths from Autodesk, zBrush, a bunch of motion capture companies, etc. It was fairly exciting at first but lost its appeal after a day. The Art Festival was also pretty fun.

Not sure if I'll attend next year. I felt like most of the students there only wanted to hit Dreamworks and Pixar for job interviews. One animator even asked why a CS person was attending Siggraph. I was a little shocked, but was polite. It's in New Orleans next year, which just got hit by Gustav. I remember shoveling mud out of people's second story houses. Why can't they get rid of the levees and turn New Orleans into the Venice of the US? It's below sea level and building levees and watching them fail again and again is getting old. You're below sea level and the current system isn't working. Time for a change.

Opinion on Ray-Traced Video Games

2008-07-18T13:16:00.000-07:00

I've posted a brief commentary of what I feel about this hype mostly Intel is pushing about bringing ray tracing to video games. Although it's an interesting idea, I don't see it replacing rasterizing GPUs anytime in the near future for several reasons.

State of Ray Tracing (in Games)

First Place in Ray Tracing!

2008-03-12T17:13:00.000-07:00

Our ray tracing class ended with a ray tracing competition that any student could optionally enter. The only requirement was our ray tracer had to implement at least two Monte-Carlo techniques. I chose to implement soft shadows using multiple samples on a light sphere and embossed reflections.

Although my ray tracer wasn't the most technically superior, it won the top $100 prize judged by an independent panel of professors. I will probably spend the money on groceries for next week...

Ray Tracing - Project 10

2007-04-23T06:42:00.000-07:00

Design Choices
I decided to model a chess set for my image. All pieces in the scene are modeled with triangles except the board (a box) and the ominous red sphere. All the chess pieces were modeled using Blender by myself and exported to the OBJ format, for which I wrote a mesh parser.

The board is rendered using two different Perlin noises and rendered with soft shadows by displacing the light position using a spherical distribution and many samples per pixel. The chess pieces have the same two materials as the board, so I tried to place them on opposing colors so the Perlin noise wouldn't match up perfectly.

This project took me a long time (close to twenty hours, I imagine), mostly because I took so long trying to decide what scene I wanted. I decided to do a chess theme since it gave me a lot of control over how I wanted to lay it out, and I didn't want to do anything too terribly abstract (like a bunch of dragons staring at a heightfield). The final images took around 30 minutes to render using 25 samples per pixel.

Extra Credit
My second Monte Carlo effect was embossed reflections. This was added to materials using a Russian roulette method, where either the diffuse color or the reflected color would be calculated based on the ratio assigned between the two. The embossed reflections were generated by perturbing the normal over a uniform disk. The disk size determined the amount of blurriness.

I originally blended the two colors together, but that introduced a number of artifacts. Switching to the Russian roulette method, these dropped significantly, but I still see an occasional blue splotch. Also, the Russian roulette method looks horrible at low-sampling rates since every other pixel might have a different shading calculation.

This is my final rendered scene using soft shadows and embossed reflections. It took about forty minutes to run using 25 samples per pixel

Code:tracer.tar.bz2

Ray Tracing - Project 9

2007-04-11T22:32:00.000-07:00

Design Choices
To implement instancing, I created an instance class inherited from the Primitive class. This allowed a simple abstraction for adding groups and other objects and stuff. The preprocess function called the grid layout preprocess for every instance so I added a check to only preprocess once. I used a matrix and a vector to hold the translations and rotations and created to functions for rotating and translating.

This is a really stupid picture of the Stanford bunny rotated and translated around in a strange manner showing the transformations possible with the new instance class

I was feeling patriotic and made a giant bunny flag and just gave it three different colors based on a series of modulos. I was really bored

Code: project9.tar.bz2'

Ray Tracing - Project 8

2007-03-28T19:00:00.000-07:00

Design Choices
Most of the code modifications occurred in the Scene class. I chose to do this since it seemed logical that different scenes be rendered using different filters and samplings. Also, the Scene class is where the rays are created, so it was a simple change in code.

The code changes had two parts. One which allowed additional samples to be calculated at different points based on the filter, and another part of the code, which calculated the weight of each sampling. I chose the Gaussian filter to implement as it seemed simple and provide okay results, although not too much better then the actual triangle filter.

Rendered with 1 sample per pixel (no jittering)
The function provided in the homework assignment

A scene of random spheres and five different material types

Rendered with 9 samples per pixel with jittering and using the triangle filter
The function provided in the homework assignment

Rendered with 9 samples per pixel using a Gaussian filter

The function provided in the homework assignment

A scene of random spheres and five different material types

Code: project8.tar.bz2

Ray Tracing - Project 7

2007-03-16T18:35:00.000-07:00

Design Choices
For the design of the texture mappers, I followed a scheme similar to the one Dr. Parker recommended. I created a TexCoordMapper that provided a basic interface for grabbing texture coordinates. The base object class--from which all primitives are descended--were given a default coordinate mapper, which could be changed through the API.

Besides the coordinate mappers, three new materials were created--a checker material(which used two sub-materials assigned to it), a marble material, which used Perlin noise, and a image material. All three materials were implemented exactly as described in the slides.

Required Image

Creative Image - Triceratops by Rainbow (and sphere)

Extra Credit
For extra credit, I chose to add an additional procedural texture (I'm shooting for half extra-credit). This material (shown in the creative image) allows spectrums of color to be display for effects like rainbows.

Code:http://www.cs.utah.edu/~jstratto/project7.tar.bz2

Ray Tracing - Project 6

2007-03-07T22:49:00.000-08:00

Design Choices
I originally intended to do a BVH using an quad-tree, where the tree were recurse down to some arbitrary size. This gave me a strange bug (which I had to use for my original image). The algorithm itself seemed simple, but and for the small part of the bunny that it did render, it rendered rather quickly. Much faster than the 2.5 hour attempt without the acceleration structure.

I then tried a uniform grid, but had difficulty debugging it (I wasn't getting anything to the screen), mostly due the short amount of time I had left on the assignment.

I also tried a octree, which gave me similar results to the quad-tree, which makes me feel the bug lies somewhere in my bounding boxes or something.

Bugged Image-If you look really, really closely you can see the form of the bunny. From the part that rendered, it seemed to work effectively, but for everything else, it completely ignored it. It was probably something really small and I probably should have just debugged the quad-tree instead of attempting the other two

Required Image-Here's my final rendering. It took about 18 seconds, wihich was a lot faster than the 2.5 hour version.

Code:project6.tar.bz2

Ray Tracing - Project 5

2007-02-24T16:54:00.000-08:00

Design Choices
The three new material models were a dielectric, a phong, and a metal. All three shared specular properties so code was shared somewhat between them. All materials extended from a general material class which made used of extensive virtual functions to minimize the code base.

Required Image

Code:project5.tar

Ray Tracing - Project 3

2007-02-06T09:03:00.000-08:00

Design Choices
This assignment added implementation of several primitives including the box, disk, ring, and triangle. The Moller intersection was used to intersect the triangles, as it was the easiest to implement. Amy Miller's implementation was used to implement the box intersection. The new primitives were rendered using existing shaders and the normals were obvious to compute.

This is the default scene for Project 3 using the updated rendering

Creative Image
This scene uses two lights: a directional light and a point light. It features 200 triangles, 60 spheres in a double-helix, a box, and a plane

About this project
Time Required: 5 hours
Difficulty: Easy. Mostly just implementing intersection algorithms
Code: project3.tar

Ray Tracing - Project 2

2007-02-01T12:30:00.000-08:00

Design Choices
Building on the previous assignment, the renderer adds Lambertian shading and two-sided lighting. The material also casts shadow rays through the image, to give a simulated shadow effect. A base object class holds basic properties for subclasses to implement, which include a sphere and a plane. Another base class is for a material, which gives some basic functionality for coloring depending on the vector.

This is the default scene for Project 2 using the updated rendering

This is the same scene rendered from underneath the default plane. Although it appears bleak, it demonstrates lighting and shadows are correctly ignored and only ambient light is applied

Creative Image
This image was rendered using 1000 point lights to simulate soft shadows. It took over two hours to finish and shows the linear scaling of adding point lights to the scene

Extra Credit 1 - Directional Lights
This image was created using only a directional light instead of two point lights. Directional lights render slightly faster than directional lights since they do not have to compute the light vector (it's saved in the directional light object), and no distances have to calculated

About this project
Time Required: ~10 hours (very approximate)
Difficulty: Easy. Lots of typing and organizing
Code: project2.tar

Ray Tracing - Project 1

2007-01-24T22:39:00.000-08:00

This is the first project for Dr. Parker's Ray Tracing class.

Design Choices
I chose to do a progressive rendering breaking the image up into frames and sending the frames off to separate threads. I chose random tiles, because I felt they would give a better visualization of how the overall scene is rendering. I also liked the idea of using threads as I hope it will get me a bit of a performance boost later. I wanted a rendering style similar to Modo's renderer. I chose C++ because my last ray tracer was in Java (pictures in previous blogs) and was decently fast, but I wanted to do some fast C++.

This is my viewer as it is being rendered kind of how Modo renders (but not as pretty)

This is my completed image. I noticed on the assignment after I was done coding, that I didn't need to handle the depth of the objects

About this project
Time Required: ~15 hours (but I rewrote it many, many times... once for my laptop having the code on it and being in the shop, another for file corruption, etc...)
Difficulty: Not too bad. Lots of debugging since I wrote most of it without testing it, but I'm hoping later projects will be more incremental
Code: project1.tar

Image Synthesis - Project 14

2006-12-23T15:27:00.000-08:00

In Project 14, for my "cool effect" I implemented shade trees. Shade trees provide a procedural, modular workflow for determining a color at a given point based on various parameters similar to the ones needed in the Heyney-Greenstein Phase Function.

These shade trees allow simple modules to be built and combined in chains or branches. Some common shade trees provide basic shading effects like Phong shading, Lambertian shading, anisotropic shading, ramp shading, etc. Other modules allow combinations and filters to provide more complex images using these simple modules.

Below are a few different spheres using some shading modules...

A sphere shaded using the Heyney-Greenstein module

A sphere shaded using a ramp module. This module allows the colors to be colored based on certain points of interest

A sphere shaded using a texture module, where the theta and phi of the sphere are mapped from [0,1]x[0,1] on the texture

Here, a layered filter module with two shaders connected to it. It also uses another texture shader as a mask to determine which of these to shaders to use

These shade trees scale to as many levels as the effect requires. The final image at the bottom of this post shows an image using several modules. A Heyney-Greenstein module provides a shiny metallic surface. Another is a texture module to provide the metal surface. These modules must be combined in a combo filter separately from the rust so that the rust doesn't appear shiny. This combo filter is fed into a mask filter with the rust as it's other shader. A texture module is fed into the mask filter to use as the mask.

The sphere with just the metal texture

The sphere using the Heyney-Greenstein module

The sphere with just the rust texture

The sphere mapped using the mask texture

The final sphere using the entire shade tree described above. This gives the overall feel of the metal, while splotching rust on parts in a natural-looking splat

Image Synthesis - Project 12

2006-12-20T12:01:00.000-08:00

In Project 12, the Heyney-Greenstein Phase Function was implemented in the renderer. The Heyney-Greenstein Phase Function (HGPF) is an imperical formula to simulate diffuse and specular reflection for a variety of materials using only two parameters. This function uses these these two parameters stored in each object and takes the incidence angle as input. This provides a much greater flexibility for different materials than using the simpler Lambertian reflection.

Finding little data as to proper values, I rendered an image using a wide range of values. From the image generated, it appears a high g-value seems important to produce a good image. This component supposedly relates directly to the angle where most of the light is leaving. It seems natural that a g-value closer to 1 will produce better pictures where light bounces off at a 90-degree angle, while a 0 value gives very splotchy results. The w-value used in the function scales the function and seems to have less of an effect after tone mapping is appled.

In the image below, 64 spheres are rendered. All spheres share the same color component, but have differing w and g parameters in the HGPF. From left to right, the g-component ranges from zero to one. From top to bottom the w-component ranges from zero to one

Image Synthesis - Project 11

2006-12-20T07:17:00.000-08:00

In Project 11, subsurface scattering is added to the renderer. This implies that light hitting the surface of the material enters and bounces around inside the medium before exiting. Many materials such as grapes, skin and marble exhibit this quality. Subsurface scattering in this implementation used ray marching, where the ray enters the medium and bounces around until exiting. Because the ray actually bounced around inside the object instead of just off the surface, the rendering was far more computationally expensive than rendering this scene without SSC.

In the image below, two spheres are placed side by side with a large rectangular light source placed overhead. The sphere on the left uses subsurface scattering while the sphere on the right uses just Lambertian reflections. Light shining from above simply bounces of the top of the Lambertian sphere, leaving the bottom dark and unilluminated. The SSC sphere, however, has light shining through the medium and appearing at the bottom of the sphere as many materials would

Image Synthesis - Project 10

2006-12-16T00:58:00.000-08:00

In Project 10, we were to implement participating media. Participating media involves computing physical bounces of light in media such as fog, dust, smoke, etc. where the light bounces around inside the volume instead of just diffusing, reflecting, or refracting.

To implement this, I used the standard marching technique through an axis-aligned bounding box. A ray was sampled multiple times across its vector using small steps. When these steps were inside the bounding volume, they probabilisitcally hit some of the media.

In the figure below, participating media is used to simulate a gaseous volume under the cube. Right now my code is very ineffecient and took six hours to get these results. Earlier images not requiring participating media required far less time to converge

Image Synthesis - Project 9

2006-12-14T08:28:00.000-08:00

In Project 9, we were to add the Beere-Lambert Law to our renderer. The Beere-Lambert Law models the amount of light absorbed while traveling through a medium. Because different wavelengths are absorbed based on the distance they must travel through the medium, different colors can be absorbed causing different wavelengths to be more pronounced. Certain types of glass often absorb high and low wavelengths leaving a greenish tint at certain angles. Usually this effect can be seen when the light is going through the greatest distance of the glass. To compute the absorbtion at certain frequencies, euler's number e was taken to the exponent of the distance times a large negative constant (which changes based on the scene metrics).

In the picture below, five spheres are modeled. The back left sphere is a reflective sphere, while the back right is a diffuse sphere. Theses spheres are only to provide background to the scene. The spheres in front are used for comparison. The left sphere is a diffuse/reflective sphere with a purplish hue. The middle sphere is a translucent sphere that implements the Beere-Lambert Law based on the distance of the medium. This gives the sphere the slightly greenish tint. The sphere on the right is also a translucent sphere, but does not implement the Beere-Lambert Law. This was to show the difference in hues generated by this principle.

This figure shows several spheres. The front-middle sphere uses the Beere-Lambert Law to absorb certain frequencies of light. The front-right sphere has the same parameters as this sphere, except it does not implement the Beere-Lambert Law. This image took 5 hours and 24 minutes to render

Image Synthesis - Project 7 and 8

2006-12-13T09:36:00.000-08:00

In Project 7, we were to use our renderer to model the Cornell box. This box was compared against a physical model to compare accuracy in the rendering software. This scene's walls and light are modeled using the geometry data and color data from the Cornell box at http://www.graphics.cornell.edu/online/box/data.html.

In addition to the light source and the walls, Project 8 added fresnel effects to the renderer. Instead of the two blocks found in the original Cornell box, two diffuse spheres have been placed in the far corners of the room. A large transparent sphere is placed in the center of the room, which shows the light refracting through it.

The scene's light seems rather blurry because it was moved down slightly to not create artifacts with the ceiling, which is one giant polygon.

Below is an image of the scene rendered at 400x400 and tone mapped. It took 4 hours to render, which is rather sad

Image Synthesis - Project 6 and 15

2006-11-01T04:31:00.000-08:00

In Project 4 & 5, the imager was modified to handle importance sampling and a pinhole camera. The importance sampling provided much faster rendering times by sending photons only at known objects in the scene, and weighting them based on their angle. The photons were generated at the sensor grid and sent through the scene until they hit a light source (or bounced too much). This seemed to provide a good sampling of the scene, but required a major rewrite of the code.

This new version of the software adds a lens to the scene as well as motion blur. To handle motion blur, the red diffuse sphere was moved from (0, 1, 3) to (1, 2, 4) over the course of the rendering. This created an easy but interesting blur effect as if the object was exposed over many sensor units while the apperture was open.

The lense was a simple biconvex lense attached to the pinhole. Upon contact with the lense, the vector was skewed based on it's angle of incidence and the refractive index of the lense (1.4 for this lense). As the photon left this lense, it would be skewed again. Snell's law was used to calculate the angles of refraction for each photon.

Rendered using 18,000,000,000 photons -- 200,000 per sensor grid (4 hours, 11 seconds rendering time)

Image Synthesis - Project 4 and 5

2006-10-10T06:15:00.000-07:00

In the previous project, a single sphere-shaped light emitter was placed onto the sensor grid. In the example, the light source has been moved back and a pinhole has been added between the sensor grid and all other objects in the scene. This pinhole only allows vectors of photons pass through it if it they travel inside the pinhole to reach the grid. Other photons are thrown out. This pinhole-camera scheme provides a much better detailed picture than the previous implementation as it simulates a perspective frustrum just like the eye or a real camera. A red diffuse sphere bounces light from the light source to the pinhole also.

Included in this project was an importance sampling implementation. This fired photons at the diffuse sphere and directly at the pinhole. The amount of photons fired to each object was a ratio of their solid angle and the total number of photons previously fired in all directions. Because only photons sent to the pinhole and the object were fired, the scene was rendered using much fewer photons. Although more overhead was required to calculate the importance sampling, it greatly reduced the calculation time for every photon collision (having much fewer photons in the scene).

Both of these projects were added to the previous code base at the same time. Importance sampling was required to provide an more interactive debugging of the pinhole code. Final images look better than the previous project, and took much less time to synthesize.

313,290,000 emissions (876,964 passed through the pinhole)

Image Synthesis - Project 3

2006-09-13T09:28:00.000-07:00

These are samples from a simulated sensor. The grid is on the xy-plane and a sphere emitting light from it's surface at random vectors hits the sensor grid and accumulates XYZ factors, which are converted to RGB on the graphics card and displayed to the screen. Below are images of this program taken at different number of photon emissions.

1000 emissions

1000000 emissions

100000000 emissions (move over Pixar)

Image Synthesis - Project 2

2006-09-04T15:40:00.000-07:00

This second project is similar to the first. I sampled XYZ estimates using the tristimulus curves and converted the samples on the graphics card to RGB using the Adobe RGB table conversion standard matrix. It took my poor little laptop almost two minutes to render 1024 time steps at 720x480.

1 sample

16 samples

256 samples

1024 samples

Image Synthesis - Project 1

2006-09-04T14:54:00.000-07:00

This first project samples various frequencies on the Macbeth color checker. If it passes a basic sampling check, the image color is sampled to the frame buffer. All the samples are acculumated over each time step to get a better average color. All these images were rendered at 720x480 (they seemed like good numbers). They were rendered on a Toshiba Tecra S2.

1 sample

16 samples

256 samples

1024 samples