Keywords: NURBS, animation, rendering, anti-aliasing
Our approach is to try to bring together the best of computer modelling and rendering techniques within a cel-based system, thereby adopting an approach which is outwardly familiar to the animator but internally harnesses the computer. We start with the conventional view taken in 3D modelling, namely that an object should be represented by a data structure so that it can be readily manipulated and modified. In doing this we have already implied that paint programs are not an allowed solution because they have no data structure above the pixel array. Then we continue to argue conventionally: in order to view the frame we will need a lighting model and a renderer. What we are doing which is new is bringing this consistently to bear on a 2D system while solving the problems that arise on the way. The advantages of this approach are all of those arising from a correct computer-based representation, namely that picture elements can be modified, scaled, rotated, and translated in a device-independent form with no reference to output spatial resolution, output colour resolution and, significantly for animation, with no regard for the output frame-rate. This approach is thus future-proof in that any scene modelled this way can at a future date be re-rendered at any required resolution or frame rate. It also gives back to the animator something which cels removed, namely a view of motion as a continuous action.
In this paper we focus on the foundation layers, namely the modelling and rendering of individual static frames, of what we intend to be a complete 2D animation system. For now, we are assuming that cels are drawn with generalised painted regions and it is these regions which need to be represented and rendered. Thus the main direction of the work here reported is that of scan-converting regions bounded by NURBS (non-uniform rational B-splines, based on the work of [DeBo72]). We do not consider the higher level, which is the provision of control and a user-interface which actually allows animation to be designed and tested.
Our computer-based system mimics this in the first instance. However we also take advantage of good graphics practice to give us further advantages not available to the traditional animator. For the most part, these arise from the way the pictures are modelled, the way they are realised and the way they are combined. We will examine these in turn.
Hand in hand with this representation of the colour of the picture components we also adopt a lighting model. Again it is important to note that we are fully modelling the entire system and we are specifically not assuming that the colour of the model component is itself the output colour. Instead, we assume that each cel is illuminated from the front by a light of known brightness and colour, and that there is a similar but independent light behind the cel. Lighting parameters can of course be modified or even animated. Thus we model full control over front and rear lighting of each cel (not just over the complete stack of cels). Lighting can be dynamically controlled and is an important way of achieving certain special effects.
Of course, other forms might be just as acceptable but NURBS have a generality which is appealing at the cost of some computing power. In fact the key item here is not the NURBS representation but the fact that all pictures are constructed of closed areas. These areas are not defined with respect to a pixel grid and are thus an abstract, fully transformable form. One consequence of this is that there is no equivalent to a Bresenham line in our system. Lines are simply elongated patches and they therefore scale correctly, looking thicker when magnified for example, just as in our earlier work [Will87]. Areas of colour are broad patches with a regular or irregular outline. One of the attractions of NURBS is their ability to represent regular shapes like circles as well as free-from shapes.
The interior of the patch is assumed to be coloured but not necessarily by a single colour. This part undoubtedly needs a proper study, but for now we are assuming that the interior colouring can be mapped from a general colour space. Even so, many cartoon applications only require a uniform interior colour and this is what we currently support.
Complex shapes or colourings can be built up hierarchically, with overlapping and/or translucent patches where appropriate. The shapes are readily transformable and, again, the transforms can be applied hierarchically in the familiar manner. Note that what we are really saying is that there is a properly constructed model of the picture, independent of its visual form, just as we would expect to find in engineering CAD and other applications but which has often been lacking from this kind of application.
Hence all items have a fully-defined geometry, allowing all the usual transformations such as rotation, translation and scaling. Furthermore, because there is really only one underlying primitive, rendering becomes greatly simplified. Of course, all items are represented in an abstract, pixel-independent space throughout the modelling (and indeed through most of the rendering).
The scan-converter itself assumes that the NURB patches are presented to it in the proper order, front-most patch first (so that patches overlie in the correct sense) and so all sorting is performed by a preparation phase in the main application program (which is where the ordering information is to be found). This frees the converter from any knowledge of how the application models the pictures, easing code development as well as allowing it to be used with other applications such as illustration packages.
Our view of scan-conversion is that we calculate the intersections of a given scanline with a given NURB, producing a sequence of interior and exterior spans. We do not perform the intersections incrementally, in the interest of obtaining robust results and to allow selective change of conversion resolution. The spans across a given scanline can then be combined according to our colour model, though it is also possible to extend this phase to include CSG operations between NURB patches, giving another modelling option.
Figure 1: Basic Features of a NURB.
In detail, scan-conversion of a single closed NURB patch proceeds as follows. We start with the control points for the NURB and calculate from them the cubic curve which represents each segment (see Figure 1). With N control points we will produce N segments because the NURB is closed (An open NURB with control points V_0 to V_(N-1) is closed by making V_N = V_0; V_(N+1) = V_1; V_(N+2) = V_2 with the same weights and inter-knot spacing). The method we use to calculate the cubic curves is a modification of that of Choi, Yoo and Lee [Choi90].
Their approach shows how to calculate a coefficient matrix, once for each segment, given the parametric inter-knot spacing for the NURB curve as a whole. The resulting matrix contains the majority of the values required for calculation of an (x,y) position on the NURB segment, given a parametric value in the range [0.0, 1.0). The application of the matrix requires two simple multiplications, firstly of the matrix with a vector comprising the x, y or w part of each control point (where w is the weight associated with each point). Secondly, the result of this (a vector) must then be evaluated into a cubic polynomial of the parametric value u by multiplication with another vector:
d d-1 [u, u , ..., u, 1] (transposed to a column vector) where u: parametric value d: degree of the NURB
The matrix can be applied separately to the x, y and w parts of the control points. Application of the matrix to the x or y parts results in a homogenous x or y coordinate, which must then be rationalised (i.e. divide the homogenous coordinate by the result of the application of the matrix to w) before further use. In order to calculate the intersection of a particular scanline (i.e. an infinite line of constant Y) with a segment of the NURB, we need to evaluate the standard rational form of the NURB curve such that the result is Y. The standard form is:
d i+d d+1 r (u) = SIGMA V_j.L(u) i j=i j-d ---------------- 0 <= u < 1 i+d d+1 SIGMA w_j.L(u) j=i j-d where i = [0,N+2] V_i = (x_i, y_i): control point i w_i: weight associated with a control point i u: parametric value for segment i L: basis function i.e. the Choi coefficient matrixBy rearranging the above equation, we produce a cubic equation the roots of which correspond to the parametric positions of the intersections between the segment and the line:
i+d d+1 y SIGMA L(u) . ( V - Y.w ) = 0 j=i j-d j j where Y: current scanline
Given that Y has already been chosen all that remains to be done is to evaluate the above directly, i.e. without using iteration. We use the pre-calculated values in the coefficient matrix, to yield parametric values which are in turn used to compute the required x values (the points of intersection), This need only be done for parameters between [0.0, 1.0) on each segment as only this range contributes to the NURB (see Figure 1). We used the REDUCE [Hear82] computer algebra package both to verify the Choi coefficient matrix and to generate the C code that implements it.
Our method has several advantages. Like Choi, Yoo and Lee [Choi90], we pre-calculate the coefficient matrix so that it may be used both for the calculation of the intersection and in the evaluation of the rational form. The amount of computation and the complexity of the required program are further significantly reduced in our scan-conversion approach because there is no Y calculation necessary, thus halving the computation for the intersection. No computational gains would arise from evaluating forward differences for the curve, since the resulting difference matrix is of a similar size as the coefficient matrix, whilst introducing numerical problems.
Additionally, it can be seen that our method provides significant advantages over polygonal approximation methods. By its very nature, our method automatically adapts to the resolution of the output device, rather than requiring the use of a heuristic function (the degree of parameterisation) to estimate the degree of polygonisation required. This adaptation shows itself at its best when weights are used to change the shape of the curve because no re-parameterisation is necessary. Additionally, our method will always produce correct output even if the NURB becomes highly curved or self-intersecting. Furthermore, should we be presented with conic sections (one of the most commonly used NURB forms in CAD/CAM and computer graphics), then the standard form simplifies to a quadratic and so root-finding is easier.
Finally, it is important to note that the entire calculation is performed with floating point arithmetic; in particular the x and y values are real quantities, not integers, so not only is there no presumption of discrete pixels but also we retain full resolution, well beyond the relatively poor resolution of any physical display. Thus our representation is both inherently portable and well-capable of addressing even the very high resolutions used in, for examples, the printing industry or in originating high-quality movie film.
Furthermore, each Y scanline is computed independently of any other, so there is no incremental updating and therefore no possibility of accumulating errors. Data structure management is also simplified: we build one output list anew for each scanline. This makes clipping against the upper and lower edges of the screen entirely unnecessary: such regions are simply never needed. We thereby avoid one potential problem with incremental methods, namely that when most of the curve is above the top of the screen we do not waste time computing invisible sections in order to calculate the shape of the visible. Horizontal clipping (against the left and right edges of the screen) is also very simple. Each line/cubic-curve pair produces one of four results: none, one, two or three intersections. These floating-point x values, and those for all other active segments, are insertion-sorted into a linked list representing the output at the current y position. Some of these values will, when mapped onto the screen, be outside the left or right picture edges. Those spans beyond the right-hand edge can be rejected immediately they are found. Any which straddle the right-hand edge can be clipped immediately or at the stage when the scan-line is turned into pixels: either is fast to do. It is however important to retain those beyond the left-hand edge so that we can correctly determine which spans are internal to the patch. This is done by walking along the linked list, starting with an "internal" flag set to false. In general each new intersection toggles this flag, identifying the interior regions. In practice, some intercept pairs may be identical (because the curve is self-intersecting) in which case both may be discarded as they cancel out. (It is not strictly necessary to keep the entire list for the part to the left of the screen, as long as the parity of the "internal" flag is correctly maintained, but our current implementation does take the simple solution.) This approach is analytically accurate, incorporating as it does spans which are smaller than a pixel and spans which are not pixel-aligned, and so avoids the usual special-case problems which arise when determining interiors. Figure 2 shows a NURB shape scan-converted to pixel accuracy; in contrast, Figure 3 shows the same shape with the correct horizontal alignment represented through partial pixel intensities. It is an important advantage of retaining accurate intersection information that it allows the correct calculation of horizontal anti-aliasing.
Figure 2: Aliased Cel
Figure 3: Horizontal Anti-Aliasing
We have devised, but not yet implemented, a general geometric solution to anti-aliasing which makes use of the accurate horizontal information together with a good approximation to the geometry in the vertical direction. Currently we are using super-sampling to achieve vertical anti-aliasing, though even here our approach is efficient because we have already computed the horizontal intersections accurately. Put another way, the cost of super-sampling with scan-conversion is linear with resolution, whereas pixel-sampling methods have a cost proportional to the square of the resolution. Figure 4 shows the test shape with 5 to 1 vertical supersampling, as well as horizontal anti-aliasing. Not only does this give very good edges to a general drawing primitive, it also means that slow movement of the shape becomes possible. This is at least as important as edge quality to our animation application area, where pixel-aligned systems would produce a very jerky result and/or "crawling" edges.
Figure 4: Full Anti-Aliasing
The beta model permits both hard and soft masks (mattes), which are optionally coloured. So, together with the cel lighting, quite sophisticated lighting and special effects are possible. Lighting is itself a powerful weapon in the animator's armoury. For example, we can model a scene in the conventional way and then illuminate it for dusk or night time. A judicious choice of lighting will modify the perceived colours of the scene and can even be used to change the relative emphasis of scene components, as when light falling from a window picks out a central character in an otherwise night-time scene. Figure 5 and Figure 6 are pixel images arranged on cel layers, matted together with all of the lighting and colour combination performed using the beta model. It is important to note that the original foreground and background images have not been changed between these two views.
Figure 5: Day Scene
Figure 6: Misty Scene
The basic lighting scheme provides a uniform light evenly illuminating the entire cel. This can easily be modified by providing additional cels to mask parts of the scene. These matte cels are created in the same way as any other; that is, they are NURB drawings with no reference to the pixel structure of the final image. There is thus no need to treat them as special cases within the renderer. It is important to realise that the NURB boundaries are not quantised by the renderer to unit pixel values and so can be blended correctly with any underlying image. This approach, using geometrically accurate boundaries, thus avoids the complexities associated with the A-buffer [Carp84].
In a similar fashion, texture effects can be produced as a modulation of a picture. The modulation is represented in a cel which is then placed over the picture to be modulated. Here we typically rely on locally varying the translucent element of the beta model, the medium, while having no reflective component.
Another useful property of the beta model is that it can be used to implement general filters to supply a range of image-modification effects. This allows "foggy" cels, or cels which are partly clear and partly translucent, to be used to enhance the basic scene without directly changing its modelled representation. This, together with the independent lighting model, makes for greater re-use of cels. Such filters are often more usefully implemented functionally, rather than as highly elaborate NURB sets, but again the beta model ensures that these are easily incorporated in the renderer.
It is acceptable to combine a stack of cels to produce a single resultant cel, which is then re-used for the creation of a more complex scene. However, the renderer would be typically used with many cels invariant across a sequence of frames, when it would be better to convert each changing cel separately, and then combine this with previously created foreground and background cels. Again, the beta model guarantees this is always possible.
What this means in practice is that, for example, an animator can construct a complex background from a variety of cels and, when satisfied with the result, the cels can be combined to produce a single cel with the same visual effect, with lower storage costs, and reduced computation at later stages. It is also possible to hold cels in scan-converted internal form (i.e. before the final RGB conversion) and to re-use these in conjunction with new cels.
In contrast with incremental methods, we can always take any NURB and treat it in a uniform manner. In particular, incremental conversion of a cubic will sometimes result in the need to start new computations for the same curve, part way through the conversion, as extra intercepts come in to play. This is unnecessarily demanding to monitor and it is space and time consuming to preprocess the cubics into pieces which are single-valued. Our method computes all of the intercepts explicitly, avoiding this problem entirely.
A bonus of working in floating point is the full accuracy of the computation, avoiding special cases and the loss of otherwise useful data. In particular horizontal anti-aliasing is available at the low additional cost of computing partial intensities from information already present. As a result, supersampling is only needed in the vertical direction, giving an anti-aliasing cost which is linear, rather than quadratic, with resolution.
Clipping against a rectangular region, such as the screen, has zero cost for the upper and lower edges and almost no additional cost for the left and right edges: again all of the information needed is already present and it is largely a matter of clamping extents.
All of the above result from our current implementation. There are also some interesting possible enhancements. We have the option of incorporating in a simple manner the CSG operations to combine 2D shapes, because this can be done at the scanline level. For some applications this can be a substantial gain simply because it will work with any class of shape which can be scan-converted. We lose little of the simplicity in doing this because such operations can be embedded in the input patch stream, for example in RPN form, and would drop out easily from a regular walk of the corresponding and conventional tree-structured model.
The potential to include colouring as a function, rather than as a fixed property, ensures that quite subtle visual effects can be achieved easily, for example through additional filter cels. Our colour model does not require filters to be scalar operations, again extending the range of visual effects. We have demonstrated these advantages with pixel images, to test the beta colour model, and that model is already part of our NURB system in anticipation of this addition.
Our approach will also work for more general image composition applications. It has the advantage over the A-buffer approach [Carp84] in not requiring pixel-by-pixel data for matting images together. It also means that areas to be matted can be bounded by curves rather than polygons and, where moving mattes are required, these curves can be animated without needing to ensure good polygonisation.
Proper boundary definition is especially pertinent in animation sequences containing a slowly moving NURB. Polygonization of the NURB is not necessarily constant between frames, which leads to an aliasing artefact known as "creeping". The major strength of our method is that it does not use any sort of polygonal approximation and so automatically avoids this problem.
We are also grateful to Peter Harding for permission to base the colour pictures showing our lighting technique on his artwork.
The images in this paper have been rescanned from printed versions and are of poorer quality than the originals.
REDUCE - A Case Study in Algebra System Development
Proceedings of EUROCAM 82, 1982, pp. 263--272, Springer-Verlag.
Carp84, Loren Carpenter,
The A-Buffer, an Antialiased Hidden Surface Method
Computer Graphics (SIGGRAPH 84), 1984, 18(3), pp. 103--108, July.
Philip Willis and Geoff Watters,
Scan Converting Extruded Lines at Ultra High Definition
Computer Graphics Forum, 1987, 6(2), pp. 133--140, May, North-Holland.
Wall81, Bruce A. Wallace,
Merging and Transformation of raster images for cartoon animation
Computer Graphics (SIGGRAPH 81), 1981, 15(3), pp. 253--262, August.
DeBo72, Carl De Boor,
On Calculating with B-Splines
Journal of Approximation Theory, 1972, 6 pp. 50--62.
Choi90, B.K. Choi and W.S. Yoo and C.S. Lee,
Matrix representation for NURB curves and surfaces
Computer-Aided Design, 1990, 22(4), pp. 235--240, May, Butterworth & Co
Oddy91, Robert J. Oddy and Philip J. Willis,
A Physically Based Colour Model
Computer Graphics Forum, 1991, 10(2), pp. 121--127, June, North-Holland.