Algebraic surface algorithm

Algebraic Surfaces

The centrepiece of the SingSurf program is the ASurf module for calculating algebraic surface in three dimensions. Also known as algebraic varieties or implicit surfaces.

Outline of the algorithm

  • Conversion of input polynomial to Bernstein form.
  • Subdivision input region into smaller boxes, exploiting the convexity properties of the Bernstein polynomials to eliminate boxes which don't contain any part of the surface.
  • Examination of the faces of the box:
    • Find solutions on the edges of the faces
    • Subdivide faces using convexity properties to
    • Find "nodes" where \(f(x,y,z)=0\) and at least one of the derivatives \(\frac{df}{dx}, \frac{df}{dy}\) or \( \frac{df}{dz} \) vanishes.
    • Use convergence routines to converge to the nodes.
    • Link together solutions and nodes to create a polygonal approximation to the intersection of the surface with the face.
  • Examination of individual boxes:
    • Use criteria on mean curvature and length of the gradient vector \(\left(\frac{df}{dx},\frac{df}{dy},\frac{df}{dz}\right)\) to further refine depth.
    • Subdivide boxes where two of more of the partial derivatives vanish.
    • Identify "singularities" points where \(f=0\) and at least two derivatives vanish. This include true singularities where all derivatives vanish and non-singular points where only two derivative vanish.
    • Use a variety of different convergence routines to find these points.
    • Link together nodes on faces and singularities inside to boxes to create a polygonal skeleton approximating the curves \(f(x,y,z)=0, \frac{df}{dx}=0\) etc.
  • Use links on faces and the skeleton linking nodes to create facets: polygons approximating the surface.
  • Triangulate the facets, using information from the normals and curvature to produce nicer triangulations.
  • To ensure that facets of adjacent boxes calculated at different resolutions match along common faces the calculation of facets is delayed until both boxes have been linked.
  • Finally, plot the triangulation. For some renderers it is necessary to blow up the true singularities, replacing a single singular point by multiple points with the same position but different normal vectors.
  • Statistics about the resulting polygonal mesh including the Euler characteristic are used to verify correctness of the generated triangulation.

Manual

A rather unfinished PDF manual for the whole package.

Msqli defined