Functional animation including sprite tree generator and interpreter

[0002] The present application is a continuation in part of co-pending application Ser. No. 09/337,701 entitled “Functional Animation including Sprite Engine for Video Imaging” having a filing date of Jun. 21, 1999. The present application also claims priority from U.S. provisional patent application Ser. No. 60/093,487 filed on Jul. 20, 1998, entitled “Functional Animation using Sprite-Based Presentation” which is incorporated herein by reference.

[0003] The present invention relates to computer imaging and more particularly to method and apparatus for converting functional animations into a form that can be efficiently updated at a rate required for visual presentation on a video display.

[0004] Computer generated animations have wide applications and have improved as hardware has improved. As the personal computer industry has evolved into a multi-billion dollar economy, high quality graphics rendering systems have become less expensive. Graphics systems once costing many hundreds of thousands of dollars are now available at a fraction of that cost.

[0005] A standard means of displaying images on a viewing screen is to first format the image into a bitmapped image and transfer the bitmapped image to a region of video memory. As the computer is composing a next subsequent bitmapped image video hardware accesses the first region of video memory that was previously formatted and causes video signals to be generated and coupled to a viewing monitor. Once the next subsequent region of memory has been formatted, the video hardware switches to the memory region containing that bitmapped image to generate appropriate video driver signals. This back and forth switching occurs at video refresh rates of display rates of at least 60 frames per second.

[0006] Lower level presentation libraries for sprite-based display and sound presentation are designed not for convenience of a program's author or readers, but rather for efficient execution on anticipated video and/or audio hardware. These presentation libraries impose rigid structure, in order to allow acceleration by hardware and low level software. Programs written directly on top of these libraries must adapt to relatively inflexible representations and tend to be relatively non-modular. Writing software that directly interfaces the presentation libraries is not an easy task and to successfully program for these libraries one must adher to the hardware protocols rather closely. The rigorous adherence to video presentation standards can make the process of producing an effective animation more difficult. There are existing programming languages that are well suited to accomplishing animation in a more intuitive way. A functional approach to animation offers considerable flexibility and modularity and is described, for example, in Arya, Kavi, “A Functional Animation Starter-Kit,” Journal of Functional Programming, Vol. 4, No. 1, pp. 1-18 (January 1994), and in Elliott, Conal, and P. Hudak, “Functional Reactive Animation,” Proceedings of the1997 ACM SIGPLAN International Conference on Functional Programming, Amsterdam, The Netherlands, pp. 263-273 (Jun. 9-11, 1997), which is herein incorporated by reference. Functional animation encourages a highly modular programming style by supplying a set of arbitrarily composable functions for building up animations.

[0007] These functional programming languages treat animations as values or elements of a data type consisting of a set of constants and combining operators. The use of an animation data type allows great flexibility in composing these basic building blocks into either directly useful or attractive animations, or new building blocks, parameterized as desired. Moreover, animation is a polymorphic notion since the functions implementing the animation can be applied to different types. Animation can be applied to 2D images, 3D geometry, and constituent types like colors, points, vectors, numbers, booleans, etc. Consequently, there is not just one type, but a collection of types and type constructors. Such a system of data types imposes just enough discipline to rule out nonsensical compositions (such as rotating by the angle “purple”), without inhibiting the author's creativity. In this way, the data types are designed to serve the need of the author (and readers) of an animation.

[0008] A computer animation system constructed in accordance with the invention animates a computer presentation that includes both images and sound. A component referred to as a normalizer interprets an animation to produce a data structure of image and sound objects. At video and audio refresh rates this data structure is in turn interpreted by a rendering software component referred to herein as a sprite engine.

[0009] The exemplary embodiment of the invention renders the animation by first describing or defining the computer animation in a high level functional programming language program. At presentation update intervals the contents of a presentation data structure are updated based on the time varying computer presentation. At presentation refresh intervals more frequent than the update intervals, a computer presentation data set is composed that approximates a change of the computer presentation between the update intervals. At a sensory presentation rate greater than a rate at which the presentation data structure is updated, the computer presentation data is sent to rendering hardware to perform the computer animation.

[0010] Computer animation typically involves a visual images that are periodically updated. The presentation data structure for this type animation includes a sequence of images that are displayed on a viewing monitor. In a bitmapped imaging process, the visual image description is data that is stored in a region of the computer memory. The frequency of the presentation refresh rate is high enough to smoothly update such video images.

[0011] The computer animation may also include an audible rendering. For an audible animation the frequency and volume of the output signal is updated rather than updating a part of memory.

[0012] In accordance with an exemplary embodiment of the invention, the presentation data structure is a sprite tree. The sprite tree is made up of a series of nodes with sprites at the leaves and behavior modifications at interior nodes of the sprite tree. The sprite interpreter or sprite engine animates the sprites that make up the sprite tree by performing a ‘paint’ function for each sprite leaf in the tree. In the instance of a sound sprite the ‘paint’ method provides an audible output from an audible hardware interface.

[0013] Use of a sprite tree datastructure facilitates the updating of the animation. Updating of the sprite tree data structure may only require an updating of a portion of the sprite tree affected by a user controlled input. This requires a replacement of an internal node of the sprite tree and all sprites descending from this so-called mutable node but does not require a complete re-construction of the sprite tree.

[0014] A normalizer component updates sprite positions much less frequently than needed to achieve video refresh rates. Between successive updates of the sprite tree the sprite tree engine renders the sprites at positions intermediate the end points determined by the normalizer component. The positions of these intermediate positions are determining by linearly interpolating between the two end points.

[0015] In one embodiment of the present invention, the computer animation is represented in a high level programming language such as Haskell (note, other functional animation programming languages could also be used) which allows the animation to be more easily programmed. This high level animation representation is converted by the normalizer component into a presentation data structure based on the time varying computer presentation defined in the Haskell program. The normalizer component defines a series of different methods that convert legal constructs from the Haskell representation to the presentation data structure by determining which of said different methods matches the Haskell animation representation. The sprite tree engine composes a bit mapped image from the data in the presentation data structure at refresh intervals and transmits the computer presentation data to rendering hardware to perform the computer animation. The preferred normalizer component recursively calls the methods until the method includes an instruction to add a sprite (image or sound) to a list of sprite trees.

[0016] A preferred computer for practicing the invention includes an operating system that can spawn multiple executing threads. In such an environment the step of updating the contents of the presentation data structure executes in a first thread and the step of accessing data stored in the data structure and composing computer presentation data executes in a second thread. The second thread executes in a higher priority thread.

[0017] These and other objects, advantages and features of the invention will become better understood from the disclosed exemplary embodiment of the present invention which is described in conjunction with the accompanying drawings.

[0018] The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements and in which:

[0019] FIG. 1 illustrates an exemplary operating environment for a functional animation sprite-based presentation system;

[0020] FIG. 2 illustrates, for one embodiment, a functional animation sprite-based presentation system;

[0021] FIG. 3 illustrates, for one embodiment, a list of sprite trees;

[0022] FIG. 4 illustrates a representation of an animated number;

[0023] FIG. 5 illustrates exemplary functional animation data types;

[0024] FIG. 6 illustrates exemplary sprites constructed from the data types of FIG. 5;

[0025] FIG. 7A illustrates the steps in interpreting a sprite tree and building a display buffer by a sprite tree engine component;

[0026] FIG. 7B illustrates the steps of creating a sprite tree by a normalizer component; and

[0027] FIG. 8 is an example of a normalizer output of a representative functional animation language statement.

[0028] A functional animation sprite-based presentation system in accordance with the present invention bridges the gap between functional specification and sprite-based presentation of animation.

[0029] 1. Exemplary Operating Environment

[0030] FIG. 1 and the following discussion are intended to provide a brief, general description of a suitable computing environment in which the invention may be implemented. Although not required, the invention will be described in the general context of computer-executable instructions, such as program modules, being executed by a personal computer. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. Moreover, those skilled in the art will appreciate that the invention may be practiced with other computer system configurations, including hand-held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

