The footage you have attached of the Alamo Cube is a lock-off shot. Here the Camera calibrator is the way to go. The cube is then the Coordinate system. Since it was shot with longer lens there is little parallax in the shot, so it needs to be done very carefully.
If the anything moves, try to get some “pre-roll” footage that starts with a different angle to the cube, that will help to find the the camera path.
Not a complete list of tips, as you can imagine, some good people have filled books with this.
In any case, shoot a lens grid, and measure the object, as well the starting and perhaps end distance of the camera. This place has AFAIK, rectangular floor “tiles”, perhaps a good support to measure the positions. Write down the lens used and the exact type of the camera. If you shoot with RED, the resolution used (not the delivered one) for this shot is crucial as well. In any case, shoot stills from the set and set up. IF possible place some markers in the scene, that can be anything that is dull and different in color, measure those as well.
There is a longer series about Motion and object Tracking here on Cineversity.
Besides that , the Books from Tim Dobbert (2nd Edition) “Matchmoving"and Erica Hornung “The Art and Science of MatchMoving” are my favorites.
Would I say that any shot is solvable, perhaps not, but the more you know and the camera is prepared (receives information), the more it will be possible.
In the moment you have the axis of the cube, you can wrap the cube, but keep in mind, that needs to be composite. So, anyone/anything covering the cube, will have the need to be rotoscoped.
My best wishes