**Abstract**

We present an algorithm for simulating the cracks found in Batik wax painting and dyeing technique used to make images on cloth. The algorithm produces cracks similar to those found in batik due to the wax cracking in the dyeing process. The method is unlike earlier simulation techniques used in computer graphics, in that it is based on the Distance Transform algorithm rather than on a phys- ically based simulation such as using spring mass meshes or ﬁnite element methods. Such methods can be difﬁcult to implement and computationally costly due to the large numbers of equations that need to be solved. In contrast, our method is simple to implement and takes only a few seconds to produce convincing patterns that capture many of the characteristics of the crack patterns found in real Batik cloth.

**1. Introduction**

Batik painting is an ancient art probably originating in India or the Middle East as many as 2000 years ago. However, it is usually associated with the Indonesian islands of Java and Bali [Fraser-Lu 1991]. Liquid wax is painted onto cloth and the cloth is then dyed.

The dye does not affect the cloth where it is painted with wax. This process can be repeated with new colours to add to the complex- ity of the image on the cloth. The wax can optionally be removed from the cloth by scraping and washing between the dye and paint cycles. During the process, cracks can form in the wax allowing dye to seep into the cloth. As the cloth undergoes successive dying procedures the cracks age and become wider. Other subtle effects take place such as cracks becoming wider at junctions with other cracks. These effects combine to form crack patterns that are im- mediately recognisable as batik. The motivation in this work was to produce batik like cracks in a 2D image as a post process operation. The algorithm has been implemented as a ﬁlter in a paint system, so that an artist may paint a simulated wax image and then apply colour and cracks simulating the dyeing and cracking process. In this way a series of layered images simulating wax painting can be combined to produce a ﬁnal simulated Batik painting. Following this introduction the paper is organised into the following sections: previous work, visual characteristics of Batik, distance transforms, crack simulation, controlling the visualization process, dye simula tion, results and conclusions.

**2. Previous Work**

The work we present here is part of the increasing number of new rendering approaches which have been loosely grouped as Non- Photo Realistic Rendering (NPR). Most of these have looked to either ﬁne arts such as painting [Hertzmann et al. 2001], [Curtis et al. 1997] and drawing styles [Winkenbach and Salesin 1994], [Sousa and Buchanan 1999b], [Kalnins et al. 2002] or cartooning [Kowalski et al. 1999]. Our work is in the same spirit in that we are interested in producing an expressive rendering method, however we differ in that we present a new NPR technique that is based on batik, a traditional craft approach. Woodcuts [Mizuno et al. 2000] and mosaics [Kim and Pellacini 2002] are also examples of crafts that have inspired rendering techniques.

In recent years there has been a great interest in modelling the crack formation process in various different media, usually for the purpose of animation. Previous work in the area of fracture forma- tion have concentrated on either simulating the process of breaking an object or on the formation of a crack pattern. An example of shattered models was done by Norton et al. [Norton et al. 1991], in which a tea pot was discretized into cubes, the physical proper- ties were simulated as a mass-spring mesh, and the springs would break when their elastic limit was exceeded. The actual crack pat- terns were quite coarse in this model since they were composed of fairly large sized cubes. Terzopoulos and Fleischer [Terzopou- los and Fleischer 1988b], investigated the modeling of visco-elastic and plastic deformations. They used a ﬁnite differencing technique, and applied it to torn paper and ripped cloth. The method requires that a surface be discretized on a rectangular grid. The resulting fractures exhibited an aliasing effect caused by the imposed grid. Realistic cracks and material behaviour were produced by Metaxas and Terzopoulos [Metaxas and Terzopoulos 1992] using a ﬁnite el- ement method for animating deformations. O’Brien and Hodgins [O’Brien and Hodgins 1999] also developed a method for fracture modelling based on continuum mechanics, in which the material deformation was expressed using strain tensors. Other recent work

