In the past years the so-called body-centered cubic grid (bcc) has been examined and proved to be superior over Cartesian lattices for certain applications. Our work deals with parallel thinning on these bcc grids. We introduce conditions which are sufficient for retaining topology and suggest additional conditions to influence the shape of the resulting skeleton. We further developed an algorithm to extract curve skeletons out of 3d objects in parallel which we also present here. We show in our results that the developed thinning approach on bcc grids is extremely efficient.

Force fields of 3d objects are used for different purposes in computer graphics as skeletonization and collision detection. In this paper we present a novel method to approximate the force field of a discrete 3d object in linear time. Similar to the distance transformation we define a rule that describe how the forces associated with boundary points are propagated into the interior of the object. The result of this propagation depends on the order in which the points of the object are processed. Therefore we analyze how to obtain an order-invariant approximation formula. For a chosen iteration order (i, j, k) the set of boundary points that influence the force of a particular point p of the object can be described by a spatial region Rijk. The geometries of these regions are characterized both for the Cartesian and the body-centered cubic grid (bcc grid). We show that in the case of the bcc grid these regions can be combined in such a way that E3 is uniformly covered which basically means that each boundary point is contained in the same number of regions. Based on the covering an approximation formula for the force field is proposed that has linear complexity and gives good results for standard objects. We also show that such a uniform covering can not be built from the regions of influence of the Cartesian grid. With our method it becomes possible to use features of the force field for a fast and topology preserving skeletonization. We use a thinning strategy on the bcc grid to compute the skeleton and ensure that critical points of the force field are not removed. This leads to improved skeletons with respect to the properties of centeredness and rotational invariance.

In the past years the so-called body-centered cubic grid (bcc) has been examined and proved to be superior over Cartesian lattices for certain applications. Our work deals with parallel thinning on these bcc grids. We introduce conditions which are sufficient for retaining topology and suggest additional conditions to influence the shape of the resulting skeleton. We further developed an algorithm to extract curve skeletons out of 3d objects in parallel which we also present here. We show in our results that the developed thinning approach on bcc grids is extremely efficient.

Force fields of 3d objects are used for different purposes in computer graphics as skeletonization and collision detection. In this paper we present a novel method to approximate the force field of a discrete 3d object in linear time. Similar to the distance transformation we define a rule that describe how the forces associated with boundary points are propagated into the interior of the object. The result of this propagation depends on the order in which the points of the object are processed. Therefore we analyze how to obtain an order-invariant approximation formula. For a chosen iteration order (i, j, k) the set of boundary points that influence the force of a particular point p of the object can be described by a spatial region Rijk. The geometries of these regions are characterized both for the Cartesian and the body-centered cubic grid (bcc grid). We show that in the case of the bcc grid these regions can be combined in such a way that E3 is uniformly covered which basically means that each boundary point is contained in the same number of regions. Based on the covering an approximation formula for the force field is proposed that has linear complexity and gives good results for standard objects. We also show that such a uniform covering can not be built from the regions of influence of the Cartesian grid. With our method it becomes possible to use features of the force field for a fast and topology preserving skeletonization. We use a thinning strategy on the bcc grid to compute the skeleton and ensure that critical points of the force field are not removed. This leads to improved skeletons with respect to the properties of centeredness and rotational invariance.