[_CDCSL_93-16_]<1>Cedar>release>G3dModel>G3dModelImpl.mesa

G3dModelImpl.mesa

Bloomenthal, October 21, 1992 5:51 pm PDT

Heckbert, June 22, 1988 4:54:42 pm PDT

Glassner, March 2, 1990 9:41:41 am PST

Shoemake, November 20, 1989 8:29:31 pm PST

DIRECTORY Draw2d, G2dBasic, G2dVector, G3dBasic, G3dDraw, G3dMatrix, G3dModel, G3dPlane, G3dPolygon, G3dShape, G3dSpline, G3dVector, Imager, Real, RefTab, Rope, RuntimeError;

G3dModelImpl: CEDAR MONITOR

IMPORTS G2dBasic, G2dVector, G3dBasic, G3dDraw, G3dMatrix, G3dPlane, G3dPolygon, G3dShape, G3dSpline, G3dVector, RefTab, RuntimeError

EXPORTS G3dModel

~ BEGIN

Types and Constants

DrawType: TYPE ~ Draw2d.DrawType;

Border: TYPE ~ G3dBasic.Border;

Box: TYPE ~ G3dBasic.Box;

Pair: TYPE ~ G3dBasic.Pair;

Triple: TYPE ~ G3dBasic.Triple;

Plane: TYPE ~ G3dPlane.Plane;

Ray: TYPE ~ G3dBasic.Ray;

Segment: TYPE ~ G3dBasic.Segment;

NatSequence: TYPE ~ G3dBasic.NatSequence;

NatSequenceRep: TYPE ~ G3dBasic.NatSequenceRep;

IntegerPair: TYPE ~ G3dBasic.IntegerPair;

IntSequence: TYPE ~ G3dBasic.IntSequence;

IntSequenceRep: TYPE ~ G3dBasic.IntSequenceRep;

SurfaceSequence: TYPE ~ G3dBasic.SurfaceSequence;

SurfaceSequenceRep: TYPE ~ G3dBasic.SurfaceSequenceRep;

PairSequence: TYPE ~ G3dBasic.PairSequence;

PairSequenceRep: TYPE ~ G3dBasic.PairSequenceRep;

TripleSequence: TYPE ~ G3dBasic.TripleSequence;

TripleSequenceRep: TYPE ~ G3dBasic.TripleSequenceRep;

Matrix: TYPE ~ G3dMatrix.Matrix;

Viewport: TYPE ~ G3dMatrix.Viewport;

Model: TYPE ~ G3dModel.Model;

ModelRep: TYPE ~ G3dModel.ModelRep;

NearModel: TYPE ~ G3dModel.NearModel;

Polygon: TYPE ~ G3dPolygon.Polygon;

PolygonSequenceRep: TYPE ~ G3dPolygon.PolygonSequenceRep;

Edge: TYPE ~ G3dShape.Edge;

EdgeRep: TYPE ~ G3dShape.EdgeRep;

EdgeSequence: TYPE ~ G3dShape.EdgeSequence;

Face: TYPE ~ G3dShape.Face;

FaceRep: TYPE ~ G3dShape.FaceRep;

FaceSequence: TYPE ~ G3dShape.FaceSequence;

FaceSequenceRep: TYPE ~ G3dShape.FaceSequenceRep;

ScreenSequence: TYPE ~ G3dShape.ScreenSequence;

Shape: TYPE ~ G3dShape.Shape;

ShapeRep: TYPE ~ G3dShape.ShapeRep;

ShapeSequence: TYPE ~ G3dShape.ShapeSequence;

SurfaceProc: TYPE ~ G3dShape.SurfaceProc;

Vertex: TYPE ~ G3dShape.Vertex;

VertexRep: TYPE ~ G3dShape.VertexRep;

VertexSequence: TYPE ~ G3dShape.VertexSequence;

VertexSequenceRep: TYPE ~ G3dShape.VertexSequenceRep;

SplineSequence: TYPE ~ G3dSpline.SplineSequence;

SplineSequenceRep: TYPE ~ G3dSpline.SplineSequenceRep;

Context: TYPE ~ Imager.Context;

ROPE: TYPE ~ Rope.ROPE;

BoundsFault: ERROR ~ RuntimeError.BoundsFault;

Error: PUBLIC SIGNAL [code: ATOM, reason: ROPE] = CODE;

File IO

ShapeFromFile: PUBLIC PROC [

fileName: ROPE,

points: BOOL Ź TRUE,

polygons: BOOL Ź FALSE,

faceCenters: BOOL Ź TRUE,

faceNormals: BOOL Ź TRUE,

edges: BOOL Ź TRUE,

curves: BOOL Ź FALSE,

normal: BOOL Ź FALSE,

center: BOOL Ź FALSE,

lines: BOOL Ź FALSE,

accs: BOOL Ź FALSE,

area: BOOL Ź FALSE]

