Fast transmission of graphic objects

FAST TRANSMISSION OF GRAPHIC OBJECTS

FIELD OF THE INVENTION

0003The present invention relates generally to computer animation, and specifically to interactive rendering of computer graphic objects from a remote source. BACKGROUND OF THE INVENTION

0004In recent years, the use of the World Wide Web (WWW) has been rapidly growing. In use of the WWW, a client computer user connects to a Web site on a server and requests that the server download and display Web pages on the client computer. In response to the request, the server sends to the client computer graphic files, which include media elements (pictures, animations, texts, sound), scripts of instructions to be performed by an Internet browser program running on the computer, and in some cases executable software code, e.g., Java code. In addition, the server usually sends a file in HTML format which describes the layout of the computer graphic files on the screen. Generally, the Internet browser program operates independently of other programs on the client computer and, in particular, limits the access of scripts from the server to files stored in the memory of the client computer, and especially to graphic objects stored in the memory.

0005In order to attract users, sites must be interesting, and it is typically desired that sites display graphics and animation. However, the time required to download and display Web pages which include animation, including three-dimensional (3D) animation, on the client computer is relatively large, which is inconvenient to users and may discourage them from using such sites. Frequently it is desired to render animated advertisements along with user- chosen data from a Web site. Such advertisements must not require long transmission periods, or the visitor at the site may leave the site and be discouraged from returning.

0006Various compression methods have been suggested to reduce the data volume of a transmitted Web page and thus reduce the amount of time required to display the page on the computer. However, even using such compression methods, available network transmission bandwidth is typically still much lower than required to transmit large high quality animation streams. The users therefore must either settle for reduced quality of the animation stream or limit its size and/or length. In addition, some compression methods require lengthy decompression, which wastes much of the time saved by the compression. Another method referred to as caching or data pushing, descπbed, for example, in U S Patent 5,727, 129, which is incorporated herein by reference, includes "pushing" data in advance while the connection of the client computer to the network is idle The computer, or the server, chooses data which may be of interest to the user and sends this data to the computer in advance of a specific request from the user, while the connection is idle However, in manv cases, there is no way to predict what the user will want to see The number of Web pages which may be stored on the computer is limited, and the user may want updated versions of the page Furthermore, there is not always an idle line available for significant periods of

0007Some Web browsers allow server-originated code to access the hard disk of the computer running the browser Such access is normally performed using programs known as "plug-ins^" or ActiveX controls In most cases, when such access is attempted, the user of the computer is typically warned of a potential security violation, arising from such access

SUMMARY OF THE INVENTION

0009It is an object of the present invention to provide improved methods and apparatus for fast rendering of an animation object, preferably a three-dimensional (3D) object, on a remote computer graphic display

0010In preferred embodiments of the present invention, an animation image of an object comprises a set of sub-objects (also referred to herein as elements) which are arranged in a predetermined hierarchv and animated responsive to the hierarchy A structure record (also referred to as a "skeleton") describes relationships between the sub-objects in the hierarchy Preferably, the structure record is written in accordance with a common script language, such as JavaScript A plurality of sub-object records describe the sub-objects At least some of the sub-object records are stored in a local memory associated with a client computer

0011When the animation image is to be rendered on a display associated with the client computer, a server sends the structure record describing the animation image to the client computer, together with required sub-object records, if any, which are not stored in the client computer's local memory Typically, only the structure record and a minimal number of sub- object records need be sent from the server Thus, in most cases remote rendering of animation objects requires relatively low bandwidth, since the heavy graphical pans of the objects are stored permanently in the memory associated with the client computer In the context of the present patent application, the term "object" is used to refer to a modular, graphic and/or mathematical description of an image (generally a representation of a physical object, which may be naturalistic or fanciful). The skeleton of the object preferably defines the parts of the object and the joints connecting those parts. The hierarchical structure of objects allows a user to exchange sub-objects between objects that share a common hierarchy.

0012In some preferred embodiments of the present invention, the object represents a human, humanoid or animal character, and the sub-objects describe organs (such as limbs) and sub- organs (such as parts of the limbs) of the character. Other optional sub-objects describe attributes such as sound and rules governing behavior of the object, such as motions of the image.