[0031] With reference to FIG. 1, an exemplary system for implementing the invention includes a general purpose computing device in the form of a conventional personal computer 120, including a processing unit 121, a system memory 122, and a system bus 123 that couples various system components including system memory 122 to processing unit 121. System bus 123 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. System memory 122 includes read only memory (ROM) 124 and random access memory (RAM) 125. A basic input/output system (BIOS) 126, containing the basic routines that help to transfer information between elements within personal computer 120, such as during start-up, is stored in ROM 124. Personal computer 120 further includes a hard disk drive 127 for reading from and writing to a hard disk, a magnetic disk drive 128 for reading from or writing to a removable magnetic disk 129, and an optical disk drive 130 for reading from or writing to a removable optical disk 131 such as a CD ROM or other optical media. Hard disk drive 127, magnetic disk drive 128, and optical disk drive 130 are connected to system bus 123 by a hard disk drive interface 132, a magnetic disk drive interface 133, and an optical drive interface 134, respectively. The drives and their associated computer-readable media provide nonvolatile storage of computer-readable instructions, data structures, program modules and other data for personal computer 120. Although the exemplary environment described herein employs a hard disk, a removable magnetic disk 129 and a removable optical disk 131, it should be appreciated by those skilled in the art that other types of computer-readable media which can store data that is accessible by a computer, such as magnetic cassettes, flash memory cards, digital video disks, Bernoulli cartridges, random access memories (RAMs), read only memories (ROMs), and the like, may also be used in the exemplary operating environment.

[0032] A number of program modules may be stored on the hard disk, magnetic disk 129, optical disk 131, ROM 124 or RAM 125, including an operating system 135, one or more application programs 136, other program modules 137, and program data 138. A user may enter commands and information into personal computer 120 through input devices such as a keyboard 140 and pointing device 142. Other input devices may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to processing unit 121 through a serial port interface 146 that is coupled to system bus 123, but may be connected by other interfaces, such as a parallel port, game port or a universal serial bus (USB). A monitor 147 or other type of display presentation device is also connected to system bus 123 via an interface, such as a video adapter 148. One or more speakers 157 or other type of audio presentation device are connected to system bus 123 via an interface, such as an audio adapter 158. Personal computers typically include other peripheral output devices, such as printers.

[0033] Personal computer 120 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 149. Remote computer 149 may be another personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to personal computer 120, although only a memory storage device 150 has been illustrated in FIG. 1. The logical connections depicted in FIG. 1 include a local area network (LAN) 151 and a wide area network (WAN) 152. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

[0034] When used in a LAN networking environment, personal computer 120 is connected to local network 151 through a network interface or adapter 153. When used in a WAN networking environment, personal computer 120 typically includes a modem 154 or other means for establishing communications over wide area network 152, such as the Internet. Modem 154, which may be internal or external, is connected to system bus 123 via serial port interface 146. In a networked environment, program modules depicted relative to personal computer 120, or portions thereof, may be stored in remote memory storage device 150. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

[0035] 2. Functional Animation Sprite-based Presentation System

[0036] FIG. 2 illustrates for one embodiment a functional animation sprite-based presentation system 200 comprising a functional animation application 210, a functional animation library 220, an animation normalizer 230, a temporal sprite engine 240, a sprite-based presentation library 250, and presentation hardware 260. Application 210, functional animation library 220, normalizer 230, sprite engine 240, and presentation library 250 for one embodiment are implemented as program modules or computer-executable instructions and may be stored on any suitable computer-readable medium for execution in a suitable operating environment, such as the computing environment of FIG. 1 for example.

[0037] Application 210 specifies one or more animations to be presented using sprite-based presentation library 250 and presentation hardware 260. Presentation library 250 comprises suitable lower level software to interface with and control presentation hardware 260 for presenting animations specified by application 210. Presentation library 250 for one embodiment comprises DirectX® by Microsoft® Corporation. Presentation library 250 may comprise, for example, DirectDraw®, DirectSound®, or Direct3DRM, which is a part of Direct3D®, by Microsoft® Corporation. Presentation library 250 may also comprise Inventor or Performer by Silicon Graphics Inc. Presentation hardware 260 may comprise any suitable hardware for animation presentation. Presentation hardware 260 for one embodiment comprises suitable hardware, such as video adapter 148 and monitor 147 for example, to display animations and/or suitable hardware, such as audio adapter 158 and speakers 157 for example, to present sound animations. Presentation hardware 260 may comprise other suitable hardware to present animations using robotics, for example.

[0038] Application 210 may be implemented in any suitable programming language, such as the purely functional language Haskell as described, for example, in Hudak, Paul, and J. H. Fasel, “A Gentle Introduction to Haskell,” SIGPLAN Notices, Vol. 27, No. 5 (May 1992) and Hudak, Paul, S. L. Peyton Jones, and (editors) Philip Wadler, “Report on the Programming Language Haskell: A Non-strict Purely Functional Language (Version 1.2),” SIGPLAN Notices, (March 1992). Application 210 specifies one or more animations supported by functional animation library 220.

[0039] The functional animation library 220 may comprise any suitable animation building blocks and may provide support for implementing animations in any suitable programming language. Functional animation library 220 for one embodiment is Fran (Functional reactive animation) as described, for example, in Elliott, Conal, and P. Hudak, “Functional Reactive Animation,” Proceedings of the1997 ACM SIGPLAN International Conference on Functional Programming, Amsterdam, The Netherlands, pp. 263-273 (Jun. 9-11, 1997); Elliott, Conal, “Modeling Interactive 3D and Multimedia Animation with an Embedded Language,” The Conference on Domain-Specific Languages, Santa Barbara, Calif., pp. 285-296 (October 1997), which is herein incorporated by reference; and Elliott, Conal, “Composing Reactive Animations,” Dr. Dobb's Journal(July 1998), which is herein incorporated by reference. Fran is implemented in Haskell and supports Haskell. Although described in the context of Fran, the present invention may be used with other suitable animation libraries.

[0040] The execution of application 210 over functional animation library 220 constructs functional animation data types 222 to define the one or more animations for presentation. Functional animation data types 222 may be implemented in the form of one or more suitable data structures and may also be stored on any suitable computer-readable medium, Functional animation data types 222 for Fran are described, for example, in Elliott, Conal, “A Brief Introduction to ActiveVRML,” Technical Report MSR-TR-96-05, Microsoft® Research, Microsoft® Corporation, Redmond, Wash. (February 1996), which is herein incorporated by reference.

[0041] The normalizer 230 bridges the gap between the high level flexibility desired for specification of animations and the low level regularity imposed by sprite engine 240. The normalizer 230 transforms the flexibly specified animations into the form required by the sprite engine 240. Normalizer 230 constructs and updates a list of sprite trees 232 based on several algebraic properties of functional animation data types 222. Normalizer 230 may be implemented in any suitable language, such as Haskell for example. Although described as separate modules, application 210, functional animation library 220, and/or normalizer 230 may alternatively be integrated. Alternatively, an imperative program may interface with sprite trees 232 directly.

[0042] Sprite trees 232 define a list of sprites for presentation by presentation library 250 and presentation hardware 260. Sprite trees 232 may be implemented in the form of one or more suitable data structures and may also be stored on any suitable computer-readable medium.

[0043] Sprite engine 240 recursively traverses sprite trees 232 and interfaces with presentation library to 250 to control the presentation of the sprites of sprite trees 232. Sprite engine 240 may be implemented in any suitable language. Sprite engine 240 for one embodiment is implemented in C++ and runs in a separate thread.

[0044] Because application 210, functional animation library 220, and normalizer 230 construct and update sprite trees 232 at a rate slower than that at which sprite engine 240, presentation library 250, and presentation hardware 260 are able to present the sprites of sprite trees 232, sprite engine 240 performs linear interpolations for sprites between updates so as to provide for a relatively smoother presentation of animations. As one example, application 210, functional animation library 220, and normalizer 230 update sprites comprising bitmap images with positional and scale information approximately ten times per second while presentation library 250 and presentation hardware 260 display those bitmap images at video refresh rate. Sprite engine 240 therefore linearly interpolates any updates by normalizer 230 in the positional and scale information of the sprites of sprite trees 232 and updates the positional and scale information of the updated sprites in accordance with the linear interpolations at a faster rate of approximately sixty times per second so as to display the movement and scaling of bitmap images in a relatively smoother manner. Sprite engine 240 may also support fast “flip-book” animation of sequences of bitmaps with linearly interpolated indexing.

[0045] 3. Animation Data Types

[0046] Fran's animation data types have been described elsewhere, such as in Elliott, Conal, and P. Hudak, “Functional Reactive Animation,” Proceedings of the1997 ACM SIGPLAN International Conference on Functional Programming, Amsterdam, The Netherlands, pp. 263-273 (Jun. 9-11, 1997) for example. Most of the animation-level types come from applying the Behavior type constructor to these static types, and “lifting” operations on the static types to operations on behaviors. As an illustrative example, and because it is particularly relevant to the sprite-based implementation of 2D animation, one such type is described next.

[0047] 3.1 Static 2D Transforms

