From: Thatcher Ulrich <tu@tu...>  20021104 05:02:59

That looks pretty handy. For alternative working code that I suspect computes the same or similar thing, have a look at this Usenet post from the mists of time: http://groups.google.com/groups?hl=en&lr=&ie=UTF8&selm=3230390B.6798%40world.std.com (Substitute "float" for "frac"; that was just a dumb typedef. And "vec3" or whatever for "vector"  I wasn't using the STL in those days.)  Thatcher Ulrich http://tulrich.com On Nov 03, 2002 at 09:49 0800, Jon Watte wrote: > > I like the cubic Hermite interpolator, which easily extends to > 2D. Assuming you have a 1D filter function on a 1D height function > like so: > > int x = floor(inPos); > float f = inPosx; > out = filt( h(x1), h(x), h(x+1), h(x+2), f ) > > Then assuming some niceness properties of h(1D) (I think that the > filter is separable, but Ron will correct me :) then you can do the > 2D version as: > > int y = floor(inPos.y); > float fy = inPos.yy; > int x = floor(inPos.x); > float fx = inPos.xx; > out = filt( > filt( h(x1,y1), h(x,y1), h(x+1,y1), h(x+2,y1), fx ), > filt( h(x1,y), h(x,y), h(x+1,y), h(x+2,y), fx ), > filt( h(x1,y+1), h(x,y+1), h(x+1,y+1), h(x+2,y+1), fx ), > filt( h(x1,y+2), h(x,y+2), h(x+1,y+2), h(x+2,y+2), fx ), > fy ); > > Even if the filter is not separable, as long as you always look up > the data using the same stride in your input function, you'll always > get the same results, and thus it's good enough for rock and roll. > I've used a function constructed like this on heightfield data before > (for continuous tesselation purposes) and it worked fine. A warning, > though: the interpolated value within a "block" may actually go > outside the extrema of the block values! Thus, if you build culling > volumes, make sure to allow for that. This is a property of any > superlinear interpolation function, AFAIK. > > The "filt" function for cubic Hermite, which is first derivative > continuous, is: > > function filt( y0, y1, y2, y3, x ) { > float c0 = y1; > float c1 = 0.5f * (y2  y0); > float c2 = y0  2.5f * y1 + 2.f * y2  0.5f * y3; > float c3 = 1.5f * (y1  y2) + 0.5f * (y3  y0); > > return ((c3 * x + c2) * x + c1) * x + c0; > } > > This last bit shamelessly copypasted from the http://www.musicdsp.org/ > source code archive :) [[By the way: applying cubic hermite to audio > interpolation makes for fairly good results; noise floor < 72 dB. It is > remarkably computationally efficient compared to an equivalent 13point > FIR interpolator, although the FIR noise is whiter and less harmonically > related to the signal than that of the cubic Hermite.]] > > Cheers, > > / h+ > > > Original Message > > From: gdalgorithmslistadmin@... > > [mailto:gdalgorithmslistadmin@...]On Behalf Of > > Marius 'LtJax' Elvert > > Sent: Saturday, November 02, 2002 6:07 AM > > To: GD Algorithms > > Subject: [Algorithms] Extracting filtered height data from quadtree > > terrain. > > > > > > Hi! > > I have a static quadtree based terrain mesh. Now I want to extract > > height data from it. > > Getting the data alone is not the problem, but I want it to be filtered > > as good as possible > > ( bilinear at least, becubic would be fine ). Any algorithms or ideas > > how to do that? > > > > Marius > > > > > > > >  > > This sf.net email is sponsored by: See the NEW Palm > > Tungsten T handheld. Power & Color in a compact size! > > http://ads.sourceforge.net/cgibin/redirect.pl?palm0001en > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > >  > This SF.net email is sponsored by: ApacheCon, November 1821 in > Las Vegas (supported by COMDEX), the only Apache event to be > fully supported by the ASF. http://www.apachecon.com > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 