JOURNAL OF LATEX CLASS FILES, VOL. 1, NO. 8, AUGUST 2002

1

Decorating Surfaces with Bidirectional Texture Functions
Kun Zhou, Peng Du, Lifeng Wang, Yasuyuki Matsushita, Jiaoying Shi, Baining Guo, and Heung-Yeung Shum

Abstract— We present a system for decorating arbitrary surfaces with bidirectional texture functions (BTF). Our systemgenerates BTFs in two steps. First, we automatically synthesize a
BTF over the target surface from a given BTF sample. Then we
let the user interactively paint BTF patches onto the surface, suchthat the painted patches seamlessly integrate with the backgroundpatterns. Our system is based on a patch-based texture synthesis
approach known as quilting. We present a graphcut algorithm
for BTF synthesis on surfaces, and the algorithm works well fora wide variety of BTF samples, including those which present
problems for existing algorithms. We also describe a graphcut
texture painting algorithm for creating new surface imperfections(e.g., dirt, cracks, scratches) from existing imperfections foundin input BTF samples. Using these algorithms we can decorate
surfaces with real-world textures that have spatially-variant reflectance, fine-scale geometry details, and surfaces imperfections.
A particularly attractive feature of BTF painting is that it allows
us to capture imperfections of real materials and paint them ontogeometry models. We demonstrate the effectiveness of our systemwith examples.
Index Terms— bidirectional texture function, texture synthesis,
interactive surface painting.

I. I NTRODUCTION
Texture mapping was introduced in [5] as a way to add
surface detail without adding geometry. Texture-mapped polygons have since become the basic primitives of the standard
graphics pipeline. Unfortunately, texture-mapped surfaces dohave a distinctive look that sets them apart from reality: theycannot accurately respond to changes in illumination and viewpoint. Real-world surfaces often are not smooth but covered
with textures that arise from both spatially-variant reflectanceand fine-scale geometry details known as mesostructures [16].
Real surfaces also exhibit imperfections, e.g., dirt, cracks,
and scratches, which usually result from rather complicatedphysical processes. Capturing these surface characteristics isa challenging goal for computer graphics.
To bring us closer to that goal, we develop a systemfor decorating arbitrary surfaces with BTFs [6]. Our system
supports two high-level texturing operations: tiling and painting. Given a BTF sample, the tiling operation automaticallysynthesizes a BTF that fits the target surface naturally andseamlessly. The BTF can model spatially-variant reflectanceand mesostructures. Moreover, the BTF can be measured fromreal materials. Thus the tiling operation provides a convenient
way to cover a surface with fairly realistic textures.
Manuscript received January 20, 2002; revised August 13, 2002.
K.Zhou, L.Wang, Y.Matsushita, B.Guo and H.-Y. Shum are with Microsoft
Research Asia, 3F, Beijing Sigma Center, No. 49, Zhichun Road, Haidian
District, Beijing 100080, PRC. E-mail: {kunzhou, lfwang, yasumat, bainguo,
hshum}@microsoft.com.
P.Du and J.Shi are with Zhejiang University, Hangzhou 310027, PRC. This
work was done while P.Du was intern at Microsoft Research Asia. E-mail:{dupeng, jyshi}@cad.zju.edu.cn.

Fig. 1.
Decorating arbitrary surfaces using BTFs. Left: Result of BTF
synthesis. Right: Result after introducing surface imperfections into thehomogeneous BTF shown on the left.

The painting operation further enhances realism by introducing imperfections and other irregular features as shown in
Fig. 1 and Fig. 7. This operation is valuable because BTFs
generated by our synthesis algorithm, as well as by mostother synthesis algorithms, are homogeneous across the wholesurface. With the painting operation, we can break this global
homogeneity by adding irregular local features. In particular,
we can capture imperfections of real materials and paint them
onto the surface, such that the painted imperfections fit inseamlessly with the background patterns. 3D painting is awell-established technique for creating patterns on surfaces[13]. BTF painting extends traditional techniques in two ways.
First, it provides a way to achieve superior realism with BTFs
measured from real materials. Second, BTF painting reduces
the demand on artistic talents and the tedium of creating
realistic imperfections.
There are two main challenges in developing our system.
First, BTF synthesis on surfaces remains hard for many BTF
samples. The most difficult problem is maintaining mesostructures of the input BTF sample. An existing algorithm [26]addresses this problem with partial success. However, synthesizing a BTF pixel-by-pixel as in [26] leads to fundamental
problems (e.g., L2-norm being a poor measure for perceptual
similarity [1]) in maintaining mesostructures. An alternative
is to synthesize BTFs by copying patches of the input sample(i.e., quilting [8]). Since mesostructures are copied alongwith the patches, this approach is particularly effective formaintaining mesostructures. Unfortunately, patch seams stillpresent a problem for BTFs. Although techniques exist forhiding seams in surface textures, these techniques do not
generalize well to BTFs. For example, [21] used blending
to hide patch seams, but blending will create inconsistentmesostructures in the blended areas (e.g., see [26]).
We present an algorithm for quilting BTF patches byusing graphcut [3], [17] to minimize the discontinuity across

