図面 (/)

技術 幾何ファセットを使用する直接的なブーリアン演算の方法

出願人 カオシャンウェン
発明者 カオシャンウェン
出願日 2017年2月3日 (3年1ヶ月経過) 出願番号 2018-568271
公開日 2019年9月12日 (6ヶ月経過) 公開番号 2019-526111
状態 未査定
技術分野 イメージ生成 CAD イメージ処理・作成
主要キーワード 内部メッシュ 機械工 中央区画 隣接三角形 CGアプリケーション メッシュ法 ブーリアン演算 点セット
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2019年9月12日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (19)

課題・解決手段

プライマリ幾何オブジェクトおよびそれらのファセットから幾何モデルを作成する目的でコンピュータを使用してブーリアン演算を実行すること。本方法は、ファセットの交線を計算するステップと、交線が通過するファセットを分割するステップと、各ファセットが見えているか隠れているかを判定するステップと、ファセットを再編成して1つまたは複数の幾何オブジェクトを形成するステップと、を含む。本方法は、CADCGソリッドモデリングステムにおいて最も使用されているデータ構造であるCSGおよびB−REPを利用せず、しかしながらCSGおよびB−REPの両方の利点を有し、すなわち実施が容易であり柔軟性が高い。これに加えて、本方法は、ソリッドモデリングシステムおよびサーフェスモデリングシステムのための統合された方法であり、この統合された方法は、編集可能なさまざまなモデルを生成することができる。

概要

背景

コンピュータハードウェアは極めて高度に発展しているため、普通のパーソナルコンピュータ(PC)(Personal Computer)さえも、商用CADCGシステム(通常ではAND、OR、およびNOTを含むブーリアン演算機能を有する)をインストールして動作させる目的に使用することができる。PCの構成要素は、入力装置マウスおよびキーボードなど)、メインマシン画面、およびプリンタを備える。ソフトウェアシステムは、幾何学機能および非幾何学機能を含む。図1は、PCの主要な構成要素を示しており、図2A〜図2Dは、一般的なCAD/CGソフトウェアシステムのアーキテクチャを示している。

ブーリアン演算は、さまざまな幾何形状プライマリ幾何オブジェクトスイープされたオブジェクト、または押し出されたオブジェクトを含む)から複雑なソリッド幾何オブジェクトを構築する一般的なプロセスを、CAD/CG/ソリッドモデリングステムに提供する。Lee氏は、サーフェスを分割する目的にブーリアン演算を適用した(特許文献1参照)。

ブーリアン演算は、プライマリ幾何オブジェクトおよび演算順序を階層的な方法で記録するために空間領域構成法CSG:Constructive Solid Geometry)(これは技術的に実施が容易である)に依拠することができ、これに対して境界表現(B−REP:Boundary Representation)は、より多くの幾何オブジェクトタイプ(延長されたジオメトリなど)をサポートする、より柔軟な方法とみなされる(非特許文献1参照)。

本発明は、5つのブーリアン演算コマンド、すなわち、結合、交差、除外、差、分割を提示し、これらは、レンダリング機能に使用される幾何ファセットから分解された三角形に対して直接機能し、データ構造である空間領域構成法または境界表現を必要としない。本発明において定義されるデータ構造は、少数の単純なクラスであり、本発明において組み込まれるアルゴリズムは、簡潔であり実施が容易であり、5つのコマンドによってユーザは、幾何オブジェクトのタイプを選択することによってのみならず、幾何オブジェクトのファセットを定義することによっても、幾何モデルを作成することができる。図3は、6つのファセットを有する直方体と球とを示しており、異なるファセットによって異なる結果になる。

5つのコマンドは、ソリッドモデリングおよびサーフェスモデリング用に設計されているが、本発明に組み込まれているサーフェストリムコマンドは、サーフェスモデリングのための代替方法を提供し、ファセットが隠れているかをさまざまな方法で識別する。

本発明は、CSGおよびB−REPとは異なるデータ構造およびアルゴリズムを提示し、本発明に組み込まれているアルゴリズムには、三角形と三角形を交差させる、サブ交線(sub-intersection line)によって三角形を分割する、ファセットが隠れているかを識別する、三角形を再編成して幾何モデルを形成する、が含まれる。

概要

プライマリ幾何オブジェクトおよびそれらのファセットから幾何モデルを作成する目的でコンピュータを使用してブーリアン演算を実行すること。本方法は、ファセットの交線を計算するステップと、交線が通過するファセットを分割するステップと、各ファセットが見えているか隠れているかを判定するステップと、ファセットを再編成して1つまたは複数の幾何オブジェクトを形成するステップと、を含む。本方法は、CAD/CG/ソリッドモデリングシステムにおいて最も使用されているデータ構造であるCSGおよびB−REPを利用せず、しかしながらCSGおよびB−REPの両方の利点を有し、すなわち実施が容易であり柔軟性が高い。これに加えて、本方法は、ソリッドモデリングシステムおよびサーフェスモデリングシステムのための統合された方法であり、この統合された方法は、編集可能なさまざまなモデルを生成することができる。

目的

