From: Thatcher Ulrich <tu@tu...>  20021104 04:35:04

On Nov 03, 2002 at 08:52 0800, Charles Bloom wrote: > > You can make the derivative continuous just by doing bilinear > but using a "hermite lerp" or "cosine lerp" instead of linear > lerp of the s,t parameters inside the four points. > > //! remap (0>1) to (0>1) but with derivative continuity > inline float fHermiteLerpParameter(const float t) > { > gAssert( t >=  EPSILON && t <= 1.f + EPSILON ); > return (3.f  2.f*t)*t*t; > } > > //! even better continuity than Hermite lerp, but slower > inline float fCosLerpParameter(const float t) > { > gAssert( t >=  EPSILON && t <= 1.f + EPSILON ); > return 0.5f  0.5f * cosf( t * PI ); > } That makes the derivative continuous by ramping it to 0 at the boundaries, correct? That would make slopes wavy  might look/act weird for a heightfield. Anyway, bicubic interpolation using 4x4 control points is the deluxe solution here, but if the quadtree is adaptive, I'm not sure of a correct way to collect the control points. I'm sure there is one, I've just never had to do it personally.  Thatcher Ulrich http://tulrich.com 
From: LtJ<ax@t...>  20021102 14:07:29

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 
From: Thatcher Ulrich <tu@tu...>  20021102 21:56:21

On Nov 02, 2002 at 03:07 +0100, Marius 'LtJax' Elvert wrote: > > 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? Bilinear is pretty easy, see GetHeight in this file: http://cvs.sourceforge.net/cgibin/viewcvs.cgi/tutestbed/tutestbed/demos/quaddemo/quadtree.cpp?rev=1.2&contenttype=text/vnd.viewcvsmarkup  Thatcher Ulrich http://tulrich.com 
From: LtJ<ax@t...>  20021103 14:35:41
Attachments:
Message as HTML

as far as I see, that only interpolates in the 'current' quad  won't that look pretty ugly at the edges of the quads? Thatcher Ulrich wrote: >On Nov 02, 2002 at 03:07 +0100, Marius 'LtJax' Elvert wrote: > > >>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? >> >> > >Bilinear is pretty easy, see GetHeight in this file: > >http://cvs.sourceforge.net/cgibin/viewcvs.cgi/tutestbed/tutestbed/demos/quaddemo/quadtree.cpp?rev=1.2&contenttype=text/vnd.viewcvsmarkup > > > 
From: Thatcher Ulrich <tu@tu...>  20021103 16:07:21

The derivative is not continuous. You *did* mention bilinear... Ugly is in the eye of the beholder  you can get edges in the shading using bilinear, but sometimes it's adequate. On Nov 03, 2002 at 03:35 +0100, Marius 'LtJax' Elvert wrote: > as far as I see, that only interpolates in the 'current' quad  > won't that look pretty ugly at the edges of the quads? > > > Thatcher Ulrich wrote: > On Nov 02, 2002 at 03:07 +0100, Marius 'LtJax' Elvert wrote: > 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? > > Bilinear is pretty easy, see GetHeight in this file: > > http://cvs.sourceforge.net/cgibin/viewcvs.cgi/tutestbed/tutestbed/demos/quaddemo/quadtree.cpp?rev=1.2&contenttype=text/vnd.viewcvsmarkup  Thatcher Ulrich http://tulrich.com 
From: Charles Bloom <cbloom@cb...>  20021103 16:48:21

You can make the derivative continuous just by doing bilinear but using a "hermite lerp" or "cosine lerp" instead of linear lerp of the s,t parameters inside the four points. //! remap (0>1) to (0>1) but with derivative continuity inline float fHermiteLerpParameter(const float t) { gAssert( t >=  EPSILON && t <= 1.f + EPSILON ); return (3.f  2.f*t)*t*t; } //! even better continuity than Hermite lerp, but slower inline float fCosLerpParameter(const float t) { gAssert( t >=  EPSILON && t <= 1.f + EPSILON ); return 0.5f  0.5f * cosf( t * PI ); }  Charles Bloom cb@... http://www.cbloom.com 
From: Thatcher Ulrich <tu@tu...>  20021104 04:35:04

On Nov 03, 2002 at 08:52 0800, Charles Bloom wrote: > > You can make the derivative continuous just by doing bilinear > but using a "hermite lerp" or "cosine lerp" instead of linear > lerp of the s,t parameters inside the four points. > > //! remap (0>1) to (0>1) but with derivative continuity > inline float fHermiteLerpParameter(const float t) > { > gAssert( t >=  EPSILON && t <= 1.f + EPSILON ); > return (3.f  2.f*t)*t*t; > } > > //! even better continuity than Hermite lerp, but slower > inline float fCosLerpParameter(const float t) > { > gAssert( t >=  EPSILON && t <= 1.f + EPSILON ); > return 0.5f  0.5f * cosf( t * PI ); > } That makes the derivative continuous by ramping it to 0 at the boundaries, correct? That would make slopes wavy  might look/act weird for a heightfield. Anyway, bicubic interpolation using 4x4 control points is the deluxe solution here, but if the quadtree is adaptive, I'm not sure of a correct way to collect the control points. I'm sure there is one, I've just never had to do it personally.  Thatcher Ulrich http://tulrich.com 
From: Jon Watte <hplus@mi...>  20021103 17:50:37

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 > 
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 