Extreme Simplification and Rendering of Point Sets using Algebraic Multigrid

We present a novel approach for extreme simplification of point set models in the context of real-time rendering. Point sets are often rendered using simple point primitives, such as oriented discs. However efficient, simple primitives are less effective in approximating large surface areas. A large number of primitives is needed to approximate even moderately simple shapes. However, often one needs to render a simplified version of the model using only a few primitives, thus to trade accuracy for simplicity. For this goal, we propose a more complex primitive, a sort of splat, that is able to approximate a larger and more complex surface area than the well-known oriented disc. To construct our primitive, we first decompose the target surface into quasi-flat regions, using an efficient algebraic multigrid algorithm. Next, we encode these regions into splats implemented using planar support polygons textured with color and transparency information and render the splats using a special blending algorithm. Our approach combines the advantages of mesh-less point-based techniques with traditional polygon-based techniques. We demonstrate our approach on various models