PDA

View Full Version : OT: algorithms behing NV_evaluators



Julien Cayzac
08-01-2002, 08:14 AM
Cass/Matt> could you guys post a few references (being links to papers or just names) about the methods implemented in NV_evaluators?

I try to allow per-edge tesselation in my own engine but I can't get an effective algorithm (and when I'm thinking about tesselating the result, I simply have nightmares http://www.opengl.org/discussion_boards/ubb/tongue.gif).

Thanks,
Julien.

AdrianD
08-01-2002, 08:25 AM
http://www.gamasutra.com has some interesting features about tesselating bezier patches in the archive.

Julien Cayzac
08-01-2002, 08:49 AM
I only found Rayner's article on Gamasutra, but it's not very useful since if you want a (2, 2, 100, 100) tesselation you will endup with a uniform 98x98 grid with some fixing ribbons around http://www.opengl.org/discussion_boards/ubb/frown.gif

I don't find anything related to non-uniform tesselating+stripifying.

Julien.

martin_marinov
08-01-2002, 11:20 AM
Hi
Usually people use non-adaptive tesselation techniques
per patch - it is much easier, because of problems related to handling cracks. I dont know how NV_evaluators works however. If you may post additional info what do you want to do, I may be able to help you. Btw, for bigger surfaces, using subdivision representaions might be better than using NURBS/Beziers. Still it depends of a lot of things.
Regards
Martin

Julien Cayzac
08-01-2002, 12:36 PM
Originally posted by martin_marinov:
I dont know how NV_evaluators works however.

Martin,
The NV_evaluators specifications can be found here (http://oss.sgi.com/projects/ogl-sample/registry/NV/evaluators.txt) .
It allows independant per-edge fractional tesselation.

I think fractional tesselation is not relevant, but I need per-edge tesselation.
I just found this (http://www.flipcode.com/tpractice/issue04.shtml) article on flipcode, but the involved algorithm assume each tesselation factor is a power of 2, which is quite restrictive.

However, I'm trying to get a scanline-based approach to work.

Julien.
(edit: UBB-code crap fixing)

[This message has been edited by deepmind (edited 08-01-2002).]

martin_marinov
08-01-2002, 02:51 PM
Hi
I read the extension specs, it seems NV_evaluators is really quite flexible. Is the implementation also fast? I mean in the most nasty case, when you have different tessellation parameters for u0, u1, v0, v1?
Btw, maybe it is time for .pdf version of these specs ;-).

I don't have idea how they do it, but if you don't need this for real time evaluation, there is something very stupid and slow, which you can do, probably you already know it. I'll speak only for quad patches.
The problem is how to tessellate the quad domain [0..1]x[0..1], i.e finding the (u,v) of the points on the patch, and the triangles. Then you can do something standard to evaluate for the vertex attributes for this (u,v).
So lets go first in the one of the two directions, lets say u. you have to put n + 1 points on the one edge, and m + 1 on the other. Lets say their coords are (u00 ... u0n) and (u10..u1m). Building (triangular) tessellation for this is not unique, but lets say we do it this way: starting from the edge u00, u10, we add to the triangle u11 if u11 < u10, otherwise u10. In the first case if there are points u12, u13, u1k <= u10, you connect them to u10 (like a fan). For the second case you do the same with respect to u11. When you find a point u1k for which u10 < u1k, and in the second case u0k, u11 < u0k, you connect to it, switch to it and continue :-).
So this is one (I think reasonable) triangulation, it's maybe not “the best” one however. But it is not “the worst” (guess which one is it...) http://www.opengl.org/discussion_boards/ubb/smile.gif)
Now here comes the nasty part: do the same for the v direction. Intersect the domain triangles (this 2D problem, not 3D, so its a bit simpler) and you end up with tris and quads, triangulate the quads, and you have a solution http://www.opengl.org/discussion_boards/ubb/smile.gif)
but this is useless for real-time of-course, and maybe there are other problems which I don't see now:-)

Regards
Martin

vegark
08-02-2002, 12:33 AM
Take a look at the Eurographics/SIGGRAPH Graphics Hardware Workshop 2001 paper
"Watertight Tessellation using Forward Differencing", by Henry Moreton, NVIDIA

This paper describes the tesselation of spline surfaces in HW.

But it's not easy to get hold of without an ACM login, or access to the Eurographics proceedings.

--
Vegar

Julien Cayzac
08-02-2002, 05:03 AM
Martin> NV_evaluators are quite slow. I think this is because of the fractional tesselation scheme. I need realtime tesselation, so I won't use the method you described. Thanks anyway for providing it http://www.opengl.org/discussion_boards/ubb/smile.gif

Vegark> Doooh I don't have an ACM login http://www.opengl.org/discussion_boards/ubb/frown.gif Would it be illegal if you send me that paper via email? http://www.opengl.org/discussion_boards/ubb/tongue.gif

I'll search for that NVidia guy on google. He might have made some related papers available on his site. Thanks for the info!

Julien.

Julien Cayzac
08-02-2002, 05:35 AM
Ok I found a presentation at http://www.graphicshardware.org/previous/www_2001/presentations/moreton-FDT.pdf . However, I'm a bit disappointed since it does a semi-uniform tesselation and only fixes borders, as in Rayner's article at Gamasutra.

I think I'll go with the algorithm I've been working on. It basicaly divides a patch in uniformly tesselated triangle sub-patches. It's slow but the good news is I can precalc several subdivisions and switch at runtime...

Julien.

martin_marinov
08-02-2002, 07:30 AM
Hi
How fast you need your algorithm to be?
You know, there is always a trade-off here:
you may have very complicated, but flexible tesselation algorithm, and to draw just the needed triangles, or you can have a simple and not so flexible algorithm, which for example does something like balanced adaptivness(you have conditions over the LOD of the connected patches). You will render more triangles with it, but it still may be faster, because the tesselation&evalution algorithms are much more simpler...
This is one reason why ppl still use mainly uniform/semi-uniform tesselation :-)

Regards
Martin