Case Study: Convex Hull

Picture this, ya goober: a huge set of points in space.

3D points in space revolving around a null
Admittedly not the hugest set if points.

You want to find the minimum wrapping shape that contains the entire set of points– the convex hull. The goal is to revolve the entire system of points– and have that wrapping shape update dynamically. Sure, you can try to do it the manual way….

using the pen tool to trace the convex hull
Look how manual.

The problem is, though– not only will the set of points that define the edge change over the course of the revolve, the number of points along the hull is likely to change, too. Those roto keyframing skills you have– keeping keyframes attached to their respective landmarks (so the interpolation is predictable) — they’ll do you no good here… because those landmarks along the silhouette aren’t going to be landmarks for the whole sequence.

I think you know where we’re going with this. An entirely new shape has to be drawn every frame. Get that Pen tool ready and hunker down, friend. I hope your podcast queue has some generous padding.

Ha haha. Kidding. This problem is luckily a simple gift wrapping algorithm. We have the tools we need in expressions to calculate this shape dynamically.

rotating set of 3D points wrapped in a convex hull
It works. It really works.
function indexOfMin(arr) { // find index of point that has the lowest x-position.
    if (arr.length === 0) {
        return -1;
    }
    var min = arr[0][0];
    var minIndex = 0;
    for (var i = 1; i < arr.length; i++) {
        if (arr[i][0] < min) {
            minIndex = i;
            min = arr[i][0];
        }
    }
    return minIndex;
}
// create the necessary things
points = [];
t=[];
hull = [];
pInd = [];
hullInd = 0;
points[0] = fromCompToSurface(thisComp.layer("ant_0200").toComp([0,0,0]));
points[1] = fromCompToSurface(thisComp.layer("ant_0201").toComp([0,0,0]));
points[2] = fromCompToSurface(thisComp.layer("ant_0202").toComp([0,0,0]));
points[3] = fromCompToSurface(thisComp.layer("ant_0203").toComp([0,0,0]));
points[4] = fromCompToSurface(thisComp.layer("ant_0204").toComp([0,0,0]));
points[5] = fromCompToSurface(thisComp.layer("ant_0205").toComp([0,0,0]));
points[6] = fromCompToSurface(thisComp.layer("ant_0206").toComp([0,0,0]));
points[7] = fromCompToSurface(thisComp.layer("ant_0207").toComp([0,0,0]));
points[8] = fromCompToSurface(thisComp.layer("ant_0208").toComp([0,0,0]));
points[9] = fromCompToSurface(thisComp.layer("ant_0209").toComp([0,0,0]));
points[10] = fromCompToSurface(thisComp.layer("ant_0210").toComp([0,0,0]));
points[11] = fromCompToSurface(thisComp.layer("ant_0211").toComp([0,0,0]));
points[12] = fromCompToSurface(thisComp.layer("ant_0212").toComp([0,0,0]));
points[13] = fromCompToSurface(thisComp.layer("ant_0213").toComp([0,0,0]));
points[14] = fromCompToSurface(thisComp.layer("ant_0214").toComp([0,0,0]));
points[15] = fromCompToSurface(thisComp.layer("ant_0215").toComp([0,0,0]));
points[16] = fromCompToSurface(thisComp.layer("ant_0216").toComp([0,0,0]));
points[17] = fromCompToSurface(thisComp.layer("ant_0217").toComp([0,0,0]));
points[18] = fromCompToSurface(thisComp.layer("ant_0218").toComp([0,0,0]));
// simple modulo to make sure our indices stay in-range of the length of the points array
function cInd(_i){ 
  return _i%points.length;
}
// find left-most point
i1 = indexOfMin(points);
// add leftMost to hullArray
addToHull(i1);
// tentative winner
cwInd = cInd(i1+1); 
// loop through every point to find the actual winner
for (var j = 1; j < points.length; j++){
	checkInd = cInd(pInd[hullInd-1]+j); // the contender
	v1 = sub(hull[hullInd-1], points[cwInd]); // vector from the last point on the hull to the tentative winner
	v2 = sub(hull[hullInd-1], points[checkInd]); // vector from the last point on the hull to the contender
	if (cross(v1,v2)[2] < 0){ // if v2 is counter-clockwise to v1, v2 is the new winner
	  cwInd = checkInd;
	}
	// when we reach the end of the loop, add the winner to the hull
	if (j == points.length-1){
		reached = addToHull(cwInd);
		cwInd = cInd(cwInd+1);
		// reset loop until the winning hull point is the left-most point again
		if (!reached){
		j=1; 
		}
	}
}
function addToHull(_pInd) {
    temp = hullInd;
    endReached = false;
    if (pInd[0] == null || pInd[0] !== _pInd) {
        hull[hullInd] = points[_pInd]; // add winning point to hull
        pInd[hullInd] = _pInd; // store index of this point's index 
        t[hullInd] = [0, 0]; // add point tangents
        hullInd++;
    } else {
        endReached = true;
    }
    return endReached;
}
createPath(hull, t, t, true);

