Triangulation of Implicit Surfaces

Overview


I developed an application for the visualization of implicit surfaces. Implicit surfaces are defined by an equation of the form f(x,y,z)=0. What is visualized is an approximation to the surface by a triangle mesh. The mesh is generated using the marching cubes algorithm, and is rendered using OpenGL. The user interface includes text input of the mathematical equation that defines the surface, control of the camera via an arcball tool, a zoom tool and input of the domain on which the mesh is generated.

This work was developed under the supervision of Luiz Velho, Leandro Cruz and with the technical assistance of Djalma Lucio. I presented it as a final project for the Design and Implementation of 3D Graphics Systems course at IMPA, June of 2015.

Video



Gallery


interface ball decocube chair eight klein klein1 new_logo

Modeling

Implicit Surfaces

An implicit surface is defined as the set of points (x,y,z) such that f(x,y,z)=0, where f is a smooth function. To visualize these objects we need to approximate them by a triangle mesh. This is accomplished using the marching cubes algorithm.

We note that a totally different approach to the visualization of implicit surfaces is ray tracing.

The Marching Cubes Algorithm

This algorithm was originally developed for the visualization of medical data. The original paper by Lorensen [1] has a good explanation of the algorithm. Basically, it consists of the following
- Generate a uniform grid of cubes
- March through the grid
- For each cube, evaluate the sign of f at the vertices
- For each configuration of signs, there is a corresponding set of triangles that form the intersection of the surface with the cube
- Refer to a predefined table to obtain the triangles generated by the intersection of the surface with the cube
The figure below shows the different cases for a 2D version of the algorithm.

new_logo

In the 3D case, 256 cases are possible, but as it is noted in [1], exploiting the symetry they can be reduced to 15 cases. An 8 bit index is used to designate each of the possible 256 cases. The table that indicates the corresponding triangles forming the intersection is indexed with this 8 bit index. The output of the algorithm is a mesh of triangles that approximates the surface.

The advatages of this algorithm are that it is fast, it is easy to implement, and the resulting mesh is easily rendered in the GPU.

In my implementation, I used the tables made by Cory Gene Bloyd found in this website.

Visualization


The triangle mesh resulting from the marching cubes algorithm is easily rendered using OpenGL. I used the API provided by the software Luiz Velho developed for the course. A scene file is created that contains the triangle mesh as the only object. Two fixed and opposing directional lights are put in the scene to provide illumination.

Interface


The user interface of the application has the following features
- Text input of the mathematical expression defining the surface
- Resolution input: this controls the number of cubes in the marching cubes algorithm
- Arcball tool for control of the camera
- Input for manual positioning of the camera
- Zoom tool: implemented by changing the field of view of the camera
The parsing of the mathematical expression was made using the ExprTk library.

Documentation

Building

The project was developed using Qt. So, to build the project, the easiest would be to use Qt Creator. In the downloadable package I include all the necessary files for the program to run.

Basic User Guide

The interface has a single window. There are two predefined surfaces that can be drawn to test the application: a sphere and a torus.


The program has several options that are controlable by the user, and there are default values for these. These default values are used by the program when no value or an invalid value is given by the user.
- Resolution: controls the number of cubes used by the algorithms. Default value is 15. Values higher than 80 are not recommended.
- Domain: gives the lower and upper z coordinates of the bounding box where the algorithm is applied. Default values are -1 and 1.
- Camera Position: the default position is (0, 0.5, -1.5).
- Field of view: is an angle and the default is 60. Values less than 4 are invalid.
- Mathematical expression: if no expression is given, or the expression is invalid, a sphere is rendered by default.
The mathematical expression must use the variables x,y and z. Valid symbols are +,-,*,/ and ^. There is also support for trigonometric and exponential functions. More details are found in the ExprTk site.

When any of the options is changed, the image must be rendered again using the Draw button for the changes to take place.

An arcball tool is implemented for intuitive control of the camera. This tool is used by simply clicking on the rendered image, holding and moving the mouse.

There are two labels on the lower right that show the number of vertices and faces of the current triangle mesh.

Issues With Current Version: 0.1

The application has the basic functionalities. However, it doesn't have robust error handling. For example, if an invalid mathematical expression is used, there is no error message to the user. Also, it is easy for the application to crash if the number of triangles in the mesh is too big. The visualization pipeline is not very optimized, so the camera rotations may be slow for large meshes.

Future Developments

- Robust error handling
- Optimize rendering pipeline
- Use a better shader to obtain smoother surfaces: for example Gouraud or Phong shading
- Alert the user if the triangle mesh is too big
- Export options

Download


- Source Code

Other Resources


- Presentation Slides

References


[1] Lorensen, William. Cline, Harvey. Marching Cubes: A High Resolution 3D Surface Construction Algorithm. Computer Graphics, Volume 21, Number 4, July 1987.