It looks like they did a simple animation in C4D or a similiar application - though it could be done with Mettle ShapeShifter, Zaxwerks or even the shatter effect in AE to create the shapes.
The tricky part is the tracking. Try some google searches for Mocha Planar tracking. I think there are some AdobeTV too(Mocha comes bundled with AE) That's how they get the camera move and objects to match up together. Depending on the shot though you could use AE's on board tracker and get a good result.
Some tracking tutorials, these deal with text, but should give you a pretty good start on working out how to accomplish this.:
"I have not failed 700 times. I have succeeded in proving that those 700 ways will not work. When I have eliminated the ways that will not work, I will find the way that will work."
---THOMAS EDISON on inventing the light bulb.