Keywords: Rivers, wave simulation, animation, phenomenological simulation, vector representation, real-time, natural phenomena Rivières, simulation de vagues, animation, simulation phénoménologique, représentation vectorielle, temps réel, phénomènes naturels

We present a feature-based vector simulation approach for simulating local wave phenomena which often appear in running streams. By using this approach, we simulate the quasi-stationary waves caused by obstacles in shallow water. The geometric features of the waves are constructed and animated using vector representation. The vector data is then converted to feature aligned meshes for capturing the shape of the waves. Our approach provides high-resolution details with real-time performance, and allows users to intuitively control the simulation behavior.

Introduction

Simulating fluids (e.g., liquids, gases) is an important topic in computer graphics because it has a wide range of applications, including video games, film effects and simulators. For water, many efforts have been put on simulating surface waves. This is because the most distinct visual impression of large bodies of water in the natural world (e.g., river, lake, and sea) is the distortion of reflection and refraction due to the deformation of the water-air surface.

To date, studies on the simulation of water waves have yielded many realistic results, but many local wave phenomena (Fig. 1) that can be often found in running streams still can not be easily handled by existing methods. Simulating these phenomena are challenges especially when we target real-time interactive applications where users are allowed to dynamically decide to observe any feature in a very close view or in a very wide view. Relying solely on Computational Fluid Dynamics (CFD) simulations [START_REF] Foster | Practical animation of liquids[END_REF] would require very high resolution discretization, which is not compatible with the large scale of the background fluid domain and the real-time context. Moreover, poor controllability is another shortcoming of using CFD techniques. There is no intuitive relation between the control variables (e.g., initial and boundary conditions) and the simulation behavior. On the other hand, there exists some nonnumerical simulation methods for simulating water waves that are often fast and stable [START_REF] Tessendorf | The elements of nature: interactive and realistic techniques[END_REF][START_REF] Yuksel | Wave particles[END_REF]. But it is not clear how to extend these methods to simulate the waves we focus on.

In this paper, we propose a feature-based vector simulation approach in order to simulate the local waves with given flow data (2D horizontal velocity and depth) of streams. Note that the resolution of the input flow data can be much coarser than the wave details we want to present. Our approach is based on the observation that most of the local wave phenomena have quasi-regular and quasi-stationary geometric structures. The idea is to separate the representation for animation and rendering. We use vector representation to capture the geometric feature and motion behavior of the target waves. The concise vector representation allows low cost animation and provides good controllability. The simulated vector information are then converted to high resolution representation, such as meshes, which is suitable for high-quality rendering. Since the high-resolution is only used for local features, we still can ensure high performance.

We apply the presented approach to simulate the wave pattern caused by the obstacles in shallow streams (Figs. 1a and1b). It is a common phenomenon in nature, but no existing method in computer graphics could ever simulate it. In this case, we treat wave crests as the geometric feature of the wave pattern. We construct the wave crests by using the knowledge from classic hydrodynamics without numerical simulation. This geometric construction technique is mostly based on our previous work [START_REF] Neyret | Phenomenological simulation of brooks[END_REF], but we have improved it for better robustness and performance. For high-quality rendering, we build feature aligned meshes along the wave crests with user defined wave profiles. Moreover, we handle wave intersection (Fig. 1c) that often appears between two close obstacles. Our results demonstrate that the presented approach provides high resolution details and real-time performance.

The rest of the paper is organized as follows. After briefly summarizing related work, we describe the input data of our model in Section 3. The two parts of our method: vector simulation and surface construction are presented in Sections 4 and 5, respectively. Section 6 gives implementation details. We demonstrate our results in Section 7. Finally, we conclude with possible future work in Section 8.

Related work

State-of-the-art water animation techniques generally rely on numerically solving full 3D Navier-Stokes equations [START_REF] Foster | Realistic animation of liquids[END_REF][START_REF] Stam | Stable fluids[END_REF] and tracking the water surfaces with the level set method [START_REF] Foster | Practical animation of liquids[END_REF][START_REF] Enright | Animation and rendering of complex water surfaces[END_REF]. Though the performance of these techniques can be improved by using adaptive grids [START_REF] Losasso | Simulating water and smoke with an octree data structure[END_REF][START_REF] Irving | Efficient simulation of large bodies of water by coupling two and three dimensional techniques[END_REF], they are still not practical in real-time graphics, especially for handling the surface waves of large bodies of water.

