Method to create a high resolution database

[0003] For decades, military establishments all over the world have used mechanical surrogates of real vehicles as part of simulated environments where human operators are trained to operate vehicles under combat or mission conditions. Perhaps the classic example of such a surrogate is a flight simulator which surrounds the flight crew and emulates the motion and environment of a cock pit. With respect to ground vehicle simulation, much research has been done by the United States Army. In particular, the US Army Tank-Automotive and Armaments Research, Engineering and Development Center (TARDEC) has been performing high-fidelity, real-time, man-in-the-loop simulations for a number of years. My invention is a method of generating a simulated terrain database that enhances TARDEC's simulation technology.

[0004] TARDEC's simulations are real-time in the sense that a computer's simulation clock is slaved to actual time, i.e., one second of simulation time on a computer takes one second to complete, no more, no less. TARDEC has integrated high-fidelity motion bases with a computer image generator (an Evans & Sutherland ESIG®-HD/3000 and a Harmony® image generator) and an audio generation system (AudioWorks 2™). This laboratory enhancement allows TARDEC to conduct soldier-in-the-loop testing to analyze the performance of new equipment, and just as importantly, to determine how effectively the soldier can use it in a simulated battlefield environment. TARDEC currently has two six-degree-of-freedom motion-based simulators. One is the Crew Station/Turret Motion Base Simulator (CS/TMBS), which has a bandwidth of ≈10 Hz and a payload capacity of greater than 25 tons. The CS/TMBS is built to handle complete turret systems as well as experimental crew stations. The CS/TMBS has a motion envelope of ±30 inches in translational motion (the x, y and z axes) and ±18° of rotational motion (roll, pitch and yaw). TARDEC's other motion-based simulator is the Ride Motion Simulator (RMS), a six degree-of-freedom simulator similar to the CS/TMBS but designed for a single crew member. The RMS has a vertical displacement of ±20 inches and ±10 inches in the horizontal (x and y) directions along with a rotational displacement of ±20° in roll, pitch and yaw. The RMS also has a bandwidth approaching 40 Hz in the vertical and 20 Hz in x and y. This simulator features an easily reconfigurable cab which will lend itself to quick experimental changes and re-testing. Both simulators' movements are controlled by real time mathematical models describing the dynamic characteristics of the particular vehicle being tested. These models receive inputs from a human driver (acceleration, steering, etc.) and reproduce accurate motion disturbances that the crew would feel.

[0005] TARDEC uses dynamic models in vehicle simulation techniques. A dynamic model is a mathematical representation of the vehicle being simulated running on a real-time computer. It is constructed using computer-based dynamics modeling and simulation algorithms tailored for real-time use. The model accurately incorporates characteristics of the suspension system, wheels or tracks, propulsion, weapon-stabilization system, etc. To accomplish its computer modeling, TARDEC has developed a real-time modeling methodology dubbed Symbolically Optimized Vehicle Analysis System (SOVAS) used to model high-fidelity dynamic systems. SOVAS is a methodology based in traditional C or FORTRAN language constructs and portable to many computer platforms. Currently, the SOVAS models are run over digitized test courses that the Army uses to baseline vehicle systems. These include test areas at the Aberdeen Proving Grounds, Yuma Proving Grounds, Ft. Knox and the Waterways Experiment Station. These courses are digitized to a resolution of 12 inches and are basically a dedicated path, meaning the model is not allowed to wander at will in any direction, but is slaved to a specified path through the test course. In this scenario, the inputs to the SOVAS model are velocity and braking.

[0006] The image generators mentioned above use a visual database to provide images to the user. The visual database uses a polygonal grid as its foundation such as that shown in FIG. 1. The grid is usually broken into triangles to guarantee polygonal planarity. To provide realism, the database is populated with various objects (trees, buildings, roads, etc.) and techniques such as Gouraud shading (Phong illumination in the latest image generators) and texture mapping are applied. The image generator's terrain database is created from terrain-position points and elevations stored in a digital format. The most common method of collecting and storing large terrain areas is to use the Digital Terrain Elevation Data (DTED) format, developed by the United States Government's Defense Mapping Agency. A limitation of DTED formatting is that it does not provide for terrain sampling at lower than 30 meter intervals. However, all image generators have polygonal output limitations since only so many polygons can be rendered in a frame. A quicker update rate (how fast the frame information changes) lowers the number of polygons that can be displayed. So, even though visual databases can be constructed with finer resolution than 30-meter intervals, rendering these databases is not practical or possible in real time.

[0007] TARDEC has incorporated the SOVAS dynamic model with the image generator. This allows for three degree-of-freedom user controlled movement of the model (x, y, yaw), with disturbances being calculated in the remaining degrees-of-freedom (z, roll, pitch). User inputs to the dynamic model now include steering as well as velocity and braking. The terrain the dynamic model is traveling over is the visual terrain database of the image generator. The terrain disturbance inputs to the dynamic model from the image generator are returned in one of two ways: 1) as a height-of-terrain value, or 2) as a planar equation (Ax+By+Cz+D=0) representing the equation of the terrain polygon the dynamic model is currently on.

