三维场景中建筑物注记的自动放置方法

摘要

本发明方法公开了一种三维场景中建筑物注记的自动放置方法，该方法针对三维建筑物的几何形态特征，在预处理阶段为每个建筑物模型构建包含固定朝向注记和动态朝向注记的候选注记集，在交互浏览阶段根据视点相关的注记评价算法筛选最优注记。将注记投影到屏幕空间冲突处理时，根据注记的全局优先级采用贪心算法依次放置注记。与现有技术相比，本发明方法的实时计算量小，并且能够适应视角、视距和可视性的动态变化，有效保持注记与建筑物要素的关联性。此外，采用贪心算法按照优先级顺序依次放置注记，可在高效处理屏幕空间注记冲突的同时，保留离视点较近、冲突度较低及具有较高建筑物显著性的注记，提高全局注记的可读性。

权利要求

1.三维场景中建筑物注记的自动放置方法，其特征在于，包含以下步骤：

(1)预处理阶段，为每个建筑物模型构建贴合建筑物表面的固定朝向候选注记和建筑物顶部的动态朝向候选注记，形成候选注记集；

(2)实时浏览时，根据建筑物朝向、注记字长特征以及注记可见性对固定朝向候选注记进行量化评价，并根据评价指标对每个建筑物的候选注记进行局部排序，可视的动态朝向候选注记排放在有效注记集的末尾；其中固定朝向候选注记的量化评价指标包括朝向因子权重Wo、字长因子权重Wl和可视性权重Wv；其中：Wo＝Wx*Wy*as；式中，as为注记所关联面的面积；记αx为注记平面水平方向与视线水平方向分量的夹角，αy为注记平面竖直方向与视线竖直方向分量夹角，Wx为αx的余弦值，Wy为αy的余弦值，当夹角αx或αy大于自定义夹角阈值αt时其对应的Wx或Wy计为0；

式中，lref为固定朝向候选注记的参考线长度，lanno为实时计算的对象空间字长，k为大于1的常数；当注记不可见时Wv视为0，否则Wv与Wl保持一致；

(3)对所有建筑物的候选注记按照注记优先级因子的加权和进行全局排序；所述优先级因子包括注记局部排序、建筑物显著性、注记深度和注记冲突度；

(4)采用贪心算法，结合注记冲突图在屏幕空间中消除注记冲突，并在对象空间中渲染所有被成功放置的注记。

2.根据权利要求1所述的三维场景中建筑物注记的自动放置方法，其特征在于，所述步骤(1)中固定朝向候选注记的默认位置为简化后建筑物模型表面的注记参考线的中心位置；所述注记参考线根据建筑物表面的水平方向、建筑物表面的宽度和预设的建筑物表面高度比例构建。

3.根据权利要求1所述的三维场景中建筑物注记的自动放置方法，其特征在于，所述步骤(1)中动态朝向候选注记的默认位置为建筑物的最高点或顶部平面的中心点位置。

4.根据权利要求1所述的三维场景中建筑物注记的自动放置方法，其特征在于，所述步骤(2)中根据以下方法剔除每个建筑物不合适的候选注记，筛选出有效注记并进行局部排序：(2.1)对候选注记集中的多个固定朝向候选注记进行朝向因子估值，得到权重Wo，并剔除背向观察者或注记平面与视线的夹角超过设定阈值的无效候选注记；

(2.2)对剩余的固定朝向候选注记进行字长因子估值，得到权重Wl，并剔除注记字长超出设定阈值的固定朝向候选注记；

(2.3)对候选注记集中的固定朝向候选注记进行可视性判断，并对部分遮挡的固定朝向注记执行位置调整，得到可视性因子权重Wv，剔除完全不可见的候选注记，注记最终的量化评价权重W与Wv一致；

(2.4)将注记集里剩余的固定朝向候选注记放入建筑物有效注记集，并按照权重值W排序，同时对动态朝向注记执行可视性判断，若未被遮挡，则动态朝向注记作为固定朝向注记的互补性注记，被放在有效注记集的末尾。

5.根据权利要求4所述的三维场景中建筑物注记的自动放置方法，其特征在于，所述步骤(2.3)中对注记进行位置调整的方法为：若建筑物部分不可见，且注记在默认位置处被视锥体所裁剪或被场景遮挡，则在垂直方向上按注记尺寸采样，计算出最长连续可见段，并在该可见段上设置新的注记位置；若在垂直方向上注记均不可见，则执行下一步；

将候选注记平移至参考线上与视点较近的一端处，计算该处的可视性状态；若该处也不可见，执行垂直方向的位置调整；若注记在默认位置和近视点一端处均不可见，将候选注记平移至参考线上与视点较远的一端处，并执行垂直方向调整；若注记参考线上的三个位置及垂直方向上的调整位置均不可见，则将该注记视为不可见。

6.根据权利要求4所述的三维场景中建筑物注记的自动放置方法，其特征在于，所述步骤(2)中采用多线程实时计算每个建筑物的候选注记的评价和筛选。

7.根据权利要求1所述的三维场景中建筑物注记的自动放置方法，其特征在于，所述步骤(3)中全局优先值的计算公式为：P＝wl*Pl+ws*Ps+wd*Pd+wc*Pc

其中，Pl为注记的局部优先级，取值为注记在有效注记集中的排序序号，Ps为设定建筑物的显著性优先级，数值越小优先级越高，Pd为根据建筑物注记的深度划分的深度优先级，Pc为屏幕空间中与注记冲突的其他注记数，wl、ws、wd和wc分别是四个优先级因子的权重。

8.根据权利要求1所述的三维场景中建筑物注记的自动放置方法，其特征在于，所述步骤(4)中具体包括以下步骤：(4.1)采用最小堆结构将所有待渲染注记按照全局优先值P排序；

(4.2)从最小堆的堆顶取出一个优先级最高的节点，并放置与该节点关联的注记；

(4.3)在冲突图中查询与步骤(4.2)中放置的注记相冲突的注记，舍弃这些注记，并去除冲突图中这些注记对应的节点，同时设置最小堆中的值P为无穷大，在最小堆中更新剩余待渲染注记的全局优先值；

(4.4)重复步骤(4.2)、(4.3)过程至最小堆为空或堆顶节点的P值无穷大为止；

(4.5)在对象空间中渲染所有被成功放置的注记。

说明书

三维场景中建筑物注记的自动放置方法

技术领域

[0001] 本发明属于地理信息科学和计算机图形学领域，具体涉及三维场景中建筑物注记的自动放置方法。

背景技术

[0002] 目前在二维地图注记放置及三维场景中注记放置方面的相关研究包括如下几个方面：

[0003] (1)二维地图注记放置

[0004] 文字注记的自动放置一直是二维地图学中的一个研究热点，按照被注记要素的类型可将地图文字注记划分为点要素注记、线要素注记、面要素注记。二维注记研究聚焦于要素注记的自动放置问题。Edmondson et al.认为地图注记的自动放置可分为候选位置生成、注记位置评价和方案选择三个阶段。

[0005] 在候选位置生成阶段，分别对每个要素生成多个候选位置。Christensen et al.提出对于点要素注记，可选取点周围的四个或八个矩形区域作为文字注记候选位置。线要素注记通常以要素中心线或沿线分布的缓冲区为候选位置，必要时将线要素分为多段重复注记。面要素注记的候选位置生成方法可分为两种，一种是选取面要素区域内若干个特征点作为其候选位置，从而将面要素注记转化为点要素注记问题；另一种方法则提取面要素骨骼线，以骨架线为注记候选位置。

