3D地形中的道路模拟

　　笔者注: 这篇文章是我本人在2009年发表在cppblog的一篇技术文章，因为个人技术博客迁移至博客园，因此转载到了此，非盗文。html

　　如下是正文：算法

　　前段时间被项目组长委派实现基于3D地形的道路系统。实现的目标是相似于Crysis编辑器的功能：能够由编辑人员在地面上指定一系列控制点，用某种合适的曲线插值生成一条道路，指定纹理后就能够智能地将道路显示出来。编辑器

　　然而要实现这些功能，必须克服如下的几个难题：
（1）用哪一种曲线能够方便模拟出道路段，并且能够灵活地调节？
（2）地形一般都有Lod优化，其网格会实时变化，如何获取道路段覆盖的地形网格？如何让道路恰好“贴”在地表上而不会产生交叉,融合,断裂现象？
（3）如何生成道路顶点的纹理，才能不让纹理产生扭曲或其它不许确的现象？

　　刚刚接到任务时，一头雾水，无从下手。因而急忙搬出google大哥，从gameres驰骋到gamedev，从项目组长询问到网上认识的高手，都没有找到道路实现的相关资料和有效的解决方法。

　　后来研究了一下Crysis编辑器的道路系统操做和线条生成模式，而且在有着十几年游戏开发经验的Dunhill兄指点迷津下，终于找到了一些眉目，通过半个月多的摸索和调试，终于在今天比较完整地将道路系统实现了。因为网上资料少，特撰此文，若是之后有人也作到相似的专题，但愿能够提供一些有用的信息。

　　首先，将编辑人员指定的道路控制点用样条曲线生成一系列平滑过渡的道路段顶点。样条曲线有不少种，通过比较，我采用了B样条曲线，感受它能够比较好地控制道路的弯曲，并且又不乏道路的平滑特性。由此解决了文章开头提出的问题（1）。效果以下图：
　　优化

　　上图有6个控制点，通过插值生成了一系列中间过渡点，从而将控制点连成了比较平滑的道路骨架。对于样条曲线插值的生成方法，网上不少资料，这里就不详细讨论了。google

　　接着，将生成的道路曲线分拆成一个个四边形（咱们不妨称之为道路单元段），将这些四边形覆盖的地形图元提取出来。因为地形Lod是不断变化的，若是道路随着地形Lod变化就不断提取地形图元会使得效率很低下。通过一番研究，发现若是地形Lod作得足够好的话，由地形Lod变化而产生的地形Pop现象对道路影响不大，彻底能够提取道路在地形最高Lod时覆盖的图元数据，由此解决了开头提出的问题（2）。注意在提取图元的时候要彻底按照地形构造的规则进行提取，不然有可能出现道路和地形相交合或分离的问题。spa

　　提取了某个道路单元段覆盖的地形图元后，将该道路单元段的四个顶点构造出四个垂直于水平面的裁剪面，将地形图元和构造的裁剪平面做为参数送入裁剪程序。裁剪程序一般是用三维齐次坐标的区位码标志裁剪方法，这个算法在《计算机图形学》一书有说起，网上也有该算法的详细描述。将裁减后的道路单元段连接起来后的效果以下图：
　　3d

　　黄色线条是地形图元，黑色的线条是道路的图元。能够看出，通过裁减后的道路增长了不少顶点和线条来连接道路和地形的相交点，这样作是为了防止道路与地形可能出现的交叉、分离和断裂现象。调试

　　裁剪完道路单元段后，给每一个道路单元段的顶点生成纹理坐标。尝试了不少方法，最后采用的纹理映射方法是以下：htm

　　见上图，v0、v二、v三、v5是道路单元段的顶点，v一、v4分别是v0与v二、v3与v5的中点，v1到道路起始点的中轴线累积长度totalL，另外求出顶点到道路单元段的四个边距L一、L二、L三、L4和中轴线长L。
　　纹理坐标u = L2 / (L2 + L4)
　　纹理坐标v = （totalL + L * L1 / (L1 + L3) ) / tileLength （tileLength是纹理的格子长度，可由编辑人员调节）

　　这种纹理映射方法在道路不是很弯的状况下，都能比较好地生产纹理图。但若道路弯曲得比较厉害，纹理也会出现扭曲。若是哪位能提出更好的纹理坐标生成方法，请告知。生成纹理坐标后,记得给道路顶点高度往上平移一点点(我取了0.01f),这样能够避免道路和地形因为Z值相同而产生闪烁现象.blog

　　最后发一张贴上纹理的道路效果图，若有什么问题欢迎留言探讨。