Pruned and optimized border of rombohedrons iso-surfacing algorithm, or POBR for short.
The algorithm we present conducts three operations in order:
- Preliminary mesh generation based on the border of rhombohedrons in a special configuration.
- Pruning of vertices with exactly three adjacent triangles.
- Optimization of the remaining vertex positions along the direction of each vertex-adjacent triangle's common normal vector.
With this, we get a high quality initial mesh, and we optimize the accuracy of the approximation for how long we want. We can balance speed and accuracy not only by picking the element size, but by doing an exact amount of optimizational iterations. Each new iteration is just one function recomputation per vertex.
Bordering
The preliminary mesh generation goes as follows. Let’s say our function that represents an implicit curve C is called F.
F | x, y, z → v; C: F(x, y, z) = 0
The region of the implicit surface we want to approximate with a triangle mesh is being placed in a bounding box. Let Bmin = (Bminx, Bminy, Bminz) be the bounding box point where all the coordinates are lowest, and Bmax = (Bmaxx, Bmaxy, Bmaxz) be the point of the bounding box where all the coordinates are highest.
In this box, a regular orthogonal 3D grid of points is then defined. However, a cube is a partial case of a rhombohedron, so for now let’s define a regular grid. So given the bounding box (Bmin, Bmax), and the cube size a, the set of grid points will be defined as follows:
pijk = Bmin + (ai, aj, ak), where
i = 0..(Bmaxx-Bminx)/a
j = 0..(Bmaxy-Bminy)/a
k = 0..(Bmaxz-Bminz)/a
The pijk points are potential vertices of the preliminary mesh. Each set of points with indices (i, j, k), (i+1, j, k), (i+1, j+1, k), (i, j+1, k), (i, j, k+1), (i+1, j, k+1), (i+1, j+1, k+1), (i, j+1, k+1) represent a set of cube vertices. If a cube C1 has a negative value of F in its center, and a neighbouring cube C2 has a positive value of F in its center, then the implicit surface intersects the segment between these centers an even number of times. We can then presume that the common face of C1 and C2 approximates the surface, giving us a quad or a pair of triangles to add to the preliminary triangulation.
We conducted a computational experiment where the axial skewnesses of a rhombohedron have been optimizational parameters and the deviation in the triangluated edges length — a target function, and found a fitting rhombohedron. We also found an affine transformation that transforms the whole space in a way that every cube becomes an optimized rhombohedron:
T = [1.1830127, 0.3169873, 0.5, 0.]
[0.3169873, 1.1830127, 0.5, 0.]
[0., 0., 1., 0.]
[0., 0., 1., 0.]
The inverse matrix is this:
Ti = [0.9106836, -0.24401694, -0.33333333, 0.]
[-0.24401694, 0.9106836, -0.33333333, 0.]
[0., 0., 1., 0.]
[0., 0., 1., 0.]
Now, to build a triangle mesh as a border of rhombohedrons, we need to apply the inverse transformation to the function F, and the direct transformation to the bounding box corner points. Note that after the transformation, the minimal corner point Bmin, for instance, might not remain minimal in the sense that all its coordinates will remain lowest. You should pick up the coordinates for the minimal (and maximal) points of the transformed bounding box among the coordinates of all the box corner points after the transformation.
After the transformation, we build the triangle mesh based on the same cubes as before but in the now-skewed space. Applying the inverse transformation to the vertices of these cubes grants us a triangle mesh based on the borders of rhombohedrons.
Pruning
This mesh has vertices with exactly three adjacent triangles, and this configuration occurs exclusively at the two specific corners of the optimized rhombohedron where all the adjacent triangles have sharp corners. This particular configuration doesn’t contribute positively to the quality of the mesh and could be safely pruned. In Figure 4, the triangle mesh after such pruning is presented.
Optimizing
The next step would be to optimize the position of every vertex vi along the mean normal vector of adjacent triangles ni by reducing the error of the surface approximation. To do so, we propose a simple bisection.
The optimization parameter is then the normal scale factor k, and the interval of optimisation [-sqrt(3)*a, sqrt(3)*a], given that the mean normal gets renormalized after the averaging. The target function is the squared value of the implicit surface function in the sum of the vertex position and the scaled normal:
T(k) = F(vi + kni)^2
The new vertex position, after the minimising k for T is found, would be
vi + kni
The presumption that there is a minimal T value on the given interval comes from the first stage of the mesh generation. We only put vertices in the proximity of a pair of positive and negative values of the implicit surface function. The maximum distance from the initial vertex position to the surface depends on the configuration but couldn’t be larger than sqrt(3)*a even in the corner case.
Note that the skewness of the rhombohedrons doesn’t break the logic here, as at the mesh generation stage we only transform the implicit surface function and the bounding box corners, and the algorithm then works with perfectly cubical elements which become rhombohedrons only after the inverse transformation at the very end.
Every iteration except the first requires only one recomputation of the implicit surface function per vertex of the pruned triangle mesh. The more iterations conducted, the more accurately the vertices align with the implicit surface regardless of its configuration.
2 itetations:
4 itetations:
8 itetations:
It is, of course, possible that the configuration in the proximity of a vertex is too complex, e. g., the target function on the selected interval is not unimodal. In this case, bisection would still provide some result, some proximity to the surface, but the topology of the approximating mesh may differ from the iso-surface we want to extract. This would be a clear indicator of the element size a being too large.
Conclusions
Approximating an isosurface with a triangle mesh based on the pruned and optimized border of rhombohedrons is a valid and effective method for isosurface extraction when we have no other assumptions about the topology and the shape of the surface other than continuity. It generally produces a high-quality mesh, and the fidelity and the accuracy of the approximation are regulated by the element size and the iteration count for the optimization step of the algorithm. Having the second parameter adjustable is essential for isosurface construction methods research, as it allows us to get preliminary results quickly and accurate results eventually.
Paper
...pending...
Connected research
This algorithm has been coined while working on triply periodic nonminimal surfaces.
https://codeberg.org/okaleniuk/faitps
Ironically, now I'm too busy writing the paper for the algorithm to wire the POBR into the FAI-TPS code that has already been published.