\documentstyle{report}
\title{The PostScript Zone\\
3D PostScript: Zone, Linmap, Warpmap, and Breakpath}
\author{Kevin Iga and Jon Monsarrat}
\date{V1.0 6/19/1991\\
Current Version: V1.0 6/19/1991}
\maketitle
\setlength{\oddsidemargin}{0pt}
\setlength{\textwidth}{7in}
\begin{document}

\chapter{Introduction}

\begin{quote}
You're traveling through another dimension.\\
A dimension not only of length and width, but of depth.\\
That's the signpost up ahead.\\
Your next stop---{\em the POSTSCRIPT ZONE}.
\end{quote}

\section{Abstract}
Normal 2D PostScript tranformation from the user page to the device
page is done with a series of 2x3 matrices. Extrapolating into three
dimensions, we have built an analogous library of 3D Postscript 3x4
matrix operators that allow the user to draw paths, translate, scale,
rotate, and otherwise treat PostScript as if it were dealing with
three dimensions and not two.

Zone is a set of macros which, when the user wants to draw a 3D path,
using natural extensions to PostScript like moveto3 and rlineto3, and
actually projects the relevant points to the user page using perspective.
From there, normal PostScript operators like stroke and fill are available.
To use even more of the PostScript path-drawing operators, Linmap imbeds
what used to be the user page into 3-space.  Similarly, Warppath
allows this imbedding to be non-linear.

Breakpath is a library that allows filling when warping would cause
superfluous self-intersections, by breaking the region into small trapezoidal
regions.  This has other applications like checkerboarding and filling
arbitrary paths with text.

3D clipping, hiding, shadows, and stereo vision are among the many
features not implemented currently.  A discussion of some of our
ideas is included.

\section{Why PostScript}
As simulation becomes more important and complex, so must the
simulation user interface become more useful. Rather than spelling it
out in text, many simulators are using 3D graphics to demonstrate
results. Unfortunately, most 3D graphics packages don't have the
versatility or speed of home-made programs, and nobody wants to write
an entire graphics interpreter just for their small project.

There is, then, a discernable need for a half-way house that provides
a library of routines in a popular language to allow versatility
without difficulty.

The official withdrawl of goliath Motorola from its attempted entry into
the printer software market has proven once and for all the stability
of Adobe's PostScript processing language. And while fancier languages
might one day come along, the number of libraries and amount of
expertise already invested in PostScript ensure that, like Fortran, it
will be around forever.

Although every university and business with a graphics department has
powerful computer 3D graphics, they generally use their own graphics language
and representation. It makes sense that the powerful 3D and picture
techniques privately held come out into the open and popular
PostScript language where anyone can use them. Workstations with PostScript
interpreters already have all of the processing power needed for fancy
images, and printer technology is rapidly catching up.

Why PostScript, and not a pre-processor written in another language,
like C? There are many books with C graphics routines. But we
want to keep the intuition of PostScript, and we want to be able to
use PostScript routines in the program, especially when the locations
of certain objects is dependent on results from PostScript
calculations like stringwidth and boundingbox.

Ultimately a pre-processor is really the better idea, because
workstations have so much more computing power. But short of writing a
complete pre-processor on our own, perhaps some volunteer will help
write it as an addition to GNU GhostScript which can ``speak''
PostScript both in input and output, and could serve as a PostScript
preprocessor for any PostScript printer.

\section{Overview}

This package includes this documentation file, four programs, and a number
of examples:

\begin{description}
\item[zone.ps] is the Three-D PostScript; it is a set of macros over PostScript
that allows you to pretend you are drawing in three dimensions.

\item[linmap3.ps] is a program that maps a 2D path onto any plane in the
3-space of zone.ps

\item[warpmap3.ps] is a program that maps a 2D path using a user-defined
warp function into the 3-space of zone.ps

\item[spherewarp.ps] is an example of such a user-defined warp function
that maps the plane stereographically onto a sphere

\item[sphere2warp.ps] is a user-defined warp function that maps the
plane totally around a sphere

\item[cylinderwarp.ps] is a user-defined warp function that maps the
plane around a cylinder

\item[butterflywarp.ps] is a user-defined warp function that maps the
plane in a surface of negative gaussian curvature