[0008] However, either method is wrought with many problems. Mainly, as mentioned earlier, the resolution of the image generator's database is very low (between 30 m and 100 m). As an input to the dynamic model, it is equivalent to driving over a flat road. This defeats the purpose of a cross-country simulation, where terrain roughness may range from relatively mild (paved or unpaved road) to severe. Also, this method provides only geometric G⁰continuity. This first derivative is not continuous or is even geometrically discontinuous at polygon boundaries as shown at polygonal boundary 2 in FIG. 2. As an input to a mathematical system, this G⁰continuity will pose difficulty for mathematical integrators.

[0009] One method used to overcome these problems is to have a correlated terrain database sampled at a higher resolution to provide the higher frequency disturbances to the dynamic model. For example, the University of Iowa has developed a Virtual Proving Ground which uses this method, but the principal use of their driving simulator is for on-road conditions. The suspension system of the vehicle is used as a low-pass filter to help overcome the G⁰continuity problem. Other methods include simply introducing random high-frequency disturbances into the motion base directly or summing it with the image generator's database as an input to the dynamic model. While the Iowa method has merit, it has not totally solved the continuity problem. It was also developed at a time when computer power was much less than it is now, so calculations were minimized to a degree that is no longer necessary. Other methods involving random high-frequency disturbances exist and are known, but these methods are non-deterministic and unacceptable.

[0010] My invention is a method to create a high-resolution terrain database correlated to a computer image generator's low-resolution terrain database such as that provided by the ESIG®-HD/3000 or Harmony® generators. The high-resolution terrain database is comprised of a multiplicity of high-resolution surface patches that are overlaid upon the generator's lower-resolution database. The resulting hybrid terrain database has the following characteristics:

[0011] 1. G¹continuity throughout the entire terrain. G¹continuity occurs when the patches adjoin one another at common boundaries and any two adjoining patches share a common normal vector at each point along their common boundary.

[0012] 2. Infinite resolution across the terrain database (a continuous surface).

[0013] 3. Data storage needed to represent this terrain is held to a minimum.

[0014] 4. The frequency content and rms (root-mean-square) magnitude of the terrain database is user selectable.

[0015] Each patch is created using fractional Brownian motion approximated by spectral synthesis. After performing the proper filtering according to a user-defined frequency content range, a 2-D inverse Fast Fourier Transform is used to transform each patch of the surface to the spatial domain. Scaling is then performed to create a surface with the proper magnitude in terms of rms (root-mean-square) value. Then specific data points are extracted from the patches of the high-resolution surface at a sampling rate small enough to properly recreate the highest frequency content specified by the user. These data points are used as the control points in a NURBS (Non-Uniform Rational B-Splines) surface patch. These control points define the rough outline of the surface which lies within a convex hull defined by the control points. This set of control points are then overlaid upon the corresponding lower-fidelity terrain polygons, thus creating the correlated high-resolution terrain database. The correlated database may be regarded as a hybrid terrain database comprised of the image generator's terrain database modified by surface patches.

[0016] To ensure that the newly created terrain surface follows closely to the visual database, the control points are filtered. This gives the newly created surface a vertical offset of zero with respect to the polygonal boundaries of the generator's lower-fidelity terrain. This means that the high-fidelity surface patches will have the same height as the lower-fidelity surface at the polygon edges of the lower-fidelity surface. In this manner, a terrain database with G²continuity over most of the database and G⁰continuity at polygonal boundaries is created. Finally, the NURBS surface patches are modified at the surface patch boundaries to create G¹continuity among the patches.

[0017] FIG. 1 is a polygonal grid used by a visual database generator such as the Evans and Sutherland ESIG® HD/3000 generator.

[0018] FIG. 2 shows geometric discontinuity at a polygonal boundary within a simulated terrain.

[0019] FIG. 3 is a diagram of the environment in which my terrain database is used.

[0020] FIG. 4 is an example of a spectral array of sampling points generated in the first overall step of my method of producing a high-fidelity simulated terrain database.

[0021] FIG. 5 is the array of FIG. 4 after low-pass filtering has been performed.

[0022] FIG. 6 is the array of FIG. 5 after high-pass filtering has been performed.

[0023] FIG. 7 is an example of a truncated pyramid used in filtering a spatial representation of a surface patch generated in my method.

[0024] FIG. 8 is a truncated pyramid whose diagonal ditch corresponds to adjoining hypotenuses of triangles of a lower resolution surface.

[0025] FIG. 9(a) shows a simulated terrain surface before filtering according to my method. FIG. 9(b) shows that surface after low pass filtering. FIG. 9(c) shows the same surface after both low-pass and high-pass filtering.

[0026] FIG. 10 is an example of control point grids for adjoining arrays representing two surface patches.

[0027] FIG. 11 shows a multiplicity of adjoining arrays where ellipses enclose rows or columns of control points to be adjusted to achieve G¹geometric continuity over the entire surface represented by the arrays. Points common to a row and column to be adjusted are enclosed by circles.

[0028] FIG. 12 is an example of a surface terrain extracted from an image generator.