RETURNS [s: Shape]

~ {

s Ź G3dShape.ShapeFromFile[fileName];

SetShape[s, points, polygons, faceCenters, faceNormals, edges, curves, normal, center, lines, accs, area];

};

Shape Specification

GetModel: PUBLIC PROC [shape: Shape] RETURNS [m: Model] ~ {

m Ź SELECT TRUE FROM

shape = NIL => NIL,

shape.modelData # NIL => NARROW[shape.modelData],

ENDCASE => (shape.modelData Ź NEW[ModelRep]);

};

SetShape: PUBLIC PROC [

shape: Shape,

points: BOOL Ź TRUE,

polygons: BOOL Ź FALSE,

faceCenters: BOOL Ź TRUE,

faceNormals: BOOL Ź TRUE,

edges: BOOL Ź TRUE,

curves: BOOL Ź FALSE,

normal: BOOL Ź FALSE,

center: BOOL Ź FALSE,

lines: BOOL Ź FALSE,

accs: BOOL Ź FALSE,

area: BOOL Ź FALSE]

~ {

IF points THEN SetPoints[shape];

IF faceCenters THEN G3dShape.SetFaceCenters[shape];

IF faceNormals AND NOT G3dShape.FaceValid[shape, normal]

THEN G3dShape.SetFaceNormals[shape, FALSE];

IF polygons THEN SetPolygons[shape, normal, center, area, accs, lines];

IF edges THEN shape.edges Ź G3dShape.MakeEdges[shape ! BoundsFault => CONTINUE];

IF curves THEN SetCurves[shape];

};

Vertex Procedures

SetPoints: PUBLIC PROC [shape: Shape] ~ {

m: Model Ź GetModel[shape];

m.points Ź G3dShape.PointsFromShape[shape, m.points];

};

IsolateVertices: PUBLIC PROC [shape: Shape] ~ {

model: Model Ź GetModel[shape];

nvert, vertno: NAT Ź 0;

old: VertexSequence Ź shape.vertices;

compute nvert, the number of new vertices: one per polygon per vertex, and allocate them

FOR i: NAT IN [0..shape.surfaces.length) DO

nvert Ź nvert+shape.surfaces[i].vertices.length;

ENDLOOP;

shape.vertices Ź NEW[VertexSequenceRep[nvert]]; -- allocate new vertices

shape.vertices.valid Ź old.valid;

shape.vertices.length Ź nvert;

shape.verticesIsolated Ź TRUE;

modify polygon indices and build new vertex list

FOR i: NAT IN [0..shape.surfaces.length) DO -- for each polygon

poly: NatSequence Ź shape.surfaces[i].vertices; -- this polygon

FOR j: NAT IN [0..poly.length) DO -- for each vertex of poly

shape.vertices[vertno] Ź NEW[VertexRep Ź old[poly[j]]^]; -- new vertex

poly[j] Ź vertno; -- modify index list

vertno Ź vertno+1;

ENDLOOP;

};

DeleteVertices: PUBLIC PROC [shape: Shape, vId0, vId1: NAT] ~ {

nPoly: NAT Ź 0;

nDeleted: NAT Ź ABS[vId1-vId0]+1;

FOR n: NAT IN [MIN[vId0, vId1]..shape.vertices.length-nDeleted) DO

shape.vertices[n] Ź shape.vertices[n] Ź shape.vertices[n+nDeleted];

ENDLOOP;

WHILE nPoly < shape.surfaces.length DO

poly: NatSequence Ź shape.surfaces[nPoly].vertices;

FOR p: NAT IN [0..poly.length) DO

SELECT poly[p] FROM

IN [vId0..vId1] => { -- this polygon now bogus

FOR n: NAT IN [nPoly..shape.surfaces.length-1) DO

shape.surfaces[n] Ź shape.surfaces[n-1];

ENDLOOP;

shape.surfaces.length Ź shape.surfaces.length-1;

LOOP;

};

> vId1 => poly[p] Ź poly[p]-nDeleted;

ENDCASE;

nPoly Ź nPoly+1;

ENDLOOP;

};

Polygon Procedures

SetPolygons: PUBLIC PROC [

shape: Shape,

normal, center, area, accs, lines: BOOL,

complyWithVertices: BOOL Ź TRUE]

