ist be inde-
each point
pectively, is
I of a point
The neig-
defined via
langulation
n). The set
centerpoint
ıbset of the
ie points in
an or equal
ch are close
sewhere on
when inter-
ly exist one
ch will have
esults from
egions that
In appropri-
1994], this
lese points,
iangulation
nes against
shold value
'e 3).
dent of the
local coor-
pproximate
updated in
1e iteration
, or can be
e triangles
coordinate
gent plane
plane at P
desired, fil-
|
than a cer-
Otherwise
iction func-
es between
two vertices of the triangulation. If filtering is applied, the
vertices of the triangulation obtain new coordinates.
4.2 Calculating the boundary curves and their normal
vector fields
Boundary curves Each boundary curve replaces an edge
of the triangulation. The end points of the curves are the
vertices of the triangulation. All curves meeting in one point
must have tangents at this point that lie in a common tangent
plane. In general this tangent plane is obtained by calculating
normal vectors for each point of the triangulation.
The boundary curves shall be of degree three. This guarantees
compatibility to various systems based on spatial curves. For
example in [Halmer,1996] a way to adjust spatial curve nets
composed of curves of degree three is described. In cases
where the curves are given, only the normal vector fields along
these curves have to be computed. Otherwise the task is to
determine a curve c(t),t € [ta, to], that interpolates two given
points Po = c(ta) and P, = c(t). Po and P; are vertices
of the triangulation, their surface normals are ng and n;.
The curve c(t) must also fullfil the ‘tangent plane conditions’
¢(ta) no = 0 and c(£5) : ni — 0. As the curves are of degree
three, we just need to compute c(£,) and c(t;).
The edges of the triangulation emanating from one point
prescribe an order: Looking at that point against the dir-
ection of its normal vector each edge has one edge to its
left and one to its right. This order must be maintained by
the curves [Kobbelt, 1995]. Laying the tangent c(£4) in Po
in the plane through PoP, and no guarantees that the or-
dering prescribed by the edges is maintained. Together with
C(ta)-No = 0 the direction of the tangent is determined com-
pletely. Analogy applies for c(t5). The length of the first
derivative vectors can be chosen in a way that the curvature
of the surface computed in a previous step is approximated
(interpolation is possible only for planar curves, which needs
another choice of the tangent directions; e.g. [Mann,1992]).
Normal vector field Given is a curve c(t),t € [tq,ts], on
a surface. The surface is represented by points and their
surface normals. The goal is to compute the surface normal
vector field along the curve. The field is discretized. For that,
parameter values f;, 1, « t; € tp, 2? — 1,..., Kk, to points on
this curve are given. The notation for the endpoints remains
as explained before. The points in the neighbourhood of Py
and P, are Q;,Q»,... and their normals n;,n»,....
To calculate the normal vector field the points
Po, P1,Q1,Q2,... and their normals are transformed
into a coordinate system which is solely dependent on these
points and possibly also on their normals. However, the
triangulation of these points has to be describable as a graph
of a bivariate function. For determining the normals in the
points c(t;) prediction is used. The data to be interpolated
are: the points on the curve c(t;) and the tangents ¢(t;), the
points Po, P1, Q1, Q», ... and their normals. The discretized
normal vector field is formed by the normals of the prediction
function at c(t;).
5 COMPUTING THE BÉZIER TRIANGLES
The previous section described how to interpolate surface nor-
mals, boundary curves and normal vector fields along these
boundary curves. Now triangular patches have to be con-
structed for each face of the triangulation interpolating the
data. The examples given in this section are based on trian-
641
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
gulations of analytical surfaces.
5.1 £G1 continuity
Two adjacent patches are joined smoothly if they have the
same tangent planes along their common boundary curve. In
this case they are geometrically continuous of first order (G1).
To maintain locality, the determination of the inner control
points of adjacent patches shall be independent from each
other, and just based on the boundary data (curves and nor-
mals). Continuous normal vector fields can in general not
be interpolated with Bézier triangles. However, if the field
is interpolated or approximated at a number of positions, the
tangent planes of the adjacent patches will not match exactly,
but it can be expected, that they deviate from each other by a
small angle only. Therefore this kind of “continuity” is called
eG1. The deviation of tangent plane fields can be judged in
two ways:
1. Comparing two adjacent patches directly: The maxi-
mum deviation angle shall be y.
2. Comparing the normal vector field of a patch with
the given normal vector field: The maximum deviation
angle shall be T then the first criterion is satisfied as
well.
The angle y is a user defined quality measure. What needs
to be done if the y—criterion can not be satisfied, is described
later on.
To ensure fast reconstruction and to reduce the amount of
data, we restricted ourselves to use patches of degree three
and four. Patches of higher degree also lead to larger systems
of equations and their shape is more likely to have unpleasing
areas of high curvature or oscillation.
5.2 Inner control points and tangent planes
It is well known and follows immediately from the tangent
plane construction with the algorithm of de Casteljau that the
tangent planes of a Bézier triangle along a boundary curve
depend only on the corresponding boundary control points
and on the points of the neighbouring row. In the case of a
Bézier triangle of degree three, there is only one inner point.
All the tangent planes along the boundary are dependent on
the choice of this point. In the case of degree four, always a
pair of two inner control points have influence on the tangent
plane along a boundary curve.
The functional dependency between the tangent plane at P
and the inner points is easily derived. Let P be a point of
the Bézier curve whose control points are P309, P210, P150,
Po30; its curve parameter shall be 7. Further, let Q be the
point with parameter £ on the Bézier curve with control points
P2o1, Pi11, Poz1. Then q = Q — P is a tangent vector at
P. With n as normal vector at P, we therefore have
n'q-m. (6)
In terms of the unknown inner point P11: and using the Bern-
stein polynomials for Bézier curves this can be written as
n-q=n-(Q-P)=0= (7)
n-((1—t)"Pzoi + 2(1 — t)Pi11 + t*Pon - P),
21(1 - )n- Pii1 2 n- (P - (1 - £ P391 — t?Poz1).
Equation 8 is a scalar product and therefore each boundary
normal to be interpolated introduces one linear scalar equation
