As some of you might know, I'm the author of several "meant for, but not
used by, the public" Include-Files. ;-)

Some of them are based upon 2d-arrays filled with vertices, in effect
defining a grid for a twodimensional, rectangular mesh. My wave-simulation
macros are also based upon such an array. Lately I'm annoyed but the
quality, or lack there-of, for the wave-mesh. As the algorithm relies upon
the grid and the effect is greatly influenced by the amount of nodes, I tend
to use few nodes for a better visual effect of the waves, but this comes at
the cost of very "trianglish" meshes.

My idea, heavily influenced by recent courses at the university, was thus to
add some subdivision process to my mesh-creating macros.

I've googled extensively for different subdivision methods to find what I
was looking for, but, without the insight I'd like to have, I've got no idea
where to start, actually. So I figured I'd give it a shot here and hope that
someone with more expertise can point me towards some bright mind which came
up with exactly what I'm in need of.

Now, what I have is this: the above-mentioned grid of vertices. As POV-Ray
doesn't have quads (and since the grid almost never describes planar quads)
the grid is visualized using triangles. If the edge of a quad is split like
/ or like \ depends on which two points are closer, works like a charm most
of the time.
I also generate averaged surface normals for smooth_triangles by calculating
the normals of the triangles, then averaging all those for each adjacent
vertex.

Now, what I'd like to have is a subdivision method which will *keep* the
first set of nodes and normals, and simply "add" new ones for a smoother
display. The methods I've found so far will somehow alter the original set
(or simply drop it in favor for the subdivided one, which complies to the
convex-hull-type of thinking, but that's not what I'm after).

The best I could come up with so far was using bilinear interpolation using
the corners of the quad, but adjacent quads won't line up properly that way
and I'd have smooth quads, but I guess I'd end up with obvious edges between
them (haven't tested that so far, but will tomorrow).

So, if anyone knows of a subdivision method based upon triangles (along with
surface normals for each vertex, if possible)... I'm investigating Loop's
subdivision for this, but I'm not sure if it'll do what I want it to. Notice
that due to the 2d-array basis of my macros I need to retain that as well,
so the subdivision should end up with a larger array.

If you've got something for me, please post a link here. :-)

Thanks in advance,
Tim

-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

How about creating a bezier patch for each quad? Then the subdivision level 
can easily be controlled. And there are macros that take exactly a 2d array 
of points and create a bezier patch "cloth" from them, automatically 
creating all but the corner control points in the process (the corner points 
being the ones that comes from the original 2d array).

If you don't want to use POV-Ray's bezier patches, you can still use the 
algorithm used in bezier patches. I don't know if it really counts as a 
subdivision algorithm, but at least it creates a smooth surface while 
keeping the first set of nodes. Depending on how the control points for the 
bezier curves are calculated, it might or might not also keep the first set 
of normals. The method I use doesn't, but it seems to me like it's not that 
important here anyway, since you just calculate the normals from the points 
in the first place. Just think of it as the normals being calculated at a 
different stage in the process.

I know you like to code everything from scratch yourself. I don't remember 
if you even already have created macros for generating bezier patches from 
2d arrays yourself (I seem to vaguely remember that you have, but I might be 
wrong), but if not, there are macros out there to get inspiration from. I 
created some once that I still have lying around, in case you're interested.

Rune
-- 
3D images and anims, include files, tutorials and more:
rune|vision:  http://runevision.com
POV-Ray Ring: http://webring.povray.co.uk

Post a reply to this message

Hey Rune! Nice to hear from you! :-)

> How about creating a bezier patch for each quad? Then the subdivision
level
> can easily be controlled. And there are macros that take exactly a 2d
array
> of points and create a bezier patch "cloth" from them, automatically
> creating all but the corner control points in the process (the corner
points
> being the ones that comes from the original 2d array).
SNIP

I thought about that and actually tried that when fiddling with bilinear
interpolation. I think I could come up with an implementation, shouldn't be
too difficult: calculate the control-nodes on the edges first and then
interpolate among the neighbours to get the inner control points (of course
keeping in mind that neighbouring patches need to have the same angle to the
edge to keep the edges smooth).
What's stuck in my head though when using bicubic-patches is their tendency
to fall apart when you go into too small and too large values (the usual
precision problem). But nontheless, I might go ahead and implement it
anyway, because it'll sure be of use to someone, and who knows, maybe it
*does* work for me, too! :-)

