Augmented reality applications on hand-held devices suffer from the limited available processing power. While methods to detect the location of artificially textured markers within the scene are com- monly used, geometric properties of three-dimensional objects are rarely exploited for object tracking. In order to track such geometry efficiently on mobile devices, existing methods must be adapted. By focusing on key behaviors of edge-based models, we present a sparse depth buffer structure to provide an efficient rasterization method. This allows the tracking algorithm to run on a single CPU core of a current-generation hand-held device, while requiring only minimal support from the GPU.