Volume Calculations

While building a physics engine the problem of determining the volume enclosed by a collision hull (or some other surface bound topology) is likely to present itself.  A simple volume determination can be carried out by dividing the space around a volume into a regular grid and summing up the volume of all the voxels enclosed by the bounding surface; while straight forward to implement this is extraordinarily slow due to the number of containment tests involved.  Collision hulls are defined by an explicit description of their bounding surface, usually in the form of a mesh tessellated by a set of n sided polygons.  With this in mind we would like to relate the volume of a collision hull to an explicit calculation on the surface of the hull.  This leads us to the Divergence Theorem:

Roughly stated (with apologies to mathematicians for the sloppy wording) the Divergence Theorem tells us that the divergence of the vector field F within the closed volume V is equal to the flux of F through the boundary of V where the boundary of V is given as the closed, oriented, 2d surface S.  The so called orientation of S comes from the unit length vector n which consistently points “outside” of V and is well defined for every point on S.  Note that the left hand side of the theorem looks very similar to the triple integral you would use to directly calculate the volume of V.

If we choose F as the vector field (x, 0, 0) then the divergence of F is trivially computed as 1.

Which of course collapses the internals of the integral on the LHS of the Divergence Theorem into a simple unit integration through the volume of V.

The Divergence Theorem can then be used to relate the volume of V to the divergence of F through S.

We now have the volume-to-surface relationship needed for the efficient calculation of the volume enclosed by a collision hull.  Assuming a straight forward mesh representation the volume of a collision hull can be computed as the piece wise summation of the flux of F = (x, 0, 0) through each polygon in the mesh.

Calculating the flux of F through Si requires integrating a vector field across area Si and therefore a 2 dimension parameterization of Si.  For the sake of simplicity we restrict ourselves to the decomposition of S into n triangular regions described by a set of counter-clock-wise wound vector triplets.

In other words, S is a triangulated mesh.  A straight forward parameterization of triangle Si is given by the parametric equation Ti.

Under this parameterization the outward facing differential area dAi is computed as:

The flux of F through triangle Ti can now be written as an explicit 2d integral.

The symbolic evaluation of the double integral is tedious and mundane and in the interest of space has been omitted; the final result follows.

Finally, the total volume of V can be expressed as:

For the mathematically adverse a basic C++ implementation should look something like this:

 float32 CalculateVolume(const Vector3* a_pVerts,
                         const int32*   a_pIndices,
                         const int32    a_nNumTris)
{
    float32 fVolume = 0.0f;

    for(int32 i = 0; i < a_nNumTris; i++)
    {
        Vector3 v1 = a_pVerts[a_pIndices[3*i  ]];
        Vector3 v2 = a_pVerts[a_pIndices[3*i+1]];
        Vector3 v3 = a_pVerts[a_pIndices[3*i+2]];

        fVolume += (v1.x+v2.x+v3.x)*((v2.y-v1.y)*(v3.z-v1.z)-
                                     (v2.z-v1.z)*(v3.y-v1.y));
    }

    return fVolume / 6.0f;
}
Advertisements

Shadow Volume Culling

A standard feature of any modern graphics engine is support for dynamic lights and shadows. Independent of the actual shadowing algorithm used is the collection of objects known to cast shadows onto the portion of the scene visible to the camera. For bounded lights (lights with a finite spatial extent) the collection of shadow casters is a simple matter of testing an object’s bounding volume against the light’s bounding volume. In the case of unbounded, directional lights such as the sun or moon this problem is considerably more complex. An object-to-light bounding volume test is meaningless since the light’s bounding volume is infinite. Testing objects against the view frustum only gets the job half done; there is still a high probability of objects outside the view frustum casting shadows onto the view frustum. The most obvious solution to this problem appears to be straight forward:

1) Extrude the bounding volumes of potential shadow casters away from the light source thereby generating capsules for bounding spheres and convex hulls for bounding boxes.

2) Cull the capsules and convex hulls from step one against the view frustum; volumes not visible to the frustum can be discarded by the shadow algorithm.

Unfortunately there are three significant problems to this approach:

1) The initial collection of potential shadow casters is nontrivial; many implementations simply consider all objects that are currently loaded. There are high level rejection tests that can be formulated based on assumptions placed on the configuration of the scene but such tests are implementation specific and only marginally cut down on the number of objects considered.

2) The minimum required extrusion distance changes from object to object and is often times expensive to accurately calculate.

3) Poorly fitting bounding volumes generate extremely large and extremely loose bounding shadow volumes.

Robust solutions to these problems are cumbersome to implement, potentially expensive and difficult to debug. An elegant solution to shadow culling can be achieved by conceptually inverting the problem. Instead of extruding the bounding volumes of objects away from the light the view frustum can be extruded towards the light by an infinite distance. The resulting topology is an unbounded, convex volume defined by a set of bounding planes which can then be used to collect shadow casters. The extrusion process is very similar to constructing a stencil-shadow-volume from an arbitrary mesh where the front cap is kept and the back cap is discarded. This method necessitates the ability to cull objects against an unconventional but still mathematically simple convex region of space. Such functionality is not typical of your average scene manager but is nonetheless simple to add.

The process of extruding a view frustum begins with the detection of silhouette edges. An edge is classified as a silhouette edge when the normal vectors of its two adjacent faces point in opposite directions with respect to the direction of incoming light. That’s something of a mouthful so here is some code:

bool FrustumEdge::IsSilhouette(const Vector3& a_vLight)
{
    float32 fDotA = m_vFaceNormalA * a_vLight;
    float32 fDotB = m_vFaceNormalB * a_vLight;

    if((fDotA * fDotB) > 0.0f)
        return false;

    return true;
}

In practice this test should be done from inside the frustum class where the dot products of the 6 face normals and the light vector are computed once and cached. The next step is to construct plane equations from the silhouette edges; this part is a bit tricky. Culling algorithms require the plane normals to point in a consistent direction, usually outside of the constructed volume. To achieve this each edge on the frustum needs to know which one of its adjacent faces have a winding order that coincides with the edge direction. This data can be explicitly computed at extrusion time via a series of cumbersome tests or the frustum can be constructed in a specific way such that the direction pairing is an implicit property of the data. Suppose the following set of conventions is chosen:

1) Light vector points toward the light source
2) Face normals point outside the volume
3) The vertex winding of a face is counter clockwise
4) The first face associated with an edge is the face with the vertex winding that coincides with the edge direction.

The construction of the bounding plane from a silhouette edge can then be constructed in a consistent manner:

bool FrustumEdge::IsSilhouette(const Vector3& a_vLight,
                               Plane3D&       a_kPlane)
{
    float32 fDotA = m_vFaceNormalA * a_vLight;
    float32 fDotB = m_vFaceNormalB * a_vLight;

    if((fDotA * fDotB) < 0.0f)
        return false;

    Vector3 vNormal;

    if(fDotA > 0.0f)
        a_kPlane.vNormal = Vector3::Cross(m_vMyDirection, a_vLight);
    else
        a_kPlane.vNormal = Vector3::Cross(a_vLight, m_vMyDirection);

    a_kPlane.fDist = -(m_vMyOrigin * a_kPlane.vNormal);

    return true;
}

Finally, any frustum faces that point away from the light source should be added to the set of bounding planes and faces that point towards the light source should be discarded. The resulting set of bounding planes can then be used to collect objects for the shadows pass.

There are a number of different techniques that can be used when culling against an infinitely extruded frustum. My current preference is to construct a set of unique plane normals and edge directions from the extruded frustum and then perform a separating axis test against potential shadow casters. As always once the system is up and running an enormous number of potential optimization await.

8th Generation Consoles and Radiometric Quantities

