Jump to content
  • Advertisement
_WeirdCat_

Make tris out of 2d set of points

Recommended Posts

Im currently looking for some easy explanation of this algorithm for now i see that this pseudocode just removes newly created triangle from list making empty triangle list, i am not quite sure if that pseudocode could even work

For now what i get

Having a set of point get min and max if y and x then create big triangle that covers whole pointset area make a circumcircle out of that tri.

Add that tri to the output tri list

Then loop through all verts for int i loop

If a vertex is inside circumcircle of that super tri add that tri to badtri list

Now for each edge in bad tri

Check whenever other bad tri shares an edge if not add this not shared edge to some outputpolygon, so in first iteration it adds supertriangle to outputtrilist

Now remove that bad triangle from tri list

Now for each edge in outputpolygon form triangle to vert[ i ]

 

Now if that newly formed triangle contains a vetex from super triangle remove that triangle ---- now thats where my brain blows off you just added a triangle only to remove it damn.

 

Heres pseducode and below a link to code

 

 BowyerWatson (pointList)
      // pointList is a set of coordinates defining the points to be triangulated
      triangulation := empty triangle mesh data structure
      add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
      for each point in pointList do // add all the points one at a time to the triangulation
         badTriangles := empty set
         for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
            if point is inside circumcircle of triangle
               add triangle to badTriangles
         polygon := empty set
         for each triangle in badTriangles do // find the boundary of the polygonal hole
            for each edge in triangle do
               if edge is not shared by any other triangles in badTriangles
                  add edge to polygon
         for each triangle in badTriangles do // remove them from the data structure
            remove triangle from triangulation
         for each edge in polygon do // re-triangulate the polygonal hole
            newTri := form a triangle from edge to point
            add newTri to triangulation
      for each triangle in triangulation // done inserting points, now clean up
         if triangle contains a vertex from original super-triangle
            remove triangle from triangulation
      return triangulation

 

https://github.com/Bl4ckb0ne/delaunay-triangulation/blob/master/delaunay.h

 

This just doesnt make any sense...

 

x_X

Share this post


Link to post
Share on other sites
Advertisement
1 hour ago, WiredCat said:

Now if that newly formed triangle contains a vetex from super triangle remove that triangle ---- now thats where my brain blows off you just added a triangle only to remove it damn.

Notice that those step is done after all the points are added. So it does not remove the triangle just added, because any addition has been done much earlier in the previous loop. (Look at the indentation level.)

The step is just there to get rid of all those wrong triangles that were build with the super triangle's corners. This is because the corners of the super triangle are build artificially; in other words, those points are not part of the original set of point. Hence also none of the edges and none of the triangles that use those points belong to the result. 

Edited by haegarr

Share this post


Link to post
Share on other sites

But since within first iteration we apply super triangle to outputpolygon and then use its edges to form new triangles they always contain a point within supertriangle...

Share this post


Link to post
Share on other sites
15 hours ago, WiredCat said:

But since within first iteration we apply super triangle to outputpolygon and then use its edges to form new triangles they always contain a point within supertriangle...

Yes, the first iteration does produce only triangles that use an edge (and hence 2 vertices) of the super triangle. Also the second and (I think) third iterations uses such vertices. The third iteration is the first one where a triangle occurs that is uncoupled from super-triangle vertices. That's fine, because you need to have at least 3 vertices in your original set to have at least 1 triangle as output.

Look at the picture sequence of wikipedia's entry to Bowyer-Watson. Notice the red triangles: They are generated as needed but are rubbish in the end. The algorithm removes them in the last step. The blue triangles are all that remain as outcome.

Edited by haegarr

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!