将3D场景分割为由计算资源处理的多个区域

摘要

本发明指向一种用于将三维场景分割为多个区域的计算机实现方法，每个区域由一计算资源处理。该方法包括：-提供包括一个或多个对象的三维场景，每个对象产生一计算资源成本；-确定三维场景中的一组位置；-以达到最贵计算成本的每个位置的最大对象占用来填充每个位置；-为三维场景的每个位置计算最高计算成本密度；和-将相邻位置分组到一个或多个区域，每个区域具有保证区域的实时性能的合成计算成本密度。

说明书

技术领域

本发明涉及计算机程序和系统的领域，尤其涉及用于将三维场景分割 为多个区域的方法、系统和程序，每个区域由计算资源处理。

背景技术

大型多用户在线应用程序(MMO)允许大量用户同时使用例如真实世 界现象模拟器、沉浸式应用程序等的应用程序。同样地，大型多用户在线 游戏(MMOG)允许大量玩家同时进行视频游戏。MMO和MMOG尤其依 赖计算机网络，比如因特网，用于允许用户或玩家连接到应用程序或视频 游戏。贯穿该说明书，词语“应用程序”和“视频游戏”将被理解为是同 义的，并且术语MMO和MMOG也不做区别使用。

MMO涉及复杂和庞大的虚拟环境，为了给用户或游戏玩家提供更加真 实的体验，希望虚拟环境以尽可能多的细节、尽可能接近实时地被呈现。 MMO被特别设计用于呈现和操纵3D场景，并典型地用在终端用户的计算 机上用于要求交互式连续实时3D场景生成的应用程序。当用户与3D场景 交互时，计算机足够快地重绘3D呈现以向用户传达用户正参与的连续的、 不间断的现实感觉。该场景由多个独立的对象构成，当用户与该3D场景交 互时可对所述对象进行操纵。这样，MMO涉及很大的数据量，通常要求高 数据速率和高数据复杂度以管理实时参与到空间复杂和高细致虚拟环境的 大量用户。

MMO典型地用于在计算机模型内模拟现实世界现象，如多体刚性动力 学、人类模拟、布料模拟、粒子模拟。模拟需要描述真实世界现象的精确 数据和算法，例如用于制造过程的材料的物理属性(强度、弹性等等)，以 便建立对该过程的模拟和对使用中的产品的模拟的产品。3D CAD/CAM(计 算机辅助设计/计算机辅助制造)工具允许建立对产品或组成部件的3D呈 现。

对MMO和MMOG主要和关键的要求是向所连接的玩家在任何时候都 能提供实时响应，而不考虑他们的数量，也不考虑用于解决和呈现应用程 序所引起的计算成本。否则，游戏体验的质量将变得糟糕，会降低玩家对 应用程序的兴趣，限制在执行协同和分布设计评审时的交互。

MMO，和MMOG一样，必须是可扩展的以动态适应永远变化的工作 负荷，从而保持实时性能。可扩展性尤其包括能够同时使用应用程序的用 户数量、用于计算模拟的计算资源数量、被应用程序所允许的3D场景的对 象之间的同时交互的数量，诸如此类。对于MMOG，用户数量、以及所有 包含的动态对象的位置和图形属性可以显著变化。然而，游戏开始之前， 周围布景是一次全部设定的，并且动态对象的类型和所支持的行为种类也 是预先定义的。换句话说，MMOG中的3D场景包括许多预先确定的特征， 这些特征强有力地限制了对计算资源的需求，从而提高了可扩展性。

相反，对于高级MMO，3D场景的布景和群体类型能够进化和充实， 特别是在应用程序运行时。事实上，MMO目的在于真实世界现象，其中， 对象行为是动态的并排除预先定义的行为种类。因此，MMO中的3D布景 不能使用像用于MMOG的预先定义的特征。

可扩展性的问题被MMOG所解决。此类方案和技术包括分片和分区。 分片在于克隆世界(部分或全部)并招待新登录的用户以便处理工作负荷 上升，但是不可能在分片之间进行交互。因此，本性而言，分片不支持虚 拟世界空间和群体的无限扩展；分片确实具有由他们被分配的处理资源的 性能所指示的物理容量上限。

分区依靠对所谓区域中虚拟世界空间的分割，他们中的每个承担计算 资源的责任。对象/用户能够进行逐区域的导航。相关联的计算资源接着在 网络上传输专用消息以便将这些移动对象集成到他们的计算模型中。

然而，在MMOG中，区域互相之间相当独立的发展：动态对象简单的 从区域“A”的若干预先定义通道位置中的一个“远程传输”到区域“B” 的若干位置中的另一个。优化负载平衡问题通过以下解决：通过使用障碍 物或实体墙围住区域、通过限制区域内部通道位置的数量、通过限制任何 时候在每个区域内对象的群体、以及通过使用调整过的静态布景(décor) 来填充区域。某种程度上，虚拟环境的不同区域被定制以符合实时需求。

