Projects/Graphing in 3D
Given a real-valued continuous multivariate function f(x,y,z), how can the surface f(x,y,z)=0 be determined and graphed in 3D?
First of all, why f(x,y,z)=0? Although the f(x,y,z)=0 surface might at first seem arbitrary, it is actually fully general since surfaces such as z=g(x,y) or x^2+y^2+z^2=R^2 can be expressed as f(x,y,z)=z-g(x,y)=0 or f(x,y,z)=x^2+y^2+z^2-R^2=0
As standard in computer graphics, 3D objects are rendered using their triangle mesh. Thus the problem is producing a net of triangles given a function f(x,y,z).
The standard algorithm for this task is known as marching cubes or marching tetrahedra. At a high-level, these algorithms work by tesselating the 3D space with cubes or tetrahedra, respectively, and then evaluating the function f(x,y,z) at each vertex of the polyhedron. If the function changes sign (positive to negative or vice versa) between vertices, then the surface is known to pass through the polyhedron.
Once the surface is known to pass through a polyhedron, the next step is to find the triangle(s) that best approximates the surface within the polyhedron. Although some public algorithms use large lookup tables, the problem can be broken down by symmetry. At this point, the marching cubes algorithms has ambiguities depending on the geometry of the sign flips between the vertices, so I'll focus on the marching tetrahedron case.
It turns out that up to symmetry, there are only 2 ways for the surface to pass through a tetrahedron:
Either the surface can cut through 3 of the edges, all adjacent to 1 vertex (in red), like so:
Or the surface can cut through half of the tetrahedron, leaving 2 vertices (in red) on one side, and 2 on the other, like so,
From there, linear interpolation of the roots of f(x,y,z)=0 along the edges can be used to find the best approximating triangles to use for the mesh.
Resources:
First of all, why f(x,y,z)=0? Although the f(x,y,z)=0 surface might at first seem arbitrary, it is actually fully general since surfaces such as z=g(x,y) or x^2+y^2+z^2=R^2 can be expressed as f(x,y,z)=z-g(x,y)=0 or f(x,y,z)=x^2+y^2+z^2-R^2=0
As standard in computer graphics, 3D objects are rendered using their triangle mesh. Thus the problem is producing a net of triangles given a function f(x,y,z).
The standard algorithm for this task is known as marching cubes or marching tetrahedra. At a high-level, these algorithms work by tesselating the 3D space with cubes or tetrahedra, respectively, and then evaluating the function f(x,y,z) at each vertex of the polyhedron. If the function changes sign (positive to negative or vice versa) between vertices, then the surface is known to pass through the polyhedron.
Once the surface is known to pass through a polyhedron, the next step is to find the triangle(s) that best approximates the surface within the polyhedron. Although some public algorithms use large lookup tables, the problem can be broken down by symmetry. At this point, the marching cubes algorithms has ambiguities depending on the geometry of the sign flips between the vertices, so I'll focus on the marching tetrahedron case.
It turns out that up to symmetry, there are only 2 ways for the surface to pass through a tetrahedron:
Either the surface can cut through 3 of the edges, all adjacent to 1 vertex (in red), like so:
Or the surface can cut through half of the tetrahedron, leaving 2 vertices (in red) on one side, and 2 on the other, like so,
From there, linear interpolation of the roots of f(x,y,z)=0 along the edges can be used to find the best approximating triangles to use for the mesh.
Resources:
- Code for finding the mesh: g.js