G3dClipVolumeImpl.mesa
Copyright Ó 1985, 1992 by Xerox Corporation. All rights reserved.
Glassner, February 20, 1991 1:24 pm PST
Jules Bloomenthal July 15, 1992 5:52 pm PDT
DIRECTORY G2dBasic, G3dBasic, G3dClipVolume, G3dBox, G3dShape, G3dPlane, G3dVector, Rope;
G3dClipVolumeImpl: CEDAR PROGRAM
IMPORTS G3dBox, G3dPlane, G3dVector
EXPORTS G3dClipVolume
~ BEGIN
Imported Types
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;
Local Types
Error:     PUBLIC SIGNAL [reason: ROPE] = CODE;
Private Types
Distribution:    TYPE ~ { allNegative, allPositive, straddles };
Clip Volume Construction
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];
};
Shape and Polygon Testing
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];
};
Utility
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;
};
Volume Clipping
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.