Technical reports

Modelling and image generation

Heng Wang

145 pages

This technical report is based on a dissertation submitted July 1991 by the author for the degree of Doctor of Philosophy to the University of Cambridge, St John’s College.

DOI: 10.48456/tr-235

Abstract

Three dimensional (3D) volume representation, processing and visualisation have gained growing attention during the last ten years due to the rapid decrease in computer memory cost and the enhancement of computation power. Recent developments in massively parallel computer architectures and special purpose graphics accelerators also facilitate the solution of 3D volume manuipulation problems which usually have large memory and computation requirements. Volumentric graphics is becoming practically possible and finding many applications such as medical image processing, computer aided design and scientific visualisation.

A volumetric object is usually represented in one of two forms: a large 3D uniform grid of voxels (volume elements), and a relatively compact non-uniform collection of volumes. Objects in the latter form are obtained by adaptive, recursive decompositions. An octree is a special case in which each non-terminal volume is subdivided into eight sub-volumes. The problems of current implementation of octrees concern the speed and complexity of memory management. This dissertation looks into a novel approach of designing octree-related volumetric graphics algorithms based on Content Addressable Memories (CAMs). A CAM is an architecture consisting of elements which have data storage capabilities and can be accessed simultaneously on the basis of data contents instead of addresses. It is demonstrated that the main features of CAMs, their parallel searching, pattern matching and masked parallel updating capabilities, are suitable for implementing octree related algorithms.

New CAM algorithms are presented for transforming octrees, evaluating set operations (union, intersection, difference), displaying volumetric objects, calculating volumes, constructing octrees from other representations, and so on. These algorithms are remarkably simple and conceptively intuitive. The simplicity plays an important role in constructing robust solid 3D modelling systems. In addition to their simplicity, many algorithms are more efficient than their conventional counterparts.

A new method has been developed to speed up the image synthesis algorithm of ray tracing using CAM octrees. It is aimed to reduce the number of ray-object intersection tests without significantly increasing the overheads of storage and computation which are related to octree data structures and their traversals. The simulation results confirm the expected improvements in speed and memory management. Ray tracing can be accelerated by applying parallelism. Preliminary analysis shows possibilities of implementing the above CAM octree ray tracer on general parallel machines such as MIMD (Multiple Instriction stream, Multiple Data stream).

Full text

PDF (10.6 MB)

BibTeX record

@TechReport{UCAM-CL-TR-235,
  author =	 {Wang, Heng},
  title = 	 {{Modelling and image generation}},
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-235.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-235},
  number = 	 {UCAM-CL-TR-235}
}