NewSDDoc.tioga
Dennis Arnon, November 23, 1987 2:13:24 pm PST
CEDAR 7.0 — FOR INTERNAL XEROX USE ONLY
Surface Display Facilities
Dennis Arnon
© Copyright 1987 Xerox Corporation. All rights reserved.
Abstract: This documents both describes what is currently available, and is a design document for future stuff. What we are talking about here are the display facilities for cad's of 2- and 3-d space, and display/explanation/browsing facilities for cad's and for the qe problem-solving process. Another possible title for the scope here is: "Topologically Reliable Display of Semi-Algebraic Sets".
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
What we really are talking about is a display facility for cad's of 2- and 3-d space, and display and explanation and browsing facilities for the cad's themselves, and for solution process for qe problems. Another possible title is: "Topologically Reliable Display of Semi-Algebraic Sets".
2. Display in the plane
1. Use Gargoyle for curve display? relationship to general plotting, other Cedar plotting?
3. Implementation 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, ...
4. Semi-Algebraic Set Display
4.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.
Display is useful for using cad algorithm in solving all types of problems, not just the cases where we are trying to display a semi-algebraic set. We will show with examples why this is so.
4.2. 2-space display
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.
4.3. 2D display improvements
Use adjacencies for continuous (no big 0-cells) display of curves.
Display of open, closed 2-cells.
Eliminate use of df's in cell display?
4.4. 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).
Ray tracing
Roth [ROT82], Davis thesis [DAV82], Kajiya [KAJ82], Hanrahan beam tracing [HAN84].
4.5. 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.6. User interface considerations
Mode: Topology-priority (faster) vs. Shape-priority (slower)
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.
4.7. 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.
4. Items to be displayed.
1. 3-space intersection curves (requires tightening up Jim's 3-space 1-cell display).
2. 2-d slice showing schematic (ball and stick) diagram of interpenetration of two or more surfaces. Use symbolic colors to distinguish the different surfaces.
3. Slices by a plane of any cad of 3-space, without doing a whole new cad.
4. 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.
5. A single cell, or a set of cells (e.g. a cluster)
6. The boundary and closure of a cell.
7. The stack(s) in 2-space (3-space) over a cell or cluster in 1-space (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.)