Algorithms for Generalized Signed Distance and Winding Numbers (PhD thesis)

[00:00:00]Hi, and thanks for tuning in. I'm so happy to be sharing some of my work in geometric computing. If there's one thing I've come to appreciate, it's that studying geometry is really compelling.

[00:00:10]So much of our lives are defined by geometry, where examples include both natural phenomena and also human structures, including some things you might see around you right now and also maybe what you might not see.

[00:00:22]And our ability to solve problems involving geometry drives a lot of technological progress. Every day we probably interact with hundreds if not thousands of objects either real or digital that have been designed, simulated or manufactured. And fundamentally these processes involve modeling and manipulating geometry. So maybe unsurprisingly problems involving geometry are everywhere and they can be tricky to solve sometimes just because computation with geometry can be tricky.

[00:00:50]To do computation we need some discrete representation of geometry that computers can interact with. For example, a smooth surface is often approximated by a mesh. And when you look at actual meshes, they can be messy. Actually, there are so many different ways they can be messy, and it's hard to predict how. Like, they might have holes or missing data. They can intersect themselves or have what are called non-manifold features. And these cause problems when you then want to analyze or do something with the shape. Now, you could repair the mesh, but repairing geometry is difficult. It usually requires human expertise and a lot of manual work. And if you talk with any person who works with 3D geometry, you will find a lot of frustration about the brittleleness of geometric software tools. Further complicating matters, there are so many different types of representations because there are so many different ways that people acquire in author geometry. Unfortunately, a lot of this data is messy too because scanning and modeling processes are never perfect, computer vision algorithms are never perfect, and so on.

[00:01:49]The point is that each of these representations have low-level defects that affect the operations done on them.

[00:01:55]This is a problem because all of these low-level defects are unpredictable and frustrate higher level design and optimization tasks such as reliable physics analysis or machine learning pipelines that require large quantities of pre-processed clean data just to name a few examples. So we need algorithms for computing geometric quantities that are tolerant of defective data. And defining what this means not just for one particular representation but about geometry itself. And being able to build constructive algorithms requires answering fundamental questions about geometry. In other words, we need robust geometry processing. We need methods that work reliably across varying degrees of quality in their input. So during my PhD I've worked on two basic geometric questions. The first on inside outside computation and the other on signed distance computation.

[00:02:46]Specifically the methods I'm going to talk about generalize from imperfect observations such as point sets and broken meshes to answer questions about the underlying curve or surface. I'll refer to these methods as providing so-called generalized versions of inside outside and sign distance to distinguish from other types of robustness that you might have heard about. So why these questions like why inside outside computation? Well, intuitively closed objects like this curve separate space into an inside or interior region and an exterior region. Determining the interior or equivalently determining the exterior of a curve or surface is a really fundamental problem. For example, surface reconstruction is this perennial task that aims to infer or reconstruct the surface underlying a set of samples collected from say a 3D scanner. And the output is a well- definfined interior and exterior of a shape and lots of other downstream tasks also depend on reliable inside outside computation.

[00:03:47]Second, why sign distance? Well, the distance part involves computing the shortest distance to the curve or surface. Distance fields have a lot of desirable geometric qualities and are used in a broad range of tasks from modeling to physics simulation, rendering and more. Signed distance then combines distance with inside outside information giving information about which side of a shape boundary a given point lies. So sign distance is actually very related to inside outside computation. And during my PhD I've also thought about the connection between inside outside and sign distance and how you can compute both.

[00:04:22]So for the rest of the talk, I'll first get into more detail about these two quantities and then describe three algorithms that aims to compute generalized versions of them as well as possible.

[00:04:33]First, I'll describe the theory underlying our work. To generalize the concepts I just introduced, we're going to think of the inside and outside of a shape as a function. When we're just talking about two regions, usually we give the inside a value of one and the outside a value of zero. But beyond inside and outside curves can enclose points multiple times. So more generally we can consider not just a binary function but an integer valued function.

[00:04:59]This function is called the winding number.

[00:05:02]Winding numbers show up in a lot of different fields because the concept of inside and outside is so fundamental.

[00:05:08]They also have an extensive history in computer graphics where a lot of quantities are secretly winding number.

