Tutorials

Mesh Manipulation Using Mean Values Coordinates in Three.js


In this post we’ll create a simple Free-Form Deformation (FFD) tool in Three.js using Mean Value Coordinates. The idea of FFD is to create a surrounding lattice around a mesh that we would like to modify. Then, by adjusting the control points of the lattice, we can deform our mesh. If you have experience with modeling software such as Maya or 3ds Max, then you are probably familiar with FFD. For those of you aren’t, here is a video showing how the tool I built works.

View demo Download source

We’ll start with a brief introduction on Mean Value Coordinates. Then I’ll explain how we can use them in order to manipulate meshes in a Free Form Deformation way.

Mean Value Coordinates

What are 3D Mean Value Coordinates? In short, given a triangular mesh, 3D Mean Value Coordinates are a way to parametrize a 3D point as a convex combination of the vertices of that mesh. More formally, given a vertex v and a polyhedron with triangular faces and vertices v_1, ..., v_n , the Mean Value Coordinates are the weights \lambda_1,..., \lambda_n such that

  • \sum_{i=1}^{n} \lambda_i = 1
  • \sum_{i=1}^{n} \lambda_i v_i = v

Mean Value Coordinates give us a way to express a 3D point as a weighted average of a set of other points, which we’ll call control points. You can think of Mean Value Coordinates as an extension of Barycentric Coordinates. If you don’t know about Barycentric Coordinates, the idea is very simple: given a triangle with vertices p_1, p_2 and p_3, any point q on the triangle can be expressed as q = \lambda_1 p_1 + \lambda_2 p_2 + \lambda_3 p_3 such that \lambda_1 + \lambda_2 + \lambda_3 = 1 . The Barycentric Coordinates are the values \lambda_1, \lambda_2 and \lambda_3.

triangle

Barycentric Coordinates have many applications in Computer Graphics. Intuitively, if we move any of the triangle’s vertices or if we apply any affine transformation to the triangle, we can use the Barycentric Coordinates of any point on the original triangle to compute their corresponding position on the new triangle.

A natural question is whether we can extend Barycentric Coordinates to work on arbitrary polygons and not just triangles. It turns out that we can. The most popular generalizations of Barycentric Coordinates are Wachpress and Mean Value Coordinates. Wachpress Coordinates only work for convex polygons, while Mean Value Coordinates can also handle non-convex polygons. This paper does a very good job of reviewing them. Now, since we’re actually interested in 3D objects, a natural follow-up question is whether we can further extend either Wachpress or Mean Value Coordinates to work in 3D, with polyhedra instead of polygons. It also turns out that we can. My implementation of 3D Mean Value Coordinates is based on this paper, which gives a very clear explanation of how to extend the Mean Value Coordinates that work in 2D to 3D.

Implementation

Once you’ve understood the 3D Mean Value Coordinates paper, the implementation can be very straightforward. In my case, I’ve used a few tricks, like reusing objects and precomputing the values of Math.Acos, in order to improve performance.

import VertexTrianglesMap from './VertexTrianglesMap';
import CoordinateCalculator from './CoordinateCalculator';

export default class MeanValueCoordinates {
    constructor(geometry) {
        this.geometry = geometry;
        this.trianglesByVertex = new VertexTrianglesMap(this.geometry);
        this.coordinateCalculator = new CoordinateCalculator();
    }

    getCoordinates(vertex) {
        const result = [];
        let sum = 0;

        for (let vertexIndex = 0; vertexIndex < this.trianglesByVertex.length; vertexIndex++) {
            const boundaryVertex = this.geometry.getVertex(vertexIndex);
            const triangles = this.trianglesByVertex.getTriangles(vertexIndex);
            const coordinate = this.coordinateCalculator.getCoordinate(vertex, boundaryVertex, triangles);

            result.push(coordinate);
            sum += coordinate;
        }

        for (let i = 0; i < result.length; i++) {
            result[i] /= sum;
        }

        return result;
    }

