'\"!  tbl | mmdoc
.if n .pH arch.path @(#)path	40.2
.ig
imaged dc 8/30/89
docformat -c -s4 -dqm4 fn
..
.\" turn off automatic hyphenation -- JHevelin (08-09-89)
.am RT
.nh
..
.ds S) Shapes
.SO BP.HEADER
.BK "Shapes Internal Architecture"
.CH "The PATH Object" "7"
.H 1 "The PATH Object" 
.H 2 "Introduction"
.nh
The path object contains geometry and color
information in a form to facilitate fast rendering.
Paths may be transformed, rendered,
or used to define clip areas.
Path rendering and construction is done via
context operators that reference the current
path of the context.
All other path operations manipulate a path
object directly.
A path constructed by one context can be rendered
via another,
allowing local paths to be maintained on the host
CPU in a common data format.
.P
All of the \*(S) implementations to date share
the same generic code for all path operators,
making the implementation of the path object
device independent.
The Display_Path operator is implemented as a
macro that calls the device-dependent Path_Raster operator,
allowing path rendering to be completely device-dependent.
.H 2 "Path Attributes"
The external path attributes are documented in the
.UI "Shapes Reference Manual."
This section discusses the internal attributes
that are used in the implementation of the path
object.
All path attributes are defined in
include/sh_PATH.ah;
their values are defined in include/sh_PATH.h.
.PC
POINT_B2D PATH_ORG;
POINT_B2D PATH_DIM;
PATH_type PATH_TYPE;
Unsgn8    path_rendered;
Unsgn8    path_flags;
OBJID     path_data;
Unsgn32   path_cur;
Unsgn32   path_end;
CONTEXT   path_ctx;
SHAPE     path_shape;
PATH      path_parent;
PATH      path_child;
Unsgn32   path_penofs;
Unsgn32   path_mark;
Unsgn32   path_analysis;
.SF
.H 2 path_ctx
.P
If this path is the current path of a context,
path_ctx points to that context and CTX_PATH
references this path.
If NULL, the path is not being used in
conjunction with a context.
.H 2 path_data
.P
Pointer to beginning of data area.
Points are stored in the data area as a list of
PATH_POINT structures.
.H 2 path_cur
.P
Specifies the number of items contained in the
geometry area of the path (path_data).
A path has no geometry description if path_cur is zero.
.H 2 path_end
.P
Specifies the maximum number of path items that
can be held in the path geometry area without reallocation
(i.e., the offset of the last item).
After a new point is placed into the path data area,
path_cur is compared to path_end.
If they are equal,
path_data is extended by the Extend_Path internal operator.
.H 2 path_mark
.P
In order to delay transformations as long as
possible so that as many points as possible can
be transformed at once,
the path_mark field records the offset into the
path when a transformation was last applied.
If the path construct transformation changes,
points added since the last time path_mark was
computed are transformed.
.H 2 path_shape
.P
Points to the SHAPE associated with this path.
If this is NULL,
the path has no area description.
.H 2 path_parent
.P
Designates the source path used in Copy_Path.
If NULL, the path does not share its data with other paths.
.H 2 path_child
.P
Designates the destination path created by Copy_Path.
If NULL, the path does not share its data with other paths.
.H 2 path_flags
.P
PATH_HAS_CLOSE indicates a close or Close Subpath
primitive is in its path.
If the path has no closure directives,
its display can be more easily accelerated.
The other flags are used only by accelerator implementations.
.TB "Path Flags"
.TS
box tab(@);
cf4I cf4I
l | l.
Flag@Description
=
PATH_HAS_CLOSE@path contains PATH_CLOSE, PATH_CLOSESUB
PATH_HAS_3D@path contains 3D coordinates
PATH_HAS_FLOAT@path contains floating point coordinates
PATH_NO_ABS@path has no absolute coordinates
.TE
.H 2 path_penofs
.P
Sequences of Move operations are compressed into
a single Move whenever the path is copied or when
the path pen is inquired.
This variable is only used in the function
di/path.c/compress_moves.
It should be reset to zero whenever the path is cleared.
The variable path_penofs (path pen offset)
describes how much of the path has been compressed.
(To compress a path is to remove unnecessray PT_MOVEs).
If compress_moves is called,
it begins compressing the path from
path_penof + path_data onwards.
.H 2 path_analysis
.P
Not used for framebuffer implementations.
.H 2 path_rendered
.P
Not used for framebuffer implementations.
.H 2 "The Current Path" Path_Cur
.P
A path can only be generated or displayed in
association with a graphics context.
Each context may have a \f2current path\fP
represented by the CTX_PATH attribute.
If this attribute is set to a path object,
context drawing operations append geometry and
color information to the path.
The current path can be displayed by Display_Context.
The Draw_xxx context operators append information
to the current path based on the type of their
second argument.
They are expressed as POINT structures in the
path data area with the type of the POINT
containing the drawing operation and coordinate type.
Other context operators append color or closure information.
.H 2 "Drawing Macros"
.P
To optimize path construction,
the drawing operators are implemented as macros.
These macros use the context path pointers to
determine whether the path element will fit in
the path data area.
The internal context operator, Extend_Context,
extends the current path and brings the context
and path object pointers into agreement.
.TB "Current Path Context Operators"
.TS
box tab(%);
lf4I | lf4I
l | l.
Operator%Description
=
Draw_XXX(ctx, PT_MOVE, ..)%Appends a move (absolute)
Draw_XXX(ctx, PT_MOVEREL, ..)%Appends a move (relative)
Draw_XXX(ctx, PT_LINE, ..)%Appends a line (absolute)
Draw_XXX(ctx, PT_LINEREL, ..)%Appends a line (relative)
Draw_XXX(ctx, PT_CURVE, ..)%Appends a curve control point
Color(ctx, col)%Appends a color to current path
Close(ctx)%Appends a close operation
CloseSubpath(ctx)%Appends a close subpath operation
.TE
.P
The Draw_B2D macro reveals the interaction
between the context and the path.
Note that the point is in the path,
and memory is checked later.
This ``do first, check later'' approach implies
that there must always be room for the path data.
When the path is frozen,
a global storage area is used
(see FREEZE_CTX_PTRS).
Also note that all Extend_Context() does is place a call to Extend_Path() ).
.PC
#define Draw_B2D(CTX, T, X, Y) do {
register path_POINT *PPTR = (CTX)->ctx_buf_ptr;
    PPTR->b.t = (T) | PT_BIN2D;
    PPTR->b.x = (X); (PPTR++)->b.y = (Y);
    (CTX)->ctx_buf_ptr = PPTR;
    if (PPTR >= (CTX)->ctx_buf_end) Extend_Context(CTX);
    } while(0)
