ImplicitKDTreeImpl.mesa
Copyright Ó 1990 by Xerox Corporation. All rights reserved.
Bloomenthal, August 11, 1992 4:07 pm PDT
DIRECTORY TerminalIO;
ImplicitKDTreeImpl:
CEDAR
PROGRAM
IMPORTS TerminalIO
EXPORTS ImplicitKDTree
~
BEGIN
Types
Cell:
TYPE ~
RECORD [
type: MajorPlane,
box: Box,
value:
REAL,
-- position of x, y, or z plane
primitives:
LIST
OF Primitive,
subCell1, subCell2: Cell
];
Public Procedures
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
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
};
END.