PDA

View Full Version : Tessellation Question



pseudosig
06-04-2007, 03:00 PM
I originally posted this in the beginner section... and after further consideration... perhaps this is more advanced than beginner.

Here's my question:

I need some help with concave polygons. I wrote a program that can take 2d spatial data and create a list of vertices (counter clockwise) to define a contour. In this contouring of my data, I can have either convex or concave polygons... so GL_POLYGON is not an option in the case of a concave polygon (unless I decompose the polygon into convex primitives... which I don't intend to do).

My question is this: How can I most efficiently render these polygon contours which consist of both concave and convex polygons? I would really like to use VBO's, since they're so fast in rendering and my data is large... but it looks like I'm forced to use gluTessCallback but I don't know how to use gluTessCallback with VBO's or vertex arrays (or it's impossible).

Any help is appreciated...
thanks

Korval
06-04-2007, 04:27 PM
Turn each concave polygon into multiple convex polygons.

pseudosig
06-04-2007, 07:55 PM
From Me: (unless I decompose the polygon into convex primitives... which I don't intend to do).

From Korval: Turn each concave polygon into multiple convex polygons.

I specifically said this was not an option. So, is there a way to load these vertices in memory (i.e. VBO's or vertex arrays) AND use gluTessCallback... or something similar to render concave pollygons?

Korval
06-04-2007, 09:26 PM
So, is there a way to load these vertices in memory (i.e. VBO's or vertex arrays) AND use gluTessCallback... or something similar to render concave pollygons?No. You're doing something that the hardware doesn't want to do, and therefore you're stuck on the slow path.

If you want to be fast, abandon gluTessCallback and do the tessellation yourself. It's not that hard.

Olivier B.
06-05-2007, 12:59 AM
I agree Korval, you have to do tessellation yourself. But I don't understand why you say that :

unless I decompose the polygon into convex primitives... which I don't intend to do

pseudosig
06-05-2007, 05:07 AM
I have a lot of large polygons, most of which are concave. I have a simple triangulation alg. but it's much slower than gluTessCallback. I figured I wouldn't be able to write something faster than what glu provides... maybe this won't be the case.

Could you point me towards "faster" implementations of breaking down concave polygons into smaller convex ones?

thanks

ZbuffeR
06-05-2007, 05:22 AM
http://en.wikipedia.org/wiki/Polygon_triangulation

Hampel
06-06-2007, 03:24 AM
But it gets much more complex if you also have to deal with polygons with holes or self intersections.

Are there any pointers for implementations considering these configurations?

Edit: OK, it helps, if one scrolls down the given wikipedia link... :)

ZbuffeR
06-06-2007, 05:33 AM
Amanith seem very robust in this area :
http://www.amanith.org/forum/viewtopic.php?pid=43

If you feel like reading a lot :
http://mathworld.wolfram.com/Triangulation.html
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html
http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

pseudosig
06-06-2007, 07:20 AM
songho in OpenGL for beginners was able to answer this exactly the way I needed. GLU's implementation of breaking down arbitrary polygons (even w/ holes) is much faster than the various triangulation alg's I've been playing around with. Not only that, but glu allows one to get those broken down polygons via callbacks, so you only need to call the method once... and then grab those vertices.

Anyways, here's the link to his reply:

http://www.opengl.org/discussion_boards/ubb/ultimatebb.php?ubb=get_topic;f=2;t=021421;p=1#0000 01