Hierarchical 4-K Meshes

Hierarchical 4-K Meshes constitute a powerful framework for variable-resolution representation of surfaces, as well as, for adaptive computations on 2D manifolds. The framework is integrated by a data structure, together with a set of procedures that operate on it.
We have developed methods for constructing 4-K meshes based on subdivision, adaptive refinement, and simplification. We have also implemented operators for mesh extraction, interrogation and conversion to other representations.
The figures below illustrate the expressiveness of the 4-K structure. These meshes conform to various adaptation criteria, including: gradual change in resolution; region segmentation; and point location. We used simplification (left) and subdivision (center, right) to generate the underlying hierarchical structures.

Papers

	Variable Resolution 4-K Meshes: Concepts and Applications (Computer Graphics Forum, 2000) This paper describes the variable-resolution 4-K data structure. It also gives an overview of construction methods, including: subdivision, refinement and simplification.
	A Unified Approach for Hierarchical Adaptive Tessellation of Surfaces (Transactions on Graphics, 2000) This paper introduces a method for adaptive tessellation of parametric and implicit surfaces. It employs a refinement algorithm that generates hierarchical 4-K meshes.
	Four-Face Cluster Simplification (Shape Modeling International, 2001) This paper presents a simplification algorithm based on edge swaps and vertex removals that produces a 4-K mesh hierarchy.
	Hierarchical Generalized Triangle Strips (Visual Computer, 1999) This paper develops a methodology for maintaining a path on a triangulation under refinement.