Generating a SDF from a watertight triangle mesh

Post ideas, share papers, compare algorithms, and learn new stuff here.
Post Reply
dkdk
Posts: 3
Joined: Thu Dec 21, 2017 4:58 pm
Role: Graphics Programmer

Generating a SDF from a watertight triangle mesh

#1

Post by dkdk » Thu Dec 21, 2017 5:10 pm

Hi there,

I am not sure if I'm searching with the wrong keywords but I have been googling SDFs and triangle meshes for a while and all I seem to get are results that explain how to do 2d font rendering using SDFs and/or how to build them for images/vector-based stuff, but nothing for 3d meshes.

Since I can't find anything I wanted to confirm if I'm on the right track.

To convert an existing, closed triangle mesh to a SDF, one must:

1 Build an uniform grid where the mesh can fit (perhaps with an extra cell in each axis?)
2 Go through all cells in the grid, marking the shortest distance to any mesh triangle for a cell.
3 Iterate trhough the grid, one slice at a time, marking even/odd cell counts as positive/negative.
4 Calculate the normals somehow? This is the step I am missing, I don't know if it would be correct to get all normals for triangles contained or overlapping with a cell and sum them or if that will give incorrect results.

I don't know if this is right but I can't seem to find anything regarding SDFs from meshes, and the ones I've found, disregard normals completely, which I kind of need.

I have found that the normals can be calculated on the fly from a SDF but I can't find a single way of doing it, everyone seems to be doing it differently, and everything I try, doesn't work.

User avatar
Lin
Site Admin
Posts: 22
Joined: Tue Jul 04, 2017 6:02 am
Location: Phoenix, Arizona
Role: Researcher
Contact:

Re: Generating a SDF from a watertight triangle mesh

#2

Post by Lin » Thu Dec 21, 2017 9:58 pm

Do you need signed distance fields or would hermite data work? If the latter is an option, you can simply divide your mesh into a uniform grid and store where a triangle intersects an edge and the face normal associated with it. Signed distance fields are only used because that's usually what scanners produce, and even that data is used to approximate edge crossings (eg. through linear interpolation, like what marching cubes does).

The reason you're struggling to find SDF algorithms that retain normals is probably because you can use partial derivatives from the existing data to calculate a gradient, which when normalized serves as an excellent normal for most purposes (smooth shading and sharp features). You mostly only run into problems when dealing with high-frequency surfaces.

I believe Polymender uses the above techniques to convert a mesh into something dual contouring can work with, so if you run into problems you can refer to that.

dkdk
Posts: 3
Joined: Thu Dec 21, 2017 4:58 pm
Role: Graphics Programmer

Re: Generating a SDF from a watertight triangle mesh

#3

Post by dkdk » Fri Dec 22, 2017 9:04 am

Thank you very much for your super quick reply!

I think that it will help if I explain what I'm trying to do ;) My end goal is to have an algorithm that does the mesh > volume > mesh conversion, which I understand that may destroy some sharp features in the process but I do an extra projection step where newly created vertices within an error threshold are reprojected back to the original triangle mesh to reduce possible deterioration as part of this process.

I have had my existing version of this process in use for roughly 3 years and have been fairly happy with the results, but at the moment meshes generated are a bit of a mess since it uses Marching Cubes for the volume to mesh step, I wanted to try out Manifold Dual Contouring since it generates much cleaner, quad-only meshes, and found out that it needs extra data (normals) so I've been trying to find out where to get them from... ;)

I found this, which after reading discouraged me a little from using gradients, since it says that they may not be accurate enough, although in my case I don't have very high frequency as you say so I might be ok with those (my grids are limited to a max of 256^256^256) https://cs.uwaterloo.ca/~c2batty/misc/l ... ction.html

I think that hermite data should work too, although I am not big on obscure scholar wording/naming, just so I understand, what the DC paper meant by hermite data, was it only intersection points and normals with grid cell edges?

If so, in my case I may have many triangles inside a cell, would it be correct to just average the intersection coordinates and normals, perhaps with some area overlap metric weights so smaller cell-overlapping triangles don't affect as much as bigger ones in the final averaged result of for points and normals? (http://xingdu.blogspot.com.es/2013/02/t ... l-set.html)

Apologies if this is obvious but I sometimes struggle to understand "simple" algorithms due to scholar obfuscation.

(edit) PS: after writing this, I realised that I'm not the only one with such questions haha, https://stackoverflow.com/questions/472 ... -algorithm

User avatar
Lin
Site Admin
Posts: 22
Joined: Tue Jul 04, 2017 6:02 am
Location: Phoenix, Arizona
Role: Researcher
Contact:

Re: Generating a SDF from a watertight triangle mesh

#4

Post by Lin » Sat Dec 23, 2017 1:03 am

Re-meshing is a whole field of its own, but fortunately there are very awesome solutions. Recently I discovered and implemented a paper that produces the highest quality results for the speed that I've found, including sharp feature reconstruction. Similar to what you're doing, it relies on projecting vertices onto the surface (typically using gradient descent) and some optional mesh refinement/decimation techniques. You can feed it any mesh you want, but the paper specifically uses marching cubes so I think you'll find the transition easy. The paper can be found here.

As far as scholar obfuscation goes, I definitely hear you there. Back about 2 years ago when I was trying to learn how dual contouring worked, it was extremely challenging getting anything to click. But at this point I've read and implemented so many papers that you can ask pretty much any question and I can clear things up.

Hermite data is just edge intersections and the normals at those points. When you have multiple triangles per cell, averaging the intersections sounds like the best idea for uniform grids; otherwise you can try an adaptive approach. Let me know if I can help in any way.

dkdk
Posts: 3
Joined: Thu Dec 21, 2017 4:58 pm
Role: Graphics Programmer

Re: Generating a SDF from a watertight triangle mesh

#5

Post by dkdk » Sat Dec 23, 2017 7:28 pm

Thank you very much! I’ll have a good look at the paper.

I’m going to start implementing Dual Contouring over the holiday break now that I understand what that “hermite data” is about ;)

I may take your word, and ask you about Manifold DC after I get DC working...

Cheers!

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest