thesis.pdf (A4, 217 pages, 1.7M)

thesis.ps (A4, 217 pages, 20.7M)

This thesis introduces Triage Polygonization, a new fast polygonization method for quasi-convolutionally smoothed polyhedra. The polygonization method exploits the property that quasi-convolutionally smoothed polyhedra usually have predominantly planar surfaces with only edges and corners rounded.

A quasi-convolutionally smoothed polyhedron is represented implicitly as a density field iso-surface. Triage Polygonization subdivides the density field in a BSP-like manner and classifies the resulting cells as inside, outside, or intersected by the iso-surface. Planar surface areas usually lie on the boundary of cells and are extracted directly from the subdivided density field with minimal fragmentation. For cells intersected by the iso-surface a more general polygonization is performed. For quasi-convolutionally smoothing scenes with a small rounding radius Triage Polygonization is 20-30 times faster and outputs only 1-2% of the polygons of the Marching Cubes algorithm without compromising the approximation. The approach taken for Triage Polygonization can be extended to related problems.

High Speed
Low Fragmentation
Extraction of Unsmoothed Surface
B-rep for Zero Rounding Radius

Above image shows a hole punch polygonized with Triage Polygonization. The result is shown as a wire-frame representation in (a) and as Gouraud shaded polygons in (b).

Richard Lobb - Quasi-Convolutional Smoothing of Polyhedra

This paper describes a system for the representation and rendering of polyhedral scenes in which individual components can have different user-specified amounts of rounding applied to edges and corners. Objects are represented by structures similar to CSG trees but with arithmetic operators at internal nodes rather than set membership operators. An object's smoothing attribute specifies the radius of a spherical smoothing filter, and the smoothed object's surface is defined by an iso-density surface after low-pass filtering. The filtering is an approximation to true convolutional filtering, but allows rapid determination of iso-density surfaces. The rounded surfaces are similar to those achieved by use of filleting and surface blending techniques during modelling, but are much easier to specify, far more economical in storage, and simpler to compute. By varying the smoothing radii, a wide range of effects can be obtained, from near-perfect polyhedra through to "blobby models".

Back to home page

burkhard@cs.auckland.ac.nz