JP2006185444A - 進化的最適化方法および自由形状変形方法 - Google Patents

Abstract

【課題】改善された最適化技法を提供する。
【解決手段】本発明は、設計を最適化するための方法を提供する。設計は変換関数によって変更される。スプライン関数によって変換関数を定義する自由形状変形が用いられる。スプライン関数は、設計が定義される空間を、新しい変更された設計が定義される第２空間に変換する。設計処理中に、スプライン関数のパラメータが、変換関数のパラメータを決定する。自由形状変形は、進化的計算の表現として使用される。
【選択図】図５

Description

本発明は、設計最適化および進化的計算を用いた自由形状変形に関する。

設計最適化問題に最適化アルゴリズムを適用するためには、最適化アルゴリズムによって変更できるパラメータの組によって設計の形態を記述する形を見つけることが必須である。周知の方法は、たとえば、最適化される物体の表面を記述する、２次元表面の場合にスプライン曲線、３次元設計の場合にスプライン曲面を定義することである。この場合に、最適化アルゴリズムによって変更されるパラメータは、制御点およびノット点（knot point）であり、さらに、ＮＵＲＢＳ（non-uniform rational B-spline、非一様有理式Ｂスプライン）の場合に、制御点の重みがある。所与の設計を表すもう１つの形が、基礎設計が与えられる空間を変換する変換関数を定義することである。この場合に、形態の変形は、変換関数のパラメータを変更することによって実現することができる。この方法を、自由形状変形（free form deformation：ＦＦＤ）という用語の下で要約することができる。

従来技術：自由形状変形
したがって、自由形状変形は、従来技術で既知であり、次で短く説明する。

拘束付き変形
この原理は、BorrelおよびBechman（非特許文献２）によって定式化された。彼らは、任意の個数のユーザ指定の点の変位拘束（displacement constraint）によって定義される一般変形方式を開発した。BorrelおよびBechmannの変形方法を、図１に示すが、この方法は、次の原理に基づく：原空間および変形された空間Ｒ^ｎは、より高次元の空間Ｒ^ｍの２つの射影である。したがって、変形は、オリジナル空間Ｒ^ｎの点をＲ^ｍの点に変換する関数ｆ:Ｒ^ｎ→Ｒ^ｍと、Ｒ^ｍからＲ^ｎへの射影Ｔの合成によって定義される。射影行列は、原空間の所与の点（拘束点（constraints points）と呼ぶ）の所与の変位（拘束（constraints）と呼ぶ）を達成するように計算される。

数学的に言うと、Ｒ^ｎの任意の点に対する変換を表す変形関数ｄは、関数ｆ:Ｒ^ｎ→Ｒ^ｍ（ｍ＞ｎ）と線形変換Ｔ:Ｒ^ｍ→Ｒ^ｎの合成として表される。Ｕ∈Ｒ^ｎであり、ＭがＴの対応する行列である場合に、
ｄ（Ｕ）＝Ｍｆ（Ｕ）
が得られる。

ｆおよび中間次元ｍの選択によって、図１からわかるように、可能な変形の組が定義される。

異なる関数ｆは、異なるタイプの変形、たとえばグローバル変形またはローカル変形を作る。具体的な変形は、行列Ｍだけに依存する。対応する変換Ｔは、潜在的な変形の集合から「適切な」変形を選択する。ｎに対してｍが大きいほど、可能な変形の範囲が広くなる。

一般に、「このモデルは、可能な変形の大きな一群をカプセル化する：たとえば、線形空間変換は、ｆが線形の時に得られ、ＦＦＤは、ｆがテンソル積ベルンシュタイン多項式であり、Ｍが制御点の変位ベクトルを用いて作られる場合に得られる」。

ｆおよびｍが指定されたならば、適切なＭおよびその結果として任意の点Ｕ∈Ｒ^ｎの変換が、ｎ_ｃ個の拘束点Ｖ_ｉの助けを得て、３ステップで実行される。

１．ｎ_ｃ個の拘束点Ｖ_ｉ、ｉ∈［１，ｎ_ｃ］の所望の変位を選択する。これらの点は、本質的に、設計最適化の自由度を確立する。

２．射影行列Ｍは、ｎ_ｃ個の式のｎ個の系を解くことによって得られ、ｍ個の未知数がＭの１行を構成する。この系は、任意のｉ∈［１，ｎ_ｃ］に対するｎ×ｎ_ｃ個の式
ｄ（Ｖ_ｉ）＝Ｍｆ（Ｖ_ｉ）
から導出される。