.SF
.P
.H 2 "Context Path Pointers"
In order to optimize path construction performance,
copies of the path_top, path_cur, and path_end
offsets are maintained locally within the context
(in the ctx_buf_top, ctx_buf_ptr,
and ctx_buf_end fields respectively).
They provide a fast mechanism for appending the
current path.
Note that the path versions are offsets into the
path data area;
the context versions are actual pointers.
.P
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 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,
most operations that rely on the path
offsets check to see if the path is associated
with a context and update the path pointers from
the context pointers if necessary.
.P
.FG "Path Construction Pointers" FG_Path_Cons_Ptrs
.DS
.BP PSART/ps.pth_cns2 3.5i 0 "" 0.75 0.75 0
.DE
.P
When the current path of a context is changed,
the old path is disassociated from the context
(its path_ctx field is set to NULL and its
path_cur field is updated from the context copy).
The path_ctx field for the new path is set to
reference the context,
and its path_cur and path_end pointers are copied
into the corresponding context fields.
It is these local context path pointers that are
used to append data to the current path.
Switching the current path is accomplished via an
internal path operator,
Attach_Path. 
.H 2 "Copy_Path, Clone_path"
.P
This section provides information about
Copy_Path and its companion operator Clone_Path.
Copy_Path is an external operator that copies an
arbitrary source path to an arbitrary destination path.
Clone_Path is an internal operator used by Copy_Context.
It only copies the current path of a context into
the current path of a different context.
It is used to implement the gsave/grestore
functions in PostScript.
Copy_Path and Clone_Path work essentially the same way.
.P
Because of the nature of X11/NeWS and
P\s-2OST\s+2S\s-2CRIPT\s+2,
copies are often made of paths,
but the copy of the path is neither used nor
manipulated before being discarded.
\*(S) optimizes the copy process by not copying
the path until it is absolutely necessary:\ \&
paths share the same data area as long as possible.
Not only is the data shared as long as neither
path changes the data,
but the shared data permits one path,
called the bottom level child path,
to append points to the path.
.P
The paths sharing data are organized into a
parent-child list,
where the parent is the source of a copy and the
child is the destination.
There is no limit on the number of paths in the list.
Since the parent path knows that the data is good
only up to the point where the copy occurred
(parent_path->path_cur),
the lowest level child is free to add new points
and new transforms without concern for the other paths.
Should the new points be appended to parent path,
a unique copy is made,
and this parent pulled out of the parent-child list.
When Transform_Path() is used,
the child is split off from its parents before
the transforms occur.
Otherwise, \*(S) allows the paths to share data
without the need to spend CPU time copying data.
.H 2 UPD_PATH_PTR
.P
Updates path_cur in the path from the data
pointers in the context.
.H 2 UPD_CTX_PTRS
.P
Initialize context pointers
(ctx_buf_end, ctx_buf_top, ctx_buf_ptr)
with data pointers in path.
.H 2 FREEZE_CTX_PTRS
.P
Freeze context pointers of current path.
Forces all pointers to reference the same global
data location.
When a path item is added,
it is put in this location and Extend_Path is
immediately called to create a path data area
and store the newly added item into it.
.P
The parent paths must extend paths in a different
manner from the bottom-level child path because
the parent paths must make their own copies of
the data before adding new points.
To accomplish this,
\*(S) uses an object extension mechanism to
create a new path type,
CLASS_Fpath, or frozen path.
All parent paths are frozen paths.
Although CLASS_Fpath inherits many of its
operators from CLASS_path,
the implementations of Update_Path(),
Transform_Path(), Attach_Path(), and most importantly,
Extend_Path(), have changed.
.H 2 "Path Operators"
The calling conventions of the external path operators
are documented in the
\f2Shapes Reference Manual\f1.
This section discusses the implementation of these operators,
assuming the reader is familiar with their behavior.
We also describe internal path operators that
are used by \*(S) but not intended to be user-callable.
All path operators are defined in include/sh_PATH.h.
.H 2 "Get_Path, Set_Path"
.P
All of the path attributes are inquired and set
via macros.
The name of the attribute is used to generate a
specific macro to return the structure field
associated with the attribute.
Macros for attributes that require computation
generate calls to the internal Get_Path or
Set_Path operator.
.P
The following section of code shows the macro
definitions for two context attributes to
illustrate the two different methods:
.PC
#define Get_Path(p,a)  CAT(a,get)((Path)(p))
#define PATH_ORGget(p)
        ((POINT_B2D *) GetOper_Obj(p, PATH_OP_Get)(p, PATH_ORG))