对于高级MMO，这种简化是不能接受的。事实上，虚拟环境，尤其当 真实世界现象被模拟时，不能支持布景的人工围栏，这限制了对模拟的真 实世界定制化的可能性。正相反，在真实世界中，区域是开放的，与他们 的相邻区域共享共同的连续边界，任何对象都可能通过这里。因此，就其 本质而言，分区能够潜在地管理如高级MMO中所需要的虚拟世界的无限 增大。然而，如MMOG中所执行的分区不适于MMO的上下文环境，因为 它需要特殊定制虚拟环境、所模拟的现实世界和对其特征的限制。

在此背景下，仍然需要改进的方法、计算机程序和系统，用于在真实 世界模拟应用程序中提供可扩展的、无缝的和有效的对3D场景的实时模 拟。

发明内容

根据一个方面，本发明因此提供一种用于将三维场景分割为多个区域 的计算机实现方法，每个区域由一计算资源处理。该方法包括：

-提供包括一个或多个对象的三维场景，每个对象产生一计算资源成 本；

-确定三维场景中的一组位置；

-以达到最贵计算成本的每个位置的最大对象占用来填充每个位置；

-为三维场景的每个位置计算最高计算成本密度；和

-将相邻位置分组到一个或多个区域，每个区域具有保证区域的实时 性能的合成计算成本密度。

该方法可以包括下面的一个或多个：

-聚集为三维场景的位置计算的最高计算成本密度，和根据聚集的最 高计算成本密度建立三维场景的成本密度地图；

-为动态对象执行以每个位置的最大对象占用来填充每个位置的步 骤，动态对象是能够在三维场景中潜在地移动的对象；

-为三维场景的每个位置提取位于所述每个位置上的静态对象，静态 对象是不能够在三维场景中移动并不能够被另外的对象穿过的对象，和根 据提取出的静态对象建立三维场景的约束地图；

-提取静态对象的步骤进一步包括为三维场景的每个位置提取静态对 象在三维场景的所述每个位置上的印迹；

-聚集三维场景的成本密度地图和三维场景的约束地图的步骤；

-计算最高计算成本密度包括计算比率P/A，其中，P是用于处理位 置所需的计算资源的测量百分比，A是三维场景中位置的面积；

-在分组步骤，每个区域的合成计算成本密度是这样的：用于处理该 区域所需要的计算资源低于预先定义的阈值；

-在分组步骤，在两个或多个区域之间的合成计算成本密度是明显一 样的；

-考虑每个区域过去所制造的计算资源的使用，进一步执行分组步骤。

本发明进一步提出一种包括用于被计算机执行的指令的计算机程序， 所述指令适用于执行本发明的方法的步骤。

本发明进一步提出一种计算机可读存储介质，在其上记录有以上所述 的计算机程序。

本发明进一步提出一种计算机化系统，包括：

-存储系统，用于存储包括一个或多个对象的三维场景；

-处理单元，用于处理分割三维场景的多个区域，每个区域由该处理 单元的一计算资源处理，该处理单元适用于根据本发明的方法将三维场景 分割为多个区域。

附图说明

现在将以非限制性例子的形式和根据附图描述本发明的实施例，其中：

-图1显示了方法的例子的流程图；

-图2显示了大商场的虚拟世界的例子的俯视图；

-图3显示了对位置的最高成本密度的分析的例子；

-图4显示了对位置的最高成本密度的量化的例子；

-图5显示了成本密度地图的例子；

-图6显示了约束地图的例子；

-图7显示了对图5和图6的成本密度地图和约束地图的聚集的例子；

-图8显示了计算机化系统的例子。

具体实施方式

根据图1的流程图，提出了一种计算机实现方法，其用于将三维场景 分割为多个区域，每个区域由计算资源处理。处理包括提供三维(3D)场 景。3D场景可以模拟真实世界环境。3D场景包括一个或多个对象，例如 3D建模对象。每个对象产生计算资源成本，也就是说，为了在3D场景中 被执行，每个对象需要计算资源的时间。该方法进一步包括确定3D场景中 的一组位置。3D场景中的位置可以是3D场景的对象可进入的面积。3D场 景中的位置可以是其中可包含3D场景的对象的体积。该方法进一步包括以 达到最贵计算成本的每个位置的最大对象占用来填充每个位置。该方法进 一步包括为3D场景的每个位置计算最高计算成本密度。最高计算成本密度 可以指每个面积单位或每个体积单位的计算成本。该方法还包括将相邻位 置分组到一个或多个区域。每个区域具有保证区域的实时性能的合成计算 成本密度。区域的合成计算成本密度是每个位置的最高成本密度乘以它的 面积或体积的总和。

