According to this tutorial, a convex hull is the most accurate shape one can build from a mesh? I have two questions regarding this:

1. How do I build a convex hull from a given, complex mesh in Bullet?
2. Should this be done offline? How do most people do this? (that is, create a collision shape from a mesh in games)

Yes, a convex hull is the tightest bounding shape.  Think of it like shrink-wrap around an object.

For complex shapes the convex hull can still be an extremely complex object when used in physics, potentially with hundreds or even thousands of faces or even more, although game objects rarely use that many vertices. There are convex hull generation algorithms that use a smaller number of objects by combining faces that are facing in nearly the same direction.

For how to build them, I believe you can use btConvexHullShape in Bullet to create the shape for you automatically. 

For doing it offline, yes, it is quite common for game modelers to create physics objects in addition to the graphical model. Usually the collision shape is much simpler than the visual shape.

This is how you do it:

void VertexBuffer::CreateConvexHull()
{
    btConvexHullShape convexHullShape(
        m_pPositions->GetVertexData(), m_pPositions->GetNumVertices(), m_pPositions->GetStride()*sizeof(float));
   //create a hull approximation
    convexHullShape.setMargin(0);  // this is to compensate for a bug in bullet
    btShapeHull* hull = new btShapeHull(&convexHullShape);
    hull->buildHull(0);    // note: parameter is ignored by buildHull
    btConvexHullShape* pConvexHullShape = new btConvexHullShape(
        (const btScalar*)hull->getVertexPointer(), hull->numVertices(), sizeof(btVector3));    
    m_pDynamicShape = pConvexHullShape;
    delete hull;
}

Note: btShapeHull is a class to reduce the polygon count in btConvexHullShape (otherwise btConvexHullShape preforms very poorly)

Also note:  some extra padding is created around the object, for unknown reasons and that makes them seem to float a bit above the ground when they are dropped.
Setting the margin parameter to zero won't work, because that parameter is actually ignored. That's why I call
convexHullShape.setMargin(0);
before creating the btShapeHull.

12 hours ago, frob said:

For doing it offline, yes, it is quite common for game modelers to create physics objects in addition to the graphical model. Usually the collision shape is much simpler than the visual shape.

After the modeler creates a physics object of the model he made, how is it loaded into Bullet?