将三维曲面展平为二维片的方法

摘要

公开了用于将三维曲面展平为二维片的方法。在一个实施方式中，该方法由以下步骤实现：由所述三维曲面的曲面片上的特征曲线构造多个线曲片，其中每个所述特征曲线均包括多个线节点；计算已构造的线曲片的每个所述线节点的最佳二维角；基于计算出的所述最佳二维角，分别确定每个所述线节点的最佳位置；以及基于所确定的最佳位置在二维布置每个所述特征曲线。还提供了用于将三维曲面展平为二维片的装置。

说明书

技术领域

本申请涉及将三维曲面展平为二维片的方法和装置。

背景技术

对于各种产业的设计和制造公司，当其产品的制造需要不使用任何拉伸而将二维片状材料(例如，船舶业中的金属、服装业和玩具业中的织物、以及鞋业和家具业中的皮革)翘曲为三维形状时，在设计和制造周期中根据设计好的三维曲面片确定二维片的形状已变为瓶颈。曲面展平(或参数化)的问题通常在约束优化框架下用公式表示，得到的三维曲面片通常不是可展曲面，其长度不是恒定的。对于像三维服装设计和制造的工程应用，如果将多个片缝合到一起，这种长度变化将导致许多问题，并且服装形状和设计的合身将受到影响。

在由平面片状材料片制造产品的产业中，设计者需要一种曲面展平工具，其可根据其三维曲面片保持二维片上的边界长度和特征曲线。尽管存在许多不同的相关方法用于图样设计的三维建模或曲面展平，但这些方法要么耗时要么不具有长度保持的性质。

例如，文献中已有一些研究提出了致力于建模或对具有可展直纹面(或以其它方法表示的直纹面——例如，B-样条(B-spline)或贝塞尔(Bézier)片段)的模型进行近似的方法。然而，这些方法仅能对具有4侧边缘的曲面片进行建模，而难以用来对自由形式的曲面进行建模，因为这些曲面通常未限定在方形参数域上。尽管可考虑裁剪曲面(trimmed surface)，但这类方法对自由形式的对象进行建模的能力仍然非常有限。也就是说，提出的方法仅能设计具有相对简单的形状的对象。

将给定的待展平的三维曲面片P展平为其相应的二维展平片D的理想的曲面展平将保持任意两点之间的距离。也就是说，在数学上需要等距映射。然而，这种性质只保持在可展曲面上。因此，现有的曲面展平方法总是估算P和D上的表面点之间的距离变化的误差，并尝试在非线性优化框架下使该误差最小。遗憾的是，在顶点位置方面，非线性优化的计算非常耗时并且很难保持特征曲线的不变的长度。

另一种引起关注的曲面展平方法通过计算用于维度减少的映射或通过多维标度(MDS)技术解决该问题。这些方法全都基于计算将曲面上的测地距离投射为R²内的欧几里得距离(即，用于更低维度的空间)的最佳映射。然而，难以在映射计算中将硬约束嵌入特征曲线的长度中。

对于特征曲线的长度保持，J.R.Manning在“Computerized patterncutting：methods based on an isometric tree(计算机化的图案切割：基于等距树的方法)”一文中提出了保持网格上的特征曲线的长度的想法，该文献发表在1980年的Computer-Aided Design(计算机辅助设计)第12卷第1期的第43至47页上，其中引入了由等距地映射到平面上的网络曲线构成的等距树。然而，该网络具有树形拓扑，等距曲线是树的分支，这些曲线被一个接一个地展平而无需考虑曲线之间的关系。

在1991年的Computer Graphics(计算机图形学)第24卷第4期的第237至246页公开的文献“Piecewise surface flattening fornon-distorted texture mapping(用于不失真纹理映射的分段曲面展平)”中，Bennis等人将等参数曲线映射到平面上，然后通过松弛过程对这些曲线之间的曲面进行定位，并使用累进式算法处理复杂曲面；然而，这些等参数曲线之间的关系没有被很好地解决。

在2001年的Computer-Aided Design(计算机辅助设计)第33卷第8期的第581至591页公开的文献“Geodesic curvature preservation insurface flattening through constrained global optimization(通过约束的全局优化在曲面展平中保持测地曲率)”中，Azariadis和Aspragathos也提出了利用特征曲线在曲面展平中保持最佳测地曲率的方法。然而，因为该方法基于顶点位置的优化，所以其为高度地非线性且不能有效地求解。