JOURNAL OF LATEX CLASS FILES, VOL. 1, NO. 8, AUGUST 2002

2

We demonstrate the effectiveness of our system with a variety of examples. Note that our techniques work for ordinary
color textures, which may be regarded as BTFs with a single
viewing direction and a single lighting direction.
II. R ELATED W ORK

Fig. 2. A straightforward extension of graphcut to [25] leads to suboptimal
quality when the synthesis results are viewed from a close distance, as theresults in the middle column demonstrate. These results are obtained byincorporating graphcut into [25], which works directly on the original input
mesh (left column, top). Notice the patch seams. The right column shows
results produced by the GIM-based sampling approach. The input texture
sample is shown in the left column (bottom).

patch seams on arbitrary surface meshes. A straightforward
extension of graphcut to hierarchical pattern mapping [25]can be used to generate texture coordinates for each triangleof the mesh. However this would lead to textures that reveal
patch seams when viewed close up. This could be a potential
problem for any attempt to apply graphcut on surfaces. Ouralgorithm solves this problem by densely re-sampling thesurfaces using geometry images [12]. We call this approach
GIM-based sampling. Specifically, given an input mesh wecreate a dense mesh by densely sampling the input mesh using
multi-chart geometry images (MCGIM) [24]. The texture synthesis is accomplished by using graphcut to generate texture
coordinates for each vertex of the dense mesh. Because atexture value is computed for each vertex of the dense mesh,
the synthesized textures can be viewed from any distancejust like those obtained with pixel-based algorithms (e.g.,[26]). Fig. 2 compares the results of the GIM-based sampling
approach with a straightforward extension of graphcut to [25].
The second challenge we face is finding a user-friendly
way to introduce irregular features into a background pattern.
Graphcut techniques suggest a straightforward approach tomerging a foreground feature with the background pattern,i.e., we simply constrain the feature to a desired location anduse graphcut to find the merging seam. However, this approach
only supports verbatim copying of existing features. To allow
the user to generate new features, we formulate the constrainedgraphcut problem for texture and BTF painting. For texture
synthesis, only smoothness energy is considered for finding
seams that minimize discontinuity [17]. For texture painting,both smoothness and constraint energies are used so that theuser’s specification of the new feature is incorporated into thegraphcut problem as constraints. Generating a new feature withthe graphcut painting algorithm is easy. The user only needs
to specify the rough shape and location of the desired newfeature; our system will synthesize the actual feature and haveit merged seamlessly with the background pattern.

