Storyboard system for the simultaneous timing of multiple independent video animation clips

Abstract

An automated storyboard system, which is updated for the creation of information sequences. The storyboard includes an array of cells arranged in columns, with the content of each cell indicating an information source having a certain active duration. For each column of the storyboard which contains active cells a determination is made as to which of the cells contains an information source having a shortest one of the active durations. The column is marked to have a column time duration of the cell of shortest active duration, with the cell of the shortest active duration being terminated at the end of the column. When other active cells exist for the column, a further column is added next to the column, with the further column containing the other active cells. The active cells have an updated active duration which is equal to their previous active duration less the column time duration.

Claims

We claim:

1. A method, using processing means, for updating an automated storyboard system for the creation of information sequences, wherein said storyboard comprises an array of cells arranged into columns and stored in a memory connected to the processing means, each said cell having contents that indicate a respective information source for one of the group consisting of audio information, video information and audio and video information, and each information source having a respective active duration, said method comprising, for each column of the storyboard which contains active cells, the steps of:

(a) determining which one of said cells contains an information source having a shortest one of said active durations and defining that one cell as a cell of shortest active duration, wherein the active duration of the information source of at least one of the cells is variable in relation to the active durations of the information sources of the other cells,

(b) marking said column in said memory to have a column time duration of said cell of shortest active duration and terminating said information source of said cell of shortest active duration at the end of said column, and

(c) where other active cells exist for said column, adding a further column next to said column, said further column containing said other active cells each having an updated active duration of their previous active duration less said column time duration.

2. A method as claimed in claim 1 further comprising the step of deleting at least one cell from said storyboard and applying said steps (a) to (c) after said deletion.

3. A method as claimed in claim 1 further comprising the step of adding at least one cell having an information source, to said storyboard and applying said steps (a) to (c) after said addition.

4. A method as claimed in claim 3 further comprising the step of adding at least one new cell between two pre-existing columns and applying said steps (a) to (c) after said addition of the new cell to create a corresponding new column.

5. A method as claimed in claim 1 further comprising the step of altering the contents of at least one of said cells and applying said steps (a) to (c) after altering said one cell.

6. A method as claimed in claim 1 further comprising the step of altering said active duration of one of said cells and then applying said steps (a) to (c).

7. A method as claimed in claim 1 further comprising the step of terminating a multiplicity of selected ones of said cells substantially simultaneously with termination of a predetermined candidate cell, said terminating step comprising the sub-steps of:

identifying a particular column of the storyboard that said information source of said predetermined candidate cell terminates; and

designating said multiplicity of selected cells to terminate in said particular column, and adjusting the active duration of said selected cells to accord with the active duration of said candidate cell.

8. The method according to claim 1, wherein said video information comprises computer-generated video information.

9. Apparatus, including processing means, for updating an automated storyboard system for the creation of information sequences, wherein said storyboard comprises an array of cells arranged into columns stored in memory means connected to said processing means, each said cell having contents that indicate a respective information source for one of the group consisting of audio information, video information and audio and video information, and each information source having a respective active duration, for each column of the storyboard which contains active cells, said apparatus comprising:

means for determining which one of said cells contains an information source having a shortest one of said active durations and defining that one cell as a cell of shortest active duration, wherein the active duration of the information source of at least one of the cells is variable in relation to the active durations of the information sources of the other cells,

means for marking said column in said memory means to have a column time duration of said cell of shortest active duration and terminating said information source of said cell of shortest active duration at the end of said column, and, where other active cells exist for said column,

means for adding a further column next to said column, said further column containing said other active cells each having an updated active duration of their previous active duration less said column time duration.

10. The apparatus according to claim 9, wherein said video information comprises computer-generated video information.

Description

FIELD OF THE INVENTION

The present invention relates to the display of video animation and in particular, the editing of video segments to produce a multilevel simultaneous display of multiple video clips.

BACKGROUND ART

Traditional film production techniques usually involve the shooting of multiple video or film `takes` or `clips`. Normally much more film is shot than is required for the final result. The resultant film is normally edited by a film editor who uses scissor like splicers and adhesive tape to cut and paste together the desired shots. Artistic decisions about the selection of shots to enhance the performance are made and a final result produced.

If dissolves or wipes are required between two sources, then the processing becomes much more complicated, often involving the use of multiple video recorders and vision switchers.

Although editing and mixing can be implemented on a frame by frame basis, it is desirable to be able to format the editing/production process with what is known in the industry as a "storyboard". The storyboard represents a plan of the film video or animation that is to be created as assists in the visualisation of the production. Storyboards are traditionally created by hand, going through many interactions and revisions during production and is basically a chart of various sources of audio/video and how they are to be combined over time to produce the final film. Furthermore, as a director, or the like may wish to alter the production once an initial storyboard has been created, it is highly desirable that the storyboard itself be readily editable.

