<<>>
<<ImplicitStorageImpl.mesa>>
<<Copyright Š 1992 by Xerox Corporation.  All rights reserved.>>
<<Bloomenthal, January 2, 1993 2:59 pm PST>>

DIRECTORY Basics, G3dBasic, G3dMatrix, G3dTriangle, G3dVector, ImplicitStorage;

ImplicitStorageImpl: CEDAR PROGRAM
IMPORTS Basics, G3dMatrix, G3dVector
EXPORTS ImplicitStorage

~ BEGIN
<<Types and Constants>>
IntegerPair:            TYPE ~ G3dBasic.IntegerPair;
Triple:                TYPE ~ G3dBasic.Triple;
Matrix:                TYPE ~ G3dMatrix.Matrix;
Viewport:                TYPE ~ G3dMatrix.Viewport;
IntTriple:                TYPE ~ G3dTriangle.IntTriple;

Centers:                TYPE ~ ImplicitStorage.Centers;
ID:                    TYPE ~ ImplicitStorage.ID;
IDs:                    TYPE ~ ImplicitStorage.IDs;
Edge:                    TYPE ~ ImplicitStorage.Edge;
Edges:                TYPE ~ ImplicitStorage.Edges;
Face:                    TYPE ~ ImplicitStorage.Face;
Faces:                    TYPE ~ ImplicitStorage.Faces;
Vertices:                TYPE ~ ImplicitStorage.Vertices;
<<Vertices>>
ScreenPick: PUBLIC PROC [p: IntegerPair, vertices: Vertices, view: Matrix, vp: Viewport]
RETURNS [vid: INT Ź -1]
~ {
dist, max: INTEGER Ź 1000000;
hasPersp: BOOL Ź G3dMatrix.HasPerspective[view];
FOR i: INTEGER IN [0..vertices.length) DO
pp: IntegerPair Ź G3dMatrix.GetScreen[vertices[i].point, view, hasPersp, vp].intPos;
d: IntegerPair _ [p.x-pp.x, p.y-pp.y];
IF (dist _ d.x*d.x+d.y*d.y) < max THEN {max _ dist; vid _ i};
ENDLOOP;
};
<<Sparse 3d Storage>>
hashNBits:     INT ~ 5;
hashMask:    INT ~ Basics.BITSHIFT[1, hashNBits]-1;
hashSize:        INT ~ Basics.BITSHIFT[1, 3*hashNBits];
<<>>
GetHashSize: PUBLIC PROC RETURNS [INT] ~ {RETURN[hashSize]};
HashAnd: PROC [i: INT] RETURNS [j: WORD] ~INLINE {jŹBasics.BITAND[ABS[i],hashMask]};
HashShift: PROC [i: INT] RETURNS [j: WORD] ~ INLINE {jŹBasics.BITSHIFT[i, hashNBits]};

Hash: PUBLIC PROC [i: IntTriple] RETURNS [id: INT] ~ { -- courtesy Wyvill, Wyvill & Cleary
id Ź
Basics.BITOR[
HashShift[
Basics.BITOR[
HashShift[HashAnd[i.i]], 
HashAnd[i.j]]],
HashAnd[i.k]];
};

NewCenters: PUBLIC PROC RETURNS [centers: REF Centers] ~ {
centers Ź NEW[Centers[GetHashSize[]]];
FOR i: INT IN [0..centers.length) DO centers[i] Ź NIL; ENDLOOP;
};

NewIDs: PUBLIC PROC RETURNS [ids: REF IDs] ~ {
ids Ź NEW[IDs[GetHashSize[]]];
FOR i: INT IN [0..ids.length) DO ids[i] Ź NIL; ENDLOOP;
};

NewEdges: PUBLIC PROC RETURNS [edges: REF Edges] ~ {
edges Ź NEW[Edges[2*GetHashSize[]]];
FOR i: INT IN [0..edges.length) DO edges[i] Ź NIL; ENDLOOP;
};

NewFaces: PUBLIC PROC RETURNS [faces: REF Faces] ~ {
faces Ź NEW[Faces[3*GetHashSize[]]];
FOR i: INT IN [0..faces.length) DO faces[i] Ź NIL; ENDLOOP;
};

AddCenter: PUBLIC PROC [centers: REF Centers, i: IntTriple] RETURNS [b: BOOL Ź FALSE] ~ {
index: INT Ź Hash[i];
list: LIST OF IntTriple Ź centers[index];
FOR l: LIST OF IntTriple Ź list, l.rest WHILE l # NIL DO
IF l.first = i THEN RETURN[TRUE];
ENDLOOP;
centers[index] Ź CONS[i, list];
};

