(57)【要約】  ３Ｄプリンタでプリント可能な建築構造の表現を生成する方法において、建築構造の、多面体を含む建築モデルを提供するステップと、前記多面体のうちの少なくとも１つと、サイズがプリンタの性能を表す別の形状とをミンコフスキー加算するステップと、結合された出力多面体を使用して、３Ｄプリンタでプリント可能な建築構造の表現を生成するステップと、を含むことを特徴とする方法。【選択図】図２
2013507679.tif 000002
【特許請求の範囲】
【請求項１】
３Ｄプリンタによりプリント可能な建築構造の表現を生成するコンピュータ化された方法において、
建築構造の、多面体を含む建築モデルを提供するステップと、
プロセッサを使用して、前記多面体のうちの少なくとも１つと、サイズが前記プリンタの性能を表す別の形状とをミンコフスキー加算するステップと、
前記結合された出力多面体を使用して、前記３Ｄプリンタによりプリント可能な前記建築構造の表現を生成するステップと、
を含むことを特徴とする、方法。
【請求項２】
請求項１に記載の方法において、前記ミンコフスキー加算するステップの前に、前記多面体の中からの各非凸多面体を凸多面体に分解するステップも含み、前記ミンコフスキー加算するステップが、少なくとも１つの凸多面体と、サイズが前記プリンタの性能を表す別の形状とをミンコフスキー加算するステップを含むことを特徴とする、方法。
【請求項３】
請求項１に記載の方法において、前記３Ｄプリンタで前記表現をプリントすることも含むことを特徴とする、方法。
【請求項４】
請求項２に記載の方法において、前記分解するステップが、前記多面体の中からの各非凸多面体を三角形以外の凸多面体に分解しようとするステップと、少なくとも１つの個々の非凸多面体への試みに失敗した場合、前記個々の非凸多面体をポリゴンに分解し、前記ポリゴンを結合するステップと、を含むことを特徴とする、方法。
【請求項５】
入力ジオメトリを３Ｄプリント可能モデルに変換するコンピュータ化された３Ｄプリントシステムにおいて、
多面体と単純で小さな凸形状とのミンコフスキー加算を計算し、それにより、３Ｄプリント可能モデルを生成するように動作可能なプロセッサを含むミンコフスキー加算器と、
３Ｄプリント可能モデルを表現する出力を生成するように動作可能な出力生成器と、
を備えることを特徴とする、システム。
【請求項６】
請求項２に記載の方法において、前記少なくとも１つの凸多面体が前記凸多面体のすべてを含むことを特徴とする、方法。
【請求項７】
請求項１又は２に記載の方法において、前記形状が単純で小さな凸形状を含むことを特徴とする、方法。
【請求項８】
請求項７に記載のシステムにおいて、前記形状が立方体を含むことを特徴とする、システム。
【請求項９】
請求項８に記載のシステムにおいて、前記立方体が１ｍｍ×１ｍｍ×１ｍｍの立方体を含むことを特徴とする、システム。
【請求項１０】
コンピュータ可読プログラムコードが具体化されたコンピュータ使用可能媒体を備えるコンピュータプログラム製品において、前記コンピュータ可読プログラムコードが、実行されて、３Ｄプリンタでプリント可能な建築構造の表現を生成する方法を実施するように構成され、前記方法が、
建築構造の、多面体を含む建築モデルを提供するステップと、
前記多面体のうちの少なくとも１つと、サイズが前記プリンタの性能を表す別の形状とをミンコフスキー加算するステップと、
前記結合された出力多面体を使用して、前記３Ｄプリンタでプリント可能な建築構造の表現を生成するステップと、
を含むことを特徴とする、コンピュータプログラム製品。
【請求項１１】
請求項４に記載の方法において、前記ポリゴンのうちの少なくともいくつかが三角形であることを特徴とする、方法。
【請求項１２】
請求項１又は２に記載の方法において、前記ミンコフスキー加算により生成されるミンコスフスキー和のうちの少なくともいくつかを結合し、それにより、少なくとも１つの結合出力多面体を生成するステップも含むことを特徴とする、方法。
【請求項１３】
請求項１２に記載の方法において、分解の結果である凸多面体の各集合のミンコフスキー和のみが結合されることを特徴とする、方法。
【請求項１４】
３Ｄプリントのために建築モデルを準備するシステムにおいて、少なくとも１つのミンコフスキー加算計算を使用して、前記建築モデルを修復する修復器を備えることを特徴とする、システム。
【請求項１５】
請求項８に記載のシステムにおいて、前記修復が前記モデルの少なくとも１つの小さなギャップを修復することを含むことを特徴とする、システム。
【請求項１６】
請求項８に記載のシステムにおいて、修復が少なくとも１つの欠落面を修復することを含むことを特徴とする、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
同時係属中の出願の参照
優先権は、２００９年１０月８日に出願された「Ｍｅｔｈｏｄ  ａｎｄ  Ｓｙｓｔｅｍ  ｆｏｒ  ｅｎａｂｌｉｎｇ  ｔｈｒｅｅ−ｄｉｍｅｎｓｉｏｎａｌ  ｏｂｊｅｃｔ  ｍｏｄｅｌｓ」という名称の米国特許出願第１２／５７５，９１９号明細書の優先権を主張するものである。
【０００２】
本発明は、一般的には３Ｄプリントに関し、より詳細には３Ｄモデルの処理に関する。
【背景技術】
【０００３】
以下の用語は、従来技術による文献に見られる任意の定義に従って、又は本明細書に従って、すなわち、以下のように解釈することができる。
凸包：ｃｏｎｖ（Ｓ）として示される、三次元空間Ｓ⊆Ｒ３における幾何学的物体の集合の凸包は、Ｓを含む最小の（包含的な）凸集合である。
凸多面体：凸多面体は、有限個の閉半空間Ｈ＝｛ｈ∈Ｒ３｜Ａ・ｈ≦Ｂ｝の交じわりとして与えられる凸集合Ｑ⊆Ｒ３であり、式中、Ａ・ｈ≦Ｂは一次式系である。ｎが定義半空間の個数であると仮定する場合、Ａは｛３×ｎ｝行列であり、Ｂは長さｎのベクトルであり、ｈは、凸多面体内に含まれる点を表す変数である。
多面体：有界の凸多面体Ｐ⊂Ｒ３が多面体である。
超平面：三次元空間において、超平面は通常の平面であり、空間を２つの半空間に分ける。
支持超平面：超平面は、Ｓが全体的に、超平面により決まる２つの閉半空間のうちの一方内に含まれ、Ｓが超平面上に少なくとも１つの点を有する場合、ユークリッド空間Ｒ３内の集合Ｓを支持する。閉半空間は、超平面を含む半空間である。
幅：ｗｉｄｔｈ（Ｓ）として示される集合Ｓ⊆Ｒ３の幅は、ｃｏｎｖ（Ｓ）を支持する平行超平面間の最小距離である。
方向幅：正規化ベクトルｖを考えると、ｗｉｄｔｈｖ（Ｓ）として示される方向幅は、ｃｏｎｖ（Ｓ）を支持し、ｖに直交する平行超平面間の距離である。
ポリゴンメッシュ：ポリゴンメッシュは、非構造格子とも呼ばれ、例えば、３Ｄ（三次元）コンピュータグラフィックス及びソリッドモデリングにおいて多面体物体の形状を定義する頂点、辺、及び面の集まりである。面は通常、レンダリングを簡易化するために、三角形、四辺形、又は他の凸ポリゴンからなるが、より一般的な凹ポリゴン、穴を有するポリゴン等で構成されてもよい。一般に、入力は、幾何学的物体の付随関係を取り出せるように、幾何学的情報及び十分な位相幾何学的情報を含むべきである。
ＳＴＬ：ＳＴＬは、米国に所在の企業「３Ｄ  Ｓｙｓｔｅｍｓ（登録商標）」により制作されるステレオリソグラフィＣＡＤ（コンピュータ支援設計）ソフトウェアに固有のファイル形式である。このファイル形式は、他の多くのソフトウェアパッケージによりサポートされ、ラピットプロトタイピング及びコンピュータ支援製造に広く使用されている。ＳＴＬファイルは、色、テクスチャ、又は他の一般的なＣＡＤモデル属性の表現のない三次元物体の表面のジオメトリを記述する。ＳＴＬ形式は、ＡＳＣＩＩ（情報交換用米国標準コード）及びバイナリ表現の両方を指定する。一般に、通常、バイナリファイルがよりコンパクトであるため、バイナリファイルがより一般である。一般に、各ＳＴＬファイルは、三次元デカルト座標系を使用して三角形の単位法線及び頂点（右手の法則による順）により未処理の非構造三角形からなる表面も記述する。ＶＲＭＬ等の他のファイル形式が、テクスチャ及び色をサポートする。
３Ｄ（三次元）プリント：は、従来のラピットプロトタイピング技術に関連する独自の形態のプリントである。３Ｄ物体は、材料の連続した断面を層化し、結び付けることにより作成される。３Ｄプリンタは通常、他の積層造形技術よりも高速であり、手頃であり、且つ使用が容易である。プリンタの分解能は層厚で与えられ、ＸＹ分解能はＤＰＩ（ドット数／インチ）で与えられる。通常、層厚は約１００μｍ（０．１［ｍｍ］（ミリメートル））であり、ＸＹ分解能はレーザプリンタの分解能と同等である。粒子（３Ｄドット）は直径約５０μｍ〜１００μｍ（０．０５ｍｍ〜０．１ｍｍ）である。
ラピット：「ラピット」という用語は、現方法を使用したモデルの構築が、使用される方法並びにモデルのサイズ及び複雑性に応じて、例えば、数時間から数日かかり得るため、相対的である。ラピットプロトタイピング用の積層システムは通常、モデルを数時間で生成することができるが、使用される機械のタイプ並びに同時に生成されるモデルのサイズ及び数に応じて大きく変化し得る。
プリント可能モデル：モデルは、内部で対毎に交差しないボリュームを結合する閉２Ｄ（二次元）多様体の集合を含むと共に、あらゆる凸片のＺ方向（垂直）幅が所与の閾値よりも大きく、あらゆる凸片のＸＹ方向（水平）幅が所与の閾値を超える（Ｘ、Ｙ、及びＺは軸である）ような凸分解も存在する場合、プリント可能である。実際には、３Ｄプリント可能モデルは、３Ｄプリンタでプリント可能なモデルである。したがって、モデルは、上記の第１の定義、例えば、交差するボリュームに従わない場合であっても３Ｄプリント可能であり得る。
【０００４】
３Ｄプリントは急速に成長しつつある市場であり、２０１１年までに３Ｄプリンタが３００，０００台になると推定される。３Ｄ建築モデルの現在の作成は通常、手動で実行される。これは遅く、高価であり、経験を要する（通常、専門的なサービス提供者による）労働集約的なプロセスである。
【０００５】
例えば、ｒａｐｉｄｔｏｄａｙ．ｃｏｍにおいてオンラインで入手可能な「Ｄｅｓｐｉｔｅ  Ｈｏｕｓｉｎｇ  Ｗｏｅｓ，Ａｒｃｈｉｔｅｃｔｕｒａｌ  ３Ｄ  Ｐｒｉｎｔｉｎｇ  Ｔｈｒｉｖｅｓ」という名称のＲａｐｉｄＴｏｄａｙの記事は、「ＲａｐｉｄＴｏｄａｙが話したサービス提供者のうち、略全員が、図面ファイルを３Ｄプリント可能にするために、広範囲にわたるファイルの修復が必要であることが多かったと述べた。ＱｕｉｃｋＡＲＣのＭａｃｋｉｅは総コストの２０％、すなわち、構築される典型的なＵＳ＄３，０００モデルのＵＳ＄６００と見積もられ・・・。修復が容易でないのは、容易に見えない場合があるが、ラピットプロトタイピングを短絡させる建築ＣＡＤファイルでのギャップ及び穴である。これらの問題は現在、ＤｅｓｋＡｒｔｅｓからのＭａｇｉｃｓ、ＶｉｓＣａｍＲＰ、ＭｅｓｈＷｏｒｋｓ、３Ｄａｔａ  Ｅｘｐｅｒｔ・・・のようなメッシュ修復プログラムを使用して、ラピットプロトタイピングサービス提供者の専門家が苦心して発見し修復している。この問題に対する高速ソフトウェアによる解決は遠い。」と述べている。
【０００６】
この１０年間で、３Ｄプリンタは、コンピュータ支援設計（ＣＡＤ）モデル及びアニメーションモデル等のデジタルデータから３Ｄの物理物体を生成する一般的なツールになった。その結果、ラピットプロトタイピングの使用は今では、多くの分野で一般的である。特に、建築家は３Ｄプリントから大きな恩恵を受け得る。建築家は、数日さらには数ヶ月ではなく数時間以内で正確な３Ｄ建築物体を生成することができる。これらのプロトタイプは、進行中に建築プロジェクトを繰り返し再評価するための自然なメカニズム及び早い段階での問題の検出を可能にする。今では、３Ｄプリントは、速度、低コスト、及び使用のし易さに関して最適化することができ、プロトタイプの正確性及び機械的強度があまり重要ではない場合、工学設計の概念的な段階中の検査に適する。
【０００７】
国際的な「Ｚ  Ｃｏｒｐｏｒａｔｉｏｎ（登録商標）」、イスラエルの「Ｏｂｊｅｃｔ  Ｇｅｏｍｅｔｒｉｅｓ（登録商標）」、並びに米国に所在の「３Ｄ  Ｓｙｓｔｅｍｓ（登録商標）」企業及び「Ｓｔｒａｔａｓｙｓ（登録商標）」企業等の多くの周知のファームが、３Ｄ物理物体を生成する装置を製造している。これらの様々な装置は、いくつかの異なる競合する技術に基づく。明らかなことに、異なる製造業者により生成される３Ｄプリンタ及び同じ製造業者により生成される異なるモデルは、異なる特徴を呈し、別様に動作し、通常、異なる制限に制約される。しかし、すべてではないにせよ大半の３Ｄプリンタは、積層製造技術に基づき、積層製造技術は、図１に概略的に示されるように、製造すべきモデルを比較的薄い水平断面１０５に変形し、それから、製造が完成するまで連続した層１０６、１０７等を作成する。様々な３Ｄプリンタの違いの１つは、層が構築されて、プリントすべき３Ｄモデルのパーツを作成する方法である。分解能は通常、層厚で与えられ、ＸＹ分解能はドット数／インチ（ＤＰＩ）で与えられる。通常、層厚は約１／１００μｍ（０．１ｍｍ）であり、ＸＹ分解能はレーザプリンタの分解能と同等である。粒子（３Ｄドット）は直径約１／５０μｍ〜１／１００μｍ（０．０５ｍｍ〜０．１ｍｍ）である。
【０００８】
従来の３Ｄプリンタは、有効なプリント可能モデルが供給された場合のみ、正確な３Ｄ物理物体を生成することができる。そのようなモデルは、例えば、ＳＴＬ（ステレオリソグラフィ）ファイル形式でポリゴンメッシュとして表現される。ポリゴンメッシュとして表現される有効モデルは、閉２Ｄ多様体、すなわち、自己交差等のアーチファクトを略有さない水密物体を表すポリゴンスープ（ポリゴンの任意の集合）又は互いに略交差しない閉２Ｄ多様体の集まりを含む。有効なプリント可能モデルは、様々なプリント装置により科される追加要件を満たす（異なるプリント装置は、異なる技術に基づくため、異なる要件を課す）。
【０００９】
３Ｄ物体の正確で一貫した表現が、モデリング、シミュレーション、視覚化、ＣＡＤ（コンピュータ支援設計）、ＣＡＭ（コンピュータ支援製造）、有限要素解析等の従来の用途により求められる。しかし、取得される３Ｄモデルは通常、手で作成されたにせよ、又は自動ツールで作成されたにせよ、エラー及び非一貫性を含む。例えば、モデルは、誤って方向付けられ、交差、又は重複するポリゴン、亀裂、及びＴ字形接合部を含み得、加えて、ポリゴンが欠け、位相幾何学的情報が一貫しないことがある。問題は、設計者のエラー又はモデリングツールのソフトウェアエラーによる。これらのエラーは、（ｉ）ＣＡＤ形式（例えば、ＩＧＥＳ（初期グラフィックス交換仕様）、ＳＴＥＰ（製品モデルデータ交換規格）、ＤＸＦ（図面相互交換形式）、ＣＡＴＩＡ（コンピュータ支援三次元インタラクティブアプリケーション）又はＡｕｔｏＣＡＤからのバイナリファイル）間、Ｂ−Ｓｐｌｉｎｅ又はＮＵＲＢＳベース（非均一関係Ｂ−Ｓｐｌｉｎｅ）形式間の自動転送、（ｉｉ）工学解析システム（例えば、三角形表面メッシュ）への幾何学的変形等のデータ交換問題により悪化する。取得された３Ｄモデルから多様体モデルを再構築する技法は、効率、ロバスト性、自動化のレベル、事前条件等に従って様々である。自動化のレベルは、必要とされるユーザ入力に関して測定される。事前条件は、（ｉ）入力集合内のポリゴンが一貫した向きであり、（ｉｉ）入力パーツが閉２Ｄ多様体である等であるがこれらに限定されない要件を含む。従来技術による一手法によれば、シーンに関連する許容性が、いくらかの許容差内でモデル内の亀裂を「充填」するか、又は特徴を結合するために使用される。境界に基づく手法等の他の手法は、入力ポリゴンメッシュがどのように一緒であるかのソリッド構造を推論しようとし、非多様体ジオメトリが存在する場合、不正確に実行する可能性が高い。従来技術によれば、すべての手法は、エラーのサイズがモデルの最小特徴よりも大きい場合、上手く機能しない。劣化した入力が実際用途では一般的であり、数値エラーは不可避であるため、この問題を考慮せずに実施されるアルゴリズムは、不正確な結果をもたらし得、劣化又は略劣化した入力で実行される間、無限ループ又は単にクラッシュし得る（例えば、「Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｇｅｏｍｅｔｒｙ：Ｔｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ」，ｖｏｌｕｍｅ  ４０，ｐａｇｅｓ  ６１−７８，２００８において公表された「Ｃｌａｓｓｒｏｏｍ  ｅｘａｍｐｌｅｓ  ｏｆ  ｒｏｂｕｓｔｎｅｓｓ  ｐｒｏｂｌｅｍｓ  ｉｎ  ｇｅｏｍｅｔｒｉｃ  ｃｏｍｐｕｔａｔｉｏｎｓ」という名称の記事においてＬｕｔｚ  Ｋｅｔｔｎｅｒ等により提示されるように、又はＳｔｅｆａｎ  Ｓｃｈｉｒｒａ，「Ｒｏｂｕｓｔｎｅｓｓ  ａｎｄ  ｐｒｅｃｉｓｉｏｎ  ｉｓｓｕｅｓ  ｉｎ  ｇｅｏｍｅｔｒｉｃ  ｃｏｍｐｕｔａｔｉｏｎ」，「Ｈａｎｄｂｏｏｋ  ｏｆ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｇｅｏｍｅｔｒｙ」（Ｊｏｒｇ−Ｒｕｄｉｇｅｒ  Ｓａｃｋ  ａｎｄ  Ｊｏｒｇｅ  Ｕｒｒｕｔｉａ，ｅｄｉｔｏｒｓ），ｃｈａｐｔｅｒ  １４，ｐａｇｅｓ  ５９７−６３２，Ｅｌｓｅｖｉｅｒ  Ｓｃｉｅｎｃｅ  Ｐｕｂｌｉｓｈｅｒｓ，２０００���により提示されるように）。
【００１０】
従来技術によれば、建築家はＣＡＤソフトウェア（例えば、米国に所在のＡｕｔｏＤｅｓｋ（登録商標）により開発されたＡｕｔｏＣＡＤ（登録商標）及びＲｅｖｉｔ（登録商標）、Ｇｏｏｇｌｅ  ＳｋｅｔｃｈＵｐ）を使用して、様々な３Ｄデジタルモデルを生成する。これらのモデルは、壁、階段、屋根等の建築パーツを含み得る。各パーツを表すデータは、破損し得るか、又は非一貫性を含み得る。データが完全な場合であっても、個々の各パーツは、不十分な厚さであり得るか、又は重力に打ち勝って空中に浮き得るため、３Ｄプリントに適さないことがある。最後に、一緒に組み合わせられたすべてのパーツが、互いに交差、特異点を含むため、３Ｄプリントに適さないことがある。
【００１１】
ＣＡＤソフトウェアは、約３０年前の発足以来、常に進化してきた。商用３Ｄ  ＣＡＤ技術は、ＳｏｌｉｄＷｏｒｋｓ（登録商標）、Ｉｎｖｅｎｔｏｒ（登録商標）、ＰＴＣ（登録商標）、ＳｏｌｉｄＥｄｇｅ（登録商標）、並びに３Ｄ空間での解析性能及び設計性能に改良を提供する多くの他の製品等の工学ソフトウェア設計と共に出現した。ラピットプロトタイピングの最初の技法は、１９８０年代後半に提供され、３Ｄ  ＣＡＤソフトウェア設計により生成される実際の有形モデルをもたらすために、すぐ後に商用３Ｄプリンタが続いた。今日、これらは多くの分野で普遍であり、広範囲の用途に使用され、比較的少数での生産品質パーツの製造にさえも使用されている。彫刻家によっては、この技術を使用して、美術品展示のために複雑な形状を生成する者もいる。それでもやはり、ソフトウェア入力の品質は比較的満足のいかないものである。３Ｄプリンタへの入力データがいくつかのエラーを含み得ることは、Ｍａｔｅｒｉａｌｉｓｅ（登録商標）、Ｍａｒｃａｍ（登録商標）、及びＤｅｓｋａｒｔｅｓ（登録商標）等のＣＡＤ後の診断及び修復ソフトウェアの開発に繋がった。
【００１２】
３Ｄプリントの問題は従来技術において認識されており、様々な解決策が提案されてきた。例えば、米国特許第２００５／０３８５４９号明細書には、ラピットプロトタイピング構築ファイルの適応変更を実行するシステム及び方法が開示されている。この方法は、三次元物体のデジタル記述を記憶したラピットプロトタイピング構築ファイルを読み取るステップを含む。記述は、複数の構築ファイル修正アルゴリズムから構築ファイル修正アルゴリズムを選択する動作も含む。別の例では、米国特許第５，７０５，１１７号明細書は、プロトタイプパーツを生成するステレオリソグラフィプロセスを提示し、このプロセスでは、非光重合材料のインサートが、結果として生成されるパーツ内に含められて、機能するプロトタイプパーツを生成する。インサートを生成されるプロトタイプパーツ内に配置することができるように、一連のＳＴＬファイルが、個々の断面でのプロトタイプパーツを形成するために定義される。非光重合インサートは、断面が形成される都度、生成されるパーツの一断面に手動で位置決めされる。
【００１３】
加えて、米国特許第７，３４３，２１６号明細書は、モデルへの群葉の繰り返しの配置及び取り出しに役立つ建築現場モデルを組み立てる方法を提示する。現場モデルは、上位シェル部分及び下位シェル部分として構築され、モデルの群葉はシェルパーツに取り付けられる。現場モデルの上位シェル部分は、下の基礎部分に取り外し可能に取り付けられるように構成される。したがって、現場モデルからのシェルの取り外しによっても、現場モデルから群葉を一動作で取り外すことができる。さらに、日本国特許第１１３３９０７０号明細書は、サブファイル内のソリッドサブモデルをサーフェス処理し、メインファイルに取り入れ、メインソリッドモデルと結合することにより、サーフェスモデルを生成する方法を提示する。このために、部分的な切断、メインソリッドモデルの投影追加等の変更動作が実行される。
【発明の概要】
【００１４】
上記観察に基づいて、当分野には、ポリゴンメッシュ（例えば、非多様体メッシュ、交差する三角形、Ｔ字形接続部を有するメッシュ等）として表現される破損及び非一貫性を有し得るモデルを比較的大きなプリント装置セットに使用される有効なプリント可能モデルに変形することができる方法及びシステムを提供する持続した必要性がある。
【００１５】
当分野には、破損又は非一貫性を有し得る３Ｄ物体デジタルモデルを、ラピットプロトタイピング（ＲＰ）とも呼ばれるプロセスである固体自由造形（ＳＦＦ）を使用することにより自動的に構築することができる物理物体モデルに変形することができる方法及びシステムを提供する持続した必要性もある。
【００１６】
ラピットプロトタイピングソフトウェアのベンダーとしては、Ｍａｔｅｒｉａｌｉｓｅ、Ｄｅｓｋａｒｔｅｓ、Ｍａｒｃａｍ  Ｅｎｇｉｎｅｅｒｉｎｇ、Ｋｘｉｎｃ、及びＣＡＤｓｐａｎが挙げられる。
【００１７】
加えて、当分野には、建物及び景観等の建築分野に見られるモデル並びに科学的視覚化及び物理的シミュレーション等の他の多くの分野に見られるモデルの処理が可能な方法及びシステムを提供することが必要である。さらに、当分野には、破損したモデルを修復し、３Ｄプリント、組み立て計画等の様々なプロセスの非一貫性をなくすように構成された方法及びシステムを提供する必要がある。さらに、当分野には、薄いパーツを、その機能を保ちながら厚化する動作が可能であり、存在し得る交差及び特異点をなくし、すべてのパーツを、１つ又は複数の閉２Ｄ多様体を含む、アーチファクトが略ない単一のプリント可能モデルに統合する方法及びシステムを提供する必要がある。
【００１８】
本明細書において言及されるすべての公開文献及び特許文献並びにそれらの文献内で直接又は間接的に引用される公開文献及び特許文献の開示は、参照により本明細書に援用される。
【００１９】
本発明の特定の実施形態は、３Ｄ（三次元）デジタル物体モデルを、主に建築用途であるが、それに限定されない３Ｄプリンタに有効な３Ｄプリント可能形態に変換する方法及びシステムを提供しようとする。
【００２０】
本発明の特定の実施形態は、（建築家、技師、及び建設）ユーザが３Ｄモデルプリント技術を完全に利用できるようにする技術を提供しようとする。
【００２１】
現在のソフトウェア（Ａｕｔｏｄｅｓｋ  Ｒｅｖｉｔ、ＳｋｅｔｃｈＵｐ等）を３Ｄプリンタと共に使用して３Ｄ設計モデルをプリントしようとする場合、設計から正確な建築３Ｄモデルを生成するには、手動での修正が必要である。これは、スケール問題、異なる設計ソフトウェア及び３Ｄプリンタの異なるタイプ間の互換性の結果である。
【００２２】
本発明の特定の実施形態は、エラーのない正確で精密にスケーリングされたサイズ変更可能な３Ｄモデルを、使用される３Ｄ設計ソフトウェア及び３Ｄプリンタに関係なく、キーに触れるだけで自動的に提供しようとする。
【００２３】
本発明の特定の実施形態は、既存の３Ｄ設計を、３Ｄプリンタによる使用に対応するＳＴＬ形式又は他の適した形式に変換するように動作可能な方法において、モデルプロトタイプ形成で節減される時間が、モデル毎に数週間から週時間に大幅に低減する、方法を提供しようとする。
【００２４】
本発明の特定の実施形態は、価格制約及びプリンタ制限により設計毎に１つのモデルが作成されることに代えて、望みに応じて同じモデルの多くのコピーを作成する能力及び／又は異なるスケールでモデルをプリントする能力を提供しようとする。
【００２５】
本発明の特定の実施形態は、従来の３Ｄモデリングは高い計算能力を必要とする動作であるため、例えば、クラウド計算を使用して、建築家、３Ｄプリントサービス提供者、及び３Ｄプリンタ製造業者を結び付け、それにより、計算能力を可能にするようとする。
【００２６】
入力ファイル形式は、例えば、Ａｕｔｏｄｅｓｋ  Ｒｅｖｉｔ、Ｇｏｏｇｌｅ  Ｓｋｅｔｃｈｕｐ、ＡｕｔｏＣＡＤ  ＤＸＦ／ＤＷＧ、ＶＲＭＬ、ＳＴＬのうちの任意又はすべてを含み得る。
【００２７】
編集は、例えば、分割、セクション／ステージ、簡略化（ポリゴン低減）、分離（シェル、材料）のうちの任意又はすべてを含み得る。
【００２８】
出力は３Ｄプリント可能モデル（例えば、ＳＴＬ、複数材料）を含み得る。
【００２９】
プロセスは、修復、選択（インタラクティブ）、厚化、及び結合（プリント可能なＳＴＬ）を含み得る。
【００３０】
本発明の特定の実施形態は、建築家に利点を提供しようとし、例えば、現在の３Ｄモデルプリントプロセスとは対照的に、好ましくは、計画された設計を顧客に示す能力を提供し、様々な設計代替を調べることができ、顧客との良好な視覚的やりとりを提供し、計画を保存し、顧客からの即時フィードバックが可能であり、建築家がプロセスを完全に制御できるようにし、同じモデルのコピー及び／又は同じモデルの異なるサイズのプリントを作成する１つ又は複数のシステムを提供しようとする。
【００３１】
建築家は、モデルを３Ｄソフトウェアからウェブサイトにアップロードすることができ、又はプロセスをクラウド計算で実行することができる。
【００３２】
本明細書に示され説明される一方法によれば、以下の動作のうちのいくつか又はすべてが実行される：
ａ．例えば、ストレートスケルトン、中心軸、又は代替の方法を使用して多面体の３Ｄスケルトンを見つけるステップ、
ｂ．
2013507679.tif 000003
スケルトンキューブのミンコフスキー加算を計算するステップであって、この和は、本明細書では「膨張スケルトン」とも呼ばれる、計算するステップ、及び
ｃ．元の多面体と膨張スケルトンとの和を計算するステップ。
【００３３】
特定の実施形態の特定の利点は、既存のエンティティの厚さがすでに所定の最小厚よりも大きい場合、本明細書に示され説明される方法により厚化されないことである。
【００３４】
したがって、特定の実施形態によれば、１つ又は複数の３Ｄ物体の非一貫性３Ｄ（三次元）モデルを有効なプリント可能３Ｄモデルに変形する方法において、
ａ）入力モデルファイル及び／又はモデラーデータを受信して、１つ又は複数のパーツを有する入力３Ｄモデルを生成するステップと、
ｂ）入力３Ｄモデルを解析し、１つ又は複数の非一貫性をなくすステップと、
ｃ）３Ｄモデルの１つ又は複数のパーツを、その機能を保ちながら厚化させるステップと、
ｄ）１つ又は複数のパーツの内積の和を統合し、それにより、自己交差及び／又は２つ以上のパーツの交差をなくし、有効なプリント可能３Ｄモデルを生成するステップと、
を含む、方法が提供される。
【００３５】
本発明の実施形態によれば、方法は、入力モデルファイル及び／又はモデラーデータをインポートするステップをさらに含む。
【００３６】
本発明のさらなる実施形態によれば、インポートするステップは、以下のうちの１つ又は複数をさらに含む：
ａ）入力モデルファイルをパーズするステップ、及び
ｂ）モデリングアプリケーションからモデラーデータを得るステップ。
【００３７】
本発明のさらに別の実施形態によれば、方法は、１つ又は複数の事前定義される基準に従って３Ｄモデルをスケーリング又はクリッピングするステップをさらに含む。本発明のさらに別の実施形態によれば、スケーリングするステップは、自動的に実行されて、３Ｄプリンタにより定義される境界ボックスを修復する。
【００３８】
本発明のさらに別の実施形態によれば、スケーリングするステップは、ユーザにより提供される事前定義されるスケーリング係数に基づいて手動で実行される。
【００３９】
本発明のさらに別の実施形態によれば、方法は、閲覧者がＧＵＩ（グラフィカルユーザインタフェース）を使用して方法の各ステップを制御するステップをさらに含む。
【００４０】
本発明のさらに別の実施形態によれば、方法は、２つ以上の分離したモデルパーツを接続し、単一の接続された３Ｄモデルを形成する物理的解析に基づいて、３Ｄモデルを変更するステップをさらに含む。
【００４１】
本発明のさらなる実施形態によれば、方法は、３Ｄモデルを１つ又は複数の分離したサブモデルに分割するステップをさらに含む。
【００４２】
本発明のさらなる実施形態によれば、方法は、略独立してプリントすべき少なくとも１つの分離したサブモデルを選択するステップをさらに含む。
【００４３】
本発明のさらなる実施形態によれば、方法は、３Ｄモデルから１つ又は複数の特異点をなくすステップをさらに含む。
【００４４】
本発明の実施形態によれば、厚化するステップは、以下のうちの１つ又は複数をさらに含む：
ａ）垂直に厚化するステップ、及び
ｂ）水平に厚化するステップ。
【００４５】
本発明の別の実施形態によれば、厚化するステップは、
ａ）３Ｄモデルが凸サブパーツを有するか否かを判断し、有さない場合、３Ｄモデルのパーツを凸サブパーツに分解するステップと、
ｂ）各サブパーツの幅を計算するステップと、
ｃ）垂直幅が第１の事前定義される値よりも小さい対応するサブパーツを垂直方向に沿って厚化させ、水平幅が第２の事前定義される値よりも小さい対応するサブパーツを水平方向に沿って厚化させるステップと、
をさらに含む。本発明のさらに別の実施形態によれば、３Ｄプリントすべき３Ｄモデルをエクスポートするステップをさらに含む。
【００４６】
本発明のさらに別の実施形態によれば、エクスポートするステップは、以下のうちの１つ又は複数をさらに含む：
ａ）サポートされるファイル形式でモデルを表す出力モデルファイルに３Ｄモデルを記憶するステップ、及び
ｂ）３Ｄモデルを３Ｄプリンタに送信するステップ。
【００４７】
本発明のさらに別の実施形態によれば、出力モデルファイルは、３Ｄプリントに使用すべきＳＴＬ（ステレオリソグラフィ）ファイルである。
【００４８】
システムは、１つ又は複数の３Ｄ物体の非一貫性３Ｄ（三次元）モデルを有効なプリント可能３Ｄモデルに変形するように構成され、
ａ）データ記憶装置から提供される入力モデルファイル及び／又はモデラーデータと、
ｂ）サブシステムであって、
ｂ．１  データ記憶装置から提供される入力モデルファイル及び／又はモデラーデータを受信して、１つ又は複数のパーツを有する入力３Ｄモデルを生成し、
ｂ．２  入力３Ｄモデルを解析し、１つ又は複数の非一貫性をなくし、
ｂ．３  ３Ｄモデルの１つ又は複数のパーツを、その機能を保ちながら厚化させ、
ｂ．４  １つ又は複数のパーツの内積の和を統合し、それにより、自己交差及び／又は２つ以上のパーツの交差をなくし、それにより、有効なプリント可能３Ｄモデルを生成する
ように構成される、サブシステムと、
ｃ）有効なプリント可能３Ｄモデルをプリントする３Ｄプリンタと、
を備える。
【００４９】
機械により実行可能であり、１つ又は複数の３Ｄ物体の非一貫性３Ｄ（三次元）モデルを有効なプリント可能３Ｄモデルに変換する命令のプログラムを明確に具体化する機械可読のプログラム記憶装置であって、方法は、
ａ）入力モデルファイル及び／又はモデラーデータを受信して、１つ又は複数のパーツを有する入力３Ｄモデルを生成するステップと、
ｂ）入力３Ｄモデルを解析し、１つ又は複数の非一貫性をなくすステップと、
ｃ）３Ｄモデルの１つ又は複数のパーツを、その機能を保ちながら厚化させるステップと、
ｄ）１つ又は複数のパーツの内積の和を統合し、それにより、自己交差及び／又は２つ以上のパーツの交差をなくし、有効なプリント可能３Ｄモデルを生成するステップと、
を含む、プログラム記憶装置。
【００５０】
本発明の特定の実施形態によれば、３Ｄプリンタでプリント可能な建築構造の表現を生成するコンピュータ化された方法も提供され、この方法は、建築構造の多面体を含む建築モデルを提供するステップと、プロセッサを使用して、多面体のうちの少なくとも１つと、サイズがプリンタの性能を表す別の形状とをミンコフスキー加算するステップと、結合された出力多面体を使用して、３Ｄプリンタでプリント可能な建築構造の表現を生成するステップと、を含む。
【００５１】
さらに、本発明の特定の実施形態によれば、方法は、ミンコフスキー加算するステップの前に、多面体の中からの各非凸多面体を凸多面体に分解するステップを含み、ミンコフスキー加算するステップは、少なくとも１つの凸多面体と、サイズがプリンタの性能を表す別の形状とをミンコフスキー加算するステップを含む。
【００５２】
さらに本発明の特定の実施形態によれば、方法は、３Ｄプリンタで表現をプリントするステップも含む。
【００５３】
さらに本発明の特定の実施形態によれば、分解するステップは、多面体の中からの各非凸多面体を三角形以外の凸多面体に分解するステップと、少なくとも１つの個々の非凸多面体への試みに失敗した場合、個々の非凸多面体をポリゴンに分解し、ポリゴンを結合するステップと、を含む。
【００５４】
本発明の特定の実施形態によれば、入力ジオメトリを３Ｄプリント可能モデルに変換するコンピュータ化された３Ｄプリントシステムも提供され、このシステムは、多面体と単純で小さな凸形状とのミンコフスキー和を計算し、それにより、３Ｄプリント可能モデルを生成するように動作可能なプロセッサを含むミンコフスキー加算器と、３Ｄプリント可能モデルを表現する出力を生成するように動作可能な出力生成器と、を備える。
【００５５】
さらに本発明の特定の実施形態によれば、少なくとも１つの凸多面体は凸多面体のすべてを含む。
【００５６】
さらに本発明の特定の実施形態によれば、上記形状は単純で小さな凸形状を含む。
【００５７】
さらに本発明の特定の実施形態によれば、上記形状は立方体を含む。
【００５８】
さらに本発明の特定の実施形態によれば、上記立方体は、例えば、１ｍｍ×１ｍｍ×１ｍｍの立方体を含む。
【００５９】
本発明の特定の実施形態によれば、コンピュータ可読プログラムコードが内部に具体化されたコンピュータ使用可能媒体を備えるコンピュータプログラム製品も提供され、コンピュータ可読プログラムコードは、実行されて、３Ｄプリンタでプリント可能な建築構造の表現を生成する方法を実施するように構成され、方法は、建築構造の、多面体を含む建築モデルを提供するステップと、多面体のうちの少なくとも１つと、サイズがプリンタの性能を表す別の形状とをミンコフスキー加算するステップと、結合された出力多面体を使用して、３Ｄプリンタでプリント可能な建築構造の表現を生成するステップと、を含む。
【００６０】
さらに本発明の特定の実施形態によれば、ポリゴンのうちの少なくともいくつかは三角形である。
【００６１】
さらに本発明の特定の実施形態によれば、方法は、ミンコフスキー加算により生成されるミンコスフスキー和のうちの少なくともいくつかを結合し、それにより、少なくとも１つの結合出力多面体を生成するステップも含む。
【００６２】
さらに本発明の特定の実施形態によれば、分解の結果である凸多面体の各集合のミンコフスキー和のみが結合される。
【００６３】
本発明の特定の実施形態によれば、３Ｄプリントのために建築モデルを準備するシステムも提供され、このシステムは、少なくとも１つのミンコフスキー和計算を使用して、建築モデルを修復する修復器を備える。
【００６４】
さらに本発明の特定の実施形態によれば、修復はモデルの少なくとも１つの小さなギャップを修復することを含む。
【００６５】
さらに本発明の特定の実施形態によれば、修復は少なくとも１つの欠落面を修復することを含む。
【００６６】
コンピュータ可読プログラムコードが内部に具体化された、通常は有形のコンピュータ使用可能媒体又はコンピュータ可読記憶媒体を備えるコンピュータプログラム製品も提供され、コンピュータ可読プログラムコードは、実行されて、本明細書に示され説明される方法のうちの任意又はすべてを実施するように構成される。本明細書に示され説明される計算ステップのうちの任意又はすべてをコンピュータで実施し得ることが理解される。本明細書における教示による動作は、所望の目的のために特別に構築されたコンピュータ又はコンピュータ可読記憶媒体に記憶されたコンピュータプログラムにより所望の目的のために特別に構成される汎用コンピュータにより実行し得る。
【００６７】
本明細書に示され説明される任意の方法及び装置により使用又は生成される情報等の情報の処理、例えば、コンピュータ画面若しくは他のコンピュータ出力装置への表示、記憶、受け入れを行うために、任意の適したプロセッサ、ディスプレイ、及び入力手段を使用することができ、上記プロセッサ、ディスプレイ、及び入力手段は、本発明の実施形態のうちのいくつか又はすべてによれば、コンピュータプログラムを含む。本明細書に示され説明される本発明の任意又はすべての機能は、処理に使用される、汎用又は特別に構築された従来のパーソナルコンピュータプロセッサ、ワークステーション、又は他のプログラム可能な装置、又はコンピュータ、又は電子計算装置と、表示のためのコンピュータディスプレイ画面、及び／又はプリンタ、及び／又はスピーカーと、光ディスク、ＣＤＲＯＭ、磁気光学ディスク、又は他のディスク等の機械可読メモリと、記憶のためのＲＡＭ、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード、光学カード、又は他のカードと、受け入れるためのキーボード又はマウスとにより実行することができる。上記で使用される「プロセス」という用語は、例えば、コンピュータのレジスタ及び／又はメモリ内で発生又は存在し得る物理的、例えば、電子的な現象として表現されるデータの任意の種類の計算、又は処理、又は変形を含むことが意図される。プロセッサという用語は、単一の処理ユニット又は複数の分散した若しくは遠隔のそのようなユニットを含む。
【００６８】
上記装置は、任意の従来の有線又は無線デジタル通信手段を介して、例えば、有線又はセルラ電話回線又はインターネット等のコンピュータネットワークを介して通信し得る。
【００６９】
本発明の装置は、本発明の特定の実施形態によれば、命令プログラムを含むか、又は記憶する機械可読メモリを含むことができ、命令は、機械により実行されると、本明細書に示され説明される本発明の装置、方法、特徴、及び機能のうちのいくつか又はすべてを実施する。代替又は追加として、本発明の装置は、本発明の特定の実施形態によれば、任意の従来のプログラミング言語で書くことができる上記のようなプログラムと、任意選択的に、本発明の教示により任意選択的に構成又は起動可能な汎用コンピュータ等であるが、それに限定されない、プログラムを実行する機械とを含み得る。本明細書に組み込まれる任意の教示は、どこであろうとも、物理的な物体又は物質を表す信号に対して適宜動作し得る。
【００７０】
上記で参照された実施形態及び他の実施形態を次項で詳細に説明する。
【００７１】
テキスト又は図面内に現れるいずれの商標も、その所有者の所有物であり、本明細書では、本発明の実施形態をいかに実施し得るかの一例を説明又は例示するためだけに現れる。
【００７２】
別途明記しない限り、以下の考察から明らかなように、本明細書の考察全体を通して、「処理」、「計算」、「推定」、「選択」、「ランク付け」、「等級付け」、「算出」、「特定」、「生成」、「再評価」、「分類」、「生成」、「生産」、「ステレオマッチング」、「登録」、「検出」、「関連付け」、「スーパーインポーズ」、「取得」等の用語の利用が、計算システムのレジスタ及び／メモリ内の電子的数量等の物理的数量として表現されるデータを処理し、且つ／又は変形して、計算システムのメモリ、レジスタ、又は他のそのような情報記憶装置、伝送装置、又はディスプレイ装置内の物理的数量として同様に表現される他のデータにするコンピュータ、又は計算システム、又はプロセッサ、又は同様の電子計算装置の動作及び／又はプロセスを指すことが理解される。「コンピュータ」という用語は、非限定的な例として、パーソナルコンピュータ、サーバ、計算システム、通信装置、プロセッサ（例えば、デジタル信号プロセッサ（ＤＳＰ）、マイクロコントローラ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）等）及び他の電子計算装置を含むデータ処理性能を有する任意の種類の電子装置を包含するものとして広く解釈されるべきである。
【００７３】
本明細書は、単に明確にするために、特定のプログラミング言語、オペレーティングシステム、ブラウザ、システムバージョン、個々の製品等に固有の用語で説明され得る。この用語は、例として動作の一般原理を明確且つ簡潔に伝えることが意図され、本発明の範囲をいかなる特定のプログラミング言語、オペレーティングシステム、ブラウザ、システムバージョン、又は個々の製品にも限定することを意図しないことが理解されよう。
【００７４】
本明細書に別個に列挙される要素は、別個の構成要素である必要はなく、代替として、同じ構造であってもよい。
【００７５】
本明細書に説明されるステップのうちのいくつか又はすべては、とりわけコンピュータプロセッサを利用し得る。
【００７６】
本発明を理解し、本発明をいかに実施し得るかを見るために、特定の実施形態を添付図面を参照して、単に非限定的な例として説明する。
【図面の簡単な説明】
【００７７】
【図１】図１は、プリントすべきモデルを比較的薄い水平断面に変形し、それから、プリントが完了するまで連続する層を作成する従来技術による３Ｄプリント技術の概略図である。
【図２】図２は、本発明の実施形態による、３Ｄ物体の破損し非一貫性を有し得るモデルを有効なプリント可能モデルに変形（変換）するシステムの概略図である。
【図３】図３は、本発明の実施形態による、３Ｄ物体の破損し非一貫性を有し得るモデルを有効なプリント可能モデルに変形する方法のフローチャートである。
【図４Ａ】図４Ａは、本発明の実施形態による自己交差モデルの概略図である。
【図４Ｂ】図４Ｂは、本発明の実施形態により適切な辺の導入を通してＴ頂点をなくすことの概略図である。
【図４Ｃ】図４Ｃは、本発明の実施形態により、欠落している四辺形を追加することにより水密モデルを形成することの概略図である。
【図４Ｄ】図４Ｄは、本発明の実施形態により、誤った向きのポリゴンを反転させることにより水密モデルを形成することの概略図である。
【図５Ａ】図５Ａは、本発明の実施形態により、修復ステップ中、単一の三角形を、上と下の三角形との距離をゼロにしながら、ゼロ容積の角柱に変換することの概略図である。
【図５Ｂ】図５Ｂは、本発明の実施形態による膨張動作の概略図である。
【図５Ｃ】図５Ｃは、本発明の実施形態による薄いパーツを含む階段に適用される一般的な厚化動作の概略図である。
【図６Ａ】図６Ａは、本発明の実施形態による位相幾何学的特異点を含むモデルの概略図である。
【図６Ｂ】図６Ｂは、本発明の実施形態により、ステッチング動作が適用され、それにより、位相幾何学的特異点をなくすモデルの概略図である。
【図７】図７は、本発明の実施形態によるメッシュを有する２つの水密壁を統合することの概略図である。
【図８】図８は、本発明の実施形態による、ＳＴＬファイル形式を表示し、ユーザが３Ｄプリントすべきモデル物体を制御し選択できるようにするサンプルＧＵＩの図である。
【図９Ａ】図９Ａ及び図９Ｂは一緒に解釈されて、本発明の実施形態により動作可能な三次元物体モデルのプリントを可能にする方法の簡略化されたフローチャート図を形成する。
【図９Ｂ】図９Ａ及び図９Ｂは一緒に解釈されて、本発明の実施形態により動作可能な三次元物体モデルのプリントを可能にする方法の簡略化されたフローチャート図を形成する。
【図１０】図１０は、図９Ａのステップ９００の実行に適した適応分解方法の簡略化されたフローチャート図である。
【図１１】図１１Ａ及び図１１Ｂは、図９Ａ、図９Ｂ、及び図１０の方法を使用した処理前後の壁の平面図である。
【図１２】図１２は、本発明の実施形態の実施態様例の図である。
【図１３】図１３は、図１２の図に対応する擬似コードである。
【発明を実施するための形態】
【００７８】
説明を簡易かつ明確にするために、図に示される要素が必ずしも一定の縮尺で描かれているわけではないことが理解されよう。例えば、明確にするために、いくつかの要素の寸法は、他の要素と比較して誇張され得る。さらに、適切であると考えられる場合、参照番号は図の間で繰り返されて、対応又は類似する要素を示し得る。
【００７９】
別途明記しない限り、以下の考察から明らかなように、本明細書の考察全体を通して、「処理」、「計算」、「算出」、「特定」等の用語の利用が、データを処理し、且つ／又は変換して他のデータにするコンピュータの動作及び／又はプロセスを指し、データが、例えば、電子的数量等の物理的数量として表現されることが理解されよう。「コンピュータ」という用語は、非限定的な例として、パーソナルコンピュータ、サーバ、計算システム、通信装置、プロセッサ（例えば、デジタル信号プロセッサ（ＤＳＰ）、マイクロコントローラ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）等）、及び他の電子計算装置を含むデータ処理性能を有する任意の種類の電子装置を包含するものとして拡大して解釈されるべきである。本明細書における教示による動作は、所望の目的のために特別に構築されたコンピュータ又はコンピュータ可読記憶媒体に記憶されたコンピュータプログラムにより所望の目的のために特別に構成される汎用コンピュータにより実行し得る。
【００８０】
本発明の実施形態によれば、システム２００（図２）により生成されるモデルは、有効なプリント可能モデル又は略してプリント可能モデルと呼ばれる。一般に、プリント可能モデルは、様々なプリント装置により課される事前定義される要件セットを満たす。異なるプリント装置は、異なる技術に基づくため、異なる要件セットを課す。本発明によれば、システム２００は、比較的大きなプリント装置セットを満たし、建物及び景観等の様々な建築モデル並びに科学的視覚化及び物理的シミュレーション等の他の多くの分野に見られるモデルを処理する。
【００８１】
簡潔にするために、以下の本発明の詳細な説明は主に、３Ｄプリントに使用されるモデルに関連する。しかし、３Ｄプリントのみに限定されるものとして考えられるべきではなく、本発明は、破損したモデルの修復及び組み立て計画の非一貫性の除去等に関連することもできる。
【００８２】
図２は、例えば、ポリゴンメッシュ（例えば、非多様体メッシュ、交差三角形、Ｔ字形接合部を有するメッシュ等）として表現される３Ｄ物体の破損し非一貫性を有し得るモデルを有効なプリント可能モデルに変形（変換）する、本発明の実施形態によるシステム２００の概略図である。本発明の実施形態によれば、従来のソフトウェアモデリングツール（例えば、ＡｕｔｏＣａｄ（登録商標）及びＲｅｖｉｔ（登録商標））のユーザ（例えば、建築家）は、建物、景観等の物体の３Ｄモデルを作成する。そのような各ツールにより作成される（デジタル）モデルは、３Ｄの個々の任意のパーツ（例えば、壁、階段、及び屋根）と、３Ｄ空間でのそれぞれの対応する位置（すなわち、並進移動及び向き）とを備える。いくつかの従来のファイル形式が、モデルを記憶するためにこれらのモデリングツールにより使用される（例えば、ＳＴＬ（ステレオリソグラフィ）及びＰＬＹ（ポリゴン）ファイル形式）。これらのモデリングツールのいくつかでは、第三者の開発者がメインアプリケーションを拡張し、一般に「プラグイン」と呼ばれる他のコンピュータプログラムを通して新しい特徴を提供することができる。すなわち、ホストアプリケーションは、プラグインがそれ自体をホストアプリケーションに登録する方法を含め、プラグインが使用できるサービスと、プラグインとデータを交換するためのプロトコルとを提供する。本発明の実施形態によれば、サブシステム２１５は、独立したアプリケーション又はプラグインのいずれかであることができ、入力として、３Ｄ空間内の物体のモデルを受け入れることができる。システム２００は、３Ｄ空間内の物体モデルのファイルを、対応するモデラーデータ２１１（例えば、メモリユニット（図示せず）から提供され、そのような物体モデルを有効なプリント可能３Ｄ物体モデルに変形（変換）すると共に受信するサブシステム２１５と、有効な三次元物体モデルをプリントする３Ｄプリンタ２２０とを備える。本発明の実施形態によれば、モデラーデータ２１１は、ソリッドモデリングデータ及び／又はポリゴンスープ（ポリゴンの任意の集合）を含むことができる。
【００８３】
本発明の実施形態によれば、３Ｄデジタルモデルは、サブシステム２１５により調べられて（自動的に）、破損又は非一貫性が突き止められる。１つ又は複数の破損又は非一貫性が見つかった場合、サブシステム２１５はそれらを修復する。次に、プリントするモデルが、プリンタ分解能に十分な厚さではない薄いパーツの厚化等の対応する動作を適用することにより準備される（自動的に）。機能的なパーツ（例えば、階段等）も識別され、次に、専用厚化動作が適用され、それにより、それらの機能性を保持する。個々のすべてのパーツは、プリント準備が整った（例えば、十分に厚く、「空中に浮遊」しない）後、統合され、交差をなくし、場合によっては特異点をなくす。その結果、最終的な一貫したモデルが得られ、これは、３Ｄプリンタ２２０によりプリント（造形）することができる。本発明の実施形態によれば、システム２００は、ＳＴＬ（ステレオリソグラフィ）、ＶＲＭＬ（仮想現実モデリング言語）、及びＸ３Ｄ（３Ｄコンピュータグラフィックスを表現するためのＸＭＬに基づく（拡張可能マークアップ言語）ファイル形式）ファイル形式のモデルをパーズすることが可能である。システム２００は、ＡｕｔｏＣａｄ（登録商標）及びＲｅｖｉｔ（登録商標）等のモデラー（モデリングソフトウェア）により生成されるモデルも、それらの対応するアプリケーションプログラムインタフェース（ＡＰＩ）を通して受け入れる。さらに、システム２００は、様々な３Ｄプリンタによりパーズ可能であり、したがって、３Ｄモデルを表現するプリントの共通形式としての役割を果たすＳＴＬファイル形式等の様々なファイル形式で有効なプリント可能モデルを生成することができる。
【００８４】
本発明の実施形態によれば、システム２００の入力において受信されるモデルファイル２０６は、破損し得るか、又は非一貫性を含み得る。個々のパーツの物理的なサイズが、３Ｄプリントに対して比較的小さい場合もあり、他方、含まれるすべてのパーツを有するモデル全体のサイズが、３Ｄプリントに対して比較的大きい場合もある。加えて、個々のパーツは、内部で互いに交差し得、又は頂点若しくは辺における境界で互いに交差し得、特異点を生じさせ得る。したがって、一連の動作がサブシステム２１５により適用され、入力モデル（ファイル）２０６を、ラピットプロトタイピング及び同様の要件を有する他の用途に使用可能なモデルに変形（変換）する。適用される一連の動作は、９フェーズ等の事前定義された数のフェーズを含むパイプラインとして実施され、フェーズのうちのいくつかは、任意選択的であり得、迂回することができる。
【００８５】
本発明の実施形態によれば、システム２００は、３Ｄ物体の破損又は非一貫性を有し得るデジタルモデルを、ラピットプロトタイピング（ＲＰ）とも呼ばれるプロセスである固体自由造形（ＳＦＦ）を使用して自動的に構築できる物理物体のモデルに変形できるようにする。
【００８６】
プリント可能モデルは、例えば、３Ｄプリンタ２２０の事前定義される要件により指定される境界ボックス内に収まらなければならない。本発明の別の実施形態によれば、モデルが境界ボックスよりも相対的に大きい場合、縮小するか、又は境界ボックスでクリッピングしなければならない。
【００８７】
図３は、３Ｄ物体の破損し非一貫性を有し得るモデルを有効なプリント可能モデルに変形する、本発明の実施形態による方法のフローチャート３００である。この実施形態によれば、方法は、例えば、示されるように適宜順番付けられた以下のステップ：インポート３０５、修復３１５、スケーリング３２０、厚化（膨張）３２５、支持３４０、選択（クリッピング）３４５、統合３５０、特異点除去３６０、及びエクスポート３６５、のうちのいくつか又はすべてを含み、ステップのうちのいくつかは、任意選択的であり、迂回することができる（支持ステップ３４０及び特異点除去ステップ３６０等）。ステップ３０５において、モデルデータがインポートされる。モデルを表す入力モデルファイル２０６（図２）は、サブステップ３０６においてＳＴＬ等のサポートされるファイル形式をパーズすることにより得られるか、又はデータは、モデリングアプリケーションＡＰＩ（アプリケーションプログラミングインタフェース）を通して、ステップ３０７においてモデリングアプリケーションから直接得られる。ステップ３１５において、（物体）モデルが受信され、解析され、非一貫性（もしあれば）が除去される。このために、閉２Ｄ多様体（互いに交差し得る）が生成される。この動作は修復と呼ばれる。次に、ステップ３２０において、モデルは、ユーザの選択に従って、３Ｄプリンタ２２０（図２）により定義される境界ボックス内に収まるように自動的に、又はユーザ提供のスケーリング係数により手動でスケーリングされる。このために、モデルの特徴の座標が現実世界座標にマッピングされる。この結果、当然ながら、それでもなお、３Ｄプリンタ２２０により定義される建物容積からはみ出るため、所与の３Ｄプリンタ２２０（図２）による造形（プリント）には比較的大きなモデルが生成され得る。ステップ３３０において、独立したビューアを使用して、各フェーズの出力、特に最終出力を閲覧（且つ必要であればセットアップ／調整）することができ、出力は個々に３Ｄプリンタ２２０（図２）に送信することができる。ユーザは、異なる種類のモデル物体の膨張を可能にすること、１つ又は複数の個々の（サブモデル）要素をプリントするか否かを判断すること、３Ｄプリンタ２２０を選択すること、スケーリング係数を選択すること等のシステム２００の対応する構成を実行することができる。次に、ステップ３２５において、薄いパーツの厚化等の動作を適用し、パーツの機能性をさらに考慮（保持）することにより、モデルの３Ｄプリントへの準備が整う。その後、ステップ３４０において、モデルは、例えば、支持梁を追加して、２つ以上の分離した構成要素を接続することにより、物理的解析に基づいて変更され、単体の接続されたモデルを形成する。その後、選択ステップ３４５が適用され、このステップにおいて、３Ｄプリントすべき１つ又は複数のモデルパーツが選択される。このステップは、選択された３Ｄポインタにより定義される境界ボックスから完全又は部分的にはみ出たパーツの自動却下で開始される。個々のパーツの手動選択も同様にサポートされる。ビューアを使用して、ユーザの選択を実行する。ビューアは、却下パーツとは異なるように選択パーツをレンダリングした状態で全体モデルを表示し、２つの相補的な部分集合を区別する。２つの部分集合のレンダリングは、ユーザにより別個に制御される。ステップ３５０において、ステップ３４０において生成されたソリッドパーツ（又は複数のパーツ）の内積の和が統合され、それにより、自己交差及び異なるパーツ間の交差がなくなる。次に、ステップ３６０において、特異点をモデルからなくす。すなわち、特異的な頂点及び辺が識別され、削除され、それにより、単体の（特異点のない）多様体が生成されるか、又はモデルがステッチングされて、いくつかの実質的に分離した２Ｄ多様体が生成される。最後に、ステップ３６５において、モデルはエクスポートされる。モデルは、サポートされるファイル形式でモデルを表現する出力モデルファイルで記憶するか、又はステップ３７０において、３Ｄプリンタ２２０（図２）に送信することができる。
【００８８】
本発明の実施形態によれば、ユーザは、ビューアを使用して上記ステップの各ステップの出力を観察し、ビューアは、ユーザにより制御される様々なビューからモデルを三次元でレンダリングすることができるインタラクティブソフトウェア構成要素である。ステップ３０５中の解析動作では、比較的多くの計算時間が必要であり得るため、ユーザはその複雑性を制御することができる。したがって、デフォルトにより、低複雑性解析を実行することができる。ユーザは、例えば、ステップ３１５において適用される修復プロセスの結果を閲覧することもできる。破損又は非一貫性が残っており、ユーザにより観察される場合、高複雑性解析を適用することができる。本発明の実施形態によれば、ステップ３０５の結果は、アーチファクトを略含まない１つ又は複数の閉２Ｄ多様体を含む有効なモデルである。しかし、２Ｄ多様体は破損し、互いに交差している可能性があり得る。
【００８９】
本発明の実施形態によれば、修復（ステップ３１５において適用される）は、３Ｄソリッドの一貫したモデルの再構築を可能にすると共に、ポリゴンの任意の集合（ポリゴンスープ）からの、適切なソリッドパーツを画定する境界表現の取得を可能にする。非有向３Ｄ多様体（例えば、クラインの管）及び非閉２Ｄ多様体（例えば、メビウスの輪）は、適切なソリッドを画定しないため、不当な入力を含む。
【００９０】
本発明の実施形態によれば、入力モデル（例えば、ＳＴＬファイルにより提示される）を自動的に修復する異なる方法（技法）セットが提供される。これらの方法は、効率と品質とをトレードオフすることができ、例えば、最も効率的な戦略をデフォルトで使用することができる。ユーザは、結果を見て、結果が満足のいくものになるまでモデルの再処理を要求することが可能であり得る。したがって、インポートステップ３０５の結果は、互いに交差するアーチファクトが略ない１つ又は複数の閉２Ｄ多様体を含む有効なモデルであることができる。比較的高品質のモデルを得る方法は、非一貫性が略ないモデルを生成することができ、このために、Ｔ．Ｍ．Ｍｕｒａｌｉ等（「Ｃｏｎｓｉｓｔｅｎｔ  Ｓｏｌｉｄ  ａｎｄ  Ｂｏｕｎｄａｒｙ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ  ｆｒｏｍ  Ａｒｂｉｔｒａｒｙ  Ｐｏｌｙｇｏｎａｌ  Ｄａｔａ  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ」，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １９９７  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｔｅｒａｃｔｉｖｅ  ３Ｄ  Ｇｒａｐｈｉｃｓ，Ｐｒｏｖｉｄｅｎｃｅ，ｐａｇｅｓ  １５５−１６２，１９９７という名称の記事において）により紹介された技法を実施することができる。この技法によれば、空間は、入力ポリゴンを支持する平面により分離される凸多面体領域に分割される。ソリッド領域は、領域の境界の不透明度に基づく規則：１）大半が透明な境界を共有する２つの隣接するセルは、同じソリッド性を有する（すなわち、一方がソリッドである場合、他方もソリッドである）可能性が高く、２）大半が不透明な境界を共有する２つの隣接するセルは、逆のソリッド性を有する（すなわち、一方がソリッドである場合、他方はソリッドではない）可能性が高く、３）境界のないセル（すなわち、点を無限遠で含む、外部にあるセル）はソリッドではない、から導出される一次式系を解くことにより識別される。ソリッド領域が識別されると、交差、同一平面上のポリゴン、又は接続されていないポリゴンのない一貫したソリッドモデル及び境界表現を出力することができる。
【００９１】
本発明の実施形態によれば、平面グラフに一般に知られているオイラーの公式を利用する解析が、各モデルパーツに独立して適用される。ｖ、ｅ、及びｆが各パーツの頂点、辺、及び面のそれぞれを示すものとする。そうすると、式ｖ＋ｆ＝ｅ−２が保たれなければならない。比較的あまり時間がかからない修復戦略は通常、以下のように進められる。まず、同一の三角形、劣化した三角形／辺等の同一の特徴及び劣化した特徴が削除される。次に、ε閉特徴が統合され、辺を分割することにより、Ｔ字形接合部がなくなる。そのような分割は、元のポリゴンに取って代わる２つのポリゴンをもたらす。
【００９２】
地形は地面の垂直寸法である。地形は通常、地形特徴の高さに関して表され、単面に関係する辺を境界とする非多様体２Ｄ表面により表される。単面に関係する辺を境界とする３Ｄ空間内の非多様体２Ｄ表面は、地形を表すか、又は単に、ゼロ容積パーツの不完全な表現を含む。修復フェーズはそのような表面を識別する。地形表面はそのようにして分類され、壁等の物体の不完全な表現は修復される。残りの表面は削除される。そのような表面の修復動作により、逆向きの２Ｄ表面及び境界に沿った１Ｄ（一次元）表面がもたらされることになる。これにより、厚化ステップ３２５により処理可能なゼロ容積パーツが生成される。
【００９３】
本発明の実施形態によれば、モデルが３Ｄプリンタの要件（構成）を満たすには相対的に大きなモデルである場合、モデルを縮小するか（ステップ３２０）、又は例えば、プリンタの事前定義される要件により指定される境界ボックスでクリッピング（ステップ３４５）しなければならない。スケーリング動作は、モデルの特徴の座標を現実世界の座標にマッピングする。さらに、クリッピング動作は、モデルを構成するパーツの中から、境界ボックス内に全体的に含まれるパーツのみを選択する。本発明の実施形態によれば、スケーリング動作は、結果として生成されるモデルが不十分な厚さのパーツを含み得るため、厚化ステップ３２５の前に適用される。本発明の別の実施形態によれば、クリッピング動作は、統合ステップ３５０の前に適用され、個々のパーツの手動選択をサポートすることもできる。ビューアを使用して（ステップ３３０において）、ユーザの選択を実行する。例えば、ビューアは、選択されたパーツを選択されていないパーツとは別様にレンダリングして、２つの相補的な部分集合を区別した状態でモデル全体を表示することができる。２つの部分集合のレンダリングは、ユーザにより別個に制御することができる。
【００９４】
本発明の実施形態によれば、厚化・膨張ステップ３２５中、モデルの各パーツが解析されて、このパーツが３Ｄプリントに十分な厚さであるか否かが判断される。十分な厚さではない場合、パーツは、結果として生成されるパーツが十分な厚さになるように変更される。無差別的な厚化は、機能の観点から元のモデルに一致しない歪んだモデルを生成し得る。したがって、専用の手続きが、パーツの機能を保ちながら、識別されたパーツの所定の群に適用される。ＣＡＤモデルは、壁、窓、階段、マリオン、屋根、床、地形等の異なるタイプのパーツを含む。異なるタイプのパーツは、作成される間に分類される。分類が保存される場合、ステップ３２５において、本発明の実施形態による新規の厚化方法（アルゴリズム）が適用される。本発明の別の実施形態によれば、厚化ステップを２回適用して、従来の３Ｄプリンタ２２０（図２）により課される２つの異なる対応する厚化基準を満たすことができる。第１の基準によれば、すべてのパーツは垂直方向で十分な厚さを有する必要がある。これは垂直厚化と呼ぶことができる。水平厚化と呼ばれる第２の基準によれば、すべてのパーツは、ＸＹ平面に含まれるすべての方向で十分な厚さを有する必要がある（Ｘ及びＹは座標系内の軸である）。一般に、垂直厚化動作及び水平厚化動作は、２つの様式で異なる。第１に、垂直厚化は、一方向を処理するため、比較的あまり複雑ではない。第２に、膨張は、パーツの特定の群に対して垂直方向に沿って適用される。ｔｖ及びｔｈが垂直（層）及び水平最小厚さ（事前定義される値を有する）のそれぞれであると仮定する。厚化動作は、例えば、説明されるように適宜順序付けられた以下のサブステップのうちのいくつか又はすべてを含む。第１に、すべてのパーツは凸サブパーツ（プロトタイプ）に分解され、多くの場合、入力モデル（ファイル）は既に凸サブパーツを含む。第２に、各サブパーツの幅が計算される。次に、幅がｔｖよりも小さなサブパーツは、垂直方向に沿って厚化され、水平幅がｔｈよりも小さなサブパーツは、適切な水平方向に沿って厚化される。サブパーツが不十分な厚さとして識別される場合、その境界の１つ又は複数の面は、境界の特徴の関連を保ちながら並進移動する。所与の距離ｄに沿った厚化により、特徴はｄ方向に並進移動することになる。３つのタイプの厚化動作、すなわち、スケーリング、膨張、及びオフセットがある。Ｐがパーツであり、ｗｖ及びｗｈがＰの垂直幅及び水平幅のそれぞれであると仮定する。垂直幅の方向に向けられた正規化ベクトルはｄｖ＝（０，０，１）である。水平幅の方向に向けられた正規化ベクトルがｄｈ＝（ｄｘ，ｄｙ，０）であると仮定する。Ｐがスケーリングを使用して厚化する場合、以下の１つ又は複数の事前定義される基準（スケーリング係数）が使用される。垂直厚化が適用される場合、パーツはｚ次元のみにスケーリングされる。適用されるスケーリング係数は、所望の幅と幅との比率、すなわち、ｔｖ／ｗｖである。水平厚化が適用される場合、パーツはｘ次元及びｙ次元においてスケーリングされる。ｘ及びｙスケーリング係数はｄｘ・ｔｈ／ｗｈ及びｄｙ・ｔｈ／ｗｈのそれぞれである。これにより、拡大が最小であるが、それでも十分な厚さのパーツを生成する。
【００９５】
ｆが、幅方向に直交する平面により支持される特徴であり、Ｆがｆ、ｆの関連特徴、及びそれらの特徴に関係する頂点を含む集合であると仮定する。ｆが面である場合、Ｆはその面と、ｆの境界上のすべての頂点及び辺とを含む。ｆが辺である場合、Ｆはその辺と、２つの関係する面と、これらの関係する２つの面の境界上のすべての頂点及び辺とを含む。ｆが頂点である場合、Ｆはその頂点と、頂点に関係するすべての面と、関係するこれらの面の境界上のすべての頂点及び辺とを含む。Ｐが膨張を使用して厚化する場合、Ｆ内の特徴は、幅要件を満たすように並進移動する。Ｆ内の特徴は、垂直厚化及び水平厚化のそれぞれで幅方向に向けられた長さ（ｔｖ−ｗｖ）及び又は（ｔｈ−ｗｈ）のベクトルにより並進移動する。続けて、モデル全体が、図５Ｂ（パーツ５２０及び５２５）に概略的に提示されるように調整される。Ｐがオフセットを使用して厚化される場合、Ｆ内のすべての特徴の支持平面は、垂直厚化及び水平厚化のそれぞれで幅方向に向けられた長さ（ｔｖ−ｗｖ）及び又は（ｔｈ−ｗｈ）のベクトルにより並進移動する。
【００９６】
プロトタイプの幅は、プロトタイプとプロトタイプの同一コピーとの侵入深さであり、侵入深さは、原点と、プロトタイプと原点を通るその反射とのミンコフスキー和との最小距離である（例えば、Ｅ．ＢｅｒｂｅｒｉｃｈによりＭａｔｈｅｍａｔｉｃｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，Ｓｐｒｉｎｇｅｒ，２００９に提出された「Ａｒｒａｎｇｅｍｅｎｔｓ  ｏｎ  Ｐａｒａｍｅｔｒｉｃ  Ｓｕｒｆａｃｅｓ  ＩＩ：Ｃｏｎｃｒｅｔｉｚａｔｉｏｎ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ」という名称の記事に提示されるように）。
【００９７】
２つのプロトタイプＰ及びＱのミンコフスキー和の正規マップは、Ｐの正規マップとＱの正規マップとの球形オーバーレイである。プロトタイプＰ毎に、Ｐの正規マップ及びその反射の正規マップが計算される。次に、２つの正規マップのオーバーレイが計算され、Ｐとその反射とのミンコフスキー和の正規マップが得られる。その後、ミンコフスキー和の面が得られる。最後に、原点と面との垂直距離及び水平距離が計算される。垂直距離及び水平距離が、ｔｖ及びｔｈのそれぞれよりも小さい場合、本発明の実施形態によれば、厚化動作（例えば、スケーリング、膨張、及びオフセット）のうちの１つが、距離基準を満たすまで適用される。垂直方向では、１回の適用で比較的十分である。しかし、水平方向での距離基準を満たすには、厚化を２回以上（すなわち、数回のループで）適用することが必要であり得る。
【００９８】
本発明の実施形態によれば、入力モデル（ファイル）は、３Ｄ空間内の２Ｄ表面として表現される地形パーツを含み得る。地形表面は、非ゼロ容積を有するソリッドパーツに変換する必要がある。このために、まず、入力モデル内のすべての地形表面が識別される。通常、地形表面の分類が入力モデル内に保持される。本発明のこの実施形態によれば、修復ステップ３１５中に最初は地形表面として分類されなかった地形表面が識別される。地形表面が識別されると、表面頂点がＸＹ平面に平行する平面に投影され、必要な境界ポリゴンが導入され、３Ｄプリントに有効な２Ｄ多様体が形成される。ｐ（ｐ＝（ｐｘ，ｐｙ，ｐｚ））が、最小の頂点座標ｐｚを有する地形表面の点であると仮定する（Ｘ、Ｙ、及びＺは座標系の軸である）。次に、ｚ＝ｖｚ−ｔｖでの投影を含む平面を、最小垂直幅基準を満たしながら配置することができる。
【００９９】
本発明の別の実施形態によれば、薄いパーツの境界への並進移動動作が屋根又は床に関連する場合、モデル全体を調整する必要がある。並進移動と調整との組み合わせられた動作は膨張と呼ばれる。一般に、膨張動作は、最小の垂直座標を有する並進移動された特徴よりも上にあるパーツの特徴に影響する厚化動作の変形と見なすことができる。したがって、膨張動作は実質的に、モデルパーツの内部間に交差を導入しない。
【０１００】
本発明のさらに別の実施形態によれば、辞書編纂的にソートされたすべてのパーツのすべての点の補助データ構造が、まずｚ座標、次にｙ座標、そして最後にＸ座標に従って保持される。Ｐが不十分な厚さのパーツであり、ｐ＝（ｐｘ，ｐｙ，ｐｚ）が、厚化動作中に並進移動されるＰのすべての点の中からの最小のｚ座標を有する境界上の点であると仮定する。ｖｚが並進移動ベクトルであるとも仮定する。次に、ｐｚ以上のｚ座標を有するパーツのうちの略すべての点が、ｖｚだけ並進移動する。これらの点は、補助データ構造内で比較的容易に見つけることができ、次に、関係する辺及び面が並進移動された点まで更新される。
【０１０１】
既知のように、一般的な厚化は、無差別に適用された場合、物体を歪ませ得る。一般的な厚化動作は、結果として生成される物体が、モデラー（例えば、建築家）により当初果たすように設計された目的にかなわない点までオペランド物体を変形させ得る。階段及びマリオンは、そのような歪みを比較的受けやすい。したがって、本発明の実施形態によれば、入力モデルが階段又はマリオンを含み、自動的又はユーザにより階段又はマリオンとして識別可能な場合、（ユーザにより制御される）専用厚化動作が適用され、専用厚化動作は、ソースと呼ばれる元のモデルパーツをターゲットと呼ばれる新しいモデルパーツで置換し、ターゲットは、（ｉ）ソースと同じ機能を提供し、（ｉｉ）幅基準を満たす。このために、既製の３Ｄプリント可能パーツの比較的大きなデータベースが作成され、３Ｄプリント可能パーツの機能に従って分類される。パーツの候補ペア（除去すべきソースパーツ及びソースパーツに代えて挿入すべきターゲットパーツ）は、本発明の実施形態により、システム２００（図２）により自動的に示唆することができる。システム２００では、ユーザは候補を追加又は削除することができ、ユーザは、都合のよいインタラクティブな選択を行うために、ビューアを使用してターゲットパーツをオーバーライドすることもできる。ペアが認証されると、（特定のソースパーツとターゲットパーツとの置換が認可され、ソースパーツの境界ボックスが計算され、ターゲットパーツは境界ボックス内に収まるようにクリッピングされ、最後に、スケーリングされたターゲットパーツがソースパーツに代えて挿入される。
【０１０２】
本発明の実施形態によれば、入力モデルは、比較的良好に支持されないパーツ又は「空中に浮遊する」パーツを含み得る。本発明のこの実施形態によれば、そのような入力モデルの造形（プリント）は、以下の２ステップを達成することにより可能にし得る。第１のステップ中、各パーツの層は、各層の特定の個片が固化する間に、首尾良く積層される。第２のステップ中、固化しなかった個片が洗浄されて除去される（これらの両ステップは図３において支持ステップ３４０として示されるものと思われる）。浮遊パーツと呼ばれる比較的良好に支持されないパーツは分離され、原点及び残りのパーツに対する位置を失う。したがって、そのような浮遊パーツが識別される。浮遊パーツ毎に、浮遊パーツを支持する新しいパーツの導入が提供される。支持パーツは、一方では、浮遊パーツの重心に接続され、他方では、ある方向において光線に直面する第１のパーツに接続される。撮影方向として、負の垂直方向をデフォルトで使用し得る。
【０１０３】
本発明の実施形態によれば、モデルはさらに、３Ｄプリンタ２２０により定義される建築容積、通常、主軸に位置合わせされたボックス内に収まらないことがある。本発明の実施形態によれば、建築容積は、プリントすべきすべてのパーツを含む必要がある。建築容積から完全又は部分的にはみ出るすべてのパーツは、自動的に却下し得る。デフォルトにより、完全に建築容積内部にあるすべてのパーツがプリントに選択されることに留意されたい。加えて、ユーザは、閲覧ステップ３３０において、例えば、建築容積からはみ出るパーツを３Ｄプリントに選択できないという条件下で、ビューアを利用して手動選択を適用することができる。システム２００は、選択ステップ３４５中に適用される細分動作もサポートし、この動作では、３Ｄプリントすべきパーツが選択される。ユーザは、モデルを構成するパーツの集合をいくつかの（分離した）部分集合に細分するようにシステムに要求することができる。これは、モデルが全体的に建築容積内に含まれない場合に有用になり得る。さらに、自動ツールが、モデルを、独立して造形（プリント）可能なサブモデルに分割することができる。ユーザは、ビューアを利用してパーツをある部分集合から別の部分集合に移すことができる。次に、異なる部分集合を独立して処理し得る。
【０１０４】
本発明の実施形態によれば、修復ステップ３１５から出力されるモデルは、アーチファクトが略ない水密のパーツを含む。しかし、パーツが交差し、その和が閉２Ｄ多様体を表さない場合がある。加えて、厚化ステップ３２５は交差の数をさらに増大させる恐れがある（モデルパーツの境界間の交差を内部間の交差で置換もする恐れもある）。したがって、パーツの内部間の交差は統合ステップ３５０において除去され、統合ステップ３５０は、本発明の実施形態により、異なる特徴を有する２つの方法を利用し得る。第１の方法は、従来技術による双対マーチングキューブ（ＤＭＣ：ｄｕａｌ  ｍａｒｃｈｉｎｇ  ｃｕｂｅｓ）アルゴリズムの拡張であり（「Ｄｕａｌ  Ｍａｒｃｈｉｎｇ  Ｃｕｂｅｓ：Ｐｒｉｍａｌ  Ｃｏｎｔｏｕｒｉｎｇ  ｏｆ  Ｄｕａｌ  Ｇｒｉｄｓ」，Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  Ｆｏｒｕｍ，ｖｏｌｕｍｅ  ２４，ｎｕｍｂｅｒ  １，ｐａｇｅｓ  １９５−２０１，２００５）という名称の記事においてＳ．Ｓｃｈａｅｆｅｒ等提示されるような）、第２の方法は、「Ｐａｒｔｉｔｉｏｎｉｎｇ  Ｐｏｌｙｈｅｄｒａｌ  Ｏｂｊｅｃｔｓ  ｉｎｔｏ  Ｎｏｎ−Ｉｎｔｅｒｓｅｃｔｉｎｇ  Ｐａｒｔｓ」，ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，ｖｏｌｕｍｅ  ８，ｎｕｍｂｅｒ  １，ｐａｇｅｓ  ５３−６７，１９８８という名称の記事においてＭ．Ｓｅｇａｌにより紹介される従来技術による技法の実施である。
【０１０５】
双対マーチングキューブアルゴリズムは、物体（パーツ）の周囲に適応容積分割（８分木）を構築するように動作可能であり、マーチングキューブ（ＭＣ）アルゴリズムを８分木に適用することに代えて、双対グラフが構築され、次に、マーチングキューブアルゴリズムが双対グラフに適用される。ＤＭＣアルゴリズムは、入力表面により近い出力の生成が可能である。加えて、ＤＭＣアルゴリズムは容積関数を必要とし、容積関数の値は、密度情報又は表面までの距離を表す。本発明のこの実施形態によれば、従来の双対マーチングキューブアルゴリズム（方法）は、等値面関数に代えて非一貫性メッシュを処理するように拡張され、３Ｄプリントに適した単一の有効メッシュを生成する。換言すれば、双対マーチングキューブアルゴリズムは２Ｄ多様体メッシュに適用され、メッシュの和である単一の閉２Ｄ多様体面が作成される。マーチングキューブアルゴリズムはボクセル（容量ピクセル）（メッシュの集合には定義されない）の角に距離フィールド（等値面）を必要とし、ＭＣアルゴリズムは双対グラフに適用されるため、８分木（各ノードが最高で８つの「子」を有するツリーデータ構造）内のボクセル毎に双対点及び値を有する必要がある。双対点は入力表面上に配置され（例えば、単一平面がボクセルを通る場合、その平面がボクセル内の唯一の特徴であるとき、双対点はその平面又は頂点に配置される）、値は比較的小さな負の値に設定される。次に、本発明の実施形態によれば、最大深度に達し、ボクセルがなお細分を必要とする場合、レイトレーシングを使用して、ボクセルの中心が入力ボリュームの内部にあるか、それとも外部にあるかを判断することができ、値はそれに従って設定される。「レイトレーシング」は、システムを通る波又は粒子の経路を計算する周知の従来の方法である。比較的小さな負の値が使用される理由は、これにより、入力表面に比較的近い出力表面を有することができるためである。
【０１０６】
本発明の別の実施形態によれば、結合ステップ３５０から生じるモデルは、位相幾何学的特異点を含み得る。したがって、ステップ３６０において、そのような特異点をポリゴンの非多様体集合からなくして、多様体ポリゴン面を作成する。モデルの特異点をなくすこのステップは、特異点を有するモデルが一般にプリント可能であるため、任意選択的である。他方、多くの場合、連結されない構成要素を有さないモデルを有することが望まれる。特異点をなくすステップ３６０は、例えば、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｖｉｓｕａｌｉｚａｔｉｏｎ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ，ｖｏｌｕｍｅ  ７（２），ｐａｇｅｓ  １３６−１５１，２００１に発表された「Ｃｕｔｔｉｎｇ  ａｎｄ  Ｓｔｉｔｃｈｉｎｇ：Ｃｏｎｖｅｒｔｉｎｇ  Ｓｅｔｓ  ｏｆ  Ｐｏｌｙｇｏｎｓ  ｔｏ  Ｍａｎｉｆｏｌｄ  Ｓｕｒｆａｃｅｓ」という名称の記事においてＡ．Ｇｕｅｚｉｅｃ等により紹介されるアルゴリズムに基づくことができる。モデルの特異点をなくすために、まず、特異頂点及び特異辺が識別される。次に、識別された特異頂点が乗算され、特異辺を通って切断されて、いくつかの分離した多様体ソリッドパーツが生成される。任意選択的なステッチング動作が要求される場合（例えば、ユーザにより要求される）、多様体としての表面を維持するために、境界辺が合体する。実施されるアルゴリズムの変形により、代替のプロトタイプの幅が３Ｄプリントに十分に大きいことを保証する。特異点は、ユーザ選択に従って禁止し得る。
【０１０７】
本発明の実施形態によれば、エクスポートステップ３６５中、出力３Ｄモデルは、ＳＴＬファイル形式等のサポートされるファイル形式で記憶されるか、又は３Ｄプリンタ２２０（図２）に直接送信されて、造形される。サポートされるファイル形式の１つでファイルに記憶された出力３Ｄモデルは、任意の時間に読み取り、３Ｄプリンタに送信することができる。システム２００（図２）の出力がいくつかのモデルを含む場合、各モデルを別個のファイルに記憶することができる。同様に、そのような各３Ｄモデルファイルは、任意の都合のよい時間に３Ｄプリンタに送信することができる。
【０１０８】
本発明の実施形態によれば、ビューアと呼ばれる独立したインタラクティブ構成要素により、ユーザは、ステップ３００において、図３に提示されるステップのそれぞれ１つの出力を閲覧し、特定の変更を加え、デフォルト設定をオーバーライドすることができる。ビューアは、モデルを画面（ディスプレイ）上のウィンドウにレンダリングして、特定の視点から見た三次元デジタルモデルを、画面を含む２Ｄ平面上に投影する。ユーザは、視点をインタラクティブに、且つ比較的平滑に変更させることができる。ユーザは、正投影を使用するか、それとも期待投影を使用するか等の他の関連する閲覧パラメータを変更することもできる。ビューアは、ユーザが様々なシステムパラメータを設定、リセット、又はオーバーライドできるようにするグラフィカルユーザインタフェース（ＧＵＩ）を備えることができる。３Ｄプリンタ２２０（図２）は、プリントすべきすべてのパーツを含む建築容積、通常は主軸に位置合わせされたボックスを定義する。ビューアは、３Ｄプリンタ２２０により課される建築容積をレンダリングし、建築容積から完全又は部分的にはみ出ているため、却下されなければならないパーツを強調表示することができる。デフォルトにより、完全に建築容積内部にあるすべてのパーツはプリントに選択される。ビューアは、プリントに選択されたパーツをレンダリングする。ビューアは、選択されていないパーツをレンダリングすることもでき、２つの完全な集合を、ユーザが選択パーツ及び非選択パーツを区別できるようにレンダリングすることができる。ビューアは、ユーザが、システム２００（図２）によりなされたデフォルト選択をオーバーライドし、パーツを選択集合から非選択集合に移し、非選択集合から選択集合に移すことができる（例えば、建築容積からはみ出ており、プリントに選択できないパーツを除く）。
【０１０９】
本発明の別の実施形態によれば、ユーザは、モデルを構成するパーツの集合をいくつかの部分集合に細分するようにシステム２００に要求することができる。これは、モデルが全体的に建築容積内に含まれない場合に特に有用になり得る。自動ツールが、モデルを、独立して造形（プリント）可能な（別個の）サブモデルに分割する。異なる集合内のパーツは別様にレンダリングされ、ユーザは、パーツをある集合から別の集合に移すことができる。次に、異なる集合は略独立してさらに処理される。ビューアにより、ユーザは、修復ステップ３１５の出力である「修復された」モデルを調べることができる。ユーザは、結果に満足しない場合、異なる修復戦略を選択し、修復動作の適用を繰り返すことができる。さらに、ビューアは、異なる戦略の検証方式を使用することができ、モデル内の３Ｄプリントに影響し得る潜在的なアーチファクトを表示することができる。ビューアにより、ユーザは、それらの潜在的なアーチファクトに印を付け、修復動作のヒントとして提供することもできる。本発明のさらに別の実施形態によれば、ビューアにより、ユーザはスケーリング係数を動的に変更することもできる。加えて、ビューアにより、ユーザは、垂直及び水平厚化基準の設定等のシステム２００の多くのパラメータを変更することができる。ビューアは、ビューアがなければ一般的な厚化動作により歪み、意図される機能を失う選択パーツの制御された置換が可能である。さらに、本発明のさらに別の実施形態によれば、ビューアにより、ユーザは、ステップ３７０においてモデルを３Ｄプリンタ２２０に送信する前、又はステップ３６６において出力モデルファイルに保存する前に（ユーザは、所定の形式セットから所望の出力ファイル形式を選ぶことができる）、モデルを調べることができる。
【０１１０】
図４Ａは、本発明の実施形態により、入力モデル内の面として現れ得る自己交差ポリゴン４００の概略図である。モデルパーツ４０５及び４１０の辺「ａ」及び「ｂ」は互いに交差する。右上の有界領域は画定され閉じられるが、左下の有界領域はそうではない。しらみ潰しの修復戦略がこの欠陥を修復する。特に、無効な面を含む自己交差ポリゴンはいくつかのポリゴンに分けられ、そのうちのいくつかは保持され、他は削除される。
【０１１１】
図４Ｂは、本発明の実施形態により適切な辺４１７の導入を通してＴ頂点４１６をなくす概略図である。
【０１１２】
図４Ｃは、本発明の実施形態により、モデル４２５内に欠けた四辺形４２６を追加することにより水密モデル４２５’を形成する概略図である。面を含む上のポリゴンは、左側の部分のモデルから欠けている。欠けているポリゴンが追加されて、右側の水未モデルを形成する。
【０１１３】
図４Ｄは、本発明の実施形態により、誤った向きのポリゴン４３１を反転させることにより水密モデル４３０’を形成する概略図である。ポリゴンの境界上の頂点の順は、反時計回りでなければならない。左側のパーツのモデル内の面を含む上のポリゴンの境界上の頂点は、時計回りの順である。これは、矢印４３２により図に示されるように、下にある平面への法線が誤って下に向けられていることを暗に示す。誤って向けられたポリゴンの境界上の頂点の順を逆にして、右側の水密モデルを形成する。
【０１１４】
図５Ａは、本発明の実施形態により、修復ステップ３１５（図３）中、上の三角形５１１と下の三角形５１２との距離をゼロにしながら、単一の三角形５０５をゼロ容積の角柱に変換する概略図である。上の三角形５１１及び下の三角形５１２は、図５Ａでは、明確にするために隔てられている。この図は、地形データの処理を示す。地形は地面の垂直寸法であり、通常、地形特徴の高さに関して表され、単面に関係する辺を境界とする非多様体２Ｄ表面により表される。修復ステップ３１５中、分離した単一の三角形５０５が識別され、地形として分類される。次に、逆の向きを有する三角形が、角柱５１０を形成する他の特徴と共に導入される。これにより、厚化ステップ３２５により処理可能なゼロ容積パーツになる。
【０１１５】
図５Ｂは、本発明の実施形態による、ステップ３２５（図３）において適用される膨張の概略図である。膨張したモデル５２０’は、別様にスケーリングされた箱の形状を有する２つのパーツ５２６’及び５２７’を備える（２つのパーツ５２６及び５２７を含む元の（非膨張）モデル５２０と同様に）。下の箱５２７’の上面を含む平面は、上の箱５２６’の下面も含む。下の箱５２７’は、垂直方向において不十分な厚さである。したがって、下の箱５２７’は垂直方向に膨張する。すなわち、上面及びそれに関連する特徴（すなわち、境界上の頂点及び辺）は、正のＺ方向に沿って並進移動する。その結果、下の箱５２７’の上面を含む平面よりも上にあるすべての特徴も同様に並進移動する。
【０１１６】
図５Ｃは、本発明の実施形態により、一般的な厚化動作が階段５３０（薄いパーツからなる）に適用され、階段５３０’を生成する概略図である。階段５３０’’は、一般的に生成された階段モデル５３０’に代えてユーザが選択することができる代替である。階段５３０’’は、階段５３０に適用される厚化動作を拡大し、次に、元のパーツ、すなわち、階段５３０の境界ボックスによりクリッピングした結果であるか、又はユーザがシステム２００（図２）を通してアクセスすることができる階段のデータベースから抽出されたモデルの例である。
【０１１７】
例えば、本発明の実施形態により、一般的な厚化動作を薄いパーツからなるマリオンモデルに適用して、隣接する窓ユニットを分割するパーツを含むマリオンモデルを生成し得る。窓は通常、３Ｄプリントに選択されない。一般的なスケーリングの結果は、厚い窓の仕切り及び小さな窓（高さ及び幅に関して）を含む。窓の数を減らすことを犠牲として、窓のサイズを保つことが望ましい場合がある。
【０１１８】
図６Ａは、本発明の実施形態による、位相幾何学的特異点６１１及び６１２を含むモデル６０５、６１０、及び６１５の概略図である。これらのモデルは非多様体ソリッドパーツを形成する。非多様体（特異）辺６１１及び頂点６１２は、より厚いペンで描かれている。
【０１１９】
図６Ｂは、本発明の実施形態による、ステッチング動作が適用され、それにより、位相幾何学的特異点６１１及び６１２（図６Ａ）が除去されたモデル６０５、６１０、及び６１５の概略図である。特異頂点６１１’及び特異辺６１２’が識別される。次に、識別された特異頂点６１１’及び特異辺６１２’に関係する頂点が乗算される。最後に、境界辺が合体して、多様体としての表面を維持する。本発明の実施形態によれば、サブシステム２１５（図２）により、ステッチング中、新たに導入されたプロトタイプの幅が３Ｄプリントに十分に大きいことが保証される。
【０１２０】
図７は、本発明の実施形態によれば、２つの水密壁７０５及び７１０と、例えば、Ｒｅｖｉｔ（登録商標）ソフトウェアにより作成されたメッシュとの統合の概略図である。本発明の実施形態によれば、従来の双対マーチングキューブアルゴリズム（方法）は、等値面関数に代えて非一貫性メッシュを処理するように拡張され、３Ｄプリントに適した単一の有効メッシュを生成する。換言すれば、双対マーチングキューブアルゴリズムは２Ｄ多様体メッシュに適用され、メッシュの和である単一の閉２Ｄ多様体面が作成される。マーチングキューブアルゴリズムはボクセル（メッシュの集合には定義されない）の角に距離フィールド（等値面）を必要とし、ＭＣアルゴリズムは双対グラフに適用されるため、８分木内のボクセル毎に双対点及び値を有する必要がある。双対点は入力表面上に配置され（例えば、単一平面がボクセルを通る場合、その平面がボクセル内の唯一の特徴であるとき、双対点はその平面又は頂点に配置される）、値は比較的小さな負の値に設定される。次に、本発明の実施形態によれば、最大深度に達し、ボクセルがなお細分を必要とする場合、レイトレーシングを使用して、ボクセルの中心が入力ボリュームの内部にあるか、それとも外部にあるかを判断することができ、値はそれに従って設定される。比較的小さな負の値が使用される理由は、これにより、入力表面に比較的近い出力表面を有することができるためである。その結果、この方法をモデル７１５に適用することにより、３Ｄプリントに有効な単一の連続した２Ｄ多様体ソリッドメッシュ７３０が生成される。提案される方法（双対マーチングキューブアルゴリズムから拡張される）は、建築（建物、例えば、建物及び景色の３Ｄモデル）又は他の任意の分野に使用することができる。
【０１２１】
図８は、本発明の実施形態による、ＳＴＬファイル形式を表示し、ユーザがモデル物体を制御し、３Ｄプリントすべきモデル物体を選択できるようにするサンプルＧＵＩの図である。この実施形態によれば、例えば、ＳＴＬモデルファイルを使用することにより比較的大きなモデルを３Ｄでプリントするには問題があり得る。したがって、モデルを２つ以上のサブモデルに自動的に分割し、各サブモデルを独立してプリントすることができる自動ツールが提示される。換言すれば、ＳＴＬファイルは、それぞれが閉２Ｄ多様体メッシュを含むように、２つ以上の有効なＳＴＬファイルに分割することができる。入力及び出力形式ファイルを表示し、ＳＴＬの無効領域に印を付け、ユーザがプリントすべき１つ又は複数のパーツを選択できるようにする対応するＧＵＩ（グラフィカルユーザインタフェース）を提供することもできる。このＧＵＩは、すべてのモデルパーツ及びＳＴＬ出力を表示することができ、したがって、建築家が、例えば、３Ｄプリントすべきパーツを選択できるようにする。ＧＵＩは、３Ｄプリントに影響し得るＳＴＬファイル内のアーチファクト（ギャップ、交差、及び劣化／同一平面上の三角形／辺等）を表示し、建築家にこれらの特定の問題のあるパーツを変更するか、それとも３Ｄプリントに続くかを判断させるＳＴＬ検証ツールを備えることもできる。加えて、ＳＴＬファイルは、ＧＵＩにより視覚化できるＶＲＭＬ等の他の形式に変換することもできる。
【０１２２】
例えば、デジタルモデルソリッドモデルは、本発明の実施形態により、システム２００（図２）への入力として提供し、システム２００により処理し、３Ｄプリンタ２２０（図２）によりプリントし、物理的なソリッドモデルを生成し得る。デジタルモデルソリッドモデルは、例えば、建築家Ｊｏｓｅｐｈ（Ｙｏｓｓｉ）  Ｃｏｒｙ博士により設立された賞を獲得した建築スタジオであるＧｅｏｔｅｃｔｕｒａ（登録商標）により設計された建築構造であり得る。ソフトウェアツールを使用して、デジタルモデルを画面にレンダリングすることができ、レンダリングツールは、デジタルモデルを含む３Ｄデータを２Ｄ画面上に投影する。
【０１２３】
図９Ａ及び図９Ｂは一緒になって、本発明の特定の実施形態により動作可能な、三次元物体モデルのプリントを可能にする方法の簡略化されたフローチャート図を形成する。図９Ａ及び図９Ｂの方法は通常、例えば、示されるように適宜順序付けられた以下のステップのうちのいくつか又はすべてを含む。
ステップ８１０：建築構造の建築三次元モデル（Ｒｅｖｉｔ、Ｓｋｅｔｃｈｕｐ、ＤＸＦ／ＤＷＧ、ＶＲＭＬ、ＳＴＬ等）を提供する。
ステップ８２０：シーングラフにロードする。
ステップ８３０：例えば、既知の技法を使用して事前処理を行うべきか否かを判断する。
ステップ８４０：任意選択的に、又は用途に適切な場合、例えば、既知の技法を使用して、面の向き／法線方向の修正を実行する。
ステップ８５０：任意選択的に、又は用途に適切な場合、デローネイ三角形分割等の従来の技法を使用して三角形分割を行う。
ステップ８６０：任意選択的に、又は用途に適切な場合、例えば、従来の技法を使用して丸め／摂動処理を実行する。
ステップ８７０：任意選択的に、又は用途に適切な場合、例えば、従来の技法を使用して、初期分解／分割を多面体／ソリッドに対して実行する。
ステップ８８０：モデル内の非凸多面体毎に、凸分解を行い＿それにより、各非凸多面体から凸多面体の集合を生成する。
ステップ８９０−
2013507679.tif 000004
モデル内の少なくとも１つ（例えば、すべて）の凸多面体に対して、単純で小さな凸形状、例えば、立方体とのミンコフスキー和を計算し、それにより、モデル内の凸多面体毎に膨張凸多面体を生成しようとする。例えば、厳密な計算カーネルを有する市販のＣＧＡＬパッケージを使用することができ、ミンコフスキー和アルゴリズム計算は通常、アルゴリズムの相違をもたらす劣化したジオメトリ及び／又はコンピュータの不十分な数値精度等の様々な制限により失敗する。したがって、通常、最高精度の計算アルゴリズム、例えば、他のカーネルよりも「厳密な計算カーネル」を有するＣＧＡＬが使用される。
ステップ９００：ステップ８９０が、特定の凸多面体に対して失敗すると予測されるか、又は失敗する場合（エラー状況又はプロセスクラッシュ）、そのような凸多面体毎に適応分解（例えば、図１０による）を行う。
ステップ９３０：好ましくは、メモリの容量に達しつつあること（ｍｅｍｏｒｙ  ｂｌｏｗ−ｕｐ）を監視しながら、ステップ８９０において生成された膨張凸多面体を「大きく」結合しようとする。
ステップ９３５：任意選択的に、メモリの容量に達しつつあることが検出される場合、対処ステップを行う。
ステップ９４０：元の凸物体のミンコフスキー和及び元々は非凸物体の結合したミンコフスキー和を適したプリント形式、例えば、ＳＴＬに変換する。
ステップ９５０：３Ｄプリンタを使用して、ＳＴＬ又は他の所望の形式の建築三次元構造をプリントする。
【０１２４】
図１０は、図９Ａ、図９Ｂのステップ９００の実行に適した適応分解方法の簡略化されたフローチャート図である。図１０の方法は通常、例えば、示されるように適宜順序付けられた以下のステップのうちのいくつか又はすべてを含む。
ステップ９６０−
2013507679.tif 000005
モデルが失敗した凸多面体を表すために使用する単純な形状（例えば、三角形）毎に、単純で小さな凸形状、例えば、立方体とのミンコフスキー和を計算し、それにより、膨張三角形を生成する。
ステップ９７０：ステップ１１０において生成された膨張三角形を「小さく」結合しようとし、それにより、中空形状を得る。
ステップ９７５：結合ステップ１２０に失敗した場合、結合に使用されたＣＧＡＬ。
【０１２５】
図９Ａ、図９Ｂ、及び図１０の方法、特にステップ８８０〜９３０は通常、様々な劣化事例を含む建築三次元モデルの処理及び従来の劣化したジオメトリを３Ｄプリンタでプリントできないことの解消に特に適する。建築三次元モデルは、プリントするために縮小し得るが、３Ｄプリンタは、プリンタに依存する最小厚未満の要素をプリントすることができない。
【０１２６】
建築モデルに対するミンコフスキー加算の本実施態様では、多面体と立方体とのミンコフスキー加算は往々にして失敗する。本明細書に記載の適応分解が、失敗のない建築３Ｄモデルのミンコフスキー和の計算に役立つ。この技法は、非中空ジオメトリを中空にレンダリングし得るという点で反直観的であるが、これは建築３Ｄモデルの３Ｄプリントには妥当である。しかし、他の使用には許容不可能であり得る。非中空のジオメトリが要求される場合、結果と元の物体とを結合する追加のステップを実行することにより達成することができる。
【０１２７】
通常、図９Ａ、図９Ｂ、及び図１０の方法により生成されるすべての幾何学的エンティティは、少なくとも最小厚を有する。通常、図９Ａ、図９Ｂ、及び図１０の方法は、小さなギャップの修復及び／又は欠けた面の修復に対して動作可能である。
【０１２８】
これより図９Ａ及び図９Ｂを参照すると、ステップ８１０は、例えば、ソフトウェアツールキットを使用して、建築三次元モデル（Ｒｅｖｉｔ、Ｓｋｅｔｃｈｕｐ、ＤＸＦ／ＤＷＧ、ＶＲＭＬ、ＳＴＬ等）等であるがこれらに限定されない入力を受信し得る。
【０１２９】
法線方向修正及び三角形分割が、図９Ａ及び図９Ｂのステップ８３０の実行に適した技法の例である。
【０１３０】
ステップ８２０は、例えば、シーングラフ技術を使用して、さらに処理するために、例えば、モデルを内部データ構造／リポジトリにロードすることを含み得る。
【０１３１】
ステップ８４０に関して、法線の方向により面の向きを特定することができる。３Ｄモデルは、時には一貫しない法線方向を含むことがあるため、修正が利用される。既知の修正技法があり、Ｒｈｉｎｏ３Ｄソフトウェア等のいくつかの従来のソフトウェアパッケージは、法線方向修正のツールを提供する。
【０１３２】
ステップ８５０に関して、ファイル形式に応じて、必ずしも三角形を使用する必要がないジオメトリのいくつかの表現があり得る。
【０１３３】
形状／ポリゴンは、テセレーション／三角形分割、例えば、例：トーラステセレーションにより別のジオメトリ表現に変換し得る。
【０１３４】
例えば、ファイル形式はポリゴン記述を含むことができ、その場合、各ポリゴンは、従来のポリゴン三角形分割方法を使用して三角形分割することができる。
【０１３５】
ステップ８８０及び８９０に関して、多面体の凸分解及び多面体の３Ｄミンコフスキー加算は、例えば、ＣＧＡＬ（計算幾何学アルゴリズムライブラリ）により提供される機能であり、ＣＧＡＬのマニュアルはオンラインｃｇａｌ．ｏｒｇ／ｍａｎｕａｌにある。
【０１３６】
ステップ８９０に関して、三角形と立方体とのミンコフスキー和が、三角形の頂点に位置決めされた立方体の凸包であることが理解される。通常、ステップ９７０の後、方法は、好ましくは、メモリが容量に達しつつあること等のエラー状況を監視しながら、ステップ８９０において生成された膨張凸多面体を「大きく」結合しようとする（ミンコフスキー加算の出力は、本明細書では「膨張凸多面体」と呼ばれる）。処理された各多面体は通常、処理されたモデル（出力）の部分である。通常、劣化したエンティティ（例えば、ゼロの長さの辺を有する三角形）以外、すべてのエンティティが処理される。
【０１３７】
ステップ９３５において、通常、メモリの容量に達しつつあることが検出される場合、プロセスは終了するか、又は「停止」させられる。
【０１３８】
ステップ９７５において、単純な結合の以下の疑似コードを利用し得る。
ｔｙｐｅｄｅｆＣＧＡＬ：：Ｎｅｆ＿ｐｏｌｙｈｅｄｒｏｎ＿３＜Ｋｅｒｎｅｌ＞Ｎｅｆ＿ｐｏｌｙｈｅｄｒｏｎ；
Ｎｅｆ＿ｐｏｌｙｈｅｄｒｏｎＮ；
ｆｏｒ（ｉｎｔ  ｉ＝０；ｉ＜ｎ；ｉ＋＋）
｛
Ｎｅｆ＿ｐｏｌｙｈｅｄｒｏｎＰ；
ｓｔｄ：：ｉｆｓｔｒｅａｍ  ｉｎ（ｆｎａｍｅ［ｉ］）；
ｉｎ＞＞Ｐ；
Ｎ＝Ｎ．ｊｏｉｎ（Ｐ）；
｝
特定のＣＧＡＬバージョンでの多面体の大きな集合の結合の問題を回避するために、Ｎｅｆ＿Ｐｏｌｙｈｅｄｒｏｎを「リセット」する（ファイルに書き込みし、再び読み取ることにより）以下のコード（Ｗｉｎｄｏｗｓオペレーティングシステムで実行され、ＶＳ２００８を使用してコンパイルされる、ＧＭＰ、ＭＰＦＲライブラリ、Ｅｘａｃｔ＿ｐｒｅｄｉｃａｔｅｓ＿ｅｘａｃｔ＿ｃｏｎｓｔｒｕｃｔｉｏｎｓ＿ｋｅｒｎｅｌカーネルを使用するＣＧＡＬバージョン３．５．１）。
Ｗｒｉｔｅ（Ｎ，”ｔｅｍｐ．ｎｅｆ３”）；
ｄｅｌｅｔｅ  Ｎ；
Ｎ＝ｎｅｗ  Ｎｅｆ＿ｐｏｌｙｈｅｄｒｏｎ；
Ｒｅａｄ（Ｎ，”ｔｅｍｐ．ｎｅｆ３”）；
【０１３９】
ステップ８９０の失敗は、エラー状況又はプロセスクラッシュにより判断し得る。この場合、通常、システムは、例えば、図１０に説明されるようなより単純な形状に分解することを含む適応分解を実行する。
【０１４０】
ステップ９３５に関して、メモリリークは最終的に、性能の極度の減速に繋がり得る。限界において、動作時間はエンドレスになり、メモリ切れによりプログラムがクラッシュする。通常、第１の動作の処理時間が測定され、結果として生成される平均が基準として使用される。動作がこの基準よりもはるかに遅くなる場合、これは問題の指標として機能する。
【０１４１】
図９及び図１０の方法の動作の前後の例が図１１Ａ及び図１１Ｂに示され、これらの図は、図９及び図１０の方法を使用する処理の前後の各壁の平面図である。例えば、縮小後の壁厚は０．１ｍｍであり、これはプリント可能ではない。図１１Ａ及び図１１Ｂでは、立方体の半分サイズが１／２＊１ｍｍであるため、各矢印は０．５ｍｍである。処理後の壁厚は
2013507679.tif 000006
＝０．５＋０．５＋０．１＝１．１ｍｍであり、これはプリント可能である。
【０１４２】
本明細書に示され説明される特定の実施形態の特定の利点は、劣化していない限り、三角形が失敗しないが、特定の実施形態により劣化した三角形が事前認識されて無視され、それにより、失敗状況がなくなることである。
【０１４３】
シーングラフ等の任意の適したデータ構造を、処理中の３Ｄシーンのリポジトリとして使用し得る。データ構造はＤＡＧ（有向非周期グラフ）を含み得る。
【０１４４】
Ｇｒａｆｆｉｔｉ  ３Ｄツールキット及びアプリケーションフレームワークは、本発明の特定の実施形態の実施に有用な３Ｄアプリケーションフレームワークであり、Ｗｉｎｄｏｗｓ  ＯｐｅｎＧＬに基づくアプリケーション及びＳａａＳフレームワークの両方に使用し得る（グラフィックス集約的なアプリケーション用のＣ＋＋ＡＰＩ及びＳａａＳフレームワーク用のＣ＃．ｎｅｔ  ＡＰＩが利用可能である）。ＯｐｅｎＧＬに基づく３Ｄビューア、プロプライエタリスーパーセットファイル形式及びシーングラフ、Ａｕｔｏｄｅｓｋ  Ｒｅｖｉｔ、Ｇｏｏｇｌｅ  Ｓｋｅｔｃｈｕｐ、ＡｕｔｏＣＡＤ  ＤＸＦ／ＤＷＧ、ＳＴＬ、ＶＲＭＬ等の広範囲の関連するファイル形式サポートが、本発明の特定の実施形態の実施に有用であり得る。
【０１４５】
本明細書で使用される立方体のサイズは、ソフトウェアのパラメータであり、通常、プリンタの性能の関数である。例えば、プリンタが少なくとも１ｍｍ厚の壁のみをプリント可能な場合、１ｍｍ×１ｍｍ×１ｍｍの立方体をすべての凸物体に使用し得る。壁厚が０の場合、処理される壁
2013507679.tif 000007
の厚さは１ｍｍになる。換言すれば、縮小後の壁厚＝０ｍｍ（プリントできないことが自明）である場合、本明細書に示され説明される処理後の壁厚
2013507679.tif 000008
＝０．５＋０．５＋０＝１ｍｍである。
【０１４６】
通常、ステップ９７０の後に、ステップ８９０において生成された膨張凸多面体の結合を実行するステップが続く。続けて、システムは、結果として生成された３Ｄプリント可能モデルをＳＴＬ又は他の形式に変換し、所望の形式の３Ｄプリント可能モデルを出力し得る。
【０１４７】
図１２は、本発明の実施形態の実施形態例の一般的に自己説明的な流れ図である。性能を最適化するために、ステップ１２４０でのループ等の時間のかかるループ内の計算は、例えば、従来のスレッドプールパターンを使用して並列計算で計算し得る。特定の実施形態によれば、図１２の方法は、ステップ１２１０が一般的に、図９を参照して上述したステップ８１０〜８２０と同様であり、ステップ１２３０が一般的に、図９を参照して上述したステップ８３０〜８７０と同様であり、ステップ１２４０〜１２５０が一般的に、図９を参照して上述したステップ８８０と同様であり、ステップ１２６〜１２７０が一般的に、図９を参照して上述したステップ８９０と同様であり、ステップ１２８０〜１２９０が一般的に、図９を参照して上述したステップ９００と同様であり、ステップ１３００〜１３１０が一般的に、図１０を参照して上述したステップ９６０と同様であり、ステップ１３２０が一般的に、図１０を参照して上述したステップ９７０と同様であり、ステップ１３３０が一般的に、図９を参照して上述したステップ９３０と同様であり、ステップ１３４０が一般的に、図９を参照して上述したステップ９４０と同様であるように実施し得る。
【０１４８】
図１３は図１２の図の疑似コードである。疑似コードは、例えば、
Ｌｉｓｔ＜Ｐｏｌｙｈｅｄｒａ＞ｍｏｄｅｌ＝Ｉｎｐｕｔ（）
ｃｕｂｅ＝プリンタの性能により立方体を構築（例えば、１×１ｍｍ）
Ｐｒｅｐｒｏｃｅｓｓｉｎｇ（ｍｏｄｅｌ）
ｆｏｒｅａｃｈ（Ｐｏｌｙｈｅｄｒａ  ｐｏｌｙｈｅｄｒａ  ｉｎ  ｍｏｄｅｌ）
Ｌｉｓｔ＜ＣｏｎｖｅｘＰｏｌｙｈｅｄｒａ＞＝ＣｏｎｖｅｘＤｅｃｏｍｐｏｓｉｔｉｏｎ（ｐｏｌｙｈｅｄｒａ）
Ｆｏｒｅａｃｈ  ｃｏｎｖｅｘＰｏｌｙｈｅｄｒａ
ｐｒｏｃｅｓｓｅｄ１＝ＭｉｎｋｏｗｓｋｉＳｕｍ（ｃｏｎｖｅｘＰｏｌｙｈｅｄｒａ＋ｃｕｂｅ）
ｉｆ（ｆａｉｌｅｄ）
ｌｉｓｔ＜Ｔｒｉａｎｇｌｅ／ＳｉｍｐｌｅＯｂｊｅｃｔ＞ｌｉｓｔ＝ＡｄａｐｔｉｖｅＤｅｃｏｍｐｏｓｅ（）
ｆｏｒｅａｃｈ（Ｔｒｉａｎｇｌｅ  ｔｒｉａｎｇｌｅ  ｉｎ  ｌｉｓｔ）
ｐｒｏｃｅｓｓｅｄ２＝ＭｉｎｋｏｗｓｋｉＳｕｍ（ｔｒｉａｎｇｌｅ＋ｃｕｂｅ）
ＥＮＤＦＯＲＥＡＣＨ
Ｕｎｉｏｎ（Ｌｉｓｔ＜ｐｒｏｃｅｓｓｅｄ２＞）
ＥＮＤＩＦ
ＥＮＤＦＯＲＥＡＣＨ
Ｕｎｉｏｎ（Ｌｉｓｔ＜ｐｒｏｃｅｓｓｅｄ１＞）
ＥＮＤＦＯＲＥＡＣＨ
Ｏｕｔｐｕｔ３ＤＰｒｉｎｔａｂｌｅ（ＰｒｏｃｅｓｓｅｄＭｏｄｅｌ，  ＳＴＬ  ｆｏｒｍａｔ）
を含み得る。
【０１４９】
本明細書に示される方法及びシステムは、以下の任意に関連付けられた用途に有用である：建築家、インテリアデザイナー、３Ｄ建築モデルをプリントする必要がある顧客、ＳＴ修復／修正ソフトウェア組織及びサービス提供者、３Ｄプリントサービス、３Ｄプリンタ／ラピットプロトタイピング機組織、並びにＣＡＤソフトウェア提供者。３Ｄモデルを生成する適したソフトウェアを備えた汎用コンピュータ等の任意の適した装置を使用して、本明細書に示され説明される方法への入力を生成し得る。任意の適した３Ｄプリンタを使用して、本明細書に示され説明される方法により生成されるデジタル出力の３Ｄプリントアウトを生成し得る。ネットワークを使用して、そのようなコンピュータ及び／又はそのようなプリンタの間並びに／或いは本明細書に示され説明される機能のうちの任意を有するサーバ、又はクライアントコンピュータ、又はプロセッサの間で通信し得る。任意の適したコンピュータ化されたデータ記憶ユニット、例えば、コンピュータメモリを使用して、本明細書に示され説明される方法への入力、暫定的な作業生産品、又はそれにより生成されるデジタル出力を記憶し得る。本明細書に説明される計算機能のうちの任意又はすべては、プロセッサで実施し得、例えば、従来のプロセッサ内に組み込まれたモジュールを含み得る。
【０１５０】
「必須の」、「要求される」、「必要とされる」、及び「しなければならない」等の用語が、明確にするために本明細書内で説明される特定の実施態様又は用途の文脈の中で行われる実施の選択を指し、代替の移植から限定を意図しないことが理解される。同じ要素が、必須又は要求されるものとして定義されなくてもよく、又はすべてなくすことさえも可能である。
【０１５１】
プログラム及びデータを含む本発明のソフトウェア構成要素が、所望の場合、ＣＤ−ＲＯＭ、ＥＰＲＯＭ、及びＥＥＰＲＯＭを含むＲＯＭ（読み取り専用メモリ）形態で実施し得、又は様々な種類のディスク、様々な種類のカード、及びＲＡＭ等であるがこれらに限定されない任意の他の適したコンピュータ可読媒体に記憶し得ることが理解される。ソフトウェアとして本明細書に説明される構成要素は、代替として、所望の場合、従来の技法を使用して全体的又は部分的にハードウェアで実施してもよい。逆に、ハードウェアとして明細書に説明される構成要素は、代替として、所望の場合、従来の技法を使用して全体的又は部分的にソフトウェアで実施してもよい。
【０１５２】
本発明の範囲内には、とりわけ、本明細書に示され説明された任意の方法のステップのうちの任意又はすべてを任意の適した順に実行するコンピュータ可読命令を搬送する電磁信号、本明細書に示され説明された任意の方法のステップのうちの任意又はすべてを任意の適した順に実行する機械可読命令、機械により実行可能であり、本明細書に示され説明された任意の方法のステップのうちの任意又はすべてを任意の適した順に実行する命令プログラムを明確に具体化する、機械により可読のプログラム記憶装置、本明細書に示され説明された任意の方法のステップのうちの任意又はすべてを任意の適した順に実行するコンピュータ可読プログラムコードを内部に具体化し、且つ／又はそのようなプログラムコードを含む、実行可能コード等のコンピュータ可読プログラムコードを有するコンピュータ使用可能媒体を含むコンピュータプログラム製品、任意の適した順に実行された場合、本明細書に示され説明された任意の方法のステップのうちの任意又はすべてによりもたらされる任意の技術的効果、本明細書に示され説明された任意の方法のステップのうちの任意又はすべてを任意の適した順に、単独で、又は組み合わせて実行するようにプログラムされた任意の適した装置、又はデバイス、又はそのような組み合わせ、プロセッサ及び協働する入力装置及び／又は出力装置をそれぞれ有し、本明細書に示され説明された任意のステップをソフトウェア内で実行するように動作可能な電子装置、コンピュータ又は他の装置を、本明細書に示され説明された任意の方法のステップのうちの任意又はすべてを任意の適した順に実行するように構成させる、ディスク又はハードドライブ等の情報記憶装置又は物理的な記録、例えば、メモリ又はインターネット等の情報ネットワークに事前記録され、ダウンロードされる前又は後に、本明細書に示され説明される任意の方法のステップのうちの任意又はすべてを任意の適した順に実施するプログラム、そのようなプログラムをアップロード又はダウンロードする方法、及びそのようなプログラムを使用する１つ若しくは複数のサーバ及び／又は１つ若しくは複数のクライアントを含むシステム、並びに単独で、又はソフトウェアと併せて本明細書に示され説明される任意の方法のステップのうちの任意又はすべてを任意の適した順に実行するハードウェアが含まれる。本明細書に説明される任意のコンピュータ可読媒体又は機械可読媒体は、非一時的なコンピュータ可読媒体又は機械可読媒体を含むことが意図される。
【０１５３】
本明細書に説明した任意の計算又は他の形態の解析は、適したコンピュータ化された方法により実行し得る。本明細書に説明した任意のステップはコンピュータにより実施し得る。本明細書に示され説明される本発明は、（ａ）コンピュータ化された方法を使用して、本明細書に説明した任意の問題又は任意の目的に対する解決策を識別することであって、解決策は任意選択的に、本明細書に説明した問題又は目的にプラスに影響する本明細書に説明された判断、動作、製品、サービス、又は任意の他の情報のうちの少なくとも１つを含む、識別すること、及び（ｂ）解決策を出力することを含み得る。
【０１５４】
別個の実施形態の文脈の中で説明した本発明の特徴は、単一の実施形態に組み合わせて提供することも可能である。逆に、簡潔にするために、単一の実施形態の文脈の中で、又は特定の順に説明された、方法ステップを含む本発明の特徴は、別個に、又は任意の適した下位組み合わせで、又は異なる順に提供することもできる。「例えば」は、本明細書では、限定を意図しない具体例の意味で使用される。任意の図面に結び付けて示されるデバイス、装置、又はシステムは、実際には、特定の実施形態では単一のプラットフォームに統合することができ、又は光ファイバ、Ｅｔｈｅｒｎｅｔ、無線ＬＡＮ、ホームＰＮＡ、電力線通信、セル電話、ＰＤＡ、Ｂｌａｃｋｂｅｒｒｙ  ＧＰＲＳ、ＧＰＳを含む衛星、又は他のモバイル伝達等であるがこれらに限定されない任意の適切な有線結合又は無線結合を介して結合することができる。本明細書に示され説明された説明及び図面では、システム及びシステムのサブユニットとして説明又は示される機能を方法及び方法内のステップとして提供することもでき、方法及び方法内のステップとして説明又は示される機能をシステム及びシステムのサブユニットとして提供することもできることが理解される。図面内の様々な要素を示すために使用される縮尺は、単なる例示であり、且つ／又は提示を明確にするために適切であり、限定を意図しない。
【図１】
2013507679.tif 000009
【図２】
2013507679.tif 000010
【図３】
2013507679.tif 000011
【図４Ａ】
2013507679.tif 000012
【図４Ｂ】
2013507679.tif 000013
【図４Ｃ】
2013507679.tif 000014
【図４Ｄ】
2013507679.tif 000015
【図５Ａ】
2013507679.tif 000016
【図５Ｂ】
2013507679.tif 000017
【図５Ｃ】
2013507679.tif 000018
【図６】
2013507679.tif 000019
【図６Ａ】
2013507679.tif 000020
【図６Ｂ】
2013507679.tif 000021
【図８】
2013507679.tif 000022
【図９Ａ】
2013507679.tif 000023
【図９Ｂ】
2013507679.tif 000024
【図１０】
2013507679.tif 000025
【図１１Ａ】
2013507679.tif 000026
【図１１Ｂ】
2013507679.tif 000027
【図１２】
2013507679.tif 000028
【図１３】
2013507679.tif 000029
【国際調査報告】
2013507679.tif 000030