DIRECTORY G3dBasic, G3dShape, G3dBox, G3dGrid, G3dPlane, Real;

G3dGridImpl: CEDAR PROGRAM
IMPORTS G3dShape, G3dBox, G3dPlane, Real
EXPORTS G3dGrid 

~ BEGIN
Box:						TYPE ~ G3dBox.Box;
CellData:					TYPE ~ G3dGrid.CellData;
CellDataRep:				TYPE ~ G3dGrid.CellDataRep;
CellDataSequence:		TYPE ~ G3dGrid.CellDataSequence;
CellDataSequenceRep:	TYPE ~ G3dGrid.CellDataSequenceRep;
Grid3d:					TYPE ~ G3dGrid.Grid3d;
Grid3dRep:				TYPE ~ G3dGrid.Grid3dRep;
GridProc:					TYPE ~ G3dGrid.GridProc;
NatSequence:				TYPE ~ G3dGrid.NatSequence;
Object:					TYPE ~ G3dGrid.Object;
ObjectRep:				TYPE ~ G3dGrid.ObjectRep;
ObjectSequence:			TYPE ~ G3dGrid.ObjectSequence;
ObjectSequenceRep:		TYPE ~ G3dGrid.ObjectSequenceRep;
Plane:						TYPE ~ G3dPlane.Plane;
Shape:					TYPE ~ G3dGrid.Shape;
TestGridProc:				TYPE ~ G3dGrid.TestGridProc;
Triple:					TYPE ~ G3dBasic.Triple;
TripleList:				TYPE ~ G3dGrid.TripleList;
CreateGrid: PUBLIC PROC [box: Box, xRes: NAT ¬ 8, yRes, zRes: NAT ¬ 0] RETURNS [grid: Grid3d] ~ {
grid ¬ NEW[Grid3dRep ¬ [xRes: xRes, box: box]];
IF yRes>0 THEN grid.yRes ¬ yRes ELSE grid.yRes ¬ xRes;
IF zRes>0 THEN grid.zRes ¬ zRes ELSE grid.zRes ¬ xRes;
grid.cellData ¬ NEW[CellDataSequenceRep[grid.xRes * grid.yRes * grid.zRes]];
grid.cellData.length ¬ grid.xRes * grid.yRes * grid.zRes;
BuildGridCells[grid];
};

CreateGridFromShape: PUBLIC PROC [shape: Shape, xRes: NAT ¬ 8, yRes, zRes: NAT ¬ 0] RETURNS [grid: Grid3d ¬ NIL] ~ {
IF shape=NIL OR shape.surfaces=NIL THEN RETURN;
grid ¬ CreateGrid[G3dShape.BoundingBox[shape], xRes, yRes, zRes];
BuildGridCells[grid];
FOR s: INT IN [0 .. shape.surfaces.length) DO
InsertSurfaceIntoGrid[shape, grid, s];
ENDLOOP;
};
InsertNatsIntoGrid: PUBLIC PROC [shape: Shape, grid: Grid3d, nats: NatSequence, surfID: INT, clientData: REF ¬ NIL] ~ {
v: TripleList ¬ NIL;
FOR i: INT IN [0 .. nats.length) DO
v ¬ CONS[shape.vertices[nats[i]].point, v];
ENDLOOP;
InsertTripleListIntoGrid[v, grid, surfID];
};

InsertSurfaceIntoGrid: PUBLIC PROC [shape: Shape, grid: Grid3d, surfID: INT, clientData: REF ¬ NIL] ~ {
InsertNatsIntoGrid[shape, grid, shape.surfaces[surfID].vertices, surfID, clientData];
};

InsertTripleListIntoGrid: PUBLIC PROC [vertices: TripleList, grid: Grid3d, surfID: INT, clientData: REF ¬ NIL] ~ {
Action: GridProc ~ {
hasInter: BOOL;
[has:hasInter] ¬ G3dBox.Intersect[cellData.box, polyBox];
IF hasInter THEN 
IF BoxCornerSignsDiffer[cellData.box, plane] THEN {
newObject: Object ¬ NEW[ObjectRep ¬ [$Polygon, surfID, clientData]];
cellData.objects ¬ AddToObjectSequence[cellData.objects, newObject]; 
};
RETURN[cellData];
};
plane: G3dPlane.Plane ¬ G3dPlane.FromThreePoints[vertices.first, vertices.rest.first, vertices.rest.rest.first];
polyBox: Box ¬ G3dBox.BoxFromPoints[vertices.first, vertices.rest.first];
FOR v: TripleList ¬ vertices, v.rest UNTIL v=NIL DO
polyBox ¬ G3dBox.BoxUnionPoint[polyBox, v.first];
ENDLOOP;
VisitGrid[grid, Action];
};

