Polygon tesselation

Hello,
im interested, is someone knew which algo use p. tesselation for traversing vertices, or does it even traverse it ;-), and where could i find formula or formulas ?

Thanx.

For every triangle…
Calculate area of triangle.
If area is greater than your threshold area
find the longest edge
find the midpoint on this edge
Create a new vertex at this midpoint
delete triangle, and create 2 new triangles out of the 4 vertices
loop back until all triangles processed

repeat the above until no triangles have an area above your threshold area.

You have to split all triangles sharing the longest edge at the same time, else you’ll get T junctions. That means, for manifold meshes, you delete 2 triangles and add 4 triangles for each edge split.

Oh yeah

knackered, jwatte,

Did I misunderstand the question ?

For me polygon tesselation is the method that breaks a polygon into triangles.

In the algorithm knackered described, he starts with “for every triangle” which supposes that you already have a triangulation…

Or perhaps it’s just me on monday morning !

Regards.

Eric

P.S.: sz, I tried to find info about triangulation a while ago and if that’s what you’re interested in, look for “Delaunay triangulation” on the web.

Guys please eaze up a little here. Yes any polygon can be broken down into triangles. If you are using opengl and want any form of speed then your “polygons” probably already are composed of triangles. Even if they aren’t properly dividing an arbitrary polygon into triangles is probably more difficult that simply tesselating triangles. Chance for concavities and you know the jazz.

The basic rule of splitting the longest edge works and works great. Most of the time though the new vertices are perturbed slightly based on the underlying mesh. Very similar to bump mapping where you calculate a du,dv, in this case its a dx,dy and I’m not going into detail. The point being that the newly created vertices are usually smoothed so that the surface is closer to being a curve. Basically implementing a MeshSmooth as in 3d Studio Max, Maya or whatever resonably decent modeling package.

Happy Coding.

Originally posted by Devulon:
Guys please eaze up a little here.

Can I ask you why you say that ?

Regards.

Eric

Thanx guys,
so lets sum, let take code :

For every triangle…
Calculate area of triangle.
If area is greater than your threshold area
find the longest edge
find the midpoint on this edge
Create a new vertex at this midpoint
* delete triangle, and create 2 new triangles out of the 4 vertices
loop back until all triangles processed
repeat the above until no triangles have an area above your threshold area.

hm, i had simmilar idea, but in code, i marked position with *, i think that there is no need to delete current triangle 'cos when we split it, that triangle “become” two other, and so on

And for Eric question:
“In the algorithm knackered described, he starts with “for every triangle” which supposes that you already have a triangulation…”

well when i asked, i didn’t think about triangulation, but, is known, every poly can represent with triangles, i think with infinity triangles (nice theorem ) .

PS.
maybe ill need to look in Mesa code, and see how they implemented this

Thanks guys

Sanel

I hope I did not understand the question wrong… you wanted an algorithm how to triangulate a polygon? The Seidel Algorithm is often used, e.g. http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html or a search on Google on “Seidel Algorithm”.

It basically makes horizontal lines at each vertex and triangulates there.

Kilam.

[This message has been edited by Kilam Malik (edited 04-15-2002).]

I said eaze up just as a response to everyone here always being so technical. It was meant as a joke nothing more. It’s just a general impression I have gotten in the advances forum. This isn’t directed at you Eric, its just that some people seem to be really anal. Don’t think anything about what I said.

( :

Devulon

Devulon, I didn’t take it as an offense, I was just wondering what you meant !

Regards.

Eric

I think that Kilam was the only one that answered the question.

However triangle subdivision is also an interesting topic. I wonder why the criteria is the triangle’s area. I thought it would be something more like aspect ratio. I guess it depends on the type of mesh you want.

Originally posted by billy:
I think that Kilam was the only one that answered the question.

So you didn’t like my reference to Delaunay Triangulation ?

Regards.

Eric

Wow people,
i thought that will be only few answers on this topic
I visited Kalim’s link, and that algo is something what im looking for.
But, , i also noticed increesing time with number of vertices. Well now in my head there is few methods how to avoid this, and speed up things.

Devolution, plese could you explain little bit your post and methods in 3DsMAX and Maya ?

PS.
anyone knows nice link with nice collection of usefull algos ?

I wish i had an algorithm. I haven’t started doing subdivision yet (short of really simply subdivision on terrain). That project was short lived. Anyway that code is worthless so I won’t waste your time.

To clarify my post I was simply pointing to the fact that any modelling/animation package worth its salt will have some form of MeshSmoothing which is basically subdivision/Tesselation. Whatever you want to call it. The only real difference is that Tesselation doesn’t change topology and Mesh Smoothing intentionally does change topology (to smooth !!).

More and More recently with the advent of faster computers and faster video cards people are starting to implement things such as tesselation in realtime. These are algorithms that for a long time were part of modelling but simply couldn’t be done in realtime.

Devulon

I commented on knackereds post, I did not answer the question. Sorry.

Here’s one (naive, but working) approach to tesselate a polygon into triangles, supporting concave polygons as long as they are not self-overlapping.

While( polygon has > 3 vertices )
Find first sequence of 3 successive vertices which describes a triangle which is INSIDE the polygon
Remember this triangle in your output set
Remove the middle vertex from the polygon

Note that the “Find” part is guaranteed to terminate. The self-overlapping / holes-inside case is MUCH harder. Do a google and read up on it if you don’t believe me

If the polygon is convex, any sequence of 3 successive vertices will describe a triangle that’s inside the polygon, and thus this algorithm would generate a fan out of a convex polygon.