Meshing
By Omar Essilfie-Quaye
Docs
Meshing - Split it all up
Meshing is the act of splitting a geometric space into neat subdivisions. This may be triangles, squares or hexagons in simple 2d scenarios, but can extend to more complicated shapes in higher dimensions. Mesh generation is a useful tool as it allows for computations to be split into small chunks that can be run on a small section of a larger problem. This can be seen in: computer graphics rendering, stress strain modelling, computational fluid dynamics, electromagnetic wave solvers or gravity simulations.
Method
I have devised my own mechanism for generating a mesh from random points. This is not necessarily an optimal method of doing it but I just wanted to learn about the process and I am not too worried about making something optimal.
- 1) Generate a series of random points within the canvas.
- 2) Use a convex hull algorithm to enclose the points in one area.
- 3) Generate an initial mesh with just the points identified as being on the convex hull.
- 4) Initial refinement of the convex hull mesh to reduce refinement complexity later.
- 5) Add randomly generated points one at a time with refinement until all points are added.
Initial Mesh Generation
The creation of the initial mesh can be done in a few ways each with their own pros and cons. Images of 3 methods are shown in the images below. I had initially started with the corner spokes method as it was very quick to implement. I realised that this created an initial mesh which requires a lot of refinement due to the long thing triangles that are created.
- 1) Triangle Strip - Create a strip of triangles using alternating points back and forth around the convex hull.
- 2) Central Spokes - Create a wheel and spoke pattern around a random point located near the centre of the convex hull.
- 3) Corner Spokes - Create a spoke pattern around one of the points that is on the convex hull.
Triangle Strip
Wheel Spokes
Corner Spokes
Convex Hull
Flood-it
