Haptic rendering of large and detailed virtual objects can require a significant computational load. Built out of a vast number of primitives, the object models can strain algorithms such as collision detection and constrained optimization, which are widely used in haptics applications. Nevertheless, to provide the necessary fidelity, haptic servo loops need to operate at 1 kHz or above. Separating the haptic processes from the more time consuming processes has long been a standard technique to protect more sensitive servo loops from the computational burden of collision detection and graphic display. In addition, local approximation techniques have been developed to allow fast update rates on small areas of the over-all model around a known contact point. Operations on the complete model are only executed at a much slower rate. However, none of the existing methods fully exploit the model's topological information. We propose the use of the Quadedge data structure to store the object model in addition to a hierarchical data structure used in collision detection. The compact, edge-based graph structure provides a topological map and the necessary tools to navigate easily along the model's surface. Also, we propose to use a velocity vector as an indicator of the intended user's motion. Such information leads to the prediction of the user's position within a short time frame. The proposed methods allow us to efficiently build local intermediate models based on predictions of the contact point movement.