这个方法改进了对3D场景的分区，其中提供了保证实时性能，不需要 对其特征施加3D场景的特殊定制或约束。另外，本方法进一步支持3D场 景的扩展、对象类型和其行为种类的扩展。事实上，分组取决于3D场景的 每上个位置的饱和度的结果，饱和度通过以达到最贵计算成本的每个位置的 最大对象占用来填充每个位置来执行。有趣的是，最大对象占用反映了3D 场景的真实状况。换句话说，分组是情节(scenario)的结果，其中每个位 置上对象的群体是最多的，情节关于模拟的真实世界是现实的。

该方法是计算机实现的。这意味着该方法的步骤(或基本上所有步骤) 由至少一台计算机或一计算机化的系统执行。在例子中，该方法的至少一 些步骤的触发可以通过用户-计算机交互来执行。所需要的用户-计算机交互 的级别取决于自动化预测的级别并平衡实现用户愿望的需要。在例子中， 这个级别可以是用户定义的和/或预先定义的。

例如，提供包括一个或多个对象的3D场景的步骤可以根据用户的选择 来执行，例如场景的。用户可以通过触觉设备执行选择，比如键盘、鼠标、 定位笔，诸如此类。例如，在两键鼠标中，左键可以用于选择场景列表中 的场景。该系统还可以默认识别场景，即不需要用户选择。

计算机实现该方法的一个典型例子是使用包含存储器和处理器的系统 执行该方法。存储器存储数据库，其仅仅是适合此类存储的任何硬件。处 理器还可以是指计算单元。这个系统在真实世界模拟应用程序中的上下文 中提供可扩展的、无缝的和有效的3D场景的实时模拟。该系统可以进一步 包括适用于显示3D场景和3D场景内的对象的图形用户界面(GUI)。GUI 与存储器和处理器耦合。

通过“数据库”，意味着对被组织用于搜索和取回的数据(即信息)的 任何采集。当存储在存储器上时，数据库允许通过计算机快速搜索和取回。 数据库事实上被结构化以便于结合各种数据处理操作来存储、取回、修改 和删除数据。数据库可以由能够被分解成记录的一个文件或一组文件组成， 每个记录由一个或多个字段组成。字段是数据存储的基本单位。用户可以 主要通过查询取回数据。使用关键字和排序命令，用户能够快速搜索、重 新排列、分组和选择许多记录中的字段，以根据正在使用的数据库管理系 统的规则来取回或建立关于特别的数据聚集的报告。

在该方法的情况下，数据库包含三维场景，该三维场景包括一个或多 个对象。一个或多个对象存储在数据库上，并可以独立于场景存储。数据 库可以进一步包含计算机程序，该计算机程序包括用于被该系统执行的指 令。指令适用于执行本方法的步骤。

该方法一般操纵对象。对象是被存储在数据库中的数据定义的任何对 象。引申开来，“对象”这个表达指定了数据本身。根据系统的类型，对象 可以由不同种类的数据定义。系统可以是CAD系统、CAE系统、CAM系 统、和/或PLM系统的任何组合。在那些不同的系统中，建模对象由相应的 数据定义。人们可以相应地谈到CAD对象、PLM对象、CAE对象、CAM 对象、CAD数据、PLM数据、CAM数据、CAE数据。然而，这些系统并 不互相排斥，因为对象可以由与这些系统的任何组合相对应的数据来定义。 这样，系统很可能既是CAD又是PLM系统，通过下面提供的这样的系统 的定义，这一点是很明显的。系统还可以是MMO或MMOG系统，其中对 象根据用户动作被操纵。

通过CAD系统，意味着至少适用于基于对建模对象的图形表示来设计 建模对象的任何系统，比如CATIA。在这种情况下，定义建模对象的数据 包括允许表示建模对象的数据。CAD系统例如可以使用边或线、某些情况 下使用面或表面，提供对CAD建模对象的表示。线、边或表面可以用各种 方式表示，例如非均匀有理B样条(NURBS)。特别的，CAD文件包含规 范，根据该规范可以产生几何图形，这反过来允许产生表示。建模对象的 规范可以存储在单一的CAD文件中或多个文件中。CAD系统中表示建模 对象的文件的典型大小是每个部件一兆字节范围内。建模对象典型的可以 是数千部件的组装。

在CAD的上下文中，建模对象典型的可以是3D建模对象，例如表示 产品，比如一个部件或部件的组装，或可能是产品的组装。通过“3D建模 对象”，意味着由允许它的3D表示的数据建模的任何对象。3D表示允许从 所有角度查看部件。例如，3D建模对象，当用3D表示时，可以围绕它的 任意轴线或围绕表示被显示于其上的屏幕内的任意轴线被处理和转动。这 显然排除不是3D建模的2D图标。3D表示的显示有利于设计(即，提高 了设计者统计上完成他们任务的速度)。这加速了行业制造过程，因为产品 的设计是制造过程的一部分。

