Finite Elements May Cry

The finite element method (FEM) is an algorithm to solve partial differential equations numerically in an area or volume. The area/volume gets subdivided into a finite number of elements usually simpleces, which in two dimensions are triangles. Then the equation gets solved at the vertices and is interpolated within the finite elements using barycentric coordinates.

Just a few weeks ago a new video game of the Devil May Cry series was released, from which we have used other games as input for algorithms in the past. This time we thought it might be fun to triangulate footage of the new game into finite elements and apply barycentric interpolation. We used delaunays triangulation algorithm, which is implemented in scipy. One of our key questions was, how many simplices/vertices are necessary so that the result of the interpolation would still be playable? Here is what a triangulation with 1000 vertices can look like.

In order to interpolate within the finite elements we use barycentric coordinates. The barycentric coordinates of a point 𝑥∈𝑇 within a simplex is defined as the solution of this system ∑𝑠𝑗=0𝜆𝑗𝑎𝑗=𝑥 and ∑𝑠𝑗=0𝜆𝑗=1. In this case 𝑎𝑗 are the vertices of the simplex and S the number of vertices. We replaced all the pixel values of our frames with the barycentric weighted sum of the vertices values of their simplex. Here are examples of a frame without, with 1000, 10,000 and 100,000 vertices.

To answer our initial question we found that with about 10,000 vertices the result looks like the game could be played. With up to 100,000 vertices the game looks almost normal. One of the interesting effects we found is that for big enough simplices the results flicker a lot. That is because the color of the simplex is defined by just three vertex pixel colors which can change very fast. For small simplices this effect starts to disappear.

As mentioned before we used scipys implementation of the delaunay triangulation. And in order to speed up the multiplication loops we used numbas just-in-time compiler which can be used to decorate regular python for loops.

Here is the result of using 10,000 vertices. We uploaded the other results to our youtube.