Hedlena Bezerra
email: hedlena@inf.puc-rio.br

Bruno Feijó

Luiz Velho
email: lvelho@impa.br

An image-based shading pipeline for 2D animation

Keywords: cel animation, non-photorealistic rendering, image-based shading, computer-assisted animation

Shading for cel animation based on images is a recent research topic in computer-assisted animation. This paper proposes an image-based shading pipeline to give a 3D appearance to a 2D character by inspecting the hand-drawn image directly. The proposed method estimates normal vectors on the character's outline and interpolates them over the remaining image. The method does not limit the animator's creative process and requires minimal user intervention. The resulting shading pipeline can be easily applied to photorealistic and non-photorealistic 2D cel animation.

In the proposed method, the animator can easily simulate environment reflections on the surface of 2D reflecting objects. As far as the authors are concerned, the proposed technique is the only one in the literature that is genuinely an image-based method for 2D animation.

Introduction

Traditional animation [START_REF] Blair | Cartoon Animation[END_REF], sometimes called cel animation, hand-drawn animation, cartoon animation, or 2D animation, is the most popular form of animation. The process of producing a 2D animation sequence can be roughly divided into two major stages: the drawing process and the ink and paint process. The drawing process can also be roughly broken into two sub-stages: (i) experienced animators draw the extreme poses of the character, which represent the main course of action; (ii) less experienced animators draw the inbetween drawings between the extreme poses. The main steps in the ink and paint process are: (i) drawings are traced onto acetate cels in ink; (ii) gouache or a similar type of paint is applied to the reverse side of the cels, producing paint regions, in which rims and tones are added to give the illusion of volume and illumination. A first major problem in 2D animation is to keep the frameto-frame coherence of the drawing volumes (e.g. the 4 legs of a tiger) and the painted strokes (e.g. the stripes of a tiger) as would be in a 3D character. Another main problem is to illuminate the 2D character as it were a 3D object living in a 3D illuminated environment (called the shading problem). The origin of these problems is the fact that the 1 animator's drawings and paints are really two-dimensional projections of 3D characters as visualized in the animator's mind. These problems become even bigger when computerassisted animation systems [START_REF] Fekete | TicTacToon: A paperless system for professional 2D animation[END_REF][START_REF] Griffin | The Animator's Guide to 2D Computer Animation[END_REF] are used. Ed Catmull [START_REF] Catmull | The problems of computer-assisted animation[END_REF], in 1978, was among the first ones to discuss the frame-toframe coherence in computer-assisted animation. The shading problem in computer-assisted 2D animation is a much recent concern [START_REF] Corrêa | Texture Mapping for Cel Animation[END_REF][START_REF] Igarashi | Teddy: a sketching interface for 3D freeform design[END_REF][START_REF] Petrovic | Shadows for cel animation[END_REF][START_REF] Johnston | Lumo: Illumination for cel animation[END_REF][START_REF] Fiore | Employing Approximate 3D Models to Enrich Traditional Computer Assisted Animation[END_REF], although some related works could be traced back to the beginning of the 90's [START_REF] Williams | Shading in two dimensions[END_REF]. S. Johnston [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF] discusses the shading problem very clearly, indicating that the components involved in the illumination of a point on a surface (position and surface normal) are incomplete in hand-drawn artwork -the surface normal is unknown and the position information lacks depth.

Computer assistance for traditional animation can be considered part of the new area of Non-photorealistic Rendering -we recommend a visit to the Web page by Craig Reynolds [START_REF] Reynolds | Stylized Depiction in Computer Graphics -Non-Photorealistic, Painterly and 'Tonn Rendering[END_REF]. Current research on computer assistance for traditional animation focuses on two main lines: geometrybased methods and image-based methods. In the first, geometric objects are created in order to support the animation process. The latter uses image-based techniques to render the 2D character without jumping to 3D geometry. The great advantage of the geometry-based methods is the possibility of supporting both the frame-to-frame coherence and the shading process. However, these methods cannot cope with more fluid animations, where few strokes would change the implied geometry drastically. On the other hand, image-based methods work directly with the vivid drawings made by the artist.

This paper proposes an image-based shading pipeline to give a 3D appearance to a 2D character by inspecting the hand-drawn image directly. The goal is to minimize the user intervention by extracting information based only on the 2D image. We show that the character's outline is the only information needed to infer a 3D aspect through an illumination model. The proposed method estimates normal vectors on the character's outline and interpolates them over the remaining image. As far as the authors are concerned, the proposed technique is the only one in the literature that is genuinely an image-based method. The proposed technique permits animators easily obtain the illusion of lighting in 2D animation that: does not require 3D input; avoids scene transformation to vectorial space; and automatically enhances depth and position perception.

This paper is organized as follows. Section 2 reviews the previous works. Section 3 presents a pipeline to process 2D images as a preparation for shading effects. Section 4 describes how rendering techniques can be adapted to use 2D position and approximate normals to illuminate a drawing. Section 5 describes how to simulate an environment reflection in a geometric 2D object. Section 6 concludes with final remarks and a discussion of ongoing work.

Previous work

Most of the prior work in this area relies on reconstructed geometry. Igarashi et al. [START_REF] Igarashi | Teddy: a sketching interface for 3D freeform design[END_REF] create a surface from 2D information, providing a gesture-based sketching interface to quickly and easily design freeform models. Correa et al. [START_REF] Corrêa | Texture Mapping for Cel Animation[END_REF] take a geometry model and deform it to match a hand-drawn figure. Fiore & Reeth [START_REF] Fiore | Employing Approximate 3D Models to Enrich Traditional Computer Assisted Animation[END_REF] generates approximate 3D models in order to help animators keep frame-to-frame coherence. Pretovic et al. [START_REF] Petrovic | Shadows for cel animation[END_REF] presents a scheme for "inflating" a 3D figure based on hand-drawn art to create shadows for cel animation.

The present research was inspired on the seminal work by Scott Johnston [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF] that uses image-based techniques. He also estimates normal vectors and uses sparse interpolation to approximate them over the remaining image to illuminate 2D drawings. However, the present work has major conceptual and technical differences. The main drawbacks of the Johnston's method are the need of multi-channel images and the need of scene transformation to vectorial space. In our model, we work directly from the 2D image and we avoid transformations to vectorial space completely. This is the reason why we claim that our method is the only one in the literature that is genuinely an image-based method.

Guessing 3D surfaces from 2D images

This section describes a pipeline to process 2D images in order to infer a 3D surface from drawings outlines. Our pipeline is suitable to cel-based animation and is intended to minimize the amount of user intervention. Figure 1 depicts pipeline main stages.

Digitization

In the traditional animation process, animators begin by drawing sequences of animation on a paper with pencils, one picture or "frame" at a time. The pipeline's input data are images made by the traditional cel animation production process. Those images are scanned from cel by a digital process. It is assumed that original drawings contain homogeneous, non-textured lines drawn onto a white background having black outlines. These requirements make the images cleaning process easier because, in the final step, it will also have black line drawings in a white background.

After the scanning process, each cel has registration holes. Those small holes allow the cel to be placed on pegs to ensure each cel aligns with the one before it. If the cells are not aligned in such a manner, the animation, when played at full speed, will look "jittery."

Skeletonization

In images consisting mainly of lines, it is the position and orientation of the lines and their relationship to one another that conveys information. Extra pixels are unwanted information that complicate the analysis, and removing them is desirable [START_REF] Parker | Pratical Computer Vision using C[END_REF]. To facilitate the extraction of image features, a thinning algorithm erodes, therefore reducing objects without changing their topology. For example, consider the bear images in Figure 2, both of them have the shape of the same cute bear, but the image on the right has the extra pixels removed and can now be further analysed for shape.

Curve extraction

This stage implements contour decoding. An arbitrary curve is composed from a sequence of unitary vectors with a limited set of possible directions. Once a skeleton has been extracted, the image curves can be well represented by storing only the direction to the next pixel for each of the connected pixels in the boundaries. A chain code method using an 8-connected grids models its layout and direction.

Determining Normals

Once the image curves were extracted, a 2D normal vector can be easily derived at any point in that representation, by taking the perpendicular direction to the curve orientation. The normals can be created in any space, but it is convenient to transform them to a screen space (X, Y ) with depth Z. For an ortographic projection, the z-component of the normals along the edge of a curve surface must be zero. This is done to keep the normals perpendicular to the eye vector.

A point in the curve may have two normal vectors that share the same direction, but have opposite orientations. The direction of this vector determines the orientation of the surface. For example, if the normals of a circle point outwards its trace, interpolating those vectors across the circle interior area generates a field of normal vectors that determines a convex surface. On the other hand, if the inner orientation is chosen, the interpolation determines a concave surface. Our method guesses, for each segment, which is the best orientation by inspecting its dominant curvature, and by choosing the one that points outwards of the curve as shown in Figure 3.

Smoothing

The chain code used models a limited range of vectors as there are just eight possible directions for neighbors. A smoothing stage low-pass filters the normal fields produced in the 3.4 section as follows: for each point, a normal vector is calculated by adding its previous and next neighbor's vectors. Figure 4 depicts a normal vector field calculated over the bear's outline image.

Labeling

Labeling, a common technique in computer vision, groups the pixels of an image into nonoverlaping regions based on some connectivity criteria [START_REF] Davies | Machine Vision: Theory, Algorithms and Practicalities[END_REF]. In this paper, we present a labeling technique that partitions an image through a flood fill algorithm; in order to indicate which region of the image the interpolation must be applied on.