[0048] The Transform2 type represents 2D geometric transformation on images, points, or vectors. It also defines a type class Transformable2 containing types of 2D transformable objects.

[0049] Intuitively, 2D transforms are mappings from 2D space to itself. Because of the restricted vocabulary above, however, one can take advantage of widely available low level rendering algorithms and hardware acceleration.

[0050] 3.2 Behaviors

[0051] The type ‘Behavior ’ is a user defined type representing time-varying values of another type where time is continuous (real-valued). Elliott, Conal, and P. Hudak, “Functional Reactive Animation,” Proceedings of the1997 ACM SIGPLAN International Conference on Functional Programming, Amsterdam, The Netherlands, pp. 263-273 (Jun. 9-11, 1997), for example, discusses the semantics of behaviors. A new formulation of some of the primitives are mentioned here.

[0052] ($*) :: Behavior (a -> b) -> Behavior a -> Behavior b

[0053] constantB :: a -> Behavior a

[0054] time :: Behavior Time

[0055] Semantically, these operators correspond to type-specialized versions of the classic SKI combinators.

[0056] The name “$*” comes from the fact that it is the lifted version of function application, whose Haskell infix operator is called “$”.

[0057] The lifting operators from Elliott, Conal, and P. Hudak, “Functional Reactive Animation,” Proceedings of the1997 ACM SIGPLAN International Conference on Functional Programming, Amsterdam, The Netherlands, pp. 263-273 (Jun. 9-11, 1997) are

[0058] and are defined simply in terms of constantB and “$*”, as follows.

[0059] Note that semantically lift1 is function composition.

[0060] Thus lifting promotes an n-ary function to an n-ary function. Semantically, from the definitions above, it follows that

[0061] (liftn f b1 . . . bn) t == f (b1 t) . . . (bn t)

[0062] Efficient implementation of behaviors is a rather tricky matter. Briefly, the current representation of behaviors is as a data structure that contains two aspects. The first is a structural representation intended for analysis and optimization. The second is a sampling representation, which is a lazily memoizing function from time streams to value streams. Hughes, J., “Lazy Memo Functions,” Functional Programming Languages and Computer Architecture, J. P. Jouannaud, editor, volume 201 of LNCS, pp. 129-146, Springer-Verlag (September 1985), which is herein incorporated by reference, discusses lazy memo functions. The representation given here is somewhat simplified from the one used in Fran.

[0063] data Behavior a = Behavior (BStruct a) ([T] -> [a])

[0064] data BStruct a

[0065] = ConstantB a

[0066] | NoStructureB

[0067] | TimeTransB (Behavior a) (Behavior Time)

[0068] | UntilB (Behavior a) (Event (Behavior a))

[0069] deriving Show

[0070] It is not currently possible to capture the SKI structure in a Haskell datatype, because doing so would require an existential type for S (i.e., “$*”) Another trick is needed for I—i.e., time. While S is too polymorphic, I is not polymorphic enough. The trick is to generalize the constructor to be polymorphic, and then define the desired specialization.

[0071] In addition to behaviors, there are some other “behavior-like” types, described by the following type class of “generalized behaviors”.

[0072] class GBehavior bv where

