CN117726774A - 基于线产生算法的三角形光栅化方法、装置以及相关设备 - Google Patents

Abstract

本发明提出了一种基于线产生算法的三角形光栅化方法、装置以及相关设备。该方法包括：步骤1，建立三维模型，并对三维模型进行网格剖分。步骤2，通过视图变换获取待光栅化的三角形。步骤3，判断获取的待光栅化的三角形是否有一边平行于x方向，若是，则进入下一步；若否，则将获取的待光栅化的三角形切分为两个有一边平行于x方向的三角形，再进入下一步。步骤4，使用线产生算法处理有一边平行于x方向的三角形。步骤5，重复步骤4，直至三角形的内部的网格单元被完全填充。本发明引入线产生算法，通过整数运算替换了原算法中的浮点运算，提升了多物理场核心工业仿真处理平台软件中后处理显示界面的渲染效率。

Description

基于线产生算法的三角形光栅化方法、装置以及相关设备

技术领域

本发明涉及计算机图形处理领域，具体涉及一种基于线产生算法的三角形光栅化方法、装置以及相关设备。

背景技术

光栅化是计算机图形学中的一个过程，它将连续的、几何上定义的图形对象（如三角形、线条等）映射到离散的像素或片元（屏幕上的最小显示单元）。这个过程是从图形的抽象表示到最终在屏幕上显示的图像之间的关键步骤。在图形学中可以把屏幕抽象为一个二维数组，二维数组中的每个元素即为像素。

在计算机图形学中，由于三角形是最基本的几何图元，并且可以构成更复杂的图形，因此三角形光栅化是一种常见而重要的技术。三角形光栅化在各种领域中都发挥着重要作用，包括：计算机游戏开发、计算机动画、虚拟现实（VR）和增强现实（AR）、工程和科学可视化和医学图像处理。在进行三角形光栅化之前，首先需要根据所需仿真的实体建立三维模型。由于屏幕是二维的，因此必须找到一种方法将这些三维模型投影到二维屏幕上，以便我们能够看到和交互，三角形光栅化便是这一过程中的关键步骤。具体地，在三维空间中对三维模型进行网格剖分以划分成若干个三角形。例如，中国专利CN116977598B公开的一种三角网格数值仿真平滑化的方法中，介绍了一种将三维结构进行网格剖分成若干个三角形以形成三角网格，并对三角网格数值仿真平滑化的方法。该发明所提供的技术方案使结果显示更符合求解的实际场景，有效解决了现有后处理结果视图在对单元数值平滑过程中产生的数据失真问题。网格剖分后的每个三角形都有一组三维坐标，表示其在三维空间中的位置。这些坐标通常是相对于某个坐标系的，例如世界坐标系或模型坐标系。为了将三维模型投影到二维屏幕上，需要进行视图变换，这个过程将三维坐标转换为二维视图坐标。在二维视图坐标中，裁剪操作会去除不在屏幕视口内的部分。一旦进行了视图变换和裁剪，接下来就是光栅化阶段。在光栅化阶段，三维模型被转换成网格单元（例如：像素），即屏幕上的点。

传统的三角形光栅化先求出三角形左右两条边的斜率，接着通过扫描线算法对每一行像素进行光栅化，然后通过浮点数加法求出下一行像素起始点和终点的位置。然而，在中央处理器（CPU）下执行浮点数加法可能面临性能瓶颈的问题，尤其是在处理大量像素、网格密集的情况下。具体而言，在一些网格密集的场景下，计算量会显著增加，这可能会降低后处理界面的流畅度，尤其是在实时图形渲染中，例如游戏或模拟器。一种解决方案是开发基于图像处理单元（GPU）的三角形光栅化方法。例如中国专利CN109598669B公开了一种面向GPU的三角形光栅化扫描系统，集成有初始化单元、Y轴步进单元和X轴扫描单元，实现了GPU的三角形光栅化扫描，从而实现了从系统架构文档到RTL的转换。虽然，图像处理单元（GPU）的并行性和专用硬件可以在浮点运算方面带来显著的优势。但是，图像处理单元（GPU）的应用场景也有所限制。