In outline images, each region is made up of pixels inside a boundary curve. Given a point in an image, a flood fill algorithm recursively colors all pixels which are adjacent to this point and have similar attributes. When applied to binary images, the algorithm finishes when it finds all pixels internal to a region's boundary. If we scan a binary image running this algorithm to non-colored pixels, we are able to extract all the image regions. As colored pixels are not considered in the scanning process, this approach has an efficient O(n) cost, where n is the number of pixels. The Figure 5 depicts an image labeling process where each area is colored with a different color.

Interpolation

Using estimated normals, an interpolation stage employs sparse interpolation to approximate normals over the remaining image. This phase is based on Johnston's work [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF] which approximates normals vectors in multi-channel images. Rather than solving the complex problem of interpolating normals as multidimensional unit-length vectors, N x and N y are interpolated as independent components, and N z is recomputed to maintain unit length. Thus, known pixel values remain fixed and unknown values are relaxed across the field using dampened springs between neighboring pixels. Given a field P to be interpolated, and a velocity field V initialized to zero, each iteration is computed by: V'i,j = d.Vi,j + K.(Pi-1,j + Pi+1,j + Pi,j-1 + Pi,j+1 + 4P) P'i,j = Pi,j + V'i,j

Johnston [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF] shows that optimal values for the dampening and spring constant vary, but d = 0.97 and k = 0.4375 minimizes the convergence time for a circle example. Iterations are performed until the mean-squared velocity per pixel reaches an acceptable error tolerance. To adjust region's puffiness, he suggests to replace a normal with the normal of a sphere that has been scaled in z. To map a field of normals to a sphere scaled in z by S, a pixel operation is applied, replacing (N x , N y , N z ) with: (S.N x , S.N y , N z ) (S.N x , S.N y , N z )

(2)

Figure 6 depicts a normal field image in RGB space obtained from the outline drawing depicted in Figure 2 left. The normal field approximates a spherical shape for the bear image and provides it with a 3D appearance. Using imagebased algorithms, it is possible to approximate the surface normals and directly avoid image transformation to 3D geometry. Our method is suitable for prototyping image-based shading techniques. For maximum control, standard 3D rendering works best.

Shading techniques

Shading is fundamental in the process of conveying a three-dimensional structure for an object in a twodimensional image [START_REF] Gooch | Non-Photorealistic Animation Rendering[END_REF]. Researchers in non-photorealistic rendering (NPR) have investigated a variety of techniques to simulate the nonlinear shadings found in art works. Using 2D positions and approximated normals, most rendering techniques can be adapted to illuminate a drawing [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF]. In this section, we demonstrate how shading techniques can be used to infuse hand-drawn artwork with not only photorealistic but also non-photorealistic vitality and beauty.

Cartoon shading

Cartoon characters are intentionally "two-dimensional". Animators deliberately reduce the amount of visual detail in their drawing in order to draw the audience into the story and to add humor and emotional appeal [START_REF] Lake | Stylized Rendering techniques for scalable real-time 3D animation[END_REF]. L. Willian [START_REF] Williams | Shading in two dimensions[END_REF] shows that one critical simplification which made traditional cel animation possible and practical is that objects and characters are represented by line drawings filled with areas of solid color. Details have to be used sparingly and consistently in order to generate hundred of thousand of drawings for an animation. In a cartoon shading, this economy leads the artist to shade part of a material that is in the shadow with a color that is a darkened version of the main material color. Lake et al. [START_REF] Lake | Stylized Rendering techniques for scalable real-time 3D animation[END_REF] developed a cartoon shading algorithm similar to the cel animator's process of painting an already inked cel. Instead of calculating the color per vertex, Lake et al. generates a texture map of colors. In most cases, the number of colors is two: one for the illuminated color and one for the shadowed color. The boundary between lit and shadowed colors on the model depends on the cosine of the angle between the light and normal vectors. Disadvantage is the need to create 3D input models.

If the animator informs the light position, we demonstrate that using an approximated normal vector field, 3D approaches for cartoon shading techniques can be applied on 2D images. The Figure 7 depicts the result of applying Lake's et al. approach to a 2D character where its surface normal was obtained through our preprocessing 2D images pipeline.

Phong shading

The Phong illumination model [START_REF] Phong | Illumination for computer-generated pictures[END_REF] is probably the most applied model in computer graphics nowadays. In this model, the light in any point is composed by three components: ambient, diffuse and specular. Those components are additive and give the color and illumination final appearance of a scene.

The primary components typically used to illuminate a point on a surface are its position and surface normal. With hand-made drawings, the surface normal is unknown, and the position lacks depth. However, we demonstrate that a Phong shading may be applied in 2D images to create a realistic style for animation films if approximated normal vectors are used. This model may give a strong tridimensional appeal by approximating the incident illumination on curved surfaces as showed in the Figure 8

Sphere mapping

In recent years, the graphics community has made due progress in 3D animation which has given to the animator a variety of facilities to apply an image over a surface. This feature improves the production process and the final appearance of a drawing. Animators often use a texture to simulate environment reflection in a geometric object. In computer graphics, a sphere mapping technique enables any arbitrary pattern in the two-dimensional space to be reflected on a spherical surface. This technique approximates the effect of the environment reflecting on the surface of a highly reflective object.

The advantage of using a sphere mapping technique instead of a texture mapping in animated films is that the texture changes according to view point changes. In the case of texture mapping, the (u, v) coordinates are a function of the object only. In the case of sphere mapping, the (u, v) coordinates are a function of the objects position, surface normal and its orientation with respect to the eye.

There are several algorithms to apply sphere mapping techniques to a surface like [START_REF] Velho | Sistemas Gráficos 3D. Instituto[END_REF]. Once again, disadvantages are the need of using 3D input models. However, we demonstrate that a sphere mapping technique can be applied to 2D images using approximated normal surfaces. Figure 9 depicts the result a circus environment reflexion into a circle where the surface normal was approximated through the pipleline described in this work. Composing the result imagem to the animation scene we get a realistic effect of a reflecting material. Using our technique, tradidional animators can easily simulate environment reflecting into the surface of reflecting objects.

To enhance properties of a reflecting material, such as chrome, illumination model with diffuse and specular components must be applied to each image pixel. The Figure 10 illustrates a circus evironment reflexion into a circle that simulates chrome material and reflexion properties.

Conclusions

Although the flat look of the 2D animations could be an intention of the artist, cel animators experience great difficulties in generating hundreds of thousands drawings with 3D appearance. Although computer assistance for traditional animation is gaining a lot of attention in recent years, the 2D shading problem is far from being completely solved. The goal is still to require minimal user intervention and do not limit the animator's creative process. Imagebased methods seem to be a good road to achieve this goal. The present paper presents a method that is the only one in the literature that is genuinely an image-based method, because it works directly from the 2D image and requires no transformation to vectorial space. Animators do not like vectorization because drawing lines are usually modified during this process. The technique proposed by Johnston [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF] has some drawbacks, because the animator needs a support system to build the multi-channels; moreover, the identification of each region of the image is made by the animator.

The following comparisons can also be done with Johnston's work [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF]: the way our method stores each curve (chain code) makes easy the task of finding normal vectors at each point (there is no need for using gradients as in [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF]); the animator needs only to select the curve and set the orientation parameter in order to define the orientation of the normal vectors (there is no need for "light over dark" lines along each curve as in [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF]); the segmentation process (labeling) is automatic, apart from the selection of the final color of each region (this process is not automatic in [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF]). There is also a difference towards the objectives of the system: our method is for traditional cartoon animation, while Johnston [START_REF] Johnston | Lumo: Illumination for cel animation[END_REF] envisages the blending of 2D animation and live action as in "Who Framed Roger Rabbit" (1998) [START_REF] Solomon | Enchanted Drawings: the History of Animation[END_REF].

