## Fluid Integration and Smoke

Over the last few days I have been adding support for PhysX fluids to my particle engine, in addition to a few enhancement+fixes to the particle engine itself. The big advantage of the fluid integration is not that it provides SPH(which is nice), but that it provides fast and robust collision detection and interaction with physical objects.

Anyway below I show a couple of screen shots of a small demo level I made, the first is the demo running(it runs at 60 to 30fps depending on resolution) and the second shows the editor with my node based particle editor. With respect to performance, it is mostly fill rate limited(unsurprisingly), I really should investigate using a low resolution render target for low frequency objects.

Some things I added to improve the quality of the results:

- I rotate the billboard normals away from the centre of the particle, to create a fake volumetric effect. This vastly improves the quality of the lighting for particles. (not sure where this idea came from, I think I read about it somewhere, I just can’t remember where…:-(
- I added particle sorting, surprisingly, most of the time this is not even needed for many smoke like effects(partly due to the implicit sorting due to emission order perhaps).
- I used the relative screen space depth to fade the edges of the particles near intersection. This is done with a bunch of shader nodes, I really should combine these into one node since it is quite a common operation.
- I use my own emitter, not the one built into PhysX, this allows detailed control of the emission parameters(eg distribution of particles within the emission cone etc)
- I expose more or less all of the fluid settings, however I havent gotten around to sorting them and allowing distributions to be assigned to appropriate parameters.

## Shallow Water Simulator, OpenCL + Rigid Body Interaction

Just a quick update to post a video of my current progress on my shallow water simulator.

Recently I converted the simulator to OpenCL(from plain C# code) and added rigid body to water and water to rigid body interaction. The conversion to run in parallel was very straightforward, for the rigid body interaction I subdivide the collision shapes into triangles when they first touch the waters bounding box, then just process each triangle separately using atomic operations to update the height and velocity fields. I need to investigate the performance in more detail and generally optimize things, but the initial conversion seems quite fast(the ducks scene runs at 45+fps when not recording video).

I have also added FFT wave simulation for small scale details and/or providing a nice water effect when interaction is not needed(although this is not shown in the video). You can find further details about this method at http://tessendorf.org/ .

## Game Engine Progress

Well its been a while since I posted here, apart from Job Hunting I have had time to do a few things on my game engine. Nothing particularly exciting, mostly stabilization, bug fixing and features which are not terribly exciting, but still important. A quick list:

- Linear space lighting, ie I adjust the gamma of textures when reading(in the shader, due to XNA/portability concerns) and convert to 2.2 gamma at the end of tone mapping. While quite a simple change this made a huge difference to the lighting quality.
- Colour correction + screen fades etc. A simple change, I added a matrix transform after tone mapping. In addition I added logic nodes to control this.
- Limited deferred lighting. The motivation for this was that since I didn’t want to add GI or lightmapping I needed a way to add many fill/fake GI lights to indoor scenes to give a convincing level of lighting complexity.

I say deferred, but all I do is draw the light volumes to a texture and read the normal/depth map to compute the lighting. I don’t have any sophisticated attribute buffer/shadow mapping etc, the deferred lighting is controlled with parameters from just the lights. Later this is combined with key lights, textures etc during the forward rendering pass. My deferred lighting texture consists of diffuse + ambient in RGB and a single channel of specular in alpha. - More animation blending nodes, including nodes for inverse kinematics, converting absolute to relative animation(eg converting a climb animation relative to a fixed point to take into account player movement), fading between animations etc. Plus I added lazy animation updates(ie only re-blending animations when something relevant to the nodes changes).
- A GUI editor and rendering/interaction system for menus, player HUD etc. This allows plugable GUI controls, each of which can be assigned another plugin node which manages the action of the node. For example loading another GUI page, changing resolution, input bindings etc.
- Load/Save support, this just consists of a function to gather marked properties and user-generated save data into a data structure from entities and components. I then use my versioned serializer to write this to a file.
- A proper input system which allows arbitrary mapping of keyboard/mouse and game pad input to linear and binary actions. This includes thread communication and UI integration components.
- Basic cube map reflectors(ie runtime generated reflection maps). Nice to create mirrored balls, environment maps etc.
- Texel snapping and fixed frustras for CSM shadow maps. More or less eliminates the very annoying shadow flickering when moving around.
- A particle history node for particle systems, this combined with a couple of other nodes and features allows my particle system to produce beam effects.
- Async level loading.
- Depth of Field post processing effect.

Not sure if I mentioned some of these changes already… Also hopefully I will find time to add some screenshots of some of these things soon.

## Real-Time Simulation of Large Bodies of Water with Small Scale Details

I should highlight this rather useful paper(pdf).

It discusses issues faced when building a 2D heightfield fluid simulator (see my former post about the bare bones simulator I added to my engine). What is so useful is that it provides many references and nuggets of information needed to extend a basic simulator to increase stability and improve interaction with other systems.

Thankfully it contains only a minimum amount of GPU Compute marketing:-)

## Sweeping a sphere against a sphere

This is going to be quite a short post, since we did the bulk of the work in the last post, the extension to sphere-sphere is fairly trivial.

All that is required is to realize that the time of impact for a sphere swept against a sphere is the same as the time of impact for a sphere which is the sum of the radii swept against a point. The contact point is simply the point along the normal at the perimeter of the sphere we swept against.

public static bool Sweep(BoundingSphere sweepSphere, BoundingSphere otherSphere, Vector3 direction, out SweepResult sweepResult) { //like a sphere-point sweep with a sphere the size of the sum of the radii sweepResult = new SweepResult(null); BoundingSphere infSphere = new BoundingSphere(sweepSphere.Center, sweepSphere.Radius + otherSphere.Radius); SweepResult infSweepResult; //Inflated sphere result bool infResult = SweepSpherePoint(infSphere, otherSphere.Center, direction, out infSweepResult); sweepResult.T = infSweepResult.T; if (infSweepResult.T != null) { sweepResult.Point = infSweepResult.Point + infSweepResult.Normal * otherSphere.Radius; sweepResult.Normal = infSweepResult.Normal; } return sweepResult.Intersection = infResult; }

## Sweeping a sphere against a point

Before beginning it is a good idea to grab a computer algebra package, since there is often a bunch of tedious algebraic manipulation involved in writing a sweep test (more so for later tests). A good choice is Maxima, which is free and fairly effective, although it does require a bunch of messing around to get it to do what you want with vectors.

First lets define the prototype for the function we want:

public static bool SweepSpherePoint(BoundingSphere sweepSphere, Vector3 pt, Vector3 direction, out SweepResult sweepResult)

I am using C# for the example code and relying on the XNA math types. The function returns true if there is an intersection along direction as t (the time of impact) ranges from 0 to 1, including an initial intersection at t equals zero. sweepSphere is the sphere we will be sweeping and pt is the point we are sweeping against. direction is the vector we will be sweeping along and sweepResult is information about the intersection, if it occurs.

public struct SweepResult { public bool Intersection; // true if there is some intersection(including an initial intersection) public float? T; public int? FaceIndex; public Vector3? Point; public Vector3? Normal; public float? PenetrationDepth; }

SweepResult contains a bunch of information, a lot of it optional, which is only set when relevant to the situation.

Since many sweeps turn into solving a quadratic equation we will be making use of a function to solve quadratics:

public static bool SolveQuadratic(float a, float b, float c, out float t0, out float t1)

This function returns true when there are one or more solutions to the equation . The solutions are returned in t0 and t1, with t0 equal to t1 if there is only one solution. The function correctly handles zero coefficients (e.g. linear or constant equations).

Before we begin with the math for this, there are a number of strategies we can use to simplify the problem at hand and other similar problems:

- Change the subject of the sweep test, for instance sweeping a point against a sphere(a raycast) is the same as sweeping a sphere against the point. This works because we are just changing the frame of reference, only the objects we are considering matter so which one is moving is just a matter of perspective.
- Reduce the dimension of the problem by deflating one object and inflating the other. For example the time of impact between spheres of radius R1 and R2 is the same as the time of impact between a sphere of radius R1+R2 and a point located at the centre of the second sphere.
- Split the test based on the features of the objects. For example when sweeping against a polyhedron we can decompose this into a number of polygons, which in turn can be decomposed into a number of planes, edges and points.

It should be noted that decomposing shapes and deflating/inflating shapes has the added advantage of improved modularity. So we can write a test for a sphere against a point, check that it works as expected, then reuse this test in another situation. For example sphere-point can be used to check the end spheres of a capsule against the points at the end of an edge.

Lets begin, first we have the equation of a line. A point swept along the reverse of our direction, however we ignore the fact that the direction is reversed until we write the code:

Where:

q is the point of interest

p is the origin of the line

V is the direction of the line

t is the time

Then we have the equation of a sphere:

Where:

S is the centre of the sphere

R is the radius of the sphere

If we substitute the equation of the line into the equation for the sphere we can solve for the time of impact:

Something we should note is that when the quadratic is solved we can end up with a number of result:

- Two results, each result represents a time when the line passes through the shell of the sphere. Or alternatively a time at which the shell of the sphere is swept into the point. We just need to sort the results to obtain the time of impact.
- One result represents a grazing impact with the sphere.
- No results represents the cases where the sphere misses the point completely.

If any of the impact times are negative or greater than one(since by convention we only consider impacts confined to the movement along direction), then we throw away that result since it is outside the range for the sweep. If we throw away both results then there is no impact.

Obtaining the point of impact is as simple as plugging the value of t into the line equation. The normal (on the sphere) is just a case of subtracting the contact point from the sphere centre and normalizing. We reverse the normal in this test, because by convention we return a normal pointing away from the second object in the test. Obviously we couldn’t compute a true normal for a point.

If we look at the above formulae, we notice that we can simplify things a bit further and improve performance. We subtract the centre of the sphere from the origin of the ray. This makes S zero and eliminates a few multiplies and dot products.

Finally we should consider a few edge cases, if the direction is zero length, then our sweep test degenerates into a simple point-sphere intersection test. The case where the point and sphere initially intersect is handled by checking if 0 is contained in the range t0 to t1 and returning an appropriate value.

public static bool SweepSpherePoint2(BoundingSphere sweepSphere, Vector3 pt, Vector3 direction, out SweepResult sweepResult) { //sweep point against sphere along -direction sweepResult = new SweepResult(null); if (direction.Length() < DirectionEpsilon) { //zero direction, is the point initially touching the sphere? return sweepResult.Intersection = Intersects(sweepSphere, pt); } Vector3 P = pt - sweepSphere.Center; float PdotV = Vector3.Dot(P, -direction); float PdotP = Vector3.Dot(pt, pt); float a = Vector3.Dot(direction, direction); float b = 2.0f * PdotV; float c = PdotP - sweepSphere.Radius * sweepSphere.Radius; float t0, t1; if (!FloatHelper.SolveQuadratic(a, b, c, out t0, out t1)) { return sweepResult.Intersection = false; } FloatHelper.Sort(ref t0, ref t1); if ((t1 < 0.0f) || (t0 > 1.0f)) { return sweepResult.Intersection = false; } if (t0 < 0.0f) { return sweepResult.Intersection = true; } Vector3 sphereHitCen0 = sweepSphere.Center + direction * t0; sweepResult.T = t0; sweepResult.Point = pt; sweepResult.Normal = Vector3.Normalize(sphereHitCen0 - pt); return sweepResult.Intersection = true; }

## Sweep Tests

Sweep tests are an essential part of any programmers tool box if they are interested in writing a 3D application. Sadly the amount of information about them is somewhat limited and often inaccessible, at least for the more sophisticated tests. So I plan on writing a number of blog posts describing the approach I have taken writing my library of sweep tests. These posts will work from basic principles, developing the more sophisticated tests based on simpler tests.

To start with I should probably define what a sweep test is: given a geometric shape and its position in space, check which shapes it intersects when it is swept along a path, returning the first shape that it intersects, the “time of impact”, the intersection point and the intersection normal. In these posts I will restrict my discussion to linear sweeps along a single line. In general sweep tests can also be formulated for rotational paths as well, but I will not cover these. In addition I will only cover “discrete” sweep tests, ie I will formulate each test individually rather than using a general method such as an adapted GJK approach.

There is a bunch of information available online(and in paper form) concerning intersection testing and some concerning sweep tests, below I will list a few useful resources:

- The Real Time Rendering Intersection Tests Page (Website + Book)
- Geometric Tools (Books + Website)
- Real Time Collision Detection (Book)
- Solid / Collision Detection in Interactive 3D Environments(Book + Website + Collision Library)

The rough plan for posts I will make(very much subject to change):

- Sweeping a sphere against a point and another sphere
- Sweeping a sphere against a line/edge
- Sweeping a sphere against a plane
- Sweeping a sphere against a polygon
- Capsules and sweeping them against a sphere
- Sweeping a capsule against a point
- Sweeping a capsule against a line
- Sweeping a capsule against a polygon
- Sweeping a capsule against another capsule
- Sweeping a polyhedron against points, faces and edges
- Sweeping a polyhedron against another polyhedron
- …

I should note that I derived the tests I use from first principles and then debugged/optimized them so that they were suitable for my needs. I do not make any assertions about their robustness or performance except that I have been using them for a while to handle player control and moving platforms etc in my hobby game.

An important point to mention is that a lot of the difficulty in writing sweep tests is related to establishing a framework to ensure they are easy to debug and robust. The approach I took was to add a command to my level editor which allowed me to experiment with the sweep tests with a visualization of important information. Being able to do this interactively is essential as most problems are related to long thin objects, objects of different scales, grazing contacts etc. In addition I created a number of unit tests to tackle regressions(however testing all permutations this way is prohibitively expensive).