Historically, computer graphics algorithms have been optimized for locally smooth surfaces. These methods fail when the surface is very rough or, in particular, fractal. This dissertation outlines the shortcomings of current computer graphics techniques for rendering fractal shapes. It then proceeds in developing and describing new efficient techniques for rendering a subset of fractal surfaces called linear fractals.

The dissertation is separated in tree sections. The first of the, Analysis, provides a mathematical framework for linear fractals. It begins with a formal treatment of iterated function systems, followed with a parallel discourse on recurrent iterated function systems. The iterated function system, along with its recurrent generalization, provides a fundamental theoretical model for linear fractals.

This part’s third chapter compares and contrasts different definitions of the adjective “fractal.” It concludes with a new definition, that of “locally fractal,” which is justified with several examples. A discussion of linear and affine maps, the definition of linear fractal, and a summary of methods for measuring the dimension of linear fractals conclude the Analysis part of this dissertation.

This dissertation’s second part, Modeling describes techniques for creating linear fractals. It begins with a comparison of implicit and explicit models, showing, algorithmically, how the recurrent iterated function system model can be treated as both. The next chapter discusses The collage theorem as a philosophy for modeling linear fractals. The third chapter details three interactive methods for automatically modeling objects as linear fractals, determining the recurrent iterated function system computationally.

The third part - the main part - of this dissertation, Rendering, describes methods for displaying the linear fractal described by a recurrent iterated function system. It begins with an outline of current methods, showing their shortcomings when applied to fractals in general.

The next four chapters of this part are devoted to describing methods for determining occlusion - solving the hidden surface problem. Ray tracing is the technique employed for this end, and efficient methods for finding the intersection of a ray with a linear fractal are developed. This includes determining the necessary level of detail by deriving the size of a pixel in object space, and computing an initial set that optimally contains the linear fractal.

Next, a shading method is developed, designed to allow the viewer to perceive fractal surface orientation, though not intended to be analytically correct. Finally, a chapter on the antialiased rasterization of linear fractal silhouettes, often fractals themselves, concludes this part of the dissertation.

A conclusion exhibiting the results of these methods and suggesting further research follows. Two appendices, one reviewing basic metric space theory, the other documenting the recurrent iterated function system codes used to generate the illustrations that decorate this dissertation, are found at the end of this dissertation.

PDF

Hart, J. C., Computer Display of Linear Fractal Surfaces, Submitted as partial fulfillment of the requirements of the degree of Doctor of Philosophy in Electrical Engineering and Computer Science, Graduate College, University of Illinois at Chicago, Chicago, IL, May 1st, 1991.