在文献中，一些方法直接在R³对可展(或可展平)曲面进行建模，而不是计算曲面展平映射。如在文献“Virtual garments：a fullygeometric approach for clothing design(虚拟服装：用于服装设计的完全几何学方法)”中提出的，通过在每个顶点处局部地对圆锥面进行拟合来对给定的网格曲面进行处理，从而可确定期望的法向量，该文献公开在2006年的Computer Graphics Forum(Eurographics’06Proceedings)(计算机图形学论坛，06年的欧洲图形学会议)第25卷第3期的第625至634页。更通常地，在“Achieving developability ofa polygonal surface by minimum deformation：a study of global and localoptimization approaches(通过最小变形实现多边形曲面的可展性：对全局和局部优化方法的研究)”一文中，采用高斯曲率的离散定义来限定对给定的多边形网格曲面上的可展性的测量，其中采用约束的优化方法使网格曲面变形，以增加其离散可展性，该文献于2004年发表在Visual Computer(图像计算机)第20卷第8-9期的第521至539页。Liu等人在2006年的ACM Transactions on Graphics(图形学ACM会报)第25卷第3期的第681至689页发表的“Geometric modeling withconical meshes and developable surfaces(用圆锥网格和可展曲面的几何建模)”中提出了一种新颖的PQ网格，其可用于对可展曲面进行条带状建模。近来，提出了FL网格建模方案，其对具有更复杂形状的可展网格曲面进行建模。然而，不容易对上述任何方法进行修改以使其可将曲面从不可展的处理为可展的，并同时保持特征曲线的长度。此外，计算也慢了许多。

因此，非常需要一种可将给定三维曲面翘曲为二维并保持其边界和特征曲线的边缘长度的快速曲面展平方法。

发明内容

公开了一种用于将三维曲面展平为二维片的方法，包括：由所述三维曲面的曲面片上的特征曲线构造多个线曲片，其中每个所述特征曲线均包括多个线节点；计算已构造的线曲片的每个所述线节点的最佳二维角；基于计算出的所述最佳二维角，分别确定每个所述线节点的最佳位置；以及基于所确定的最佳位置在二维布置每个所述特征曲线。

还公开了一种用于将三维曲面展平为二维片的装置，包括：构造单元，配置为构造三维曲面中的多个线曲片并将所构造的线曲片排序为队列，所述队列限定所述多个线曲片的翘曲顺序；翘曲单元，配置为根据所述翘曲顺序对所述多个线曲片中的每个进行翘曲，以确定每个所述线节点的最佳二维位置；以及布置单元，配置为基于所确定的每个所述线节点的最佳二维位置在二维布置每个特征曲线。

附图说明

图1是待翘曲的四个线曲片的示意图；

图2示出了根据本发明一个实施方式的累进式翘曲方法的流程图；

图3示出了根据本发明一个实施方式将给定的线曲片翘曲为二维片的过程的流程图；

图4示出了根据本发明一个实施方式布置已翘曲的线曲片的特征曲线和内部网格的过程的流程图；

图5示出了根据本发明另一实施方式的全局翘曲方法的流程图；

图6示出了根据本发明一个实施方式将三维曲面展平为二维片的示意性装置；以及

图7是根据本发明的实施方式计算长度保持的最佳边界的示意图。

具体实施方式

首先，对本说明书中使用的术语给出如下必要的定义。

“特征曲线”是由给定的待展平的分段式线性曲面片上的多边形边缘形成的分段式线性曲线。具体地，每个特征曲线包括一个或多个线段，其中每个线段在分段式线性曲面片和展平片上都需要具有相同的长度。

对于特征曲线，如果其在展平片上的平面形状已经预先定义，其则称为“关键特征曲线”。其它的特征曲线则称为“附属特征曲线”，附属特征曲线的平面形状通过使在线段每个端点处的表面角和平面角之间的变化最小来确定。

将给定的曲面片上由特征曲线围绕的每个区域定义为“线曲片”(wire-patch)。给定的曲面片可分割为多个线曲片。每个线曲片的边界都包括多个特征曲线并由一系列“线节点”(wire-nodes)表示，其中每个线节点与一个特征曲线上的顶点重合。

对于同一线曲片上的三个相邻的线节点q_i-1、q_i和q_i+1，用α_i表示由q_i-1和q_i之间的第一线与q_i和q_i+1之间的第二线形成的表面角。与线节点q_i相关联的相应的二维角由θ_i表示。