Recently, computer systems have been introduced which go part of the way to automate this process. Typically, these systems require animations to be created on a frame by frame basis, storing each frame on a disk, with the image being played back at a later date by reading each frame from the disk and displaying it on a computer screen or the like.

Recently, in Australian Patent Application No. 38238/93, entitled "An Audio and Video Processor System", claiming priority from Australian Provisional Patent No. PL2141 filed 29th Apr., 1992, and to which U.S. patent application Ser. No. 08/053,569 corresponds, now U.S. Pat. No. 5,590,252, the contents of which are hereby incorporated by cross-reference, a video animation system was proposed that was capable to producing real-time video animation through the use of real-time object (RTO) technology. That document, and other co-related documents describe apparatus that can perform audio and video mixing, editing, sampling, and the like at a substantially reduced cost with respect to prior art arrangements. For a discussion of RTO technology, refer to Australian Patent Application No. 38244/93, entitled "A Real-Time Object Based Graphics System" claiming priority from Australian Provisional Patent No. PL2147, filed 29th Apr., 1992, and to which U.S. patent application Ser. No. 08/053,373 corresponds, now U.S. Pat. No. 5,444,839, the contents of which are hereby incorporated by cross-reference.

As a result of these developments, there is an ever increasing need for an automated storyboard system capable of editing, ordering and timing multiple clips for subsequent display.

It is an object of the present invention to provide an automated storyboard mechanism which substantially meets these needs.

SUMMARY OF THE INVENTION

In accordance with one aspect of the present invention there is provided a method for updating an automated storyboard system for the creation of information sequences, wherein said storyboard comprises an array of cells arranged into columns, in which the contents of each cell indicates an information source having a certain active duration, the method comprising, for each column of the storyboard which contains active clips, the storyboard calculation steps of:

determining which cell contains an information source having the shortest active duration,

marking the current column to have a column time duration of said cell of shortest active duration and terminating said cell of shortest active duration at the end of the current column, and

where other active cells exist for a current column, adding a column next to the current column and containing said other active cells with the active cells having an updated active duration of their previous active duration less said column time duration.

Preferably the method for updating an automated storyboard system further includes providing a means for terminating a multiplicity of cells at substantially the same time comprising the steps of:

identifying in which cell of a storyboard that a second cell terminates;

designating a first cell to stop in that cell, and adjusting the active duration of that cell to accord with the length of the second cell.

In accordance with other aspects of the present invention, there are provided various methods for automatically adding and moving clips within a storyboard.

The columns can have any number of cells either active or inactive therein, thereby allowing different animations to be simultaneously displayed at different priority levels above one another.

Apparatus for implementing the methods is also disclosed.

BRIEF DESCRIPTION OF THE DRAWINGS

A preferred embodiment of the present invention will now be described with reference to the accompanying drawings in which:

FIG. 1 illustrates an AVAPS system and its operational environment.

FIG. 2 illustrates the AVAPS system of FIG. 1 in more detail.

FIG. 3 illustrates a simple storyboard containing 4 columns, two rows, and therefore 8 cells.

FIG. 4 illustrates a storyboard having two clips in sequence.

FIG. 5 illustrates a storyboard having two clips in parallel.

FIG. 6 illustrates a storyboard example that could be used for a presentation describing the uses of a particular product in two countries.

FIG. 7 illustrates a storyboard directory entry.

FIG. 8 illustrates a ROM storyboard structure.

FIG. 9 illustrates a ROMCard Usage Table.

FIG. 10 illustrates a Cell structure.

FIG. 11 illustrates the structure of the flag entry in a cell.

FIG. 12 illustrates a clip reference pointed to by a cell in a storyboard.

FIG. 13 illustrates a clip address.

FIG. 14 illustrates a storyboard in RAM.

FIG. 15 illustrates an entry in the column table.

FIG. 16 illustrates a RowTable entry.

FIG. 17 illustrates the basic cell information copied in Get Cell Contents.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The preferred embodiment of the present invention is designed to provide an automated storyboard mechanism capable of simultaneously editing, ordering and timing multiple video animation clips for subsequent display on an audio and video animation processor system (AVAPS) such as that disclosed in the above mentioned patent application.

Referring now to FIG. 1 there is shown an AVAPS 1 and its operational environment. Users purchase ROMcards 2, and operate the AVAPS 1 to sequence clips from the ROM cards into storyboards. Storyboards are played on one or many AVAPS's. Users 4 can edit and save their sequenced clips (storyboards) onto RAMcards 3 for future use.