CAD系统可以是基于历史的。在这种情况下，建模对象进一步由包括 几何特征历史的数据来定义。建模对象事实上可以由自然人(即设计者/用 户)使用标准建模特征(如伸出、转动、切割和/或变圆等等)和/或标准表 面特征(如扫除、混合、放样(loft)、填充、变形、平滑和/或等等)进行 设计。许多支持这样的建模功能的CAD系统是基于历史的系统。这是指设 计特征的建立历史典型地通过用输入和输出链接将所述几何特征链接在一 起的非循环数据流而被保存。自80年代初期，基于历史的建模范例被众所 周知。建模对象由两个持久性数据表示来描述：历史和B-rep(即边界表示 法)。B-rep是历史中定义的计算的结果。当建模对象被表示时，显示在计 算机屏幕上的部件的形状是(曲面细分的)B-rep。部件的历史是设计的意 图。基本上，历史收集了建模对象已经经历的操作的信息。B-rep可以与历 史一起保存，以使得更容易显示复杂部件。为了允许根据设计意图改变部 件的设计，历史可以与B-rep一起保存。

通过PLM系统，意味着适用于管理表示物理制造产品的建模对象的任 何系统。在PLM系统中，建模对象因而由适用于制造物理对象的数据来定 义。这些典型的可以是尺寸值和/或公差值。对于正确制造对象，具有这样 的值确实更好。

通过CAE系统，意味着适用于分析建模对象物理行为的任何系统。在 CAE系统中，建模对象因而由适用于分析这类行为的数据来定义。这典型 的可以是一组行为特征。例如，与门相对应的建模对象可以由表明这扇门 围绕轴线旋转的数据来定义。

图8显示了客户端计算机系统的例子，例如用户的工作站。

客户端计算机包括连接到内部通信总线1000的中央处理单元(CPU) 1010，随机存取存储器(RAM)1070也连接到总线。客户端计算机进一步 设置有图形处理单元(GPU)1110，其与连接到总线的视频随机存取存储 器1100相关联。视频RAM1100也就是本领域公知的帧缓冲器。大容量存 储设备控制器1020管理对大容量存储设备的访问，例如硬盘驱动器1030。 适用于有形地体现计算机程序指令和数据的大容量存储设备包括所有形式 的非易失性存储器，举例来说包括半导体存储器设备，例如EPROM、 EEPROM、和闪速存储器设备；磁盘，例如内置硬盘和可移动磁盘；磁光 盘；和CD-ROM盘1040。前述的任何一个可以通过特殊设计的ASIC(专 用集成电路)来补充或并入其中。网络适配器1050管理对网络1060的访 问。客户端计算机还可以包括触觉设备1090，例如光标控制设备、键盘等 等。光标控制设备用在客户端计算机中，以准许用户有选择地将光标放在 显示器1080上任何希望的位置。另外，光标控制设备允许用户选择各种命 令，和输入控制信号。光标控制设备包括若干信号产生设备，用于将控制 信号输入到系统。典型地，光标控制设备可以是鼠标，鼠标的按键用来产 生信号。

计算机程序可以包括依据计算机的指令，指令包括用于引起上述系统 执行上述方法的方式。本发明例如可以用数字电子电路或用计算机硬件、 固件、软件或用他们的组合来实施。本发明的装置可以用有形地体现在机 器可读存储设备中由可编程处理器执行的计算机程序产品实施；并且本发 明的方法步骤可以由执行程序指令的可编程处理器来执行，以通过通过操 作输入数据和产生输出来执行本发明的功能。

本发明可以有利地用在可编程系统上可执行的一个或多个计算机程序 实施，可编程系统包括用来从数据存储系统接收数据和指令和传输数据和 指令到数据存储系统的至少一个耦合的可编程处理器、至少一个输入设备 和至少一个输出设备。应用程序可以用高级过程编程语言或面向对象编程 语言、或者如果需要则用汇编或机器语言来实现；并且在任何情况下，语 言可以是编译或解释语言。

根据图1的流程图，现在讨论用于将三维场景分割为多个区域的方法 的一个例子。

在步骤100，提供包括一个或多个对象的三维(3D)场景。提供3D场 景可以包括在显示器上显示3D场景和一个或多个对象，例如根据图2提到 的显示器1080。3D场景是描述了其中对象之间的空间关系的空间。场景由 至少两个对象组成，对象可以是，但不限制为，建模对象或3D建模对象。 3D建模对象是对3D空间中对象的描述。3D场景是物理宇宙的模型，其可 以由依靠坐标描述3D空间中的每个点的几何图形进行数学表示。3D场景 典型的是模拟的真实世界，其中对象之间的真实交互被模拟。表达真实交 互意思是模拟的交互反映了真实世界的交互，例如物理定律如作用力/转向 力(重力、磁力、接触)、控制定律如信息流、控制事件等等。一个或多个 对象在3D场景中发展并受模拟的真实世界的定律支配，例如两个对象不能 相互交叉。3D场景包括能够为了特定的情节而被修改的布局。情节描述了 3D场景中一个或多个对象的至少可预测的交互。情节因而描述了一种方式， 即3D场景用于或设想用于活动的上下文中，例如分析商店中新的区域对顾 客流程管理的影响或万一火灾疏散对安全的影响。每个特定的情节将在布 局中被模拟。要知道情节可以由用户定义。事实上，3D场景的布局由不能 在3D场景中移动和不能被另一对象穿过的静态对象组成。

