__amazing demo__. This article will only discuss the second difficulty, building the height field for waves using Fast Fourier Transformation (FFT).

There are many, many complicated equations in Tessenforf's paper. The first time when I read it, it appeared math-intense. However, most of them are not directly related to building the height field for waves, but are important oceangraphic concept, such as Gerstner Wave. Here, I will try to illustrate it in an as simple as possible way and will only discuss several key equations that's directly related to implementing this algorithm.

This algorithm is based on a statistical model, in which wave height is a random variable of horizontal position and time,

*h*(

*X,t*). It decomposes the wave height field into a set of sinus waves with different amplitudes and phases. The model itself provides us with a method to generate these amplitudes and phases, and we use inverse FFT as a mean to quickly evaluate the sum of these sinus waves.

First, let's take a look at the equation of which we need to perform FFT to evaluate the sum:

*h*(x, t) represents the height at horizontal position

**x**= (x, z) at time t. Each ~h(

**k**, t) is a complex number that represents a set of amplitude and phase at time t, and the vector

**k**points to the direction of travel of the given wave, with a magnitude

*k*dependent on the length of the wave(λ):

*L*is the size of the height field we animate, and

*N*is the resolution of the grid(dimention of FFT), then we can get a discrete range of vector

**k**.

**k**, we now need to know how to generate amplitude and phase for each ~h(

**k**, t). Oceangraphic research has proposed a particular spectrum for wind-driven waves larger than capillary waves in a fully developed sea, the Phillips spectrum, which is defined by the following equation.

We now want to generate a set of time-dependent amplitude and phase with Phillips spectrum. To do that, we first need to create a set of amplitudes and phases at time zero, and then we animate the field. The following equation will finish the first task.

**k**, t)=~h(-

**k**, t). Above is the equation for generating each ~h(

**k**, t) at different

**k**and t. The only thing we don't know about know is the wave frequency w(

*k*). For water waves there is a well-known relationship between these frequencies and the magnitude of the corresponding wavevectors, ki. In deep water, where the bottom may be ignored, that relationship is:

*g*is again the gravitational constant and

*k*is the magnitude of vector

**k**.

Now, we have a set animated amplitudes and phases to which we can perform FFT to evaluate the sum. We can also perform FFT to other equations to producing the choppy vectors as well as slope vectors of the height field, but they are not discussed here.

The computational cost of performing FFT with dimensions of 512x512 is extremely high on CPU. Therefore I implemented it on the pixel shader on the GPU, the parallel computing ability of which vastly enhances the efficiency of this algorithm, and enable it to run in real-time.

FFT is a delicate algorithm. The basic idea can be illustrated by the figure below:

My implementation is simply to first pre-compute all the indices and weights(W) in the figures above and pack the pre-computed data into a texture. At each stage, these indices and weights are fetched in the pixel shader and used to perform a single butterfly operation. Two Ping-Pong textures are used to write data back and forth between stages. The following is the HLSL code for a basic butterfly operation along the horizontal direction.

**k**, t), the animated amplitudes and phases produced by the Phillips spectrum, and h(

**x**, t), the height field for waves.

__here__.

oceanmesh1.obj |