Referring now to FIG. 2 there is shown the AVAPS 1 in more detail. When playing a storyboard, the AVAPS generates graphics and selects shapes for miming based on audio input. These generated images are merged in a controlled manner with an incoming video signal, producing an output video signal. Sound effects are also generated, merged with the input audio signal and leave the AVAPS 1 in the form of audio out. Limited run-time animation control can be provided by the user, and a limited amount of synchronisation can occur with other AVAPS's.

Those skilled in the art will appreciate that in other embodiments, the AVAPS 1 can include a laser-disc or another form of CD-ROM which can substitute for, or supplement the operation of the ROMcards 1 of FIG. 1 and FIG. 2, which are provided for a substantially portable AVAPS. Similar alternatives apply to the RAMcards 3 which can be supplemented by an integral RAM or hard/floppydisc drives.

The overriding emphasis in the AVAPS 1 is on giving the user easy access to sophisticated but canned (preformatted and recorded) animations, which the user can modify in simple ways and combine to achieve the desired effect.

A clip is a predesigned `canned` animation component that usually contains graphics and sound. However, those skilled in the art will appreciate that a clip can comprise only sound information, or visual information. The former would be used for preparing an audio recording or soundtrack, for example. The latter could be used to create a "silent film". A clip with visual information is capable of manipulating shapes, position, size, and color and synchronising with the user (e.g. by means of a keypress). The preferred embodiment to be described relates to clips with both sound and visual information.

Clips can contain user-editable components (such as editable text) and fixed (non-editable) components. The author of the clip can specify defaults for all of the user-editable components, so that a clip can be used without any customization.

Each clip provided by the author has a duration type. The type is one of:

fixed, where the clip can determine its duration without outside constraints (i.e. by examining its own components). For example, a clip may show scrolling credits at a constant speed. The number of lines of text to scroll will determine the duration of the clip.

unknown, where the clip has no idea of its duration, nor can it easily be determined. For example, if a clip waits for the user to press a key, the clip will not know ahead of play-time how long it will be before the user presses the key.

infinite, where the clip has no duration limit, and will be displayed for as long as the user wishes it to. An example of this is a background image behind some sequenced animation. The background image should be displayed as long as necessary in theanimation. Typically, a clip with infinite duration will need to be tied to the duration of another clip. For instance, a background image should be tied to last as long as the scrolling credit clip lasts.

The preferred embodiment of a storyboard system is configured to allow a user to:

select a clip from a ROMcard;

edit those components of a clip that are editable;

play a clip; and

sequence, layer and synchronize multiple clips.

For the purposes of the preferred embodiment, the user can decide to combine clips into a storyboard. The storyboard represents the display order and sequence of the clips. It indicates which clips are run together, what dependencies they have on their starting and finishing times, and what display order in terms of relative visual priority each clip has.

Consequently a storyboard represents:

time order. This includes representing clips that run in parallel (clip A runs at the same time as clip B), and sequence (clip A follows clip B)

display order. This includes representing the relative display order priorities of clips that are active at the same time (clip A should be displayed above clip B)

synchronization. This includes starting and stopping clips together (clip A should terminate when clip B terminates) as well as clip markers for random access during playback

FIG. 3 illustrates that a storyboard is conceptually like a spreadsheet, with rows, columns, and cells. Consecutive columns represent consecutive time segments, and rows represent display order within a time segment. Both dimensions are relative rather than absolute. Thus each column may represent a different length of time.

A storyboard is read from left to right, one column at a time. Each column represents one time segment, and the cells in each column represent relative display levels during that time segment.

Each cell within a column may contain one of the following items:

nothing. If a cell contains nothing, it means that there is nothing of consequence happening during that time segment on that relative display level.

a clip. If a cell contains a clip, it means that the clip starts at the beginning of the cell's time segment at that cell's relative display level.

a continuation marker. If a cell contains a continuation marker, it means that the clip that began in an earlier time segment on this same row is continuing through this cell's time segment.

Each cell also has a stopped flag, which indicates if the clip is to be forced to stop at the end of that cell's time segment.

The length of time represented by a particular column is defined to be the minimum time of all cells in that column. All clips that are in a particular column are defined to start together. Their finishing times will vary depending on the length of each clip. The length of the column will therefore be the length of the shortest clip. All other clips will then continue into the next column (or time segment) via a continuation marker. The length of the next column will be the shortest of all remaining times for each clip and any new clips that have started in that column. For the purposes of calculating a minimum time, an unknown duration is treated as zero time, and an infinite duration is treated as infinite.

The continuation markers are automatically added and removed by the AVAPS storyboard system, and therefore the number of columns that exist in a storyboard can change dynamically based on the number of time segments that are required to represent the clips.

