Implicit Objects and the Marching Cubes Algorithm (implementation in C++)

Hello,

today I am going to talk about algebraic representation of Objects and the Marching Cubes Algorithm. This tutorial's code is available at:
https://github.com/Art-n-MathS/ImplicitObjects

The code is part of the open source software DASOS, which is able to reconstruct forest from full-waveform LiDAR data. For more information about DASOS please look at: http://miltomiltiadou.blogspot.co.uk/2015/03/las13vis.html

Please note that some of the explanation were copied from my paper:
Miltiadou, M, Warren M.A, Grant M., Brown M., 2015, Alignment of Hyperspectral Imagery and full-waveform LiDAR data for Visualisation and Classification purposes, 36th International Symposium of Remote Sensing of the Enviroment, ISPRS Archives
Available at: http://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XL-7-W3/1257/2015/isprsarchives-XL-7-W3-1257-2015.pdf

Implicit Representation of objects

Numberical implicitization was introduced by Blinn in 1982. Numerical implicitization allows definition of complex objects, which can easily be modified, without involving large number of triangles.

A function f(X) defines an object, when every n-dimensional point X the following conditions apply:

f(X) = a, when X lies on the surface of the object
f(X) > a, when X lies inside the object
f(X) < a, when X lies outside the object

where,
X = an n-dimensional point. It usually it is in Euclidean space defining the x, y, z poisitions of the point
f(X) = the function that defines the object of our interest. In the coding example is the function of the sphere
a = the isosurface of the object, which defines the boundaries of the object. f(X) is equal to a iff X lies on the surface of the object.

Marching Cubes Algorithm:

Even though numerical implicitization is beneficial for reducing storage memory and for various resolution renderings of the same object, visualising numerical/algebraic objects is not straight forward, since they contain no discrete values. This problem can be addressed either by ray-tracing or by polygonisation. In 1983, Hanraham suggested a ray-tracing approach, which used the equation derived from the ray and the surface intersection to depict the algebraic object into an image. The Marching Cubes algorithm was later introduced for polygonising implicit objects.

The Marching cubes algorithm constructs surfaces from implicit object using a search table. Assume that f(X) defiens an algebraic object. At first the space is divided into cubes, named voxels.Each voxel is defined by eight corner points, which lie either inside of outside the object. By enumerating all the possible cases and linearly interpolating the intersections along the edges, the surface of the implicit object is constructed (Lorensen and Cline, 1987).

In 2021 a research was published that investigates the performance of 6 different data structures for extracting an iso-surface (creating a 3D polygonal model) from voxelised data (Miltiadou et, al. 2021). It was shown that Integral Volumes was the fastest from the six, but it consumes the most memory. Each data structure has its owns prons and cons. Additionally, in that paper a new category of data strucutre "Integral Trees" were introduced. 


For more information about the Marching Cubes algorithm please look at the following blogpost:
http://paulbourke.net/geometry/polygonise/

Example Output:

The output .obj file, visualised in Meshlab

Code

This tutorial's code is available at: https://github.com/Art-n-MathS/ImplicitObjects

In this example, a sphere is defined using an function, polygonised using the Marching Cubes Algorithm and then exported into an .obj file.

Requirements:
- gmtl library
- c++11
- qmake

Compile:
$: qmake
$: make clean
$: make

Run:
$: ./ImplicitObjects

References

Miltiadou, M.; Campbell, N.D.F.; Cosker, D.; Grant, M.G. A Comparative Study about Data Structures Used for Efficient Management of Voxelised Full-Waveform Airborne LiDAR Data during 3D Polygonal Model Creation. Remote Sens. 2021, 13, 559. https://doi.org/10.3390/rs13040559

Blinn, J.F, 1982. A Generalization of Algebraic Surface Drawing. ACM Trans.Graph, pp. 235-256

Hanrahan, P., 1983. Ray tracing algebraic surfaces. ACM SIGGRAPH Computer Graphics, Vol 17, No. 3.

Lorense, W. E., & Cline, H.E., 1987. Marching Cubes: A high resolution 3D surface construction algorithm ACM Siggraph Computer Graphics, Vol 21, No 4 pp. 163-169


Miltiadou, M, Warren M.A, Grant M., Brown M., 2015, Alignment of Hyperspectral Imagery and full-waveform LiDAR data for Visualisation and Classification purposes, 36th International Symposium of Remote Sensing of the Enviroment, ISPRS Archives

DOI: 10.5194/isprsarchives-XL-7-W3-1257-2015