本発明は、製品の設計、製造、およびシミュレーションにおいて幅広く使用されているコンピュータ支援設計(CAD:Computer Aided Design)、コンピュータグラフィックス(CG:Computer Graphics)、ソリッドモデリング(Solid Modeling)システム、およびサーフェスモデリング(Surface Modeling)システムに、プライマリ幾何オブジェクトから3次元幾何モデルを構築するための直接的なブーリアン演算法を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

コンピュータシステム内で実施されかつコンピュータによって動作する、幾何ファセットを使用する直接的なブーリアン演算を実行する方法であって、レンダリングファセットを、隣接三角形を含む拡張された三角形マッピングするステップと、2つの最小バウンディングボックスが重なるかを検出し、エッジと三角形の交差を実行することによって、交線の始点を保持する最初の三角形ペアを探索するステップと、隣接する三角形を探索することによって前記交線が閉じる、または、すべての三角形が横切られるまで前記交線を延長するステップと、交線が通過する三角形を分割するステップと、ファセットを再編成し、ブーリアン演算のタイプに従って三角形を削除および維持するステップと、拡張された三角形をレンダリングファセットにマッピングするステップと、を含む方法。

請求項2

結合、交差、除外、差および分割を含む任意のブーリアン演算が、データ構造である空間領域構成法CSG)および境界表現(B−REP)を用いずに、幾何オブジェクトのレンダリングファセットを使用して新しい幾何オブジェクトを作成し、その結果がただちにレンダリング三角形にマッピングされる、請求項1に記載の方法。

請求項3

結合、交差、除外、差および分割を含む任意のブーリアン演算が、データ構造CSGおよびB−REPを用いて、幾何オブジェクトのレンダリングファセットを使用して新しい幾何オブジェクトを作成し、その結果がただちにレンダリング三角形にマッピングされる、請求項1に記載の方法。

請求項4

交点が正確であり、かつ、交線が近似的な曲がったエッジラインではないように、交線を構築するステップが、2つのファセットが重ならないかを前記最小バウンディングボックスを使用して検出し、エッジと三角形の交差の計算を実行する、請求項1に記載の方法。

請求項5

エッジと三角形の交差の直接的な計算が、点が三角形のエッジ上であるかを確認することに置き換えられるように、交点を探索するステップが、エッジと三角形の交差を計算し、かつ、隣接するファセットを採用する、請求項1に記載の方法。

請求項6

三角形を分割するステップが、すべての3次元三角形およびそのすべてのサブ交線を2次元平面上に投影し、かつ、修正されたWatson法によってドロネー2Dメッシュを構築し、前記修正されたWatson法においては、たとえ前記サブ交線が凸状ではないときにも三角形が異なる区画に分割される、請求項1に記載の方法。

請求項7

Aに属する三角形Taが幾何オブジェクトBと境界を接しているかをチェックするステップが、t−バッファを利用し、さらに、Taの重心cを計算するステップと、前記重心cを通過しかつTaの法線に沿った線l:p=c+t*Nを構築するステップと、オブジェクトBの各三角形Tbについて、lが内点pにおいてTbと交差するかをチェックしてtをt−バッファに追加するステップと、t−バッファの中の負のtのサイズが正のtのサイズに等しいときにTaを「隠れている」に設定するステップと、を含む、請求項1に記載の方法。

請求項8

サーフェスパッチトリムするときに三角形が「隠れている」かどうかをチェックするステップが、関与するパッチのBlOpTriangleSetの正則点のm_IDを0に設定し、前記パッチの交線の点のm_IDを、前記線とトリム輪郭が同じ方向であるかに応じて昇順または降順に設定するステップと、各三角形のメンバーm_Pointsのm_IDに従って、各三角形が境界三角形であるかを判定するステップと、各境界三角形について、前記境界三角形が前記トリム輪郭の左側であるか右側であるかを判定し、境界三角形ではない隣接三角形を「左」または「右」に設定するステップと、をさらに含む、請求項1に記載の方法。

請求項9

結合、交差、除外、差または分割などのブーリアン演算が、その演算結果を構築するために、見えているファセット、または、隠れているファセット、または、見えているファセットおよび隠れているファセットの混合、を維持する、請求項1に記載の方法。

請求項10

ブーリアン演算結果が、表示されるようにレンダリングデータ直接マッピングされ、かつ、次のブーリアン演算にデータを提供する、請求項1に記載の方法。

請求項11