参照图1，示出了曲面片P上的四个线曲片10至13以及其上的线节点14。对于特征曲线上的顶点，其可附有不止一个线节点，例如，由图1中的圆形围绕的顶点v就具有四个线节点。与曲面顶点相关联的线节点的数量等于与该顶点邻接的线曲片的数量。

“线曲线”(wire-curve)由曲面片P上一系列有序的定向边缘限定，其将两个相邻的线曲片分开。显然，线曲线与特征曲线重合，并且一个线曲片的边界通常由多个线曲线构成。

在本申请中，公开了用于将三维曲面展平为二维片的两种翘曲(warping)方案，即，累进式翘曲方案和全局翘曲方案，下文将分别对其进行讨论。

1.累进式翘曲方案

将参照图2详细描述根据本申请一个实施方式的累进式翘曲方法1000。该方法适用于接近可展的曲面片，并可适应于特征曲线上的局部形状控制。

如图2所示，在步骤101，由三维曲面的给定曲面片P上的特征曲线构造线曲片。在步骤102，将全部线曲片的形状显著因子(shape-evidence factor)初始化。对于每个给定的线曲片，其形状显著因子定义为：

l(P_i)＝n′/n    (1)

其中，n′是给定线曲片上二维角已知的线节点的数量，n是该给定线曲片上全部线节点的数量。基于全部线曲片的形状显著因子，在步骤103，将全部线曲片排序为队列，例如，由形状显著因子决定的最大堆栈，并且线曲片的翘曲顺序根据该队列确定。

在确定了翘曲顺序之后，在步骤104，从队列的顶部取出一个线曲片。取出的线曲片是全部线曲片中具有最大形状显著因子的线曲片。然后，在步骤105对该线曲片进行翘曲。对线曲片的翘曲将参照图3详细描述。

在步骤105之后，在步骤106随机地在该已翘曲的线曲片中选择线节点。然后，在步骤107，方法1000确定是否具有所选线节点的主顶点(host vertex)是线曲片P上的内部顶点(不在给定曲面的边界上的顶点)、并且该主顶点周围除了线节点q之外的全部线节点的二维角都已知。如果不是这样，方法1000则直接进入步骤109。否则，在步骤108锁定并存储线节点q的二维角。令$\hat{Q}\left(q\right)=\{q_k\in v\left(q\right)\}\backslash \left\{q\right\}$表示除了q之外与主顶点v(q)相关联的线节点的集合，且Г被定义为具有中的线节点的全部线曲片的集合。由于中的全部线节点的二维角都已知(例如，当Г内的全部线曲片都已翘曲为平面)，因此q的二维角被锁定为：

$\theta \left(q\right)=2\pi -\underset{q_k\in \hat{Q}\left(q\right)}{\Sigma }\theta \left(q_k\right)---\left(2\right)$

否则，v(q)周围的展平的线曲片将相互不相容。

在步骤109，方法1000确定是否已翘曲的线曲片中的全部线节点都已被选择。

如果在步骤109确定已翘曲的线曲片中的全部线节点都已被选择，方法1000则转至步骤110，以进一步确定是否全部线曲片都已被取出并因而队列为空。否则，方法1000回到步骤106，在已翘曲的线曲片中选择另一线节点。例如，逆时针地选择线节点。

如果在步骤110确定队列为空，则对与已翘曲的线曲片邻接的全部线曲片的形状显著因子进行更新，并对队列进行更新。否则，方法1000返回步骤104并从队列的顶部取出另一线曲片。

在步骤111之后，在步骤112，在二维中布置特征曲线，并对每个线曲片的内部网格进行计算和布置。稍后将参照图4对特征曲线和线曲片的内部网格的布置进行详细描述。

这样，在根据上述步骤对全部线曲片进行处理之后，给定的曲面就被累进地翘曲为二维片。

下面，参照图3详细描述对线曲片P进行翘曲的步骤105。

在步骤1051，如式(3)所示，根据约束优化计算从队列中取出的曲面片P上的线曲片上的线节点的最佳二维角。

为了将曲面片P上的特征曲线展平并保持线曲片的边界长度，在展平过程中，应该将线曲片的边界上的边缘模拟为钢筋线(tendonwire)，并且应该使边缘和钢筋线之间的表面角变化最小化。因此，翘曲的线曲片的二维形状与其在曲面片P上的形状类似。

基于上述要求，实际由特征曲线上的边缘形成的、线曲片的最佳平面边界可在如下约束优化框架下计算：