在多物理场核心工业仿真处理平台软件中，因其后处理显示界面需要考虑各种硬件兼容问题，所以针对有限元仿真结果的显示功能完全基于CPU硬件，GPU并不适用于多物理场核心工业仿真处理平台软件。如果希望在多物理场核心工业仿真处理平台软件中进行三角形光栅化的处理，还是需要基于CPU的处理方案。因此，设计出一种能够提升多物理场核心工业仿真处理平台软件中后处理显示界面的渲染效率的新三角形光栅化的技术方案显得尤为重要。

发明内容

为了解决现有技术中的问题，本发明所提供的技术方案为：一种基于线产生算法的三角形光栅化方法、装置以及相关设备。其中，线产生算法即布雷森汉姆线段生成算法（Bresenham's line algorithm）。本发明引入线产生算法，通过整数运算替换了原算法中的浮点运算，避免在中央处理器（CPU）下执行浮点数加法，提升多物理场核心工业仿真处理平台软件中后处理显示界面的渲染效率，提高CPU下的性能。

本发明提出了一种基于线产生算法的三角形光栅化方法，包括：

步骤1，根据所需仿真的真实结构建立三维模型，在三维空间中对三维模型进行网格剖分以将三维模型切分成若干个三角形，每个三角形都有一组三维坐标以表示其在三维空间中的位置；

步骤2，通过视图变换将被切分成若干个三角形后的三维模型投影到光栅成像设备上，以获取若干个待光栅化的三角形，所述视图变换为将三维坐标转换为二维视图坐标；

步骤3，分别判断获取的每个待光栅化的三角形是否有一边平行于x方向，若是，则进入下一步，若否，则将该三角形切分为两个有一边平行于x方向的三角形，再进入下一步；

步骤4，对于有一边平行于x方向的三角形，使用线产生算法同时求出该三角形两条斜边上当前网格单元的下一个网格单元，直至下一个网格单元在y方向上的坐标与上一个网格单元在y方向上的坐标不同，以分别在该三角形的两条斜边上获取两个在y方向上的坐标相同的网格单元，并填充这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步；

步骤5，重复步骤4，直至步骤4中有一边平行于x方向的三角形的内部的网格单元被完全填充；

其中，所述基于线产生算法的三角形光栅化方法用于在光栅成像设备上形成所有待光栅化的三角形所对应的网格单元集合，所述光栅成像设备被划分为若干个相同的网格单元，在光栅成像设备上建立二维视图坐标系，所述x方向为二维视图坐标系中x轴所处的方向，所述y方向为二维视图坐标系中y轴所处的方向。

在一个实施例中，所述步骤4包括：

令有一边平行于x轴的三角形的三个顶点分别为P1、P2、P3，边P1P2、边P1P3分别为两条斜边L、R，斜边L以P1为起始点、P2为终点，斜边R以P1为起始点、P3为终点，令当前网格单元的初始值为起始点P1；

使用线产生算法同时求出该三角形的两条斜边L、R上当前网格单元的下一个网格单元；

如果斜边L上的下一个网格单元在y方向上的坐标的高度大于斜边R上的下一个网格单元在y方向上的坐标的高度，则在斜边L上继续使用线产生算法获取下一个网格单元，直至斜边L上的下一个网格单元在y方向上的坐标的高度等于斜边R上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步；

如果斜边L上的下一个网格单元在y方向上的坐标的高度小于斜边R上的下一个网格单元在y方向上的坐标的高度，则在斜边R上继续使用线产生算法获取下一个网格单元，直至斜边R上的下一个网格单元在y方向上的坐标的高度等于斜边L上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步；

如果斜边L上的下一个网格单元在y方向上的坐标的高度等于斜边R上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步。

在一个实施例中，所述步骤5包括：重复步骤4，使用线产生算法同时求出该三角形的两条斜边L、R上当前网格单元的下一个网格单元，直至扫描至两条斜边L、R的终点，且该三角形的内部的网格单元被完全填充。

在一个实施例中，所述步骤4中，使用线产生算法同时求出该三角形的两条斜边上当前网格单元的下一个网格单元的方法包括：

将斜边上的两个顶点分别作为起始点和终点，令e的初始值为-dx，dx为下一个网格单元与当前网格单元之间在x方向上的距离，令当前网格单元的初始值为斜边的起始点；