Further work will be carried out in building a framework to visual creation and edition of computer assisted animations. Through this framework, the animator will work in interactive high level programming environment which provides a fast adapted concept of: (i) shade engines (e.g. Perlin's Pixel Stream Editor [START_REF] Perlin | Image analogies[END_REF]), (ii) shading languages (e.g. Cook's shade Trees [START_REF] Robert | Illumination for computer-generated pictures[END_REF] and Pixar Renderman [START_REF]Pixar's RenderMan Products[END_REF]), (iii) real-time previews using normal look-up tables, (iv) realtime shadow effects by changing light position, (v) new styles application by learning analogies (e.g. Aaron Hertzmann et al. [START_REF] Hertzmann | Image analogies[END_REF] Image Analogies) and (vi) creation of a styles library.

Figure 1 .

 1 Figure 1. Pipeline main stages.

Figure 2 .

 2 Figure 2. The skeletonization of the figure on left removes extra pixels and produces a simper image (right).

Figure 3 .

 3 Figure 3. Derived normal vectors.

Figure 4 .

 4 Figure 4. Normalized smoothed normal vectors in RGB space.

Figure 5 .

 5 Figure 5. Image labeling through a flood fill algorithm.

Figure 6 .

 6 Figure 6. A normal image in RGB space.

Figure 7 .

 7 Figure 7. Lake's cartoon shading approach applied to a 2D animation frame.

Figure 8 .

 8 Figure 8. Images illuminated by a Phong shading. On the right image, silhouette and outline details are added.

  . If silhouette and outline details are added, the result looses the artificial appearance often found in computer generated imagery (Figure 8 right).

Figure 9 .

 9 Figure 9. A sphere mapping technique applied to a 2D circle image(left). The image composed into an animation scene(right).

Figure 10 .

 10 Figure 10. A circle simulating a chrome material and reflexion properties.

Acknowledgments. The authors thank César Coelho for all lovely bear outlines and his support as a renowned traditional animator. We also would like to thank Ives Macedo Júnior and Marcelo Vieira for many helpful discussions and comments regarding the present work. This work was developed at ICAD/VisionLab (PUC-Rio) -sponsored by CNPq and FINEP -and VISGRAF (IMPA) -sponsored by CNPq, FAPERJ, FINEP, and IBM Brasil. The first author is partially supported by scholarships from PUC-Rio and CAPES. The second author's research work is under research contracts CNPq Grant PQ No. 305982/2003-6, SEPIN-CNPQ-FINEP No. 01.02.0230.00 (Ref. 2425/02) and FINEP No. 01.04.0945.00 (Ref. 3110/04).


Keywords: CR Categories: I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism-Real-Time Shadowing; stencil shadows, shadow volume, real-time rendering, graphics hardware

We present a novel algorithm for the rendering of hard shadows cast by a point light source. The well-known Z-pass method for rasterizing shadow volumes is not always correct. Our algorithm, which we call ZP+, elegantly corrects Z-pass defects. ZP+ takes advantage of triangle strips and the fast culling capabilities of graphics hardware not available to conventional robust methods like Z-fail. While Zfail can be up to 80% slower than Z-pass, our new method ZP+ is typically less than 10% slower than Z-pass. Finally, we compare the three methods. When a scene is geometry-bound, ZP+ is always faster than Z-fail. We also explain why, in some situations, Z-pass (hence ZP+) is surprisingly slower than Z-fail on more recent graphics hardware.

The Z-pass shadow volume method (left) pre-renders a scene into the z-buffer, and then renders shadow volumes (bold), incrementing (decrementing) the stencil buffer when front (back) facing fragments pass the z-test, but fails when shadow volume geometry is clipped by the near plane. The Z-fail method instead counts shadow volume fragments that fail the depth test, using far plane caps to robustly fix stencil sums, but requires all shadow volumes to be rendered including completely occluded shadow volumes. This paper's ZP+ algorithm initializes the stencil buffer by first rendering from the light source to correctly set the stencil buffer to the proper values ordinarily clipped by Z-pass, and thus processes shadow volumes with the depth-culled speed of Z-pass but with the robustness of Z-fail.

Introduction

Shadows are an important visual cue for the perception of depth in the 2-D depiction of 3-D scenes, and for some scenes, shadows often provide the only cue of the spatial relationship of disjoint objects. The quest to make videogames, virtual environments and other interactive graphics applications more photorealistic has included a recent surge in real-time shadow generation [START_REF] Kilgard | Robust stencil shadow volumes[END_REF][START_REF] Everitt | Practical and robust stenciled shadow volumes for hardware-accelerated rendering[END_REF]Aila and Akenine-Möller 2004;[START_REF] Chan | An efficient hybrid shadow rendering algorithm[END_REF][START_REF] Lloyd | CC shadow volumes[END_REF][START_REF] Aldridge | Robust, geometry-independent shadow volumes[END_REF][START_REF] Hasenfratz | A survey of real-time soft shadows algorithms[END_REF]].

The current state-of-the-art in real-time shadowing relies on the efficient processing of shadow volumes, and is used by the latest video game engines including the one used for iD Software's Doom 3. This paper describes a new algorithm called ZP+ that accelerates the shadow volume processing used in Doom 3 and other interactive 3-D games and applications.

Shadow volumes are object-space tesselations of the boundaries of the regions of space occluded from the light source [START_REF] Crow | Shadow algorithms for computer graphics[END_REF]]. The alternative to shadow volumes is shadow mapping, which computes shadows by transforming a visible fragment's positions into the light's viewing coordinate system and compares it against a depth map precomputed in this coordinate system. Stenciled shadow volumes are popular and widely adopted because they provide crisp geometric shadow boundaries whereas shadow mapping suffers from the limited resolution of its image-based approach.

The Z-pass method is an early approach to implementing stenciled shadow volumes [START_REF] Heidmann | Real shadows, real time[END_REF]] demonstrated here in Figure 1 (left). The Z-pass method first initializes the stencil buffer to zero and the z-buffer with the depth values of visible objects in the scene, and then rasterizes the sides of the shadow volumes. For each visible shadow volume fragment (rasterized pixel that passes the depth-test), the method increments the corresponding stencil buffer pixel if the fragment is front-facing and decrements if the fragment is back-facing. A version of the Jordan curve theorem leads to the conclusion that shadows occur at pixels with non-zero stencil buffer entries.

The Z-pass method fails when the shadow volume intersects the near clipping plane (the terminology we use is presented in Fig- ure 2). In the example in Figure 1 (left), the topmost point is incorrectly classified as shadowed because the circle's lower shadow volume boundary was clipped by the near clipping plane. Methods that cap the clipped shadow volume with additional geometry [START_REF] Diefenbach | Multi-pass Pipeline Rendering: Interaction and Realism through Hardware Provisions[END_REF][START_REF] Batagelo | Real-time shadow generation using bsp trees and stencil buffers[END_REF][START_REF] Kilgard | Robust stencil shadow volumes[END_REF]] are computationally expensive and suffer from robustness problems that lead to glaring pixel-wide shadow cracks.

This near-plane clipping problem of the Z-pass method led others, including [START_REF] Carmack | E-mail to private list[END_REF], to devise the Z-fail method, which processes shadow volume fragments that fail (instead of pass) the depth test, as demonstrated in Figure 1 (middle). This approach moves the problem from the near clipping plane to the far clipping plane which can be handled robustly by extending it to homogeneous infinity [START_REF] Everitt | Practical and robust stenciled shadow volumes for hardware-accelerated rendering[END_REF]. This robustness comes at the cost of speed, as the Z-fail method must now, during shadow volume rasterization, also rasterize the front faces of the scene geometry at their original location, and the back faces of scene geometry projected onto the far plane. Furthermore, Z-fail cannot capitalize on early z-culling which Z-pass uses to avoid the processing of shadow volume fragments occluded from view by scene geometry.

This paper presents a new algorithm we call ZP+ (for Z-pass plus) that provides the robust correctness of Z-fail at a speed more comparable to the Z-pass approach. The ZP+ algorithm, demonstrated in Figure 1 (right), constructs in a separate pass a sheared frustum extending from the light source to the original view's near plane. Since the far clipping plane of this sheared light frustum aligns with the near plane of the view frustum, it contains only the scene geometry responsible for generating the shadow volume clipped by the original near plane. Rasterizing this scene geometry projects its fragments onto the original near clipping plane where it can be used to properly and robustly initialize the stencil buffer.

Section 2 compares the ZP+ approach to its predecessors, establishing its novelty and utility. Section 3 describes the ZP+ algorithm in more general configurations beyond the simple demonstration in Figure 1 (right), concluding with a proposal for a new OpenGL extension to aid its efficiency. Section 4 describes why ZP+ is faster than Z-fail, whereas Section 5 analyzes the robustness of ZP+, focusing on the discrepancy between rasterization and clipping that can lead to cracks and recommendations on how to avoid them. We note one case of numerical inaccuracy that, while exceedingly rare, causes artifacts that may warrant a switch to Z-fail. Section 6 exhibits the quality and speed of its shadows with demonstrations and performance charts on a variety of recent graphics processors.

Previous Work

Z-pass Corrections

The introduction demonstrated that the original Z-pass algorithm [START_REF] Heidmann | Real shadows, real time[END_REF]] leads to errors when the shadow volumes intersect the near rectangle (the near clipping plane of the view frustum). The problem is initializing the stencil buffer: some portions may be lit, and some may be shadowed. It is not as simple as knowing whether or not the viewer is shadowed; the eye's position may be lit even though the entire near plane is shadowed. Figure 3a illustrates such a configuration.

To compensate, some have proposed the generation of additional geometry at the near plane to cap the shadow volume. [START_REF] Batagelo | Real-time shadow generation using bsp trees and stencil buffers[END_REF] suggest computing the intersection of every polygon's shadow geometry with the near plane, creating additional geometry to cap the portions of the near plane in shadow. However, computing the intersection of shadow volumes with the near plane was expensive and prone to numerical errors that exhibit themselves as cracks in the shadow. [START_REF] Diefenbach | Multi-pass Pipeline Rendering: Interaction and Realism through Hardware Provisions[END_REF] caps the near rectangle by rasterizing additional geometry enclosing the space between the light source and occluder's silhouette. [START_REF] Everitt | Practical and robust stenciled shadow volumes for hardware-accelerated rendering[END_REF] note Diefenbach's approach is not robust in every configuration and provide three counter-examples where the cap would not be rendered due to combined clipping by both the near and far clip planes.

Kilgard's solution [START_REF] Kilgard | Robust stencil shadow volumes[END_REF]] explicitly mirrors scene geometry close to the near plane. An additional pass renders a cap by projecting an occluder through the light source. This projection pushes occluding geometry up against a near ledge, a plane very close to the near plane, yet not so near as to clip this extra geometry. Since this projected geometry does not share vertices with shadow geometry, this approach too suffered from cracking problems.

None of these methods prove satisfying due to the complicated geometric computations required of the CPU. Moreover, critics note that any sort of method requiring computational geometry is inherently fragile, due to the imprecise nature of computer arithmetic. These problems tend to manifest themselves as unsightly cracking artifacts, which are unacceptable to the demanding expectations of real-time graphics enthusiasts. This suggests that any sort of feasible solution must rely on simple rasterization-based operations available to graphics hardware.

Z-fail

