中山大学 地理科学与规划学院 广州 510006
摘 要：可编辑的大型三维WebGIS具有一定的应用场景需求，常见的3D Tiles数据格式局限于静态场景渲染，在编辑的三维场景中，需要构建动态的3D Tile文件格式和多细节层次(level of detail，LoD)渲染方法。本文从动态空间索引和多细节层次技术两方面研究Web在线编辑大型三维场景的构建方法，将动态松散八叉树和半边折叠LoD构建算法应用于3D Tiles构建流程中，实现支持可编辑场景的3D Tiles构建与更新。结果表明：①松散八叉树索引在计算量上能够实现动态更新的目标，且在视锥体剔除上有着良好的精度；②基于半边折叠法进行准实时LoD的构建，能够满足动态场景下实时计算LoD的需求；③所构建的3D Tiles场景，配合Three.js等成熟框架并应用Web Worker等技术，能够顺利完成3D Tiles的高效调度和渲染。研究成果对城市三维模型在线编辑、动态地理三维场景的加载渲染等相关研究和应用具有一定的参考价值。
关键词：3D Tiles；松散八叉树；空间索引；LoD；三维地理空间数据；三维渲染；WebGIS
引用格式：马林兵, 代兴龙, 胡靖元. 2024. 可编辑三维场景的动态3D Tiles构建方法. 时空信息学报, 31(4): 500-512
Ma L B, Dai X L, Hu J Y. 2024. Construction method for dynamic 3D tiles in editable three-dimensional scenes. Journal of Spatio-temporal Information, 31(4): 500-512, doi: 10.20117/j.jsti.202404002
1 引 言
由表1可知，在更新过程中BVH树需要递归计算不同位置和大小的场景物体包围盒，BSP树需要计算合适分割平面，两者所需的计算量较大；K-D树可视为分割平面垂直于坐标轴的特殊BSP树且不支持动态更新。相比之下，八叉树的空间划分方式简单，动态更新索引所耗费的计算成本更小，但常规八叉树索引所存在的“黏性”区域和模型跨节点问题会降低索引查询速度，如图1所示。
在不改变八叉树空间划分方式的情况下，有两种方案可解决图1中两个特殊模型的存储问题。一是将模型放置于足够大的节点中；二是多个节点引用同一个模型。前者会导致“黏性”区域问题，即较大模型和位于节点交界处的模型只能存放于浅层节点中，这在实际场景渲染时可能造成更多模型的加载。后者会导致模型改动时涉及更多节点的更新，不利于场景的实时编辑。而松散八叉树扩展了每一个节点的范围且允许相邻节点之间存在重叠，其虽能很好地解决上述问题，却造成相邻节点之间存在较多的重叠，这一定程度上会降低索引检索的速度与精度。因此，本文在下文所述索引构建时，采用递归了更新包围盒的方式来弥补松散八叉树应用中的不足。
式中，u和v分别为构成边的两个顶点；Tu为包含了顶点u的关联三角形；Tuv为包含了边uv的关联三角形；fn、nn分别为三角形f和三角形n的法向量。
3 支持动态场景的3D Tiles文件构建
实验采用一种拓展节点入口边界的松散八叉树构建方法，即拓展节点立方体入口边界的大小，使各节点间存在一定的重叠部分。有研究表明，拓展比例k =2是一个较理想的综合取值，此时物体移动的更新操作时间复杂度为O（1）能很好地适应动态的物体（梁爱民等，2007）。因此，实验中拓展比例取值2。
八叉树的构建即向节点中依次添加对象的过程，其中每个节点主要有以下属性：节点中心的空间位置、节点所包含的正方体空间的边长（入口边界）；节点包围盒和节点所在的卦限，即三维空间中三条坐标轴所划分的八个区域。为防止树的深度过深或单个节点包含的模型对象过多，造成检索效率低下的问题，构建时对树的深度和单个节点所包含的模型对象数量添加约束，具体的构建流程见图2。
场景中模型位置变动和模型编辑造成的八叉树索引更新有两种类型。一是模型仍在当前节点的入口边界内，但模型包围盒产生变动；二是模型的中心点超出了当前节点范围。前者需对当前节点和上层节点的包围盒范围进行递归更新，后者需将模型移动到一个新的八叉树节点中。节点间模型对象的移动行为，可分为两步。首先从原节点中删除待移动模型，此时需考虑节点合并问题；其次将待移动模型插入到新节点中，具体操作与上文所述八叉树构建时一致。
八叉树节点随着对象的增删会产生合并和分割两种情况。向一个包含对象达到阈值的节点继续插入对象时，会分割该节点的对象到子节点中；删减对象时，若删除后当前节点包含对象数量为0且存在子节点，则考虑合并子节点的对象到当前节点中，若没有子节点则删除当前节点。图4展示了节点分割阈值为5时，删除对象的特殊情况。
三维场景更新主要包括模型移动、模型增删、模型编辑（如精细编辑、边界修改、模型整平和雕刻等）三种情况。图5展示了实际情况中涉及的模型编辑和模型移动两种情况。其中：①节点内编辑，主要为模型编辑的常见操作，一般不涉及空间索引变动，只需对变更节点的节点包围盒进行更新。这是因为模型几何的变动，还需要动态计算并更新LoD（节点LoD由各模型LoD组成）。②跨节点移动，主要为模型移动或大尺度的模型编辑，一般涉及空间索引变动，需要更新节点内对象和节点包围盒大小。若不涉及模型几何的变动，只需更新节点LoD，即将模型的LoD关联到新节点中。
1）准实时LoD
在非计算密集如Web平台上，静态LoD比较适合大场景的渲染，然而完全静态的LoD无法应用于涉及模型编辑的场景。因此本文舍弃了常见3D Tiles的HLoD解决方案，而采用在单个瓦片节点上构建不同精度的模型来组成LoD。同时考虑到实际模型编辑中顶点编辑的高频性、连续性，实时计算LoD的计算成本太高，进而影响场景渲染。因此，实验采用一种准实时LoD的方法来对模型编辑后的LoD进行更新。准实时LoD的更新并不是随着用户的编辑操作立即计算，对于具体的计算时机，实验采取了用户编辑后手动触发和一定时间内无编辑操作时触发两种方案。用户编辑模型之后，系统将静态LoD更新为新版本；在浏览模型时会使用已经预构建的LoD模型，新版本的LoD更新则在相应的时机触发。
2）LoD构建过程
LoD的构建主要是为每个瓦片节点生成不同精度的模型，利用基于半边折叠法实现模型简化，具体有以下步骤：①构建顶点索引，目的是得到顶点间的相邻关系；②构建顶点的关联三角形索引，即顶点与包含该顶点的所有三角形的对应关系；③根据步骤②得到的顶点邻接关系计算每条边的折叠代价，按照式（1）需考虑u、v构成的边的方向；④按折叠代价对顶点排序，最终构建排序好的顶点栈；⑤从栈顶取出顶点，将顶点向最小折叠代价方向折叠，删除当前顶点、被折叠的边和三角形。
目前常用的3D Tiles生成工具缺乏自定义空间索引的功能，因此结合上文所述空间索引和准实时LoD构建方法生成3D Tiles。实验采取自下而上的方法来构建，即根据源数据先构建glTF模型，其次将glTF模型内嵌到b3dm文件中，最后根据整个场景构建具备松散八叉树约束的3D Tiles，如图7所示。
（1）构建索引。本文使用的源数据有两种。一是人工建模生成的obj建筑模型；二是包含三维信息的矢量二维数据，即geoJSON，用属性标注每个元素的高度。首先计算场景的最大尺寸作为索引的根节点，其可由场景的总AABB包围盒拓展为正方体得到，而总包围盒由各模型包围盒递归计算得出。按照上文所述，依次向根节点插入对象，即可构建松散八叉树索引。
（2）构建glTF。一般而言，3D Tiles的每个空间索引节点存储一个b3dm/i3dm文件，并在其中封装glTF。以每个空间索引节点中的所有模型为一组创建glTF文件，具体见图6。
（3）构建b3dm。只对b3dm的基本字段进行构建，首先忽略未使用的batchTable，记录为{ BATCH_LENGTH : 0 }，并保存featureTable信息；其次根据实际模型信息构建b3dm的magic、byteLength等其余头部信息，并将生成的glTF置于b3dm头部之后。
（4）构建tileset.json。由于3D Tiles基于包围盒进行空间划分，因此需将空间索引节点转换为3D Tiles规范的包围盒。包围盒由12个参数表示；前3个参数定义了包围盒的中心点位置，后以3个参数为一组定义了3个向量，分别表示包围盒x、y、z轴的方向和半径。根据八叉树节点包围盒的中心位置v，计算出其三个坐标轴方向的半径Rx、Ry和Rz，则3D Tiles包围盒可表示为[v.x，v.y，v.z，Rx，0，0，0，Ry，0，0，0，Rz]。
几何误差用于计算屏幕空间误差（screen space error，SSE），其为几何体在渲染时产生的误差反映在屏幕上的像素距离。渲染器根据SSE阈值决定模型渲染的精度。SSE与摄像机和物体的相对关系有关，精确的SSE计算相对复杂，优化的计算方法为
式中，fov为视场角，（°）；height为屏幕像素高度；dist为相机与物体的距离。结合采用的模型简化算法的特点，应用一种基于顶点与其前向顶点距离最大值的启发式计算方法来计算几何误差。具体地，由于对模型进行边折叠简化时，被折叠边的长度等于顶点移动的距离，因此将最长的折叠边作为几何误差，可保证在任意角度上的误差都小于设定的SSE阈值。
4 实验验证
4.1 数据准备
根据OpenStreetMap导出的广州天河区geojson格式矢量建筑数据和罗岗村的人工三维模型为基础，构建3D Tiles并测试三维模型渲染的准确性与效率。同时，结合由美国斯坦福大学提供的一个的测试数据集——斯坦福龙模型，和实验制作的由不规则三角网构造的山体地形数据集——山体模型，测试基于半边折叠算法构建的LoD精度。具体数据见表2。
实验在一台CPU为i7-11700、内存16GB、GPU型号3050Ti的计算平台上进行。后端基于Node.js进行单线程开发，由于使用了自定义索引和LoD的3D Tiles，因此前端基于封装程度较低的Three.js框架进行开发。
完成数据准备和环境搭建后，进行数据请求与加载，图9为构建的罗岗村三维场景的渲染结果，为了体现模型的分块效果对每个节点的入口边界进行了显示。从渲染结果来看，基于松散八叉树的3D Tiles能完整地加载渲染大型场景，且拥有较好的渲染结果。在加载以上场景时，会将模型分块依次显示，3D Tiles流式传输和渐进式加载的特点得到了保留。
在场景渲染的剔除效果上，基于松散八叉树构建的空间索引在实际渲染时能更加精确地显示视锥体范围内的内容，而常规八叉树构建的场景由于“黏性”区域等问题造成一些不在视野范围内的模型加载，降低了场景渲染的效率和效果，如图10所示。
图12中：（a）为模拟实际应用中场景的缩放、漫游等浏览行为，其在模型加载的初期出现短暂7 fps，浏览帧率均值为49 fps。（b）为固定摄像机视角下对多模型进行跨节点移动的帧率表现，同时对松散八叉树节点的入口边界进行显示。可以看出，模型的跨节点移动操作对帧率影响不大，平均帧率为37 fps，最低帧率为35 fps。（c）为模拟实际应用中模型编辑的场景，包含场景缩放、模型移动、顶点编辑、模型旋转综合应用场景下的表现，帧率表现为均值48 fps、最低36 fps。
综上所述，本文方法所搭建的3D Tiles在场景浏览、模型移动、模型编辑场景下的渲染流畅度和帧率表现均能满足实际地理三维场景编辑应用的需求。
为了评估LoD简化效果，实验制作了25%、50%、75%共三个简化等级的山体模型，如图13所示。可以看出，简化后的模型特征得到保留，验证了半边折叠算法在连续地形模型的动态LoD生成上的可行性。
在LoD的构建时间上，实验以一个约10万面的模型进行测试，得到不同简化比例下的时间成本如图14所示。可以看出，简化约10万面树的模型所用时间基本小于1 s。考虑到实际应用场景的编辑频率，本文方法能够很好地满足Web端模型编辑中实时计算的需求。
实验基于松散八叉树构建空间索引和半边折叠算法构建LoD，构建了一种能够很好地满足Web大型三维场景存在在线编辑需求的3D Tiles格式。在模型渲染的精度上，基于松散八叉树构建的空间索引能够精确进行视锥体剔除，比常规八叉树拥有更快的渲染效果；在模型编辑等动态场景中，基于半边折叠算法构建准实时LoD的时间成本较低，拥有良好的帧率表现，且能保证良好的模型简化结果。本文提出的动态3D Tiles构建方法，可以为三维建模及城市孪生领域提供重要的技术参考。
（1）提升三维建模效率。通过动态空间索引和准实时LoD的结合，实现对大规模三维场景的高效管理和实时编辑，显著提升三维建模的效率和精度。
（2）推动城市孪生技术发展。本文方法为城市三维模型的在线编辑和动态更新提供技术支持，有助于实现城市孪生系统中的实时数据同步和场景更新，为城市规划、管理和仿真提供新的工具和手段。
（3）促进Web三维应用普及。基于Web的三维场景编辑技术，降低用户使用门槛，增强三维地理信息系统应用的互动性和灵活性，推动三维地理信息系统在更多领域的应用和普及。
限于实验条件，所选取的实验场景较小。由于采用3D Tile文件格式，从理论上讲，本文方法所适用的场景大小取决于3D Tile文件所支持的容量。但在实际应用中，三维模型的复杂度（LoD层级）、计算资源的算力，以及用户对操作响应的容忍度都需要继续对算法的实用性做深入探讨。另外，本文方法不适用于复杂曲面定义的三维模型，隐式曲面三角网格化问题需要继续研究。同时，在纹理贴图编辑方面本文未作深入探讨，仅是基于原始模型所定义的贴图进行了展开，在材质贴图编辑上有所限制，这也需要在后续工作中进一步加强完善。
参考文献（References）
褚杰, 盛一楠. 2017. 无人机倾斜摄影测量技术在城市三维建模及三维数据更新中的应用. 测绘通报, (S1): 130-135[Chu J, Sheng Y N. 2017. Application of UAV tilt photogrammetry in urban 3D modeling and 3D data updating. Bulletin of Surveying and Mapping, (S1): 130-135 (in Chinese)]
梁爱民, 梁晓辉, 于卓. 2007. 一种基于松散八叉树的复杂场景可见性裁剪算法. 计算机辅助设计与图形学学报, 19(12): 1593-1598[Liang A M, Liang X H, Yu Z. 2007.Visibility culling for complex scene based on a loose octree structure. Journal of Computer-Aided Design & Computer Graphics, 19(12): 1593-1598 (in Chinese)]
刘璐. 2020. 基于WebGL与动画技术的滑坡与泥石流演变过程展示技术研究.硕士学位论文. 北京: 北京交通大学[Liu L.2020. Research on display technology of evolution process of landslide and debris flow based on WebGL and animation technolgy. Master Dissertation. Beijing: Beijing Jiaotong University (in Chinese)]
刘中华, 李鹏飞, 许章平. 2019. 基于点云数据的改进四叉树空间索引研究. 测绘与空间地理信息, 42(5): 38-39, 42, 47[Liu Z H, Li P F, Xu Z P. 2019.Research on improved quadtree spatial index based on point cloud data. Geomatics & Spatial Information Technology, 42(5): 38-39, 42, 47 (in Chinese)]
施银迪, 王君杰, 孙健. 2021.基于SuperMap iDesktop的高精度三维场景重建方法. 北京测绘, 35(3): 308-311[Shi Y D, Wang J J, Sun J. 2021.A method of high-precision 3D scene reconstruction based on SuperMap iDesktop. Beijing Surveying and Mapping, 35(3): 308-311 (in Chinese)]
宋卓荣. 2018. 基于Web的大规模倾斜摄影模型可视化技术研究. 硕士学位论文. 长沙:国防科技大学[Song Z R.2018. Research on Web-based visualization technologies of massive oblique photogrammetry models. Master Dissertation.Changsha: National University of Defense Technology (in Chinese)]
孙昕. 2019. Web环境下三维对象编辑的研究. 硕士学位论文. 淮南: 安徽理工大学[Sun X.2019. Research on 3D object editing in Web environment.Master Dissertation. Huainan: Anhui University of Science and Technology (in Chinese)]
汪玲玲, 刘星, 高娜, 鹿凤, 余起怡. 2019.基于插件式3D WebGIS的八叉树空间索引研究. 东华理工大学学报(自然科学版), 42(4): 449-454[Wang L L, Liu X, Gao N, Lu F, Yu Q Y. 2019.Octree spatial index based on pluggable 3D WebGIS. Journal of East China University of Technology (Natural Science), 42(4): 449-454 (in Chinese)]
肖际亚. 2016. 基于Web的三维场景协同编辑关键技术研究与实现. 硕士学位论文. 成都: 电子科技大学[Xiao J Y.2016.The research and implementation of three-dimensional dcene collaborative editing based on Web technology.Master Dissertation.Chengdu: University of Electronic Science and Technology of China (in Chinese)]
杨晓宇, 包妮沙, 曹粤, 刘善军. 2021. 基于无人机成像光谱技术的农田土壤养分估测及制图. 地理与地理信息科学, 37(5): 38-45[Yang X Y, Bao N S, Cao Y, Liu S J. 2021. Estimation and mapping of soil nutrient in farmland based on UAV imaging spectrometry. Geography and Geo-Information Science, 37(5): 38-45 (in Chinese)]
杨彦梅, 王莹, 施磊, 陶思蓉, 李宏. 2021. 基于DP-Modeler的精细化三维模型构建. 测绘通报, (5): 106-110[Yang Y M, Wang Y, Shi L, Tao S R, Li H. 2021. Construction of refined 3D model based on DP-Modeler. Bulletin of Surveying and Mapping, (5): 106-110 (in Chinese)]
赵波, 边馥苓. 2007. 面向移动GIS的动态四叉树空间索引算法. 计算机工程, 33(15): 86-87, 93[Zhao B, Bian F L. 2007. Dynamic quadtree spatial index algorithm for mobile GIS. Computer Engineering, 33(15): 86-87, 93 (in Chinese)]
周艳, 朱庆, 黄铎. 2006.三维城市模型中建筑物LOD模型研究. 测绘科学, 31(5): 74-77[Zhou Y, Zhu Q, Huang D. 2006.LOD of complex buildings for 3DCM. Science of Surveying and Mapping, 31(5): 74-77 (in Chinese)]
Biljecki F, Ledoux H, Stoter J. 2016. An improved LOD specification for 3D building models. Computers, Environment and Urban Systems, 59: 25-37
Eberly D. 2008.Triangulation by ear clipping. Geometric Tools, 2002-2005
Geoger G, Plumer L. 2012. CityGML–Interoperable semantic 3D city models. ISPRS Journal of Photogrammetry and Remote Sensing, 71:12-33
Hoppe H. 1996. Progressive meshes//Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. DOI:10.1145/237170.237216
Ju T, Zhou Q Y, Hu S M. 2007. Editing the topology of 3D models by sketching. ACM Transactions on Graphics, 26(99): 42
Melax S. 1998. A simple, fast, and effective polygon reduction algorithm. Game Developer,(11): 44-49
Pang M, He L G, Xiong F G, Yang X W, He Z Y, Han X. 2020. Developing an image-based 3D model editing method. IEEE Access, 8: 167950-167964
Peters S. 2013. Quadtree- and octree-based approach for point data selection in 2D or 3D. Annals of GIS, 19(1): 37-44
Qiu G J, Chen J X. 2018. Web-based 3D map visualization using WebGL//2018 13th IEEE Conference on Industrial Electronics and Applications (ICIEA). Wuhan, China. 759-763
Soon K H, Khoo V H S. 2017. CityGML modelling for Singapore 3d national mapping. ISPRS-International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 42W7: 37-42
Tang L, Ying S, Li L, Biljecki F, Zhu H H, Zhu Y, Yang F, Su F. 2020. An application-driven LOD modeling paradigm for 3D building models. ISPRS Journal of Photogrammetry and Remote Sensing, 161: 194-207
↓↓ 了解更多产业要闻 ↓↓
请将我设为星标★
来源：《时空信息学报》2024年第4期
>>协会通知
“企业家风采”“创新之声”“会员喜讯”“新品发布汇”“产学研合作”“国际市场”“专精特新”“科普”“预见2024”等主题宣传（专栏）进行中，欢迎投稿！
联系人：李娟 13370105015（微信）
邮箱：xc@cagis.org.cn
欢迎关注、分享！
