Is there a library/code snipped which which can convert meshes to a sdf in vector representation for subvoxel exact representation?

Question

I need to generate a sdf on a grid from a 2D mesh to represent the mesh as a closed body in cinder.

My first approach was to use a distance function (euclidean) to check if a gridpoint is close to a meshpoint and then set the value to - or +, but this resulted in bad resolution. Next I tried to add up distances to get a continuous distance field. which resulted in a blown up object. I am not sure how to represent the the distance to a closed object described by a mesh (concav or convex). My current approach is described in the code below.

#include <iostream>
#include <fstream>
#include <string>
#include <Eigen/Dense>
#include <vector>
#include <algorithm>
#include <random>

using namespace std;
using namespace Eigen;
typedef Eigen::Matrix<double, 2, 1> Vector2;
typedef Eigen::Matrix<double, 3, 2> Vector32;
typedef std::vector<Vector2, Eigen::aligned_allocator<Vector2> > Vector2List;
typedef std::vector<Eigen::Vector3i, Eigen::aligned_allocator<Eigen::Vector3i> > Vector3iList;
typedef std::vector<Vector32> Vector32List;
typedef Eigen::Array<double, Eigen::Dynamic, Eigen::Dynamic> grid_t;


void f( Vector2List vertices, Vector3iList triangles)
{ // each entry of triangles describe which vertice point belongs
  // to a triangle of the mesh 
grid_t sdf  = grid_t::Zero(resolution, resolution);
for (int x = 0; x < resolution; ++x) {
        for (int y = 0; y < resolution; ++y) {
            Vector2d pos((x + 0.5) / resolution, (y + 0.5) / resolution);
            double dist = 1 / double(resolution*resolution);
            double check = 100;
            double val = 0;
for (std::vector<Vector2>::iterator mean = vertices.begin(); mean != vertices.end(); ++mean) {
        //try sdf with euclidian distance function
                check = (pos - *mean).squaredNorm();
                if (check < dist) {
                    val = -1; break;
                }
                else {
                    val = 20;
                }

            }

            val *= resolution;
            static const double epsilon = 0.01;
            if (abs(val) < epsilon) {
                val = 0;
                numberOfClamped++;
            }
            sdf(x,  y) = val; //
        }
    }
}

Answer 1

It seems as if you have a slight misunderstanding of what the SDF actually is. So let me start with this.

The Signed Distance Function is a function over 2D space that gives you the distance of the respective point to the closest point on the mesh. The distance is positive for points outside of the mesh and negative for points inside (or the other way around). Naturally, points directly on the mesh will have zero distance. We can represent this function formally as:

sdf(x, y) = distance

This is a continuous function and we need a discrete representation that we can work with. A common choice is to use a uniform grid like the one that you want to use. We then sample the SDF at the grid points. Once we have distance values for all our grid points, we can interpolate the SDF between them to get the SDF everywhere. Note that each sample corresponds to a single point and not an area (e.g., a cell).

With this in mind, let us take a look at your code:

Vector2d pos((x + 0.5) / resolution, (y + 0.5) / resolution);

This depends on how the grid point indices map to global coordinates. It might be correct. However, it looks as if it assumes that sample positions are located in the middle of the respective cells. Again, this might be correct, but I assume the + 0.5 should be left away.

for (std::vector<Vector2>::iterator mean = vertices.begin(); mean != vertices.end(); ++mean)

This is an approximation of the SDF. It calculates the closest vertex of the mesh and not the closest point (which may lie on an edge). For dense meshes, this should be fine. If you have coarse meshes, you should iterate the edges and calculate the closest points on these.

if (check < dist) {
    val = -1; break;
} else {
    val = 20;
}

I don't really know what this is. As explained above, the value of the SDF is the signed distance. Not some arbitrary value. Also the sign should not correspond to whether the mesh is close to the grid position. So, what you should have done instead is:

if(check < val * val) {
    //this point is closer than the current closest point
    val = std::sqrt(check); //set to absolute distance
    if(*mean is inside the mesh)
        val *= -1; //invert the sign
}

And finally, this piece:

val *= resolution;
static const double epsilon = 0.01;
if (abs(val) < epsilon) {
    val = 0;
    numberOfClamped++;
}

Again, I don't know what this is supposed to do. Just leave it away.