This work is framed within the context of computer graphics starting out from the intersection of three fields: rendering, information theory, and complexity. Initially, the concept of scene complexity is analysed from a geometric visibility point of view. Then, the main focus of this dissertation, the development of new refinement criteria for the global illumination problem is presented. Firstly, based on Shannon entropy, a set of pixel measures are defined. They are applied to supersampling in ray-tracing as refinement criteria, obtaining a new entropy-based adaptive sampling algorithm with a high rate quality versus cost. Secondly, based on Harvda-Charvát-Tsallis generalised entropy, new refinement criteria are defined for hierarchical radiosity. Oracles based on transported information, information smoothness, and mutual information are presented, with very significant results for the latter. And finally, three f-divergences are analysed as refinement criteria. These measures give us a rich variety of efficient and highly discriminative measures which are applicable to rendering in its pixel-driven (ray-tracing) and object-space (hierarchical radiosity) approaches.