SubCenter: PUBLIC PROC [centers: REF Centers, id: IntTriple] ~ {
prev: LIST OF IntTriple Ź NIL;
index: INT Ź Hash[id];
FOR l: LIST OF IntTriple Ź centers[index], (prev Ź l).rest WHILE l # NIL DO
IF l.first # id THEN LOOP;
IF prev = NIL THEN centers[index] Ź l.rest ELSE prev.rest Ź l.rest;
EXIT;
ENDLOOP;
};

Order2: PUBLIC PROC [i1, i2: IntTriple] RETURNS [IntTriple, IntTriple] ~ {
IF i1.i > i2.i OR (i1.i = i2.i AND (i1.j > i2.j OR (i1.j = i2.j AND i1.k > i2.k)))
THEN RETURN[i2, i1]
ELSE RETURN[i1, i2];
};

SetID: PUBLIC PROC [ids: REF IDs, location: IntTriple, vid: INT] ~ {
index: INT Ź Hash[location];
ids[index] Ź CONS[[location, vid], ids[index]];
};

GetID: PUBLIC PROC [ids: REF IDs, location: IntTriple] RETURNS [i: INT Ź -1] ~ {
FOR l: LIST OF ID Ź ids[Hash[location]], l.rest WHILE l # NIL DO
IF l.first.id = location THEN RETURN[l.first.vid];
ENDLOOP;
};

SetEdge: PUBLIC PROC [edges: REF Edges, i1, i2: IntTriple, vid: INT] ~ {
index: INT;
[i1, i2] Ź Order2[i1, i2];
index Ź Hash[i1]+Hash[i2];
edges[index] Ź CONS[[i1, i2, vid], edges[index]];
};

GetEdge: PUBLIC PROC [edges: REF Edges, i1, i2: IntTriple] RETURNS [i: INT Ź -1] ~ {
[i1, i2] Ź Order2[i1, i2];
FOR l: LIST OF Edge Ź edges[Hash[i1]+Hash[i2]], l.rest WHILE l # NIL DO
IF l.first.i1 = i1 AND l.first.i2 = i2 THEN RETURN[l.first.vid];
ENDLOOP;
};

Order3: PUBLIC PROC [i1, i2, i3: IntTriple] RETURNS [r1, r2, r3: IntTriple] ~ {
Greater: PROC [a, b: IntTriple] RETURNS [r: BOOL] ~ {
r Ź a.i > b.i OR (a.i = b.i AND (a.j > b.j OR (a.j = b.j AND a.k > b.k)));
};
Inner: PROC [i1, i2, i3: IntTriple] ~ {r1 Ź i1; [r2, r3] Ź Order2[i2, i3]};
IF Greater[i1, i2]
THEN {IF Greater[i1, i3] THEN Inner[i1, i2, i3] ELSE Inner[i3, i1, i2]}
ELSE  {IF Greater[i2, i3] THEN Inner[i2, i1, i3] ELSE Inner[i3, i1, i2]};
};

SetFace: PUBLIC PROC [faces: REF Faces, i1, i2, i3: IntTriple, vid: INT] ~ {
<< [Artwork node; type 'Artwork on' to command tool] >>
<<If face (i1, i2, i3) is already stored, add vid to its list; otherwise, store a new face.>>
index: INT;
[i1, i2, i3] Ź Order3[i1, i2, i3];
index Ź Hash[i1]+Hash[i2]+Hash[i3];
FOR l: LIST OF Face Ź faces[index], l.rest WHILE l # NIL DO
IF l.first.i1 = i1 AND l.first.i2 = i2 AND l.first.i3 = i3 THEN
FOR vIDs: LIST OF INT Ź l.first.vIDs, vIDs.rest DO
IF vIDs.rest = NIL THEN {vIDs.rest Ź LIST[vid]; RETURN};
ENDLOOP;
ENDLOOP;
faces[index] Ź CONS[[i1, i2, i3, LIST[vid]], faces[index]];
};

GetFace: PUBLIC PROC [
faces: REF Faces,
i1, i2, i3: IntTriple,
p: Triple,
vertices: Vertices]
RETURNS [id: INT Ź -1]
~ {
<<If a vertex of the same location is stored on this face, return its id; else, return -1.>>
FOR vIDs: LIST OF INT Ź GetAllFaceIDs[faces, i1, i2, i3], vIDs.rest WHILE vIDs # NIL DO
IF G3dVector.Equal[vertices[vIDs.first].point, p] THEN RETURN[vIDs.first];
ENDLOOP;
};

GetAllFaceIDs: PUBLIC PROC [
faces: REF Faces,
i1, i2, i3: IntTriple]
RETURNS [ids: LIST OF INT Ź NIL]
~ {
[i1, i2, i3] Ź Order3[i1, i2, i3];
FOR l: LIST OF Face Ź faces[Hash[i1]+Hash[i2]+Hash[i3]], l.rest WHILE l # NIL DO
IF l.first.i1 = i1 AND l.first.i2 = i2 AND l.first.i3 = i3 THEN RETURN[l.first.vIDs];
ENDLOOP;
};

END.