Abstract
Fractals with Iterated Function Systems (IFSs) can be used in two applications: object modeling and image compression. However, there are problems on both of the applications to be solved.For modeling 2D or 3D graphic objects, we point out two significant problems that deter the ongoing development of fractals. The first problem is where fractal objects are. It is necessary to compute the bounding extent of a fractal object before the rendering procedure. Unfortunately, the current bounding extents were determined by trial and error methods. We develop an algorithm to compute tight bounding boxes of fractal objects. The second problem is how to determine the intersections of rays and fractal objects. The intersection problem is a prerequisite of rendering 3D objects with ray tracing. We develop another algorithm, called stencil tracing, to compute the intersections of rays and fractal objects. Based on the solutions, we are able to draw 2D fractal pictures at any resolution and to render fractal objects in synthetic 3D scenes.On the other hand, we tackle the obstacles of fractal image compression. Fractal image compression is notorious for its very slow encoding procedure. Thus we suggest a new coding scheme to accelerate the encoding procedure. In fractal image compression, an image is divided into overlapped domain blocks and non-overlapped range blocks. For each range block, the mapped domain block that is affine-similar to the range block is determined. The collection of the affine mappings forms a Partitioned Iterated Function System (PIFS). The time consuming problem comes from massive computation needed for searching a best match among a multitude of range-domain block pairs. In the past, people exploited block classification algorithms or fast greedy searching algorithms to solve the problem. We give another approach. We try to build indices onto the domain image. Only those range and domain blocks with same index keys are compared. The domain indexing technology is different from variant domain classification ones because we don’t cluster all of the domain blocks really. Thus we can accelerate the encoding procedure on a large scale. We consider the efficiency of the decoding procedure in our new scheme, too. We investigate the kernel of a partitioned iterated function system that must be computed iteratively. Thus it also benefits from the speed-up of decoding images.