5 replies to this topic

[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).

Edited by luca-deltodesco, 27 June 2012 - 05:32 PM.

[szecs]

Why don't you triangulate while at it?
I don't understand every aspect of your algorithm, but it seems similar to the algo I had in mind (though I only implemented a 2D version).
if you find a candidate triangle, why don't you just use the indices of them to fill the triangle list on the spot?

Maybe my algo is different, it's something like this:

RecursiveFunction(triangle_normal, current_edge) // edges are defined by the two end vertex indices, and should have a consistent vertex winding (CCW)
{
	 calculate current_edge_vector using the consistent winding;
	 Perp_edge_vector = normalize( current_edge_vector cross triangle_normal);
	 // this vector points away from the triangle, perpendicular to the current edge and perpendicular to the triangle_normal

	 loop through all the vertices
	 {
	 	 Perp_vector_new = normalize( current_edge_vector cross potential_triangle_normal); // I'm not sure about signs here
	
	 	 Find next vertex:
	 	 	 with the biggest dot product between Perp_edge_vector and Perp_vector_new
	 } // no need to do extra checks, if the first triangle is selected correctly, only convex edges can occur now.

	 if( triangle is not constructed yet ) // ATM i can only think of looping through all already constructed triangles to check
	 // there's got to be a better way
	 {	 With the found vertex and the current edge, build a new triangle, and add the vertex indices to the triangle list;

	 	 call RecursiveFunction(new_triangle_normal, second_edge);
	
	 	 call RecursiveFunction(new_triangle_normal, third_edge);
		  // one of the edges of the new_triangle is the same as the current_edge fed to recursiveFunction. So no need to call the function for the third neighbour triangle
	 }
}

......

BuildConvexHull()
{
	 Get the first triangle: the first three vertices on one of the axes // I'm not sure about this one....
	 Store indices in the triangle list;

	 call RecursiveFunction(first_triangle_normal, first_edge):
	 call RecursiveFunction(first_triangle_normal, second_edge):
	 call RecursiveFunction(first_triangle_normal, third_edge):
// maybe you don't even have to call the third one, because I think the convex hull will be complete by this time
}

No sorting in this algo, except for the rather trivial one to fist the first triangle.

Edited by szecs, 28 June 2012 - 01:12 AM.

[szecs]

Wait.
I have found some mistakes, so I'm still editing the post.

[Inferiarum]

Why not just implement the quick-hull algorithm you mentioned

[luca-deltodesco]

Quick hull does not give you a way of triangulating the surface of the hull, only find it's points.

I implemented a 3d graham scan in the end which with some additional cases for degeneracies has proved stable and fast enough.

[Inferiarum]

Since the Quickhull algorithm iteratively improves an inner approximation of the convex hull you need to calculate the normals of faces of the inner approximation and you can store the points of those faces too if you want to.

But if you found something that works I guess you should stick to that.