
DIRECTORY G2dBasic, G3dBasic, G3dMatrix, G3dPlane;

G3dPolygon: CEDAR DEFINITIONS
~ BEGIN
PolygonProc:				TYPE ~ PROC [nPolygon: NAT, polygon: NatSequence]
									RETURNS [continue: BOOL м TRUE];
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
];
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
];
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
];
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;
SetTriangle: PROC [triangle: Triangle, accs, lines: BOOL м FALSE];
SetPolygon: PROC [
polygon: Polygon,
vertices: TripleSequence м NIL,
normal, center, area, accs, lines: BOOL м FALSE];
SetPolygonNeighbors: PROC [polygons: PolygonSequence];
IsConvex: PROC [polygon: Polygon] RETURNS [BOOL];
NPoints: PROC [points: TripleSequence, polygon: NatSequence м NIL] RETURNS [NAT];

PolygonFlatness: PROC [
points: TripleSequence,
polygon: NatSequence м NIL,
polygonPlane: Plane м []]
RETURNS [REAL];
PolygonReverse: PROC [poly: NatSequence] RETURNS [NatSequence];
InsidePolygon: PROC [q: Triple, polygon: Polygon] RETURNS [Border];
InsidePolygonXY: PROC [q: Triple, points: TripleSequence, indices: NatSequence м NIL]
RETURNS [Border];
InsidePolygonXZ: PROC [q: Triple, points: TripleSequence, indices: NatSequence м NIL]
RETURNS [Border];
InsidePolygonYZ: PROC [q: Triple, points: TripleSequence, indices: NatSequence м NIL]
RETURNS [Border];
TriangleArea: PROC [p0, p1, p2: Triple] RETURNS [REAL];
PolygonArea: PROC [
points: TripleSequence,
polygon: NatSequence м NIL,
polygonPlane: Plane м []]
RETURNS [REAL];

PolygonAreas: PROC [
points: TripleSequence,
polygons: SurfaceSequence,
areas: RealSequence м NIL]
RETURNS [RealSequence];
PolygonAngles: PROC [
points: TripleSequence,
polygon: NatSequence м NIL,
angles: RealSequence м NIL]
RETURNS [RealSequence];
TriangleAngles: PROC [p0, p1, p2: Triple] RETURNS [Triple];
TriangleCenter: PROC [p0, p1, p2: Triple] RETURNS [Triple];

PolygonCenter: PROC [
points: TripleSequence,
polygon: NatSequence м NIL,
solid: BOOL м TRUE]
RETURNS [Triple];

PolygonCenters: PROC [
points: TripleSequence,
polygons: SurfaceSequence,
solid: BOOL м TRUE,
centers: TripleSequence м NIL]
RETURNS [TripleSequence];
TriangleNormal: PROC [p0, p1, p2: Triple, unitize: BOOL м FALSE] RETURNS [Triple];
PolygonNormal: PROC [
points: TripleSequence,
polygon: NatSequence м NIL,
normalize: BOOL м FALSE]
RETURNS [Triple];
PolygonNormals: PROC [
points: TripleSequence,
polygons: SurfaceSequence,
normals: TripleSequence м NIL,
unitize: BOOL м FALSE]
RETURNS [TripleSequence];
NearestToTriangle: PROC [triangle: Triangle, q: Triple] RETURNS [NearTriangle];
NearestToPolygon: PROC [polygon: Polygon, q: Triple] RETURNS [NearPolygon];
NearestTriangleEdge: PROC [triangle: Triangle, q: Triple] RETURNS [Segment];
NearestPolygonEdge: PROC [polygon: Polygon, q: Triple] RETURNS [Segment];
ApplyToPolygons: PROC [polygonProc: PolygonProc, polygons: SurfaceSequence];
ApplyToFrontFacingPolygons: PROC [
polygonProc: PolygonProc,
polygons: SurfaceSequence,
view: Matrix,
faceCenters: TripleSequence,
normals: TripleSequence];
Triangulate2Polygons: PROC [polygon0, polygon1: NatSequence, points: TripleSequence]
RETURNS [Nat3Sequence];
CopyPolygonSequence: PROC [polygons: PolygonSequence] RETURNS [PolygonSequence];
AddToPolygonSequence: PROC [polygons: PolygonSequence, polygon: Polygon]
RETURNS [PolygonSequence];
LengthenPolygonSequence: PROC [polygons: PolygonSequence, amount: REAL м 1.3]
RETURNS [PolygonSequence];
CopyTriangleSequence: PROC [triangles: TriangleSequence] RETURNS [TriangleSequence];
AddToTriangleSequence: PROC [triangles: TriangleSequence, triangle: Triangle]
RETURNS [TriangleSequence];
LengthenTriangleSequence: PROC [triangles: TriangleSequence, amount: REAL м 1.3]
RETURNS [TriangleSequence];

