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;
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;
};