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.
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.
SZ.
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.
Knackered
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.
"If you can't afford to do something right,
you'd better make sure you can afford to do it wrong!"
Oh yeah
Knackered
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.
Can I ask you why you say that ?Originally posted by Devulon:
Guys please eaze up a little here.
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
SZ.
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