Introduction
The purpose of this project is to develop an interactive mathematical tool that is able to model the consecutive level sets of 4-dimensional functions.
Level set: The set of points in the domain of a 4-dimensional function that produce the same scalar result.
Level sets are analogous to a 3-dimensional function's contour lines, except that they exist in 3-space rather than 2-space. To render level sets in 3D, this project will implement a "Surface Reconstruction" technique that approximates level sets through isosurfaces.
Isosurface: An approximation of a level set.
More specifically, the project implements the Marching Cubes algorithm. This algorithm was chosen over others because it is computationally efficient and allows for real time rendering. In contrast, algorithms that involve a different technique called "Direct Volume Rendering" use ray tracing approach which tends to be computationally expensive and has trouble running in real time. Moreover, Marching Cubes is relatively simple to understand and implement in comparison to its algorithmic variants: Dual Contouring, Polyhedron Meshes, Surface Nets,...
Marching Cubes Concept
Marching Cubes is an algorithm that was developed in 1987 by Lorensen and Cline for the purpose of visualizing 3-dimensional representations of medical data extracted from CT and MRI scans. This data is referred to as volumetric data because it contains "density" information for points in a given 3-space domain. In other words, every point in a given 3D domain is associated with some specific scalar value. Lorensen and Cline were able to successfully model, to a certain degree of resolution, the organic tissues, bones and organs of various human subjects using this algorithm. The algorithm divides the 3-dimensional domain into a grid of voxels, and approximates the intersection of a level set through these voxels at various edges. These intersection points are then linked together to form one or more triangular primitives or meshes. Finally, to reconstruct the whole volumetric data set, the algorithm iterates through all possible isovalues, and renders their respective isosurface.
Isovalue: The scalar value that is associated with a level set.
Pseudo Code
|
|
Objectives
The main objectives this project aimed to accomplish are listed as follows and are checked accomplished or crossed unrealized:
- Implementing the Marching Cubes algorithm for level set rendering. ✔
- Making the level set rendering interactive by implementing buttons and a slider. ✔
- Implementing shading that colors the level sets based on their y-value heights. ✖ (although Gourad Shading was implemented)
- Implementing a graphical coordinate system to put the level sets in perspective to their unit size. ✖
The first two objectives for this project were accomplished sucessfully and yield satisfactory results. On the other hand, the last two objectives were not finalized due to inadequacies relating to the desired result for the appearence of the level sets. At first, shading the heights of the level sets was considered and attempted, but when implemented resulted in a poor depiction of level sets' shape. I decided it would be more meaningful to display the level sets using realistic lighting as it would highlight their edges and shadows. In this way, the 4-dimensional functions would mimic real world objects and be more easily distinguishable by the human eye. Futhermore, I decided to drop the last objective in order to focus on resolving issues relating to the rendering resolution of the level sets.
Problems with the resolution
Initially the level sets were rendered using a scaling factor of (Slider Isovalue / Current Isovalue) which was applied to the edge size and starting position of the Marching Cubes' grid of nxnxn voxels. While this allowed for a smooth transition between the level sets of the sphere function, it was also causing resolution issues for the other functions. The resolution of the Taurus function at a high Isovalue was extremely poor and ended up distorting the correct rendering of the level set. Likewise, the grid resolution for the Genus function was insatisfactory for any Isovalue. The following videos demonstrate the resolution issues for the prior functions:
| Taurus | Genus |
|---|---|
Solution
To solve the resolution problem, 3 more interactive sliders were implemented.
- Grid starting position scale: scales the starting position of the grid. The grid is initially located at (x,y,z) = (-1,-1,1)
- Grid edge size scale: scales the edge size of the grid. The initial edge size is (width,height,depth) = (2,2,2)
- Grid edge resolution scale: scales the number of partitions at each edge. The initial number of partitions is (width,height,depth) = (1,1,1)
| Taurus | Genus |
|---|---|
Demo
Here are the demos for the remaining functions:
| Sphere | Cassini Oval |
|---|---|
| Surface of Revolution | Tauri Intersection |
Considerations
Obstacles encountered during development
Three main obstacles inhibited the development of this project
- Shading issue
- Shading the fragments of the functions with respect to their y-values(heights) resulted in a poor depiction of the function's shape. Gourad shading was implement to solve this issue by simulating a real-world lighting environment. A light was attached to the camera for better clarity.
- Depth testing issue
- At some point in the development of this project, the rendering of the functions stopped working. I had enabled depth testing, but forgot to clear the depth buffer bit before updating each frame. It took me a while to figure out what the problem was because it was not something I had previously encountered. This issue severely inhibited the development process of this project.
- Resolution issue
- As mentioned in "Objectives", the resolution of certain functions' level sets was too poor with the old scaling method I was using. To solve this problem, 3 new sliders were added for more accurate control of the Marching Cubes algorithm.
Improvements
One improvement that would greatly benefit this project would be to interpolate the normals of the vertices in the vertex shader rather than doing that on the CPU. Additionally, implementing a graphical coordinate system or some kind of graphical reference that would situate the grid of voxels would make it easier to configure the algorithm.
Next steps
The next steps in the development of this project would involve implementing the previously mentioned improvements and looking into making the transitions between level sets smoother with respect to the resolution of the algorithm.
