EUROGRAPHICS 2019 / P. Alliez and F. Pellacini(Guest Editors)

Volume 38 (2019), Number 2Generating Stochastic Wall Patterns On-the-fly with Wang Tiles
Alexandre Derouet-Jourdan1, Marc Salvati1 and Théo Jonchier1,2

1 OLM Digital Inc, Japan
2 ASALI-SIR, XLIM, France

(a)

(b)

(c)

Figure 1: (a) Wall painted by an artist. (b) Stochastic wall pattern generated using our on-the-fly procedural algorithm. (c) Final texture
after adding details. Our algorithm generates a line structure similar to the one created by the artist. This structure is used to generate brickcolors and details around the edges. The global material appearance has been generated using texture bombing techniques.
Abstract
The game and movie industries always face the challenge of reproducing materials. This problem is tackled by combining
illumination models and various textures (painted or procedural patterns). Generating stochastic wall patterns is crucial in
the creation of a wide range of backgrounds (castles, temples, ruins...). A specific Wang tile set was introduced previously totackle this problem, in an iterative fashion. However, long lines may appear as visual artifacts. We use this tile set in a new
on-the-fly procedure to generate stochastic wall patterns. For this purpose, we introduce specific hash functions implementing
a constrained Wang tiling. This technique makes possible the generation of boundless textures while giving control over the
maximum line length. The algorithm is simple and easy to implement, and the wall structure we get from the tiles allows toachieve visuals that reproduce all the small details of artist painted walls.
CCS Concepts• Computing methodologies → Texturing;

1. Introduction

Voronoi...) with some well designed BSDF to re-create a material
appearance.