[0006] 在注记位置评价阶段，根据候选位置与被注记要素的相对空间关系对每个候选注记进行评价。在方案选择阶段，从一系列候选位置中为每个要素选择一个位置，以获取最合适的注记方案。二维要素文字注记均在一个平面上，在大多数算法中，这种平面注记的放置被看作全局最优问题，即给定每个注记的候选位置，在确保没有互相压盖的情况下，在平面上放置最多数量的注记，这被证明是一个NP-hard问题。Steven Zoraster等采用启发式搜索算法来解决这一组合优化问题。在二维电子地图中，为取得交互效率与全局注记放置效果的平衡，多采用贪心算法来实现注记的快速放置。

[0007] (2)通用三维注记研究

[0008] 尽管二维注记研究已较为充分，但二维注记方法难以直接应用于三维注记中。与二维注记类似，三维注记具有视觉和空间属性，其文字大小、位置和朝向等属性在对象空间中均存在固定不变或动态变化两种不同的样式。注记的视觉属性包括文字内容、色彩、字体类型、文字大小等。文字大小固定的类型规定注记与被注记物体的尺寸始终保持一致，类似于现实场景中的标识牌，存在着远处注记尺寸过小难以识别的缺陷。在动态变化情况下，文字基于视点距离缩放，使得场景中较远对象的注记依旧保持较高的可读性。

[0009] 注记的空间属性包含位置和朝向，体现着其与被注记对象的关联性。其中注记的位置可能是固定的或动态变化的。固定位置的注记在对象空间中位置保持不变。现有的三维虚拟地球引擎多采用固定位置的文字注记，例如，Google Earth将建筑物注记放置在建筑物的顶部的某一个固定位置。但由于不同视角下要素在屏幕空间中呈现的形状不一致，固定位置的注记难以在多个视角下保持与被注记要素的相关性，并存在被遮挡的可能。相比而言，位置动态变化的注记则随着要素在屏幕空间中呈现的形状动态调整位置，以确保在不同的视角下，注记始终保持较高的可视性及对象关联性。

[0010] 注记的朝向也可分为对象空间固定和动态变化两种。动态变化的注记随视点变化而调整对象空间中的文字方向，使得注记始终面向用户。但三维要素(如线、面、体要素)的朝向、拐角等地理形态属性更多地体现在对象空间中，朝向动态变化的屏幕对齐注记方法难以全面地传达这些形态信息。为改进朝向动态变化注记的缺陷，相关研究提出了对象空间朝向固定的注记方法，以反映要素的走向和形状特征，并最大化注记与被注记物体间的视觉相关性。Maass提出了一种三维线要素注记方法，该方法放置为线要素放置贴合地表的嵌入式注记。She提出了另一种三维地图中的线要素注记方法，结合沿线分布的固定朝向注记和动态朝向注记，以保证不同视角下注记的可读性。

[0011] 除了为三维要素放置具有合适的视觉属性和空间属性的注记外，三维注记面临着与二维注记类似的注记冲突问题。在三维场景中，注记的冲突体现为注记间的透视遮挡，这难以在对象空间中解决。通常需要将注记投影到屏幕中，在屏幕中解决注记冲突。同时为了确保不会剔除较为重要的注记，如何对注记按照合适的优先级排序也是挑战之一，相关研究将注记与视点的距离视为一种优先级因素。

[0012] (3)三维建筑物注记研究

[0013] 区别于三维场景中的点、线、面要素，三维建筑物要素本身具有复杂的立体形态，且在不同视口下呈现在屏幕中的形状变化多样，并且可能存在注记遮挡，使得三维建筑物注记更加困难。

[0014] Bell提出的虚拟与增强现实领域背景下的建筑物注记方法中，采用位置动态变化的注记，通过计算建筑物在屏幕空间中的可见部分，将注记放置在最大的可见矩形中。Lehmann提出一种可视性驱动的方案，在屏幕空间中提取三维对象的轮廓线，并将文字注记放置在一条最佳轮廓线上。这两种方法采用动态位置注记，以确保投影变化情况下的注记可视性，但忽略了对象空间中的朝向信息。

