Re: surface interpolation?
Wolfgang Draxinger
> Does OpenGL offer a way to, given a set of control points, to
> automatically generate interpolated surfaces that pass through the control
> points? I've managed to discover the glMap2() and glEval2() functions but,
> according to my test code, it appears that the surfaces generated through
> this method don't cross the intermediate control points.
Those are the bezier evaluators, so there are points where are intercepted,
and points controlling the tangent direction.
Be aware that OpenGL evaluators have been implemented as part of the drivers
for most contemporary GPUs, so there's probably no gain using it instead of
implementing it in the own code.
> So, does OpenGL offer a way to do this or do I need to hand-code it?
Do it yourself. In the end it's easier and more flexible. Any textbook on
numerics should have an exhaustive chapter on interpolation and how to do it
efficiently.
This is better discussed on c.g.algorithms though, redirecting there.
Wolfgang
--
OpenGL tip #42:
How to exactly map texture texels to screen pixels:
<http://preview.tinyurl.com/cgndc8>
Rui Maciel
> Those are the bezier evaluators, so there are points where are
> intercepted, and points controlling the tangent direction.
OpenGL's documentation does mention Bezier surfaces but unfortunately it appears it
doesn't state what type of surface it generates.
> Be aware that OpenGL evaluators have been implemented as part of the
> drivers for most contemporary GPUs, so there's probably no gain using it
> instead of implementing it in the own code.
That's nice to know. Thanks.
>> So, does OpenGL offer a way to do this or do I need to hand-code it?
>
> Do it yourself. In the end it's easier and more flexible. Any textbook on
> numerics should have an exhaustive chapter on interpolation and how to do
> it efficiently.
Sounds good. As the surfaces I intend to generate must pass through the control
points, I'm thinking of interpolating the surface points with the help of a set of
Lagrange polynomials. Yet, I'm not sure that is the best option available. Is there
a better way to generate surfaces which must pass through the control points that
are used to define it?
Thanks in advance,
Rui Maciel
Kaba
> Sounds good. As the surfaces I intend to generate must pass through the control
> points, I'm thinking of interpolating the surface points with the help of a set of
> Lagrange polynomials. Yet, I'm not sure that is the best option available. Is there
> a better way to generate surfaces which must pass through the control points that
> are used to define it?
Hi,
Would interpolating subdivision surfaces fill your needs?
Dave Eberly
news:4b40ba50$0$7407$a729...@news.telepac.pt...
> Sounds good. As the surfaces I intend to generate must pass through the
> control
> points, I'm thinking of interpolating the surface points with the help of
> a set of
> Lagrange polynomials. Yet, I'm not sure that is the best option available.
> Is there
> a better way to generate surfaces which must pass through the control
> points that
> are used to define it?
Are your points ordered or unordered? For example, if all you have is a
point
cloud, you most likely have no information about how the points "connect" to
each other. If your points are ordered, is the surface intended to be a
height
field or an arbitrary surface?
If a height field, consider the following example. Suppose you have a 4x4
grid of "control points", C[i][j], for 0 <= i <= 3 and 0 <= j <= 3. Suppose
that the control points are (x[i],y[j],z[i][j]), so you have a regular grid
in the
xy-plane. You could attempt a bivariate polynomial surface of the form
z = Transpose(P(x)) * M * P(y)
where P(u) is a 4x1 column vector, written here as a 4-tuple (1, u, u^2,
u^3).
So P(y) is 4x1 and Transpose(P(x)) is a 1x4. The matrix M is 4x4 and its
entries are unknown. Set up a system of 16 linear equations in the 16
unknowns of M by
z[i][j] = Transpose(P(x[i]) * M * P(y[j])
If a height field, but irregularly spaced points, try thin-plate splines.
If not a height field, you can still try the bivariate polynomial approach,
but think of x and y as the surface parameters. In this case M is a 4x4
matrix of unknown 3-tuples and z is a surface point. Formally, you get
a system of 16 linear equations in 16 unknown 3-tuples.
Alternatively, you might relax the constraint on "exact interpolation" and
try a fitting algorithm, or some other more sophisticated algorithm for
generating a surface from a point set.
--
Dave Eberly
http://www.geometrictools.com
Rui Maciel
> Hi,
>
> Would interpolating subdivision surfaces fill your needs?
As long as Lagrange polynomials are used as the interpolating function then I
believe it would work. Yet, as I'm new to this subject I may be wrong. What are
your thoughts on this?
Rui Maciel
Rui Maciel
> Are your points ordered or unordered? For example, if all you have is a
> point
> cloud, you most likely have no information about how the points "connect"
> to each other. If your points are ordered, is the surface intended to be
> a height
> field or an arbitrary surface?
The points are used to define arbitrary surfaces, each of a very specific format.
To be more precise, each set of points are used to define surfaces of polyhedrons,
such as tetrahedrons and hexahedrons, which may have distorted faces.
<snip/>
> If not a height field, you can still try the bivariate polynomial
> approach, but think of x and y as the surface parameters. In this case M
> is a 4x4 matrix of unknown 3-tuples and z is a surface point. Formally,
> you get a system of 16 linear equations in 16 unknown 3-tuples.
Sounds interesting. Is there any online doc which touches that subject that I can
access?
> Alternatively, you might relax the constraint on "exact interpolation" and
> try a fitting algorithm, or some other more sophisticated algorithm for
> generating a surface from a point set.
Unfortunately that constraint can't be relaxed and the surface must contain the
control points.
Thanks for the help,
Rui Maciel
Kaba
(I am writing this after reading your answer to Dave)
When you mention Lagrance polynomials it seems that you are expecting to
represent the surfaces either using a single polynomial patch or a set
of independent polynomial patches.
Out of these two the first one is often a bad idea since surfaces are
usually more complex than that. The second idea is a better one but then
you are left with the problem of ensuring continuity between the patches
(positional, derivatives, ...).
These problems then naturally lead you to splines and subdivision
surfaces.
Regarding the latter, have a look at this paper:
http://mrl.nyu.edu/~dzorin/papers/zorin1996ism.pdf
Especially, see the images at the last page of the paper. Is that what
you want?
Also visit Wikipedia for general information:
Dave Eberly
> The points are used to define arbitrary surfaces, each of a very specific
> format.
> To be more precise, each set of points are used to define surfaces of
> polyhedrons,
> such as tetrahedrons and hexahedrons, which may have distorted faces.
What else do you know about the points? For example, is a "distorted face"
generated by moving the originally planar points in the direction
perpendicular to the plane? Are the points grouped by face? Are your faces
essentially triangles? Do you know adjacency information about the points
on a distorted face? Any such information will help avoid the generic case
of "I have an unordered point cloud ...".
> Sounds interesting. Is there any online doc which touches that subject
> that I can
> access?
The algebra is straightforward. However, from what you describe, this
approach cannot help you.
david_f_knight
It seems to me there's a terminology problem here. If you have true
control points, then you already have everything you need to solve
your problem. There is no such thing as generic control points; all
control points are specific to their particular algorithm. On the
other hand, if all you have is data points on a surface, then there
are infinitely many possible solutions, and it's impossible to
identify "the" unique and correct one, in any general sense.
I know more about Bezier surfaces than other surface types, so I don't
want to overstate my expertise here. Take it for what it's worth. No
need for flames. I'm trying to use broad brush strokes.
I'll assume that you do not have control points, but just simple data
points on a surface, since otherwise you already know everything you
need and you didn't need to ask your question. This means you really
have two separate problems: choosing an interpolation technique (there
are infinitely many, most of which have never been imagined yet), and
then implementing it.
To give meaningful advice on choosing the interpolation technique you
should use requires additional information about the nature of your
surface, and the structure of your data points. If you don't have
that, then just choose the easiest way, since your result must be
essentially random.
As for the implementation, that depends on the interpolation
technique.
Now a few words about Bezier surfaces, since you mentioned that the
OpenGL documentation didn't define them adequately for you to be able
to use them. I'm not an expert on OpenGL, but it's pretty safe to
assume that unless stated otherwise, the Bezier surfaces it uses are
tensor product Bezier surface patches (i.e., essentially, the surface
can be defined by a varying swept surface curve). Given that, all you
need to know to classify the type of Bezier surface patch, is how many
control points are in each of the UV dimensions of the control net.
Almost always, in practical matters, that will be (or should be) four
in each dimension, which defines a bicubic Bezier surface patch. And
that means that each coordinate of the points in 3-space on the swept
surface curve is defined by a cubic polynomial.
As with any Bezier surface patch, in general only the four corner
control points lie on the surface. But the set of control points
uniquely define exactly one surface (as long as all control points are
distinct).
Now, there's no need to convert your surface representation, once
you've decided how to interpolate your surface data points, to a set
of bicubic tensor product Bezier surface patches if you want to write
all your own code to do everything on the CPU. But, if you do convert
the representation, at some point in the future, you should be able to
utilize a GPU hardware tessellator to tessellate and render your
Bezier surface patches, offering huge performance gains and
simplification of your own code.
I haven't been following this real closely (partly because it seems to
be moving at a shamefully and pathetically slow pace), but DirectX 11,
I think, was supposed to introduce bicubic Bezier surface patch
tesselation into the graphics pipeline. ATI has had a hardware
tessellation circuit in their graphics chips since Microsoft chose
them for whatever incarnation of Xbox they were first selected for.
But, ATI, in all their wisdom, never exposed this hardware to any API
(outside of the Xbox world). Anyway, with DirectX11, I guess
Microsoft expanded on this to add a full blown bicubic Bezier surface
patch evaluator into the graphics pipeline. Obviously, if OpenGL
wishes to remain relevant, it needs to follow suit. I don't know
where things stand on this (I'm not currently working in this area),
but every time I check it seems that no progress has been made.
Note: I'm sure I haven't got all the details above just right. For
those of you with more accurate, up to date information, please feel
free to correct or add to whatever I've written. No need for flames,
though, because I admit I don't have all the details here. I just
thought I could add something to this discussion.
-- david_f_knight
Rui Maciel
> When you mention Lagrance polynomials it seems that you are expecting to
> represent the surfaces either using a single polynomial patch or a set
> of independent polynomial patches.
Yes, I'm aiming for a set of independent polynomial patches.
> Out of these two the first one is often a bad idea since surfaces are
> usually more complex than that. The second idea is a better one but then
> you are left with the problem of ensuring continuity between the patches
> (positional, derivatives, ...).
In my case it's only important to ensure C0 continuity.
> These problems then naturally lead you to splines and subdivision
> surfaces.
>
> Regarding the latter, have a look at this paper:
>
> http://mrl.nyu.edu/~dzorin/papers/zorin1996ism.pdf
Thanks for the link, Kaba. After a quick browse I believe that that isn't
necessarily what I had in mind. What I'm looking for should be simpler than the
process described in the paper, as I only need to generate a surface from a small
set of control points and which must include them.
For example, let's consider an hexahedron. In order to render one I would need to
define 6 separate surfaces which must preserve C0 continuity between the near
edges. So that might be achieved by interpolating between the nodes which are used
to define each surface. Yet, I'm not sure what's the best way to perform this.
Nonetheless, I've found the paper to be very interesting. Great stuff.
Rui Maciel
> What else do you know about the points? For example, is a "distorted
> face" generated by moving the originally planar points in the direction
> perpendicular to the plane?
The points aren't positioned following any set of rules. They just respect their
relative placement among each other and the surface that they generate isn't
heavily distorted. It's just like I start off with a set of points which fully
describe a regular polyhedron but the nodes may be moved a bit off their original
position.
> Are the points grouped by face? Are your faces
> essentially triangles?
Some faces are in fact triangles but I also have quadrilaterals.
> Do you know adjacency information about the points
> on a distorted face? Any such information will help avoid the generic
> case of "I have an unordered point cloud ...".
The relative position among the points, along with their order, is known
beforehand.
So, do you have suggestion in mind? Any help is more than welcomed.
Dave Eberly
> The relative position among the points, along with their order, is known
> beforehand.
>
> So, do you have suggestion in mind? Any help is more than welcomed.
You say you know the order? Then you have a triangle mesh, right? This
meets your C0-continuity criterion. I am missing something in your posts,
because this would easy enough that you would not be posting about it :)
If you have a triangle mesh and you want instead C1 continuity, there are
tricks you can do with Bezier triangle patches (your quads would be split
to triangles) to get C1.
Perhaps you can post a sample data set with a description of the "relative
position among the points, along with their order"?
Kaba
> If you have a triangle mesh and you want instead C1 continuity, there are
> tricks you can do with Bezier triangle patches (your quads would be split
> to triangles) to get C1.
Hi Dave,
Could you post a link to such a paper (or papers)?
For my own interest:)
Rui Maciel
> You say you know the order? Then you have a triangle mesh, right? This
> meets your C0-continuity criterion. I am missing something in your posts,
> because this would easy enough that you would not be posting about it :)
I only have a set of points which are used to define a polyhedron. For example, I
may have 8 points to define a 8-node hexahedron but I may also have 27 points to
define a 27-node hexahedron.
<snip />
> Perhaps you can post a sample data set with a description of the "relative
> position among the points, along with their order"?
What I have in mind is something similar to this:
http://www.geuz.org/gmsh/doc/texinfo/gmsh.html#Node-ordering
So, from the info in that site, when dealing with a 8-node hexahedron then we would
know beforehand that I will have 8 nodes where, for example, nodes {4,5,6,7} define
a face. If we're dealing with a 27-node hexahedron then we would know that the face
equivalent to the one previously mentioned will be defined by nodes {4, 16, 5, 18,
6, 19, 7, 17, 25}.
Dave Eberly
news:MPG.25aca9016...@news.cc.tut.fi...
> Could you post a link to such a paper (or papers)?
Here is one idea:
http://www.geometrictools.com/Documentation/C1QuadraticInterpolation.pdf
I also have code for C1 Bezier triangle meshes (algorithm different from the
one in the link, the patches are degree 9). It has not yet been "moved"
into my downloadable distribution. It includes documentation about the
algorithm. If you are interested in this, send me an email and I'll try to
get it posted to my web site after a couple of weeks (I have to finish a
book project first).
Niels Fröhling
> But, ATI, in all their wisdom, never exposed this hardware to any API
> (outside of the Xbox world).
http://www.opengl.org/registry/specs/AMD/vertex_shader_tessellator.txt
Down to 2007 (X1xxx cards) :^)
Ciao
Niels
Kaba
> Here is one idea:
> http://www.geometrictools.com/Documentation/C1QuadraticInterpolation.pdf
>
> I also have code for C1 Bezier triangle meshes (algorithm different from the
> one in the link, the patches are degree 9). It has not yet been "moved"
> into my downloadable distribution. It includes documentation about the
> algorithm. If you are interested in this, send me an email and I'll try to
> get it posted to my web site after a couple of weeks (I have to finish a
> book project first).
Thanks. No need to hurry. My intent was just to skim the main idea,
since nowadays I have to be a bit wary on what I spend my time on
(studying on a grant). Its almost too easy to get lost on irrelevant
(but interesting) things:)
Dave Eberly
> What I have in mind is something similar to this:
> http://www.geuz.org/gmsh/doc/texinfo/gmsh.html#Node-ordering
This is a page describing a software package. I do not know what
you mean "something similar to this".
> So, from the info in that site, when dealing with a 8-node hexahedron then
> we would
> know beforehand that I will have 8 nodes where, for example, nodes
> {4,5,6,7} define
> a face. If we're dealing with a 27-node hexahedron then we would know that
> the face
> equivalent to the one previously mentioned will be defined by nodes {4,
> 16, 5, 18,
> 6, 19, 7, 17, 25}.
Sorry, I cannot help you. None of this is sufficient information for
me to infer what is the nature of your data sets.
Rui Maciel
> "Rui Maciel" <rui.m...@gmail.com> wrote in message
> news:4b431fc7$0$8973$a729...@news.telepac.pt...
>> What I have in mind is something similar to this:
>> http://www.geuz.org/gmsh/doc/texinfo/gmsh.html#Node-ordering
>
> This is a page describing a software package. I do not know what
> you mean "something similar to this".
That's odd. Although it's a page regarding a software package's documentation, I
intended to link to a section regarding node ordering definitions for a set of
elements.
> Sorry, I cannot help you. None of this is sufficient information for
> me to infer what is the nature of your data sets.
No problem. Following the node ordering info contained in that site I've managed
to define a Lagrange polynomial-based interpolation function that is able to
generate surfaces that include the control points.
Thanks anyway,
Rui Maciel
Andrew_M
As for me, the best way to perform 2D interpolation is solving
biharminic equation (thin flexible plate method). There are some more
or less efficient methods how to do it (I did it for cartographs, for
example- millions of control points). You may try one of my progs,
availible at http://www.smartfills.com/Html/2D.zip . Not the fastest
method, but if you have not a huge number of control points, it may be
efficient enough.
Andrew.