Hello:

I am looking for an algorithm that would define a quadratic
(C1) surface over a localized portion of a triangulation
(defined as shown below).  The points need not lie in the
same plane.  Also, the number of triangles adjacent to
point P can vary.  Any pointers to code/references would

0------------0
/ \          / \
/   \        /   \
/     \      /     \
/       \    /       \
/         \  /         \
/           \/ P         \
0------------0-------------0
\          / \           /
\        /   \         /
\      /     \       /
\    /       \     /
\  /         \   /
\/           \ /
0------------0

Thanks.

------

>I am looking for an algorithm that would define a quadratic
>(C1) surface over a localized portion of a triangulation
>(defined as shown below).  The points need not lie in the
>same plane.  Also, the number of triangles adjacent to
>point P can vary.  Any pointers to code/references would

Code for C1 quadratic interpolation of point sets (x,y,f(x,y)) is at
http://www.cs.unc.edu/~eberly, Numerical Utilities, files interp2.{h,c}.
The vertex data structure does not have a list of triangles including
it, but the code should be easy to modify to add that feature.  The
interpolation is a global one, but with local control.

I've nearly finished the code for interpolation of meshes (the underlying
surface not necessarily the graph of a function) using an extension of
this algorithm.  I should have it at the web site over the weekend.
If your problem involves general meshes and you care only about a local
fit (without requiring a global one), then you can directly use the
code interp2 by effectively rotating the local mesh so that it is the
graph of a function, then apply the interpolation to it.

Dave Eberly

>...
>If your problem involves general meshes and you care only about a local
>fit (without requiring a global one), then you can directly use the
>code interp2 by effectively rotating the local mesh so that it is the
>graph of a function, then apply the interpolation to it.

Is that always possible?  How large a neighborhood is "local"?

Suppose I start with a simple mesh - a tetrahedron...will that work?

--

Computer and Information Sciences                       (205) 934-2213
University of Alabama at Birmingham                 FAX (205) 934-5473
Birmingham, AL 35294-1170   http://www.cis.uab.edu/info/faculty/sloan/

>>...
>>If your problem involves general meshes and you care only about a local
>>fit (without requiring a global one), then you can directly use the
>>code interp2 by effectively rotating the local mesh so that it is the
>>graph of a function, then apply the interpolation to it.
>Is that always possible?

The poster had a drawing of six triangles with a common vertex.  I
inferred that he wanted an interpolation only for those triangles.
The object he drew did not appear to be closed.  So yes, it is always
possible in that situation.

Quote:> How large a neighborhood is "local"?

The largest neighborhood such that the corresponding mesh is the graph of
a continuous piecewise linear function in some rotated coordinate system.

Quote:>Suppose I start with a simple mesh - a tetrahedron...will that work?

In the case of more general meshes, I finally finished my analysis and
posted a description and code for the extension of the Cendes-Wong
C1 quadratic interpolation algorithm.  It is at my web site,
meshintr.{h,c,ps}.  The sample driver applies the algorithm to the
tetrahedron with vertices (0,0,0), (1,0,0), (0,1,0), and (0,0,1).
The algorithm cannot handle arbitrary topology.  There is a "regularity"
condition which must be satisfied by the vertices.  I suspect that if
such vertices are encountered in applications, the mesh itself can be
modified locally about such vertices before applying the smoother.

There are a few more minor modifications that need to be made to the
code.  Currently it works fine on closed meshes.  For open meshes,
you need to add degenerate triangles to boundary edges.  I'll trap
those edges in a later revision and automatically handle them.  Second
thing is that if a vertex is not "regular", I don't trap the return
value of the routine that attempts to build a good normal.  I need
to add this (and possibly provide the automated procedure for modifying
the mesh before continuing).

Dave Eberly

>There are a few more minor modifications that need to be made to the
>code.  Currently it works fine on closed meshes.  For open meshes,
>you need to add degenerate triangles to boundary edges.  I'll trap
>those edges in a later revision and automatically handle them.  Second
>thing is that if a vertex is not "regular", I don't trap the return
>value of the routine that attempts to build a good normal.  I need
>to add this (and possibly provide the automated procedure for modifying
>the mesh before continuing).

Code now handles open meshes.  On encountering non-regular vertex, the
mesh interpolation object gracefully aborts and sets a flag to be
checked by the caller.  The sample driver shows how that is used.

Dave Eberly