![]() It supports the intuition that we want to move vertices as little as possible (and would rather move two vertices distance \(d\) than one vertex distance \(2d\)).The resulting optimization problem is easier.The squared distances were chosen because Then, given the center of mass for the square (which is the same as the quadrilateral’s) and the desired side length, we want to find an angle \(\alpha\) which minimizes the sum of squared distances between quadrilateral vertices and square vertices. We start with an arbitrary quadrilateral, and order the vertices clockwise around the center of mass. This smoothly moves the vertices to create a nice grid-like structure:Īn appendix for the curious: explanation of my method for finding the “closest” square to a given quadrilateral. Using this technique we can iterate over the quadrilaterals, and accumulate for each vertex the “squaring forces” from all the quadrilaterals it belongs to. Is oriented such that the sum of squared distances from each quadrilateral vertex to the corresponding square vertex is minimizedĬoupled with calculus, this formulation admits a closed-form solution for the square angle which looks quite good:.Shares the same center of mass as the quadrilateral.Eventually I tackled the problem very explicitly: for each quadrilateral, I want to find a square which. For this step I tried a lot of different things which didn’t work out, such as trying to simulate particles with attraction and repulsion forces. The next part will attempt to make all quadrilaterals more square-like. We now have a quadrilateral mesh with interesting connectivity, but it doesn’t look anything like a grid. Some triangles remain as this merging technique is not guaranteed (and usually doesn’t) result in a proper quadrangulation.įinally, each triangle / quadrilateral is tiled with smaller quadrilaterals, to give us the final quadrilateral mesh: Before merging I make sure that the resulting quadrilateral is convex and doesn’t contain angles that are too sharp (\( 0.9 \pi\)). Then, triangles are iteratively merged to form quadrilaterals. This is followed by a Delaunay triangulation and filtering out triangles with too-obtuse angles (I chose \(0.825 \pi\) as the upper threshold): The first step is to sample 2D points using Poisson disk sampling: This involved a lot of trial and error (mostly error), but I’m pretty satisfied with the end result. I found his approach very clever but also very different from what I’d intuitively try, so I was curious to try my own approach at generating such a grid. Oskar has a great talk where he explains how various aspects of the game work, including the grid generation. One of the features I really liked is the “organic grid”: Townscaper screenshot. Oskar Stålberg’s Townscaper is a beautiful city-building game based on procedural generation.
0 Comments
Leave a Reply. |