Thursday, September 23, 2010

Cel Shader

I've recently had to dabble in non-photorealistic rendering (NPR) techniques, specifically cel or toon shading and silhouette edge rendering, and thought I'd share a simple cel shader that I implemented.

Toon shading is a rendering style that gives everything a "cartoony" look. It can have a good deal of variation applied to it, but at its simplest it applies solid colors with distinct color boundaries to objects, akin to what you'd see in cartoons. The cartoon feel can be further enhanced by applying some type of black outlining around significant features of the object, i.e. some type of silhouette edge rendering.

Below is a composite screenshot taken from my demo showing the difference between an NPR-rendered and non-NPR-rendered teapot. The teapot on the left uses classic Phong shading, while the teapot on the right uses cel shading with silhouette edge rendering.


The cel shading is accomplished by first calculating classic Phong shading values, then mapping them to their final color based on the computed light intensity. My particular implementation uses an ambient layer, three diffuse layers, and one specular layer. To make the color transitions slightly smooth (instead of a hard boundary) we use the HLSL instinsic smoothstep which bleeds each subsequent layer into the previous one. There are other more efficient techniques for cel shading (with varying results) but this is what I chose to go with. The HLSL 4.0 pixel shader code is shown below.


// layerXStart: Percent of light intensity at which to start each diffuse layer. Subsequent layers
// should be greater than the previous ones. Valid range is [0,1].
static float layer1Start = 0.0;
static float layer2Start = 0.1;
static float layer3Start = 0.25;

// Range, at the beginning of each layer, to bleed into the previous one. Valid range is (0,1].
static float layerBleed = 0.025;

// layerXColor: Percent of diffuse material color for each diffuse layer. Valid range is [0,1].
static float layer1Color = 0.35;
static float layer2Color = 0.7;
static float layer3Color = 1.0;

// Specular modifiers have the same meanings as above.
static float specStart = 0.35;
static float specBleed = 0.2;
static float specColor = 0.7;

float4 PS_CelShade(PS_INPUT input) : SV_TARGET
{
input.normal = normalize(input.normal);
input.viewDir = normalize(input.viewDir);
vector reflection = reflect(lightDir * -1.0, input.normal);

float diffuseIntensity = saturate(dot(lightDir, input.normal));
float specIntensity = pow(saturate(dot(input.viewDir, reflection)), potSpecPower) * ceil(diffuseIntensity);

float toonIntensity = 0.0;
toonIntensity += smoothstep(layer1Start, layer1Start + layerBleed, diffuseIntensity) * layer1Color;
toonIntensity += smoothstep(layer2Start, layer2Start + layerBleed, diffuseIntensity) * (layer2Color - layer1Color);
toonIntensity += smoothstep(layer3Start, layer3Start + layerBleed, diffuseIntensity) * (layer3Color - layer2Color);

float4 outputColor = 0.0;
outputColor += potKs * (lightKs * smoothstep(specStart, specStart + specBleed, specIntensity) * specColor);
outputColor += potKd * (lightKd * toonIntensity);
outputColor += potKa * lightKa;
outputColor.a = 1.0;

return outputColor;
}

Silhouette rendering is accomplished through a bit of rendering trickery known as the shell extension method. After the cel shading is performed, the object is rendered again with front-face culling turned on, i.e. the back-facing triangles will be visible instead of the front. Each vertex is then extented slightly along the vertex normal in the vertex shader, proportional to the distance from the camera (to create a uniform extension as viewed from the camera). The new vertex positions are then sent to the pixel shader, which just outputs black as the color, resulting in a black outline around the object wherever the back-facing pixels are visible.

Of course, this particular method of silhouette rendering only works if an object's vertices all use shared, averaged vertex normals. For example, this method wouldn't work on a cube whose vertices all used different vertex normals; it would leave clear gaps in the outline around the cube.

Here's the complete vertex and pixel shader code for silhouette edge rendering.


// This controls the thickness of the outline.
static float thickness = 0.0035;

// Vertex shader that uses the shell extension method to create a silhouette outline.
float4 VS_ShellExtension(VS_INPUT input) : SV_POSITION
{
input.position.w = 1.0;
input.normal.w = 0.0;

// Put everything into world-space first.
input.position = mul(input.position, world);
input.normal = mul(input.normal, world);

// Offset the vertex along the normal, proportional to the distance from the camera.
float distance = min(length(input.position - cameraPos), 20.0);
input.position += input.normal * distance * thickness;
input.position = mul(input.position, viewProj);

return input.position;
}

// Simply outputs black.
float4 PS_Black(float4 position : SV_POSITION) : SV_TARGET
{
return float4(0.0, 0.0, 0.0, 1.0);
}