使用线产生算法从斜边的起始点开始扫描，以寻找当前网格单元的下一个网格单元，所述寻找当前网格单元的下一个网格单元包括：

当前网格单元P在x方向上步进一个单位，更新e=e+2*dy，dy为下一个网格单元与当前网格单元之间在y方向上的距离；

判断e是否大于等于0，若e大于等于0，则下一个网格单元在y方向上的坐标为当前网格单元在y方向上步进一个单位，同时更新e=e-2*dx，若e小于0，则下一个网格单元在y方向上的坐标为当前网格单元在y方向上的坐标。

在一个实施例中，所述网格单元为像素。

在一个实施例中，所述基于线产生算法的三角形光栅化方法应用于电子设备中。

在一个实施例中，所述基于线产生算法的三角形光栅化方法应用于芯片封装中。

本发明还提出了一种基于线产生算法的三角形光栅化装置，包括存储器和处理器；

所述存储器用于存储计算机程序；

所述处理器，用于当执行所述计算机程序时，实现如上文所述的基于线产生算法的三角形光栅化方法。

本发明还提出了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时，实现如上文所述的基于线产生算法的三角形光栅化方法。

本发明还提出了一种计算机程序产品，包括计算机程序，所述计算机程序被处理器执行时，实现如上文所述的基于线产生算法的三角形光栅化方法。

本发明的基于线产生算法的三角形光栅化方法及相关设备的有益效果在于：在三角形光栅化算法中引入了线产生算法，通过整数运算替换了原算法中的浮点运算，提升了多物理场核心工业仿真处理平台软件中后处理显示界面的渲染效率。

附图说明

图1为本发明一实施例的基于线产生算法的三角形光栅化方法的流程示意图。

图2为本发明一实施例的基于线产生算法的三角形光栅化方法中待光栅化的三角形没有一边平行于x方向时的切分示意图。

图3a、图3b、图3c为本发明一实施例的基于线产生算法的三角形光栅化方法应用在有一边平行于x方向的三角形实施例的示意图。

图4为本发明一实施例的基于线产生算法的三角形光栅化方法应用在电子设备实施例的示意图。

图5a、图5b、图5c、图5d、图5e、图5f、图5g为本发明一实施例的基于线产生算法的三角形光栅化方法应用在电子设备实施例的各切分层二维几何模型示意图。

图6a、图6b、图6c、图6d、图6e、图6f、图6g为本发明一实施例的基于线产生算法的三角形光栅化方法应用在电子设备实施例的各切分层网格剖分示意图。

图7为本发明一实施例的基于线产生算法的三角形光栅化方法应用在电子设备实施例的三维模型的网格剖分示意图。

图8为为本发明一实施例的基于线产生算法的三角形光栅化方法应用在芯片封装实施例应用在芯片封装实施例的示意图。

图9a、图9b、图9c、图9d为本发明一实施例的基于线产生算法的三角形光栅化方法应用在芯片封装实施例的各切分层二维几何模型示意图。

图10a、图10b、图10c、图10d为本发明一实施例的基于线产生算法的三角形光栅化方法应用在芯片封装实施例的各切分层网格剖分示意图。

图11为本发明一实施例的基于线产生算法的三角形光栅化方法应用在芯片封装实施例的三维模型的网格剖分示意图。

图12为利用本发明一实施例的基于线产生算法的三角形光栅化方法进行三角形光栅化的热力仿真图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解的是，此处所描述的具体实施例仅用以解释发明，并不用于限定发明。

如图1所示，本发明提出一种基于线产生算法的三角形光栅化方法，包括：

步骤1，根据所需仿真的真实结构建立三维模型，在三维空间中对三维模型进行网格剖分以将三维模型切分成若干个三角形，每个三角形都有一组三维坐标以表示其在三维空间中的位置。

步骤2，通过视图变换将被切分成若干个三角形后的三维模型投影到光栅成像设备上，以获取若干个待光栅化的三角形。其中，视图变换为将三维坐标转换为二维视图坐标。