When you implemented this, did you have some paper as a guide, or did you
make it up yourself (which has a tendency these days to result in some
technique someone somewhere else has also come up with, sigh)? If you've
followed a paper, I'd be interested in it because of the mathematical
background like second order continuancy and such. If you did it yourself,
I'd be interested in the macro and maybe a short explanation how you came up
with it, and, if you still remember, what you tried and didn't work until
you ended up with the final version. You can send it via email, of course.
:-)

Thanks for the reply,
Tim

-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

Rune wrote:
> How about creating a bezier patch for each quad? [...]

Note that this would have serious parse performance advantages (since 
generating the mesh from the patch definition is done internally) but 
render time performance would be better with one single mesh.

Some useful hints for subdivision can be found on:

http://www.rhythm.com/~ivan/dispMap.html

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 27 Feb. 2005 _____./\/^>_*_<^\/\.______

Post a reply to this message

Tim Nikias wrote:
> Hey Rune! Nice to hear from you! :-)
> 
> 
>>How about creating a bezier patch for each quad? Then the subdivision
> 
> level
> 
>>can easily be controlled. And there are macros that take exactly a 2d
> 
> array
> 
>>of points and create a bezier patch "cloth" from them, automatically
>>creating all but the corner control points in the process (the corner
> 
> points
> 
>>being the ones that comes from the original 2d array).
> 
> SNIP
> 
> I thought about that and actually tried that when fiddling with bilinear
> interpolation. I think I could come up with an implementation, shouldn't be
> too difficult: calculate the control-nodes on the edges first and then
> interpolate among the neighbours to get the inner control points (of course
> keeping in mind that neighbouring patches need to have the same angle to the
> edge to keep the edges smooth).
An internal representation where at every node you record the x,y and z
position plus the derivatives in the u and v direction plus the second
derivative in the uv direction (a set that can be used to create a
smooth surface using Hermite polynomials) can uniquely be converted to a
smooth bicubic patch. I only mention this because it might be a more
natural set of parameters to work with during computation.

Post a reply to this message

Hey, thanks for the link! Not only is the subdivision stuff interesting, but
the other stuff as well! :-)

-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

> An internal representation where at every node you record the x,y and z
> position plus the derivatives in the u and v direction plus the second
> derivative in the uv direction (a set that can be used to create a
> smooth surface using Hermite polynomials) can uniquely be converted to a
> smooth bicubic patch. I only mention this because it might be a more
> natural set of parameters to work with during computation.

Hm, you're right. Question is if the added complexity is worth the effort.
Simply adding the nodes along the edges first, then accessing the various
finished nodes to average the inner nodes doesn't look that complicated to
me.

But I'm actually getting in favor of subdividing the triangles, looks
somewhat easier to me. :-)

-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

Tim Nikias wrote:
>>An internal representation where at every node you record the x,y and z
>>position plus the derivatives in the u and v direction plus the second
>>derivative in the uv direction (a set that can be used to create a
>>smooth surface using Hermite polynomials) can uniquely be converted to a
>>smooth bicubic patch. I only mention this because it might be a more
>>natural set of parameters to work with during computation.
> 
> 
> Hm, you're right. Question is if the added complexity is worth the effort.
> Simply adding the nodes along the edges first, then accessing the various
> finished nodes to average the inner nodes doesn't look that complicated to
> me.
> 
> But I'm actually getting in favor of subdividing the triangles, looks
> somewhat easier to me. :-)
> 
Will you be starting from a square grid and start subdividing or will
you start from a hexagonal grid?

Post a reply to this message

> Will you be starting from a square grid and start subdividing or will
> you start from a hexagonal grid?

Square-Grid. The triangulation uses the nearest-neighbour approach to decide
how the quad is split into triangles. Why?

-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

Tim Nikias wrote:
>>Will you be starting from a square grid and start subdividing or will
>>you start from a hexagonal grid?
> 
> 
> Square-Grid. The triangulation uses the nearest-neighbour approach to decide
> how the quad is split into triangles. Why?
> 
Because it might be more realistic if you do all the computations in
a triangular grid to begin with. Otherwise you have artifacts that
come from the square grid _and_ from the triangulation afterwards.
That all depends also of course on the algorithm used.

