次の問題があります。3Dモデルの2次元ビューを生成する必要があります。通常の状況下では、これはもちろん些細なことです。ペインタのアルゴリズムや同様の手法を使ってすべてをスクリーンにレンダリングします。残念ながら、CADパッケージに送信できるように、出力は2次元ジオメトリである必要があります。これは、隠面消去はピクセルレベルではなくベクトルレベルで行わなければならないことを意味します。これにより、標準的なメソッド（ペインタのアルゴリズム、zバッファなど）のほとんどが使用できなくなります。効率的なオブジェクト空間の隠面消去
オブジェクトスペースの隠面消去を実行するために私が見つけた最も一般的な手法は、理論上はうまく動作するBSPツリーを使用することです。だから私はそれを実装しましたが、パフォーマンスは遠隔から受け入れられませんでした.O（n ）の複雑さを考えると、全く驚くことではありません。私が使っているテストシーンには、背面のカリング後に約4800の三角形がありますが、その数は約5倍から10倍のシーンを処理する必要があります。ジオメトリライブラリの（不足している）スピードは、正確には役に立ちません。
これまで、O（n-）の影響を減らすために、小さいグループの三角形を分割するという考え方に基づいて、このパフォーマンスの問題を回避するさまざまな方法を試みました。 （ポリゴンの半分以上がルートノードに格納されていました）、2次元投影されたシーンを10x10グリッドで分割して、1平方あたりの三角形の数を減らしました（動作しますが、ポリゴンの交点の減少は、 100回）。
今日私は、すべての三角形を2Dに投影し、どの四角形が重なり合っているかを最初にテストし、次に2つのポリゴンの各組み合わせに対して各エッジの交差点（3x3 = 9）をテストすることによって交差しています。線の交差については、hereと記載されたアルゴリズムを使用してジオメトリライブラリをバイパスしました。合計で約1160万本の交差点が実行されていますが、これはまだ30秒しかかかりません（絶対最大実行時間は約5秒です）。これはアルゴリズムの一部にすぎません。
私はこのパフォーマンスの問題を解決する方法に関するアイデアがなくなり始めており、より良いアルゴリズムのための良いアイデアがあることを期待していました。私が考えることができるものはすべてO（n ）です。
あなたはいくつかのより多くの実装仕様（言語、するライブラリなどを...）を提供することができますか？ – ChristopheD
2Dビューで実際に表示されるサーフェスの一般的な数はいくつですか？ – ElKamina
私はC＃で働いています。ジオメトリライブラリは、私が働く会社によって書かれたもので、オープンソースではありません。また、C＃で書かれており、非常に高速な方法ではありませんが、ポリゴンの交差などの基本的な操作をサポートしています。私はちょうどそれを無視して、直接、必要であれば、三角形のポイントのx軸、y軸およびz-coordiantesで動作することができますので、幾何学ライブラリは、しかし、特に重要ではありません。私は言語が大事だとは思わない。問題は主にアルゴリズムの1つです。任意のソリューションをC＃に移植するのはかなり簡単です。 – FalconNL