[0073] (By convention, the name of the lifted version of a type is formed by adding a “B” to the end of the unlifted type's name. Thus the types TimeB and BoolB mentioned in the GBehavior type class refer to time- and boolean-valued behaviors respectively.) These operations support reactivity, time transformation, and conditional behaviors, respectively. The last of these is an unoptimized conditional, from which the optimized conditional is defined as follows.

[0074] condB :: GBehavior bv => BoolB -> bv -> bv -> bv

[0075] condB (Behavior (ConstantB True) _) imb _ = imb

[0076] condB (Behavior (ConstantB False) _) _ imb’ = imb’

[0077] condB c imb imb’ = condBUnOpt c imb imb’

[0078] Naturally, behaviors are in the GBehavior class.

[0079] instance GBehavior (Behavior a) where

[0080] condBUnOpt = lift 3 (\ a b c -> if a then b else c)

[0081] Most animated types are defined very simply, by lifting. For instance, here is the type Transform2B of animated 2D transforms.

[0082] module Transform2B where

[0083] import qualified Transform2 as T

[0084] type Transform2B = Behavior T Transform2

[0085] class Transformable2B a where

[0086] (*%) :: Transform2B -> a -> a

[0087] instance T.Transformable2 a => Transformable2B (Behavior a) where

[0088] (*%) =lift2 (T.*%)

[0089] 3.3 Image Animation

[0090] Fran images are spatially continuous and infinite in extent and may contain embedded sounds.

[0091] The type ImageB represents image animation. Some of the types used in the construction of ImageB values are as follows.

[0092] For notational convenience, Fran also provides a few functions for directly transforming ImageB values.

[0093] move :: Transformable2B bv => Vector2B -> bv -> bv

[0094] move dp = (translate2 dp *%)

[0095] stretch :: Transformable2B bv => RealB -> bv -> bv

[0096] stretch sc = (uscale2 sc *%)

[0097] turn :: Transformable2B bv => RealB -> bv -> bv

[0098] turn angle = (rotate2 angle *%)

[0099] In Haskell, an infix operator with one argument but missing the other denotes a function that takes the missing argument and fills it in. In these definitions, the missing argument is the 2D transformable value.

[0100] Displaying an animated image also plays the sounds it contains. Spatial transformation has audible effect; the horizontal component of translation becomes left/right balance, and the scale becomes volume adjustment. Cropping silences sounds outside of the crop region.

[0101] By definition, a renderer not only has the type above, but must also have the following property:

[0102] The “$” operator is an alternative notation for function application. Because it is right-associative and has very low synthetic precedence, it is sometimes used to eliminate cascading parentheses.

[0103] For simple file-based bitmap images, there is also a simple utility that loads a named file, makes a one-page flip-book and applies flipImage:

[0104] importBitmap :: String -> ImageB

[0105] In the early implementations of Fran, ImageB was simply defined to be Behavior Image, for a type Image of static images. This representation made for a very simple implementation, but it has a fundamental problem: the image structure of an ImageB value cannot be determined at the behavior level. It must first be sampled with some time t to extract a static image, whose structure can then be examined. To display an animation then, one must repeatedly sample it, and display the resulting static images. Consequently, the display computation cannot build and maintain data structures and system resources for parts of an animation. In particular, it cannot allocate one sprite for each flipImage and renderImage, set them moving, and then update the motion paths incrementally. That is, the implementation cannot take advantage of sprite engine 240 running in a separate thread.

[0106] It appears then that the modularity imposed by lifting it requires an underlying “immediate mode,” rather than “retained mode,” presentation library, to borrow terms from 3D graphics programming. In designing Fran, however, the upcoming generation of graphics accelerator cards which are believed to be increasingly oriented toward retained mode were targeted. Of special interest is the sprite-based Talisman architecture as described, for example, in Torborg, Jay, and J. Kajiya, “Talisman: Commodity Real-time 3D Graphics for the PC,” SIGGRAPH96 Conference Proceedings, Addison Wesley, Holly Rushmeier, editor, ACM SIGGRAPH, Annual Conference Series, New Orleans, La., pp. 353-364 (Aug. 4-9, 1996). The sprite-based Talisman architecture performs transformation and overlaying of sprites with blending and high-quality anisotropic image filtering, without requiring a screen-size frame buffer.

[0107] For reasons given above, the ImageB is not represented in terms of a static Image type, but rather as its own recursively defined data type.

[0108] Image animations are generalized behaviors:

[0109] instance GBehavior ImageB where

[0110] untilB = UntilI

[0111] timeTransform = TimeTransI

[0112] condBUnOpt = CondI

[0113] They are also transformable. The definition below includes a simple optimization, namely transformation of the empty image. Although a programmer would not be likely to transform empty images explicitly, such compositions arise at runtime due to modular programming style, as well as some reactivity optimizations.

[0114] instance Transformable2B ImageB where

[0115] _ *% EmptyImage = EmptyImage

[0116] xf*% im = xf ‘TransformI‘ im

[0117] The other ImageB operators are defined similarly, applying simple optimizations or the corresponding constructor.

[0118] 3.4 Sound

[0119] Fran has a fairly simple type SoundB of “animated sounds.” Its building blocks are similar to those of ImageB.

[0120] Representation of SoundB via lifting is problematic both conceptually and pragmatically. Conceptually, it is unclear what is a useful and implementable notion of static sound. Pragmatically, as with ImageB, a lifting-based implementation would require an immediate mode presentation library, but known libraries such as DirectSound® by Microsoft® Corporation are retained mode. See, e.g., Microsoft® Corporation and Peter Donnelly, Inside DirectX®, Microsoft Press® (1998), which is herein incorporated by reference. DirectSound® provides interfaces to allocate sound buffers in either main memory, such as RAM 125 of FIG. 1, or the memory of audio adapter 158, for example, and direct the sound buffers to be mixed and played. The client program can then optionally adjust the sound buffers' volume, frequency, and left/right balance attributes. A retained mode architecture is especially desirable for sound, because it is difficult for an application program to keep the hardware's sound buffers filled and perform or direct mixing and output in a timely enough fashion to avoid buffer overflow or underflow, both of which have easily discernible effects. A lazy functional program would have particular difficulty because of unpredictable interruptions due to garbage collection and evaluation of postponed computations. DirectSound® creates a few highest-priority threads that feed buffers and adjust registers in the sound hardware.

[0121] The representation of SoundB is as a recursive data type.

[0122] Animated sounds are generalized behaviors as well. Conditional is implemented by mixing two sounds with applied volumes that silence one or the other, depending on the boolean behavior. (With—blending for transparency, an analogous implementation of conditional image animations would be possible. Alternatively, one could use stretch.)

[0123] instance GBehavior SoundB where

[0124] untilB = UntilS

[0125] timeTransform = TimeTransS

[0126] condBUnOpt c snd snd’ =

[0127] volume v snd ‘mix‘ volume v’ snd’

[0128] where

[0129] v = condB c 1 0

[0130] v′ = 1 − v

[0131] 3.5 3D Animation

[0132] Many 3D graphics presentations libraries also have a retained-mode structure, e.g., Inventor by Silicon Graphics, Inc. as described, for example, in Strauss, Paul S. and R. Carey, “An Object-Oriented 3D Graphics Toolkit,” Computer Graphics, Vol. 26, No. 2, pp. 341-349 (July 1992), and Performer by Silicon Graphics, Inc. as described, for example, in Rohlf and J. Helman, “IRIS Performer: A High Performance Multiprocessing Toolkit for Real-Time 3D Graphics,” Proceedings of SIGGRAPH '94, ACM Press, Andrew Glassner, editor, Computer Graphics Proceedings, Annual Conference Series, Orlando, Fla., pp. 381-395 (Jul. 24-29, 1994), and Direct3DRM by Microsoft® Corporation as described, for example, in Glidden, Rob, Graphics Programming With Direct3D®: Techniques and Concepts, Addison-Wesley (1996). Fran for one embodiment uses Direct3DRM to display its type GeometryB of animated 3D geometry. Its structure is much like ImageB and SoundB.

[0133] 4. Sprite Engine 240

[0134] The primary purpose of sprite engine 240 is to scale, move, and overlay a sequence of images, and to do so at a very high and regular rate near video refresh rate. Because animations may involve arbitrarily complex behaviors and because garbage collection and lazy evaluation cause unpredictable delays, this goal could not be met if the window refresh were implemented in Haskell or even invoked by a Haskell program. For these reasons, sprite engine 240 for one embodiment is implemented in C++, does no memory allocation, and runs in its own thread. Sprite engine 240 for one embodiment is implemented with the C++ programming language.

[0135] 4.1 Sprites and Sprite Trees

[0136] Sprite engine 240 maintains an ordered collection of sprites, represented for one embodiment via a C++ class hierarchy. Exemplary classes representing individual sprites are as follows.

[0137] FlipSprite has a bitmap that is selected from a “flip book” object. Each flip book contains a pointer to a bitmap (e.g., a DirectDraw® surface) stored in video memory, and information describing a rectangular array of images contained somewhere within the images. This array is taken to be a linear sequence of consecutive “pages”. Flip books and the images to which they refer are immutable and may be shared among any number of flip sprites. The current page number, spatial transform, and cropping rectangle are all stored in the unshared sprites rather than the shared flip book.

[0138] RenderedSprite has its own drawing surface and a method for replacing the surface with a new one. This sprite is used for all “rendered” images, such as text, 2D geometry, and 3D geometry viewed through a camera.

[0139] SolidSprite is a uniformly colored sprite, cropped but not spatially transformed.

[0140] SoundSprite is an embedded sound, and is neither cropped nor transformed. It contains a DirectSound® “duplicate” sound buffer and volume, frequency, and left/right balance attributes. A duplicate buffer is a DirectSound® object that contains a pointer to (typically immutable) shareable sound data, plus its own unshared attributes for volume, frequency, and left/right balance.

[0141] A displayed animation could be represented by a list of individual sprites, in back-to-front order, so that upper (later) sprites end up painted over lower (earlier) sprites. This representation is the simplest for display, but is awkward for editing. When an event occurs in an animation, an animated object may be introduced, removed, or replaced. Since the appearance of such a component may contain any number of image and sound sprites, the event may introduce, remove, or replace a whole contiguous subsequence of sprites.

[0142] Sprite engine 240 makes it easy and fast to edit the sprite list at a conceptual level by using a list of sprite trees 232, as illustrated in FIG. 3, rather than a list of individual sprites. The list of sprite trees 232 comprise leaf nodes 234 and edit nodes 236. Leaf nodes 234 each correspond to an individual sprite. Edit nodes 236 each correspond to one or more related sprites as represented by any leaf nodes 234 or edit nodes 236 emanating from the edit node 236. Edit nodes 236 correspond exactly to the points of structural (as opposed to parametric) mutability of the animation being displayed. (For Fran's use, the points of mutability are generated from the reactivity construct “untilB”) Correspondingly, there is a SpriteTree subclass SpriteGroup that contains a list of sprite trees and supports a method to replace the list, in its entirety, with another one. Sprite engine 240 for one embodiment requires that there be no structure sharing, so the old list and all of its elements are recursively deallocated. Lack of sharing also allows direct linking of sprite trees. Each sprite tree contains a next pointer.

[0143] For conditional animations, such as generated by Fran's “condB”, there is a SpriteTree subclass CondSpriteTree, which contains an externally mutable boolean and two sprite tree lists.

[0144] Sprite engine 240 expects sprite trees 232 to be updated less often than they are redrawn. For example, Fran tries to sample behaviors at roughly ten times per second and sends updates to sprite engine 240. Between updates, sprite engine 240 performs linear interpolation of all sprite attributes, which are actually represented as linear functions rather than constant values. For smoothness, updates must then be given for times in the future, so that the a new linear path may be set from the current time and value to the given one. These linear behaviors form a compromise between arbitrary behaviors, which have unpredictable sampling requirements, and mere constant values, which fail to provide smooth motion. Other possible compromises include quadratic and cubic curves, for which fast incremental sampling algorithms may be used.

[0145] As one example with reference to FIG. 4, application 210 specifies the animation of a point moving along a sine curve path 211. At time t₀, the position value of the sprite for the point is updated to x₀by normalizer 230. At time t₁or approximately one-tenth of a second after time t₀, the position value of the sprite for the point is updated to x₁by normalizer 230. At time t₂or approximately one-tenth of a second after time t₁, the position value of the sprite for the point is updated to x₂by normalizer 230. Normalizer 230 similarly updates the position value of the sprite for the point at times t₃, t₄, t₅. Rather than presenting the movement of the point at each position value x₀, X₁, X₂, X₃, . . . sprite engine 240 linearly interpolates the position value of the sprite for the point at each approximately one-sixtieth of a second interval between each pair of update times t₀, t₁, t₂, t₃, . . . and accordingly updates the position value of the sprite every approximately one-sixtieth of a second to present a relatively smoother movement of the point by presentation library 250 and presentation hardware 260.

[0146] In performing the linear interpolation of the position value of the sprite for the point between update times t₀and t₁, for example, sprite engine 240 determines each linearly interpolated position value x as x=x₀+(t-t₀)*rate, where rate=(x₁-x₀)/(t₁-t₀) and t is the time at which the sprite for the point is to be presented with the new linearly interpolated position value x. The time t is incremented in approximately one-sixtieth of a second intervals. The linearly interpolated position values are illustrated in FIG. 4 as linear paths l₁,l₂,l₃, . . .

[0147] The main loop of sprite engine 240 is then to traverse sprite tree list 232 recursively and in depth-first, back-to-front order. Each image sprite in turn is told to paint itself, and in doing so samples its attributes' linear functions and then does a very fast “blit” (copy). Sound sprites are “painted” by updating the DirectSound ® buffer attributes. Updating is double buffered to avoid visible image tearing. Thus the blitting is done to a “back buffer”, which is a video memory surface being the same size as the display window. When all of the sprites have been painted, the back buffer is blitted to the front (visible) buffer. Given a modern video card with adequate video RAM and hardware stretching, these operations are extremely fast.

[0148] 4.2 Interpretation of Sprite Trees

[0149] The goal of ImageB display is first to “spritify”, i.e., convert an abstract ImageB value to a initial list of sprite trees 232 and then update the trees iteratively. Concurrently, sprite engine 240 traverses and displays sprite trees 232. Sprite trees 232 for one embodiment are implemented in C++, yet for the purpose of exposition are expressed as the following Haskell type definitions.

[0150] type SpriteTrees = SpriteTree]

[0151] In order to define “correct” conversion, an interpretation of sprite tree lists is needed. This interpretation may be specified by mapping sprite tree lists to ImageB values. Note that this mapping is hypothetical, serving to (a) specify what sprite engine 240 does, and (b) justify the implementation in Section 5 of the reverse mapping, i.e., from ImageB values to sprite tree lists.

[0152] Note that SpriteTrees type almost fits the GBehavior style, but not quite. Instead, it matches the data structure of sprite engine 240.

[0153] The interpretation functions are as follows.

[0154] treesIm :: SpriteTrees -> ImageB

[0155] treesIm [ ] = emptyImage

[0156] treesIm (bot : above) = treesIm above ‘above‘ treeIm bot

[0157] treeIm :: SpriteTree -> ImageB

[0158] treeIm (SoundSprite soundB) = soundImage soundB

[0159] treeIm (RenderedSprite motionB surfaceB) =

[0160] move motion (surfaceIm surfaceB)

[0161] treeIm (SolidSprite rectB colorB) =

[0162] crop rectB (withColor colorB solidImage)

[0163] treeIm (trees ‘UntilBT‘ e) =

[0164] treesIm treesIm ‘untilB‘ e ==> treesIm

[0165] treeIm (CondT c trees trees’) =

[0166] condB c (treesIm trees) (treesIm trees’)

[0167] The function treesIm is the main interpretation function, and says that a list of sprite trees 232 represents an overlay of the images represented by the member trees, in reverse order. This reversal reflects the fact that the sprite tree lists 232 are in back-to-front order so that sprite engine 240 can paint sprite trees 232 in list order. Later (upper) sprite trees are then painted over earlier (lower) sprite trees.

[0168] The first four clauses of the treeIm function interpret individual sprites. Note the rigidity of order of applied operations imposed by the sprite constructors, as contrasted with the flexibility afforded by the ImageB type from Section 3.3.

[0169] The UntilBT case says that a reactive sprite tree represents a reactive image animation. This animation is initially the one represented by the initial sprite tree. When the event occurs, yielding a new sprite tree list, the animation switches to the one represented by these new sprite trees. The conditional case is similar.

[0170] 5. From Abstract Animations to Sprite Trees

[0171] The interpretation of sprite tree lists as image animations given above helps to specify the reverse process, which is implemented by normalizer 230 so that sprite engine 240 may be used to display animations. This algorithm works by recursive traversal of ImageB values, accumulating operations that are found out of order. The type and specification are as follows.

[0172] spritify :: SpriteTrees -> RectB -> Maybe ColorB -> Transform2B

[0173] -> TimeB -> ImageB -> SpriteTrees

[0174] That the algorithm given below satisfies this specification may be proved by induction on the ImageB representation. Rather than give the algorithm first and then the proof, the algorithm is instead derived from the specification so that it is correct by construction. Many simple algebraic properties of the data types are relied upon. These properties may be taken as axioms or proved from semantic models of the data types.

[0175] Normalizer 230 for one embodiment is implemented with the Haskell source code.

[0176] 5.1 Solid Images

[0177] Consider the following facts about solid images.

[0178] SolidImage ‘timeTransform‘ tt == SolidImage

[0179] xfB *% SolidImage == SolidImage

[0180] withColor defaultColor SolidImage = SolidImage

[0181] These facts simplify the specification of spritify:

[0182] treesIm (spritify above rectB mbColorB xfB tt SolidImage) ==

[0183] treesIm above ‘over‘

[0184] crop rectB (withColor (chooseColorB mbColorB) SolidImage)

[0185] where

[0186] chooseColorB :: Maybe ColorB -> ColorB

[0187] chooseColorB Nothing = defaultColor

[0188] chooseColorB (Just c) = c

[0189] Now considering the interpretation of SolidSprite, the specification simplifies further:

[0190] treesIm (spritify above rectB mbColorB xfB tt SolidImage) ==

[0191] treesIm above ‘above‘

[0192] treeIm (SolidSprite rectB (chooseColorB mbColorB))

[0193] Finally, recall from the definition of treesIm that

[0194] treesIm (bot : above) == treesIm above ‘over‘ treeIm bot

[0195] The specification then becomes

[0196] treesIm (spritify above rectB mbColorB xfB tt SolidImage) ==

[0197] treesIm (SolidSprite rectB (chooseColorB mbColorB) : above)

[0198] This final simplification then directly justifies the SolidImage case in the spritify algorithm.

[0199] spritify above rectB mbColorB xfB tt SolidImage =

[0200] SolidSprite rectB (chooseColorB mbColorB) : above

[0201] 5.2 Rendered Images

[0202] Because of their spatially continuous nature, ImageB values may be thought of as being constructed bottom-up, whereas their implementation via spritify is top-down. This difference is especially clear in the treatment of rendered images.

[0203] Although sprite engine 240 can perform scaling as well as translation, the scaling it does is necessarily approximate, i.e., it scales discrete images. With a rendered image, however, the rendering operation itself should produce a discrete image of the appropriate resolution. For this reason, the transform behavior should be factored into translation, scale, and rotation. Fran's factorTransform2 function does just this:

[0204] xfB == translate motionB ‘compose2‘

[0205] uscale scaleB ‘compose2‘

[0206] rotate angleB

[0207] where

[0208] (motionB, scaleB, angleB) = factorTransform2 xfB

[0209] Moreover, the meaning of transform composition is function composition:

[0210] (xfB ‘compose2‘ xfB’) *% thing == xfB *% (xfB’ *% thing)

[0211] Factoring the spatial transform and turning transform composition into function composition, the specification becomes the following.

[0212] where

[0213] (motionB, scaleB, angleB) = factorTransform2 xfB

[0214] Next, since renderers do not perform motion, the move must be extracted from within applications of withColor and crop, as justified by the following properties.

[0215] withColor c (xfb *% imb) == xfb *% (withColor c imb)

[0216] crop rectB (xfb *% imb) == xfb *% crop (inverse2 xfb *% rectB) imb

[0217] The definition of a renderer in Section 3.3 then leads to the following rule for spritifying rendered images.

[0218] spritify above rectB mbColorB xfB tt (RenderImage renderer) ==

[0219] RenderedSprite motionB

[0220] (renderer (move (-motionB) rectB)

[0221] mbColorB scaleB angleB tt)

[0222] above

[0223] where

[0224] (motionB, scaleB, angleB) = factorTransform2 xfB

[0225] 5.3 Flip-book Animation

[0226] A similar analysis to the one for SolidImage above applies to flip book animation. Fran imposes two restrictions on flip-book animations (and the special case of constant bitmaps). First, they may not be colored, and second, they may not be rotated. Simplifying the spritify specification under these assumptions yields the following.

[0227] where

[0228] (motionB, scaleB, constantB 0) = factorTransform2 xfB

[0229] The spritify specification can be simplified further, using the following facts.

[0230] mbWithColor Nothing imb == imb

[0231] turn (constantB 0) imb == imb

[0232] (flipImage book pageB) ‘timeTransform‘ tt ==

[0233] flipImage book (pageB ‘timeTransform‘ tt)

[0234] After applying these properties, the specification matches the interpretation of FlipSprite, resulting in the following rule for flipImage.

[0235] spritify above rectB _ xfB tt (FlipImage book pageB) =

[0236] FlipSprite rectB motionB scaleB

[0237] book (pageB ‘timeTransform‘ tt)

[0238] : above

[0239] where

[0240] (motionB, scaleB, _) = factorTransform2 xfB

[0241] 5.4 The Empty Image

[0242] The empty image is trivially spritified, because (a) time transformation, space transformation, coloring, and cropping all map the empty image to itself, and (b) the empty image is the identity for over.

[0243] spritify above _———— EmptyImage = above

[0244] 5.5 Overlays

[0245] The treatment of overlays follows from the distribution of time transformation, space transformation, coloring, and cropping over the over operation, plus the associativity of over.

[0246] spritify above rectB mbColor xfB tt (top ‘Over‘ bot) =

[0247] spritify above’ rectB mbColor xfB tt bot

[0248] where

[0249] above’ = spritify above rectB mbColor xfB tt top

[0250] 5.6 Time Transformation

[0251] Spritifying a time transformed animation is relatively simple because of the following composition property.

[0252] (imb ‘timeTransform‘ tt’) ‘timeTransform‘ tt ==

[0253] imb ‘timeTransform‘ (tt’ ‘timeTransform‘ tt) ==

[0254] Thus:

[0255] spritify above rectB mbColor xfB tt (TimeTransI imb tt’) =

[0256] spritify above rectB mbColor xfB (tt’ ‘timeTransform‘ tt) imb

[0257] 5.7 Space Transformation

[0258] Space and time transformation do not commute, but the following property holds.

[0259] (xfB *% imb) ‘timeTransform‘ tt ==

[0260] (xfB ‘timeTransform‘ tt) *% (imb ‘timeTransform‘ tt)

[0261] Space transforms compose:

[0262] xfB *% (xfB’ *% imB) == (xfB ‘compose2‘ xfB’) *% imB

[0263] The rule for TransformI then follows easily.

[0264] spritify above rectB mbColor xfB tt (xfB’ ‘TransformI‘ imb) =

[0265] spritify above rectB mbColor tt

[0266] (xfB ‘compose2‘ (xfB’ ‘timeTransform‘ tt))

[0267] 5.8 Coloring

[0268] The treatment of withColor follows from the following commutativity-like properties and combination rule. (Note that in the case of nested colorings, the outer ones win, in contrast to many graphics libraries. The reason is that the informal model of coloring is to simply paint over what is already present. The conventional, innermost-wins policy is simpler to implement, but has arguably more complex semantics.)

[0269] (withColor c imb) ‘timeTransform‘ tt ==

[0270] withColor (c ‘timeTransform‘ tt) (imb ‘timeTransform‘ tt)

[0271] xf *% withColor c imb == withColor c (xf *% imb)

[0272] withColor c (withColor c’ imb) == withColor c imb

[0273] Then

[0274] spritify above rectB mbColor xfB tt (withColor color’ imb) =

[0275] spritify above rectB mbColor’’ xfB tt imb

[0276] where

[0277] mbColor’’= mbColor ++ Just (color’ ‘timeTransform‘ tt))