[0029] FIG. 13 is a plot of NURBS control points derived by my method and overlaid on the terrain Of FIG. 12 to create a hybrid terrain database.

[0030] FIG. 14 is a rendering of the surface represented by the arrays in FIG. 13.

[0031] FIG. 15 is a plot of the NURBS control points of FIG. 13 after smoothing is done to enhance geometric continuity.

[0032] FIG. 16 is a rendering of the surface represented by the points of FIG. 15.

[0033] FIG. 3 shows the environment in which the hybrid, high-fidelity terrain database will be used. There, a dynamic mathematical model 20 of the vehicle to be emulated is accessed by a computer's CPU 22. The CPU also accesses input from image generator 24 and the hybrid terrain database 28, which can be stored in the computer's memory. A human driver manipulates input devices 26 that effect virtual steering, acceleration and braking of the dynamic model of the vehicle. One result of the driver's inputs is that the vehicle model travels to and upon different zones of the terrain represented by database 28 as directed by the driver. At a given moment, only a portion of the control points of database 28 is used to generate a terrain surface and a visual representation thereof. That portion of the control points corresponds to the zone of the terrain surface where the vehicle model is at the given moment. The CPU does the necessary calculations on that portion of the control points to convert these points into a simulated terrain surface and the corresponding visual representation. The control points are a very efficient way of representing a large-area terrain, whereby a database for a large terrain area of, say 100 km by 100 km, can be stored in a computer. The CPU controls actuators 30 for the motion simulator in response to inputs from database 28, dynamic model 20 image generator 24 and driver input devices 26. Using the same inputs, the CPU controls graphical user interface 32, which typically includes a set of screens representing the viewing ports of a vehicle by which the driver views the simulated terrain. The CPU also controls audio output device 34.

[0034] The first step in creating my high-resolution database is to create sets of points that lie on spectral fractal Brownian surfaces that will become surface patches in the spatial domain. Three-dimensional spectral fractal geometry is used in the generation of the surface patches because it lends itself well to creating random surfaces. To create these arrays, one may first refer to the following discrete two-dimensional Fourier transform: $\begin{array}{cc}F\left(u,v\right)=\frac{1}{\mathrm{MN}}\sum _{x=0}^{M-1}\sum _{y=0}^{N-1}f\left(x,y\right)e^{-j\left(\frac{\mathrm{ux}}{M}+\frac{\mathrm{vy}}{N}\right)}& \left(1\right)\end{array}$

[0035] where f(x,y) represents a fractal Brownian surface in the spatial domain along the x and y axes, M samples are taken along the x axis and N samples are taken along the y axis, and F(u,v) represents the fractal Brownian surface in the spectral domain along the u and v axes. If, as I prefer in my method, x and y are sampled equally in a square array with size M=N, the above relationship simplifies to: $\begin{array}{cc}F\left(u,v\right)=\frac{1}{N}\sum _{x=0}^{N-1}\sum _{y=0}^{N-1}f\left(x,y\right)e^{-j\left(\mathrm{ux}+\mathrm{vy}\right)/N}& \left(2\right)\end{array}$

[0036] The two-dimensional Fourier series of equation (2) can be used to implement an algorithm to calculate values for points on spectral Brownian surfaces. To do so, let phase (the term e^{−j(ux+vy)/N}in equation (2)) be a random number between 0 and 2π. Also, for each point in the M×M array, let the amplitude (the term f(x,y) in equation (2)) be a different random number from a Gaussian distribution multiplied by the scaling factor $\sqrt{1/{\left(u^2+v^2\right)}^{H+1}}$

[0037] where the particular values for u and v at any given point are used for the scaling factor of that point, and H is the Hurst exponent.

[0038] Alternatively to equation (2), I prefer to use a trigonometric form of equation (1), which is: $\begin{array}{cc}F\left(u,v\right)=\frac{1}{\mathrm{MN}}\sum _{x=0}^{M-1}\sum _{y=0}^{N-1}{a}_{u,v}\left(\cos \omega +j\sin \omega \right).& \left(3\right)\end{array}$

[0039] where $\omega =2\pi \left(\frac{\mathrm{ux}}{M}+\frac{\mathrm{vy}}{N}\right).$

[0040] Here, a_u,vis a random number from a Gaussian distribution multiplied by the scaling factor $\sqrt{1/{\left(u^2+v^2\right)}^{H+1}}$

[0041] and the phase, ω, is a uniform random number between 0 and 2π.

[0042] As is known, H relates to the degree of fluctuation where a function or phenomenon exhibits random variations. For simple Brownian motion, H=½. For fractional Brownian motion generally, which includes spectral fractal Brownian motion, 1≦H≦0. As can be gleaned by observing the above scaling factor, the degree of fluctuation decreases as H increases in value, so that the roughness of a spectral fractal Brownian surface diminishes as H approaches 1. The Hurst component is related to the fractal dimension, D, which is a measure of complexity based on how fast length, surface or volume changes when measured with progressively finer scales. In the spatial domain, the Hurst exponent and the fractal dimension of a surface are related by the equation

