Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Page 1 of 2 12 LastLast
Results 1 to 10 of 17

Thread: Polygon tesselation

  1. #1
    Junior Member Newbie
    Join Date
    Apr 2002
    Location
    Bla,bla
    Posts
    12

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

  2. #2
    Senior Member OpenGL Guru knackered's Avatar
    Join Date
    Aug 2001
    Location
    UK
    Posts
    2,833

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

  3. #3
    Senior Member OpenGL Guru
    Join Date
    Mar 2001
    Posts
    2,411

    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.
    "If you can't afford to do something right,
    you'd better make sure you can afford to do it wrong!"

  4. #4
    Senior Member OpenGL Guru knackered's Avatar
    Join Date
    Aug 2001
    Location
    UK
    Posts
    2,833

    Re: Polygon tesselation

    Oh yeah
    Knackered

  5. #5
    Advanced Member Frequent Contributor
    Join Date
    Feb 2000
    Location
    France
    Posts
    880

    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. #6
    Junior Member Regular Contributor
    Join Date
    Feb 2002
    Posts
    125

    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. #7
    Advanced Member Frequent Contributor
    Join Date
    Feb 2000
    Location
    France
    Posts
    880

    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. #8
    Junior Member Newbie
    Join Date
    Apr 2002
    Location
    Bla,bla
    Posts
    12

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

  9. #9
    Member Regular Contributor
    Join Date
    Jul 2000
    Location
    Augsburg, Germany
    Posts
    334

    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. #10
    Junior Member Regular Contributor
    Join Date
    Feb 2002
    Posts
    125

    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
  •