[00:05:14]Slightly more formally, winding number can be described mathematically, extending this intuitive notion that it should jump by one every time we cross the curve. We can then extend this jump condition into a PTE describing how the function gets interpolated across space in some nice way. Here the resulting function is a particular type of function called harmonic. Solving this equation gives us a nice way to compute inside outside functions. Since the curves here on this cow were not closed, we get not an integer valued function but sort of a soft real valued function that gives us a reasonable estimate.

[00:05:50]Then you can round or contour this function to get clear integer valued region labels. The point is that the initial curves even though they're not perfect do provide some meaningful signal about inside and outside and that information gets interpolated in a nice way using this equation. So this equation is already a generalization of the ordinary integer valued winding number. Alternatively, in ordinary uklitian space, meaning space that's not a curved surface, you can formulate a boundary integral equivalent to this PTE, meaning you just have to convolve a particular kernel over the geometry omega. And this has led to several other reconstruction algorithms.

[00:06:30]Beyond inside and outside, we can of course also talk about distance to the curve. When this distance information is combined with inside outside information, it's called signed distance because you can denote the inside and outside with a positive or negative sign on the distance value.

[00:06:47]Signed distance can also be described by an equation. This time it's called an iconal equation and it has certain boundary conditions. This equation is different than the one that describes winding numbers. But surprisingly, it turns out the two equations are actually related.

[00:07:03]In particular, you can consider a slight perturbation of this iconal equation adding a small amount of diffusion or viscosity and use something called the hopole transformation to arrive at a jump screened lelass equation where the viscosity term in the originally nonlinear iconal equation becomes a screening term on this linear lelass equation where we also have boundary conditions making the solution jump by an integer amount across the curve or surface omega. In fact, up to the screening term in some scaling, this is equivalent to the equation we showed for winding numbers. And to the best of our knowledge, this connection wasn't really known before. The thing is, people had largely been aware of similar exponential transformations, but mostly for unsigned distance. And so the connection to inside outside in finding numbers wasn't so clear. To get a feel for why this transformation works, here's the solution to the jump screen lelass equation for a closed curve, which you can think of as diffusing double-sided boundary conditions from the curve. Diffusion results in a function that decays roughly exponentially in distance. So applying the inverse hop transformation essentially reverses this exponential decay by taking a log to give us an approximation of distance. The drum screen leelass equation can also be rewritten as a screen pan equation. So now we actually have a close relationship between some classic inside outside methods and sign distance. On the one hand as this screening parameter lambda goes to zero. The left equation becomes a jump lelass equation whose solutions are the jump harmonic functions I introduced earlier for winding number. The right equation is a special case of a classic algorithm called panon surface reconstruction as lambda goes to zero which in turn is equivalent to a regularized version of winding numbers.

[00:08:53]Like before in uklitian space we can formulate an equivalent boundary integral meaning we just have to convolve a particular kernel over the geometry characterized by exponential decay. But actually the kernel used for convolution doesn't even have to be this particular one. In fact, for any integral of the following exponential form, as lambda gets larger and larger, this integral becomes asmtoically equivalent to an expression involving xstar, the global minimizer of the function fee inside the exponential.

[00:09:22]Intuitively, this happens because the integrant is becoming increasingly peaked where f is smallest. And in the limit, all the other contributions become exponentially small with respect to this peak contribution. So applying a log to both sides, this means that asmtoically we obtain a direct estimate for the minimum of fee. I find this argument most intuitive in the discrete setting. So imagine we're given a vector of n values, for example, these five values. If we apply the exponential function, the difference between the largest of these values versus the rest will become exponentially exaggerated.

[00:09:58]Similarly, if we apply the exponential function instead to the negation of these values, it's instead the smallest of these contributions that becomes exponentially larger than the rest. And the severity of the exponential disparity is controlled by the parameter lambda with greater lambda meaning more extreme differentiation. In other words, the exponential function supercharges the most extreme value and makes it dominate the sum or integral. So when we take the log this makes the whole process acts as a smoothed version of the minimum or maximum operator.

