|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Smoothing Using Curved Surfaces With images that have a large amount of height variation, such as a terrain that goes from a valley at sea level to a mountain peak, the amount of smoothing needed to produce a satisfactory terrain model would be so large that a great amount of detail would be lost in the process - your mountains might suddenly turn into rolling hills. So a different approach for these images must be used. A more obvious yet slightly more complicated method is to find some form of surface representation from the initial set of data points. This can be a surface either shaped by or interpolating through these points. There are many ways to do this, but this discussion will be limited to creating a uniform cubic B-spline surface to achieve our goal. Introduction to B-Splines I will assume that you have some basic knowledge of parametric curved surfaces, such as Bézier curves and surfaces. If not, Brian Sharp's articles on Bézier curves and surfaces ("Implementing Curved Surface Geometry," June 1999, and "Optimizing Curved Surface Geometry," July 1999) are a very good introduction. You may recall that four control points define a cubic Bézier curve and that 16 control points define a cubic Bézier surface. In general, a degree n Bézier curve is defined by n + 1 control points, and a degree n Bézier surface is defined by (n + 1)2. However, the desired final set of elevation points will be much larger than a 4x4 grid. Therefore, one will need to use either a much larger degree Bézier surface, or employ another approach that will remain a third degree surface that allows any number of points to define it. This is where the cubic B-spline comes in. In simple terms, a B-spline of degree n can be thought of as a composite curve made up of several curve segments, each also of degree n, with each curve segment defined by n + 1 control points. In this case, each curve segment is a third degree curve defined by four control points. An important feature of the B-spline is what's known as "C2 continuity." This means that at any point on the curve, the second derivative will exist (means that no sharp points will exist anywhere on the curve - a nice property to have). To define the B-spline as a whole, if we have m + 1 control points, then we have m - 2 curve segments. Let a given curve segment Qi be defined over the interval 0 = u = 1 by basis functions Bk(u)(k = 0,…,3) and control points pi , pi+1, pi+2, pi+3 as follows:
This should look familiar, since it's very reminiscent of how a Bézier curve is defined. For the sake of brevity, here are the basis functions for a cubic B-spline (if you'd like more information how the functions are actually derived, please see the References section at the end of this article):
Since these segments are connected together to create one large curve, it makes sense to have a parameterization of the entire curve in terms of one parameter U, instead of having just a parameter u for every curve segment. Globally, U is defined over [0, m - 2], and u defined (as one would expect) over [0, 1]. The parameter u for any given curve segment i is given by U - i. Except for the end points of the B-spline curve, each control point (in the case of a cubic B-spline) influences four curve segments, that is, control point pi influences curve segments Qi -3, Qi -2, Qi -1, and Qi. The influence of each control point pi over the curve at some global parameter value U is "collected" into one global function (called a blending function), Ni(U). Think of the blending function as the sum of the basis functions (which is similar to the basis functions used when evaluating Bézier curves) for any given point on the curve. In formal terms, the B-spline curve Q(U) is defined by:
where
The global function Ni(U) takes the global parameter U and converts it to the appropriate local parameter uj for each curve segment involved. As mentioned earlier, this type of B-spline is a uniform B-spline, which means that the curve consists of curve segments between endpoints that are spaced equally apart (there are other types of B-splines that do not have the ends equally spaced, but we won't worry about those here, since we're dealing with a regular grid of control points). In our case, these ends are located at [0, 1, …, m] of U for m number of control points. These ends will be referred to as knots (to be consistent with any other reference one may find on B-splines). Thus, the spline curve becomes a collection of the knot intervals t0 < t1 < ··· < tm. Also, the order k (the degree + 1) of a B-spline can vary, but for simplicity's sake, we will keep the order of our spline constant at k = 3. Now we can recursively define a blending function Ni,k(u) of degree k over the knot range [ti, ti + k] as follows (otherwise known as the Cox de Boor algorithm):
Now that we have the definition of a B-spline curve, how do we define a B-spline surface? Informally put, any point (u, v) on the surface is calculated by multiplying two separate curves together. Formally, let a point (u, v) on a cubic B-spline surface S defined by a grid of control points pi,j(i = 0, … , n; j = 0, … , m), and blending functions Ni,k(u) and Mj,k(v)
Now that we have basic knowledge of B-splines, applying what we have learned to create our desired amount of elevation data should be relatively easy. The initial set of elevation points should be used as control points for the final surface. Next, determine the dimensions the final elevation data should satisfy. Let our final elevation data set be s values wide by t values tall. When evaluating points on the surface, one needs to know the change in u(du) and change in v(dv) from one point to the next, which is defined by:
The code to do all of this is available on the Game Developer web site, http://www.gdmag.com. Terrain Smoothing In smoothing the terrain bitmap, neither the straightforward smoothing algorithms described above nor any other image processing technique used for scaling or smoothing images can be applied. All of these methods have potential to introduce new color values into the final image, and only the terrain values contained in the original terrain bitmap can be present in the final bitmap. In this smoothing method, another nxn array of values centered on a pixel g[i, j] in an image g will be used to calculate the value of the pixel h[i, j] in the final image h. However, instead of using an equation or other means independent of the values contained in the source bitmap, the values in the nxn convolution mask will be taken directly from source bitmap (specifically, the nxn neighborhood surrounding pixel g[i, j]). Next, a histogram (an "inventory" of all the different values contained in the specific nxn area of the source bitmap) of the nxn array is calculated. From this histogram, the value that is most frequently occurring in the nxn region surrounding the pixel g[i, j] shall be the value of the pixel h[i, j]. Conclusion The convenience of using bitmaps for generating game data can extend beyond just polygonal terrain generation. Other examples could be world object placement (for trees and other vegetation), non-player character (NPC) placement (perhaps for a real-time strategy game where hundreds of units need to be placed for a given scenario), setting paths for NPCs to follow, or providing any addition information about the terrain (for example, setting "off-limits" areas for certain player characters or NPCs). The number of things that an image can represent is virtually limitless. So, before considering creating your own custom tools for generating game data, make sure that you're not simply reinventing the wheel by wanting to provide something that a bitmap could provide just as well. References Image
Filtering Jain, Ramesh, and others. Machine Vision. New York: McGraw-Hill College Division, 1995.
|
|
|
Features
