## Re: [Algorithms] Extracting filtered height data from quadtree terrain.

 Re: [Algorithms] Extracting filtered height data from quadtree terrain. From: Thatcher Ulrich - 2002-11-04 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=UTF-8&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 = inPos-x; > out = filt( h(x-1), 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.y-y; > int x = floor(inPos.x); > float fx = inPos.x-x; > out = filt( > filt( h(x-1,y-1), h(x,y-1), h(x+1,y-1), h(x+2,y-1), fx ), > filt( h(x-1,y), h(x,y), h(x+1,y), h(x+2,y), fx ), > filt( h(x-1,y+1), h(x,y+1), h(x+1,y+1), h(x+2,y+1), fx ), > filt( h(x-1,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 > super-linear 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 copy-pasted from the http://www.music-dsp.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 13-point > 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: gdalgorithms-list-admin@... > > [mailto:gdalgorithms-list-admin@...]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/cgi-bin/redirect.pl?palm0001en > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > ------------------------------------------------------- > This SF.net email is sponsored by: ApacheCon, November 18-21 in > Las Vegas (supported by COMDEX), the only Apache event to be > fully supported by the ASF. http://www.apachecon.com > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ```

 [Algorithms] Extracting filtered height data from quadtree terrain. From: - 2002-11-02 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 ```
 Re: [Algorithms] Extracting filtered height data from quadtree terrain. From: Thatcher Ulrich - 2002-11-02 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/cgi-bin/viewcvs.cgi/tu-testbed/tu-testbed/demos/quaddemo/quadtree.cpp?rev=1.2&content-type=text/vnd.viewcvs-markup -- Thatcher Ulrich http://tulrich.com ```
 Re: [Algorithms] Extracting filtered height data from quadtree terrain. From: - 2002-11-03 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/cgi-bin/viewcvs.cgi/tu-testbed/tu-testbed/demos/quaddemo/quadtree.cpp?rev=1.2&content-type=text/vnd.viewcvs-markup > > > ```
 Re: [Algorithms] Extracting filtered height data from quadtree terrain. From: Thatcher Ulrich - 2002-11-03 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/cgi-bin/viewcvs.cgi/tu-testbed/tu-testbed/demos/quaddemo/quadtree.cpp?rev=1.2&content-type=text/vnd.viewcvs-markup -- Thatcher Ulrich http://tulrich.com ```
 Re: [Algorithms] Extracting filtered height data from quadtree terrain. From: Charles Bloom - 2002-11-03 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 ```
 Re: [Algorithms] Extracting filtered height data from quadtree terrain. From: Thatcher Ulrich - 2002-11-04 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 ```
 RE: [Algorithms] Extracting filtered height data from quadtree terrain. From: Jon Watte - 2002-11-03 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 = inPos-x; out = filt( h(x-1), 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.y-y; int x = floor(inPos.x); float fx = inPos.x-x; out = filt( filt( h(x-1,y-1), h(x,y-1), h(x+1,y-1), h(x+2,y-1), fx ), filt( h(x-1,y), h(x,y), h(x+1,y), h(x+2,y), fx ), filt( h(x-1,y+1), h(x,y+1), h(x+1,y+1), h(x+2,y+1), fx ), filt( h(x-1,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 super-linear 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 copy-pasted from the http://www.music-dsp.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 13-point 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: gdalgorithms-list-admin@... > [mailto:gdalgorithms-list-admin@...]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/cgi-bin/redirect.pl?palm0001en > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```
 Re: [Algorithms] Extracting filtered height data from quadtree terrain. From: Thatcher Ulrich - 2002-11-04 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=UTF-8&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 = inPos-x; > out = filt( h(x-1), 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.y-y; > int x = floor(inPos.x); > float fx = inPos.x-x; > out = filt( > filt( h(x-1,y-1), h(x,y-1), h(x+1,y-1), h(x+2,y-1), fx ), > filt( h(x-1,y), h(x,y), h(x+1,y), h(x+2,y), fx ), > filt( h(x-1,y+1), h(x,y+1), h(x+1,y+1), h(x+2,y+1), fx ), > filt( h(x-1,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 > super-linear 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 copy-pasted from the http://www.music-dsp.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 13-point > 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: gdalgorithms-list-admin@... > > [mailto:gdalgorithms-list-admin@...]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/cgi-bin/redirect.pl?palm0001en > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > ------------------------------------------------------- > This SF.net email is sponsored by: ApacheCon, November 18-21 in > Las Vegas (supported by COMDEX), the only Apache event to be > fully supported by the ASF. http://www.apachecon.com > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ```