Showing posts with label PC. Show all posts
Showing posts with label PC. Show all posts

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!

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.





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.



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.