1 Introduction

Elasticity simulation can be used to animate the clothes that CGI characters wear or calculate how much weight structures will hold before they collapse [2] [1]. In general it lets us model how objects deform when forces are applied to them. The numerical methods used to do this require the object we’re simulating to be discretized into finite pieces. The technique by which we discretize the object gives rise to two classes of numerical methods. One class, called Finite Element Methods, uses a polygon mesh discretization (Figure 1a), but mesh generation requires a lot of user tuning and can fail if the object has complicated geometry. The other class is Meshfree Methods, which uses a point cloud discretization (Figure 1b) rather than a mesh to perform the simulation.

a) A triangle mesh for the finite element method.

b) Two discretizations of an object that can be used for simulation.

Figure 1: Two discretizations of an object that can be used for simulation.

An important distinction between point cloud and polygon mesh representations is the point cloud’s lack of connectivity information. Elasticity requires a notion of connectivity to determine how applying a force to one point affects the points connected to it. Most meshfree methods simply take the set of all points in a certain radius $h$ around a given point to be connected to it (Figure 2). [3]

(a) All points in a radius $h$ are connected.

(b) A case where the radial approach connects across a gap.

Figure 2: The radial approach in meshfree methods

This radial approach is problematic if two points are close to each other in space but have a large geodesic distance. Geodesic distance is the shortest distance between two points when taking paths that stay on the object (Figure 3). An incorrect interpretation of the topology will result in “invisible connections” that incorrectly constrain the movement of the object (Figure 4). The goal of our paper is to enhance the interpretation of the topology using point cloud geodesics. If you think of the point cloud as approximating a 2D shape, then a point cloud geodesic between two points is the geodesic distance between the points lying that 2D shape.

(a) Euclidean distance cuts through space.

(b) Geodesic distance stays on the object.

Figure 3: The Euclidean distance vs. geodesic distance distance between two points on a circle.

Figure 4: Due to an "invisible connection" in (a) the movement of the object is incorrectly constrained in (b). We expect the elastic lower bar to bend downwards.

2 Approach

We combine meshfree methods with point cloud geodesics to more accurately simulate point cloud data. The core of our approach is to use shortest-path graph searches to compute point cloud geodesic distances, then simulating the particles using those geodesic distances rather than standard Euclidean distances.

To compute these point cloud geodesic distances, we represent the point cloud as a weighted graph with edge weights equal to the Euclidean distance between points (Figure 5). By exponentiating the weights we penalize large jumps. With sufficiently large exponent, the shortest-path graph distance approximates the geodesic distance.

Figure 5: A graph defined over a point cloud. Two points are connected by an edge when their Euclidean distance is less than or equal to $h$. Edge weights are not represented in this figure

We define our graph as follows: given points $x_i$ and $x_j$, $(x_i, x_j)$ is an edge if and only if $|x_i - x_j| \leq h$, where $|\cdot|$ is the Euclidean norm. While our methods work if the graph is complete, we only connect points in a small radius to increase efficiency. Denote the edge weights by $w(x_i,x_j)$.

We define a parameter, the $geodesicness$, which represents the extent to which our method avoids large jumps while searching for a geodesic path between points. Let $\gamma \geq 1.0$ denote the geodesicness. Different point clouds may require different values of $\gamma$ since there will be different sized jumps in the data. This parameter is tuned by the user.

Our geodesic approach uses $w(x_i, x_j) = |x_i - x_j|^\gamma$. As a result, large jumps in the data are expensive for the shortest-path graph search. With a sufficiently large $\gamma$, the path will walk around gaps and take a point cloud geodesic path (Figure 7). It can be seen that letting $\gamma = 1.0$ is equivalent to the traditional approach. The geodesicness required to get an improved simulation result depends on the size of the gaps in the data, the number of points along the geodesic paths, and the distance between each point along the geodesic paths.

(a) Regular grid of particles.

(b) Noisy particle arrangement.

Figure 6: The shortest path with a traditional radial based approach.

(a) Regular grid of particles.

(b) Noisy particle arrangement.

Figure 7: The shortest path with our geodesic approach.

3 Results

We demonstrate our method’s effectiveness by applying it to several point cloud data sets. Our simulations were done using a linear elastic material model, although our method works independently of the material model.

Figure 8 uses a point cloud of two bars connected only on the left. We fix the top bar in place and leave the bottom bar free to deform under gravity. With the traditional radial approach, the bottom bar does not deform, since it is incorrectly connected to the fixed top bar. With our geodesic approach, the bottom bar is free to bend downwards.

(a) An undeformed point cloud.

(b) Traditional radial approach: No visible deformation.

(c) Our geodesic approach: The bar bends downwards as expected. Uses $\gamma = 15$ .

Figure 8: The upper bar is held in place while an elastic lower bar should bend down due to gravity. Colour denotes displacement from original position.

Figure 9 demonstrates our approach in the case of a user interacting with a pair of point cloud pants. We begin by fixing the top of the pants in place and allow the legs to deform freely. Next, a user attempts to pull the right leg to the right. With the traditional radial approach, the legs are incorrectly connected together and both pant legs deform. With our geodesic approach, the legs can move independently of each other as expected.

(a) An undeformed point cloud of a pair of pants.

(b) Traditional radial approach: The legs are stuck together.

(c) Our geodesic approach: The artifical constraint is not present. Uses $\gamma = 15$ .

Figure 9: A user deforms a pair of pants by pulling the black particle to the right. Colour denotes displacement from original position.

Figure 10 demonstrates an application of our approach to character animation. We begin by fixing the head of the octopus in place and allow the arms to deform freely. With the traditional approach, the animator can’t wiggle the arms around as they are stuck together. With our geodesic approach, the arms can move independently, allowing the octopus to wave hello.

(a) An undeformed octopus bandit.

(b) Traditional radial approach: The arms are stuck together.

(c) Our geodesic approach: The arms may move freely. Uses $\gamma = 15$ .

Figure 10: An artist attempts to animate the octopus bandit waving hello

4 Limitations

Unfortunately, the quality of a simulation produced using this method does not gracefully degrade as the geodesicness decreases. If the geodesicness falls below a certain threshold, the close points that are far geodesically will immediately connect and the simulation will behave as in the traditional radial approach.

5 Conlusion

Since point clouds have no connectivity information it’s easy to incorrectly interpret the topology when simulating elasticity. We introduced a method which combines meshfree methods with point cloud geodesics to help interpret the topology in cases where points are close in space but far geodesically. Future work includes generalizing to three dimensions and investigating a gracefully degrading point cloud geodesic distance.

Acknowledgement

I would like to acknowledge David Levin and Alec Jacobson, my supervisors, and Tim Jeruzalski, my mentor, for their support and ideas throughout this project.

References

[1] Ray W. Clough. Original formulation of the finite element method. Finite Elem. Anal. Des., 7(2):89–101, November 1990.

[2] G. Irving, J. Teran, and R. Fedkiw. Invertible finite elements for robust simulation of large deformation. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’04, pages 131–140, Aire-la-Ville, Switzerland, Switzerland, 2004. Eurographics Association.

[3] G.R. Liu and Y.T. Gu. An Introduction to Meshfree Methods and Their Programming. Springer Netherlands, 2005.