Dynamic Window ID Computation
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-27
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.
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.
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.
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
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.
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
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
windows. Each of these has a different pixel int...