CS679 - Simplifying Spline Models

Introduction

My project involved simplifying spline models to produce a series of approximations to the original model. The algorithm operates directly with a spline model consisting of cubic triangular bezier patches. The simplification process attempts to merge adjacent patches to reduce the number of patches in the model while attempting to keep the error between the simplified form and orignal form as small as possible. This project is based on a paper by Gopi and Manocha [1].

Model simplifications has many applications in computer graphics.

• Accelerating rendering
• View-dependent tessellation
• Progressive transmission.
• Level-of-detail models for games and other visualization applications.

Algorithm

The algorithm iteratively simplifies a model by removing vertices. At every iteration a search is done to find vertices that are suitable to be removed. To remove a vertex all the surrounding patches must be collapsed such that there are only two faces. Then the vertex can be removed.

A predefined set of patch topologies are defined that can be successfully merged. The search algorithm performs a depth first search of the model to find as many instances of the patterns as possible. Once all the patterns have been found the patches in these patterns are merged.

A more detailed look at the algorithm and the techniques used can be found in the talk I gave for this project.

Results

This example shows a sphere rendered with the cubic bezier patches as well as the corresponding wire-frame rendering. The simplification process can easily be seen in the wire-frame rendering. The bezier patch rendering shows that the simplification process has little effect on the shape and continuity of the sphere.

5500 patches	4000 patches	2500 patches

This example shows a more complicated model. This initial model is on the far left. The simplification process does a good job of reducing the face count but at the same time maintaining the features of the model. The only problem is that the continuity of the simplification is not maintained. There are noticeable ridges and discontinuities as the simplification proceeds. Further iterations of the model only compound this behaviour.

49000 patches	36000 patches	27000 patches

This examples shows another complicated model. This model has a large number of initial patches. The results seem better than those produced with the cow model. Unfortunately, further iterations show that as the simplification proceeds, the problems that arose early in the cow model simplification are also apparent.

Problems

• Improve the continuity by re-implementing the swap diagonal and merge patches operations to enforce continuity requirements with adjacent patches.
• Improve control over pattern matching. In particular the method for relaxing constraints using thresholds can be improved with a more dynamic relaxation rather than simply incrementing the threshold at every step.
• Improve the graph searching algorithm to find the best matching out of a set of possible matchings instead of choosing the first matching found.
• Introduce a method of moving boundary points to improve quality the quality of patches and likelihood of patches being mergable (this is briefly discussed in the paper [1] but the details were not provided).

References

Talk

For my project I also gave a talk that describes the techniques I used and also has more results.