DOCSEARCHbyAlgolia
Submit Docs

Multiresolution Sparse Block Grids (MSBG)

repository·main·Indexed 41 days ago

https://github.com/tum-pbs/msbg

A high-performance, treeless, spatially adaptive data structure for large-scale 3D simulations on the CPU. MSBG supports sparsity and multiresolution adaptivity for PDE solving and surface reconstruction, capable of handling effective resolutions up to 32768^3. It includes a BlockPool for memory management, BlockProcessor for SIMD-accelerated parallel processing, and a RaymarchRenderer for visualizing sparse volumes.

Tokens
8.5K
Snippets
29
Records
37
Agent score
51%

What's inside MSBG

  1. Overview of Multiresolution Sparse Block Grids (MSBG)

    main

    MSBG is a treeless, spatially adaptive data structure designed for high-performance CPU computing. It supports both sparsity and multiresolution adaptivity, making it suitable for extremely large-scale 3D volumes.

    Key Capabilities:

    • CPU Optimized: Designed to leverage large amounts of RAM rather than requiring a GPU.
    • High Scalability: Capable of handling effective resolutions up to $32768^3$ (e.g., 100 billion active voxels) on a single high-memory CPU node.
    • Efficient PDE Solving: Includes a highly efficient solver for sparse volumes, capable of advancing solutions at approximately 10 billion unknowns per second per iteration.
    • Applications: Useful for sparse surface reconstruction from particles and sparse PDE smoothing (such as mean curvature flow).

  2. Use vectorclass version 1 for legacy compilers

    main

    If you are using older compilers that cannot handle vectorclass version 2, you should use version 1. This includes:

    • Intel C++ compiler version 19
    • Older versions of Microsoft Visual C++
    • Older versions of GNU (GCC)
    • Older versions of Clang
    [Download code for version 1](https://github.com/vectorclass/version1/archive/master.zip)

  3. Build MSBG from source

    main

    To build the MSBG library and the msbg_demo executable, use the provided Make-based build script. Ensure you have C++11 and Intel TBB installed.

    git clone https://github.com/your-org/MSBG.git
cd MSBG

mkdir build && cd build

# builds the library and 'msbg_demo' executable
../mk

  4. Prerequisites for MSBG

    main

    Before building, ensure your environment meets the following requirements:

    • C++11 compiler
    • Intel TBB (oneTBB)
    • Operating System: Linux or Windows (via MSYS2/MinGW64)

    Note: The VectorClass header-only library is included in the repository and does not need to be installed separately.

  5. Use IpolAccessCache to optimize interpolation

    main

    The IpolAccessCache class is designed to accelerate repeated interpolation lookups by caching the last accessed position and its associated data. This is particularly effective when performing lookups in a spatially coherent manner (e.g., sweeping through a volume).

    Usage

    1. Instantiate an IpolAccessCache object.
    2. Pass it to the interpolateFloatFast method.
    IpolAccessCache cache;
// In a loop over positions...
float val = grid.interpolateFloatFast(pos, 0, &cache);
    IpolAccessCache cache;
cache.reset(thread_id);

for (const auto& pos : positions) {
    float val = grid.interpolateFloatFast(pos, 0, &cache);
}

  7. Configure lighting and surface color in RaymarchRenderer

    main

    The renderer supports basic lighting and material properties to enhance the visualization of the volume density.

    • setSunLight(const Vec3& sunPos): Sets the position of the directional light source (sun).
    • setSurfaceColor(const Vec3& color): Sets the base RGB color of the volume surface.
    renderer.setSunLight({10, 10, -10});
renderer.setSurfaceColor({1.0, 0.5, 0.5}); // Light red surface

  8. Create and manage a BlockPool

    main

    The BlockPool class provides lightweight, low-contention memory management for fixed-size sparse blocks. It allows for pre-allocating a specific number of blocks and growing the pool up to a defined maximum size in MB.

    To use a BlockPool, use the static create method. Blocks are then acquired via allocBlock and returned via freeBlock_ (note the underscore in the free method).

    Configuration Options

    When creating a pool, you can pass options using the following bitmask flags:

    • OPT_PROTECTABLE: Enables protection mechanisms.
    • OPT_FIXED_EXTEND: Uses a fixed extension strategy.

    Monitoring

    You can query the pool's state using:

    • getNumBlocksAllocated(): Returns the number of currently allocated blocks.
    • getMemUsage(): Returns the total memory currently used by the pool.
    • getBlocksAvailable(): Returns the total number of blocks available in the pool.
    • isOutOfMem(): Returns true if the pool has reached its memory limit.
    // Example: Creating a pool for 1024 blocks of 1KB each, starting with 100 blocks,
// with a maximum growth limit of 512MB.
BlockPool* pool = BlockPool::create("MyPool", 1024, 1024, 100, 512);

// Allocate a block
void* myBlock = pool->allocBlock(0);

// ... use block ...

// Free the block
pool->freeBlock_(myBlock, 0);

// Cleanup
BlockPool::destroy(&pool);

  9. Coordinate conversion and indexing

    main

    The SparseGrid provides several utilities to convert between different coordinate systems: grid coordinates, block coordinates, and voxel-in-block coordinates.

    Key Conversion Methods

    • getBlockCoords(int i, int j, int k): Converts grid coordinates to block coordinates $(bi, bj, bk)$.
    • getVoxelInBlockCoords(int i, int j, int k): Converts grid coordinates to local voxel coordinates within a block $(vi, vj, vk)$.
    • getVoxelInBlockIndex(Vec4i ivp): Calculates the linear index of a voxel within its block.
    • getBlockIndex(int bi, int bj, int bk): Calculates the linear index of a block in the global block map.
    • getGridIndex(int i, int j, int k): For dense grids, returns the linear index in the dense array.

  10. Iterate over voxels in a block using SBG macros

    main

    The library provides convenience macros to loop over voxels within a specific block. This is useful for high-performance kernels where you need both the grid coordinates $(x, y, z)$ and the local voxel index vid within the block.

    • SBG_FOR_EACH_VOXEL_IN_BLOCK(sg, bid, x, y, z, vid): Loops through all voxels in block bid of grid sg.
    • SBG_FOR_EACH_VOXEL_IN_BLOCK_GEN(sg, bid, x, y, z, vid): A generalized version that supports strides (useful for SIMD or downsampling).
    // Loop over all voxels in block 'bid'
SBG_FOR_EACH_VOXEL_IN_BLOCK(grid, bid, x, y, z, vid) {
    // Use x, y, z for grid coordinates
    // Use vid for the local index within the block
    float val = grid->getValueInBlock(bid, vid);
}

  11. Access and set voxel values in SparseGrid

    main

    Values can be accessed or modified using grid coordinates $(i, j, k)$, block coordinates and voxel indices, or floating-point positions.

    Reading values:

    • getValue(i, j, k): Returns the value at grid coordinates.
    • getValue(Vec4f pos): Returns the value at a floating-point position (using floor and truncation).
    • getValueInBlock(bid, vid): Returns the value at a specific block and local voxel index.

    Writing values:

    • setValue(i, j, k, value): Sets the value at grid coordinates. This may trigger block allocation.
    • setValueInBlock(bid, vid, value): Sets the value at a specific block and local voxel index.
    // Set value at grid coordinate
grid->setValue(10, 20, 30, 1.5f);

// Get value at floating point position
float val = grid->getValue(Vec4f(10.5f, 20.2f, 30.9f));

  12. Retrieve a neighborhood of voxels

    main

    To perform stencil-based operations (like finite differences), you can retrieve a neighborhood of pointers to neighboring voxels.

    getSevenPointStencil

    Retrieves a 7-point stencil (center + 6 neighbors) for a target position. This is useful for second-order derivative approximations.

    • pos: The target Vec4i position.
    • neighbors: An output array of Data_T* pointers.

    getNeighborhood

    A more generic method to retrieve a $N imes N imes N$ neighborhood.

    • ix0, iy0, iz0: The target integer coordinates.
    • neighbors: An output array of Data_T** pointers.
    • Returns: The number of actual neighbors found (may be less than the requested volume if near boundaries or empty blocks).
    // Example: Getting a 7-point stencil
Data_T neighbors[7];
int rc = grid.getSevenPointStencil(targetPos, neighbors);
if (rc == MI_OK) {
    // neighbors[0] is center, neighbors[1..6] are neighbors
}