步骤3，分别判断获取的每个待光栅化的三角形是否有一边平行于x方向，若是，则进入下一步；若否，则将该三角形切分为两个有一边平行于x方向的三角形（参见图2），再进入下一步。

步骤4，对于有一边平行于x方向的三角形，使用线产生算法同时求出该三角形两条斜边上当前网格单元的下一个网格单元，直至下一个网格单元在y方向上的坐标与上一个网格单元在y方向上的坐标不同，以分别在该三角形的两条斜边上获取两个在y方向上的坐标相同的网格单元，并填充这两个网格单元及这两个网格单元中间的所有网格单元，参见图3a、图3b和图3c。将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步。

步骤5，重复步骤4，直至步骤4中有一边平行于x方向的三角形的内部的网格单元被完全填充，参见图3c。

其中，光栅成像设备被划分为若干个相同的网格单元，在光栅成像设备上建立二维视图坐标系，所述x方向为二维视图坐标系中x轴所处的方向，所述y方向为二维视图坐标系中y轴所处的方向，所述基于线产生算法的三角形光栅化方法用于在光栅成像设备上形成每一个待光栅化的三角形所对应的网格单元集合。

进一步，步骤4包括：

如图3a所示，令有一边平行于x轴的三角形的三个顶点分别为P1、P2、P3，边P1P2、边P1P3分别为两条斜边L、R，斜边L以P1为起始点、P2为终点，斜边R以P1为起始点、P3为终点，令当前网格单元的初始值为起始点P1。

使用线产生算法同时求出该三角形的两条斜边L、R上当前网格单元的下一个网格单元。

如果斜边L上的下一个网格单元在y方向上的坐标的高度大于斜边R上的下一个网格单元在y方向上的坐标的高度，则在斜边L上继续使用线产生算法获取下一个网格单元，直至斜边L上的下一个网格单元在y方向上的坐标的高度等于斜边R上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步。

如果斜边L上的下一个网格单元在y方向上的坐标的高度小于斜边R上的下一个网格单元在y方向上的坐标的高度，则在斜边R上继续使用线产生算法获取下一个网格单元，直至斜边R上的下一个网格单元在y方向上的坐标的高度等于斜边L上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步。

如果斜边L上的下一个网格单元在y方向上的坐标的高度等于斜边R上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元。并将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步。

例如，如图3b所示，斜边L、R均以起始点P1为当前网格单元，斜边L的下一个网格单元P11在y方向上的坐标的高度小于斜边R上的下一个网格单元P12在y方向上的坐标的高度，则在斜边R上继续使用线产生算法获取下一个网格单元P13。此时斜边L上的下一个网格单元P11在y方向上的坐标的高度等于斜边R上的下一个网格单元P13在y方向上的坐标的高度，则填充两条斜边L、R上的P11、P13这两个网格单元及这两个网格单元中间的所有网格单元。并将P11、P13这两个网格单元分别作为两条斜边L、R的当前网格单元并进入下一步。

步骤4中同时利用线产生算法对三角形的左右两条斜边进行扫描转换，每次选择靠后的一个点迭代，当两点处于同一高度时生成一条横线。上述步骤的伪代码如下所示：

FuncDrawTriangle（point p1, point p2, point p3）

Get l by p1,p2

Get r by p1,p3

pl = pr = p1

While pl not equal p2

If pl’s height equal pr’s height

Generate line to pl and pr

Use Bresenham get next scan point pl in l line

Use Bresenham get next scan point pr in r line

Else if pl’s height>pr’s height

Use Bresenham get next scan point pl in l line

Else

Use Bresenham get next scan point pr in r line

推导到其他类型的三角形只需要切分三角形和适当变换递推的方向即可。

再进一步，步骤4中，使用线产生算法同时求出该三角形的两条斜边上当前网格单元的下一个网格单元的方法，包括：

将斜边上的两个顶点分别作为起始点和终点。令e的初始值为-dx，dx为下一个网格单元与当前网格单元之间在x方向上的距离，令当前网格单元的初始值为斜边的起始点。

使用线产生算法从斜边的起始点开始扫描，以寻找当前网格单元的下一个网格单元，所述寻找当前网格单元的下一个网格单元包括：

