AbstractThis paper addresses the problems of maintaining the consistency of spatial data under recursive subdivision algorithms for artificial terrain generation. Fractal modelling techniques are outlined, with particular reference to those based on fractional Brownian motion, and included is a brief history of recursive subdivision techniques. Existing polyhedral data structures are reviewed and shown to be inadequate for maintenance of consistency as polygons are subdivided. A new edge‐based data structure is presented which provides for the efficient use and consistent storage of spatial data under these conditions. The data structure is applicable to polygons of any order and allows neighbouring polygons of different order to be stored and subdivided. Artificial terrain is demonstrated from subdivision of the hexagon, of the quadrilateral and of a combination of hexagons, quadrilaterals and triangle