幾何オブジェクトのレンダリングファセットを使用する直接的なブーリアン演算を実行する、ハードウェアおよびソフトウェアからなるコンピュータシステムであって、前記システムが、データおよびコマンドを入力するための入力装置と、ユーザインタフェース、幾何オブジェクト、およびさらなるデータを表示する表示装置と、幾何データと、ソフトウェアシステムを構成する命令とを記憶する媒体と、前記命令を部分的または完全に埋め込んでいるマイクロチップまたは集積回路と、計算を実行するプロセッサと、を有する前記コンピュータ、を備えており、前記計算が、スイープされた幾何オブジェクトおよび押し出された幾何オブジェクトを含むプライマリ幾何オブジェクトを作成する、修正する、または、ロードして、前記プライマリ幾何オブジェクトを、前記コンピュータの入力装置によってさまざまな位置または向きに再配置するステップと、前記幾何オブジェクトの2つを選択するステップと、レンダリングファセットを、隣接三角形を含む拡張された三角形にマッピングするステップと、2つの最小バウンディングボックスが重なるかを検出することによってと、エッジと三角形の交差を実行することによって、交線の始点を保持する最初の三角形ペアを探索するステップと、隣接する三角形を探索することによって前記交線が閉じる、またはすべての三角形が横切られるまで、前記交線を延長するステップと、交線が通過するファセットを分割するステップと、ファセットを再編成し、ブーリアン演算のタイプに従ってファセットを削除、維持、およびマージするステップと、拡張された三角形をレンダリング三角形にマッピングするステップと、からなる、コンピュータシステム。

請求項12

結合、交差、除外、差および分割を含む任意のブーリアン演算が、データ構造であるCSGおよびB−REPを用いずに、幾何オブジェクトのレンダリングファセットを使用して新しい幾何オブジェクトを作成し、その結果がただちにレンダリングデータにマッピングされる、請求項11に記載のシステム。

請求項13

結合、交差、除外、差および分割を含む、任意のブーリアン演算が、データ構造CSGおよびB−REPを用いて、幾何オブジェクトのレンダリングファセットを使用して新しい幾何オブジェクトを作成し、その結果がただちにレンダリングデータにマッピングされる、請求項11に記載のシステム。

請求項14

交点が正確であり、かつ、交線が近似的な曲がったエッジラインではないように、交線を構築するステップが、2つのファセットが重ならないかを前記最小バウンディングボックスを使用して検出し、エッジと三角形の交差の計算を実行する、請求項11に記載のシステム。

請求項15

エッジと三角形の交差の直接的な計算が、点が三角形のエッジ上であるかを確認することに置き換えられるように、交点を探索するステップが、エッジと三角形の交差を計算し、かつ、隣接する三角形を採用する、請求項11に記載のシステム。

請求項16

三角形を分割するステップが、すべての3次元三角形およびそのすべてのサブ交線を2次元平面上に投影し、かつ、ドロネー2Dメッシュを構築し、前記ドロネー2Dメッシュにおいては、たとえ前記サブ交線が凸状ではないときにも三角形が異なる区画に分割される、請求項11に記載のシステム。

請求項17

Aに属する三角形Taが幾何オブジェクトBと境界を接しているかをチェックするステップが、t−バッファを利用し、さらに、Taの重心cを計算するステップと、前記重心cを通過しかつTaの法線に沿った線l:p=c+t*Nを構築するステップと、オブジェクトBの各三角形Tbについて、lが内点pにおいてTbと交差するかをチェックしてtをt−バッファに追加するステップと、t−バッファの中の負のtのサイズが正のtのサイズに等しいときにTaを「隠れている」に設定するステップと、を含む、請求項11に記載のシステム。

請求項18

サーフェスパッチをトリムするときに三角形が「隠れている」かどうかをチェックするステップが、関与するパッチのBlOpTriangleSetの正則点のm_IDを0に設定し、前記パッチの交線の点のm_IDを、前記線とトリム輪郭が同じ方向であるかに応じて昇順または降順に設定するステップと、各三角形のメンバーm_Pointsのm_IDに従って、各三角形が境界三角形であるかを判定するステップと、各境界三角形について、前記境界三角形が前記トリム輪郭の左側であるか右側であるかを判定し、境界三角形ではない隣接三角形を「左」または「右」に設定するステップと、をさらに含む、請求項11に記載のシステム。

請求項19

結合、交差、除外、差または分割などのブーリアン演算が、その演算結果を構築するために、見えているファセット、または、隠れているファセット、または、これら2つのタイプの幾何ファセットの混合、を維持する、請求項11に記載のシステム。

請求項20

ブーリアン演算結果が、表示されるようにレンダリングデータに直接マッピングされ、かつ、次のブーリアン演算にデータを提供する、請求項11に記載のシステム。

技術分野

0001

本発明は、製品の設計、製造、およびシミュレーションにおいて幅広く使用されているコンピュータ支援設計CAD:Computer Aided Design)、コンピュータグラフィックスCG:Computer Graphics)、ソリッドモデリング(Solid Modeling)システム、およびサーフェスモデリング(Surface Modeling)システムに、プライマリ幾何オブジェクトから3次元幾何モデル構築するための直接的なブーリアン演算法を提供する。機械工業、カルチャースポーツなど、幾何形状が存在するあらゆるところでCAD/CGアプリケーションを導入することができる。

背景技術

0002

コンピュータハードウェアは極めて高度に発展しているため、普通のパーソナルコンピュータ(PC)(Personal Computer)さえも、商用CAD/CGシステム(通常ではAND、OR、およびNOTを含むブーリアン演算機能を有する)をインストールして動作させる目的に使用することができる。PCの構成要素は、入力装置マウスおよびキーボードなど)、メインマシン画面、およびプリンタを備える。ソフトウェアシステムは、幾何学機能および非幾何学機能を含む。図1は、PCの主要な構成要素を示しており、図2A〜図2Dは、一般的なCAD/CGソフトウェアシステムのアーキテクチャを示している。

