Geographic data and information, Cloud computing, Machine learning Swept Volumes via Spacetime Numerical Continuation – SIGGRAPH 2021 Technical Paper Presentation
. Let me draw you a picture you’re, a member of the galactic resistance flying near the surface of a planet on a secret mission. When, suddenly, you come under fire As a reflex, you hit the button on your cockpit that reads: quotEVASIVE MANEUVERSquot., The ship’s computer identifies a rock arch nearby, where you may be able to take cover from the fire. In a fraction of a second. The computer must simulate your movement through the arch and answer one key question: will we crash against the rock, or will we clear it if we attempt the maneuver One way of answering this question would be to compute the region of space that is covered by our Spaceship along its trajectory and then check, if it intersects with the rock. In this case there is an intersection, so the computer must immediately discard the maneuver and try something else.. This may be a fairly high stakes example, but even for more mundane things like carving a pumpkin or making a long exposure image of a ballet dancer, there’s one single mathematical computation, we need to make computing the region of space covered by a shape along a trajectory.. We call this the volume of the shape along its trajectory. In what follows: we’ll use the traditional definition of the swept volume where the trajectory is assumed to be rigid, the shape, doesn’t deform it only ever rotates and translates., And by the way, since the 3D volume Is uniquely determined by a bounding surface and a surface is usually much easier to compute and lighter to represent and to store than a volume.
We’Ll talk about computing, the bounding surface of a volume as the same thing as computing, this volume. Okay. So, given a shape and a trajectory, how would we do this today? Well, as it turns out, swept volume? Computation has been studied for many many decades. In particular. There are many works in the 80s and 90s that considered this problem, albeit because of the technology of the time most didn’t consider interactive applications at all, or they didn’t consider sweeps of general surfaces. Instead, they devise very specific algorithms, restricted, for example, to very simple parametric. Shapes., Regardless they’re still where most of our theoretical knowledge about swept volumes comes from today. More recently, there have also been many works about sweeping triangle meshes, and we can place most of these in a spectrum between sacrificing precision by performing certain conversions or approximations versus sacrificing Generality by computing volumes very well, but only for certain inputs or certain trajectories.. This is a tradeoff we wouldn’t like to make. So what we’re going to do from now on in this talk is forget about triangle meshes and instead consider the problem of sweeping implicit, surfaces.. Let’S use this circle as a 2D didactic example.. Now, when we say we’re going to represent it implicitly, we mean, instead of storing it as a set of edges and a set of vertices we’re, going to store the same information, but as a function which is negative inside the circle and positive outside the circle.
. I could query this function anywhere on this 2D plane on this slide. Implicitly, this is describing the same shape as the list of vertices. An example of a very common implicit shape. Representation is a sign distance field, a function that for each point in space returns the distance to the closest point in the shape’s surface, with a positive sign if it’s outside and a negative sign if it’s inside., If it’s easier every time. I talk about implicit surfaces from now on, you can imagine i’m talking about sign distance fields, but in reality all that we’re going to say is going to be much more general than that. So i will call f just a general implicit function, but you can pretend it’s a sign distance field if that’s easier. One thing that’s very easy to do with implicit surfaces, which is very challenging with meshes, is boolean operations.. So, for example, imagine I call the function that defines this disk f1 and i also consider another shape described by another function. F2. Then, the union of f1 and f2 is described by another function, f, which just takes the minimum of f1 and f2.. So that was fairly easy to do. Now. Similarly, the swept volume of a disk is basically a union of an infinite number of shapes, which we can parametrize by some time, parameter t and then the implicit function f, which we want to get which represents the swept volume, will be the minimum of all these Ft.
Well, how do we calculate this minimum Now a usual strategy in computer science, when we are faced with a continuous parameter that we don’t know how to handle is to discretize it so, instead of t changing continuously between 0 and 1, we take a time step, Like 0.1 and consider a discrete minimum, which will give us something like this., We refer to this algorithm as quotStampingquot.. Yes, it’s, clearly better than nothing, but it doesn’t really look very good.. Of course it will become better if we make the discretization finer, but it will take many very, very small steps to make it look like the smooth swept volume. So this doesn’t seem like a particularly smart or a particularly efficient, algorithm. And that’s, partly the sad part of working in swept volumes, while this stamping algorithm isn’t, particularly good the robustness and generality challenges of previous works, makes this the industry standard in some interactive applications like Adobe Medium., So how can we do better than that? Well, if the problem was the discretization let’s, try not discretizing the time, parameter. That’s, fine, the same way, we have a field of discrete optimization. We have a field of continuous, optimization right, So let’s take any point in the plane, like this green point and we’re, going to plot on the left. What this ft function looks like as time passes for the green point just to get a feeling for how hard this would be as a continuous minimization, problem.
It’ll, be something like this it’ll start being positive, because it’s initially outside the shape, it will then be negative. Briefly, because it’s inside the disk and then again end up being very positive as it ends up being very far away.. Now, if this is confusing, you can imagine what I’m moving around is a sign distance field and the graph on the left is just showing the value of the sign distance field. At the green point, as i move the sign distance, field. Let’s try for a different point. This blue point, here. It’ll, look something like this. And yet another point like this red point.. Basically, what we’re seeing is that the function that we want to minimize can vary heavily and have different local minima, depending on the point that we choose to query – and this is happening already for a very simple 2D case – a very convex shape the most convex shape. Maybe and a very simple trajectory.. So if we want to solve this robustly for more complex examples and in 3D, it seems like maybe we’re going to need some global search, optimization where we find all the local minima, and we compare them to make sure that we can find the right global one.. There’S one way we can circumvent this, though Imagine we’re at some point on the boundary of the swept volume like this green point here, and imagine also that I know where the right global minimum happens for this green point, which we’re going to call t star from Here onwards.
, Then, if we move to a new blue point that is close to the green point, the graph of ft at the blue point will be relatively similar to that of the green point and therefore the t star from the green point, which we assume we Already knew can serve as a good starting guess to optimize this function from where we can do gradient descent to find t star for the blue point. Once I’ve done this, I can just as well move to another nearby point like this red point here and repeat: The same process to minimize ft at the red point using gradient descent, starting from t star at the blue point to then find t star at the red point. In the literature. This general type of algorithm, where we slowly trace the boundary of a shape, is called a continuation algorithm.. There is an issue, though, even if i know all the information about this green point and about its minimizer and where t star is, for this green point, it’s impossible for me to know the direction in which the boundary continues, and I would like to just stick To the boundary, because I know computing, the boundary is a good way of representing the whole swept volume and computing values of f that are far from the boundary seems a little bit wasteful right That’s. Why? Instead of starting from a single point whose value of f, we know we’re, going to start from a whole square cell, where we know the values of f at every corner and i’ll use grey to mean negative values of f or inside the swept volume and white For positive values of f or outside the swept volume.
, The vertices of this cell don’t need to fall on the boundary themselves.. As long as there is a sign change, meaning that there are some vertices inside and some vertices outside this cell, then even without knowing anything else about the swept volume, I can be sure that the boundary of the swept volume crosses these edges.. So what i can do is, I can add, the cells that contain these edges and for all the new vertices of these grid cells. I will use my information about the minimization of the points that i already had in my initial cell to compute. F of the new vertices., I can then re identify the edges that intersect, the boundary of the swept volume, add new square cells and so on, and so on. Until i have a sparse grid that contains the boundary of the swept volume completely.. So, to sum up, the algorithm that we’re presenting is a continuation along the boundary of the swept volume with a sparse grid data structure that allows us to compute all the interesting values of f and none of the superfluous ones that are either deep inside the shape Or, very far, from it., We use information from each individual grid cell to query fx the function that implicitly describes the swept volume efficiently at its neighbours.. Of course, this algorithm still requires one initial cell that we can start the continuation from for each boundary component.. In fact, this isn’t very hard to do.
We can look at our shape at any moment in time, for example, at time, zero and look for points in the shape’s boundary whose normal direction is orthogonal to the velocity., Then we take any square that contains this point. Do gradient descent starting on t star, equals zero, and this allows us to start from a fully computed square cell.. We can do this again for many moments in time, like 0.5 using those time values as start guesses in the gradient descent and use these cells. As our starting points for our final algorithm., The output of our algorithm is in the form of this sparse grid, with values of f at each grid corner. But of course, we could use any grid to surface algorithm like in 3D, marching cubes or, in our case, dual contouring, to obtain an explicit representation of the boundary of the final swap volume., Like i just hinted at our algorithm won’t just work for a very simple 2D convex example, in fact, everything we described works just as well in 3d and we can obtain swept volumes of general 3d shapes on general trajectories like this one.. So the obvious next question is how good is the algorithm that we just described? Well, there are several metrics by which we can measure its success. For example, like i said a few minutes ago, there exist some algorithms in the related work that compute swept volumes very well at the cost of restricting themselves to a specific set of meshes or a specific set of trajectories.
. We can perfectly replicate the flagship results of these types of works while at the same time imposing no restriction on the input, complexity or trajectory so beating them in generality.. The only algorithm that’s similar to ours in generality is the stamping algorithm that we saw before so. Another measure of success is how do we compare to stamping Well in this representative example, we see the stamping can be catastrophic, creating topological noise and not being able to replicate the zones of this volume that are swept by very thin components., Even attempting to improve on The stamping, by adding a mixture of continuous and discrete minimization, that we show in the paper doesn’t work. Our algorithm, however, perfectly recovers the swept volume while at the same time, being significantly faster.. Finally, there’s one really nice feature of our algorithm. I haven’t even told you about yet, if you think about it, the only part of our algorithm that involves computing f is this step here and in everything we’ve said today, we haven’t really set any restrictive conditions of what f must be like.. We consider this function. F, which we saw determined the swept volume, but the same way we considered this. We could have considered many CSG operations like this. The minimum of two swept volumes which would amount to their union or the maximum which would amount to their intersection., Or we could have had the subtraction of an existing implicit shape with a swept volume.
. We can plug any of these functions into our algorithm, which means that our algorithm will be output, sensitive and only trace the boundary of the output of whatever CSG operation. We eventually wish to compute. So like we saw, if f just describes a swept volume, then our algorithm traces, the boundary components of the swept volume.. But what? If what we want to compute is the subtraction of this blue rectangle minus the swept volume Then there’s. Obviously, no need to compute the whole swept volume if we’re just going to use it to subtract it from this blue rectangle. Tracing. The f that describes this CSG operation directly means that our algorithm is output, sensitive and doesn’t need to compute the whole swept volume.. For example, say we want to compute the subtraction of this mountain minus the path of an object going through it.. Since we can incorporate the CSG operation into our algorithm, we can concentrate the queries near the regions that actually matter to obtain the CSG output, making our algorithm output sensitive in runtime., Or we can calculate whether a path and a rock intersect without needing to compute the Sweep of the whole trajectory. Alright, so these are some of the nice and unique features of our algorithm and the one I really want to hone into is its generality.. Our algorithm can work on any rigid trajectory and any input which accepts an implicit representation. So to end this talk, i want to guide you through some results that exemplify just this.
. For example, we can find the distances from any point in space to a 2D polygonal curve like this one, which means that we can use our algorithm to compute the swept volume of a 2D curve.. There are also shapes that have analytic implicit representations, for example a torus.. We can transition between an L2 torus one whose cross section is a disk and an L1 torus one whose cross section is a square to obtain a ceramic vase.. Recently, implicit shapes have also been fashionable because they are used as representations in many machine learning applications. For example. Here we use a neural network representation of this chair, as obtained by Davies et al., as an input shape for an algorithm and obtain its swept volume.. Of course, the most common shape representation, whatever the machine learning people want to say, is still going to be a triangle mesh, and since we can compute signed distances from triangle, meshes to any point in space, we can similarly recover their swept volume.. A union of triangle matches can also be swept, even if they have independent trajectories like in this example. Thanks to the integration of CSG operations into our algorithm., Our algorithm is so general. We can even do things that don’t have a clear definition. Like sweeping a point cloud, thanks to the generalized winding number by Barill et al., which allows for signing point cloud distances., So we can move the point cloud around and obtain its swept volume whatever that means.
. This generality means that our algorithm can be used for any of the traditional swept volume applications like 3D modelling. As in the pumpkin example, I teased earlier for path planning not only for resistance spaceships, but for the mundane autonomous cars where a parking maneuver can be pre tested to see if it intersects with any obstacle later on, using its swept volume computed with our algorithm., We Can use it for artistic applications too, for example, this pendulum’s swept volume as it swings can be computed to get something like this. Then we can deduct this white shape from the pink cylinder to obtain a satisfying animation like this one.. Our algorithm can also be used to do social commentary about the effects of capitalism and even to check if we’re, dreaming or not, by spinning a spintop and computing. Its swept volume. I’d, like to end by thanking all our academic and industrial sponsors as well.