15 Oct 17:49 2010

## Re: Fwd: Interpolation problem

Moreland, Kenneth <kmorel <at> sandia.gov>

2010-10-15 15:49:12 GMT

2010-10-15 15:49:12 GMT

If I can, I would like to expand the conversation a little bit because I don’t think the technical details are telling the whole story.

The root of the problem is that the interpolation of a scalar field based on the four corners of a square (or any quadrilateral) is in general ill-defined. We usually mean for field to be linearly interpolated between the points. That is, find some function of the form f(x,y) = a*x + b*y + c that gives the correct scalar for all four points. But, in fact, four points over constrain the problem and no such linear function exists.

So really, the differences you are seeing are the differences between how the internal VTK functions resolve the interpolation and how your rendering hardware is doing it. I haven’t looked at the source code, but I’m assuming that VTK is using something like bilinear interpolation. Bilinear interpolation works by first interpolating the scalar on opposite edges and then interpolating again between these edges to get a point in the interior. Bilinear interpolation has several advantages: it can be done independently of neighboring polygons and still be C0 continuous, it is easy to implement, it is smooth in the interior, and it gives an interpolation that intuitively makes sense. Note, however, that bilinear interpolation is not linear. This is evident by your plot (which is a parabola).

Your graphics driver is much more concerned with speed. As such, it takes your quadrilateral and breaks it into triangles. This circumvents the whole interpolation problem because the three vertices of the triangle perfectly constrain the linear function. It is also easy for the graphics hardware to compute the interior of the triangle. Of course, the result is not as, shall we say, pleasant as bilinear interpolation. It is not smooth: There is a C1 discontinuity at the line where the quadrilateral was split into triangles. Also, this splitting is arbitrary. The split could just as easily been made in the opposite direction. In that case, you would see a red line go from upper left to lower right instead of that blue line from lower left to upper right.

So the rendering is probably not what was indented when defining the scalar value on a quadrilateral. However, ParaView allows it because correcting the problem would make the rendering prohibitively slow. Furthermore, it is rarely even noticeable. The square in this example is worst case. Not only do no linear functions fit, they are not even close. Thus, the different ways to resolve the issue are dramatically different. In a practical application, this does not occur. The scalar values tend to more closely fit a linear function. If a quadrilateral like this occurred in a real data set, it might be indicative of a meshing problem. Furthermore, real meshes have lots of facets. If this square was a small part of a much bigger surface, differences in interpolation are less meaningful.

In short, the interpolation your graphics hardware performs is sufficient for qualitative analysis (getting an overview of behavior), which is all its really good for anyway. When you do qualitative analysis (showing actual numbers in the data) such as in your plot, the more accurate interpolation models of VTK are used.

-Ken

On 10/14/10 9:06 AM, "Andy Bauer" <andy.bauer <at> kitware.com> wrote:

The root of the problem is that the interpolation of a scalar field based on the four corners of a square (or any quadrilateral) is in general ill-defined. We usually mean for field to be linearly interpolated between the points. That is, find some function of the form f(x,y) = a*x + b*y + c that gives the correct scalar for all four points. But, in fact, four points over constrain the problem and no such linear function exists.

So really, the differences you are seeing are the differences between how the internal VTK functions resolve the interpolation and how your rendering hardware is doing it. I haven’t looked at the source code, but I’m assuming that VTK is using something like bilinear interpolation. Bilinear interpolation works by first interpolating the scalar on opposite edges and then interpolating again between these edges to get a point in the interior. Bilinear interpolation has several advantages: it can be done independently of neighboring polygons and still be C0 continuous, it is easy to implement, it is smooth in the interior, and it gives an interpolation that intuitively makes sense. Note, however, that bilinear interpolation is not linear. This is evident by your plot (which is a parabola).

Your graphics driver is much more concerned with speed. As such, it takes your quadrilateral and breaks it into triangles. This circumvents the whole interpolation problem because the three vertices of the triangle perfectly constrain the linear function. It is also easy for the graphics hardware to compute the interior of the triangle. Of course, the result is not as, shall we say, pleasant as bilinear interpolation. It is not smooth: There is a C1 discontinuity at the line where the quadrilateral was split into triangles. Also, this splitting is arbitrary. The split could just as easily been made in the opposite direction. In that case, you would see a red line go from upper left to lower right instead of that blue line from lower left to upper right.

