[_CDCSL_93-16_]<1>Cedar>release>G3dBasic>G3dPolygon.mesa

Callback Procs

PolygonProc: TYPE ~ PROC [nPolygon: NAT, polygon: NatSequence]

RETURNS [continue: BOOL ¬ TRUE];

nPolygon is polygon id; polygon is sequence of vertex indices.

Triangles and Polygons

Triangle: TYPE ~ REF TriangleRep;

TriangleRep: TYPE ~ RECORD [

p0, p1, p2: Triple ¬ [], -- triangle vertices

a0, a1, a2: Quad ¬ [], -- nearness accelerators

l0, l1, l2: Triple ¬ [], -- planar line equations

plane: Plane ¬ [], -- plane of triangle

majorPlane: MajorPlane ¬ xy, -- major plane of triangle

refAny: REF ANY ¬ NIL -- for client use

];

Polygon: TYPE ~ REF PolygonRep;

PolygonRep: TYPE ~ RECORD [

points: TripleSequence ¬ NIL, -- sequence of points

indices: NatSequence ¬ NIL, -- to points, if nil use points only

normal: Triple ¬ [], -- polygon normal

plane: Plane ¬ [], -- plane of polygon

majorPlane: MajorPlane ¬ unknown, -- major plane of polygon

center: Triple ¬ [], -- center of polygon

area: REAL ¬ 0.0, -- area of polygon

fwdFacing: BOOL ¬ FALSE, -- true if facing towards eyepoint

accs: QuadSequence ¬ NIL, -- nearness accelerators

lines: TripleSequence ¬ NIL, -- planar line equations

neighbors: PolygonSequence ¬ NIL, -- neighbor across edge

convex: BOOL ¬ TRUE, -- if polygon is convex

refAny: REF ANY ¬ NIL -- for client use

];

In general, the edge attributes (accs, lines, neighbors) are indexed such that

polygon.attribute[n] is relative to the edge between vertices [n] and [n+1].

Nearness

NearTriangle: TYPE ~ RECORD [

point: Triple ¬ [], -- point on triangle

inside: BOOL ¬ FALSE, -- true iff point inside triangle

w0, w1, w2: REAL ¬ 0.0 -- point = w0*p0+w1*p1+w2*p2

];

NearPolygon: TYPE ~ RECORD [

point: Triple ¬ [], -- point on polygon

inside: BOOL ¬ FALSE, -- true iff point is inside polygon

distance: REAL ¬ 0.0 -- distance to point on polygon

];

Sequences

TriangleSequence: TYPE ~ REF TriangleSequenceRep;

TriangleSequenceRep: TYPE ~ RECORD [

length: CARDINAL ¬ 0,

element: SEQUENCE maxLength: CARDINAL OF Triangle

];

PolygonSequence: TYPE ~ REF PolygonSequenceRep;

PolygonSequenceRep: TYPE ~ RECORD [

forwardFacingValid: BOOL ¬ FALSE,

normalsValid: BOOL ¬ FALSE,

centersValid: BOOL ¬ FALSE,

areasValid: BOOL ¬ FALSE,

length: CARDINAL ¬ 0,

element: SEQUENCE maxLength: CARDINAL OF Polygon

];

Nat3Sequence: TYPE ~ REF Nat3SequenceRep;

Nat3SequenceRep: TYPE ~ RECORD [

length: CARDINAL ¬ 0,

element: SEQUENCE maxLength: CARDINAL OF Nat3

];

Imported Types

Border: TYPE ~ G2dBasic.Border;

Nat3: TYPE ~ G2dBasic.Nat3;

NatSequence: TYPE ~ G3dBasic.NatSequence;

SurfaceSequence: TYPE ~ G3dBasic.SurfaceSequence;

Quad: TYPE ~ G3dBasic.Quad;

QuadSequence: TYPE ~ G3dBasic.QuadSequence;

RealSequence: TYPE ~ G3dBasic.RealSequence;

Segment: TYPE ~ G3dBasic.Segment;

Triple: TYPE ~ G3dBasic.Triple;

TripleSequence: TYPE ~ G3dBasic.TripleSequence;

Matrix: TYPE ~ G3dMatrix.Matrix;

Plane: TYPE ~ G3dPlane.Plane;

MajorPlane: TYPE ~ G3dPlane.MajorPlane;

Attributes

SetTriangle: PROC [triangle: Triangle, accs, lines: BOOL ¬ FALSE];

Set various fields in the triangle record, depending on which of the following are true:

accs: compute triangle.a0, a1, a2, the accelerators for nearness testing

lines: compute triangle.l0, l1, l2, the 2d line equations for edges in the majorPlane

triangle.plane and triangle.majorPlane are always set.

SetPolygon: PROC [

polygon: Polygon,

vertices: TripleSequence ¬ NIL,

normal, center, area, accs, lines: BOOL ¬ FALSE];

If polygon.points is NIL, set them.

Set various fields in the polygon record, depending on which of the following are true:

normal: compute polygon.normal, the polygon's normal

center: compute polygon.center, the polygon's center

area: compute polygon.area, the polygon's area

accs: compute polygon.accs, the accelerators for nearness testing

lines: compute polygon.lines, the 2d line equations for edges in the majorPlane

IF NOT points, then use polygon.indices to index vertices, otherwise, use polygon.points.

polygon.plane and polygon.majorPlane are always set.

SetPolygonNeighbors: PROC [polygons: PolygonSequence];

Set polygon.neighbors for each polygon.

Miscellaneous Procedures

IsConvex: PROC [polygon: Polygon] RETURNS [BOOL];

Return TRUE iff the polygon is convex.

NPoints: PROC [points: TripleSequence, polygon: NatSequence ¬ NIL] RETURNS [NAT];

Return the number of points in the polygon. If polygon = NIL, return points.length.

PolygonFlatness: PROC [

points: TripleSequence,

polygon: NatSequence ¬ NIL,

polygonPlane: Plane ¬ []]

RETURNS [REAL];

Return the maximum angular deviation, in degrees, of an edge from the polygon plane;

if polygon # NIL, use it to index points; compute polygonPlane if null.

PolygonReverse: PROC [poly: NatSequence] RETURNS [NatSequence];

Reverse the order of the point indices.

Inside Procedures

InsidePolygon: PROC [q: Triple, polygon: Polygon] RETURNS [Border];

Determine whether q is within the closed polygon boundary.

polygon.majorPlane and polygon.points are presumed set.

InsidePolygonXY: PROC [q: Triple, points: TripleSequence, indices: NatSequence ¬ NIL]

RETURNS [Border];

Determine q containment in points as projected to xy plane, index if indices # NIL.

InsidePolygonXZ: PROC [q: Triple, points: TripleSequence, indices: NatSequence ¬ NIL]

RETURNS [Border];

Determine q containment in points as projected to xz plane, index if indices # NIL.

InsidePolygonYZ: PROC [q: Triple, points: TripleSequence, indices: NatSequence ¬ NIL]

RETURNS [Border];

Determine q containment in points as projected to yz plane, index if indices # NIL.

Area Procedures

TriangleArea: PROC [p0, p1, p2: Triple] RETURNS [REAL];

Return the area of the triangle.

PolygonArea: PROC [

points: TripleSequence,

polygon: NatSequence ¬ NIL,

polygonPlane: Plane ¬ []]

RETURNS [REAL];

Return the area of the polygon; compute polygonPlane if null.

If polygon # NIL, use it to index points.

PolygonAreas: PROC [

points: TripleSequence,

polygons: SurfaceSequence,

areas: RealSequence ¬ NIL]

RETURNS [RealSequence];

Return the areas of the input polygons, using areas if non-NIL.

Angle Procedures

PolygonAngles: PROC [

points: TripleSequence,

polygon: NatSequence ¬ NIL,

angles: RealSequence ¬ NIL]

RETURNS [RealSequence];

Return a sequence of angles (in radians), using angles if # NIL.

If polygon # NIL, use to index points.

TriangleAngles: PROC [p0, p1, p2: Triple] RETURNS [Triple];

Return angles a, b, and c as a triple.

Center Procedures

TriangleCenter: PROC [p0, p1, p2: Triple] RETURNS [Triple];

Return the center of the triangle = (p0+p1+p3)/3.

PolygonCenter: PROC [

points: TripleSequence,

polygon: NatSequence ¬ NIL,

solid: BOOL ¬ TRUE]

RETURNS [Triple];

If solid, return the point about which a solid, convex polygon would balance; otherwise,

return the point about which a wireframe polygon would balance.

If polygon # NIL, use it to index points.

PolygonCenters: PROC [

points: TripleSequence,

polygons: SurfaceSequence,

solid: BOOL ¬ TRUE,

centers: TripleSequence ¬ NIL]

RETURNS [TripleSequence];

Return the centers of the polygons, using centers if non-NIL. Use polygons to index points.