In light of the difficulties inherent in creating a truly robust Z-pass algorithm, [START_REF] Carmack | E-mail to private list[END_REF] discovered Z-fail. This algorithm, symmetric and equivalent to Z-pass, removes the problem at the near plane and pushes it to its far plane counterpart. The idea is that just as a pixel's shadow status may be determined by counting the number and orientation of shadow faces in front of it, one may compute the identical solution by inspecting the shadow faces behind. In this way, Z-fail sidesteps Z-pass's near rectangle problem, since shadow geometry between the eye and a pixel are irrelevant. [START_REF] Bilodeau | Real time shadows[END_REF] developed earlier a similar idea now called reversed Z-pass. Instead of counting shadow volume fragments that fail the depth test, their method reversed the depth test and counted fragments that passed this reversed test. While they may appear similar, Z-fail outperforms reversed Z-pass on modern GPUs that terminate subsequent fragment processing operations once the z-test has failed.

Yet, we are left with the problem of shadow volume clipping resulting in incorrect stencil counts. As Figure 2 (right) illustrates, we can close a shadow volume by adding its light cap and dark cap. The light cap is simply composed of scene object polygons that face the light, whereas the dark cap is composed of the object's back-facing polygons (w.r.t. the light) whose vertices have been projected to the end of the shadow volume. The problem now lies at the far plane. If the dark cap is clipped, inner portions of the shadow volume will be exposed, producing incorrect stencil values. [START_REF] Everitt | Practical and robust stenciled shadow volumes for hardware-accelerated rendering[END_REF] solved this problem by extending the far clipping plane and the projection of the dark cap along the shadow volume to homogeneous infinity. This Z-fail method, while robust, incurs the added expense of rendering the light and dark cap geometry which must be processed separately since the dark cap is translated from its original position. This separation according to polygon orientation disables any advantage a meshed data structure (e.g. a triangle strip) might provide. Furthermore, since stencil counts are counted from the pixel's depth backward, shadow volumes that would normally be occluded by the existing depth buffer must be rendered, which may disable some acceleration that early z-culling might provide when rendering shadow volumes.

Shadow Mapping

Shadow maps were introduced by [START_REF] Williams | Casting curved shadows on curved surfaces[END_REF] as a simple, general, and efficient technique for generating shadows. They are now natively supported in graphics hardware. However, since it is an image-based technique, shadow mapping exhibits aliasing due to quantization and perspective projection. Recent work addresses these problems [START_REF] Stamminger | Perspective shadow maps[END_REF][START_REF] Wimmer | Light space perspective shadow maps[END_REF][START_REF] Martin | Anti-aliasing and continuity with trapezoidal shadow maps[END_REF]. In particular, [START_REF] Chong | A lixel for every pixel[END_REF] describe a technique for shadow maps with perfect sampling for planes of interest. Our contribution, ZP+, uses a similar approach in a different context. Our ZP+ method effectively constructs a shadow map to initialize the stencil plane with a robust cap of the Z-pass shadow volumes. However, we do not store the nearest depth value, but instead increment the stencil buffer for each front-facing fragment. We still use shadow volumes to compute the precise geometry of shadow boundaries, and use a "shadow map" to repair the topology of clipped shadow volumes. As such, we do not suffer artifacts due to the finite image resolution of the shadow map. Figure 5 discusses the issue of rectifying the rules of polygon clipping with the stenciled rasterization of a shadow mask to construct a watertight seal that avoids shadow cracks.

Shadow Volumes Optimization

Recent research aims to enhance the shadow volumes algorithm. In CC Shadow Volumes, [START_REF] Lloyd | CC shadow volumes[END_REF] describe a method to reduce fill rate requirements by culling unnecessary occluders and clamping irrelevant shadow geometry. Aila and Akenine-Möller [2004] also reduce fill by using a hierarchical method that only performs shadow volume rasterization at the boundary of the shadow. Similarly, [START_REF] Chan | An efficient hybrid shadow rendering algorithm[END_REF] reduce fill by using a shadow map to identify pixels that lie near shadow discontinuities. Shadow volumes are then rasterized only for these pixels to produce accurate shadow boundaries. [START_REF] Aldridge | Robust, geometry-independent shadow volumes[END_REF] describe a robust method to produce correct shadow volumes for non-manifold geometry. Our contribution corrects the core of the shadow volumes algorithm, and is complementary to all these methods.

ZP+

As the previous section described in detail, the Z-pass approach processes shadow volumes efficiently but incorrectly when they intersect the near clipping plane, and methods designed to cap the clipped shadow volumes have proved less than robust. The Z-fail approach can be made robust but only after adding the expense of processing cap geometry and sacrificing the acceleration of early depth culling of occluded shadow volumes. This section describes the main contribution of this paper, the ZP+ algorithm that corrects the near-clipping errors introducted by Z-pass at the expense of a single pass rasterization of the occluder into the stencil buffer. We restrict our description of ZP+ to a single light-occluder pair interaction, as details on implementing a complete stencil shadowing system can be found elsewhere [START_REF] Mcguire | Fast, practical and robust shadows[END_REF]].

The added cost of Z-fail motivates our search for a simpler method that produces equivalent results. Inspection of Figure 1 (right) reveals that Z-pass's problem area is the pyramidshaped volume between the light source and the camera's near plane. Any occluder lying within this region casts a shadow volume that intersects the near rectangle and causes Z-pass to malfunction.

The projection of the occluder from the light source onto the camera's near plane closes the gap created when the shadow volume is clipped. Previous methods which attempt to construct projected cap geometry [START_REF] Diefenbach | Multi-pass Pipeline Rendering: Interaction and Realism through Hardware Provisions[END_REF][START_REF] Batagelo | Real-time shadow generation using bsp trees and stencil buffers[END_REF][START_REF] Kilgard | Robust stencil shadow volumes[END_REF]] are computationally expensive and experience numerical problems when rendering because of the proximity of the cap geometry to the near clipping plane.

Whereas others project the light cap geometry onto the near plane to fix a clipped shadow volume, the ZP+ approach rasterizes the light cap and uses the resulting fragments to initialize the stencil buffer, illustrated in Fig. 3b according to the following algorithm. A perspective view frustum is positioned at the light source and sheared so its far rectangle aligns with the camera's near rectangle. The rasterization of any light cap geometry that falls within this sheared light frustum generates the fragments corresponding to a cap of the portion of the shadow volumes clipped by the camera's near plane. We then use these fragments to initialize the stencil buffer to the values necessary to correct Z-pass.

This alignment provides an identification between every point in the camera's near-rectangle with a line segment connecting that point to the light. Thus, this skewed perspective allows us to initialize the stencil values for each one of these points simply by rendering light-front-facing polygons from the light's point of view.

Placing the light frustum at the light's position amounts to leftmultipling a translation matrix to the camera's modelview matrix. If necessary, an antiparallel orientation results from a 180 • rotation matrix about the frustum's y-axis. The light frustum is then sized using the values illustrated in Figure 3c.

When rasterizing the polygons inside the light frustum, we instruct the graphics library to increment stencil fragments and enable the culling of back-faces. Once the rasterization is complete, each stencil pixel contains precisely the number of entrances into shadow for the line segment starting at the light and ending at that pixel's 3-D position on the near-rectangle. We then proceed with the usual Z-pass method.

Light Frustum Setup

The only addition to the standard Z-pass method is the near-cap rasterization in the stencil buffer. We describe how to setup the OpenGL modelview and projection matrices for the near-cap rasterization.

The modelview matrix M l is seen as a frame with origin at the light's position. This "light-frame" is setup so as to have the same vertical vector (Y) as the camera-frame, and a view vector (-Z) parallel to the camera view vector, and oriented towards the camera's near-plane. Thus, the transformation from the camera-modelview to the light-modelview involves a translation and possibly a rotation of 180 degrees around the up vector if the camera and the light lie on opposite sides of the camera's near-plane.

The projection matrix P l is an off-centered perspective transformation. It can be setup using a call to glFrustum. To minimize numerical inaccuracies, we set it up directly as:

P l =      2αl f ar c width 0 -2∆x c width 0 0 2l f ar c height -2∆y c height 0 0 0 lnear +l f ar lnear -l f ar 2lnear l f ar lnear -l f ar 0 0 -1 0    
where α = 1 if the light and the camera are on the same side of the camera's near-plane (otherwise α = -1), c width (resp. c height ) is the horizontal (resp. vertical) dimension of the camera's near rectangle, and ∆ = l -c, in camera space, i.e., the position of the light l in camera space. The matrix above is derived directly from the matrix given in the OpenGL reference book and Figure 3d. We now send the occluder geometry to the graphics pipeline to effectively rasterize the near-cap. Since we want to count, for each pixel of the stencil buffer, the number of entrances into the shadow volume, we set the OpenGL states so as to (1) cull back faces (resp. front faces) if α = 1 (resp. α = -1). (2) increment the stencil buffer value for each fragment. (3) disable writing to the color and depth buffers. (4) disable depth testing.

The rest of the procedure follows exactly the Z-pass method.

Setting the Light's Near Plane

When rasterizing the near-cap, only the part of the occluder inside the light-frustum gets rasterized onto the stencil buffer. Let On the full image, one can see 8 inverted pixels. Middle. View from above. The white rectangle is the camera near-rectangle, yellow is the light-frustum, blue is the camera frustum. The shadow receiver is a plane in front of the camera (not visible). Right.

Artifact-free shadow.

us call the light-pyramid the pyramid formed by the light and its near-rectangle. If a part of the occluder lies in the light-pyramid, then it will not be rasterized onto the stencil buffer because it will be clipped by the light's near plane. Therefore, it is crucial that the light-pyramid be empty. If the light lies outside the occluder (which is assumed to be the case), it is always possible to find a light's nearplane distance lnear for the light-frustum so that the light-pyramid is empty. However lnear should be as large as possible so as to avoid precision loss. We give a simple procedure to calculate lnear.

