Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-13
2002-01-29
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C709S241000, C711S004000
Reexamination Certificate
active
06343298
ABSTRACT:
TECHNICAL FIELD
This invention relates to multimedia titles having a plurality of media clips interconnected by seamless branches, to methods of authoring such multimedia titles, and to methods of scheduling data delivery during multimedia titles.
BACKGROUND OF THE INVENTION
Typical computer games and other multimedia programs are frequently distributed on removable optical storage media such as CD-ROMs (compact disc-read only memory) and DVDs. CD-ROMs are currently the most common media used for program distribution. DVDs, commonly referred to as digital video discs or digital versatile discs, use a high density optical disc format that has been in development for the past several years. DVD was introduced in Japan and Korea in late 1996, and is expected to be available in the U.S. and other markets in 1997. There are several variations of the DVD format. DVD-Video is a format designed to deliver linear motion picture content. DVD-Audio is a format designed for audio. The term DVD-ROM is used to reference an optical storage medium that is formatted in accordance with the DVD standard.
Games and other programs such as these often use continuous data streams that are stored on the optical storage media for rendering during program execution. Such continuous data streams include video and audio streams. Digital video and audio streams are usually stored in a compressed and encoded format such as industry standards consisting of MPEG-2 Video, MPEG-2 Audio, and other MPEG-2 systems. MPEG stands for the Moving Picture Experts Group, which is a group that coordinates the definition of these standards.
Commonly used optical digital media typically have data stored in continuous spiral tracks. Continuous data can then be read in its proper order at high speeds by reading sequentially along the spiral of the media.
Many multimedia programs and games use a number of media clips that are tied together into a cohesive story under program control or according to user actions. This requires that a program or game be able to instantly switch from one continuous clip to another in response to user input, without any discernible rendering discontinuity or gap between clips. Such gaps are referred to as “seams.” A continuous branch, without discontinuities, is referred to as a “seamless” jump or branch. As a specific example, a video game utilizes audio and video clips while allowing users to influence the particular sequence of rendered video clips. In some games, for instance, a user can manipulate a mouse or a joystick to change story lines and influence game outcomes. As the user makes choices, the game responds so that the audio and video appear to flow seamlessly. In many cases, the user at some point will have several different alternatives, and the game must react immediately to whichever of the alternatives is actually chosen by the user.
As used here, the term “clip” refers to a segment of data that is intended to be read and rendered as a stream and that is stored on a storage medium in such a way that it can be read from the storage medium at a rate that is at least as fast as the normal rate at which the data is intended to be rendered. In most cases, an individual media clip will be laid out contiguously along a spiral of a CD-ROM or DVD.
In addition to branching seamlessly to another clip, a program sometimes must access extraneous data files while playing a single media clip. For example, a game might need a data file containing a digitized sound effect of short duration (such as a “beep” to signal an error), which is to be rendered simultaneously with the primary audio and video. When the file must be obtained from the same CD-ROM or DVD, this is referred to as intervening file access.
When using storage media such as CD-ROMs and DVDs, seamless jumps between media clips are difficult to achieve. This is because of the relatively high latency these devices exhibit when switching between different physical locations on the media. The time required to access a different DVD location can be nearly ⅓ of a second. To preserve visual and audio continuity, something needs to be rendered during this time, even though new data is not available.
Existing solutions to this problem primarily involve some type of pre-loading. One solution, for example, requires caching the initial segments, referred to as bridge data, of all media clips that might potentially be the target of a seamless branch. When a branch is taken, the cached data is rendered while accessing the appropriate location on the storage medium. This approach is useful both for intervening file access and for branching from one media clip to another. However, this approach requires significant amounts of low-latency memory to store the bridge data for all available media clips. This is wasteful and expensive, and in some cases is simply not a possibility (such as in a consumer device with no hard disk). Furthermore, new video standards such as MPEG2 require high bandwidths and thus greatly increase the amount of low-latency memory that would be required to implement a pre-loading scheme such as described above.
Some solutions take advantage of storage device characteristics to provide seamless branching. For example, DVD-Video uses data interleaving for multiple angle viewing. Video clips from different camera angles are laid out in an interleaved manner. Angle of view can be changed seamlessly since the video clips corresponding to different camera angles can be delivered simultaneously. This technique has the advantage of requiring no caching beyond internal read-ahead buffering, but is very limited in scope. It cannot be used for general-purpose seamless branching such as used in games or other similar multimedia titles. In addition, some DVD-Video systems utilize a read-ahead buffer to store bridge data. This technique relies on the ability to read data faster than it can be consumed. While this approach is practical in some situations, it imposes limitations on the physical layout of clips. Also, there are many situations, such as where there are a plurality of available branches at a given time, where this approach simply will not work.
Some applications utilize more than one high-latency storage medium for rendering continuous media content, such as two CD-ROMs. However, this is an expensive solution, and requires equipment (two drives) that most users do not have.
SUMMARY OF THE INVENTION
The invention utilizes caching to achieve seamless branching. However, the invention reduces bridge memory requirements by scheduling bridge data for delivery from the primary storage device (such as a CD-ROM or DVD-ROM) just before it is needed. Bridge data is discarded after the point when the bridge data can no longer be utilized. This is in contrast to previous methods in which bridge data for all available media clips was cached before even beginning a rendering process.
When authoring a software title that utilizes continuous media, the media is divided into individual clips. Seamless jumps or branches are defined between the clips. For example, a game might allow jumps to clips B and C from clip A. Other jumps might be available from clips B and C.
Each clip is assigned to be either a carrier clip or a non-carrier clip. Bridge data is scheduled for delivery to bridge memory only during carrier clips. If A is a carrier clip having available branches to clips B and C, for example, bridge data for clips B and C will be delivered during the playback of initial parts of clip A. A branch to clip B or C will only be allowed after the bridge data is delivered. If this is a problem, and the game must allow an immediate branch from clip A, clip A is designated as a non-carrier clip, and the bridge data for clips B and C must be delivered during a media clip that is upstream from or previous to clip A.
Intervening files, referred to herein as data clips, are considered non-carrier clips. The bridge data for a data clip comprises the entire data clip.
This scheme allows an author to minimize and optimize bridge memory requirements. S
Nelson Robert B.
Nirkhe Vivek
Savchenko Alexander V.
Sun Yi
Homere Jean R.
Lee & Hayes PLLC
Microsoft Corporation
Robinson Greta L
LandOfFree
Seamless multimedia branching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Seamless multimedia branching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Seamless multimedia branching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2839767