Direction relations between extended spatial objects are im- portant commonsense knowledge. Recently, Goyal and Egen- hofer proposed a formal model, called Cardinal Direction Calculus (CDC), for representing direction relations between connected plane regions. CDC is perhaps the most expressive qualitative calculus for directional information, and has at- tracted increasing interest from areas such as artificial intelli- gence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking consistency of basic CDC constraint networks. As one byproduct, we also show that any consistent network of CDC constraints has a canonical realization in digital plane. The cubic algorithm can also been adapted to cope with dis- connected regions, in which case the current best algorithm is of time complexity O(n5).