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