This short research paper looks at the problem of affine transformation of vertices defining a rigid body. The interesting and common case is when many vertices lie on or close to a small number of straight lines. If this can be detected, and the vertices effectively placed into groups on lines to within a specified tolerance, then the processing of the geometry needed for transformation (prior to, say, rendering) is simplified. One goal is to remove about half of the vertices, and about one third of the clipping overhead.

The problem is thus reduced to the optimization problem of finding a good (or best) set of lines, so that as few vertices as possible will need to be calculated. A relatively simple recursive branch-and-bound algorithm is found to be sufficient, and this fact is itself elegant. The algorithm has been tested on a number of practical meshes. Given some fine-tuning of the tolerance for the linearity, the results are good, and give real improvements within real examples. Whether or not this is merely an artifact of the examples chosen is not completely clear.

The paper is well laid out, well illustrated, and easy to follow, even for those not especially well versed in the area of study. A sparse but relevant set of references is supplemented by a Web site, from which much further detail can be obtained, and source code and results downloaded.