A static C++ library for the generation of discrete functions on a box-shaped domain

Discregrid

  

Figure 1: Left: Slice of a three-dimensional discrete signed distance field of the Stanford dragon. Right: Density map for SPH boundary handling of Stanford dragon.

Discregrid is a static C++ library for the parallel discretization of (preferably smooth) functions on regular grids. The library generates a (cubic) polynomial discretization given a box-shaped domain, a grid resolution, and a function that maps a three-dimensional position in space to a real scalar value. Isoparametric cubic polynomials of Serendipity type for the cell-wise discretization are employed. The coefficient vector for the discrete polynomial basis is computed using regular sampling of the input function at the higher-order grid's nodes. The algorithm to generate the discretization is moreover fully parallelized using OpenMP and especially well-suited for the discretization of signed distance functions. The library moreover provides the functionality to serialize and deserialize the a generated discrete grid. Discregrid ships with TriangleMeshDistance to directly provide the capability to compute and discretize signed distance fields to triangle meshes.

Besides the library, the project includes three executable programs that serve the following purposes:

  • GenerateSDF: Computes a discrete (cubic) signed distance field from a triangle mesh in OBJ format.
  • DiscreteFieldToBitmap: Generates an image in bitmap format of a two-dimensional slice of a previously computed discretization.
  • GenerateDensityMap: Generates a density map according to the approach presented in [KB17] from a previously generated discrete signed distance field using the widely adopted cubic spline kernel. The program can be easily extended to work with other kernel function by simply replacing the implementation in sph_kernel.hpp.

Author: Dan Koschier, License: MIT

Libraries using Discregrid

  • PBD - A C++ library for physically-based simulation of rigid bodies, deformables, cloth and fluids using Position-Based Dynamics. Discregrid is used to compute discrete signed distance fields of rigid objects for collision handling purposes.
  • SPlisHSPlasH - A C++ library for the physically-based simulation of fluids using Smoothed Particle Hydrodynamics. Discregrid is used to compute density maps according to my paper [KB17] for boundary handling.

Build Instructions

This project is based on CMake. Simply generate project, Makefiles, etc. using CMake and compile the project with the compiler of your choice. The code was tested with the following configurations:

  • Windows 10 64-bit, CMake 3.8, Visual Studio 2017
  • Debian 9 64-bit, CMake 3.8, GCC 6.3.

Usage

In order to use the library, the main header has to be included and the static library has to be compiled and linked against the client program. In this regard a find script for CMake is provided, i.e. FindDiscregrid.cmake. The main header can be included as follows:

#include <Discregrid/All>

A base class for the data structure that generates and holds a discretization of a function f: R^3 -> R can be constructed as follows:

// Firstly, create a domain on which a discretization will be generated.
Eigen::AlignedBox3d domain;
// Then specify domain extents using e.g. domain.extend(...).
// Secondly, specify a grid resolution.
std::array<unsigned int, 3> resolution = {{10, 10, 10}}
// Finally, instantiate the grid.
Discregrid::CubicLagrangeDiscreteGrid discrete_grid(domain, resolution);

Then, an arbitrary number of functions can be discretized on the initiated grid:

Discregrid::DiscreteGrid::ContinuousFunction func1 = ...;
Discregrid::DiscreteGrid::ContinuousFunction func2 = ...;

auto df_index1 = discrete_grid.addFunction(func1);
auto df_index2 = discrete_grid.addFunction(func2);

Optionally, only coefficients at nodes fulfilling a certain predicate can be generated by specifying the predicate:

Discregrid::DiscreteGrid::ContinuousFunction func3 = ...;
auto df_index3 = discrete_grid.addFunction(func3, false, [&](Vector3d const& x)
{
	...
	// Return true if a certain criterion for the node location x is fulfilled, e.g.
	return x.y() > 0.0;
});

A value of a discrete field can be evaluated by interpolation. Additionally, the gradient at the given query point can be computed if desired.

auto val1 = sdf->interpolate(df_index1, {0.1, 0.2, 0.3});
Eigen::Vector3d grad2;
auto val2 = sdf->interpolate(df_index2, {0.3, 0.2, 0.1}, &grad2);

If a discretization of the input function is only required in certain regions of the given domain, the discretization can be reduced resulting in a sparsely populated grid to save memory:

discrete_grid.reduce_field(df_index1, [](Eigen::Vector3d const& x, double v)
{
	// E.g.
	return x.x() < 0.0 && v > 0.0;
});

Here x represents the location of sample point in the grid and v represents the sampled value of the input function. If the predicated function evaluates to true the sample point is kept but discarded otherwise.

Optionally, the data structure can be serialized and deserialized via

discrete_grid.save(filename);
discrete_grid.load(filename); // or
discrete_grid = Discregrid::CubicLagrangeDiscreteGrid(filename);

References

  • [KDBB17] D. Koschier, C. Deul, M. Brand and J. Bender, 2017. "An hp-Adaptive Discretization Algorithm for Signed Distance Field Generation", IEEE Transactions on Visualiztion and Computer Graphics 23, 10, 2208-2221.
  • [KB17] D. Koschier and J. Bender, 2017. "Density Maps for Improved SPH Boundary Handling", ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 1-10.
Owner
Comments
  • Error when compiling with clang

    Error when compiling with clang

    When compiling with clang 7.0, I'm getting this error:

    discregrid/include/Discregrid/acceleration/kd_tree.inl:188:32: error: variable 'node' declared with deduced type 'const auto &' cannot appear in its own initializer auto const& node = node(node_index); ______________________^

    I believe clang is right at considering this an error, although I'm no expert in newer C++ syntax.

  • If the mesh is not closed

    If the mesh is not closed

    Hello, I want to use Discregrid to generate a signed distance field but my mesh is not closed, is that means I can't use Discregrid to generate a SDF?

  • Wrong behavior in mesh_distance when using parallelization methods other than OpenMP

    Wrong behavior in mesh_distance when using parallelization methods other than OpenMP

    I had problems with strange results while using Intel TBB along with this library. The problem is in MeshDistance::distance() and MeshDistance::signedDistance(). This happens when the code is roughly like this:

    auto trimesh = std::make_unique<Discregrid::MeshDistance>(...)
    tbb::parallel_for(0, N, [&](size_t i) {
        auto dist = trimesh->signedDistance(v); //race condition!
    })
    

    Although these functions are documented as thread-safe, it seems to be so only in the context of using OpenMP, since it relies on using the thread index from omp_get_thread_num() to make sure that two different threads do not access the same mutable field (such as m_nearest_face). When using this function with other parallelization methods that do not rely on omp_get_thread_num(), errors will likely happen (such as race conditions, or just plain invalid results being returned)

    From delving into the code for MeshDistance, I'm actually confused why there are mutable fields indexed with omp_get_thread_num(), it seems like these fields aren't really necessary for the algorithm to work. m_queues actually seems redundant for the whole code, and m_nearest_face isn't necessary when you can make it as a local variable. The only reason where these mutable fields are needed seems to be for the cached version of the methods (signedDistanceCached, unsignedDistanceCached), but these are still thread-unsafe because of the reason I've mentioned (reliance of OpenMP thread-ids)

    In my opinion it would be best to remove the mutable fields, and move the caching functionality (which I assume was the main reason for making those mutable fields) outside of the MeshDistance class. This will allow the methods to be thread safe, while also allowing for OpenMP-safe caching if the user needs it.

  • How to use cdf file?

    How to use cdf file?

    Hello, I run "./GenerateSDF -r "50 50 50" box.obj" and I got a cdf file, box.cdf. But I don't know how to use the cdf file. How can I visualize the cdf file? I could not read the cdf file using python, such as: f=open('box.cdf','r') text=f.readlines() These codes failed. I study in robotics. And I want to use the sdf to detect collision between robot hand and objects, when I train my neuron network using Tensorflow. How can I do it?

  • If the triangles of the mesh are not consistently oriented.

    If the triangles of the mesh are not consistently oriented.

    Hi, Recently, I find confused about the situation which if the triangles of the mesh are not all consistently oriented, which means some triangles' normals point inwards while some point outward. Does the Discregrid be capable of fix the orientation of all triangles, so that they are consistently oriented? Best regards, Fallen.

  • How to decide the resolution?

    How to decide the resolution?

    Hello, I wonder what factor determines the resolution ? e.g. what's the different may cause to the signed distance field when I use resolution{50,50,50} and resolution{100,100,100} ? And how do I decide which resolution I should use?

  • some problem in mesh_distance.cpp

    some problem in mesh_distance.cpp

    when i peek the source code in geometry/mesh_distance.cpp, i got some questions. image If dmr is lower then 0.0, the code "if (dmr > d_center)" would never be conducted.

    And i could figure out the physical meaning of the variables like temp_ and dist_candiate in the piece of code.

    Thank you very much.

  • how does the discregrid handle the holes in mesh?

    how does the discregrid handle the holes in mesh?

    There always exists some holes in mesh?
    Is there any partical place in the code to handle the issues of holes in meshes? as far as i am concerned, i noticed that the signed of the distance only related to the nearest entity and related triangle info, in which holes may not handled? (UE4 use an heuristic way to determined the "inside", which use the percentage of the hit of mesh faces)

    Thank you very much.

  • Some redundancy data in serialize/deserialize

    Some redundancy data in serialize/deserialize

    i found that m_cell_map and m_cells never change after initialization in cubic_lagrange_discrete_grid.cpp and they only related to the size "m_n_cells". And why to save them in serialize/deserialize?

    [Also, i want to ask is there any references which can help me to understand the serialize and deserialize operations? i do not know m_cell_map's and m_cells's functionality to cope with the interpolation.]

    Thank you very much.

  • how to solve cmake error

    how to solve cmake error

    recently,

    i searched your code, and your code is very well made for PBD.

    so i want to look around your code.

    however, this project makes error when using cmake.

    the error is about EIGEN3_INCLUDE_DIR error.

    how can i solve this problem? can you tell me some tips or solution?

    below is error massage from cmake

    CMake Error at C:/Program Files/CMake/share/cmake-3.10/Modules/FindPackageHandleStandardArgs.cmake:137 (message): Could NOT find Eigen3 (missing: EIGEN3_INCLUDE_DIR EIGEN3_VERSION_OK) (Required is at least version "2.91.0") Call Stack (most recent call first): C:/Program Files/CMake/share/cmake-3.10/Modules/FindPackageHandleStandardArgs.cmake:378 (_FPHSA_FAILURE_MESSAGE) cmake/Modules/FindEigen3.cmake:76 (find_package_handle_standard_args) discregrid/CMakeLists.txt:86 (find_package)

    Thank you in advance.

  • Writing to a specific grid location

    Writing to a specific grid location

    How do I write a value to a specific grid location?

    I have a small number (relative to number of grid cells) of particles. I need to write a value to the grid for a 3x3 grid around each particle

  • Can this work fully runs on a gpu?

    Can this work fully runs on a gpu?

    Background

    • I was implementing a particle based physic engine fully on gpu,here is some result

    taichi

    • But the collision detect is now my bottle neck,so I want to find some sdf representation on gpu
    • I find this repository maybe is the answer, so I read your paper fisrt
    • The paper use polymonials and octree to discretize the domain
    • To be honest,the paper has too much equation beyond my ability now
    • I try to implement it,but I want ask that is it possible to let this code running fully on gpu,because I find a priority queue in the persudo code

    Another question

    • I found nanovdb published
    • And openvdb also use a tree-liked data structure(fixed depth),which has some common with this repository
    • For your opinion,which one is more easily to implement,nanovdb or Discregrid?
  • macOS compatibility

    macOS compatibility

    These adaptations allow builds using Clang on recent versions of macOS (tested on Apple silicon):

    • Recent versions of CMake automatically determine the correct flags for OpenMP and provide a target to link against. Nevertheless, Clang does not include an OpenMP implementation on macOS by default, but the user can easily install a build of LLVM libomp (e.g. via Homebrew) to be shared by all projects requiring OpenMP which is then detected by CMake.