One way of reducing the computational complexity is to neglect the 3D features of waves, i.e., to model the water surfaces with height fields. In this case, various simplified fluid equations could be derived from 3D Navier-Stokes equations with different assumptions. Kass and Miller [KM90] used linear wave equation to simulate waves with small amplitude in shallow water. Layton and van de Panne [START_REF] Layton | A numerically efficient and stable algorithm for animating water waves[END_REF] simulated waves by solving 2D shallow water equations with a semi-Lagrangian time integration method. Chen et al. [START_REF] Chen | Real-time fluid simulation in a dynamic virtual environment[END_REF] used the pressure solved from 2D Navier-Stokes equations to modulate the height of water surfaces. In a small bounded domain, these methods are applicable for generating waves with limited resolution in real-time interactive applications.

Instead of numerically simulating fluid motion, some wave models reconstruct the water surfaces directly from the geometric or statistical properties of waves. This kind of approach appeared earlier than did the physically-based simulation in graphics communities, but it is still the first choice in many today's industry applications due to their advantages of fast and stable computation, low memory cost and high controllability. Perlin noise [START_REF] Perlin | An image synthesizer[END_REF] can be used for modeling random waves with very low computational cost. Classic procedural wave models approximate deep water waves by superposing sinusoidal functions [START_REF] Max | Vectorized procedural models for natural terrain: Waves and islands in the sunset[END_REF][START_REF] Fournier | A simple model of ocean waves[END_REF][START_REF] Darwyn | Modeling waves and surf[END_REF]. By introducing an adaptive scheme, Hinsinger et al. [START_REF] Hinsinger | Interactive animation of ocean waves[END_REF] achieved interactive animation of unbounded ocean surfaces. Instead, FFT wave models [START_REF] Mastin | Fourier synthesis of ocean scenes[END_REF][START_REF] Tessendorf | The elements of nature: interactive and realistic techniques[END_REF] perform the superposition in INRIA the spectrum domain, and thus the statistical wave spectrum of real ocean can be easily applied.

There existing some wave models which focus on local wave phenomena. Glassner [START_REF] Glassner | [END_REF] simulated ship waves by geometric construction. However, in his method the interaction between the waves and other floating perturbations (e.g., leaves) is not possible. Most recently, Yuksel et al. [START_REF] Yuksel | Wave particles[END_REF] proposed a concept called wave particles to efficiently simulate surface waves triggered by object-water interaction. However, this method does not treat the waves related to water current.

Input data

The physical cause of the wave phenomenon we focus on is related to the local flow conditions such as flow velocity and water depth. We take this data as the input of our simulation.

Since everyday rivers are calm, we can model the river flow with the superposition of a steady mean flow and time-varying perturbations. We precompute the steady velocity v s and water depth h by solving the shallow water equations with the finite volume method [START_REF] Wu | Depth-averaged two-dimensional numerical modeling of unsteady flow and nonuniform sediment transport in open channels[END_REF]. Note that the resolution of simulation could be much coarser than the resolution required by the rendering. To enhance the dynamic details of the velocity field, we make the steady velocity field quasi-stationary by superimposing the velocity fields of local perturbations v p i on it as in [START_REF] Wejchert | Animation aerodynamics[END_REF]:

v = v s + ∑ i v p i . (1)
For example, v p i can be the analytic solution of sink, source or vortex with a cutoff radius. Note that these perturbations should be advected with the stationary flow v s .

Vector simulation

We assume that the predominant stationary wave caused by an obstacle in a shallow stream can be approximated by the shallow water theory [Sto57, page 22], which suggests that its wave speed is independent of its wavelength:

|c| = gh, ( 2
)
where g is the gravitational acceleration and h is the local water depth. Using the analogy of the shallow water theory with compressible gas dynamics, we call the wave shockwave in the following discussion. In addition, we assume that the shockwave triggers a series of ripples upstream of it. Fig. 2 gives a schematic illustration of our assumptions. In the following, we examine the geometric properties of the shockwave. In a running stream, a wave can be stationary provided the wave speed

|c| = |v| cosα, ( 3
)
where v is the local flow velocity and α is the propagation angle of the wave relative to the upstream direction (Fig. 3). Therefore, the crest of a shockwave should lie at an angle to the upstream direction. Now, let us examine where the most upstream point, starting point, of a shockwave locate (Fig. 4). At the starting point, the wave crest should be orthogonal to v, i.e., α = 0. Substituting it into Eq. 4, we get |v| = √ gh. To facilitate further discussion, we remind the Froude number:

α = arccos √ gh |v| (4)
F r = |v| √ gh . (5)
A supercritical flow (F r > 1) past an obstacle will leave a subcritical area (F r < 1) in front of the obstacle (Fig. 4). This means we can expect to find a starting point at the boundary of the subcritical area where F r = 11 . Based on the above observation, we can construct the shockwave crest in front of an obstacle as follows (Fig. 4):

1. Identify a subcritical region upstream from the obstacle by constructing a contour line of F r = 1 (Section 4.1).

2. Find the starting point of the shockwave along this contour line (Section 4.2).

3. Generate particles at the starting point and advect them to trace the shockwave crest according to Eq. 4 (Section 4.3).

For animating the wave, we update the starting point at every frame according to local time-varying velocity (Section 4.4).

Constructing the contour line of F r = 1

When a flow passes an obstacle, there must be a point, called stagnation point, along the boundary of the obstacle where |v| = 0, i.e., F r = 0. In addition, there are two endpoints, where F r = 1, on the two sides of the stagnation point (Fig. 4). Starting from one of the endpoints, we can trace a contour line in the triangular mesh of the water surface from cell to cell by linking linearly interpolated points on cells' edges where F r = 1. The tracing procedure stops until it reaches another endpoint. Finally, we can get a contour line that consists of straight line segments by connecting these points.

To find the endpoint, we search edges along the boundary of the obstacle, starting from the edge containing the stagnation point. For the edge containing the stagnation point, if F r ≥ 1 at one of the nodes of the edge, we can find an endpoint on this edge between the stagnation point and the node by interpolating (Fig. 5a). For other edges, an endpoint exists if and only if F r ≤ 1 at one node and F r ≥ 1 at the other node (Fig. 5b).

Finding the shockwave starting point on a contour line

As stated earlier, the wave starting point should lie on the contour line of F r = 1, and the flow velocity v should be orthogonal to the wave crest at the staring point. Furthermore,

v 0 v 1 l iso Fr=1 (a) l 0 l 1 v iso Fr=1 (b)
Figure 6: The starting point of a shockwave can be found on the contour line of F r = 1. Since the contour line consists of line segments, the starting point may locate (a) on a segment where

(v 0 • l) • (v 1 • l) ≤ 0, or (b)at a node where (v • l 0 ) • (v • l 1 ) ≤ 0.
the wave crest should be tangent to the contour line at the starting point, otherwise the wave crest will enter into the subcritical area where F r < 1 and Eq. 2 can not be satisfied. Therefore, we can find the starting point along the contour line of F r = 1 by searching the location where flow velocity v is orthogonal to the contour line. Since the contour line consists of line segments in practice, we find the starting point by approximation. We first try to find a segment with direction l which satisfies:

(v 0 • l) • (v 1 • l) ≤ 0, (6)
where v 0 and v 1 are the flow velocities at the two ends of the segment (Fig. 14a). Once having found such a segment, we interpolate along this segment to find the starting point. If no such segment is found, we use the node which satisfies

(v • l 0 ) • (v • l 1 ) ≤ 0 (7)
as the starting point. Here, v is the flow velocity at the node in question, and l 0 and l 1 are the directions of the two segments connected to this node, respectively (Fig. 14b).

Tracing wave crest with particles

