DIRECTORY TerminalIO; ImplicitKDTreeImpl: CEDAR PROGRAM IMPORTS TerminalIO EXPORTS ImplicitKDTree ~ BEGIN Cell: TYPE ~ RECORD [ type: MajorPlane, box: Box, value: REAL, -- position of x, y, or z plane primitives: LIST OF Primitive, subCell1, subCell2: Cell ]; GetCells: PUBLIC PROC [p: Triple, tree: Cell] RETURNS [LIST OF Primitive] ~ { IF tree.subCell1 = NIL OR tre.subCel2 = NIL THEN RETURN[tree.primmitives] ELSE GetCells[sp, SELECT tree.type FROM x => IF p.x < tree.value THEN tree.subCell1 ELSE tree.subCell2, y => IF p.y < tree.value THEN tree.subCell1 ELSE tree.subCell2, z => IF p.z < tree.value THEN tree.subCell1 ELSE tree.subCell2, ENDCASE; }; MakeTree: PROC [primtivies: LIST OF Primitive, depth: NAT] RETURNS [root: Cell] ~ { type: MajorPlane ¬ x; Cut: [mp: MajorPlane] ~ { FOR l: LIST OF Primitive ¬ primitives, l.rest WHILE l # NIL DO }; END. f ImplicitKDTreeImpl.mesa Copyright Σ 1990 by Xerox Corporation. All rights reserved. Bloomenthal, August 11, 1992 4:07 pm PDT Types Public Procedures sort cut at medain plane, makje .box FOR l: LIST OF Primitives ¬ primitives, l.rest WHILE l # NIL DO FOR each of 8 corners if point in .box, or .box.corner in primitive.box, then add primitive to cell ΚΙ•NewlineDelimiter ™™Jšœ<™J™J™™?™J™M————J˜J˜——Jšœ˜—…—t£