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
DIRECTORY G3dBasic, G3dShape, G3dBox, G3dGrid, G3dPlane, Real;
G3dGridImpl: CEDAR PROGRAM
IMPORTS G3dShape, G3dBox, G3dPlane, Real
EXPORTS G3dGrid
~ BEGIN
Types
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;
Creation Procs
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] ~ {
Build polygon lists for each grid cell from the input shape.
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;
};
Polygon Insertion and Deletion Procs
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] ~ {
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
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];
};
Grid Visiting Procs
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;
};
Utility Procs
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;
};
Private Procs
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];
};
Auxiliary Procs
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;
};
Object Sequences
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;
};
CellData Sequences
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.