3维地形的金字塔上下采样局部实时简化算法

在大型三维地理信息系统中，往往需要在预加载整体地形数据的基础上，对局部地形数据重新构建三角网，用于物理模拟等应用。针对这一问题，本文提出了一种三维地形的金字塔“上下采样”局部实时简化算法，实现对局部三角网地形实时高效的简化。该算法基于图像金字塔思想，通过对原始地形的三角格网执行“下采样”和“上采样”，结合“预测残差”对“下采样”的地形做局部简化，简化后的三角网十分逼近原始的高精度三角网。本文将该算法用于GeoBeans 3D平台的汽车驾驶模拟系统中。该算法生成的地形简化且稳定，随着汽车活动范围的变化，按需销毁及重构更新地形。实验证明，当预测残差阈值取0.1时，三角形个数能简化到原始数量的2/3；阈值取0.2时，三角形个数可以简化到原始个数的1/4左右。由此可见，在视觉精度允许的范围之内，该算法对地形的简化效果较好，且耗时少，满足了三维系统及车辆驾驶模拟的实时性。

Local real-time simplification algorithm for three-dimensional terrain using up and down sampling and pyramid theory

In a large three-dimensional Geographic Information System (GIS), we usually reconstruct a triangular network on the local terrain on the basis of the complete preloaded terrain data for some specific applications such as a physical engine. In order to handle this problem, we propose a real-time algorithm for local three-dimensional terrain simplification, by using up and down sampling and the pyramid theory. This algorithm executes the down sampling and the up sampling at the triangle grid of the original terrain, then performs the partial revision with the predicted residuals in specific regions, and finally obtains the fine terrain triangular network, which is considerably similar to the original terrain. We have applied this algorithm to the simulation of a vehicle driving application in our GeoBeans three dimensional system. The terrain constructed by this algorithm is simplified and stable. It will be updated according to the range of the vehicle and be destroyed or reconstructed as needed. Our test shows that if the threshold of the predicted residuals is 0.1, the number of triangles will reduce to 2/3 of the original number; if the threshold is 0.2, the number of triangles can almost reduce to 1/4. Hence, as demonstrated here, in the visual precision permitted range, this algorithm results in a good terrain simplification with little time consumption, and it satisfies the request of real-time simplification for a three-dimensional system and the simulation of a vehicle driving application.