次の問題があります。3Dモデルの2Dビューを生成する必要があります。通常の状況では、これはもちろん些細なことです。画家のアルゴリズムまたは同様の手法を使用して、すべてを画面にレンダリングするだけです。残念ながら、CADパッケージに送信できるように、出力は2Dジオメトリである必要があります。これは、隠面判定をピクセルレベルではなくベクトルレベルで実行する必要があることを意味します。これにより、ほとんどの標準的な方法（画家のアルゴリズム、Zバッファなど）が使用できなくなります。
オブジェクト空間の隠面判定を実行するために私が見つけた最も一般的な手法は、理論的には問題なく機能するBSPツリーを使用することです。だから私はそれを実装しましたが、パフォーマンスはリモートでさえ受け入れられませんでした。それは、そのO（n 2）の複雑さを考えるとまったく驚くべきことではありません。私が使用しているテストシーンには、裏面カリング後に約4800の三角形がありますが、アルゴリズムはその数の約5倍または10倍のシーンを処理する必要があり、2乗する必要がある場合はすぐに大きくなります。ジオメトリライブラリの（不足している）速度も、正確には役に立ちません。
それ以来、このパフォーマンスの問題を回避するためのさまざまな方法を試しました。主に、三角形を小さなグループに分割して、八分木などのO（n 2 ）の影響を減らすというアイデアに基づいています（ポリゴンの半分以上がルートノードに保存されます）、2D投影シーンを10x10グリッドに分割して、正方形あたりの三角形の数を減らします（機能しますが、ポリゴンの交差の削減は、プロセスを100回繰り返す必要があることよりも重要です）。
今日は、すべての三角形を2Dに投影し、最初に境界の正方形が重なっているかどうかをテストし、次に2つのポリゴンのすべての組み合わせについて各エッジの交差（3x3 = 9）をテストして、どの三角形が交差するかを確認しました。線の交点については、ここで説明するアルゴリズムを使用してジオメトリライブラリをバイパスしました。合計で約1160万のライン交差が実行され、約30秒かかりますが、それでも長すぎます（絶対最大実行時間は約5秒だと思います）。これはアルゴリズムの一部にすぎないことを気にしないでください。
私はこのパフォーマンスの問題を解決する方法についてのアイデアを使い果たし始めており、より良いアルゴリズムのためのいくつかの良いアイデアを持っている人がいることを望んでいました。私が考えることができるものはすべてO（n 2）です。