luca-deltodesco

Trying to work this through myself without looking at other complete algorithms.

Taking set of 3d points, and computing convex hull formed by triangles.

What I have so far (as a candidate solution; doesn't need to be more optimal), based on quick-hull ideas:

fun convex_hull(points) {
	// cannot form a hull
	if (points.length < 3) return []

	// trivial; degenerate hull formed by points
	if (points.length == 3) return [points, [points[0], points[2], points[1]]]

	sort points lexicographically along axis (1, 0, 0)
	p0 = points[0]
	p1 = points[sorted.length - 1]
	p2 = point furthest from line containing p0, p1

	fun recurse(points, p0, p1, p2) {
		n = normal(p0, p1, p2)
		discard p from points where p in [p0, p1, p2] or (p-p0) dot n < 0

		if (points.length == 0) return [p0, p1, p2]
		else {
			 sort points lexicographically along axis n
			 return recurse(points, p0, p1, p3) concat
					recurse(points, p1, p2, p3) concat
					recurse(points, p2, p0, p3)
	}

	candidates = recurse(points, p0, p1, p2) concat recurse(points, p0, p2, p1)

    // remove any triangles not part of hull
	discard (p0, p1, p2) from candidates where exists p in points s.t (p - p0) dot normal (p0, p1, p2) > 0

    // remove any degenerate triangles (still allowing 0-area triangles).
    discard (p0, p1, p2) from candidates where p0 == p1 || p0 == p2 || p1 == p2

	return candidates;
}

Now, this works for some test cases (including simple (perfect) boxes) in that it gives me a set of triangles which as a whole can unify to give the convex hull, but i'm interested in how you can take this further to produce a minimal set of triangles as many of the triangles returned by this implementation will be overlapping.

I imagine that without drastically changing the algorithm, you could identify those triangles that are coplanar, collect vertices, order by angle in plane and do a trivial triangulation as a fan. But I would worry about numerical issues with determining coplanar planes in the general case here.

I've so far avoided that I can tell numerical issues by doing a lexicographical sort (which in the general case involves computing a tangent and bitangent for the given axis to additionally project onto for the sorting if projections on primary axis are equal).