残念ながら、この連立方程式は、どの場合にも一意に解くことが可能ではなく、これが、ここで説明する技法の主要な短所を構成する。次の３つの状況を区別することができる。

ａ）ｍがｎ_ｃより大きく、すべてのｆ（Ｖ_ｉ）ベクトルが線形独立である場合に、無限の個数の解が存在する。ユーザが１つのＭを選択することによって、変形が固定される。それを行う複数の形が、BorrelおよびBechmann（非特許文献２）によって議論されている。

ｂ）ｍ＝ｎ_ｃの場合に、１つの解Ｍだけが存在する。

ｃ）それ以外の場合に、拘束を満足する変形を見つけることはできない。この場合に、最良の近似解が使用される。

３．すべての点Ｕの変位を、ｄ（Ｕ）＝Ｍｆ（Ｕ）によって計算する。

再変換Ｍが、拘束点Ｖ_ｉだけに依存するという事実に起因して、最初のオブジェクトＵ（点Ｕ_ｌの集合）の変形は、非常に効率的に実行することができる。値ｆ（Ｕ_ｌ）は、一回だけ計算する必要があり、その後、拘束の複数の組によって定義される複数の変形に使用することができる。その結果、設計最適化は、追加、削除、または変更された拘束についてのみｆ（Ｖ_ｉ）の値の再計算を必要とし、オブジェクト点Ｕ_ｌについては不要である。

既に指摘したように、Ｍの選択処理は、技術的に要求が厳しく、ユーザとのインタラクションを必要とする。さらに、変形の形態は、拘束に強く相関せず、これによって、この技法が非直観的になっている。これらの不足を迂回するために、BorrelおよびRappoport（非特許文献３）は、一般拘束変形概念を単純化した。この手法は、単純化拘束変形（Simplified Constraint deformation：Scodef）と呼ばれる。Scodef手法の中心概念は、再変換Ｍの統一であり、それによる処理全体の単純化である。これは、それぞれがある拘束点を中心とするＢスプライン基底関数（basis function）のテンソル積としてのｆの選択によって達成され、各点は、変形処理に影響する。さらに、ｎ_ｃ個の拘束点ごとに、各Ｂスプラインのスコープに影響する半径が導入され、すなわち、各基底関数は、対応する拘束点の半径の外で０になる。したがって、異なる半径を、変形処理の微調整に使用することができる。その結果、「Scodef変形は、空間で任意の個数の可能なオーバーラップするＢスプラインの形の「バンプ（bump）」を作成することによって得られる変形と見なすことができる。バンプの位置および高さは、拘束によって定義され、その幅は、影響の拘束半径によって定義される」。

すべてのタイプの形態を拘束変形手法によって表現できるかどうか（完全性要件（completeness requirement））は文献からは不明瞭であるが、Ｂスプラインの使用は、この技法が、Ｂスプラインのように複雑な曲線を効率的かつ正確に表現できることの強い証拠を与える。

ＥＳを使用する設計最適化について、拘束および／または拘束の変位は、ＥＳ標準の遺伝的操作（genetic operator）の助けを得て変更できる自由パラメータを構成する。単純化拘束変形の場合に、ｎ_ｃ個の拘束点Ｖ_ｉに関連する半径を、追加の設計パラメータとして使用することができる。その結果として、３つのグループの設計パラメータが使用可能であり、これにより設計パラメータの数においてこの技法が非常に柔軟になる。最良の場合に、４つの拘束点だけが、３Ｄ物体の変形に必要である。さらに、ｎ_ｃ個の式の基礎になる系に起因して、拘束点、その変位、および半径の３つ組を、他の設計パラメータに影響せずにたやすく追加し、または削除することができる。もちろん、そのような適応処理は、変換行列Ｍの構造を変更することができ、したがって、結果の設計を変更することができる。これは、たとえば、対照的に制御点の再計算を強制する、加算演算子を保存する面の曲線が存在するＢスプラインまたはＮＵＲＢＳと対照的である。

自由形状変形
より以前に開発されたが、自由形状変形（ＦＦＤ）手法（非特許文献９）（図２も参照されたい）は、上で説明した拘束変形手法の特殊事例である。これは、変形関数ｆが、ベルンシュタイン多項式（Bernstein polynomials）のテンソル積（または、単純化拘束変形の場合にＢスプライン基底関数）であり、Ｍが、制御点の変位ベクトルを用いて作られる場合に当てはまる。拘束変形に非常に似て、ＦＦＤは、より一般的な対話型の形態編集概念の形成に焦点を合わせたものである。SederbergおよびParry（非特許文献９）は、ベジエ、Ｂスプライン、およびＮＵＲＢＳを用いて作られた曲線または曲面の変形の正確な指定が、ほとんどの場合に面倒すぎると考えた。「知覚的に単純な変更であっても、多数の制御点の調整を必要とする場合がある」（非特許文献５）。

SederbergおよびParryは、立方体または円筒などの標準的な幾何形態のグリッド点の格子に物体を埋め込むことによって、規則的な変形（固体のＲ^３からＲ^２への写像）に対する手法を一般化した（非特許文献１）。グリッドのノードの操作によって、３変数テンソル積ベルンシュタイン多項式の助けを得て、グリッドの内部の空間に対する変形が誘導される。これらの変形は、物体を形成する基礎になるグラフィックス・プリミティブを変換する。SederbergおよびParryは、ＦＦＤのよい物理的類似を与えた。「変形が望まれる１つまたは複数の物体が組み込まれた透明で柔軟なプラスティックの平行六面体を検討されたい。物体も柔軟であると考えられ、その結果、物体は、その周囲のプラスティックに似た形で変形する」（非特許文献９）。

既に指摘したように、ＦＦＤの最初のステップは、囲む平行六面体領域の局所座標系Ｓ、Ｔ、Ｕの固定である。ある基本的な線形代数の助けを得ると、平行六面体の各点Ｘを、次のように新しい座標系で表すことができる。

Ｘ＝Ｘ_０＋ｓＳ＋ｔＴ＋ｕＵ
ＦＦＤのアイデアは、囲むボリュームの変形が、そのボリュームの内部の変形を誘導することなので、次のステップは、平行六面体の制御点Ｐ_ｉｊｋのグリッドの形成である。Ｓ方向でｌ個、Ｔ方向でｍ個、Ｕ方向でｎ個のグリッド点が、その制御点がグリッド点である３変数テンソル積ベルンシュタイン多項式の助けを得て、変形された囲むボリュームの定式化を可能にする。潜在的な設計最適化の自由パラメータを本質的に作る制御点の変形は、単に、その変位していない格子位置からＰ_ｉｊｋを移動することによって指定される。任意の点Ｘの変形された位置Ｘ_ｆｆｄは、まず局所座標系でその（ｓ，ｔ，ｕ）座標を計算し、次にベクトル値を有する３変数ベルンシュタイン多項式

を評価することによって見つかるが、ここで、Ｘ_ｆｆｄは、変位された点のデカルト座標であり、各Ｐ_ｉｊｋは、制御点のデカルト座標を含むベクトルである。ほとんどの他の設計表現技法と異なって、（単純化）拘束変形手法の主な動機づけは、形態設計者のための直観的な設計ではない。そうではなく、基礎になる幾何表現に依存しない形態変更ツールが、主な関心事である。

拡張型自由形状変形（ＥＥＦＤ）
Sederberg他によって導入された基本的な自由形状変形の概念を、より高度な柔軟性に関して改善するために、Coquillartは、拡張型自由形状変形（Extended Free Form Deformation：ＥＥＦＤ）と呼ばれる方法を開発した（非特許文献１）。この方法では、標準的な自由形状変形の制御点の平行六面体ボリュームという制限的要件と異なって、任意の制御ボリュームの使用が可能である。この変更のゆえに、物体を変形する手順が、適合されなければならず、数学的基礎が、Ｂスプラインに切り替えられなければならなかった。これは、主に、下で短く説明する３つのステップに分かれる。