[00:10:32]So back to our analysis we can derive a distance formula just by letting the function f equal a uklitian distance function and ultimately approximate the distance from a point x to its closest point in omega. In summary, this argument yields a more general form for what I call a convolutional distance formula where a special case is the formula we derived earlier using hop coal. There are also a lot of other instances of this formula throughout math and science. So this set of insights was theoretically quite satisfying. In summary, we showed that the intuitive connection between sign distance and inside outside can be formalized through a relatively simple change of variables in their PTEES and that many exponential transformations can be seen as instances of just one general principle. Because of this, many past methods for either reconstruction or distance can be seen as different facets of the same framework. But while these insights may feel satisfying, unfortunately, I also found that these distance formulas break down in practice for discrete or messy shapes. In particular, we obtain a distance function whose level sets are to the sampled geometry rather than to the underlying surface from which the discrete geometry is sampled. In this case, we just get a trivial distance function to the set of points. And the sign basically corresponds to a simple plane test heristic using the point normals. This is a problem because we want distance to a nice completion of the surface. The reason for this behavior is that convolutional distance approximations are essentially single point approximations which makes them not capable of generalization by nature.

[00:12:09]The exponential is so powerful it just dominates everything. There seems to be no happy medium either in terms of the amount of screening. Meaning even if we let lambda not be so large empirically there's no point at which you get both good level sets to a good reconstruction and good distance. I also found that when lambda is smaller it's easy to get additional artifacts. But the upshot is that these asmtoics are based on scalar diffusion which maybe suggests developing strategies that for example use higher order information.

[00:12:39]In our first method for achieving generalized sign distance does exactly that. Here our idea was to diffuse not scalar data but the normal vectors of the source geometry. Then it turns out the vector fields you get by normalizing these diffused vectors approximates the gradient of a sign distance field. So to get signed distance we find the function whose gradient best matches this vector field giving us a generalized sign distance function. Because this method is based on heat diffusion we called it the signed heat method. The reason why this procedure actually works boils down to the following theorem which says that something called parallel transport along shortest geodessics can be computed using shorttime vector diffusion. Intuitively in the plane the shortest geodessic or shortest path between two points is simply a straight line connecting them. And if we have a vector at P parallel transporting this vector along the line means keeping it as parallel as possible to its original state. Equivalently, we want this vector to maintain a constant angle with the geodeic during transport.

[00:13:48]Of course, in the plane, you can see that parallel transport of a vector along the shortest geodeic simply amounts to translating the initial vector along the straight line. On a curved surface, things get a bit more complicated. But we can still consider a shortest geodessic connecting two points and play a similar game to define parallel transport. And what that theorem was saying is that almost miraculously this transport can be computed using short-time vector diffusion. To understand vector diffusion, I'll first start by describing scalar heat flow where an initial scalar distribution changes in time according to its leashion. When you flow the heat equation, extreme values and bumps get smoothed out and we get something that basically looks like a blurred out version of the initial distribution as time goes on. And this blurriness is characterized by exponential decay.

[00:14:38]The same picture more or less applies for vector value distributions. We can likewise define a vector heat equation that acts on vector value data and describes similar dynamics in uklidian space. This is equivalent actually to simply apply the scalar heat equation component-wise to the vector fields. So each component of the vector field is going to diffuse according to scalar heat flow. Meaning vectors basically get translated throughout space while their magnitudes decay exponentially.

[00:15:06]On manifolds, the tangent space at every point locally looks uklidian and vector heat flow looks really similar.

[00:15:12]Asmtoically, we end up arriving at the following expansion where the magnitude is governed by the same exponential decay that describes the scalar heat kernel in uklidian space. Most importantly, the leading term is the parallel transport map that takes vectors from one point to another along the shortest due desic connecting the two. And as the diffusion time t gets smaller and smaller, this term dominates asmtoically.

[00:15:37]This property had already been recognized and used in geometry processing. And we just recognize the additional implications for computing sign distance.

[00:15:46]In particular, the theorem tells us that as a diffusion time becomes shorter, a diffused normal vector will align with a vector obtained by parallel transporting the normal along a short estic. And this means that this vector is aligned with the gradient of sign distance because traveling along the shortest geodisic is by definition the shortest way back to the curve. Then normalizing this vector field approximates a sign distance gradient and we can simply integrate to obtain the sign distance function itself.

[00:16:16]In contrast, the convolutional distance formulas from before couldn't give both a reconstruction and good distance because the screening amount lambda was coupled to both in opposite directions.

[00:16:28]But here we are essentially decoupling these two things because we diffuse gradients which leads to better completion behavior and ultimately we get a function with good distance accuracy to a good reconstruction of the surface.

[00:16:41]By the way, the diffuse vectors before normalization actually still exhibit this shorttime diffusion specific phenomenon of being really concentrated around the points. But now it's okay.