当前网格单元P在x方向上步进一个单位，更新e=e+2*dy，dy为下一个网格单元与当前网格单元之间在y方向上的距离；

判断e是否大于等于0。若e大于等于0，则下一个网格单元在y方向上的坐标为当前网格单元在y方向上步进一个单位，同时更新e=e-2*dx。若e小于0，则下一个网格单元在y方向上的坐标为当前网格单元在y方向上的坐标。

如上文所述，光栅成像设备被划分为若干个相同的网格单元。应理解的是，在一个具体的实施例中，在光栅成像设备上建立的二维视图坐标系中x轴和y轴分别平行于一个网格单元的两条邻边。一个单位即为一个网格单元在x方向或y方向上的宽度。

线产生算法的原理是在一条斜率在0到1之间的直线，x每次增加1（一个单位），那么y就有增加1（一个单位）或者保持不变这两种可能。如何在两者之间选择，成了此算法的关键要点。上述步骤的伪代码如下所示：

Func（point p1, point p2）

Get dx and dy by p1,p2.

e = -dx

p = p1

For i = 0:dx

// p is result point

p add x direction 1

e = e + 2*dy

If e>0

p add y direction 1

e = e - 2*dy

进一步，步骤5包括：重复步骤4，使用线产生算法同时求出该三角形的两条斜边L、R上当前网格单元的下一个网格单元，直至扫描至两条斜边L、R的终点，以填充整个三角形。

在一个实施例中，两条斜边的斜率在0到1之间。

在一个实施例中，光栅成像设备为屏幕。

在一个实施例中，网格单元为像素。

本发明提出的基于线产生算法的三角形光栅化方法的应用场景为多物理场核心工业仿真处理平台软件，一个示例性的应用场景是多物理场核心工业仿真处理平台软件（CPU环境）中后处理显示界面的渲染效率的提升。

本发明一实施例的基于线产生算法的三角形光栅化方法在在电子设备实施例中的应用如下：

步骤1，如图4所示，建立电子设备的三维模型，将XY轴平面作为切分平面，沿着Z轴方向将其切分为多个切分层。将电子设备三维模型的边界曲面与各切分层进行相交运算，即可得到如图5a、图5b、图5c、图5d、图5e、图5f、图5g所示的各切分层的二维模型。将各切分层的二维模型进行网格切分，离散为多个三角形的集合，参见图6a、图6b、图6c、图6d、图6e、图6f、图6g。将各切分层按空间位置依次叠放起来，就可以得到如图7所示的多层层状几何模型即2.5D几何模型的网格剖分示意图。

步骤2，要将多个三角形的集合显示在光栅成像设备（例如，屏幕）上，则需要将落在三角形内部的像素点着色。首先通过视图变换将被切分成若干个三角形后的三维模型投影到光栅成像设备上，以获取若干个待光栅化的三角形。

步骤3，分别判断待光栅化的三角形是否为有一边平行于x方向的三角形。如果待光栅化的三角形为有一边平行于x方向的三角形，则直接进入下一步。如果待光栅化的三角形找不到平行于x方向的一边，则对其进行切分，切分为两个有一边平行于x方向的三角形，再进入下一步。

以一个找不到平行于x方向的底边的待光栅化的三角形为例（参见图2），该三角形的三个顶点分别为P1、P2、P3。该三角形P1P2P3没有一边平行于x方向。因此，利用直线L0将三角形切分为两个有一边平行于x方向的三角形，直线L0经过点P2，并与边P1P3交于点P4，两个有一边平行于x方向的三角形分别为三角形P1P2P4和三角形P2P3P4。接下来分别对三角形P1P2P4和三角形P2P3P4进行步骤4。

步骤4，以三角形P1P2P4为例。边P2P4平行于x方向，因此边P1P2和边P1P4为两条斜边L、R。斜边L以P1为起始点、P2为终点，斜边R以P1为起始点、P3为终点。令两条斜边L、R当前网格单元的初始值均为起始点P1。