まず、物体全体または物体のうちで変形について対象とされている部分のいずれかを囲む制御点の格子（lattice）を構成しなければならない。第２ステップで、幾何座標を、格子のパラメータ空間に変形しなければならず、これを、「フリージング（freezing）」とも呼ぶ。物体のフリージングによって、スプライン・パラメータ空間での幾何形態のｕ、ｖ、およびｗ座標が計算される。これは通常、最も高速の手法である見込みがあるニュートン近似によって行われるが、類似する傾きに基づく方法または進化的最適化（evolutionary optimisation）によって行うこともできる。ｕ、ｖ、およびｗ座標をうまく計算した後に、制御点を所望の位置に移動し、表面または固体のｘ、ｙ、およびｚ座標を更新することによって、変形を適用することができる。したがって、Ｂスプライン式を、制御点の新しい空間座標を使用して解かなければならない。この方法は、幾何モデルが固体と等しいか、助変数方程式または暗黙の式によって定義される場合にも有効である。
A.H. Bar, "Global and Local Deformation of Solid Primitives", Computer Graphics, 18(3):21-30, 1984. P. Borrel and D. Bechmann, "Deformation of n-dimensional objects", International Journal of Computational Geometry Applications, 1(4):427-453, 1991. P. Borrel and A. Rappoport, "Simple Constrained Deformations for Geometric Modeling and Interactive Design", ACM Transactions on Graphics, 13(2):137-155, April 1994. S. Coquillart, "Free-Form Deformation: A Sculpturing Tool for 3D Geometric Modeling", Computer Graphics, 24(4):187-196, August 1990. S. Gibson and B. Mirtich, "A Survey of Deformable Modeling in Computer Graphics", Tech. Report No.TR-97-19, Mitsubishi Electric Research Lab., Cambridge, November 1997 Markus Olhofer, Yaochu Jin and Bernhard Sendhoff, "Adaptive encoding for aerodynamic shape optimization using evolutionary strategies", Congress on Evolutionary Computation (CEC), volume 2, pages 576-583, Seoul, Korea, May 2001. IEEE Press. L. Piegl and W. Tiller, "The NURBS BOOK", Springer-Verlag Berlin Heidelberg 1995 and 1997. T.W. Sederberg, D.L. Cardon, G.T. Finnigan, N.S. North, J. Zheng and T. Lyche, "T-spline Simplification and Local Refinement", ACM Transactions on Graphics, 23(3):276-283, August 2004. T.W. Sederberg and S.R. Parry, "Free-Form Deformation of Solid Geometric Models", Computer Graphics, 20(4):151-160, August 1986. T.W. Sederberg, J. Zheng, A. Bakenov and A. Nasri, "T-splines and T-NURCCs", ACM Transactions on Graphics, 22(3):477-484, July 2003.

本発明の目的は、改善された最適化技法を提案することである。

この目的は、独立請求項の特徴によって達成される。従属請求項は、さらに、本発明の中心概念を展開するものである。本発明は、本発明による表現として自由形状変形を使用する進化的計算（Evolutionary Computation）を提案する。

自由形状変形と進化的計算の組合せは、本発明の１態様である。

自由形状変形での本発明のもう１つの態様によれば、変形が、問題に適合される。

本発明のもう１つの態様によれば、Ｔスプラインが、自由形状変形の変換関数としての進化的計算と組み合わせて使用される。

本発明のさらなる目的、特徴、および長所は、添付図面を参照して実施形態の次の説明に進む時に明白になる。

進化的計算での（拡張型）自由形状変形
進化的最適化に関して、自由形状変形技法の適用は、特に、最適化されなければならない形態の幾何定義がかなり複雑である場合および／またはコストの高い計算流体力学（Computationally Fluid Dynamics：ＣＦＤ）計算または有限要素法（Finite Element Method：ＦＥＭ）計算を実行しなければならない場合に、多数の利益を特徴とする。自由形状変形と、最適化の目標にされているパラメータとの一体化は、形態幾何自体によって定義されるのではなく、格子の制御点によって定義される。その結果、設計者は、グローバル形態変更またはローカル形態変更の度合を選択することができる。

一般に、最適化ループを開始できるようになる前に、初期形態を格子に埋め込まなければならず、幾何形態をフリーズして、パラメータ空間内のｕ、ｖ、およびｗ座標を入手しなければならない。これらの座標は、進化的最適化の設計評価ステップの前の遺伝子型−表現型写像（genotype-phenotype mapping）で主要な役割を演ずる。パラメータとしての制御点に基づいて、突然変異を適用することができ、適応度評価のためにシステムを準備することができる。したがって、新しい設計は、新しい制御点と結合されるフリーズされたｕ、ｖ、ｗ座標に基づくＢスプライン式またはＮｕｒｂｓ式を介して計算される。その後、設計を評価することができ、適応度の値が、各個々に割り当てられる。最後に、新しいパラメータを選択し、次世代の親を、選択された進化的アルゴリズムに従って決定する。

ＣＦＤ評価またはＦＥＭ評価と結合された（拡張型）自由形状変形の効果
ＣＦＤまたはＦＥＭと組み合わされた自由形状変形の多数の利益を理解するために、制御点の位置の変更が、格子のある空間領域に強い影響を有することを考慮しなければならない。サイズがたとえばスプラインのタイプ、スプライン次数、制御点の個数、ノットベクトル（knot vector）などによって定義されるこのボリューム全体が変形される、すなわち、このボリューム内で見つかる形態設計だけではなく、それを囲むすべてのものが変形される。ＣＦＤ計算に関係する結果として、このボリューム内に位置するすべてのグリッド点も変形される。したがって、複雑な形態に関して、計算的にコストの高いメッシュ生成処理を省略することができる。というのは、自由形状変形が適用される時に、グリッドが、変形された形態に直接に適合されるからである。第２に、ＣＦＤに関して、時間のかかるＣＦＤ計算全体を繰り返すのではなく、既に解に収束している、以前の結果を使用することも可能である。

