PARALLEL 3-D FILLING WITH OCTREES

There are a number of different algorithms which attempt to perform th e reconstruction of a volume representation (filling) of an object giv en some level of border representation for the object. These algorithm s usually fall into two main categories: connectivity labeling, which digitizes polygons in space and fills the corresponding enclosed volum es, and filling by quadrants or octants which finds the interior of a previously digitized border. An algorithm in the second category prese nted by Atkinson, Gargantini and Walsh encodes information within the border elements of an object indicating in which direction the outer n ormal points at that point on the edge (for 2-D objects) or surface (f or 3-D objects) of the object. This paper described a parallel algorit hm that has been developed based on this approach using the shared mem ory, multiprocessor model and reports on its implementation. (C) 1994 Academic Press, Inc.