Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
AT9-91-037
Description 2~8~
METHOD AND APP~RATUS FOR PROCESSING
CONCURRENT PICK EVEN~S
Technical Fiald
The present invention relates generally to graphics
data processing pick events and more specifically to
processing concurrent pick events.
\
Backqround Art
Graphics applications often display images derived from
multiple objects described in memory. These graphics
applications generally allow the user to select or pick a
displayed object for various purposes such as to erase the
object, change the color of the object, etc. Each attempt
of the user to pick an object or objects is called a pick
event. Each pick event is processed by the graphics
application before the user can attempt another pick event.
However, if the user is using multiple graphics applications
on a host computer with multiple graphics adapters, the user
may perform separate pick events on each adapter, with each
adapter handling only one pick event at a time. The
graphics adapters may have separate or shared graphics
displays.
Various apparatus and methods for performing picks are
described are describad below.
U.S. Patent No. 4,958,147 is directed to a graphics
display processing system which utilizes a graphic data
buffer to allo~ the user to perform a pattern pick within a
pick aperture.
U.S. Patent No. 4,941,111 is directed to a video
picking and clipping system which includes a list of
displayed objects stored in main memory which is used to
determine whether an object has been picked.
U.S. Patent No. 4,885,704 is directed to an image
processing system for scanning a document, displaying the
scanned document and a file device for filing the scanned
document.
AT9-91-037 2
U.S. Patent No. 4,847,605 is directed to a graphics
system which temporarily separates the cursor tracking and
the picking functions at the time the user attemp-ts to pick.
U.S. Patent No. 4,698,625 is directed to a system which
highlights a selected graphics object to indica-te that the
object has been selected.
U.S. Patent No. 4,189,744 is directed to a system for
allowing a user to select desired portions of an existing
scene and automatically obtain stored contour outlines of
those portions.
Disclosure of the Invention
The present invention includes an apparatus for
processing objects to be displayed including a display for
displaying objects, means, coupled to the display means, for
processing pick events pertaining to the displayed objects,
means, coupled to the processing means, for requesting the
processing means to process a first pick event, and means,
coupled to the processing means, for requesting, after
processing of the first pick event has been reguested and
prior to completion of the processing of the first pick
event, the processing means to process a second pick event.
The present invention also includes a method of
processing objects to be displayed including the steps of
displaying objects, processing pick events pertaining to the
displayed objects on a common processing means, requesting
the processing means to process a first pick event, and
requesting, after processing of the first pick event has
been requested and prior to completion of the processing of
the first pick event, -the processing means to process a
second pick event.
A further understanding of the nature and advantages of
the present invention may be realized by re~erence to the
remaining portions of the specification and the drawing.
Brief Description of the D awi~
Fig. 1 is a block diagram of a typical digital
computer;
Fig. 2 is a block diagram illustrating -the layers of
code typically utilized by -the host computer and graphics
adapter to perform graphics functions;
AT9-91-037 3
9 6
Fig. 3 is a 1Owchar~ of how a typical three
dimensional graphics system executes a pick event;
Fig. 4, 5 and 6 are flowcharts illustrating
modifications to the flowchart given in Fig. 3 to utilize a
preferred embodiment of the invention; and
Fig. 7 is a block diagram illustrating a pick event
buffer entry utilized by the device driver.
_st Mode for Carrying out the Invention
Fig. 1 is a block diagram of a typical diyital computer
100. The computer includes main processor(s) 110 coupled to
a memory 120, input device(s) 130 and output device(s) 140.
Main processor(s) 110 may include a single processor or
multiple processors. Input device(s) 130 may include a
keyboard, mouse, tablet or other types of input devices.
Output device(s) 140 may include a text monitor, plotter or
other types of output devices. The main processor may also
be coupled to graphics output device(s) 150 such as a
graphics display through a graphics adapter 200. Graphics
adapter 200 receives instructions regarding graphics from
main processor 110 on bus 160. The graphics adapter then
executes -those instructions with graphics adapter
processor(s) 220 coupled to a graphics adapter memory 230.
The graphics processors in the graphics adapter then execute
those instructions and updates frame buffer(s) 240 based on
those instructions. Frame buffer(s) 240 includes data for
every pixel to be displayed on the graphics output device.
A RAMDAC (random access memory digital-to-analog converter)
250 converts the digital data stored in the frame buffers
into RGB signals to be provided to the graphics display 150
thereby rendering the desired graphics output from the main
processor.
Fig. 2 is a block diagram illustrating the layers of
code typically utilized by the host computer and graphics
adapter to perform graphics functions. An operating system
300 such as UNIX provides the primary control of the host
computer. Coupled to the operating system is an operating
system kernel 310 which provides the hardware intensive
tasks for the operating system. The operating system kernel
communicates directly with the host computer microcode 320.
The host computer microcode is the primary instruction set
AT~-91-037 4
2~
executed by the host computer processor. Coupled to the
operating system 300 are graphics applications 330 and 332.
This graphics application software can include software
packages such as Silicon Graphic s GL'M, IBM graPHIGS~, MIT~s
PEXIM, etc. This software provides the primary functions of
two dimensional or three dimensional graphics. Graphics
applications 330 and 332 are coupled to graphics application
API (application program interface) 340 and 342,
respectively. The API provides many of the computationally
intensive tasks for the graphics application and provides an
interace between the application software and software
closer to the graphics hardware such as a device driver for
the graphics adapter. For example, API 340 and 342 may
communicate with a GAI (graphics application interface) 350
and 352, respectively. The GAI provides an interface
between the application API and a graphics adapter device
driver 370. In some graphics systems, the API also performs
the function of the GAI.
The graphics application, API, and GAI are considered
by the operating system and the device driver to be a single
process. That is, graphics applications 330 and 332, API
340 and 3~2, and GAI 350 and 352 are considered by operating
system 300 and device driver 370 to be processes 360 and
362, respectively. The processes are identified by the
operating system and the device driver by a process
identifier (PID) that is assigned to the process by the
operating system kernel. Processes 360 and 362 may use the
same code that is being executed twice simultaneously, such
as two executions of a program in two separate windows. The
PID is used to distinguish the separate executions of the
same code.
The device driver is a graphics kernel which is an
extension of the operating system kernel 310. The graphics
kernel communicates directly with microcode of the graphics
adapter 380. In many graphics systems, the GAI, or the API
if no GAI layer is used, may request direct access from the
GAI or API to the adapter microcode by sending an initial
request instruction to the device driv~r. In addition, many
graphics systems also allow the adapter microcode to request
direct access from the adapter microcode to the GAI or API
if no GAI is used by sending an initial request instruction
AT9-91-037 5 ~8~ ~
to the device driver. Both processes will hereinaf-ter be
referred to as direct memory access (DMA). DMA is typically
used when transferring large blocks of data. DMA provides
for a quicker transmission of da-ta between the host computer
and the adapter by eliminating the need to go through the
display driver other than the initial re~uest for the device
driver to set up the DMA. In some cases, the adapter
microcode utilizes context switching which allows the
adapter microcode to replace the current attributes being
utilized by the adapter microcode. Context switching is
used when the adapter microcode is to receive an instruction
from a graphics application that utilizes different
attributes than the adapted microcode is currently using.
The context switch is typically initiated by the device
driver which recognizes the attribute changes.
Blocks 300-3~0 are software code layers that are
typically independent of the type of graphics adapter being
utilized. Blocks 350-380 are software code layers that are
typically dependent upon the type of graphics adapter being
utilized. For example, if a different graphics adapter were
to be used by the graphics application software, then a new
GAI, graphics kernel and adapter microcode would be needed.
In addition, blocks 300-370 reside on and are executed by
the host computer. However, the adapter microcode 380
resides on and is executed by the graphics adapter.
However, in some cases, the adapter microcode is loaded into
the graphics adapter by the host computer during
initialization of the graphics adapter.
In typical graphics systems, the user instructs the
graphics application to construct an image from a two or
three dimensional model. The user first selects the
location and type of lights. The user then instructs the
application software to build the desired model from a set
of predefined or user defined objects. Each object may
include one or more drawing primitives describing the
object. For example, a set of drawing primitives such as
many triangles may be used to define the surface of an
object. The user then provides a perspective in a window to
view the model, thereby defining the desired image. The
application software then starts the rendering of the image
from the model by sending the drawing primitives describing
AT9-91-037 6 '~ ~ 6~ ~6
the objects to the adapter microcode through the ~PI, the
GAI, and then the device driver unless DMA is used. The
adapter microcode then renders -the image on the graphics
display by clipping (i.e. not using) those drawing
primitives not visible in the window. The adapter microcode
then breaks each remaining drawing primitive into visible
pixels from the perspective given by the user. The pixels
are then loaded into the frame buffer, often with the use o
a depth buffer in the case of a three dimensional model.
This step is very computationally intensive due to the
number of drawing primitives, variables, and pixels
involved. As a result, the resulting image stored in the
frame buffer and displayed on the graphics display typically
does not carry the original information such as which
drawing primitive or object the pixel was derived from. As
a result, the image may need to be rerendered in part or in
whole if the window, the user perspective, the model, the
lighting, etc. are modified. This also presents a
difficulty when trying to pick a displayed object in the
window. In a typical three dimensional model, when a user
is picking an object displayed in a window, a complicated
and sometimes time consuming process is followed.
Fig. 3 is a flowchart of how a typical three
dimensional graphics system executes a pick event. The
steps in blocks 400, 410, 420, 430 and 440 are performed by
the graphics application, application API, GAI, device
driver and adapter microcode, respectively. In a first step
500, the graphics application software receives a pick
request from the user such as the clicking of a mouse. The
graphics application software then allocates a pick data
buffer, for receiving the name or other identifier of the
drawing primitives that are picked, and a pick data buffer
length. The application software then calls a pick
subroutine referencing the pick data buffer and the pick
data buffer length (e.g. Pick [Buffer, Bufferlenl). In step
505, the graphics application API allocates a pick data
structure for passing data to and from the adapter
microcode. The pick data structure includes the pick data
bufer and the pick data buffer length. In addition, the
pick data structure includes a pick report for identifying
that the pick data structure is being used for a pick event.
AT9-91-037 7
8(~.6
Furthermore, the pick data structure includes the X and Y
coordinates of the cursor and some application specific
variables such as a device number describing the type of
graphics adapter being used and a pick device number
describing whether a mouse or other type of I/o device is
being used. The graphics application API then passes a pick
mode instruction to the GAI with pointers to the allocated
pick data structure. In step 510 the GAI responds to the
pick mode instruction from the API by issuing a pick mode
command to the device driver. The pick command includes the
pick data structure pointers including pointers to the pick
report and the pick buffer. The device driver also receives
the process identiier (PID) of the process (graphics
application, API and GAI) issuing the pick mode command. In
step 515, the device driver sets up a DMA for moving data
between the graphics adapter and the host computer in
response to the pick command. The device driver then issues
a pick mode command including the pick data structure
pointers to the graphics adapter microcode. In step 520,
the microcode stores the pointers to the pick data structure
in the adapter memory and then enters into a pick mode. In
the pick mode, the adapter will not display received
primitives. The adapter will determine whe-ther received
primitives are picked. In addition, in the pick mode the
adapter will not accept any other commands, other than
commands relating to the pick event, from the device driver
until the pick event is completed. As a result, the
application software or other application software coupled
to the graphics adapter will be unable to utilize the
graphics adapter until the pick event is completed.
Shortly after the graphics application calls the pick
subroutine, the graphics application starts generating
primitives relating to the image being picked in step 525.
In step 530, the graphics application API sends these
drawing primitives plus names or other identifiers
identifying the drawing primitives to the GAI. In step 535,
the GAI sends these drawing primitives and their names to
the graphics adapter microcode by D~A. In step 540, the
graphics adapter microcode receives the primitives via DMA
and begins the process of deciding whether any of the
primitives are picked (i.e. the rendered primitive includes
AT9-91-037 8
a pixel located at the X and Y coordinates of`~he cursor
which are provided in the pick data structure).
In step 545, after the first primitive has been
determined to be picked, the microcode begins the DMA (from
the adapter microcode to the GAI) to transfer the name of
the first picked primitive back to the graphics application
in the pick buffer. The microcode then generates a pick
complete interrupt signal to the device driver to signal
that the first primitive, that has been determined by the
adapter microcode to be picked, has been sent to the GAI via
DMA. In step 550, the device driver receives the pick
complete interrupt signal then informs the GAI that the
irst picked primitive has been sent to the G~I via DMA. In
the prior art, some adapters utilize a status register in
the adapter, that can be read by the device driver, that
would include a code inserted in the status register by the
adapter microcode designating what type of interrupt signal
(pick interrupt, error interrupt, etc.) was sent to the
device driver by the adapter. In step 555, the GAI informs
the API that the first picked primitive is in the pick
buffer. In step 560, the graphics adapter API informs the
graphics application that the first picked primitive is in
the pick data buffer.
At this point, the graphics application may continue
sending drawing primitives to the microcode or it may stop
sending drawing primitives to the microcode. This is
dependent upon whether the pick event for this particular
graphics application is a pick first, pick last, pick all,
pick visible, etc. If it is a pick first, then no more
drawing primitives need to be picked. Therefore, the
graphics application would stop sending drawing primitives
to the adapter microcode. If this is a pick last, visible,
or all, then the graphics application would continue sending
drawing primitives to the adapter microcode until all the
drawing primitives have been sent to the adapter microcode.
In step 562, upon completion of sending the drawing
primitives in either case, the graphics application
instructs the API~ in step 564, to issue a re~uest to end
pick mode to the GAI. In step 566, the GAI issues a end
pick mode instruction to the device driver. In step 570,
AT9-91-037 9 ~ ~ ~8~ ~
the device driver sends an end pick mode instruction to the
adapter microcode.
In step 575, the graphics adapter microcode finishes
the DMA of picked drawing primitives. If no primitives have
been picked or after the DMA of picked primitive name(s) is
complete, the graphics adapter then exits the pick mode,
thereby allowing the adapter to accept new commands not
relating to the pick event, and sends a pick complete
interrupt signal to the device driver. In step 580, the
device driver informs the GAI that the pick has been
completed by the adapter microcode. In step 585, the GAI
informs the graphics application API that the pick event is
completed and that the names or identifiers of the picked
primitives is in the pick buffer. In step 590, the graphics
application API informs the graphics application that the
picked primitives are in the data buffer. In step 595, the
graphics application has the allocated pick data buffer full
of the primitives that meet the pick requirements of this
application and the graphics application can utilize that
information according to its requirements.
One of the difficulties with the above described
process is that when the user initiates a pick event for a
given graphics adapter, the user may not initiate another
event such as a pick event in the same or another window or
process until the pick event has been completed. This is
particularly true when the model is complicated enough to
cause the user to wait a substantial amount of time for the
pick event to be completed after the user initiates the pick
event. It is desirable for a user to initiate a pick event
and then be able to continue work on another task such as a
pick event in another window prior to the completion of the
first pick event.
Fig. 4 is a flowchart illustrating modifications to the
flowchart given in Fig. 3 to utilize a preferred embodiment
of the invention. Blocks 600 and 650 correspond to blocks
515 and 520 of Fig. 3. Block 600 includes four steps
performed by the device driver. In a first step 610, the
device driver sets up a DMA for moving data between the
graphics adapter and the host computer in response to the
pick command. In step 620, the device driver then obtains a
pick event identifier, referred herein as a correlator code
AT9-91-037 10
8~3~ 6
or correlator. In a preferred embodiment, the host computer
memory includes a register or memory location for a
correlator code. Each time the correlator code is used for
another pick event, the correlator code is incremented by
one in preparation for the next pick event. In an
alternative embodiment, the process identifier may be used
as the pick event identifier if each graphics application
can send only one pick event at a time. The device driver
then stores the correlator code in a pick event buffer in
the host computer main memory in conjunction with the
process identifier (PID) and pick data structure pointers.
In step 6~0, the device driver then issues a pick mode
command including the pick data structure pointers and
correlator code to the graphics adapter microcode.
In step 650, the adapter microcode performs three
steps. In steps 660 and 670, the adapter microcode stores
the pointers to the pick data structure and the
corresponding correlator code in adapter memory. In step
680, the adapter microcode enters into a pick mode. In the
pick mode, the adapter will not display received primitives
corresponding to the correlator code. The adapter will
determine whether these received primitives are picked.
Unlike the prior art pick mode, the adapter will st.ill
accept other commands other than commands relating to the
pick event from the device driver, and may render primitives
sent from other application software. The adapter microcode
is capable of handling other commands including other pick
events because the device driver and the adapter microcode
have a correlator or pick event identifier with the pick
data structure pointers identifying which pick event the
pick data structure refers to. For adapters that utilize
context switching, the device driver will use the process
identifier and the correlator in signalling the adapter
microcode that the context needs to be changed for use by
the adapter microcode.
Fig. 5 is a flowchart illustrating modifications to the
flowchart given in Fig. 3 to utilize a preferred embodiment
of the invention. Blocks 700 and 760 correspond to blocks
535 and 540 of Fig. 3. The GAI performs two steps in step
700. In step 710, the GAI sends the drawing primitives and
their names to the graphics adapter microcode by DMA. In
AT9-91-037 11 ~C ~
step 720, the GAI informs the device driver that it has sen-t
the primitives to the adapter mi.crocode. In s-tep 730, the
device driver first determines whe-ther the GAI is different
from the previous GAI from the process identifier for the
GAI in step 740. If yes, the device driver informs the
adapter of the change in pick events in s-tep 750. If no,
then the device driver allows the adapter microcode to
continue processing in the current state. The adapter
microcode performs up to three s-teps iII step 760. If the
device driver informed the adapter of the change in pick
events, the adapter microcode will modify what poin-ters to
the data, including the pick data structure, that the
adapter microcode utilizes in step 770. For adapters that
utilize context switching, the device driver will use the
process identifier and the correlator in signalling the
adapter microcode that the context needs to be changed for
use by the adapter microcode. In step 780, the adapter
microcode then reads the primitives and primitive names from
the GAI via DMA. In step 790, the adapter microcode then
determines which of the primitives have been picked.
Fig. 6 is a flowchart il].ustrating modifications to the
flowchart given in Fig. 3 to utilize a preferred embodiment
of the invention. Blocks 800 and 850 correspond to blocks
5~5 and 550 or blocks 575 and 580 of Fig. 3. The adapter
microcode performs three steps in step 800. In step 810,
the adapter microcode begins the DMA ~from the adapter
microcode to the GAI) to transfer the name of the picked
primitive(s) back to the graphics application in the pick
buffer. The picked primi-tive names are sent to the
appropriate GAI because the same data structure pointers are
used by both the GAI and the adapter microcode for the pick
event. In step 820, the adapter microcode then puts the
correlator code, corresponding to the primitive names passed
by DMA, in a status register in adapter memory that is
accessible by the device driver. In step 830, the adapter
microcode then issues a pick complete interrupt signal to
the device driver to signal that the primitives have been
determined by the adapter microcode to be picked and that
the names of the picked primitives have been sent to the GAI
via DMA.
AT9-91-037 12
~@68~
In step 850, the device driver performs three steps.
In a first step 860, the device driver receives the pick
complete interrupt signal. In step 870, the device driver
reads the status register in the adapter memory to obtain
the correlator code. Based on the correlator code, the
device driver reads the pick event buffer in main memory to
obtain the process identifier (PID) corresponding to the
correlator code in step 880. Based on the PID, the device
driver in step 890 informs the appropriate GAI that the
picked primitive(s) has been sent to the GAI via DMA.
Fig. 7 is a block diagram illustrating a pick event
buffer entry stored by the device driver in the host
computer main memory. The entry in the pick event buffer
900 includes the process identifier (PID) 910 of the process
that initiated the pick event. Also included are the pick
data structure pointers 920 for the pick data structure
allocated by the process. Also included is the correlator
930 corresponding to the pick event.
As a result of the use of the pick event identifier or
correlator code, the device driver and the adapter microcode
are able to handle multiple concurrent pick events. That
is, the correlator provides a means of identifying each pick
event, thereby allowing the graphics system to identify
which pick event corresponds to certain data, instructions,
or other pick event specific information. For example, as
the primitives for a first pick event are being sent to the
adapter microcode from a first graphics application, a
second graphics application may request a pick event be
initiated and then start sending primitives relating to the
second pick event prior to the completion of the first pick
event.
Although the present invention has been fully described
above with reference to specific embodiments, other
alternate embodiments may be apparent to those of ordinary
skill in the art. For example, the same graphics
application may perform two concurrent picks by using the
operating system to generate the correlator code and using
the correlator code as a pick event identifier in the pick
data structure that is passed to the device driver and the
adapter microcode. In addition, the pick event identifier
may be used in other types of pick event methodologies than
AT9-91-037 13
6~
that described above. Therefore, the above description
should not be taken as limi-ting the scope of the present
invention which is defined by the appended claims.