0003

ブーリアン演算は、さまざまな幾何形状(プライマリ幾何オブジェクト、スイープされたオブジェクト、または押し出されたオブジェクトを含む)から複雑なソリッド幾何オブジェクトを構築する一般的なプロセスを、CAD/CG/ソリッドモデリングシステムに提供する。Lee氏は、サーフェスを分割する目的にブーリアン演算を適用した(特許文献1参照)。

0004

ブーリアン演算は、プライマリ幾何オブジェクトおよび演算順序を階層的な方法で記録するために空間領域構成法CSG:Constructive Solid Geometry)(これは技術的に実施が容易である)に依拠することができ、これに対して境界表現(B−REP:Boundary Representation)は、より多くの幾何オブジェクトタイプ(延長されたジオメトリなど)をサポートする、より柔軟な方法とみなされる(非特許文献1参照)。

0005

本発明は、5つのブーリアン演算コマンド、すなわち、結合、交差、除外、差、分割を提示し、これらは、レンダリング機能に使用される幾何ファセットから分解された三角形に対して直接機能し、データ構造である空間領域構成法または境界表現を必要としない。本発明において定義されるデータ構造は、少数の単純なクラスであり、本発明において組み込まれるアルゴリズムは、簡潔であり実施が容易であり、5つのコマンドによってユーザは、幾何オブジェクトのタイプを選択することによってのみならず、幾何オブジェクトのファセットを定義することによっても、幾何モデルを作成することができる。図3は、6つのファセットを有する直方体と球とを示しており、異なるファセットによって異なる結果になる。

0006

5つのコマンドは、ソリッドモデリングおよびサーフェスモデリング用に設計されているが、本発明に組み込まれているサーフェストリムコマンドは、サーフェスモデリングのための代替方法を提供し、ファセットが隠れているかをさまざまな方法で識別する。

0007

本発明は、CSGおよびB−REPとは異なるデータ構造およびアルゴリズムを提示し、本発明に組み込まれているアルゴリズムには、三角形と三角形を交差させる、サブ交線(sub-intersection line)によって三角形を分割する、ファセットが隠れているかを識別する、三角形を再編成して幾何モデルを形成する、が含まれる。

0008

米国特許第6,307,555号明細書(2001年10月)、Lee、345/423

先行技術

0009

"Boolean Set Operations on Non-Manifold bounding Representation Objects", E. Gursoz et al., Computer-Aided Design 23 (1991) Jan./Feb. No. 1 London, GB
"Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopest", D.F. Watson, The Computer Journal 24 (2) 1981

発明が解決しようとする課題

0010

本発明は、ブーリアン演算を実行するための一連のデータ構造および一連のアルゴリズムを提供し、複雑な幾何モデルを構築することを目的とする。

課題を解決するための手段

0011

本発明は、ブーリアン演算を実行するための一連のデータ構造および一連のアルゴリズムを提供し、これらは複雑な幾何モデルを構築するために使用され、コンピュータハードウェアおよびレンダリング機能(OpenGLライブラリなど)によってレンダリングデータとして使用される幾何ファセットから分解された三角形に対して直接機能する。幾何形状(例えば球、円錐円柱、直方体、三角形のファセット、押し出されたオブジェクトまたはスイープされたオブジェクト、サーフェスパッチ)は、表示するために三角形に分けられてセット(TriangleSetと称する)を構築する。ブーリアン演算を実行するために2つの幾何形状を選択すると、隣接する三角形がTriangleSet内の各三角形に追加され、形状それぞれのための別のセットBlOpTriangleSetが形成される。

0012

本発明に記載されているブーリアン演算の第2のステップでは、三角形セットの間で交線を探索して構築する。このステップでは、最初に、交差する三角形の最初のペアを見つける。本システムは、各三角形に対して、軸線に合わせた最小バウンディングボックス(bounding box)を構築し、2つのバウンディングボックスが重なっているかをチェックして、エッジと三角形の交差を計算する必要があるかを判定する。エッジと三角形の(1つまたは複数の)交点が三角形の内側にあるとき、本システムは探索タスクを完了し、点データを交線セットに格納する。

0013

現在の交線を延長するため、本方法は、隣接する三角形をトレースし、交線が閉じるまでエッジと三角形の交点を計算する。

0014

本発明に記載されているブーリアン演算の第3のステップでは、三角形を分割する。交線の各線分は2つの三角形を参照し、これらの三角形それぞれが、三角形を3つ以上のより小さい三角形に分割する1つまたは複数の線分を含む少なくとも1本のサブ交線を有する。三角形を分割した後、元の三角形が除去され、分割された小さい三角形がBlOpTriangleSetに追加される。

0015

本発明に記載されているブーリアン演算の第4のステップでは、各三角形が隠れているか見えているかを判定する。ある三角形が別の三角形によって囲まれている場合、その三角形は隠れている。三角形が見えているとは、その三角形が別のオブジェクトの外側であることを意味する。

0016