[0278] The Haskell operation “++” on Maybe is defined as follows.

[0279] Nothing ++ mb = mb

[0280] Just x ++ _ = Just x

[0281] 5.9 Cropping

[0282] Cropping works very much like space transformation and coloring, justified by analogous properties.

[0283] (crop rectB imb) ‘timeTransform‘ tt ==

[0284] crop (rectB ‘timeTransform‘ tt) (imb ‘timeTransform‘ tt)

[0285] xf *% crop rectB imb == crop (xf *% rectB) (xf *% imb)

[0286] crop rectB (crop rectB’ imb) ==

[0287] crop (rectB ‘intersectRect‘ rectB’) imb

[0288] Then

[0289] spritify above rectB mbColor xfB tt (CropI rectB’ imb) =

[0290] spritify above rectB’’ mbColor xfB tt imb

[0291] where

[0292] 5.10 Conditional Animation

[0293] The rule for spritifying a conditional animation relies on several distributive properties.

[0294] (condB boolB thenB elseB) ‘timeTransform‘ tt

[0295] == condB

[0296] (boolB ‘timeTransform‘ tt)

[0297] (thenB ‘timeTransform‘ tt)

[0298] (elseB ‘timeTransform‘ tt)

[0299] xf *% (condB boolB thenB elseB)

