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.

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.