（拡張型）自由形状変形のパラメータ適応性
自由形状変形のこの拡張は、本発明のさらなる開発に特に有利である。すべての種類の最適化において、適用される表現の高い度合の柔軟性が有利である。設計者は、常に、検索空間とパラメータ最小化の間の適当なトレードオフを見つけることを強いられる。一方で、できる限り多くの設計を表現しなければならず、他方で、少数のパラメータを使用して最適化処理を高速化しなければならない。柔軟性に対するよい代替案は、適応的な表現によって提供される。その結果、最適化の開始時に、少数のパラメータを最適化するだけでよく、収束の過程で、パラメータの個数を増やすことができる。

自由形状変形は、設計処理で実際の形態を変更せずに、さらなる制御点を追加することによってノットベクトルを拡張する可能性を提供する。この事実は、進化的設計最適化において非常に重要である。非常に少数のパラメータだけを用いて最適化を開始し、必要な時にいつでも、新しい制御点を追加して、実際の最良の設計を失わずに形態に対する影響を拡張することができる。この表現のこれらの非常に前向きの特徴のほかに、制御点挿入に、１つの主要な不利益が付随する。新しい制御点を挿入しなければならない時に、必ず、２次元の場合に制御点の新しい列または行全体、３次元の場合に制御点の平面を制御点グリッドに導入する可能性だけが存在する。したがって、残念ながら、幾何学的理由から直接に望ましい場合に１つの制御点だけを挿入することは不可能であり、結果として、多数の余分な点を考慮に入れなければならない。この影響を最小にするために、Ｔスプラインという概念を、以下に説明する。Ｔスプラインとは、制御点の部分的な行または列だけを制御メッシュに挿入することを可能にする特別な種類の点ベースのＢスプラインである。

Ｔスプライン
したがって、Ｔスプラインの概念は、たとえばコンピュータ・グラフィックスに関して、既に既知の表現である。

従来技術から既知のＴスプラインの導入
Ｔスプラインの概念は、グラフィカル設計の処理でのより高い柔軟性を達成するために、Sederberg他によって導入された（非特許文献１、非特許文献１０）。Ｔスプラインは、基礎になるメッシュでの制御点の配置の指定に関する限りない利益を提供する、不均一Ｂスプライン曲面の一般化である。水平線および垂直線の各交点で定義される制御点の長方形グリッドを必要とするＢスプライン曲面と異なって、Ｔメッシュの線は、グリッドの端で始まり、終わる必要はなく、Ｔ字型接続点で終わることができる（たとえば、図４）。その結果、制御点の総数が劇的に減る。この事実は、より柔軟で効率的な曲面設計を可能にするために１つまたは複数の追加制御点を挿入しなければならない場合に、さらに重要になる。Ｂスプライン曲面では、制御点の完全な新しい行および／または列を設けなければならないが、Ｔメッシュでは、ほとんどの場合に、少数の新しい点を追加するだけでよい。

ノット挿入（knot insettion）の手順について、Sederberg他は、後で詳細に説明するローカル洗練アルゴリズム（local refinement algorithm）を開発し、次いで、「Ｔスプライン単純化（T-spline Simplification）」と呼ばれる、余分な制御点を除去する概念を開発した。除去アルゴリズムの適用によって、設計形態がＢスプラインを介して定義されている場合に必要な制御点の総数を減らすことが可能になる。

図５に、ＮＵＲＢＳモデルのＴスプラインへの変換の効果を示す。モデル化された頭の制御点の総数は、４７１２個から１１０９個に減り、女性の場合に１０３０５個から３９５５個に減っている。その結果、設計者は、モデルに対するより効率的な制御を得、単一の制御点の位置の移動が、形態に対するより密接な影響を有する。さらに、Ｔスプラインの概念は、２次元での曲面モデリングに有効であるだけではなく、他の次元およびＴスプラインの任意トポロジ版であるＴ−ＮＵＲＣＣ（Non-Uniform Rational Catmull-Clark Surface、非一様有理式カットマル−クラーク局面）に簡単に拡張することができる（非特許文献１、非特許文献８、非特許文献１０）。