When calculating the distance from the camera you may have noticed the upper bound placed upon it. Without this, the outline would maintain a uniform thickness regardless of the size of the model, which is exactly what we want as long as the model is visibly large enough that the outlining doesn't dwarf the actual geometry. As the model gets farther and farther away from the camera, however, the outline begins to overcome the geometry until eventually all you see is a black blob. Placing an upper limit on the distance forces the outline to start scaling down with the model at that distance, thus avoiding the problem of the "black blob".

The source code for the demo is given below, along with an .exe-only version for those who just want to see it in action. Again, a DX10-capable GPU is required. Enjoy!

CelShader Source.zip (full source code/project)
CelShader Demo.zip (.exe only)

Thursday, September 2, 2010

HTD Update 2

Three months since my last post! The summer flew by fast. Unfortunately, the HTD project revamp isn't really any further along since my last update. Almost immediately another higher-priority project came up, and then another after that, and so on...and now fall classes have begun. So the HTD revamp was pushed aside and has remained there ever since.

However, I said I'd post the source code at some point, so before my classes completely consume me I thought I'd go ahead and post at least the code for the water flow simulation. The hydraulic erosion part is still buggy and not working, so I stripped out any code related to it. I'm also posting just the executable for those who want to see the sim in action without having to build it first. The readme file explains how to run/control it. A DX10-capable GPU is required (sorry XP users!)

Water Flow Source.zip (full source code/project)
Water Flow Demo.zip (.exe only)

As for the explanation of the implementation and flow equations, I refer the interested reader to the paper that my project is based upon, the Symposium on Computer Animation 2008 paper titled Interactive Terrain Modeling Using Hydraulic Erosion by St'ava et al.

I do hope to one day return to this and finish it, but for now it will have to continue to sit on the back burner - classes are going to keep me extremely busy for the next few months. In the meantime, enjoy the water flow simulation!

Thursday, June 10, 2010

HTD Update

The other day I realized I hadn't posted anything new in nearly two months, so I figured I'd better give an update on the Hydraulic Terrain Deformation (HTD) project I was/am working on.

Of course the semester is long over with by now, and the project submitted long ago, but I've been cleaning up the messy and sometimes hackish code that inevitably made it into the project as the deadline approached. And in the process of the cleanup, I also decided to give my personal code libraries an overhaul and add new functionality, which means breaking and changing the way my project worked beforehand. The hope is to release a nice, polished, and properly-commented program for public consumption when I'm done.

So in short, I'm still "working" on it. It'll probably be a while longer before I'm done, but I will get it out the door...eventually. =)

Friday, April 16, 2010

Hydraulic Terrain Deformation Preview

Here's a quick couple of screenshots and videos of my hydraulic terrain deformation project I'm working on. So far I have water flowing over arbitrary terrain, and pretty much all the underlying code and systems necessary to start deforming the terrain via hydraulic erosion. The simulation runs in real-time entirely on the GPU, i.e. no data is transferred between the CPU and GPU while it's running - all data calculations are done with GPGPU methods.

I'll give a more thorough explanation when I have more time (probably when I'm done with the project) and I'll probably post the source code as well.





Tuesday, April 13, 2010

GPU FTL....Again

Having one GPU fail on you is rare as it is, but having the second just-replaced-less-than-a-month-ago GPU fail also??? What rotten luck I must have. Either that, or the GPU seriously disagrees with my shader code and is willing to destroy itself so that it doesn't have to be subjected to my cruel instructions anymore. I think it's a toss-up.

Once again I had a replacement shipped out under warranty, and again the response was prompt, which made the loss of the GPU about as painless as it could be. I take a small bit of comfort in knowing that when this GPU fails it'll only take a couple days to get replaced.

Friday, March 26, 2010

The Joys of DirectX 10

For the last couple of weeks I've been working on my final project for my physically-based modeling and simulation course, which is going to be a real-time, interactive terrain modeling system using hydraulic erosion (more on that at a later date). Instead of using OpenGL like we have all semester I decided to delve into DirectX 10, since I most likely will be using DirectX out in industry and therefore need to start getting experienced with it. Yup, this is my first DirectX adventure, and what an adventure it's turning out to be.

I'm finding that good online DX10 resources are few and far between. Sure, there's MSDN that lists all the API functions and whatnot, but it doesn't really clearly tell you what they're used for or exactly how you would use them. Most of the documentation is fairly vague, and there aren't any code examples of everything in action except for a few basic tutorials that come with the SDK. For someone new to DirectX, the journey is frequently rough and slow-going. I guess it's time to find a good book on the subject.

As soon as I have something to show from my project I'll get it posted.

Wednesday, March 17, 2010

Constrained Particle Dynamics

For our second assignment in my physically-based modeling and simulation course we were given the task of implementing a particle system capable of imposing constraints upon the particles. An example of a constraint would be requiring two particles to always stay a fixed distance apart. The trick is getting the particles to obey physics while also obeying all constraints imposed upon them. How do we define the particles' behavior to accomplish this?