This expression assumes two things:

  1. Every point has its anchor point at [0,0,0]… as Null objects do… or as Shape Layers you populate using the “Add” menu in the timeline do.
  2. This expression is on a Path property (either within a Shape Layer or a Mask Path).

The algorithm is fairly simple. I’ll do my best to describe it, but know that I’m a bit of a computer science ding-dong, so you might want to check out some learning materials about Graham scans for more info.

  1. Find the left-most point in our set. This is going to be the first point on our wrapping shape.
  2. We then check every point to find which one has the most “counter-clockwise-est” angle from the first point. (You could also think of this as traveling from the first point to the point that is the greatest left turn.) The winner gets added to the hull.
  3. Finding the subsequent ‘winners’ is a matter of repeating the above step, using the last winner we’ve added to our wrapping shape as our “traveling from” point.
  4. We exit out of the algorithm when the left-most point (the first point we added to our hull) is the winner.

Setup

For any of this stuff to work, we first need to load up an array with all of the locations of every point layer in the comp. To be completely honest with you, this was the most tiring step in the process of working out the expression. You declare an empty array as a variable (points = [];), and then you can manually fill the array, hard-coding the indices of the array with the locations of your point layers. I opted to use a fromCompToSurface via the comp space position (toComp) for each layer, so the placement of the convex hull layer (the Solid or Shape Layer) would be irrelevant…. if I accidentally nudged it out of place.

points[0] = fromCompToSurface(thisComp.layer("ant_0200").toComp([0,0,0]));
points[1] = fromCompToSurface(thisComp.layer("ant_0201").toComp([0,0,0]));
points[2] = fromCompToSurface(thisComp.layer("ant_0202").toComp([0,0,0]));
points[3] = fromCompToSurface(thisComp.layer("ant_0203").toComp([0,0,0]));
points[4] = fromCompToSurface(thisComp.layer("ant_0204").toComp([0,0,0]));
points[5] = fromCompToSurface(thisComp.layer("ant_0205").toComp([0,0,0]));
points[6] = fromCompToSurface(thisComp.layer("ant_0206").toComp([0,0,0]));
points[7] = fromCompToSurface(thisComp.layer("ant_0207").toComp([0,0,0]));
points[8] = fromCompToSurface(thisComp.layer("ant_0208").toComp([0,0,0]));
points[9] = fromCompToSurface(thisComp.layer("ant_0209").toComp([0,0,0]));
points[10] = fromCompToSurface(thisComp.layer("ant_0210").toComp([0,0,0]));
points[11] = fromCompToSurface(thisComp.layer("ant_0211").toComp([0,0,0]));
points[12] = fromCompToSurface(thisComp.layer("ant_0212").toComp([0,0,0]));
points[13] = fromCompToSurface(thisComp.layer("ant_0213").toComp([0,0,0]));
points[14] = fromCompToSurface(thisComp.layer("ant_0214").toComp([0,0,0]));
points[15] = fromCompToSurface(thisComp.layer("ant_0215").toComp([0,0,0]));
points[16] = fromCompToSurface(thisComp.layer("ant_0216").toComp([0,0,0]));
points[17] = fromCompToSurface(thisComp.layer("ant_0217").toComp([0,0,0]));
points[18] = fromCompToSurface(thisComp.layer("ant_0218").toComp([0,0,0]));

And yes– I know what you’re thinking. Can I avoid that manual code and just use a loop to fill the array like how the Create Nulls From Paths window does it? Yes. You absolutely can. I opted for the long-winded way of doing it to save on a bit of calculation/processing time. The algorithm expression is pretty heavy, so anywhere I can save on the number of for loops I need to do– it can’t hurt. And if you have a bit of scripting know-how**, generating that array-fill list can be a pretty fast operation.