Hmm, did I say hexagonal grid? I meant of course a triangular grid with
equilateral triangles or equivalently a regular one with six neighbours
each.

Post a reply to this message

Tim Nikias wrote:
> Hey, thanks for the link! Not only is the subdivision stuff interesting, but
> the other stuff as well! :-)
> 

My parametric surface generator uses uv-interpolated points.  Basically I 
interpolate the parameters and calculate the function at that point:

p(i,j) p(i+1,j)
  i(i+.5,j+.5)
p(i,j+1) p(i+1,j+1)

Now my "quads" are split into 4 triangles each, at the cost of (at most) 
doubling the number of points.  I think the effect is called face-centered square.

Mind you I now have to keep track of whether the u and/or v loops are closed or 
not.  A far edge of the interpolated grid goes away if its associated loop is open.

--------------
David Wallace
TenArbor Consulting
"Just In Time Cash"
www.tenarbor.com
1-866-572-CASH

Post a reply to this message

> Because it might be more realistic if you do all the computations in
> a triangular grid to begin with. Otherwise you have artifacts that
> come from the square grid _and_ from the triangulation afterwards.
> That all depends also of course on the algorithm used.

That's the trouble my latest attempts have run into. I always get artifacts
somewhere. It might work for a single subdivision step, but once I use it
twice or thrice, I get rectangular patterns. Sigh.

> Hmm, did I say hexagonal grid? I meant of course a triangular grid with
> equilateral triangles or equivalently a regular one with six neighbours
> each.

The source I start with is a 2d-grid of points, like the corners on a
checker field. Useful for various simulations, but, as I've found now, quite
difficult to handle for subdivision.

With the last few hours of failed attempts I've decided to let this idea
rest for a while, until I've got more time and patience (and concentration)
at hand. Due to university courses I've got so much other stuff to take care
of and think about, that I can't really focus on this.

Thanks for all the comments anyway, they'll be useful when I get back to
this macro. :-)

Regards,
Tim

-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

> My parametric surface generator uses uv-interpolated points.  Basically I
> interpolate the parameters and calculate the function at that point:
>
> p(i,j) p(i+1,j)
>   i(i+.5,j+.5)
> p(i,j+1) p(i+1,j+1)
>
> Now my "quads" are split into 4 triangles each, at the cost of (at most)
> doubling the number of points.  I think the effect is called face-centered
square.

I've googled for this, but didn't find any site or pdf explaining this. Have
you got something on this topic which you could share with me? Additionally,
where can I find this surface generator of yours, is it a POV-Ray Macro, or
some external app?

Note though (also stated in a post to Andrel) that I'll leave the plans for
this subdivision macro of mine rest for a while, as I've got too much other
stuff to do and think about that I don't really have the time, patience and
concentration to script a proper subdivision macro. Still, anything I can
find and archive about this will sure come in handy when I get back to it.

Regards,
Tim
-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

Tim Nikias wrote:
>>Because it might be more realistic if you do all the computations in
>>a triangular grid to begin with. Otherwise you have artifacts that
>>come from the square grid _and_ from the triangulation afterwards.
>>That all depends also of course on the algorithm used.
> 
> 
> That's the trouble my latest attempts have run into. I always get artifacts
> somewhere. It might work for a single subdivision step, but once I use it
> twice or thrice, I get rectangular patterns. Sigh.

That was why I suggested triangiular grids. They have the additional
property that circular ripples are more close to hexagons (that you can
make with triangles (finally got the hexagons in in the right context
;) ).
> 
>>Hmm, did I say hexagonal grid? I meant of course a triangular grid with
>>equilateral triangles or equivalently a regular one with six neighbours
>>each.
> 
> 
> The source I start with is a 2d-grid of points, like the corners on a
> checker field. Useful for various simulations, but, as I've found now, quite
> difficult to handle for subdivision.
> 
> With the last few hours of failed attempts I've decided to let this idea
> rest for a while, until I've got more time and patience (and concentration)
> at hand. Due to university courses I've got so much other stuff to take care
> of and think about, that I can't really focus on this.
> 
> Thanks for all the comments anyway, they'll be useful when I get back to
> this macro. :-)

