# The Industry's Foundation for High Performance Graphics

1. ## 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.

2. ## Re: Polygon tesselation

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.```

3. ## Re: Polygon tesselation

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

5. ## Re: Polygon tesselation

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.

6. ## Re: Polygon tesselation

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.

7. ## Re: Polygon tesselation

Originally posted by Devulon:
Guys please eaze up a little here.
Can I ask you why you say that ?

Regards.

Eric

8. ## Re: Polygon tesselation

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

9. ## Re: Polygon tesselation

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).]

10. ## Re: Polygon tesselation

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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•