[0300] == condB boolB (xf *% thenB) (xf *% elseB)

[0301] withColor c (condB boolB thenB elseB)

[0302] == condB boolB (withColor c thenB) (withColor c elseB)

[0303] crop rectB (condB boolB thenB elseB)

[0304] == condB boolB (crop rectB thenB) (crop rectB elseB)

[0305] The rule:

[0306] spritify above rectB mbColor xfB tt (CondI c imb imb’) =

[0307] CondT c

[0308] (spritify [ ] rectB mbColor xfB tt imb)

[0309] (spritify [ ] rectB mbColor xfB tt’ imb)

[0310] : above

[0311] The animations imb and imb’ are spritified with an empty above list, and the whole conditional sprite tree is placed under the given above sprites. Alternatively, the animations imb and imb’ may be spritified each with the given above list, and a singleton CondT sprite tree list may be made. The implementation above preserves the invariant that sprite tree structure is never shared (Section 4.1).

[0312] 5.11 Reactive Animation

[0313] Reactive animations are spritified in much the same way as conditional animations, justified by analogous properties. The rule:

[0314] spritify above rectB mbColor xfB tt (imb ‘UntilI‘ e) =

[0315] UntilBT (spritify [ ] rectB mbColor xfB tt imb)

[0316] (e ‘afterE‘ (rectB, mbColor, xfB, tt) ==>

[0317] \ (imb’, (rectB’, mbColor’, xfB’, tt’)) ->

[0318] spritify [ ] rectB’ mbColor’ xfB’ tt’ imb’)

[0319] above

[0320] The afterE combinator gives access to the “residual”, or “aged” version, of a value of a GBehavior type upon the occurrence of an event. Using the unaged behaviors instead would cause a time-space leak, since the behaviors would be held onto from their beginning while waiting for the event to occur.

[0321] 5.12 Embedded Sound

[0322] Image-embedded sounds are spritified by generating a collection of sound sprites. In Fran, the pan (left/right balance), and the volume are influenced by the spatial transform being applied. If the sound's location is outside of the cropping rectangle then it is silenced. (The operator “+{circumflex over ( )}” is point/vector addition.)

[0323] spritify above rectB _ xfB tt (SoundI sound) =

[0324] spritifySoundB above vol pan pitch tt sound

[0325] where

[0326] (motion, scale, _) = factorTransform2 xfB

[0327] - - Pan based on x coordinate. The 7.0 is empirical.

[0328] pan = 7.0 * fst (vector2XYCoords motion)

[0329] -- Volume is based on scale, possibly silenced by cropping

[0330] vol = ifB

[0331] (rectContains rectB (origin2 +{circumflex over ( )} motion))

[0332] (abs scale) 0

[0333] pitch =1

[0334] The new sound conversion function spritifySoundB is specified and implemented much like spritifying image animations. The specification:

[0335] spritifySoundB :: SpriteTrees -> RealB -> RealB -> RealB

[0336] -> TimeB -> SoundB -> SpriteTrees

[0337] The following implementation is somewhat simpler than that of spritify, because of the independence of the operations for adjusting pan, volume, and pitch.

[0338] spritifySoundB above _——— SilentS = above

[0339] spritifySoundB above volB panB pitchB tt (BufferS buff repeat) =

[0340] SoundSprite volB panB pitchB repeat buff : above

[0341] spritifySoundB above volB panB pitchB tt (sound ‘MixS‘ sound’) =

[0342] spritifySoundB above’ volB panB pitchB tt sound’

[0343] where

[0344] above’ = spritifySoundB above volB panB pitchB tt sound

[0345] spritifySoundB above volB panB pitchB tt (sound ‘TimeTransS‘ tt’) =

[0346] spritifySoundB above volB panB pitchB (tt’ ‘timeTransform‘ tt)

[0347] sound

[0348] spritifySoundB above volB panB pitchB tt (VolumeS v sound) =

[0349] spritifySoundB above (volB * v ‘timeTransform‘ tt)

[0350] panB pitchB tt sound

[0351] spritifySoundB above volB panB pitchB tt (PanS p sound) =

[0352] spritifySoundB above volB

[0353] (panB + timeTransform p tt)

[0354] pitchB tt sound

[0355] spritifySoundB above volB panB pitchB tt (PitchS p sound) =

[0356] spritifySoundB above volB panB

[0357] (pitchB * p ‘timeTransform‘ tt)

[0358] tt sound

[0359] spritifySoundB above volB panB pitchB tt (sound ‘UntilS‘ e) =

[0360] UntilBT (spritifySoundB [ ] volB panB pitchB tt sound)

[0361] (e ‘afterE‘ (volB, panB, pitchB, tt) ==>

[0362] \ (sound’, (volB’, panB’, pitchB’, tt’)) ->

[0363] spritifySoundB [ ] volB’ panB’ pitchB’ tt’ sound’)

[0364] : above

[0365] 5.13 State and Concurrent Updating

