language: en

Efficient Rasterization of Implicit Functions

Torsten Mller and Roni Yagel
Department of Computer and Information Science The Ohio State University
Columbus, Ohio
-moeller, yagel-@cis.ohio-state.edu

Abstract Implicit curves are widely used in computer graphics because of their powerful features for modeling and their ability for general function description. The most popular rasterization techniques for implicit curves are space subdivision and curve tracking. In this paper we are introducing an efficient curve tracking algorithm that is also more robust then existing methods. We employ the Predictor-Corrector Method on the implicit function to get a very accurate curve approximation in a short time. Speedup is achieved by adapting the step size to the curvature. In addition, we provide mechanisms to detect and properly handle bifurcation points, where the curve intersects itself. Finally, the algorithm allows the user to trade-off accuracy for speed and vice a versa. We conclude by providing examples that dem-onstrate the capabilities of our algorithm.

1. Introduction