#define PATH_STATUSget(p)
        ((int) GetOper_Obj(p, PATH_OP_Get)(p, PATH_STATUS))

#define Set_Path(p,a,v) CAT(a,set)(p,v)
#define PATH_SIZEset(p,v)
        ((p->path_end < v) &&
          Extend_Path(p, v * sizeof(PATH_POINT)))
.SF
.H 2 "Display_Path"
.P
Display_Path is implemented as a macro that
calls an internal raster operator Path_Raster.
This scheme permits generic path code to be used
while allowing rendering to be completely device-dependent.
The operation of Path_Raster is described in
Chapter 4.
.H 2 "Path Area Operators"
.P
The path area operators, Union_Path, Intersect_Path,
Differ_Path, Area_Path, Overlap_Path,
PointIn_Path, Inside_Path, and Translate_Path,
are implemented on top of shape operators of the
same names
(i.e., Union_Path is a call to Union_Shape).
Chapter 11
describes the shape operators in detail.
.H 2 Extend_Path
.P
Extends path data area by a given number of bytes.
If the path is frozen,
a unique and independent copy of the data for the
path must be created.
This operator is called by Extend_Context when
the path area is enlarged during path construction.
.H 2 "Transform_Path"
.P
Transform_Path is implemented as a macro that
calls an internal transform operator Path_Transform.
This scheme permits generic path code to be used
while allowing coordinate transformation to be
completely device-dependent.
The operation of Path_Transform is described in
Chapter 6.
.H 2 Update_Path
.P
Updates untransformed path points by path construct transforms.
The points affected are those between path_mark and path_cur.
If the path is associated with a context and the
context is in immediate mode,
the path is posted instead of being transformed,
allowing immediate mode to be emulated by a path internally.
The actual transformation of points is done by
the internal operator, Path_Transform.
Typically, Path_Transform is device-specific to
allow use of transformation hardware if it exists.
.P
Update_Path is implemented as a macro.
It differs depending on compile time options.
Here is the SH_SMALL version of Update_Path:
.PC
#define Update_Path(p,c) { int temp;
   if ((p->path_cur = c->ctx_buf_ptr - c->ctx_buf_top) &&
       (p->path_cur > p->path_mark))
     {
      temp = p->path_mark;
      Path_Transform(c->ctx_ctm, p, temp),
      p->path_mark = p->path_cur;
     } }