If we know d, the distance from the light to the occluder, and dmax, the farthest distance from the light to its far-rectangle (the camera's near-rectangle), then lnear = l f ar d/dmax.

Proposal for an OpenGL Extension

Recent NVIDIA hardware offers an OpenGL extension called NV depth clamp that -simply speaking -disables clipping due to the near and far planes and instead clamps the depth of the fragments to the [near, far] range. This extension would be useful to make sure we do not clip the part of the occluder in the lightpyramid. However, activating this extension would also disable clipping by the light's far-plane, which we clearly do not want. We believe that a slight modification to this extension to allow clamping on one side (e.g., the near-plane) and clipping on the other side (e.g., the far-plane) would preclude the computation of lnear, and ease the implementation of ZP+.

Discussion

Why is ZP+ more efficient than Z-fail? First, we eliminate the need for the dark cap at infinity. Z-fail requires the occluder to be rendered twice, to increment and decrement the stencil for both the light-and dark-caps. ZP+ does not need to rasterize the dark cap, since a Z-pass-style stencil test ensures the far plane never clips relevant shadow geometry.

Second, Z-fail may not take advantage of "batched geometry" such as triangle strips, because they prevent the classification of a vertex as belonging to the light-cap or the dark-cap. ZP+ needs no such classification, and may enjoy the performance advantages of batched geometry.

Third, the proportion of capping geometry that is culled by Zpass is much higher, since the size of the light frustum is much smaller than the camera frustum used by Z-fail. Since Z-fail renders capping geometry in the camera's frame, cap faces which do not project on the near plane must be culled manually. Conversely, since ZP+ renders the cap in the light's frame, it may take advantage of the fast automatic culling capabilities of graphics hardware.

And fourth, from a fragment processing point of view, we believe that Z-fail may not take advantage of the depth-test optimizations featured in graphics hardware (early depth culling), if the depth-test is tuned to quickly reject fragments that fail the depth-test, instead of quickly letting them through. In that regard, ZP+, as Z-pass, are "depth-test friendly". We validate these predictions in Section 6.

ZP+ is compatible with all previous work on optimizing stencil shadow volume algorithms: hybrid shadows [START_REF] Chan | An efficient hybrid shadow rendering algorithm[END_REF], hierarchical shadow volumes [Aila and Akenine-Möller 2004], CC-shadow volumes [START_REF] Lloyd | CC shadow volumes[END_REF], and other various optimizations [START_REF] Mcguire | Fast, practical and robust shadows[END_REF]].

Avoiding Cracks

The implementation described above leads to visual artifacts as illustrated in Figure 4: when the camera's near-rectangle lies both in light and shadow, one can observe a few (less than 10 in practice) sparse pixels that are lit while they should be dark or vice versa. These artifacts may or may not be a concern depending on the application: we happily tested ZP+ for a few hours before discovering the problem. A closer observation reveals that these wrong pixels lie on the boundary of the near-cap, along the edges where the sides and the near-cap meet on the near-plane (see the dark spot in Figure 3a). The screen-space coordinates of these edges are computed in two different ways: when rendering the near-cap, they are the projection of some silhouette edges with the special modelview M l and projection P l matrices. When rendering the sides, they are the coordinates of some clipped sides. Because of non exact arithmetic precision, the results of the two transformations differ slightly and the rasterizations of these edges are no longer pixel-wise identical. Figure 3d illustrates this discrepancy.

In some applications, it is desirable to eliminate these artifacts. We present a possible way to do so, which we have successfully implemented. The central idea to correct these artifacts is twofold. First, we leave the near-cap rasterization as is. Second, we manually clip shadow volume quads on the camera's near-plane. If a quad vertex A is found to be clipped, we replace its screen position by the one it would have as transformed with matrices M l and P l , and clamp its depth value to lie on the near-plane. We call this replacement vertex A's near-cap counterpart. We implement this in a vertex program.

Let us examine an infinite quad Q intersecting the near-plane (Figure 5). Four cases can be distinguished:

(A): The near-plane does not intersect Q. There is nothing to do.

(B): The near-plane intersects both I1 and I2 (green line in Fig-

ure 5). The two clipped vertices are replaced with their nearcap counterpart. Thus, the quad's rasterization will perfectly match the corresponding part of the near-cap boundary.

(C): The near-plane intersects one infinite edge I1 or I2 and one finite edge Em or E∞ (cyan and blue lines in Figure 5).

(D):

The near plane intersects Em and E∞ (red line in Figure 5).

In case (C), depending on the orientation of the near-plane, one or three vertices will be clipped. As for case (B) we replace these by their near-cap counterpart. In doing so, alas, we create a triangular "hole" in the quad: Let us examine the case of the cyan near-plane in Figure 5. Assume that it is oriented so that vertex V1 is clipped and replaced by vertex V * 1 while the three other vertices stay in place. Then the modified quad misses the dark-gray triangle in the figure. We fill the hole by rasterizing a new triangle V1V2V * 1 . The implementation details below explain how we efficiently create these corrective triangles using degenerate quads.

Case (D) is more involved. This geometric situation appears when the light-frustum is extremely skewed and flat, because the light is both far from the viewpoint and close to the near-plane. Figure 6 illustrates case (D) artifact. In this case, we cannot simply use the vertices' near-cap counterparts. Furthermore, case (D) conservatively detects the situation where the matrices M l and P l behave very poorly numerically. For these reasons, if case (D) is detected for some occluder, we temporarily switch to the Z-fail method, but for this light/occluder pair only.

V 1 I 1 V 2 V * 1 case (B) case (D) case (C) I 2 Q E ∞ E m case (A)
The cases are explicitly examined during the search for silhouette edges. Our experiments show that, fortunately, case (D) is extremely rare. In a general, free walkthrough in our test scenes, case (D) almost never happened. When modelling specific camera paths to reveal case (D), the transition from ZP+ to Z-fail and vice versa is smooth, with no artifacts. We dicuss the switch to Z-fail in more detail at the end of this section. Case (C) could be the cause of some artifacts, because we cannot perfectly correct the quad at the intersection between the near-plane and E m|∞ . However, in our experiments, we do not notice artifacts due to case (C). Case (B) is the most common (about on par with case (A)), and we have seen that its correction with the near-cap counterparts is exact. To sum up, we have no more wrong pixels.

Vertex Shader Details

Figure 7 presents the vertex program for rendering the sides. The x, y, z input coordinates contain the position of the corresponding silhouette vertex. The w input coordinate is 0, 1, 2 or 4. 0 and 1 carry their standard "homogeneous" meaning: 1 leaves the vertex in place. 0 indicates that the vertex must be extruded infinitely away from the light (lines 6, 7). If the vertex happens to be clipped by the near-plane (line 12), then the vertex (x, y, z, 1) (lines 13, 14) is transformed as in the near-cap rasterization (lines 15, 16) and is projected on the near-plane (line 17). A vertex V with w = 0 or 1 is called a floating vertex and is noted Ṽ .

If w = 2 or 4, the vertex is kept in place (w = 2) or extruded (w = 4) but is not modified if it happens to be clipped (line 11). A vertex with V w = 2 or 4 is called a nailed vertex and is noted V . Nailed vertices are used to create the corrective quads, as we explain now.

In case (C), one need to add a corrective triangle to fill the "hole" left by the modified quad. However we use a corrective quad instead. The reason is twofold. First, this permits to handle symmetric cases automatically (e.g., when the near-plane intersects [I1 and Em] or [I2 and Em], the same corrective quad is used). Second, and perhaps most importantly, we can append these corrective quads to the vertex containing the sides of the shadow volume, thus avoiding the burden of having to treat them in a special vertex array.

Let AD be a silhouette edge yielding a quad Q in case (C). AD is oriented so that the normal of triangle ADlight points away from the shadow volume.

Case (C1) corresponds to the cyan dashed line (the nearplane intersects Em). The corrective quad for case (C1) is {(A, 2); (A, 1); (D, 1); (D, 2)}.

Case (C2) corresponds to the blue dashed line (the nearplane intersects E∞). The corrective quad for case (C2) is {(A, 0); (A, 4); (D, 4); (D, 0)}.

In all cases, two vertices of the corrective quad collapse and the corrective quad becomes a corrective triangle. The bottom of Figure 7 explains the case (C1): The edge Em of quad Q is duplicated so as to create a second (corrective) quad, two of whose endpoints are nailed.

Switching to Z-fail

In the broader context of a full stencil shadowing system, that is, with many lights and many occluders, switching from ZP+ to Zfail for a single light/occluder pair is not possible. Indeed, ZP+ initially renders the scene into the depth buffer, with respect to finitely remote near-and far-planes. After this is done, rasterizing a shadow volume as in the Z-fail method would produce fragment depths incompatible with the values stored in the depth-buffer. Therefore, one has two choices for the "switched" method: if the NV depth clamp is available, the Z-fail method can be used without pushing the far-plane to infinity. Otherwise, one can use the ZF+ approach that we will describe in Section 7. This is guaranteed to give a correct result, because the switch is made upon encounter of case (D), i.e., when the light is close to the near-plane. Unless a silhouette edge is large enough to pass through both the near-and far-planes, this implies that case (D) will not be triggered for that light/occluder pair with the ZF+ approach.

Note that the "switched" method should be used only for those light/occluder pairs for which a case (D) has been detected. For efficiency, one could treat these light/occluder pairs together.

Performance

We implemented the three methods: Z-pass, Z-fail and ZP+. Z-pass does not produce correct shadows in general, but is used as reference for performance comparison. To make their comparison as fair as possible, we have heavily optimized each method:

• Common optimization to all three methods: The shadow volume sides' coordinates are stored in a dynamic vertex buffer (we used the ARB vertex buffer object extension).

The second rasterization of the sides (for decrementing in the stencil buffer) can be executed in a single OpenGL call.

