<<>> <> <> <> <> <<>> DIRECTORY G2dBasic, G3dBasic, G3dClipVolume, G3dBox, G3dShape, G3dPlane, G3dVector, Rope; G3dClipVolumeImpl: CEDAR PROGRAM IMPORTS G3dBox, G3dPlane, G3dVector EXPORTS G3dClipVolume ~ BEGIN <> Box: TYPE ~ G3dBox.Box; ClipVolume: TYPE ~ G3dClipVolume.ClipVolume; ClipVolumeRep: TYPE ~ G3dClipVolume.ClipVolumeRep; NatSequence: TYPE ~ G2dBasic.NatSequence; Plane: TYPE ~ G3dPlane.Plane; PlaneSequence: TYPE ~ G3dPlane.PlaneSequence; Ray: TYPE ~ G3dPlane.Ray; ROPE: TYPE ~ Rope.ROPE; Shape: TYPE ~ G3dShape.Shape; Triple: TYPE ~ G3dBasic.Triple; TripleList: TYPE ~ G3dClipVolume.TripleList; <> Error: PUBLIC SIGNAL [reason: ROPE] = CODE; <> Distribution: TYPE ~ { allNegative, allPositive, straddles }; <> ClipVolumeFrom4Points: PUBLIC PROC [p0, p1, p2, p3: Triple] RETURNS [tetra: ClipVolume] ~ { BuildPlane: PROC [p0, p1, p2, testPoint: Triple] RETURNS [plane: Plane] ~ { plane ¬ G3dPlane.FromThreePoints[p0, p1, p2]; IF G3dPlane.DistanceToPoint[testPoint, plane] < 0.0 THEN plane ¬ NegatePlane[plane]; }; tetra ¬ NEW[ClipVolumeRep ¬ []]; tetra.planes ¬ G3dPlane.AddToPlaneSequence[tetra.planes, BuildPlane[p0, p1, p2, p3]]; tetra.planes ¬ G3dPlane.AddToPlaneSequence[tetra.planes, BuildPlane[p0, p2, p3, p1]]; tetra.planes ¬ G3dPlane.AddToPlaneSequence[tetra.planes, BuildPlane[p0, p3, p1, p2]]; tetra.planes ¬ G3dPlane.AddToPlaneSequence[tetra.planes, BuildPlane[p1, p2, p3, p0]]; tetra.box ¬ G3dBox.BoxFromPoints[p0, p1]; tetra.box ¬ G3dBox.BoxUnionPoint[tetra.box, p2]; tetra.box ¬ G3dBox.BoxUnionPoint[tetra.box, p3]; }; <> ShapeInVolume: PUBLIC PROC [shape: Shape, clipVolume: ClipVolume] RETURNS [BOOL ¬ FALSE] ~ { FOR i: INT IN [0 .. shape.surfaces.length) DO tl: TripleList ¬ TripleListFromSurface[shape, i]; IF PolygonInVolume[tl, clipVolume] THEN RETURN [TRUE]; ENDLOOP; }; PolygonInVolume: PUBLIC PROC [pts: TripleList, clipVolume: ClipVolume] RETURNS [BOOL] ~ { new: TripleList ¬ NIL; FOR v: TripleList ¬ pts, v.rest UNTIL v=NIL DO new ¬ CONS[v.first, new]; ENDLOOP; FOR i: INT IN [0 .. clipVolume.planes.length) DO new ¬ ClipToPlane[new, clipVolume.planes[i]]; ENDLOOP; RETURN [new#NIL]; }; <> NegatePlane: PUBLIC PROC [plane: Plane] RETURNS [Plane] ~ { RETURN[[-plane.x, -plane.y, -plane.z, -plane.w]]; }; TripleListFromSurface: PUBLIC PROC [shape: Shape, surfID: INT] RETURNS [vList: TripleList ¬ NIL] ~ { FOR i: INT IN [0 .. shape.surfaces[surfID].vertices.length) DO vList ¬ CONS[shape.vertices[shape.surfaces[surfID].vertices[i]].point, vList]; ENDLOOP; }; <> PointSpread: PROC [vList: TripleList, plane: Plane] RETURNS [dist: Distribution ¬ straddles] ~ { epsilon: REAL ¬ 0.000001; -- numerical voodoo - if this close to plane, no penetration distSet: BOOL ¬ FALSE; IF vList = NIL THEN RETURN; FOR v: TripleList ¬ vList, v.rest UNTIL v=NIL DO val: REAL ¬ G3dPlane.DistanceToPoint[v.first, plane]; IF ABS[val] > epsilon THEN { location: Distribution ¬ IF val>0.0 THEN allPositive ELSE allNegative; IF distSet THEN { IF location # dist THEN RETURN [straddles]; } ELSE { distSet ¬ TRUE; dist ¬ location; }; }; ENDLOOP; }; ClipToPlane: PUBLIC PROC [vList: TripleList, plane: Plane] RETURNS [result: TripleList ¬ NIL] ~ { <<-- Sutherland-Hodgman clip. >> MakeNewPt: PROC ~ { Xor: PROC [a, b: BOOL] RETURNS [BOOL]~{RETURN[(a AND NOT b) OR (b AND NOT a)];}; IF Xor[newIn, oldIn] THEN { ray: Ray ¬ [base: oldPt, axis: G3dVector.Sub[newPt, oldPt]]; intersection: Triple ¬ G3dPlane.IntersectWithLine[plane, ray ! G3dPlane.Error => GOTO skipError]; result ¬ CONS[intersection, result]; EXITS skipError => result ¬ CONS[newPt, result]; }; }; tstPt, oldPt, newPt, firstPt: Triple; list: TripleList; newIn, oldIn, firstIn: BOOL; epsilon: REAL ¬ 0.00001; -- numerical voodoo - if this close to plane, no penetration distribution: Distribution ¬ PointSpread[vList, plane]; IF distribution = allNegative THEN RETURN[NIL]; -- all points are clipped IF distribution = allPositive THEN RETURN[vList]; -- no points are clipped IF vList=NIL OR vList.rest=NIL THEN RETURN; list ¬ vList; WHILE (list # NIL) AND ABS[G3dPlane.DistanceToPoint[list.first, plane]] < epsilon DO list ¬ list.rest; ENDLOOP; IF list=NIL THEN RETURN [vList]; -- all the points are in this plane oldIn ¬ G3dPlane.Side[list.first, plane] = positive; FOR v: TripleList ¬ vList, v.rest UNTIL v=NIL DO newPt ¬ v.first; IF ABS[G3dPlane.DistanceToPoint[newPt, plane]] < epsilon THEN newIn ¬ oldIn ELSE newIn ¬ G3dPlane.Side[newPt, plane] = positive; IF v = vList THEN { firstPt ¬ newPt; firstIn ¬ newIn; } ELSE MakeNewPt[]; IF newIn THEN result ¬ CONS[newPt, result]; oldPt ¬ newPt; oldIn ¬ newIn; ENDLOOP; newPt ¬ firstPt; newIn ¬ firstIn; MakeNewPt[]; }; END.