Once having obtained the starting point of a shockwave, our task is to trace the wave crest. Before introducing our method, let us first investigate the behavior of the elements of a stationary wave (Fig. 7). In a running stream, waves not only propagate at the wave velocity c but also advect with the current of velocity v. Hence the resultant velocity of a wave element is the vector sum of the two velocities:

v e = v + c. (8)
Eq. 2 tells us that the component |v| cos α of stream velocity at right angles to the crest cancels the crest's motion at the wave speed |c|. Thus we have

|v e | = |v| sin α = |v| 2 -|c| 2 , (9)
and v e is tangent to the wave crest. Based on the above observation, we propose a method from the Lagrangian point of view. We uses particles to represent the wave elements discussed above. At each time step, we generate two new particles respectively at the two sides of a shockwave starting point and update all existing particles with v e . In addition, in order to imitate the attenuation of wave energy, we associate an intensity value to each particle. The intensity value starts from 1 and linearly decrease to 0 in a given time period. We kill a particle once its intensity value vanishes. Finally, connecting existing particles with line segments gives us a shockwave crest (Fig. 4).

Animating the waves

In our previous work [START_REF] Neyret | Phenomenological simulation of brooks[END_REF], the steps presented in the previous subsections were executed every frame for accounting for the time-varying velocity field. That is to say, we reconstruct the whole contour line of F r = 1 at each time step. However, this might occasionally yield discontinuous constructions which lead to the popping of wave crests. Since the water flow considered in our problem is quasi-stationary with small perturbations, it is not necessary to reconstruct the contour line of F r = 1. For obtaining better robustness and higher efficiency, we construct the contour line and find the corresponding shockwave starting point only once. At every frame, we update the shockwave starting point according to local velocity perturbations. For a shockwave starting point x, we store its initial location x 0 and a local steady velocity gradient dv 0 = ∇|v s (x 0 )|. As shown in Fig. 8, at each time step we update x with an offset λ from x 0 along the direction dv 0 :

x = x 0 + λ dv 0 |dv 0 | , (10)
to ensure |v(x)| = |c|, i.e., , Fr = 1. Now our goal is to solve λ at each time step. Using linear approximation, we can estimate stationary flow velocity v s (x) with

v s (x) ≈ v s (x 0 ) + λ dv 0 . (11)
In addition, we assume that only the nearest perturbation v d has a significant influence on the position of the shockwave starting point. Substituting Eqs. 10 and 11 in Eq. 1 yields

|v(x)| = |v s (x 0 ) + λ dv 0 + v p (x 0 + λ dv 0 |dv 0 | )| = |c| (12)
Finally, we can solve the above equation for λ by using a simple iterative scheme.

Efficient high quality rendering of waves

We next turn to the problem of rendering a water surface on which the quasi-stationary waves caused by obstacles are present. We aim at quality rendering with minimum memory and computation cost. In real-time graphics, the surface of a large body of water is often represented by a height field. However, this regular grid representation is not optimal in our case. On one hand, the wave phenomenon we focus on is local, i.e., it appears only at some specific locations but not everywhere in the flow domain. Therefore, a wanted representation scheme should be adaptive, i.e., use higher resolution at wave locations and lower resolution elsewhere. On the other hand, as shown in Fig. 9, using a mesh aligned with a feature line is preferable than using a regular grid for reducing geometric aliasing and normal noise [START_REF] Botsch | Resampling feature and blend regions in polygonal meshes for surface anti-aliasing[END_REF].

To overcome the shortcomings of height fields, we propose an adaptive representation scheme by exploiting the vector wave information that results from our simulation model. We model the water surface by superposing wave surfaces on a mean water surface (Fig. 10). As has been stated in Section 3, the mean water surface is treated as the input of our method which is represented by a coarse mesh. Each wave surface is represented by a fine mesh strip aligned to the feature curve of the corresponding wave. In the next subsection, we present how to construct these wave surfaces and superimpose them on the mean water surface. Then, we handle wave intersection in Section 5.2.

Figure 9: Left: Using a regular grid over the domain, cells as thin as a narrow feature can still generate very distracting geometric aliasing. Middle:

The sampling rate should be even greater, given by Shannon's theorem. Right: Using a mesh aligned with the feature line prevents geometric aliasing with fewer cells.