Discrete Conformal Equivalence of Polyhedral Surfaces
Discrete Conformal Equivalence of Polyhedral Surfaces

Discrete Conformal Equivalence of Polyhedral Surfaces C++ demo for "Discrete Conformal Equivalence of Polyhedral Surfaces" by Mark Gillespie, Boris Sp

Jul 10, 2022
FFTW is a free collection of fast C routines for computing the Discrete Fourier Transform in one or more dimensions

FFTW is a free collection of fast C routines for computing the Discrete Fourier Transform in one or more dimensions

Aug 12, 2022
Libft is an individual project at 42 that requires us to re-create some standard C library functions including some additional ones that can be used later to build a library of useful functions for the rest of the program.
Libft is an individual project at 42 that requires us to re-create some standard C library functions including some additional ones that can be used later to build a library of useful functions for the rest of the program.

Libft is an individual project at 42 that requires us to re-create some standard C library functions including some additional ones that can be used later to build a library of useful functions for the rest of the program.

Apr 5, 2022
`lv_lib_100ask` is a reference for various out of the box schemes based on lvgl library or an enhanced interface for various components of lvgl library.

Introduction lv_lib_100ask is a reference for various out of the box schemes based on lvgl library or an enhanced interface for various components of

Aug 11, 2022
A toolkit for pointcloud processing, including: filter, bounding box, ground segmentation, cluster