[0043] D=3−H.  (4)

[0044] For a spatially generated fractal surface, D is defined in the range 2≦D≦3, with a value of D=2 generating a flat surface and a value of D=3 generating a surface approaching white noise. The aforementioned scaling factor thus can be rewritten as $\sqrt{1/{\left(u^2+v^2\right)}^{4-D}}$

[0045] and it can be seen that surface roughness increases with the fractal dimension. In the spectral domain, D has no upper and lower limits, D=4 represents a surface having white noise, D<4 gives a smoother surface and D>4 gives a rougher surface. As in the spatial domain, surface roughness increases with higher values of D. In either domain, the scaling factor has a tendency to act as a high-pass filter in the sense that D or H affects the maximum frequency values of u or v which have an appreciable affect on surface topography. A user of my method selects the fractal dimension as an input or alternatively the user selects the Hurst exponent, the respective value depending on the desired roughness of the terrain surface to be generated.

[0046] Other variables selected by the user are the maximum and minimum frequencies to be used in generating the terrain database or alternatively, the minimum and maximum wavelengths to be used. Inclusion of higher frequencies tends to give greater resolution, or fineness of detail, to the terrain represented by the database. However, given that the scaling factor will increasingly reduce the effect of successively higher frequencies, it is sensible to exclude frequencies above a certain level for the sake of computational economy, depending upon the desired level of resolution. For example, very small variations in terrain topography may be superfluous in simulations of a heavy combat vehicle interacting with the terrain. Likewise, as frequencies lower, they tend to introduce gradients in terrain so slight that they do not affect the vehicle performance modeled on that terrain. Thus it may be desirable to eliminate these frequencies below a chosen threshold for the sake of computational economy.

[0047] A further implication of the choice of maximum frequency or minimum wavelength is that this frequency Or wavelength affects the number of samples of F(u, v) from equation (3) that are needed to properly define a surface containing the chosen frequency range. The number of sampling points along the u vector and the v vector is chosen according to the Nyquist sampling criteria. To properly sample and reproduce a signal according to that criteria, the signal must be sampled at a rate at twice that of the its highest frequency component. Accordingly, in my method, the spatial sampling step size is no more than half the minimum wavelength used in generating a particular terrain surface. For a square array in the spatial domain having a side length l, the number of columns, N, and the number of rows, M, are related to sample step size by the formulae $\begin{array}{cc}\Delta x=\frac{1}{M}\mathrm{and}\Delta y=\frac{1}{N}& \left(5\right)\end{array}$

[0048] where Δx is the spatial sampling step size in the x direction and Δy is the spatial sampling step size in the y direction, M is the number of columns in the array and N is the number of rows in the array. Per the Nyquist criteria, Δx and Δy will be one-half the selected minimum wavelength. Of course, since the array is square, M=N and the number of samples is N². The side length, l, of the array is chosen according to the desired area size of the terrain unit to be generated. I prefer to increase the value of N²to the nearest power of 2. Thus if N²is 49, I increase N²to 64, or 2⁶. It is not necessary that N²be a power of 2, but a power of 2 is more efficient for Fast Fourier Transform algorithms, which are used at a later stage of my method. An example of a spectral array of sampling points is seen in FIG. 4, which shows F(u,v) for an array A in the spectral domain, where N=8. Note that the corner points of A (a_1,I,a_I,N/2+1,a_M/2+1and a_M/2+1,N/2+1) are real numbers. When the inverse 2-D Fast Fourier Transform is applied, the real numbers at the corner points of array A prevent the resulting spatial array from being complex.

[0049] For computer programming purposes, the following pseudocode will create any array A representing a spectral surface, using Equation (3) above:

[0050] Filtering

[0051] Once the spectral representation of the surface F(u,v) exists, filtering is done to bring the frequency content into conformity with the user's specified minimum and maximum frequencies, ω_Land ω_Hrespectively. The high-pass filter breakpoint, ω_L, and the low-pass filter breakpoint, ω_H, are derived from λ_maxand λ_minby: $\begin{array}{cc}{\omega }_L=\frac{2\pi }{{\lambda }_{\max }}\mathrm{and}{\omega }_H=\frac{2\pi }{{\lambda }_{\min }}& \left(6\right)\end{array}$

[0052] First, let low pass filtering be performed, thus removing all components of F(u,v) that have a frequency value greater than ω_H. While many filtering techniques exist, the simplest is rectangular filtering, where all the frequency components above ω_H(and their corresponding complex conjugates) are set to 0. While this method of filtering will introduce a ringing effect when the 2-D Fast Fourier Transform is done, this is not important because as NURBS control points are extracted during a later step in my method, this ringing is simply a minor random shift in the control points' z value. Using the most common case where the length of each side of the surface is equal and the number of samples in each direction are the same (M=N), Δx=Δy and Δu+Δv. The natural frequency, ω_a, of an element a_ijin the array A, which represents F(u,v), then is given by:

[0053] ω_a=Δu{square root over ((i−1)²+(j−1)²)}  (7)

