0

3D 凸包を計算するためのクイック ハル アルゴリズムを実装しようとしています。問題は、ポイントが特定のサーフェスを「見る」ことができるかどうかを知る必要があることです。

サーフェスには、時計回りまたは反時計回りの方向があります。

アルゴリズムの動作をグラフィカルに説明するために、小さな opengl プログラムを作成しました。

他のアルゴリズムが使用しているのを見たさまざまな方程式を試しました (正規化された外積、平面からのドットの距離)

それらはすべて、アルゴリズムで間違った手順を実行することにつながりました。つまり、特定のサーフェスがそのポイントから見えると判断したことを意味します (グラフィックで見ることができますが、そうではありません)。

表面または「面」の例。

e1 = 0, 0, 0 to 10, 0, 0
e2 = 10, 0, 0 to 10, 10, 0
e3 = 10, 10, 0 to 0, 10, 0
e4 = 0, 10, 0 to 0, 0, 0

<---------/\
||        ||
||        ||
||        ||
\/--------->

2 つのポイントがあり、それらがサーフェスのどちら側にあるかを知りたいとしましょう。

p1 = -1、-1、-1 p2 = 1、1、1

どんな助けでも大歓迎です。

4

1 に答える 1

1

最初のステップは、平面の法線を決定することです。これはクロス積で達成できます。例えば：

normal = cross(e2 - e1, e3 - e1);

次に、法線と比較するためのベクトルが必要です。

compare = point - e1

また、両方のベクトルが法線の同じ方向を指している場合、両方のベクトルの内積は次のようになります。

side = dot(normal, compare)

side > 0 の場合、ポイントは法線が向いている平面の側面にあります。< 0 の場合は、反対側にあります。= 0 の場合、正確に平面上にあります。

重要なステップは、法線が正しい記述を指すように法線を定義することです。ポリゴンのみを使用すると、コーナー ポイントの順序によって法線を定義できます。たとえば、上側はポイントが時計回りにある側です。別のものが必要な場合は、より多くの情報を提供する必要があります。

于 2012-07-11T09:44:56.733 に答える