It turns out a good way to do this is through the use of constraint forces, which are directly-calculated forces that cancel out all illegal accelerations, thereby only allowing the particles to move in a way that maintains their constraints. When I say the forces are directly calculated I mean that the force calculations are done before the particles have violated their constraints, in effect never allowing them to do so. This is in contrast to the penalty method which applies restorative forces after the particles have already violated their constraints (such as in the collision response of the mass-spring system I did earlier).


There's an excellent reference on the internet by Andrew Witkin of Pixar that explains constrained particle dynamics and how to use them. Because his article is basically what I used to learn about the topic, I'm not going to give any kind of lengthy explanation about the math or implementation of the system, since I would essentially just be repeating what he's already said. And besides, I'm sure his explanations are better anyway. The article can be found here.

One aspect of Witkin's method that makes it ideal for interactive applications is the treatment of constraints as individual objects that can be inserted and deleted from the system as needed. Each constraint object is responsible for calculating and filling in its own portions of the required matrices. What this means is that you don't have to hard-code the linear system of equations that need to be solved, which allows for an interactive simulation that can add and remove particles, and their constraints, at will. If you have no idea what I'm talking about, then I refer you to the reference above. =)

The video below shows my implementation of Witkin's system, using 18 particles constrained to a ring. The top-most particle is constrained to remain in place, the bottom-most particle is constrained to remain on the ring, and every particle is constrained to remain a fixed distance from its neighbors. External forces are applied interactively through keyboard input. There's also no collision (by design), because the 3D-ness of everything is just meant as a visual aid to help "see" the constraints. And just like the first assignment, this too is written in C/C++ and OpenGL.

Tuesday, March 16, 2010

Deformable Objects Via 3D Mass-Spring Systems

This semester I'm taking a course on physically-based modeling and simulation, a topic that sounded interesting when I signed up for it but one that I didn't know too much about. So far it's turning out to be very interesting indeed, and challenging and fun too. I'd say it's the best course I've taken yet.

For our first assignment we had to simulate a deformable jello cube that moves around within a bounding box under an arbitrary non-uniform force field, bouncing off any plane it comes into contact with. The jello cube itself is modeled as a 3D mass-spring system: the cube is discretized into a grid of mass points that are all connected to their neighbors with springs. The springs are what maintain the cube's shape but at the same time allow jello-like deformity.


It turns out just having each mass point connect to each of its six direct neighbors isn't enough to maintain the cube's shape - the grid of points can shear while still allowing the springs to remain at rest, resulting in a collapsed (i.e. flattened) cube of jello. There are actually three different types of springs needed to keep the cube from losing its form:

1) structural springs (direct neighbor links, defines the shape of the cube)
2) shear springs (diagonal neighbor links, prevents shearing)
3) bend springs (direct 2nd-neighbor links, prevents folding)