图2举例说明了3D场景的俯视图的例子，其模拟了大商场的虚拟世界。 这个虚拟商场由被墙(由粗线表示)隔开的几个店铺200、210、220、230、 走廊260、270和楼梯240、250构成。店铺包含架子280、收银机290和其 他设备。图2中，3D场景的布局由静态对象组成，例如走廊的地面、楼梯、 墙、架子。3D场景的其他对象(例如收银机)不是布局的一部分，因为这 些对象不是静态对象：事实上，收银机是能够移动的对象，除非收银机被 设计为布局的一部分并从而是静态对象。

然后，在图1中的步骤110，确定3D场景中的一组位置，这相当于说 在3D场景中标识两个或多个位置。可选地，可以仅确定一个位置。位置是 3D场景的对象可以到达的3D场景的一部分。典型地，动态对象可以到达 3D场景的位置。动态对象是能够在三维场景中潜在移动的对象。动态对象 因而是与静态对象相对的，静态对象从来不在3D场景中移动并不能被另一 个对象穿过。术语“位置”可以指3D场景的对象可进入的3D场景的划定 面积，或也可以指3D场景的其中包含3D场景的对象的体积。换句话说， 位置可以是由一个或多个对象占用的或可以占用的3D场景中的地点。

返回图2中显示的3D场景，由对象模拟顾客(未显示)。顾客能够行 走、浏览、挑选陈列在架子上的货物并将它们放入他们的购物车中。要知 道货物(未显示)也是对象。这些顾客和货物是动态对象，也就是说，能 够在3D场景中潜在移动的对象。这里，动态对象和可能动作的列表不是广 泛的，取决于应用程序的目的和3D场景支持的情节的本性。图2上所表示 的3D场景持续运转或由计算机资源处理。这涉及同时地用户在任何时候注 册/注销、商场中建立新店铺并开始营业、能够增加象电梯一样的新设备和 能够引进新的商品。换句话说，布局可以被修改，动态对象也可以被修改； 例如，顾客可以被抑制、增加或甚至修改。

因而，3D场景可以被考虑为包括静态对象的布局和在所述布局中移动 /发展的一组动态对象。有趣的是，位置和静态对象紧密相关。事实上，在 布局内动态对象的移动被静态对象所限制，所述静态对象定义了不能被动 态对象穿过的3D空间中的表面或体积。例如，在图3中，表示顾客34和 购物车35的对象是动态对象，其在静态对象走廊33(图2中被称为走廊 270、280)中移动。走廊33的地面可以被动态对象到达，因而能够被标识 为位置。作为另一个例子，表示堆32中的罐头的对象是动态对象，其能够 从一个架子31潜在地被移动(例如，他们可以被顾客抓取并放入购物车中)。 因此，显示实例30的架子31能够被确定为是位置。

返回参看图1，在步骤120，用达到最贵计算成本的每个位置的最大对 象占用来填充事先确定的每个位置。用位置的最大对象占用来填充位置意 思是对象被放在位置上，并且放在这个位置上的对象数量是允许放在该位 置的最大对象数量。这个最大对象数量是该位置的特征，这个特征可由3D 场景上播放或应用的情节定义。情节关于模拟的真实世界的是真实的，并 限制3D场景中对象的可能动作。

3D场景上的一个或多个对象是实例化的对象，这是本领域公知的。当 对象在3D场景中被实例化时，该对象产生计算成本。实例化的对象的计算 成本是实例化参数的函数。实例化的这些参数可以是，但不限制为，对象 的3D网格的选择复杂性、纹理精度、3D场景中对象的反射和阴影、与动 态行为(如接触/冲突、弹性、热传递等等)相关联的属性。要知道，当用 于位置上的最大数量对象的实例化参数最多时(如用最大的现实实例化)， 产生的计算成本最高。

根据图2，货物可以放在店铺200里的架子280上。例如，货物可以是 洗发水瓶，架子可以是位置。当3D场景播放真实世界模拟情节时，架子可 以支撑用最大现实实例化的最大数量的洗发水瓶，结果是为这个架子获得 了最贵计算成本。这种情况显示在图3中。显示实例30包括6个架子31。 显示实例30显示了带有最大允许的架子(31)的它的最高成本情况，每个 架子处于它们最高容量的堆(32)中的罐头，对于最贵CPU的罐头，具有 用于呈现的复杂3D网格和丰富纹理。

