Advancing-Front Node Generators

· Created with the assistance of Claude Fable 5

nodes: 0 front size: 0

60 both algorithms 1.0 both algorithms 5 Fornberg–Flyer 10 van der Sande–Fornberg 8 animation

Two bulk generators, ported line for line from the reference Fortran/C. Both sweep the box bottom to top, placing each node at the lowest admissible point and pushing an exclusion disc of radius r(x, y) into the front; the red line is the front. Click (or tap) the canvas to restart.

Fornberg–Flyer keep the front as an x-sorted list of potential dot positions (PDPs). The next node is the lowest PDP; it is accepted, and the PDPs inside its exclusion disc are replaced by a configurable number of cell-centred points on the exclusion arc (five by default), spliced between the nearest outside PDPs found by walking outward from the dot.

Van der Sande–Fornberg keep a height field on a background grid of grid-factor × ninit columns. The next node goes to the lowest column; each accepted dot raises the heights under its exclusion disc to the disc’s far hemisphere. When the radius varies, the node is first pushed off the discs of earlier nearby nodes — the direction-dependence correction of their section 2.3 (inactive for constant radius).

①②③placed nodesnearest outside PDPcurrent lowest pointnew front
Fornberg–Flyer, a snapshot from an actual run of the port. Dark dots are placed nodes; the front advances downward. ① the lowest PDP of the old front (grey dashed) is accepted as a node. ② the PDPs inside its exclusion disc are removed. ③ the angle between the directions to the nearest outside PDPs (dotted rays) is divided into five equal cells (ticks), and one point is placed at each cell’s centre — so the end gaps to the rays are half the dot-to-dot gap, keeping new PDPs clear of the surviving outside ones. The spliced result is the new front (red).
①②old heightsnew heights followthe disc boundarybackground columnslowest column
Van der Sande–Fornberg. The height field (one value per background column) is the front. ① the node is placed at the lowest column of the old heights (grey dashed). ② the heights under its exclusion disc are raised to the disc’s far hemisphere, so the new heights (red) sample the disc boundary on the columns; elsewhere the old heights already lie outside the disc and are unchanged. The data is a snapshot from an actual run of the height-field port. Later nodes sit on the height curve, hence at least r away — for constant radius no node ever lands inside another’s disc.

References:

Fornberg, B., & Flyer, N. (2015). Fast generation of 2-D node distributions for mesh-free PDE discretizations. Computers & Mathematics with Applications, 69(7), 531–544. doi:10.1016/j.camwa.2015.01.009

van der Sande, K., & Fornberg, B. (2021). Fast variable density 3-D node generation. SIAM Journal on Scientific Computing, 43(1), A242–A257. doi:10.1137/20M1337016

Inspired by the visualisations of Jason Davies.

#Meshless   #Node-Generation   #Rbf-Fd   #Visualisation  

← Back to the gallery