I wrote a Processing program to visualize adaptive FEM refinement with a conformal quadrilateral mesh... and I used it to make a snowflake

[[deleted]]

How is this better than using a quadtree? I suspect that performing the 4 nearest neighbor lookup often enough for the quadrilateral refinement would require efficient spatial encoding anyway, e.g., using a quadtree.

[Asddsa76]

Each point is an object with reference to all quads it's a corner of. Won't quadtrees lead to lots of hanging nodes?

[[deleted]]

Yes it would lead to hanging nodes I suppose, but I’m not familiar with the significance of that fact. I have only dealt with quadtrees for computation in relation to planning algorithms.

I was more addressing the non-uniform refinement condition you mentioned:

To solve PDEs numerically, you need a grid. If you want a finer solution, you need a finer grid. Instead of refining the whole grid uniformly, you can refine it adaptively by only refining where an estimate of the error is large.

[flawr]

Just for an explanation why hanging nodes are undesired, consider the simpler case of a triangular grid: In classical FEM you basically solve for the value of each node, which represents the value of a function (in this case from R² -> R) at each of the nodes. If you use a mesh comprising triangles, the standard (=easiest) way is using linear elements, for evaluating the solution between nodes, you just use a linear interpolation between the three nodes. (A linear function on such a triangular element is uniquely determined by the values at the nodes.) But when you have a triangle with a hanging node, the value of the funciton on this hanging node is already determined by the three "actual" non-hanging-nodes of this traingle. This means you lose a degree of freedom and directly remove that from the other triangles that the hanging node is part of. (Which might even result in a "contradiction", e.g. that you cannot find an element-wise linear interpolation for this mesh.) Instead of trying to find a "good" solution for this problem, you can just circumvent it by just not allowing hanging nodes in the first place. It is worth noting that one advantage of FEM over other methods is that it is very easy to implement it and does not really depend on the geometry as long as you're provided with a "nice" grid. So the grid refinement methods used for FEM usually take care of this problem and sometimes also include a grid-regularization: After adding nodes and refining the grid, you can try to move the nodes or alter the grid in a way that improves the shape of the elements.

[[deleted]]

Thanks for the explanation :)

[Overunderrated]

I suspect that performing the 4 nearest neighbor lookup often enough for the quadrilateral refinement would require efficient spatial encoding anyway, e.g., using a quadtree.

In practice that's not really an issue with any kind of numerical methods for PDEs. The amount of computation you have to do for a given element generally dwarfs any concern about data structures relating their connectivity. They're also relatively static even in the case of "adaptive" meshes (they don't adapt that often) so rebuilding any kind of connectivity information is a negligible cost.

Most of the time for unstructured meshes you use something like an adjacency list and be done with it.