The final look in movies and games is the result of the combinationof textures, 3D models and illumination models. It is usually more
efficient to increase the level of details through a texture rather
than directly into the 3D model. With the continuous improvement
in display technology (4k and 8k) and an increase of CPU/GPU
power, always higher resolution textures are required. The cost of
painting textures by hand is then increasing. Generating textures atrender time that preserve the organic feeling of hand painted ones isthe challenge that all shading artists face everyday. They typicallycombine noises and patterns (fractal, Perlin, Gabor, cellular, flakes,

Every movie and cartoon involves the creation of patterns to generate textures for backgrounds. In this context, we face the problem
of generating stochastic wall patterns for stone walls and paved
grounds as shown in Figure 2. These patterns appear in various
constructions such as castles, temples or ruins. The problem we
address in this paper focuses on generating the lines representing
the edges of the bricks forming the wall. These patterns are different from a regular wall pattern with unique size of bricks (seeFigure 3). Particularly, for aesthetic reasons, it is important that thegenerated patterns follow two constraints:© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John
Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.

A. Derouet-Jourdan, M. Salvati & T. Jonchier / Generating Stochastic Wall Patterns On-the-fly with Wang Tiles

We showed in a previous work [KDJO16] that the long lines artifacts is related to the orientations of the Wang tiles and that theissue can be addressed by precomputing their orientations in orderto break the long lines. We called this the dappling problem andproposed an iterative algorithm to solve it.
(a)

(b)

Figure 2: Examples of stochastic walls. (a) Painting. (b) Photography.

Figure 3: Photographies of regular wall patterns. Left: alternate
pattern. Right: square pattern.

• No cross: pattern where 4 bricks share a corner.
• No long lines: brick with edges aligned in sequences.
This is an important request from our artists. They need to control the focus and the points of interest in their renderings. Cross
patterns and long alignments of bricks tend to attract the eye (seeFigure 18). This is backed up by works in visual perception, where
it was shown that elongated blobs and crosses tend to be perceived
at an early stage of vision and tend to stand out [Bec83, JB83]. So
to prevent the background from attracting the eye of the viewer andput the focus on the foreground, it is crucial to prevent long lines
and crosses from occurring in the wall pattern.
Previous efforts have been devoted to generating such patterns[LDG01, Miy90]. However, they do not always account for crosses
or long lines. Moreover, they are offline techniques by nature,
which means that the whole pattern must be created at once. In sucha case, it is impossible to generate unbounded textures or to accessonly a part of it. In a production setting, being able to perform a
GPU preview of the result or to generate arbitrarily large textures isimportant. This can be achieved by using an on-the-fly evaluationof fully procedural techniques (defined on a boundless domain), i.e
aperiodic, parameterized, random-accessible and compact function
as defined in [LLC∗ 10].
Our goal is to generate stochastic wall patterns on-the-fly whileaccounting for crosses and long lines. Using such patterns, it is theneasy to produce complete textures by adding colors to the bricks,
noise on their edges and other details, as we present Section 3.3.
In a preliminary work, we introduced the use of Wang tiles tocreate walls with no cross patterns [DJMS15], albeit using an iterative algorithm and generating long lines artifacts. Wang tiles havebecome a standard tool in texture synthesis. They have the advantage of producing stochastic patterns, while providing access to thestructure of the pattern. This feature is helpful to provide control
over the rendering and shading of the structure once the pattern isgenerated. Also, as shown in previous work [LD05], it is possible
to design on-the-fly procedural methods to evaluate Wang tilings.

In this paper, our contribution is to create a new and simple yet
general procedural algorithm with on-the-fly evaluation that generates stochastic wall patterns while avoiding cross patterns. In addition, our algorithm provides full control over the maximum lengthof the lines. For this purpose, we propose an on-the-fly solution to
the dappling problem we introduced in [KDJO16]. The procedural
nature of the algorithm makes its GPU implementation straightforward (we provide one as additional material to the present paper).
After an overview of the related work, we explain the Wang tilemodel we use and the limitations of current algorithms. We thenintroduce our on-the-fly solution. Finally we present some result
analysis and discussion about the iterative flavors of the patterngeneration. We compare our results with state of the art texture
synthesis methods and another wall generation algorithm before
concluding about the future work.
Although we illustrate our method with the reproduction of handpainted walls with cartoon style, there is no restrictions to use ourstochastic wall structure to render photo-realistic walls.

2. Related work
To create material appearance, artists use a combination of rastertextures and procedural textures. There is no limit but the skill of
the artist to what they may paint in a raster texture. Because of
the need of very high resolution textures, multiple methods havebeen proposed to generate them. It is a very long studied problem
and it is out of the scope of the present paper to discuss it extensively. In the following, we present a few techniques that have been
proposed to tackle this problem. We can distinguish solutions proposed to this problem into two families, example-based techniques
and purely generative ones.

2.1. Example-based texture synthesis
Texture synthesis generates large size textures based on an exemplar of limited size [DBP∗ 15, KSE∗ 03, LH06, YBY∗ 13]. Thesemethods either work by reproducing statistical properties of the exemplar [GLLD12] or by aggregating patches of the exemplar locally, satisfying local continuity of the structure in the larger texture [LH06, KNL∗ 15]. Large textures can be generated on the fly[VSLD13], without storing at any time the result in memory. For an
extensive overview of these methods, please consult [RDDM17].
As we show Section 5, the strong structure of the wall pattern ishard to capture for such techniques. They produce bend lines, nonrectangular bricks or arbitrarily long lines. Moreover, the control
over the final result is limited. For example it would be very hard tocontrol the color of individual bricks or the space between bricks ofa wall pattern produced by such a method. The reason is that even
if the visual structure is reproduced, the algorithm does not havethe knowledge of the underlying structure of the pattern.
© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John Wiley & Sons Ltd.

A. Derouet-Jourdan, M. Salvati & T. Jonchier / Generating Stochastic Wall Patterns On-the-fly with Wang Tiles

2.2. Rectangular packing and tiling

3. Walls with Wang tiles

Outside of the computer graphics community, the problem of generating arrangements of rectangles has been extensively studied in
combinatorics and discrete mathematics. Domino tiling consists in
tiling a given polygon with rectangles of size 2 × 1 [KP80]. Tatami
tiling is a constrained domino tiling where no four dominos sharea corner, which correspond to our no cross constraint [ERWS11].
Another similar problem is the rectangular packing which consistsin packing with no overlap as many rectangles of various sizes inside a given larger rectangle [LMM02]. In this case, the constraint
is to minimize the area of the larger rectangle that is not covered.

In this section we describe how we use Wang tiles to generate thevisual goal. First we recall the Wang tile model as introduced in[DJMS15] and then we explain how to use the generated structure
to render the walls.

These works have a great theoretical value but are hard to apply
practically to our specific problem. Tatami tilings are limited to two
different sizes of rectangles, and the rectangular packing doesn’t
account for crosses and leaves holes in the pattern.

3.1. Wang tiles
Wang tiles are square tiles with colors on the edges as shown in
Figure 4. Tiles are placed edges to edges in the tiling space. A tilingis valid when every two tiles sharing an edge have the same color
on this edge. We identify the problem of tiling to a problem of edge
coloring like in [LD05]. In that configuration, for a tile in (i, j), we
denote Hi, j+1 , Vi, j , Hi, j and Vi+1, j the top, left, bottom and rightedges, as well as their colors. Wang tiles have the characteristics ofHi, j+12.3. Purely generative texture synthesis
Purely generative methods like noises or pattern arrangements create textures from a small set of parameters or a description of thewanted result [Per85,Wor96,LLDD09,SP16,LHVT17]. For example, texture bombing [Gla04] has been used successfully [SRVT14]
to generate on the fly the equivalent of 100k textures while preserving the hand painted feeling. We use this technique to add details
to the final result in Section 3.3.
Some dedicated techniques have been proposed [LDG01,Miy90]
to create wall patterns. However the control over the size of thebricks and the occurrence of crosses and long lines remain an issue. Also the iterative nature of those methods prevents an on-thefly evaluation. The technique we presented in [DJMS15] is basedon Wang tiles [Wan61] which have been introduced in computer
graphics to generate aperiodic stochastic textures [CSHD03,Sta97].
They have been proven to be usable in an on-the-fly context [LD05,
SD10, Wei04]. Although the technique presented in [DJMS15] accounts for cross patterns, it cannot guarantee in itself that the lines
will remain short. We introduced in [KDJO16] an algorithm thatcan be used to limit the lines’ lengths in the pattern by precomputing the orientations of the Wang tiles. Unfortunately, this approach is iterative and limited to fixed size textures and cannot be
adapted easily for an on-the-fly evaluation. Wang tiles have also
been used to generate point distributions with a blue noise Fourier
spectrum [KCODL06]. In that paper, the authors introduce a hierarchical Wang tiling algorithm. Essentially, the algorithm first generates a tiling with a low resolution. Then the tiling is locally refined.
This way, the algorithm can produce point sets with non uniform
density.
In this paper, we propose a new procedural technique to evaluate
on-the-fly a Wang tiling specially tailored for the Wang tiles designed in [DJMS15]. Our technique enforces a fixed upper boundon the lines’ lengths in the pattern. It is inspired by [KCODL06].
We first generate a subdivision of the texture space which has
the property of limiting the lines’ lengths, based on the ideas
from [KDJO16]. Then we construct the final tiling following thesubdivision. The Wang tiles we use allows us to solve both steps atonce, by generating the subdivision implicitly.
© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John Wiley & Sons Ltd.

(i, j)
Vi+1, j

Vi, j

Hi, j

Figure 4: Model of Wang tile. In a valid tiling, the color of a sharededge is the same for the two tiles sharing the edge. The tile (i, j) ismade from the colors Hi, j+1 , Vi, j , Hi, j and Vi+1, j
providing local continuity on the edges of the tiles.
3.2. Wang tile model
The stochastic wall patterns we generate consist of a set of rectangular bricks in various sizes. They don’t contain cross patterns
as these break the randomness and attract the eye. That is the reason why, when painting by hand, artists avoid such patterns (seeFigure 2 (a)).
Expressing stochastic wall patterns with Wang tiles is straightforward. Each tile models the corner junctions of four bricks. Thisis done by mapping the four colors of each tile to the bricks’ edges’
placement as shown in Figure 5. However to avoid non rectanguHi, j+1

Vi+1, j

Vi, j
Hi, j

Figure 5: Modeling a wall pattern with Wang tiles. Tile colors are
mapped to the bricks edges positions.
lar bricks (see Figure 6 (c) (d) (e)) and avoid cross patterns (seeA. Derouet-Jourdan, M. Salvati & T. Jonchier / Generating Stochastic Wall Patterns On-the-fly with Wang Tiles

In Figure 9, we decompose the painting and our rendering in thosefeatures. We then explain how we use the stochastic wall pattern toreproduce all those features.
(a)

(b)

(c)

(d)

(e)

Figure 6: The tiles removed from the Wang tile set. (a) cross tiles(Hi, j+1 = Hi, j and Vi+1, j = Vi, j ). (c) (d) (e) non rectangular tiles/(b)extra brick tiles (Hi, j+1 6= Hi, j and Vi+1, j 6= Vi, j ).

Figure 6 (a)), the tile set is restricted. To enforce rectangular bricks
and avoid cross patterns, only "vertical" and "horizontal" tiles are
considered. These constraints are shown in Figure 7 and formulated
in Equations (1) and (2) . This avoids all the tiles introducing non(a) The global appearance: artist (left), texture bombing (right).

(b) The brick color painted: artist (left), from wall structure (right).

Figure 7: Correspondence between the brick pattern(left), theWang tile (center) and the orientation (right). Top line describes
horizontal tiles, and bottom line vertical ones.
rectangular bricks (such that Hi, j+1 6= Hi, j and Vi+1, j 6= Vi, j ).

Vertical constraint Hi, j+1 = Hi, j and Vi+1, j 6= Vi, j(1)

Horizontal constraint Hi, j+1 6= Hi, j and Vi+1, j = Vi, j(2)This also excludes tiles introducing an extra brick in the center(Figure 6 (b)). It would not be complicated to consider them, butthey introduce tiny bricks that stand out. For nc colors, we obtain atile set of size 2 ∗ n2c ∗ (nc − 1) (see Figure 8 for the tile set with 3colors, 36 tiles)(c) The lines and edge highlights: artist (left), from brick parameterization(right).

Figure 9: Comparison of the features of both artist painted wall(left) and the generated wall rendering (right).

Space between bricks, corner roundness and edge scratches arefeatures localized near brick edges. Thanks to the brick structure
we can generate a Cartesian parameterization as well as a polar
parameterization that includes corner roundness (see Figure 10).
From that structure, it’s easy to generate normal maps to be used ina photo-realistic context.

Figure 8: Tile set example with 3 colors, 36 possible tiles.

3.3. Rendering and shading
In this section we focus on the visual appearance of the bricks,
given a stochastic wall structure of rectangular bricks without crosspatterns. Observing the hand painted wall (see Figure 2), we notice
the following features created by the artist:• The global rock material.
• Color variation for each brick.
• Variable space between the bricks and corner roundness.
• Highlights and scratches near the edges of the bricks.

Figure 10: UV parameterization of brick. Cartesian (left), polar
parameterization with corner roundness (right).

Distance to brick edges can be combined with some noise function to create irregular space between bricks (see Figure 9 (c)).
The same distance can also be used to localize and apply highlights and scratch textures (see Figure 9 (c)). The color variation
is simply enforced by generating a color based on the brick id or© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John Wiley & Sons Ltd.

A. Derouet-Jourdan, M. Salvati & T. Jonchier / Generating Stochastic Wall Patterns On-the-fly with Wang Tiles

center position (see Figure 9 (b)). We can also use a texture map
to determine this color. As for the global material appearance it
may be obtained by a combination of hand-painted and procedural
textures. In our case we use texture bombing techniques as in thebrush shader [SRVT14] to generate all those details while keeping
the hand-painted touch (see Figure 9 (a)).

horizontal lines occur on the top. The stochastic variation of Wang
tiling [KCODL06] does not suffer from this limitation. However
the stochastic nature of the algorithm makes difficult the controlof the length of the straight lines shown in Figure 11. The dap-

Without the wall/brick structure, such visual features would bereally difficult to reproduce.
4. Algorithm
This section presents our procedural algorithm for wall pattern generation. As seen in various procedural texture generation papers
like [Wor96], we make a correspondence between a given request
point P(x, y) and an underlying "virtual" grid cell (i, j) (for example
integer part of scaled coordinates). In our algorithm, we build twofunctions h0 (i, j) and v0 (i, j) implementing procedural tiling while
avoiding long lines:
Hi, j = h0 (i, j) Vi, j = v0 (i, j).
In the following sections, we start by explaining the long line problem inherent to [DJMS15]. We start by giving a general procedural
solution (Section 4.2) that do not consider the long line problem.
Then we explain how to build h0 and v0 on top of the general solution to avoid long lines procedurally in Section 4.3.

Figure 12: Notice the long lines on the side when the number ofconnections is increasing (from left to right: 3, 5, 10 connections).
pling algorithm of [KDJO16] can be combined to the sequential
algorithm of [DJMS15] to solve the issue of long lines for nonrepeatable walls. We use that algorithm as a general reference tocompare against our procedural approach in Section 5.
4.2. General solution
The general on-the-fly tiling method is based on a property of ourWang tiles set, enunciated in [DJMS15], that a 2 × 2 square canalways be tiled, for any boundary coloring.

4.1. The long line problem

The idea is to cut the grid into 2 × 2 squares. We need to determine the color of their outer edges.

The Wang tile set we use has been introduced along with an algorithm to generate a repeatable wall pattern in [DJMS15]. Howeverlong lines occur in walls generated by this algorithm (see Figure 11
and 12).

For each cell (i, j), we compute the bottom left cell index (i0 , j0 ),which identify a 2 × 2 square, withi0 = i − i%2

j0 = j − j%2,where x%y is the positive remainder in the Euclidean division of x
by y.
We use h and v to associate pseudo-random values to the outeredge color (Hi0 , j0 +2 , Hi0 , j0 , Hi0 +1, j0 , Hi0 +1, j0 +2 , Vi0 , j0 +1 , Vi0 , j0 ,Vi0 +2, j0 , Vi0 +2, j0 +1 ) as shown in Figure 13 (a):h(i, j) = H(i, j)%ncv(i, j) = V(i, j)%nc ,Figure 11: Long lines stand out and attract the eye in a wall pattern.

where H and V are hash function and associate "random" integer
values to (i, j). In practice we use a FNV hash scheme [FNV91]
to seed a xorshift random number generator from which we pick avalue.

The reason behind the occurrence of long lines in Figure 11 issimple. Tiles are separated in two categories: the vertical and horizontal ones. So the probability to have a horizontal/vertical lineof more than three tiles length is 1/23 = 0.125. The occurrence oflong lines on the side in Figure 12 is inherent to the sequential algorithm of [DJMS15]. We can see that the length of the lines on
the side is increasing with the number of connections. In a sequential algorithm, the last tile of a row is solved with 3 constraints.
With nc connections the probability that the last constraints matchis roughly 1/nc . This means that the probability the last tile of a row
is horizontal is roughly 1/nc . The more connections you have, thelonger the vertical lines on the side are. For the same reasons long

However to satisfy the constraints (Equations (1) and (2)) of ourWang tile model, we cannot use pseudo-random values for the inneredge. We compute their colors using the result from [DJMS15]: wesolve the interior of the 2 × 2 square by considering the different
cases on the border. This gives us the colors Hi0 , j0 +1 , Hi0 +1, j andVi0 , j0 +1 ,Vi0 +1, j0 +1 . Denoting h2 and v2 the function combining thetwo coloring of the edges (both outer and inner edges of 2 × 2), wehave
h(i, j)
if j%2 = 0
Hi, j = h2 (i, j) =solvedby2
×2
solverotherwise,v(i, j)if i%2 = 0
Vi, j = v2 (i, j) =solved by 2 × 2 solver otherwise.

© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John Wiley & Sons Ltd.

A. Derouet-Jourdan, M. Salvati & T. Jonchier / Generating Stochastic Wall Patterns On-the-fly with Wang Tiles

An example of 2 × 2 solution is shown in Figure 13 (b).
[DJMS15] proves that there is a solution, without explicitly giving
Hi0 , j0 +2

Hi0 +1, j0 +2
Vi0 +1, j0 +1
Vi0 +2, j0 +1

Vi0 , j0 +1
Hi0 +1, j0 +1
Hi0 , j0 +1(i0 , j0 )V

Vi0 +2, j0

i0 , j 0

Hi0 , j0

We start with the case of an upper bound n greater than 2, andthen consider the special case of n = 2 which is simpler and can betreated more efficiently.
4.3.1. Case of n > 2
For a maximum number of n consecutive tiles of a same orientation, we use 2 × 2 checkerboards (see Figure 15) on diagonals.
Each diagonal is separated from the other one by n − 2 cells horizontally and vertically (see Figure 16). The cells inbetween theVi0 +1, j0

Hi0 +1, j0
(a)

(b)

Figure 15: 2 possible checkerboard patterns.
Figure 13: Given a set of colors (a), an example solution (b).
it. Solution can be built by constraints based or backtracking algorithms. In our implementation, we choose to consider all possible
cases of color matching for opposite edges. It leads to 16 possible
cases that are listed in appendix A.
n−2

n−1

4.3. Restricting the line length with dappling
In Figure 14, we can see how the dappling algorithm of [KDJO16]
can produce random distributions while avoiding the long lines.
The vertical tiles are represented in red and the horizontal ones in

Figure 14: Left: without dappling, we can notice the long continuous horizontal and vertical lines. Right: iterative dappling algorithm from [KDJO16] (maximum line length of 2)
yellow. Vertical successions of red tiles and horizontal successionsof yellow tiles result in long lines. By combining this dappling algorithm with the previous tiling algorithm of [DJMS15], it is possible to generate stochastic patterns with a given maximum lengthof lines. However this approach is strictly iterative. We propose anon-the-fly method to achieve similar results and restrict the longest
line length to an arbitrary value n.
The idea behind the dappling in [KDJO16] is to traverse the configuration diagonally and correct the dappling when the number ofconsecutive horizontal or vertical tiles is too large. It is not possible to use this method in an on-the-fly fashion as it necessitates
constructing the whole configuration until the requested cell. What
we propose is to force the correction, that is, we "preemptively"
correct the dappling automatically, whether the correction is necessary or not. In the following, we explain the core idea behindthe on-the-fly evaluation of the dappling. Then, we explain how toevaluate on-the-fly a tiling that satisfies the dappling constraints directly, without having to build explicitely the dappling beforehand.

n−2

n−1

Figure 16: Dappling pattern for even n (left), odd n (right). For
even values of n, we use both checkerboard patterns randomly. For
odd values of n, we pick at random one of the two checkerboard
patterns and use it everywhere.
2 × 2 checkerboards are not constrained and can be oriented in any
way. It is easy to see that in such a case, there are no alignmentof more than n consecutive tiles with the same orientation (n − 2
for the cells inbetween and +2 for the checkerboards). Because thecheckerboards are of size 2 × 2, this technique only works for evenvalues of n. It is possible to solve the same problem for odd valuesof n: we use only one type of checkerboard and separate each diagonal from the other one by n − 1 cells horizontally and vertically.
To include it in the general solution of Section 4, we need toadjust the hash functions h2 and v2 and replace them by dappling
enabled ones h0 and v0 .
2 × 2 checkerboards are aligned on the diagonal: i0 %n = j0 %n,with i0 = i − i%2, j0 = j − j%2. Considering a checkerboard withits bottom left cell in (i0 , j0 ), there is exactly one horizontal tile between two horizontal edges opposed on the outer border, Hi0 , j0 and
Hi0 , j0 +2 . It means that we necessarily have h0 (i0 , j0 ) 6= h0 (i0 , j0 + 2).
The same reasoning applies for v0 . So we need to create h0 and v0
to enforce that condition.

if j%2 = 0 and i0 %n = j0 %n
 hd1 (i, j, h(i, j + 2))0h(i, j)
if j%2 = 0 and i0 %n 6= j0 %nh (i, j) =solvedby2
×2
solver
if
j%2 =
6 0

if i%2 = 0 and i0 %n = j0 %n
 vd1 (i, j, v(i + 2, j))v(i, j)if i%2 = 0 and i0 %n 6= j0 %n
v0 (i, j) =solved by 2 × 2 solver if i%2 6= 0
© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John Wiley & Sons Ltd.

A. Derouet-Jourdan, M. Salvati & T. Jonchier / Generating Stochastic Wall Patterns On-the-fly with Wang Tiles

This defines all the outer edges of the 2 × 2 squares. We then use
the general solution to solve each 2 × 2 locally. hd1 and vd1 compute random colors different from their input and are defined inAppendix A.
4.3.2. Case of n = 2
In the special case of n = 2, we just need to generate a dapplingwith randomly chosen 2 × 2 checkerboards (from Figure 15).
The idea to create a hash function that generate such a dappling is to consider the grid by pack of four cells, enforcing in
the middle the checkerboard condition (opposite outer edge color
are different). Similarly to the case n>2, we get the condition
h0 (i0 , j0 ) 6= h0 (i0 , j0 + 2). Since in this case n − 2 = 0, there is another checkerboard with its bottom left corner in (i0 , j0 + 2), meaning h0 (i0 , j0 + 2) 6= h0 (i0 , j0 + 4). Combining the two constraints we
get h0 (i0 , j0 +2) = hd2 (i0 , j0 +2, h0 (i0 , j0 ), h0 (i0 , j0 +4). If we choose
h0 (i0 , j0 ) and h0 (i0 , j0 + 4) arbitrarily, we can compute h0 (i0 , j0 + 2).
The same reasoning apply to v0 and can be summed up as hd2 (i, j, h(i, j − 2), h(i, j + 2))h(i, j)h0 (i, j) = solved by 2 × 2 solver vd2 (i, j, v(i − 2, j), v(i + 2, j))v(i, j)v0 (i, j) =solved by 2 × 2 solver

if j%4 = 2
if j%4 = 0
otherwise.
if i%4 = 2
if i%4 = 0
otherwise.

hd2 and vd2 compute random colors different from their input andare defined in Appendix A.
5. Results and Discussion
5.1. Visual results and comparison

Figure 18: Production result using [DJMS15] (left), using ouralgorithm (n = 2) (right). Our method breaks the long lines artifacts behind the character. These lines attract the eye, breaking
them restores the focus on the character. Pokémon Generations
Episode 3: The Challenger : ©2016 Pokémon. ©1995-2016 Nintendo/Creatures Inc. /GAME FREAK inc.

Figure 19: Box packing method

patterns or line length. We have access to the structure of the bricks,
but the method is iterative and cannot be evaluated on-the-fly.
Figure 20 and 21 we show the results of two patch-based methods [LH06, KNL∗ 15] on a hand-painted wall sample. These two
methods are designed to take into account not only the color ofeach pixel but also its distance to features like the brick edges inour case. Unfortunately, texture synthesis methods can only reproduce approximative look, introducing holes or bending the lines,
which makes them unsuited for production.

Thanks to our algorithm, we can control over the maximum lengthof the lines of the stochastic wall pattern. Output result of the pattern for maximum line length n = 1, n = 3, n = 5 are shown in
Figure 17. We could also reproduce the artist painted wall patten as
shown in Figure 1.

exemplarfeature mask
output

n=1

n=3

n=5

Figure 17: Output of our algorithm for n = 1, n = 3, n = 5

Figure 20: Result of [LH06]. The mask is used to compute the distance to the bricks’ edges. The computation time is low (just a few
seconds). Although this method manages to keep the general aspect of a wall, we can see that a lot of bricks have non rectangularshapes and that some edges are not properly connected.

The algorithm from [DJMS15] has been used in production andlong lines were standing out (Figure 18 (left)). Limiting the maximum length to n = 2 with our new algorithm, the output looks
much more natural (Figure 18 (right)).

5.2. GPU implementation

Existing methods failed to reproduce our wall pattern structure.
We tried the box packing method from [Miy90] (see Figure 19).
It produces elongated brick and does not give control over cross

The GPU implementation of the procedural approach was straightforward in OpenGL3 and WebGL (we provide a ShaderToy implementation of the case n = 2). We use integer based hash functions© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John Wiley & Sons Ltd.

A. Derouet-Jourdan, M. Salvati & T. Jonchier / Generating Stochastic Wall Patterns On-the-fly with Wang Tiles

We evaluate the quality of the dappling results by computing
histograms of the number of consecutive tiles of same orientation in rows (see Figure 22). We use the original dappling methodfrom [KDJO16] for the sequential algorithm, because it is the mostgeneral solution as far as we know. Figure 22 shows that the propor-

outputexemplarFigure 21: Result of [KNL∗ 15]. The result is impressive and close
to our goal. However, we can still see bended lines and non rectangular bricks. Also, the computation time of the authors’ implementation is large (around 40 minutes).

in our production implementation. However, the integer support
seems to be limited in OpenGL, and we then switched to different, float based hash functions.
We reach real time performance even with high number of pixel
samples as shown in Table 1.
Pixel Samples
VGA(1024x768)
HD(1920x1080)

1
520
200

2
515
220

8
450
187

16
180
70

32
148
60

Table 1: GPU algorithm performance (in frame per seconds).
GPU results have been obtained using a Nvidia Quadro K620.

5.3. Computation time and discussion
We measure and compare the performance of our on-the-fly evaluation against the general iterative algorithm, combination of thesequential algorithm of [DJMS15] with the solution to the dappling problem of [KDJO16]. Both algorithms give the same kindof results, and computation time are given in Table 2. Although

S/SD
F/FD

Initialization
2.1/2.50Time for 107 computation (x NP)
790 (1x)
3320 (4.2x)/3726 (4.7x)

Table 2: CPU algorithms performance measured in ms. Time forthe retrieval of a brick, using a 100x100 grid. Sequential algorithm without/with dappling (S/SD n = 2). On-the-fly evaluation
without/with dappling(F/FD n = 2)
the on-the-fly evaluation is 4 to 5 times slower than the iterative
version, in production rendering context, this timings remain negligible compared to the full rendering times. It represents 2% of
our wall rendering time (roughly 2 minutes per frame). The computation time difference comes from the multiple evaluation of thesame tile in the on-the-fly approach. To compute one tile, it is necessary to compute some local neighboring tiles. Without memory,when we compute the next tile, some of the same neighboring tiles
are computed again. We are confident that this computation time
can be reduced by a carefully designed local cache system to avoid
some re-computations.

Figure 22: Histogram of the vertical line length occurrence. Comparison between non procedural (NPD) and procedural (PD) version. Left: with maximum line length n = 4. Right: with maximum
line length n = 10.
tion of lines with the same length are similar with either on-the-fly
evaluation and sequential algorithms. However we found a flaw inthe original algorithm from [KDJO16]. In the case n = 4, the number of lines of length 4 is oddly equivalent to line of length 3. Our
assumption is that every lines over 4 of length will be clamped to 4
and then artificially increase their occurrence, which inserts a bias
in the result. Our on-the-fly evaluation technique produces a betterline length distribution than the previous method.
The iterative approach is faster than our algorithm. It requires
memory proportional to the number of bricks. It is also customizable and allows the caching of per brick information (color, randomization values...). In the case of a small wall pattern, using
memory is not a big issue. But the fact that the memory used by thisapproach is unbounded makes it problematic in the case of a verylarge wall when the memory budget is tight. Our on-the-fly method
generates unbounded textures without any repetitions, without using memory, But its cost is an increased computation time because
it needs to recompute all the bricks information constantly. We believe that this cost could be reduced in some cases by crafting abounded memory local cache system. We are currently investigating this approach.

6. Conclusion and future work
By designing custom hash functions for our specific problem, we
succeed to provide a simple yet general solution to the generation ofstochastic wall patterns. Our algorithm is fully procedural, avoids
common visual artifacts and gives control to the user over the maximum line length. The computation overhead is low and the GPU
implementation enables preview of the result, making it ready to integrate into movie production pipeline, extending artists’ creation
palette.
We are now considering the inclusion of multi resolution Wangtiles ( [KCODL06]) or the combination of various sets of tiles toenable more variations in the brick sizes and patterns. We are also
thinking about using border constrained 2D Wang tiling solutionsin the context of texture synthesis. We are also working on the 3D
procedural texture generation of stochastic wall patterns, and we© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John Wiley & Sons Ltd.

A. Derouet-Jourdan, M. Salvati & T. Jonchier / Generating Stochastic Wall Patterns On-the-fly with Wang Tiles

think about extending those results to general voxelization problems. Our intuition is that the stochastic structure of the underlying
grid may improve the quality of volume rendering and collision
detections.

[KSE∗ 03] K WATRA V., S CHÖDL A., E SSA I., T URK G., B OBICK A.:
Graphcut textures: Image and video synthesis using graph cuts. In ACM
SIGGRAPH 2003 Papers on - SIGGRAPH '03 (2003), Association for
Computing Machinery (ACM). URL: http://dx.doi.org/10.
1145/1201775.882264, doi:10.1145/1201775.882264. 2

References[LD05] L AGAE A., D UTRÉ P.:
A procedural object distributionfunction. ACM Transactions on Graphics 24, 4 (October 2005),
1442–1461. URL: http://doi.acm.org/10.1145/1095878.
1095888, doi:10.1145/1095878.1095888. 2, 3

[Bec83] B ECK J.: Textural segmentation, second-order statistics, andtextural elements. Biological Cybernetics 48, 2 (Sep 1983), 125–130. URL: https://doi.org/10.1007/BF00344396, doi:
10.1007/BF00344396. 2[CSHD03] C OHEN M. F., S HADE J., H ILLER S., D EUSSEN O.: Wangtiles for image and texture generation. In ACM SIGGRAPH 2003 Papers on - SIGGRAPH 03 (2003), Association for Computing Machinery (ACM). URL: http://dx.doi.org/10.1145/1201775.
882265, doi:10.1145/1201775.882265. 3[DBP∗ 15] D IAMANTI O., BARNES C., PARIS S., S HECHTMAN E.,
S ORKINE -H ORNUNG O.: Synthesis of complex image appearance
from limited exemplars. ACM Transactions on Graphics 34, 2 (mar2015), 1–14. URL: http://dx.doi.org/10.1145/2699641,
doi:10.1145/2699641. 2[DJMS15] D EROUET-J OURDAN A., M IZOGUCHI Y., S ALVATI M.:
Wang Tiles Modeling of Wall Patterns. In Symposium on Mathematical Progress in Expressive Image Synthesis (MEIS2015) (2015), vol. 64
of MI Lecture Note Series, Kyushu University, pp. 61–70. 2, 3, 5, 6, 7, 8
[ERWS11] E RICKSON A., RUSKEY F., W OODCOCK J., S CHURCH
M.:
Monomer-Dimer Tatami Tilings of Rectangular Regions.
Electronic Journal of Combinatorics 18, 1 (2011).
URL:
http://www.combinatorics.org/Volume_18/
Abstracts/v18i1p109.html. 3[FNV91] F OWLER G., N OLL L. C., VO P.: Fowler / Noll / Vo (FNV)
Hash, 1991. URL: http://isthe.com/chongo/tech/comp/fnv/. 5[Gla04] G LANVILLE R. S.: Texture bombing. In GPU Gems, FernandoR., (Ed.). Addison-Wesley, 2004, pp. 323–338. 3[GLLD12] G ALERNE B., L AGAE A., L EFEBVRE S., D RETTAKIS G.:
Gabor noise by example. ACM Transactions on Graphics (Proceedingsof ACM SIGGRAPH 2012) 31, 4 (July 2012), 73:1–73:9. doi:10.
1145/2185520.2335424. 2[JB83] J ULESZ B., B ERGEN J. R.: Human factors and behavioral
science: Textons, the fundamental elements in preattentive visionand perception of textures. Bell System Technical Journal 62, 6(1983), 1619–1645. URL: https://onlinelibrary.wiley.
com/doi/abs/10.1002/j.1538-7305.1983.tb03502.x,
arXiv:https://onlinelibrary.wiley.com/doi/
pdf/10.1002/j.1538-7305.1983.tb03502.x,
doi:
10.1002/j.1538-7305.1983.tb03502.x. 2[KCODL06] KOPF J., C OHEN -O R D., D EUSSEN O., L ISCHINSKI D.:
Recursive wang tiles for real-time blue noise. In ACM SIGGRAPH 2006
Papers on - SIGGRAPH '06 (2006), Association for Computing Machinery (ACM). URL: http://dx.doi.org/10.1145/1179352.
1141916, doi:10.1145/1179352.1141916. 3, 5, 8
[KDJO16] K AJI S., D EROUET-J OURDAN A., O CHIAI H.: Dappled
tiling. In Symposium on Mathematical Progress in Expressive Image
Synthesis (MEIS2016) (2016), vol. 69 of MI Lecture Note Series, Kyushu
University, pp. 18–27. 2, 3, 5, 6, 8
[KNL∗ 15] K ASPAR A., N EUBERT B., L ISCHINSKI D., PAULY M.,
KOPF J.: Self tuning texture optimization. Computer Graphics Forum 34, 2 (may 2015), 349–359. URL: http://dx.doi.org/10.
1111/cgf.12565, doi:10.1111/cgf.12565. 2, 7, 8
[KP80] K LARNER D., P OLLACK J.:
Domino tilings of rectangles with fixed width.
Discrete Mathematics 32, 1 (1980),
45 – 52.
URL: http://www.sciencedirect.com/
science/article/pii/0012365X80900989, doi:https://doi.org/10.1016/0012-365X(80)90098-9. 3© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John Wiley & Sons Ltd.

[LDG01] L EGAKIS J., D ORSEY J., G ORTLER S.: Feature-based cellular
texturing for architectural models. In Proceedings of the 28th Annual
Conference on Computer Graphics and Interactive Techniques (NewYork, NY, USA, 2001), SIGGRAPH ’01, ACM, pp. 309–316. URL:
http://doi.acm.org/10.1145/383259.383293, doi:10.
1145/383259.383293. 2, 3
[LH06] L EFEBVRE S., H OPPE H.: Appearance-space texture synthesis.
In ACM SIGGRAPH 2006 Papers on - SIGGRAPH '06 (2006), Association for Computing Machinery (ACM). URL: http://dx.doi.
org/10.1145/1179352.1141921, doi:10.1145/1179352.
1141921. 2, 7
[LHVT17] L OI H., H URTUT T., V ERGNE R., T HOLLOT J.: Programmable 2d arrangements for element texture design.
ACM
Trans. Graph. 36, 4 (May 2017).
URL: http://doi.acm.
org/10.1145/3072959.2983617, doi:10.1145/3072959.
2983617. 3[LLC∗ 10] L AGAE A., L EFEBVRE S., C OOK R., D E ROSE T., D RETTAKIS G., E BERT D., L EWIS J., P ERLIN K., Z WICKER M.: A Survey of Procedural Noise Functions. Computer Graphics Forum (2010).
doi:10.1111/j.1467-8659.2010.01827.x. 2[LLDD09] L AGAE A., L EFEBVRE S., D RETTAKIS G., D UTRÉ P.: Procedural noise using sparse gabor convolution. ACM Transactions on
Graphics (Proceedings of ACM SIGGRAPH 2009) 28, 3 (July 2009),
54–64. doi:10.1145/1531326.1531360. 3[LMM02] L ODI A., M ARTELLO S., M ONACI M.: Two-dimensional
packing problems: A survey. European Journal of Operational Research141, 2 (2002), 241 – 252. URL: http://www.sciencedirect.
com/science/article/pii/S0377221702001236,
doi:
https://doi.org/10.1016/S0377-2217(02)00123-6. 3[Miy90] M IYATA K.: A method of generating stone wall patterns. In
Proceedings of the 17th Annual Conference on Computer Graphics
and Interactive Techniques (New York, NY, USA, 1990), SIGGRAPH’90, ACM, pp. 387–394. URL: http://doi.acm.org/10.1145/
97879.97921, doi:10.1145/97879.97921. 3, 7
[Per85] P ERLIN K.: An image synthesizer. SIGGRAPH Comput. Graph.
19, 3 (July 1985), 287–296. URL: http://doi.acm.org/10.
1145/325165.325247, doi:10.1145/325165.325247. 3[RDDM17] R AAD L., DAVY A., D ESOLNEUX A., M OREL J.-M.: A
survey of exemplar-based texture synthesis. Annals of Mathematical Sciences and Applications (2017), To appear. 2[SD10] S CHLÖMER T., D EUSSEN O.: Semi-stochastic tilings forexample-based texture synthesis. Computer Graphics Forum 29, 4 (aug2010), 1431–1439. URL: http://dx.doi.org/10.1111/j.
1467-8659.2010.01740.x, doi:10.1111/j.1467-8659.
2010.01740.x. 3[SP16] S ANTONI C., P ELLACINI F.: gtangle: A grammar for the procedural generation of tangle patterns. ACM Trans. Graph. 35, 6 (Nov.
2016), 182:1–182:11. URL: http://doi.acm.org/10.1145/
2980179.2982417, doi:10.1145/2980179.2982417. 3[SRVT14] S ALVATI M., RUIZ V ELASCO E., TAKAO K.: The brushshader: A step towards hand-painted style background in cg, 2014. 3,
5[Sta97]
3

S TAM J.: Aperiodic Texture Mapping. Tech. rep., ERCIM, 1997.

[VSLD13]VANHOEY K., S AUVAGE B., L ARUE F., D ISCHLER J.-M.:

A. Derouet-Jourdan, M. Salvati & T. Jonchier / Generating Stochastic Wall Patterns On-the-fly with Wang Tiles
On-the-fly multi-scale infinite texturing from example. ACM Transactions on Graphics 32, 6 (nov 2013), 1–10. URL: http://dx.doi.
org/10.1145/2508363.2508383, doi:10.1145/2508363.
2508383. 2

8. solver 0111

[Wan61] WANG H.: Proving theorems by pattern recognition II. Bell
System Technical Journal 40 (1961), 1–42. 3

9. solver 1000

[Wei04] W EI L.-Y.: Tile-based texture mapping on graphics hardware.
In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conferenceon Graphics hardware - HWWS '04 (2004), Association for Computing Machinery (ACM). URL: http://dx.doi.org/10.1145/
1058129.1058138, doi:10.1145/1058129.1058138. 3• Vi+2, j+1 , Hi, j+2 ,Vi+2, j , hd2 (i + 1, j + 1, Hi+1, j , Hi+1, j+2 )• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 ,Vi+2, j , Hi+1, j+2• Vi+2, j+1 , Hi, j+2 , vd2 (i + 1, j,Vi, j ,Vi+2, j ), Hi+1, j[Wor96] W ORLEY S.: A cellular texture basis function. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (New York, NY, USA, 1996), SIGGRAPH ’96, ACM,
pp. 291–294. URL: http://doi.acm.org/10.1145/237170.
237267, doi:10.1145/237170.237267. 3, 5
[YBY∗ 13]

Y EH Y.-T., B REEDEN K., YANG L., F ISHER M., H ANRA HAN P.: Synthesis of tiled patterns using factor graphs. ACM Transac-

tions on Graphics 32, 1 (jan 2013), 1–13. URL: http://dx.doi.
org/10.1145/2421636.2421639, doi:10.1145/2421636.
2421639. 2

A. Base case solver
We separate the 16 cases for the equalities Hi, j+2 = Hi, j Hi+1, j =Hi+1, j+2 Vi, j+1 = Vi+2, j+1 Vi, j = Vi+2, j . The solutions are given as
4 values for respectively Vi+1, j+1 , Hi, j+1 , Vi+1, j and Hi+1, j+1 .
1. solver 0000
• Vi, j+1 , Hi, j ,Vi+2, j , Hi+1, j+2• Vi+2, j+1 , Hi, j+2 ,Vi, j , Hi+1, j
2. solver 0001
• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 ,Vi, j , Hi+1, j+2• Vi+2, j+1 , Hi, j+2 ,Vi, j , hd2 (i + 1, j + 1, Hi+1, j , Hi+1, j+2 )• Vi, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , Hi+1, j+2
3. solver 0010
• Vi, j+1 , Hi, j , vd2 (i + 1, j,Vi, j ,Vi+2, j ), Hi+1, j• Vi, j+1 , Hi, j ,Vi+2, j , hd2 (i + 1, j + 1, Hi+1, j , Hi+1, j+2 )• Vi, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , Hi+1, j• Vi, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , hd2 (i + 1, j +1, Hi+1, j , Hi+1, j+2 )10. solver 1001
• Vi+2, j+1 , Hi, j+2 , vd2 (i + 1, j,Vi, j ,Vi+2, j ), Hi+1, j• Vi, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , Hi+1, j+2
11. solver 1010
• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 ,Vi+2, j , Hi+1, j+2• Vi+2, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , Hi+1, j
12. solver 1011
• Vi, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , hd2 (i + 1, j +1, Hi+1, j , Hi+1, j+2 )13. solver 1100
• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 , vd2 (i +1, j,Vi, j ,Vi+2, j ), Hi+1, j• Vi, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , Hi+1, j• Vi+2, j+1 , Hi, j+2 ,Vi+2, j , hd2 (i + 1, j + 1, Hi+1, j , Hi+1, j+2 )14. solver 1101
• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 , vd2 (i +1, j,Vi, j ,Vi+2, j ), Hi+1, j
15. solver 1110
• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 , vd2 (i +1, j,Vi, j ,Vi+2, j ), Hi+1, j
16. solver 1111

4. solver 0011

• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 , vd2 (i +1, j,Vi, j ,Vi+2, j ), Hi+1, j• Vi, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , hd2 (i + 1, j +1, Hi+1, j , Hi+1, j+2 )• Vi, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , hd2 (i + 1, j +1, Hi+1, j , Hi+1, j+2 )• Vi, j+1 , Hi, j , vd2 (i + 1, j,Vi, j ,Vi+2, j ), Hi+1, j• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 ,Vi, j , Hi+1, j+2

with vd1 and vd2 (resp. hd1 and hd2 ) to compute random colors
different from its input:m
if m < cvd1 (i, j, c) =m + 1 if m ≥ c

5. solver 0100

where m = V(i, j)%(nc − 1)
 0
if m0 < min(c1 , c2 ) m
m0 + 1 if min(c1 , c2 ) ≤ m0 < max(c1 , c2 ) − 1
vd2 (i, j, c1 , c2 ) = 0
m + 2 if m0 ≥ max(c1 , c2 ) − 1• Vi, j+1 , hd2 (i, j + 1, Hi, j+2 , Hi, j ),Vi, j , Hi+1, j• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 ,Vi, j , Hi+1, j• Vi, j+1 , Hi, j , vd2 (i + 1, j,Vi, j ,Vi+2, j ), Hi+1, j
6. solver 0101

where m0 = V(i, j)%(nc − 2).

• Vi, j+1 , Hi, j , vd2 (i + 1, j,Vi, j ,Vi+2, j ), Hi+1, j• Vi+2, j+1 , Hi, j+2 ,Vi, j , hd2 (i + 1, j + 1, Hi+1, j , Hi+1, j+2 )7. solver 0110
• vd2 (i + 1, j + 1,Vi, j+1 ,Vi+2, j+1 ), Hi, j+2 ,Vi, j , Hi+1, j• Vi+2, j+1 , Hi, j ,Vi+2, j , hd2 (i + 1, j + 1, Hi+1, j , Hi+1, j+2 )© 2019 The Author(s)Computer Graphics Forum © 2019 The Eurographics Association and John Wiley & Sons Ltd.