Your pictures remind me of the space of phylogenetric trees (which is cubical and exhibits similar folding), so if you are interested in reading about very concrete such examples, you might take a look at:

- L. Billera, S. Holmes, K. Vogtmann, Geometry of the space of phylogenetic trees, Advances in Applied Math, 27 (2001), no. 4, 733-467.
- M. Owen and S. Provan, A fast algorithm for computing geodesic distances in tree space, IEEE/ACM Trans. Computational Biology and Bioinformatics, 8: 2-13, 2011.
- F. Ardila, M. Owen and S. Sullivant, Geodesics in CAT(0) Cubical Complexes, Advances in Applied Math. 48 (2012), 142-163.

(1) proves uniqueness of geodesics in tree space, (2) gives a polynomial time algorithm to find geodesic distances, and (3) works in more generality.

Metric Spaces of NonPositive Curvature, 2009) seems perfect, even freely downloadable as PDF (in comparison to 122 $US to purchase new!)---Thanks! – Joseph O'Rourke Jul 14 '12 at 1:48