0013Preferably, the objects also include sub-objects that define their response to sensitivity conditions that may arise externally to the object itself, such as the presence of other objects in the computer display. Furthermore, objects may include sub-objects that have learning capabilities, as are known in the art, whereby the behavior of the object is modified adaptively in response to inputs from the computer-animated environment. Preferably, some of the sub- objects are themselves formed of other sub-objects. In a preferred embodiment of the present invention, the objects comprise Smart Objects as are described in PCT publication WO97/35280, which is incorporated herein by reference. Preferably, the client computer runs a scene manager program, which displays the animated images on a screen associated with the client computer. The scene manager is preferably part of a Web browser, which downloads graphic pages from a network. The client computer preferably also runs an element manager program, which keeps track of the locations of the records of sub-objects stored on the client computer. The scene manager interacts with the element manager to properly render the object using the received records and the stored records.

0014Preferably, the element manager maintains a look-up table which is used to find the location in the memory of sub-objects referenced by the received structure record. Most preferably, the element manager receives the name of a desired sub-object and returns a pointer to the stored location of the object based on the name. If the desired sub-object in not held in the memory of the client computer, the element manager returns a negative answer. Alternatively or additionally, the element manager orders the requested element from the server and provides the scene manager with a pointer to an input directory in which received sub-objects are stored.

0015In some preferred embodiments of the present invention, the element manager is included within the Web browser. Thus, the user does not need to install any "'plug-in" to the browser. Preferably, the browser as supplied to the client computer includes a set of records describing commonly-used sub-objects. Most preferably, the browser and set of records are pre-installed in a computer with dedicated three-dimensional graphics capabilities.

0016In some preferred embodiments of the present invention, when a sub-object not already in the memory is received by the client computer, the sub-object is stored in the memory and its address is added to the look up table.

0017In some preferred embodiments of the present invention, when a server instructs the client computer to render a new object, the server sends the computer a list of the sub-objects to be used in constructing the transmitted object, and the computer responds with a list of the sub-objects which the computer has and/or with a list of the sub-objects which the computer does not have. The server responds by sending the sub-objects missing from the client computer. Preferably, while waiting for the computer's response, the server sends the structure record and/or records describing sub-objects which are least likely to be already stored in the memory of the computer.

0018Preferably, when a computer responds that it does not have a copy of a sub-object which itself is formed of sub-sub-objects, the server sends a second list which lists the sub-sub- objects which form the sub-object and requests that the computer identify those sub-sub- objects which it does not have. This process may continue for the sub-sub-objects until there are no further sub-objects or until the records describing the sub-objects are so small that it is simpler to send the records, rather than to ask if they are needed. Alternatively or additionally, the server only asks the client computer about sub-objects for which there is a high probability that the computer has records describing its sub-sub-objects.

0019Alternatively or additionally, the client computer determines the required sub-objects from the received structure record. Preferably, the JavaScript of the structure record describes the animation conditionally, based upon the presence or lack of sub-objects in the client computer. The JavaScript preferably uses "If-Then" directives to reference the sub-objects, wherein a referenced sub-object is first accessed in the local memory using the element manager, and if it is not found in the local memory, the sub-object is requested from the server either bv the scene manger or by the element manager

0020There is therefore provided, in accordance with a preferred embodiment of the present invention a method for rendering an animation object, including a plurality of sub-objects, on a display of a client computer under control of a remote server, including transferring from the server to the client, program code which descπbes a structure of the object, accessing within a local memory associated with the client a program descπption of at least one of the sub-objects of the object, and displaying the object such that the sub-object is coupled to the structure in accordance with the program code

0021Preferably, the method includes reporting to the server the identity of at least some of the sub-objects stored in the memory Most preferably, reporting the identity of the sub- objects includes receiving a list of sub-objects from the server and reporting on a correspondence between the list and the sub-objects that are stored in the memory