[0366] The spritifying algorithms above are idealized in that they construct immutable sprite tree lists containing Fran behaviors. In fact, the sprite engine's data structures are mutable, both parametrically and structurally, and only accommodate linear behaviors. The implementation of spritify and spritifySound create the mutable sprite trees with initial constant parameters for position, scale, pitch, etc., and then iteratively update these parameters, while the sprite engine runs concurrently. For simplicity of implementation, every active sprite is managed by its own Haskell thread, using the Concurrent Haskell primitives as described, for example, in Jones, Simon Peyton, and A. Gordon and S. Finne, “Concurrent Haskell,” Conference Record of POPL '96: The23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St. Petersburg Beach, Fla., pp. 295-308 (Jan. 21-24, 1996). Each such thread is fueled by a request channel, each of which says either to continue or to quit, and puts status messages into a response channel. Each sprite thread iteratively samples the appropriate behaviors (slightly into the future) and invokes an update method on the sprite object. In response, the sprite engine charts a new linear course for each parameter.

[0367] The handling of a reactive image animation, imb ‘untilB‘ e, is somewhat tricky. The initial animation imb is spritified, starting any number of (Haskell) threads. The resulting sprite tree list is wrapped up in a SpriteGroup object (corresponding to the UntilBT constructor in the Haskell type definition). One more thread runs to watch for event occurrences and causes the update work corresponding to imb to continue until the first occurrence of the event e, and then to stop. At that point, a new animation is available and is spritified, generating a new sprite tree list, which is then passed to a method on the SpriteGroup object that recursively deletes its old list and installs the new one. The number of running threads thus varies in response to events. Because every thread has accompanying overhead for controlling its work, a useful optimization would be to create many fewer threads.

[0368] As one example where application 210 contains the following Haskell source code supported by Fran:

[0369] pat = importBitmap “pat.bmp”

[0370] jake = importBitmap “jake.bmp”

[0371] anim=