in this vein, was done by Koichi Hirota et al, [Hirota et al. 2000], [Hirota et al. 1998]. The continuous model was then discretized into tetrahedral meshes and the ﬁnite element method applied. Re- cent work by Federl and Prusinkiewicz [Federl and Prusinkiewicz 2002] also used ﬁnite element methods applied to a growing rather than a static surface. He was able to reproduce realistic bark pat- terns by simulating the tree growth and patterns of cracks forming in drying mud. Although these physically based methods can produce highly plausible visual results, they are difﬁcult to program and solving the matrices associated with a larger ﬁnite element mesh can take considerable compute time, making fast response in an interactive situation difﬁcult to achieve. O’Brien and Hodgins [O’Brien and Hodgins 1999], for example, report computing times of several minutes per frame; in contrast our crack formation process takes about 4 seconds on a resolution of 1000 squared. O’Brien and Hod- gins point out in [O’Brien and Hodgins 1999] that engineering and computer graphics requirements are different in that engineers wish to use their simulations to make predictions about the real world whereas users of computer graphics are only concerned about how the cracks appear visually. In our work we go a step further and use an algorithm that achieves good results but does not claim to follow physical simula- tion principles. Our approach should therefore be considered more in the context of non-photorealistic rendering rather than in physi- cally based modelling. Others have also followed this principle, see [Raghavachary 2002] and [Gobron and Chiba 2001]. Our method is relatively simple, using only one algorithm, the Distance Transform [Jain 1989]. The interface to the software was written so that artists could use this technique to add a crack texture to an existing battery of ﬁlters. For this reason we built the “crack ﬁlter” as a Photoshop plugin.

**3. Visual Characteristics of Batik**

Figure 2 shows an example of real Batik painting. The inset image (bottom right of the ﬁgure) is a close up taken from within the white rectangle, which shows the characteristic crack patterns found in Batik. There are a number of factors which affect the appearance of the cloth. Firstly the dye is absorbed non-homogenously by the cloth. Introducing some noise into the image can produce a rea- sonable simulation of this effect. In our system, a variation on Perlin noise [Wyvill and Novins 1999] has been used to simulate non-homogenous dye absorption. Cracks are formed in time order, rather than all at once, so a crack will run until meeting the edge of the wax or another crack either of which will stop it. It can be observed in the close-up image that there are few places where one crack crosses another, but there are many T-junctions.

Cracks often end in maximally concave regions of the wax bor- der, as depicted in Figure 3, possibly because it is energetically cheaper for the cracks to be shorter. The wax mask for Figure 3b, was generated by giving as input to our system, an image that rep- resents the wax areas without any cracks. The number of cracks generated is chosen by the user. The generated and real cracks have an overall similarity in position. They are not exact since the start positions for the generated cracks in our system are chosen stochas- tically, and the number of cracks user driven. The tendency for cracks to end in concave regions can be observed in both images and many of the cracks in image a have very similar counterparts in image b.

Cracks erode, therefore older cracks are wider than younger cracks. At T-junctions the wax becomes fragile at the edges and tends to break off, widening the cracks in this region. There are many types of wax used by the various different batik manufactur- ers. Most wax is a combination of beeswax and parafﬁn, and the ra- tio between the two determines how much it will crack (more paraf- ﬁn gives more cracking). For example, unlike Indonesian batik, Chinese batik is made using mostly beeswax, which resists crack- ing when dyed, avoiding the crack patterns that the algorithms de- scribed in this paper attempt to reproduce.

In our simulation the user ﬁrst generates one or more wax im- ages, which will be combined to form the ﬁnished artwork. In our case they are digital images, which encode the characteristics of the wax in the colour channels (see section 7). A wax image is loaded into the simulator, cracks are produced, simulated dye is applied and the result is composited with the ﬁnal image.

**4. Distance Transforms**

In this and the following sections we use the following deﬁnitions: Ω deﬁnes the image domain. W deﬁnes the part of Ω that is covered with wax, and the set V consists of the border of W together with all the cracks. In order to achieve a plausible distribution of cracks, we start from the following observations: (1) newer cracks run from one older crack to another older crack (where the border of the wax domain also counts as one or more cracks), and (2) cracks serve to alleviate the tension in the wax. Therefore tension is close to zero near an older crack, so new cracks should mainly run through regions that are far removed from older cracks. In order to achieve (2), we need to know, in every point of Ω, how far the nearest older crack is. A simple way to do that, is by using a distance transform. Given a subset V of W, the distance transform D(p) in a point p ∈W is deﬁned as

D(p) = MIN(v : v ∈V : |p−v|),

