'\"!  tbl | mmdoc
.if n .pH arch.memraster @(#)memraster	40.2
.\" turn off automatic hyphenation -- JHevelin (08-09-89)
.am RT
.nh
..
.ds S) Shapes
.BK "Shapes Internal Architecture"
.CH "Memory Raster Implementation" "2" 
.SO BP.HEADER
.H 1 "Memory Raster Implementation"
.H 2 "Introduction"
This chapter describes the \*(S) memory raster
implementation and its specific orientation for
dumb framebuffers.
It discusses the interaction between objects,
path construction, and rendering;
detailed descriptions of the objects and
a discussion of rendering occur in subsequent
chapters in this manual.
.P
Primarily, \*(S) renders paths according to the
attributes within the \*(S) objects.
These attributes determine how the path is transformed,
clipped, and converted to pixels on the screen.
Figure 2-1
shows how the context relates to other \*(S)
objects when constructing or rendering the
current path.
.P
.FG "Relationship of \*(S) Objects" FG_Rel_Obj
.DS
.BP PSART/ps.ctx_objs 3.5i 0 "" 0.6 0.6 0
.DE
.H 2 "The Path"
.P
In the \*(S) viewing model,
graphic primitives are directed towards a graphic
context object where they are transformed by a
viewing pipeline and accumulated in the current
path associated with the context.
The coordinates of a primitive may be transformed
by one of several transform objects
(model, view, VDC) either before they are
appended to the path or at the time the path is
rendered.
.P
The CTX_PIPELINE attribute selects the graphics
pipeline configuration
(which transforms are applied and when,
whether clipping is enabled, etc.).
If you enable the CTX_APPLY_RENDER option in CTX_PIPELINE,
a transform object is applied to the points in
the path as they are rendered.
Application of the path render transform does not
change the contents of a path.
However, if you instead enable the
CTX_APPLY_CONSTRUCT option,
a transform object is applied to the points in
the path as the path is constructed,
permanently altering the geometry.
Note that the graphics pipeline may be applied at
construction time
.UI or
at rendering time, but not both.
.H 2 "Clip Paths"
.P
As primitives are rendered,
they are clipped first to the context clip path
and then to the raster clip path.
These clip paths designate the outline of two areas;
pixels falling outside the region common to
both clip areas are not rendered.
In other words, drawing only occurs in
the region described by the intersection of the
context and raster clip paths.
.P
\*(S) maintains a description of a path's area in
an internal object known as a shape.
The shape object represents an area as a sorted
list of non-overlapping rectangles.
Shape objects support intersection,
union, and difference operations.
.BL
.LI
The context clip path (CTX_CLIP_PATH) describes
an area within the context to which all
primitives are clipped.
It is expressed in raster coordinates.
Whenever the context clip path is changed,
the context clip shape is derived to represent
the area enclosed by the path.
.LI
Each context is associated with a raster defining
the physical drawing area on the screen or in memory.
The raster performs the actual path rendering,
using the context attributes.
The raster clip path (RAS_CLIP_PATH) designates
the drawable area of the raster and is expressed
in physical device coordinates.
As with the context clip path,
when the raster clip path is changed,
a raster clip shape is created representing the area
enclosed by the raster clip path.
.LI
Each raster maintains a shape object representing
the intersection of the raster and context clip paths.
Whenever anything is rendered to a context
(text, path or raster),
\*(S) inquires whether this shape is still valid.
There is no new computation unless the raster or
context clip paths have changed,
thus preventing a costly shape intersection
operation each time a path is rendered.
.\" begin new page
.LE
.H 2 "Pipelines"
.P
The flow of data from the application, into a path,
and onto the screen is a \f2graphic pipeline\fP.
The pipeline creation occurs in three steps:
.BL
.LI
Path construction transforms the coordinates and
appends them to the current path.
(Path construction and path rendering are
separate operations.)
.LI
Path rendering translates the path into
individual drawing primitives based on the
current context and raster attributes.
Coordinate transformations, viewing,
and view volume clipping
are included in this step.
The exact path rendering pipeline is selected
based on the context attributes
and the characteristics of the path rendering
transform.
.LI
Individual rendering routines draw low-level primitives
(vectors, polygons, etc.).
This set of raster drawing operators is chosen by
raster and context attributes
when the raster is asked to render the path.
.LE
.P
Path construction appends an opcode and,
optionally, some coordinates,
to a pre-allocated data area.
If the new information doesn't fit,
the path data area is extended or re-allocated.
.P
In order to optimize path construction performance,
\*(S) keeps two sets of path pointers \(em
an up-to-date set in the context,
and a possibly out-of-date set in the path.
When a path becomes the current path of a context,
its path pointers are copied into corresponding
pointers in the context.
If the user switches paths,
the context pointers are copied back to the old
path and updated from the new path.
The process is complicated because some
path operators access the path directly and the
path pointers may be out of date.
To accommodate this,
\*(S) checks to see if the path is associated
with a context and updates the path pointers from
the context pointers if necessary.
.P
To increase performance,
\*(S) defers coordinate transformation as long
as possible and only applies the path construct
transform to the current path if one of the
following conditions is met:
.BL
.LI
the path construct transform is changed
.LI
the path is disassociated from the context
.LI
the path is rendered
.LI
CTX_PIPELINE is changed
.LE
.P
Such deference allows transformation of groups of
points rather than a single coordinate at a time.
If you have a hardware accelerator that can do
high-speed transformations,
you may want to improve performance.
It may not be worth the communication overhead to
use the accelerator for a single point;
however, it may make sense for a list of points.
.P
Figure 2-2
gives a more detailed picture of the path construction process.
.\" begin new page
.P
.FG "Path Construction Architecture" FG_Path_Cons_Arch
.DS
.BP PSART/ps.pth_cns1 3.5i 0 "" 0.75 0.75 0
.DE
.H 2 "Path Rendering"
.P
Paths are rendered in steps:
.AL
.LI
Establish the raster/context clip shape.
.P
The raster/context clip shape is the intersection
of the areas defined by the raster and context
clip paths.
Often, a context will render many paths using the
same raster;
therefore, it is optimal to have the raster
maintain some state information about the last
context it was used with,
such as raster clip shape and context clip shape.
Before a path is rendered,
the clip shape is checked for validity.
The intersection is invalid if any of the
following conditions occur:
.BL
.LI
the raster is associated with a different context
.LI
the context clip path changes
.LI
the raster position and/or size changes
.LI
the raster clip path changes.
.P
If the intersection is invalid,
it is recomputed.
.LE
.LI
Construct the transform to map path coordinates
to screen space.
More than one transformation may be selected in
the viewing pipeline
(any one of model, view, VDC).
Concatenation of viewing pipeline transformations
is deferred until the result of the concatenation
\(em the pipeline transform \(em is needed.
If transformations are being applied at path
construction time,
this concatenation is done before a group of path
coordinates are transformed.
If transformation is being done at render time,
the pipeline transforms are concatenated before
the path is rendered.
A flag bit is kept in the graphics context to
indicate whether concatenation is necessary
(i.e., if the pipeline or any of its associated
transformations have been changed).
.LI
Select the appropriate pipeline to convert path
elements into individual raster drawing primitives.
The path rendering pipeline can be of several
different forms depending on the context
attributes and the path to screen space transform.
.BL
.LI
Vector pipelines transform, clip,
and render single-width vectors, solid color vectors,
and curve segments.
The version of this pipeline depends on the
characteristics of the path-to-screen-space transform.
If the transform contains only translation factors,
a pipeline that adds the appropriate offsets is selected.
Otherwise the pipeline does a full matrix multiplication
and calls the raster drawing primitives to draw
individual vectors and curve segments.
There are also separate pipelines that optimize
fract and float coordinates.
.LI
Area pipelines transform, clip, and render filled areas
(polygons or curve-bounded regions).
The path coordinates are transformed,
clipped, and converted to a polygon edge list
containing both curved and linear edges.
A single path may represent several distinct areas.
When all of the edges for a region have been accumulated,
a raster primitive is invoked to draw the area
based on the edge table.
.LI
The outline pipeline handles vectors which are
either wide, dashed, or both.
It inputs a source path containing the original
line endpoints and outputs a path describing
these lines in wide dashed form.
For thin, dashed vectors,
the output path contains vectors,
one for each dash.
For wide vectors (dashed or not),
the output path contains polygons.
Unless round endcaps and joins are selected,
the output path for wide lines is usually
composed of quadrilaterals and triangles.
The output path is then rendered using the
appropriate vector or area pipeline.
.LE
.LE
.P
Although the particular pipeline formats
described above are peculiar to the \*(S) memory raster,
the technique of having multiple pipelines is
applicable to other \*(S) implementations as well.
Device specific trade-offs depend on hardware capabilities.
For example, because \*(S) implements transforms in software,
transforming a point is a high-cost operation.
You can optimize performance by selecting
different pipelines based on whether the
transform is limited to only one type.
For a high-performance accelerator with hardware
transform assist,
this particular optimization would not be necessary.
If, however, the hardware was optimized to render triangles,
then a special pipeline for this case would improve performance.
.\" begin new page
.P
.FG "Path Rendering Architecture" FG_Path_Rend_Arch
.DS
.BP PSART/ps.pth_rnd1 3.75i 0 "" 0.75 0.75 0
.DE
.H 2 "Other Rendering"
.P
In addition to rendering paths,
\*(S) can render rasters and glyphs in a variety of ways.
.BL
.LI
Raster Copy operations are performed by Display_Raster,
Store_Raster, Read_Raster, and Write_Raster.
Like path rendering,
raster copying has its own special set of drawing
routines that are selected based on context
attributes.
.LI
The Poly_Glyph operator also has its own set of
drawing routines.
These are similar to the raster copy routines,
but optimized for usage with glyphs.
.LI
The Image_Raster and Point_Raster operations do
not have their own set of drawing routines.
They are stand-alone.
.LE
.H 2 "Raster Drawing Primitives"
.P
The raster object has a set of internal drawing
primitives that are invoked by the rendering pipelines.
Each type of pipeline has its own set of drawing primitives.
The table below shows which drawing primitives
are used by which \*(S) functions.
.TB "Raster Drawing Primitives for Shapes Functions"
.TS
box;
l | l | l.
Display_Path	Display_Raster	Poly_Glyph
Display_Context	Store_Raster
	Read_Raster
	Write_Raster
_
render vector 	copy raster	draw glyph
render curve
render edge table
fill region
.TE
.TT
.P
The complexity of the raster/context clip shape
is a primary criteria in drawing set selection.
If this shape is simple, such as a rectangle,
it is optimal to clip simple primitives
(like vectors and curves) analytically.
For complex clip shapes,
we construct a shape that represents the area
enclosed by the primitive and use the shape
intersection operator to derive the visible part
to render.
This requires a raster drawing set that outputs
a shape object rather than rendering directly on
the screen.
.P
Context and raster attributes also influence the
selection of the raster drawing set.
Attributes like raster-op, bit planes, raster depth, etc.,
select different groups of primitives specialized
to render for that set of conditions.
.P
For example, Poly_Glyph may have several different versions of the
\f2draw glyph\f1
primitive,
one for solid filled characters clipped to a rectangle,
another for stippled characters, etc.
The exact one used to render a list of glyphs is
selected based on these attributes.
In the case of the path rendering,
more than one primitive may be selected.
The vector pipeline needs
\f2render vector, render curve"\f1
and
\f2fill region\f1,
while the area pipeline needs
\f2render edge table\f1
and
\f2fill region\f1.
Selection of the drawing primitives is done once
before a path is rendered and remains in effect
until all the path elements have been rendered.
.H 2 "Inheritance and Device Independence"
.P
One of the most powerful features of the \*(S)
architecture is the ability to inherit from an
existing implementation at several different levels.
This allows a port of \*(S) to a new device to
get the maximum leverage out of existing code for
a similar device.
Inheritance can be of several flavors:
.BL
.LI
You can inherit the implementation of an entire class.
All \*(S) ports done to date share the same code
for the path object.
.LI
You can inherit the implementation of some of the
operators of a class,
using your own functions for the others.
Most \*(S) ports share many of the context,
raster, and transform operators.
In the case of rasters,
many of the rendering routines,
like Display_Raster,
are replaced with device-specific versions.
Ports to accelerators that have transformation
hardware will frequently override Mul_Transform,
Path_Transform, and Pipeline_Context.
.\" begin new page
.LI
You can inherit the implementation of individual
rendering functions.
Ports to framebuffers with some hardware assist
typically inherit from the memory framebuffer
implementation of the corresponding depth.
Functions that can be optimized
(say, copying a screen rectangle)
can use device-dependent versions of specific
rendering functions.
.LE
.P
.H 2 "Class Types and Devices"
.P
Each device known to \*(S) has the potential to
implement all of the built-in classes
independently of any other device.
(In practice, this is not done.
A great deal of code is actually shared between ports.)
.P
\*(S) keeps a table of class types that defines
the characteristics of each class for each device.
The table determines how big objects of the class are,
which classes they inherit from,
what the functions are that implement the class
operators, etc.
There is a one to one correspondence between
class types and devices.
.P
When a new device is defined,
it designates an existing device from which it will
inherit class implementations.
It also provides a template that indicates which
classes it wants to inherit and which classes it
would like to change.
The template also indicates the specific
functions of each class that are to be replaced
by device-specific versions.
Creating a new device creates a new class type
that defines the implementation of the \*(S)
classes for that device.
.P
An individual object has both a class ID
(the class it belongs to)
and a class type
(the device where it derives its implementation from).
When most objects are created,
they have a generic class type and therefore
derive their implementation from generic code not
associated with any device.
.P
Figure 2-4
illustrates inheritance between the generic
8-bit memory and cg2 ports.
The highlighted functions and classes are those
that are
\f2not\f1
inherited from the parent device.
Notice that the 8-bit memory CMAP object is
different than the generic one.
This is because color maps behavior differently
for different raster depths.
The 8-bit memory implementation of the CMAP class
replaces the Init_Cmap, Install_Cmap,
and Set_Cmap operators.
The cg2 version of the CMAP class also replaces
these functions with cg2-specific versions.
Some of the raster operations are also replaced \(em
Path_Raster, Clear_Raster, and Display_Raster.
The context, transform, path, and other objects
can be shared by the cg2 and 8-bit memory port.
.\" begin new page
.FG "Class Types" FG_Class_Type
.DS
.BP PSART/ps.cls_typ 3.5i 0 "" 0.6 0.6 0
.DE
Some objects, like rasters, screens, contexts and cmaps,
can be bound to another object.
For example, when a raster object is created,
it is explicitly associated with a particular
display device or a memory
implementation of a particular depth.
The new raster object is assigned a class type
based on that.
When a context is created,
it is associated with a specific raster.
Its class type is the same as the class type of
the raster it is currently attached to.
Similarly, context transforms derive their class
types from the context they belong to.
.P
The class type of an object may be switched
dynamically depending on what other objects it is
associated with.
This has the effect of changing the
implementation of that object.
This happens when a context is associated with a
different raster.
The class type of the context and all of its
transforms is changed to be consistent with the
new raster.
This is how \*(S) efficiently supports rendering
the same image to both a memory raster and an
accelerator.
.H 2 "Rendering to a Device"
.P
The raster defines the implementation of all
rendering operators.
Rendering operators belong to other objects,
like Poly_Glyph, Display_Context, and Display_Path,
are really macros which call internal raster operators
(Glyph_Raster and Path_Raster, to be exact).
This keeps the device dependencies all in one
place and with an object that is,
by nature, device-dependent.
.P
All rasters are associated with a screen object.
There is one screen object for each device;
the screen defines the characteristics of that device.
It also designates the set of rendering
routines used for rendering to that device.
The routines are organized in dispatch tables,
allowing individual cases to be isolated
.\" begin new page
and optimized.
These tables define the implementation of path
transformation pipelines and low-level primitive
rendering.
.P
If your device is similar to an existing one,
you can use the same table layout and most of the
same functions,
replacing the ones you wish to optimize or modify.
For example, the \*(S) port for 8-bit memory
framebuffers handles plane enables in software.
The dispatch tables allow you to have different
rendering functions for the case when all bit
planes are enabled and some are masked.
The ``all planes enabled'' case is optimized for
some primitives.
If you are porting to an 8-bit framebuffer that
has a hardware plane-enable mask,
you could use the dispatch tables from the 8-bit
memory port but remove the distinction for
plane-enable.
Then you could provide versions of the raster
rendering routines that set the plane enable
mask from the context attribute before
dispatching to lower level primitives.
.P
Figure 2-5
shows the organization of some of the dispatch
tables for the 8-bit memory port.
The area pipeline dispatch table
(mem8_fill_fun) has different rendering functions
for rectangular clip areas vs. complex clip shapes.
Notice that the vector pipeline dispatch table
(mem8_stroke_fun) is also organized this way even
though rectangular and complex clips use the same
functions.
Both pipelines share the same shape rendering functions
(mem8_fill_shape).
These functions are dispatched off the fill style,
having different functions for solid,
textured, stippled, and opaque stippled fills.
.FG "Memory Framebuffer Dispatch Tables" FG_Mem_Disp
.DS
.BP PSART/ps.disp_tab 3.75i 0 "" 0.6 0.6 0
.DE