[0372] stretch 0.5 (

[0373] moveXY (−2) 0 pat ‘over‘

[0374] stretch 4 (

[0375] circle ‘over‘ moveXY 0 1 jake)

[0376] and functional animation data types 222 therefore comprise data types 500 as illustrated in FIG. 5, normalizer 230 constructs a sprite tree list 600 having three sprite trees 602, 604, 606 as illustrated in FIG. 6 based on data types 500, noting circle with radius 2 refers to a rendered image. Normalizing data types 500 can be thought of as turning anim into the following equivalent image:

[0377] norm =

[0378] moveXY (−1) 0 (stretch 0.5 pat) ‘over‘

[0379] moveXY 0 0 (stretch 2 circle) ‘over‘

[0380] moveXY 0 2 (stretch 2 jake)

[0381] to construct the sprite tree list 600.

[0382] Provisional application serial No. 60/093,487 includes a Haskell source code listing (Appendix K) that implements the normalizer 230. The listing of Appendix K is incorporated herein by reference. The process of converting an animation representation to a sprite tree list such as the list of FIG. 6 converts the arbitrary composition of image and sound constructors into a normal form which can be viewed as being in ‘sprite normal form’. The normalizer 230 exploits the algebraic properties of the image and sound algebras to make the conversion to a sprite tree list 600.

[0383] The normalizer is implemented as a number of case statement-like functions that evaluate correct Fran based animations. The normalizer checks against each of a series of ‘spritifyImageB’ function implementations. The result of a match between the form of the function can produce either of two results. If the matching spritifyImageB function is on a solidimage, for example, the spritifyImageB function produces a sprite tree (in this instance of one node) and adds that sprite tree to the head of a list of such sprite trees. This is an instance where the spritifyImageB function produces a terminal sprite tree.

[0384] An alternative result of the matching of one of the multiple number of spritifyImageB is a recursive call to spritifyImageB. The example Fran statement “anim = stretch 0.5 (moveXY (−2) 0 pat ‘over’ stretch 4 (circle ‘over’ moveXY 0 1 jake))” results in such a recursive call. One of the spritifyImageB implementations from Appendix K is listed below:

[0385] spritifyImageB rectB mbColor xfB (TransformI xfB’ imb) mbTT t0 =

[0386] spritifyImageB rectB mbColor (xfB ‘compose2’ mbTTrans xfB’ mbTT)

[0387] Imb mbTT t0.

[0388] The lowercase items rectB mbColor and xfB correspond to variables so that in attempting to match the Fran statement “anim = . . . (above)” the normalizer sees the statement to the left of the equal sign as:

[0389] spritifyImageB windowrect nothing identity2 (stretch 0.5 . . . ) t0. When the user requests a display of the animation, the display operation invokes spritifyImageB and in doing so provides all arguments to spritifyImageB. The rectB argument is the display window's rectangle. The mbColor is nothing (denoting that no color has been applied) and the xfB argument is identity2 (denoting no transform has been applied). The fourth argument is anim itself The mbTT is nothing, denoting no time transform has been applied and the argument t0 is the current time. This results in the recursive call to the spritifyImageB function defined by the matching function. As noted previously, the recursive calls continue until a terminal spritifyImageB match is identified. Such a terminal match causes the normalizer 230 to produce a sprite tree (possibly having only one sprite such as a flip sprite) and add that sprite tree to the list of such sprite trees maintained by the normalizer. The recursive traversal of the spritifyImageB functions causes the first sprites of the list of sprite trees to be painted first by the sprite tree engine and the later sprite of the sprite tree list to be ‘painted’ later so that for example, the flipsprite ‘pat.bmp’ of the flipsprite 606 (FIG. 6) will be painted after the bitmapped image jake.bmp of the flipsprite 602. The process of updating the sprite tree list occurs in its own operating system thread and as noted above it occurs at a rate slower than the rate at which the sprite tree engine converts the list 600 into an image.

[0390] It is noted that sound is also handled by the normalizer 230 since there is a spritify function implemented for sound and the sound and images are contained on a resultant sprite tree list so that when the sprite tree engine encounters a sound sprite the rendering hardware for emitting a sound is properly activated.

[0391] The Fran application that is interpreted by the normalizer 230 typically does not produce only one sprite. The typical animation is more likely a sequence of sprites (for various body parts, vehicles, tools etc). When a significant event occurs in the application (possibly in response to a mouse click or movement) editing of the sprite tree lists are required. Sprite sub-sequences (referred to as spritegroups) corresponding to an application object need to be inserted or removed from the sprite tree list. If the multiple sprites were organized as a linear representation of the sprite collection of the objects, the normalizer would have to perform an insertion or deletion at an arbitrary location of the sequence or to find the start and end points of a sprite subsequence to delete. This information is difficult to keep track of since the objects of the list change in response to activity by animation objects whose sprites exist in the list.

[0392] The exemplary normalizer 230 implements the sprite tree lists in a way that makes it relatively easier to perform editing of the lists. Certain of the cases of the spritify function build sprite trees with internal nodes representing points of structural mutability of the animation being presented. Such a point of mutability serves as an anchor for a sprite tree list. The normalizer may (depending on events that may occur) replace the list anchored at this point of mutability with another such list as needed. A contiguous subsequence of sprites for an animated object may therefore be introduced, removed, or replaced without the necessity of reconstructing the entire list. The spritify function on an imageB data type that implements this structure is the case including the ‘until’ Fran Construct.

[0393] From appendix K of the provisional application this construct is:

[0394] spritifyImageB rectB mbColor xfB (imb1 ‘UntilI’ e) mbTT t0 =

[0395] spritifyUntilB (\ (rectB,mbC,xfB) imb1 -> spritifyImageB rectB mbC xfC xfB imb1)

[0396] (rectB, mbColor, xfB) imb1 e mbTT t0

[0397] This statement creates two sprite tree lists, one to send to the sprite tree list created by the normalizer before the event e and a second sprite tree list to sent to the sprite tree list created by the normalizer after the event e.

[0398] A second example useful for describing the animation process of the invention is an animation that displays a bitmapped image (obtained from a suitable source such as a file on a computer disk) moving along a path of circular motion on the video monitor 147. Four appendices (A-C, F) contained in provisional application serial No. 60/093,487 that are incorporated herein by reference contain source code for implementing an exemplary embodiment of the sprite engine. Those listings contain copyrighted material owned by the assignee of the present invention. Reference is also made to the Dr. Dobbs article incorporated by reference in this application which describes use of the functional programming language FRAN to define circular motion as well as other functions which can be combined to define more complex animations.

[0399] The Fran code for circular motion:

[0400] moveXY waggle wiggle (importBitmap “pat.bmp”), where

[0401] wiggle = sin (pi * time); and

[0402] waggle = cos (pi * time).

[0403] Recall that one goal of the invention is to convert this functional animation program that defines the animation into data that can understood by the rendering hardware such as the video adapter 148 and audio adapter 158 of FIG. 1.

[0404] The normalizer 230 runs at a rate appreciably slower than the sprite engine 240. It transforms the simple FRAN program of listing 1 through a series of conversions into a form suitable for interpretation by the sprite engine. First expand the definitions of moveXY and importBitmap:

[0405] v = vector2xy waggle wiggle

[0406] Im1 = TransformI (Translate2v) (FlipImage patBook)

[0407] Then:

[0408] Spritify[ ] windowRect nothing identity2 im1

[0409] => Spritify[ ] windowRect nothing (Translate2 v) (FlipImage patBook 0)

[0410] =>[ FlipSprite windowRect v 1 ( patBook 0) ]

[0411] For the case of circular motion of a single bitmapped image, the normalizer 230 constructs a sprite tree that includes a single instance of the flipsprite class with only window cropping, circular motion (translation) and a scale of 1. There are no overlays so there is only a single sprite tree and since there is only one image, the flipsprite has a single page. In many animations, however, there will be a linked list of sprite trees having multiple nodes (See FIG. 3). After creation of the sprite tree list by the normalizer, the sprite engine 240 traverses the sprite tree list from first to last to update an output buffer in the video adapter 148.

[0412] FIGS. 7A and 7 B are flowcharts 230′, 240′ showing the operations of the normalizer 230 and the sprite engine 240, each of which run in its own thread in a multitasking operating system. The functionality of the normalizer 230 is depicted in FIG. 7B. The normalizer is written in Haskel but interfaces to C++ data structures and also calls certain of the functions that are implemented in C++. The normalizer interpreprets the Haskell code 232 for accomplishing the animation and performs its spritify function 234 on an ImageB data type to produce one or more sprite trees 236. In an instance of multiple trees the normalizer forms a linked list of sprite trees. For an instance of circular motion the normalizer produces a single flipsprite which is a tree with one node. This updating of the sprite tree list takes place at a first rate which in one presently preferred embodiment for practicing the invention occurs every {fraction (1/10)} second.

[0413] In FIG. 7A, one sees the steps performed by the sprite tree engine 240. The sprite tree engine writes to an output buffer at a rate at least once every sixtieth of a second. The sprite tree engine initially clears 242 the output buffer in video memory. The buffer is a so-called back buffer since the bitmapped image created in this portion of memory is not displayed, but instead serves as a holding location that is updated as the list of sprite trees is traversed. The sprite tree engine repeatedly accesses 244 the sprites of the sprite tree and updates 246 a video buffer. Once the entire tree list has been traversed the contents of the back buffer are transferred 248 to video memory by a rapid transfer (a blit).

[0414] The definition of an instance of type Flipsprite for the circular motion example is contained above. An object of type Flipsprite includes a pointer to a instance of type Flipbook which defines a bitmapped image in video memory. The instance of class Flipsprite inherits from the type TransformableSprite which contains two protected fields of type LinearDouble designated as ‘m_posX’ and ‘m_posY’. These values are the positions of the sprite and are instantiated by a constructor function when the Flipsprite is created. The Flipsprite constructor (called by the normalizer) passes an initial value to the two variables ‘m_posX’ and ‘m_posY’. The normalizer periodically updates these position values (by means of an update function defined as part of the flipsprite) as the animation takes place. For the example of simple circular motion, the normalizer updates the position values by causing them to move in a circle about the center of the circle.

[0415] The definition for instances of type ‘SpriteTree’ has a virtual ‘Paint’ method which takes as input parameters a surface to draw onto and a time. The ‘Paint’ function is a pure virtual function for an object of type ‘SpriteTree’ and must be implemented by an instance of a class that inherits from the Spritetree class. When a sprite tree is created, it may be the first tree in which case there are no links to other trees. If the normalizer determines the animation involves only a single sprite such as is the case for the simple circular motion there are no other sprites trees in the list. If there is a list of sprites trees already created, however, when the normalizer creates a new sprite tree, the new tree is created and linked at the head of the existing sprite tree list.

[0416] One chain of inheritance is: Spritetree -> ImageSprite -> TransformableSprite -> FlipSprite. An instance of type FlipSprite paints itself on the video monitor by inheriting the ‘Paint’ method from a class called TransformableSprite.

[0417] The paint function takes as an input parameter a paint time which is a real number intermediate the two immediately preceding times at which the normalizer has updated the sprite tree list. The ‘Paint’ function first locks other threads that are running and in particular locks the thread doing updates. The function then performs a ‘GetSrc’ from the flipsprite instance being painted. This causes the paint function to obtain a DirectDraw surface on which to draw and a cropping rectangle to use in performing the paint function. The ‘Paint’ function for a Flipsprite instance is inherited from a class transformablespite.

[0418] The TransformableSprite definition of ‘Paint’ has an input parameter the time t, and a drawing surface to which it is to transfer an image. The function GetSrc for a flipsprite determines which page of the potentially multi-page Flipsprite is to be rendered. The ‘Paint’ function next samples the flipsprite position by calling the at(t) function of the ‘m_posX’ and ‘m_posY’ fields (of type Lineardouble) and returns updated positions of those fields in the variables moveX and moveY. These variables are real double variables and correspond to the position of the image of the object of type FlipSprite.

[0419] The at(t) function for determining the X and Y positions respectively for the Flipsprite ‘Paint’ function uses two times that are updated by the normalizer m_startVal and m_startTime to calculate a new value of moveX and moveY based on a speed variable m_speed which is calculated by the normalizer. The m_speed variable is defined as a real double precision value. Its value is calculated in a SetMotion function which is called by the normalizer. Turning to the example of FIG. 4 illustrating motion between points on a curve. Although the curve in FIG. 4 approximates a sine curve, the curve could also be a segment of a circle along which the Flipsprite moves. When the normalizer calls the SetMotion function it first locks out the sprite engine and then calculates the speed. The normalizer is aware of the position and time for the two end points x₂, x₃, for example, for the Flipsprite. Based on this information the speed m_speed variable is calculated. Once this calculation is performed the thread in which the sprite engine runs can be unlocked. The sprite engine then uses the speed value to calculate an intermediate position along the linear path between the endpoints x₂, x₃of the circular motion path 211.

[0420] The sprite engine 240 traverses all elements in a tree by calling the ‘paint’ function for the individual sprite that make up the leafs of the spritetree. Generally, the sprite tree is more complex than the simple Flipsprite of the circular motion example. A more general case is the sprite tree 232 of FIG. 3. This sprite tree has sprites 234 and non-leaf nodes 236. The non-leaf nodes 236 are defined as objects of type ‘SpriteGroup’. The object of type ‘SpriteGroup’ inherits from the SpriteTree class. An instance of type SpriteGroup is initialized by the normalizer during construction of the sprite tree 232. The ‘Paint’ function for an object of type SpriteGroup calls a ‘PaintAll’ function for all child elements (sprites and SpriteGroups) that are decendents of the SpriteGroup for which ‘Paint’ is called. In practice, the first call is PaintAll on a chain of root nodes, which in turn calls the Paint function for each tree in the chain. These calls visit the elements of the tree in back-to-front order, left to right so that as soon as a leaf sprite is reached the paint function for that leaf is performed and the backbuffer is updated.

[0421] Each instance of type SpriteGroup has a boolean field designated as ‘m_isMutable’. Initially, the value of the field is true. When it is set to false, the tree can be simplified, replacing the SpriteGroup node with its (final) list of children.

[0422] The invention supports animations for sprites of type ‘Soundsprite’ and sprite trees of type ‘CondSpriteTree’. The objects of type Soundsprite have their own paint function which is quite different from the paint for the other sprites such as a FlipSprite. A sound sprite is positioned by the normalizer on the tree but the sprite engine responds quite differently when the ‘paint’ function for a ‘soundsprite’ is called. The sound sprite ‘Paint’ function interfaces with the audio interface or adapter 158 to adjust the frequency and volume of an audio output by means of calls to DirectSound control functions.

[0423] The conditional sprite tree is like any other tree positioned by the normalizer in a linked list of sprite trees. When the condition for the tree to be rendered is true, then the sprite engine executes the ‘PaintAll’ function on one sprite list, and when false, on another sprite list.

[0424] In the foregoing description, the invention has been described with reference to specific exemplary embodiments thereof. It will, however, be evident that various modifications and changes may be made hereto. Specifically, the examples in the functional programming language Fran derived from the Haskell language are regarded in an illustrative rather than a restrictive sense.