Geometry and geometrical algorithms have traditionally been neglected in computer science. Scheme, in particular, has no primitives for manipulating 2D and 3D geometrical objects. Envision supplies a set of basic types and functions, similar to those provided for other types of applications (e.g. string manipulation). This set is not intended to be exhaustive, any more than scheme's set of list manipulation operations is exhaustive. More elaborate (and typically more parochial) types and operations can easily be defined by the individual user.

In Envision, geometrical objects play a critical role in the graphics interface: drawing is done by calling a single function (draw) on an appropriate geometrical object. Therefore, our choice of geometrical primitives has been heavily influenced what operations are provided by X windows. In particular, some object types are included primarily to provide a high-level interface to the efficient bulk drawing operations provided by X and other graphics substrates.

When applied to geometrical objects, the predicate equal? should true if the two objects have the same type and parameters. However, this applies only to "small" geometrical objects. If the objects are "large," i.e. sheets are used to represent large collections of points, then they will be considered equal only when their sheets represent the same piece of storage.

Geometrical objects are implemented using scheme vectors. However, operations such as vector-set! should not be applied to geometrical objects and we will not be responsible for the consequences of doing so.

Operations which create geometrical objects are allowed to, but are not required to, copy any input structure. In particular, sheets may be (but are not required to be) preserved in the internal representation of the geometrical object, provided that built-in operations (e.g. draw) are designed so they will never damage the contents of the sheet. Copying large sheets is usually undesirable for efficiency reasons. If this shared structure might create problems for your algorithm, copy the sheet yourself.

When numbers are used to specify parameters of geometrical objects constructed in scheme code, any type of real number can be used. So, one coordinate of a 2D point may be an inexact real and the other an exact one. When geometrical objects are passed to coprocessor functions (built-in or user-defined), these parameters are coerced to the nearest appropriate type. In particular:

- non-integer exact reals are converted to inexact reals,
- inexact integers are not distinguished from other inexact real numbers,
- floating point contagion is applied when several numbers must be the same type (e.g. the coordinates of a point).

However, if an exact integer point is required by the function, it must be given one. To coerce an arbitrarily chosen point to an exact integer point, the user should apply the function round, followed (if necessary) by inexact->exact.

A limited set of scheme arithmetic functions, notably round and inexact->exact, can be applied to 2D and 3D points.

For each type mentioned below, there is a similarly-named type-testing function, e.g. point? tests whether its input is a point.

A point is a bundle of N coordinates representing a location in N-dimensional space. In the current implementation, N may be 1, 2, or 3. 1D points are the same as numbers. Operations include

- (make-point coord1 coord2 ...) returns a point
- (point-coordinate point n) returns the nth coordinate of the point

A large set of points should be represented as a sheet with a 1D discrete domain (an integer-grid or a real-grid).

Complex geometrical objects represent shapes embedded in 2D or in higher-dimensional Euclidean space. They are created from sets of points or sets of sheets. Complex types include line segments, line segment bundles, polygons, polygon bundles, and ellipses.

When creating a complex geometrical object, the input points must all have the same dimension. The same applies to the codomains of any sheets involved. It is an error for the points and codomains to be 1D. If the points and codomains are 2D, draw will be able to do useful things with these objects. However, it is not an error for the points and codomains to have higher dimension. It is up to the individual function (built-in or user-defined) operating on a geometrical object to impose constraints on the dimension of the space that the object is embedded in.

In particular, it is likely that many non-graphical algorithms will be able to handle line segments and curves in higher dimensions. Furthermore, draw may be able to render 3D line segments and polygons, in implementations on high-end graphics workstations.

A line segment is defined by two points (of the same dimension). The two points are ordered, i.e. the line segment is oriented, though the user is free to ignore this.

- (make-line-segment point1 point2)
- (line-segment-start line-segment)
- (line-segment-end line-segment)

A connected curve should be represented as a 1D manifold. For examples, see the discussion of how draw handles these objects. Missing values are allowed in the sheet.

A line segment bundle represents a large collection of non-connected line segments. Line segment bundles probably have some applications in computer vision algorithms, but the primary reason for including them is to provide an efficient way to draw a large number of line segments (cf. the Xlib function XDrawSegments). Missing values are allowed in the sheets: the entire segment is treated as missing if either of its endpoints is missing.

In scheme, a line segment bundle looks just like a line segment (and is accepted by line-segment?). However, instead of containing two points, its representation contains two sheets.

