A model predictive control law (MPC) is given by the solution to a parametric optimization problem that can be pre-computed offline, which provides an explicit map from state to input that can be rapidly evaluated online. However, the primary limitations of these optimal explicit solutions are that they are applicable to only a restricted set of systems and that the complexity can grow quickly with problem size. In this paper we compute approximate explicit control laws that trade-off complexity against approximation error for MPC controllers that give rise to convex parametric optimization problems. The algorithm is based on the classic double- description method and returns a polyhedral approx- imation to the optimal cost function. The proposed method has three main advantages from a control point of view: it is an incremental approach, meaning that an approximation of any specified complexity can be produced, it operates on implicitly-defined convex sets, meaning that the prohibitively complex optimal explicit solution is not required and finally it can be applied to any convex parametric optimization problem. A sub-optimal controller based on barycentric in- terpolation is then generated from this approximate polyhedral cost function that is feasible and stabiliz- ing. The resulting control law is continuous, although non-linear and defined over a non-simplical polytopic partition of the state space. The non-simplical nature of the partition generates significantly simpler approx- imate control laws, which is demonstrated on several examples.