$\underset{{\theta }_i}{\min }\underset{i=1}{\overset{n}{\Sigma }}\frac{1}{2}{({\theta }_i-{\alpha }_i)}^2---\left(3\right)$

约束条件为：$\mathrm{n\pi }-\underset{i=1}{\overset{n}{\Sigma }}{\theta }_i\equiv 2\pi ,$$\underset{i=1}{\overset{n}{\Sigma }}{l}_i\cos {\phi }_i\equiv 0,$$\underset{i=1}{\overset{n}{\Sigma }}{l}_i\sin {\phi }_i\equiv 0$

其中，q_i表示将要计算其最佳二维角的线节点；θ_i是与该线节点相关联的二维角；α_i表示该线节点的三维表面角；l_i表示线节点q_i所在的线曲片的边界上的边缘长度；φ_i表示线曲片的边界上的边缘的转动角；以及n是边界上线节点的数量。

应该注意到，角度变化项被设置为目标函数中的软约束，长度恒定项则被设置为硬约束。以这种方式，在角度空间中表明长度不变条件下的角度变化，这极大地简化了计算。

对于简单的非自相交的平面闭合路径，如果其路径是逆时针的，则该路径上任何顶点的总转动角都一定为2π。通过将顶点转动角累积得到的总转动角可由∑_i＝1ⁿ(π-θ_i)计算，其得到第一个约束nπ-∑_iθ_i≡2π。式(3)中的最后两个约束由位置相符要求而得到。如图7所示，通过给定内转角θ_i并将线节点q₁置于原点，线节点q_i的平面坐标(x_i，y_i)变为$x_i={\Sigma }_{k=1}^{i-1}{l}_k\cos {\phi }_k$和$y_i={\Sigma }_{k=1}^{i-1}{l}_k\sin {\phi }_k.$此外，可得到线节点q_i处的θ_i＝2π-(φ_i-β)，且线节点q_i-1处的β＝φ_i-1-π，从而得到：

φ_i＝π-θ_i+φ_i-1    (4).

由于φ₁＝π-θ₁，可推导出φ_i的通用公式为${\phi }_i=\mathrm{i\pi }-{\Sigma }_{b=1}^i{\theta }_b.$为了确保线曲片的边界是闭合的，(x_n+1，y_n+1)必须与原点一致，从而得到式(3)中的最后两个约束。

在计算出θ_i的最佳值之后，φ_i的值则可确定。因此，在步骤1052，由下式确定每个线节点的最佳位置：

q_i+1＝q_i+(l_i cosφ_i，l_i sinφ_i)^T    (5)

这样，则对从队列取出的线曲片进行了翘曲。

注意，计算线曲片的最佳平面边界可需要锁定某些线节点处的二维角度值。例如，如果线节点q_i位于关键特征曲线上且其二维形状由设计者指定，那么q_i处的最佳值已经给定。

下面，参照图4描述特征曲线和每个线曲片的内部网格的布置。

为了布置特征曲线，需要通过传播对线曲片重新排序并存储在列表中。通过扩散算法(flooding algorithm)确定线曲片的重新排序的顺序，其中，重新排列的列表随机地从与特征曲线邻接的任意线曲片开始，然后是其相邻线曲片、与该相邻线曲片相邻的线曲片等等。由于线曲片顺序地排列在列表中，可对逐个线曲片中的线节点的主顶点进行放置。

当给定的网格曲面被展平后，主顶点可为内部顶点或边界顶点，其中，边界顶点是待展平的给定曲面的边界上的顶点，内部顶点是不位于给定曲面的边界上的顶点。线曲片的边界实际上由特征曲线的边缘形成。待展平的给定网格曲面上的每个顶点均为网格顶点，如果一个网格顶点不在边界上，其则为内部顶点。

当在二维布置线曲片及其内部网格时，首先放置特征曲线，因为线曲片的边界实际上是由特征曲线上的边缘形成的。然后，在线曲片的边缘固定的情况下计算内部网格顶点(内部顶点)的位置，并放置线曲片的内部顶点。下面详细描述放置翘曲的线曲片的特征曲线和内部网格的步骤。