0022Further preferably, the method includes transferπng from the server to the client descriptions of sub-objects not already stored in the memory and stoπng the transferred descriptions in the memory In a preferred embodiment, at least some of the sub-objects include sub-sub-objects, and transferring descriptions of the sub-objects includes transferπng only those sub-sub-objects not stored in the memory

0023In another preferred embodiment, the method includes storing in the memory a plurality of descriptions of sub-objects when installing a browser on the computer

0024Preferably, accessing the at least one description includes looking up the location of the descπption in the memory in a look-up table Alternatively or additionally, accessing the at least one description includes receiving an exact location of the description from an element manager and accessing the exact location

0025In a preferred embodiment, the object includes a three dimensional graphical object

0026Preferably, at least some of the sub-objects include graphical descriptions of parts of the object Further preferably, at least some of the sub-objects include sound modules Preferably, accessing the program description of at least one of the sub-objects includes calling a routine which returns the address of the object in the local memory Most preferably, transferπng the program code includes transferπng a scπpt which references the sub-objects in the local memory and if the object is not found in the local memory, references the sub-ob_ject in an input location

0027There is also provided in accordance with a preferred embodiment of the present invention, apparatus for rendering an image of an animation object under control of a remote server including a memory, which stores descriptions of sub-objects which are used to form the objects, an animation generator, linked locally to the memory, which receives a skeleton which describes a structure of the object and retrieves the descπptions of at least some of those sub- objects from the memory, and a display on which the image is displayed by rendering the sub-objects responsive to the descriptions thereof and responsive to the skeleton

0028In a preferred embodiment, the object includes a three dimensional object Preferably, the memory includes a look up table which lists the sub-objects of which there are descriptions in the memory Further preferably, the animation generator receives from the server a list of the sub-objects in the object and responds by indicating to the server those sub-objects of which descπptions are not stored in the memory

0029The present invention will be more fully understood from the following detailed descπption of the preferred embodiments thereof, taken together with the drawings in which

BRIEF DESCRIPTION OF THE DRAWINGS

0031Fig 1 is a schematic illustration of a system for rendeπng an animation sequence on a client computer under control of a server in accordance with a preferred embodiment of the present invention.

0032Fig 2 is a block diagram illustrating the program structure of an animation object, in accordance with a preferred embodiment of the present invention,

0033Fig 3 is a flow chart illustrating a method of rendering an animation object, in accordance with a preferred embodiment of the present invention,

0034Fig 4 is a schematic block diagram illustrating a data structure in a memory associated with the client computer, in accordance with a preferred embodiment of the present invention, and

0035Fig 5 is a flow chart illustrating the actions of a computer in rendering an object under control of a remote server, in accordance with another preferred embodiment of the present invention

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

0037Fig 1 is a schematic illustration of a system 18 for rendeπng of an animation sequence, in accordance with a preferred embodiment of the present invention The sequence is rendered on an animation generator, typically a client computer 26, under control of a server 24 connected to computer 26 by a network 28, preferably the Internet Server 24 is preferably a Web server as is known in the art

0038The animation sequence is preferably described by a script generated in accordance with a general programming language, such as JavaScript, using computer programming methods known in the art The animation sequence is transmitted from server 24 over a network 28 to a scene manager program, preferably associated with Internet browser software running on computer 26, as descπbed further hereinbelow The scene manager displays the animation on a display 30 associated with the computer Preferably, computer 26 further comprises a memory 32 which is used to store building blocks of animation objects, referred to herein as elements, which are accessed in accordance with the scπpt, as descπbed hereinbelow Fig 2 is a block diagram illustrating the program structure of a 3D animation object 70 in accordance with a preferred embodiment of the present invention Object 70 comprises a plurality of elements 78 and a structure record 72 which describes relationships between the plurality of elements 78 Elements 78 may comprise "organs" which are. in general, coherent groups of 3D shapes that form a part of the physical representation of object 70 Other elements 78 include "sound elements" 74, "behavior elements" 76, "surface detail elements," and other types of groups of data associated with object 70 Elements 78 preferably are made up of a plurality of sub-elements 90 and a sub-structure 88 which describes the relationships between sub-elements 90 Preferably, at least some of sub-elements 90 are made up, in a manner similar to elements 78, of a structure element and sub-sub-elements 92 The sub-sub- elements 92 comprise further sub-elements or basic building blocks 94, such as simple geometrical shapes, single sound notes, basic behavior features, etc Preferably, object 70 comprises a "Smart Object", as described in PCT publication WO97/35280