    evaluate(coordinates) {
        const result = new THREE.Vector3();
        let total = 0;

        for (let vertexIndex = 0; vertexIndex < coordinates.length; vertexIndex++) {
            const coefficient = coordinates[vertexIndex];

            if (coefficient > 0) {
                const boundaryVertex = this.geometry.getVertex(vertexIndex);

                result.add(boundaryVertex.clone().multiplyScalar(coefficient));
                total += coefficient;
            }
        }

        result.divideScalar(total);

        return result;
    }
}

The input to the MeanValueCoordinates class is a geometry object. In our FFD example, this will be the lattice object that we’ll use to control the mesh that we want to edit.

lattice


Example of lattice controlling a mesh of a dog

The class has two methods:

  • getCoordinates(vertex), which receives a vertex and computes its Mean Value Coordinates, and
  • evaluate(coordinates). This method does the opposite of the method above. It receives an array of Mean Value Coordinates and returns the corresponding vertex position with respect to the geometry.

Free Form Deformation

Once we have an efficient implementation of Mean Value Coordinates, implementing the FFD functionality is also very straightforward. Assume that we have two objects in our scene: a mesh that we wish to deform and a control lattice, which will be the tool that we’ll use to deform the mesh. The first thing we need to do is iterate through the vertices in our mesh, and for each one of them we compute its corresponding Mean Value Coordinates with respect to the lattice. We’ll do this in our Controller class.

 ...
setupLattice() {
        this.mvc = new MeanValueCoordinates(this.lattice);
        this.coordinates = [];

        const latticeBundingBox = this.lattice.getBoundingBox();

        for (let vertexIndex = 0; vertexIndex < this.geometryAdapter.numVertices; vertexIndex++) {
            const v = this.geometryAdapter.getVertex(vertexIndex);
            const vertexCoordinates = latticeBundingBox.containsPoint(v) ?  this.mvc.getCoordinates(v) : null;

            this.coordinates.push(vertexCoordinates);
        }

...
    }

Then, every time the lattice is modified all we need to do is iterate through the vertices in the mesh and compute their new position based on the coordinates that we computed at the beginning and the new positions of the control points in the lattice.

 ...
    updateTargetVertices() {
        for (let vertexIndex = 0; vertexIndex < this.coordinates.length; vertexIndex++) {
            const vertexCoordinates = this.coordinates[vertexIndex];

            if (vertexCoordinates) {
                const position = this.mvc.evaluate(vertexCoordinates);

                this.geometryAdapter.setVertex(vertexIndex, position.x, position.y, position.z);
            }
        }

        this.geometryAdapter.updateVertices();
    }
...

The diagram below shows how all the different components are connected. The user only interacts with the lattice. Any time the geometry of the lattice has changed, the controller will a receive notification, upon which, it will update the geometry of the mesh. Notice that the lattice object doesn’t need to know about the mesh, and vice versa.

flow

Any changes to the geometry of the lattice will update the geometry of the mesh. The last piece of the puzzle is to define how the user will be able to manipulate the lattice.

Lattice Manipulation

In my sample application, I’ve implemented two ways in which the user can manipulate the lattice. The first one is by moving the vertices of the lattice individually. Every time a vertex is moved, the lattice object notifies the controller, which as we saw before, will update the geometry of the mesh.

points

The other way the user can manipulate the lattice is by using the Three.js Transform Control. Every time the control object modifies the lattice, it will also notify the controller.

transform

Conclusions

Computing the Mean Value Coordinates at the beginning can be a bit slow if the target mesh has too many vertices. Let me know if you have ideas on how to make this faster. Other than that, if you need an implementation of Mean Value Coordinates or Free Form Deformation feel free to use this code

Tutorials
Better Testing of Microservices Using Consumer-Driven Contracts in Node.js
Programming Patterns
MVC Pattern For Building Three.js Applications
Programming Patterns
Efficient WebVR Development Using the Adapter Pattern in Three.js