本発明に記載されているブーリアン演算の第5のステップでは、三角形を再編成する。三角形のいくつかを除去しなければならず、三角形のいくつかをまとめる必要があり、再編成には5つのケースがある。

0017

本発明に記載されているブーリアン演算の最後のステップでは、BlOpTriangleSetをTriangleSetにマッピングする。

0018

このサーフェストリムコマンドのプロセスも、6つのステップを含む。最初に、本システムは、サーフェスをBlOpTriangleSetにマッピングし、そのトリム輪郭の1つを押し出された形状にマッピングして、BlOpTriangleSetを形成する。ステップ2、ステップ3、およびステップ6は、ブーリアン演算のステップと同じである。ステップ4では、三角形がトリム輪郭の左側であるか右側であるかをチェックし、それを維持する必要があるかを判定する。再編成機能(ステップ5)は、システムがサーフェスをトリムするときに左側の三角形のみ、または右側の三角形のみを削除する。

図面の簡単な説明

0019

図1は、パーソナルコンピュータの主要な構成要素を示しており、これらは、一般的にはメインマシン、入力装置(マウスおよびキーボードを含む)、ディスプレイ、およびプリンタを含む。高度に発展したCAD/CGシステムは、PCマシン上で動作することができる。
図2A、図2B、図2Cおよび図2Dは、CAD/CG/幾何モデリングシステムがブーリアン演算およびサーフェストリムを使用して幾何モデルを構築するためのソフトウェアアーキテクチャを示している。
図3は、ファセットの元の幾何オブジェクトのタイプおよびサイズがたとえ同じであっても、異なるファセットがさまざまな結果をもたらす状況を表している。左側の例は、より少ないファセットを有し、右側は、より多くのファセットを有する。これらの例では、ブーリアン交差演算が直方体および球に対して機能している。
図4は、幾何ファセットを使用する直接的なブーリアン演算(immediate Boolean operation)の流れ図である。
図5は、三角形が3つの隣接三角形を有することを示している。三角形とその2つの頂点が与えられると、ソリッドモデルにおいてただ1つの隣接する三角形が存在する。
図6Aおよび図6Bは、2つの最小バウンディングボックスが重ならない場合と、2つのバウンディングボックスが互いに重なる場合を示している。各三角形は仮想的に最小バウンディングボックスを有する。2つのボックスが重ならない場合、それら2つのボックスに含まれている三角形は交差しない。ボックスが重なる場合、エッジと三角形の交差を計算する必要がある。
図7A、図7Bおよび図7Cは、エッジと三角形が交差する3つの場合、すなわち、交点が三角形の内側である場合、交点が三角形のエッジ上に位置する場合、交点が三角形の頂点である場合、を示している。
図8A、図8B、図8Cおよび図8Dは、探索候補セットを示している。探索候補セットによってシステムは、エッジと三角形の計算を行うことにより次の三角形を横切って交線を延長することができる。塗りつぶされている三角形は、互いに交差する三角形の最後のペアであり、塗りつぶされていない三角形は、データ構造Triangle3dExのメンバーm_NeigTriによって参照されており、塗りつぶされていない三角形は、交線を構築するときに三角形の最小のセットを探索するようにシステムをガイドする。セットは、1つの三角形または2つの三角形を含む、または三角形を含まない。
図9A、図9B、図9Cおよび図9Dは、交線の4つの例を示している。直方体が球と交差し、球が異なるファセット数を有する。
図10A、図10Bおよび図10Cは、サブ交線の3つの例を、濃い色で示している。図10Aは1本のサブ交線、図10Bは2本のサブ交線、図10Cは1本のサブ交線を有する。
図11A、図11B、図11Cおよび図11Dは、三角形がサブ交線によって一連の三角形に分割されている4つの例を示している。
図12A、図12B、図12C、図12D、図12E、図12F、図12Gおよび図12Hは、メッシュに各交点が段階的に挿入されるドロネー(Delaunay)メッシュシーケンスを示している。
図13は、図12A乃至図12Hのシーケンスを作成した、ドロネーメッシュWatson法(Delaunay mesh Watson method)の流れ図である。
図14は、三角形とそのドロネーメッシュを示している。元の三角形が除去され、後の計算用にドロネーメッシュのみが維持される。
図15は、t−バッファを示している(tは負または正)。t−バッファ内で負のtと正のtのサイズが釣り合っている場合、関与する三角形は、別のオブジェクトによって閉じられており隠れている。
図16A〜図16Eは、直方体と球を使用して行われるブーリアン演算の5つの例を示している。図16Fおよび図16Gは、2つのブーリアン演算(結合および除外)の結果の内部メッシュを示している。
図17は、閉じたサーフェス(変形した球)が輪郭線によってトリムされ、2つの孔を生成する状況を示している。
図18は、押し出されたサーフェス(管)が輪郭線によってトリムされ、孔を作成する例を示している。

実施例

0020