Typically the world of real-time rendering uses relatively esoteric metrics for the illumination characteristics of a scene.  This is largely intentional as the most commonly used lighting models have very little to do with the actual physics involved.  Terms like energy, radiance, reflectance, albedo and so on are used fast and loose without much thought given to the units of measure or the phenomena being modeled.  Fortunately (or unfortunately) such days are number.

The ground work for the next generation of rendering engines has started and nearly all of them involve a physically derived reflection model and some type of dynamic, global-illumination scheme that accounts for 2nd and even 3rd order reflection events in combination with this generation’s direct (1st order shadows) and indirect (nth order shadows or ambient) occlusion computations.  Understanding, using and augmenting this level of sophistication requires real-time graphics programmers to start talking and coding like their offline counterparts in the ray-tracing world.  The prerequisites of this necessary adaptation are a basic grasp on vector calculus, multi-dimensional integrals and the physics of light; specifically, radiometric quantities.

The most important radiometric quantities are a set of four metrics that can be used to model the propagation of light throughout a scene.  They are:  radiant flux, irradiance, intensity, and radiance and are written as Φ, E I, and L respectively.  Radiant flux is often times referred to as flux, a useful abbreviation that shall be used here as it lessens the likelihood of confusing it with radiance.

Flux:                 Φ

Flux is the simplest of all and is used to quantify the total amount of energy passing through a surface per unit of time and is measured in joules per second or watts.  For the purposes of rendering it is useful to restrict the energy being measured to photons of light that fall in the visible spectrum while ignoring wavelengths beyond ultraviolet and below infrared as they (usually) have no effect on the visual appearance of the scene.  If you were to place an imaginary sphere around a light source then the flux would be the amount of energy passing through the surface of the sphere; it is therefore a natural parameterization of light sources and should be used as such.  Note that the radius of the sphere can take on any arbitrary value and as long as the light source is inside of the sphere the measured flux is constant.

Irradiance:         E = dΦ / dA

The next quantity, irradiance, measures the area density of flux where the area is perpendicular to the direction of flow.  Once again we start by placing an imaginary sphere around a light source.  We know that the flux through the surface of the sphere is equal to the amount of energy passing through it per unit time; the irradiance can be calculated by dividing the total flux by the area of the sphere.  Notice that the radius of the sphere changes the measurement; as the radius increases so too does the area, spreading out the flux and therefore decreasing the irradiance.  This is where the familiar inverse square law comes from by which the intensity of a light source is scaled by the inverse of the radius squared.  It’s worth noting that there is no such thing as a radial emitting light source with an intensity that does not falloff as a linear function of the inverse of the distance squared; such a phenomenon is physically impossible.  While building an engine it may be tempting to include more exotic falloff functions; I highly discourage this.  It may be easy to achieve the desired amount of illumination in a scene by faking the physics but doing so will lace the rendered image with a subtle strangeness; indeed, the image may look spectacular overall but it will also have a hard to quantify artificialness to it.

Intensity:           I = dΦ / dω

Intensity is very similar to irradiance.  Instead of measuring the flux per unit area intensity measures the flux per solid angle.  A solid angle is the 2-dimensional counterpart to an angle.  Just as an angle can be thought of as the length of an arc traced out on the unit circle a solid angle can be thought of as the area of a circular dome traced out on the unit sphere.

Radiance:         L = dΦ / ( dω dA)

While the hardest to conceptualize radiance can be thought of as the most fundamental off all radiometric quantities.  It is constant along rays through empty space and if its value is known all the other radiometric quantities can be derived from it by integrating against the appropriate dimensions.  These two characteristics make radiance the ideal value for managing the propagation of light throughout a scene.  Mathematically speaking radiance is the flux density per solid angle per unit area.  Irradiance can be calculated from radiance by integrating across a solid angle; likewise, intensity can be calculated from radiance by integrating across a perpendicular area.