• Z-fail: A version of the occluder's mesh is stored as independent triangles in a vertex array, wherein each entry has the vertex coordinates and the triangle's normal. A vertex program computes whether or not to project the vertices of this mesh to infinity, based on its facingness with respect to the light. This rasterizes the dark-and light-caps. This mesh is rasterized twice: once to increment the stencil buffer and once to decrement it.

• ZP+: A version of the occluder's mesh is stored as a triangle strip in a vertex array, wherein each entry only contains the vertex coordinates. This mesh is rendered only once to rasterize the near-cap. Sides are rasterized together with additional corrective quads, using a special vertex program described in Section 5.

Our test scenes consist of a central object (the occluder, see Figure 8), a surrounding box, and a point light source. The rendering of a frame includes the brute-force computation of silhouette edges, the preliminary pass to fill the depth-buffer, the shadow volume rasterization, and the lighting pass to shade lit pixels.

Comparing the three methods is no trivial matter. The rendering times are dependent on the scene in both its complexity and spatial configuration. They also largely depend on the pixel coverage of Figure 9: Relative timings -the lower the better. Each plot depicts the varying rendering time of ZP+ (green) and Z-fail (red) relative to Z-pass (in %). The X axis is the frame number. For example, a value of 30 at frame 100 means that around frame 100, the average rendering time for each frame is 30% slower than Z-pass. Each line plots the results for one occluder. Each column plots results for one specific camera path: the paths used the first two columns leave the camera entirely inside the shadow, hence Z-pass gives a wrong shadow and can not be used in an application. The Zoom path is a forward zoom where the occluder covers only about 100 pixels at the first frame and occupies the whole screen at the last frame; the shadow begin cast toward the left of the screen. The Various path makes the camera fly around the scene in a random fashion.

the shadow-volume sides. Furthermore, the set of stencil pixels modified during the shadow-volume rasterization is very different between Z-pass and ZP+ (the near-cap is added), and between ZP+ and Z-fail. In particular, the set of stencil pixels modified in ZP+ and the set of pixels modified in Z-fail form a partition of the set of pixels touched when rasterizing the capped shadow-volume. The respective size of these sets is not balanced in general.

The performance measurements below include the correction of the artifacts, which we found incur no significant overhead.

GeForce4 Performance

We first tested ZP+ on a desktop PC (2.4GHz Xeon) with a GeForce4 Ti 4800. Results for these tests are presented in Figures 9 and10.

• As expected, ZP+ is slower than Z-pass.

• ZP+ is faster than Z-fail.

• ZP+ performance is closer to Z-pass than to Z-fail. This gets more salient as the geometric complexity of the occluder increases.

To accommodate for the high variability of the rendering time, we designed several specific camera paths, each of which highlights a different aspect of the methods' behavior. Figure 9 shows the behavior of ZP+ and Z-fail relative to Z-pass. The first two columns of this figure indicate paths that place the camera entirely in shadow, in which case the Z-pass method always computes a wrong shadow and necessitates an alternative method, either Z-fail or ZP+. The "Eye looks away" camera path places the camera facing a wall, where most depth tests fail. This test favors ZP+. The "Eye looks at occluder" path places the camera viewing the occluder, where most depth tests pass. This favors Z-fail, which is illustrated by the curves being closer. In both tests however, using ZP+ is profitable.

Another observation we can make from Figure 9 is that the relative timings for Z-fail increase with the geometric complexity of the occluder, while the relative timings of ZP+ stabilize around 10%. The "flattening" of the curves observed with the pregnant woman occluder is due to the graphics pipeline becoming geometry bound. Compared to Z-fail, ZP+ performs especially well with highly detailed 3D models, as shown in Figure 10 (right).

Section 5 explains why, in rare cases, one cannot use ZP+ and must switch to Z-fail (or the modified Z-fail presented earlier). In all the tests of Figure 9, the switch to Z-fail was never triggered. We setup a special camera path to reveal this switch. The path makes the camera move slowly when the near-plane pass through both the light and the occluder. Relative timings are depicted on Figure 10 (left). As expected, the switch is triggered very seldom.

GeForce FX Performance

We also tested ZP+ on a desktop PC (3.0GHz Xeon) with a GeForce FX 5900 Ultra. Results for these tests are presented in Figure 11. In particular, we enabled the use of the EXT stencil two side extension (not available on GeForce4) so that rendering the sides and the caps is done only once in Z-fail, and rendering the sides is done only once in ZP+

The vertex and fragment processing of the GeForce FX is faster than the GeForce4. Thus, the plots in Figure 11 discriminate Z-fail and ZP+ in an interesting way, which was not apparent with the GeForce4: When the occluder has small geometric complexity, the performance of Z-pass versus Z-fail depends highly on the geometric configuration of the scene (see the plots on the left side of the figure). Although the number of processed vertices is much larger in Z-fail, Z-pass (and thus, ZP+) happens to be slower in some geometric configurations of the scene. We may deduce that when the occluder is simple, the vertex processing time is negligible. Furthermore, the performance of Z-pass / ZP+ varies with the number of fragments that pass the depth test, in the opposite way that Z-fail's does.

As occluder complexity rises, ZP+ always performs better because the main bottleneck comes from the vertex processing stage, and ZP+ takes advantage of triangle strips (see the plots on the right side of Figures 10 and11). The plots in Figure 11 clearly show that ZP+ incurs only a marginal overhead to Z-pass. As a result, we now have two methods to robustly rasterize a shadow volume. Our observations show that for an occluder with small geometric complexity, the cost of shadow volume rasterization depends heavily on the proportion of fragments that pass (Z-pass and ZP+) or fail (Z-fail) the depth test: ZP+ may be slower than Z-fail but this is inherently due to Z-pass being slower than Z-fail in that case. This is a surprising observation which opens new tracks of research: It does not seem trivial to know beforehand what proportion of fragments will pass or fail the depth test for a given shadow volume and scene.

We also performed tests with an ATI Radeon 9700. Our observations were inline with those from the NVIDIA experiments.

Conclusions

We have presented a simple method called ZP+, to correct the defects of the Z-pass method for the rendering of hard shadows. ZP+ only involves the rasterization of the light-occluding mesh with special transformation matrices. While ZP+ is mathematically exact, the discrete nature of computer calculus yields some minor artifacts. We have described both the reasons of these artifacts and an efficient way to remove them. We have seen that ZP+ is generally faster than Z-fail and behaves particularly well with large meshes. We also have described a simple modification to the NV depth clamp OpenGL extension that would simplify some aspects in the implementation of ZP+.

The observations made when testing with a GeForce FX yields the following question: can we efficiently decide whether to use ZP+ or Z-fail if its occluder is simple enough that processing shadow volume fragments outweighs the processing of its vertices?

We believe it is possible to express P l in a different way, so as to avoid numerical inaccuracies which, for now, force us to switch to Z-fail in rare cases.

Finally, we can observe that ZP+ can also be adapted to a Z-fail-like method (that we call ZF+), by capping the far-plane instead of the near-plane (i.e., rasterizing a far-cap). We would like to examine ZF+ and ZP+ in more detail in the search for a heuristic that would tell when to use one or the other.

  Figure1: The Z-pass shadow volume method (left) pre-renders a scene into the z-buffer, and then renders shadow volumes (bold), incrementing (decrementing) the stencil buffer

Figure 2 :Figure 3 :

 23 Figure 2: Some terminology. c is the camera position, l is a point light source. The picture on the right depicts the various shadow volume elements: the light-cap is the set of polygons facing the light. The dark-cap is the set of polygons not facing the light, projected onto the far-plane. The light-and dark-cap are used in the Z-fail method. The near-cap is the intersection of the camera's near-rectangle with the shadow volume. The near-cap is used in the new ZP+ method. The sides are used in all three methods.

  1. Position light frustum at light position. 2. If camera and light are on the same side of camera's near plane, (a) then orient light frustum parallel to camera frustum, (b) else orient light frustum antiparallel to camera frustum. 3. Fit the light frustum's far-rectangle to the camera's nearrectangle. See Figure 3c. 4. Rasterize front facing (w.r.t. the light frustum) scene geometry, accumulating fragment counts into the stencil buffer. 5. Execute standard z-pass shadow computation initialized with current stencil buffer.

Figure 4 :

 4 Figure 4: Left. Pixel artifacts: the closeup reveals 3 lit pixels that should be dark.

Figure 5 :Figure 6 :

 56 Figure 5: The quad Q has two infinite edges, I1 and I2, and two finite edges. One finite edge of Q, Em, is also an edge of the mesh, while the other, E∞, is finite in the angular domain, and lives at infinity. The dashed lines stand for the possible near-plane positions, up to symmetry. two-sided quad shadow artifact in case (D)

Figure 7 :

 7 Figure 7: The vertex program for rendering the sides.

Figure 8 :

 8 Figure 8: The occluders used in our tests. The twisted torus (12000 triangles) is interesting because of its highly complex shadow volume. The head (20222 triangles) and the pregnant woman (83666 triangles) are used to test the increase in geometric data.

Figure 10 :

 10 Figure10: Left. The blue bar indicates frames where the use of Z-fail was detected as needed. One clearly observe the increased rendering times for ZP+ around these frames. Right. Frame rates for the Eye looks away path and the pregnant woman occluder. Z-pass tops at 35fps but give wrong shadows all along this path. ZP+ gives correct shadows and yet can render 50% more frames per second than Z-fail.

Acknowledgments

We are grateful to Mark Kilgard and Eric Chan who took the time to discuss ZP+ with us. Thanks to Sylvain Paris and Xavier Decoret for their comments on early drafts. This research funded in part by the NSF ITR CCR-0219594 and a CNRS-UIUC partnership.