A clip can be terminated prematurely by setting a stopped flag in a cell. This can be accomplished directly (e.g. by changing the stopped flag explicitly), or indirectly (e.g. by starting another clip where a continuation marker was previously). In either case, the clip will then terminate at the end of the column, regardless of how much time was remaining on that clip.

Storyboards also contain user-defined clip markers. Each column can have a clip marker associated with it provided there is at least one clip in that column. The clip marker refers to all clips that begin in the column.

Given the above representation of a storyboard, it is possible to interpret the meaning of a given storyboard.

Referring now to FIG. 4 there is shown a storyboard 6 having the same two clips in sequence, clip A and clip B. The first column is of length clip A, and the length of the second column is of length clip B. Consequently clip A is run first, then clip B is run when clip A has finished. This is true regardless of the length of A or B. If clip A had an unknown duration, then clip B would be run only when clip A finished (however long that was). If clip A had an infinite duration, then clip B would never be run, as clip A would never terminate.

Referring now to FIG. 5 there is shown a storyboard 7 having the same two clips in a parallel. The first column has the two clips, so its length is that of the shortest of the two clips (i.e. clip A). As clip A has finished by the end of the first time-segment, it does not continue to the next time-segment. Consequently, the second column has a continuation marker in the cell of the same row that clip B was in, to indicate that it continues to the next time-segment. The minimum time of the clips active in this second time-segment is the time (clip B-clip A). The relative display order of the two clips is apparent from the storyboard. Clip A is displayed on a higher priority than clip B, therefore when rendering the storyboard, if an object from clip A is drawn overlapping an object from clip B, the viewer will see the object from clip A on-top-of the object from clip B.

The first column represents the starting time of the animation, the second column represents the time when clip A has finished (and B is continuing), and the third column represents the time when clip B has finished.

Referring now to FIG. 6 there is shown a storyboard example 8 that could be used for a presentation describing the uses of a particular product in two countries. Clips A, B, and C (the first column) may represent the animated company logo and title. Clip D may represent the text describing the product's use in the first country, while clip G may represent the text describing the product's use in the second country. Clip E represents the graphics of the product itself, while clips F and H represent the graphical maps of the two countries.

The first column contains clips A, B, and C. If clips A and B have their stopped flags set, they will both terminate when clip C terminates, i.e. the animated title and logo will be on the screen for the duration of the delay clip C.

The second column shows that clips D, E, and F are started simultaneously when clips A, B, and C terminate. Clip F is terminated by the shortest clip in the column (clip D), and clip E continues after clips D and F are terminated. The third column shows that clips G and H start when D and F terminate, and finally all clips terminate when clip G finishes.

A storyboard is changed by performing actions on cells and columns in the storyboard. Each action affects the cell, and then the storyboard is re-evaluated. Effectively, the minimum time for the cell's column is recalculated, and this calculation is propagated as far as required.

The following actions can be performed on cells in the storyboard:

place a clip in a cell;

delete a clip from a cell;

change the stopped flag of a cell;

edit a clip; and

insert a clip between cells.

