1-Introduction to Convex Hull

Convex Hull: The smallest convex bounding volume that can enclose a set of points.

Taking a 2D point set as an example, its convex hull can be imagined as the outline formed by pulling a rubber band tight around all the points.

Common convex hull algorithms:

Algorithm	Time Complexity	Characteristics	Applicable Scenarios
Brute Force	O(n3)	Enumerates all edges for judgment; theoretical teaching, not practical	Learning principles only
Graham Scan	O(nlogn)	Polar angle sorting + stack	Classic introductory algorithm
Andrew's Monotone Chain	O(nlogn)	Coordinate sorting, simplest and most stable implementation	Engineering first choice
Jarvis March (Gift Wrapping)	O(nh), h is the number of convex hull vertices	Similar to gift wrapping, very fast when h is small	Sparse convex hull scenarios
QuickHull	Expected O(nlogn), worst O(n2)	Divide and conquer, similar to quicksort	Large-scale point clouds

In graphics development, prioritize using Andrew's Monotone Chain algorithm, as the code is concise, numerically stable, and less prone to polar angle precision issues.

Next, we will detail the common methods for calculating 2D and 3D convex hulls.

2-2D Convex Hull

Next, we will use Andrew's Monotone Chain algorithm to calculate the 2D convex hull.

2-1-Calculation Principle

Given: A set of 2D vertices A to G

Find: The convex hull of the 2D vertex set

Solution:

1. Sort.

Sort the vertices by the size of their x position. If x is the same, sort by the size of their y value.

1. Calculate the lower convex hull in order, which is ADG.

The calculation principle is to use the sorted order, from front to back, to construct 2 vectors from 3 adjacent vertices for a cross product operation, and use the cross product result to determine if the convex hull condition is met.

For example: AB cross AC, if the result is less than 0, discard point B, then use AC cross AD, ...; otherwise, keep point B, then use BC cross BD, ....

1. Calculate the upper convex hull in order, which is GFBA.

The principle is the same as above.

1. Combine the lower convex hull and the upper convex hull together, which is the convex hull of the 2D vertex set.

2-2-Code Implementation

1. Randomly generate a 2D point set.

   function randomPoints(count: number): Point2[] { const out: Point2[] = []; const span = 9; for (let i = 0; i < count; i++) { out.push({id: nextId++, x: (Math.random() * 2 - 1) * span, y: (Math.random() * 2 - 1) * span, }); } return out; } const points = randomPoints(10);

2. Calculate the convex hull of the 2D point set.

   const convexHull=monotoneChain(points)

monotoneChain is the method for calculating the 2D convex hull, the code is as follows:

export type Point2 = { x: number; y: number };

