使用立方体图的实时多分辨率3D冲突检测

摘要

公开了使用立方体图进行实时的、多分辨率的3D冲突检测的装置、系统和方法。例如，公开了一种方法，包括：接收第一多面体；接收第二多面体，随后使用存储在存储器中的纹理图检测在第一和第二多面体之间的冲突。还公开了其它实施方式。

说明书

背景技术

在三维(3D)图形中的冲突检测是确定两个对象是否彼此接触的处理过程，其中这两个对象通常是包括链接的多个多边形(例如三角形)的刚性体。通常，这通过使处理器执行算法以计算一个对象的三角形是否在空间上与另一个对象的三角形相冲突来实现。尽管存在针对这个问题的多种方案，但所有标准解决方案都使用处理器来执行包括以下步骤的计算：使用空间数据结构，例如八叉树，来测试对象到对象的冲突；并随后执行一系列几何计算，来为其包围体(bounding volume)显示为是相交候选的那些对象评价多面体到多面体的冲突。

当在诸如中央处理单元(CPU)之类的处理器中执行时，用于冲突检测的这些常规方案会占用相当大的计算资源，这些资源在进行诸如物理计算之类的CPU专用任务或执行人工智能例程时能够得到更好的利用，尤其是在3D游戏背景中。而且，通过在CPU中而不是在诸如图形处理单元(GPU)之类的专用图形处理器中执行冲突检测，常规方案不能利用由现代图形纹理采样硬件所支持的硬件图元。

附图说明

包含在说明书中，并组成其一部分的附图示出了与本发明原理相一致的一个或多个实施方式，附图与本发明的说明一起解释这些实施方式。附图并非一定是按照比例绘制的，相反地，重点在于示出本发明的原理。在附图中，

图1示出了根据本发明一些实施方式的3D渲染引擎或装置的多个部分；

图2是示出根据本发明一些实施的一个处理过程的流程图；

图3是示出根据本发明一些实施的一个处理过程的流程图；

图4-7示出了多个实例方案，用于论述图2和3中的处理过程；及

图8示出了根据本发明一些实施方式的一个系统。

具体实施方式

以下说明参考了附图。在不同附图中相同的参考数字标记用于标识相同或相似的元件。尽管以下说明通过阐述特定细节，例如具体结构、架构、接口、技术等，提供了对所声明的发明的不同方面的全面理解，但此类细节是为了解释的目的而提供的，不应视为限制性的。而且，按照本公开内容，本领域技术人员会意识到，可以在脱离这些特定细节的其它实例或实施方式中实现所声明的发明的各种方面。在以下的公开内容中的某些时机，省略了对公知的装置、电路和方法的说明，以避免由于不必要的细节而使本发明的说明不清楚。

图1是根据所声明的发明的一些实施方式的3D渲染引擎100的多个部分的简化框图。引擎100包括：冲突检测算法102、纹理采样器104、和纹理存储器106。本领域技术人员会认识到，3D渲染引擎可以包括其它组件(例如镶嵌单元(tessellation unit)，顶点着色器等)，已经从图1排除了这些组件，以便不会混淆本发明的实施。另外，尽管本发明不限于这一点，图1包括像素着色器108，其可以将算法102耦合到纹理采样器104。而且，尽管图1示出了一个纹理采样器104，但是本领域技术人员会认识到，在不脱离所声明的发明的范围和精神的情况下，可以实现一个以上的纹理采样器，和/或这些纹理采样器耦合到冲突检测算法102和/或存储器106。

冲突检测算法102可以包括检测例程，所述检测例程包括可以用于检测对象之间的冲突的软件和/或固件的任何组合。为此，算法102可以为纹理采样器104提供一个或多个查询索引。可替换地，算法102可以为着色器108提供一个或多个查询索引，并且着色器108可以将这些索引传送到纹理采样器104。采样器104随后可以使用这些索引来访问在纹理存储器106中保存或存储的纹理图的相应纹理地址处所存储的距离数据，所述距离数据以下会更详细解释。本领域技术人员会认识到，算法102可以包括冲突检测核，其由在支持引擎100的计算系统上执行的3D图形应用程序(未示出)产生。可替换地，算法102可以包括由像素着色器108产生的冲突检测核。本领域技术人员还会认识到，术语对象、几何结构、多边形、体和多面体可以互换地使用。

纹理采样器104可以是能够根据由算法102提供的一个或多个查询索引来访问存储器106中的纹理数据的任何纹理采样逻辑，包括硬件、软件和/或固件的任何组合。根据本发明的一些实施方式，存储在存储器106中并由采样器104访问的纹理数据可以包括纹理图，例如立方体图，其包括存储距离值的像素(或“纹理像素(texels)”)阵列，所述距离值以下会更详细解释。采样器104随后可以使用由算法102提供的索引来确定用于访问存储和/或保存在存储器106中的相应距离值的相关纹理地址。采样器104随后可以使用这些距离值产生插值的距离值，并可以将这些插值距离值提供给算法102，如以下会更详细说明的。可替换地，采样器104可以将这些距离值提供给着色器108，着色器108可以产生插值距离值，并将这些插值距离值提供给算法102。

纹理存储器106可以包括适合于存储和/或保存一个或多个纹理图(例如一个或多个立方体图)的任何存储装置或机构，并指定了纹理像素数据，例如距离值。尽管存储器106可以包括任何易失性或非易失性存储技术，例如随机存取存储器(RAM)存储器或闪存，但是本发明决不受所使用的用作存储器106的存储器类型的限制。

图2是示出根据本发明一些实施方式的处理处理过程200的流程图。尽管为了易于解释，可以针对图1的引擎100来说明处理过程200，但所要求发明不限于这一点，由根据所声明的发明的适当装置支持的其它处理过程或方案也是可行的。

处理过程200可以开始于第一多面体的接收[动作202]和第二多面体的接收[动作204]。根据一些实施方式，动作202和204例如可以包括冲突检测算法102接收第一和第二三角形的顶点坐标，例如，在这里相对于可由3D图形应用程序(未示出)实现的一个模型坐标系来定义这些坐标。这个3D图形应用程序可以产生算法102，并可以为算法102提供几何图元，例如三角形。

本领域技术人员会认识到，作为总冲突检测过程的一部分，算法102在动作202和204之前可能已经使用空间数据结构(例如八叉树或kd树)使3D图形对象经过了琐碎拒绝阶段(trivial reject phase)。在如此进行时，算法102可能已经确定了两个对象，一个包括动作202的第一多面体，另一个包括动作204的第二多面体，已经通过了这个琐碎拒绝阶段，从而这两个对象是进一步冲突检测测试的候选。与进行冲突检测过程的琐碎拒绝阶段的各种方法有关的细节超出了所声明的发明的范围，并且是本领域公知的。

处理过程200还可以包括产生用于存储距离值的纹理图[动作206]。根据本发明的一些实施方式，可以在处理过程200中任何其它步骤之前进行的预处理阶段中，由应用软件来进行动作206。在本发明的其它实施方式中，可以在与处理过程200的其它动作同时的运行时间中，由应用软件来进行动作206。无论如何，本发明不受何时进行动作206的限制。

图3是示出了处理过程300的流程图，根据本发明一些实施，可以进行处理过程300来产生根据处理过程200的动作206的用于存储距离值的纹理图。尽管为了易于解释，可以针对图1的引擎100来说明处理过程300，但所声明的发明不限于这一点，由根据所声明的发明的适当装置支持的其它处理过程或方案也是可行的。

图4示出了一个代表性的立方体图标记方案400，虽然该方案400有助于对处理过程300和/或相关处理过程的论述，但是其决不应解释为限制所声明的发明。方案400显示了3D立方体图图元402，如本领域技术人员会认识到的，图元402可以对应于如由公知的3D图形应用程序(例如DirectX)所定义的标准立方体图图元，尽管本发明并不限于具体的立方体图图元。图402可以由6个二维(2D)纹理图404-409组成，这些纹理图被排列为立方体的面，其中，图404-409每一个都可以包括8×8的像素阵列，并且其中，图404-409中的每一个像素都能够存储浮点距离值，如以下会更详细解释的。然而，本发明并不限于图404-409的特定分辨率，且本发明也不限于在图404-409中的像素位置上所存储的数据类型。而且，本领域技术人员会认识到，3D立方体图402的2D图404-409每一个都可以被视为是数值的查询表，这些数值可以通过使用指定图404-409的具体像素的索引来访问。

如本领域技术人员会认识到的，2D图404-409中的每一个像素的坐标都可以由3D方向向量410来索引，该方向向量以立方体图402的原点412为起点。在本发明的一些实施方式中，原点412可以对应于对象(例如多面体)的质心，如以下会更详细解释的。然而，本发明不限于如何定义原点412，因此，例如，原点412可以包括对象的外心。本领域技术人员还会认识到，可以定义一组唯一的方向向量，以使得这组向量中的每一个向量都穿过一个2D图404-409中的相应像素。例如，向量410穿过图408中的像素414，在此图408对应于立方体图402的+X面，并且在此像素414可以对应于图402的一个具体的(u，v)纹理坐标对。因此，向量410可以由原点412和对应于像素414的纹理坐标对来定义。

根据本发明的一些实施方式，原点412可以是对象的质心或对象的外心。然而本发明不限于这一点，因此原点412可以包括位于对象内的任何点。而且，尽管在处理过程200和300中所用的纹理图元可以包括立方体图图元，但本发明不限于这一点，因此，例如，可以使用其它3D纹理图元来进行处理过程200和300，例如采用了多于6个2D面的纹理图元，或者例如抛物面或球面纹理图元。

处理过程300可以开始于对第一多面体的原点的确定[动作302]，在此该多面体与在处理过程200的动作202中所接收的多面体是同一个多面体。本领域技术人员会将用于确定多面体的包围球(bounding sphere)的公知技术认知为根据动作302确定多面体原点的一种方式。为了论述的原因，图5示出了方案500，其用于根据动作302的一些实施方式确定包围球。尽管为了说明的目的，图5以2D形式示出了包围球502和相关的多面体504，但可以在产生3D包围球的3D多面体上进行动作302的实施。

本领域技术人员会认识到，包围球502表示一个假定球面，该假定球面包围多面体504，从而使球面502的标量半径505定义了从该球的中心506到多面体504任意点的最大距离。当如此定义时，球502的中心506表示多面体504的质心。因此，作为动作302的结果，可以确定第一多面体的原点，例如质心。然而，如上指出的，本发明并不限于如何确定或定义对象的原点。因此，根据本发明，可以使用任一任意手段来确定要由处理过程300处理的3D对象的原点。

处理过程300可以继续进行到接收立方体图图元[动作304]，在此该图元包括6个2D纹理像素阵列。如上所述，立方体图是公知的3D图形图元类型。处理过程300随后可以继续到确定从第一多面体的原点沿着以该原点为起点并穿过立方体图的像素的方向，到与第一多面体的面的交点之间的距离值[动作306]。

图6示出了方案600，用于根据动作306的一些实施确定距离值。图6显示了多面体602和立方体图604的2D横截面。尽管为了说明的目的，图6示出了多面体602和图604的2D横截面，但可以对3D多面体进行动作306的执行，导致了相对于3D立方体图的距离值的确定。图6显示了图604的一个面608的像素P1-P7的一个行606，在此，根据动作306的一些实施，可以沿8个唯一方向612确定距离值，在此每一个方向612都在多面体602的原点614开始，并穿过像素606之中单独的一个。因此，例如，穿过像素P7的方向616具有与多面体602的一个面的交点618和距离值620，距离值620定义为在原点614与像素P7的位置之间以纹理空间单位计的距离。以类似的方式，可以为图6中的所有方向612，以及为立方体图604的剩余像素的所有其它方向(未示出)，确定根据动作306的距离值。

尽管图6显示了立方体图604的横截面，在此图604的每一面都可以包括8×8像素阵列，从而使立方体图604可以包括总共144个像素，但是本发明并不限于在处理过程200和300中所用的立方体图的具体分辨率。因此，例如，可以对在处理过程300中所处理的每一个多面体以不同分辨率的立方体图来进行动作306。例如，在动作302中接收的立方体图可以包括6个2D 16×16像素阵列，从而使得在处理过程200和300中所用的立方体图可以包括总共1,536个像素。可替换地，在动作302中接收的立方体图可以包括6个2D 4×4像素阵列，从而使得在处理过程200和300中所用的立方体图可以包括总共96个像素。而且，本领域技术人员会认识到，可以通过仅沿方向的一个子集(例如仅沿方向612的子集)确定距离值并且由在动作306中所确定的距离值对之间的线性内插值来确定剩余的距离值，来进行动作306。

处理过程300可以继续进行到将距离值存储为立方体图的像素值[动作308]。根据本发明的一些实施方式，动作308可以包括将在动作306中确定的每一个距离值存储为位于与该距离值相关的方向上的像素的像素值。例如，如果动作306包括确定与方向616相关的距离值620，那么动作308就可以包括将距离值620存储为位于方向616上的像素P7的像素值。在本发明的一些实施方式中，在动作306中确定且在动作308中存储的那些距离值可以包括浮点值，尽管本发明不限于具有特定数据格式的距离值。

而且，尽管在此提供的详细说明指的是凸多面体，例如多面体504或多面体602，但本发明并不限于这一点，在处理过程200/300中也可以使用凹多面体。本领域技术人员会认识到，可以将凸多面体定义为这样的一个对象，即其中，连接该对象的任意两点的任何完整直线段都完全包含在该对象内，而可以将凹多面体定义为这样的一个对象，即其中，可以找到连接该对象的两个点的一条完整直线段，其中该线段并不完全包含在该对象内。

为了在处理过程200/300中使用凹多面体，可以确定与凹多面体的凸包(convex hull)的包围体，在此该凸包包围体所具有的标量半径对应于该对象的原点与该对象的任意点之间的最大距离值。随后可以在动作302中使用这个凸包包围体。可替换地，可以使用凸分解技术将凹几何体划分为更小的凸几何体。随后可以使用处理过程200/300来检测在这些凸子几何体之间的冲突。凸包包围体和凸分解技术是本领域公知的，在此不再更详细论述。

再次参考处理过程200，在本发明的一些实施方式中，应用程序，例如3D图形应用程序，可以进行处理过程300在预处理阶段中的所有动作(即在进行处理过程200之前)，并在动作206中向算法102提供产生的纹理图。可替换地，在本发明的其它实施方式中，算法102可以响应于在由引擎100执行的3D渲染期间发生的每一个冲突检测事件，以动态方式进行处理过程300。此外，对于在动作202中接收的每一个多面体，可能已经在处理过程300中产生了(即在动作206中产生了)用于存储该多面体的距离值的相关立方体图，并且可以在处理过程300的进一步动作中使用，如在以下更详细解释的。根据本发明的一些实施方式，处理过程300可以产生立方体图，其保存或存储在存储器106中，在此，该立方体图存储了特定多面体的距离值。

处理过程200可以继续进行到确定从第一多面体的原点到第二多面体的顶点的第一距离值[动作208]，在此第一距离沿着从第一多面体的原点延伸到第二多面体的顶点的方向向量。图7示出了方案700，用于根据动作208的一些实施方式来确定第一距离值。

图7显示了第一多面体702和第二多面体704，在此，根据动作208的一些实施方式，可以在多面体702的原点706与多面体704的顶点708之间沿方向向量710确定第一距离值705，方同向量710从原点706开始并穿过顶点708。类似地，例如，动作208可以包括确定在原点706与多面体704的顶点714之间沿方向向量715的第一距离值712，方向向量715从原点706开始并穿过顶点714。尽管为了说明的目的，图7示出了多面体702和704的2D横截面，但可以针对3D多面体来进行动作208的执行，其导致沿着由3D坐标定义的方向向量的第一距离值的确定。在本发明的一些实施方式中，可以在相应的动作202和204中接收到第一和第二多面体之后，由算法102来进行动作208。

处理过程200随后可以继续进行到通过执行对纹理图的一个或多个查询，来确定沿方向向量从第一多面体的原点到第一多面体的一个面的第二距离[动作210]。再次参考图7，在本发明的一些实施方式中，动作210可以包括确定例如沿方向向量710从原点706到多面体702的面722的第二距离720。在该实例中，确定第二距离720可以包括：查询在动作206中所产生的纹理图的像素725和726(即动作308中)处存储的距离值(即在306中确定的)，并随后在这些距离值之间进行线性内插值，以便在动作210中获得第二距离720。

类似地，例如，动作210可以包括确定沿方向向量715从原点706到面722的第二距离724。然后，在该实例中，确定第二距离724可以包括：查询在动作206中所产生的纹理图的像素727和728处存储的距离值，随后在这些距离值之间进行线性内插值，以便在动作210中获得第二距离724。在本发明的一些实施方式中，动作210可以包括算法102为纹理采样器104提供像素相关的查询索引(例如像素725和726或像素727和728)。采样器104随后可以使用这些索引来产生相应的存储器地址，用于访问在存储器106中所存储的立方体图的相应像素的距离值。采样器104随后可以在这些距离值之间进行线性内插值，并向算法102提供产生的插值距离值。可替换地，采样器104可以向算法102提供距离值，算法102可以在这些值之间进行线性内插值，以便在动作210中确定第二距离。

尽管在图7中将每一个方向向量710和715都显示为经过或指定了分别位于像素725和726及像素727和728之间的纹理坐标对，但本发明并不限于图7中所示的2D表示。因此，例如，方向向量710和715任何一个都可以经过或指定位于立方体图的一个面的两个像素行或列之间的纹理坐标对。因此，动作210可以包括：使用4个查询索引来访问在约束该纹理坐标对的这4个像素处存储的距离值，并随后在这4个距离值之间进行双线性内插值，以获得第二距离值。然而，本发明不限于线性内插值(双线性、三线性或其它的)。因此，例如，可以使用从纹理图获得的距离值的最近的点采样来进行动作210。

在本发明的其它实施方式中，动作210可以包括算法102，算法102为像素着色器108提供了与像素(例如像素725和726或像素727和728)相关的查询索引，并且着色器108可以将这些索引传送到纹理采样器104。采样器104随后可以使用这些索引来产生相应的存储器地址，用于访问在存储器106中所存储的立方体图的相应像素的距离值，并将这些距离值提供给着色器108。着色器108随后可以在这些距离值之间进行线性内插值，并将产生的插值距离值提供给算法102。可替换地，着色器108可以将距离值提供给算法102，算法102可以在这些值之间进行线性内插值，以便在动作210中确定第二距离。

处理过程200可以随后继续进行到比较第一距离值与第二距离值[动作212]，如果第二距离大于或等于第一距离，就检测到在第一和第二多面体之间的冲突[动作216]。再次参考图7，动作212例如可以包括沿方向向量710比较第一距离705与第二距离720。在此情况下，第一距离705大于第二距离720，将不会检测到冲突。然而，对于另一个实例，动作212可以包括沿方向向量715比较第一距离712和第二距离724。在此情况下，第二距离724大于第一距离712，因此在动作216中检测到冲突。在本发明的一些实施方式中，算法102可以进行动作212的比较，并且如果第二距离大于或等于第一距离，则在动作216中确定发生冲突。

尽管如上所述的动作208和210分别指的是确定第一和第二距离，且尽管动作212指的是相互比较这两个距离，但在本发明其它实施方式中，处理过程200可以包括确定这些距离的平方的动作，随后在动作212中相互比较这些距离的平方值。因此，在这些实施方式中，动作214可以包括确定第二距离的平方是否大于或等于第一距离的平方。然而，本发明不限于在动作212中比较距离或比较距离的平方。因此，例如，处理过程200可以包括确定这些距离的平方根的动作，随后在动作212中相互比较这些距离的平方根值。

不必按所示的顺序执行在图2和3中所示的动作；也不必执行所有的动作。此外，那些不依赖于其它动作的动作可以与所述其它动作并行地执行。例如，可以并行地进行动作202和204。可替换地，可以将动作202和204合并到单一动作中。换句话说，可以在单一动作中进行对第一和第二多面体的接收。另外，如上指出的，动作206，即根据本发明一些实施方式的立方体图的产生，可以在处理过程200的所有其它动作之前进行，或者可替换地，动作206可以在动作202或204之后进行或与其并行进行。此外，在该附图中的至少一些动作可以实现为指令或指令组，所述指令或指令组在机器可读介质中实现。

在本发明的一些实施方式中，在处理过程200和/或300中所用的算法102可以包括以下伪代码：

Collision_Detection_Using_Cubemaps(...)

bool Collision＝false；

Foreach vertex V_2J of polygon P₂{

   Direction Vector＝V_2J-C₁；

   d1＝texCube(Direction Vector}；

   d2＝distance(C₁，V_2J}；

       if(d1＞＝d2){

          Collision＝true；

          break；//冲突

   }

}

If(Collision){

   //对冲突的相应进行建模

}else{

  //无冲突，继续进行，以评估下一对几何体的冲突检测

}

在本发明的其它实施方式中，在处理过程200和/或300中所用的算法102可以由引擎100的像素着色器108产生或与其相关联，并可以包括以下高级着色语言(shading language)像素着色器代码：

PS_OUTPUT CollisionDetectionPS(VS_OUTPUT In，

                               uniform bool bTexture)

{

    PS_OUTPUT Output；

    int Index＝0；

    foat sum＝0.0；

    float fActualDist，fCubeMapDist；

    float4temp＝(0，0，0，1)；

    float4 WorldPos，WorldCentroid，dir；

    bool collision＝false；

    float2 tex；

    //bool results[115]；

    int trouble＝0；

    Output.RGBColor.r＝Output.RGBColor.g＝

Output.RGBColor.b＝Output.RGBColor.a＝0.0；

//这些是用于索引像素中心并访问对象的位置数据的纹理(u，v)坐标

    float disp＝0.5/g_iNumVertices[1]；

    tex.y＝0.5

    //对象0的重心的全局位置

    WorldCentroid＝mul(g_vCentroids[0]，g_mWorldMat0)；

    //经过对象1的所有顶点的射线

    for(Index＝0；Index＜g_iNumVertices[1]；Index++)

{

    tex.x＝Index/g_iNumVertices[1]+disp；

    //得到在纹理中存储的对象1的顶点位置

    WorldPos＝tex2D(g_samPositions 1，tex)；

    //转换到全局空间

    WorldPos＝mul(WorldPos，g_mWorldMat 1)；

    dir＝WorldPos-WorldCentroid；

    fActualDist＝sqrt(dir.x*dir.x+dir.y*dir.y+dir.z*dir.z)；

    //将方向转换回通过与对象0的全局矩阵的逆相乘产生立方体图的空间

    dir＝mul(dir，g_mWorldMat0Inv)；

    dir＝normalize(dir)；

    temp＝texCUBE(g_samCubeMapDistance0，dir)；

    fCubeMapDist＝temp.x；

    if(fCubeMapDist＞fActyalDist){

        collision＝true；

    }

}

//进行与以上相同的计算，但是切换对象。从而现在循环遍历对象0的顶点

    disp＝0.5/g_iNumVertices[0]；

    WorldCentroid＝mul(g_vCentroids[1]，g_mWorldMatl)；

    for(Index＝0；Index＜g_iNumVertices[0]；Index++)

    {

        tex.x＝Index/14.0+disp；

        WorldPos＝tex2D(g_samPositions0，tex)；

        WorldPos＝mul(WorldPos，g_mWorldMat0)；

        dir＝WorldPos-WoridCentroid；

        fActualDist＝sqrt(dir.x*dir.x+dir.y*dir.y+dir.z*dir.z)；

        dir＝mul(dir，g_mWorldMatlInv)；

        dir＝normalize(dir)；

            temp＝texCUBE(g_samCubeMapDistancel，dir)；

        fCubeMapDist＝temp.x；

        if(fCubeMapDist＞fActualDist){

            collision＝true；

        }

    }

    if(collision＝＝true){

          Output.RGBColor.r＝Output.RGBColor.g＝

          Output.RGBColor.b＝1.0；

          Output.RGBColor.a＝1.0；

    }

    return Output；

}

图8示出了根据本发明一些实施方式的实例系统800。系统500可以包括具有两个或更多个处理内核803的主处理器802、图形处理器804、存储器806和808(例如动态随机存取存储器(DRAM)、静态随机存取存储器(SRAM)、非易失性存储器等)、总线或通信通路810，网络接口814(例如有线和/或无线局域网(LAN)和/或广域网(WAN)和/或个域网(PAN)，和/或其它有线和/或无线网络接口)、以及显示处理器和/或控制器816。系统800还可以包括天线815(例如偶极天线，窄带曲折线型天线(MLA)，宽带MLA，倒“F”型天线，平面倒“F”型天线，Goubau天线，贴片天线(Patch antenna)等)，其耦合到网络接口814。系统800可以是适合于处理3D图形数据并以光栅化形式提供该数据的任何系统，光栅化形式的数据适合于在显示装置(未示出)上的呈现，列举几个实例，所述显示装置例如为液晶显示器(LCD)、或阴极射线管(CRT)显示器。

系统800可以采取多种物理实现方式。例如，系统800可以在个人计算机(PC)、联网的PC、服务器计算系统、手持计算平台(例如个人数字助理(PDA))、游戏系统(便携式的或其它形式的)，3D蜂窝电话手机等中实现。而且，尽管可以在单个装置中实现系统800的所有组件，例如芯片上系统(SOC)集成电路(IC)，但系统800的组件也可以分布在多个IC或装置中。例如，可以将主处理器802连同组件806和814实现为包含在单个PC内的多个IC，而图形处理器804及组件808和816可以在一个分离的装置中实现，例如通过通信通路810耦合到主处理器802及组件806和814上的电视机或其它显示器。

主处理器802可以包括专用或通用处理器，其包括能够为图形处理器504提供3D图形数据和/或指令的任何控制和/或处理逻辑、硬件、软件和/或固件。处理器802可以执行各种3D图形计算，例如3D坐标变换等，其结果可以通过总线810提供给图形处理器804，和/或可以存储在存储器806和/或808中用于由处理器804最终使用。在本发明的一些实施方式中，主处理器802可以是中央处理单元(CPU)。

在一个实施方式中，主处理器802能够执行支持或实现使用立方体图的实时的、多分辨率的3D冲突检测的任何数量的任务。支持的任务例如可以包括：向图形处理器804提供3D图形数据；在存储器808中设置一个或多个纹理图，例如立方体图；将微代码(经由天线815和接口814)下载到处理器804；初始化和/或配置处理器804中的寄存器；中断服务；以及提供总线接口，用于上载和/或下载3D图形数据，尽管本发明并不限于这一点。在可替换的实施方式中，可以由图形处理器804执行这些功能中的一些或全部。尽管图5将主处理器802和图形处理器804显示为不同组件，但本发明不限于这一点，本领域技术人员会认识到，除了系统800的其它组件之外，处理器802和804也可以在单一IC内实现。

根据本发明的一些实施方式，每一个内核803都可以使用冲突检测算法102的不同实现针对不同多面体对并行地执行处理过程200/300。可替换地，这种并行处理方案可以由图形处理器804来实现。

图形处理器804可以包括能够处理图形数据的任何处理逻辑、硬件、软件和/或固件。在一个实施方式中，图形处理器804可以实现能够根据一个或多个标准化渲染应用编程接口(API)来处理图形数据的3D图形架构，列举几个实例，所述标准化渲染应用编程接口(API)例如为：OpenGL 2.0^TM(“The OpenGL Graphics System：A Specification”(2.0版；2004年10月22日))和DirectX 9.0^TM(9.0c版；2004年8月8日)，尽管本发明不限于这一点。图形处理器804可以处理由主处理器802提供的、保存或存储在存储器806和/或808中的、和/或由系统800外部的源提供并通过总线810从接口814获得的3D图形数据。

图形处理器804可以接收3D场景数据形式的3D图形数据，并处理该数据，以便以合适的形式提供图像数据，该形式适于由显示处理器816转换为显示器专用数据。另外，除了类似于纹理采样器104的一个或多个纹理采样器之外，图形处理器804还可以实现多种3D图形处理组件和/或级(未示出)，例如光栅化器级。由图形处理器804实现的纹理采样器可以读取或访问在存储器806和808的任意一个或二者中以立方体图形式存储或保存的纹理数据。此外，根据本发明的一些实施方式，图形处理器804可以实现能够使用存储在一个或多个立方体图中的距离值来以并行方式对多对多面体进行冲突检测的两个或更多个纹理采样器。

总线或通信通路810可以包括用于在系统800的任意元件之间传送信息(例如图形数据、指令等)的任何机制。例如，通信通路810可以包括能够在处理器802与处理器804之间传送例如指令(例如宏代码)的多用途总线，尽管本发明不限于这一点。可替换地，通路810可以包括无线通信通路。

显示处理器816可以包括能够将由图形处理器804提供的光栅化图像数据转换为适于驱动显示器的格式(即显示器专用数据)的任何处理逻辑、硬件、软件和/或固件。例如，处理器804可以将图像数据以特定颜色数据格式提供给处理器816，例如以压缩的红-绿-蓝(RGB)格式，并且处理器816可以通过产生例如相应的LCD驱动数据级等来处理此类RGB数据，尽管本发明并不限于这一点。尽管图8将处理器804和816显示为不同的组件，但本发明不并限于这一点，本领域技术人员会认识到，例如显示处理器816的一部分功能或全部功能可以由图形处理器804和/或主处理器802来执行。

因此，通过利用硬件图元，例如立方体图，根据本发明的冲突检测算法可以完全在图形处理器(例如处理器804)上执行，该情况(有可能)排除了处理过程300的预处理，处理过程300的预处理可以对每一个多面体执行一次并且可以在处理过程200之前进行。此外，根据本发明的冲突检测算法能够平衡(leverage)高级八叉树结构，以使得对象-对象检测最小化，并且对于由八叉树数据结构确认为候选的对象-对象交互，可以依赖于立方体图。因此，通过将冲突检测算法移到图形处理器(例如处理器804)，可以释放CPU(例如主处理器802)来承担其它任务。尽管如此，根据本发明的冲突检测算法也可以在CPU上执行。而且，使用诸如立方体图之类的硬件图元来检测冲突会实现每一个冲突的数学运算的相当大的减少(可能多达三倍的减少)，并且由于执行完全独立于冲突检测测试这一能力，因此能够进行多处理内核实现(例如使用内核803)。

尽管与所声明的发明一致的一个或多个具体实例的在前说明提供了对本发明的例证和说明，但是其意图不是穷举性的或将本发明的范围限制为所公开的具体实施方式。明确而言，按照以上的教导，可以有多种修改和变化，或者可以从本发明的各种实施方式的实现中获得多种修改和变化。例如，尽管图1和附属的文字显示并说明了耦合到单一纹理存储器106的单一纹理采样器104，但本领域技术人员会认识到，根据本发明的数据处理器可以包括采用多个纹理采样器的渲染引擎，每一个纹理采样器都按照本发明进行操作，并耦合到一个或多个纹理存储器。明确而言，可以使用许多其它实施方式来提供根据本发明的使用立方体图的实时的、多分辨率的3D冲突检测。

在本申请的说明中阐述的装置、元件、动作、数据类型、指令等都不应解释为对本发明是关键性或不可缺少的，除非明确表述为如此。此外，如在此所用的，冠词“一”意图包括一个或多个项。而且，当在此或附带的权利要求中使用诸如“耦合的”或“响应的”或“与……通信”之类的术语或短语时，这些术语意图是作最广泛的理解。例如短语“耦合到”可以指的是按照对于使用该短语的上下文适当的方式可通信地、电气地、和/或可操作地进行耦合。在实质上不脱离本发明的精神和原理的情况下，可以对所声明的发明的上述实施方式做出多种改变和修改。所有此类修改和改变都意图在此包括在本公开内容的范围内，并受到附带的权利要求的保护。