由于特征曲线由线节点限定，因此需要首先布置线节点并从而布置特征曲线。线曲片中的线节点分为两类：固定节点和自由节点，固定节点的主顶点的二维位置是已知的，而自由节点的主顶点是还未被放置的。由于在列表中的第一线曲片上不具有固定的线节点，因此，在步骤1121，从第一线曲片中随机选取两个相邻的线节点，并通过保持这两个线节点之间的距离将其在二维固定。在步骤1122，从固定节点开始对线曲片中的线节点进行逆时针地搜寻，以顺序地寻找自由节点。利用前两个固定节点的主顶点的位置、自由节点的主顶点和与该自由节点相邻的固定节点的主顶点的三维边缘长度、以及与该自由节点相邻的固定节点的最佳二维角，可由式(5)确定该自由节点的主顶点位置。当确定了自由节点的主顶点的位置之后，则可放置该自由节点和相应的固定线节点之间的特征曲线。

此后，该自由节点变为固定节点。类似地，可连续放置该线曲片上的其它自由节点。

在步骤1123，以这种方式根据上述重新排序的顺序对全部特征曲线顺序地放置。

最后，需要在二维放置与任何线节点都不相关的网格顶点(即，线曲片的内部顶点)，以生成正确的网格曲面表示。在步骤1124，首先将每个线曲片的每个内部顶点v_i布置在相应线曲片的边界顶点的平均位置。接下来，在步骤1125，通过如下算子迭代地移动v_i的位置：

${v_i}^{\mathrm{new}}\leftarrow \frac{1}{w\left(v_i\right)}\underset{j\in N\left(v_i\right)}{\Sigma }{\left|\right|v_i{v}_j\left|\right|}^{-1}{v}_j,---\left(6\right)$

其中||...||表示给定曲面上两个顶点之间的距离，N(v_i)表示顶点v_i的一环近邻(1-ring neighbor)，且w(v_i)是总权重。

为了进一步加速计算，可引入松弛因子(relaxing factor)，在大多数实施例中，其将迭代步骤的数量减少大约三分之二。由于松弛因子的使用是本领域常用的，因此在此不对其进行详细描述。

2.全局翘曲方案

参照图5，示出了根据本申请另一实施方式的全局翘曲方案4000的示意性流程图。该方法适用于对高度弯曲的曲面进行展平。对于完全不可展的曲面，使用累进式翘曲方案进行展平将会在给定的翘曲线曲片上出现很大失真，这是因为该方案会将已翘曲的线曲片上的失真从第一个翘曲的线曲片一直累加到最后一个翘曲的线曲片。因此，提出了全局翘曲方案，以用于高度弯曲的曲面。

为了通过全局翘曲计算线曲片的展平，将用于全部线曲片的约束优化综合为一致的约束优化，以对全部线曲片一起进行翘曲。除了闭合路径约束和位置相符约束之外，还引入了相容性约束，从而与内部主顶点v相关联的线节点的二维角的总和为2π。

在不失一般性的情况下，在步骤4002，首先由给定曲面片上的特征曲线构造线曲片。如果给定曲面片P上总共构造了m个线曲片，则具有∑_p＝1^mn_p个线节点，其中n_p表示索引为p的线曲片P_p的线节点的个数。由于全部线曲片都将被一起翘曲，因此每个线节点都将具有线曲片内的一个局部索引以及另一个全局索引，稍后将对此进行详细描述。为了简化表示，定义了置换函数Г_p(b)及其反函数Г_p^-1(j)，函数Г_p(b)用于返回线曲片P_p上局部索引为b的线节点的全局索引，函数Г_p^-1(j)则提供线曲片P_p上的线节点q_j的局部索引。在步骤4004，计算所构造的全部线曲片上的线节点的约束的最佳二维角，以使展平的全局失真最小化，其可由如下公式表示：

${\min }_{{\theta }_i}{\Sigma }_i\frac{1}{2}{({\theta }_i-{\alpha }_i)}^2---\left(6\right)$

约束条件为：

$n_p\pi -{\Sigma }_{b=1}^{n_p}{\theta }_{{\Gamma }_p\left(b\right)}\equiv 2\pi$$(\forall p=1,...,m)$

${\Sigma }_{b=1}^{n_p}{l}_b\cos {\phi }_b\equiv 0,$${\Sigma }_{b=1}^{n_p}{l}_b\sin {\phi }_b\equiv 0$$(\forall p=1,...,m)$

${\Sigma }_{q_k\in v}{\theta }_k\equiv 2\pi$$(\forall v\in \Phi )$

其中，q_i表示将要计算其最佳二维角的线节点；Φ表示附属特征曲线上的内部顶点的集合；θ_i是与线节点q_i相关联的二维角；α_i表示与线节点q_i相关联的三维表面角；φ_b表示线曲片的边界上的边缘的转动角；以及l_b表示特征曲线上的边缘的长度。

