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
.