RemoveSurfaceFromGrid: PUBLIC PROC [grid: Grid3d, surfID: INT] ~ {
Action: GridProc ~ {
newCell: CellData ¬ NEW[CellDataRep ¬ cellData­];
newCell.objects ¬ NIL;
IF cellData.objects # NIL THEN FOR i: INT IN [0 .. cellData.objects.length) DO
IF ((cellData.objects[i].type # $Polygon) OR (cellData.objects[i].index # surfID)) THEN
newCell.objects ¬ AddToObjectSequence[newCell.objects, cellData.objects[i]];
ENDLOOP;
RETURN[newCell];
};
VisitGrid[grid, Action];
};
VisitGrid: PUBLIC PROC [grid: Grid3d, proc: GridProc, client: REF ANY ¬ NIL] ~ {
FOR x: INT IN [0 .. grid.xRes) DO
FOR y: INT IN [0 .. grid.yRes) DO
FOR z: INT IN [0 .. grid.zRes) DO
index: INT ¬ GridIndexFromXYZ[grid, x, y, z];
grid.cellData[index] ¬ proc[grid.cellData[index], client];
ENDLOOP;
ENDLOOP;
ENDLOOP;
};

TestGrid: PUBLIC PROC [grid: Grid3d, proc: TestGridProc, client: REF ANY ¬ NIL] ~ {
FOR x: INT IN [0 .. grid.xRes) DO
FOR y: INT IN [0 .. grid.yRes) DO
FOR z: INT IN [0 .. grid.zRes) DO
index: INT ¬ GridIndexFromXYZ[grid, x, y, z];
IF NOT proc[grid.cellData[index], client] THEN RETURN;
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
CopyGrid: PUBLIC PROC [grid: Grid3d] RETURNS [new: Grid3d] ~ {
new ¬ NEW[Grid3dRep ¬ [
xRes: grid.xRes,
yRes: grid.yRes,
zRes: grid.zRes,
box: grid.box
]];
new.cellData ¬ NEW[CellDataSequenceRep[grid.cellData.length]];
new.cellData.length ¬ grid.cellData.length;
FOR x: INT IN [0 .. grid.xRes) DO
FOR y: INT IN [0 .. grid.yRes) DO
FOR z: INT IN [0 .. grid.zRes) DO
index: INT ¬ GridIndexFromXYZ[grid, x, y, z];
new.cellData[index] ¬ NEW[CellDataRep ¬ [box: grid.cellData[index].box]];
new.cellData[index].objects ¬ CopyObjectSequence[grid.cellData[index].objects];
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
BuildGridCells: PROC [grid: Grid3d] ~ {
xSize: REAL ¬ (grid.box.max.x - grid.box.min.x)/REAL[grid.xRes];
ySize: REAL ¬ (grid.box.max.y - grid.box.min.y)/REAL[grid.yRes];
zSize: REAL ¬ (grid.box.max.z - grid.box.min.z)/REAL[grid.zRes];
min, max: Triple;
FOR x: INT IN [0 .. grid.xRes) DO
min.x ¬ x * xSize;
max.x ¬ min.x + xSize;
FOR y: INT IN [0 .. grid.yRes) DO
min.y ¬ y * ySize;
max.y ¬ min.y + ySize;
FOR z: INT IN [0 .. grid.zRes) DO
cellIndex: INT ¬ GridIndexFromXYZ[grid, x, y, z];
min.z ¬ z * zSize;
max.z ¬ min.z + zSize;
grid.cellData[cellIndex] ¬ NEW[CellDataRep ¬ []];
grid.cellData[cellIndex].box ¬ G3dBox.BoxFromPoints[min, max];
grid.cellData[cellIndex].objects ¬ NIL;
ENDLOOP;
ENDLOOP;
ENDLOOP;
};

BoxCornerSignsDiffer: PROC [box: Box, plane: Plane] RETURNS [BOOL] ~ {
sign0: G3dPlane.Sign ¬ G3dPlane.Side[box.min, plane];
IF sign0 # G3dPlane.Side[[box.min.x, box.max.y, box.min.z], plane] THEN RETURN [TRUE];
IF sign0 # G3dPlane.Side[[box.min.x, box.max.y, box.max.z], plane] THEN RETURN [TRUE];
IF sign0 # G3dPlane.Side[[box.min.x, box.min.y, box.max.z], plane] THEN RETURN [TRUE];
IF sign0 # G3dPlane.Side[[box.max.x, box.min.y, box.min.z], plane] THEN RETURN [TRUE];
IF sign0 # G3dPlane.Side[[box.max.x, box.max.y, box.min.z], plane] THEN RETURN [TRUE];
IF sign0 # G3dPlane.Side[[box.max.x, box.max.y, box.max.z], plane] THEN RETURN [TRUE];
IF sign0 # G3dPlane.Side[[box.max.x, box.min.y, box.max.z], plane] THEN RETURN [TRUE];
RETURN[FALSE];
};
GridIndexFromXYZ: PUBLIC PROC [grid: Grid3d, x, y, z: INT] RETURNS [cellIndex: INT] ~ {
cellIndex ¬ z+(y*grid.zRes)+(x*grid.yRes);
IF cellIndex<0 OR cellIndex > INT[grid.cellData.length] THEN cellIndex ¬ -1;
};
CopyObjectSequence: PUBLIC PROC [objects: ObjectSequence] RETURNS [ObjectSequence] ~ {
copy: ObjectSequence ¬ NIL;
IF objects # NIL THEN {
copy ¬ NEW[ObjectSequenceRep[objects.length]];
copy.length ¬ objects.length;
FOR n: NAT IN [0..objects.length) DO copy[n] ¬ objects[n]; ENDLOOP;
};
RETURN[copy];
};

AddToObjectSequence: PUBLIC PROC [objects: ObjectSequence, object: Object] RETURNS [ObjectSequence]
~ {
IF objects = NIL THEN objects ¬ NEW[ObjectSequenceRep[1]];
IF objects.length = objects.maxLength THEN objects ¬ LengthenObjectSequence[objects];
objects[objects.length] ¬ object;
objects.length ¬ objects.length+1;
RETURN[objects];
};
LengthenObjectSequence: PUBLIC PROC [objects: ObjectSequence, amount: REAL ¬ 1.3]
RETURNS [new: ObjectSequence] ~ {
newLength: NAT ¬ MAX[Real.Ceiling[amount*objects.maxLength], 3];
new ¬ NEW[ObjectSequenceRep[newLength]];
FOR i: NAT IN [0..objects.length) DO new[i] ¬ objects[i]; ENDLOOP;
new.length ¬ objects.length;
};
CopyCellDataSequence: PUBLIC PROC [cells: CellDataSequence] RETURNS [CellDataSequence] ~ {
copy: CellDataSequence ¬ NIL;
IF cells # NIL THEN {
copy ¬ NEW[CellDataSequenceRep[cells.length]];
copy.length ¬ cells.length;
FOR n: NAT IN [0..cells.length) DO copy[n] ¬ cells[n]; ENDLOOP;
};
RETURN[copy];
};

AddToCellDataSequence: PUBLIC PROC [cells: CellDataSequence, cell: CellData] RETURNS [CellDataSequence]
~ {
IF cells = NIL THEN cells ¬ NEW[CellDataSequenceRep[1]];
IF cells.length = cells.maxLength THEN cells ¬ LengthenCellDataSequence[cells];
cells[cells.length] ¬ cell;
cells.length ¬ cells.length+1;
RETURN[cells];
};
LengthenCellDataSequence: PUBLIC PROC [cells: CellDataSequence, amount: REAL ¬ 1.3]
RETURNS [new: CellDataSequence] ~ {
newLength: NAT ¬ MAX[Real.Ceiling[amount*cells.maxLength], 3];
new ¬ NEW[CellDataSequenceRep[newLength]];
FOR i: NAT IN [0..cells.length) DO new[i] ¬ cells[i]; ENDLOOP;
new.length ¬ cells.length;
};


END.


ˆ
G3dGridImpl.mesa
Copyright Σ 1985, 1992 by Xerox Corporation.  All rights reserved.
Glassner, February 19, 1991 9:19 am PST
Jules Bloomenthal July 15, 1992 4:09 pm PDT
Ken Fishkin, August 25, 1992 3:42 pm PDT

Types
Creation Procs
Build polygon lists for each grid cell from the input shape.
Polygon Insertion and Deletion Procs
this test will include the polygon in some boxes around its perimeter which it shouldn't, but it's fast, and there won't be many of these false positives, which clients should be able to handle without trouble
Grid Visiting Procs
Utility Procs
Private Procs
Auxiliary Procs
Object Sequences

CellData Sequences

Κ
•NewlineDelimiter

–
"cedarcode" style™™Jšœ	Οeœ6™BJ™'J™+J™(J™JšΟk	œ5˜>J˜—šΡblnœžœ
ž˜Jšžœ!˜(Jšžœ	˜J˜—Jšœž˜
headš
Οl™Jšœ
žœ˜Jšœžœ˜&Jšœžœ˜+Jšœžœ˜3Jšœžœ˜8Jšœžœ˜"Jšœžœ˜'Jšœžœ˜&Jšœžœ˜+Jšœžœ˜"Jšœžœ˜'Jšœžœ˜0Jšœžœ˜5Jšœžœ˜"Jšœžœ˜ Jšœžœ˜-Jšœžœ˜#Jšœžœ˜)—š
 ™šΟn
œžœ
žœžœžœžœ˜aJšœžœ%˜/Jšžœžœžœ˜6Jšžœžœžœ˜6Jšœžœ9˜LJ˜9J˜J˜J˜—š‘œžœ
žœžœžœžœžœ˜tJš
œ<™<Jšžœžœ
žœžœ
žœ
žœ
˜/J˜AJš
œ˜šžœžœ
žœž˜-Jš
œ&˜&Jšžœ
˜—J˜——š
 $™$š‘œžœ
žœ9žœžœžœ˜wJšœžœ
˜šžœžœ
žœž˜#Jšœžœ#˜+Jšžœ
˜—J˜*J˜J˜—š‘œžœ
žœ&žœžœžœ˜gJ˜UJ˜J˜—š‘œžœ
žœ.žœžœžœ˜rJš
œΡ
™Ρ
š‘œ˜Jšœ
žœ
˜J˜9šžœ
žœ
˜šžœ+žœ˜3Jšœžœ-˜DJ˜EJ˜——Jšžœ˜J˜—J˜pJ˜Išžœ"žœžœ
ž˜3J˜1Jšžœ
˜—J˜J˜J˜—š‘œžœ
žœžœ˜Bš‘œ˜Jšœžœ˜1Jšœžœ
˜š
žœžœ
žœ
žœžœ
žœ ž˜Nšžœ(žœ'ž˜WJ˜L—Jšžœ
˜—Jšžœ
˜J˜—J˜J˜——š
 ™š‘	œžœ
žœ(žœ
žœžœ˜Pšžœžœ
žœž˜!šžœžœ
žœž˜!šžœžœ
žœž˜!Jšœžœ#˜-J˜:Jšžœ
˜—Jšžœ
˜—Jšžœ
˜—J˜J˜—š‘œžœ
žœ,žœ
žœžœ˜Sšžœžœ
žœž˜!šžœžœ
žœž˜!šžœžœ
žœž˜!Jšœžœ#˜-Jšžœ
žœ$žœ
žœ
˜6Jšžœ
˜—Jšžœ
˜—Jšžœ
˜—J˜——š
 
™
š‘œžœ
žœžœ˜>šœžœ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ
˜
Jš
œ˜—Jšœžœ,˜>J˜+šžœžœ
žœž˜!šžœžœ
žœž˜!šžœžœ
žœž˜!Jšœžœ#˜-Jšœžœ0˜IJ˜OJšžœ
˜—Jšžœ
˜—Jšžœ
˜—J˜——š
 
™
š‘œžœ˜'Jšœžœ%žœ˜@Jšœžœ%žœ˜@Jšœžœ%žœ˜@J˜šžœžœ
žœž˜!J˜J˜šžœžœ
žœž˜!J˜J˜šžœžœ
žœž˜!Jšœžœ#˜1J˜J˜J˜1J˜>Jšœ#žœ
˜'Jšžœ
˜—Jšžœ
˜—Jšžœ
˜—J˜J˜—š‘œžœž	œ
žœ˜FJ˜5JšžœAžœ
žœžœ˜VJšžœAžœ
žœžœ˜VJšžœAžœ
žœžœ˜VJšžœAžœ
žœžœ˜VJšžœAžœ
žœžœ˜VJšžœAžœ
žœžœ˜VJšžœAžœ
žœžœ˜VJšžœ
žœ˜J˜——š
 ™š‘œžœ
žœžœžœ
žœ˜WJ˜*Jšžœ
žœ'žœ˜LJ˜——š
 ™š‘œžœ
žœžœ˜VJšœžœ
˜šžœžœ
žœ˜Jšœžœ$˜.J˜Jš
žœžœ
žœžœžœ
˜CJ˜—Jšžœ˜
J˜J˜—š‘œžœ
žœ+žœ˜cJ˜Jšžœžœ
žœžœ˜:Jšžœ$žœ+˜UJ˜!J˜"Jšžœ
˜J˜J™—š‘œžœ
žœ#žœ˜QJšžœ˜!Jšœžœžœ,˜@Jšœžœ˜(Jš
žœžœ
žœžœžœ
˜BJ˜J˜——š
 ™š‘œžœ
žœžœ˜ZJšœžœ
˜šžœ	žœ
žœ˜Jšœžœ$˜.J˜Jš
žœžœ
žœžœžœ
˜?J˜—Jšžœ˜
J˜J˜—š‘œžœ
žœ+žœ˜gJ˜Jšžœ	žœ
žœ	žœ˜8Jšžœ žœ)˜OJ˜J˜Jšžœ˜J˜J™—š‘œžœ
žœ#žœ˜SJšžœ˜#Jšœžœžœ*˜>Jšœžœ!˜*Jš
žœžœ
žœžœžœ
˜>J˜J˜J˜—J˜—Jšžœ
˜J˜J˜—…— ,§