On Fri, 18 Feb 2000 19:44:17 +0200, Margus Ramst <mar### [at] peakeduee>
wrote:

>Yes, but construct such a tree I would still have to test all points against the
>current one, no? I can't construct the tree at generation time, because
>consequent points are not necessarily spatially close (I'm talking about an
>actual case here).

Try this approach. Let's assume it's points we're working with though
things won't change much for objects:

1. Find the smallest box that encloses all points
2. Put all x-coords in an array and sort it. Do this for y and z as
well.
3. Get the middle point of each array (x,y and z) and form a vector
4. Divide the initial bounding box into eight bounding boxes using the
vector from point 3
5. Recursively repeat the procedure for each child of the parent
bounding box until a recursion limit is reached or no further
subdivision is pointless

Each parent will bound its children. Only the leafs of the oct-tree
will bound actual objects.

Does this make any sense to anyone?


Peter Popov
pet### [at] tagpovrayorg
ICQ: 15002700

Post a reply to this message