Figure 11: Average framerate on a GeForce FX 5900 Ultra, using two-sided stencil.

The camera makes a forward zoom towards the occluder while the shadow volume admits 2 positions relative to the camera.


Hedlena Bezerra
email: hedlena.bezerra@imag.frbruno@inf.puc-rio.brlvelho@impa.br

Bruno Feijó

Luiz Velho

A Computer-Assisted Colorization Algorithm based on Topological Difference

Region-based approaches to cel painting typically use shape similarity and topology relations between regions of consecutive animation frames. This paper presents a new colorization algorithm based on topological differences defined over a hierarchical graph of adjacent regions, which allows an almost full automatic colorization process. Also this paper discusses other attributes that improve the solution of the image association problem.

Introduction

Computer Assisted Cartoon Animation is arguably one of the most challenging areas in the field of Computer Animation. Since the seminal paper of Ed Catmull [START_REF] Catmull | The problems of computer-assisted animation[END_REF], from SIGGRAPH 1978, where he describes the 2D animation pipeline and its main problems, there has been intense research in this area. Nonetheless, almost thirty years have passed and some of these problems remain unsolved.

There are several good reasons to explain this difficulty: On one hand, traditional cartoon animation is grounded on artistic interpretation of reality. Therefore, any computer solution has to accommodate both aesthetics results and creative control. On the other hand, 2D animation is mostly about depicting the dynamics of an imaginary 3D world through the two-dimensional strokes of the animator. In essence, these aspects together make most tasks of computer assisted cartoon animation into very hard inverse problems, which are ill-posed and related to perceptual issues.

Ed Catmulls paper concentrated specially on the problem of inbetweening, i.e., the interpolation of key-frames in a 2D animation sequence, which is a stepstone in automating the cartoon animation pipeline.

Here we consider the dual problem of inbetweening, the tracking of 2D structural elements throughout an animation sequence. That is, we aim to establish correspondences between parts of the drawing of objects in subsequent frames. The solution of this problem has, among other things, the practical application of propagating colors from the first frame of the sequence to all the other frames. Thus, it makes the task of inking a totally automatic process. It also allows very easily to change the look of an entire animation sequence, simply by editing the rendering of one frame. Furthermore, this type of scenario integrates very well into the traditional animation process, in which the artist creates an animation drawing it frame-by-frame.

Our approach to solve the region correspondence problem is based on propagating the structural information of the drawings from one frame to the next in an animation sequence. Each frame is described by a two-dimensional graph where nodes represent regions of the drawing and arcs their adjacency relationship. Nodes have several attributes that characterize the associated regions, such as centroid, area and shape. We perform an analysis of local and global properties guided by the connectivity struc-ture, in order to establish a partial isomorphism between the graphs in subsequent frames. Since the region correspondence problem can be inherently ambiguous, we cannot hope to solve it completely in all situations. Therefore, we employ multiple criteria and adopt strategy of only accepting a match when all criteria agree. We leave ambiguous cases for the animator to decide and create an interface that facilitates this decision. Nonetheless, our algorithm is able to establish correspondences automatically in a majority of the cases.

This paper is organized as follows. Section 2 reviews the previous works. Section 3 presents the main challenges faced in computer-assisted color propagation pointing out how to solve some of those problems using information inherent to traditional animation. Section 4 places the colorization problem in the image-based approaches. Section 5 presents how to establish the connection between a frame previously colored and another uncolored using image region information. Section 6 concludes with final remarks and a discussion of ongoing work.

Previous Work

Several works have been proposed to automate cel painting. Madeira et al. [START_REF] Madeira | An approach to computer-supported cartooning[END_REF] use region shape similarity and Chan and Lee [START_REF] Chang | Automatic cel painting in computerassisted cartoon production using similarity recognition[END_REF] work with topological relations. In a positionbased approach to cel painting, Seah and Feng [START_REF] Seah | Computer-assisted coloring by matching line drawings[END_REF] work with a hierarchical motion estimation to establish similarity between frames. These previous work, however, do not consider occlusion and other topological characteristics. One of the best current works on computer-assisted colorization systems is presented by Qiu et al [START_REF] Qiu | Computer-assisted auto coloring by region matching[END_REF]. These authors propose a region-based approach using region shape similarity, topology relations, and master frames. They use a couple of predefined master frames to define pseudo 3D appearance of individual characters. The present paper does not consider pseudo 3D issues like in Qiu et al [START_REF] Qiu | Computer-assisted auto coloring by region matching[END_REF], but achieves great spatial coherence due to a robust metrics for region similarity.

Challenges in colorization

The first challenge in computer-assisted color propagation for traditional animation lies in the freedom practiced by the artist. In the cartoon movies of Saturday mornings, it is easy to notice that geometric or motion information are not very realistic. The animator is completely free to create any kind of situation, even the most surreal one. In addition to this, a large set of ambiguity problems might show up due to the fact that the animator's drawings and paintings are really two-dimensional projections of 3D characters as visualized in the animator's mind. In this section we will examine several scenarios and explain the difficulty of our problem and the basic criteria involved in the association process. Though consecutive frames of an animation look very similar, sometimes animators face ambiguous situations during the colorization process. Figure 1 illustrates a situation that may occur in any animation movie. How can we determine the best association between the circumferences of images a) and b)?

Even a complete analysis of the objects movement on previous frames could not solve this ambiguity with a 100% reliability. This implies shows the difficulty to design failsafe algorithms. However, once the frames are presented in an animation, usually, only small variations occur from one frame to the other. We show that the data concerning object localization and their topological structure in the scene can be exploited to improve on ambiguity in several situations.

Figure 2 shows a good match between objects from images in a) and b). Although this association is not guaranteed, it becomes clear that object C is linked to object A, as shown by their respective positions in the scene. Position presents a good indicator, but it is not enough to solve all cases. Figure 3 shows an ambiguous situation where the distances between probable pairs are the same.

Another clue of association between objects is shape similarity and volume. In general, as in the case of displacements, these values vary little between consecutive frames. Figures 4 illustrates an association based on geometric data. Combining position and geometric is even more effective. However, objects with identical geometry and movement, lead to the same dilemmas as in Figure 3.

To further improve topological structures of the scene should be taken into account to achieve correct associations. Figure 5 illustrates objects added to the scene of the Figure 3. Through the location of each object and their relative positions, it is now possible to deduce the right correspondence. In Figure 5, the relative positions of the star and square indicate the association of the circles between two consecutive frames. However, this wealth of information still does not suffice to guarantee a perfect association.

As image association is inherently an ill-posed problem, there cannot be a complete solution. Nevertheless in this paper presents an approach based on a set of local and global image attributes that allow an almost fully automatic colorization process in most of the cases.

Computer-asssited colorization based on images

Establishing correspondences between two different images, involves the determination of regions. The solution is given by a set of region pairs. The remaining question is, what attributes are needed to succeed in this task? This section introduces a series of local and global aspects present in animation images and shows how to apply them in our context.

The image association problem first requires a system that can identify the compound regions of the image. In outline images, each region is made up of pixels inside a boundary curve. Labeling, a common technique in computer vision, groups the pixels of an image into nonoverlaping regions based on some connectivity criteria [START_REF] Davies | Machine Vision: Theory, Algorithms and Practicalities[END_REF]. E.g. the labeling algorithm proposed by [START_REF] Bezerra | An image-based shading pipeline for 2d animation[END_REF], based on a floodfill, is well adapted to find the entoured regions. In the end of the process, the image I is completely fragmented in a finite group of regions.

Once the regions of an image are identified, it is neces- sary to collect a series of attributes that will be essential to establish the associations with other regions. Some of these attributes determine local aspects, such as, area and position. These characteristics as well as topological aspects of the scene are crucial. In addition, we present other elements that can easily be extracted from any region, as well as guidelines for their application on tracking 2D animation objects. In the following subsections we will present the properties of regions, that we exploit in our matching approach.

Area

The appearance of a character can roughly be given by the shape of its open and closed lines. To transmit the idea of smooth movement, the animator makes small modifications to a previous frame, like changing the position and shape of those lines. Area can vary, but, in general, its relative change is very small [START_REF] Qiu | Computer-assisted auto coloring by region matching[END_REF]. Figure 6 shows two consecutive frames of an animation and that shows this claim; the general volume of the character regions is kept.

Figure 6. Small variations of local areas between two consecutive frames. Image by Mar ão [10]

This property makes area a useful element. After segmentation, each pixel of a same region will have exactly the same label. So, it becomes easy to compute the area (or volume) of a region by counting its pixels.

Position and contour

Maybe the most fragile attributes of a region are its position and contour. In traditional animation there is a special connection between those two attributes. When an animator performs a drastic change in the position, the contour remains mostly the same (and vice versa) in order to make the audience follow the movement. This situation is illustrated in the Figure 7, where although the position of the whip's end changes very much, its shape remains the same. It is thus possible for the audience to recognize and track the object.

To apply this idea to regions, we associate a position to them which is given by the centroid. The region centroid can be calculated by the arithmetic average of positions (x, y) of each associated pixel. However, this might result in a point outside the region. This would not be very representative for the region's position. We realized that in practice these cases are rare for line drawings, thus we can allow a simply strategy and choose an arbitrary point.