in other words: it is the distance to the point v in V that is nearest to p; |p−v| is the distance between p and v according to some metric. The value of D(p) depends on the distance metric chosen. Us- ing an L2 metric is preferred in many applications as it provides a rotationally invariant measure. Brute force methods to calculate a rotationally invariant distance transform require O(|Ω||V|) calcula- tions. Various work has been done on such methods to increase the efﬁciency [Gavrilova and Alsuwaiyel 2001]. For our application however, experiments show that we don’t re- ally need rotational invariance. A simple implementation using L1 metric, based on Jain’s algorithm [Jain 1989] gives results that are visually just as appropriate with the additional advantage of much simpler code and considerably more efﬁcient execution. The Jain algorithm is a two-pass algorithm with complexity O(|Ω|) as follows:

for(pixel p in V) D(p)=0; for(pixel p in Omega–V) D(p)=infinity; for(pixel p: scan from top left to bottom right){ for(pixel n in upper left half Neighbourhood(p)) if(D(n)+|n-p|<D(p))D(p)=D(n)+|n-p|; } for(pixel p: scan from bottom right to top left){ for(pixel n in lower right half Neighbourhood(p)) if(D(n)+|n-p|<D(p))D(p)=D(n)+|n-p|; }

For some applications, such as modeling the widening of older cracks, not only do we need to know the distance to the nearest fea- ture but also the identity of this feature. (A “feature” here means a crack or the border of W). To this aim, we use an extended ver- sion of the distance transform [Jain 1989]; we call this the identity transform (IDT). Assume that every point p in Ω has a label, λ (p). The labels for points inV are taken from a set Λ = { λ 0, λ 1, λ 2,…}. The algorithm for IDT is as follows:

In our approach to crack propagation, we assume that cracks serve to alleviate the stress distribution in the wax. The energeti- cally cheapest way to do this, is to have cracks of minimal length. So there are two boundary conditions: (1) as explained in section 4, a crack should pass through a point that is at (locally) maximal distance from any earlier crack, since there the stress is (locally) maximal; and (2) a crack should propagate as fast as possible to the nearest feature (i.e. earlier crack or border of the wax). The latter will ensure that begin and end points of new cracks are likely to begin and end at a point of local maximal curvature of older cracks, which conforms to the physical behaviour of cracks.

In order to steer cracks in the direction of the steepest descent of D(p), we need the gradient of D(p). As well as storing D(p) and λ (p) at each pixel, the gradient~ ∇D(p) = ( ∂ D(p) ∂ x , ∂ D(p) ∂ y ) of the distance transform is also calculated and stored. The derivatives are computed on the grid locations using ﬁnite differences; to mitigate aliasing, we ﬁrst low-pass ﬁlter D(p).

Once distance values and their gradients have been computed the crack propagation algorithm is initiated by ﬁrst choosing a seed point inside the wax region. A random point q inside W is chosen (see also section 6). From q, we follow a path in the direction of increasing D(p) to ﬁnd a local maximum of D(p). Let q0 be the location of the local maximum.

From the point q0, the crack is propagated simultaneously in two (normalized) directions ~ d and −~ d. We ﬁnd ~ d as the direction of the steepest descent of D(q0).

In order to represent cracks as polylines, we represent them as a chain of line segements (a polyline) where every vertex has at least one integer coordinate. Notice that pixels, such as the starting point q’, fall in this category as it has both integer coordinates. So, let the current crack point be pc where pc is either on the horizontal or the vertical edge between two adjacent pixels.

From pc downhill,~ ∇D is used to determine the direction of prop- agation, say~ r, by following the gradient. To do this,~ r is evaluated in pc at sub-pixel resolution by linearly interpolating the values of ~ ∇D(p) in the two pixels adjacent to pc. We intersect the line pc + µ ~ r with the four sides of the square shown in ﬁgure 5, con- sisting of pc’s neighbouring pixels and their appropriate opposites. The intersection point that is closest to pc will be the next point on the crack.

Propagating the crack as outlined above, would lead to very straight cracks. To get the characteristic wrinkled appearance, we perturb ~ r with a ﬁltered Brownian motion noise. Both the noise amplitude and the ﬁltering strength are put under user control. The noise amplitude is locally controllable (see section 6); the ﬁlter strength is a global parameter.

In Figure 5 the pixels indicated with black squares are labelled as “on a crack”. Their λ -values receive a serial number that encodes the age of the crack. If there are n cracks required, the λ -value in the pixels that are “on” crack number i are set to n−i. After completion of this crack, the IDT propagates these λ -values to the environment. So, after the IDT, all pixels have the age of the nearest crack set in their λ -value.

## 0