Ｔスプラインの数学的定義および規則
Ｔスプラインは、Sederberg他（非特許文献１０）によって導入されたいわゆる点ベースＢスプライン（point based B-splines、ＰＢスプライン）から導き出すことができる。ＰＢスプラインは、制御点の組と、２次元で制御点ごとのノットベクトルの対によって定義される。結果の面の点を計算するために、次の式を解かなければならない。

Ｂ_ｉ（ｓ，ｔ）は、ブレンディング関数であり、次式にように定義される。

B_ｉ(s, t)＝N[s_i０, s_i１, s_i２, s_i３, s_i４](s)N[t_i０, t_i１, t_i２, t_i３, t_i４](t)
N[s_i０, s_i１, s_i２, s_i３, s_i４](s)およびN[t_i０, t_i１, t_i２, t_i３, t_i４](t)は、それぞれ、一般形状で次式によって与えられる３次Ｂスプライン基底関数である。

ｕ_ｉは、ノットベクトルのノットであり、ｐは、スプラインの次数を定義する。Ｂ_ｉの計算のために、基底関数式を、短いノットベクトルs_i＝[s_i０, s_i１, s_i２, s_i３, s_i４]およびt_i＝[t_i０, t_i１, t_i２, t_i３, t_i４]を使用して評価しなければならない。このベクトルのそれぞれが、制御点Ｐ_ｉに直接に接続されている。重みｗ_ｉは、自由に選択することができる。すべてのｗ_ｉが1.0である場合に、ＰＢスプライン式は次のように単純になる。

一般的に定義されたＰＢスプラインと対照的に、Ｔスプラインは、制御点の位置に対するある順序を定義する、いわゆるＴメッシュによって構成される。Ｔメッシュの例を、図６に示す。

このメッシュは、制御点Ｐ_ｉに密接に接続されるノットベクトルの定義に重要である。Ｔメッシュが満足しなければならない次の要件が定式化されている。

１．「すべての面の１側面に沿ったすべてのノット間隔（knot interval）の合計は、対向する側面のノット間隔の合計と等しくなければならない」。ノット間隔は、２つのノットの間の差と等しく、したがって、たとえば図６ではｄ_ｉおよびｅ_ｉである。

２．２つのＴ字交差点は、接続の後に新しい面が各対向する側面に等しいノットベクトルの合計を有する場合に限って接続されなければならない（非特許文献８）。

ノットベクトルｓ_ｉおよびｔ_ｉの定義は、ノット間隔に基づき、Ｂスプライン曲面の計算に必要な定義と全く異なる。これは、（非特許文献８）でルール１として示されている。

「パラメータ空間内の光線Ｒ（□）＝（ｓ_ｉ２＋□，ｔ_２）を検討されたい。すると、ｓ_ｉ３およびｓ_ｉ４は、その光線が交差する最初の２つのｓ辺のｓ座標である。ｓ辺とは、定数ｓの垂直線分を意味する。ｓ_ｉおよびｔ_ｉの他のノットは、同様の形で見つかる」。すべてのノットベクトルが判定されたならば、Ｔスプラインを計算することができる。

ノット挿入−ローカル洗練アルゴリズム
Ｔスプラインの主要な利益の１つが、制御点の新しい行または列全体を挿入する必要なしに、Ｔメッシュ内の任意の位置に新しい制御点を挿入する可能性である。Sederberg他は、成功したノット挿入に関するルールおよびアルゴリズムを含む手順を開発した。挿入処理は、トポロジ・フェーズおよびジオメトリ・フェーズと呼ばれる２フェーズで行われる。トポロジ・フェーズでは、追加して挿入されなければならない制御点を識別し、ジオメトリ・フェーズでは、新しいＴメッシュの新しい座標および重みを計算する。

Sederberg他（非特許文献８）は、挿入処理中に発生する可能性があり、追加制御点を挿入することによって訂正されなければならない３つの可能な違反を示した。

「違反１：ブレンディング関数（blending function）が、現在のＴメッシュについてルール１によって指定されるノットを含まない。

違反２：ブレンディング関数が、現在のＴメッシュについてルール１によって指定されていないノットを有する。

違反３：制御点が、それに関連するブレンディング関数を有しない。」
まず、すべての制御点を、より多くの制御が望まれる位置に挿入する。グリッド検査を行い、違反が発生している場合に追加の点を挿入する。すべての違反を解決した後に、新しい座標を、線形変換によって計算する。