~ {

model: Model Ź GetModel[shape];

normalFromFace: BOOL Ź normal AND G3dShape.FaceValid[shape, normal];

IF normalFromFace THEN normal Ź FALSE; -- we'll get from shape.faces

IF shape.vertices = NIL AND shape.surfaces = NIL THEN RETURN;

IF model.polygons = NIL OR model.polygons.maxLength < shape.surfaces.length

THEN model.polygons Ź NEW[PolygonSequenceRep[shape.surfaces.length]];

model.polygons.length Ź shape.surfaces.length;

FOR n: NAT IN [0..shape.surfaces.length) DO

poly: NatSequence Ź shape.surfaces[n].vertices;

polygon: Polygon Ź model.polygons[n] Ź NEW[G3dPolygon.PolygonRep];

polygon.points Ź NEW[TripleSequenceRep[poly.length]];

polygon.points.length Ź poly.length;

polygon.indices Ź poly;

FOR n: NAT IN [0..poly.length) DO

polygon.points[n] Ź shape.vertices[poly[n]].point;

ENDLOOP;

IF normalFromFace THEN { -- if complyWithVertices, assume faces[n].normal complies

v: Triple Ź shape.faces[n].normal;

polygon.plane Ź [v.x, v.y, v.z, G3dPlane.DFromNormalAndPoints[v, polygon.points]];

IF normalFromFace THEN polygon.normal Ź v;

};

G3dPolygon.SetPolygon[polygon, polygon.points, normal, center, area, accs, lines];

ENDLOOP;

IF complyWithVertices AND shape.vertices # NIL AND normal THEN

we didn't have face normals, so comply with vertices by testing polygon plane or normal

FOR n: NAT IN [0..shape.surfaces.length) DO

p: Polygon Ź model.polygons[n];

v: Triple Ź IF normal THEN p.normal ELSE [p.plane.x, p.plane.y, p.plane.z];

IF G3dVector.Dot[v, shape.vertices[p.indices[0]].normal] < 0.0 THEN {

p.plane Ź [-p.plane.x, -p.plane.y, -p.plane.z, -p.plane.w];

IF normal THEN p.normal Ź [-p.plane.x, -p.plane.y, -p.plane.z];

};

ENDLOOP;

};

CullBadPolygons: PUBLIC PROC [polygons: SurfaceSequence, maxNVertices: NAT] ~ {

n: NAT Ź 0;

poly: NatSequence Ź polygons[n].vertices;

FOR nn: NAT IN [0..poly.length) DO

IF poly[nn] >= maxNVertices THEN { -- overwrite this polygon

polygons.length Ź polygons.length-1;

IF n # polygons.length THEN polygons[n] Ź polygons[polygons.length];

EXIT;

};

REPEAT

FINISHED => n Ź n+1;

ENDLOOP;

IF n >= polygons.length THEN RETURN;

ENDLOOP;

};

Nearness Procedures

EnsureModelPolygons: PROC [s: Shape] RETURNS [m: Model] ~ {

IF (m Ź GetModel[s]) # NIL THEN {

ok: BOOL Ź m.polygons # NIL AND m.polygons.length # 0;

IF ok THEN {

p: Polygon Ź m.polygons[0];

ok Ź p.plane # [] AND p.accs # NIL AND p.lines # NIL;

};

IF NOT ok THEN SetPolygons[s, TRUE, TRUE, FALSE, TRUE, TRUE];

};