仍然根据图2，作为另一个例子，对象可以放在走廊270上。例如，对 象可以是拿着购物篮的用户。再次，当3D场景播放真实世界模拟情节时， 走廊可以包括最大数量的拿着购物篮的用户，其为架子产生了最贵计算成 本。这在显示位置的图3上举例说明，这里是走廊33(图2中被称为走廊 270、280)，其处于最高成本情况，当每个顾客34推着充满物品36的购物 车35，每个顾客和它的车处于“一个挨一个”的情况；也就是说，“一个挨 一个”的情况是更差的情况，其中走廊33包括最大数量的顾客。要知道， 对象(用户、车和物品)使用被选择用于产生最高计算资源成本的参数实 例来被实例化；例如，选择呈现参数用来获得对象的最精确表示。

有利地，步骤120可以仅为动态对象执行，也就是说，为能够在3D场 景中潜在移动的对象执行。事实上，动态对象具有不可预测的计算成本， 因为他们的计算成本取决于比如他们的数量、他们呈现的细节这些因素。 相反，静态的，也就是，不能够在三维场景中移动且不能够被另外的对象 穿过的对象，产生计算资源的可预测计算成本，或换句话，他们的计算资 源成本能够事先知道。

这样，在步骤120，当达到给定位置上可接受的最大数量的对象时和当 对象至少用最大现实被实例化时，达到该位置上的最贵计算成本。因此， 执行最高成本情况分析：虚拟世界的每个位置都被分析它的最高CPU成本 情况。

然后，在步骤130，计算3D场景的每个位置的最高计算成本密度。这 有利地允许为在步骤120执行的所有位置量化和表征更差的成本情况。为 步骤120填充的每个位置执行计算。

最高计算成本密度可以是指每面积单位或每体积单位的计算成本，取 决于位置的种类(面积，体积)。例如，如果位置是面积，那么最高计算成 本密度将是每面积单位的计算成本；作为另一个例子，如果位置是体积， 那么最高计算成本密度将是每体积单位的计算成本。显然，最高计算成本 密度能够包括3D对象的本性。这相当于说，最高计算成本密度可以根据所 述面积或体积单位上的3D对象的本性来计算。例如，对于同样的面积，最 高计算成本密度可以取决于是模拟基本3D对象比如立方体、球体等，或是 模拟复杂3D对象比如表面、网格等。

事实上，计算步骤130包括计算比率P/A，其中，P是用于处理达到它 的最贵计算成本的位置所需的计算资源的测量百分比，如根据步骤120所 讨论的，并且其中A是三维场景中位置的面积。可选地，A可以是三维场 景中位置的体积。计算资源P典型的是实施本方法的系统的处理器，或处 理区域的计算资源。

现在参看图4，举例说明了对根据图2所描述的大商场中的架子的最高 计算成本密度的计算。图4中，确定的位置40是包括其上放置动态对象(货 物)的显示实例30的三个架子31的体积。比率P/A的计算结果是每体积 单位的最高计算成本，例如每立方米的最高计算成本。

可选地，仍然根据图4，位置40的比率P/A的计算结果可以是每面积 单位的最高计算成本，例如每平方米。因为位置40是体积，所以表示该位 置的体积的面积被计算。为了这个目标，从体积40提取印迹(print)41： 这是指体积40的投影在跟随一个方向的投影平面上(例如商场的地面42) 完成，也就是说，通过将3D空间中的点线性映射到二维投影平面上的点来 构造投影。因而，印迹是面积。图4中，投影的方向由这里垂直于投影平 面42的箭头43表示。这个例子中投影平面可以是走廊33的地面。因而， 印迹41是体积40在投影平面42投影的结果。

典型地，投影平面可以是跨越3D场景延伸的平面，以便每个位置能够 投影到这个平面上。当在步骤110已经确定混合的面积和体积位置时，这 样的投影平面允许计算最高计算成本密度。事实上，所有位置(面积或体 积)都投影到投影平面上。在图4的例子中，3D场景是大商场，其中大商 场的地面是平面。在这种情况下，地面充当用于确定位置的平面：面积位 置比如商场的走廊在大商场的地面上被直接标识，体积位置的印迹比如架 子在大商场的地面上被计算。

通过运行几批基础的但是重要的情节来执行计算步骤130，这些情节满 足实时模拟以测量最高计算机资源成本情况下选择的典型位置的小的同质 面积的计算资源性能。

接着，在图1的步骤132，执行聚集计算出的3D场景的每个位置的最 高计算成本密度的步骤。聚集是指计算出的每个位置的最高计算成本密度 的结果被连接(或收集)到一起。

然后，在图1的步骤134，根据聚集的最高计算成本密度建立3D场景 的成本密度地图。术语“成本密度地图”指的是对计算出的最高计算成本 密度的表示。这个表示典型的用于2D平面，其可以与3D场景叠加，例如 3D场景的俯视图。换言之，成本密度地图是对与3D场景一致的最高计算 成本密度的表示。

有趣的是，成本密度地图可以建立在与位置可以在上面投影的一个投 影平面相同的平面上。通过这种方式，位置和计算出的最高计算成本密度 之间的一致更加容易保持。而且，因为作为位置在投影平面上投影的结果 预先建立3D场景地图，这有利地使得聚集和建立步骤132、134更加容易。

