The generalized Voronoi...

Figure 1: Two example applications of the approximated generalized Voronoi diagram (GVD) computed by our novel, adaptive algorithm. Previous GVD methods require a gridded space of 224 (gears dataset) and 236 (knives dataset) voxels to resolve the closely spaced objects. (a) Two gears with regions of very tight spacing. (b) The GVD of the gears model. The surface is colored red in areas of very close tolerance. (c) Three butter knives in a wood block. To animate removal of the knives without intersecting the block requires extreme care because of close mesh spacing. (d) Intersection-free motion is guaranteed by computing motion vectors based on the GVD and allowing motion only within a Voronoi cell. We present an algorithm to compute an approximation of the generalized Voronoi diagram (GVD) on arbitrary collections of 2D or 3D geometric objects. In particular, we focus on datasets with closely spaced objects; GVD approximation is expensive and sometimes intractable on these datasets using previous algorithms. With our approach, the GVD can be computed using commodity hardware even on datasets with many, extremely tightly packed objects. Our approach is to subdivide the space with an octree that is represented with an adjacency structure. We then use a novel adaptive distance transform to compute the distance function on octree vertices. The computed distance field is sampled more densely in areas of close object spacing, enabling robust and parallelizable GVD surface generation. We demonstrate our method on a variety of data and show exampl