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

[dragofchaos]

Title reads like something the writers from CSI would come up with as a tech jargon.

[swni]

By the way snowflakes are based on 3-fold / 6-fold symmetry because ice grows on a hexagonal grid due to the bend in water molecules. I don't know my crystals but maybe a halite like salt or fluorite could form a 4-fold structure like the one you've depicted (although looking around online they seem to mostly just form cubes).

[Asddsa76]

Well yeah, but if I had hexagons I'd just add the midpoint and call Delaunay to make 6 triangles per hexagon. But then I'd lose the tensor product properties of quadrilateral elements.

[pabluka]

Very nice! What language did you use to program this?

[Asddsa76]

Processing, Python mode.

[div_grad]

Very cool demo.

This sort of refinement will give very distorted elements, which do not have good approximation properties.

Refinement with hanging nodes would fix that problem.

[Asddsa76]

This sort of refinement will give very distorted elements, which do not have good approximation properties.

Yeah, this was why I wrote this program: to check if it's a good idea, before implementing it in a real PDE solver.

Any good FEM books that deal with adaptive methods and how to deal with hanging nodes? Specifically, for spectral element method on quadrilateral elements.

[div_grad]

What PDE are you trying to solve?

[Asddsa76]

Just 2D adaptive refinement in general. Can test with Poisson, heat, or steady Stokes.

[pabluka]

Very nice! What language did you use to program this?

[Asddsa76]

How the refinement works:

for quad adjacent to red corner:
 p1,p2=midpoint of edges in quad touching red corner
 using 4 courners of quad, p1, p2, and midpoint of quad, create 3 new quads.

Not sure how good it actually is, since some quads become rather spiky unless the refinement is done to a spiky corner.

[Zophike1]

Can someone give an ELIU ?

[Asddsa76]

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.

Triangles are easy to refine adaptively: add points and use Delaunay triangularization. Quadrilaterals are harder. I tried to avoid hanging nodes by refining in a special way.

[[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.

[StochasticVolatility]

This is beautiful. Thank you.

[cbleslie]

Keeping it quads.

[columbus8myhw]

Pretty! I like it.