一旦成本密度地图已经建立，它可以被显示以便用户能够看到3D场景 的什么面积需要多少数量的计算资源。为了这个目标，地图可以提供图形 信息，显示了计算出的3D场景的位置的最高计算成本密度。例如，颜色色 标可以被用于表示最高成本密度。

现在参看图5，表示的是图2上表示的3D场景(大商场)的成本密度 地图的例子。作为计算、聚集和建立步骤130、132和134的结果获得这个 成本密度地图。图5中显示的成本密度地图是能够与3D场景叠加的一个平 面，例如图2的3D场景。图5中，成本密度地图由成本密度K_i多边形(i 是自然数)的集合组成，每个多边形K_i表示已为其计算了成本密度的位置。 例如，多边形K₈近似地对应于动态对象(放在架子上的货物)的位置。作 为另一个例子，多边形K₁对应于顾客和他们的车能够在其中移动的商场的 区域。

有趣的是，根据聚集的最高计算成本密度建立的地图可以是跨越3D场 景延伸的平面，以便3D中的每个位置投影到这个平面上。当在步骤110已 经确定混合的面积和体积位置时，这样的单一投影平面允许计算最高计算 成本密度。

在图1上描述的过程的这个步骤，作为步骤120到134的结果，已经 建立3D场景的成本密度地图。在步骤140-142，现在计算第二地图，其被 称为3D场景的约束地图。成本密度地图和约束地图的建立可以顺序执行， 或并行执行。对于两个地图，仅需要提供包括一个或多个对象的3D场景(步 骤100)和确定3D场景中一组位置(步骤110)。可选的，可以提供在3D 场景上播放的情节。可以用和3D场景相似的方式提供该情节。

在步骤140，为3D场景的每个位置提取位于所述每个位置上的静态 对象。如先前所见，静态对象是不能够在3D场景中移动并不能够被另外的 对象穿过的对象。术语“提取”意思是为标识3D场景的静态对象对3D场 景执行计算。这样，提取静态对象相当于标识静态对象。当虚拟世界被设 计时，可以由虚拟世界的知识引起对静态对象的标识。

接下来，在步骤142，根据在步骤140提取的静态对象建立3D场景的 约束地图。术语“约束地图”是指对静态对象的表示。这个表示典型地在 2D平面中完成，其可以与3D场景叠加，例如3D场景的俯视图。

约束地图的目的是提供对用于在步骤160将被分组的区域的实用规则 的图形转化。这些实用规则想要提供依赖于规则的适宜的成形区域。例如， 规则的范围可以涉及但不限制于环境的几何形状：事实上，如先前所见， 3D场景可以被考虑成包括能够为了特定情节而修改的布局，其该布局可以 包括不能够在3D场景中移动并不能够被另外的对象穿过的静态对象。另 外，其他规则可以管理除环境的几何形状之外的其他考量，如物理、工程 等等。

就成本密度地图而言，约束地图典型的是一2D平面，其可以与3D场 景叠加，例如图2的3D场景的俯视图。因为静态对象是3D对象，所以提 取步骤可以进一步包括提取3D场景的每个位置上的每个静态对象的印迹。 如先前根据图4所解释的，提取对象的印迹相当于说该对象的投影在依照 投影方向的投影平面上完成，以便完成从3D空间中的点映射到二维投影平 面上的点。

约束地图可以建立在与位置可以在上面投影的一个投影平面相同的平 面上。通过这种方式，位置和提取的静态对象之间的一致性更加容易保持。 一旦成本密度地图已经建立，它可以被显示以便用户能够看到3D场景的特 定面积上的约束。

现在参看图6，表示的是图2上表示的3D场景(大商场)的约束地图 的例子。这个约束地图是作为提取和建立步骤140和142的结果获得的。 通过提取一些静态对象的印迹，一些静态对象已从3D场景被提取，如图4 的实例所示。例如，显示实例30的一些支撑件66已经被提取。每个支撑 件66是不能够被任何其他的对象穿过的静态对象。作为从3D场景提取的 静态对象的另外的例子，有支撑大商场屋顶的桩子62、隔开商场店铺的隔 离墙64。

有趣的是，依附于支撑件66的架子31也是静态对象；它们不能在3D 场景中移动并不能够被任何其他的对象穿过。然而，当建立约束地图时它 们没有被提取。事实上，一个或多个动态对象可以潜在地位于架子上，如 图3或4所示，当架子的印迹被提取时，也就是说，当架子36的投影在投 影中面上(这里是地面42)完成时，潜在的一个或多个动态对象的投影(该 投影的执行类似于对架子的)可以至少部分的重新覆盖架子的印迹。因为 一个或多个动态对象的印迹很可能至少部分的重新覆盖静态对象的印迹， 所以当建立约束地图时没有保持架子。相反，没有动态对象可以放在上面 的支撑件66的印迹被保持。