END.


   r  
G3dPolygon.mesa
Copyright ╙ 1985, 1992 by Xerox Corporation.  All rights reserved.
Bloomenthal, September 27, 1992 2:56 pm PDT
Glassner, July 5, 1989 6:47:14 pm PDT
Callback Procs
									nPolygon is polygon id; polygon is sequence of vertex indices.
Triangles and Polygons
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
Sequences
Imported Types
Attributes
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.

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.

Set polygon.neighbors for each polygon.
Miscellaneous Procedures
Return TRUE iff the polygon is convex.

Return the number of points in the polygon.  If polygon = NIL, return points.length.
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.

Reverse the order of the point indices.
Inside Procedures
Determine whether q is within the closed polygon boundary. 
polygon.majorPlane and polygon.points are presumed set. 

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

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

Determine q containment in points as projected to yz plane, index if indices # NIL.
Area Procedures
Return the area of the triangle.

Return the area of the polygon; compute polygonPlane if null.
If polygon # NIL, use it to index points.
Return the areas of the input polygons, using areas if non-NIL.
Angle Procedures
Return a sequence of angles (in radians), using angles if # NIL.
If polygon # NIL, use to index points.

Return angles a, b, and c as a triple.
Center Procedures
Return the center of the triangle = (p0+p1+p3)/3.
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.
Return the centers of the polygons, using centers if non-NIL.  Use polygons to index points.
Normal Procedures
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.
 
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.
 
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
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.

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.

Return the triangle edge nearest to q.

Return the polygon edge nearest to q.
Callback Procedures
Apply polygonProc to each of the polygons.

Apply the polygonProc to all front-facing polygons.
Triangle Procedures
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
Return a copy of the input sequence of polygons.

Add polygon to the sequence.

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

Return a copy of the input sequence of triangles.

Add triangle to the sequence.

