Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Dynamic Window ID Computation

IP.com Disclosure Number: IPCOM000112330D
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 8 page(s) / 192K

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR

Abstract

In a graphics window system different windows may have different pixel interpretations, i.e., one window may be a 24-bit true color window while another window may be a 12-bit double-buffered window. These differences need to be conveyed to the display device for correct display of the image.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 25% of the total text.

Dynamic Window ID Computation

      In a graphics window system different windows may have
different pixel interpretations, i.e., one window may be a 24-bit
true color window while another window may be a 12-bit
double-buffered window.  These differences need to be conveyed to the
display device for correct display of the image.

      Traditionally this has been done by using window-id planes in
the frame buffer.  In this work we develop a data structure and an
algorithm for evaluating the pixel interpretation dynamically.  The
data structure is similar to the concept of active edge lists in
graphics and computational geometry [1,2].  We then consider the
insertion and deletion of windows into this data structure.

ALGORITHM

      Given is a set of windows and their relative visibility
priorities and pixel interpretation modes.  The visibility priorities
of the windows define a partial order.  If two windows do not
overlap, their relative visibility is not important for this
algorithm.

      The main idea here is to be able to obtain a list of
"separators" for each scan line.  An active separator is a vertical
line segment which separates two regions with different pixel
interpretations.  The list of separators is maintained in a sorted
order by the "x" coordinate for the separator.  Once the list of
active separators has been obtained it is simple to traverse this
list and determine the interpretation for a pixel.

      Note: The horizontal edges of the windows are ignored because
their contribution can be accounted for by the vertical edges.

Examples - The algorithm will be derived through a sequence of
examples shown in Figs. 1-3.  In these examples P(x) refers to the
pixel interpretation of a window of which "x" is a part.  The
expression "a>b" means that the visible priority of edge "a" is
higher than that of edge "b".  $P(W)$ refers to the pixel
interpretation of window "W", and "P(e)" refers to the pixel
interpretation of edge "e".  In our separator list data structure, an
entry "a" implies that edge "a" is an active separator, an entry "b'"
implies that edge "b" is an invisible separator, and an entry "c''"
implies that edge "c" is a dormant separator, i.e., it is visible but
is not an active separator because of identical pixel interpretations
for more than one window.  Thus a list "a g b' h" gets interpreted as
the list of "a g h" of active separators.  For pixels in the range
[a, g) the interpretation is the same as that for "a".  Similarly in
the range [g, h) the interpretation is the same as that for "g".  If
separators "a" and "b" belong to the same window they are referred to
as each other's complement.  The separator for the left edge of a
window is called an "originating" separator.  The separator for the
right edge of a window is called a "terminating separator."

      Fig. 1 shows an example window configuration.  There are 4
windows.  Each of these has a different pixel int...