A Novel Representation
of 3D Shapes Based on Modified Sphere Equation
Computer Graphics Group
Technical University of Szczecin
Szczecin / Poland
|
1. Introduction 3. Mathematical Interpretation 4. Using GSE Models in Ray
Tracing 6. Conclusions and Future Work 7. References |
1. Introduction
The blob term is used with
reference to 3D models with smooth shapes. This paper discusses a new method of
obtaining models which are generalization of classical blobs. The method has
been called GSE (Generalized Sphere Equation). The GSE models differ
significantly, depending on parameters which have influence on their shape,
size and specific surface bumps. The simplest variant of GSE method allows to
obtain the classical blobs. This paper discusses the input data, mathematical
interpretation and solutions which allow to render pictures of GSE models using
ray tracing method.
Blob models are described as three-dimensional
surfaces. There are two classifications of such surfaces: parametric and
implicit.
Parametric surface is a set of points generated by three
functions of given number of variables. For example, bivariate parametric
surfaces are generated by functions of two variables: fx(i,j), fy(i,j),
fz(i,j).
Implicit surface is a set of points which satisfy some equation
in the three-dimensional space:
F(x,y,z)=0.
Implicit surface whose equation is of the second
degree has been called quadric surfaces. (This term is also used with curves.)
Thus, surface equation is:
Depending on values of parameters A, B, …, J
equation 1 can describe plane, sphere, cone, cylinder, and the like.
Next chapter examines how the surfaces allied
to quadrics have been used to making blobs. Section 3 includes the input data and the
mathematical interpretation of the GSE method. In section 4 the usage of GSE method in ray
tracing is discussed. There is description of implementation and results in section 5. The last
chapter includes consclusions and
discussions of future work.
2.1 J. F. Blinn's method
The first blobs were generated in 1982, when
James F. Blinn used a method allied to quadric surfaces to solve the problem of
computer aided visualization of molecular model.
In [1],
a physical interpretation is given for mathematical solutions used. According
to quantum mechanics, the electron in an atom can be represented as a density
function of the spatial location. For a hydrogen atom, density function is:
where
,
(x1, x2, x3)
is the center of an atom.
According to superposition theorem, density
function can be used for many atoms. Thus the sum of density contributions of
each atom should be taken into account:
where ri is the distance from
(x, y, z) to the center of atom i.
A molecular surface can be defined as a set of
points where density function equals some threshold value T. Using
implicit surface definition a molecular surface can be described as:
In above equation bi has been
specified in term of a blobbines parameter Bi.
[1]
describes how to obtain the pictures of Blinn's blobs using ray tracer.
Deriving ray equation begins with the various transformations into a standard
viewing space. Reciprocal transformations let calculate viewing ray equation
for each pixel on the screen. For each point of the ray, coordinates x and
y depend on the z coordinate. Thus, calculating the z coordinate
is enough to get the ray and surface intersection. J. F. Blinn has divided z
value calculating into two phases:
1.
Root
isolation phase: finding the range in which is a solution. In Blinn's solution
for each viewing ray, a list of n values: z1, z2 ...
zn-1 is made. The zi value is a z
coordinate of this point on the ray in which atom i has the biggest influence Di
on density function D. The list of z0, z1 ... zn-1
values is sorted in ascending order. The list is searched for the first
value zi for which Di(zi) is
greater than or equals T. Thus, <zi-1, zi>
is a required range for numeric methods of finding zeros.
2.
Root
refinement phase: finding a solution in a given range (using general numeric
methods of finding zeros, like Newton method or regula falsi method).
Blinn suggested using combination of two numeric methods of finding zeros:
Newton method and regula falsi method.
The surface normal at a given point can be found
by taking the gradient of the surface defining function, F:
Described method in previous chapter works well
for small number of atoms (a few dozen). Yet it is much to slow when number of
atoms is in the order of a few thousands. That is why the algorithm has been
optimized.
The idea is based on the fact that only a part
of atoms have influence on surface and ray intersection. Thus, the calculation can
be limited to these atoms which are close enough to the viewing ray. Each atom
could then be enclosed in a sphere. The enclosing spheres of all atoms are
projected into screen space. Thus, it is possible to find atoms which can have
influence on the color of each pixel.
2.2 Other solutions for
Blinn’s method
The solutions of optimizing the algorithm of
ray tracing implicit surfaces are described in [3].
While looking for intersection of viewing ray and
implicit surface it is usually not possible to use an analytical method. That
is because surface functions are very complicated as it was in case of the
function H in J. F. Blinn’s method.
The solution is to use a numeric analysis.
Usually, modifications or combinations of classical numeric methods are used,
preceded by necessary transformations. Authors follow J. F. Blinn and divide
calculations into root isolation phase and root refinement phase. Next two
subsections describe two methods of optimizing the root isolation phase.
One of the methods of optimizing the root
isolation phase is to approximate the complicated implicit function with a
polynomial. In 1986, Geoff Wyvill suggested the approximation by the polynomial
function C(r2):
The received models have been called soft
objects. They are described in [2].
[5]
describes how to use method taken from numerical analysis in root isolation
phase. The method is called interval analysis and originated in 1966 [6].
To start the interval analysis, a function and
a bracket of arguments must be given. The method narrows given bracket down to
new bracket in which function is monotonic and has zero.
Let’s start description of the interval
analysis with some definitions.
Def. An interval [a, b] is an ordered
pair a≤b representing the range of numbers {x:a≤x≤b}.
Several operations on intervals were defined:
addition, subtraction, multiplication, division, squaring, exponentation. They
allowed to calculate the value of Blinn’s surface function when the argument is
a given interval.
Interval analysis consists in the following
algorithm:
1.
Calculating
the interval [s0, s1]=H[t0,
t1].
2.
If 0Ï[ s0, s1], it
means that in the bracket <t0, t1>
function doesn’t have zeros. The algorithm is finished with the adequate
communicate.
3.
Calculating
the interval: [r0, r1]=H[t0,
t1].
4.
If 0Ï[r0, r1],
it means that the function f is monotonic in bracket <t0;
t1>. The algorithm is finished and the <t0, t1>
bracket is returned.
5.
Back
to first step for intervals: [t0, t0+½(t0+t1)]
and [t0+½(t0+t1), t1].
Realization of above algorithm gives monotonic
segment of the function, so then the root refinement phase can start.
3. Mathematical Interpretation of GSE (Generalized Sphere
Equation) Method
The idea of GSE method
is based on observation that sphere is a set of points which distance from one
point (center) is constant whereas ellipsoid is a set of points which sum of
distances from two points is constant. The idea is to generalize this principle
for three, four or more points. Thus, the generalized sphere equation is:
where
,
(x, y, z) is the point on
the surface,
(xi, yi, zi)
is the ith equivalent of the center.
We assume that the models made using GSE method meet the following
conditions:
1)
The
model surface should be determined by a set of points,
2)
The
model should have soft shape,
3)
The gravity
points should have only a local influence on the shape of model (to make
modeling intuitive).
The models described by
equation 3 meet the conditions first and second, but the condition third which
concerns local influence of the gravity point on the model shape is not met.
So, the GSE model equation has been expanded to:
where
Derivation of the equation 4 can be found under 3.2 . The accurate meaning of f(di),
g(di) and φi
is explained in 3.1.
In case when n=1, φ0=1, f(di)=1,
g(di)=0 we result in a sphere equation (or circle on the
plane) where the radius equals d:
3.1 Input Values
Every model is described by:
§
set
of n (n≥1) gravity
points {(x0, y0, z0),
..., (xi, yi, zi),
..., (xn-1, yn-1, zn-1),
} in the 3D space,
§
set of
weights {φ0, ... φi, ..., φn-1},
φi Ì<-1;1>,
§
d parameter determining size of the
model,
§
pair of
functions f and g describing the shape and the
bumps of the model, respectively.
The gravity points describe shape of the model. Every intersection of
the model is a closed curve of soft shape or set of such curves (fig. 1). The weights
describe influence of every single point on shape of the model. Weights range
from –1 to 1, both inclusive. In fig.
2 there are model intersections with the gravity points marked. The d
parameter determines size of the model. The larger the model, the smaller the
influence of each gravity point (fig.
3). The functions f and
g are described in section 3.1.1.
|
|
|
Figure 2: The influence of the weights assigned to the gravity points on the model
shape (intersections). The size of each dot is proportional to the absolute
value of the weight, while the color means sign of the weight: red –
positive, blue – negative |
|
|
|
Figure 3: The influence of the d parameter on the model size and shape
(intersections) |
The function f describes the overall shape of the
model. It’s arguments are d0, d1, d2
... dn-1. di stands for the
distances between a given surface point and the ith gravity point. For
the model to have expected shape, the function
f should have smooth graph. Example
equations that meet both conditions are shown below. Moreover, the function f should assign lower values to the further gravity points. (dmax
stands for the distance between given surface point and the furthest gravity
point).
|
a) |
|
|
b) |
|
|
c) |
|
|
a) for
k=2
|
b) for
A=-3
|
c)
|
|
Figure 4: The influence of the function f on the model shape (intersections) |
||
The function
g describes the surface bumps. In previous examples, the function g was constant and
equal to 0. In fig. 5
an example of a model with non-constant function
g is shown. The intersection of the same model for g=0 is marked
with red.
|
|
|
Figure 5: Intersection (on left) and draft 3D image of model with non-constant function |
Let’s exchange the sum on the left side of equation (1) with the
weighted average:
Coefficients w(d0)... w(dn-1) should meet
the following conditions:
1)
The
coefficients should be chosen so that the gravity points located closer to a
given point of the surface have more influence on it’s location than further
gravity points.
2)
The
coefficients should depend on weights φi assigned to
each gravity point.
3)
The
coefficients should allow modifying surface bumps described by the function g.
The first condition means that coefficients should have the greatest
values for the nearest gravity points and the smallest values for the furthest
ones. An example solution is the inverted square of the distance:
Let’s generalize and replace the inverted square of the distance with
any function f (see section
3.1) that meets the first condition:
To meet the second condition, value of each coefficient should be
determined by a weight assigned to each gravity point:
To meet the third condition, we need to take into consideration the
surface bumps described by the function
g (see section 3.1).
|
|
|
|
|
,
|
|
|
|
|
|
|
|
6. Conclusions and Future Work
Presented results show that GSE method allows getting models which
resemble Blinn's blobs. According to expectations, the method lets control
the shape of model and modify surface bumps.
The main future work is to ray trace the GSE models with surface bumps
(g≠0). In the figure
12 draft pictures of such models are presented.
[3] John C. Hart. Ray tracing implicit surfaces. 1993.
[4] Teresa
Jurlewicz, Zbiegniew Skoczylas, Algebra liniowa (in Polish). Wroclaw, 1999.
[5] D. P. Mitchell. Robust ray intersection with interval arithmetic. Pages
68-74, 1990.
[6]
R. E. Moore. Interval Analysis. Prentice Hall, 1966.
[7]
Wanda Ronka-Chmielowiec and Antoni Smoluk. Metody
numeryczne (in Polish). 1987.