Constructing wave surfaces along shockwave crests

The waves produced by an obstacle in the flow consist of a dominating shockwave and a train of parasitic ripples upstream of it. To construct the wave surface, in theory we need to simulate the crests, profiles and amplitudes of both the shockwave and the ripples. However, what we can obtain now from the simulation model introduced in the previous section is only the shockwave crests. Fortunately, one important feature of the wave pattern we target is that all the wave crests are nearly regular and parallel. Therefore, it is reasonable to assume that the wave surface to be constructed is the resultant of sweeping a profile curve along a shockwave crest (Fig. 11). Here, the profile curve represents the superposition of one shockwave and a series of ripples. With this assumption, we are able to define the wave surface based on simulated shockwave crests and user given profile curves.

We formulate the surface definition as follows. The sweeping operation uses a shockwave crest as its base curve C(u). Let T, B, N be a local frame moving along the base curve, with T the unit tangent to the base curve, N the normal of the mean water surface, and B = T × N. Given a normalized wave profile z(v), a wave amplitude function a(u) and a wave width function w(u), we define the parameterized wave surface as:

S(u, v) = S b (x(u, v)) + a(u) • z(v) • N, (13)
where S b is the base water surface and

x(u, v) = C(u) + v • w • B. (14)
If we neglect the derivative of amplitude a(u), the surface normal can be calculated by

N w (u, v) = - a w ∂ z ∂ v B + N renormalized. ( 15
)
Note that this formula allows us to compute normals efficiently by using pre-computed derivatives of the wave profile z.

Our goal now is to tessellate the parameterized wave surface, S(u, v), to get a mesh strip that is able to minimize the geometric aliasing. As suggested in [START_REF] Botsch | Resampling feature and blend regions in polygonal meshes for surface anti-aliasing[END_REF], an effective way to achieve this is to construct a quad mesh whose edges are aligned to iso-parameter lines (Fig. 12). We build the quad mesh in two steps. First, we create rib curves uniformly sampled along the base curve. Meanwhile, we let the rib curves be orthogonal to the base curve. Note that the rib curves may intersect each other when the curvature radius of the base curve is less than w/2. In this case, we relax the the requirements of orthogonality. Second, we uniformly sample on the rib curves to create lines in another parameterization direction, i.e., , v direction. The sampling density is controlled by the LOD scheme that will be introduced in Section 6. Once having tessellated the wave surfaces, we need to apply the mesh strips upon the mesh of the mean water surface. Drawing them separately would not give a correct result because wave surfaces may have negative offset from the mean water surface (Fig. 10). The mesh-stitching technique described in [START_REF] Kobbelt | An interactive approach to point cloud triangulation[END_REF] may work for merging these meshes. However, this method requires remeshing the two surfaces to be merged. Since the waves are dynamic, the remeshing would have to be done in each frame. It is not only computationally expensive but also leads to an extra time cost for uploading the new surface data to the GPU memory.

To avoid remeshing the mean water surface, we solve the mesh composing problem by using the stencil buffer found on graphics hardware. We first draw all wave surfaces into not only a color buffer but also a stencil buffer. The stencil buffer is able to indicate which fragments are covered by the wave surfaces. Then we draw the mean water surface into the color buffer where the wave surfaces are not present. By using this method, we do not need to modify the mean water surface. Still, we need to ensure a perfect continuity between the wave surface and the base water surface. When the boundary of a wave surface intersects with the edges of the mean water surface mesh, geometry gaps may appear. To avoid this, we insert extra ribs by interpolation as shown in Fig. 13.

Handling the intersection of waves

When two obstacles are close, the waves caused by them may intersect and superpose (Fig. 1c). Simply drawing two wave surfaces without handling the intersection will lead to an un-smooth result (Fig. 14a), and can not account for the addition of wave amplitudes. To properly superpose waves, we construct a dedicated mesh patch for the intersection part. Suppose that two wave surfaces S 1 (u 1 , v 1 ) and S 2 (u 2 , v 2 ) intersect as shown in Fig. 15. The superposed surface of the intersection part is defined by:

