Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Quadtree based Mesh Generator for 2D Surfaces  (Read 3292 times)

0 Members and 1 Guest are viewing this topic.

LucasM

  • Newbie
  • *
  • Posts: 13
    • View Profile
    • Email
Quadtree based Mesh Generator for 2D Surfaces
« on: January 22, 2022, 06:50:05 am »
Made a quadtree based mesh renderer for 2d surfaces.  You can use it for procedural terrain generation especially if you want a more blocky grid type look, or even if not.  I posted the source at https://github.com/LucasM127/QuadTreeTesselation  And made a decent looking readme there so I won't type too much more here.  Made it while developing some ideas I had for procedural terrain generation (in 2d) to make a more interesting looking surface.
I came up with the idea for triangulating convex polygons that had been sliced through on my own though so that was neat and motivated me to develop this idea further.

The examples are made with sfml.  It is not 100% finished but I don't think anything ever will be.  Not too many other examples of this that I could find on github.  Most were more oriented to making a grid for finite element analysis than for creating distinct surface regions.

The algorithm itself is not based on sfml however.

The codes not polished but I've pretty much given up on having perfect code after a while.  It gets better, but never great.

Hopefully someone may find it interesting.

eXpl0it3r

  • SFML Team
  • Hero Member
  • *****
  • Posts: 10800
    • View Profile
    • development blog
    • Email
Re: Quadtree based Mesh Generator for 2D Surfaces
« Reply #1 on: January 23, 2022, 07:16:17 pm »
I like the images in the readme, you should link them in your post here as well ;)

What algorithm did you use for the tesselation?
Official FAQ: https://www.sfml-dev.org/faq.php
Official Discord Server: https://discord.gg/nr4X7Fh
——————————————————————
Dev Blog: https://duerrenberger.dev/blog/

LucasM

  • Newbie
  • *
  • Posts: 13
    • View Profile
    • Email
Re: Quadtree based Mesh Generator for 2D Surfaces
« Reply #2 on: January 24, 2022, 12:47:26 am »
The quadtree mesh algorithm is kind of similar to the idea posted here: http://homepages.math.uic.edu/~jan/mcs481/quadtrees.pdf

I just divided the quadtree till each line point was on a cell 'wall' so that either a cell would contain no lines, or would contain lines cutting through the whole length of the cell.

Triangulating the empty cells was pretty trivial (just see whether the cell needed steiner points or not and create triangles based on a set of predefined triangulations).

To triangulate the cells cut through by the lines, I used a border walk polygonization strategy that I don't know the name of the algorithm as I came up with it myself (though I doubt I am the first to do so).  I uploaded a pic on github to explain that algorithm better.  https://raw.githubusercontent.com/LucasM127/QuadTreeTesselation/master/Pics/BorderWalk.jpeg

The whole point of using a quadtree vs a regular grid was to have different sized squares for variety and also to save on number of triangles rendered.  The look is also a bit 'different' than delaunay.  That's all.