\item[latlongwarp.ps] is a user-defined warp function that maps a
cylindrical projection (a way of spreading a globe into 2D)
onto a sphere. Assumes X coordinate is latitude and Y coordinate is longitude.

\item[breakpath.ps] holds a library of path-chopping algorithms; in particular,
algorithms to chop a path to be filled into small trapezoids.  Useful when
filling regions on warps.

\item[ex\_....ps] a lot of examples, described in HOWTO-EXAMPLE.txt

\item[README]  Read him.

\item[HOWTO-EXAMPLE.txt] What the examples are, which programs need to
  be concatenated to them, and how to modify them for interesting effects

\end{description}

\section{Zone---a 3D preprocessor for PostScript}

To start making drawings in 3-space (known as ``the Zone''), create a
new file using some text editor and include the prescript library file
zone.ps at the beginning. It has to go before any 3D path-defining
code that you write. When using any of the libraries included you will
need similarly to place the library in the file before your own code
(or before the example file).

Then construct a PostScript program the way that you normally would.
Nothing has changed about the basic PostScript language, and you will
find that all your normal 2-space programs work fine. An extra set
of operators will manipulate your 3-space.

For example, normally in PostScript, you might create a line with ``200
100 moveto 50 10 lineto stroke''. ``moveto'', ``lineto'', and ``stroke'' are
all operators which are defined in any PostScript book. There are
analogous operators ``moveto3'', ``lineto3'', and ``stroke3'', which are
documented here but you might also just intuit their 3D meaning
without looking at the documentation. ``150 10 71 moveto3 100 20 61
lineto3 stroke3'' will draw a line in 3-space from the (x,y,z)
point (150,10,71) to (100,20,61).

This 3-space of course must eventually be projected into the
user page, which will eventually get transformed into device
space as the page prints out or image is drawn on the screen. And just
as you can translate and scale the way 2-space fits on the
device page, you can translate3 and scale3 3-space to fit in
your 2-space. So when it finally prints out, the
transformation matricies of both 3D and normal 2D spaces are used to
make the drawing. The default 3D view is with the 3D origin in the
middle of the page with X and Y axis going right and up respectively,
with the Z axis out of the page.

Here is a list of operators defined. The rule of thumb is that they
work just like the analogous PostScript operators, only in 3D.

\subsection{Path Construction Operators}
\begin{tabular}{rcll}
-   &   newpath3   &      -  &
   Clears the 3D path.\\
-   &   currentpoint3 &   x y z &
   Returns the 3D current point (x,y,z) \\
x y z & moveto3 &  - &
   Moves current point to (x,y,z) \\
dx dy dz & rmoveto3 & - &
   Moves current point from (x,y,z) to (x+dx,y+dy,z+dz)\\
x y z  & lineto3 &   - &
   Appends a line to the path from current point to (x,y,z)\\
dx dy dz & rlineto3  & - &
   Appends a line to the path from current point (x,y,z) to\\
&&&(x+dx, y+dy, z+dz)\\
- &  closepath3 &  - &
   Appends a line from current point to the original point\\
&&& of the subpath (the point last set by a moveto3 {\em or} moveto)\\
- &  reversepath3 &  - &
   Reverses the direction of the current path. Same as
reversepath\footnote{Actually operates on the 2D path of course; there is no
real stored 3D path.}.\\
- &  flattenpath3 &  - &
   Does nothing; included for compatibility with 2D PostScript.\\
- & strokepath3 &  - &
   Same as strokepath; included for compatibility with 2D PostScript.\\
\end{tabular}

\subsection{Path Construction Operators With No Analogy}
Because there is no real 3-space path (any 3D point is converted into
2-space and a normal 2D path is constructed), there can be no
3D analogy to pathforall, pathbbox, initclip, clip, eoclip, or clippath.

Also because there are no 3D fonts (yet), having a charpath3 makes
little sense. To place fonts in 3-space, you should define them in 2D
space normally, use charpath on some font that you have permission to
'pathforall' (i.e. not Adobe locked fonts), and then use the Linmap
library to stick the 2D drawing in 3-space (in an arbitrary fashion
and shape). More on the warppath library later.

