Applied Discrete Differential Geometry in Houdini #1: Curvature Flow
Prof. Keenan Crane posted lectures on his Discrete Differential Geometry course on YouTube, and his lecture notes can also be found directly on his course’s website.
Link dumps here:
Applied mathematics in Houdini is a topic I’ve been wanting to learn for a while, and would like to see if any of these experiments would ever have any value in production, or if there is already existing functionality.
Computer graphics is still a black box to me, and I still find it cool how much knowledge is applied into designing any 3D software. And especially how every simple operation in 3D is accessible to the artist, far removed from the theory.
Going into this lecture the term “Discrete Differential Geometry” excited me, but I wasn’t clear on what value it would provide to me as an artist. I still don’t know. I often enjoyed classes on theory, but struggle to make connections to application.
To break down the terminology:
Discrete - Fixed quantities. This is as opposed to infinitely continuous. Directly translating to computer graphics, an example of discrete geometry is polygonal modeling. Any 3D model defined by points with a mesh is discretely defined. The opposite would be a NURBs curve/surface, or anything that is parametrized.
Differential - Relates to infinitesimals. When we calculate the rate at which things change, with respect to space or time, we sample over extremely small partitions to make inferences at a global level.
A lot of the techniques described in this class are broadly applicable as it is a toolbox and language that broadly describes all sorts of applications in any field that requires analysis of discrete data, in which computer graphics is a small piece of this puzzle.
The first lecture described the high level of the course. In general, we are trying to quantify and extract properties from discrete data, which is a large part of working in 3D! And the more properties we can work with and animate with a given system, the more potential for interesting animation and animation tools.
In a perfect world, we would have infinite resolution for everything. We could either define an image or geometry in a scene with an intuitive, perfect equation for a parametrized surface. Or, in the discrete world, we would have an infinite number of points so that we could capture every nook and cranny of a 3D model (with the assumption that realism is the artistic goal).
But! We have to approximate to save time in the discrete world, and not every mathematical model is solvable from an analytic perspective, where the answer is input x parameters to spit out y.
Prof. Crane expressly describes two main distinctions here: The idealized continuous world vs. the approximated discrete world.
Let’s work within the context of a curve. These definitions are my personal definitions in my head and are in no means rigorous:
Continuous: When a curve from beginning to end (without repetition) can be parametrized from t = [0,1).
Discrete: In contrast, a discrete curve is equivalent to the above when it is sampled with n points, where the points are connected by n-1 line segments.
Given our mathematical tools, we can take differentials and apply them to the continuous curve to get several properties of the curve, such as curvature, velocity, tangent/bitangent vectors along any point of the curve.
We can get an equivalent definition in the discrete world, but as described in the lecture, one model sacrifices properties that another model can capture better.
In this section, there is one application related to curves described as curvature flow. In the last section of this series, will always be some attempt of the theory into application.
Curvature flow is an algorithm that aims to reduce the curvature of a given closed curve over time. Given an infinite number of iterations, this will always lead to a circle. This is accomplished by moving each point in the direction of the normal of a curve, attenuated by the magnitude of curvature. You can imagine that areas of high curvature will move at a larger speed than areas of low curvature, and the curve will eventually even out to a circle.
Easily, we can identify the parts that are relevant to implementation - iterable and operates on the previous step leads to using a solver. This breaks down into three easy steps:
1) Calculate normal of each point. Houdini had the polyframe node which was sufficient.
2) Calculate curvature at each point. Houdini’s measure SOP does NOT calculate signed curvature. Sign of curvature is an important feature to this algorithm, it determines whether to point towards or away from the center of mass of the curve.
This was manually calculated via the “turning angle” of the previous and next vector, pointing to and away from the current point respectively. Curvature is then ultimately a calculation of the angle, in radians, of how much the angle changes between these aforementioned vectors.
This calculation caused some headaches, as atan2() has a range of [-PI, PI), units in radians. Negative angles go clockwise on the unit circle, positive counter-clockwise. Theoretically, -PI and PI would then be the same angle, however, PI subtracted from -PI = 2*PI, which resulted in curvature calculations much larger than they should’ve been.
Thus, a key assumption is made with this calculation: When the curve has sufficient definition and is assumed to be a smooth, “nice” curve, the curvature should always be less than PI in magnitude. If the curvature calculation’s magnitude is greater than PI, compensate by adding or subtracting PI with respect to the sign of the calculation.
3) Move points on the normal vector, multiplied by the curvature. See how the sign is important?
Here is my node structure:
I had to add a few nodes for quality of life.
Resample was to help maintain even spacing of points between each step. Instead of having the same number of points, it enforced there was a maximum segment length between points. If you resampled with the same number of points, it would introduce artificial curvature, where the curvature begins to alternate to force the same number of points. This would introduce instability in the algorithm.
See how unstable the curve gets at the end.
An attribute wrangle to delete all points if there were only two points left. This occurred when the circle became too small to accommodate at least three points.
Polyframe helped calculate the normals of curve. Later, the curve needed to be flipped to ensure the orientation of the normals point inward.
The final product.
Let’s end off this blog by describing the limitations of my current setup.
1) This only works on a single curve. To allow for multiple curves, you could group by connectivity.
2) Does not enforce curves that are not restricted to the x-z plane. Could project all points to this plane, or could add functionality to project to an arbitrary plane.
A fun future project will to be try and implement mean curvature flow for a closed 3D mesh.