[00:16:53]The concentration is happening in the magnitude of the vectors. The vectors still have the right direction. So when we normalize, we get an approximation of the gradient.

[00:17:03]This behavior is significantly different than diffusing scalar data where because the concentration is happening directly in the scalar function that we care about, it's hard to get a generalized distance function.

[00:17:14]The steps of the sign heat method boil down to the following equations. I won't go into the details, but in total, the method amounts to solving just two sparse linear systems.

[00:17:26]By the way, not only can we compute sign distance to curves, but we can also compute unsigned distance just by changing the direction of the normal vectors we diffuse in the first step. So we can do interesting things like combine both signed and unsigned distance into a single distance field.

[00:17:43]For some more examples and applications, here we compute generalized sign distance to a broken surface. By extracting level sets of this distance function, we get nice closed manifold surfaces. And these surfaces also have the nice property that they're evenly spaced with distance.

[00:18:00]In general, we find that our method is robust to defects in the source curves, for example, ones that might arise from drawing on surfaces.

[00:18:08]The method is also robust to errors in the surface domain itself and applies out of the box to non-manifold and self-intersecting meshes.

[00:18:18]Now, the question is, can we make this method even better? In particular, one drawback of the sign heat method is that like all finite element based methods, you have to discretise space and discretize reasonably well. Also, even if you only want the solution at one or a few particular points, you always have to solve this global system. Now, this has good amortized performance if you want the solution densely in space like in this demo, but not so much if you only want the solution at one single point. Now, given how well the sign method worked, it's tempting to just try adapting it.

[00:18:52]The first thing you might try is turning its PTE formulation into the following integral formulation. Just like we did before with all of the other PTE based distance formulas, this sequence of steps can be boiled down into just the last integral. But unfortunately, this integral isn't well posed. In particular, the solution needs to decay to zero at infinity. Whereas a distance function actually does the opposite. It goes to infinity at infinity. Now instead of an infinite domain, let's say we try some finite domain.

[00:19:24]But this integral formulation is also not tractable. Here's the standard integral equation for a pan problem. But this equation is recursive. It requires that we know the value of the solution on the domain boundary.

[00:19:37]This problem stumps me for a couple years. And the solution we eventually developed actually revisits the convolutional distance formulas I trash talked before because even though they give us the wrong answer, they're at least fast and have the computational properties that we're asking for. Now, now this formula we said unfortunately can't produce generalized distance. But we can also derive a second type of convolutional distance formula and this self-normalized variant is more promising because it interpolates this function G instead whose design space can be much larger. In fact, the sign heat method effectively implemented this formula already where we first diffused normal vectors and then normalized by their magnitudes. The vector heat method which was a method that came before ours actually also use this formula.

[00:20:26]So it's tempting to do something like the following where we interpolate some local function for sign distance. Many works in the past actually do use this type of pseudonormal heristic.

[00:20:36]Unfortunately for point clouds we get these ugly vorinoi like linear completions. So instead of linear surface approximations our big idea was to fit second order surfaces instead.

[00:20:47]And in particular, we decided to use tory because tory can locally capture spherical and ellipsoil surfaces as well as saddle-shaped surfaces. And in the limit, they can also capture your usual planes and cylinders. Seconds, unlike polomial patches and quadric surfaces and all of the other geometric proxies that people have used to fit point clouds in the past, to actually have closed form sign distance functions that are cheap to evaluate. We're not the first ever to consider fitting to point sets, but as far as I know, they hadn't been used before to construct SDFs.

[00:21:20]These toy can look kind of crazy once fitted to a point cloud, but they all blend together nicely into a global SDF using our self-normalized convolutional formula. The reason this works is because it's only important that each Taurus matches the underlying surface within a small neighborhood. And to match a Taurus to the underlying surface, the idea is pretty straightforward. Around each point we assume the true surface can be expressed as a quadratic polomial. We use a coordinate system aligned with a point normal which we assume is given to us.

[00:21:50]And this information is enough to determine an osculating Taurus. And in fact, we actually only need the following six coefficients. These six coefficients determine a Taurus whose equator passes through the surface point at the origin and aligns with the principal curvatures and directions at that point. Then the SDF of a Taurus has the following simple expression which basically boils down to two applications of the SDF of a circle.