Also there is no 3D arc, arcn, arcto, curveto, or rcurveto, since a
Bezier curve in 3D will not, in general, project into a Bezier curve
in 2D, which is what PostScript has available.  In order to achieve the
fidelity of the desired path, we were forced to break up each curveto
into smaller lineto's using the PostScript operator flattenpath. You
may wish to adjust the amount of flattening with the ``setflat''
operator. Flatter paths compute faster but may look choppy.

Essentially we would be forced to break a 3D curveto into a flat 3D path,
and hacking together a setflat3 to handle this breaking up seems a
little anachronistic if we haven't even built a real 3D path yet. The
easiest way to get 3D arcs and any arbitrary complex image is to draw
it in 2D, and then warp the 2D image into 3D as described in the
Linmat library section later. Because there are no curves in 3D
space, flattenpath3 has been defined as null.

If anyone comes up with a good alternate solution that would be faithful
to a true Bezier curve in three dimensions, or even represents a consistent
curve for different vantage angles, please let us know.

\subsection{Matrix Operators}
Matrix operators are a complex and versatile way of manipulating
3-space. Read the red book to learn more about matricies in the 2D world.

\nopagebreak
\begin{tabular}{rcll}
 - &  matrix3  & matrix &
    returns identity matrix\\
 - & initmatrix3 & - &
    fills CTM3 with the identity matrix \\
matrix & identmatrix3 & matrix &
    fills matrix with the identity matrix\\
matrix & defaultmatrix3 & matrix &
    same as identmatrix3 \\
matrix & currentmatrix3 & matrix &
    fills matrix with CTM3\\
matrix & setmatrix3 & - &
    fills CTM3 with matrix \\
tx ty tz & translate3 &-&
   translates by tx ty tz\\
sx sy sz & scale3  & - &
   scales by sx sy sz \\
angle & rotate3& - &
   defaults to rotatez3 \\
angle & rotatez3& - &
   rotates around Z axis. Right hand rule applies. \\
angle & rotatey3 & - &
   rotates around Y axis. Right hand rule applies.\\
angle & rotatex3 & - &
   rotates around X axis. Right hand rule applies. \\
matrix & concat3  & - &
   replaces CTM3 with matrix $\times$ CTM3\\
matrix1 matrix2 matrix3 & concatmatrix3 & matrix3 &
   fills matrix3 with matrix1 $\times$ matrix2\\
x y z & transform3 & x' y' z' &
   transforms (x,y,z) by CTM3\\
x y z matrix & transform3 & x' y' z' &
   transforms (x,y,z) by matrix\\
dx dy dz & dtransform3 & dx' dy' dz' &
   transforms distance (dx,dy,dz) by CTM3\\
dx dy matrix & dtransform3 & dx' dy' &
   transforms distance (dx,dy,dz) by matrix\\