Texture Synthesis: Algorithms for synthesizing textures on
surfaces can be divided into two categories. The first category[11], [27], [29], [32], [26], [33], [34] is based on per-pixel nonparametric sampling [9], [28]. Per-pixel sampling is susceptible to the problems caused by the fact that the commonly used
L2-norm is a poor measure of perceptual similarity. For thisreason algorithms in this category have difficulty maintaining
texture patterns with certain types for textures [1], [14], [34].
Currently there is no general solution, but remedies exist forvarious specific scenarios [1], [34].
Algorithms in the second category synthesize textures bycopying patches of the input texture sample. Since texture
patterns are directly copied onto the target surface, thesealgorithms are not seriously affected by the issue with theL2-norm. Earlier algorithms randomly paste patches and usealpha-blending to hide patch seams [23], [31]. Quilting [8],[19], [25], [21], [17] generates significantly better results bycarefully placing patches to minimize the discontinuity acrosspatch seams. After placing patches, [19], [21] simply usealpha-blending to hide patch seams, while [8], [17] further
enhance the smoothness across the seams by searching for the“min-cut” seams.
For image textures, [17] recently demonstrated that quiltingwith graphcut produces arguably the best results on the largest
variety of textures. In this paper we show how to perform
graphcut on surfaces.
Decorating Surfaces: For decorating implicit surfaces, [22]proposed a set of texturing operations which include tilingand positioning of small images onto surfaces. [15], [10], [4]presented several 3D surface painting systems. For decorating
surfaces with imperfections, existing techniques (e.g., [2], [30],[7] mostly focus on generating synthetic surface imperfections.
Complementary to their approaches, our techniques synthesize
imperfections from real-world and synthetic samples.
III. BTF S YNTHESISGiven a mesh M and input BTF sample, we first build adense mesh Md and then synthesize a BTF value for eachvertex of Md by quilting patches of the input sample on Md .
A. GIM-based Sampling
As mentioned, it is possible to incorporate graphcut techniques into a synthesis algorithm that works directly on theoriginal input mesh. One such algorithm is pattern mapping[25], which generates texture coordinates for each triangle ofthe input mesh. Unfortunately, the synthesis results are notideal when viewed from a close distance, as Fig. 2 demonstrates. With the pattern mapping approach, two adjacenttriangles on the mesh may be far apart in the texture space.
During texture synthesis, textures on two such triangles arematched at a fixed sampling resolution (this resolution is a

JOURNAL OF LATEX CLASS FILES, VOL. 1, NO. 8, AUGUST 2002

(a)

(b)

(c)

(d)

Fig. 3. Construction of a dense mesh for BTF synthesis. (a) and (b) Texture
atlas. (c) and (d) Multi-chart geometry image mesh (MCGIM), which samples
a surface using a regular grid. Each mesh vertex is a grid point.

parameter of the synthesis algorithm). When synthesis results
are viewed at a higher resolution, the seam between the two
triangles becomes noticeable.
Our GIM-based sampling approach provides an effective
and general solution for applying graphcut to surfaces. Fromthe input mesh M , we construct the dense mesh Md as an
MCGIM [24]. The MCGIM uses a texture atlas to resample
M and zippers chart boundaries to obtain a “watertight”
mesh Md . We create the texture atlas using the method
proposed in [35], which partitions a mesh into fairly large
charts and parameterizes the charts with minimized stretch.
Fig. 3 provides an example of MCGIM. The sampling rateof the MCGIM is a user-specified parameter. For examples
reported in this paper, the sampling rate is either 512 × 512
or 1024 × 1024.
The main advantage of the dense mesh Md is the oneto-one correspondence between vertices of Md and pixels in
the texture atlas. Because of the correspondence, synthesizing
BTF values for vertices on Md is the same as that for
pixels of the charts of the texture atlas. The pixel-vertex
correspondence makes it easy to flatten a large patch of Md
without introducing noticeable texture distortion. In fact, fora pixel in the interior of a chart, the pixel’s 2D neighborhood
directly provides neighboring samples and a local flattening.
We will use the pixel-vertex correspondence to simultaneously
work on a surface patch of Md and its corresponding image
and switch freely between the two.
B. Quilting on the Dense Mesh
From the input of an MCGIM Md and a BTF sample S,
the pseudo-code shown in Fig. 4 produces BTF values of allvertices of Md .
The algorithm synthesizes the surface BTF by copying
patches of the sample BTF. Each time, the next BTF patch Pb
to be generated is around an un-synthesized vertex v which

3

While there are still un-synthesized vertices in Md dopick the most constrained un-synthesized vertex v
build a work patch P (v) centered at v
found work patch = FALSE
While found work patch == FALSE do
If P (v) lies inside a single chartfound work patch = TRUE
obtain the work image I(v) from the chartElseparameterize P (v) using LSCM
If parameterization distortion ≤ threshold Td
found work patch == TRUE
create the work image I(v) by resampling P (v)Elsedecrease the size of P (v)found cut = FALSE
While found cut == FALSE dopatch matching in I(v)patch fitting in P (v) using graphcut
If the optimal seam cost is below threshold Tc
found cut = TRUE
Else
decrease the size of I(v) and P (v)get BTF values for vertices of P (v)Fig. 4.

Pseudo-code for texture quilting on the dense mesh.

is the most constrained, i.e., having the largest number of
immediate vertex neighbors that are synthesized.
Work Patch/Image: To compute the next BTF patch Pb , westart by building a work patch P (v) centered at v. We find
P (v) by a breadth-first traversal starting at v. The numberof levels in the breadth-first traversal is defined as a usersupplied parameter called the work patch size rw . For a 512 ×
512 MCGIM Md , a typical working patch size is rw = 32.
Intuitively, we can think of the work patch P (v) as a disk ofradius rw .
From the work patch P (v) we derive the work image I(v)using a continuous parameterization of P (v) by considering
two cases. The first case is simple. If P (v) lies completely
inside a chart of the MCGIM Md , then I(v) is simply thecorresponding sub-image of the chart image and no parameterization or resampling is necessary. The second case is more
complex. If P (v) crosses chart boundaries, we parameterize
P (v) using the least squares conformal mapping (LSCM) [18]and resample the result to obtain the work image I(v). To
minimize the texture distortion caused by LSCM we monitor
the area distortion by a threshold Td , which is set to 4 in ourcurrent implementation. For resampling, we set the sampling
step to the average edge length of the work patch. If a sampling
point p is located in a triangle with three synthesized vertices,
the BTF value at p is interpolated from these vertices andthe sampling point is marked as synthesized. Otherwise p
is marked as un-synthesized. This way we obtain a partiallysynthesized work image I(v).
Patch Matching: Having built the work patch and image, we
can now calculate the next BTF patch Pb using graphcut. For
quilting with graphcut, the main tasks are patch matchingand patch fitting [17]. Patch matching places a candidate
patch (the input sample) over a target area by comparing
the candidate patch and the synthesized pixels in the target
area. Patch fitting applies graphcut to select a piece of the

JOURNAL OF LATEX CLASS FILES, VOL. 1, NO. 8, AUGUST 2002

(a)

4

(b)

(a)

(b)

(c)

(d)

Fig. 6. Singular value decomposition of a BTF. (a) Two images of the
BTF with different viewing and lighting directions. (b) - (d) The three mostsignificant eigen pixel appearance functions (PAF; top row) and geometrymaps (bottom row). A 4D PAF is packed into a 2D image, in which eachrow corresponds to the varying light direction and each column corresponds
to the varying view direction.
(c)

(d)

Fig. 5. BTF synthesis using a work patch and a work image. (a) Finding awork patch on the surface. (b) The initial work patch. (c) Work image withsynthesized and un-synthesized pixels. (d) Work patch after fitting a new
texture patch, with the graphcut seam shown in yellow.

candidate patch to be the next synthesized BTF patch Pb . We
perform patch matching in the work image I(v) using theentire patch matching method proposed in [17]. The sum-ofsquared-differences (SSD) cost for the BTF is normalized withthe area of the overlap region between the input sample and thework image, and the patch placement with the minimal cost is
selected for patch fitting. The SSD-based search is acceleratedusing FFT as in [17].
A technical difference between our patch matching and thatof [17] is that we use both translations and rotations, whereas
they only use translations. The reason for this difference isthat surface quilting involves a vector field. The vector field isimportant for orienting anisotropic textures on surfaces and for
BTF rendering, which requires a local frame at each surface
point [26]. We designed a user interface to let the user specify
vectors at a few key faces and then interpolate these vectors
to other faces using radial basis functions [23].
During patch matching, we calculate an average orientation
for the work image using the vector field on the work patch.
The average orientation is then used to align the input BTF
sample S for patch matching. In our system we pre-compute72 rotated versions of S and select the best for patch matching.
Patch Fitting: After the input sample S is placed over thework patch I(v) by patch matching, we can easily map S
onto the work patch P (v) using the correspondence between
I(v) and P (v). Now every vertex of P (v) covered by the
mapped and rotated input sample S gets a new BTF value,and every synthesized vertex of P (v) also has an old BTF
value. Based on these old and new values, we apply graphcut
to select a piece of S by regarding vertices of P (v) as graphnodes and the edges of P (v) as graph edges. The BTF valuesof the selected piece are copied to the vertices of P (v) if theseam cost is below a prescribed threshold Tc . Note that old
seams from previous graphcut steps can be accounted for thesame way as in [17].

Hierarchical Search: For high-quality results we only accept
a piece selected by graphcut if the seam cost is below thethreshold Tc . If the seam cost exceeds Tc we decrease thework patch size rw by a constant factor (which is set to 0.8
for examples reported in this paper) and repeat the search. We
decrease rw as many times as needed until rw reaches theminimum size of 4. We employ the same hierarchical searchstrategy to control the area distortion of the LSCM parameterization when we build the work patch. Other researchers (e.g.
[25]) used similar ideas for texture synthesis.
Handling BTF Values: The BTF is a 6D function f (x, v, l),where x = (x, y) is the texture coordinate. v = (θv , φv ) andl = (θl , φl ) are the lighting and viewing directions in sphericalcoordinates. For each texel x = (x, y), the BTF value is a
4D function discretized into a high-dimensional vector. Thishigh dimension requires careful treatment when storing BTFs
and calculating SSD costs for patch matching and fitting. For
efficient storage of various BTFs including rotated copies of
the input sample and the synthesized surface BTFs, we only
store the texture coordinates as in [26]. When necessary theactual BTF value is retrieved from the input sample using
texture coordinates.
For efficient SSD cost calculation, we factorize the BTF as
a sum of products of 2D and 4D functions using singular value
decomposition (SVD) as in [20].
f (x, v, l) ≈nXgi (x)pi (v, l),i=1where gi (x) is called a geometry map and pi (v, l) is calledan eigen point appearance function (PAF). Fig. 6 shows a
SVD factorization of a 128 × 128 BTF sample (the viewing
and lighting resolution is 12 × 8 × 12 × 8 ). The geometrymaps depend on texture coordinates only, whereas the PAF
is a function of the viewing and lighting directions. [20]developed an algorithm which synthesizes a surface BTF using
the corresponding geometry maps. We adopt this algorithm forsurface quilting with n = 40 and calculate the SSD costs with
low-dimensional vectors.
For ordinary color textures, we store vertex colors directly
into Md and thus create a texture map (usually of size 512 ×

JOURNAL OF LATEX CLASS FILES, VOL. 1, NO. 8, AUGUST 2002

5
e(i,j)
tAi
tBi

...
...

...

cut

Patch B

2

A
...

(a)

...
5

...

...

B

8
...

...

3

7
...

...

...
Patch A

4

...
. ..

1

Overlap

...
6

9
...

(a)

(b)

(c)

(d)

Fig. 7.
Constructing a constrained quilt. (a) Input texture sample. (b)Specifying a foreground feature (shown in white) in the input sample. (c)User-specified foreground region F (shown in white) in the output texture.
(d) A constrained quilt with patch boundaries (cut seams) shown in yellow.

(b)Fig. 8. Graph formulation for the seam finding problem in graphcut texture
painting.

512 or 1024 × 1024). With this texture map, the synthesized
surface texture can be rendered using the standard texture
mapping pipeline.

of the overlapping region, we have a user-specified constraint
value m0 (p).
Our goal is to assign a patch label σp to every pixel p in
the overlapping region (σp = A or B), so that the region isdivided into two parts by a seam of minimum cost (energy).
The energy we minimize is defined as

IV. BTF PAINTING

E(σ) = Edata (σ) + Esmooth (σ).

Suppose that we are given a sample texture S with aforeground feature over a background pattern. Suppose that thebackground pattern has been synthesized onto the target mesh
M . Our BTF painting system lets the user interactively synthesize new foreground features on M by roughly specifying
their shapes and locations. Prior to this synthesis, we assume
that the user has roughly specified the foreground feature inS.
The key ingredient of the painting system is our graphcut
texture painting algorithm, which minimizes both smoothness
and constraint energy to build a quilt of patches.
A. Graphcut Texture Painting
Fig. 7 shows the construction of a constrained quilt Q. We
assume that the sample texture S has been partitioned into
two parts: the background pattern Sb and foreground feature
Sf . We also assume that the user has specified a foregroundregion F of the target mesh M . The constrained quilt Q(F ) isa quilt consisting of patches of M such that Q(F ) completely
covers F and each patch of Q(F ) is directly texture-mappedfrom a patch in the input sample S. The constraint on Q(F )is that F should be textured only by the foreground feature
Sf .
To construct the constrained quilt Q(F ) using graphcut, we
encode the user-specified constraints as constraint functions.
We define a function m0 on the target mesh M such thatm0 (p) = 1 if point p belongs to F and m0 (p) = 0 otherwise.
Similarly, for every patch P of the constraint quilt Q(F ) we
define a function mP such that mP (p) = 1 if point p belongs
to the foreground feature and mP (p) = 0 otherwise. With
these functions defined, we introduce constrained graphcut,
which is the core part of graphcut texture painting.
Constrained Graphcut: For simplicity we describe constrained graphcut for image textures. Consider two overlapping
constrained patches A and B as shown in Fig. 8 (a). Each pixel
p of patch A has a texture value fA (p) and a constraint valuemA (p). Similarly, each pixel p of patch B has a texture valuefB (p) and a constraint value mB (p). Finally, for every pixel p

In general graphcut problems, the smoothness energy Esmoothmeasures the extent to which σ is not smooth, while thedata energy Edata measures the difference between σ andsome known data [3]. For graphcut texture painting, Esmoothmeasures how well the patches fit together along their seams,
whereas Edata = Econstraint measures how well the synthesized texture satisfies the user specified constraint m0 .
Fitting patches together while minimizing Esmooth along
the seams is done the same way as graphcut texture synthesis[17]. The energy Esmooth is defined as in [3]XV(p,q) (σp , σq ),Esmooth (σ) =p,qP

where p,q is the sum over all pairs of adjacent pixels in theoverlapping region. The smoothness function V(p,q) (σp , σq ) isdefined asV(p,q) (σp , σq ) = ||fσp (p) − fσq (p)|| + ||fσp (q) − fσq (q)||,where fA (p) and fB (p) are pixel p’s texture values for patches
A and B respectively.
For graphcut texture painting, we need to further satisfy theuser-specified constraint m0 . This is where graphcut texture
painting differs from graphcut texture synthesis, which uses
Esmooth only. We incorporate the user-specified constraint into
quilting by making use of the energy Edata defined asX
Dp (σp ),Edata (σ) = Econstraint (σ) =pPwhere p is the sum over all pixels in the overlapping region.
The function Dp (σp ) is defined as
Dp (σp ) = ||mσp (p) − m0 (p)||where mσp (p) is the constraint value of patch σp at pixel p,
while m0 (p) is the user-specified constraint value at pixel p.
We use the optimal swap move approach [3] to minimize
the energy E(σ). Fig. 8 (b) illustrates the graph construction.
The nodes of the graph consist of all pixels in the overlapping
region and two terminals A and B. Each pixel p in the

JOURNAL OF LATEX CLASS FILES, VOL. 1, NO. 8, AUGUST 2002

6

(a)

(b)

(e)

Fig. 9. Our painting user interface. Input samples with surface imperfections
are shown on the right-hand side panel.

overlapping region is connected to the terminals A and B by
B
edges tAp and tp , respectively. These edges are referred to as
t-links (terminal links). Each pair of the adjacent pixels (p, q)
in the overlapping region is connected by an edge e(p,q) called
an n-link (neighbor link). The weights of the edges areBweight(tAp ) = Dp (A), weight(tp ) = Dp (B)weight(e(p,q) ) = V(p,q) (A, B)
Applying the min-cut algorithm to the constructed graphproduces the minimum cost cut that separates node A fromnode B. As explained in [3], any cut in the graph must include
exactly one t-link for any pixel p. Thus, any cut leaves eachpixel p in the overlapping region with exactly one t-link, which
defines a natural label σp according to the minimum cost cut
C,
½
A
tA
p ∈C
σp =
B
tB
p ∈C
The approach for handling old seams in graphcut texture
synthesis also works with graphcut texture painting.
Quilting on Surfaces: The surface quilting algorithm described in Section III can be adopted for graphcut texture
painting on surfaces with modifications of the patch matching
and fitting steps. For patch matching, we use both the BTF
values and the constraint values (ms and m0 values) toperform a joint search for optimal patch placement. For patch
fitting, we use constrained graphcut.
B. Painting System
Fig. 9 exhibits a screenshot of our painting system. For userinteractivity we do not render surfaces with the BTF. Instead
we display an ordinary color texture that provides a quick
preview of the actual BTF. The color texture is obtained as
one of the BTF images (usually the one with the front parallelview and head-on lighting).
Our painting system modifies the user-specified constraintfunction m0 to improve the quality of the constrained quilt.
As mentioned, the user specifies the foreground region F on
the target surface and thus defines the constraint m0 such that

(c)

(d)

(f)

(g)

Fig. 10. Computing the constraint function m0 in our painting system.
(a) Input sample. (b) Specifying a foreground feature in the input sample.
(c) User-specified m0 . (d) m0 computed by our painting system. (e) Painting
results using a naive modification of m0 . (f) Painting results using m0 shownin (c). Notice the broken texture patterns in the orange area. (f) Painting results
using m0 shown in (d).

m0 = 1 over F and m0 = 0 elsewhere. Unfortunately, m0
defined this way has an abrupt change along the boundary of F
and this abrupt change often leads to destroyed texture patterns
in nearby areas, as illustrated in Fig. 10 (f). A naive solution tothis problem is to weaken m0 as m0 = λ over F and m0 = 0
elsewhere for some small λ. From the definition of the data
energy Edata , if m0 is set to a small value λ, Edata will playa less important role in the total objective energy. However,when λ is small, m0 ceases to be effective and backgroundelements start to appear in F as shown in Fig. 10 (e). Our
solution is to expand a transition zone from the boundary of F
and interpolate the values of m0 in the transition zone using
linear interpolation as shown in Fig. 10 (d). The width of
the transition zone is a user-adjustable parameter. Fig. 10 (g)shows a synthesis result with the transition zone.
In addition to synthesizing new foreground features, our system also supports verbatim copying of the foreground featurefrom the input sample onto the surface. This is a straightforward extension of the verbatim copying technique for image
textures ([17] called this interactive blending and merging).
A useful feature of our system is that it previews a verbatim
copying operation by directly projecting the foreground feature
onto the surface. Although the projected foreground feature isnot seamlessly merged with the background, the preview still
provides valuable visual feedback. With our system the user
can slide the foreground feature on the surface to find a desired
pasting location since the foreground feature can be mapped
onto the surface extremely quickly using the work patch/imageat the target location.
V. R ESULTSBTF Synthesis: Our synthesis algorithm generates good results on a wide variety of BTFs, including those that cannot
be handled well by existing pixel-based BTF synthesis algorithms. Fig. 11 provides examples of our synthesis results.
Fig. 12 (a) shows an example of a BTF that cannot be handled

JOURNAL OF LATEX CLASS FILES, VOL. 1, NO. 8, AUGUST 2002(a)Fig. 11.

(b)

7

(c)

BTF synthesis results for three synthetic BTF samples.

Fig. 13. Tree bark generated with BTF synthesis followed by BTF painting.
The input BTF sample is shown in the lower left.

(b)

(a)

(d)

(c)

(e)

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 12.
Comparison of pixel-based BTF synthesis with our synthesis
algorithm. (a) Input sample. (b) and (d) Pixel-based systhesis result. Noticethat mesostructure of the leaves are not well maintained. (c) and (e) Our result.

well with existing techniques. This BTF is measured fromreal plastic leaves. Fig. 12 (b) and (c) exhibit the synthesis
results of the pixel-based algorithm proposed by [26] andour algorithm respectively. Our result faithfully captures themesostructures of the original BTF, while the pixel-basedalgorithm does not.
BTF synthesis is an off-line process that usually takes about
10 - 20 minutes for a 128×128 input sample (the lighting andviewing resolution is 12 × 8 × 12 × 8). The timing depends
on the number of charts in the MCGIM dense mesh Md andthe size of Md (512 × 512 or 1024 × 1024 ). The timings aremeasured on a PC with a Xeon 3.0 GHz processor.
BTF Painting: BTF painting (verbatim copying) is an interactive process. With BTF painting we can capture imperfectionsof real materials and paint them onto geometry models. Fig. 14(a) shows a BTF captured from a real knitwear with a small
imperfection. Fig. 14 (b) and (c) exhibit results generatedby BTF synthesis followed by interactive painting. With thisapproach, we can generate real-world imperfections that are
difficult to obtain by physically-based simulation techniques.
Note that the foreground synthesis is an off-line process justlike the background BTF synthesis. It depends on the sizes ofthe foreground areas specified by users.
Fig. 13 and 15 provide more examples of surface decoration
with BTFs and imperfections. The BTF samples used in theseexamples are modelled by an artist and rendered using a

Fig. 17.

Texture atlases for models used in Fig.16.

ray tracer. Acquiring these BTF samples is difficult and time
consuming. With our system, the user only has to generatesmall BTF samples and can decorate arbitrarily large objects
using automatic BTF synthesis followed by interactive BTF
painting.
Texture synthesis: Note that our surface quilting algorithm
also works well for ordinary color textures. Fig. 16 provides
synthesis results for some texture samples with highly structured patterns, using both a pixel-based algorithm [27] and ouralgorithm. For these texture samples, the pixel-based algorithm
always causes the texture patterns to break apart while oursurface quilting algorithm can preserve the integrity of texture
patterns very well. Fig. 17 shows the texture atlases for models
used in Fig. 16.
VI. C ONCLUSION
We presented a system for decorating surfaces with BTFs.
This system is based on a graphcut algorithm for BTF synthesis on surfaces and a graphcut texture painting algorithm.
Our work on BTF synthesis demonstrates that quilting BTF

JOURNAL OF LATEX CLASS FILES, VOL. 1, NO. 8, AUGUST 2002

8

(a)

(b)

(c)

Fig. 14. Decorating surfaces with BTFs measured from real materials. (a) Input BTF sample with imperfections. (b) and (c) Surfaces decorated with BTF
synthesis followed by BTF painting.

Fig. 15.

Surfaces decorated with BTF synthesis followed by BTF painting. The input BTF sample is shown in the upper right.

patches with graphcut provides an effective way to maintainmesostructures, which is not possible with existing techniques.
Our graphcut texture painting algorithm allows us to interactively paint with BTF patches. With BTF painting we canmeasure surface imperfections from a real material and paintthem onto geometry models, making graphics models moreinteresting and better resemble real-world objects. In future
work, we are interested in improving the speed of our synthesis
algorithm.
ACKNOWLEDGEMENTS
We thank Steve Lin for his help in video production andproofreading of this paper. Thanks to anonymous reviewers
for their constructive critiques on our ill-fated Siggraph 2004
submission. Yi Wang wrote the BTF rendering code andgenerated the BTF rendering results shown here. Jiaoying Shi
was supported by NSFC (No. 60033010).
R EFERENCES[1] Michael Ashikhmin. Synthesizing natural textures. 2001 ACM Symposium on Interactive 3D Graphics, pages 217–226, March 2001.
[2] Norman I. Badler and Welton Becket. Imperfection for realistic image
synthesis. Journal of Visualization and Computer Animation, 1(1):26–
32, August 1990.
[3] Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy
minimization via graph cuts. IEEE Trans on Pattern Analysis andMachine Intelligence, 23(11):1–18, November 2001.

[4] Nathan A. Carr and John C. Hart. Painting detail. ACM Transactions
on Graphics, 23(3):842–849, August 2004.
[5] Edwin Catmull. A subdivision algorithm for computer display of curved
surfaces. 1974.
[6] Kristin J. Dana, Bram van Ginneken, Shree K. Nayar, and Jan J.
Koenderink. Reflectance and texture of real-world surfaces. ACM
Transactions on Graphics, 18(1):1–34, January 1999.
[7] Julie Dorsey, Alan Edelman, Justin Legakis, Henrik Wann Jensen, andHans Køhling Pedersen. Modeling and rendering of weathered stone. In
Proceedings of SIGGRAPH 99, Computer Graphics Proceedings, Annual
Conference Series, pages 225–234, August 1999.
[8] Alexei A. Efros and William T. Freeman. Image quilting for texture
synthesis and transfer. In Proceedings of ACM SIGGRAPH 2001,
Computer Graphics Proceedings, Annual Conference Series, pages 341–
346, August 2001.
[9] Alexei A. Efros and Thomas K. Leung. Texture synthesis by nonparametric sampling. In Proceedings of International Conference on
Computer Vision, September 1999.
[10] Mark Foskey, Miguel A. Otaduy, and Ming C. Lin. Artnova: Touchenabled 3d model design. In IEEE Virtual Reality Conference, pages
119–126, March 2002.
[11] Gabriele Gorla, Victoria Interrante, and Guillermo Sapiro. Growing
fitted textures. SIGGRAPH 2001 Sketches and Applications, page 191,
August 2001.
[12] Xianfeng Gu, Steven J. Gortler, and Hugues Hoppe. Geometry images.
ACM Transactions on Graphics, 21(3):355–361, July 2002.
[13] Pat Hanrahan and Paul E. Haeberli. Direct wysiwyg painting and texturing on 3d shapes. In Computer Graphics (Proceedings of SIGGRAPH90), volume 24, pages 215–223, August 1990.
[14] Aaron Hertzmann, Charles E. Jacobs, Nuria Oliver, Brian Curless, andDavid H. Salesin. Image analogies. Proceedings of SIGGRAPH 2001,
pages 327–340, August 2001.
[15] Takeo Igarashi and Dennis Cosgrove. Adaptive unwrapping for interac-JOURNAL OF LATEX CLASS FILES, VOL. 1, NO. 8, AUGUST 2002

(a)

(b)

(c)

9

(d)

(e)

(f)

Fig. 16. Texture synthesis results. (a) and (d) are the input texture samples. (b) and (e) show the synthesis results using a pixel-based algorithm [27]. (c)and (f) show the results using our algorithm.

tive texture painting. In ACM Symposium on Interactive 3D Graphics,
pages 209–216, March 2001.
[16] Jan J. Koenderink and Andrea J. Van Doorn. Illuminance texture due
to surface mesostructure. Journal of the Optical Society of America,
13(3):452–463, 1996.
[17] Vivek Kwatra, Arno Schödl, Irfan Essa, Greg Turk, and Aaron Bobick.
Graphcut textures: Image and video synthesis using graph cuts. ACM
Transactions on Graphics, 22(3):277–286, July 2003.
[18] B. Lévy, S. Petitjean, N. Ray, and J.-L. Mallet. Least squares conformal maps for automatic texture atlas generation. In Proceedings of
SIGGRAPH 2002, pages 362–371, 2002.
[19] Lin Liang, Ce Liu, Yingqing Xu, Baining Guo, and Heung-Yeung
Shum. Real-time texture synthesis using patch-based sampling. ACM
Transactions on Graphics, 20(3), July 2001.
[20] Xinguo Liu, Yaohua Hu, Jingdan Zhang, Xin Tong, Baining Guo, andHeung-Yeung Shum. Synthesis and rendering of bidirectional texture
functions on arbitrary surfaces. IEEE Trans on Visualization andComputer Graphics, 10(3):278–289, May 2004.
[21] Sebastian Magda and David Kriegman. Fast texture synthesis onarbitrary meshes. In Eurographics Symposium on Rendering, June 2003.
[22] Hans Køhling Pedersen. Decorating implicit surfaces. In Proceedingsof SIGGRAPH 95, pages 291–300, August 1995.
[23] Emil Praun, Adam Finkelstein, and Hugues Hoppe. Lapped textures.
Proceedings of SIGGRAPH 2000, pages 465–470, July 2000.
[24] P.V. Sander, Z. Wood, S.J. Gortler, J. Synder, and H. Hoppe. Multi-chartgeometry images. In Symposium on Geometry Processing 2003, pages
146–155, 2003.
[25] Cyril Soler, Marie-Paule Cani, and Alexis Angelidis. Hierarchicalpattern mapping. ACM Transactions on Graphics, 21(3):673–680, July
2002. (Proceedings of ACM SIGGRAPH 2002).
[26] Xin Tong, Jingdan Zhang, Ligang Liu, Xi Wang, Baining Guo, andHeung-Yeung Shum. Synthesis of bidirectional texture functions onarbitrary surfaces. ACM Transactions on Graphics, 21(3):665–672, July
2002.
[27] Greg Turk. Texture synthesis on surfaces. Proceedings of SIGGRAPH
2001, pages 347–354, August 2001.
[28] Li-Yi Wei and Marc Levoy. Fast texture synthesis using tree-structured
vector quantization. Proceedings of SIGGRAPH 2000, pages 479–488,
July 2000.
[29] Li-Yi Wei and Marc Levoy. Texture synthesis over arbitrary manifold
surfaces. Proceedings of SIGGRAPH 2001, pages 355–360, August
2001.
[30] Tien-Tsin Wong, Wai-Yin Ng, and Pheng-Ann Heng. A geometry dependent texture generation framework for simulating surface imperfections.
In Eurographics Rendering Workshop 1997, pages 139–150, June 1997.
[31] Y. Q. Xu, B. Guo, and H. Y. Shum. Chaos Mosaic: Fast and Memory
Efficient Texture Synthesis. In Microsoft Research Technical Report
MSR-TR-2000-32, April 2000.
[32] Lexing Ying, Aaron Hertzmann, Henning Biermann, and Denis Zorin.
Texture and shape synthesis on surfaces. Proceedings of 12th Eurographics Workshop on Rendering, pages 301–312, June 2001.
[33] Steve Zelinka and Michael Garland. Interactive texture synthesis on
surfaces using jump maps. In Eurographics Symposium on Rendering:
14th Eurographics Workshop on Rendering, pages 90–96, June 2003.
[34] Jingdan Zhang, Kun Zhou, Luiz Velho, Baining Guo, and Heung-Yeung
Shum. Synthesis of progressively variant textures on arbitrary surfaces.
ACM Transactions on Graphics, 22(3):295–302, July 2003.
[35] Kun Zhou, John Snyder, Baining Guo, and Heung-Yeung Shum. Isocharts: Stretch-driven mesh parameterization using spectral analysis. In
Symposium on Geometry Processing 2004, pages 47–56, 2004.