A toolkit for pointcloud processing, including: filter, bounding box, ground segmentation, cluster. And implemented by different algorithms(some with pcl wrapper). c++17 supported

Jun 23, 2022
Project to remove the 'dotted focus box' around your selections in Windows 11.

Thank you https://github.com/mrexodia/NoFlashWindow for providing this template. With out it this would not have been as easy. Do not run the 32 bit i

Jul 28, 2022
HESS (Hyper Exponential Space Sorting) is a polynomial black-box optimization algorithm, that work very well with any NP-Complete, or NP-Hard problem

The original HESS (Hyper Exponential Space Sorting) is a polynomial black-box optimization algorithm, that work very well with any NP-Complete, or NP-Hard problem, at 2021 thanks to suggestions of Daniel Mattes, work like a complete algorithm.

Jan 18, 2022
HESS HAMILTONIAN PATH COMPLETE (2021) black-box for Hamiltonian Path Problem

The original HESS (Hyper Exponential Space Sorting) is a polynomial black-box optimization algorithm, that work very well with any NP-Complete, or NP-Hard problem

Jan 19, 2022
A tool box of cp/m code that is known to run on cp/m

cpmtoolbox A tool box of cp/m code that is known to run on cp/m This code repo contains cp/m programs that are known to build and run on cp/m systems.

Feb 3, 2022
AVX2-vectorized box filter

vs-boxblur AVX2-vectorized box filter. For integer input, it favors architectures with fast cross lane shuffle (e.g. haswell or later architectures of

Apr 7, 2022
stb single-file public domain libraries for C/C++

stb single-file public domain (or MIT licensed) libraries for C/C++ Noteworthy: image loader: stb_image.h image writer: stb_image_write.h image resize

Aug 18, 2022
Jittey - A public domain text editor written in C and Win32
Jittey  - A public domain text editor written in C and Win32

Jittey (Jacob's Terrific Text Editor) is a single-file basic text editor written in pure C and Win32, there is no real reason to use it, but it

Aug 7, 2022
Public domain, header-only file to simplify the C programmer's life in their interaction with strings

SCL_String Public domain, header-only file to simplify the C programmer's life in their interaction with strings NOTE: This library is still under con

May 5, 2022
Single header lib for JPEG encoding. Public domain. C99. stb style.

tiny_jpeg.h A header-only public domain implementation of Baseline JPEG compression. Features: stb-style header only library. Does not do dynamic allo

Jul 20, 2022
Just another "Won't Fix" Windows Privilege Escalation from User to Domain Admin.
Just another

RemotePotato0 Just another "Won't Fix" Windows Privilege Escalation from User to Domain Admin. RemotePotato0 is an exploit that allows you to escalate

Aug 3, 2022
Several single-file, cross-platform, public domain libraries for C/C++ that I use for learning / testing

HTC Several single-file, cross-platform, public domain libraries for C/C++ that I use for learning / testing (Not meant for production code). This is

Jul 12, 2022
ApeX is a static library for C++ software. Originally it was created to make C++ studying easier,

ApeX is a static library for C++ software. Originally it was created to make C++ studying easier, so it has functions to complete common tasks with just one line of code. But who knows, maybe this library will get bigger some day

Jan 18, 2022
It's a static library that's provide a way to do hooking (intercepting software components) in native shared object from some Android Packages
It's a static library that's provide a way to do hooking (intercepting software components) in native shared object from some Android Packages

ARM_hook It's a static library that's provide a way to do hooking (intercepting software components) in native shared object from some Android Package

Feb 17, 2022
A static C library to build applications for the Foenix retro computers, and, eventually, a single-tasking operating system and file browser that sits atop the Foenix MCP Kernel

@mainpage Foenix A2560 Foenix Retro OS: fr/OS A2560-FoenixRetroOS This project provides 2 things: A static C library/framework that anyone can use to

Jun 24, 2022