My suggestion for creating that array manually (by typing) is making sure your layers have predictable, repeatable names… so you only need to alter a number. In the list above, you can see that my null name suffixes are directly related to their index within the array “ant_0218“, for example, is at index 18 within my array.

The array t (t = [];) is the array where tangent positions get added for use in createPath(). It’s simply populated alongside the hull array with [0,0] positions. (…to make pointy corners.)

The array called hull (hull = [];) is the array that will be populated with the positions of all the vertices of our wrapping shape (the calculated position values of the ‘winners’). It’s the one we use to draw the polygon with createPath(). The array pInd (pInd = [];) gets populated alongside the hull array with the index of the ‘winners’. For example, let’s say the 6th vertex on our wrapping shape (the 6th point added to hull) is points[11]. hull[5] is the 2D position that is calculated (fromCompToSurface via the layer’s [0,0] in composition space). The value in the array pInd at index 5 (pInd[5], in other words) is 11.

points[11] = fromCompToSurface(thisComp.layer("ant_0211").toComp([0,0,0]));

The Processing

Lucky for you, once you have the list for your points array written out, the rest of the expression just works. If you don’t care about how or why the thing works, that’s fine. Thanks for reading. I’m gonna do my best to break down the expression piece by piece so you can get an idea of why things are written the way they are.

The left-most layer

This function is the way to find our left-most layer. It’s a modified version of this “find index of greatest value” JavaScript function:

function indexOfMin(arr) { // find index of point that has the lowest x-position.
    if (arr.length === 0) {
        return -1;
    }
    var min = arr[0][0];
    var minIndex = 0;
    for (var i = 1; i < arr.length; i++) {
        if (arr[i][0] < min) {
            minIndex = i;
            min = arr[i][0];
        }
    }
    return minIndex;
}

The reason we need to find the index, as opposed to just finding the value of the left-most x-position (like Math.min() would give us), is that we need the position array– the x and y to do our calculations in the algorithm– not just the x-value.

Keeping track of indices

The next thing I’d like to look at is this weird little function:

function cInd(_i){ 
  return _i%points.length;
}

I knew the looping on this algorithm was going to be messy if I didn’t manage the starts and ends of my loops in a smart, predictable way. I wanted to make sure I was excluding the vertex added last to the hull array by default, without having to write a conditional statement in the winner-search loop. The loop to find the next winner would start with the layer at the next index of my ‘points’ array from the current “traveling from” layer (the winner that just got added to the hull). So, if points[5] was just added to the hull array, the search for the next winner would start at points[6]. The modulo operator (% – the remainder) in that cInd function is the way to handle the case where points[18] (in this example) would roll back over to points[0].

The variables cwInd and checkInd are the ways of keeping track of the ‘current winner’ and the ‘contender’, respectively. They duke it out to see who’s the most counter-clockwise-est.

Who’s the most counter-clockwise-est?

This block of code is the math that makes it all happen:

v1 = sub(hull[hullInd-1], points[cwInd]); // vector from the last point on the hull to the tentative winner
v2 = sub(hull[hullInd-1], points[checkInd]); // vector from the last point on the hull to the contender
if (cross(v1,v2)[2] < 0){ // if v2 is counter-clockwise to v1, v2 is the new winner
  cwInd = checkInd;
  }

In short, we use the cross product (the ‘z’ value of the cross product, specifically) of 2 vectors:

  1. The vector defined by looking from the last point that got added to the hull array to the current, tentative winner.
  2. The vector defined by looking from the last point that got added to the hull array to the contender.

Think about a pair of 2D vectors sticking out of a common point on a screen (let’s call them a and b). The cross product, basically, (apologies to actual smart trigonometry/vector math people for this explanation)…. is a vector that points either into the screen (away from you) or out of the screen (toward you), depending on whether a is clockwise in relation to b or vice versa. I would highly recommend seeking better reference materials to learn about the cross product… because I’m a bit of a vector math dingus.

Thankfully, to find our winner, we don’t need to know the exact value of the cross product, we just need to know if it’s negative or positive (whether it points at you or away from you). (Please forgive me, vector math experts. I get confused about which direction– positive or negative z-position– is the result of clockwise vs. counter clockwise.)

Add. Add. Add.

The addToHull function is fairly simple in the grand scheme of what’s going on in this expression.

