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)$".

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.

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.

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).

Roth [ROT82], Davis thesis [DAV82], Kajiya [KAJ82], Hanrahan beam tracing [HAN84].

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.

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.

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.

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.

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).

It would be nice if the user could point, or otherwise indicate, particular cells to be deleted or added to the 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.

This was Rice's suggestion, also found in Pavlidis' book.

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]).

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.