Re: Details of subdivision algorithm.

[Reinoud Zandijk]

Hi folks,

has anyone tried the 2 dimentional hermite interpolation before? Does anyone
have a good pointer to the math involved? The articles i've found so far are
not that complete.

As for interdependency, should i read that as i have to interatively solve all
the curved surfaces that connect? So in the sphere example all surfaces to get
the C2 continuity?

With regards,
Reinoud

[Alexander Zimmermann]

Reinoud,

I've tried this. The formulas are not to difficult if you are familiar with
barycentric coordinates on the triangle:

Given 0 <= u,v,w <=1 with u+v+w=1 and
Vertices: PU PV PW
Tangents: TUV,TUW TVU,TVW TWU,TWV
Free parameter: X
the hermite polynomial h(u,v,w) can be written as

h(u,v,w) = u*v*w*X
+ (3*PW-TWV)*v*w^2 + (3*PW-TWU)*u*w^2 + PW*w^3
+ (3*PV-TVW)*v^2*w + (3*PU-TUW)*u^2*w + PV*v^3
+ (3*PV-TVU)*u*v^2 + (3*PU-TUV)*u^2*v + PU*u^3;

The tangents (f.e. TUV: tangent at PU in direction to PV) always point inside the
triangle in this formula. There is one (3D) parameter X free to choose.

In any case the border curves between the vertices are independent of X :

h(1-s,s,0) = (2*s^3-3*s^2+1)*PU+(-s^3+2*s^2-s)*TUV+(-2*s^3+3*s^2)*PV+(s^3-s^2)*TVU
h(0,1-s,s) = (2*s^3-3*s^2+1)*PV+(-s^3+2*s^2-s)*TVW+(-2*s^3+3*s^2)*PW+(s^3-s^2)*TWV
h(s,0,1-s) = (2*s^3-3*s^2+1)*PW+(-s^3+2*s^2-s)*TWU+(-2*s^3+3*s^2)*PU+(s^3-s^2)*TUW

and this looks very familiar ;)

Jon proposed to choose the free parameter in order to minimize the energy of the
surface. I'm currently looking for an operator that calculates the energy.

In the context of splines normaly not the real energy of a curve is minimized
(that would require calculation of the curvature and the use of square roots)
but a simular value: the integral over the square of the second derivative.

I know that there is an operator that works with barycentric coordinates that
calculates a similar "energy" on surfaces, but I currently don't remember the
formula and even the place where I read it :(

It depends mostly on the choice of the free parameters X , whether the resulting
surface has G0 or G1 continuity between adjacent triangles (one free X for each
triangle). As I know G2 continuity is an exceptional case, only.

Keep on searching for the formula...

-- Alexander

[Alexander Zimmermann]

I forgot to add a maxima file with the formulas ;)
If anyone can cope with it.

-- Alexander

On Mon, 28 Jan 2013 20:55:33 +0100
Reinoud Zandijk <rei...@13thmonkey.org> wrote:

[Alexander Zimmermann]

Hi folks,

finally I found the formula for the differential operator of polynomials over
simplices in

T. Sauer, The genuine Bernstein–Durrmeyer operator on a simplex,
Results in Mathematics 26 (1994), 99-130

The original defintion is even older.

To make a long story short, after some calulation, integration, miscalculation
and optimization I got

X = 2*(PU+PV+PW) - (TUV+TUW+TVU+TVW+TWU+TWV)/66

But the visualization ( exp_min_energy_1.png , together with the bezier
control mesh) looks not like I expected it.
However thinking of a soap bubble in a wire frame it may be possible.

Anyway, thinking of continuity: in order to be "translation invariant", in
the following sense: if all the vertices move (translate and rotate) the same
way, the midpoint X must move the same way too. Then the calculation of X need
to be of the form

X = 2*(PU+PV+PW) + beta*(TUV+TUW+TVU+TVW+TWU+TWV)

for some arbitrary real beta (negativ or positiv or even zero).
This implies that the transverse tangent (inside the triangle) at the
subdivision point, f.e. on the edge between the vertices PU and PV depends on
the values of PW, TUW+TVW and TWU+TWV (if beta is not zero)

TransTangent = (4PW-2PU-2PV + 2*beta*(TUV+TUW+TVU+TVW+TWU+TWV)
- 2*(TUW+TVW)+3*(TVU+TUV)) / 4

And so will the normal at the subdivision point depend on the values of the
third vertex and its tangents.

Considering two adjacent triangles with two identical vertices and tangents
(along one edge), but different third point will have different transverse
tangents (and normals). This results in CO continuity.

I've tried to make an example, but it's not easy to see in the screendump,
that the surface is only C0. ( exp_min_energy_2.png )

Your thoughts?

-- Alexander