[0015] Maass将嵌入式固定朝向注记引入了三维建筑物注记方法中，该方法首先在预处理阶段为每栋建筑创建一个盒体，在交互阶段分别计算盒体上采样点的权重和可视性，最终将注记附着于可见性最佳的位置。Yaoda Huang针对S.Maass的方法提出了改进方案，在预处理阶段对建筑物模型各个面进行分割融合，提取出建筑物各表面的骨架线，在交互过程中对候选面、骨架线及采样点进行评估，最终，将注记放置在最佳骨架线上。但这两种方法实时计算对象表面的最优注记位置，使得注记潜在位置过多，且计算量过大。

[0016] 总的来说，上述方法通过实时计算最优注记位置放置注记。一类方法是将动态朝向注记放在最佳投影表面或轮廓线上，另一类方法将固定朝向注记放在建筑物表面。但这些方法都认为注记可放置在建筑物表面或轮廓线的任意位置。理论上讲，通过设定合理的规则与公式，可以计算出每个建筑物的最优位置与朝向，但这种最优注记计算方法复杂度较高、计算耗时多，对交互性能影响大。

发明内容

[0017] 发明目的：针对现有三维场景中建筑物注记放置方法的缺陷，本发明提供三维场景中建筑物注记的自动放置方法，可以在浏览过程中实时、高效地放置建筑物注记，解决注记间的冲突问题，提升三维场景中建筑物的可读性。

[0018] 技术方案：本发明公开了三维场景中建筑物注记的自动放置方法，可用于三维场景中建筑物模型的文字注记的位置、朝向、尺寸等参数的实时计算，及注记的渲染显示，包含以下步骤：

[0019] (1)预处理阶段，为每个建筑物模型构建贴合建筑物表面的固定朝向候选注记和建筑物顶部的动态朝向候选注记，形成候选注记集；

[0020] (2)实时浏览时，根据建筑物朝向、注记字长特征以及注记可见性对固定朝向候选注记进行量化评价，并根据评价指标对每个建筑物的候选注记进行局部排序，可视的动态朝向候选注记排放在有效注记集的末尾；

[0021] (3)对所有建筑物的候选注记按照注记优先级因子的加权和进行全局排序；所述优先级因子包括注记局部排序、建筑物显著性、注记深度和注记冲突度；

[0022] (4)采用贪心算法，结合注记冲突图在屏幕空间中消除注记冲突，并在对象空间中渲染所有被成功放置的注记。

[0023] 进一步地，所述步骤(1)中固定朝向候选注记的默认位置为简化后建筑物模型表面的注记参考线的中心位置；所述注记参考线根据建筑物表面的水平方向、建筑物表面的宽度和预设的建筑物表面高度比例构建。

[0024] 进一步地，所述步骤(1)中动态朝向候选注记的默认位置为建筑物的最高点或顶部平面的中心点位置。

[0025] 进一步地，所述步骤(2)中固定朝向候选注记的量化评价指标包括朝向因子权重Wo、字长因子权重Wl和可视性权重Wv；其中：

[0026] 将水平分量权重值Wx、垂直分量权重值Wy和注记所关联面的面积相乘得到朝向因子权重值Wo。

[0027] 根据固定朝向候选注记的参考线长度lref和实时计算的对象空间字长lanno，计算得到字长因子权重Wl。

[0028] 当注记不可见时可视性权重Wv视为0，否则Wv与Wl保持一致。

[0029] 进一步地，所述步骤(2)中根据如下方法剔除每个建筑物不合适的候选注记，筛选出有效注记并进行局部排序：

[0030] (2.1)对候选注记集中的多个固定朝向候选注记进行朝向因子估值，得到权重Wo，并剔除背向观察者或注记平面与视线的夹角超过设定阈值的无效候选注记；

[0031] (2.2)对剩余的固定朝向候选注记进行字长因子估值，得到权重Wl，并剔除注记字长超出设定阈值的固定朝向候选注记；

[0032] (2.3)对候选注记集中的固定朝向候选注记进行可视性判断，并对部分遮挡的固定朝向注记执行位置调整，得到可视性因子权重Wv，剔除完全不可见的候选注记，注记最终的量化评价权重W与Wv一致；

[0033] (2.4)将注记集里剩余的固定朝向候选注记放入建筑物有效注记集，并按照权重值W排序，同时对动态朝向注记执行可视性判断，若未被遮挡，则动态朝向注记作为固定朝向注记的互补性注记，被放在有效注记集的末尾。

[0034] 进一步地，步骤(2.3)中根据注记的可见性对注记调整位置的方法为：

[0035] 对于固定朝向注记，首先计算注记在默认位置的可视性状态；若不可见，则在垂直方向上按注记尺寸采样，计算出最长连续可见段，并在该可见段上设置新的注记位置。若在垂直方向上注记均不可见，则依次判断参考线上离视点较近的一端与离视点较远的一端，并执行潜在的垂直方向调整。若三个位置均不可见，则将该注记视为不可见。

[0036] 进一步地，所述步骤(3)中全局优先值的计算公式为：

[0037] P＝wl*Pl+ws*Ps+wd*Pd+wc*Pc

[0038] 其中，Pl为注记的局部优先级，取值为注记在有效注记集中的排序序号，Ps为设定建筑物的显著性优先级，数值越小优先级越高，Pd为根据建筑物注记的深度划分的深度优先级，Pc为屏幕空间中与注记冲突的其他注记数，wl、ws、wd和wc分别是四个优先级因子的权重。

[0039] 进一步地，步骤(4)中采用贪心算法，并结合最小堆数据结构，依次放置最高优先级注记，以在屏幕空间中消除注记冲突。最终，在对象空间中渲染所有被成功放置的注记。

[0040] 有益效果：本发明方法针对三维建筑物的几何形态特征，在预处理阶段为每个建筑物模型构建包含固定朝向注记和动态朝向注记的候选注记集，在交互浏览阶段根据视点相关的注记评价算法筛选最优注记。与现有技术相比，本发明方法的实时计算量小，并且能够适应视角、视距和可视性的动态变化，有效保持注记与建筑物要素的关联性。此外，本发明方法采用贪心算法按照优先级顺序依次放置注记，可在高效处理屏幕空间注记冲突的同时，保留离视点较近、冲突度较低及具有较高建筑物显著性的注记，提高注记全局放置的可读性。

附图说明

[0041] 图1为本发明方法的流程图。

[0042] 图2为固定朝向和动态朝向候选注记示意图。固定朝向注记沿参考线分布，贴合建筑表面。动态朝向注记以参考点为中心调整注记平面方向，以保持始终面向观察者。

[0043] 图3为同一建筑物在不同视距下的注记字长效果对比图。

[0044] 图4为遮挡情况下固定朝向候选注记的动态调整。(a)默认位置处被遮挡时，注记位置调整至参考线上近视点一端。(b)默认位置与近视点一端均被遮挡时，注记位置调整到远视点一端。

[0045] 图5为采用本发明方法时，在不同观察角度下的注记放置效果图。

[0046] 图6为本发明方法有效处理注记冲突的效果图。

具体实施方式

[0047] 下面结合具体实施方式和附图对本发明的技术方案作进一步的介绍。

[0048] 本发明公开的三维场景中建筑物注记的自动放置方法的处理流程分为三个阶段(图1)。在候选注记构建阶段，构建出包含固定朝向注记和动态朝向注记的候选集。在候选注记筛选阶段，通过实时计算候选注记集中不同注记的朝向因子、字长因子和可视性因子，筛选出有效注记。在此之后，不同建筑物的待渲染注记在有限的屏幕空间中互相竞争，导致了注记冲突。在冲突处理阶段，根据注记的全局优先级采用贪心算法依次放置注记。

[0049] 步骤(1)预处理阶段，构建候选注记集，具体包括：

[0050] (1.1)构建贴合建筑物表面的固定朝向候选注记。

[0051] 固定朝向的注记贴合建筑物表面，可以反映其走向和形状特征，不仅能提升漫游、导航等情境下的视觉效果，还可以减少屏幕空白空间的占用，提高全局注记数量。固定朝向候选注记基于表面参考线结构，其示意图如图2所示。通过简化并提取建筑物模型表面，并设置几何属性，包括设定方向为贴合建筑物表面的水平方向、长度为建筑物表面的宽度、高度为自定义的建筑物表面高度比例，可构建出注记参考线。

[0052] (1.2)生成建筑物顶部的动态朝向候选注记。

[0053] 建筑物各个表面的朝向差异性意味着同一个建筑物需要构建不同的固定朝向候选注记。但对不规则表面而言，例如金字塔型或尖顶型建筑物屋顶，难以构建合适的固定朝向注记。此外，平坦屋顶面上的固定朝向注记在视角变化时也可能与视线逆向，导致注记文字上下颠倒，难以辨认。而动态朝向注记可以在多角度下始终保持注记的可读性。因此，可在建筑物顶部构建基于布告板的动态朝向候选注记，作为固定朝向注记的互补性注记。该注记随视口变化动态调整其朝向，始终面向观察者。图2展示了动态朝向候选注记的示意图。生成动态朝向候选注记，需要选取一个参考点作为放置位置，本方法选择建筑物的最高点或顶部平面的中心点作为动态朝向注记的参考点。

[0054] 步骤(2)实时浏览阶段，对候选注记进行视点相关的评价，其中评价因素主要包括朝向、字长和可视性，具体包括：

[0055] 固定朝向的候选注记贴合建筑物表面，在交互过程中，随着三维场景中观察相机的方位角和俯仰角变化，注记表面的法线与观察视线的夹角随之改变，注记效果也相应变化。对于固定朝向候选注记而言，定义朝向因子Wo，其计算公式如下：式(1)计算注记平面水平方向与视线水平方向分量的夹角αx的余弦值Wx，式(2)计算注记平面竖直方向与视线竖直方向分量的夹角αy的余弦值Wy。其中，Wx负值表示注记背向观察者，Wy负值表示注记相对于视点上下颠倒。同时当Wx或Wy的值为正，但夹角αx或αy大于一定阈值时，注记平面与视线接近平行，可读性较低。本方法设该阈值为自定义值αt，当夹角αx或αy大于阈值αt时其对应的Wx或Wy值计为0。式(3)将Wx、Wy和注记所关联面的面积as相乘得到朝向因子权重值Wo，Wo可近似代表对应建筑物表面的朝向特征，体现注记的朝向优劣性。

[0056]

[0057]

[0058] Wo＝Wx*Wy*as#(3)

[0059] 本方法采用字体大小动态变化的方案，以确保注记在屏幕中的可读性。该方案预先定义屏幕空间中注记的像素大小，再根据视距相关的对象空间尺寸与屏幕像素大小的对照公式，计算出对象空间注记尺寸和字长lanno，最后根据注记尺寸在三维空间中相应位置生成注记。在屏幕空间中建筑物模型的像素大小与视点到物体的距离负相关，而屏幕中的注记字体大小不变。因此，当建筑物远离视点时，在屏幕空间中注记的字长会大于注记参考线的长度，注记超出了建筑物表面，注记尺寸甚至远大于建筑物的像素尺寸，最终导致建筑物各表面的方向特征显著弱化，相应地固定朝向注记体现表面走向的优势迅速下降(图3)。故当建筑物较远时，应采用动态朝向的布告板注记替代与建筑物表面对齐的固定朝向候选注记，以取得更好的视觉效果。

[0060] 通过构建合适的字长与参考线长度对应函数，可反映固定朝向候选注记在字长变化情况下的优劣性。根据固定朝向候选注记的参考线长度lref和实时计算的对象空间字长lanno，定义字长因子权重函数Wl。公式(4)表示当注记字长小于等于参考线长度lref时，注记字长因子权重与朝向因子权重值Wo保持一致；当lanno大于lref时，注记超出参考线，部分文字悬浮在空中，此时随着lanno的增加，注记的字长权重逐渐下降；当lanno超过特定阈值时，固定朝向注记的方向特征减弱，注记权重降为0。本方法设该阈值为k倍lref，其中k为大于1的自定义常数。

[0061]

[0062] 定义注记可视性权重函数Wv，当注记不可见时Wv视为0。特别地，对于固定朝向注记，首先计算注记在默认位置，即参考线中点处的可视性状态；若建筑物部分不可见，且注记在默认位置处被视锥体所裁剪或被场景遮挡，则在垂直方向上按注记尺寸采样，计算出最长连续可见段，并在该可见段上设置新的注记位置。若在垂直方向上注记均不可见，则执行下一步。

[0063] 将候选注记平移至参考线上与视点较近的一端(图4中的(a))，计算该处的可视性状态；若该处也不可见，执行垂直方向上的位置调整。类似地，若注记在默认位置和近视点端均不可见，将候选注记平移至参考线上与视点较远的一端(图4中的(b))，并执行潜在的垂直方向调整。若注记参考线上的三个位置及垂直方向上的调整位置均不可见，则该固定朝向注记可视性因子iv视为0，否则Wv与Wl保持一致。

[0064] 根据通过整合上述视点相关的评价指标，构建注记效果实时评价与选用算法，可依次剔除部分不合适的候选注记，筛选出有效注记，其主要流程如下：

[0065] (2.1)对候选注记集中的多个固定朝向候选注记进行朝向因子估值，得到权重Wo，并剔除背对观察者或注记平面与视线的夹角超过特定阈值的无效候选注记。

[0066] (2.2)对剩余的固定朝向候选注记进行字长因子估值，得到权重Wl，并剔除注记字长超出一定阈值的固定朝向候选注记。

[0067] (2.3)对候选注记集中的固定朝向候选注记进行可视性判断，并对部分遮挡的固定朝向注记执行位置调整，最终得到可视性因子权重Wv，同时剔除完全不可见的候选注记，注记最终的量化评价权重W与Wv一致。

[0068] (2.4)将注记集里剩余的固定朝向候选注记放入建筑物有效注记集，并按照权重值W排序，同时对动态朝向注记执行可视性判断，若未被遮挡，则动态朝向注记作为固定朝向注记的互补性注记，被放在有效注记集的末尾。这些不同建筑物的有效注记集随后进入待渲染状态。

[0069] 每个建筑物的注记筛选过程互不干扰，该实时评价算法采用了多线程技术。通过上述候选注记实时评价流程，两种类型的候选注记得到保留，并可发挥各自在不同视点、视角背景下的优势，使得每个建筑物可在各种观察条件下均取得较为适宜的注记。

[0070] 步骤(3)将注记投影到屏幕空间，处理注记之间的相互冲突关系。具体包括：

[0071] (3.1)为每个候选注记设置注记优先级。

[0072] 每个建筑物的有效注记集里，注记按照量化评价权重值排序。通常情况下，只需要对各个建筑要素放置一个最优注记。但是，当最优注记与其他注记产生注记冲突时，其余候选注记可以作为备选方案。本方法将每个有效注记集中的元素排序后，设定注记的局部优先级Pl，其取值为注记在有效注记集中的排序序号，1代表最优注记，2代表次优注记，以此类推。在有效注记集里，动态朝向注记的排序最靠后，故其优先级最低。

[0073] 建筑物的显著性各有差异，例如地标性建筑相比于其他建筑物而言，在导航寻路等过程中可以起到更好的认知识别作用，可根据建筑物的高度、面积、类型、颜色、形状等指标对建筑物的显著性量化分级。本方法在预处理阶段设定建筑物的显著性优先级为Ps，其取值为1～5之间的整数，1代表优先级最高，5代表最低。所有候选注记继承其关联建筑的显著性优先级Ps。

[0074] 建筑物注记的深度即注记和视点的距离。一些研究在处理注记的空间冲突时，考虑到注记的深度信息，按照离视点由近及远的顺序在屏幕空间放置注记。本方法计建筑物注记的深度为d，深度优先级为Pd，其值按深度由近及远分别取1～5，见公式(5)，其中ceil函数返回大于或者等于指定表达式的最小整数。

[0075]

[0076] 将所有待渲染注记投影到屏幕空间中，可能会导致注记冲突，为记录注记之间的冲突关系，构建注记冲突图。对注记在屏幕中的投影依次构建R-Tree空间索引，每当记录一个有效候选注记时，注记的投影矩形被插入到R-Tree中，同时，采用一个二维Boolean矩阵来记录冲突关系图，随着R-Tree的构建过程而更新冲突图的节点。图的节点表示待渲染注记，两节点之间的边表示注记间的冲突关系，每个节点与之相连的边的数目总和即为与之冲突的注记总数，并称之为冲突度。本方法计屏幕空间中与每个注记冲突的其他注记数为Nc，注记冲突权重为Pc＝Nc。

[0077] 根据注记的局部排序、建筑物显著性、注记深度和注记冲突度，每个注记的全局优先级计算如公式(6)。其中P是注记的全局优先值，其值越小代表其优先级越高，wl、ws、wd和wc分别是四个优先级因子的权重。

[0078] P＝wl*Pl+ws*Ps+wd*Pd+wc*Pc#(6)

[0079] (3.2)采用贪心算法依次放置注记，以消除屏幕空间的注记冲突，生成可渲染的注记对象。

[0080] 1)采用最小堆结构将所有待渲染注记按照全局优先值P排序。

[0081] 2)从最小堆的堆顶取出一个优先级最高的节点，并放置与该节点关联的注记。

[0082] 3)在冲突图中查询与2)中放置的注记相冲突的注记，舍弃这些注记，并去除冲突图中该注记对应的节点，同时设置最小堆中的值P为无穷大，在最小堆中更新剩余待渲染注记的全局优先值。

[0083] 4)重复2)、3)过程至最小堆为空或堆顶节点的P值无穷大为止。

[0084] 5)在对象空间中渲染所有被成功放置的注记。

[0085] 图5为采用本发明方法渲染的不同观察角度下的注记放置效果图。该场景为上海浦东陆家嘴金融贸易区中心地带。在预处理阶段对场景中的45栋主要建筑物构建不同的候选注记集，共包含146个固定朝向候选注记和45个动态朝向候选注记，并按照显著性指标对建筑物进行分级。在浏览过程中，根据候选注记量化评价指标实时挑选出每栋建筑的有效注记，并在屏幕空间中解决不同建筑物间的冲突问题，该过程在视角切换时才会发生，以避免静态视角下的计算消耗。(该场景中取注记参考线构建时的表面高度比例为80％，朝向因子对应公式(1)、(2)中夹角阈值αt为60°，字长权重因子对应公式(4)中的k为2，注记优先级中四个因子的权重wl、ws、wd和wc分别为1/4)。

[0086] 图6为本发明方法有效处理注记冲突的效果图。综合注记的局部排序、建筑显著性、注记深度、注记冲突度为注记优先级，在放置过程中依照贪心思想依次放置最高优先级注记，并剔除潜在冲突注记。本发明方法在有效处理注记冲突的同时，既会优先放置地标建筑物注记及离视点较近的注记，也可展示较高数量的注记，同时当建筑物的最优注记被剔除时，次优注记可作为备选者被放置场景中。