'\"!  tbl | mmdoc
.if n .pH arch.edge @(#)edge	40.1
.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
.BK "Shapes Internal Architecture"
.CH "The Edge Table" "12"
.H 1 "The Edge Table" 
.H 2 "Introduction"
.nh
An edge table is an internal-only object that
facilitates the rendering of polygons.
It is a two-level linked list.
At the first level,
an edge table is a linked list of polygon edges,
one edge per edge table entry.
At the second level,
an edge table is a list of memory blocks with
multiple edges per memory block.
.H 2 "Level 1\(emPolygon Edges"
.P
Each edge table entry contains the following fields
(as defined in src/include/di/sh_ET.h).
.P
Each entry can describe a curved or straight polygon edge,
and contains all the fields necessary to step
along either edge type during polygon scan-conversion.
.P
The edge table fields table:
.PC
typedef	union { float f; Sgn32 i; } EDGE_COORD;

typedef struct sh_poly_edge_table
  {
   EDGE_COORD xstart, ystart, wstart;
   EDGE_COORD x1, y1, w1;
   EDGE_COORD x2, y2, w2;
   EDGE_COORD xend, yend, wend;
   Sgn8       direction;
   Unsgn8     edge_type;
   SHAPE      shape;
   ENTRY      *y_ptr;
   Sgn32      breserr;
   Sgn32      in1, in2, in3, in4;
   struct sh_poly_edge_table *nxt;
  } POLY_EDGE;
.SF
.H 2 "Level 2\(emMemory Blocks"
At the second level,
an edge table is a list of memory blocks with
multiple edges per memory block.
The structure of each block consists of a header
field followed by edge data.
.P
The header field contains the following fields:
.P
et_prev \(em a pointer to the previous memory block in the list
.P
et_next \(em a pointer to the next block in the linked list
.P
The first edge entry immediately follows these two fields.
If there is only a single edge table in the system,
\*(S) renders its primitives in a sequential fashion,
and thus there cannot be more than one active
polygon at a time.
This global edge table can grow,
but will never shrink and is never deleted.
.H 2 "The et Field"
The field \f2et\fP in the global variable
sh_fb_rend_glob maintains a series of pointers
that in turn maintain the current state of the
edge table.
The fields in this structure as defined in
src/include/di/sh_ET.ah are as follows:
.TB "The et Fields"
.TS
box tab (@);
cf2 | cf2
l | l.
Field@Description
=
et_next@Pointer to the first memory block in block list.
_
et_this@Pointer to the current memory block.
_
ET_START@Pointer to the first entry in the edge
@linked list. Note that the first entry
@in this list is always a ``dummy'' entry \(em
@its data is never interpreted, but is used
@to ease manipulations of the list.
ET_BOUND@Pointer to the first edge in the current
@bound. Note that this is not always the
@same as the first edge in the list:  a polygon
@can have multiple bounds (for example a polygon
@with several holes).
_
ET_CUR@The first open entry in the linked list.
_
et_end@Pointer to the end of the current memory block.
.TE
.H 2 "The POLY_EDGE Structure"
This section gives a short description of each field in the
polygon edge table structure.
This structure is defined in include/di/sh_ET.h.
.H 2 "nxt"
.P
Pointer to following POLY_EDGE structure.
.H 2 "xstart, ystart, wstart"
.P
X, Y coordinates of start of edge or
X, Y, W components of first curve control point.
.H 2 "xend, yend, wend"
.P
X, Y coordinates of end of edge or
X, Y, W components of last curve control point.
.H 2 "x1, y1, w1"
.P
X, Y, and W coordinates of second curve control point.
.H 2 "x2, y2, w2"
.P
X, Y, and W coordinates of third curve control point.
.H 2 direction
.P
Original edge orientation.
.H 2 edge_type
.P
Type of edge.
This field is composed of bits from the following table.
For example, a 3D floating point edge describing a rational conic
would have a type of EDGE_TYPE_FLT | EDGE_TYPE_RATIONAL |
EDGE_TYPE_3D | CONIC_EDGE_TYPE.
.TB "Polygon Edge Types"
.TS
box;
cf4I lf4I
l | l.
Type	Description
=
EDGE_TYPE_FLT	Edge coordinates are floating
EDGE_TYPE_RATIONAL	Rational curve segment (has W)
EDGE_TYPE_3D	Edge coordinates are 3D
LINE_EDGE_TYPE	Line segment
CONIC_EDGE_TYPE	Conic (order 3) Bezier curve
CUBIC_EDGE_TYPE	Cubic (order 4) Bezier curve
SHAPE_EDGE_TYPE	Shape computed for edge
.TE
.H 2 shape
.P
Shape object describing pixels of a thin curved edge.
.H 2 y_ptr
.P
Pointer to current Y shape range.
.H 2 breserr
.P
Bresenham error accumulator.
.H 2 "in1, in2, in3, in4"
.P
Increments for bresenham along edge.
.H 2 "Polygon rendering"
.P
This is the code called by the RenderPgon drawing function.
Polygon rendering follows a two step approach:\ \&
first, a polygon is scan-converted into a shape,
then the shape is rendered to the screen.
The polygon algorithm is a standard
scanline-based algorithm with extensions and
optimizations.
The optimizations include special-casing rectangles
(easily distinguished based on the number of input edges)
and two-edge active polygons
(also relatively easy to detect).
If these special cases fail,
then a scanline polygon algorithm works as follows:
.AL
.LI
Sort all of the edges by Y.
.P
The pointers in the edge linked list are
re-organized so that when the edges are now encountered,
the minimum Y in each edge occurs in increasing Y.
Horizontal edges are discarded,
since they have no effect on a polygon
during filling.
The direction field is updated during this
process because the x/ymn and x/ymx fields are
sorted so that ymn <= ymx.
In addition,
the bresenham error terms and accumulators are
initialized for each of the straight edges,
and a pixel description in the form of a shape
created for the curved edges.
.LI
Build a second linked list
(by once again changing edge pointers)
so that the active edges are in one list,
while the other edges are stored in a second list.
.P
An active edge is an edge whose y range surrounds
the current y
(the starting Y is the minimum Y of all the edges).
These active edges are now sorted by
the X that intersects the current scanline and
the result is a list of all the edges that
intersect the current scanline sorted by x.
.LI
Identify the x ranges that are inside of the
current polygon.
.LE
.P
\*(S) supports two methods of filling polygons:\ \&
non-zero winding, and even-odd filling.
The first method depends on the direction of each
edge as follows:
.AL
.LI
A counter is initialized to zero.
.LI
The direction of each edge is added to this
counter starting from the edge with minimum
current X to that with maximum current X.
So long as the value of this accumulator is non-zero,
one is inside the polygon.
Otherwise, one is outside.
The even-odd fill rule specifies that filling is
enabled between the first and second edge encountered,
the third and fourth, etc.
.LI
The current Y is now incremented,
one step is taken along each of the active
edges\(emeither with a bresenham algorithm for straight edges,
or by incrementing the y_ptr pointer for curved edges.
.LI
The last two steps are repeated.
.LE
.P
This process continues until all the edges have
been processed.
.H 2 "Caution"
The polygon code does essentially no error
checking on the edges in a table.
Thus, for example, there is no effort to insure
that the current sequence of edges forms a closed
loop or exists in edge pairs.
The polygon code is thus very easy to crash
and requires careful coding during edge table
construction to avoid this problem.
.H 2 "Curve Rendering"
The edge table is an integral part of rendering
both curve bounded regions and thin curves
(fat curves use an entirely different mechanism
and set of routines).
In fact, rendering thin curves and curve-bounded
regions differs only in the final step,
the actual rendering of the curve.
The code and steps followed up to this point are
the same.
.P
The first step in rendering a curve is to
create a list of edge table entries by loading
the control points to each consecutive curve into
a POLY_EDGE structure.
A separate pipeline is called to load either
conic or cubic curves
(sh_fb_conic_b2d, and sh_fb_cubic_b2d, respectively).
.P
The polygon code continues to add to the edge
table until the end of the bound.
Straight, conic, and cubic edges can be mixed in
a single edge table:\ \&
they are distinguished by the value loaded into
the edge_type field in the edge table.
.P
Scan conversion of the curves into pixel
descriptions is performed during polygon
initialization.
Integer iterative functions are used for scan
conversion of both conic and cubic curves.
The Pitteway algorithm for the scan-conversion of
conics is described in two papers:\ \&
``Algorithms for drawing ellipses and hyperbolae
with a digital plotter''
(Pitteway, M.L.V., Computer Journal, B10P,
pp. 282\(en289, 1967),
and ``Techniques for conic splines''
(Pratt, V., Computer Graphics, Vol 19, No 3,
pp. 151\(en159, 1985).
The adaptive forward difference algorithm used to
scan-convert cubic curves is described in
``Adaptive forward differencing for rendering
curves and surfaces''
(Lien, Sheue-Ling, et al, Computer Graphics,
Vol 21, No 4, pp. 111\(en118, 1987).
.P
Thin curve rendering follows a slightly different
course after parsing of the path.
The edge table is passed to the routine
sh_fb_render_curve_2d,
which traverses the edge table,
scan-converting each curve,
then filling the resulting shape directly in the
destination raster.
.H 2 "Polygon Scan Conversion"
.P
As the polygon edge structure is initialized for
each edge of an area,
information is accumulated to improve performance
later during edge processing.
.P
The simplest form of information obtained is a
count of edge types.
The counts include the horizontal edges,
the vertical edges, the curved edges,
and the total number of edges minus the
horizontal edges.
When edge processing begins,
if the number of vertical edges is equal to the
total number of edges,
then the edge processing code assumes the area is
one or more rectangles and calculates where old
edges end and new edges begin along the y-axis,
skipping the scanlines between those.
The single rectangle can easily be a
special case if the number of vertical edges is
equal to the total number of edges and
the total number of edges is 2.
.P
Other edge processing simplifications can be made,
especially if the hardware has quad-fill capability.
If an area is \f2two edge active\fP,
i.e., there are never more than two active edges per scanline,
there is no need to resort edges after processing each scanline.
Also, since there is never more than one edge pair per scanline,
one of the inner edge processing loops can be removed.
If the hardware has quad-fill capability and rectangle clipping support,
software scan conversion can be completely
eliminated also as long as there are no curved edges.
.H 2 "Two-Edge-Active Test"
A test during edge structure initialization takes
advantage of the fact that edges are always
presented in a continuous manner \- the end point
of one edge is the starting point of the next
edge in the edge list
(unless a subpath ends at the current edge).
The test is designed to never give a false
positive while attempting to limit the false
negatives without adversely affecting edge
initialization performance.
.P
For example, if a discontinuity in y is detected
from one edge to the next,
the test will fail even though each of the
subpaths may not intersect each other vertically
and may not each contain more than two active edges.
.P
The test performs the following actions:
.BL
.LI
Counts the number of times an increasing-y edge
is followed by an edge decreasing-y or vice versa.
.LI
Determines where a local maximum-y or minimum-y exists.
.LI
Assumes the area is two-edge-active if the total
area defined by all the edges contains only 1
maximum-y and 1 minimum-y and if the edges were
presented as a single continuous edge list.
.LI
Verifies that none of the edges from the
increasing-y side of the area cross those on the
decreasing-y side to eliminate edge sorting.
This can be easily determined if a bounding box
is accumulated for the increasing-y edges and
another bounding box is accumulated for the
decreasing-y edges
(a left-half and a right-half bounding box).
If the two bounding boxes intersect in x,
then there is a chance that an edge crossing may
exist and the two-edge-active test fails.
.LE
.P
However, consider a square rotated 45 degrees
around the z-axis to form a diamond shape.
If the x-value of the y-maximum exactly matches
that of the y- minimum,
the two-edge-active test will pass.
If, however, the rotation is slightly different,
the left- and right-half bounding boxes will
intersect and the test will fail.
To reduce the number of false negatives,
the code does not include the two edges where a
local y-maximum or y-minimum occurs in the
left/right bounding box determinations
(they are included in the total bounding box determination).
To accomplish this,
the bounding box updates are delayed by 1 edge so
that both edges can be eliminated when a
y-maximum or y- minimum is detected.
In this way, the two-edge-active test has a much
greater chance of passing while still avoiding
false positives.
