法律状态公告日
法律状态信息
法律状态
2008-05-28
专利权的终止(未缴年费专利权终止)
专利权的终止(未缴年费专利权终止)
2006-07-26
授权
授权
2004-08-04
实质审查的生效
实质审查的生效
2004-05-26
公开
公开
相关申请的交叉引用
本申请要求于2001年3月27日申请的、名称为“使用立方根高度定标来指定多边形预算,范围和对象尺寸到空间层次的系统和方法”的共同未决临时申请系列号60/279,181的权利。
技术领域
本申请涉及确定用于在显示设备上表示图像的多边形数据的空间层次。更特别地,本申请涉及通过使用立方根高度定标来指定多边形预算,范围(range),对象尺寸等到空间层次的系统和方法。
相关技术描述
视觉场景的计算机生成受数据存储中的局限性和场景中对象的表示所约束。已经提出许多图像绘制技术。
美国专利号4,715,005描述一种使用数学模型数据库来计算机生成丘陵区和海景的视觉场景的技术。数学公式确定必须用来覆盖显示器的一部分的地形或海洋的范围。地形和海洋使用正弦波来模拟。既没有描述也没有提出(i)使用数据多边形表示和/或(ii)使用数据(地形)的层次表示。在专利号4,715,005中也没有描述或提出使那里在地形和海景的环境中描述的技术适合于人文特征(例如建筑物)。
美国专利号5,367,615描述顶点的空间增加以及用于平滑改变地形多边形密度的细节过渡的连续级,其中细节是统计获得的。在美国专利号4,715,005中没有描述或提出使那里在地形的环境中描述的细节处理技术适合于人文特征(例如建筑物)。而且,既没有描述也没有提出数学地推导范围圈。
概述
本申请提供一种用于确定多边形数据的空间层次的系统和方法。该方法包括,根据一种实施方案,获得切换范围,并且通过使用切换范围和立方根定标因子来确定空间层次的多边形密度。
该方法包括,根据另一种实施方案,基于高度参数来确定立方根定标因子,并且使用立方根定标因子来定标空间层次的细节级切换范围。
该方法可以包含在存储于计算机可读介质,例如致密盘(CD)上,和/或通过计算机网络,例如因特网,或其他传输介质来传送的计算机程序(或者一些代码单元)中。
本申请也提供一种用于确定多边形数据的空间层次的系统。在一种实施方案中,该系统包括用户接口和特征分析仪。特征分析仪通过使用通过用户接口获得的(i)立方根定标因子和(ii)切入距离和切出距离来确定空间层次的多边形密度。
立方根定标因子可以基于高度参数来确定。空间层次可以是基于瓷砖的(tile-based)。多边形数据可以对应于人文特征。
空间层次的设计参数可以通过用户接口来获得和/或修改。例如,下面的一个或多个可以通过用户接口来获得和/或修改:空间层次中的级数;空间层次的每一级的瓷砖的范围;将插入到空间层次的每一级中的多边形元素的临界尺寸;以及空间层次的每一级的瓷砖的切换距离。
附图简述
本申请的特征可以从下面参考附图的详述中更容易明白,其中:
图1A和1B显示从所选视点看到的计算机屏幕主体带的各个二维图形表示;
图2显示垂直视场的图形表示;
图3显示从显示屏中心开始垂直密度减小的图形表示;
图4显示从显示屏中心开始水平密度减小的图形表示;
图5显示当定标开启时,瓷砖的地面范围作为高度的函数的图形表示;
图6A和6B显示在各个附加和替代的设计中,用于确定对象尺寸的临界距离的图形表示。
图7显示根据本申请一种实施方案的点特征密度分析工具中的输入表单;
图8显示根据本申请一种实施方案的点特征密度分析工具中的输出瓷砖设计表单;
图9显示根据本申请一种实施方案的点特征密度分析工具中的输出特征尺寸表单;
图10显示根据本申请一种实施方案的点特征密度分析工具中的输出四叉树表单;
图11显示根据本申请一种实施方案用于确定多边形数据的空间层次的系统的框图;
图12显示根据本申请一种实施方案用于确定多边形数据的空间层次的方法的流程图;并且
图13显示根据本申请另一种实施方案用于确定多边形数据的空间层次的方法的流程图。
详述
本申请提供用于确定在显示器和/或输出媒体(例如传统显示器和输出设备)上表示图像的多边形数据的空间层次的新的方法学(例如,以系统和方法的形式)。在空间层次中,显示特征(feature)的细节级根据视点和特征之间的距离而变化。
可以使用由本申请提供的密度计算方法,与特征优先化方法一起,以提供源特征数据的选择和几何模型到数据库的特定细节级的指定。由本申请提供的方法可以用来使数据库中的特征内容最大,而不超过图像绘制系统的容量。该方法也可以用来实现任何高度的恒定多边形密度。该方法可以适用于例如飞行模拟/视觉模拟/地理数据库,系统或软件。
根据图11中所示的一种实施方案,系统110包括用户接口111,特征分析仪112以及显示器113。特征分析仪112包括定标模块112a。用户接口111和/或特征分析仪112可以是存储于计算机可读介质中和/或通过计算机网络或其他传输介质传送的计算机程序。
根据本申请的一种实施方案,一种用于确定多边形数据的空间层次的方法将参考图11和12来描述。切换范围通过用户接口111来获得(步骤121)。多边形密度由特征分析仪112使用切换范围和立方根定标因子来确定(步骤122)。
根据本申请的另一种实施方案,一种用于确定多边形数据的空间层次的方法将参考图11和13来描述。立方根定标因子由特征分析仪112基于通过用户接口111获得的高度参数来确定(步骤131)。特征分析仪的定标模块112a使用立方根定标因子来定标空间层次的细节级的切换范围(步骤132)。
现在将提供用于确定多边形数据的空间层次的系统和方法的更细节描述。
假设多边形预算例如与数据库中的存储空间相对应,地面上(假设为平地)的理想多边形密度可以表示为观察高度z和到视点的距离d的函数,如下:
chaninfo*预算*(z/d3),其中
FOVh表示水平视场,FOVu表示垂直视线之上的角度,而FOVd表示垂直视线之下的角度。
对于给定(指定)高度z0,上面等式可以用来计算多边形瓷砖可能包含的多边形的(理想)数目(依赖于瓷砖的切换范围和范围)。
当在与设计高度z0显著不同的高度z绘制时,多边形预算可能被破坏,例如在高的高度几乎没有多边形,而在低的高度有非常多。这可以通过用立方根定标,(z/z0)1/3,定标细节级(LOD)切换范围来防止。
1连续区中的分析
1.1对应于水平屏幕带的地面上的区域
为了计算多边形密度,参考图1A和1B,考虑计算机屏幕的水平带(对应于从视点看到的角度θ;t=tanθ),并且相应的地面区域如下来确定:
其中,FOVh表示水平视场,p表示视点高度z0的仰俯角,并且
中间结果如下:
等式(1)可以大大地简化,通过选择非常小的θ,从而实现t<<tanp,对于所有斜度(因为远剪取平面的存在暗示着p具有下界),使得下式成立:
为了计算正确的多边形密度,当将水平视场与地面相交时,角度β实际上小于FOVh。
1.2连续区中的多边形密度
为了确定多边形密度,焦距首先从垂直视场参数中确定。如下面所说明的,描绘给定对象的垂直象素的数目使用焦距来确定。
参考图2,垂直视场一般是不对称的,具有垂直视线之上的角度FOVu和垂直视线之下的角度FOVd。下面式子可以参考图2来确定:
象素的垂直数目=upix+dpix,
焦距=upix/tanFOVu=dpix/tanFOVd,
为了从等式(1)推导密度(density),分配给水平屏幕带(角度θ)的多边形数目n除以等式(1)的面积。
获得下面的等式:
1.3密度下落和校正
屏幕(视线)中心的密度典型地大于周围。等屏幕面积的垂直带在屏幕的底部和顶部边缘对应较小的角度。上视场的总体减小如下,并且类似的等式对下视场成立:
总垂直密度减小是等式(3)对于上和下视场由(tanFOVu,tanFOVd)加权的平均值。具有相等的屏幕长度增量(t),与屏带相对应的角度随着离屏幕中心的角度从θ减小到θcos2ψ,如图3中所示。
现在参考图4,在屏幕的左和右边缘,到投影在屏幕上的对象的距离比在中心大。因此,密度乘以cos3。总体水平下降(cos3)如下:
多边形预算可以通过除以等式(3)和(4)的乘积来增加。等式(4)中的最大角度小于FOVh/2,对于不等于零的与垂直视线的偏角ψ(最大角度的正切乘以cosψ)。而且,瓷砖式排列的人工制品可以减轻水平减小。密度减小可能是有益的现象,假设屏幕中心应该得到更多细节的话。
2分层瓷砖式排列系统的分析
2.1瓷砖的多边形密度
如果(d1,d2)表示瓷砖的切换范围,并且z0表示设计高度,适当的瓷砖密度可以通过求等式(2)的总的多边形贡献对覆盖在d1和d2之间的地面面积的平均值来计算,如下:
对地面范围r积分和对斜距d积分是相同的,如由下面的变量变换所显示的:
rδr=dδd
瓷砖的多边形预算可以通过用等式(5)乘以瓷砖面积来获得。
可以考虑附加的和替代的瓷砖层次。在附加的平铺层次中,切出距离对每个瓷砖是零。当子瓷砖切入时,它们增加多边形密度。父瓷砖不切出,除非到瓷砖中心的距离大于该瓷砖的切入距离。
在替代的层次中,当瓷砖切出时,占用由切出瓷砖留下的空位的子瓷砖被强行切入,代替父瓷砖。由此可见,仅有切出信息用来确定可见性。替代的层次的多边形密度等式如下:
其中d1是瓷砖的切出距离,而d2是“切入距离”(父瓷砖的切出距离)。
对于附加的层次,相同的等式用作出发点,其中d2表示瓷砖切入距离,d1表示下一个较小瓷砖集的切入距离,并且给它加上所有较大瓷砖的累积密度(因为密度正在增加)。
2.2定标LOD切换范围
为了确定如何“变换”切换距离以使z0的密度曲线与z的密度曲线相匹配,恒定的密度强加到等式(2),并且立方根定标如下直接获得:
在定标之后,使高度与切入距离si相等,给定瓷砖可见所处的最大高度如下获得:
在显著小于较小瓷砖的切入半径的高度使用立方根定标在某些情况下可能是不适合的。例如,立方根定标匹配理想的密度曲线,从而假设同样具有更高密度的较小瓷砖可以无限获得。
而且,一旦高度小于最小切入半径的某个分数,当高度减小时,所有地面范围仅最低程度地增加。从而多边形数保持大约恒定而不定标。例如,第二次观察,最小瓷砖的地面范围r可以作为高度的函数来绘制,如图5中所示,假设定标开启,使用如下等式:
其中,si是该瓷砖的静态(定标前)切入半径。对应最大范围的高度,其通过求出使r2的导数为零的高度而获得,如下:
这个高度对应于定标的良好固定高度。在该高度之下,定标同时减少所有级的多边形数,没有附加的级来填充间隙。
2.3填充每组瓷砖的对象的推荐尺寸
用户定义MINPIX值,以及MAXPIX值,例如[1象素,4象素]。MINPIX是对象可以的(垂直)象素(通道不需要使用方形象素)中的最小尺寸。MAXPIX是当对象切入(或“弹入”)瓷砖和从切出瓷砖时,对象可以的(垂直)象素中的最大尺寸。
考虑下面:
图6A和6B显示在分别是附加和替代的方案中,用于使用等式(7)来确定合适的对象尺寸的距离,其中使用的MINPIX为d2并且MAXPIX为d1。因此,最小和最大对象尺寸可以对于瓷砖在该高度上是可见的所有高度来确定[参看等式(6)]。
用户可以指定最小瓷砖的地面范围,例如以瓷砖直径的因子来表示。在3附近的数是合理的选择,其指定大约十到二十个这种瓷砖是可见的。设计高度z0可是设置在该地面范围内,如上所述。定标在上面比在下面(最小瓷砖的限度)工作得更好。但是,设计高度不能比该第一地面范围小太多(在必须固定定标之前提供一些上下定标杠杆)。
随着z0如上所述地确定,第一切入距离可以确定。随后的切入距离可以被设置,以在每个瓷砖中具有大约相同的多边形数(可能具有一些调整)。例如,如果瓷砖的尺寸加倍(如在四叉树中),那么密度除以四,这当切入距离乘以(4)1/3≈1.6时发生(参见等式(2))。
立方根定标在变化的高度精确匹配(理想)密度曲线。为了对整个多边形数据库使用单一的标度,多边形瓷砖可以在相同的高度设计并且使用等式(5),即使并不是所有的瓷砖都可见,以指定密度。
示范性实施方案在下面描述。该实施方案使用电子表格来提供用户接口。但是,应当理解,也可以使用或交替使用其他类型的用户接口。例如,用户接口可以是标准的,常规的或专用的图形用户接口中的一种或其组合。用户接口也可以包括语音接口特征,这些特征也是传统已知的因此不在这里详细讨论。
3点特征密度分析工具
点特征密度分析工具(PFDA)可以用来指定描绘例如人文特征的多边形数据的瓷砖基空间层次。可以被指定的信息包括层次的类型(附加的或替代的),层次中的级数,层次每一级的瓷砖的范围,以及每一级的瓷砖的切换距离。指定信息也可以包括将应用到每一级的多边形密度,LOD定标函数(其是高度的函数),以及将插入到每一级中的多边形元素的临界尺寸(下面描述)。PFDA提供用户接口和特征分析仪。点特征选择和分配工具(不在这里讨论)可选地可以用来指定实际的特征到人文层次的瓷砖。
临界尺寸是在显示器上看见的特征的尺寸,或者相同特征的两种显示之间的尺寸的差。一般地,这是特征的最大尺寸,但是依赖于特征的类型,其他情况可以应用。一些具体情况的实例包括飞机场,无线电塔以及其他“线框”特征,以及特别拉长的特征。当替换模型时,使用两个模型之间差的量度。
临界尺寸用来确定模型在场景中适合的范围。一个极端的例子是房屋模型,门的纹理画面处于低LOD并且多边形门框处于高LOD。高LOD的临界尺寸仅有1/2英寸!虽然门是7×3英尺,门框仅当观察者足够近以识别门的1/2英寸厚度时是成比例的。临界尺寸是建模的考虑因素,并且仅可以由模型几何的算法检验来粗略地估计。
根据一种实施方案,PFDA可是实现为用于分析点特征(建筑物,桥梁,树木等)的Excel电子表格,但是也可以提供用于分析其他可见元素的装置。PFDA可以具有内置的确认步骤,通过该步骤可见的瓷砖对于广阔范围的高度和视线交互地计算,以模拟多边形预算如何在各种设置下使用,假设遵循每个瓷砖的多边形数的推荐值。
图7显示示范性的输入表。由PFDA提供的下面的输入可以由用户来修改:(a)通道和视图信息,包括水平和垂直视场,象素数目,视场深度(到远的剪取平面的距离);(b)瓷砖式排列方案定义,包括以米为单位的地理单元的覆盖范围,四叉树级数,以及地理单元中的四叉树数目;(c)设计参数,包括多边形预算,当相应的瓷砖切入或切出时屏幕上以象素为单位的对象最小尺寸(minpix)和最大尺寸(maxpix),以及minpix和maxpix与其相关的最大高度maxAlt;以及(d)四叉树显示设置(设计确认),包括垂直视线,高度,以及视点的x,y坐标。一旦通道和视图信息,以及设计参数被输入,大部分设计工作包括完成瓷砖式排列方案定义。
设计定义可以在单元格N3-6中输入。用户在单元格N3-4中输入“瓷砖中对象的最小和最大尺寸”(minpix和maxpix)参数。Minpix指出在屏幕上在任何时间任何对象可以是多小(一般地,一个象素是合理的选择)。Maxpix指出当对象随着它的瓷砖切入或切出而“弹入”和“弹出”时对象可以是多大。如果对象用该对象的不同LOD取代时,那么两者之间的视差是所要测量的。多边形预算可以在单元格N5中输入。minpix和maxpix与其相关的最大高度可以在单元格N6中输入。
瓷砖式排列方案定义可以通过单元格E13-20输入。总的覆盖尺寸在单元格E13-14中指定。用户可以选择在x和y方向E15-16将其分成任何数目(整数)的四叉树。
四叉树级数可以在单元格E17中输入,并且典型地在2到8之间。有效级的数目也可以反映在输出表格中。四叉树中的级数越多,最高LOD处产生越小的瓷砖,从而也有机会显示更小的特征。这是以增加的挑选深度和更大的区域文件存储空间为代价而得来的。
第一范围带(最高LOD)中的瓷砖数目可以在单元格E18中输入,并且是特别感兴趣的参数。当增加该数目时,在第一带之后,所有范围带的尺寸增加。从而获得更精细粒度的四叉树,通常对应于多边形预算的更优美的匹配。这是以每个瓷砖较低的多边形数,和较大的挑选和切换负载为代价而获得的。降低该数目使得瓷砖切换更加积极,因此增加层次级在替换设计中被跳过的可能性。四叉树模拟提供这种效果的可视化。
“每瓷砖多边形的减小率”可以在单元格E19中输入,并且用来控制随后四叉树LOD的每瓷砖的多边形数目。当设置为1时,它近似恒定。当增加时,每瓷砖的多边形数目减小,并且范围带的尺寸减小。
层次类型(附加=1,替代=0)在单元格E20中指定。附加层次使得特征随着观察者的靠近而切入并驻留。在替换层次中,随着观察者的靠近,特征用更高多边形数的版本来替换。这个选择对密度在整个场景中分配的方式以及使用模型的类型有重大的影响。四叉树模拟提供这种效果的可视化。
输出概要(行24~35)可以在输入表格上提供(见图7)。每个瓷砖的切换范围(斜距)在单元格N27-034中显示。切换范围受到由定标模块执行的基于高度的定标。在定标模块中用于定标的输出参数在输入表格的单元格N18-19中提供。定标模块依赖于高度而使用N18∶20中的信息来定标这些值。
单元P27-Q34显示每个瓷砖的实际多边形预算以及以每1平方公里多边形数目为单位的实际密度。使用这些输入,用户可以确定什么样的累积密度是合理的。减少四叉树级数(E17),显著地减少最高级的密度。增加覆盖范围内四叉树的数目(E15∶16)增加该密度。增加最高级的范围带中瓷砖的数目(E18)减小该密度以及每瓷砖的多边形。增加每瓷砖多边形的减小率(E19)仅影响随后级(低于最高级)的每瓷砖的多边形,但不影响最高级的多边形数和密度。
单元格R27-T34显示每个瓷砖的推荐的最小和最大对象尺寸,基于在单元格N3∶N4中输入的信息。如果最小尺寸超过最大尺寸,Min>Max出现在T列中。尺寸分布是符合要求的,如果“Min>Max”不出现,如果尺寸范围匹配用户数据,并且如果瓷砖之间的间隙不是太宽。增加四叉树的级数提供较大的分布和较小的尺寸。增加每覆盖范围的四叉树的数目全局地减小尺寸。增加每瓷砖多边形的减小率可以消除Min>Max问题,以较大瓷砖中很少的多边形为代价。相同方法使用于增加最高级的范围带中的瓷砖数目。此外,在改变这些中的任何一个之后,用户可以按压四叉树模拟按钮来使可见瓷砖的新的挑选负载和数目生效。
为了使每种类型的可见瓷砖的数目和给定高度的可见多边形的数目生效,四叉树宏可以通过按压单元格K25-L25中的“运行四叉树模拟”按钮来激活。然后,对于所选高度(N9)和视线(N10)的可见瓷砖的图形显示在输出四叉树表格中产生(图10)。
单元格K27-L31显示确认/模拟的概要,包括LOD挑选(L28)和截锥体(frustrum)挑选(L29)负载的测量。可见的瓷砖(L30)和多边形(L31)的数目也可以提供。在单元格L31中指出的多边形数目近似地对应预算,依赖于高度(N9),垂直视线(N10)以及视点位置(N12-13)。在输入数据的任何改变之后,激活“运行四叉树模拟”按钮,使得这些数目可以更新。它们基于在模拟中计算可见的瓷砖,但是不表示实际场景图可能提供什么。
更详细的输出信息可以在其他表格上提供,例如图8-10中所示,包括下面:(1)每瓷砖的多边形数以及瓷砖静态切换范围(输出-瓷砖设计表格:图8);(2)对一个范围的高度,推荐的最小和最大特征临界尺寸(输出-特征尺寸表格:图9),其显示在给定输入条件下所选的瓷砖;以及(3)所选设计的图形确认(输入-四叉树表格:图10)。
现在将描述在输出-瓷砖设计表格(图8)中的输出。在该工作表中计算的静态切换范围(单元格A11-18)和每瓷砖的多边形计数(G11-18)在输入表中拷贝。用户可以通过在单元格H11-18中键入许多他/她的选择来覆盖多边形密度等式。
当执行四叉树确认时(通过按压输入表格中的“运行四叉树”按钮来触发),确认输出被提供,包括挑选和LOD切换负载(G2,G3),可见的瓷砖(F11-19)和可见的多边形数(I11-19)。这些可见的瓷砖和多边形使用模拟来计算,但是不用于密度计算(代替地,使用一般的等式)。它们依赖于观察参数(高度,仰俯角,视点的x和y位置)。模拟仅执行瓷砖挑选,与精确的观察截锥体挑选相反。而且,观察截锥体可能大于模拟的工作空间。因此,输入的多边形预算不与单元I19中的精确匹配。而且,模拟假设精确的多边形数(G11-18,或者H11-18当用户选择覆盖时)应用到每个瓷砖,如由将聚集的特征的人造物到地理瓷砖所示的。改变模拟的视点位置在瓷砖挑选过程中导致混迭效应。“动态人文定标”在定标模块中启用。
现在将描述输出-特征尺寸表格(图9)中的输出。下面的表格(B17-I24)指定最大LOD-瓷砖级(LOD1)的特征临界尺寸的范围。minpix和maxpix输入值对于一定范围的高度转换成以米为单位的特征临界尺寸,从在输入表格中指定的maxAlt开始,并且以指数级减小。在所有高度,低于单元格B24且大于单元格C17的尺寸不违反约束。单元格I17中的值,其在单元格I18-24中重复,是单元格B24和C17的几何平均值。
上面的表格(B4-I11)应用到其他LOD。用户在单元格D2中指定适当的LOD数目。右边的图表说明与上面的表格相对应的最小和最大特征临界尺寸。
输出-四叉树表格(图10)提供在按压输入表格中的“运行四叉树模拟”按钮之后,在细节级和观察截锥体挑选之后的可见瓷砖的图形布局。
上面具体的实施方案是说明性的,并且可以不背离公开内容的本质或者附加的权利要求书的范围,在这些实施方案上引入许多变化。在该公开内容和附加的权利要求书的范围内,不同说明性实施方案的要素和/或特征可以彼此组合和/或彼此取代。
例如,通过阅读于2001年3月27日申请的美国临时申请系列号60/279,181,在此引入仅作参考,附加的变化对本领域技术人员将是显然的。
机译: 通过调整立方根比例尺确定多边形数据空间层次的系统和方法
机译: 通过使用立方根缩放确定多边形数据的空间层次的系统和方法
机译: 通过使用立方根缩放确定多边形数据的空间层次的系统和方法