Due to the vulnerability of this attribute, it is important to consider a threshold when calculating the proximity between two regions in different frames. This approach can also be improved by considering the movements in the preceding n frames. Thus, a translation during the last n frames can be detected and thus the position of the new centroid in frame n + 1 estimated (but not stated). In order to deal with contour, it is necessary to use robust algorithms to recognize shapes by some particularities that remain unaltered during a frame sequence (through which we still can recognize a form). Belongie et al. [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF] present a simple and strong algorithm to detect associations between two distinct shapes. In their approach, shapes are represented by a group of points from internal or external objects contours. An important aspect described in the algorithm by Belongie et al. is the concept of shape context, which describes the allocation of points from a certain shape based on the position of a pre-determined one. Finding the association between two different shapes means determining which pair of points on both shapes share the closest shape context. Once this association is established, it is extended to the whole shape, estimating an alignment between both the first shape and the second one. The proposed method is independent of scale and object transla-tion, and tolerates geometric distortions as well as occlusions. Shapes indicators represent a powerful assistance to the connection of different regions.

Adjacency and the proposed algorithm

Although the area, position and contour of objects are good indicators of a region, there are times when the key to a better association is the relation of each region to its adjacencies [START_REF] Qiu | Computer-assisted auto coloring by region matching[END_REF]. The connection between objects are also a powerful attribute to make the audience understand and follow the character's appearance and movement.

These proximity associations can be represented by adjacency graph, illustrated in Figure 8. Here, vertices represent regions, while their edges correspond to the proximity associations. When there is an edge linking two vertices on the graph, it means that corresponding regions of the image share a common boundary. Adjacency graphs represent topological region data that can be used as an indicator of good associations between images. In this way, it is important to establish the connection between the graph of a frame previously colored and another uncolored one.

There are several ways of associating two different graphs. The most simple, is also the most costly and consists in a combinatorial solution testing all pairs of nodes. This method is ineffective with images containing several regions. We present a hierarchical approach that deals with objects of the domain in an incremental way providing a more effective and satisfactory solution.

The graph from the scene must be developed in a way that permits a complete tracking of its objects. In animation frames, the background has an important role in the association process (and can be detected easily, e.g. as the region containing pixel (0, 0)). Even though the region seems to be distant and disconnected from the group, we will include it in the graph. This way, all regions are spanned by a single graph and it is easy to associate the root node of two consecutive frames. This allows us to gain speed, as we can now apply a hierarchical combinatorial method.

Given two associated nodes (in the first step these are the roots), we test all children against each other. Having found the best match we furtheron apply our algorithm recursively to the these newly associated regions. During each recursion, some nodes may not get colored in the target graphs. This occurs when the number of children nodes in the source graph is smaller than in the target graph. The algorithm finishes once every node in the source graph has been analyzed.

We have not explained yet how we test the child nodes for proximity. This is where we use our new metric that encodes topologic similarity.

We define for a region r its adjacency function, with respect to the morphology of its surrounding regions. We will then compare two regions by comparing the similarity of their respective adjacency function and choose the best matching pair. The adjacency function of a node is defined as follows:

Let A be a group of regions in an image (Figure 9a), let G be the graph that describes the topology of A (Figure 9b), let V ⊂ A be a group of regions that are adjacent to a region r ∈ A. V is illustrated by dashed lines in Figure 9c). Let P i be the set of points of the contour that defines a region i (Figure 9d). Also let a be an angle and we define d as the most distant intersection of the contour P i with a ray forming an angle a with the x-axis and origin in the centroid of the region r (Figure 9a). Then, the adjacency function F (r,i) of the region r with relation to its adjacent region i is the group of pairs (a j , d j ), where 0 < a j < 2π (Figure 10b and Figure 11). To measure the topological difference between regions s and t we will define the degree of topological difference DT D(s, t). It will give us an information about the proximity of two regions based on a comparison of their adjacency functions. The distance of two adjacency functions is given by their l 2norm. Given two regions we want to measure the best possible association of adjacency functions. Thus the DTD is given by the sum of the distances of the best association of adjacency functions. Figure 12 illustrates the calculation of the DT D(C, a), where the pair #6 and the pair #3 have the lowest value of square error. A low value of DTD indicates a good match of two regions.

The proposed algorithm calculates the degrees of topological difference for all possible relationships between regions in the current iteration level of the adjacency graph. Figure 13 shows these calculations and indicates the best pairs of association (the ones with the lowest value of DTD).

The colorization process

So far we have developed several criteria that we combined to a complete algorithm allowing automatic colorization of an animation sequence. This became possible due to the analysis of local and global characteristics existing in a region such as: area, position, contour and adjacencies. The key to this algorithm is the intent of coloring regions with maximum precision, in other words, the association of colors between regions will only be possible if all other aspects agree. This way, it is necessary that all uncolored regions present similar volume, contour, position and adjacencies. If any of these items are divergent, the algorithm, will not color the region. It is important to know that once the region was colored in a wrong way, this flaw can interfere on next colorizations lowering association quality. Therefore, the colorization process must not be taken with the risk of a wrong association. It is easier to the animator to color some blanked regions than undo the process. As a suggestion to get better results, the animator can be consulted, at every method discrepancy, in order solve the dilemma. After this intervention, more regions can be colored with conviction. Still, it is possible to improve the final association quality trough the analysis of each frame examining transformations that may occur in each re- gion.

The algorithm developed in this paper is, in a certain way, a simplification of the proposed method above. To better evaluate the quality of adjacencies contribution we created a simple system only based on area, position and adjacencies. Neither user iteration nor frames examination was considered. However, even for simple approaches like this, it is possible to color almost 60% of target image, as illustrated on images 14, 15, 16. Figure 14 shows regions from the second frame being colored using information from the first one. Even if there are some blank regions, for this example the algorithm was considered 100% successful, because these regions represent "new" regions on the image.

An example for a case where a region was not associated can be seen in Figure 15. In this case, it is possible to notice the discrepancy between the volume of this area in the original frame and in the target one. Besides that, the association was unsatisfactory as the color of the character's neck was transferred to the bottom lip. This can be explained because in the drawing, the neck disappears, whereas the bot- tom lip is introduced and both have quite similar appearance; the volume, positions and adjacencies seem alike.

On the third and last sequence, some blank regions occur next to the eyes and tongue. Also, on superior eyelids there is a volume variation comparing original and target images. The under eyelids and also internal regions of the eye show a big modification in their adjacencies. The uncolored tongue area is considered a new region, thus, it is not associated with any other. Nevertheless the approach correctly associated several parts, even though the images represent a drastic change.

Conclusions

Although the literature presents several works on computer-assisted colorization [START_REF] Madeira | An approach to computer-supported cartooning[END_REF], [START_REF] Chang | Automatic cel painting in computerassisted cartoon production using similarity recognition[END_REF], [START_REF] Qiu | Computer-assisted auto coloring by region matching[END_REF], [START_REF] Seah | Computer-assisted coloring by matching line drawings[END_REF], the subject has a lot of problems to be solved. The image association problem is inherently ambiguous and there is no complete solution. This paper presents a new colorization algorithm based on topological differences defined over a hierarchical graph of adjacent regions, which allows an almost full automatic colorization process. The use of the adjacency function and the Degree of Topological Difference (DTD) within a hierarchical adjacency graph generate good results. The proposed algorithm can cope with regions that come out or disappear (like a tongue that comes into view when the mouth opens or an ear that appears when the head rotates). Improvements in the quality of the proposed algorithm can be achieved by adding contour information and intelligent iteration that learns during the process. Different values can also be attributed to each element of the iteration process (area, adjacencies, position). The present paper lacks a comparative analysis with correlated works, specially with the one by Qiu [START_REF] Qiu | Computer-assisted auto coloring by region matching[END_REF] et al. Nevertheless the system we presented is quite successful despite its simplicity indicating that the new distance metric we introduced represents an important clue concerning the association of regions. The graph structure not only accelerates computation but also helps guiding the matching process proving to be a very useful concept.

Figure 1 .

 1 Figure 1. Ambiguity in colorization.

Figure 3 .

 3 Figure 2. Association between regions by intuition.

Figure 4 .Figure 5 .

 45 Figure 4. Association based on shape and volume.

Figure 7 .

 7 Figure 7. The variation of position is large, the variation of shape is small. Images by Mar ão [10].

Figure 8 .

 8 Figure 8. Adjacency graph. Regions (circles) and their adjacencies (lines) represented on both source (a) and target images (b).

Figure 9 .

 9 Figure 9. a) Group of regions A. b) Graphs of A. c) Adjacencies of r. d) Points located on the regions contour on r adjacencies.

Figure 10 .

 10 Figure 10. a) Line from the centroid of r, where a is the angle and d is the most distant intersection point with contour Pi. b) Group of lines from region r to its adjacent region i.

Figure 11 .

 11 Figure 11. Adjacency Function F (r,i) .

Figure 12 .

 12 Figure 12. a) Adjacency Functions to hypothetical regions C and a. Table indicates the values of square error between each possible pair. Pairs with lower values are chosen to illustrate the difference of topology among regions C and a.

Figure 13 .

 13 Figure 13. Statistics of association between regions from current iteration. Only the best scores will be used.

Figure 14

 14 Figure 14. a) Source image. b) Target image. Blank areas indicate new regions on the sequence.

Figure 15

 15 Figure 15. a) Source image. b) Target image. Blank areas indicate disconnection between volumes from sample region and upcoming one.

Figure 16

 16 Figure 16. a) Source image. b) Target image. Blank areas indicate disconnection between volumes and adjacencies from sample region and upcoming one.

Acknowledgments. The authors thank César Coelho and Marão for all images and support as traditional animators. We also would like to thank Elmar Eisemann for unique discussions and comments regarding the present work. The authors would like to thank CNPq, CAPES, and FINEP for the financial support given to them in the form of scholarships and research contracts. Also they are thankful to the R&D centers involved in this work: VisionLab/PUC-Rio e Visgraf/IMPA. The first author is supported by a grant from the European Community under the Marie-Curie project VISI-TOR.