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