.SF
.H 2 "Inside_Path(path, org, dim)"
.P
Determines whether the specified rectangle is
inside or outside or overlapping the given path.
The org argument references a POINT_B2D
structure containing the coordinates of the upper
left corner of the rectangle in fract 2D format
(real fracts, not integers).
The coordinates are in raster space,
device coordinates relative to the upper left of
the raster.
The dim argument gives the dimensions of the
rectangle in fract 2D raster coordinates.
The return codes are as follows:
.TB "Inside_Path Return Codes"
.TS
box tab(@);
lf4I | lf4I
l  | l .
Code@Description
=
 0@box contained entirely inside path
\(mi1@box entirely outside path
 1@box overlaps path
.TE
.H 2 Attach_Path
.P
Attaches a path to a context.
This operator is invoked whenever the current
path of a context is changed
(CTX_path attribute set).
If the context already has a current path,
that path is detached.
The path construction transform is applied to
pending points,
the context pointers are copied into the path pointers,
and path_ctx is set to NULL.
The new path is attached by setting its path_ctx
to ctx and updating the context pointers from the
path pointers of the new path.
.H 2 Pen_Path
.P
Returns last pen position,
untransformed if possible.
It is called whenever the value of CTX_PATH_PEN
is inquired.
If there are coordinates in the path that have
not yet been transformed,
and if an absolute coordinate can be found,
the path pen is computed from that.
A special optimization is made for the case where
the last point in the path is untransformed and is absolute.
An untransformed path pen yields a return code of 0.
If all of the points in the path have already
been transformed,
RasterPen_Path is called to read the pen,
and a return value of 1 is returned.
In this case,
the caller will have to inverse transform the
pen to return the correct value.
.TB "Pen_Path Return Codes"
.TS
box tab(@);
lf4I | lf4I
l  | l .
Code@Description
=
 0@path pen is untransformed
 1@path pen is transformed
\(mi1@error (path empty)
.TE
.H 2 RasterPen_Path
.P
Returns last pen position, transformed.
Special optimizations are made for cases where
the last point is an absolute coordinate or the
last two coordinates are both MOVES.
This function calls compress_moves to turn
sequences of MOVE operations into a single MOVE.
This may change the geometry area of the path.
.TB "RasterPen_Path Return Codes"
.TS
box tab(@);
lf4I | lf4I
l  | l .
Code@Description
=
 1@path pen is transformed
\(mi1@error (path empty)
.TE
.H 2 "Apply_Path(src, dst, ctx, opt)"
.P
Apply_Path is an operator that applies all or
part of the viewing and/or rendering pipeline to
a source path to produce a destination path.
It is used internally by the outline pipeline to
widen and/or dash fat lines and curves.
It is also used by PostScript to stroke or flatten paths.
.P
The
.UI opt
argument tells which part of the viewing pipeline
to apply.
It specifies what things will happen to the
path \(em transformation,
flattening, widening, etc.
One or more of the following bits may be enabled.
.TB "Apply_Path Options"
.TS
box;
cBI cBI
l | l.
Option	Description
=
CTX_APPLY_MODEL	apply model transform
CTX_APPLY_VIEW	apply view transform
CTX_APPLY_VDC	apply VDC transform
CTX_APPLY_CLIP	clip to view volume (not implemented)
CTX_APPLY_LINE_STYLE	dash the path
CTX_APPLY_LINE_SIZE	widen the path
CTX_APPLY_FLATNESS	flatten the path
.TE
.P
Apply_Path decides where to put the output path
based on its input arguments.
There are several cases.
.BL
.LI
If the destination path is NULL,
a new path is created,
and the result is returned here.
This becomes the return value of Apply_Path.
The source path is left unchanged.
.LI
If the destination path is not the same as the
source path and it is not NULL,
the result is returned in the specified destination path.
Again, the source path is left unchanged.
.LI
If the destination path and the source path are
the same and it is the current path of the given context,
the result will be in the current path of that context.
Note that this path may
\f2not\f1 be the same as \f2srcpath\f1.
This usage does not allow for the case where a
reference to the current path of the context is
saved and used again later.
The CTX_PATH attribute of the context will be
changed by Apply_Path.
.LI
The final case is where the source and
destination paths are the same but they are not
the current path of the context.
This puts the result into the source path.
.LE
.P
Internally, Apply_Path may create one or more
temporary paths to do its work.
To do dashing and widening,
two active paths are needed.
Apply_Path may use sh_path_temp1 and/or allocate
a new path.
It does not use sh_path_temp.
.H 2 "Coordinate Transformation"
.P
The path construction model allows you to apply
the context model transform and/or the context
view transform to all coordinates as they are
added to the path.
If the path construction transform changes,
subsequent points added to the path use the new
transform.
.P
The ctx_ctm field in the context references the
TRANSFORM object to be applied to the current path.
Whenever this transform is about to be modified,
its old value must be applied to the appropriate
points in the current path
(those that have been added since the path
construction transform was last changed).
Thus, transformation of coordinates is done to a
group of points at once rather than to each
individually.
This allows efficient use of hardware
transformation capabilities.
The path construction transformation must also be
applied when the current path is changed or rendered.
This functionality is discussed in more detail in
Chapter 6.
.H 2 "Internal Path Representation"
.P
The elements of the path data area have several
different formats.
Usually, they are typed points
(POINT structures) that look like:
.P
int t, fract/float x, y, z;
.P
The first field is an integer type giving the
drawing operation and point type
(LPT_MOVE_B2D, PT_LINEREL_F3D, etc.)
The next four longwords give the coordinates as
integers or floats
(depending on the preceding type).
Path elements can also be single opcodes,
such as PATH_CLOSE,
or an opcode followed by data.
.P
The PATH_POINT structure defines the internal
format of path coordinates.
All path items are the same size no matter what
their type is.
Except for homogeneous curve control points
(coordinates requiring w),
all path items fit in a single PATH_POINT
structure.
Homogeneous coordinates are represented using two
PATH_POINT structures.
The first contains the x,y,z coordinates.
The second has point type PT_W and stores the w
component in the x field.
Note:\ \&
in the SH_SMALL version of \*(S),
PATH_POINT does not have a z component.
.TB "Internal Path Opcodes"
.TS
box tab(%);
cf4I  | cf4I  | cf4I
l | l  | l .
Operation%Opcode%Description
=
PT_MOVE%PT_MOVE_B2D%Move absolute fract 2D
%PT_MOVE_F2D%Move absolute float 2D
_
PT_LINE%PT_LINE_B2D%Line absolute fract 2D
%PT_LINE_F2D%Line absolute float 2D
_
PT_MOVEREL%PT_MOVEREL_B2D%Move relative fract 2D
%PT_MOVEREL_F2D%Move relative float 2D
_
PT_LINEREL%PT_LINEREL_B2D%Line relative fract 2D
%PT_LINEREL_F2D%Line relative float 2D
_
PT_CURVE%PT_CURVE_B2D%Curve control point fract 2D
%PT_CURVE_F2D%Curve control point float 2D
_
Close%PATH_CLOSE%Close the current area within the path
_
CloseSubpath%PATH_CLOSESUB%Close current subpath
_
Color%COL_xxx%Set current color
_
Curve%PATH_CURVE%Set curve form
_
Surface%PATH_SURFACE%Set surface form
%PATH_END%Indicate end of path
.TE