本発明による適応表現
Ｔスプラインの概念と進化的最適化の組合せが、本発明のさらなる態様である。

進化的最適化でのＴスプライン
上で既に指摘したように、表現の適応的挙動は、最適化問題に関して非常に重要である。パラメータの個数をできる限り少なく保ち、同時にさまざまな形態設計を保証するように努めなければならない。Ｔスプラインは、設計最適化のこの要件に関する非常によいトレードオフを提供する。一般に、パラメータは、Ｔメッシュの制御点に対してセットされる。したがって、非常に少数の制御点から開始し、最適化の過程で、制御点を任意の位置に追加して、分解能を高めることができる。したがって、この表現を適用することによって、Ｔスプラインの高い柔軟性を使用して、制御点を必要な場所に直接に位置決めして、それまでの最善の設計を保ちながら幾何形態に対する最大の影響を達成することができる。これは、ほとんどの場合に、ごく少数の制御点の追加になるので、パラメータの個数が、できる限り少なく保たれる。これは、非常に良い形で最適化に影響する。

変換のパラメータが変更の自由度を決定するという事実に起因して、パラメータを、選択されたパラメータによって必要な変更を実行できる形でセットしなければならない。どの種類の最適化の場合でも、「必要な変更」は、事前にはわからず、経験に基づいてのみ知られる可能性がある。一般に自由度を高めるために、自由形状変形の場合に制御点の個数を単純に増やすことができる。これは、制御点の影響をよりローカルにし、設計に対するグローバル変更は、さまざまな制御点を同時に変更しなければならないので、実現がより困難になる。さらに、拘束付き変形の場合に、変更の自由と、制御点の個数または行列Ｍの次元の変更による最適化の次元数の間にトレードオフがある。この関係は、スプラインを使用する線または面の表現でも観察することができる。

上で説明したＴスプラインの特性が、その開発の理由である。たとえばＮＵＲＢＳ面スプラインによって面を表現することによって、単一の制御点の追加が、表現によって与えられる拘束を満足するだけのために、追加制御点の行または列全体の追加を必要とする。同一のことが、別の変更された設計への設計の変換を定義する自由形状変形方法に適用された時にもあてはまる。

自由形状変形の既存の方法は、制御点のメッシュを定義することを必要とし、これは、設計の間の変換関数を定義する。この自由形状変形の既存方法に対する拡張が、制御点の自動追加または自動除去である。この方法を用いると、設計の最適化中の変換関数の変更を変更できるようになる。所与の変換関数が、十分に高い自由度をもたらさない場合に、制御点を、制御点の既存の組に追加することができる。この追加に起因して、より高い自由度が、変換関数に存在し、所与の品質尺度に関して設計をさらに改善できるより詳細な変形が可能になる。

スプライン（たとえば、面スプライン）に新しい制御点を導入する時に、所与の面の近似の場合に新しい制御点の最適位置を決定するさまざまな方法が存在する。新しい制御点の最適位置を見つけるためのローカル近似方法およびグローバル近似方法が存在する。しかし、これらの方法は、ローカル品質尺度が存在する場合に限って適用可能である。このローカル品質尺度が存在しない時には、これらの方法を適用することができない。これは、たとえば、表された機体の空気力学特性に基づく品質尺度にあてはまる。たとえば、タービン・ブレードの最適化の場合に、非常にしばしば、圧力損失が、品質尺度として使用される。この圧力損失は、設計の本体全体に依存し、追加制御点を挿入しなければならなくなる前に判定することができない。

この場合に、変換関数の追加パラメータの導入は、表現の追加の突然変異演算子（mutation operator）によって実現することができる。ランダムな制御点が、変換関数を表すスプラインに追加される。この変更された表現が、進化の既知の処理を受ける。追加制御点が、変換関数の前向きの変動を可能にするという意味で有益である場合に限って、これらが、進化の処理中に選択される。したがって、自由形状変形の所与の方法、制御点の導入の方法、および進化的計算の組合せが、自由形状変形に使用される変換関数を実際の最適化の必要に適合させる洗練された優雅な手法をもたらす。

説明された方法によって変更される変換関数としてスプライン関数を使用する既述の方法が、特殊な必要に対する処理中の最適化の自由を高める洗練された優雅な方法である場合であっても、表現の主な短所はまだ存在する。制御点の導入は、表現の拘束を満足するだけのための複数の他の制御点の導入を必要とする。

既に説明したように、Ｔスプラインは、面の表現の場合にこの問題を解決する。ＮｕｒｂｓスプラインではなくＴスプラインを使用すると、その場合の単一の追加制御点の導入が可能になる。

