@device(file) @make(report) @heading(3D PostScript, Warps, Dali, and Escher) @heading(Kevin Iga and Jon Monsarrat) @chapter(Abstract) Normal 2D PostScript tranformation from the virtual page to the device page is done with a series of 3x3 matricies. Extrapolating into three dimensions, we have built an analogous library of 3D Postscript 4x4 matrix operators that allow the user to draw paths, translate, scale, rotate, and do other intuitive operations in virtual 3D space. Transformation from virtual 3D space to the virtual page is done instantly so that the user can make use of fancy postscript algorithms like "reversepath". But this means that a true 3D space path is not available for such operators as "pathforall", which would return virtual page numbers. A separate library breaks complex virtual page paths into iteratively defined one or two-dimensional regions. This can be used as a front end to mapping the virtual space to virtual 3D space, or to warping virtual space to any one-to-one corresponding map space. Some standalone uses for this path-breaking library include checkerboard tiling and filling arbitrary paths with text. A short theoretical discussion of 3D clipping, hidding, shadows, stereo vision, and other issues is also presented. @chapter(Why PostScript) As simulation becomes more important and complex, so must the simulation user interface become more useful. Rather than spelling it out in ASCII, many simulators are using graphics to demonstrate results, and sometimes this means using 3D graphics. Unfortunately, most 3D graphics packages aren't intended for an interactive simulation session. They don't have the versatility or speed of home-made programs, but 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. So although every university or business graphics department has powerful 3D techniques, 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. @chapter(Overview) This package includes this documentation file and six others: prescript.ps is a front end for PostScript that contains the 3D operators warpmap3.ps contains some standard warped spaces and a simple example of use breakpath.ps holds a library of path-chopping algorithms example.ps demonstrates checkerboarding and wrapping 2D areas into 3D space example2.ps demonstrates path-chopping to fill arbitrary paths with text example3.ps has complex examples that are best displayed on workstations. It would be a good idea to make a backup of these files if you'll be experimenting by changing things inside them. These algorithms make an extension to the PostScript language, so that normal two-dimensional PostScript coding can be made applicable to a three-dimensional world. We break up any two-dimensional PostScript path into small approximation deltas that can be smoothly converted through matrix transformation and geometry onto any complexly curved and warped surface. Limitations of PostScript include not being able to do garbage collection and lack of a 'real' subroutine argument system. And the limitations of real printers constantly hound the PostScript programmer. However, we want use existing PostScript code. So our code must either be written in PostScript or we need to write an entire PostScript interpreter in C or some other language. We've chosen to do it in PostScript for simplicity, and if it becomes popular, perhaps someone will volunteer to include it in GNU GhostScript which can "speak" PostScript both in input and output, and could serve as a PostScript preprocessor for any PostScript printer. @chapter(Prescript - a 3D preprocessor for PostScript) To start making drawings in virtual 3D space, create a new file using some text editor and include the prescript library file prescript.ps at the beginning. It has to go before any 3D path-defining code that you write. 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 virtual 2D space programs work fine. An extra set of operators will manipulate your virtual 3D 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 virtual 3D space from the (x,y,z) point (150,10,71) to (100,20,61). This virtual 3D space of course must eventually be projected into virtual 2D space, which will eventually get transformed into device space as the page prints out or image is drawn on the screen. And just like you can translate and scale the way virtual 2D space fits on the device page, you can translate3 and scale3 virtual 3D space to fit in your virtual 2D 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 into 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. @section(Path Construction Operators) - newpath3 - Clears the 3D path. - currentpoint3 x y z Leaves x y z on the stack representing the current (x,y,z) point x y z moveto3 - Starts a subpath by moving the current point to (x,y,z) dx dy dz rmoveto3 - Starts a subpath by relatively moving the current point from (x,y,z) to (x+dx,y+dy,z+dz) x y z lineto3 - Appends a line to the current path from the current point to (x,y,z) and makes the current point this new point. dx dy dz rlineto3 - Appends a line to the current path from the current point (x,y,z) to (x+dx, y+dy, z+dz) and makes the current point this new point. - closepath3 - Appends a line from the current point to the original point of the subpath (the point last set by a moveto3 OR moveto) and makes the current point that point. - reversepath3 - Reverses the current path. Same as reversepath. 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 - Creates a path around the outline of the line that would be drawn were the current path to be stroked. @section(Path Construction Operators With No Analogy) Because there is no real 3D space path (any 3D point is converted into 2D 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 3D space, you should define them in 2D space normally and then use the warppath library to stick the 2D drawing in 3D space (in an arbitrary fashion and shape). More on the warppath library later. Also there is no 3D arc, arcn, arcto, curveto, or rcurveto. Essentially we would be forced to break these up 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 warppath library section later. So because there are no curves in 3D space, flattenpath3 has been defined as null. @section(Matrix Operators) Matrix operators are a complex and versatile way of manipulating virtual 3D space. Read the red book to learn more about matricies in the virtual 2D world. - matrix3 matrix leaves blank 4x4 identity matrix on stack - initmatrix3 - sets the CTM3 to the identity matrix matrix identmatrix3 matrix sets the given matrix equal to the identity matrix, and returns it. matrix defaultmatrix3 matrix same as identmatrix3 matrix currentmatrix3 matrix sets the given matrix equal to CTM3, returns it matrix setmatrix3 - sets the CTM3 to given matrix tx ty tz translate3 - translates the 3D user space by tx ty tz NOTE: does not do the analogous "tx ty tz matrix translate3 matrix" sx sy sz scale3 - scales the 3D user space by sx sy szn NOTE: does not do the analogous "sx sy sz matrix scale3 matrix" angle rotate3 defaults to rotatez3 angle rotatez3 rotates around the Z axis. Right hand rule applies. angle rotatey3 rotates around the Y axis. Right hand rule applies. angle rotatex3 rotates around the X axis. Right hand rule applies. matrix concat3 - takes a matrix and concatenates it with CTM3, replacing CTM3 matrix1 matrix2 matrix3 concatmatrix3 matrix3 multiplies matrix1 times matrix2, leaving the result in matrix3 x y transform3 x' y' x y matrix transform3 x' y' transforms 3D user-point to 3D draw-space based on CTM3 or based on some other matrix if given dx dy dtransform3 dx' dy' dx dy matrix dtransform3 dx' dy' transforms 3D user delta to 3D draw-space based on CTM3 or based on some other matrix if given. x' y' itransform3 x y x' y' matrix itransform3 x y transforms x' y' back into the original space using the inverse of the CTM3 or the inverse of some given matrix. dx' dy' idtransform3 dx dy dx' dy' matrix idtransform3 dx' dy' transforms dx' dy' delta back into the original space using the inverse of the CTM3 or the inverse of some given matrix. matrix1 matrix2 invertmatrix3 matrix2 inverts matrix1, placing the result in matrix2 @section(Other Operators) - stroke3 - strokes the projection of the current path x y z project3d x' y' takes (x,y,z) a 3D point giving the (x,y) 2D projection to screen - enterthreed - uses 3D dictionary, does VM save - exitthreed - restores VM Some of the operators don't really do anything. For example, "stroke3" is just defined to be "stroke". This is because as the 3D 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 3D space. @chapter(Prescript - How it Works) @chapter(Warppath) Warppath is a back end for WarpStroke and WarpFill, and a front end for Prescript. @chapter(How Warppath works) @chapter(Using WarpFill and WarpStroke) WarpFill and WarpStroke are back ends for 3D PostScript, but they can be used on their own. The purpose of the algorithms is to translate normal PostScript space into any other space based on a simple one-to-one mapping (x,y) -> (x',y'). @section(warp) The basic function for this mapping is called "warp", which the user must define. warp takes two numbers x y from the stack and leaves two numbers x' y' on the stack. We provide you with a number of sample warp functions to experiment with, which are all based on doing something interesting inside an 8 inch square centered on the origin, although they handle any points out to infinity. Wrap around a sphere (to the center) Wrap around a sphere (to the top) Wrap around a cylinder Project onto a plane @section(User-definable Variables for Filling) The PostScript Red Book has a good explanation of filling in Chapter 4.6: Painting, and Warp Painting should work the same way. When filling a complex image, it is necessary to tell where the inside of the image is and where the outside is. The general technique to telling whether a point A is inside or outside is tostart outside the shape (at infinity) and close into the point A arbitrarily, stopping at every place we cross the path. Depending on whether the path is going counterclockwise or clockwise we either add or subtract to our "winding number", which is zero at infinity and it turns out that the winding number is zero wherever we are outside the image. The other way of calculating "inside" is again to start at infinity and close into the point A, assuming that every time we cross the path we change from inside to outside or vice versa. This latter method is called the evenodd 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 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" is a good default. Use the fillout boolean 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 a good 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. To actually stroke or fill in warped space, first define the path using normal PostScript operators (don't use translate, rotate, or clip until we figure out how to handle them). Then use WarpStroke in place of stroke and WarpFill in place of fill. @section(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. @chapter(How WarpFill works) @section(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 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. @section(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. @section(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 two 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. A good enhancement for the WarpFill routine would be to add a little intelligence so that if it is warping in just two dimensions, it knows the limitations of the device it's using and combines tiles into large but not too large regions, instead of drawing each tile individually. @section(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. @section(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. @section(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 an array [ 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. @section(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 ] array to calculate winding values and we pop off any X values that don't represent inside/outside boundaries. @section(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. @section(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. @section(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". @chapter(Plans for 3D PostScript) @chapter(Implementation Ideas for 3D PostScript) @chapter(How to do 3D Hiding) @chapter(How to do 3D Clipping) @chapter(Shadows, Reflection, and Translucency) @chapter(Stereo Vision) @chapter(How to Help)