通过连续线性约束的程序，约束优化问题可通过求解一系列稀疏线性方程用牛顿法解决。当用牛顿算法将曲面展平时，通过令θ_i＝α_i开始计算，牛顿算法总是在10次迭代内停止。牛顿算法如下所示：

while||δ_θ||²/n＞10^-8do

$\mathrm{Solve}{▿}^{2}J\left(X\right)\delta =-▿J\left(X\right);$

X←X+δ；

end while

如上所述，每个线节点均具有一个局部索引和另一个全局索引。对于每个线节点，利用这两个索引非常容易确定其在最终线性方程系统(即，上述牛顿算法的第二步中的稀疏线性方程系统)中的行和列。在其行索引和列索引已知后，可将相应的系数插入线性方程系统，然后迭代地求解以确定最佳二维角。此外，对与线节点相关的角度值的估算也非常容易。通过这两个索引，可有效地执行该优化问题的数值计算。

在步骤4006，以与累进式翘曲的步骤1052类似的方式计算特征曲线上的顶点的平面坐标。在步骤4008和4010，以与步骤1123和1124相同的方式在二维放置内部顶点。应该注意，当使用φ_i＝π-θ_i+φ_i-1，从而根据θ_i计算φ_i的值时，应包括了被锁定的线节点的二维角，这是因为其也对每个线曲片的形状做出了贡献。

根据本申请，计算以下两个误差项，即，边缘长度误差和角度误差，用于测量展平的结果。

1.边缘长度误差

通过下式测量特征曲线上的边缘的长度变化：

$E_{\mathrm{len}}=\frac{1}{N\left({\Omega }_e\right)}\underset{e\in {\Omega }_e}{\Sigma }\frac{|l_e^0-l_e|}{l_e^0},---\left(7\right)$

其中Ω_e是全部特征曲线上的边缘的集合，N(...)定义了集合中的元素数量，l_e⁰是边缘e的三维长度，l_e是其二维长度。

2.角度误差

给定分段式线性曲面上的全部多边形的角度变化如下测量：

$E_{\mathrm{ang}}=\frac{1}{N\left({\Omega }_a\right)}\underset{a{\in \Omega }_a}{\Sigma }\frac{|{\theta }_a^0-{\theta }_a|}{{\theta }_a^0}---\left(8\right)$

其中Ω_a是给定网格曲面P上全部多边形角的集合；θ_a⁰和θ_a分别是二维和三维的多边形角a的值。

对于理想的展平结果，应该令E_len和E_ang都为零。然而，在不可展曲面中，这两个误差项通常不能相互相容。根据本申请的方法的结果保持E_len≡0，并试图使E_ang的值最小化。

根据本申请的累进式翘曲方案和全局翘曲方案都能计算展平片并保持特征曲线上的边缘长度。全局翘曲方案具有较小的角度失真，这是因为其实际上将失真误差分散至全部的线曲片，而累进式翘曲方案则将误差累积。同样，累进式翘曲方案和全局翘曲方案均能以交互速度实现。

图6示例性地示出了根据本发明一个实施方式将三维曲面展平为二维片的装置100。

装置100包括构造单元10、翘曲单元20以及布置单元30。

构造单元10被配置为在三维曲面中构造多个线曲片。线曲片由三维曲面的给定曲面片上的特征曲线限定。对于每个给定的线曲片，根据式(1)对形状显著因子进行初始化。基于全部线曲片的形状显著因子，构造单元10操作为将全部线曲片排序为队列，所述队列例如为由形状显著因子决定的最大堆栈，根据该队列，确定线曲片的翘曲顺序。

翘曲单元20被配置为根据构造单元10确定的翘曲顺序对线曲片进行翘曲，以确定各线节点的最佳二维位置。具体地，翘曲单元20可具有两种翘曲方案，即，累进式翘曲方案和全局翘曲方案。由于上文已参照图3和图4分别对这两种方案进行了讨论，在此不再进行描述。

布置单元30被配置为基于所确定的各线节点的最佳二维位置在二维布置每个特征曲线。布置单元30的布置与图4的步骤类似，因此在此不再对其进行描述。

尽管图6中将构造单元10、翘曲单元20和布置单元30示为三个分离的单元，但本发明并不限于此。应该理解，单元10、20和30可集成到一个芯片中或分离地设置为多个单元，并可由软件、硬件或其组合实现。

尽管示出并描述了本发明的实施方式和实现，但应该理解，可在形式和细节上做出各种其它变化而不偏离本发明的精神。