0039Fig 3 is a flow chart illustrating a method of rendering animation object 70, in accordance with a preferred embodiment of the present invention Server 24 transmits to client computer 26 a list of the elements of object 70 In response, computer 26 sends back a list of those elements which it does not have Alternatively or additionally, computer 26 sends a list of the elements it does have Meanwhile, server 24 sends structure record 72 to computer 26, since the structure record must be sent in any event Preferably, if the returned list has not been received yet, server 24 continues sending elements which are most likely to be required, or elements which are chosen randomly Once the returned list from computer 26 is received, server 24 continues sending only those elements which the computer does not have. Thus, it is possible to take advantage of substantially all the elements which are stored in computer 26, without server 24 knowing beforehand the contents of memory 32 of the computer

0040In some preferred embodiments of the present invention, when an element 78 which must be sent to computer 26 includes large sub-elements 90, server 24 sends a list of the sub- elements which it intends to send, and computer 26 responds with a list of those sub-elements it does not have This process may be continued recursively as illustrated by the pseudo code in Table 1 , which is a procedure performed by server 24 when sending the elements of an object 70 The procedure is preferably invoked by the pseudo command Handle_organ (highest organ in hierarchy)

0041Table 1

0042Procedure Handle_organ {organ Jo be handled) { If organ to _be handled exists on client

0043Exit Else If organ to be handled has sub-organs then {

0044For each sub-organ oϊ organ Jo be handled { Handle_organ (the sub-organ)

0045Else

0046Send organ to client

0047}

0048Alternatively or additionally, the original list of elements 78 of object 70 also lists all or some of the sub-elements 90 in the elements, and computer 26 indicates for those elements that it does not have in memory 32, which sub-elements it does have. It is noted that a similar procedure may be used for any depth of hierarchy of object 70. Further alternatively or additionally, at the beginning of each session of rendering objects on computer 26 under control of server 24, the computer sends the server a list of all the elements and sub-elements it has already stored in memory 32. Thereafter, server 24 updates the list each time another object is rendered on computer 26, so that the list transmitted by the server to the computer is kept as short as possible and in some cases may not be necessary.

0049Fig. 4 is a schematic illustration of memory 32, in accordance with a preferred embodiment of the present invention. Memory 32 includes an area 34 in which descriptions of objects 70, elements 78 and sub-elements 90 are stored. Preferably, whenever any object 70, element 78, or sub-element 90 is downloaded for rendering on the screen of computer 26, it is in addition stored in memory 32 for further use. Alternatively or additionally, a group of commonly-used objects and/or elements are provided along with the browser. Further alternatively or additionally, a group of commonly used objects and/or elements are stored in memory 32 upon manufacture, and are provided to every purchaser of computer 26. Further alternatively or additionally, a user may download from an Internet site groups of objects and/or elements.

0050Preferably, memory 32 comprises a look-up table 36 which points to the location in area 34 of each object, element and sub-element stored in memory 32 When computer 26 receives a list of objects from server 24, it compares the list to look-up table 36 and responds accordingly. Thereafter, when the browser displays object 70, it accesses look-up table 36 to determine the location of elements it needs for rendering.

0051Preferably, elements 78 are cataloged in look up table 36 both as elements and according to their sub-elements, so that sub-elements included in more than one element need be sent for rendering only once.

0052Fig. 5 is a flow chart illustrating the actions of computer 26 during rendering of object 70, in accordance with another preferred embodiment of the present invention. Object 70 is sent in the form of a script to a Web browser on computer 26. The script includes structure record 72 of object 70, in which the elements of the object are referenced along with the connections between them. The browser renders the elements on display 30, as is known in the art. For each element to be rendered, the browser calls an element manager which provides the address of the description of the element.

0053Preferably, the element manager is stored in memory 32 together with the descriptions of the objects. Preferably, the element manager is an ActiveX element and is provided with the

0054Web browser, with an operating system or with computer 26. Alternatively or additionally, the element manager may be downloaded from a Web site or is provided along with an animation stream.

0055The element manager preferably consults look-up table 36 to find the element. If the element is in memory 32, the element manager returns a pointer to the exact area 34 where the description of the element resides. Providing the exact address of the element allows the script from server 24 to access the element directly without searching through memory 32, a search which generally causes the Web browser to display an alert message. However, if the element is not in memory 32 the element manager returns a pointer to an input directory in which elements from server 24 are temporarily stored. In addition, the element manager preferably orders the element from server 24, by sending an appropriate message. Preferably, if the element is formed of relatively large sub-elements, and some of the sub-elements are stored in memor _' 32 (as listed in LUT 36), the element manager orders only those elements which are not in the memory. After the element manager has ordered one of the elements from server 24, computer

005626 waits for the server to return the ordered element. Preferably, while the computer is waiting, the element manager proceeds to process the rest of structure record 72. Alternatively, the element manager waits for the ordered element to be returned before proceeding.

0057Table 2 is a subroutine which finds the objects referenced by the structure record, in accordance with a preferred embodiment of the present invention.

0058Table 2

0059// da - DirectAnimation object for creating parts // number_of_parts - the number of parts in the character

0060// alternate path - the path where all parts will reside if

0061// not found in local users hard disk

0062// characterURLs - array with entry for each part.

0063// If entry is "", no part is needed. // If entry is "?", part can be found only in

0064// alternatePath, and not on user's local hard disk.

0065// otherwise, points to relative path of part in Zapa's

0066// folder on user's local hard disk.

0067function ZapaCreateCharacter (da, number_of_parts, alternatePath, characterURLs)

0068{

0069// create ActiveX object that searches for local content // Zapa.LocalContent is the element manager var zapaContents = new ActiveXObject("Zapa.LocalContent"); // array that will receive DA parts var allParts = new Array(skeleton. length);

0070var i;

0071// in Zapa's characters, base part is always a null part allParts[0] = da.EmptyGeometry; for (i = 1, i <= number_of_parts, ++i)

0072var localFileName = characterURLs[i-l]; // alternate filename is as below var alternateFileName = alternatePath + i + " x",

0073if(localFileName == "") // if part i is an empty part allParts[i] = da.EmptyGeometry; else if (zapaContents ι= null && localFileName ι= '">")

0074{

0075// if part may be in local content and activeX object // was created correctly, ask it for local path var path = zapaContents. PathOfFile(localFileName,alternateFileName);

0076// ActiveX returns either local file name or alternate file name if (path != "") allPartsfi] = da.ImportGeometryAsync(path, da.EmptyGeometry). Geometry; else allPartsfi] = da.EmptyGeometry;

0077} else // if no local content, then just use alternateFileName allParts[i] = da.ImportGeornetryAsync(alternateFileNarne,da.EmptyGeometry) Geometry;

0078Thereafter, the elements received from server 24 are preferably passed to long-term storage in memory 32 in appropriate directories. In addition, the elements are preferably cataloged in list 36 The long term storage is preferably performed at a later time when computer 26 is idle Alternatively or additionally, elements which appear more than once in an animation stream or are likely to appear in animation streams to be accessed in the future are placed in the long-term storage while the rest of the elements received are left in the temporary directory and are eventually erased Preferably, each element sent from server 24 is tagged with a "store" / "don't store" label, which instructs computer 26 whether to pass the element to long term storage

0079Alternatively or additionally, the elements are tagged with a priority value which states the expected frequency of use of the element Computer 26 determines, based on the priority value and the available storage room in memory 32, whether or not to pass the element to the long-term storage Preferably, other variables may also be used to determine whether to pass the element to long-term storage, and a user of computer 26 may change the settings of the variables

0080It will be appreciated that the preferred embodiments described above are cited by way of example, and the full scope of the invention is limited only by the claims