On Thu, 14 Sep 2000 07:09:50 -0500, Chris Huff wrote:
>In article <slr### [at] fwicom>, ron### [at] povrayorg 
>wrote:
>
>> Yes, but you'd need an efficient data structure to find the closest 
>> center to a given sample point quickly.  Fortunately, I've done some 
>> work in that field (though in 2D) so I have some ideas on how it 
>> might be done.
>
>Any suggestions? I am thinking of it as an addition to the blob pattern, 
>which has several more component types than the blob object. Could this 
>data structure also handle line(cylinder) components? Of course, just 
>having it available for the spherical components(and components that can 
>be approximated by spheres) would help...

The code I had (in 2d) used a quadtree to store the points, and another to
store the lines.  Points are simple: find the quadtree node that contains
the sample point, and search it for closer points.  If any edges are closer
than the closest point, search the quadtree node on that side for closer
points as well.  If any corners are closer, search the node diagonally
adjacent to the current node as well.  Continue for all edges and corners
of all tested nodes, until none are closer than the closest point found.
(This is easier than it looks, due to the structure of a quadtree.)  For 3d,
of course, you'd use an octree, and you'd generalize the above description 
to faces, edges, and corners of an octree node.

To store lines, you have to corrupt the quadtree structure a bit by storing
lines that are too long to fit entirely in a leaf node in the interior nodes
of the tree.  The procedure is the same, though, with the caveat that you must
also search all ancestor nodes of any leaf node you search.  This structure 
is not as efficient as the one for points unless your line segments are all 
very small, with the possible exception of a few large ones.  In my case,
working with digital cartography, this was true.  In the case of a blob, it
may not be.  You may need to modify the criteria you use to split (for example,
it may make more sense to break the nodes on one axis at a time rather than 
all at once.)

If you generalize to 3d, it should become obvious that the same strategy
that works for line segments will work for polygons.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message