[0054] As an example of low-pass filtering, if ω_H=4.9Δu, FIG. 5 shows the resultant matrix. Note that the imaginary frequencies are also set to 0 for frequency values that are removed. The following pseudocode will perform the low pass filtering:

[0055] High pass filtering is now performed to remove all frequencies less than ω_L. Using the same rectangular filtering, all terms with frequency content less than ω_Land their respective complex conjugates are set to 0. Letting ω_L=3.9Δu, FIG. 6 illustrates the spectral surface array after both the low- and high-pass filtering have been performed.

[0056] The following pseudocode will perform high-pass filtering:

[0057] It tends to be easier to filter the real frequencies, then copy the complex conjugates to where the imaginary frequencies are stored in the spectral array instead of performing the filtering on both the real and imaginary frequencies.

[0058] Now, using any acceptable Fast Fourier Transform routine, the representation of spatial surface f(xy), can now be created. It will be an array of points M×N in size (where preferably M=N) with spatial step sizes of Δx and Δy. The spatial surface will be comprised of a sum of sine waves between the frequencies ω_Land ω_H. The next step is to calculate the magnitude of the spatial surface in terms of root-mean-square, or rms, of a discrete 2-D surface represented by the array. I use the formula: $\begin{array}{cc}\mathrm{rms}=\sqrt{\frac{1}{\mathrm{mn}}\sum _{i=1}^m\sum _{j=1}^n{x}^2\left(i,j\right)}& \left(8\right)\end{array}$

[0059] where m is the number of columns in the array and n is the number of rows in the array. The resulting rms value for the array is compared to a rms value pre-selected by the user in accordance with the magnitude the user desires the generated terrain surface to have. Each of the points in the array is multiplied by a/b, where a is the desired rms value and b is the rms value of the array. The resulting array will have the desired rms value.

[0060] The resulting array can be regarded as representing a high-resolution square surface patch of terrain where the sides of the square patch have a length l. The patch will be superimposed onto a lower resolution surface generated by a computer image generator. As exemplified in FIG. 1, the computer-generated lower resolution surfaces are typically comprised of pairs of isosceles right triangles having a common hypotenuse, the pairs of triangles forming squares having diagonals running between opposed corners. It is contemplated that the side length, l, of the square patch is chosen to be equal to the side length of the square formed in the lower resolution surface. In the case where the triangles in the computer generated surface form non-square rectangles, the sides of the patches are chosen to equal the lengths of the sides of the non-square rectangles.