The effect on storyboard for each of these actions is described in the table below:

    ______________________________________
                                  Change
    Cell               Delete contents
                                  stopped
    contains
          Place clip in cell
                       of cell    flag   Edit cell
    ______________________________________
    nothing
          change cell to new
                       not meaningful,
                                  not    not
          clip, set time =
                       leave cell as
                                  meaning-
                                         meaningful
          clip's duration,
                       nothing    ful
          clear stopped flag      leave
                                  flag clear
    clip  preserve changed
                       change cell to
                                  change set time =
          data from old clip
                       nothing,   flag   clip's
          to new clip, change
                       set time = 0,     duration
          cell to new clip,
                       clear stopped
          set time = clip's
                       flag
          duration, preserve
          stopped flag
    contin-
          set stopped flag in
                       not meaningful,
                                  change not
    uation
          previous cell in
                       leave cell as
                                  flag   meaningful
          same row, change
                       continuation
          cell to new clip,
          set time =
          clip's duration,
          preserve stopped
          flag
    ______________________________________

    ______________________________________
    while not finished
     recalculate column
     if column changed during recalculation
      advance to next column
     else
      finished
    ______________________________________

    ______________________________________
    set minimum time of column to be infinity
    for each cell in column
     recalculate cell
     adjust minimum time of column
    for each cell of column
     set time = time - minimum time of column
    if entire column is full of nothings
     delete column
    ______________________________________

    ______________________________________
    Cell type
            t .ltoreq. 0   t > 0
    ______________________________________
    nothing leave cell as nothing
                           change cell to continuation
                           marker with clear stopped flag,
                           set time = t, update
                           minimum time (m) for column
    clip    leave cell as clip with
                           insert new column of nothings,
            original stopped flag,
                           re-evaluate from new column
            leave time as clip's
            duration, update
            minimum time (m) for
            column
    continuation
            change cell to nothing,
                           leave cell as continuation marker
    marker  set time = 0   with original stopped flag,
                           set time = t, update
                           minimum time (m) for column
    ______________________________________

    ______________________________________
    ColumnSize = #Rows * CellSize
    A = SpreadsheetSize = #Columns * ColumnSize
    B = ClipMarkerTableSize = MaxClipMarkers * sizeof(ClipMarkerTable
    entry)
    C = ColumnTableSize = #Columns * sizeof(ColumnTable entry)
    D = RowTableSize = #Rows * sizeof(RowTable entry)
    Mem Required = A + B + C + D + sizeof(Storyboard)
    Allocate the single portion of memory required for the storyboard
    If unable to allocate
     return NotEnoughMemory
    Set the maximum number of rows and columns
    Set the number of active rows and columns
    For each column:
     set the number of clip markers in the ColumnTable to 0
     set the address of the column in the ColumnTable
     For each row:
      MakeEmpty(cell)
    For each row
     set the ComponentCount in the RowTable to be 0
    Set ROMcardUsageTable to be NULL
    Store address of new storyboard in specified location
    #UnresolvedClips = 0
    #UnresolvedExternals = 0
    return OK
    ______________________________________

    ______________________________________
           If (Storyboard is playing)
            return StoryboardPlaying
           For each column from 0 to #Columns
            For each row in column
             Sub.sub.-- Delete Cell
           EvaluateCompleteStoryboard
           return OK
    ______________________________________

    ______________________________________
    If (Storyboard is playing)
     return StoryboardPlaying
    ErrorCode = Get Cell Address(row, column, cell)
    If (ErrorCode = OK)
     If (cell.type = Empty or ContinuationMarker)
      return CellContainsNonDeletableComponent
     Sub.sub.-- Delete Cell
     ErrorCode = EvaluateStoryboard(Column)
    return ErrorCode
    ______________________________________

    ______________________________________
    If (Storyboard is playing)
     return StoryboardPlaying
    ErrorCode = Get Cell Address(row, column, cell)
    If (ErrorCode = OK)
     ec = column
     If (cell.type = CONTINUATION.sub.-- MARKER)
      ec--
      Sub.sub.-- SetStoppedFlag(row, ec, TRUE)
     Sub.sub.-- Add Clip(Row, column)
     EvaluateStoryboard(ec)
    return ErrorCode
    ______________________________________

    ______________________________________
    If (Storyboard is playing)
     return StoryboardPlaying
    ErrorCode = InsertCell
    If (ErrorCode = OK)
     ec = column
     If ((GetCellAddress(row, ec+1, next.sub.-- cell) = OK) AND
      (next.sub.-- cell.type = CONTINUATION.sub.-- MARKER))
      ec--
      Sub.sub.-- SetStoppedFlag(row, ec, TRUE)
     Sub.sub.-- Add Clip(row, column)
     EvaluateStoryboard(ec)
    return ErrorCode
    ______________________________________

    ______________________________________
    If (Storyboard is playing)
     return StoryboardPlaying
    ErrorCode = ValidateFromCell(from.sub.-- row, from.sub.-- column,
    from.sub.-- cell)
    If (ErrorCode = OK)
     ErrorCode = Get Cell Address(to.sub.-- row, to.sub.-- column, to.sub.--
    cell)
    If ((ErrorCode = OK) AND (to.sub.-- cell != from.sub.-- cell))
     If (to.sub.-- cell.type = CONTINUATION.sub.-- MARKER)
      Sub.sub.-- SetStoppedFlag(to.sub.-- row, to.sub.-- column-1, TRUE)
     Sub.sub.-- Delete Cell (to.sub.-- cell)
     *to.sub.-- cell = *from.sub.-- cell
     Make.sub.-- Empty(from.sub.-- cell)
     IncrementRowUsage(to.sub.-- row)
     DecrementRowUsage(from.sub.-- row)
     if (to.sub.-- cell.type = CLIP.sub.-- MARKER)
      Update.sub.-- CM.sub.-- Entry(to.sub.-- cell.cm.sub.-- id, to.sub.--
    column)
     EvaluateCompleteStoryboard
    return ErrorCode
    ______________________________________

    ______________________________________
    If (Storyboard is playing)
     return StoryboardPlaying
    ErrorCode = ValidateFromCell(from.sub.-- row, from.sub.-- column,
    from.sub.-- cell)
    If (ErrorCode = OK)
     ErrorCode = InsertCell
    If (ErrorCode = OK)
     If ((GetCellAddress(row, column-1, prev.sub.-- cell) = OK) AND
      (cell2.type = CONTINUATION.sub.-- MARKER))
      Sub.sub.-- SetStoppedFlag(row, column-1, TRUE)
     If (row1 != row2) AND (row1 < from.sub.-- row)
      from.sub.-- row++
     If (column1 != column2) AND (column1 < from.sub.-- column)
      from.sub.-- column++
     ErrorCode = MoveCell(from.sub.-- column, from.sub.-- row, row, column)
    return ErrorCode
    ______________________________________

    ______________________________________
           return Copy.sub.-- Cell.sub.-- To.sub.-- Storyboard(this)
    ______________________________________

    ______________________________________
    If (Storyboard is playing)
     return StoryboardPlaying
    ErrorCode = ValidateFromCell(from.sub.-- row, from.sub.-- column,
    from.sub.-- cell)
    If (ErrorCode = OK)
     ErrorCode = InsertCell
    % Can copy the cell, we just must be careful about where to
    If (ErrorCode = OK)
     ec = column
     If ((GetCellAddress(row, column+1, next.sub.-- cell) = OK) AND
      (next.sub.-- cell.type = CONTINUATION MARKER))
      ec--
      Sub.sub.-- SetStoppedFlag(row, ec, TRUE)
    % Fix up from address (may have changed due to an inserted column)
     If ((row1 != row2) AND (row1 < from.sub.-- row))
      from.sub.-- row++
     If((column1 != column2) AND (column1 < from.sub.-- column))
      from.sub.-- column++
     GetCellAddress(from.sub.-- row, from.sub.-- column, from.sub.-- cell)
     Sub.sub.-- Delete Cell (to.sub.-- cell)
     ErrorCode = Sub.sub.-- Copy cell(from.sub.-- cell, to.sub.-- cell
     if (ErrorCode = OK)
      EvaluateStoryboard(ec)
    return ErrorCode
    ______________________________________

    ______________________________________
    ErrorCode = Get Cell Address(row, column, cell)
    If (ErrorCode = OK)
     Store base components of cell from clipref at specified address
    return ErrorCode
    ______________________________________

    ______________________________________
    ErrorCode = ValidateCell (Column, 0)
    If (ErrorCode = OK)
     For each cell in column
      Add Effects and Color usage to total
     Store total usage in desired location
    return ErrorCode
    ______________________________________

    ______________________________________
    ErrorCode = GetCellAddress(from.sub.-- row, from.sub.-- column,
    from.sub.-- cell
    If (ErrorCode = OK)
     If (from.sub.-- cell.type = EMPTY OR CONTINUATION.sub.-- MARKER)
      ErrorCode = InvalidCellType
    return ErrorCode
    ______________________________________

    ______________________________________
    For each entry in ColumnTable up to #Columns
     If (Column Table[entry].cells = column)
      Store column number (entry) in specified location
      return OK
    return NoSuchColumn
    ______________________________________

    ______________________________________
    ErrorCode = GetCellAddress(row, column, cell)
    If (ErrorCode = OK)
     If (cell->type = Clip)
      store cell->clipref in specified location
     Else
      ErrorCode = CellDoesNotContainClip
    return ErrorCode
    ______________________________________

    ______________________________________
    ErrorCode = ValidateCell
    If (ErrorCode = OK)
    store address of cell in specified location
    (cell address = address of (columntable[column].cells[row]))
    return ErrorCode
    ______________________________________

    ______________________________________
             If (Column# > Max.sub.-- columns)
               return ColumnOutOfRange
             If (Row# > Max.sub.-- rows
               return RowOutOfRange
             return OK
    ______________________________________

    ______________________________________
              cell.fwdarw.type = Empty
              cell.fwdarw.flags = 0
              cell.fwdarw.clipref = NULL
              cell.fwdarw.time.sub.-- remaining = 0
    ______________________________________

    ______________________________________
    ErrorCode = ValidateCell(row1#, column1#)
    If ErrorCode = OK
    ErrorCode = ValidateCell(row1#, column1#)
    If ErrorCode != OK
    return ErrorCode
    row = max(Row1#, Row2#)
    min.sub.-- row = min(Row1#, Row2#)
    column = max(Column1#, Column2#)
    min.sub.-- column = min(Column1#, Column2#)
    % Now validate that they are adjacent
    if ((row - min.sub.-- row) > 1) OR ((column - min.sub.-- column) > 1))
    return CellsNotAdjacent
    % Do the work
    If (Column1# != Column2#)
    InsertColumn(column)
    If (Row1# != Row2#)
    InsertRow(row)
    store row in specified location
    store column in specified location
    err = GetCellAddress(row, column, cell)
    return OK
    ______________________________________

    ______________________________________
    If (N > (#rows+1))
    return RowOutOfRange
    If (# rows = max.sub.-- rows)
    return OutOfMemory
    for each active column
    for (r = max.sub.-- rows-1 up to N)
    copy data from cell[r] to cell[r+1]
    set cell[r] to be Empty
    % Fix up the row table. The new row inserted has no entries yet
    for (r = max.sub.-- rows-1 up to N)
    copy row.sub.-- table[r] to row.sub.-- table[r+1]
    row.sub.-- table[r] = 0
    #rows++
    return OK
    ______________________________________

    ______________________________________
    If (R2 > max.sub.-- rows)
    return RowOutOfRange
    column = columns[0]
    count = max.sub.-- columns)
    while (count)
    % first copy the data in the column (i.e. the cells)
    to = r1
    from = r2
    while (from < max.sub.-- rows)
           cell[to] = cell[from]
           from++
           to++
    while (to < max.sub.-- rows)
           MakeEmpty(cell[to])
           to++
    % now update the row table
    to = r1
    from = r2
    while (from < max.sub.-- rows)
           row.sub.-- table[to] = row.sub.-- table[from]
           from++
           to++
    while (to < max.sub.-- rows)
           row.sub.-- table[to].count = 0
           to++
           column++
           count--
    return OK
    ______________________________________

    ______________________________________
    m = max.sub.-- columns - 1
    if (c >= m)
            return ColumnOutOfRange
    row = 0
    cell = columntable[c].cells
    while (row < #rows)
            if (cell.sub.-- type != Empty)
              return StoryboardTooSmall
            row++
            cell++
    % Now can insert the column
    tmp = columntable[m]
    while (m > c)
            columntable[m] = columntable[m-1]
            m--
    columntable[m] = temp
    return OK
    ______________________________________

    ______________________________________
            if (c2 > max.sub.-- columns)
              return ColumnOutOfRange
            while (c2 > c1)
              temp = columns[c1]
              i = c1+1
              while (i < max.sub.-- columns)
                columns[i-1] = columns[i]
              columns[i-1] = temp
              c2--
            return OK
    ______________________________________

    ______________________________________
                rowtable[row]++
    ______________________________________

    ______________________________________
                rowtable[row]--
    ______________________________________

    ______________________________________
    last.sub.-- active.sub.-- row = -1
    rows.sub.-- to.sub.-- move = 0
    row = 0
    num.sub.-- rows = max.sub.-- rows
    while (row < num.sub.-- rows)
    if (RowTable[row].count = 0)
    rows.sub.-- to.sub.-- move++
    else
    if (rows.sub.-- to.sub.-- move > 0)
            last.sub.-- active.sub.-- row++
            DeleteRows(last.sub.-- active.sub.-- row, row)
            row = last.sub.-- active.sub.-- row
            num.sub.-- rows -= rows.sub.-- to.sub.-- move
            rows.sub.-- to.sub.-- move = 0
    else
            last.sub.-- active.sub.-- row = row
    row++
    #rows = last.sub.-- active.sub.-- row + 1
    ______________________________________

    ______________________________________
    if (column < 0)
    column = 0
    CompressRows
    % See if the change was made outside the range of the active board.
    % If so, delete any columns from the active.sub.-- board up to the new
    one
    if (column >= #columns)
    columns.sub.-- to.sub.-- move = column - #columns
    #columns++
    if (columns.sub.-- to.sub.-- move > 0)
    DeleteColumns(#columns, column)
    #columns++
    return OK
    % Otherwise re-evaluate the storyboard from the column of change to a
    % point where there is no change
    last.sub.-- active.sub.-- column = column - 1
    columns.sub.-- to.sub.-- move = 0
    while (column < #columns)
    column.sub.-- status = Evaluate.sub.-- Column(column, is.sub.-- active)
    switch (column.sub.-- status)
    case CANNOT.sub.-- INSERT:
    return StoryboardTooSmall
    case INSERTED
    #columns++
    if (#columns > max.sub.-- columns)
    #columns = max.sub.-- columns
    return StoryboardTooSmall
    case CHANGED:
    case NOCHANGE:
    if (! is.sub.-- active)
    columns.sub.-- to.sub.-- move++
    if (is.sub.-- active OR (column = #columns - 1))
    if (columns.sub.-- to.sub.-- move > 0)
    last.sub.-- active.sub.-- column++
    DeleteColumns(last.sub.-- active.sub.-- column, column)
    column = last.sub.-- active.sub.-- column
    #columns -= columns.sub.-- to.sub.-- move
    columns.sub.-- to.sub.-- move = 0
    else
    last.sub.-- active.sub.-- column = column
    if (column.sub.-- status = CHANGED)
    column++
    else
    column = #columns
    column = #columns
    return OK
    ______________________________________

    ______________________________________
    CompressRows
    column = 0
    last.sub.-- active.sub.-- column = -1
    num.sub.-- cols = max.sub.-- columns
    while (column < num.sub.-- cols)
    switch (Evaluate.sub.-- Column(column, is.sub.-- active))
    case CANNOT.sub.-- INSERT:
    return StoryboardTooSmall
    case INSERTED:
    num.sub.-- cols++
    if (num.sub.-- cols > max.sub.-- columns)
    num.sub.-- cols = max.sub.-- columns
    case CHANGED:
    case NOCHANGE:
    if (is.sub.-- active)
    if (columns.sub.-- to.sub.-- move > 0)
            last.sub.-- active.sub.-- column++
            DeleteColumns(last.sub.-- active.sub.-- column, column)
            column = last.sub.-- active.sub.-- column
            num.sub.-- cols -= columns.sub.-- to.sub.-- move
            columns.sub.-- to.sub.-- move = 0
    last.sub.-- active.sub.-- column = column
    else
    columns.sub.-- to.sub.-- move++
    column++
    #columns = last.sub.-- active.sub.-- column + 1
    return OK
    ______________________________________

    ______________________________________
    is.sub.-- active = FALSE
    status = UNCHANGED
    min.sub.-- time = INFINITE
    % Get the current cell and previous column's cell
    cell = columntable[column].cells
    if (column = 0)
    prev.sub.-- cell = blank.sub.-- cell
    else
    prev.sub.-- cell = columntable[column-1].cells
    % Now go through the cells one by one
    row = 0
    while (row < #rows)
    t = prev.sub.-- cell.fwdarw.time.sub.-- remaining
    % Update status if the cell had changed due to some external source
    if (cell.fwdarw.flags.changed)
    status = CHANGED
    cell.fwdarw.flags.changed = FALSE
    % Is a clip attempting to continue into this column?
    if (t > 0)
    switch (cell.fwdarw.type)
    case EMPTY:
    cell.fwdarw.type = CONTINUATION.sub.-- MARKER
    cell.fwdarw.flags.stopped = FALSE
    cell.fwdarw.time.sub.-- remaining = t
    min.sub.-- time = min(min.sub.-- time, t)
    case CLIP:
    case CLIP.sub.-- MARKER:
    is.sub.-- active = TRUE
    if (status = CHANGED)
            cell.fwdarw.flags.changed = TRUE
    err = InsertColumn(column)
    if (err = OK)
            return INSERTED
    else
            return CANNOT.sub.-- INSERT
    case CONTINUATION.sub.-- MARKER:
    cell.fwdarw.time.sub.-- remaining = t
    cell.fwdarw.clipref = prev.sub.-- cell.fwdarw.clipref
    min.sub.-- time = min(min.sub.-- time, t)
    else
    % (t <= 0)
    switch (cell.fwdarw.type)
    case EMPTY:
    do nothing
    case CLIP:
    cell.fwdarw.time.sub.-- .sub.-- remaining = cell.fwdarw.clipref.fwdarw.dur
    ation
    min.sub.-- time = min(min.sub.-- time, cell.fwdarw.time.sub.-- remaining)
    case CLIP.sub.-- MARKER:
    is.sub.-- active = TRUE
    case CONTINUATION.sub.-- MARKER:
    Make Empty(cell)
    status = CHANGED
    fi
    % Update to be at the next cell
    cell++
    if (column > 0)
    prev.sub.-- cell++
    row++
    % Can now determine if the column is active (if not registered already)
    if (min.sub.-- time = 0)
    is.sub.-- active = TRUE
    If (is.sub.-- active AND (min.sub.-- time > 0))
    % Finally go through and adjust the time of each cell by min.sub.-- time
    cell = columntable[column].cells
    row = 0
    while (row < #rows)
    t = cell.fwdarw.time.sub.-- remaining
    if (min.sub.-- time = INFINITE)
    t = 0
    else
    if (t < INFINITE)
            t-= min.sub.-- time
    if (cell.fwdarw.flags.stopped)
    t = 0
    cell.fwdarw.time.sub.-- remaining = t
    cell++
    row++
    return status
    ______________________________________

• Inventors
  Walmsley, Simon Robert;
• Assignee
  Canon Information Systems Research Australia Pty Ltd. (North Ryde, AU); Canon Inc. (Tokyo, JP)
• Published
  Aug-19-1997
• Current US Classes:
  715/500.1
• Application #
  181247
• International Classes
  G06F 017/00
• Field of Search
  395/152-154 395/155-161 395/762 395/764 395/765 395/806 395/807
• Examiner
  Herndon; Heather R.
• Agent
  Fitzpatrick, Cella, Harper & Scinto
• US Patent References:
  4893256
  5119474
  5274758