Skip to content

Latest commit

 

History

History
182 lines (143 loc) · 8.36 KB

README.md

File metadata and controls

182 lines (143 loc) · 8.36 KB
Raw

Data visualization

Official git repository: https://gitlab.com/Marc--Olivier/DataVisualization

What is this project about?

The data visualization project is a small project whose current goal is to display 4D data using isosurfaces. The project contains an implementation of the marching cubes algorithm to compute these isosurfaces.

The project is composed of the following modules:

  • third-parties defines rules to download and compile some dependencies ( catch2, googletest, google/benchmark), and some small wrappers on top of them.
  • utils contains cache friendly data structures for tiny containers.
  • marching-cubes contains the classes that implement the marching cubes algorithm.
  • gui defines a simple Graphical User Interface that can display isosurfaces for either the function f(x,y,z)=x²+y²+z², or a DICOM file of your choice. To perform these tasks, the module depends on the libraries Qt5 and DCMTK that you must install separately.

Note that the gui module mainly contains code I wrote in 2010 using Qt4. Although I updated some parts of the code, some other parts require more work, especially the class MCubesRenderer that displays the triangles using OpenGL, or DicomReader that reads DICOM files. Actually, my plan is rather to get rid of the gui module at some point (after having extracted DicomReader into a different module), and compile the code to WebAssembly: would it not be convenient if you could visualise your DICOM data in a web browser?

Building the project

To build the whole project, you need to install the following components and libraries:

  • CMake, version 3.8 or higher
  • Ninja, if you want a build system much faster than Make
  • DCMTK
  • Qt5, preferrably a recent version (I use Qt 5.11.1)

Then, execute the following commands:

git clone https://gitlab.com/Marc--Olivier/DataVisualization.git
cd DataVisualization
mkdir -p build/release
cd build/release
QT5_PATH=<path-to-your-installation-of-Qt5>
DCMTK_PATH=<path-to-your-installation-of-DCMTK>
# The following command will take some time:
# it downloads and compiles catch2, google-test and google/benchmark
cmake -G Ninja ../.. -DCMAKE_BUILD_TYPE=Release -DCMAKE_PREFIX_PATH="$QT5_PATH;$DCMTK_PATH"
ninja
ninja test
# To run the application:
./gui/datavisualization
# Or ./gui/datavisualization.app/Contents/MacOS/datavisualization
# if you are using macos.

Compiler support

So far, I only tested on macos with clang 6.0.0 and Apple LLVM version 10.0.0 (clang-1000.11.45.2).

One of my next step is to compile the code with (at least) gcc.

The marching cubes algorithm

Description of the algorithm

The goal of the marching cubes algorithm is to approximate the isosurface for a value viso of a function f(x,y,z). This approximated isosurface is composed of triangles.

The algorithm first breaks down the domain (x, y, z) of the function f(x,y,z) into cubes.


Figure 1: Decomposing the domain into cubes

Then, for each, the algorithm calculates a set of triangles that approximate the isosurface within the cube. Each vertex of one of these triangles is located on an edge of the cube. The number of triangles require to approximate the isosurface, and the edges where the vertices of these triangles are located, are determined by the sign of f(Vi) - viso at each cube vertex Vi. The set of signs sign(Vi) = (f(Vi) - viso ≥ 0) for a cube is called the cube configuration.


Figure 2: Triangle approximation of the isosurface within a cube

Figure 2 shows an example of one triangle approximating the isosurface within a cube that has the configuration + - + + + + + +. Since V1 is the only 'negative' vertex of the cube, the vertices of this triangle are on the edges connected to V1. The exact positions of the intersection points depend on the value of f at the vertices V0, V1, V3 and V5: a linear interpolation is performed to calculate these exact positions.

The class marchingcubes::MarchingCubes is the entry point of the code that calculates the approximating triangles.

Cube configurations

If cubeconfig is a cube configuration, the cube configuration flippedcubeconfiguration obtained by flipping each sign of cubeconfig produces the same set of triangles as cubeconfig. These are the only cube configurations that produce the same sets of triangles. Therefore, there are 28 / 2 = 128 different set of triangles. However, we don't need to implement the set of triangles for each of these 128 configurations, but we can calculate them from 15 base configurations described on Wikipedia by applying well chosen symmetries to these base configurations:


Figure 3: The originally published 15 cube configurations from Wikipedia

Actually, generating the set of triangles for each cube configuration is not very expensive, but this should be rather done before the algorithm starts to loop over all the cubes. marchingcubes::MarchingCubes uses the class marchingcubes::ConfigsGenerator to create a marchingcubes::AllConfigs object that contains the set of triangles for each cube configuration.

Final thoughts

Next steps

  • Add CI jobs that compile the code and run the tests using different compilers.
  • Add support for gcc.
  • Compile the code to WebAssembly (except the gui module). This especially requires to compile the library DCMTK to WebAssembly, library that depends on other libraries...

Issues

Rendering svg images that are on GitLab

Issue https://gitlab.com/gitlab-org/gitlab-ce/issues/17276

I converted the svg images using Inkscape (see https://mijingo.com/blog/exporting-svg-from-the-command-line-with-inkscape.):

/Applications/Inkscape.app/Contents/Resources/bin/inkscape \
     -z `pwd`/doc/images/grid.svg -e `pwd`/doc/images/grid.png
/Applications/Inkscape.app/Contents/Resources/bin/inkscape \
     -z `pwd`/doc/images/cube_approximating_triangles.svg \
     -e `pwd`/doc/images/cube_approximating_triangles.png

DICOM Datasets

Related softwares