Ok, that's not entirely true. The bend springs aren't strictly necessary for a cube shape because the other two types will keep the cube from folding over anyway. However, a 2D simulation such as cloth would need all three types (assuming you didn't want to allow the cloth to fold over on itself).

The cube in our assignment consists of 512 mass points in total (8x8x8) resulting in 6,220 springs in the system. In contrast, a system consisting of just 8 points (2x2x2) would have 28 springs. As you can see, the number of springs grows exponentially with the number of mass points. This can make finely-grained modeling of large objects using mass-spring systems not very feasible. The screenshot below shows just the surface points and connected structural springs of the jello cube.


The elastic forces exerted by the springs are found by using Hook's Law, F = -kx. In addition to these forces there also needs to be a damping force that always opposes the motion. Without any kind of damping the springs would oscillate indefinitely and eventually the simulation would fail. Damping forces are modeled similarly to elastic spring forces, except they depend on the velocity: F = -kv. Note that the value of k is different for damping than it is for springs. The two forces are added together to obtain a spring's overall force contribution.


Collision with a plane is handled via the penalty method. Once a mass point has been found to be colliding with the plane, an artificial collision spring is placed perpendicularly between the plane's surface and the mass point. This new spring will push/pull the mass point backwards and away from the colliding plane. As you might expect, collision springs have their own elasticity and damping coefficients, just like ordinary springs.


The final piece of the simulation is the external force field which causes the jello cube to move around within the bounding box. The field's resolution (i.e. the number of force points in the field) can be arbitrary, and the cube is constantly moving, so trilinear interpolation is used to find the exact force at each mass point.


So what does all of this add up to? Using Newton's 2nd Law, F = ma, the acceleration of each mass point can be calculated as follows:


Combining the equations together for all the mass points gives us a system of ODEs (ordinary differential equations), which can be solved numerically using integrators. Examples of such integrators are Euler, Runge-Kutta 2nd-order (RK2, a.k.a. midpoint method), and Runge-Kutta 4th-order (RK4). I won't go into how they work here; that's a topic unto itself. Deciding which integrator to use is usually a tradeoff between accuracy and computational cost. For example, the Euler method is computationally inexpensive but very inaccurate. Very small timesteps are needed to keep it stable which doesn't allow for fast simulations, so it's rarely used in practice. The Euler and RK4 methods were both implemented for the assignment.

The first video below clearly shows the deformations of the jello cube as it bounces off the walls. The second video is the simulation I turned in for the assignment. Different values for the spring and damping coefficients were used to achieve the different effects. And for those who are wondering, the simulation is writtin in C/C++ and OpenGL.



GPU's Back In The Game!

After being told that my replacement GPU would take about a week to arrive, imagine my surprise when it showed up today, only two days after I called the company about it. Now that's service!

But even after just two days of looking at 1024x768 resolution with graphical corruption, having my screen returned to normal looked strange at first. I think I was actually getting used to my sub-par visuals. Scary.

Sunday, March 14, 2010

GPU FTL

Efforts to post my projects have been put on hold for at least a week, thanks to my GeForce 8800 GTX crapping out on me. Most of the projects from here on out require a GPU, and without one of those I can't get any screenshots or videos. Annoying to say the least.

Luckily the card is still under warranty, so a new replacement is on its way for free. But not being able to work from home on any of my current school projects requiring a GPU is definitely frustrating, and will inevitably lead to some long nights in the near future in order to make up for lost time. Thanks, GPU.

Friday, March 12, 2010

The Best 2D Space Shooter Ever Made...

...was of course Gradius 3. Some may argue with that statement, but that game gave me countless hours of enjoyment on the Super NES. Even today I still have fun playing it. So when a fellow hobbyist game developer clued me in to the world of homebrew GameBoy Advance games, I pretty much knew immediately what game I'd love to make for it. Doing Gradius 3 for the GBA would pose few problems, if any, since the GBA is essentially a hand-held SNES.


Creating a GBA game for my second dev experience seemed like a good fit because I would be working in a console environment, but without the scariness of jumping head-first into full-blown 3D. It turned out to be a very fun project, I thoroughly enjoyed having to design for a limited-memory and limited-capability system (getting all five of the parallaxed starfields to operate within just one of the four hardware tilemap layers was quite a challenge in itself).

The video below is the demo game I put together. Sadly I stopped working on it before it could be considered a "complete" game - it was reaching a point of diminished returns for my time and effort, so I thought it would be better to move on to something else. The entire thing is written in C and was tested on the VisualBoy Advance GBA emulator.



The video is a bit choppy (to keep the file size down) but the game runs at a smooth 60 FPS. Well, technically it runs at 59.73 FPS (2^24 clock speed with a full screen refresh taking exactly 280,896 cycles), but who's counting...

Thursday, March 11, 2010

Good ol' Tetris

Back when I was first becoming interested in game development a few years ago, I didn't know the first thing about making a game, even a simple one. I knew how to write code, but that was it. So after some searching around on the internet on "how to make a video game" it seemed the popular answer was to start off by making some sort of variant of either Tetris or Breakout. I was much more familiar with Tetris, having played the crap out of that game on the original GameBoy when I was a kid, so I went with that.


I learned just enough Windows programming to make it run on a PC, and wrote the entire thing in C++. The video below shows a quick demo of the final version.



What you don't see in the video is the variable grid size and additional block shapes I added. The initial launch window that appears when you run the game lets you select the size of the grid to play in, and lets you select what kind of block shapes to use. For instance, the standard grid size is 10x18, but on my current monitor I can have a grid size of up to 64x42 - pretty ridiculous. Playing with a huge grid area and up to 87 different block shapes is amuzing, but the classic version is truly the most fun.

Tuesday, March 9, 2010

And so it begins...

As I'm sure many a blog start off, I will also start off by saying "This is my first experience with blogs." I'm not into the whole social networking craze, so this is also my first real experience with putting bits and pieces of my personality and life out for everyone to read about. However, I think it's important that I have a place to showcase some of the work I've been doing and will do in the future, given that I'm currently a grad student who will graduate in a little over a year, at which point I will need to have found that ever-important job. Throwing it all into a blog seems like a perfectly fine choice to me, and hopefully will somewhat demonstrate what I'm capable of. That's not the only reason for this blog, but it is a piece of the puzzle.

My first few posts will most likely be about past projects, with the current stuff to follow. Another good reason for me to start this blog is it will help me remember everything that I've worked on, and any interesting tidbits I learned along the way. I look forward to taking fond (and likely horrid, too) trips down coder memory lane.