So the rendering is probably not what was indented when defining the scalar value on a quadrilateral. However, ParaView allows it because correcting the problem would make the rendering prohibitively slow. Furthermore, it is rarely even noticeable. The square in this example is worst case. Not only do no linear functions fit, they are not even close. Thus, the different ways to resolve the issue are dramatically different. In a practical application, this does not occur. The scalar values tend to more closely fit a linear function. If a quadrilateral like this occurred in a real data set, it might be indicative of a meshing problem. Furthermore, real meshes have lots of facets. If this square was a small part of a much bigger surface, differences in interpolation are less meaningful.

In short, the interpolation your graphics hardware performs is sufficient for qualitative analysis (getting an overview of behavior), which is all its really good for anyway. When you do qualitative analysis (showing actual numbers in the data) such as in your plot, the more accurate interpolation models of VTK are used.

-Ken

On 10/14/10 9:06 AM, "Andy Bauer" <andy.bauer <at> kitware.com> wrote:

2010/10/14 小縣信也 <so0208jp <at> gmail.com>Hi Andy,

Thank you for replying.

Do you mean that the rendering image doesn't reflect the result of

interpolation ?

Yes.

If so, what is the most common usage?

In what situation is the interpolation used ?

If your grid uses triangles then the image should match the interpolation for the typical node/point based interpolation.

Shinya

2010/10/13 Andy Bauer <andy.bauer <at> kitware.com>:

> I think this is a rendering issue and not an interpolation issue. From the

> 2d plot you can see that it's properly interpolating the values. I think

> the quadrilateral is getting rendered as 2 triangles in which case the

> diagonal values appear to be constant since the 2 end points are at the same

> value.

>

> 2010/10/12 小縣信也 <so0208jp <at> gmail.com>

>>

>> Hello

>>

>> I'm sending the following e-mail again ,because nobody answered it.

>> Does anyone have information on my problem?

>>

>> Shinya

>>

>>

>> ---------- Forwarded message ----------

>> From: 小縣信也 <so0208jp <at> gmail.com>

>> Date: 2010/10/7

>> Subject: Interpolation problem

>> To: paraview <at> paraview.org

>>

>>

>> Hello, paraview users

>>

>> I draw the file “Sample_inter.vtk” on ParaView. (ref:attached file)

>> I chose “Gouraud” in Interpolation option.

>> The contor picture doesn’t seem to be interpolated by 4 points.

>> However,the graph which is made by PlotOverLine shows the gradation of

>> 4 points scalar.

>> Why are they different?

>> Does anyone know this problem?

>> How can I make contour picture interpolated by Gouraud ?

>>

>> I look forward to your reply to my inquiry

>>

>> Shinya Ogata

>>

>> _______________________________________________

>> Powered by www.kitware.com <http://www.kitware.com>

>>

>> Visit other Kitware open-source projects at

>> http://www.kitware.com/opensource/opensource.html

>>

>> Please keep messages on-topic and check the ParaView Wiki at:

>> http://paraview.org/Wiki/ParaView

>>

>> Follow this link to subscribe/unsubscribe:

>> http://www.paraview.org/mailman/listinfo/paraview

>>

>

>