本発明は、幾何オブジェクトをレンダリングするためにファセットを格納するPoint3D、Triangle3D、Triangle3dSetを継承するデータ構造Point3dEx、Triangle3dEx、およびBlOpTriangle3dSetを定義する。システムは、ブーリアン演算を実行するとき、レンダリングファセットをBlOpTriangle3dSetにマッピングし、その後のすべてのプロセスは、BlOpTriangle3dSetのメンバーおよび属性焦点をあてる。図4は、本発明によって行われるブーリアン演算の主な手順を記述した流れ図である。システムは、ブーリアン演算が完了した後、BlOpTriangle3dSetに格納された結果をレンダリングファセットにマッピングする。

0021

<レンダリングのための幾何ファセット>
CADシステムは、幾何オブジェクト(球、円錐、直方体、円柱、押し出されたオブジェクト、またはスイープされたオブジェクトなど)を表すためにファセットをレンダリングする。ファセットは3つ以上の点から構成される。ファセットは、通常では計算を容易にするため三角形に分解される。直方体は、12の三角形に分解される6つのファセットを有する。球は、24の三角形を構成する18のファセットを有することができる。球は、1000より多くのファセットおよび三角形を使用してレンダリングすることもできる。図3は、さまざまなファセットを使用してレンダリングされた球を示している。本方法では、幾何オブジェクトをレンダリングする目的で三角形セットのデータ構造を記述するためにTriangle3dSetを使用し、Triangle3dSetは、2つの属性、すなわち3次元点セットおよび三角形セットを含み、この場合、Triangle3dがPoint3dを参照する。
class Triangle3dSet
{
DataSet m_PointSet;
DataSet rn_TriangleSet;
};
class Triangle3d
{
Point3d *m_Points[3];
};
class Point3d
{
DataTypeI m_X, m_Y, m_Z;
};

0022

<ブーリアン演算のための三角形>
本発明に記載されているブーリアン演算法では、3つの主要クラス、すなわちBlOpTriangleSet、Triangle3dEx、およびPoint3dExを定義する。
class BlOpTriangleSet
{
DataSet m_PointSet;
DataSet m_TriangleSet;
};
class Point3dEx : Point3d
{
DataTypell m ID; //位置および順序インデックス
DataTypelll m_X, m_Y, m_Z; //DataTypelllはDataTypelと異なっていてよい
};
class Triangle3dEx : Triangle3d
{
Point3dEx *m_Points[3];
DataTypell m_ID;
Plane m_Plane;
DataTypelV m_Normal[3];
Triangle3dEx *m_NeigTri[3]; //隣接する三角形
};

0023

DataTypellは、int、long、unsigned long、または他の整数型とすることができる。Datalypelllは、浮動小数点数データ型(float、double、さらにはlong doubleなど)である。

0024

クラスTriangle3dExは、各三角形が3つの隣接する三角形を有しうることを指定し、すべての三角形それぞれのただ1つのコピーがBlOpTriangleSetに格納される。直方体を例に挙げれば、最も単純な場合、直方体は12の三角形を有し、たとえ各三角形が3つの隣接三角形を有してもBlOpTriangleSetは依然として合計で12の三角形を格納する。

0025

技術的には、Triangle3dは属性m_Normalを有することができる。DataTypelとDataTypelVが同じ型(例えばdouble)である場合、属性m_Normalを継承することができる。

0026

<データのマッピング>
Triangle3dSetをBlOpTriangleSetにマッピングするプロセスでは、レンダリング像(rendering statue)からの点セットおよび三角形セットをコピーし、デフォルトの属性を与える。データのマッピングは、以下の手順を含む。
1)Triangle3dSetからの点をBlOpTriangleSetにコピーし、このとき同じ点が存在しないようにする。
2)Triangle3dSetからの三角形をBlOpTriangleSetにコピーする。
3)BlOpTriangleSetの中の各三角形について、その隣接する三角形を設定する。
4)BlOpTriangleSetの中の各三角形について、法線を計算し、平面方程式確立する。

0027

注1: 2点a,bが与えられたとき、|xa−xb|<εかつ|ya−yb|<ε(εは正の浮動小数点数、例えば5.0e−16)ならば、bはaと同じである。

0028

注2:レンダリングデータからの点をBlOpTriangleSetにマッピングするとき、システムは、BlOpTriangleSetの中に同じ点が存在するかをチェックする。

0029

注3:三角形(3つの点を有する)は、数式がax+by+cz+d=0である平面を定義し、クラスPlaneは、その平面を4つの数の配列(m_ABCD[4]など)として内部的に記録する。

0030

注4:三角形は、その3点が同じでない場合、つねに有効な法線を有する。たとえ三角形がm_ABCDに関連していても、個別にコピーすることによって明確性が高まり、後から扱うときにも容易である。

0031

注5: すべての三角形は3つのエッジを有し、重複する点が存在しないとき、その三角形はソリッドモデルにおいて3つの隣接する三角形を有する。図5は一例を示している(塗りつぶされた三角形およびその3つの隣接三角形)。サーフェストリムのためのサーフェスパッチに関与するとき、三角形の1つまたは2つの隣接三角形がヌルであってもよい。

0032

<第1の交点>
すべての三角形は3つの頂点を有し、これらの頂点は最小バウンディングボックスを定義する。本方法では、軸線に合わせた最小バウンディングボックスのコンセプトを採用した。

