DIRECTORY Basics, G3dBasic, G3dMatrix, G3dTriangle, G3dVector, ImplicitStorage; ImplicitStorageImpl: CEDAR PROGRAM IMPORTS Basics, G3dMatrix, G3dVector EXPORTS ImplicitStorage ~ BEGIN 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; 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; }; 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] ~ { 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] ~ { 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. ž ImplicitStorageImpl.mesa Copyright c 1992 by Xerox Corporation. All rights reserved. Bloomenthal, January 2, 1993 2:59 pm PST Types and Constants Vertices Sparse 3d Storage [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. If a vertex of the same location is stored on this face, return its id; else, return -1. ÊDñ•NewlineDelimiter ™™Jšœ Ïmœ1™Ä@Ô5Ä­òwã¡’˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r j  Š ªÄx •ÄeÖ=Ä“®ÄÙR¡£À  £¡ ” ç­“¡¯“¢°“¢·“ÄH9YÄ)ã™ÄKï\Ä7H!Ä\QnĬ„gzÄ[¡’Ä>MHÄ<ƒ$Ä2ß:ÄE4)„Q¡’Ä Õ ÄxPGÄy×…ÄxWGÄyăR¡’˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄ:ËzŠ ªÄàB»Äß³Ä!+ò£¡£À  £¡ ” ç­“¡¯“¢°“¢·“Äp]Ä8‘ÙÄeLŽ˜ k é kÄ¡¨ ¡ ¡™ x j r jÄ:ËzŠ ªÄ «ÄgÏBÄ$MÄ ¡£À  £¡ ” ç­“¡¯“¢°“¢·“ÄB¼kÄ8‘ÙÄ™ã[ŽÄ4!˜ k é kÄ¡¨ ¡ ¡™ x j r jÄ:ËzŠ ª@Ä%ú}£¡£À  £¡ ” ç­“¡¯“¢°“¢·“ÄCÄí™Äei;Ž˜ k é kÄ¡¨ ¡ ¡™ x j r jÄ!‘ØÄ:ËzŠ ª@Ä%ú}£¡£À  £¡ ” ç­“¡¯“¢°“¢·“ÄCÄí™Äei;Ž˜ k é kÄ¡¨ ¡ ¡™ x j r jÄ"ÕlÄ:ËzŠ ª@Ä%ú}£¡£À  £¡ ” ç­“¡¯“¢°“¢·“ÄCÄí™Äei;Ž˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r j  Š ªÄÁ*Ä5ßÄ#£¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä €Äl>™ÄH9YŽ˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r j ÄòhŠ ªÄÁ*Ä5ßÄ#£¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä €Äl>™ÄH9YŽ˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r j ÄÒÑÓŠ ªÄÁ*Ä5ßÄ#£¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä €Äl>™ÄH9YŽ˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r j Äá«ÑŠ ªÄÁ*Ä5ßÄ#£¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä €Äl>™ÄH9YŽ˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r j Ä¥¢ÓŠ ªÄÁ*Ä5ßÄ#£¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä €Äl>™ÄH9YŽ˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r j  Š ªÄÁ*Ä¢£ÄkP¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä €Ä M™Äl>˜ k é k x jÅxeroxÅxc1-2-2ÅModern£¡ “¡•¡ —  À£¡ ” ç­“Äew ¤Ä},Äæyƒ ¢ ¥ ¨  Š¡²“Áfaces– k x jÅxeroxÅxc1-2-2ÅModern£¡ “¡•¡ —  À£¡ ” ç­“Äew ¤Ä}ÄiUC ¢ ¥ ¨  Š¡²“Á. . .– k x jÅxeroxÅxc1-2-2ÅModern£¡ “¡•¡ —  À£¡ ” ç­“Äew ¤Ä4Ü_ÄCâ) ¢ ¥ ¨  Š¡²“Á LIST OF Face– k  À£¡ ” ç­“ ¡ ¡™ x j r j  Š ªÄx •Ä¢£ÄkP¡£  À£¡ ” ç­“¡¯“¢°“¢·“ÄH9YÄl>™Ä M˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄ0€Äö·eŠ ªÄÁ*Ä5ßÄ#£¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä €Äl>™ÄH9YŽ˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄ:ËzŠ ªÄõÄ|OÄ0°Äã¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä{MƒÄ*û¸™ÄI~ÑÄp]Ž˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄ:ËzŠ ªÄàB»Ä|O£Äã¡£  À£¡ ” ç­“¡¯“¢°“¢·“Äp]ÄI~Ñ™Ä*û¸˜ k é k x jÅxeroxÅxc1-2-2ÅModern£¡ “¡•¡ —  À£¡ ” ç­“Äew ¤Ä®ïºÄA†' ¢ ¥ ¨  Š¡²“Ái1, i2, i3, vIDs– k  À£¡ ” ç­“ ¡ ¡™ x j r jÄZ8uÄö·eŠ ªÄÁ*Ä5ßÄ#£¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä €Äl>™ÄH9YŽ˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄå:Ä:ËzŠ ªÄõÄ|OÄ0°Äã¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä{MƒÄ*û¸™ÄI~ÑÄp]Ž˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄå:Ä:ËzŠ ªÄàB»Ä|O£Äã¡£  À£¡ ” ç­“¡¯“¢°“¢·“Äp]ÄI~Ñ™Ä*û¸˜ k é k x jÅxeroxÅxc1-2-2ÅModern£¡ “¡•¡ —  À£¡ ” ç­“Äew ¤ÄNt;ÄA†' ¢ ¥ ¨  Š¡²“Ái1, i2, i3, vIDs– kÄ¡¨ ¡ ¡™ x j r jÄ:ËzŠ ªÄkåAÄ®ñºÄ,êÑ£¡£À  £¡ ” ç­“¡¯“¢°“¢·“ÄyšIÄXÄÝ™Äx%FŽ˜ k é kÄ¡¨ ¡ ¡™ x j r jÄ:ËzŠ ªÄ˜´[ÄK=1Ä ]£¡£À  £¡ ” ç­“¡¯“¢°“¢·“Ä£WaÄTÆ7™Äb:Ž˜ k é kÄ¡¨ ¡ ¡™ x j r jÄ:ËzŠ ªÄÇ–yÄgÏBÄ6gŽ£¡£À  £¡ ” ç­“¡¯“¢°“¢·“Ä—òÄ4!™Äs²CŽ˜ k é k x jÅxeroxÅxc1-2-2ÅModern£¡ “¡•¡ —  À£¡ ” ç­“Äew ¤âÄ( ¢ ¥ ¨  Š¡²“Á(LIST OF INTEGER)– k  À£¡ ” ç­“ ¡ ¡™ x j r jÄää“ÄUŠ ªÄDÄíñ©Ä)qÈ£¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä&»"ÄÏÔ“™Är…^Ž˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄää“ÄUŠ ªÄDÄÄ)qÈÄs3¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä&»"ÄÏÔ“™Ä9Y*Är…^Ž˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄV”ÄóUŠ ªÄàB»Ä|O£Äã¡£  À£¡ ” ç­“¡¯“¢°“¢·“Äp]ÄI~Ñ™Ä*û¸˜ k é k x jÅxeroxÅxc1-2-2ÅModern£¡ “¡•¡ —  À£¡ ” ç­“Äew ¤Ä¹ Ä‚èU ¢ ¥ ¨  Š¡²“Áid– k  À£¡ ” ç­“ ¡ ¡™ x j r jÄ ÄUŠ ªÄDÄíñ©Ä)qÈ£¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä&»"ÄÏÔ“™Är…^Ž˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄ ÄUŠ ªÄDÄÄ)qÈÄs3¡£  À£¡ ” ç­“¡¯“¢°“¢·“Ä&»"ÄÏÔ“™Ä9Y*Är…^Ž˜ k é k  À£¡ ” ç­“ ¡ ¡™ x j r jÄkÄóUŠ ªÄàB»Ä|O£Äã¡£  À£¡ ” ç­“¡¯“¢°“¢·“Äp]ÄI~Ñ™Ä*û¸˜ k é k x jÅxeroxÅxc1-2-2ÅModern£¡ “¡•¡ —  À£¡ ” ç­“Äew ¤Ä~æCÄ‚èU ¢ ¥ ¨  Š¡²“Áid– kÄ¡¨ ¡ ¡™ x j r jÄ%!jÄ÷Y·Š ªÄkåAÄ®ñºÄ,êÑ£¡£À  £¡ ” ç­“¡¯“¢°“¢·“ÄyšIÄXÄÝ™Äx%FŽ˜ k é kÄ¡¨ ¡ ¡™ x j r jÄ%!jÄ÷Y·Š ªÄ˜´[ÄK=1Ä ]£¡£À  £¡ ” ç­“¡¯“¢°“¢·“Ä£WaÄTÆ7™Äb:Ž˜ k é kÄ¡¨ ¡ ¡™ x j r jÄ$gÄãÆUŠ ªÄÇ–yÄgÏBÄ6gŽ£¡£À  £¡ ” ç­“¡¯“¢°“¢·“Ä—òÄ4!™Äs²CŽ˜ k é kÄ¡¨ ¡ ¡™ x j r jÄ:ËzŠ ªÄdP1Ä%A£Ä ¡£À  £¡ ” ç­“¡¯“¢°“¢·“Äpë7Äí™Ä´ ˜ k é k k k gš¡3™3J™YJšœžœ˜ J˜"J˜#š žœžœžœžœžœž˜;šžœžœžœž˜?š žœžœžœžœž˜2Jš žœ žœžœžœžœ˜8Jšžœ˜——Jšžœ˜—Jšœžœžœ˜;Jšœ˜J˜—š¡œž œ˜Jšœžœ˜J˜J˜ J˜Jšžœžœ˜J˜J™Xš žœžœžœžœ/žœžœž˜WJšžœ0žœžœ ˜JJšžœ˜—J˜J˜—š¡ œž œ˜Jšœžœ˜J˜Jš žœžœžœžœžœ˜ J˜J˜"š žœžœžœ2žœžœž˜PJš žœžœžœžœžœ˜UJšžœ˜—J˜——J˜Jšžœ˜J˜J˜—…—j[ù