x' y' z' & itransform3 & x y z &
   inverse transform (x',y',z') by CTM3\\
x' y' z' matrix & itransform3 & x y z &
   inverse transform (x',y',z') by matrix\\
dx' dy' dz' & idtransform3 & dx dy dz &
   inverse transform distance (dx',dy',dz') by CTM3\\
dx' dy' dz' & matrix idtransform3  & dx dy dz &
   inverse transform distance (dx',dy',dz') by matrix\\
matrix1 matrix2 & invertmatrix3 & matrix2 &
   fills matrix2 with inverse of matrix1\\
\end{tabular}

\subsection{Other Operators}
\begin{tabular}{rcll}
 -   &  stroke3 &    -  &
   strokes the projection of the current path \\
x y z &  project3d &  x' y' &
   projects 3D point (x,y,z) to \\
& & & (x,y) using the perspective projection\\
 - & gsave3 & - &
    Saves currentpoint and current\\
& & & transformation matrix (CTM3) on 3D graphics stack.\\
& & & Also does a normal ``gsave''\\
 - & grestore3 & - &
    Restores currentpoint and current\\
& & & transformation matrix (CTM3) from 3D graphics stack.\\
& & & Also does a normal ``grestore''\\
 - & grestoreall3 & - &
    Initializes graphics stack and CTM3.\\
&&&    Also does a normal ``grestoreall''\\
\end{tabular}

Some of the operators don't really do anything. For example,
``stroke3'' is just defined to be ``stroke''. This is because as the 3-space
path is built, it is instantly transformed into a normal 2D path.
However, in the future we will probably actually construct a real 3D
path, so for the sake of version compatibility please use
the ``stroke3'' when dealing with a 3-space.

\subsection{The Perspective Projection}

Zone uses a perspective projection to map the 3-space onto the 2D
PostScript page.  The model here is that you are looking at a screen
a certain distance sz3 away, at an object with an origin at a distance
of dz3.  Every point on this object appears to your eye to be coincident
with a point on the screen.  The perspective projection maps the point on
the object with the corresponding coincident point on the screen.

Initially, dz3 and sz3 are defined to be equal so that the origin lies
on the plane of the screen.  The user can change these (though negsz3,
the negation of sz3, is what is really defined).  Note, however, that
it is possible to effectively change dz3 with translate3, and sz3 with
scale (normal 2D scale).  If you want drastic perspective, make
dz3 small (or translate so that the origin is closer to your eye).  If
you want minimal perspective, make dz3 large (or translate so that the
origin is far away from your eye).  To preserve the scale, of course,
you will need to multiply sz3 by the same ratio.

Note that points behind the eye are mapped to the negative point on the screen,
and that points in the plane of the eye don't match up to any point on the
screen.  For this reason, it is suggested that you do not draw behind the
eye ($z > dz3$).

The inital value of dz3 and sz3 is 500, so that your eye is at (0,0,500).

\section{Linmap}

Linmap is the way to use your normal postscript commands as if the
postscript page were a plane in the 3D space.  In this way, you can
take your old postscript programs and make them bona fide 3D objects.
To use it, draw your picture, then {\em before} you stroke, fill, or
clip, use linmap.

Linmap takes the current path and turns it into a transformed path,
in a plane defined by linctm3, and projects it back to the 2D page using
Zone's perspective 3D rendering.  The resulting current path is the
transformed path.

The plane is defined by linctm3, and is originally in the plane of z=0,
so that it is face-on.  Using zone matrix operators, you can rotate,
translate, scale, or set this plane.

Linmap approximates curves with flattenpath.  This is because a Bezier
curve, mapped in this fashion, is, in general, not a Bezier curve.
For the sake of having a consistent curve, for different CTMs, we
break up the curve into small lines with flattenpath.  For decent
resolution in flattenpath, however, the difference is imperceptible.

\section{Warppath}

Just as Linmap is for linear maps, Warppath is for non-linear maps.
Suppose, for example, you wanted to map the plane onto a sphere.
Warppath is the tool to use.  Instead of saying ``linmap'', you would
say, ``warppath''.  Instead of setting a transformation matrix, you define
a warping function.

\subsection{The warping function}
The warping function for this mapping is called ``warp3'', which the user
must define. warp takes two numbers x y from the stack and leaves
three numbers x' y' z' on the stack. We provide you with a number of sample
warp functions to experiment with.

\begin{itemize}
\item spherewarp.ps - Wrap around a sphere (to the center)

\item spherewarp2.ps - Wrap around a sphere (to the top)

\item cylinderwarp.ps - Wrap around a cylinder

\item latlongwarp.ps - Wrap a cylindrical projection around a sphere

\item butterflywarp.ps - Wrap onto a surface of negative curvature
\end{itemize}

\section{Using WarpFill}
Warppath takes a 2D path and returns a 3D path, which Zone uses to
make a projected 2D path.  For stroking, this produces the correct
result; but if the resulting path is filled, there are problems,
especially when dealing with regions that ``fold over'' with the
warp surface onto itself.

If the region is broken up, however, into small pieces, each piece will
be fairly well-behaved.  This is the purpose of WarpFill.

WarpFill is a front end to Warppath, put it can be used on its own.
The purpose is to take a path intended for fill, and breaks it up
into small pieces, each of which it warps and fills.

\subsection{User-definable Variables for Filling}

The PostScript Red Book has a good explanation of filling in Chapter
4.6: Painting.  Warp Painting works in the same way. When filling a
complex image, we need to know which points are inside, and which are
outside.

The general technique of deciding whether a point A is inside or
outside is to start outside the shape (at infinity) and examine the line
to the point A, looking for intersections with the path.  There are
two ways to use this information to determine whether or not point A
is inside or outside.

If we use ``winding number'' (the PostScript default), we stop at each
point where the line intersects the path.  Depending on whether the
path is going counterclockwise or clockwise we either add or subtract
to our ``winding number'', which is defined to be zero at infinity.
Whenever the winding number associated with a point is zero, we
declare the point to be outside the image.

The other way of calculating ``inside'' is again to start at infinity
and examine the line to the point A, assuming that every time we cross
the path we change from inside to outside or vice versa.  Thus, if we
cross an even number of times, we say that the point A is outside the
path, while if we cross an odd number of times, we say that the point
A is inside the path.  This method is called the even-odd rule.

In the example file, Shape2 is defined ``correctly'' and looks the same
either way. Shape3 is defined ``wrong'' and looks different depending on
which rule is used.

Use the evenodd boolean variable as a means of controlling which rule
WarpFill will use. If ``evenodd'' is defined as true, the evenodd rule
will be used, else the winding rule will be used. ``/evenodd false
def'' will result in a what PostScript uses for ``fill'' as a default,
and is usually the default that will produce the desired effect.

Use the ``fillout'' boolean variable to determine whether you want to
fill inside or outside the object (something that PostScript does not
normally allow you to do in two dimensions). If ``fillout'' is defined
as true, then all areas outside the path up to the borders will be
filled.  Defining ``fillout'' to be false is the usual default and filling
will take place as normal inside the path. TM, BM, LM, and RM are all
variables defining borders for the page, for outside filling. Try not
to set them ludicrously large, or WarpFill will use up ludicrously large
quantities of time and memory.

To actually stroke or fill in warped space, first define the path
using normal PostScript operators. Then use WarpStroke in
place of stroke and WarpFill in place of fill.

\subsection{Limitations and Workarounds}
PostScript doesn't have any way to do garbage collection or memory
management except with the 'save' and 'restore' operators which we use
as best we can. Any complex path may be too complex for flattenpath to
do a good job, and you should try using 'setflat' to adjust the extent
to which the path is flattened. Alternatively, try breaking up the
path into lines (for stroking) or regions (for filling).

Any PostScript printer, if fed the same piece of paper twice, will
have a 1/4 inch error somewhere just because it's not feeding the
paper through the printer exactly properly. However, if you have two
complex images which don't have to be exactly aligned, you could try
printing them out separately, feeding the paper through twice.

When in doubt, simulate it on-line and take a bitmap ``snapshot'' of the image!
That's how I'm forced to print out my most complex images, by
simulating with GhostScript in X and then using ``xdpr'' to printout a
snapshot of the bitmap comprising the X window.

Chances are that unless you really need a lot of accuracy, you can
afford to have ``delta|'' reasonably large, unless the warp space you're
translating into is really heavily curved.

\subsection{Flatten the Path into Line Segments}
Unfortunately, it is simply not possible to represent warp spaces by
curveto's and other mathematically precise representations.  Except
with the simplest transformations (translating, rotating, and
scaling), lines and curves become strange things that cannot be
represented in PostScript. Therefore we are forced to use the
PostScript operator 'flattenpath' to break a curvy path into a series
of lines. The good news is that if your printer has enough memory to
do a good flattenpath, you really can't tell the difference.

Filling cannot be done iteratively on the path, because we need to know every
aspect of the path to know where the boundaries to our filling regions
are. Therefore, WarpFill passes the flattened path to the routine
Approx which will represent the path as a triple-dimension array. Once
we have a global knowledge of the entire path, we can begin to
understand what it looks like, region-wise.

\subsection{Break the Path into a Path Representation}
The PostScript operator ``pathforall'' skips along the currentpath,
calling different routines when it finds moveto's, lineto's, and
closepath's. There shouldn't be any curveto's because the path has
been flattened.

Whenever a ``moveto'' is encountered, it starts a new subpath. There can
be several subpaths inside one current path. In general a subpath is
much like having a completely separate path for stroking, but it is
taking into account for filling because it helps to define the overall regions.

Closepath is just a handy alias for going back to the starting point
of the current subpath. Closepath generally emulates ``lineto'' back to
the starting point. However, for filling purposes, even a path which
is not closed gets closed with a straight line. This in effect puts a
closepath automatically at the end of all subpaths. This is the standard
PostScript way of handling filling open subpaths.

The path is broken into an array of arrays of arrays. The outermost
array is just a series of subpaths, each of which is an array of
arrays. These double-arrays are series of vertices which compose the
endpoints for all the line segments in the path. Each vertex is a
small [ X Y ] array.

\subsection{Why Tiling}
The simplest solution to filling in warp space is to warp the
1-dimensional path into a 1-dimensional warped path, and then fill
that. This works, takes up less memory, and is generally a good idea.
However, there are a couple of reasons to do tiling to handle complex
cases. For one, suppose that your simple circle is now flattened into
a thousand little line segments. The printer (or other device) may not
be able to handle such a big path for filling, which means you must do
it iteratively by breaking it up. Or if your normal line turns into
an impossibly long curve in warp space, it must be approximated with a
thousand little line segments, which give the same filling problem.

Perhaps the best reason to have full tiling, however, is possibly
because when warping a two-dimensional plane in 2-space, any flat
region is equal to the sum of its tiles, but when warping a
two-dimensional plane in three space, any flat region composed of
tiles can be different depending on what angle it is being viewed at.
In particluar, if your region is on a sphere, and the vantage point
is such that the region is at the edge of the circle that the sphere maps
to, then the path might intersect itself, so that some parts of the
region to be filled is declared ``outside'' by PostScript and are not
filled.  With WarpFill, though, we only deal with small patches that
are less likely to have this problem, and when it does, happens to
an unnoticable degree.

A good enhancement for the WarpFill routine would be to add a little
intelligence so that if it knows when combining tiles is not harmful to
the filling region, and does so whenever possible.

\subsection{Tiling in the Y Direction}
A simple loop goes through the mock path ``coords'' that Approx produced
and makes an array of all the Y values of all  X Y  vertices. This
list is then sorted in increasing order, with duplicates being
removed. We want to guarantee that between any two lines y=Y, for all
Y in this list, there are no vertices.

Also we want to guarantee that no two consecutive Y values are more
than 'delta' width apart, so as the second big loop in WarpFill steps
through the Y values and passes them along to TileLine, it makes sure
that any large spaces are plugged with extra Y values.

\subsection{Tiling in the X direction}
TileLine accepts Y values in consecutive pairs, bounding an infinite
horizontal region. We've made sure that there are no vertices in this
infinite horizontal region, so any line segments that pass through
this region must pass all the way through. Any two of these line
segments form the left and right sides to a trapezoid bounded on top
and bottom by the normal boundaries to this infinite region.

\subsection{Scanning our infinite horizontal space}
Our step now, then, is to take the list of vertices and grab all the X
values where the path intersects the two Y lines. CheeseWhiz is the
routine that does this by traversing the mock path 'coords'
and passing all line segments to a subroutine called CheeseY.

CheeseY figures out which line segments cross the Y lines, and whether
the line segments ACTUALLY pass through the infinite horizontal space
or whether they just happen to have an endpoint on one of the Y lines.
If it's the latter case, these lines don't really count and there
aren't including.

Also there's a twist. CheeseY doesn't just return X values, it returns
X W  where W is the winding value. W is -1, 0, or 1
depending on whether the line segment at the point of intersection is
going down, horizontal, or going up. In other words it's the sign of
the slope. This is kind of complex; read about winding values in the
Red Book.

\subsection{Not all Edges are Inside/Outside boundaries}
CheeseWhiz sorts the big old array so now we have an array of all X
intersections with the infinite Y lines (top or bottom). This allows
us to do our ``winding value'' trick where we start at negative infinity
and zoom out to positive infinity. What we want to do is figure out
which lines represent a change from inside to outside, and which lines
just happen to be lines and don't represent a transition. Of course,
if we use the evenodd rule, we assume that all lines represent
inside/outside boundaries. If we use the winding rule, then we
calculate use the W part of the X W list to calculate winding
values and we pop off any X values that don't represent inside/outside
boundaries.

\subsection{Building trapezoids}
Going back to TileLine, CheeseWhiz has given us two separate arrays.
One is a whole bunch of X points for the upper Y boundary, and one is
for the lower Y boundary. Since each and every X point represents an
inside/outside boundary (remember, we deleted everything else), we can
group these babies in groups of four vertices. Two vertices
intersecting the top Y boundary, and two vertices intersecting the
lower Y boundary forming a trapezoid. And as we move from right to
left, the first trapezoid gets filled, the second trapezoid doesn't
get filled, and so on, alternating. If the ``fillout'' variable has been
set, we just add on the Left Margin LM and the Right Margin RM to the
left and right of this array, and this rule still applies.

\subsection{Filling in trapezoids}
Once you have this trapezoid, you could do anything with it, but we're
going to fill it, so FillDeltaArea is called to place the vertices in
the right order and all that good stuff, and then FillTrapezoid does
the actual filling - but don't forget! It has to call the warp
algorithm to convert all four vertices to the warp space.

\subsection{The Bowtie Bug}
Remember the place where we made sure that there would be no vertices
between two vertical lines? Unfortunately this doesn't preclude lines
crossing without a vertex in kind of a ``bow tie'' effect. The example
file has a bow tie commented out. If you uncomment it, you should
notice that the neck of the tie is not a neat intersection but an ugly box.
In fact, if you increase the size of delta this box will get bigger.
The overall problem is that the intersection of these two lines is not
a vertex and is not getting noticed.

One workaround is to NOT define fancy crossover paths. Or, add
something to your path which places a vertex at a point where you know
there'll be a crossover. Alternately, just scale the delta very low
and hope for the best. I will be adding a more complex algorithm to
fix this bug which will run a little slower, such that for speed
purposes you'll normally turn it off, but if you know you'll have
complex filling requirements, you can toggle the flag that enables it.

The same bug manifests itself if a vertex is the endpoint for line
segments of different winding values. There are effectively two
vertices, but because they are located at the same point it is
difficult to order them from ``left to right'' correctly. Since this
only matters for winding values, if you find your code breaking
because of a ``rangecheck in get'' involving ``nxb'', ``nxa'', ``xb'', or
``xa'', that's probably this bug and you can workaround it by setting
the evenodd flag to true with ``/evenodd true def''.

\section{Future Plans for 3D PostScript}

Having a real 3D Path is probably the most immediate concern, but
exactly how to store the 3D Path is unclear. With a real 3D path many
new operators become possible.

The bowtie bug for WarpFill needs to be fixed, as well as a known
invertmatrix3 bug that causes it to dies on very simple matricies due
to division by zero. Fortunately, the ctm3 is general not simple.

The Linmap library needs to be upgraded to do more versatile things
with respect to imbeding user space planes within 3-space, and with
manipulating these user space planes.

There should be an operator prism3 which takes a plane (with an image)
imbedded in 3-space and moves this plane to a new 3-space location.
With the intial and the final locations of this plane, it
then does a one-to-one mapping of all vertices in the two drawings,
connecting the lines and the quadrilaterals the lines forms, so that
a new 3D solid is defined and it's lines can be stroked or can be filled in.

Obvious extensions are hidden-line routines, 3D clipping routines, and
2D clipping in a warped space.

Eventually, we would like to add shading, shadowing, translucency,
3D fonts, stereo vision, and other features to the 3D PostScript world.
Many of these algorithms are well understood in other computer
languages, but need to be applied and optomized for PostScripts
ever-present time and memory limitations.

\section{How to Help}
If you create a nifty 3D image or warp function, please send it to us
\footnote{Send them to drwho@athena.mit.edu}.  We
will be starting a library of 3D PostScript definitions. We would also
be overjoyed to hear from anyone who has successfully written a useful
general algorithm or modified our code. We would also greatly
appreciate your comments on the readability, and useability of the
code, or on its memory and speed characteristics, or on bugs may you
discover. Finally, for any other teams out there doing similar 3D
PostScript work, we would like to get in touch.

\end{document}
