Triangle mesh to level set

Well I had the idea for this project since last summer, but I did not put it into practice until today.

Level set field data is extremely useful in all kinds of simulation, especially in fluid simulation. Also level set is a good interface for blue noise sampling technique.

Generating level set for a implicit surface is easy, all you have to do is to calculate the function value, and it's always somehow related to the minimum distance(signed).

However, things are not that easy when it comes to general case. You'll always be given a triangle mesh(obj file or ply file) as input. The problem for triangle mesh to level set is: triangle mesh is not continuous.

For a single point-triangle minimum distance, it's sometimes ambiguous how to determine the sign of the distance. For those points within the prism of the triangle, judging sign is easy, but for the those who's nearest point is on edge or vertex, it's hard to determine the sign.

So the idea I had is to calculate normal for all vertices(if not given from input) and all edges. I'm using a weighted sum for all surfaces normal related to the vertex/edge. The weight is the incident angle.

By using this method, the sign of a certain point to an arbitrary triangle is obvious and easy to compute.

No one would like to compute the signed distance for all sample points against all triangles. Two possible solutions:
1. using spacial subdivision data structure like KD tree. calculating signed distance for each sample points in a local region.
2. going the other way around. splat each triangle to a certain neighbor region, forming a narrow-band level set, and propagate the date to the whole field.

The second one is obviously faster but technically harder meanwhile. Since I've already spend a lot of time implementing fast sweeping, this approach fits me better. In fact it took me only a few hours to finish this method.

It cost 3.6s to calculate the level set data of a Stanford bunny using a 105*104*82 grid, running on single core laptop without any optimization. I'm pretty satisfied with the performance, since this conversion has to be done only once off-line.

Here's a demo showing the result of the level set. In order to show the correctness of the data, I shrink the whole field by a certain rate.