约束地图可以是跨越3D场景的平面，以便3D场景中的每个位置可以 投影到这个平面上。当在步骤110已经确定混合的面积和体积位置时，这 样的单一投影平面允许提取静态对象。

返回到图1，一旦成本密度地图和约束地图已经建立，在步骤150处可 以聚集两个地图。聚集地图是指地图被合并。聚集两个地图可以通过叠加 两个地图来实行。特别是，当两个地图具有相同比例时，这个操作可以更 加容易地执行。要知道，术语“比例”指的是地图上的距离相对3D场景上 对应的距离的比率。

接下来，在步骤160，执行将相邻位置分组到一个或多个区域。位置是 相邻的，也就是说，每个位置与区域的另一个位置具有至少一个共同的点 或一个共同的边界。可选的，分组步骤可以包含部分相邻位置被分组到一 个或多个区域。因而，步骤160在于将虚拟环境分割为一个或多个区域。 例如，并参看图5，每个多边形K₈表示一位置并与另一个多边形K₁共享至 少一条边。由虚线表示的区域52包括部分相邻位置。

每个区域具有保证区域的实时性能的合成计算最高成本密度。这是指 实施本方法的计算机化系统的处理单元能够给区域提供确保实时性能的计 算资源。术语“实时性能”是指在严格的时间限制内提供有保证的响应。

执行分组以便每个区域的合成计算成本密度是这样的：用于处理该区 域所需要的计算资源低于预先定义的阈值。区域的合成计算成本密度是每 个位置的最高成本密度乘以它的面积的总和。换句话，通过用它的最高成 本密度乘它的面积来计算每个位置的最高计算成本，每个位置获得的结果 被加在一起。预先定义的阈值可以是实施本方法的计算机化系统的处理单 元的百分比，或者是区域的计算资源的百分比。尤其是，可以创建这样的 区域：它们形成叫做最小区域的区域，其中，在3D场景的最高成本情况下， 最小区域是它的CPU成本明显等于其相关联的处理资源的100％的区域。 优选的，CPU成本低于100％，例如因为满足约束的形状调整。

另外，将位置分组为一个或多个区域可以被执行以便两个或多个区域 之间的合成计算成本密度是明显一样的。这有利地有助于使得共享区域之 间的CPU的处理资源更加容易。特别是，当计算机化系统包括提供区域的 计算资源的两个或多个CPU时，CPU之间的负载更加容易被共享。

而且，通过考虑使用每个区域过去制造的计算资源，分组可以进一步 被执行。事实上，3D场景持续运转或由计算机资源处理，从而，新的动态 和静态对象可以连续不断地被添加、修改或抑制。这样，优选地，用于分 割3D场景的方法可以被定期执行以便3D场景的修改可以被考虑。例如， 在经过预先确定的一段时间之后，该方法可以再次被执行。可选的，在已 经完成了对3D场景的一个或多个修改之后，可以再次执行用于分割3D场 景的方法。因为本发明的方法已经被执行了几次，所以有可能知道过去使 用的每个区域的计算资源，从而可以标识仅使用了一小部分分配给它的计 算资源的区域。事实上，根据区域的合成计算成本密度分配用于处理该区 域的计算资源被降低了。这可以通过降低预先定义的阈值来执行。

可以根据用户动作执行分组，例如通过与3D场景的位置被显示在上面 的显示进行交互。为了这个目标，可以通过显示为用户提供图形编辑工具， 如图7上所示；通过将区域分割编辑器的视图与约束地图叠加和与成本密 度地图叠加来产生该显示。当编辑和拖拽区域46的形状时，用户连续接收 对产生的区域的CPU成本(这里是75％)的更新。对区域的拖拽相当于执 行对区域分割编辑器上的面积的选择，可以由用户经由触觉设备执行该选 择，比如键盘、鼠标、定位笔、或直接是显示器，例如显示器是触敏屏幕。 例如，在两键鼠标中，当移动光标44时左键可以用于选择一个面积。

另外，可以协助用户定位区域的定义点：基于从约束地图提取的规则， 用户的拖拽能够被操纵或禁止。对于图2上表示的大商场实例，这样的协 助将使得区域区段与墙一致，或与最近的架子保持垂直。

可以通过用于编辑区域的一个或多个规则进一步协助用户，例如，但 不限制为：

·区域不能够具有包含需要超过计算机化系统的处理单元的100％的 计算成本的合成计算成本密度；

·区域不能是成块的；

·区域具有最少可能数量的带有可交叉边界的相邻区域；

·区域具有与相邻区域最短长度的交叉边界；

·区域具有尽可能的最紧凑的形状。

还可以根据执行该方法的系统的计算自动执行分组。这可以通过使用 优化程序来执行，所述优化程序能够自动产生虚拟环境到区域的可能分割， 这接近差不多可能100％的计算资源的CPU功耗。

已经描述了本发明的优选实施例。要知道，不脱离本发明的精神和范 围可以进行各种不同的修改。因此，其他实现包含在下面的权利要求范围 内。