使用线产生算法同时求出该三角形两条斜边上当前网格单元的下一个网格单元。具体地，使用线产生算法同时求出该三角形两条斜边上当前网格单元的下一个网格单元的步骤包括：令e的初始值为-dx，dx为下一个网格单元与当前网格单元之间在x方向上的距离。使用线产生算法从斜边的起始点开始扫描，以寻找当前网格单元的下一个网格单元：当前网格单元在x方向上步进一个单位，更新e=e+2*dy，dy为下一个网格单元与当前网格单元之间在y方向上的距离。判断e是否大于等于0，若e大于等于0，则下一个网格单元在y方向上的坐标为当前网格单元在y方向上步进一个单位，同时更新e=e-2*dx；若e小于0，则下一个网格单元在y方向上的坐标为当前网格单元在y方向上的坐标。

如果斜边L上的下一个网格单元在y方向上的坐标的高度大于斜边R上的下一个网格单元在y方向上的坐标的高度，则在斜边L上继续使用线产生算法获取下一个网格单元，直至斜边L上的下一个网格单元在y方向上的坐标的高度等于斜边R上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步；

如果斜边L上的下一个网格单元在y方向上的坐标的高度小于斜边R上的下一个网格单元在y方向上的坐标的高度，则在斜边R上继续使用线产生算法获取下一个网格单元，直至斜边R上的下一个网格单元在y方向上的坐标的高度等于斜边L上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步；

如果斜边L上的下一个网格单元在y方向上的坐标的高度等于斜边R上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步。

步骤5，重复步骤4，使用线产生算法同时求出该三角形的两条斜边L、R上当前网格单元的下一个网格单元，直至扫描至两条斜边L、R的终点P2和P3，以填充整个三角形。其中，从起始点到终点一共对斜边循环迭代dx次。

此外，本发明的基于线产生算法的三角形光栅化方法还可以应用于芯片领域。步骤1，如图8所示，建立芯片封装的三维模型，还是将XY轴平面作为切分平面，沿着z轴方向将其切分为多个切分层。将芯片封装三维模型的边界曲面与各切分层进行相交运算，即可得到如图9a、图9b、图9c、图9d所示的各切分层的二维模型。将各切分层的二维模型进行网格切分，离散为多个三角形的集合，参见图10a、图10b、图10c、图10d。将各切分层按空间位置依次叠放起来，就可以得到如图11所示的多层层状几何模型即2.5D几何模型的网格剖分示意图。步骤2至步骤5与上文所述的在电子设备实施例中的一致。

图12为本发明一实施例的基于线产生算法的三角形光栅化方法应用于电子设备或芯片封装时的热力仿真图，不同颜色代表不同温度。应理解的是，基于线产生算法的三角形光栅化方法不影响三角形光栅化的效果，但是显著提升了三角形光栅化的处理速度。

本发明还提出了一种基于线产生算法的三角形光栅化装置，包括存储器和处理器。存储器用于存储计算机程序。处理器用于当执行计算机程序时，实现如上文所述的基于线产生算法的三角形光栅化方法。

本发明还提出了一种计算机可读介质，该计算机可读介质上存储有计算机程序。计算机程序被处理器执行时，实现如上文所述的基于线产生算法的三角形光栅化方法。

本发明还提出了一种计算机程序产品，包括计算机程序。该计算机程序被处理器执行时，实现如上文所述的基于线产生算法的三角形光栅化方法。

本发明的基于线产生算法的三角形光栅化方法及相关设备的有益效果在于：在三角形光栅化算法中引入了线产生算法，通过整数运算替换了原算法中的浮点运算，提升了多物理场核心工业仿真处理平台软件中后处理显示界面的渲染效率。

本领域技术人员将进一步领会，结合本文中所公开的实施例来描述的各种解说性逻辑板块、模块、电路、和算法步骤可实现为电子硬件、计算机软件、或这两者的组合。为清楚地解说硬件与软件的这一可互换性，各种解说性组件、框、模块、电路、和步骤在上面是以其功能性的形式作一般化描述的。此类功能性是被实现为硬件还是软件取决于具体应用和施加于整体系统的设计约束。技术人员对于每种特定应用可用不同的方式来实现所描述的功能性，但这样的实现决策不应被解读成导致脱离了本申请的范围。