Normal Procedures

TriangleNormal: PROC [p0, p1, p2: Triple, unitize: BOOL ¬ FALSE] RETURNS [Triple];

Return the unit-length normal for three vertices, p0, p1, and p2.

The normal will face the viewer if the vertices appear in clockwise order.

PolygonNormal: PROC [

points: TripleSequence,

polygon: NatSequence ¬ NIL,

normalize: BOOL ¬ FALSE]

RETURNS [Triple];

Return the normal for these vertices using Newell's technique (A Characterization of Ten

Hidden-Surface Algorithms, ACM Computing Surveys, March, 1974) to minimize non-

planarity distortion. The normal will face the viewer if the vertices appear in clockwise

order. The normal's length is proportional to the area of the polygon unless normalize,

in which case it is unit length. If non-NIL, use polygon to index the points.

PolygonNormals: PROC [

points: TripleSequence,

polygons: SurfaceSequence,

normals: TripleSequence ¬ NIL,

unitize: BOOL ¬ FALSE]

RETURNS [TripleSequence];

Return a sequence of polygon normals (one per polygon); store in normals if non-nil.

Normalize the normals to unit length iff normalize. Use polygons to index points.

Nearness Procedures

NearestToTriangle: PROC [triangle: Triangle, q: Triple] RETURNS [NearTriangle];

NearTriangle.inside TRUE iff the projection of q onto triangles's plane is within the triangles.

If NearTriangle.inside then NearTriangle.point is the projection q;

otherwise NearTriangle.point is a point on a triangle edge nearest to q.

NearTriangle.w0, w1, and w2 are the weights applied to p0, p1, and p2

to obtain NearTriangle.point; w0+w1+w2 = 1.

Presumes triangle.l0, l1, l2 are set.

NearestToPolygon: PROC [polygon: Polygon, q: Triple] RETURNS [NearPolygon];

NearPolygon.inside TRUE iff the projection of q onto polygon's plane is within the polygon.

If NearPolygon.inside then NearPolygon.point is the projection q;

otherwise NearPolygon.point is a point on a polygon edge nearest to q.

NearPolygon.distance is the distance from q to NearPolygon.point.

Presumes triangle.a0, a1, a2 are set.

NearestTriangleEdge: PROC [triangle: Triangle, q: Triple] RETURNS [Segment];

Return the triangle edge nearest to q.

NearestPolygonEdge: PROC [polygon: Polygon, q: Triple] RETURNS [Segment];

Return the polygon edge nearest to q.

Callback Procedures

ApplyToPolygons: PROC [polygonProc: PolygonProc, polygons: SurfaceSequence];

Apply polygonProc to each of the polygons.

ApplyToFrontFacingPolygons: PROC [

polygonProc: PolygonProc,

polygons: SurfaceSequence,

view: Matrix,

faceCenters: TripleSequence,

normals: TripleSequence];

Apply the polygonProc to all front-facing polygons.

Triangle Procedures

Triangulate2Polygons: PROC [polygon0, polygon1: NatSequence, points: TripleSequence]

RETURNS [Nat3Sequence];

Triangulate between two presumably planar polygons; the technique is similar to that of

Christiansen and Sederberg (Conversion of Complex Contour Line Definitions into Polygonal

Element Mosaics, Siggraph, 1978) in which each polygon is mapped to a unit square to

facilitate the vertex matching.

Sequence Operations

CopyPolygonSequence: PROC [polygons: PolygonSequence] RETURNS [PolygonSequence];

Return a copy of the input sequence of polygons.

AddToPolygonSequence: PROC [polygons: PolygonSequence, polygon: Polygon]

RETURNS [PolygonSequence];

Add polygon to the sequence.

LengthenPolygonSequence: PROC [polygons: PolygonSequence, amount: REAL ¬ 1.3]

RETURNS [PolygonSequence];

Return a copy of the input sequence whose maxLength is amount*input.maxLength.

CopyTriangleSequence: PROC [triangles: TriangleSequence] RETURNS [TriangleSequence];

Return a copy of the input sequence of triangles.

AddToTriangleSequence: PROC [triangles: TriangleSequence, triangle: Triangle]

RETURNS [TriangleSequence];

Add triangle to the sequence.

LengthenTriangleSequence: PROC [triangles: TriangleSequence, amount: REAL ¬ 1.3]

RETURNS [TriangleSequence];

Return a copy of the input sequence whose maxLength is amount*input.maxLength.