S(u 1 , u 2 , v 1 , v 2 ) = S 1 (u 1 , v 1 ) + S 2 (u 2 , v 2 ) -S b (u 1 , u 2 ). (16)
The surface normal can be calculated by:

N w (u 1 , u 2 , v 1 , v 2 ) = - a 1 w 1 ∂ z ∂ v (v 1 )•T 2 + a 2 w 2 ∂ z ∂ v (v 2 )•T 1 +B 1 ×B 2 renormalized. ( 17
)
We tessellate the intersection part with a structured grid aligned with the grid lines of S 1 and S 2 . Moreover, we need to cut out this intersection part in both S 1 and S 2 .

u 1 u 2 v 1 v 2 N 1 B 1 T 1 N 2 B 2 T 2
Figure 15: For handling wave intersection, we cut out the intersection part in the two intersected meshes. In addition, we create a dedicated mesh patch (bounded by red dashed lines). .

Implementation details

Wave Profile

The choice of the wave profile z(x) is up to users except the constraint: z(x) = z ′ (x) = z ′′ (x) = 0 at the two ends. This constraint ensures G 2 continuity between the wave surface and the base water surface. In our implementation, we used the normalized wave profile illustrated in Fig. 11. It is defined as the sum of a gravity wave profile z g (x) and a capillary wave profile z c (x) inspired by [START_REF] Alexey | Nonlinear gravity-capillary waves with forcing and dissipation[END_REF]:

z(x) = z g (x) + z c (x), x ∈ [-1..1], (18)
where

z g (x) = 2(3x + 1 √ 2 )e -(3x+ 1 √ 2 ) 2 , (19)
and

z c (x) = .045(e -2x cos(24πx) -1 -x(e -2 cos(24π) -1)), x ≥ 0, 0, x < 0. (20)

Bump-mapping and LOD

Defining a wave surface by sweeping allows us to calculate accurate surface normals efficiently. We always determine per-pixel normals through the analytical bump computed from Eqs. 15 and 17. Problems may occur when we should filter the bumps themselves, i.e., when the sampling frequency (i.e. pixel size) is smaller than the frequency of waves. As predicted by Shannon's theorem, this yields aliasing. In practice, this occurs for the capillary wave component of the profile (Eq. 18). So, these high frequency waves must be properly filtered. We progressively fade the capillary ripples according to the view distance d. We rewrite Eq. 18 to:

z(x) = z g (x) + β z c (x), (21)
INRIA where β decreases from 1 to 0 as d increases. The filtered geometric information should be accounted for in the illumination model, which is a general and tough problem. We leave it as future work.

To ensure good performance, we determine the resolution of wave mesh strips according to the view distance d. We set the level of subdivision of a wave surface in the direction u as ⌊log 2 ((1 -δ )N max )⌋, with N max the maximum number of grid lines, and

δ =      0, d ≤ d near , d-d near d f ar -d near , d near < d < d f ar , 1, d ≥ d f ar . (22)
where d near and d f ar correspond to the finest and the coarsest LOD, respectively.

Shading model

For realistic rendering of water surfaces, we rely on existing GPU techniques. We consider reflection (global and local, with Fresnel term) and refraction effects. Local reflection and refraction are achieved by projecting reflection and refraction maps onto the water surface [START_REF] Isidoro | Rippling reflective and refractive water[END_REF]. A cube map is used to account for global environment (e.g., sky) where the projective texture does not provide pixels of close objects. Finally, we combine those colors in the pixel shader using a Fresnel term.

Results

We benched our method on a scene containing 35m long 3m wide river. All tests were done on an AMD Athlon 3000+ at 1.8Ghz with an NVIDIA GeForce 8800GTS. Fig. 16 shows very detailed waves generated by our method in real-time. The wave phenomenon we target is only one of many kinds of waves on river surfaces. Therefore, mixing our model with other wave models is necessary in real applications. Fig. 17 demonstrates that our method is well compatible with other wave models using bump mapping. Fig. 18 shows waves disturbed by floating leaves. Please consult the accompanying video for wave animation and interactive editing of waves2 .