[0061] Before superimposing the patch onto the square or rectangle of the lower resolution surface, the surface boundaries, or edges of the patch are forced to zero. This forcing is done by filtering the spatial surface of the patch. One method of filtering is to multiply the spatial surface by a truncated pyramid, keeping the boundary points to zero while keeping the interior points at their constructed values with a small ramp between the boundary points and the interior points. FIG. 7 shows an example of a truncated pyramid used in filtering the spatial surface. The user may wish to force the patch not only to be bound to the lower resolution surface at the rectangular boundaries, but may also wish the patch to be close to the aforementioned diagonal (the boundary between the lower resolution surface's triangles). If so, the filtering can be done by using a truncated pyramid with a gain of one and a diagonal trench corresponding to the boundary between the triangles. An example of a truncated pyramid featuring a diagonal trench is shown in FIG. 8. Examples of the results of different filtering techniques are illustrated by use of FIGS. 9(a), 9(b) and 9(c). An unfiltered surface is shown in FIG. 9(a), a surface filtered by a truncated pyramid is shown in FIG. 9(b) and a surface filtered by a truncated pyramid having a diagonal trench is shown in FIG. 9(c).

[0062] With respect to FIG. 9(c), one notes that the values of the high-resolution surface patch along the diagonal are zero. However, in a NURBS (non uniform rational B-spline) surface corresponding to the patch created later in my technique, the points along the diagonal will not be forced completely to zero, but will merely be pulled toward zero. If the user wishes for the high resolution surface to be pulled closer to zero along the diagonal, the weights of control points on the diagonal can be increased in value relative to control points elsewhere on the NURBS surface.

[0063] Extracting NURBS Control Points

[0064] Once the filtering of the spatial surface of the patch is complete, one has an acceptable representation of a surface, which can be overlaid upon the corresponding portion of the lower-resolution image generator database to create the representation of a hybrid surface. Once the hybrid surface representation is created, the control points for the corresponding NURBS surface can be extracted from it. If one denotes the hybrid surface as f(x,y), then the sampling increment in the x and y directions, Δx and Δy, are defined as: $\begin{array}{cc}\Delta x=\frac{l_x}{M}\mathrm{and}\Delta y=\frac{l_y}{N}& \left(9\right)\end{array}$

[0065] where l_xis the length of the side of the surface patch along the x axis and l_yis the length of the side of the surface patch along the y axis, and f(x,y) is represented by an M×N array, which can be called P. Usually, as stated earlier M and N will be equal and f(x,y) will be a square surface patch. M can be unequal to N when, for example, the surface patch is rectangular, or when the surface patch has different frequency contents along the x and y axes so that Δx ≠Δy. Additionally, M can be unequal to N when special surface features require further manipulation of NURBS control points so as to necessitate a smaller sampling increment along one axis. Most commonly, though, the high-resolution surface patch is designed to introduce random elevation perturbations to a lower-fidelity surface patch. In this situation M=N, l_x=l_y, and Δx=Δy.

[0066] The surface that has been created, f(x,y), contains, as a minimum, all the necessary frequency content which has been specified by the user. To extract the NURBS control points from the surface, extraction steps along the x and y axes must respectively be less than $\frac{{\lambda }_{x\min }}{2}\mathrm{and}\frac{{\lambda }_{y\min }}{2}$

[0067] to satisfy the Nyquist sampling criteria. It will be recalled that the satisfaction of the Nyquist criteria was accomplished at an earlier stage of my method, when points were selected to represent a spectral fractal Brownian surface in the spatial domain. The number of sample points has remained constant up to this point in the method, whereby an appropriate number of sample points still exist to satisfy the Nyquist criteria in nearly all cases. Exceptions may occur, for example, if the user at this stage determines that the maximum frequency content of the surface can be lowered, so that the number of samples required by the Nyquist criteria becomes lower. In these exceptional cases, the extraction step size should be used which is the largest integer multiple of Δx and Δy that still satisfies the Nyquist criteria. To do this, find the largest value of k_xwhere $k_x\Delta x\le \frac{{\lambda }_{x\min }}{2}$

[0068] and the largest value of k_ywhere $k_y\Delta y\le \frac{{\lambda }_{y\min }}{2}.$

[0069] Since one needs to extract the first and last points, along each axis, adjust the foregoing values of k_xand k_yso that (M−1)/k_xand (N−1)/k_yare integers that will satisfy the extraction step criteria. Then select the first point along each axis and continue e at an increment of k_xΔx in the x direction and k_yΔy in the y direction. The control points now form a new 2-D array P_newof new size M_p×N_pin contrast to the previous array P, whose size is M×N.

[0070] Characteristics of the NURBS Control Points and Surface

[0071] The aforementioned control points of P (or P_new) for the NURBS surface are homogeneous points represented as the quadruplet (w_i,jx_i,j, w_i,jy_i,j, w_i,jz_i,j, w_i,j) where w_i,jis the weight assigned to the control point P_i,j. The weights are user selectable and have the effect of pulling the NURBS surface closer to the control point as w_i,jincreases. Setting w_i,jto zero has the effect of removing the control point from the surface. Setting all the weights to the same value reduces the NURBS surface to a B-spline surface. A more general discussion of NURBS surfaces, including control points, weights and other subjects has been published by L. Piegl and W. Tiller in The NURBS Book,2^ndEdition,Springer-Velag, Berlin, 1997.

[0072] NURBS were chosen for the final representation form of the high-resolution terrain because they exhibit the following important properties: the surface follows the shape of the control point polygon and is constrained to lie in the convex hull of the control points; an affine transformation can be applied to the surface by applying the affine transformation to its control point representation; the curve or surface exhibits local control (a control point is connected to a limited number of nearby curve segments or surface sections, and moving a control point can influence only these segments or sections); since NURBS are rational, higher weights at certain knot values will draw the surface closer to the control points; and the curve or surface, while defined by a finite set of control points and knots, has continuous resolution.

[0073] Once the control point array P has been created, two knot vectors need to be created. The knot vectors U and V correspond to the x and y directions, respectively. Let the degree (the highest exponent for a variable in an equation representing the surface) of the surface in the x direction be denoted as p and the degree of the surface in the y direction be denoted as q. If the number of control points in the x direction is m and the number of control points in the y direction is n, then the number of knots in U will be r+1 and the number of knots in V will be s+1 where

[0074] r=m+pand s=n+q  (10)

[0075] The knot vectors are defined as $\begin{array}{cc}V=\left\{\underset{\underset{q+1}{⏟}}{0,\dots 0},v_{q+1},\dots ,v_{s-q-1},\underset{\underset{q+1}{⏟}}{1,\dots 1}\right\}& \left(11\right)\end{array}$

[0076] where the horizontal brackets indicate that U has p+1 knots whose value is 0 and has p+1 knots whose value is 1, and $\begin{array}{cc}U=\left\{\underset{\underset{p+1}{⏟}}{0,\dots 0},u_{p+1},\dots ,u_{r-p-1},\underset{\underset{p+1}{⏟}}{1,\dots 1}\right\}& \left(12\right)\end{array}$

[0077] where the horizontal brackets indicate that U has q+1 knots whose value is 0 and has q+1 knots whose value is 1. For a cubic NURBS surface, p=q=3 and U has m+4 knots in the vector and V has n+4 knots in the vector. The knot vectors will look like:

[0078] U={0,0,0,0,u₅. . . u_m,1,1,1,1}  (13)

[0079] V={0,0,0,0,v₅. . . v_m,1,1,1,1}  (14)

[0080] Typically the knot values are spaced equidistantly between 0 and 1.

[0081] Continuity among Surface Patches

[0082] The final step in the creation of a high-resolution surface overlay is to create G¹continuity between surface patches. The definition of geometric continuity between two adjacent surfaces P and Q is: G⁰continuity exists if P and Q share a common boundary; and G¹continuity exists if P and Q share a common normal vector at each point along the common boundary. The first step in achieving G¹continuity is to ensure that the number of control points for surface patches P and Q along the common boundary are equal. If they are not, apply the technique of knot insertion described in the section described below. If they are equal, one can proceed directly the surface smoothing described in the subsequent section.

[0083] Knot Insertion

[0084] As stated by Piegl and Tiller, supra, knot insertion can be used to: evaluate points and derivatives on curves and surfaces, subdivide curves and surfaces, and add control points in order to increase flexibility in shape control (for interactive design). To begin the knot insertion process, let $\begin{array}{cc}{C}^w\left(u\right)=\sum _{i=0}^n{B}_{i,p}\left(u\right)P_i^w& \left(15\right)\end{array}$

[0085] be a NURBS curve defined on U={u₀, . . . ,u_m} where B_i,p(u) are the p^thdegree basis functions and P_i^ware the control points. While this method is detailed here using curves, it is easily expanded for use on NURBS surfaces. If one wishes to insert a knot {overscore (u)} into U to form the new knot vector {overscore (U)}={{overscore (u)}₀=u₀, . . . ,{overscore (u)}_k=u_k,{overscore (u)}_k+1={overscore (u)},{overscore (u)}_k+2=u_k+1, . . . ,{overscore (u)}_m+1=u_m}, the new curve $\begin{array}{cc}{C}^w\left(u\right)=\sum _{i=0}^{n+1}{\stackrel{\_}{B}}_{i,p}\left(u\right)Q_i^w& \left(16\right)\end{array}$

[0086] is created using the modified basis functions {overscore (B)}_i,p(u) and the new set of control points Q_i^w. From Piegl and Tiller, supra, we are given the relationship between the original control points P_i^wand the new control posts Q_i^wresulting from inserting a knot as

[0087] P_l^w=Q_i^wi=0, . . . ,k−p−1

[0088] P_i^w=Q_i+1^wi=k=1, . . . ,n  (17)

[0089] We seek control points Q_i^wfor i=k−p, . . . , k. Piegl and Tiller, supra, provide a complete theoretical description of inserting knots and creating a new set of control points. The equations below present the final solution for doing so. Let $\begin{array}{cc}\alpha =\{\begin{array}{cc}1& i\le k-p\\ \frac{\stackrel{\_}{u}-u_i}{u_{i+p}-u_i}& k-p+1\le k\\ 0& i\ge k+1\end{array}& \left(18\right)\end{array}$

[0090] and

[0091] Q_i^w=a_iP_i^w+(1−a_i)P_i−1^w  (19)

[0092] For a surface, this method would be applied in both the u and v axis as needed to make the number of control points in each surface patch equal. Note that if knot insertion is used and control points are added along the surface edges, spatial surface filtering will have to be performed again to bring the edge control points to zero, giving us G⁰continuity between patches.

[0093] Surface Smoothing

[0094] Now that the adjacent surface patches P and Q have the same number of control points along the common boundary, an algorithm to achieve G¹continuity can be applied to them. Various studies have been performed on geometric continuity between adjacent NURBS surface patches. (Oppenheim A. V., Schafer R. W., Discrete-Time Signal Processing,Prentice Hall, Englewood Cliffs, N.J. 07632; Zhou, S., Yang H., Tangent Plane Continuity Condition Between Adjacent NURBS Surface Patches, Proceeding from the Fourth International Conference on Computer-Aided Design and Computer Graphics, Oct. 23-25, 1995; Lizhaung Ma and Zhijun He, Methods and Techniques for Advanced Curve and Surface Modeling,Proceeding from the Fourth International Conference on Computer-Aided Design and Computer (Graphics, Oct. 23-25, 1995; Barsky B. A. and DeRose T. D., Geometric Continuity of Parametric Curves: Three Equivalent Characterizations,IEEE Computer Graphics and Applications, Vol. 9, No. 6, 1989; and Barsky B. A. and DeRose T. D., Geometric Continuity of Parameteric Curves: Construction of Geometrically Continuous Splines,IEEE Computer Graphics and Applications, Vol. 10, No. 1 , 1990.) Fortunately, since one is creating a random surface in my method, one is not bound by the tight restraints that normally otherwise govern the manipulation of NURBS surfaces when achieving G1 continuity.

[0095] By performing the filtering described earlier, all surface patches were manipulated so that the z values of the edges of the patches were set to zero before they were overlaid upon the lower-resolution terrain. This produces G⁰continuity between surface patches. Put simply, all the surface patch edges meet (there are no gaps between surface patches), but they have different surface normals at the points where they meet. If a row or column of control points along the surface are manipulated, we are still left with a random surface, which meets the initial goal of a cross-country terrain representation to provide high-fidelity perturbations to a vehicle dynamic model.

[0096] FIG. 10 shows a sample control point grid for adjacent surface patches P and Q. The number of the control points along the common boundary between patches P and Q are equal, thus making it simpler to guarantee G¹continuity between the surface patches. One now need only adjust the vectors that connect points in the shared column or boundary (“SC” in FIG. 10) with control points in the columns to either side (“LC” and “RC”). These vectors are adjusted to have the same direction and have a constant factor for magnitude along the boundary. Due to the filtering performed previously, the boundary control points of array P are equal to the boundary control points of array Q along the edge between P and Q. That is, in FIG. 10, P_i,n=Q_i,1for 1≦i≦m. Now we make an adjustment to the column of control points P_i,n−so that the three columns of control points P_i,n−1, P_i,n(which is also Q_i,1) and Q_i,2are linear (on the same straight line) for all i, where 1≦i≦m. This adjustment also causes the set of vector lengths between P_i,n−1and P_i,n(or Q_i,1) to have a constant ratio with corresponding vector lengths between P_i,n(or Q_i,1) and Q_i, for all i, where 1≦i≦m. That is $\begin{array}{cc}\underset{P_{i,n-1}{P}_{i,n}}{\to }=k\underset{Q_{i,1}{Q}_{i,2}}{\to }\mathrm{for}1\le i\le m& \left(20\right)\end{array}$

[0097] Although the foregoing aspect of surface smoothing was described in terms of adjusting columns of points in spectral arrays, the aspect of surface smoothing is also useful for adjusting rows of points in adjoining arrays.

[0098] The final step in surface smoothing is to take note of the interior corner control points, which are circled in FIGS. 10 and 11. These control points are shared by the row and column of control points that need to be manipulated to achieve G¹continuity. A solution exists in which this control point will satisfy the conditions for G¹continuity simultaneously for both the border and row column of control points. See Nachman, L. J., Matching NURBS Surfaces G¹and G², Presented to Mathematics of Curves and Surfaces VI, Brunel University, 1994. Although the Nachman paper has been published for several years, a copy of the Nachman paper is attached as an Appending at the end of this application for convenient reference.

[0099] G¹Continuity Example

[0100] As an example of my method of generating a terrain surface, FIG. 12 shows a surface terrain extracted from an image generator. The terrain surface consists of 18 triangular polygons grouped into 9 square polygons. Each side of the square polygons is 30 m in length. The high-resolution overlay was created using the following parameters:

[0101] Maximum Wavelength=15 m

[0102] Minimum Wavelength=30 m

[0103] rms value=0.5 m

[0104] Fractal Dimension=1.0

[0105] The following steps were then performed: creating a high-resolution surface using spectral fractal geometry, performing the low- and high-pass filtering in the frequency domain, converting it to the spatial domain, performing magnitude scaling, edge-filtering and then overlaying the surface upon the low-resolution image generator's surface. As a result of these steps, one obtains a set of control points, which comprise the high resolution surface. FIG. 13 is a plot of these control points and FIG. 14 is the actual rendering of the surface. Notice the circled areas in FIG. 14 which represent the areas where G⁰continuity exists at the surface patch edges where the edges are obvious to the naked eye.

[0106] The smoothing methods described previously are then applied to the control point array from FIG. 13, which generated the G⁰surface. Starting from the point (0,0) and moving out, the next to right column and next to top row in each surface patch were manipulated to provide G¹continuity. The resultant control point plot is given in FIG. 15 and the corresponding surface is shown in FIG. 16. Note the area circled in FIG. 16 and compare them to the circled areas in FIG. 14. One can notice the smoothing where the surfaces come together. Each surface is a 20 m×30 m patch, so looking at the boundaries (along the 0 m, 30 m, and 60 m grid lines) will point out the benefits of G¹smoothing.

[0107] Computer Code for NURBS Surface Creation

[0108] Code has been developed in MATLAB™ which perform the following functions:

[0109] 1 Provide a GUI to enable user input of the surface parameters.

[0110] 2 Create the spectral surface using spectral fractal geometry (the Fourier filtering method of fractional Browning motion).

[0111] 3 Perform spectral filtering to create a surface in the specified frequency range.

[0112] 4 Perform a 2-D inverse FFT to create a spatial surface.

[0113] 5 Perform magnitude scaling to achieve the desired rms value.

[0114] 6 Filter the spatial surface to provide G⁰continuity.

[0115] 7 Manipulate the control points to achieve G¹continuity

[0116] 8 Pass the control points and knot vectors to a Visual C++™ program for surface analysis.

[0117] 9 Provide a suite of plotting tools.

[0118] The code used to perform the NURBS surface analysis was based upon pseudo code provided by Piegl and Tiller, supra, and is written in Visual C++™ on a Windows NT™ platform. This code is presented below as Table A and reads in data files created by the MATLAB™ program (produced by the Math Works, Inc., 24 Prime Park Way, Natick, Mass.) and writes the surface to a data file which the MATLAB™ program will read in. It was decided to write the NURBS surface evaluation code in Visual C++™ for the sake of portability.

[0119] I wish it to be understood that I do not desire to be limited to the exact details of construction or method shown herein since obvious modifications will occur to those skilled in the relevant arts without departing from the spirit and scope of the following claims.