<div> <span>If I can, I would like to expand the conversation a little bit because I don’t think the technical details are telling the whole story.<br><br> The root of the problem is that the interpolation of a scalar field based on the four corners of a square (or any quadrilateral) is in general ill-defined. We usually mean for field to be linearly interpolated between the points. That is, find some function of the form f(x,y) = a*x + b*y + c that gives the correct scalar for all four points. But, in fact, four points over constrain the problem and no such linear function exists.<br><br> So really, the differences you are seeing are the differences between how the internal VTK functions resolve the interpolation and how your rendering hardware is doing it. I haven’t looked at the source code, but I’m assuming that VTK is using something like bilinear interpolation. Bilinear interpolation works by first interpolating the scalar on opposite edges and then interpolating again between these edges to get a point in the interior. Bilinear interpolation has several advantages: it can be done independently of neighboring polygons and still be C0 continuous, it is easy to implement, it is smooth in the interior, and it gives an interpolation that intuitively makes sense. Note, however, that bilinear interpolation is not linear. This is evident by your plot (which is a parabola).<br><br> Your graphics driver is much more concerned with speed. As such, it takes your quadrilateral and breaks it into triangles. This circumvents the whole interpolation problem because the three vertices of the triangle perfectly constrain the linear function. It is also easy for the graphics hardware to compute the interior of the triangle. Of course, the result is not as, shall we say, pleasant as bilinear interpolation. It is not smooth: There is a C1 discontinuity at the line where the quadrilateral was split into triangles. Also, this splitting is arbitrary. The split could just as easily been made in the opposite direction. In that case, you would see a red line go from upper left to lower right instead of that blue line from lower left to upper right.<br><br> So the rendering is probably not what was indented when defining the scalar value on a quadrilateral. However, ParaView allows it because correcting the problem would make the rendering prohibitively slow. Furthermore, it is rarely even noticeable. The square in this example is worst case. Not only do no linear functions fit, they are not even close. Thus, the different ways to resolve the issue are dramatically different. In a practical application, this does not occur. The scalar values tend to more closely fit a linear function. If a quadrilateral like this occurred in a real data set, it might be indicative of a meshing problem. Furthermore, real meshes have lots of facets. If this square was a small part of a much bigger surface, differences in interpolation are less meaningful.<br><br> In short, the interpolation your graphics hardware performs is sufficient for qualitative analysis (getting an overview of behavior), which is all its really good for anyway. When you do qualitative analysis (showing actual numbers in the data) such as in your plot, the more accurate interpolation models of VTK are used.<br><br> -Ken<br><br><br> On 10/14/10 9:06 AM, "Andy Bauer" <<a href="andy.bauer <at> kitware.com">andy.bauer <at> kitware.com</a>> wrote:<br><br></span><blockquote> <span><br><br> 2010/10/14 小縣信也 <<a href="so0208jp <at> gmail.com">so0208jp <at> gmail.com</a>><br></span><blockquote><span>Hi Andy,<br><br> Thank you for replying.<br> Do you mean that the rendering image doesn't reflect the result of<br> interpolation ?<br></span></blockquote> <span><br> Yes.<br> <br></span><blockquote><span>If so, what is the most common usage?<br> In what situation is the interpolation used ?<br></span></blockquote> <span><br> If your grid uses triangles then the image should match the interpolation for the typical node/point based interpolation. <br><br> <br></span><blockquote><span>Shinya<br><br><br> 2010/10/13 Andy Bauer <<a href="andy.bauer <at> kitware.com">andy.bauer <at> kitware.com</a>>:<br> > I think this is a rendering issue and not an interpolation issue. From the<br> > 2d plot you can see that it's properly interpolating the values. I think<br> > the quadrilateral is getting rendered as 2 triangles in which case the<br> > diagonal values appear to be constant since the 2 end points are at the same<br> > value.<br> ><br> > 2010/10/12 小縣信也 <<a href="so0208jp <at> gmail.com">so0208jp <at> gmail.com</a>><br> >><br> >> Hello<br> >><br> >> I'm sending the following e-mail again ,because nobody answered it.<br> >> Does anyone have information on my problem?<br> >><br> >> Shinya<br> >><br> >><br> >> ---------- Forwarded message ----------<br> >> From: 小縣信也 <<a href="so0208jp <at> gmail.com">so0208jp <at> gmail.com</a>><br> >> Date: 2010/10/7<br> >> Subject: Interpolation problem<br> >> To: <a href="paraview <at> paraview.org">paraview <at> paraview.org</a><br> >><br> >><br> >> Hello, paraview users<br> >><br> >> I draw the file “Sample_inter.vtk” on ParaView. (ref:attached file)<br> >> I chose “Gouraud” in Interpolation option.<br> >> The contor picture doesn’t seem to be interpolated by 4 points.<br> >> However,the graph which is made by PlotOverLine shows the gradation of<br> >> 4 points scalar.<br> >> Why are they different?<br> >> Does anyone know this problem?<br> >> How can I make contour picture interpolated by Gouraud ?<br> >><br> >> I look forward to your reply to my inquiry<br> >><br> >> Shinya Ogata<br> >><br> >> _______________________________________________<br> >> Powered by www.kitware.com <<a href="http://www.kitware.com">http://www.kitware.com</a>> <br> >><br> >> Visit other Kitware open-source projects at<br> >> <a href="http://www.kitware.com/opensource/opensource.html">http://www.kitware.com/opensource/opensource.html</a><br> >><br> >> Please keep messages on-topic and check the ParaView Wiki at:<br> >> <a href="http://paraview.org/Wiki/ParaView">http://paraview.org/Wiki/ParaView</a><br> >><br> >> Follow this link to subscribe/unsubscribe:<br> >> <a href="http://www.paraview.org/mailman/listinfo/paraview">http://www.paraview.org/mailman/listinfo/paraview</a><br> >><br> ><br> ><br></span></blockquote> <span><br><br></span> </blockquote> </div>