To demonstrate the performance of our method, we tested it with various view distances (Fig. 19). The simulation time includes two main parts: generating dynamic shockwave crests and constructing wave surface meshes. The result, shown in Table 7, demonstrates that our method is applicable for real-time applications.

Conclusion

In this paper, we have proposed a feature-based vector simulation approach for simulating local wave phenomena that often appear in streams. The key idea is to separate the representation of the animation and rendering. By using this approach, we have simulated the quasi-stationary waves produced by obstacles. The results show that the vector description allows efficient animation of the waves, and the feature aligned meshes yields high-quality rendering. Further more, the approach allows users to intuitionally control the animation. For example, one can easily tune the wave profiles or even keyframe the whole animation.

In the future, we would like to apply the presented approach to more local wave phenomena as shown in Fig. 1. For each type of wave, we first need to find an appropriate vector representation and a way to animated it. For this, we can resort to some classical hydrodynamics work as we did in this paper. Next, we need to transform the vector information to some representation that is suitable for high-quality rendering.

Figure 1 :

 1 Figure 1: Local wave phenomena in water flow: (a,b) waves caused by obstacles in shallow water, (c)intersection of waves caused by obstacles, (c) waves caused by underwater obstacles in deep water, (d) hydraulic jump and foams, and (e) boils (note the circular feature in the middle).

Figure 2 :Figure 3 :

 23 Figure 2: We assume that the waves made by an obstacle consist of a predominant shockwave and a series of ripples.

Figure 4 :

 4 Figure 4: Illustration of our method.

F r > 1 Figure 5 :

 15 Figure 5: Along the boundary of an obstacle, finding edges which contain the endpoints of iso F r =1 . It might be (a) an edge which contains the stagnation point and F r > 1 at one of the two ends, or (b) an edge which does not contains the stagnation point but F r > 1 at one end and F r < 1 at the other end.

Figure 7 :

 7 Figure 7:The velocity of a wave element v e is the vector sum of the wave velocity c and the stream velocity v. Here, the wave crest propagates at the angle of α to the upstream direction.

Figure 8 :

 8 Figure 8: Updating a shockwave starting point x from its initial value x 0 in the vicinity of a perturbation.

Figure 10 :Figure 11 :

 1011 Figure 10: We obtain the river surface by superposing wave surfaces on a base (mean) water surface resul.

Figure 12 :

 12 Figure 12: Wave surface is sampled by a quad mesh aligned with iso-parameter lines for reducing normal noise.

INRIA

Figure 13 :

 13 Figure 13: Left: Mean water surface mesh (dash) and original mesh strip (plain). Boundary edges like AB, CD and DE must be split because they intersect with the edges of the mean water surface mesh (dash). Right: The mesh strip with added extra ribs (red dashed lines) by interpolating.

Figure 14 :

 14 Figure 14: The intersection of two wave patterns. (a) A simple Z-buffer rendering without handling crossing. (b) We generate a dedicated mesh patch for the intersection part. (c) Final rendering with a proper intersection treatment.

Figure 16 :

 16 Figure 16: High resolution waves simulated in real-time.

Figure 17 :Figure 18 :

 1718 Figure 17: By using bump mapping, we can easily combine noise waves (a)(b)(c) and boils (d) with the waves simulated by our method .

( a )

 a Far view. (b) Middle view. (c) Close view.

Figure 19 :

 19 Figure 19: Typical views considered in our performance test.

INRIA

Table 1 :

 1 Computational time of our wave simulation method.

	t (ms/frame)	near view middle view far view
	shockwave crests	2.5	2.5	2.5
	wave meshes	12	13	17

RR n°6855

As stated in[START_REF] Neyret | Phenomenological simulation of brooks[END_REF], it is also possible to find a starting point downstream of an obstacle. For clarity, we only consider the upstream case in this paper, but the downstream case is mostly identical.INRIA

Available at http://evasion.inrialpes.fr/Membres/Qizhi.Yu/projects/vecsim RR n°6855

Acknowledgments

The work of the first author was supported by a grant from the European Community under the Marie-Curie project MEST-CT-2004-008270.