I submit this for the consideration of interested parties.

While reading up on a version of a subdivision surface scheme, I
developed the idea of using a simplified version of it to provide
smooth interpolation of height field data.

The method builds a small quartic patch around each of the interior
points of the height field.  The coefficients for this quartic are
based on the value of that point and each of its eight neighbors.
When clipped properly the patches all meet perfectly, and there are
no discontinuities in the surface normal across the borders.

The result is a smooth surface across the entire height field with
no creases or seams.

The advantages are:
* There is no "stepping" as is commonly observed in height fields,
  especially 8-bit height fields.  A gently rising set of data
  points yields a gently sloping surface.

* There is no need for smoothing calculations; the patches are
  naturally smooth.

The disadvantages are:

* Slightly more data is needed to generate the same number of squares.
  In a normal height field, an M x N image will produce a (M-1) x (N-1)
  set of squares, which are comprised to two triangles.  This new
  method produces a (M-2) x (N-2) set of patches.

* The patches are mostly quartic objects; however some of them will be
  cubic, quadratic, or even linear.  Furthermore, a bounding box is
  very easy to calculate for each patch.  The method will be slower in
  any event.

I have posted some code that demonstrates this method, and an MPG
animation of it, in p.t.s-f and p.b.a.

So, what do you think?

Regards,
John
-- 
ICQ: 46085459

Post a reply to this message

currently, an advantage height fields have is a defined inside and
outside.  would your method also have this?  plus, i can make cuts from
height fields (like caves).  would yours be able to do this as well? 
other than that.  it sounds nice.  i'm off to check your pics!

John VanSickle wrote:
> 
> I submit this for the consideration of interested parties.
> 
> While reading up on a version of a subdivision surface scheme, I
> developed the idea of using a simplified version of it to provide
> smooth interpolation of height field data.
> 
> The method builds a small quartic patch around each of the interior
> points of the height field.  The coefficients for this quartic are
> based on the value of that point and each of its eight neighbors.
> When clipped properly the patches all meet perfectly, and there are
> no discontinuities in the surface normal across the borders.
> 
> The result is a smooth surface across the entire height field with
> no creases or seams.
> 
> The advantages are:
> * There is no "stepping" as is commonly observed in height fields,
>   especially 8-bit height fields.  A gently rising set of data
>   points yields a gently sloping surface.
> 
> * There is no need for smoothing calculations; the patches are
>   naturally smooth.
> 
> The disadvantages are:
> 
> * Slightly more data is needed to generate the same number of squares.
>   In a normal height field, an M x N image will produce a (M-1) x (N-1)
>   set of squares, which are comprised to two triangles.  This new
>   method produces a (M-2) x (N-2) set of patches.
> 
> * The patches are mostly quartic objects; however some of them will be
>   cubic, quadratic, or even linear.  Furthermore, a bounding box is
>   very easy to calculate for each patch.  The method will be slower in
>   any event.
> 
> I have posted some code that demonstrates this method, and an MPG
> animation of it, in p.t.s-f and p.b.a.
> 
> So, what do you think?
> 
> Regards,
> John
> --
> ICQ: 46085459

Post a reply to this message

John VanSickle wrote:
[...]
> 
> I have posted some code that demonstrates this method, and an MPG
> animation of it, in p.t.s-f and p.b.a.
> 
> So, what do you think?
> 

I just checked it out with a larger array (128x128):

15384 objects
33 Mb memory use
parse: 36 seconds
trace: 11 seconds

compared to conventional heightfield:

290 Kb memory use
parse: 0 seconds
trace: 6 seconds

it seems your construction is incredibly fast in trace, the rest is worse of
course, but anyway it's a very interesting idea.  

It's probably very useful if you need a perfectly smooth heightfield surface for
example when it's reflective or when the camera is very near to the surface at
one point.  

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
Homepage: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

Looks useful for certain types of HF. Bit worried about the extra memory
use.

Mick