function cross(o: Point2, a: Point2, b: Point2): number {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

function compareXY(a: Point2, b: Point2): number {
  if (a.x !== b.x) return a.x - b.x;
  return a.y - b.y;
}

function pointKey(p: Point2): string {
  return `${p.x},${p.y}`;
}

function dedupeSorted(points: Point2[]): Point2[] {
  const out: Point2[] = [];
  const seen = new Set<string>();
  for (const p of points) {
    const key = pointKey(p);
    if (seen.has(key)) continue;
    seen.add(key);
    out.push(p);
  }
  return out;
}

/** Andrew's Monotone Chain: sort O(n log n), build chain O(n) */
export function monotoneChain(input: Point2[]): Point2[] {
  if (input.length === 0) return [];

  // 1. Sort by x (then by y) and deduplicate
  const sorted = dedupeSorted([...input].sort(compareXY));
  if (sorted.length <= 2) return [...sorted];

  // 2. Lower convex hull: left → right, maintain strict left turn
  const lower: Point2[] = [];
  for (const p of sorted) {
    while (lower.length >= 2) {
      const o = lower[lower.length - 2]!;
      const a = lower[lower.length - 1]!;
      if (cross(o, a, p) <= 0) lower.pop();
      else break;
    }
    lower.push(p);
  }

  // 3. Upper convex hull: right → left; skip interior points of the lower chain, keep endpoints
  const upper: Point2[] = [];
  const lowerInterior = new Set(lower.slice(1, -1));

  for (let i = sorted.length - 1; i >= 0; i--) {
    const p = sorted[i]!;
    if (lowerInterior.has(p)) continue;

    while (upper.length >= 2) {
      const o = upper[upper.length - 2]!;
      const a = upper[upper.length - 1]!;
      if (cross(o, a, p) <= 0) upper.pop();
      else break;
    }
    upper.push(p);
  }

  // 4. Merge (remove duplicate endpoints); degenerate to leftmost ↔ rightmost if all collinear
  const result = [...lower.slice(0, -1), ...upper.slice(0, -1)];
  return result.length >= 2
    ? result
    : [sorted[0]!, sorted[sorted.length - 1]!];
}

Explain the while logic above.

The role of while is to continuously discard points that would break the convex hull before pushing a new point onto the stack.

Take the following diagram as an example to determine the lower convex hull.

ABC is the lower convex hull, so ABC can be pushed onto the stack;

BCD is not the lower convex hull, so C is discarded, but before D is pushed onto the stack, it must check further back to see if there are points that break the convex hull.

ABD is not the lower convex hull, so B is discarded, and now AD is pushed onto the stack.

3-3D Convex Hull

Next, we will use the incremental construction method to calculate the convex hull.

Incremental construction (beneath-beyond): Starting from a tetrahedron, expand point by point into a multi-faced convex hull.

3-1-Implementation Logic of Incremental Construction

1. Given random 3D points.

1. Find the tetrahedron with the largest volume among the 3D points.

1. Iterate through the other vertices outside the tetrahedron. If a vertex is inside the tetrahedron, skip it; otherwise, find the faces of the tetrahedron that face towards this vertex.

In the diagram above, the red vertex can be understood as our eye. The faces we can see are visible faces, otherwise they are invisible faces.

1. In the tetrahedron, find the boundary edges between visible and invisible faces.

The condition for a boundary edge is: an edge has 2 adjacent faces, one face is visible, and one face is invisible.

1. Delete the visible faces. Connect the boundary edges to the red vertex to construct new triangular faces, which together with the previous invisible faces form a new geometry.

1. Repeat step 3, iterate through all vertices, and you can obtain the 3D convex hull using the incremental construction method.

3-2-Code Implementation of 3D Convex Hull

1. Assign IDs to vertices

/** Spatial point; id is used for visualization tracking, not involved in geometric calculations. */
export type Point3 = {
  x: number;
  y: number;
  z: number;
  id: number;
};
/** Current input point set */
let points: Point3[] = [];
/** Point id auto-increment counter, ensures visualization can stably track each point */
let nextId = 1;

function randomPoints(count: number): Point3[] {
  const out: Point3[] = [];
  const span = 6;
  for (let i = 0; i < count; i++) {
    out.push({
      id: nextId++,
      x: (Math.random() * 2 - 1) * span,
      y: (Math.random() * 2 - 1) * span,
      z: (Math.random() * 2 - 1) * span,
    });
  }
  return out;
}

const points = randomPoints(12);

The vertices above are randomly generated; in practical work, they are taken from some model.

2. Calculate the convex hull of the vertex set

const faceList=incrementalHull(points)

incrementalHull is the method for calculating the convex hull using incremental construction. Its overall code is as follows:

/**
 * 3D Convex Hull Incremental Construction (beneath-beyond)
 * Deduplicate → Find four non-coplanar points with max volume to build initial tetrahedron → Point by point: visible faces → horizon → delete faces → triangulate
 */

export type Point3 = {
    x: number;
    y: number;
    z: number;
    id: number;
};

/** Triangular face: three points ordered by the right-hand rule of the outward normal */
export type Face3 = {
    a: Point3;
    b: Point3;
    c: Point3;
};

const EPS = 1e-9;

type Vec3 = [number, number, number];

function sub(a: Point3, b: Point3): Vec3 {
    return [a.x - b.x, a.y - b.y, a.z - b.z];
}

function cross3(u: Vec3, v: Vec3): Vec3 {
    return [
        u[1] * v[2] - u[2] * v[1],
        u[2] * v[0] - u[0] * v[2],
        u[0] * v[1] - u[1] * v[0],
    ];
}

function dot(u: Vec3, v: Vec3): number {
    return u[0] * v[0] + u[1] * v[1] + u[2] * v[2];
}

function len2(u: Vec3): number {
    return dot(u, u);
}

/** ((b-a)×(c-a))·(p-a); when the outward normal faces outward, >0 indicates p is on the outside */
export function orient(a: Point3, b: Point3, c: Point3, p: Point3): number {
    return dot(cross3(sub(b, a), sub(c, a)), sub(p, a));
}

function pointKey3(p: Point3): string {
    return `${p.x},${p.y},${p.z}`;
}

function faceKey(f: Face3): string {
    const ids = [f.a.id, f.b.id, f.c.id].sort((x, y) => x - y);
    return ids.join('-');
}

function dedupe(points: Point3[]): Point3[] {
    const out: Point3[] = [];
    const seen = new Set<string>();
    for (const p of points) {
        const key = pointKey3(p);
        if (seen.has(key)) continue;
        seen.add(key);
        out.push(p);
    }
    return out;
}

function centroidOfPoints(pts: Point3[]): Point3 {
    let x = 0;
    let y = 0;
    let z = 0;
    for (const p of pts) {
        x += p.x;
        y += p.y;
        z += p.z;
    }
    const n = pts.length || 1;
    return { id: -1, x: x / n, y: y / n, z: z / n };
}

function uniqueVertices(faces: Face3[]): Point3[] {
    const map = new Map<number, Point3>();
    for (const f of faces) {
        map.set(f.a.id, f.a);
        map.set(f.b.id, f.b);
        map.set(f.c.id, f.c);
    }
    return [...map.values()];
}

function orientFaceOutward(face: Face3, interior: Point3): Face3 {
    if (orient(face.a, face.b, face.c, interior) > 0) {
        return { a: face.a, b: face.c, c: face.b };
    }
    return face;
}

function orientAllOutward(faces: Face3[], interior: Point3): Face3[] {
    return faces.map((f) => orientFaceOutward(f, interior));
}

/** Select the four non-coplanar points with the largest volume */
function findInitialTetra(
    points: Point3[],
): { tetra: [Point3, Point3, Point3, Point3]; rest: Point3[] } | null {
    if (points.length < 4) return null;

    let i0 = 0;
    let i1 = 1;
    let bestD = -1;
    for (let i = 0; i < points.length; i++) {
        for (let j = i + 1; j < points.length; j++) {
            const d = len2(sub(points[i]!, points[j]!));
            if (d > bestD) {
                bestD = d;
                i0 = i;
                i1 = j;
            }
        }
    }
    if (bestD <= EPS) return null;

    const a = points[i0]!;
    const b = points[i1]!;
    const ab = sub(b, a);

    let i2 = -1;
    let bestArea = -1;
    for (let i = 0; i < points.length; i++) {
        if (i === i0 || i === i1) continue;
        const area = len2(cross3(ab, sub(points[i]!, a)));
        if (area > bestArea) {
            bestArea = area;
            i2 = i;
        }
    }
    if (i2 < 0 || bestArea <= EPS) return null;

    const c = points[i2]!;

    let i3 = -1;
    let bestVol = -1;
    for (let i = 0; i < points.length; i++) {
        if (i === i0 || i === i1 || i === i2) continue;
        const vol = Math.abs(orient(a, b, c, points[i]!));
        if (vol > bestVol) {
            bestVol = vol;
            i3 = i;
        }
    }
    if (i3 < 0 || bestVol <= EPS) return null;

    const used = new Set([i0, i1, i2, i3]);
    const tetra: [Point3, Point3, Point3, Point3] = [
        points[i0]!,
        points[i1]!,
        points[i2]!,
        points[i3]!,
    ];
    const rest = points.filter((_, i) => !used.has(i));
    return { tetra, rest };
}

function makeTetraFaces(
    p0: Point3,
    p1: Point3,
    p2: Point3,
    p3: Point3,
): Face3[] {
    const interior = centroidOfPoints([p0, p1, p2, p3]);
    const raw: Face3[] = [
        { a: p0, b: p1, c: p2 },
        { a: p0, b: p2, c: p3 },
        { a: p0, b: p3, c: p1 },
        { a: p1, b: p3, c: p2 },
    ];
    return orientAllOutward(raw, interior);
}

function edgeKey(u: Point3, v: Point3): string {
    return u.id < v.id ? `${u.id}_${v.id}` : `${v.id}_${u.id}`;
}

type HorizonEdge = { from: Point3; to: Point3 };

/** Horizon: edges that connect exactly one visible face and one invisible face */
function findHorizon(faces: Face3[], visible: Face3[]): HorizonEdge[] {
    const visibleSet = new Set(visible.map(faceKey));

    type EdgeRec = {
        from: Point3;
        to: Point3;
        visible: boolean;
    };

    const byEdge = new Map<string, EdgeRec[]>();

    for (const f of faces) {
        const vis = visibleSet.has(faceKey(f));
        const directed: Array<[Point3, Point3]> = [
            [f.a, f.b],
            [f.b, f.c],
            [f.c, f.a],
        ];
        for (const [from, to] of directed) {
            const key = edgeKey(from, to);
            const list = byEdge.get(key) ?? [];
            list.push({ from, to, visible: vis });
            byEdge.set(key, list);
        }
    }

    const horizon: HorizonEdge[] = [];
    for (const recs of byEdge.values()) {
        if (recs.length !== 2) continue;
        const [r0, r1] = recs;
        if (r0!.visible === r1!.visible) continue;
        const visRec = r0!.visible ? r0! : r1!;
        horizon.push({ from: visRec.from, to: visRec.to });
    }
    return horizon;
}

function facesFromHorizon(
    horizon: HorizonEdge[],
    eye: Point3,
    interior: Point3,
): Face3[] {
    return horizon.map((e) =>
        orientFaceOutward({ a: e.from, b: e.to, c: eye }, interior),
    );
}

/** Validation: all vertices should be on the inside or on the face of each face */
export function validateHull(faces: Face3[], eps = 1e-6): boolean {
    if (faces.length < 4) return faces.length === 0;
    const verts = uniqueVertices(faces);
    const interior = centroidOfPoints(verts);
    for (const f of faces) {
        if (orient(f.a, f.b, f.c, interior) > eps) return false;
    }
    for (const f of faces) {
        for (const p of verts) {
            if (p.id === f.a.id || p.id === f.b.id || p.id === f.c.id) continue;
            if (orient(f.a, f.b, f.c, p) > eps) return false;
        }
    }
    return true;
}

/** Incrementally construct the 3D convex hull, returning a set of triangular faces */
export function incrementalHull(input: Point3[]): Face3[] {
    if (input.length === 0) return [];

    const points = dedupe(input);
    if (points.length < 4) return [];

    const initial = findInitialTetra(points);
    if (!initial) return [];

    const [p0, p1, p2, p3] = initial.tetra;
    let faces = makeTetraFaces(p0, p1, p2, p3);

    for (const eye of initial.rest) {
        const visible = faces.filter((f) => orient(f.a, f.b, f.c, eye) > EPS);
        if (visible.length === 0) continue;

        const horizon = findHorizon(faces, visible);
        if (horizon.length < 3) continue;

        const visibleKeys = new Set(visible.map(faceKey));
        const kept = faces.filter((f) => !visibleKeys.has(faceKey(f)));
        const interior = centroidOfPoints([...uniqueVertices(kept), eye]);
        const added = facesFromHorizon(horizon, eye, interior);
        faces = [...kept, ...added];
    }

    faces = orientAllOutward(faces, centroidOfPoints(uniqueVertices(faces)));
    return faces;
}

The incrementalHull method involves quite a bit of code, let's explain it in detail.

4-incrementalHull Code Explanation

4-1-Vertex Deduplication, Check Vertex Count

For vertices at the same position, only take one.

If the number of vertices after deduplication is less than 4, return [].

if (input.length === 0) return [];

const points = dedupe(input);
if (points.length < 4) return [];

dedupe is the vertex deduplication method.

function pointKey3(p: Point3): string {
	return `${p.x},${p.y},${p.z}`;
}
function dedupe(points: Point3[]): Point3[] {
    const out: Point3[] = [];
    const seen = new Set<string>();
    for (const p of points) {
      const key = pointKey3(p);
      if (seen.has(key)) continue;
      seen.add(key);
      out.push(p);
    }
    return out;
}

This method turns the vertex position into a string, then uses it as a Set value to determine if points are the same.

1. If the number of vertices after deduplication is less than 4, return [].

   if (points.length < 4) return [];

4-2-Get the Largest Tetrahedron Among the Vertices

const initial = findInitialTetra(points);
if (!initial) return [];

The findInitialTetra method is the method for obtaining the largest tetrahedron.

function findInitialTetra(
    points: Point3[],
): { tetra: [Point3, Point3, Point3, Point3]; rest: Point3[] } | null {
    if (points.length < 4) return null;

    let i0 = 0;
    let i1 = 1;
    let bestD = -1;
    for (let i = 0; i < points.length; i++) {
        for (let j = i + 1; j < points.length; j++) {
            const d = len2(sub(points[i]!, points[j]!));
            if (d > bestD) {
                bestD = d;
                i0 = i;
                i1 = j;
            }
        }
    }
    if (bestD <= EPS) return null;

    const a = points[i0]!;
    const b = points[i1]!;
    const ab = sub(b, a);

    let i2 = -1;
    let bestArea = -1;
    for (let i = 0; i < points.length; i++) {
        if (i === i0 || i === i1) continue;
        const area = len2(cross3(ab, sub(points[i]!, a)));
        if (area > bestArea) {
            bestArea = area;
            i2 = i;
        }
    }
    if (i2 < 0 || bestArea <= EPS) return null;

    const c = points[i2]!;

    let i3 = -1;
    let bestVol = -1;
    for (let i = 0; i < points.length; i++) {
        if (i === i0 || i === i1 || i === i2) continue;
        const vol = Math.abs(orient(a, b, c, points[i]!));
        if (vol > bestVol) {
            bestVol = vol;
            i3 = i;
        }
    }
    if (i3 < 0 || bestVol <= EPS) return null;

    const used = new Set([i0, i1, i2, i3]);
    const tetra: [Point3, Point3, Point3, Point3] = [
        points[i0]!,
        points[i1]!,
        points[i2]!,
        points[i3]!,
    ];
    const rest = points.filter((_, i) => !used.has(i));
    return { tetra, rest };
}

Explain the calculation steps of the findInitialTetra method in detail.

1. Find the 2 points farthest apart, i.e., a, b

   let i0 = 0; let i1 = 1; let bestD = -1; for (let i = 0; i < points.length; i++) { for (let j = i + 1; j < points.length; j++) { const d = len2(sub(points[i]!, points[j]!)); if (d > bestD) { bestD = d; i0 = i; i1 = j; } } } if (bestD <= EPS) return null;

   const a = points[i0]!; const b = points[i1]!; const ab = sub(b, a);

sub is vector subtraction.

function sub(a: Point3, b: Point3): Vec3 {
    return [a.x - b.x, a.y - b.y, a.z - b.z];
}

len2 calculates the square of the vector length using the dot product of the same vector.

function len2(u: Vec3): number {
    return dot(u, u);
}
function dot(u: Vec3, v: Vec3): number {
    return u[0] * v[0] + u[1] * v[1] + u[2] * v[2];
}

1. Find the point that forms the largest triangle with ab, i.e., c.

   let i2 = -1; let bestArea = -1; for (let i = 0; i < points.length; i++) { if (i === i0 || i === i1) continue; const area = len2(cross3(ab, sub(points[i]!, a))); if (area > bestArea) { bestArea = area; i2 = i; } } if (i2 < 0 || bestArea <= EPS) return null;

   const c = points[i2]!;

The area of a triangle can be calculated using the length of the cross product of its two sides.

const area = len2(cross3(ab, sub(points[i]!, a)));

cross3 is the 3D vector cross product method.

function cross3(u: Vec3, v: Vec3): Vec3 {
    return [
        u[1] * v[2] - u[2] * v[1],
        u[2] * v[0] - u[0] * v[2],
        u[0] * v[1] - u[1] * v[0],
    ];
}

1. Find the point that forms the largest tetrahedron with abc.

   let i3 = -1; let bestVol = -1; for (let i = 0; i < points.length; i++) { if (i === i0 || i === i1 || i === i2) continue; const vol = Math.abs(orient(a, b, c, points[i]!)); if (vol > bestVol) { bestVol = vol; i3 = i; } } if (i3 < 0 || bestVol <= EPS) return null;

The volume of a tetrahedron is half the absolute value of the determinant of its three adjacent edges.

const vol = Math.abs(orient(a, b, c, points[i]!));

The code above does not halve it, because this is just for comparison, not halving is fine.

orient is the determinant calculation method, its geometric concept is to use three vectors to calculate the signed volume of the parallelepiped formed by them as edges.

/** ((b-a)×(c-a))·(p-a); when the outward normal faces outward, >0 indicates p is on the outside */
export function orient(a: Point3, b: Point3, c: Point3, p: Point3): number {
    return dot(cross3(sub(b, a), sub(c, a)), sub(p, a));
}

1. Return the vertices of the largest tetrahedron, and the other vertices in the vertex set.

   const used = new Set([i0, i1, i2, i3]); const tetra: [Point3, Point3, Point3, Point3] = [ points[i0]!, points[i1]!, points[i2]!, points[i3]!, ]; const rest = points.filter((_, i) => !used.has(i)); return { tetra, rest };

4-3-Generate Outward-Facing Triangular Faces from the Tetrahedron's Vertices

const [p0, p1, p2, p3] = initial.tetra;
let faces = makeTetraFaces(p0, p1, p2, p3);

makeTetraFaces is the method for generating outward-facing triangular faces from the tetrahedron's vertices.

function makeTetraFaces(
    p0: Point3,
    p1: Point3,
    p2: Point3,
    p3: Point3,
): Face3[] {
    const interior = centroidOfPoints([p0, p1, p2, p3]);
    const raw: Face3[] = [
        { a: p0, b: p1, c: p2 },
        { a: p0, b: p2, c: p3 },
        { a: p0, b: p3, c: p1 },
        { a: p1, b: p3, c: p2 },
    ];
    return orientAllOutward(raw, interior);
}

1. Use the centroidOfPoints method to get the centroid of the tetrahedron.

   function centroidOfPoints(pts: Point3[]): Point3 { let x = 0; let y = 0; let z = 0; for (const p of pts) { x += p.x; y += p.y; z += p.z; } const n = pts.length || 1; return { id: -1, x: x / n, y: y / n, z: z / n }; }

2. Construct triangular faces

   const raw: Face3[] = [ { a: p0, b: p1, c: p2 }, { a: p0, b: p2, c: p3 }, { a: p0, b: p3, c: p1 }, { a: p1, b: p3, c: p2 }, ];

At this point, the normals of the triangular faces are not necessarily facing outward.

1. Use the orientAllOutward(raw, interior) method to correct the normal orientation of all triangular faces.

   function orientFaceOutward(face: Face3, interior: Point3): Face3 { if (orient(face.a, face.b, face.c, interior) > 0) { return { a: face.a, b: face.c, c: face.b }; } return face; }

   function orientAllOutward(faces: Face3[], interior: Point3): Face3[] { return faces.map((f) => orientFaceOutward(f, interior)); }

In the orientFaceOutward method, you can see that if the determinant formed by the centroid and the triangle is greater than 0, it means the triangle's normal is facing inward. At this time, you need to swap any 2 points in the triangular face.

4-4-Incrementally Construct the Polyhedron

Iterate through the other vertices outside the tetrahedron, and incrementally construct a polyhedron with each vertex and the tetrahedron.

for (const eye of initial.rest) {
    const visible = faces.filter((f) => orient(f.a, f.b, f.c, eye) > EPS);
    if (visible.length === 0) continue;

    const horizon = findHorizon(faces, visible);
    if (horizon.length < 3) continue;

    const visibleKeys = new Set(visible.map(faceKey));
    const kept = faces.filter((f) => !visibleKeys.has(faceKey(f)));
    const interior = centroidOfPoints([...uniqueVertices(kept), eye]);
    const added = facesFromHorizon(horizon, eye, interior);
    faces = [...kept, ...added];
}

eye is the other vertex outside the tetrahedron. The reason it's called eye is because it needs to look at the tetrahedron and divide the tetrahedron into visible and invisible faces.

1. Find visible faces.

   const visible = faces.filter((f) => orient(f.a, f.b, f.c, eye) > EPS); if (visible.length === 0) continue;

The principle for determining visible faces is the signedness of the determinant formed by eye and the triangular face.

If no visible faces are found, it means eye is inside the tetrahedron, so continue, and iterate to the next point.

1. Find the boundary edges between visible and invisible faces.

   const horizon = findHorizon(faces, visible); if (horizon.length < 3) continue;

findHorizon is the method for finding boundary edges.

function findHorizon(faces: Face3[], visible: Face3[]): HorizonEdge[] {
    const visibleSet = new Set(visible.map(faceKey));

    type EdgeRec = {
        from: Point3;
        to: Point3;
        visible: boolean;
    };

    const byEdge = new Map<string, EdgeRec[]>();

    for (const f of faces) {
        const vis = visibleSet.has(faceKey(f));
        const directed: Array<[Point3, Point3]> = [
            [f.a, f.b],
            [f.b, f.c],
            [f.c, f.a],
        ];
        for (const [from, to] of directed) {
            const key = edgeKey(from, to);
            const list = byEdge.get(key) ?? [];
            list.push({ from, to, visible: vis });
            byEdge.set(key, list);
        }
    }

    const horizon: HorizonEdge[] = [];
    for (const recs of byEdge.values()) {
        if (recs.length !== 2) continue;
        const [r0, r1] = recs;
        if (r0!.visible === r1!.visible) continue;
        const visRec = r0!.visible ? r0! : r1!;
        horizon.push({ from: visRec.from, to: visRec.to });
    }
    return horizon;
}

Explain the logic of the findHorizon method.

① Generate a set of keys for visible faces

const visibleSet = new Set(visible.map(faceKey));

The face key is calculated by sorting the vertex positions. So as long as the vertex positions of a face are the same, its key is the same.

function faceKey(f: Face3): string {
    const ids = [f.a.id, f.b.id, f.c.id].sort((x, y) => x - y);
    return ids.join('-');
}

② Collect data for each edge in the polyhedron.

const byEdge = new Map<string, EdgeRec[]>();
for (const f of faces) {
    const vis = visibleSet.has(faceKey(f));
    const directed: Array<[Point3, Point3]> = [
        [f.a, f.b],
        [f.b, f.c],
        [f.c, f.a],
    ];
    for (const [from, to] of directed) {
        const key = edgeKey(from, to);
        const list = byEdge.get(key) ?? [];
        list.push({ from, to, visible: vis });
        byEdge.set(key, list);
    }
}

In the code above, first iterate through the faces of the polyhedron, get the visibility of each face, and declare the edge set of the face; then iterate through the edge set, using the edge as a key, and write set data into byEdge.

Data structure of byEdge:

{
	edge1 key:[
		{from, to, visible: visibility of adjacent face A},
		{from, to, visible: visibility of adjacent face B}
	],
	edge2 key:[
		{from, to, visible: visibility of adjacent face C},
		{from, to, visible: visibility of adjacent face D}
	],
	...
}

The edgeKey method can get the unique key of an edge.

function edgeKey(u: Point3, v: Point3): string {
    return u.id < v.id ? `${u.id}_${v.id}` : `${v.id}_${u.id}`;
}

edgeKey sorts by vertex id, so the key value for the common edge of different faces is the same.

byEdge can record the visibility of the adjacent faces for each edge.

③ Based on the byEdge data, find the boundary edges between visible and invisible faces.

A boundary edge has 2 adjacent faces, one face is visible, and one face is invisible.

const horizon: HorizonEdge[] = [];
for (const recs of byEdge.values()) {
    if (recs.length !== 2) continue;
    const [r0, r1] = recs;
    if (r0!.visible === r1!.visible) continue;
    const visRec = r0!.visible ? r0! : r1!;
    horizon.push({ from: visRec.from, to: visRec.to });
}
return horizon;

1. Construct new faces based on eye and the boundary edges.

   const visibleKeys = new Set(visible.map(faceKey)); const kept = faces.filter((f) => !visibleKeys.has(faceKey(f))); const interior = centroidOfPoints([...uniqueVertices(kept), eye]); const added = facesFromHorizon(horizon, eye, interior);

visibleKeys is the set of keys for visible faces.

Filter out the visible faces from faces based on visibleKeys, the remaining ones are the invisible faces kept.

Based on the invisible faces and eye, the centroid interior of the new convex polyhedron can be calculated.

Use the facesFromHorizon method to generate new outward-facing triangular faces added based on the centroid, boundary edges, and eye.

function facesFromHorizon(
    horizon: HorizonEdge[],
    eye: Point3,
    interior: Point3,
): Face3[] {
    return horizon.map((e) =>
        orientFaceOutward({ a: e.from, b: e.to, c: eye }, interior),
    );
}

The new triangular faces are generated by iterating through the boundary edges horizon and connecting them to eye. Of course, the orientFaceOutward method will also make the face normals outward based on interior.

1. Combine the invisible faces and the new faces into a new polyhedron.

   faces = [...kept, ...added];

4-5-Ensure Normals Face Outward

To avoid data errors, you can uniformly execute the orientAllOutward method again to ensure normals face outward.

faces = orientAllOutward(faces, centroidOfPoints(uniqueVertices(faces)));
return faces

Summary

In this chapter, we used Andrew's Monotone Chain algorithm to calculate the 2D convex hull, and used the incremental construction method to calculate the 3D convex hull.

Both of these convex hull algorithms are very classic and commonly used. There are many other convex hull algorithms, which I will not elaborate on one by one; you can expand on them as needed.

In practical work, convex hull algorithms have many uses, such as simplifying models, creating bounding volumes for models, and for collision detection.