Return a copy of the input sequence whose maxLength is amount*input.maxLength.
Э╩
H  ХNewlineDelimiter
Ц"cedarcode" styleЩ ЩJЪЬ	╧eЬ6ЩBJЩ+JЩ%JШ JЪ╧k	Ь)Ш2JШ ЧЪ╨bl
ЬЮЬЮШJЪЬЮШЧheadЪ╧lЩЪЬЮЬЮЬЮЬШAJЪЬ	ЮЬЮЬЮЬШ)JЩGЧЧЪаЩJЪЬЮЬЮЬШ%ЪЬЮЬЮЬШJЪЬ"╧cШ6JЪЬ бШ8JЪЬ#бШ;JЪЬбШ2JЪЬ%бШ?JЪЬЮЬЮЬЮЬбШ0JШJШ ЧJЪЬЮЬЮЬШ#ЪЬЮЬЮЬШJЪЬЮЬбШ:JЪЬЮЬб$ШHJЪЬбШ0JЪЬбШ1JЪЬ(бШAJЪЬбШ3JЪЬЮЬбШ/JЪЬЮЬЮЬб"ШCJЪЬЮЬбШ:JЪЬ ЮЬбШ>JЪЬ"ЮЬбШ>JЪЬЮЬЮЬбШ5JЪЬЮЬЮЬЮЬбШ0JШJЩNJЩMЧЧЪаЩЪЬЮЬЮЬШJЪЬбШ2JЪЬЮЬЮЬб!Ш?JЪЬЮЬ
бШ;JШJШ ЧЪЬЮЬЮЬШJЪЬбШ1JЪЬЮЬЮЬб#ШAJЪЬЮЬ
бШ=JШЧЧЪа	Щ	JЪЬЮЬЮЬШ2ЪЬЮЬЮЬШ$JЪЬЮЬШJЪЬЮЬЮЬЮЬ	Ш7JШJШ ЧJЪЬЮЬЮЬШ0ЪЬЮЬЮЬШ#JЪЬЮЬЮЬШ#JЪЬЮЬЮЬШJЪЬЮЬЮЬШ JЪЬЮЬЮЬШJЪЬЮЬШJЪЬЮЬЮЬЮЬШ6JШJШ ЧJЪЬЮЬЮЬШ+ЪЬЮЬЮЬШ!JЪЬЮЬШJЪЬЮЬЮЬЮЬШ3JШЧЧЪаЩJЪЬЮЬШ#JЪЬЮ	ЬШ JЪЬЮЬШ,JЪЬЮЬШ2JЪЬЮ	ЬШ JЪЬЮЬШ-JЪЬЮЬШ-JЪЬ	ЮЬШ%JЪЬЮЬШ#JЪЬЮЬШ1JЪЬЮ	ЬШ$JЪЬЮ
ЬШ"JЪЬЮЬШ*ЧЪа
Щ
Ъ╧nЬЮЬ#ЮЬЮЬШBЪЬXЩXJЪЬJЩJJЪЬWЩWЧJЪЬ6Щ6JЩ ЧЪв
ЬЮЬШJШJЪЬЮЬШJЪЬ#ЮЬЮЬШ1JЪЬ╧sЬЩ#ЩWJЩ5JЩ5JЩ0JЩCJЩQЧJЪгЬгЬRЩYJЩ4JЩ ЧЪвЬЮЬШ6JЩ'ЧЧЪаЩЪвЬЮЬЮЬЮЬШ1JЪЬгЬЩ&JЩ ЧЪвЬЮЬ1ЮЬЮЬЮЬЮШQJЪЬ:гЬЩTJШ ЧЪвЬЮЬШJЪЬШJЪЬЮЬШJШJЪЮЬЮЬШJЩTJЪЬгЬ7ЩGJЩ ЧЪвЬЮЬЮЬШ?JЩ'ЧЧЪаЩЪвЬЮЬЮЬ
ШCJЩ;JЩ8JЩ ЧЪвЬЮЬ<ЮЬШUJЪЮЬ
ШJЪЬOгЬЩSJЩ ЧЪвЬЮЬ<ЮЬШUJЪЮЬ
ШJЪЬOгЬЩSJЩ ЧЪвЬЮЬ<ЮЬШUJЪЮЬ
ШJЪЬOгЬЩSЧЧЪаЩЪвЬЮЬЮЬЮЬШ7JЩ JЩ ЧЪвЬЮЬШJШJЪЬЮЬШJШJЪЮЬЮЬШJЩ=JЪЬгЬЩ)JШ ЧЪвЬЮЬШJЪЬШJЪЬШJЪЬЮЬШJЪЮЬШJЪЬ;гЬЩ?ЧЧЪаЩЪвЬЮЬШJШJЪЬЮЬШJЪЬЮЬШJЪЮЬШJЪЬ<гЬЩ@JЪЬгЬЩ&JЩ ЧЪвЬЮЬЮЬ
Ш;JЩ&ЧЧЪаЩЪвЬЮЬЮЬ
Ш;JЩ1JШ ЧЪвЬЮЬШJШJЪЬЮЬШJЪЬЮЬЮЬШJЪЮЬ
ШJЩXJЩ?JЪЬгЬЩ)JШ ЧЪвЬЮЬШJШJШJЪЬЮЬЮЬШJЪЬЮЬШJЪЮЬШJЪЬ9гЬ Щ\ЧЧЪаЩЪ
вЬЮЬЮЬЮЬЮЬ
ШRJЩAJЩJJЩЧЪвЬЮЬШJШJЪЬЮЬШJЪЬЮЬЮЬШJЪЮЬ
ШJЪЬ?╧zЩXJЪдЬ6ЩOJЩZJЩXJЪЬ)гЬ"ЩNJЩЧЪвЬЮЬШJШJШJЪЬЮЬШJЪЬ	ЮЬЮЬШJЪЮЬШJЩTJЩRЧЧЪаЩЪвЬЮЬ ЮЬШOJЪЬгЬHЩ`JЩCJЩHJЩEJЩ+JЩ%JЩ ЧЪвЬЮЬЮЬШKJЪЬгЬDЩ[JЩAJЩFJЩAJЩ%JЩ ЧЪвЬЮЬ ЮЬШLJЩ&JЩ ЧЪвЬЮЬЮЬШIJЩ%ЧЧЪаЩЪвЬЮЬ7ШLJЩ*JЩ ЧЪвЬЮЬШ"JШJШJШJШJШJЩ3ЧЧЪаЩЪвЬЮЬ:ШTJЪЮЬШJЩWJЪЬд=ЩYJЪдЬEЩTJЩЧЧЪаЩЪвЬЮЬЮЬШPЩ0JЩ ЧЧЪвЬЮЬ.ШHJЪЮЬШЩJЩ ЧЧЪвЬЮЬ%ЮЬШMJЪЮЬШJЩNJЩ ЧЪвЬЮЬЮЬШTЩ1JЩ ЧЧЪвЬЮЬ2ШMJЪЮЬШЩJЩ ЧЧЪвЬЮЬ'ЮЬШPJЪЮЬШJЩNЧЧJШ JЪЮЬШJШ JШ Ч ЕЧ    ▐  7Ш  