I assume you use a rectangular grid for ease of representation. To my
surprise it is not commonly known (or at least used) that when you
/pretend/ that in every alternating row the gridpoints are shifted one
half that you get conceptually a triangular grid. Gridpoints on every
odd line will be connected to the points to the left on the adhacent
rows and the even to the ones on the right. You can find out what the
real neaghbours are with a simple bit mask. If I make myself clear,
probably not :(


*   *   *   *
   *   *   *   *
*   *   *   *
   *   *   *   *
*   *   *   *

There is a small disadvantage that this grid is a bit anisotropic, so
you may have to account for that in the computation.

Post a reply to this message

> I assume you use a rectangular grid for ease of representation. To my
> surprise it is not commonly known (or at least used) that when you
> /pretend/ that in every alternating row the gridpoints are shifted one
> half that you get conceptually a triangular grid. Gridpoints on every
> odd line will be connected to the points to the left on the adhacent
> rows and the even to the ones on the right. You can find out what the
> real neaghbours are with a simple bit mask. If I make myself clear,
> probably not :(

Oh, I understood fine. That's something to keep in mind in case I write
future macros that might need them. As it is now, my MMM and LSSM work on
the rectangle-grid. I've got no excuse for the MMM aside that it was just
easy to visualize and represent the data in an array, but for the LSSM, the
algorithm is deriven from a technique that normally works on textures and is
pixel-based, hence 2d-grid instead of hexagon.

I've got in mind to script a more versatile set of macros for
vertex/normal/UV generation on arbitrary topology (something close to the
usual mesh2-format, with arrays of vertices, normals and uvs, which are
index with a fourth array to build the actual mesh). But that'll have to
wait till I've got some spare time *and* a use for it. :-)

-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

Tim Nikias wrote:
>>I assume you use a rectangular grid for ease of representation. To my
>>surprise it is not commonly known (or at least used) that when you
>>/pretend/ that in every alternating row the gridpoints are shifted one
>>half that you get conceptually a triangular grid. Gridpoints on every
>>odd line will be connected to the points to the left on the adhacent
>>rows and the even to the ones on the right. You can find out what the
>>real neaghbours are with a simple bit mask. If I make myself clear,
>>probably not :(
> 
> 
> Oh, I understood fine. That's something to keep in mind in case I write
> future macros that might need them. As it is now, my MMM and LSSM work on
> the rectangle-grid. I've got no excuse for the MMM aside that it was just
> easy to visualize and represent the data in an array, but for the LSSM, the
> algorithm is deriven from a technique that normally works on textures and is
> pixel-based, hence 2d-grid instead of hexagon.
I know you understood it, but let me reiterate that you can even
reinterpret a rectangular grid of pixels as a grid of hexagons.
It is at first sight counterintuitive, but I sometimes use it
for erosions and dilations if I want the operations to be invariant
for foreground/background inversions.

Post a reply to this message

I may have something.
 I use natural_spline to interpolate a height field image of MARS. I wanted to
get a better view close up( like on the surface). It should work with any array
of points as long as the points a line on the grid. It's not a macro yet.
 How it works is:
An array is made so that it can hold all the points and all the interpolated
points in between. The original array of points are place and spread out(only
the heights are placed) to what every degree of division you want.
  A spline for a row is made with the placed points as contol points. Then the
interpolated points are calculated and placed. After all the rows with points in
them are done then all the columns can use the array to fill the
control points for another natural_spline.
 If you need something like this, give me awhile, I'll clean it up for you and
send it to ya.

--
Have Fun!

Post a reply to this message

>  I use natural_spline to interpolate a height field image of MARS. I
wanted to
> get a better view close up( like on the surface). It should work with any
array
> of points as long as the points a line on the grid. It's not a macro yet.

Hm, a natural_spline, you say? I might have a look at that, but after your
description of the process, I don't think you need to clean it up just for
me. I guess I could quickly script the macro myself with that approach, just
have to figure out how natural_splines work, and/or if I might want to use a
different one.

At the moment I'm working on different things and I haven't got much need
for the subdivision of my wave-meshes, still, thanks for the reply
nontheless!

Regards,
Tim

-- 
aka "Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message

I went ahead and dress it up a bit then put it in the binaries_scene_files under
Mars_Mesh. Where it might be some use to you and others .



--
Have Fun!

Post a reply to this message