QuadTree Based Mesh Tesselation Algorithm

Generates a triangular mesh divided into regions according to input polylines.

Motivation: For creating an interesting ground surface vs a quick triangulation.

Input criterion:

• Must contain coordinates such that points land on cell walls of the generated quadtree (ie either the x or y component must be an integer).
• Lines must define the id for the region to the right of the line and optionally for the region to the line's left if it isn't empty space. (Empty space is defined by index 0 so try not to use it for a polygonal region.)
• Input must also lie within the quadtrees boundaries. If a line exits from the quadtree it is ok, but if the line starts outside of the quadtree and enters into it (clipping) it is no good. (I included some examples of clipping algorithms you can use if unsure if the input is always going to be in range.)

Creates a static mesh geometry with discrete coordinates.

The quad tree is now using cached neighbours as that tested faster. Still you can refer to http://www.lcad.icmc.usp.br/~jbatista/procimg/quadtree_neighbours.pdf as it is neat.

Here's an example scene.

This scene was generated in the SceneTest.cpp file. The triangle vertex colours were modified on three factors.

1. The cell id (For the blocky look.)
2. The index of the point (For a smoother gradation.)
3. A random variance for each vertex generated. (Shows the individual triangles more.)

How it works.

• First, after inputing all the line points, a quadtree surface mapping is generated by subdividing a region using the following rule. If any region contains a point, subdivide into 4 equal child areas. Continue subdividing until a point is on a cell wall. Optionally, neighbouring regions may be subdivided if the difference in each regions subdivision depth is greater than 1 (so that if one square is subdivided small, neighbouring cells aren't super big in comparison).
• Once the region is mapped. Points are generated for the basic quadtree mesh using a sw to ne walk.
• Each line is ray cast against the grid to see where collides with the walls and if the point of collision does not coincide with a grid point, a point is added to the structure.
• (optionally) Duplicate line points are removed. (ie if 2 lines go to the same point, a duplicate point may have been generated)
• A record is kept of which cells were crossed by the lines.
• The cells that were cut through by lines are then triangulated. Triangulation occurs by a ccw boundary walk around the perimeter of the cell starting at the NE corner. The triangulation algorithm that follows can be applied to any convex shape cut through by non intersecting straight lines.
  • Walk around the perimeter ccw. When you reach a line intersection point, start a new polygon. When you reach the end of the line, finish the polygon.
• The rest of the quadtree cells are triangulated trivially using a floodfill method to determine which region each cell belongs to.

Examples were created using SFML. However the algorithm can work with anything that can be typedefed to a point. (ie, a struct with x,y coords and an overriden + operator)

Issues.

• Could always run faster, particularly the triangulateCellNode function. My brain is mushy after a bit and may go revisit that logic at a later time. However, the logic is sound and can handle input up to a range of 32000 due to using 32 bit unsigned integers for the quadtree direction vectors. (2 bits for out of bounds checking, and 2 bits for each level quadrant id for a resolution of 2^15)
• There's probably bugs to be found, ALWAYS. Hopefully if someone makes a better version, I can see it on github.
• The code is always messy.

Alternative approach.

• An alternative approach to an interesting background surface would be based on Delaunay triangulation. In that approach, I would subdivide each line with steiner points of a distance d. I would then generate new points using a poisson point generation algorithm with new points getting placed gradually getting farther and farther away. Then run a delaunay convex hull sweep line algorithm on the point structure. Then I would search through all the points till I find a line start, walk along the line through the mesh cutting if have to. However, if I subdivided the line appropiately, hopefully I wouldn't have to cut that much. Would create a more random structure than the grid effect here though. And if I can code at all maybe a bit slower.

A couple pretty pictures.

Testing pointy polygons contained one inside the other. This was before I added balancing to the quadtree. The black is the result from not mapping each line's right/left regions properly resulting in the floodfill algorithm getting confused about the region being inside or outside.

Just a random line wiggling through a larger quadtree.