Solid Modelling 

 
 

Contacts

Secretary:
Marilyn Dodd
Tel: (+44) 191 222 6213
Fax: (+44) 191 222 8600
 
Investigator:
Dr. Clive Grant
Postgraduate Admissions:
 Prof.G.J.Johnson 
 
Complex [2D] and [3D] shapes can be represented in a highly compressed form known as a Quadtree and Octtree respectively.  These representations are easy to manipulate and economical to store in a computer. 
    Computer procedures have been implemented to create, store, recall, transform and display compressed images directly in coded form, independently of the storage mechanism used.  The application has been implemented with Delphi 2 from an earlier Turbo Pascal 7 DOS version.  The DataStream mechanism was transferred intact and unmodified to implement a single bitplane Leafcode storage mechanism. Extension to multiple bitplanes and to [3D] Octtrees is very sraightforward. 

The figure shows the Windows Quadtree imlementation with graph, tree and bitstream views of a quadrant section.  The graph view display resolution is set to 6 bits( 64x64) but the quadtree has a resolution of 8 bits (256x256).  The view automatically uses the extra two bits of resolution in a post-order traversal to display grey pixels to improve anti-aliasing at the boundaries. 

The general aim is to create a generic (abstract) quadtree component TQuadtree that will contain all of the methods for manipulating quadtrees such as creation, pre-order and post-order traversing, merging (AND, OR, XOR etc.), searches (block containing a point, a rectangle) and linear geometric transformations(shift, scale, rotate, shear). All of the methods that rely on a particular storage mechanism, namely the block and file transfer operations, are abstract meaning that no code is provided for them in the TQuadtree object.  These methods must be implemented in any derived component such as TLeafCode.  Virtually all operations (create, display, merge, search, transform) on quadtrees employ a generic pre-order or post-order traversal method. 
     TQuadtree is a non-visible Delphi component that employs a series of viewer components to display the structure in graphic views, tree views, bit stream views, block views and geometry views etc.  The viewers are given type identifiers TxxxView with instances identified as XxxView where xxx is Graph, Tree etc.  Each view has a TQuadtree property and a TImage, TMemo or TStringGrid property to implement the view. A start has been made on the Graph View (TImage), bit stream view (TMemo) and Tree View (TTreeView) in the main unit. The figure shows the main form implemented in the test unit with the views incorporated directly into the main form. 

 
 

 
  
Page Design:  Clive Grant  with  Acknowledgments. Updated: 6 June, 1998