Line segment bundles are created (accessed) using the same function as to create (access) a line segment but the inputs (outputs) are sheets rather than single points. An additional operation, bundle-slice, is used to retrieve an individual line segment from the bundle.

- (make-line-segment sheet1 sheet2)
- (line-segment-start line-bundle) returns a sheet
- (line-segment-end line-bundle)
- (bundle-slice line-bundle n) returns the nth line segment in bundle

For X graphics, the sheets should have 1D discrete domain and 2D codomain. However, it is not an error to create line segment bundles in which the domain is continuous. If the sheets have continuous 1D domain, and 3D codomain, then the bundle is a twisted strip. (If the domains are 2D, the object is still well-defined but more difficult to visualize.)

A polygon is a region defined by a circular list of points. It can be created either from an explicit list of points (e.g. if its shape is simple) or from a circular-1D-manifold (which may be preserved in the polygon's internal representation).

- (make-polygon point1 point2 ...)
- (make-polygon circular-1D-manifold)
- (polygon-length polygon)
- (polygon-vertex polygon n)

Polygons are conceptually distinct from curves: curves are 1D and polygons are 2D. It makes sense to compute the area of a polygon, but not the area of a curve. In particular, curves always display as a thin outline, whereas polygons may display as filled regions, depending on what options are given to draw. For this reason, missing values are not allowed in a manifold used to define a polygon.

Polygons included as an explicit built-in datatype primarily to provide an interface to the Xlib commands XFillPolygon, XDrawRectangle, and XFillRectangle.

A polygon bundle is a large collection of polygons. It is represented internally as a vector of three or more sheets, each of which has a 1D domain. Missing values are allowed in the sheets. However, functions such as draw will ignore a polygon entirely if any of its vertices is missing.

- (make-polygon sheet1 sheet2 sheet3 ...)
- (polygon-length polygon-bundle) returns the number of vertices in each polygon in the bundle
- (polygon-vertex polygon-bundle n) returns the sheet for that vertex.
- (bundle-slice polygon-bundle n) returns the nth polygon in bundle

Polygon bundles are required to provide an interface to the Xlib commands XDrawRectangles and XFillRectangles. They would also be used as an interface to the fast commands for drawing sets of triangles provided by high-end graphics adaptors.

For graphics, a polygon bundle should have a 1D discrete domain and a 2D codomain. However, it is not an error to create polygon bundles in which the domain is continuous: this represents a filled region whose shape is interpolated between the explicitly specified polygons. This is most useful if the coordinates of the polygon vertices are 3D: the bundle then represents (polyhedral type of) a generalized cylinder.

Ellipses are ellipses or portions of ellipses. They are conceptually 2D regions, not curves. (E.g. they can display as filled.) A circle is an ellipse whose major-length and minor-length are equal, exact numbers.

Ellipses are created using make-ellipse:

- (make-ellipse center length width start-angle angular-length orientation normal)
- (make-ellipse center length width start-angle angular-length orientation)
- (make-ellipse center length width start-angle angular-length)

The center is a point. The length and width are real numbers. The starting angle and angular length are given in degrees. Angles are specified in degrees, rather than radians, so that exact arithmetic is possible (e.g. representing the full 360 degree range precisely).

The orientation is a unit vector pointing along the major axis. The normal is a unit vector perpendicular to the plane of the ellipse. If the ellipse is a circle, the orientation will be ignored. If the ellipse lives in 2D, the normal will be ignored. In these cases, any scheme object can be supplied for the parameter: whatever you supply will be ignored. Furthermore, the normal, or the normal and orientation, can be omitted in these cases.

Accessors include:

- (ellipse-center ellipse)
- (ellipse-length ellipse)
- (ellipse-width ellipse)
- (ellipse-normal ellipse)
- (ellipse-orientation ellipse)
- (ellipse-start-angle ellipse)
- (ellipse-angular-length ellipse)

Ellipse bundles bear the same relation to ellipses as polygon bundles bear to polygons. That is, the ellipse creation and access functions can take sheets in lieu of points. The predicate ellipse? returns true on the objects containing sheets. Bundle-slice can be used to extract an individual ellipse.

An ellipse bundle with discrete 1D domain represents a set of ellipses, and displays nicely. An ellipse bundle with a continuous 2D domain represents an elliptical tube. It is not guaranteed to display nicely.

Ownership, Maintenance and Disclaimers

Last modified Monday, 22-Sep-1997 22:50:05 PDT