结合本文所公开的实施例描述的各种解说性逻辑模块、和电路可用通用处理器、数字信号处理器（DSP）、专用集成电路（ASIC）、现场可编程门阵列（FPGA）或其它可编程逻辑器件、分立的门或晶体管逻辑、分立的硬件组件、或其设计成执行本文所描述功能的任何组合来实现或执行。通用处理器可以是微处理器，但在替换方案中，该处理器可以是任何常规的处理器、控制器、微控制器、或状态机。处理器还可以被实现为计算设备的组合，例如DSP与微处理器的组合、多个微处理器、与DSP核心协作的一个或多个微处理器、或任何其他此类配置。

结合本文中公开的实施例描述的方法或算法的步骤可直接在硬件中、在由处理器执行的软件模块中、或在这两者的组合中体现。软件模块可驻留在RAM存储器、闪存、ROM存储器、EPROM存储器、EEPROM存储器、寄存器、硬盘、可移动盘、CD-ROM、或本领域中所知的任何其他形式的存储介质中。示例性存储介质耦合到处理器以使得该处理器能从/向该存储介质读取和写入信息。在替换方案中，存储介质可以被整合到处理器。处理器和存储介质可驻留在ASIC中。ASIC可驻留在用户终端中。在替换方案中，处理器和存储介质可作为分立组件驻留在用户终端中。

在一个或多个示例性实施例中，所描述的功能可在硬件、软件、固件或其任何组合中实现。如果在软件中实现为计算机程序产品，则各功能可以作为一条或更多条指令或代码存储在计算机可读介质上或藉其进行传送。计算机可读介质包括计算机存储介质和通信介质两者，其包括促成计算机程序从一地向另一地转移的任何介质。存储介质可以是能被计算机访问的任何可用介质。作为示例而非限定，这样的计算机可读介质可包括RAM、ROM、EEPROM、CD-ROM或其它光盘存储、磁盘存储或其它磁存储设备、或能被用来携带或存储指令或数据结构形式的合意程序代码且能被计算机访问的任何其它介质。任何连接也被正当地称为计算机可读介质。例如，如果软件是使用同轴电缆、光纤电缆、双绞线、数字订户线（DSL）、或诸如红外、无线电、以及微波之类的无线技术从web网站、服务器、或其它远程源传送而来，则该同轴电缆、光纤电缆、双绞线、DSL、或诸如红外、无线电、以及微波之类的无线技术就被包括在介质的定义之中。如本文中所使用的盘（disk）和碟（disc）包括压缩碟（CD）、激光碟、光碟、数字多用碟（DVD）、软盘和蓝光碟，其中盘（disk）往往以磁的方式再现数据，而碟（disc）用激光以光学方式再现数据。上述的组合也应被包括在计算机可读介质的范围内。

以上所述实施例仅是对本发明的进一步说明，并非对本发明做其他形式的限制，本发明还可有其它多种实施例。在不背离本发明精神及其实质的情况下，熟悉本领域的技术人员可根据本发明作出各种相应的修改和变化，但这些相应的修改和变化都应落入本发明的保护范围。

Claims (10)

1.一种基于线产生算法的三角形光栅化方法，其特征在于，包括：

步骤1，根据所需仿真的真实结构建立三维模型，在三维空间中对三维模型进行网格剖分以将三维模型切分成若干个三角形，每个三角形都有一组三维坐标以表示其在三维空间中的位置；

步骤2，通过视图变换将被切分成若干个三角形后的三维模型投影到光栅成像设备上，以获取若干个待光栅化的三角形，所述视图变换为将三维坐标转换为二维视图坐标；

步骤3，分别判断获取的每个待光栅化的三角形是否有一边平行于x方向，若是，则进入下一步，若否，则将该三角形切分为两个有一边平行于x方向的三角形，再进入下一步；

步骤4，对于有一边平行于x方向的三角形，使用线产生算法同时求出该三角形两条斜边上当前网格单元的下一个网格单元，直至下一个网格单元在y方向上的坐标与上一个网格单元在y方向上的坐标不同，以分别在该三角形的两条斜边上获取两个在y方向上的坐标相同的网格单元，并填充这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步；

步骤5，重复步骤4，直至步骤4中有一边平行于x方向的三角形的内部的网格单元被完全填充；