"Christoph Hormann" <Chr### [at] schunteretctu-bsde> wrote in
message news:39F14FA8.6CE74FFD@schunter.etc.tu-bs.de...
>
>
> John VanSickle wrote:
> [...]
> >
> > I have posted some code that demonstrates this method, and an MPG
> > animation of it, in p.t.s-f and p.b.a.
> >
> > So, what do you think?
> >
>
> I just checked it out with a larger array (128x128):
>
> 15384 objects
> 33 Mb memory use
> parse: 36 seconds
> trace: 11 seconds
>
> compared to conventional heightfield:
>
> 290 Kb memory use
> parse: 0 seconds
> trace: 6 seconds
>
> it seems your construction is incredibly fast in trace, the rest is worse
of
> course, but anyway it's a very interesting idea.
>
> It's probably very useful if you need a perfectly smooth heightfield
surface for
> example when it's reflective or when the camera is very near to the
surface at
> one point.
>
> Christoph
>
> --
> Christoph Hormann <chr### [at] gmxde>
> Homepage: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

Christoph Hormann wrote:
> 
> I just checked it out with a larger array (128x128):
> 
> 15384 objects
> 33 Mb memory use
> parse: 36 seconds
> trace: 11 seconds
> 
> compared to conventional heightfield:
> 
> 290 Kb memory use
> parse: 0 seconds
> trace: 6 seconds
> 
> it seems your construction is incredibly fast in trace, the rest is
> worse of course, but anyway it's a very interesting idea.

You're making an apples-to-oranges comparison.  A method that has
several thousand primities will of course be more memory intensive
and run slower than a method that has one primitive.  The height_field
primitive could be modified to allow this interpolation method as an
option.

> It's probably very useful if you need a perfectly smooth heightfield
> surface for example when it's reflective or when the camera is very
> near to the surface at one point.

-- 
ICQ: 46085459

Post a reply to this message

ryan constantine wrote:
> 
> currently, an advantage height fields have is a defined inside and
> outside.  would your method also have this?

If it were available as an option with the height field, it would have
an inside and an outside.

> plus, i can make cuts from height fields (like caves).  would yours be
> able to do this as well?

Yes, if it were an option for the height_field object.

Which was my point.

Regards,
John
-- 
ICQ: 46085459

Post a reply to this message

John VanSickle wrote:
> 
> You're making an apples-to-oranges comparison.  A method that has
> several thousand primities will of course be more memory intensive
> and run slower than a method that has one primitive.  The height_field
> primitive could be modified to allow this interpolation method as an
> option.
> 

I did not want to make any judging comparison, just tried to figure out how
things change when using larger heightfields.  

Coding this technique into povray is an interesting idea, it surely makes things
more effective, but NTL you will have to decide whether you calculate things in
advance (leading to longer parsing time and more memory use), or during trace
(slowing it down).

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
Homepage: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

Christoph Hormann wrote:
> 
> Coding this technique into povray is an interesting idea, it surely
> makes things more effective, but NTL you will have to decide whether
> you calculate things in advance (leading to longer parsing time and
> more memory use), or during trace (slowing it down).

The option of calculating during the trace probably won't slow things
down that much.  The internal bounding for each patch can be done on the
fly with fairly good speed, and calculating the coefficients of the
quartics themselves is just as fast.  The fact that the patches are
quartic surfaces will make any additional calculations relatively
unimportant as far as speed considerations go.

Regards,
John
-- 
ICQ: 46085459

Post a reply to this message

There might be need for optimizing the number of objects created since they
take quite a lot of memory (just think about the gigantic heightfields used
in most scenes...).

  Could it be possible to use, for example, a higher order polynomial to
make a patch that covers 9 points (instead of 4)? The number of objects
would then reduce to 1/4, I think.
  You could go even further and make each patch to cover 16 points. In this
case a polynomial object is not enough (I think it would need an order higher
than 7, which is the max for polys), but you could do it with isosurfaces
(and isosurfaces render a bit faster than polys anyways).

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Warp wrote:
> 
> There might be need for optimizing the number of objects created
> since they take quite a lot of memory (just think about the gigantic
> heightfields used in most scenes...).

The method only uses that many objects because the renderer does not
support biquadric interpolation of height field data.  What could have
been done with one primitive had to be simulated with many.  A
height_field in POV-Ray has MxNx2 triangles, but it all counts as one
object.

Regards,
John
-- 
ICQ: 46085459

Post a reply to this message