function addToHull(_pInd) {
    temp = hullInd;
    endReached = false;
    if (pInd[0] == null || pInd[0] !== _pInd) {
        hull[hullInd] = points[_pInd]; // add winning point to hull
        pInd[hullInd] = _pInd; // store index of this point's index 
        t[hullInd] = [0, 0]; // add point tangents
        hullInd++;
    } else {
        endReached = true;
    }
    return endReached;
}

Basically, I take the index of the current winner, and use it to insert the necessary things into the necessary arrays (the hull array, the pInd array, and the t array). There’s a universal counter (hullInd) to keep track of how many things have been added to the arrays. It’s mainly a way to watch out for when the hull is ‘closed’: when the left-most layer shows up as the winner after the algorithm has run its course.

Exit. Exit. Please exit.

My first pass at writing this expression was rough. The nature of the looping/finding the vertices on our convex hull– not knowing how many points defined the boundaries (the hull could potentially have a different number of vertices on every frame)– made this expression very easy to go into an infinite loop. And I ran into that problem over and over working through the algorithm.

I’ll be honest– I had to start writing the expression in a text editor because accidentally clicking out of the expression editor in the middle of writing the expression was causing me to infinite loop/error-out/crash.

The end cases– when the end of each winner search loop is reached… and when the hull wraps around to the first-added vertex– they both had to be choreographed carefully so the expression would know when to exit.

if (j == points.length-1){ 
reached = addToHull(cwInd);
cwInd = cInd(cwInd+1);
// reset loop until the winning hull point is the left-most point again
if (!reached){
j=1; 
}

The lines above exist within the winner search loop. In short, they simply wait for the end of the winner search (the current-winner-vs.-contender process). When winner search loop ends, the current winner is added to the hull.

To find the next winner, though… we have to reset the winner search loop back to 1 (we do that using j=1).

In the addToHull function, I’ve written the exit logic for the whole process to be true when the index of the current winner is the index of left-most layer (the first vertex on the hull). Though, the conditional has to allow us to add the left-most layer to the hull at the beginning of the algorithm. That’s what pInd[0] == null does below.

function addToHull(_pInd) {
temp = hullInd;
endReached = false;
if (pInd[0] == null || pInd[0] !== _pInd) {
hull[hullInd] = points[_pInd]; // add winning point to hull
pInd[hullInd] = _pInd; // store index of this point's index 
t[hullInd] = [0, 0]; // add point tangents
hullInd++;
} else {
endReached = true;
}
return endReached;
}

The endReached variable is presumed false. We only switch it to true when the current winner is the left-most layer.

This endReached is vital in stopping the winner search loop from looping forever:

// reset loop until the winning hull point is the left-most point again
if (!reached){
j=1; 
}

Conclusion

This expression was an interesting challenge. Thankfully, I was able to follow a lot of the methodology in the Coding Train walk-through because of the expression language being built on top of JavaScript.

The open-ended nature of the algorithm– not knowing how many vertices make up the convex hull (so not knowing how many loops there would be on any given frame) made the process frustratingly delicate.

There are things I might do differently if I were to start over writing this expression. For instance– there’s likely a way to shorten the points array over time, as layers get added to the hull array. A vertex that gets added to the array (after the left-most point, that is) will never be declared a winner again, so there’s no use in having it part of the ‘current winner’/’contender’ search. It could shorten the processing time a touch– a negligible amount, I’m fairly certain. If the points array is really massive, though… it might save a second of calculation for every frame that the expression needs to run.

** A footnote

I wrote the linked jsx script to help me populate the points list and generate a Shape Layer with the expression applied to a path shape. (It was for a moving infographic with 3D point data that changed over the course of the project. I needed to be able to iterate/update the shapes quickly.)

convex hull auto-populate scripting demo
It’s gonna be that easy.

An update (09-26-2020) – This convex hull expression is a perfect example of an opportunity to save yourself some serious time using After Effects scripting. Check out this post on my AE scripting blog that covers this exact scenario. I feel all After Effects artist should have a basic understanding of how to write scripts, in the same way all Photoshop artists should have a basic understanding of Actions. There are repeatable, predictable workflows that you shouldn’t be wasting your time on… writing a list of 120 variables to simply fill an array with points included.

Published by thatsmadden

I'm an animation artist with an interest in code-driven motion.

One thought on “Case Study: Convex Hull

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: