QEDisplayDoc.tioga
Dennis Arnon, November 23, 1987 2:13:24 pm PST
CEDAR 7.0 — FOR INTERNAL XEROX USE ONLY
Cylindrical Algebraic Decomposition Display Facilities
Dennis Arnon
© Copyright 1987 Xerox Corporation. All rights reserved.
Abstract: We are talking here about display facilities for cad's of 2- and 3-d space.
Created by: James Rauen and Dennis Arnon
Maintained by: Dennis Arnon <Arnon.pa>
Keywords:
XEROX  Xerox Corporation
   Palo Alto Research Center
   3333 Coyote Hill Road
   Palo Alto, California 94304

For Internal Xerox Use Only
1. Introduction
1.1. General considerations for display
What we really are talking about is a display facility for cad's of 2- and 3-d space.
The simplest routines we have are display of individual cells, using the same conventions and data that are available for display of other AlgebraStructures or other objects (see comments in DisplayManager interface).
There are two key properties of having done a c.a.d. of an sas: (1) knowing topology exactly, and (2) having a bounding box around interesting behavior.
The field of semi-algebraic geometry is active; see [BEC86].

[BEC86]
E. B{\smallertype ECKER}, {\sl On the real spectrum of a ring and its application to semialgebraic geometry}, Bull. AMS, 15, 1 (1986) 19-60.
For "topological reliability", having adjacency information is critical. References are [ACM84b] and Prill.
2. Generalities of Displays and the User Interface
1.1. General considerations for display
We are displaying semi-algebraic sets in r-space, for r = 1, 2, 3, for which we have algebraic cell decompositions (acd's). For any such semi-algebraic set, there are particular sets of r-variate, r-1-variate, ..., 1-variate polynomials involved in its description. We assume that a cylindrical algebraic decomposition (cad) that is sign-invariant for those sets of polynomials has been computed, and that the acd we have for the semi-algebraic set to be displayed is the union of certain of the cells of the cad.
1.2. Basic things to display
1. An arbitrary semi-algebraic set, given by a df. Check that current cad is sign-invariant for it, or search db to find one that is, or (hopefully incrementally) build a sign-invariant cad.
2. A single cell, or a set of cells (e.g. a cluster)
3. The boundary and closure of a cell, or a semi-algebraic set.
1.3. Basic techniques for display
1. Fatten up a selected cell, change its color, or make it flash to show presence or absence of boundaries, to distinguish individual cells.
2. Use "improved" df's, i.e. in terms of "ith real root of" ...
1.4. User interface considerations
Mode: Topology-priority (faster) vs. Shape-priority (slower)
In general, there is a tradeoff: User selects whether he is more concerned with rapid real-time interaction in which the only constraint is to show topology accurately, or with beautiful pictures that show the true shape of objects.
Mode: Smooth vs. Structural
User selects whether to have the individual cells "glued together", in order to see smooth objects, or whether to see the individual cells. In the latter case, 0-cells are expanded into fat balls and 1-cells are fattened into "wires".
An interesting special case of this mode is displays of entire cad's. A cad is just a particular cell decomposition of the line, plane, or all space. If the user selects geometry mode, we just see some indication that the displayed set is the entire line, plane, or space. In structure mode, we see the individual cells of the cad.
A simple initial interface for surface display
The user gives a trivariate polynomial, which we interpret as a surface to be displayed, and a bounding box. A cad (for the surface and bounding box), and a triangulation of each positive dimensional cell, is done on Vaxc and written to a file, which includes a specification of which cells comprise the portion of the surface in the bounding box. The display tool reads the file.
Initially there are two kinds of display available: a topology-priority, structural mode (done by displaying the triangulations of the cells which comprise the surface), and a shape-priority, smooth mode (done by ray tracing the surface defining equation directly).
Someone (it is unspecified who) may crawl over triangulations in an effort to "topologically optimize" them, i.e. to get by with as few polygons as possible while still guaranteeing the topological correctness of any collection of cells.
At this level there are no handles on individual cells. You can only display the entire portion of the surface in the bounding box.
Next stage: ray tracing 2-cells contained in surfaces
Now cad files are required to contain some kind of defining formula for each 2-cell, the format of which has been negotiated. The requirement is that the ray tracer has to be able to use it in order to ray trace individual 2-cells.
Ideally, the ray tracer should be able to work with the "glued-together" quantifier-free formulas of a cluster of cells. Thus we should be able to have a shape-priority, structural mode for a collection of cells lying in a surface, in which we see all the different cells and 2-cells are individually ray traced, or a shape-priority, smooth mode for a subset of surface, in which we display the union of all the cells in a smooth fashion.
Now the display tool should now show the indices of all the cells currently being displayed, and allow the user to add and delete cells named by index.
Future user action: define a semi-algebraic set to display
As mentioned, in every display situation we have particular sets of polynomials, and a cad for those sets. The display tool assigns names to these polynomials, say A, B, ... The user is then able to write any valid quantifier-free formula using these names, e.g. "$A = 0~AND~B < 0$", or "$A = 0~\Rightarrow~B < 0$" The display tool determines the cells satisfying this formula (i.e. the cells comprising the semi-algebraic set defined by that formula), and displays them in the current display mode(s).
Future user action: Pointing at cells
It would be nice if the user could point, or otherwise indicate, particular cells to be deleted or added to the display.
Summary
In the future we expect to offer ray tracing or 2-cells contained in surfaces, direct rendering of a semi-algebraic set from its defining formula, and the ability of the user to point at cells. For example, in every display situation we have particular sets of polynomials, and a cad for those sets. The display tool assigns names to these polynomials, say A, B, ... The user would then be able to write any valid quantifier-free formula using these names, e.g. "$A = 0~AND~B < 0$", or "$A = 0~\Rightarrow~B < 0$" The display tool determines the cells satisfying this formula (i.e. the cells comprising the semi-algebraic set defined by that formula), and displays them in the current display mode(s).
RE: prior work on display of sas: we mention Contour plotting implicit curve display, Differential equation implicit curve display, Pitteway's algorithm for implicit curve display, and Hanrahan.
3. Displays and Display Techniques specific to Cad's of 2-space
1. Principles
Covering sets and triangulations for implicit plane curves
This was what was done in [ARN83]. The idea is simple: you assume you have a acd of the curve into 0- and 1-cells, with adjacencies known. Each 1-cell is a function graph, so you just step along the appropriate x-interval, find roots of the appropriate F(x,y) at each x, then use the rest of the defining formula to put yourself on the correct "branch" of the curve. You use adjacency information to make the correct transitions from 0- to 1-cells. May be desirable to have the cad algorithm produce 1-section defining formula's which have the form "$a < x < b ~AND~ i^{th} ~real~root~of~F(x,y)$".
Covering sets for semi-algebraic sets in the plane
The task here is - given a particular semi-algebraic set $X$ and an $\epsilon$, generate a finite set of points so that for every point $x$ in $X$, there is some point $p$ in the covering set so that the distance from $x$ to $p$ is less than $\epsilon$.\footnote{D.T. Lee (Siam Conf. Albany, July 1985) says that this is called the "sources" problem in OR. Also mentioned Shamos thesis p. 159. Seems to be some connection with the minimum covering circle problem
Easy to generalize the approach used to get covering sets for curves in the plane, by adding $y$-stepping for 2-cells.
Triangulation of semi-algebraic sets in the plane
Assuming a covering set has been constructed, we could use the general algorithms of Lloyd (1977) thesis, Shamos thesis, Tarjan et al, to triangulate. Probably would be smarter to triangulate as the covering set is generated, given that one knows the arrangement of points.
2. Techniques
1. Use Gargoyle for curve display? relationship to general plotting, other Cedar plotting?
2. Displays 1-cells by generating (piecewise linear) Imager Trajectory from DF.
3. Displays a 2-cell by walking around boundary creating a single trajectory, then MaskFills it (need a way to knit together two trajectories that are segments of this boundary). Use colors for boundary cells to indicate whether they are in the sas, e.g. to distinguish display of a closed 2-cell from that of an open 2-cell.
2. Things to display
1. The stack(s) in 2-space over a cell or cluster in 1-space. Maybe this is just a special case of semi-algebraic set display, plus a "cylinder over" operator (i.e. given that current display is in i-space, "cylinder over" operator says display the cylinder over it in i+1 space.)
4. Displays and Display Techniques specific to Cad's of 3-space
1. 2-space displays
1. 2-d slice showing schematic (ball and stick) diagram of interpenetration of two or more surfaces. Use symbolic colors to distinguish the different surfaces.
2. Slices by a plane of any cad of 3-space, without doing a whole new cad.
3. Slice of a stack in 3-space (see below).
2. Methods for 3-space display
Triangulation of surfaces in 3-space
Algorithm: Run the cad algorithm with a bounding box. Then you get a cad of the plane in which some bounded collection of 0, 1, and 2 cells constitute the projection of the surface. Construct covering set and triangulation for this semi-algebraic set. Then use the same idea used for plane curves to triangulate the 0- and 1-cells in space, by extending over the 0- and 1-cells in the plane. For each 2-cell in space, triangulate it by simply extending over its projection in the plane, and picking the appropriate root of the appropriate $F(x,y,z)$, Then using known adjacencies of 2- and 0,1-cells in space, connect up all the triangulated objects in 3-space to get the final triangulation of the (portion of the) surface (in the bounding box).
Display of 3-dimensional (solid) semi-algebraic sets in 3-space
Not clear how to do this, except by displaying the boundary surfaces of the entire set, or of individual 3-cells.
Ray tracing
Roth [ROT82], Davis thesis [DAV82], Kajiya [KAJ82], Hanrahan beam tracing [HAN84].
3. 3D display improvements
Merge in Rauen's tool (changes to ThreeDWorld format). Need to normalize forward and up vectors?
Why does Rauen have to read files? Why does he need his own internal form?
Use Jules' Geometry3DApplied interface. Offer wireframes.
Maureen's color solid viewing tools. Giordano's assertion of the three standard, plus a certain perspective view, as giving intuition.
Rauen has alg to determine what cells a ray hits? Would be a good op to offer in interface, i.e. what cells would I see if I had xray vision?
Vuillemin - draw in axes on request. Giordano's 3D interface proposal (CSL-Notebook).
How do you come up with a good triangulation? How to have a good algorithm which both may, and may not, take account of adjacency information?
Steps by which Rauen takes a triangulation and renders it.
Eliminate use of df's in cell display?
4. 3-space displays
1. 3-space intersection curves (requires tightening up Jim's 3-space 1-cell display).
2. The stack(s) in 3-space over a cell or cluster in 2-space. Maybe this is just a special case of semi-algebraic set display, plus a "cylinder over" operator (i.e. given that current display is in i-space, "cylinder over" operator says display the cylinder over it in i+1 space.)
3. A display function to support for 3-space - I fire a ray from this position; tell me (in order) all the cells I hit.
5. Implementation and improvements notes
Goal: avoid the translation step currently present, where Jim's code reads in a cad in the format that I've dumped it and translates it into his internal format.
Need a good general scheme for distinguishing when (some portion of) boundary of a displayed sas is included, and when it isn't. Use symbolic/distinct colors for boundaries. Work out iteratively, i.e. first in 1-space, then 2-space, ...
Goal is to have the display routines getting data they need out of the LoganBerry database, and saving useful things they compute in that db. Thus it should be possible to redo a covering set for a cell under control of CaminoReal, via the db. Also, there might be an op to "knit together", i.e. "merge" or "harmonize", covering sets of adjacent cells, and perhaps to compute new ones if needed. Thus, for example, if you want to display a cluster, the repeated application of this routine would result ultimately in the rendering of a "continuous" collection of polygons.
6. Prior work on display of sas
Contour plotting implicit curve display
This is perhaps one of the oldest ideas. Rice pointed to this method [SNY83]. Sederberg (letter 10/1/84) refers to [PET84]. Note the idea arising from discussions with Dobkin of getting a "wireframe" for a surface by contour tracing.
Differential equation implicit curve display
This was Rice's suggestion, also found in Pavlidis' book.
Pitteway's algorithm for implicit curve display
Pitteway's algorithm is for implicit equations; a version of it can be given for implicit equations of any degree. Knuth (Maureen says he did this in a course some time back) asked the question - would it be competitive to plot a parametric cubic curve by implicitizing it and then applying Pitteway's algorithm? Perhaps it's worth investigating how a Pitteway algorithm applied to arbitrary algebraic curves would compete with method of [ARN83] (cf. Pratt SIGGRAPH '85 [PRA85]).
Miscellaneous
Farouki [FAR85]. Geisow [GEI83]. Tiller [TIL85] use of power series to generate points on a curve. Griffiths surface display [GRI78]; note the need to distinguish the problems of displaying function graphs, parametric curves and surfaces, and implicit curves and surfaces. Soiffer surface display algorithm and the references he cites. Blinn thesis and paper on generalization of algebraic surface display.