[00:22:16]Then of course we just have to determine the sign of the Taurus. Here are the two sign combinations of principal curvatures corresponding to a positive SDF meaning the Taurus osculates the surface from the shaped interior. And likewise there are two sign combinations for a negative SDF. Okay. So fitting a Taurus to a given polomial surface is easy. The hard part is getting this polomial in the first place. It's hard because inferring the true surface even locally within a small neighborhood of the point cloud is hard because just figuring out what this neighborhood should be is really difficult and classic methods are extremely dependent on heristics for neighborhood size and shape. For example, a classic paradigm is to use a Gausian kernel to determine neighborhood size which we find incredibly brittle. There's no one kernel bandwidth that yields good results and so the downstream SDF breaks down. Because of how difficult this problem is, there's been a huge amount of literature proposing endless variations of similar kernelbased methods for local reconstruction. We tried classic tricks like anisotropic kernels and hierarchical approaches, but these were sensitive to parameter tuning. And of course, there are more sophisticated statistical methods, but they come at a cost. And probably any one of these methods you choose, you can also probably think of a class of data for which your assumed model breaks down. For example, there might be some models that work really well for smooth shapes but break down for CAN models with edges and corners. And so rather than manually tweak the parameters of one particular surface fitting model, we instead just use a fixedsiz neighborhood, but use a datadriven approach that can fit to an extremely large set of examples. far more examples and using a far more sophisticated data fitting model than we could ever craft purely by hand. And we can do this easily precisely because we've broken down the problem into one that's dominated by local surface behavior and it's easy to generate massive amounts of training data for individual surface batches. So to that end, we design a neural network that as input takes in a point in its K nearest neighbors and outputs the six coefficients needed to fit a Taurus. We use the following architecture which at a high level embeds the input points and normals into a higher dimension. Uses transformer blocks to learn which points in the neighborhood are most important for fitting a local surface. Then projects the feature vector corresponding to the input point down to six scalar values using a learned projection. To train this network, we use CAD models and procedurally generated shapes and sample them into point clouds. We use size 64 neighborhoods and in total this made about 40 million training examples. as our loss function within each neighborhood. We simply penalize the difference between the predicted and true sign distance values and also use an iconal error that implicitly encourages neighborhoods to blend together smoothly. In total, pre-training took about 45 hours on a single GPU. Because this network is purely local, it needs to be pre-trained only once before you can apply it to any neighborhood of any possible surface. So for a given point cloud, we first fit to by applying this pre-trained network to each neighborhood, which usually takes a few seconds or if the point cloud is a few tens of millions of points, a few minutes, but this needs to be done only once per point cloud. Then the final SDF is obtained using the simple formula. So queries are fast and of course multiple queries are easily parallelizable.

[00:25:34]We also just have a single simple formula for lambda. So, we don't have to play around with lambda or make this trade-off between reconstruction and distance. In these past convolutional formulas, it's actually not even very easy to choose a lambda that gives a good reconstruction. For example, it's easy to accidentally merge the two roots of this tooth.

[00:25:53]In fact, our method gives better reconstructions than other fast point-based methods, including past point-based versions of winding number while also providing sign distance almost as fast. Due to the point-wise nature of this method, you can directly sphere trace level set surfaces in a shader, as well as do some other cool shader demos. Here, the SDF values you see are being evaluated per pixel in real time. Here's the method's performance as a function of point cloud size using a 3D scan. Here, the largest point cloud has about 29 million points, and there premputee does take about 12 1/2 minutes, which is not super trivial.

[00:26:28]But in contrast, the sign heat method can really struggle sometimes. Here the linear solver complains that the linear system was indefinite where it expected a positive definite system. Now on the one hand it's easily possible to either modify the linear system or adjust the linear solver or make the method run faster by meshing only in select regions where you actually want the solution.

[00:26:49]But these workarounds still add a layer of manual complexity in implementation.

[00:26:54]And on larger systems like this one, it's kind of annoying to wait a long time just to find out that the implementation needs adjusting.

[00:27:01]The network was also still able to handle some amount of noise and varying density in the point cloud even though I didn't train on examples with those features. The top is an example where I'm taking offset surfaces to a point cloud of varying density and at the bottom are some point clouds from coal map. And actually for sparse point clouds the new method can give better results than the sign heat method.