IntersectWithRay: PUBLIC PROC [shape: Shape, ray: Ray] RETURNS [near: NearModel] ~ {

model: Model Ź EnsureModelPolygons[shape];

minSqDistance: REAL Ź Real.LargestNumber;

IF model = NIL THEN RETURN;

FOR n: NAT IN [0..model.polygons.length) DO

polygon: Polygon Ź model.polygons[n];

pdDot: REAL Ź G3dVector.Dot[polygon.normal, ray.axis]; -- see G3dPlaneImpl

IF pdDot # 0.0 THEN {

alpha: REAL Ź (-polygon.plane.w-G3dVector.Dot[polygon.normal, ray.base])/pdDot;

IF alpha >= 0.0 THEN { -- if < 0.0 then no intersection in direction of ray

intersection: Triple Ź G3dVector.ScaleRay[ray, alpha];

sqDistance: REAL Ź G3dVector.SquareDistance[intersection, ray.base];

IF sqDistance < minSqDistance THEN {

IF G3dPolygon.InsidePolygon[intersection, polygon] # outside THEN {

minSqDistance Ź sqDistance;

near Ź [intersection, FALSE, n];

};

ENDLOOP;

};

ClosestPoint: PUBLIC PROC [shape: Shape, point: Triple] RETURNS [near: NearModel] ~ {

model: Model Ź EnsureModelPolygons[shape];

minDistance: REAL Ź Real.LargestNumber;

IF model # NIL THEN FOR n: NAT IN [0..model.polygons.length) DO

polygon: Polygon Ź model.polygons[n];

nearPolygon: G3dPolygon.NearPolygon Ź G3dPolygon.NearestToPolygon[polygon, point];

IF nearPolygon.distance < minDistance THEN {

near Ź [nearPolygon.point, FALSE, n];

minDistance Ź nearPolygon.distance;

};

ENDLOOP;

};

Creation

ShapeFromRevolvedCurve: PUBLIC PROC [

curve: PairSequence,

axis: Ray,

res: NAT,

start: NAT Ź 0,

stop: NAT Ź LAST[NAT]]

RETURNS [s: Shape]

~ {

newStop: NAT Ź MIN[res, stop];

nStrips: NAT Ź IF start < newStop THEN newStop-start ELSE res-start+newStop;

mat: G3dMatrix.Matrix Ź G3dMatrix.ObtainMatrix[];

nthVertex, nthPolygon: CARD Ź 0;

nPolygons: CARD Ź nStrips*(curve.length-1);

nVertices: CARD Ź (IF nStrips = res THEN nStrips ELSE nStrips+1)*curve.length;

curveNormals: PairSequence Ź NormalsFromCurve[curve];

s Ź NEW[ShapeRep];

s.surfaces Ź NEW[SurfaceSequenceRep[nPolygons]];

s.vertices Ź NEW[VertexSequenceRep[nVertices]];

s.surfaces.length Ź nPolygons;

s.vertices.length Ź nVertices;

s.vertices.valid[normal] Ź TRUE;

FOR n: NAT IN [0..IF nStrips = res THEN nStrips-1 ELSE nStrips] DO

a: NAT Ź (n+start) MOD res;

theta: REAL Ź 2.0*G3dBasic.PI*REAL[a]/REAL[res];

mat Ź G3dMatrix.MakeRotateAbout[axis.axis, theta, FALSE, axis.base, mat];

FOR i: NAT IN [0..curve.length) DO

p: Pair Ź curve[i];

pn: Pair Ź curveNormals[i];

v: Vertex Ź s.vertices[nthVertex] Ź NEW[VertexRep];

v.point Ź G3dMatrix.Transform[[p.x, 0.0, p.y], mat];

v.normal Ź G3dMatrix.TransformVec[[pn.x, 0.0, pn.y], mat];

nthVertex Ź nthVertex+1;

ENDLOOP;

FOR n: NAT IN [0..nStrips) DO

FOR i: NAT IN [0..curve.length-1) DO

p: NatSequence Ź s.surfaces[nthPolygon].vertices Ź NEW[NatSequenceRep[4]];

p.length Ź 4;

p[0] Ź n*curve.length+i;

p[1] Ź p[0]+1;

p[2] Ź (p[1]+curve.length) MOD nVertices;

p[3] Ź (p[0]+curve.length) MOD nVertices;

nthPolygon Ź nthPolygon+1;

ENDLOOP;

G3dMatrix.ReleaseMatrix[mat];

};

ShapeFromPointsPolys: PUBLIC PROC [

name: ROPE,

points: TripleSequence,

polys: SurfaceSequence]

RETURNS [s: Shape]

~ {

s Ź NEW[ShapeRep Ź [name: name, surfaces: polys, matrix: G3dMatrix.Identity[]]];

s.vertices Ź NEW[VertexSequenceRep[points.length]];

s.vertices.length Ź points.length;

FOR n: NAT IN [0..points.length) DO

s.vertices[n] Ź NEW[VertexRep Ź [point: points[n]]];

ENDLOOP;

s.objectExtent Ź G3dShape.BoundingBox[s];

};

PolyFromTwoPoints: PROC [n0, n1: NAT] RETURNS [poly: NatSequence] ~ {

poly Ź NEW[NatSequenceRep[2]];

poly[0] Ź n0;

poly[1] Ź n1;

poly.length Ź 2;

};

ShapeFrom2dCurve: PUBLIC PROC [name: ROPE, curve: PairSequence] RETURNS [s: Shape] ~ {

IF curve # NIL AND curve.length > 1 THEN {

triples: TripleSequence Ź NEW[TripleSequenceRep[curve.length]];

triples.length Ź curve.length;

FOR n: NAT IN [0..curve.length) DO

p: Pair Ź curve[n];

triples[n] Ź [p.x, 0.0, p.y];

ENDLOOP;

s Ź ShapeFrom3dCurve[name, triples];

};

ShapeFrom3dCurve: PUBLIC PROC [name: ROPE, curve: TripleSequence] RETURNS [s: Shape]

~ {

IF curve # NIL AND curve.length > 1 THEN {

polys: SurfaceSequence Ź NEW[SurfaceSequenceRep[curve.length-1]];

polys.length Ź curve.length-1;

FOR n: NAT IN [0..curve.length-1) DO polys[n].vertices Ź PolyFromTwoPoints[n, n+1]; ENDLOOP;

s Ź ShapeFromPointsPolys[name, curve, polys];

};

ShapeFromSegments: PUBLIC PROC [name: ROPE, segments: LIST OF Segment]

RETURNS [s: Shape]

~ {

nPoints, nPolys: NAT Ź 0;

FOR l: LIST OF Segment Ź segments, l.rest WHILE l # NIL DO

nPolys Ź nPolys+1;

nPoints Ź nPoints+2;

ENDLOOP;

IF nPoints > 1 THEN {

AddVertex: PROC [p: Triple] ~ {

s.vertices[s.vertices.length] Ź NEW[VertexRep Ź [point: p]];

s.vertices.length Ź s.vertices.length+1;

};

s Ź NEW[ShapeRep Ź [name: name, matrix: G3dMatrix.Identity[]]];

s.surfaces Ź NEW[SurfaceSequenceRep[nPolys]];

s.vertices Ź NEW[VertexSequenceRep[nPoints]];

FOR l: LIST OF Segment Ź segments, l.rest WHILE l # NIL DO

AddVertex[l.first.p0];

AddVertex[l.first.p1];

s.surfaces[s.surfaces.length].vertices Ź PolyFromTwoPoints[s.vertices.length-2,s.vertices.length-1];

s.surfaces.length Ź s.surfaces.length+1;

ENDLOOP;

s.objectExtent Ź G3dShape.BoundingBox[s];

};

ShapeFromPoints: PUBLIC PROC [name: ROPE, points: TripleSequence] RETURNS [Shape] ~ {

ERROR;

};

Cleaving

SkipNPolys: PUBLIC PROC [shape: Shape, nPolys: NAT] ~ {

FOR n: NAT IN [nPolys..shape.surfaces.length) DO

shape.surfaces[n-nPolys] Ź shape.surfaces[n];

ENDLOOP;

shape.surfaces.length Ź shape.surfaces.length-nPolys;

};

Hash: PROC [key: REF ANY] RETURNS [CARD] ~ {

i: REF IntegerPair ~ NARROW[key];

RETURN[i.x+i.y];

};

Equal: PROC [key1, key2: REF ANY] RETURNS [BOOL] ~ {

RETURN[NARROW[key1, REF IntegerPair]^ = NARROW[key2, REF IntegerPair]^];

};

Cleave: PUBLIC PROC [shape: Shape, plane: Plane, cap: BOOL Ź FALSE]

RETURNS [neg, pos: Shape Ź NIL]

~ {

CapInfo: TYPE ~ RECORD [vID, pID0, pID1: INTEGER Ź -1];

Caps: TYPE ~ RECORD [len: CARD Ź 0, s: SEQUENCE max: CARD OF REF CapInfo];

VertexState: TYPE ~ RECORD [v: Vertex, dist: REAL, sign: Border, old, pos, neg: INTEGER];

VertexStates: TYPE ~ RECORD [element: SEQUENCE max: CARD OF VertexState];

IF shape # NIL AND shape.vertices # NIL AND shape.vertices.length > 2 THEN {

Init: PROC RETURNS [s: Shape] ~ {

s Ź NEW[ShapeRep];

s.vertices Ź NEW[VertexSequenceRep[10]];

s.surfaces Ź NEW[SurfaceSequenceRep[10]];

s.faces Ź NEW[FaceSequenceRep[10]];

};

AddVertex: PROC [s: Shape, v: Vertex] ~ {

s.vertices Ź G3dShape.AddToVertexSequence[s.vertices, NEW[VertexRep Ź v^]];

};

AddPoly: PROC [s: Shape, poly: NatSequence, old: NAT] ~ {

s.surfaces Ź G3dBasic.AddToSurfaceSequence[s.surfaces, [NIL, poly]];

IF shape.faces # NIL AND shape.faces.length > old THEN

s.faces Ź G3dShape.AddToFaceSequence[s.faces, NEW[FaceRep Ź shape.faces[old]^]];

};

AllInPlane: PROC [poly: NatSequence] RETURNS [b: BOOL Ź TRUE] ~ {

FOR i: INTEGER IN [0..poly.length) DO

IF vertexStates[poly[i]].sign # edge THEN RETURN[FALSE];

ENDLOOP;

};

ToCaps: PROC [caps: REF Caps, vID, pID: INTEGER] RETURNS [ret: REF Caps] ~ {

IF (ret Ź caps) = NIL THEN ret Ź NEW[Caps[1]];

FOR i: INTEGER IN [0..ret.len) DO

IF ret[i].vID = vID THEN {ret[i].pID1 Ź pID; RETURN};

ENDLOOP;

IF ret.len = ret.max THEN {

old: REF Caps Ź ret;

ret Ź NEW[Caps[MAX[2*old.max, 3]]];

FOR i: INTEGER IN [0..(ret.len Ź old.len)) DO ret[i] Ź old[i]; ENDLOOP;

};

ret[ret.len] Ź NEW[CapInfo Ź [vID, pID, -1]];

ret.len Ź ret.len+1;

};

PosNegToCaps: PROC [posVid, negVid, posPid, negPid: INTEGER] ~ {

posCaps Ź ToCaps[posCaps, posVid, posPid];

negCaps Ź ToCaps[negCaps, negVid, negPid];

};

Cap: PROC [s: Shape, caps: REF Caps] ~ {

This will fail for concave polygons (ie, a polygon cut more than once by the plane).

GetAny: PROC RETURNS [r: REF CapInfo] ~ {

FOR i: INTEGER IN [0..caps.len) DO IF (r Ź caps[i]) # NIL THEN EXIT; ENDLOOP;

};

GetForIDAndDelete: PROC [pID: INTEGER] RETURNS [r: REF CapInfo] ~ {

FOR i: INTEGER IN [0..caps.len) DO

IF (rŹcaps[i]) # NIL AND (r.pID0=pID OR r.pID1=pID) THEN {caps[i]ŹNIL; RETURN};

ENDLOOP;

RETURN[NIL];

};

a, b: REF CapInfo;

WHILE (a Ź GetAny[]) # NIL DO

poly: NatSequence Ź NIL;

start, id: INTEGER Ź a.pID0;

WHILE (b Ź GetForIDAndDelete[id]) # NIL DO

poly Ź G2dBasic.AddToNatSequence[poly, b.vID];

id Ź IF b.pID0 = id THEN b.pID1 ELSE b.pID0;

ENDLOOP;

IF id = start THEN s.surfaces Ź G3dBasic.AddToSurfaceSequence[s.surfaces, [, poly]];

ENDLOOP;

};

posCaps, negCaps: REF Caps Ź NIL;

hash: RefTab.Ref Ź RefTab.Create[equal: Equal, hash: Hash];

vertexStates: REF VertexStates Ź NEW[VertexStates[shape.vertices.length]];

pos Ź Init[];

neg Ź Init[];

FOR i: INTEGER IN [0..shape.vertices.length) DO

v: Vertex Ź shape.vertices[i];

dist: REAL Ź G3dPlane.DistanceToPoint[v.point, plane, FALSE];

sign: Border Ź SELECT dist FROM > 0.01 => inside, < -0.01 => outside, ENDCASE => edge;

vertexStates[i] Ź [v, dist, sign, i, pos.vertices.length, neg.vertices.length];

IF sign = outside OR sign = edge THEN AddVertex[neg, v];

IF sign = inside OR sign = edge THEN AddVertex[pos, v];

ENDLOOP;

FOR n: INTEGER IN [0..shape.surfaces.length) DO

[Artwork node; type 'Artwork on' to command tool]

oldPoly: NatSequence Ź shape.surfaces[n].vertices;

posPoly, negPoly: NatSequence Ź NIL;

IF AllInPlane[oldPoly]

THEN { -- case 1

IF cap THEN FOR i: INTEGER IN [0..oldPoly.length) DO

vs: VertexState Ź vertexStates[oldPoly[i]];

posPoly Ź G2dBasic.AddToNatSequence[posPoly, vs.pos];

negPoly Ź G2dBasic.AddToNatSequence[negPoly, vs.neg];

ENDLOOP;

}

ELSE { -- case 2, 3, 4, or 5

nInside, nOutside, nEdge: INTEGER Ź 0;

s1: VertexState Ź vertexStates[oldPoly[oldPoly.length-1]];

FOR i: INTEGER IN [0..oldPoly.length) DO

SELECT vertexStates[oldPoly[i]].sign FROM

inside => nInside Ź nInside+1;

outside => nOutside Ź nOutside+1;

ENDCASE => nEdge Ź nEdge+1;

ENDLOOP;

FOR i: INTEGER IN [0..oldPoly.length) DO

s0: VertexState Ź s1;

s1 Ź vertexStates[oldPoly[i]];

IF s0.sign # s1.sign AND s0.sign # edge AND s1.sign # edge THEN { -- interp.

indices: IntegerPair; -- pos and neg indices for interpolated vertex

key: REF IntegerPair ŹNEW[IntegerPairŹ[MIN[s0.old,s1.old],MAX[s0.old,s1.old]]];

ref: REF Ź RefTab.Fetch[hash, key].val;

IF ref # NIL

THEN indices Ź NARROW[ref, REF IntegerPair]^ -- previously stored

ELSE { -- interpolate and store

v: Vertex Ź G3dShape.InterpolateVertex[s0.dist/(s0.dist-s1.dist), s0.v, s1.v];

indices Ź [pos.vertices.length, neg.vertices.length];

[] Ź RefTab.Store[hash, key, NEW[IntegerPair Ź indices]];

AddVertex[pos, v];

AddVertex[neg, v];

};

IF cap THEN

PosNegToCaps[indices.x, indices.y, pos.surfaces.length, neg.surfaces.length];

posPoly Ź G2dBasic.AddToNatSequence[posPoly, indices.x]; -- case 2

negPoly Ź G2dBasic.AddToNatSequence[negPoly, indices.y]; -- case 2

};

IF cap AND s1.sign = edge THEN SELECT TRUE FROM

nInside > 0 AND nOutside > 0 => -- case 4 (rightmost poly in fig)

PosNegToCaps[s1.pos, s1.neg, pos.surfaces.length, neg.surfaces.length];

nInside > 0 AND nEdge >= 2 => -- case 5 (leftmost poly in fig)

posCaps Ź ToCaps[posCaps, s1.pos, pos.surfaces.length];

nOutside > 0 AND nEdge >= 2 => -- case 5 (leftmost poly in fig)

negCaps Ź ToCaps[negCaps, s1.neg, neg.surfaces.length];

ENDCASE; -- case 3

IF nInside > 0 AND s1.sign # outside

THEN posPoly Ź G2dBasic.AddToNatSequence[posPoly, s1.pos];

IF nOutside > 0 AND s1.sign # inside

THEN negPoly Ź G2dBasic.AddToNatSequence[negPoly, s1.neg];

ENDLOOP;

};

IF posPoly # NIL THEN AddPoly[pos, posPoly, n]; -- add poly if not fully clipped

IF negPoly # NIL THEN AddPoly[neg, G3dPolygon.PolygonReverse[negPoly], n];

ENDLOOP;

IF posCaps # NIL THEN Cap[pos, posCaps];

IF negCaps # NIL THEN Cap[neg, negCaps];

pos.edges Ź G3dShape.MakeEdges[pos ! BoundsFault => CONTINUE];

neg.edges Ź G3dShape.MakeEdges[neg ! BoundsFault => CONTINUE];

};

Curve Procedures

DrawCurves: PUBLIC PROC [

context: Context,

shape: Shape,

view: Matrix,

viewport: Viewport Ź [],

type: DrawType Ź solid,

backFaces: BOOL Ź TRUE,

screens: ScreenSequence Ź NIL,

forceTransform: BOOL Ź FALSE,

forInterpress: BOOL Ź FALSE]

RETURNS [ScreenSequence]

~ {

FrontFacingAction: SurfaceProc ~ {

i0: CARD Ź surface[surface.length-1];

FOR n: INTEGER IN [0..surface.length) DO

i1: CARD Ź surface[n];

index: INT Ź G3dShape.FindEdge[shape.edges, i0, i1];

i0 Ź i1;

IF index = -1 THEN LOOP;

IF type # solid

THEN G3dDraw.DotCurve[context, model.curves[index], x, viewport]

ELSE G3dDraw.Curve[context, model.curves[index], x, viewport,, forInterpress];

ENDLOOP;

};

model: Model Ź GetModel[shape];

mat: Matrix Ź IF shape.matrix # NIL THEN shape.matrix ELSE G3dMatrix.Identity[];

x: Matrix Ź G3dMatrix.Mul[shape.matrix Ź mat, view, G3dMatrix.ObtainMatrix[]];

IF model = NIL THEN RETURN[NIL];

IF forceTransform OR screens = NIL OR NOT screens.screensValid

THEN screens Ź G3dDraw.SetScreenCoords[context, shape, x, viewport, screens];

IF shape.edges = NIL THEN shape.edges Ź G3dShape.MakeEdges[shape];

IF backFaces

THEN G3dDraw.Curves[context, model.curves, x, viewport, type # solid, forInterpress]

ELSE G3dShape.DoWithFacingPolygons[shape, x, FrontFacingAction];

RETURN[screens];

};

SetCurves: PUBLIC PROC [shape: Shape] ~ {

model: Model Ź GetModel[shape];

IF G3dShape.VertexValid[shape, normal] AND shape.edges # NIL THEN {

IF model.curves = NIL OR model.curves.maxLength < shape.edges.length

THEN model.curves Ź NEW[SplineSequenceRep[shape.edges.length]];

model.curves.length Ź shape.edges.length;

FOR n: NAT IN [0..shape.edges.length) DO

e: Edge Ź shape.edges[n];

v0: Vertex Ź shape.vertices[e.v0];

v1: Vertex Ź shape.vertices[e.v1];

model.curves[n] Ź G3dSpline.SplineFromPointsAndNormals[

v0.point, v1.point, v0.normal, v1.normal,, model.curves[n]];

ENDLOOP;

};

MakeCurves: PUBLIC PROC [

vertices, normals: TripleSequence,

edges: EdgeSequence,

curves: SplineSequence Ź NIL]

RETURNS [SplineSequence]

~ {

IF vertices # NIL AND normals # NIL AND edges # NIL THEN {

IF curves = NIL OR curves.maxLength < edges.length

THEN curves Ź NEW[SplineSequenceRep[edges.length]];

curves.length Ź edges.length;

FOR n: NAT IN [0..edges.length) DO

e: Edge Ź edges[n];

curves[n] Ź G3dSpline.SplineFromPointsAndNormals[

vertices[e.v0], vertices[e.v1], normals[e.v0], normals[e.v1], , curves[n]];

ENDLOOP;

};

RETURN[curves];

};

NormalsFromCurve: PUBLIC PROC [curve: PairSequence]

RETURNS [curveNormals: PairSequence]

Unit normals are created by rotating estimated tangents left 90° as we follow curve.

If data is specified in the opposite order, the normals may be 180° out of phase.

For evenly spaced data points tangent estimation is no problem; irregularly spaced points require more care. The intent here is to average the (normalized) incoming and outgoing vectors at an interior point when their magnitudes are the same, so simple data works as expected. However when one of the vectors is small compared to the other, it gets more weight (after normalization)--on the assumption that the curve is parameterized by arc length so nearly incident points provide a better tangent estimate.

~ {

curveNormals Ź NEW[PairSequenceRep[curve.length]];

curveNormals.length Ź curve.length;

SELECT curve.length FROM

= 2 => {

tangent: Pair Ź G2dVector.Unit[G2dVector.Sub[curve[1], curve[0]]];

curveNormals[0] Ź curveNormals[1] Ź [-tangent.y, tangent.x];

};

> 2 => {

dm, dp, tangent: Pair;

delm, delp, delSum: REAL;

Estimate tangent from chord length parameterized parabola

FOR i: NAT IN [1..curve.length-1) DO

dm Ź G2dVector.Sub[curve[i], curve[i-1]];

dp Ź G2dVector.Sub[curve[i+1], curve[i]];

delm Ź ABS[dm.x] + ABS[dm.y];

delp Ź ABS[dp.x] + ABS[dp.y];

delSum Ź delm+delp;

tangent Ź G2dVector.Combine[G2dVector.Unit[dm], delp/delSum,
G2dVector.Unit[dp], delm/delSum];

curveNormals[i] Ź G2dVector.Unit[[-tangent.y, tangent.x]];

ENDLOOP;

Estimate tangent at trailing end using left-over values

tangent Ź G2dVector.Combine[G2dVector.Unit[dp], 2.0*delSum,
G2dVector.Unit[tangent], -1];

curveNormals[curve.length-1] Ź G2dVector.Unit[[-tangent.y, tangent.x]];

Estimate tangent at leading end

dm Ź G2dVector.Sub[curve[1], curve[0]];

dp Ź G2dVector.Sub[curve[2], curve[1]];

delm Ź ABS[dm.x] + ABS[dm.y];

delp Ź ABS[dp.x] + ABS[dp.y];

delSum Ź delm+delp;

tangent Ź G2dVector.Combine[G2dVector.Unit[dm], 2.0*delSum,
[curveNormals[1].y, -curveNormals[1].x], -1];

curveNormals[0] Ź G2dVector.Unit[[-tangent.y, tangent.x]];

};

ENDCASE;

};

END.

MakeEdges: PUBLIC PROC [polygons: SurfaceSequence, edges: EdgeSequence Ź NIL]

RETURNS [EdgeSequence] ~ {

n0, n1, min, max: CARD;

IF vertices = NIL OR polygons = NIL THEN RETURN[NIL];

IF edges = NIL OR edges.maxLength < vertices.length

THEN edges Ź NEW[EdgeSequence[vertices.length]];

FOR i: NAT IN [0..polygons.length) DO

polygon: NatSequence ~ polygons[i];

n0 Ź polygon[polygon.length-1];

FOR ii: NAT IN [0..polygon.length) DO

n1 Ź polygon[ii];

IF n0 < n1 THEN {min Ź n0; max Ź n1} ELSE {min Ź n1; max Ź n0};

IF min+1 > edges.length THEN edges.length Ź min+1;

FOR l: LIST OF NAT Ź edges[min], l.rest WHILE l # NIL DO

IF l.first = max THEN EXIT;

REPEAT

FINISHED => edges[min] Ź CONS[max, edges[min]];

ENDLOOP;

n0 Ź n1;

ENDLOOP;

RETURN[edges];

};