   Tesselating a 2D level
  I have a 2D level:Its made up completally of line segments, they arent connected in a strip or anything, with the normals pointing out from the level.  I need to generate triangles to fill the entire "outside" of the level.  I think itd be some type of tessilation, but most of those want a single polygon, and I dont have one...   
  I don't think you understand what tessellation *is,* actually. It's a process of subdivision, not a flood fill. I think you're after the latter.   ;  Is there a floodfill that makes triangles from line segments?  Ive only heard of the pixel kind   ;Quote:Original post by zacajIs there a floodfill that makes triangles from line segments?  Ive only heard of the pixel kindYou're a programmer, this is the exact kind of problem you're supposed to be able to solve! :)Have you considered adapting the pixel fill algorithm to suit your needs? All you need to do is figure out what you can partition into blocks (which can be covered with two triangles, as I'm sure you're aware) and degenerate regions, which you can cover with triangles derived from a combination of box edge info and the line segments themselves. It isn't 100% ideal, but it should suit your needs.Is there a particular reason you can't do this by hand, either? It seems as if you could just do this yourself in less than a tenth of the time it would take were you to write and debug a program to do it for you.   ;  Basically, I just really dont want to have to manually tesselate all the levels.  Most of them will be giant, this is just a test I use because it has most of the different kinds of features a level could have.  A level with mostly diagonal lines isnt going to partition too well into blocks either   ;  Do you need to support individual lines? I'm assuming no, since the pic you posted has closed shapes (i.e no loose lines floating in mid-air). Two ideas:a) Why aren't the linesegs in strips? If you aren't going to have loose linesegs, you gain nothing by keeping them loose -- if all the shapes you're making are closed, then represent them as a closed set of lines.b) If you want to keep dealing with loose linesegs, you could just form a polygon and then triangulate it: find linesegs whose endpoints are within some small distance of each other and connect them, forming polygons.But (a) would certainly be easiest -- rather than trying to reconstruct/infer info, just explicitly provide it.   ;Quote:Original post by zacajBasically, I just really dont want to have to manually tesselate all the levels.  Most of them will be giant, this is just a test I use because it has most of the different kinds of features a level could have.  A level with mostly diagonal lines isnt going to partition too well into blocks eitherI had to do something similar recently - here are a couple of suggestions for approaches you might consider.I think the Triangle library would probably do exactly what you want (note that there may be licensing issues to consider when using this library).What you would do in this case is add a suitably large rectangle (four additional line segments) around the entirety of the level, and then use the Triangle library to build a Delaunay triangulation from the line segments making up the level. Triangle also allows you to specify areas that should be considered 'holes'; you would mark all areas except for the perimeter as holes, which would result in only the perimeter area (the area between the level perimeter and the enclosing rectangle) being triangulated.Another possibility would be to use the GLU tesselator, or any other tesselator that can handle polygons with holes. For this you'd need to provide a line loop (contour) representing the perimeter of your level (this might need to be done manually, but would certainly be less work than triangulating by hand).Feel free to ask if you have any questions or need further details.   ;  If you want to implement a solution yourself you should look up techniques on triangulation and monotone decomposition.  The idea is to consider the line segments as composing a polygon, then you will decompose that polygon into monotone polygons, which can be triangulated easily.  The algorithm for monotone decomposition of a polygon is not very difficult to understand, but I've found implementing it to be a chore.  Some resources:Polygon PartitioningPolygon TriangulationMonotone Decomposition (sort of a slide show, click through all of it);  jyk: Thanks, triangle looks perfect   