0033

三角形のペアが与えられたとき、それらのバウンディングボックスが重ならない場合、2つの三角形は交点を持たない。そうでない場合、本方法ではエッジと三角形の交差の計算を実行する。

0034

三角形Taのエッジが、三角形Tbによって定義される平面と交差し、かつ交点petがTbの内側である場合、petは第1の交点である。petがTbの外側である場合、ペアにおける三角形の位置を交換し((Ta,Tb)を(Tb,Ta)に変更する)、エッジと三角形の交差の計算を行う。

0035

三角形Taのi番目(i∈[0,2])のエッジ(その式はp=pi+t*(p(i+1)%3−pi)である)と、三角形Tbによって定義される平面(その式はax+by+cz+d=0である)とが与えられたとする。2つの式が解を持つ場合、エッジは平面と交差する。エッジと平面の交点が三角形Tbの内側である場合、その点はエッジと三角形の交点である。

0036

<交線の延長>
本方法では、交点をPntEgTriとして記録するためのデータ構造を定義する。
class PntEgTri
{
Triangle3dEx *m_Tri0, *m_Tri1;
DataTypell m_Edgelndex;
DataTypell m_PointPosi;
Point3dEx m_Point;
Point3dEx *m_PntGlobalIndexA, *m_PntGlobalIndexB;
};

0037

PntEgTri(簡潔にはpet)は、三角形における交点の位置に従って、図7A〜図7Cに示した3つのカテゴリ分類することができる。
1)最も一般的なケースは、エッジと三角形が交差する場合であり、petは、三角形Taのエッジ上、かつ三角形Tbの内側に位置する。
2)エッジとエッジが交差する場合、petは、三角形Taのエッジ上、かつ三角形Tbのエッジ上に位置する。
3)エッジと頂点が交差する場合、petは、三角形Taのエッジ上、かつ三角形Tbの頂点に位置する。

0038

交線を延長するため、本システムでは、次の(1つまたは複数の)隣接する三角形を認識し、交線が閉じる、またはすべての三角形が横切られるまで、エッジと三角形の交差をチェックする。

0039

<サブ交線>
交線は一連の三角形を通過し、各三角形を複数の区画(partition)に分割する。三角形の内側の交線の線分がサブ交線を構成する。図10A〜図10Cは、3つの例を示しており、濃い色の線がサブ交線である。実際には、三角形は、0本、1本、2本、または3本のサブ交線を有することができる。

0040

次のアルゴリズムは、少なくとも1本のサブ交線を有する三角形への有効な参照を得る方法を示している。

0041

各交線において、
各交点について、三角形の参照を得る(m_Tri0,m_Tri1)
三角形ペアの各三角形において、その三角形が分割されない場合、
各交線において、
サブ交線を探索して構築する。

0042

有効な三角形と交線が与えられたとき、petがその三角形のサブ交線に属するかを判定するため、本方法は以下をチェックする。
1)petが三角形のエッジ上であるか
2)またはpetが三角形の内側であるか
3)またはpetが三角形の頂点に等しいか

0043

<三角形の分割>
一連のサブ交線が与えられたとき、三角形を分割するため、本方法は、
1)重複しているpetを除去する。隣り合うpetが同じである場合、本方法は1つのコピーのみを維持する。
2)最後のpetの位置を識別する。各petが三角形のどのエッジ上に位置しているかをチェックする。
3)三角形の上側区画、下側区画、および中央区画に分割する(適用可能な場合)。

0044

三角形の区画を表す平面上の一連の点が与えられたとき、その平面を三角形のグループに分解するため、本方法では、1981年に公開されたドロネー2DメッシュWatson法を修正する[非特許文献2]。

0045

ドロネー2Dメッシュは、3つのデータセット、すなわち、生成された三角形を保持する三角形セットと、直前に削除された三角形を格納する削除三角形セットと、削除三角形セットのアウトラインを記録するポリゴン、を有する。

0046

修正されたドロネー2Dメッシュ法は、以下のステップを含む。
1)サブ交線と三角形の頂点を結ぶアウトライン点列を構築する(適用可能な場合)。
2)この3次元点列を、平面の向きに従って2次元点列にマッピングする。
3)4つの点を加えて、2次元の点すべてを囲む、より大きいバウンディングボックスを形成する。
4)バウンディングボックスの1本のダイアログライン対角線)が、バウンディングボックスを2つの三角形に分割するものと想定し、これらの三角形を三角形セットに追加する。
5)境界上の点を除くすべての点を三角形セットに挿入する。

0047

a)各点について、三角形セットの中の三角形の外接円がその点を含むか、または最後の線分が三角形を通過するか、三角形セットの中のすべての三角形をチェックする。条件が満たされる場合、その三角形を三角形セットから消去し、削除三角形セットに追加する。

0048

b)削除済み三角形セットを使用してポリゴンを拡張し、削除済み三角形セットをただちにクリアする。

0049

c)ポリゴンを使用して三角形セットを生成し、それらを三角形セットに追加する。

0050

図12A〜図12Hは、ドロネー2Dメッシュシーケンスを示している。

0051

<分割された三角形の削除>
上のステップでは、分割された三角形にはマークが付される。すべての三角形が横切られた後、本方法は、マークの付いた三角形を削除する。図14は、削除結果を示している。

0052

<隠れているファセット>
2つの三角形セットA,Bが与えられたとき、AがBの三角形Tbと境界を接している場合、Tbは隠れており、BがAの三角形Taと境界を接している場合、Taは隠れている。

0053

三角形TがオブジェクトOと境界を接しているかをチェックするため、本発明では以下のステップを使用する。
1)三角形Tの重心cを計算する。
2)線l:p=c+t*Nを構築する。この線は重心を始点とし三角形Tの法線Nに沿って延びる。
3)オブジェクトOの各三角形Toについて、線と平面の交点を計算する。三角形Toの内側である有効な交点petが存在する場合、重心cおよびpetによって決まるtを計算し、tを深さバッファ(bufferT)に追加する。
4)butterTに格納されている負のtおよび正のtのサイズをチェックする。2つのサイズが等しい場合、三角形Tは境界を接しており隠れている。

0054

サーフェストリムを実行するとき、本システムは、三角形が隠れているかを判定するため以下の手順を呼び出す
1)関与するサーフェスパッチのBlOpTriangleSetの各Point3dExのメンバーm_IDを0に設定する。
2)このパッチの交線のPoint3dExのm_IDを、この線とトリム輪郭が同じ方向である(例えば両方が左回りである)かに応じて昇順または降順にマークする。
3)各三角形のメンバーm_Pointsのm_IDに従って、各三角形が境界三角形であるかを判定する。
4)各境界三角形について、その三角形がトリム輪郭の左側であるか右側であるかを判定し、境界三角形ではない隣接三角形を「左」または「右」に設定する。

0055

<ファセットの再編成>
本発明は、5種類のブーリアン演算を記載しており、ブーリアン演算それぞれが異なる再編成手順を有する。

0056

結合演算(この演算は論理的にはORである)は、2つのソリッド幾何オブジェクトを結合して新しいオブジェクトを生成し(通常では、外側から見て隠れている区画を破棄し、見えている区画を維持する)、以下の手順を有する。
1)オブジェクトAの隠れている三角形を削除する。
2)オブジェクトBの隠れている三角形を削除する。
3)オブジェクトAの三角形とオブジェクトBの三角形をマージする。

0057

交差演算(この演算は論理的にはANDである)(2つの幾何オブジェクトの共通部分(public section)を使用してソリッド幾何オブジェクトを作成し、共有される共通部分の外側のAおよびBの区画を破棄する)は、以下の手順を有する。
1)オブジェクトAの隠れていない三角形を削除する。
2)オブジェクトBの隠れていない三角形を削除する。
3)オブジェクトAの三角形とオブジェクトBの三角形をマージする。

0058

除外演算(2つの幾何オブジェクトの共通部分を除去し、共有されていない区画を保持することによって、ソリッド幾何オブジェクトを構築する)は、以下の手順を有する。
1)オブジェクトAの隠れている三角形をバッファbufferAにコピーする。
2)オブジェクトAから、隠れている三角形を削除する。
3)オブジェクトBの隠れている三角形をオブジェクトAにコピーする。
4)オブジェクトBから、隠れている三角形を削除する。
5)bufferA内の三角形をオブジェクトBにコピーする。
6)AおよびBのすべての隠れている三角形の法線を反転させる。
7)2つのオブジェクトの三角形をマージする。

0059

差演算(Bの内側のAの区画を除去することによって、幾何オブジェクトAを別のオブジェクトBによって切り取る)は、以下の手順を有する。
1)オブジェクトAの隠れている三角形を削除する。
2)オブジェクトBの隠れていない三角形を削除する。
3)オブジェクトBのすべての三角形の法線を反転させる。
4)オブジェクトAとオブジェクトBの三角形をマージする。

0060

分割演算(2つのソリッド幾何オブジェクトA,Bを3つのオブジェクト、すなわち、2つの幾何オブジェクトの共通部分、オブジェクトAの共有されていない区画、オブジェクトBの共有されていない区画、に分割する)は、以下の手順を有する。
1)オブジェクトAの隠れている三角形をバッファbufferAにコピーする。
2)オブジェクトBの隠れている三角形をbufferAにコピーする。
3)オブジェクトAの隠れている三角形を別のバッファbufferBにコピーする。
4)オブジェクトAの隠れている三角形を削除する。
5)オブジェクトBの隠れている三角形をオブジェクトAにコピーする。
6)オブジェクトBの隠れている三角形を削除する。
7)bufferAに格納されているオブジェクトAの隠れている三角形を、オブジェクトBにコピーする。
8)AおよびBのすべての隠れている三角形の法線を反転させる。

0061

<レンダリングファセットへのマッピング>
ブーリアン演算が終了した時点で、本方法は、BlOpTriangleSetをレンダリング三角形にマッピングする。
1)BlOpTriangleSetの各Point3dExを、TriangleSetのPoint3dにマッピングする。
2)BlOpTriangleSetの各Triangle3dExを、TriangleSetのTriangle3dにマッピングする。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