Generalized Distance Functions
|
Ergun Akleman Visualization Laboratory Department of Architecture Texas A&M University |
Jianer Chen Department of Computer Science Texas A&M University |
Extended Abstract
Abstract
In this paper, we obtain a generalized version of
the well-known distance function family Lp norm. We prove
that the new functions satisfy distance function properties.
By using these functions, convex symmetric shapes can
be described as loci, the set of points
which are in equal distance from a given point.
We also show that these symmetric convex shapes can
be easily parameterized. We also show
these distance functions satisfy a Lipschitz type Condition.
We provide a fast ray marching algorithm
for rendering shapes described by these distance functions.
These distance functions can be used as building
blocks for some implicit modeling tools such
as soft objects, constructive soft geometry, freps or ray-quadrics.
Motivation
The concept of distance function has been developed to provide a formal description for measuring distance between two points in a vector space. Any function which satisfies the following logical conditions for distance can be used for measuring distance in a vector space.
There exist various distance functions defined over different vector spaces such as Lp norm, Hausdorf-Besicowitch distance, and Hamming distance. Lp norm is a particularly interesting distance function for modeling shapes. Lp norm is based on the Minkowski operators. These operators satisfy well-known Minkowski's inequality. Interested readers can find a proof for this inequality in many classical mathematics textbooks. Loci defined by Lp norm in 3-dimension gives shapes including octahedron, sphere and cube as shown in Figure 1.
|
|
| Figure 1: Loci described by Lp norm. |
The Minkowski operators have been used in implicit shape modeling in quite a long time. Ricci extended these operators by including negative p values and obtained exact and approximate set operations which we call Ricci operators. Barr, independently, has developed superquadrics by using Minkowski operators. Hanson also used Minkowski operators to generalize superquadrics to Hyperquadrics. Akleman developed ray-linears, a function family that provide fast computation and closed under Ricci operators. Wyvill has developed Constructive Soft Geometry also by using Ricci's operators. Even Rvachev's exact set operations are related to Minkowski operators. Distance functions are also useful to generate implicit field functions from various types of shape information. In this paper, we obtain new distance functions also using Minkowski operations.
Properties of Generalized Distance Functions
|
| Figure 2.a: Loci described by octahedral distance. |
|
| Figure 2.b: Loci described by dodecahedral distance. |
|
| Figure 2.c: Loci described by icosahedral distance. |
|
| Figure 2.d: Loci described by truncated icosahedral distance. |
|
| Figure 2.e: Loci described by truncated octahedral distance. |
1) Locus of all the points which have equal distance to a given point gives various symmetric convex shapes when different distance functions are used. Examples of such shapes are shown in Figure 2.
2) The loci defined by using generalized distance functions can be computed extremely fast and interactively be modified.
3) Since the loci can be modified interactively, they can be used as building blocks in constructive (either solid or soft) geometry. In this way, the user can have an approximate idea how the overall shape will look like, before rendering the whole shape.
4) The new distance functions we propose extend the number of building blocks considerably by including every symmetric convex polyhedra and their approximation.
5) The distance functions satisfy a Lipschitz type condition. This condition provides a fast ray marching method for rendering shapes described by these distance functions.
Discussion and Conclusion
We obtain a generalized version of the well-known distance function family Lp norm. We prove that the new functions satisfy distance function properties. By using this functions, convex symmetric shapes can be described as loci, the set of points which are in equal distance from a given point. We also show that these symmetric convex shapes can be easily parameterized. We also show these distance functions satisfy a Lipschitz type Condition. We provide a fast ray marching algorithm for rendering shapes described by these distance functions. These distance functions can also be used as building blocks.
We remark that the techniques presented for simple loci are also applicable for the generation of non-symmetric convex shapes. In order to create non-symmetric convex shapes from symmetric convex hyperquadrics, Hanson observed that non-symmetric shapes can be obtained by intersecting the symmetric convex shapes with a lower dimensional hyperplane. For instance, the intersection of plane with a cube can create triangles, quadrilaterals and pentagons. The same idea can also be used to obtain non-symmetric convex 3D shapes by intersecting 4D simple loci with a 3D hyperplane. Moreover, The resulting shapes can still be computed by using the ray marching algorithm we presented.