Date: Sat, 18 Jan 1997 21:22:34 -0800 (PST) Message-Id: <199701190522.VAA08819@dawn1.CS.Berkeley.EDU> Subject: DOH draft 3 From: "Adam M. Costello" ============================================= Dancing Optical Hallucinations (DOH!) draft 3 ============================================= Sun 19 Jan 1997 Adam M. Costello Contributors: Tom Lane Glenn Randers-Pehrson All contributors to MNG draft 32 This proposal leaves out some details of chunk layout and exception handling. I am working under the premise that terminology is important, because it affects how people think. Two proposals that are isomorphic are not necessarily the same in every respect that matters. The name DOH is just a name for this draft lineage, not a suggestion for the name of a real format. Contents ======== Changes from the Previous Draft Terminology Model Format Stream Delimiters Declarations Embedded Image Definitions Directives Amphibious Note on Compositing Chunk Ordering and Copying Rules Examples Very Simple Movie Simple Movie Single Composite Frame Simple Moving Icons Simple Moving Animated Icon Efficient Moving Animated Icon Tiling Scrolling Changes from the Previous Draft =============================== Changes from draft 2: Removed the term "frame drawing sequence". Removed the default frame duration. Removed EPRO. Removed FREZ. It is now implied by the end of the first section. Removed pAUS. It is subsumed by the new eFRA. Added the terms "signal", "declaration", "directive", "stream delimiter", "declarable state", "directable state", "prologue", "section", "regular section". Added a discussion of state rules to the Model chapter. Added a discussion of criticality to the Format chapter. Added a background color to the state. Added the display writability flag. Added SECT. Added SLOO and ESLO. Added fRIN and iMIN. Added eFRA. Added the Note on Compositing chapter. Renamed DOHE to EDOH, and added a section index to it. Tightened the UNIM spec. Allowed tIME to appear in each section. Changed bACk to BACK, and added the mandatory flag. Changed LOOP. Renamed ENDL to ELOO. Changed FRAM. Changed the Chunk Ordering and Copying chapter. Updated the Examples chapter to conform to the new spec. Terminology =========== image: A 2D array of pixels, each of which has color and transparency information. All images used within a single DOH have the same sized pixels. color encoding: File gamma and chromaticity values, or an sRGB rendering intent, or whatever is involved in mapping between RGB values and colors. concrete image: An image whose pixels have a publicly visible representation, and which uses a publicly known color encoding. abstract image: An image whose pixels have a hidden representation. subimage: A rectangular region of an image. The subimage is also an image, and inherits the abstract/concrete status from the larger image. If concrete, it inherits the color encoding of the larger image, and the palette if there is one. image delta: An object that can be applied to a concrete image to produce another concrete image. For any two concrete images, there exists an image delta which will produce one from the other. parent image: An image to which a delta is applied. child image: An image produced by applying an image delta to a parent image. embedded image: A concrete image that appears in-line in a DOH stream. buffer: A conceptual place where an image or target (see below) can be stored. There are many buffers, with integer IDs starting at 0. target: An object specifying a point in an image. It contains a buffer ID, called the target image ID, and (x,y) coordinates, called the target point. image N: Shorthand for "the image in buffer N". target N: Shorthand for "the target in buffer N". frame: An image that should be displayed as part of an animation. An animation should ideally appear to a perfect observer (with an inhumanly fast visual system) as a sequence of still images. frame duration: The amount of time a frame should be visible when an animation is played. In reality, it takes a non-zero amount of time to display a frame. No matter which moment is picked as the "start" of the frame, the frame duration measures the time to the "start" of the next frame. signal: An entity with a name that can arrive at the decoder at a particular time. More detailed semantics, like whether multiple signals of the same name (or even different names) can be queued, are beyond the scope of this specification. declaration: A kind of chunk. Declarations are unordered. directive: A kind of chunk or sequence of chunks. Directives are ordered. A directive may contain multiple chunks only if the first is critical. stream delimiter: A kind of chunk. The stream delimiters are DOHH, SECT, EDEC, SLOO, ESLO, and EDOH. declarable state: State that can be affected by declarations. directable state: State that can be affected by directives. prologue: The part of a DOH stream after DOHH and before the first SECT chunk. See alse the Format chapter. section: A part of a DOH stream starting with a SECT chunk and extending to just before the next SECT chunk (or EDOH chunk if there is no next SECT chunk). See also the Format chapter. regular section: Any section other than the first. frozen buffer: A buffer which is not allowed to be affected, i.e. discarded, replaced, or modified. sprite: An object with a position, an active/inactive flag, a depth relative to the other sprites, and a pointer to an image. When a sprite's parameters are changed or its image is changed, the display is updated automatically, without the need for drawing instructions. Model ===== There are no sprites. Images are either abstract or concrete, depending on how they are created, but there are no abstract/concrete flags anywhere in the DOH stream. Every piece of state defined in this specification and in future extensions must be specified as declarable or directable, not both. All buffers and their contents are directable. Every section starts with the same declarable state, determined by the prologue. The decoder is responsible for restoring this state at the start of each section. This modest burden on the decoder allows sections to be kept mostly independent of each other (see the Chunk Ordering and Copying Rules chapter). All buffers except buffer 0 that are nonempty at the end of the first section are frozen, and all subsequent sections (called "regular sections") are forbidden from affecting frozen buffers, and are forbidden from making assumptions about the initial contents of any unfrozen buffers. These restrictions on the encoder allow the decoder, at any time after it has processed the first section, to jump to the beginning of any regular section, optionally discarding the contents of all unfrozen buffers. If it jumps to the start of the first section, it must reinitialize not only the declarable state (as always), but also the directable state (as described below), and must process the entire first section before jumping again. At the start of the first section, all buffers are empty except buffer 0, which contains a completely transparent abstract image with dimensions specified in DOHH. Buffer 0 cannot be discarded, nor replaced. It contains the one and only displayed image; the frames of the animation are the states of image 0 at the end of each frame definition (see FRAM and eFRA). There is a default color encoding, declarable, which is undefined unless declared. There is a background color, declarable, which can be either mandatory or advisory, which is undefined unless set by the declaration BACK. There is a display writability flag, directable, which is affected by SECT, FRAM, and eFRA. This flag is not actually useful, and needn't be implemented by decoders--it is a trick for describing a requirement of encoders. No directive may affect image 0 unless the display writability flag is . Note that decoders are not required to follow this model, nor to follow the instructions in this specification, as long as they produce results identical to those that could be produced by a decoder that did use this model and did follow the instructions. Format ====== DOH uses the same chunk format and chunk naming conventions as PNG. ::= DOHH EDOH ::= * ::=
(
| )*
::= * ::= SECT ( * EDEC )? ::= SLOO (
| )* ESLO All chunks defined in future extensions must be declarations or directives, or both. A chunk which is both must obey the state-modification rules stated in the Model chapter, either by behaving differently in different contexts, or by never modifying any state at all. All decoders must understand all the stream delimiters. If a decoder does not understand a critical chunk in a regular section, it must assume that it does not understand the entire section. If a decoder does not understand a critical chunk in the prologue or the first section, it must assume that it does not understand the entire DOH. The individual chunks are specified below. Stream Delimiters ----------------- DOHH: DOH header Width Height Rate (ticks per second) Specifies the dimensions of image 0 (the display) and the meaning of "tick". SECT: section header Declare (boolean) Name (text) SECT marks the beginning of each section. The decoder must restore the declarable state to what it was at the end of the prologue. SECT also resets the display writability flag to . The SECT chunk may contain the first one or two of the fields listed above. If and only if declare is , SECT must be immediately followed by zero or more declarations and then an empty EDEC chunk. Those declarations can modify the declared state. The name field provides a name for the section. If it is missing, the section has no name. EDEC: end of declarations Empty. See SECT. SLOO: section loop Exactly like LOOP, except that it defines a loop of sections rather than a loop of directives. Note that the decoder knows more invariants regarding the state at the top of a loop of sections than it does at the top of a loop of directives, which might allow some optimizations. ESLO: end section loop Exactly like ELOO, except that it matches with SLOO rather than LOOP. EDOH: end of DOH Stream offset Section name (null-terminated text) ... Chunk length The EDOH chunk may contain only the chunk length field, or may contain one entry for each section of the DOH (in order of appearance), followed by the chunk length field. Each entry contains the offset of the corresponding SECT chunk (the number of bytes preceeding the SECT chunk in the DOH stream) followed by the section name (the empty string if the section has no name) The chunk length field is the same as the one at the very beginning of the EDOH chunk. Every encoder is obligated to write a valid EDOH chunk. If the encoder is not ambitious enough to write a fully informative EDOH chunk, it must write a trivial one containing only the chunk length field. Decoders with random access to the DOH can locate the chunk length field by seeking backward 8 bytes from the end of file. The decoder is then able to seek to the beginning of the EDOH chunk. If the EDOH chunk is non-trivial, the decoder is then able to seek to the beginning of any section. Declarations ------------ Except where noted, the declarations below are free to appear in both the prologue and section headers. gAMA, cHRM, sRGB Same format as in PNG. They specify the default color encoding. Each of these chunk types may appear at most once in the prologue, and at most once in each section. When one of these chunks appears in the prologue, it can be overridden but not undone. If the encoder would like to undo one of them, the encoder should not have put the chunk in the prologue in the first place. sPLT Same format and meaning as in PNG. May appear zero or more times. If sPLT appears in the prologue, the suggestion applies to the entire DOH. If it appears in a section, the suggestion applies only to that section. No sPLT chunk may have the same name as another sPLT chunk in the same section or in the prologue. pHYs Same format and meaning as in PNG. May appear at most once, only in the prologue. tIME Same format as in PNG. May appear at most once in the prologue, and at most once per section. In the prologue it indicates the last time any part of the DOH was modified. In a section it indicates the last time that section was modified. dISR: display restrictions May read (boolean) May replace pixels (boolean) May composite over (boolean) May composite under (boolean) May appear at most once, only in the prologue. If the may read field is , it is a promise that image 0 (and any subimage thereof) will never be used as a source image. If any of the other flags is , it is a promise that the corresponding operation type will never be used when image 0 is the destination. BACK: background color Red Green Blue Mandatory (boolean) Sets the background color. May appear at most once in the prologue, and at most once per section. The RGB values use a bit depth of 16, and are interpreted according to the default color encoding (which means that BACK cannot be interpreted until all declarations in the prologue or section have been processed). If mandatory is , the color is only a suggestion for use when the decoder does not already have its own background. If mandatory is , the decoder must obscure its own background, and use a solid background instead. tERm: termination Termination Suggests how the end of the DOH stream should be handled. May appear at most once, only in the prologue. The termination field may take the following values: Cease displaying anything. Show the last frame indefinitely. Repeat the animation starting at the end of the first section. Repeat the animation starting at the beginning of the first section. fRIN: frame index Section name (null-terminated text) Frame name ... (null-terminated text) Empty string (null byte) ... Contains one entry for each section. Each entry contains the name of a section, followed by a sequence of frame names appearing in that section, followed by the empty string. [Should we require the sections to appear in order? The frames? Should we require all named sections to appear? All named frames?] iMIN: image index Section name (null-terminated text) Exported image name ... (null-terminated text) Empty string (null byte) ... Exactly like fRIN, except that it contains exported image names (see eXPI) instead of frame names. [Same questions as fRIN.] Embedded Image Definitions -------------------------- Three of the directives are subclassified as embedded image definitions. If any of them is not immediately preceeded by a ROUT chunk, then a ROUT chunk is implied. The contents of the implied ROUT chunk depend on the type of embedded image. (ROUT determines what is done with the embedded image.) See the Directives portion of this chapter for the rest of the directives, including ROUT. IHDR...IEND Defines a concrete image. See the PNG spec. Any chunks inside the PNG which attempt to set the pixel dimensions or the drawing location must be ignored. If the PNG contains no gAMA, cHRM, or sRGB chunks, it inherits the default color encoding; if it contains any of those chunks, it completely ignores the default color encoding. If it is not preceeded by a ROUT chunk, then "ROUT 0 0 0 " is implied. IDEL...IEND Encodes an image delta, which contains the ID of a buffer which must contain a concrete image, which is the parent image. The resulting child image is the embedded image. Note that the image in the buffer is not necessarily affected. But if the IDEL is not immediately preceeded by a ROUT chunk, then "ROUT parentID 0 0 0 " is implied, in which case the parent is affected. Cases in which the parent gets modified can allow for the avoidance of a copy, and decoders will probably want to take advantage of that. The format of an image delta is defined elsewhere. UNIM: uniform image Width Height Bit depth Color type Red Green or gray Blue Alpha Index Defines a concrete image of the specified parameters. If the color type is indexed, every pixel uses the specified palette index, and the palette has Index+1 entries, all identical, defined by the RGBA fields. The image inherits the default color encoding. Some of the fields are ignored for some color types, but they must all be present. If UNIM is not preceeded by a ROUT chunk, then "ROUT 0 0 0 " is implied. Directives ---------- COBU: copy buffer Source ID Destination ID Copies the contents of the source buffer into the destination buffer, replacing its current contents (if any). This works no matter whether the source buffer contains an image, target, or nothing. If multiple source/dest pairs appear, they are processed sequentially. TRAS: transfer subimage Source ID Source offset X Source offset Y Width Height Storage ID Drawing ID Drawing offset X Drawing offset Y Operation type If the source buffer contains an image, either concrete or abstract, the source image is a subimage thereof, as specified by the source offset, width, and height. If the source buffer contains a target, the source image is a subimage of its target image, and the source offset is relative to the target point rather than the origin. If the drawing buffer contains an image, it is the destination image, and the source image's origin is offset from the destination image's origin as specified by the drawing offset. If the drawing buffer contains a target, its target image is the destination image, and the destination offset is relative to the target point. The destination image must be abstract. The operation type may be or or , and specifies the manner in which the source image is to be drawn onto the destination image. If the storage ID is not the source image is copied into the storage buffer, replacing its current contents (if any). The drawing ID, drawing offsets, and operation type may be omitted, in which case no drawing takes place. The drawing ID must differ from the storage ID. The decoder must be careful when the destination image equals the source image--the pixels to be drawn are the ones that existed before the drawing operation began. DRIM: draw image Source ID Drawing ID Drawing offset X Drawing offset Y Operation type A simplified version of TRAS. The source image is an entire image, not a subimage. If the source buffer contains a target, its target image is the source image, but the target point is ignored. There is no storage ID, so no copy is made. Unlike TRAS, DRIM does not allow fields to be omitted, and it does allow multiple sets of parameters, in which case they are processed sequentially. ROUT: route embedded image Storage ID Drawing ID Drawing offset X Drawing offset Y Operation type Exactly like TRAS, except that the source image is not a subimage of an existing image, but is rather an entire embedded image, which must immediately follow the ROUT chunk. ABIM: new abstract image Destination ID Width Height Creates a new abstract image, totally transparent, of the given dimensions, and stores it in the specified buffer, replacing the current contents (if any). If multiple sets of parameters appear, they are processed sequentially. TARG: target Destination ID Change target X (no/replace/increment) Change target Y (no/replace/increment) Target X Target Y Target image ID If the destination buffer does not contain a target, a new one with target image ID 0 and offset (0,0) is created, replacing the current contents of the destination buffer (if any). Then the target is modified according to the parameters. The target image ID may be , otherwise it replaces the existing value in the buffer. If multiple sets of parameters appear, they are processed sequentially. DISC: discard Buffer ID Discards the contents of the specified buffer. If multiple IDs appear, all the buffers are emptied. If the chunk is empty, all unfrozen buffers except buffer 0 are emptied. Empty DISC chunks may not appear in the first section. Encoders are encouraged to discard buffer contents when they are no longer needed, especially in the first section. FRAM: frame definition Duration (in ticks) Name (text) The first in a sequence of directives which together define a frame. FRAM sets the display writability flag to . The first frame in a regular section must completely overwrite image 0 (the display) because it may not assume anything about the contents of unfrozen buffers. FRAM may contain the first one or two of the fields listed above. Duration specifies the frame duration for the frame being defined. The name field provides a name for the frame being defined. If it is absent, the frame has no name. Encoders should put FRAM chunks as early in the stream as possible, to enable decoders to do more planning. eFRA: end of frame definition Termination condition Timeout (in ticks) Signal name Marks the end of a frame definition, and resets the display writability flag to . A frame definition need not be terminated by eFRA; it can also be terminated by the next FRAM chunk or by a stream delimiter chunk, in which case the termination condition is (see below). A simple decoder can ignore all the fields. The timeout field can be a number or . The termination condition specifies how much longer, after the normal frame duration has elapsed, the frame will endure. It can take the following values: The frame endures no longer than the normal frame duration. Even though this is the default, a streaming encoder talking to a real-time decoder might write eFRA with a condition of to force the display to be updated while the encoder decides its next move. The decoder may lengthen the duration of the frame, by no more than the timeout. A streaming decoder could use take the opportunity to wait for its input buffer to fill to a comfortable level. The decoder should wait for permission from the user (e.g. via a keypress) before proceeding, but must wait no longer than the timeout. If the decoder cannot interact with the user, this condition degenerates into . The decoder should wait for the arrival of a signal whose name matches the name field, but must wait no longer than the timeout. The signal name field may be omitted if the termination condition is not . LOOP: begin loop Nest level Iteration count Termination condition Iteration min Iteration max Signal name (text) Causes the directives between LOOP and the matching ELOO to be executed multiple times. LOOP may contain the first three, five, or six fields listed above. Simple decoders can ignore all fields except iteration count. [Should we forbid IHDR and IDEL inside directive loops? Or discourage them?] The nest level must be strictly greater than that of any enclosing LOOP, but need not be exactly one greater (it helps in recovering from a corrupt stream). The iteration count, iteration min, and iteration max may be any non-negative integers or , but must satisfy min <= count <= max. The termination condition specifies how the actual number of iterations is determined. It is very similar to the termination condition field of eFRA, and may take the same values: The loop terminates after exactly the number of iterations specified by the iteration count. This value must be used if altering the number of repetitions would mess up the DOH stream, but may be used merely to preserve the author's intent. The number of iterations may be chosen by the decoder, and must fall between the iteration min and max. If the decoder has no reason to choose its own value, it should use the iteration count. One example of a decoder wishing to choose its own value is a real-time streaming decoder hovering at a loop while waiting for its input buffer to fill to a comfortable level. The number of iterations should be chosen by the user (e.g. by pressing the escape key), but the decoder must enforce the min and max limits. Some decoders may not be able to interact with the user, and many (most?) decoders will find that nested user-discretion loops present too great of a user-interface challenge, so the condition may degenerate into the condition. The number of iterations must lie between the min and max limits, but the exact number can be determined by the arrival of a signal whose name matches the signal name field. The signal name may be omitted only if the termination condition is not . The iteration min and max may be omitted only if the condition is . ELOO: end loop Nest level Closes the scope of the matching LOOP directive, which must have an equal nest level. eXPI: export image Source ID Name (text) Takes a snapshot of the image (either concrete or abstract) in the specified buffer, associates the name with that snapshot, and makes the name available to the "outside world" (like a scripting language). Note that the name is associate with the snapshot, not the buffer nor its future contents; discarding the contents of the buffer will not affect the snapshot. The name means nothing inside the DOH. If two eXPI chunks use the same name, it is the outside world's problem (and the outside world's prerogative to regard it as an error). A decoder that knows of no "outside world" can simply ignore eXPI. This chunk could be used in DOHs that define libraries of related images, rather than (or in addition to) animations. Names beginning with "thumbnail" are reserved for snapshot images that are intended to make good icons for the DOH. Amphibious ---------- The following chunks can be used as both declarations and directives, because they do not affect any state. tEXt, zTXt Same format and meaning as in PNG. Note on Compositing =================== The PNG specification gives a good explanation of how to composite a partially transparent image over an opaque image, but things get more complicated when both images are partially transparent. Pixels in PNG images are represented using gamma-encoded RGB (or gray) samples along with a linear alpha value. Alpha processing can only be performed on linear samples. This chapter assumes that R, G, B, and A values have all been converted to real numbers in the range [0,1], and that any gamma encoding has been undone. For a top pixel (Rt,Gt,Bt,At) and a bottom pixel (Rb,Gb,Bb,Ab), the composite pixel (Rc,Gc,Bc,Ac) is given by: Ac = 1 - (1 - At)(1 - Ab) s = At / Ac t = (1 - At) Ab / Ac Rc = s Rt + t Rb Gc = s Gt + t Gb Bc = s Bt + t Bb When the bottom pixel is fully opaque (Ab = 1.0), the function reduces to: Ac = 1 Rc = At Rt + (1 - At) Rb Gc = At Gt + (1 - At) Gb Bc = At Bt + (1 - At) Bb When the bottom pixel is not fully opaque, the function is much simpler if premultiplied alpha is used. A pixel that uses non-premultiplied alpha can be converted to premultiplied alpha by multiplying R, G, and B by A. For a premultiplied top pixel (Rt,Gt,Bt,At) and a premultiplied bottom pixel (Rb,Gb,Bb,Ab), the premultiplied composite pixel (Rc,Gc,Bc,Ac) is given by: Ac = 1 - (1 - At)(1 - Ab) Rc = Rt + (1 - At) Rb Gc = Gt + (1 - At) Gb Bc = Bt + (1 - At) Bb As mentioned in the PNG specification, the equations become much simpler when all the alpha values are integers, and the RGB samples need not be linear in that case. Chunk Ordering and Copying Rules ================================ The chunks defined in this specification, and chunks defined in future extensions to this specification, must obey some basic rules. * Declarations may have no ordering restrictions beyond those implied by the grammar in the Format chapter, except that some declarations may be allowed only in the prologue. * Directives may have arbitrary ordering restrictions relative to each other and relative to stream delimiters, in addition to the restrictions implied by the grammar in the Format chapter. * There can be no new stream delimiters, only new declarations and directives. An editor is a program which makes changes to an existing DOH. Because an editor might not be intimately familiar with the DOH, it must be careful to avoid inadvertantly breaking the DOH. The remainder of this chapter contains rules for editors, which should also be studied by designers of new ancillary chunks. An editor must not edit a DOH or a section that it does not understand, according to the definition of "understand" in the Format chapter. Each change that an editor makes is classified as either safe or unsafe. Alterations of existing ancillary chunks are safe. Alterations of existing critical chunks are generally unsafe, but the specification of a critical chunk may bless certain alterations as safe. [Do we want any of the critical chunks in this spec to bless any changes? Remember, no ancillary chunk can ever depend on information that is safe to change.] Reordering of directives (even ancillary ones) is unsafe. Reordering of declarations (even critical ones) is safe. The insertion or deletion of a directive is unsafe. The insertion or deletion of a declaration is safe if it is ancillary, unsafe if it is critical (unless its specification has blessed its insertion or deletion as safe). If an editor makes an unsafe change to a regular section, it must delete all unknown unsafe-to-copy chunks in that section, and in the first section, and in the prologue. If an editor makes an unsafe change to the first section, or the prologue, or DOHH, it must delete all unknown unsafe-to-copy chunks in the entire DOH. Chunks inside embedded images are an exception: They are immune from changes (even unsafe ones) made outside the embedded image. Internal changes to an embedded image may require internal chunks to be discarded, but that situation is covered by the specification of the embedded image format. The editor must always write a valid EDOH. See EDOH. Examples ======== Very Simple Movie ----------------- DOHH ... SECT FRAM IHDR ... IEND # implied "ROUT 0 0 0 " FRAM IHDR ... IEND # implied ROUT FRAM IHDR ... IEND # implied ROUT EDOH ... Simple Movie ------------ DOHH ... sRGB ... SECT # allow easy seeking to the next section SECT FRAM ROUT 2 0 0 0 IHDR ... IEND # store in buffer 2 and draw to display FRAM IDEL 2 ... IEND # alter image 2 and composite over display FRAM IDEL 2 ... IEND # alter image 2 and composite over display SECT FRAM ROUT 2 0 0 0 IHDR ... IEND # store in buffer 2 and draw to display FRAM IDEL 2 ... IEND # alter image 2 and composite over display EDOH ... Single Composite Frame ---------------------- DOHH ... gAMA ... cHRM ... sPLT ... pHYs ... tERm ... SECT FRAM ROUT 2 IHDR ... IEND # store in buffer 2, but do not draw eXPI 2 "thumbnail" ROUT 2 IHDR ... IEND # store in buffer 2, but do not draw eXPI 2 "thumbnail" ROUT 2 0 0 0 IHDR ... IEND # store in buffer 2 and draw to display ROUT 2 0 x y IDEL 2 ... IEND # alter image 2 and composite over # display at a different location DISC 2 # discard image 2 ROUT 0 x y IHDR ... IEND # draw a new image at a third location EDOH ... Simple Moving Icons ------------------- DOHH ... sRGB ... SECT ROUT 10 IHDR ... IEND # store background image, but do not draw ROUT 11 IHDR ... IEND # store first icon, but do not draw ROUT 12 IDEL 11 ... IEND # second icon is modified version of first SECT FRAM DRIM 10 0 0 0 # draw background 11 0 x1 y1 # draw first icon 12 0 x2 y2 # draw second icon SECT FRAM DRIM 10 0 0 0 # draw background 11 0 x3 y3 # draw first icon 12 0 x4 y4 # draw second icon # repeat SECT, FRAM, DRIM cycle several times EDOH ... Simple Moving Animated Icon --------------------------- DOHH ... sRGB ... SECT ROUT 10 IHDR ... IEND # background image ROUT 11 IHDR ... IEND # icon view 1 of 4 ROUT 12 IDEL 11 ... IEND # icon view 2 of 4 ROUT 13 IDEL 12 ... IEND # icon view 3 of 4 ROUT 14 IDEL 13 ... IEND # icon view 4 of 4 TARG 1 ... # new target for icon LOOP ... FRAM DRIM 10 0 0 0 # draw background 11 1 0 0 # draw icon view 1 TARG 1 ... # increment target point FRAM DRIM 10 0 0 0 # draw background 12 1 0 0 # draw icon view 2 TARG 1 ... # increment target point FRAM DRIM 10 0 0 0 # draw background 13 1 0 0 # draw icon view 3 TARG 1 ... # increment target point FRAM DRIM 10 0 0 0 # draw background 14 1 0 0 # draw icon view 4 TARG 1 ... # increment target point ENDL ... EDOH ... Efficient Moving Animated Icon ------------------------------ # Possibly improve efficiency in three ways: # * Do not redraw entire background for every frame, only the part # corrupted by the icon. An especially sophisticated decoder could # figure this out itself. # * Use abstract images for the icon views, rather than concrete. # Drawing an abstract image is likely to be more efficient. # * Apply image deltas in-place (child replaces parent). DOHH ... sRGB ... SECT FRAM "" 0 IHDR ... IEND # draw background image ABIM 11 ... # create abstract images for icon view 1 12 ... # and view 2 13 ... # and view 3 14 ... # and view 4 ROUT 10 11 0 0 IHDR ... IEND # icon view 1 of 4 ROUT 10 12 0 0 IDEL 10 ... IEND # icon view 2 of 4 ROUT 10 13 0 0 IDEL 10 ... IEND # icon view 3 of 4 ROUT 10 14 0 0 IDEL 10 ... IEND # icon view 4 of 4 TARG 1 ... # new target for icon TRAS 1 0 0 w h 10 # save background behind icon LOOP ... FRAM DRIM 10 1 0 0 # restore background TARG 1 ... # increment target point TRAS 1 0 0 w h 10 # save background behind icon DRIM 11 1 0 0 # draw icon view 1 FRAM DRIM 10 1 0 0 # restore background TARG 1 ... # increment target point TRAS 1 0 0 w h 10 # save background behind icon DRIM 12 1 0 0 # draw icon view 2 FRAM DRIM 10 1 0 0 # restore background TARG 1 ... # increment target point TRAS 1 0 0 w h 10 # save background behind icon DRIM 13 1 0 0 # draw icon view 3 FRAM DRIM 10 1 0 0 # restore background TARG 1 ... # increment target point TRAS 1 0 0 w h 10 # save background behind icon DRIM 14 1 0 0 # draw icon view 4 ENDL ... EDOH ... Tiling ------ DOHH ... sRGB ... SECT FRAM ABIM 10 ... # abstract image for tile ROUT 10 IHDR ... IEND # tile LOOP ... LOOP ... DRIM 10 0 0 0 # copy tile onto display TARG 1 ... # increment target X ENDL ... TARG 1 ... # reinit target X and increment Y ENDL ... EDOH ... Scrolling --------- Date: Sat, 18 Jan 1997 21:26:02 -0800 (PST) Message-Id: <199701190526.VAA08836@dawn1.CS.Berkeley.EDU> To: mpng-list@dworkin.wustl.edu Subject: IDS draft 3 From: "Adam M. Costello" ================================ Image Delta Stream (IDS) draft 3 ================================ Sun 19 Jan 1997 Adam M. Costello Contributors: Glenn Randers-Pehrson All contributors to MNG draft 32. This proposal leaves out some details of chunk layout and exception handling. IDS is just a name for this draft, not a suggestion for the name of a real format. Contents ======== Changes from the Previous Draft Design Goals Format Non-Pixel Operations Pixel Operations Changes from the Previous Draft =============================== Changes from draft 2: Removed the Motivating Thoughts chapter. Removed the Relation to DOH chapter. Removed the Comparison with PND chapter (it will appear separately). Added the Design Goals chapter. Changed IDEL. Renamed the Stream Format chapter to Format, and subdivided it. Completely revamped the way non-pixel data is altered. Renumbered the orientation field values in CPIX. Design Goals ============ An IDS may be applied to a parent PNG to produce a child PNG, or the same IDS may be applied to a parent concrete image to produce a child concrete image. An IDS can be designed to work with a variety of parent PNGs or images, but there is no requirement that an IDS must work with every possible parent. The applier of the IDS needs only streaming access to the IDS, but may need random access to the parent PNG or image. Format ====== ::= IDEL IHDR ( DROP | DBYK | ORDR )* * IEND ::= | IDAT+ | * | ( CPIX* * ) ::= EPIX IDAT+ IDEL: image delta Source ID Pixel operation (replace/edit/copy-and-edit) Deepening function (left-bit-replication/zero-fill) If the pixel operation is , and the pixel data portion must be a sequence of one or more IDAT chunks. All fields of the IHDR are significant, and need bear no relation to the parent. If the pixel operation is , the width and height must match those of the parent, the bit depth and color type must not be less than those of the parent, and the remaining IHDR fields are ignored. The pixel data portion must be a sequence of zero or more pixel edits (see EPIX). The pixel data of the parent is used to initialize the pixel data of the child, but the edits can then alter the pixel data. If the pixel operation is , the width and height need not match those of the parent, the bit depth and color type must not be less than those of the parent, and the remaining IHDR fields are ignored. The pixel data portion must be a sequence of zero or more CPIX chunks followed by a sequence of zero or more pixel edits (see EPIX). The pixel data portion is obligated to overwrite the entire child pixel array, because it is not initialized. The CPIX chunks can copy pixels from the parent. The less-than relation on color types is defined by the following partial order: RGBA / \ RGB GA / \ / indexed G RGBA is the greatest color type. Non-Pixel Operations -------------------- Immediately following the IHDR is a sequence of zero or more DROP, DBYK, and ORDR chunks, followed by zero or more PNG chunks. These tell the applier of the delta what chunks other than IHDR, IDAT, and IEND should appear in the child PNG, and where. This portion of the IDS can also be used to determine changes to be made to a concrete image. DROP: drop chunks Chunk name All chunks in the parent with the specified name are inhibited from being copied into the child. If multiple name appear in DROP, it is shorthand for multiple DROP chunks. DBYK: drop by keyword Chunk name Polarity (only/all-but) Keywords (null-separated text strings) The chunk name must be the name of a chunk that begins with a null-terminated text string. Some parent chunks with the specified chunk name are inhibited from being copied into the child. If polarity is , then any parent chunk whose keyword appears in the keywords list is inhibited. If polarity is , then any parent chunk whose keyword does not appear in the keywords list is inhibited. ORDR: ordering restrictions Chunk name Order type ORDR informs the applier of the IDS of the ordering restrictions for chunks. The order type may take the following values: 0: anywhere 1: after IDAT 2: before IDAT 3: before IDAT, but not before PLTE 4: before IDAT, but not after PLTE Critical chunk names may not appear in ORDR, since the applier needs to know everything about them anyway. If a chunk name appears in ORDR, it is a promise that any chunk of that name appearing in the parent which is not inhibited by DROP/DBYK will not be broken by this IDS, and therefore the applier must copy it into the child at a location compatible with its ordering restrictions. After all the DROP, DBYK, and ORDR chunks there may appear zero or more PNG chunks other than IHDR, IDAT, and IEND. For any that are ancillary (i.e. any other than PLTE), their names must have appeared in an ORDR chunk, so that the applier knows where they can be placed in the child. If any ancillary chunk appears in the parent, and it is not inhibited, and its name does not appear in ORDR, then the applier should copy it into the child only if it knows the chunk well enough to be sure that it is consistent with the changes made by the IDS, and knows where it may be placed in the child. Those conditions are always true of safe-to-copy chunks. If any critical chunk defined in neither this specification nor the PNG specification appears in the parent or in the IDS, it is a fatal error unless the applier knows how to handle it. The specification of the critical chunk may include provisions for this scenario. If the IDS is being applied to a concrete image rather than a PNG, the ORDR chunks can be ignored. The DROP, DBYK, and PNG chunks indicate what changes need to be made to the parent image in order to produce the child. Pixel Operations ---------------- If the child color type does not equal the parent color type, then the applier needs to promote the pixel data before it can perform pixel copying or editing. The cases are: G -> GA Don't change the gray values. Set all the alpha values to fully opaque, except for pixels marked transparent by cheap transparency--set their alpha values to fully transparent. Discard the cheap transparency information. RGB -> RBGA Don't change the RGB values. Handle the alpha values as in the G -> GA promotion. G -> RGB Set R, G, and B equal to the gray value. Apply the same operation to the cheap transparency information (if any). GA -> RGBA Set R, G, and B equal to the gray value. Don't change the alpha values. G -> RGBA Set R, G, and B equal to the gray value. Handle alpha values as in the G -> GA promotion. indexed -> RGB Set R, G, and B according to the palette entry corresponding to the index. Discard the cheap transparency information (if any). indexed -> RGBA Set R, G, and B as in indexed -> RGB. Set the alpha value according to the cheap transparency information (if any). Discard the cheap transparency information. If the bit depth has been changed, values may need to be deepened. The applier must use left-bit-replication or zero-fill according to the deepening function in IDEL. Remember that if the color type has been promoted from indexed, the parent bit depth is considered to be 8. In some cases, the parent pixel array can be mutated (destructively) into the child pixel array. In others, the parent pixel array can be discarded as soon as the child array is initialized. But if the pixel operation is , the parent array is still needed while the copies are being performed. All pixel copies must preceed all pixel edits. Copies and edits must be processed sequentially in order of appearance. CPIX: copy pixels Source X Source Y Width Height Destination X Destination Y Orientation Copy a rectangle of pixels from the parent pixel array into the child pixel array. The source X and Y values are in the parent's coordinate system, while the destination X and Y values are in the child's coordinate system. The destination point specifies where the original upper-left pixel of the rectangle falls in the child image. The orientation is one of: 0: 1 2 -> 1 2 3 4 3 4 1: 1 2 -> 4 3 3 4 2 1 2: 1 2 -> 3 1 3 4 4 2 3: 1 2 -> 2 4 3 4 1 3 4: 1 2 -> 2 1 3 4 4 3 5: 1 2 -> 3 4 3 4 1 2 6: 1 2 -> 1 3 3 4 2 4 7: 1 2 -> 3 2 3 4 4 1 Notice that bit 2 indicates whether the rectangle is mirrored, bit 1 indicates whether it is sideways, and bit 0 indicates whether the original upper-left corner ends up at the top or the bottom. EPIX: edit pixels Destination X Destination Y Width Height Edit type Compression method Filter method Interlace method EPIX is followed by a sequence of IDATs containing (width * height) pixels, filtered, interlaced, and compressed (see the PNG specification). Those pixels are used to modify a rectangle within the child pixel array, whose upper-left corner is given by the destination X and Y. The bit depth and color type are not specified by EPIX because they must match those of the child pixel array (except as noted below). The nature of the modification is specified by the edit type, which is one of: The pixels in the IDATs replace the pixels in the child array. The pixels in the IDATs are used to increment the pixels in the child array. The addition is by sample, modulo 2^bitdepth. The pixels in the IDATs use color type G, and are used to replace the alpha values in the child array. The pixels in the IDATs use color type G, and are used to increment the alpha values in the child array. The addition is by sample, modulo 2^bitdepth. -- Send the message body "help" to mpng-list-request@dworkin.wustl.edu