[00:27:22]Sometimes the sign heat method just gives pretty bad results on really sparse data. comparing against some other reconstruction algorithms like bassan surface reconstruction or the more recent n and vips method both of them can also struggle here. So while I think something like the sign heat method is the better general purpose solution, I think the points histori has the edge here because the network is drains on relatively sparse point clouds and within that indistribution data has the better performance. That being said, bonan surface reconstruction uses an adaptive multi-grid strategy that scales better with point cloud size. As a datadriven method, our method can fail in unexpected ways. For example, I found that when I applied the method to point clouds with significantly different densities than seen in training, which only used point clouds with around 2,000 points, the level sets inside the shape can actually get worse. So, it's probably important to train on more diverse data or perhaps include some form of neighborhood size estimation after all. Or maybe just sample point clouds accordingly or apply some pre-processing to the input data. I think this project also has some lessons that encourage more judicious use of learning in other problems. For example, these days people are talking a lot about something called foundation models where the general feeling is that they should provide these three properties.

[00:28:38]Well, in our problem we achieve these properties by relying on this particular analytical formula for sign distance.

[00:28:44]There is a datadriven component but it can be reused across multiple problems and the algorithm as a result is more scalable than past methods. Recently, there have been other similar appeals for how we should build things like neural operators or basis functions for FEM. And in each of these cases, the higher level takeaway is that you can get a lot of mileage sometimes out of using datadriven methods to gain representational power, but otherwise still rely on classical methods if you can to provide structure and convergence and stability. Going even further, I think the ideas we learned through the perspective of lowdimensional geometry can also benefit tasks like generative modeling that are currently dominated by expensive massive neural networks. In particular, diffusion and flow matching models aim to sample from some target distribution by parameterizing a transformation between samples as a time dependent differential equation. In most cases, there's actually a closed form expression for this OD that looks really similar to our distance formula. Namely, this purple part is a vector that points from the current sample to an estimate of the closest data point seen in training. So this whole update rule simply pushes samples towards the closest point in the training data. As is, this means that flow-based models can actually only just memorize their training data, meaning they can't generalize. In other words, we simply reproduce the distribution represented by the discrete training data rather than the true distribution we hope to approximate. And this is exactly the reason why naive convolutional distance formulas all fail to generalize.

[00:30:16]Many authors have observed this phenomenon in the context of generative modeling and the current state-of-the-art is to train a really expensive neural network that implicitly regularizes the problem. Very recently some authors have begun to explore some of these geometry based ideas and I still think there are improvements to be made. Okay, so that wraps up our discussion of sign distance. And now I'd like to address one more ambiguity and that has to do with a seemingly much simpler idea of computing inside and outside. Before I had presented this nice picture of what it means to be inside or outside a shape. But actually there can exist cases where shapes don't have a well- definfined inside or outside. For example, the first fence forms a closed curve that confines the cows, but the second fence doesn't even though it also forms a closed curve. In other words, one curve bounds a region and the other doesn't. Complicating things, these so-called non-bounding curves can still combine to bound meaningful regions. So, you can't just throw them all away. It's also hard to know which curves, if any, to ignore because there can be multiple ways to partition a curve into bounding and non-bounding components. There are other ambiguous cases as well. And just like we saw with distance computation, it gets harder to answer these questions if some curves are corrupted. To answer these questions, we'll be revisiting winding numbers, which have this extensive history across math and physics. Unfortunately, none of the many formulas people have come up with over the last few hundred years work on general surfaces because fundamentally there can exist curves that don't bound regions. What happens is that if the domain has trivial topology, then everything is fine like we saw before.

[00:31:52]But if our domain has non-trivial topology, then simply rounding results in discontinuities that don't actually corresponds to any region boundaries.

[00:32:01]The basic idea of our method is to actually look at the derivative of this jump harmonic function instead. It turns out this derivative tells us about non-bounding curves. In particular, the derivative is zero if and only if all curves are bounding because the function is peace-wise constant. But if some parts of the curve are non-bounding, then the derivative will be a nonzero harmonic one form. You don't really need to know what it means for a one form to be harmonic. Only that there's this really nice topology fact that there's a correspondence between non-bounding curves and harmonic one forms. In general, for broken curves, the derivative is not purely harmonic, but has additional non-harmonic parts. So we apply Hodgej decomposition, which is a classic tool for decomposing one forms to extract the harmonic part. Then we integrate this harmonic form into a scalar residual function whose jumps will identify the non-bounding parts of the curve. Doing this integration at a high level searches for the shortest completion of the curve that agrees with the harmonic one form. The reason why we look for the shortest completion is that there are always multiple possible completions and we want to pick one that's well behaved. And if there are multiple possible curve decompositions, we always pick the one with the shortest possible set of non-bounding curves.

