{"id":423,"date":"2024-08-06T17:12:09","date_gmt":"2024-08-06T17:12:09","guid":{"rendered":"https:\/\/summergeometry.org\/sgi2024\/?p=423"},"modified":"2024-08-07T00:38:27","modified_gmt":"2024-08-07T00:38:27","slug":"a-study-on-surface-reconstruction-from-signed-distance-data-part-1","status":"publish","type":"post","link":"https:\/\/summergeometry.org\/sgi2024\/a-study-on-surface-reconstruction-from-signed-distance-data-part-1\/","title":{"rendered":"A Study on Surface Reconstruction from Signed Distance Data Part 1: SDFs"},"content":{"rendered":"\n

Primary mentors<\/strong>:\u00a0 Silvia Sell\u00e1n, University of Toronto and Oded Stein, University of Southern California<\/p>\n\n\n\n

Volunteer assistant<\/strong>:\u00a0 Andrew Rodriguez<\/p>\n\n\n\n

Fellows<\/strong>: Johan Azambou, Megan Grosse, Eleanor Wiesler, Anthony Hong, Artur, Sara\u00a0\u00a0<\/p>\n\n\n\n

The definition of SDFs using ducks<\/h2>\n\n\n\n

Suppose that you took a piece of metal wire,<\/em> twisted into some shape you like, let’s make it a flat duck, and then put it on a little pond. The splash of water made by said wire would propagate as a wave all across the pond, inside and outside the wire. If the speed of the wave were \\(1 m\/s \\), you\u2019d have, at every instant, a wavefront<\/em> telling you exactly how far away<\/em> a given point is from the wire.<\/p>\n\n\n

\n
\"\"<\/figure>\n<\/div>\n\n\n

This is the principle behind a distance field<\/em>, a scalar valued field \\( d(\\mathbf{x}) \\) whose value at any given point \\(\\mathbf{x}\\) is given by <\/em>\\( d(\\mathbf{x}, S) = \\min_{\\mathbf{y}}d(\\mathbf{x}, \\mathbf{y})\\), where \\( S \\) <\/em>is a simpled closed curve. To make this a signed <\/em>distance field, we can distinguish between the interior and exterior <\/em>of the shape by adding a minus sign in the interior region.<\/p>\n\n\n\n

Suppose we were to define sdf without knowing the boundary \\(S\\); given a region \\( \\Omega \\) and a surface \\( S \\), whose inside is defined as the closure of \\( \\overline{\\Omega} = A \\). A function \\( f : \\mathbb{R}^n \\rightarrow \\mathbb{R} \\) is said to be a signed distance function<\/strong><\/em> if for every point \\( \\mathbf{x} \\in \\Omega \\) , we have eikonality<\/strong><\/em> \\( | \\nabla f | = 1 \\) and closest point condition<\/em><\/strong>:
\\[ f( \\mathbf{x} – f(\\mathbf{x}) \\nabla f(\\mathbf{x})) = 0 \\]<\/p>\n\n\n

\n
\"\"<\/figure>\n<\/div>\n\n\n

The statement reads very simply: if we have a point \\( \\mathbf{x} \\), and take the difference vector to the normal of the level set at hand times the distance, it should take us to the point \\( \\mathbf{x} \\) closest to the zero level set.<\/p>\n\n\n\n

This second definition is equivalent to the first one by an observation that eikonality implies \\(1\\)-Lipschitz property of the function \\(f\\) and it is also used for the last step of the following derivation: \\(\\exists q \\in S:=f^{-1}(0)\\)
$$
p-f(p) \\nabla f(p)=q \\Longrightarrow p-q=f(p) \\nabla f(p) \\Longrightarrow|p-q|=|f(p)|
$$<\/p>\n\n\n\n

This combined with \\(1\\)-Lipschitz property gives a proof of contradiction for characterization of sdf by eikonality and closest point condition.<\/p>\n\n\n\n

Our project was focused on the SDF-to-Surface<\/em> reconstruction methods, which is, given a SDF, how can we make a surface out of it? I’ll first tell you about the much simpler problem, which is Surface-to-SDF<\/em>.<\/p>\n\n\n\n

Our SDFs<\/h2>\n\n\n\n

To lay the foundation, we started with the 2D case: SDFs in the plane from which we can extract polylines. <\/em>Before performing any tests, we needed a database of SDFs to work with. We created our SDFs using two different skillsets: art and math.<\/p>\n\n\n\n

The first of our SDFs were hand-drawn, using an algorithm that determined the closest perpendicular distance to a drawn image at the number of points in a grid specified by the resolution. This grid of distance values was then converted into a visual representation of these distance values – a two-dimensional SDF. Here are some of our hand-drawn SDFs!<\/p>\n\n\n\n

\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n<\/div>\n\n\n\n
\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n<\/div>\n\n\n\n

The second of our SDFs were drawn using math! Known as exact SDFs, we determined these distances by splitting the plane into regions with inequalities and many AND\/OR statements. Each of these regions was then assigned an individual distance function corresponding to the geometry of that space. Here are some of our exact SDF functions and their extracted polylines!<\/p>\n\n\n\n

\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n<\/div>\n\n\n\n

Exact vs. Drawn<\/h3>\n\n\n\n

Exact Signed Distance Functions (SDFs) provide precise, mathematically rigorous measurements of the shortest distance from any point to the nearest surface of a shape, derived analytically for simple forms and through more complex calculations for intricate geometries. These are ideal for applications demanding high precision but can be computationally intensive. Conversely, drawn or approximate SDFs are numerically estimated and stored in discretized formats such as grids or textures, offering faster computation at the cost of exact accuracy. These are typically used in digital graphics and real-time applications where speed is crucial and minor inaccuracies in distance measurements are acceptable. The choice between them depends on the specific requirements of precision versus performance in the application.<\/p>\n\n\n\n

Operations on SDFs<\/h3>\n\n\n\n

For two SDFs, \\(f_1(x)\\) and \\(f_2(x)\\), representing two shapes, we can define the following operations from constructive geometry:<\/p>\n\n\n\n

Union<\/strong>
$$
f_{\\cup}(x) = \\min(f_1(x), f_2(x))
$$<\/p>\n\n\n\n

Intersection<\/strong>
$$
f_{\\cap}(x) = \\max(f_1(x), f_2(x))
$$<\/p>\n\n\n\n

Difference<\/strong>
$$
f_{\\setminus}(x) = \\max(f_1(x), -f_2(x))
$$<\/p>\n\n\n\n

We used these operations to create the following new sdfs: a cat and a tessellation by hexagons.<\/p>\n\n\n\n

\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n<\/div>\n\n\n\n

Marching Squares Reconstructions with Multiple Resolutions<\/h2>\n\n\n\n

The marching_squares<\/strong> algorithm<\/a> is a contouring method used to extract contour lines (isocontours) or curves from a two-dimensional scalar field (grid). It’s the 2D analogue of the 3D Marching Cubes algorithm, widely used for surface reconstruction in volumetric data. When applied to Signed Distance Functions (SDFs), marching_squares provides a way to visualize the zero level set (the exact boundary) of the function, which represents the shape defined by the SDF. Below are visualizations of various SDFs which we passed into marching squares with varied resolutions in order to test how well it reconstructs the original shape.<\/p>\n\n\n\n

SDF \/ Resolution<\/td>100×100<\/td>30×30<\/td>8×8<\/td><\/tr>
leaf<\/td><\/td><\/td><\/td><\/tr>
leaf
marching_squares
<\/td>		<\/td><\/td><\/td><\/tr>
uneven capsule<\/td><\/td><\/td><\/td><\/tr>
uneven capsule marching_squares<\/td><\/td><\/td><\/td><\/tr>
snowman<\/td><\/td><\/td><\/td><\/tr>
snowman marching_squares<\/td><\/td><\/td><\/td><\/tr>
square<\/td><\/td><\/td><\/td><\/tr>
square
marching_squares
<\/td>		<\/td><\/td><\/td><\/tr><\/tbody><\/table>
sdfs and reconstructions in three different resolutions.<\/figcaption><\/figure>\n\n\n\n

SDFs in 3D Geometry Processing<\/h2>\n\n\n\n

While the work we have done has been 2D in our project, signed-distance functions can be applied to 3D geometry meshes in the same way. Below are various examples from recent papers that use signed distance functions in the 3D setting. Take for example marching cubes, a method for surface reconstruction in volumetric data developed by Lorensen and Cline in 1987 that was originally motivated by medical imaging. If we start with an implicit function, then the marching cubes algorithm works by \u201cmarching\u201d over a uniform grid of cubes and then locating the surface of interest by seeing where the surface intersects with the cubes, and adding triangles with each iteration such that a triangle mesh can ultimately be formed via the union of each triangle. A helpful visualization of this algorithm can be found here<\/a>. <\/p>\n\n\n\n

Take for example our mentors Silvia Sell\u00e1n and Oded Stein\u2019s recent paper \u201cReach For the Spheres<\/em>:Tangency-Aware Surface Reconstruction of SDFs<\/a>\u201d with C. Batty which introduces a new method for reconstructing an explicit triangle mesh surface corresponding to an SDF, an algorithm that uses tangency information to improve reconstructions, and they compare their improved 3D surface reconstructions to marching cubes and an algorithm called Neural Dual Contouring. We can see from their figure below that their SDF and tangency-aware and reconstruction algorithm is more accurate than marching cubes or NDCx.<\/p>\n\n\n\n

\"\"
(<\/em>From Sellan et al, 2024) The Reach for the Spheres method that using tagency information for more accurate surface reconstructions can be seen on both 10^3 and 50^3 SDF grids as being more accurate than competing methods of marching cubes and NDCx. They used features of SDF and the idea of tangency constraints for this novel algorithm.<\/figcaption><\/figure>\n\n\n\n

Another SGI mentor, Professor Keenan Crane, also works with signed distance functions. Below you can see in his recent paper \u201cA Heat Method for Generalized Signed Distance<\/a>\u201d with Nicole Feng, they introduce a novel method for SDF approximation that completes a shape if the geometric structure of interest has a corrupted region like a hole.<\/p>\n\n\n

\n
\"\"
(From Feng and Crane, 2024): In this figure, you can see that the inputted curves in magenta are broken, and the new method introduced by Feng and Crane works by computing signed distances from the broken curves, allowing them to ultimately generate an approximated SDF for the corrupted geometry where other methods fail to do this.<\/figcaption><\/figure>\n<\/div>\n\n\n

Clearly, SDFs are beautiful and extremely useful functions for both 2D and 3D geometry tasks. We hope this introduction to SDFs inspires you to study or apply these functions in your future geometry-related research. <\/p>\n\n\n\n

<\/p>\n\n\n\n

References<\/strong><\/p>\n\n\n\n

Sell\u00e1n, Silvia, Christopher Batty, and Oded Stein. “Reach For the Spheres: Tangency-aware surface reconstruction of SDFs.” SIGGRAPH Asia 2023 Conference Papers<\/em>. 2023.<\/p>\n\n\n\n

Feng, Nicole, and Keenan Crane. “A Heat Method for Generalized Signed Distance.” ACM Transactions on Graphics (TOG)<\/em> 43.4 (2024): 1-19.<\/p>\n\n\n\n

Marschner, Zo\u00eb, et al. “Constructive solid geometry on neural signed distance fields.”\u00a0SIGGRAPH Asia 2023 Conference Papers<\/em>. 2023.

<\/span><\/div><\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Primary mentors:\u00a0 Silvia Sell\u00e1n, University of Toronto and Oded Stein, University of Southern California Volunteer assistant:\u00a0 Andrew Rodriguez Fellows: Johan Azambou, Megan Grosse, Eleanor Wiesler, Anthony Hong, Artur, Sara\u00a0\u00a0 The definition of SDFs using ducks Suppose that you took a piece of metal wire, twisted into some shape you like, let’s make it a flat […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[37],"tags":[],"ppma_author":[24,15,31,16,12],"class_list":["post-423","post","type-post","status-publish","format-standard","hentry","category-research"],"authors":[{"term_id":24,"user_id":0,"is_guest":1,"slug":"cap-ar-bb","display_name":"ar.bb","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","author_category":"","first_name":"","last_name":"","user_url":"","job_title":"","description":""},{"term_id":15,"user_id":0,"is_guest":1,"slug":"cap-hong-x","display_name":"hong.x","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","author_category":"","first_name":"","last_name":"","user_url":"","job_title":"","description":""},{"term_id":31,"user_id":0,"is_guest":1,"slug":"cap-megan-e-grosse","display_name":"megan.e.grosse","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","author_category":"","first_name":"","last_name":"","user_url":"","job_title":"","description":""},{"term_id":16,"user_id":0,"is_guest":1,"slug":"cap-jjohanar","display_name":"jjohanar","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","author_category":"","first_name":"","last_name":"","user_url":"","job_title":"","description":""},{"term_id":12,"user_id":0,"is_guest":1,"slug":"cap-ewiesler","display_name":"ewiesler","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","author_category":"","first_name":"","last_name":"","user_url":"","job_title":"","description":""}],"_links":{"self":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/423","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/comments?post=423"}],"version-history":[{"count":10,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/423\/revisions"}],"predecessor-version":[{"id":1009,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/423\/revisions\/1009"}],"wp:attachment":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/media?parent=423"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/categories?post=423"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/tags?post=423"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/ppma_author?post=423"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}