其中，所述基于线产生算法的三角形光栅化方法用于在光栅成像设备上形成所有待光栅化的三角形所对应的网格单元集合，所述光栅成像设备被划分为若干个相同的网格单元，在光栅成像设备上建立二维视图坐标系，所述x方向为二维视图坐标系中x轴所处的方向，所述y方向为二维视图坐标系中y轴所处的方向。

2.根据权利要求1所述的基于线产生算法的三角形光栅化方法，其特征在于，所述步骤4包括：

令有一边平行于x轴的三角形的三个顶点分别为P1、P2、P3，边P1P2、边P1P3分别为两条斜边L、R，斜边L以P1为起始点、P2为终点，斜边R以P1为起始点、P3为终点，令当前网格单元的初始值为起始点P1；

使用线产生算法同时求出该三角形的两条斜边L、R上当前网格单元的下一个网格单元；

如果斜边L上的下一个网格单元在y方向上的坐标的高度大于斜边R上的下一个网格单元在y方向上的坐标的高度，则在斜边L上继续使用线产生算法获取下一个网格单元，直至斜边L上的下一个网格单元在y方向上的坐标的高度等于斜边R上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步；

如果斜边L上的下一个网格单元在y方向上的坐标的高度小于斜边R上的下一个网格单元在y方向上的坐标的高度，则在斜边R上继续使用线产生算法获取下一个网格单元，直至斜边R上的下一个网格单元在y方向上的坐标的高度等于斜边L上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步；

如果斜边L上的下一个网格单元在y方向上的坐标的高度等于斜边R上的下一个网格单元在y方向上的坐标的高度，则填充两条斜边L、R上的这两个网格单元及这两个网格单元中间的所有网格单元，将这两个网格单元分别作为两条斜边的当前网格单元并进入下一步。

3.根据权利要求2所述的基于线产生算法的三角形光栅化方法，其特征在于，所述步骤5包括：重复步骤4，使用线产生算法同时求出该三角形的两条斜边L、R上当前网格单元的下一个网格单元，直至扫描至两条斜边L、R的终点，且该三角形的内部的网格单元被完全填充。

4.根据权利要求1所述的基于线产生算法的三角形光栅化方法，其特征在于，所述步骤4中，使用线产生算法同时求出该三角形的两条斜边上当前网格单元的下一个网格单元的方法包括：

将斜边上的两个顶点分别作为起始点和终点，令e的初始值为-dx，dx为下一个网格单元与当前网格单元之间在x方向上的距离，令当前网格单元的初始值为斜边的起始点；

使用线产生算法从斜边的起始点开始扫描，以寻找当前网格单元的下一个网格单元，所述寻找当前网格单元的下一个网格单元包括：

当前网格单元P在x方向上步进一个单位，更新e=e+2*dy，dy为下一个网格单元与当前网格单元之间在y方向上的距离；

判断e是否大于等于0，若e大于等于0，则下一个网格单元在y方向上的坐标为当前网格单元在y方向上步进一个单位，同时更新e=e-2*dx，若e小于0，则下一个网格单元在y方向上的坐标为当前网格单元在y方向上的坐标。

5.根据权利要求1所述的基于线产生算法的三角形光栅化方法，其特征在于，所述网格单元为像素。

6.根据权利要求1-5中任一项所述的基于线产生算法的三角形光栅化方法，其特征在于，所述基于线产生算法的三角形光栅化方法应用于电子设备中。

7.根据权利要求1-5中任一项所述的基于线产生算法的三角形光栅化方法，其特征在于，所述基于线产生算法的三角形光栅化方法应用于芯片封装中。

8.一种基于线产生算法的三角形光栅化装置，其特征在于，包括存储器和处理器；

所述存储器用于存储计算机程序；

所述处理器，用于当执行所述计算机程序时，实现如权利要求1至7中任一项所述的基于线产生算法的三角形光栅化方法。

9.一种计算机可读介质，所述计算机可读介质上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时，实现如权利要求1至7中任一项所述的基于线产生算法的三角形光栅化方法。

10.一种计算机程序产品，包括计算机程序，其特征在于，所述计算机程序被处理器执行时，实现如权利要求1至7中任一项所述的基于线产生算法的三角形光栅化方法。