一种基于包络控制的三角形收缩简化三维几何模型的新算法

A New Algorithm for Simplifying 3D Geometric Models Based on Triangle Contraction Confined by Envelopes

本文算法先将原始模型上的每一点沿各自的法矢量方向偏移一定的距离 ,使整个原始模型收缩或扩张 ,生成内外两层包络 .在构造包络时采用了一维搜索中的二分法来逼近最佳偏移值 ,以保证原始模型尽可能简化 ,然后依次选择原始模型上的一些三角形 ,将其三个顶点合并 ,收缩成一个三维点 .如果这样收缩简化后的模型依然位于两层包络围成的空间中 ,则收缩操作产生的误差被认为是可接受的 ,这也就保证了简化模型与原始模型外形上的相似 .同时 ,本文还设计了一个演示系统 ,实现了这种算法 .实验结果表明 ,通过这种算法简化三维几何模型后 ,简化模型不仅具有一定的压缩率 ,而且保留了原始几何模型的尖锐特征 。

We put forward a new algorithm of simplifying a 3D geometric model in this paper, which unites the triangle contraction simplification with the error controlled by the original geometric model's envelope. The 3D geometric model will be simplified at a high efficiency using our algorithm and our algorithm ameliorates the method of envelope's conformation proposed by Cohen. We firstly excurse every vertices of the original model a certain distance respectively along the direction of its normal vector to shrink or expand the original model. So an inside envelope or an outside envelope are created, which are used to control the error resulted from simplifying operation on the original model. When the envelopes were creating, the method of dichotomy in linear search is used to approach the best offset-value in order to simplifying the original model as possible. And then, we select some triangles, move each three vertices to a same position. If the simplified model after such a contract operation is still within the volume encircled by two envelopes, the error introduced by the operation is considered to be acceptable, and it is able to hold a similar shape between simplified model and its original model. And we have developed a demo system to verify this algorithm. The results from our experiment show that the simplified model by our algorithm is of a higher resemblance with its original geometric model and is of a higher efficiency.