面モデリングと同一の形で、Ｔスプラインの使用は、自由形状変形の制御点追加中の問題を解決することができる。拡張型自由形状変形の場合と同一の形で、新しい制御点の導入を、追加の突然変異演算子によって実現することができる。追加の突然変異演算子は、変換のパラメータの代わりに変換の表現を同一の形で変更する。追加制御点の導入に関して最適の位置の選択を可能にする機構は、既に説明したものと同一である。相違と利益は、この方法が、変換関数のローカル拡張を可能にすることである。

要約すると、説明した方法は、変換関数によって変更される基本設計を使用する設計の既知の表現に基づく。自由形状変形技法の場合に、変換関数は、設計が定義される空間を、新しい変更された設計が定義される第２空間に変換するスプライン関数によって定義される。設計処理中に、スプライン関数のパラメータが、変換関数のパラメータを決定する。進化戦略を使用している間に、スプライン関数のパラメータは、それと同時に、最適化アルゴリズムが働くパラメータを決定する。変換関数を所与の問題および必要な変換に最適に適合させるために、制御点の導入および削除を可能にする突然変異演算子が提案される。進化戦略での標準的な突然変異演算子ではなく、この突然変異演算子は、問題／設計の表現を操作する。

上の方法にあてはまる短所は、基礎になるスプライン記述の使用によって導入される拘束であり、これは、単一のパラメータの導入が多数の点の導入を必要にすることである。この問題に対する解決策は、スプライン曲面の表現に関して説明され、Ｔスプラインと呼ばれる。本明細書で、変換関数としてのこの特殊なスプライン・タイプの超次元拡張を使用することを提案した。この特殊な変換関数のパラメータは、進化的計算の枠組みの中で使用することができ、表現を直接に扱う新しい突然変異演算子によって実際の最適化の特殊な必要に適合させることができる。

拘束変形の原理を示す図であり、２つの異なる変形された２Ｄ曲線を得るために、３Ｄ曲線が、オリジナル２Ｄ曲線から計算され、２回射影されている。 自由形状変形の原理を示す図である。 ＥＦＦＤの原理を示す図であり、任意の制御ボリュームの変位前（左）および変更後（右）の制御点を示す図である。 Ｂスプライン・メッシュおよびＴメッシュの例を示す図である。 Ｔスプライン単純化の例を示す図である。 （左）ブレンディング関数のノット線および（右）Ｔメッシュを示す図である。

Claims (13)

1. 設計を最適化する方法であって、
   前記設計は、変換関数を使用して変更され、前記設計が定義される空間を前記変更された設計が定義される別の空間に変換するスプライン関数によって前記変換関数が定義される自由形状変形が使用されており、
   前記スプライン関数のパラメータは、前記変換関数のパラメータを変更し、
   前記自由形状変形は、進化的計算の表現として使用される、方法。
2. 前記スプライン関数の前記パラメータは、進化的最適化アルゴリズムのパラメータも定義する、請求項１に記載の方法。
3. 前記進化的計算の突然変異演算子は、前記スプライン関数の制御点を導入または削除するために、問題の表現を直接に操作する、請求項１または２に記載の方法。
4. Ｔスプラインが使用される、請求項３に記載の方法。
5. 進化的計算は、進化戦略であり、または
   進化的計算は、遺伝的アルゴリズムである、
   請求項１に記載の方法。
6. 自由形状変形で使用される変換の適合を伴う進化的計算と組み合わされた自由形状変形方法。
7. 進化的計算は、進化戦略であり、または
   進化的計算は、遺伝的アルゴリズムである、
   請求項６に記載の方法。
8. パラメータ適合用の進化的計算と組み合わされた変換としてＴスプラインを使用する自由形状変形方法。
9. 進化的計算は、進化戦略であり、または
   進化的計算は、遺伝的アルゴリズムである、
   請求項８に記載の方法。
10. パラメータ適合用の進化的計算と組み合わされた変換としてのＴスプラインと、さらに点挿入および削除によるＴスプライン構造のオンライン適合と、を使用する自由形状変形方法。
11. 進化的計算は、進化戦略であり、または
    進化的計算は、遺伝的アルゴリズムである、
    請求項１０に記載の方法。
12. 請求項１乃至請求項１１のいずれかに記載の方法を実行する計算手段を含むシステム。
13. 計算デバイスで実行される時に請求項１乃至請求項１２のいずれかに記載の方法を実施するコンピュータプログラム。
    
    

Images