[00:33:16]In the end, we get an algorithm that we call surface winding numbers. And it handles general topology, meaning all of the interesting types of surfaces I showed before, as well as broken curves.

[00:33:27]And computationally speaking, the algorithm ends up boiling down to some sparse linear systems in a small linear program. The insights from this method help us better understand sign distance as well because sign distance again depends directly on having a well- definfined inside and outside. Now it doesn't matter so much in Rn where it's not possible to have non-bounding curves. But something we tried on curved surfaces was to adjust the final step of the sign heat method. If you look at the sign distance gradient of a non-bounding curve, you get this vector fields that can't be integrated into a continuous solution which maybe is unsurprising given this curve doesn't really have an inside or outside. So if you try and integrate this vector field as usual, the fields will look incredibly warped.

[00:34:10]So we instead tried integrating the vector field into a function that's only peacewise continuous using an optimization very similar to the one used for the residual function in the surface winding numbers algorithm. This results in an SDF that has much better behaved isoblines despite the fundamental sign ambiguity. Now, if you did just want to identify or filter out non-bounding loops, we tested this by setting up a benchmark of about 900 surfaces with a combination of bounding and non-bounding curves on them and scrupted these curves randomly.

[00:34:41]When there are non-bounding loops, our method correctly classifies inside and outside more accurately as a percentage of surface area compared to simply rounding the initial jump harmonic function that you get from solving the equivalent of ordinary whining number on surfaces. So without processing the non-bounding loops, they can really influence the results. And our method here is obviously not perfect. There is still some amount of error in the top chart. But sometimes this is simply due to other types of fundamental ambiguity in the input. For example, here we've constructed an example starting with five loops all in the same homology class. And given their orientations, you'd have the following ground truth region labeling with the extra non-bounding loop in red. On the other hand, this is the answer given by our method which decides to actually keep the red loop because it's shorter and instead ignore a different loop. So there are cases that are just fundamentally ambiguous because there are multiple correct answers and we just decide to pick the one that results in the shortest set of non-bounding loops.

[00:35:41]As usual, for more results and discussion about the methods discussed in this talk, check out my website and other presentation materials. To wrap up my talk, first I hope I've convinced you of the need for robust geometry processing. One theme that has appeared throughout my work is that functions can often be nicer than working directly with defective curves and surfaces because they offer a richer computational space and are tolerant of defects. A second theme is that higher order information can be valuable, but naively could be expensive to integrate.

[00:36:12]We saw this in the sign heat method where diffusing gradients works better than diffusing scalar data, but it also required an extra integration step. In the points to method, we effectively estimate curvature using a learned kernel. And this of course comes with other computational trade-offs, but leads to higher quality results than naive formulas. And finally, a theme that may be obvious to some people working in this field, but I think is maybe worth pointing out a little bit more is that diffusion is really powerful. In all of the methods I showed you, diffusion played an important theoretical or computational component.

[00:36:45]For example, for interpolating initial data, for connections to parallel transports to connections to geodisic distance and closest point maps, and also basically all kernel methods, whether they be found in geometric computing, machine learning or PTE methods, and for connections to topology. Diffusion and geometry have a close relationship. And it's amazing to me that just by monitoring how information is flowing around in space, you can extend, probe, and infer information about that space. And on top of this, diffusion usually also has nice computational properties that give well-behaving algorithms. That being said, simply applying diffusion naively is also not a guarantee for success. For example, we saw the limitations of naive convolutional distances and I had also run into challenges using standard manifold learning techniques on the way to developing the points as to method.

[00:37:36]At the time of this recording, I still have yet to publish the software tools for this latest algorithm. But something I'm proud of is that people are already using my earlier tools. For the sign heat method in particular, I released a C++ library as well as a Python package that you can just pip install, standalone demos, documentation on the web where you can easily toggle between C++ and Python, and integration into some of the best geometry processing libraries. And of course, everything is crossplatform and open source. Sometimes open source can be tricky with some of the fancier solvers, but in those cases, I found an integrated open- source alternatives. Obviously, this took some extra work, but people have been able to use our methods in their own work. And I think a big part of why they chose to use our method was because it was available.

