Simplify ConvexPolyhedron creation

[pmndrs]

Simplify ConvexPolyhedron creation

[Dannie226]

Apparently it doesn't support .js files, so I had to zip it, but here it is. As I said above, I am mainly a JS developer because I cant download the tools for TS, so that is what the file is written in, so I hope that isn't too much of an inconvenience. But, I have used this multiple times, and it works, and there is also a convenience static method in it for automatically creating the hull, and returning the faces. Cheers.
QuickHull.zip

Edit:
Formatting for the functions. The first parameter in all of the vector math functions are a target parameter (except for the ones that don't actually change a vector), and then the other parameters are for whatever math is wanting to be done. And it always returns the target vector.

[rogerscg]

I've been trying to work on something like this for some time. Even when using ConvexGeometry from Three.js, I get errors along the lines of <vector> looks like it points into the shape? The vertices follow. Make sure they are ordered CCW around the normal, using the right hand rule.

This in an incredibly frustrating part of the library. Would love to see some development here.

[Dannie226]

Because of the way that the built-in convex polyhedron works, there is no way to get what you are asking for. A convex polyhedron will always push a body away from its center, so, if you have a body on the inside of a convex polyhedron, the body will be pushed outside of it.

[Dannie226]

@marcofugaro, it's been a while since a message on this issue, but I created a pull request for integration of a convex hull from a set of points. The pull request can be found here, and I would very much like to see some progress in this area. Even if it isn't this exact thing, I would still like some progress.

[Dannie226]

@Glavin001, one thing to note though. For ease of use purposes, the code that I wrote can take in a 2D array of numbers, or an array of 3D vectors (just objects with an x, y, and z component). The code to convert to the THREE.Vector3 array is not necessary, and the vectors just get converted back to a 2D array of numbers. I am assuming that shapePoints is a 2D array of numbers? If so, just pass shape points into the function for creating the hull, and the rest is done for you.

[outercloudstudio]

I'm experiencing this exact problem too. Anybody have an idea of a fix?

[stockhuman]

Hi there, could you post this example as a codesandbox? And if you know how to get this information, the length of your index arrays in each shape?

[Dannie226]

Edit: I forgot to say that I merged the vertices as user "Dannie226" said, and it didn't change the problem, so I'm assuming that the fact that I'm using cannon-es is the whole reason it didn't solved it.

Out of curiosity, did you also try deleting the uv coordinates? Because after a small amount of experimentation, if you don't delete the uv mapping on the tetrahedron geometry, none of the vertices get merged. So, if you have your heart set on having the uv mapping there, I think you can clone the geometry, delete all the attributes but the position, merge the vertices, and use that for making the shape. That might work, but I haven't tested it. And, the Buffer Geometry Utils was working for you, right? Because Cannon es is a type script engine, so I wasn't sure how well those mesh. I am a primarily javascript developer, because I can't download typescript, at least, not yet anyway, so I am sorely inexperienced in that area. But, try cloning the geometry, and only keeping the position attribute, merging the vertices, and using the new geometry to make the shape rather than the old one. Might be a bit innefficient, but cant really think of any other way to keep the uv mapping.

Edit:
A way of doing this would be

function createFromIndexed(mesh){

  let geometry = new THREE.BufferGeometry();
  geometry.setAttribute('position', mesh.geometry.getAttribute('position'));

  geometry = THREE.BufferGeometryUtils.mergeVertices(geometry); 
  //if using import statement  
  //geometry = BufferGeometryUtils.mergeVertices(geometry);  

  let position = geometry.attributes.position.array;  
  let geomFaces = geometry.index.array;   

  const points = [];  
  const faces = [];  

  for(var i = 0; i < position.length; i += 3){  
    points.push(new CANNON.Vec3(position[i], position[i+1], position[i+2]);  
  }  

  for(var i = 0; i < geomFaces.length; i += 3){  
    faces.push([geomFaces[i], geomFaces[i+1], geomFaces[i+2]);  
  }  

  return new CANNON.ConvexPolyhedron(points,faces);  
}

And that should work. This is written in javascript, so you would have to convert it to typescript, but other than that, it should work, because all vertices in the geometry are merged, so you get a solid convex representation, and you don't lose any data from the original geometry, so, you keep the uv and normals, but should still get convex-convex collision

[marcofugaro]

This is an error that happens while converting a three.js geometry to a ConvexPolyhedron, not an issue with the ConvexPolyhedron itself.
Please provide some sample code of the conversion you're performing, otherwise we can't help you.

Closing this, feel free to reopen it if you provide an example.

[marcofugaro]

Found the repro example in schteppe#459, so I fixed it, here it is working:

https://codesandbox.io/s/old-resonance-xpsn1?file=/src/index.js

The conversion function looks like this:

function getPolyhedronShape(mesh) {
  let geometry = new THREE.BufferGeometry();
  geometry.setAttribute("position", mesh.geometry.getAttribute("position"));

  geometry = mergeVertices(geometry);

  const position = geometry.attributes.position.array;
  const index = geometry.index.array;

  const points = [];
  for (let i = 0; i < position.length; i += 3) {
    points.push(new CANNON.Vec3(position[i], position[i + 1], position[i + 2]));
  }
  const faces = [];
  for (let i = 0; i < index.length; i += 3) {
    faces.push([index[i], index[i + 1], index[i + 2]]);
  }

  return new CANNON.ConvexPolyhedron({ vertices: points, faces });
}

[marcofugaro]

There should be a simpler way to do this.. reopening this issue until I figure it out

[Dannie226]

Why don't you do what Ammo.js does and automatically create the convex hull given a set of points, rather than having the person put in an array of points and faces, and then checking whether that is convex?

[marcofugaro]

Yeah that should be easier, I'll look into the quickhull algorithm

[Dannie226]

if it helps, i do have a file that has everything you need for the quickhull algorithm in it, including a way of getting the convex hull faces from a set of points

[marcofugaro]

Yess, please share what you have, it would be really useful 🙏

[Dannie226]

One way I can think of simplifying the creation would to just add a static property to the convex polyhedron shape. i.e.

//imported the ConvexPolyhedron and QuickHull file that I put above
//points is an array of CANNON.Vec3 so that way we can plug it straight into the CANNON.ConvexPolyhedron
ConvexPolyhedron.createHullFromPoints = function(points){
    const faces = QuickHull.createHull(points);
    return new ConvexPolyhedron({vertices:points, faces});
}

and it should be that simple to make.

Edit:
After some testing, that does seem to work, so, feel free to use the QuickHull code above, and this small function if it makes your job easier

[Glavin001]

Thanks for sharing the QuickHull implementation, @Dannie226! Was a huge help.

I'm working on a way easily convert complex geometries into decomposed convex shapes in browser/Node.js, such that they can collide with other shapes, not just spheres: https://twitter.com/GlavinW/status/1518397865592303618?s=20&t=db0kTGnYxorVMd-_93CqjQ
Works well with Cannon in my testing, except for the error about looks like it points into the shape?.

With the QuickHull implementation above and using OBJExporter workaround I was able to achieve my goal:

1. Convert mesh's geometry to vertices and faces.
2. Process geometry with V-HACD.
3. Convert hulls back into multiple ConvexPolyhedron shapes with vertices and faces.

For those interested below are a couple lessons learned with code.

Convert Mesh's geometry to vertices and faces

Unfortunately, I was unable to get #103 (comment) to work. If I recall correctly, geometry.index.array was not defined.

Looking at OBJExporter.js now the following change might work. Will need to test later.

- geometry.index.array;
+ geometry.getIndex();

As a temporary solution, I created a hacky workaround using OBJExporter since I knew the OBJ format had what I needed:

// object being an instance of https://threejs.org/docs/?q=object3#api/en/core/Object3D
function getVerticesAndFaces(object) {
  return useMemo(() => {
    const exporter = new OBJExporter();
    const contents = exporter.parse(object);

    const rows = contents
      .split("\n")
      .filter(Boolean)
      .map((line) => line.split(" "));
    const vertices = rows
      .filter((row) => row[0] === "v")
      .map((row) => row.slice(1).map(parseFloat));
    const faces = rows
      .filter((row) => row[0] === "f")
      .map((row) => row.slice(1))
      .map((row) => row.map((cell) => parseInt(cell.split("/")[0], 10) - 1));

    return {
      vertices,
      faces,
    };
  }, [object]);
}

Convert hulls (groups of vertices) to ConvexPolyhedrons

This might not be relevant to everyone. I want to show how groups of vertices (in my case convex hulls, Array<Array<Vector3>>) could be converted to ConvexPolyhedrons with QuickHull for passing to use-cannon:

function useHullShapes({ hulls }) {
  const shapes = useMemo(() => {
    if (!hulls) {
      return null;
    }
    return hulls.map((shapePoints) => {
      const vertices = shapePoints.map((p) => new THREE.Vector3().fromArray(p));
      const faces = QuickHull.createHull(vertices);
      return {
        type: "ConvexPolyhedron",
        position: [0, 0, 0],
        rotation: [0, 0, 0],
        args: [shapePoints, faces],
      };
    });
  }, [hulls]);
  return shapes;
}

And now to use-cannon:

  const shapes = useHullShapes({ hulls });

  const [ref] = useCompoundBody(
    () => ({
      // ...
      shapes,
    }),
    undefined,
    [shapes, ...]
  );

I got most of the way there thanks for this thread so wanted to contribute back what I learned. Hope this helps others, too!

[Dannie226]

Glad that my implementation worked and was helpful

[RedstoneWizard08]

I just converted QuickHull to TypeScript.

QuickHull.ts (expand)

export const dot = (a: number[], b: number[]) => {
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
};

export const pointLineDistance = (p: number[], l1: number[], l2: number[]) => {
    //https://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
    const x10 = new Array(3);
    const x21 = new Array(3);
    const c = new Array(3);

    subtract(x10, l1, p);
    subtract(x21, l2, l1);
    cross(c, x21, x10);

    const len = length(c) / length(x21);

    if (isNaN(len)) return 0;

    return len;
};
export const getPlaneNormal = (
    t: number[],
    a: number[],
    b: number[],
    c: number[]
) => {
    const v1 = new Array(3);
    const v2 = new Array(3);
    subtract(v1, b, a);
    subtract(v2, b, c);
    cross(t, v2, v1);
    return t;
};

export const add = (t: number[], v1: number[], v2: number[]) => {
    t[0] = v1[0] + v2[0];
    t[1] = v1[1] + v2[1];
    t[2] = v1[2] + v2[2];
    return t;
};

export const subtract = (t: number[], v1: number[], v2: number[]) => {
    t[0] = v1[0] - v2[0];
    t[1] = v1[1] - v2[1];
    t[2] = v1[2] - v2[2];
    return t;
};

export const cross = (t: number[], v1: number[], v2: number[]) => {
    t[0] = v1[1] * v2[2] - v1[2] * v2[1];
    t[1] = v1[2] * v2[0] - v1[0] * v2[2];
    t[2] = v1[0] * v2[1] - v1[1] * v2[0];
    return t;
};

export const copy = (t: number[], f: number[]) => {
    t[0] = f[0];
    t[1] = f[1];
    t[2] = f[2];
    return t;
};

export const length = (v: number[]) => {
    return Math.sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
};

export const scale = (t: number[], v: number[], l: number) => {
    t[0] = v[0] * l;
    t[1] = v[1] * l;
    t[2] = v[2] * l;
    return t;
};

export const scaleAndAdd = (
    t: number[],
    v1: number[],
    l: number,
    s: number
) => {
    t[0] = v1[0] * l + s;
    t[1] = v1[1] * l + s;
    t[2] = v1[2] * l + s;
    return t;
};

export const normalize = (t: number[], v: number[]) => {
    let len = length(v);
    if (len === 0) {
        t[0] = 0;
        t[1] = 0;
        t[2] = 0;
    } else {
        len = 1 / len;
        t[0] = v[0] * len;
        t[1] = v[1] * len;
        t[2] = v[2] * len;
    }
    return t;
};

export const distance = (v1: number[], v2: number[]) => {
    return Math.sqrt(squaredDistance(v1, v2));
};
export const squaredDistance = (v1: number[], v2: number[]) => {
    return (v1[0] - v2[0]) ** 2 + (v1[1] - v2[1]) ** 2 + (v1[2] - v2[2]) ** 2;
};

export const debug = (...text: any) => {
    if (debug.enabled) console.log(...text);
};

debug.enabled = false;

export class VertexList {
    public head: Vertex | null;
    public tail: Vertex | null;

    constructor() {
        this.head = null;
        this.tail = null;
    }

    clear() {
        this.head = this.tail = null;
    }

    /**
     * Inserts a `node` before `target`, it's assumed that
     * `target` belongs to this doubly linked list
     *
     * @param {*} target
     * @param {*} node
     */
    insertBefore(target: Vertex, node: Vertex) {
        node.prev = target.prev;
        node.next = target;
        if (!node.prev) {
            this.head = node;
        } else {
            node.prev.next = node;
        }
        target.prev = node;
    }

    /**
     * Inserts a `node` after `target`, it's assumed that
     * `target` belongs to this doubly linked list
     *
     * @param {Vertex} target
     * @param {Vertex} node
     */
    insertAfter(target: Vertex, node: Vertex) {
        node.prev = target;
        node.next = target.next;
        if (!node.next) {
            this.tail = node;
        } else {
            node.next.prev = node;
        }
        target.next = node;
    }

    /**
     * Appends a `node` to the end of this doubly linked list
     * Note: `node.next` will be unlinked from `node`
     * Note: if `node` is part of another linked list call `addAll` instead
     *
     * @param {*} node
     */
    add(node: Vertex) {
        if (!this.head) {
            this.head = node;
        } else {
            if (!this.tail) throw new Error("tail is null");
            this.tail.next = node;
        }
        node.prev = this.tail;
        // since node is the new end it doesn't have a next node
        node.next = null;
        this.tail = node;
    }

    /**
     * Appends a chain of nodes where `node` is the head,
     * the difference with `add` is that it correctly sets the position
     * of the node list `tail` property
     *
     * @param {*} node
     */
    addAll(node: Vertex) {
        if (!this.head) {
            this.head = node;
        } else {
            if (!this.tail) throw new Error("tail is null");
            this.tail.next = node;
        }
        node.prev = this.tail;

        // find the end of the list
        while (node.next) {
            node = node.next;
        }
        this.tail = node;
    }

    /**
     * Deletes a `node` from this linked list, it's assumed that `node` is a
     * member of this linked list
     *
     * @param {*} node
     */
    remove(node: Vertex) {
        if (!node.prev) {
            this.head = node.next;
        } else {
            node.prev.next = node.next;
        }

        if (!node.next) {
            this.tail = node.prev;
        } else {
            node.next.prev = node.prev;
        }
    }

    /**
     * Removes a chain of nodes whose head is `a` and whose tail is `b`,
     * it's assumed that `a` and `b` belong to this list and also that `a`
     * comes before `b` in the linked list
     *
     * @param {*} a
     * @param {*} b
     */
    removeChain(a: Vertex, b: Vertex) {
        if (!a.prev) {
            this.head = b.next;
        } else {
            a.prev.next = b.next;
        }

        if (!b.next) {
            this.tail = a.prev;
        } else {
            b.next.prev = a.prev;
        }
    }

    first() {
        return this.head;
    }

    isEmpty() {
        return !this.head;
    }
}

export class Vertex {
    public point: number[];
    public index: number;
    public next: Vertex | null;
    public prev: Vertex | null;
    public face: Face | null;

    constructor(point: number[], index: number) {
        this.point = point;
        // index in the input array
        this.index = index;
        // vertex is a double linked list node
        this.next = null;
        this.prev = null;
        // the face that is able to see this point
        this.face = null;
    }
}

export class HalfEdge {
    public vertex: Vertex;
    public next: HalfEdge | null;
    public prev: HalfEdge | null;
    public face: Face | null;
    public opposite: HalfEdge | null;

    constructor(vertex: Vertex, face: Face) {
        this.vertex = vertex;
        this.face = face;
        this.next = null;
        this.prev = null;
        this.opposite = null;
    }

    head() {
        return this.vertex;
    }

    tail() {
        return this.prev ? this.prev.vertex : null;
    }

    length() {
        if (this.tail()) {
            return distance(this.tail()?.point || [0, 0], this.head().point);
        }
        return -1;
    }

    lengthSquared() {
        if (this.tail()) {
            return squaredDistance(
                this.tail()?.point || [0, 0],
                this.head().point
            );
        }
        return -1;
    }

    setOpposite(edge: HalfEdge) {
        // eslint-disable-next-line @typescript-eslint/no-this-alias
        const me = this;
        if (debug.enabled) {
            debug(
                `opposite ${me.tail()?.index} <--> ${
                    me.head()?.index
                } between ${me.face?.collectIndices()}, ${edge.face?.collectIndices()}`
            );
        }
        this.opposite = edge;
        edge.opposite = this;
    }
}

const VISIBLE = 0;
const NON_CONVEX = 1;
const DELETED = 2;

export class Face {
    public normal: number[];
    public centroid: number[];
    public offset: number;
    public outside: Vertex | null;
    public mark: number;
    public edge: HalfEdge | null;
    public nVertices: number;
    public area = 0;

    constructor() {
        this.normal = [];
        this.centroid = [];
        // signed distance from face to the origin
        this.offset = 0;
        // pointer to the a vertex in a double linked list this face can see
        this.outside = null;
        this.mark = VISIBLE;
        this.edge = null;
        this.nVertices = 0;
    }

    getEdge(i: number) {
        if (typeof i !== "number") {
            throw Error("requires a number");
        }
        let it = this.edge;
        while (i > 0) {
            it = it?.next || it;
            i -= 1;
        }
        while (i < 0) {
            it = it?.prev || it;
            i += 1;
        }
        return it;
    }

    computeNormal() {
        const e0 = this.edge;
        const e1 = e0?.next;
        let e2 = e1?.next;
        const v2 = subtract(
            [],
            e1?.head().point || [0, 0],
            e0?.head().point || [0, 0]
        );
        const t: number[] = [];
        const v1: number[] = [];

        this.nVertices = 2;
        this.normal = [0, 0, 0];
        while (e2 !== e0) {
            copy(v1, v2);
            subtract(
                v2,
                e2?.head().point || [0, 0],
                e0?.head().point || [0, 0]
            );
            add(this.normal, this.normal, cross(t, v1, v2));
            e2 = e2?.next;
            this.nVertices += 1;
        }
        this.area = length(this.normal);
        // normalize the vector, since we've already calculated the area
        // it's cheaper to scale the vector using this quantity instead of
        // doing the same operation again
        this.normal = scale(this.normal, this.normal, 1 / this.area);
    }

    computeNormalMinArea(minArea: number) {
        this.computeNormal();
        if (this.area < minArea) {
            // compute the normal without the longest edge
            let maxEdge;
            let maxSquaredLength = 0;
            let edge = this.edge || null;

            // find the longest edge (in length) in the chain of edges
            do {
                const lengthSquared = edge?.lengthSquared() || 0;
                if (lengthSquared > maxSquaredLength) {
                    maxEdge = edge;
                    maxSquaredLength = lengthSquared;
                }
                edge = edge?.next || null;
            } while (edge !== this.edge);

            const p1 = maxEdge?.tail()?.point;
            const p2 = maxEdge?.head().point;
            const maxVector = subtract([], p2 || [0, 0], p1 || [0, 0]);
            const maxLength = Math.sqrt(maxSquaredLength);
            // maxVector is normalized after this operation
            scale(maxVector, maxVector, 1 / maxLength);
            // compute the projection of maxVector over this face normal
            const maxProjection = dot(this.normal, maxVector);
            // subtract the quantity maxEdge adds on the normal
            scaleAndAdd(
                this.normal,
                this.normal,
                maxVector.length,
                -maxProjection
            );
            // renormalize `this.normal`
            normalize(this.normal, this.normal);
        }
    }

    computeCentroid() {
        this.centroid = [0, 0, 0];
        let edge = this.edge;
        do {
            add(this.centroid, this.centroid, edge?.head().point || [0, 0]);
            edge = edge?.next || null;
        } while (edge !== this.edge);
        scale(this.centroid, this.centroid, 1 / this.nVertices);
    }

    computeNormalAndCentroid(minArea?: number) {
        if (typeof minArea !== "undefined") {
            this.computeNormalMinArea(minArea);
        } else {
            this.computeNormal();
        }
        this.computeCentroid();
        this.offset = dot(this.normal, this.centroid);
    }

    distanceToPlane(point: number[]) {
        return dot(this.normal, point) - this.offset;
    }

    /**
     * @private
     *
     * Connects two edges assuming that prev.head().point === next.tail().point
     *
     * @param {HalfEdge} prev
     * @param {HalfEdge} next
     */
    private connectHalfEdges(prev: HalfEdge, next: HalfEdge) {
        let discardedFace;
        if (prev.opposite?.face === next.opposite?.face) {
            // `prev` is remove a redundant edge
            const oppositeFace = next.opposite?.face || null;
            let oppositeEdge;
            if (prev === this.edge) {
                this.edge = next;
            }
            if (oppositeFace?.nVertices === 3) {
                // case:
                // remove the face on the right
                //
                //       /|\
                //      / | \ the face on the right
                //     /  |  \ --> opposite edge
                //    / a |   \
                //   *----*----*
                //  /     b  |  \
                //           ▾
                //      redundant edge
                //
                // Note: the opposite edge is actually in the face to the right
                // of the face to be destroyed
                oppositeEdge = next.opposite?.prev?.opposite;
                oppositeFace.mark = DELETED;
                discardedFace = oppositeFace;
            } else {
                // case:
                //          t
                //        *----
                //       /| <- right face's redundant edge
                //      / | opposite edge
                //     /  |  ▴   /
                //    / a |  |  /
                //   *----*----*
                //  /     b  |  \
                //           ▾
                //      redundant edge
                oppositeEdge = next.opposite?.next;
                // make sure that the link `oppositeFace.edge` points correctly even
                // after the right face redundant edge is removed
                if (oppositeFace?.edge === oppositeEdge?.prev) {
                    if (!oppositeFace) throw Error("oppositeFace is null!");
                    oppositeFace.edge = oppositeEdge || null;
                }

                //       /|   /
                //      / | t/opposite edge
                //     /  | / ▴  /
                //    / a |/  | /
                //   *----*----*
                //  /     b     \
                if (!oppositeEdge) throw Error("oppositeEdge is null!");
                oppositeEdge.prev = oppositeEdge?.prev?.prev || null;

                if (!oppositeEdge.prev)
                    throw Error("oppositeEdge.prev is null!");
                oppositeEdge.prev.next = oppositeEdge || null;
            }
            //       /|
            //      / |
            //     /  |
            //    / a |
            //   *----*----*
            //  /     b  ▴  \
            //           |
            //     redundant edge
            next.prev = prev.prev;

            if (!next.prev) throw Error("next.prev is null!");
            next.prev.next = next;

            //       / \  \
            //      /   \->\
            //     /     \<-\ opposite edge
            //    / a     \  \
            //   *----*----*
            //  /     b  ^  \
            if (!oppositeEdge) throw Error("oppositeEdge is null!");
            next.setOpposite(oppositeEdge);

            oppositeFace?.computeNormalAndCentroid();
        } else {
            // trivial case
            //        *
            //       /|\
            //      / | \
            //     /  |--> next
            //    / a |   \
            //   *----*----*
            //    \ b |   /
            //     \  |--> prev
            //      \ | /
            //       \|/
            //        *
            prev.next = next;
            next.prev = prev;
        }
        return discardedFace;
    }

    mergeAdjacentFaces(
        adjacentEdge: HalfEdge,
        discardedFaces: (Face | null)[] = []
    ) {
        const oppositeEdge = adjacentEdge.opposite;
        const oppositeFace = oppositeEdge?.face || null;

        discardedFaces.push(oppositeFace || null);

        if (!oppositeFace) throw Error("oppositeFace is null!");
        oppositeFace.mark = DELETED;

        // find the chain of edges whose opposite face is `oppositeFace`
        //
        //                ===>
        //      \         face         /
        //       * ---- * ---- * ---- *
        //      /     opposite face    \
        //                <===
        //
        let adjacentEdgePrev = adjacentEdge.prev;
        let adjacentEdgeNext = adjacentEdge.next;
        let oppositeEdgePrev = oppositeEdge?.prev;
        let oppositeEdgeNext = oppositeEdge?.next;

        // left edge
        while (adjacentEdgePrev?.opposite?.face === oppositeFace) {
            adjacentEdgePrev = adjacentEdgePrev.prev;
            oppositeEdgeNext = oppositeEdgeNext?.next;
        }
        // right edge
        while (adjacentEdgeNext?.opposite?.face === oppositeFace) {
            adjacentEdgeNext = adjacentEdgeNext.next;
            oppositeEdgePrev = oppositeEdgePrev?.prev;
        }
        // adjacentEdgePrev  \         face         / adjacentEdgeNext
        //                    * ---- * ---- * ---- *
        // oppositeEdgeNext  /     opposite face    \ oppositeEdgePrev

        // fix the face reference of all the opposite edges that are not part of
        // the edges whose opposite face is not `face` i.e. all the edges that
        // `face` and `oppositeFace` do not have in common
        let edge;
        for (
            edge = oppositeEdgeNext;
            edge !== oppositeEdgePrev?.next;
            edge = edge?.next
        ) {
            if (!edge) throw Error("edge is null!");
            edge.face = this;
        }

        // make sure that `face.edge` is not one of the edges to be destroyed
        // Note: it's important for it to be a `next` edge since `prev` edges
        // might be destroyed on `connectHalfEdges`
        this.edge = adjacentEdgeNext;

        // connect the extremes
        // Note: it might be possible that after connecting the edges a triangular
        // face might be redundant
        let discardedFace;
        if (!oppositeEdgePrev) throw Error("adjacentEdgePrev is null!");
        if (!adjacentEdgeNext) throw Error("adjacentEdgeNext is null!");
        if (!adjacentEdgePrev) throw Error("adjacentEdgePrev is null!");
        if (!oppositeEdgeNext) throw Error("oppositeEdgeNext is null!");

        discardedFace = this.connectHalfEdges(
            oppositeEdgePrev,
            adjacentEdgeNext
        );
        if (discardedFace) {
            discardedFaces.push(discardedFace);
        }
        discardedFace = this.connectHalfEdges(
            adjacentEdgePrev,
            oppositeEdgeNext
        );
        if (discardedFace) {
            discardedFaces.push(discardedFace);
        }

        this.computeNormalAndCentroid();
        // TODO: additional consistency checks
        return discardedFaces;
    }

    collectIndices() {
        const indices = [];
        let edge = this.edge;
        do {
            indices.push(edge?.head().index);
            edge = edge?.next || null;
        } while (edge !== this.edge);
        return indices;
    }

    static createTriangle(v0: Vertex, v1: Vertex, v2: Vertex, minArea = 0) {
        const face = new Face();
        const e0 = new HalfEdge(v0, face);
        const e1 = new HalfEdge(v1, face);
        const e2 = new HalfEdge(v2, face);

        // join edges
        e0.next = e2.prev = e1;
        e1.next = e0.prev = e2;
        e2.next = e1.prev = e0;

        // main half edge reference
        face.edge = e0;
        face.computeNormalAndCentroid(minArea);
        if (debug.enabled) {
            debug("face created %j", face?.collectIndices());
        }
        return face;
    }
}

const MERGE_NON_CONVEX_WRT_LARGER_FACE = 1;
const MERGE_NON_CONVEX = 2;
export class QuickHull {
    public tolerance: number;
    public nFaces: number;
    public nPoints: number;
    public faces: Face[];
    public newFaces: Face[];
    public claimed: VertexList;
    public unclaimed: VertexList;
    public vertices: Vertex[];
    public discardedFaces: Face[];
    public vertexPointIndices: number[];

    constructor(points: number[][]) {
        if (!Array.isArray(points)) {
            throw TypeError("input is not a valid array");
        }
        if (points.length < 4) {
            throw Error("cannot build a simplex out of <4 points");
        }

        this.tolerance = -1;

        // buffers
        this.nFaces = 0;
        this.nPoints = points.length;

        this.faces = [];
        this.newFaces = [];
        // helpers
        //
        // let `a`, `b` be `Face` instances
        // let `v` be points wrapped as instance of `Vertex`
        //
        //     [v, v, ..., v, v, v, ...]
        //      ^             ^
        //      |             |
        //  a.outside     b.outside
        //
        this.claimed = new VertexList();
        this.unclaimed = new VertexList();

        // vertices of the hull(internal representation of points)
        this.vertices = [];
        for (let i = 0; i < points.length; i += 1) {
            this.vertices.push(new Vertex(points[i], i));
        }
        this.discardedFaces = [];
        this.vertexPointIndices = [];
    }

    addVertexToFace(vertex: Vertex, face: Face) {
        vertex.face = face;
        if (!face.outside) {
            this.claimed.add(vertex);
        } else {
            this.claimed.insertBefore(face.outside, vertex);
        }
        face.outside = vertex;
    }

    /**
     * Removes `vertex` for the `claimed` list of vertices, it also makes sure
     * that the link from `face` to the first vertex it sees in `claimed` is
     * linked correctly after the removal
     *
     * @param {Vertex} vertex
     * @param {Face} face
     */
    removeVertexFromFace(vertex: Vertex, face: Face) {
        if (vertex === face.outside) {
            // fix face.outside link
            if (vertex.next && vertex.next.face === face) {
                // face has at least 2 outside vertices, move the `outside` reference
                face.outside = vertex.next;
            } else {
                // vertex was the only outside vertex that face had
                face.outside = null;
            }
        }
        this.claimed.remove(vertex);
    }

    /**
     * Removes all the visible vertices that `face` is able to see which are
     * stored in the `claimed` vertext list
     *
     * @param {Face} face
     * @return {Vertex|undefined} If face had visible vertices returns
     * `face.outside`, otherwise undefined
     */
    removeAllVerticesFromFace(face: Face) {
        if (face.outside) {
            // pointer to the last vertex of this face
            // [..., outside, ..., end, outside, ...]
            //          |           |      |
            //          a           a      b
            let end = face.outside;
            while (end.next && end.next.face === face) {
                end = end.next;
            }
            this.claimed.removeChain(face.outside, end);
            //                            b
            //                       [ outside, ...]
            //                            |  removes this link
            //     [ outside, ..., end ] -┘
            //          |           |
            //          a           a
            end.next = null;
            return face.outside;
        }
    }

    /**
     * Removes all the visible vertices that `face` is able to see, additionally
     * checking the following:
     *
     * If `absorbingFace` doesn't exist then all the removed vertices will be
     * added to the `unclaimed` vertex list
     *
     * If `absorbingFace` exists then this method will assign all the vertices of
     * `face` that can see `absorbingFace`, if a vertex cannot see `absorbingFace`
     * it's added to the `unclaimed` vertex list
     *
     * @param {Face} face
     * @param {Face} [absorbingFace]
     */
    deleteFaceVertices(face: Face, absorbingFace: Face) {
        const faceVertices = this.removeAllVerticesFromFace(face);
        if (faceVertices) {
            if (!absorbingFace) {
                // mark the vertices to be reassigned to some other face
                this.unclaimed.addAll(faceVertices);
            } else {
                // if there's an absorbing face try to assign as many vertices
                // as possible to it

                // the reference `vertex.next` might be destroyed on
                // `this.addVertexToFace` (see VertexList#add), nextVertex is a
                // reference to it
                let nextVertex;
                for (
                    let vertex: Vertex | null = faceVertices;
                    vertex;
                    vertex = nextVertex
                ) {
                    nextVertex = vertex.next;
                    const distance = absorbingFace.distanceToPlane(
                        vertex.point
                    );

                    // check if `vertex` is able to see `absorbingFace`
                    if (distance > this.tolerance) {
                        this.addVertexToFace(vertex, absorbingFace);
                    } else {
                        this.unclaimed.add(vertex);
                    }
                }
            }
        }
    }

    /**
     * Reassigns as many vertices as possible from the unclaimed list to the new
     * faces
     *
     * @param {Faces[]} newFaces
     */
    resolveUnclaimedPoints(newFaces: Face[]) {
        // cache next vertex so that if `vertex.next` is destroyed it's still
        // recoverable
        let vertexNext = this.unclaimed.first();
        for (let vertex = vertexNext; vertex; vertex = vertexNext) {
            vertexNext = vertex.next;
            let maxDistance = this.tolerance;
            let maxFace;
            for (let i = 0; i < newFaces.length; i += 1) {
                const face = newFaces[i];
                if (face.mark === VISIBLE) {
                    const dist = face.distanceToPlane(vertex.point);
                    if (dist > maxDistance) {
                        maxDistance = dist;
                        maxFace = face;
                    }
                    if (maxDistance > 1000 * this.tolerance) {
                        break;
                    }
                }
            }

            if (maxFace) {
                this.addVertexToFace(vertex, maxFace);
            }
        }
    }

    /**
     * Computes the extremes of a tetrahedron which will be the initial hull
     *
     * @return {number[]} The min/max vertices in the x,y,z directions
     */
    computeExtremes() {
        // eslint-disable-next-line @typescript-eslint/no-this-alias
        const me = this;
        const min = [];
        const max = [];

        // min vertex on the x,y,z directions
        const minVertices = [];
        // max vertex on the x,y,z directions
        const maxVertices = [];

        let i, j;

        // initially assume that the first vertex is the min/max
        for (i = 0; i < 3; i += 1) {
            minVertices[i] = maxVertices[i] = this.vertices[0];
        }
        // copy the coordinates of the first vertex to min/max
        for (i = 0; i < 3; i += 1) {
            min[i] = max[i] = this.vertices[0].point[i];
        }

        // compute the min/max vertex on all 6 directions
        for (i = 0; i < this.vertices.length; i += 1) {
            const vertex = this.vertices[i];
            const point = vertex.point;
            // update the min coordinates
            for (j = 0; j < 3; j += 1) {
                if (point[j] < min[j]) {
                    min[j] = point[j];
                    minVertices[j] = vertex;
                }
            }
            // update the max coordinates
            for (j = 0; j < 3; j += 1) {
                if (point[j] > max[j]) {
                    max[j] = point[j];
                    maxVertices[j] = vertex;
                }
            }
        }

        // compute epsilon
        this.tolerance =
            3 *
            Number.EPSILON *
            (Math.max(Math.abs(min[0]), Math.abs(max[0])) +
                Math.max(Math.abs(min[1]), Math.abs(max[1])) +
                Math.max(Math.abs(min[2]), Math.abs(max[2])));
        if (debug.enabled) {
            debug("tolerance %d", me.tolerance);
        }
        return [minVertices, maxVertices];
    }

    /**
     * Compues the initial tetrahedron assigning to its faces all the points that
     * are candidates to form part of the hull
     */
    createInitialSimplex() {
        const vertices = this.vertices;
        const [min, max] = this.computeExtremes();
        let v0, v1, v2, v3;
        let i, j;

        // Find the two vertices with the greatest 1d separation
        // (max.x - min.x)
        // (max.y - min.y)
        // (max.z - min.z)
        let maxDistance = 0;
        let indexMax = 0;
        for (i = 0; i < 3; i += 1) {
            const distance = max[i].point[i] - min[i].point[i];
            if (distance > maxDistance) {
                maxDistance = distance;
                indexMax = i;
            }
        }
        // eslint-disable-next-line prefer-const
        v0 = min[indexMax];
        // eslint-disable-next-line prefer-const
        v1 = max[indexMax];

        // the next vertex is the one farthest to the line formed by `v0` and `v1`
        maxDistance = 0;
        for (i = 0; i < this.vertices.length; i += 1) {
            const vertex = this.vertices[i];
            if (vertex !== v0 && vertex !== v1) {
                const distance = pointLineDistance(
                    vertex.point,
                    v0.point,
                    v1.point
                );
                if (distance > maxDistance) {
                    maxDistance = distance;
                    v2 = vertex;
                }
            }
        }

        // the next vertes is the one farthest to the plane `v0`, `v1`, `v2`
        // normalize((v2 - v1) x (v0 - v1))
        const normal = getPlaneNormal([], v0.point, v1.point, v2?.point || []);
        // distance from the origin to the plane
        const distPO = dot(v0.point, normal);
        maxDistance = -1;
        for (i = 0; i < this.vertices.length; i += 1) {
            const vertex = this.vertices[i];
            if (vertex !== v0 && vertex !== v1 && vertex !== v2) {
                const distance = Math.abs(dot(normal, vertex.point) - distPO);
                if (distance > maxDistance) {
                    maxDistance = distance;
                    v3 = vertex;
                }
            }
        }

        // initial simplex
        // Taken from http://everything2.com/title/How+to+paint+a+tetrahedron
        //
        //                              v2
        //                             ,|,
        //                           ,7``\'VA,
        //                         ,7`   |, `'VA,
        //                       ,7`     `\    `'VA,
        //                     ,7`        |,      `'VA,
        //                   ,7`          `\         `'VA,
        //                 ,7`             |,           `'VA,
        //               ,7`               `\       ,..ooOOTK` v3
        //             ,7`                  |,.ooOOT''`    AV
        //           ,7`            ,..ooOOT`\`           /7
        //         ,7`      ,..ooOOT''`      |,          AV
        //        ,T,..ooOOT''`              `\         /7
        //     v0 `'TTs.,                     |,       AV
        //            `'TTs.,                 `\      /7
        //                 `'TTs.,             |,    AV
        //                      `'TTs.,        `\   /7
        //                           `'TTs.,    |, AV
        //                                `'TTs.,\/7
        //                                     `'T`
        //                                       v1
        //
        const faces = [];
        if (dot(v3?.point || [], normal) - distPO < 0) {
            // the face is not able to see the point so `planeNormal`
            // is pointing outside the tetrahedron
            if (!v3) throw new Error("v3 is not defined");
            if (!v2) throw new Error("v2 is not defined");
            if (!v1) throw new Error("v1 is not defined");
            faces.push(
                Face.createTriangle(v0, v1, v2),
                Face.createTriangle(v3, v1, v0),
                Face.createTriangle(v3, v2, v1),
                Face.createTriangle(v3, v0, v2)
            );

            // set the opposite edge
            for (i = 0; i < 3; i += 1) {
                const j = (i + 1) % 3;
                // join face[i] i > 0, with the first face
                if (!faces[0]) throw new Error("faces[0] is not defined");
                if (!faces[j + 1]) throw new Error("faces[i] is not defined");
                // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
                faces[i + 1].getEdge(2)?.setOpposite(faces[0].getEdge(j)!);
                // join face[i] with face[i + 1], 1 <= i <= 3
                // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
                faces[i + 1].getEdge(1)?.setOpposite(faces[j + 1].getEdge(0)!);
            }
        } else {
            // the face is able to see the point so `planeNormal`
            // is pointing inside the tetrahedron
            if (!v3) throw new Error("v3 is not defined");
            if (!v2) throw new Error("v2 is not defined");
            if (!v1) throw new Error("v1 is not defined");
            faces.push(
                Face.createTriangle(v0, v2, v1),
                Face.createTriangle(v3, v0, v1),
                Face.createTriangle(v3, v1, v2),
                Face.createTriangle(v3, v2, v0)
            );

            // set the opposite edge
            for (i = 0; i < 3; i += 1) {
                const j = (i + 1) % 3;
                // join face[i] i > 0, with the first face
                faces[i + 1]
                    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
                    .getEdge(2)
                    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
                    ?.setOpposite(faces[0].getEdge((3 - i) % 3)!);
                // join face[i] with face[i + 1]
                // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
                faces[i + 1].getEdge(0)?.setOpposite(faces[j + 1].getEdge(1)!);
            }
        }

        // the initial hull is the tetrahedron
        for (i = 0; i < 4; i += 1) {
            this.faces.push(faces[i]);
        }

        // initial assignment of vertices to the faces of the tetrahedron
        for (i = 0; i < vertices.length; i += 1) {
            const vertex = vertices[i];
            if (
                vertex !== v0 &&
                vertex !== v1 &&
                vertex !== v2 &&
                vertex !== v3
            ) {
                maxDistance = this.tolerance;
                let maxFace;
                for (j = 0; j < 4; j += 1) {
                    const distance = faces[j].distanceToPlane(vertex.point);
                    if (distance > maxDistance) {
                        maxDistance = distance;
                        maxFace = faces[j];
                    }
                }

                if (maxFace) {
                    this.addVertexToFace(vertex, maxFace);
                }
            }
        }
    }

    reindexFaceAndVertices() {
        // remove inactive faces
        const activeFaces = [];
        for (let i = 0; i < this.faces.length; i += 1) {
            const face = this.faces[i];
            if (face.mark === VISIBLE) {
                activeFaces.push(face);
            }
        }
        this.faces = activeFaces;
    }

    collectFaces(skipTriangulation: boolean) {
        const faceIndices = [];
        for (let i = 0; i < this.faces.length; i += 1) {
            if (this.faces[i].mark !== VISIBLE) {
                throw Error("attempt to include a destroyed face in the hull");
            }
            const indices = this.faces[i].collectIndices();
            if (skipTriangulation) {
                faceIndices.push(indices);
            } else {
                for (let j = 0; j < indices.length - 2; j += 1) {
                    faceIndices.push([
                        indices[0],
                        indices[j + 1],
                        indices[j + 2],
                    ]);
                }
            }
        }
        return faceIndices;
    }

    /**
     * Finds the next vertex to make faces with the current hull
     *
     * - let `face` be the first face existing in the `claimed` vertex list
     *  - if `face` doesn't exist then return since there're no vertices left
     *  - otherwise for each `vertex` that face sees find the one furthest away
     *  from `face`
     *
     * @return {Vertex|undefined} Returns undefined when there're no more
     * visible vertices
     */
    nextVertexToAdd() {
        if (!this.claimed.isEmpty()) {
            let eyeVertex, vertex;
            let maxDistance = 0;
            const eyeFace = this.claimed.first()?.face;
            for (
                vertex = eyeFace?.outside;
                vertex && vertex.face === eyeFace;
                vertex = vertex.next
            ) {
                const distance = eyeFace?.distanceToPlane(vertex.point) || 0;
                if (distance > maxDistance) {
                    maxDistance = distance;
                    eyeVertex = vertex;
                }
            }
            return eyeVertex;
        }
    }

    /**
     * Computes a chain of half edges in ccw order called the `horizon`, for an
     * edge to be part of the horizon it must join a face that can see
     * `eyePoint` and a face that cannot see `eyePoint`
     *
     * @param {number[]} eyePoint - The coordinates of a point
     * @param {HalfEdge} crossEdge - The edge used to jump to the current `face`
     * @param {Face} face - The current face being tested
     * @param {HalfEdge[]} horizon - The edges that form part of the horizon in
     * ccw order
     */
    computeHorizon(
        eyePoint: number[],
        crossEdge: HalfEdge,
        face: Face,
        horizon: HalfEdge[]
    ) {
        // moves face's vertices to the `unclaimed` vertex list
        this.deleteFaceVertices(face, new Face());

        face.mark = DELETED;

        let edge;
        if (!crossEdge) {
            edge = crossEdge =
                face.getEdge(0) || new HalfEdge(new Vertex([], 0), new Face());
        } else {
            // start from the next edge since `crossEdge` was already analyzed
            // (actually `crossEdge.opposite` was the face who called this method
            // recursively)
            edge = crossEdge.next;
        }

        // All the faces that are able to see `eyeVertex` are defined as follows
        //
        //       v    /
        //           / <== visible face
        //          /
        //         |
        //         | <== not visible face
        //
        //  dot(v, visible face normal) - visible face offset > this.tolerance
        //
        do {
            const oppositeEdge = edge?.opposite;
            const oppositeFace = oppositeEdge?.face;
            if (!oppositeEdge) throw new Error("oppositeEdge is not defined");
            if (oppositeFace?.mark === VISIBLE) {
                if (oppositeFace.distanceToPlane(eyePoint) > this.tolerance) {
                    this.computeHorizon(
                        eyePoint,
                        oppositeEdge,
                        oppositeFace,
                        horizon
                    );
                } else {
                    if (edge) horizon.push(edge);
                }
            }
            edge = edge?.next;
        } while (edge !== crossEdge);
    }

    /**
     * Creates a face with the points `eyeVertex.point`, `horizonEdge.tail` and
     * `horizonEdge.tail` in ccw order
     *
     * @param {Vertex} eyeVertex
     * @param {HalfEdge} horizonEdge
     * @return {HalfEdge} The half edge whose vertex is the eyeVertex
     */
    addAdjoiningFace(eyeVertex: Vertex, horizonEdge: HalfEdge) {
        // all the half edges are created in ccw order thus the face is always
        // pointing outside the hull
        // edges:
        //
        //                  eyeVertex.point
        //                       / \
        //                      /   \
        //                  1  /     \  0
        //                    /       \
        //                   /         \
        //                  /           \
        //          horizon.tail --- horizon.head
        //                        2
        //
        const face = Face.createTriangle(
            eyeVertex,
            horizonEdge.tail() || new Vertex([], 0),
            horizonEdge.head()
        );
        this.faces.push(face);
        // join face.getEdge(-1) with the horizon's opposite edge
        // face.getEdge(-1) = face.getEdge(2)
        face.getEdge(-1)?.setOpposite(
            horizonEdge.opposite || new HalfEdge(new Vertex([], 0), new Face())
        );
        return face.getEdge(0);
    }

    /**
     * Adds horizon.length faces to the hull, each face will be 'linked' with the
     * horizon opposite face and the face on the left/right
     *
     * @param {Vertex} eyeVertex
     * @param {HalfEdge[]} horizon - A chain of half edges in ccw order
     */
    addNewFaces(eyeVertex: Vertex, horizon: HalfEdge[]) {
        this.newFaces = [];
        let firstSideEdge, previousSideEdge;
        for (let i = 0; i < horizon.length; i += 1) {
            const horizonEdge = horizon[i];
            // returns the right side edge
            const sideEdge = this.addAdjoiningFace(eyeVertex, horizonEdge);
            if (!firstSideEdge) {
                firstSideEdge = sideEdge;
            } else {
                // joins face.getEdge(1) with previousFace.getEdge(0)
                sideEdge?.next?.setOpposite(
                    previousSideEdge ||
                        new HalfEdge(new Vertex([], 0), new Face())
                );
            }
            this.newFaces.push(sideEdge?.face || new Face());
            previousSideEdge = sideEdge;
        }
        firstSideEdge?.next?.setOpposite(
            previousSideEdge || new HalfEdge(new Vertex([], 0), new Face())
        );
    }

    /**
     * Computes the distance from `edge` opposite face's centroid to
     * `edge.face`
     *
     * @param {HalfEdge} edge
     * @return {number}
     * - A positive number when the centroid of the opposite face is above the
     *   face i.e. when the faces are concave
     * - A negative number when the centroid of the opposite face is below the
     *   face i.e. when the faces are convex
     */
    oppositeFaceDistance(edge: HalfEdge) {
        return edge?.face?.distanceToPlane(edge.opposite?.face?.centroid || []);
    }

    /**
     * Merges a face with none/any/all its neighbors according to the strategy
     * used
     *
     * if `mergeType` is MERGE_NON_CONVEX_WRT_LARGER_FACE then the merge will be
     * decided based on the face with the larger area, the centroid of the face
     * with the smaller area will be checked against the one with the larger area
     * to see if it's in the merge range [tolerance, -tolerance] i.e.
     *
     *    dot(centroid smaller face, larger face normal) - larger face offset > -tolerance
     *
     * Note that the first check (with +tolerance) was done on `computeHorizon`
     *
     * If the above is not true then the check is done with respect to the smaller
     * face i.e.
     *
     *    dot(centroid larger face, smaller face normal) - smaller face offset > -tolerance
     *
     * If true then it means that two faces are non convex (concave), even if the
     * dot(...) - offset value is > 0 (that's the point of doing the merge in the
     * first place)
     *
     * If two faces are concave then the check must also be done on the other face
     * but this is done in another merge pass, for this to happen the face is
     * marked in a temporal NON_CONVEX state
     *
     * if `mergeType` is MERGE_NON_CONVEX then two faces will be merged only if
     * they pass the following conditions
     *
     *    dot(centroid smaller face, larger face normal) - larger face offset > -tolerance
     *    dot(centroid larger face, smaller face normal) - smaller face offset > -tolerance
     *
     * @param {Face} face
     * @param {number} mergeType - Either MERGE_NON_CONVEX_WRT_LARGER_FACE or
     * MERGE_NON_CONVEX
     */
    doAdjacentMerge(face: Face, mergeType: number) {
        let edge = face.edge;
        let convex = true;
        let it = 0;
        do {
            if (it >= face.nVertices) {
                throw Error("merge recursion limit exceeded");
            }
            const oppositeFace = edge?.opposite?.face;
            let merge = false;

            // Important notes about the algorithm to merge faces
            //
            // - Given a vertex `eyeVertex` that will be added to the hull
            //   all the faces that cannot see `eyeVertex` are defined as follows
            //
            //      dot(v, not visible face normal) - not visible offset < tolerance
            //
            // - Two faces can be merged when the centroid of one of these faces
            // projected to the normal of the other face minus the other face offset
            // is in the range [tolerance, -tolerance]
            // - Since `face` (given in the input for this method) has passed the
            // check above we only have to check the lower bound e.g.
            //
            //      dot(v, not visible face normal) - not visible offset > -tolerance
            //
            if (mergeType === MERGE_NON_CONVEX) {
                if (
                    (this.oppositeFaceDistance(
                        edge || new HalfEdge(new Vertex([], 0), new Face())
                    ) || 0) > -this.tolerance ||
                    (this.oppositeFaceDistance(
                        edge?.opposite ||
                            new HalfEdge(new Vertex([], 0), new Face())
                    ) || 0) > -this.tolerance
                ) {
                    merge = true;
                }
            } else {
                if (face.area > (oppositeFace?.area || 0)) {
                    if (
                        (this.oppositeFaceDistance(
                            edge || new HalfEdge(new Vertex([], 0), new Face())
                        ) || 0) > -this.tolerance
                    ) {
                        merge = true;
                    } else if (
                        (this.oppositeFaceDistance(
                            edge?.opposite ||
                                new HalfEdge(new Vertex([], 0), new Face())
                        ) || 0) > -this.tolerance
                    ) {
                        convex = false;
                    }
                } else {
                    if (
                        (this.oppositeFaceDistance(
                            edge?.opposite ||
                                new HalfEdge(new Vertex([], 0), new Face())
                        ) || 0) > -this.tolerance
                    ) {
                        merge = true;
                    } else if (
                        (this.oppositeFaceDistance(
                            edge || new HalfEdge(new Vertex([], 0), new Face())
                        ) || 0) > -this.tolerance
                    ) {
                        convex = false;
                    }
                }
            }

            if (merge) {
                debug("face merge");
                // when two faces are merged it might be possible that redundant faces
                // are destroyed, in that case move all the visible vertices from the
                // destroyed faces to the `unclaimed` vertex list
                const discardedFaces = face.mergeAdjacentFaces(
                    edge || new HalfEdge(new Vertex([], 0), new Face()),
                    []
                );
                for (let i = 0; i < discardedFaces.length; i += 1) {
                    this.deleteFaceVertices(
                        discardedFaces[i] || new Face(),
                        face
                    );
                }
                return true;
            }

            edge = edge?.next || null;
            it += 1;
        } while (edge !== face.edge);
        if (!convex) {
            face.mark = NON_CONVEX;
        }
        return false;
    }

    /**
     * Adds a vertex to the hull with the following algorithm
     *
     * - Compute the `horizon` which is a chain of half edges, for an edge to
     *   belong to this group it must be the edge connecting a face that can
     *   see `eyeVertex` and a face which cannot see `eyeVertex`
     * - All the faces that can see `eyeVertex` have its visible vertices removed
     *   from the claimed VertexList
     * - A new set of faces is created with each edge of the `horizon` and
     *   `eyeVertex`, each face is connected with the opposite horizon face and
     *   the face on the left/right
     * - The new faces are merged if possible with the opposite horizon face first
     *   and then the faces on the right/left
     * - The vertices removed from all the visible faces are assigned to the new
     *   faces if possible
     *
     * @param {Vertex} eyeVertex
     */
    addVertexToHull(eyeVertex: Vertex) {
        const horizon: HalfEdge[] = [];

        this.unclaimed.clear();

        // remove `eyeVertex` from `eyeVertex.face` so that it can't be added to the
        // `unclaimed` vertex list
        this.removeVertexFromFace(eyeVertex, eyeVertex.face || new Face());
        this.computeHorizon(
            eyeVertex.point,
            new HalfEdge(new Vertex([], 0), new Face()),
            eyeVertex.face || new Face(),
            horizon
        );
        if (debug.enabled) {
            debug(
                "horizon %j",
                horizon.map(function (edge) {
                    return edge.head().index;
                })
            );
        }
        this.addNewFaces(eyeVertex, horizon);

        debug("first merge");

        // first merge pass
        // Do the merge with respect to the larger face
        for (let i = 0; i < this.newFaces.length; i += 1) {
            const face = this.newFaces[i];
            if (face.mark === VISIBLE) {
                while (
                    this.doAdjacentMerge(face, MERGE_NON_CONVEX_WRT_LARGER_FACE)
                ) {
                    void 0;
                }
            }
        }

        debug("second merge");

        // second merge pass
        // Do the merge on non convex faces (a face is marked as non convex in the
        // first pass)
        for (let i = 0; i < this.newFaces.length; i += 1) {
            const face = this.newFaces[i];
            if (face.mark === NON_CONVEX) {
                face.mark = VISIBLE;
                while (this.doAdjacentMerge(face, MERGE_NON_CONVEX)) {
                    void 0;
                }
            }
        }

        debug("reassigning points to newFaces");
        // reassign `unclaimed` vertices to the new faces
        this.resolveUnclaimedPoints(this.newFaces);
    }

    build() {
        let iterations = 0;
        let eyeVertex;
        this.createInitialSimplex();
        while ((eyeVertex = this.nextVertexToAdd())) {
            iterations += 1;
            debug("== iteration %j ==", iterations);
            debug(
                "next vertex to add = %d %j",
                eyeVertex.index,
                eyeVertex.point
            );
            this.addVertexToHull(eyeVertex);
            debug("end");
        }
        this.reindexFaceAndVertices();
    }

    /**
     *
     * @typedef {Object} Vector3
     * @property {Number} x
     * @property {Number} y
     * @property {Number} z
     */

    /**
     *
     * @param {Array<Vector3 | Array<Number>} points
     * @returns {Array<Array<Number>>}
     */
    static createHull(points: number[][]) {
        points = points.slice();
        for (let pti = 0; pti < points.length; pti++) {
            const pt = points[pti];
            if (!Array.isArray(pt)) {
                points[pti] = [pt[0], pt[1], pt[2]];
            }
        }
        const hull = new QuickHull(points);
        hull.build();
        const faces = hull.collectFaces(false);
        return faces;
    }
}

export default QuickHull;

[Dannie226]

Nice. My only complaint with the conversion is that with the createHull function, it can no longer take an array of number triplets or an array of vectors. Other than that, good job on the conversion.

[RedstoneWizard08]

@Dannie226 Then I think I might add a conversion utility to convert vectors/triplets to numbers, then implement it internally. I'm going to create a GitHub repo and NPM package for this.

https://github.com/RedstoneWizard08/QuickHull.git

[RedstoneWizard08]

Added the vertex conversion

[RedstoneWizard08]

Ok, I made the NPM package quickhull-ts, and I added a small bit of docs to the README. Also, I made a few changes to help people, like allowing them to use Vector3s and number arrays at the same time, and some other nice things. I do need help with one thing, though. When I test it, it keeps saying v3 or v2 is undefined. Can you help me, @Dannie226?
Check this line: https://github.com/RedstoneWizard08/QuickHull/blob/0aa626e7a08c317d1e73dd9c67f7a1a0ee11919c/src/quickhull.ts#L319

[Dannie226]

try initializing max distance to -1, not 0

[RedstoneWizard08]

Ok

[RedstoneWizard08]

That worked! Thanks! Fixing the bug under version 1.0.2

[Dannie226]

Let's move this conversation over to the quickhull repo that you made because technically, this conversation isn't directly part of improving the cannon-es convex polyhedron creation

[RedstoneWizard08]

Okay.

[nektdev]

Thank you for brilliant code @Dannie226 and to other contributors!
What could be a reasonable approach to creating an inside-out collision convex (to be able to have collisions within the object)? Flipping the geometry in Blender or via code before passing to QuickHull does not change the fact CANNON.ConvexPolyhedron is wrapping the outside of the mesh.