[00:38:24]Now, I'd like to highlight some limitations and still unanswered questions about the methods I showed today. One question is whether we can develop a multi-sign or nary distance function because all sign distance fields including ours can only give binary region classifications corresponding to the inside or outside of a shape. So all sign distance methods fail to give ner region classifications.

[00:38:48]For example, here's what happens when you run the sign heat method on this figure 8. It tries and fails to represent this three region segmentation and doing the optional peacewise integration that I briefly discussed produces unintuitive cuts. It decides to jump kind of far away from the true zero level sets. For what it's worth, here's what a preliminary 2D version of the point tory method does, which at least interpolates the zero set better because it's based on local patches of the point cloud rather than solving a global problem. for this particular problem.

[00:39:20]There are some workarounds used in the level set literature where typically one tracks an SDF for every type of interface present in the problem. Now, winding numbers could be an elegant way to capture arbitrary region classifications, but it's not straightforward how to best design an N area distance function. Now, on the one hand, acquired data like point clouds almost always don't represent nested regions or surfaces with inward- facing normals like this. But these types of shapes do show up a lot in modeling data. And so this problem could be interesting to think about. Second, as is always the case with methods that deal with illpost problems, we can't guarantee that we return exactly the true answer if the data is ambiguous. On the one hand, each of the methods I talked about approach the right solution as your data improves. But when the data is not perfect, we fundamentally can't know the true solution. There is some work in geometry processing trying to quantify how wrong an algorithm might be usually by assuming a model for the source of error or by simply taking fitting error as uncertainty. What makes some of this type of statistical analysis difficult to extend to our work is that the formulas we end up using are nonlinear. But it's certainly possible to measure things like integration error in the sun heat method or how far points end up being from the fitted tory in the points as to method or maybe measuring the sensitivity of the method to perturbations in the input and so on.

[00:40:44]Finally, the points to method I showed before is not yet truly instance since there is a non-negligible premputation cost for each new point cloud. So it would be nice to speed this up. For example, I know that people are coming up with faster and faster implementations of attention because it's so widely used in neural networks these days. But it's also not clear that I even tried the best architecture or chose the right input features or normalized them the best way or embedded them in the best way. I really think there might be a lot of improvements still on the table given I didn't extensively engineer the network. I think it's also perhaps possible to develop the Taurus based SDF parameterization more as a data structure. For example, to simplify geometry or achieve a more compressed representation.

[00:41:30]Speaking of representations, during my PhD, I focused a lot on robust geometric inference. But it's interesting to think whether the quantities or representations I've explored also have benefits for geometric optimization.

[00:41:44]For example, one opinion these days is that neural fields aka neural implicits are sort of the ultimate geometric representation for geometric data processing. The insights I give in my PhD, for example, formulating the PTE and boundary conditions describing geometric quantities are precisely the variational characterization needed to train neural field representations.

[00:42:07]But also, just making a field neural also doesn't solve everything in practice. Neural fields often do have drawbacks that you need to be careful of. For example, one limitation is that naively they can be impractically slow because at every iteration you have to refit some deep neural network and auto diffing through that is not cheap. They can also inherit a lot of the classic limitations of implicit oran representations while introducing additional complexities from the neural network. I don't have an easy answer to all of these questions, but maybe this points to extending our point-based SDF in the context of inverse problems where there's really been a huge push recently to make meaningful progress.

[00:42:47]There also seems to be no consensus yet on the right way to represent geometry for datadriven tasks. For example, people have explored all sorts of representations for generating geometry, but there seems to be no clear winner yet. In my opinion, a lot of the challenges in 3D learning are very classic. For example, there's this classic tension between explicit and implicit representations in their representation power versus optimization ability versus their memory requirements and so on. And as someone who works in geometry processing, these basic questions interest me. As another example, a lot of methods, including mine, are probably going to struggle with ultra fine geometric detail, either computationally or in terms of memory.

[00:43:29]Something that has been inspiring to me lately are encodings that are combinatorial or integer based like normal coordinates or nef polyhedra. I feel like these types of representations are still underexplored and maybe they can address some of the perennial shortcomings of the other representations in certain applications.

[00:43:48]Anyway, that's the end of my talk and thank you for listening.