凸な平面多角形用の新しいバリセントリック座標計算アルゴリズム

2023年6月28日 14:31

バリセントリック座標について

頂点に色が付いた多角形を想像してみてください。
そして、多角形のどこかに点を打ちます。
その点は、何色に塗るべきでしょうか？
この問題を解決するのが「バリセントリック座標」です。

例えば、五角形 ABCDE があり、A:赤 B:緑 C:青 D:黒 E:白で色付いているとします。
打った点 P が A に近ければ赤く、B に近ければ緑になってほしいですよね。
という感じで、点の位置に応じて、どの頂点をどれくらい真似するかの「重み」を決めることができ、この重みを「バリセントリック座標」と呼びます。

先程の五角形の P のバリセトンリック座標を (s,t,u,v,w) と決めたとすると、P = sA + tB + uC + vD + wE で表せます
これで色を計算できますね！
この式は、色だけでなく、色々な情報に対して使えます。
頂点ウェイトの補間や、テクスチャ座標なんてものにも使えたりします。
というわけで、バリセントリック座標を決めることができると、とても便利なのです。

三角形のバリセントリック座標

三角形のバリセントリック座標を求めるのは簡単です。
高校の数学で習ったように、点Pの座標はベクトルABとベクトルACのパラメータとして求めることができます。
P = sAB + tAC
あとは何やかんやして変形すれば、以下の式が求められます。
P = (1 - s - t) * A + s * B + t * C
これが三角形における P のバリセントリック座標です。

バリセントリック座標の弱点

しかし、三角形以外の多角形に対して、バリセントリック座標を求める一般的な方法は、実は確立されていません。
それば、三角形以外では、バリセントリック座標は一意に定まらないからです。
あちらを上げればこちらを下げて……という風に、バランスさえ取れていれば、適当に決めることができてしまいます。

なので、面積を使う方法や、頂点との距離を使う方法、角度を使う方法など、様々なアルゴリズムが考案されてきました。
しかし、特定の条件で計算できなくなったり、ある特定の場所で不具合が起こらないような特別処理を施したりした結果、急に座標が変化したりして、綺麗でなめらかなバイセントリック座標を求めることは、なかなかに難しい問題です。

新しいアルゴリズムの提案

今回私が考案したのは、とても素朴な方法です。
ある平面の上に多角形 polygon があり、その多角形の中に点 P があるとします。
このとき、点 P を通る平面を考え、その平面を適切に傾けて polygon の各頂点と原点を結んだ直線との交点を求め、重みとします。
平面の傾け方は、P と polygon の辺との距離を計算し、距離の逆数と辺の作る側面の法線をかけ合わせて求めます。
こうすることで、P が辺に近付けば近付くほど平面が側面側に傾き、交点が「上に」移動します。
つまり、近い辺のバリセントリック座標ほど強く重みづけされるわけです。

紫の平面を傾けて側面との交差を求める
(実際には計算のために原点をズラしているので、画像の平面はフェイクです)

特徴/長所と短所

この方法は、多角形が凸で、かつ、おおよそ同一平面上にある時に、とてもよく働きます。
3D-CG だと大抵のポリゴンは三角形から五角形の平面なので、相性がとても良いです。
また、例外的な特別処理がほとんど必要なく、なめらかに連続したバリセントリック座標を得られます。
一方で、凹な多角形の凹んだ部分や、曲がったり捻れたりして曲面になっている多角形では、あまり正確な値が得られませんので注意してください。

発展/改良案など

現在は頂点ごとの法線ベクトルを、一つ隣りの側面の法線ベクトルだけにしています。
これを両隣の側面の法線ベクトルの平均にすることで、鋭角の部分での補間がより滑らかになる……かも？

また、現在は曲がった面ではうまく計算できず、ズレが生じてしまいますが、各頂点の位置を最初に平面上に投影して、その座標を計算用に使えば、ズレなくなるかもしれません。

ソースについて

ソースコードは GitHub にあります。
https://github.com/DaDaDan3D/DDDTools/blob/main/mathUtils.py#L631
計算自体は Numpy で 30 行程度なので、ご興味がありましたら読んでみてください。
MIT ライセンスで公開していますので、どんどん改良してください～。

def intersection_based_barycentric_mapping(verts, face_normal, point):
    """
    平面上の凸な多角形におけるバリセントリック座標を、原点と頂点を結ぶ直線と
    特定の平面との交点を用いて求める。

    Parameters:
    -----------
    verts : np.ndarray
      平面上の凸な多角形
    face_normal : np.ndarray
      平面の法線
    point : np.ndarray
      バリセントリック座標を求める点

    Returns:
    --------
    np.ndarray
      バリセントリック座標
    """
    n = verts.shape[0]

    # Calculate the epsilon
    max_value = np.max(np.abs(verts))
    epsilon = 16.0 * np.finfo(float).eps * max_value

    # 計算誤差を避けるため、面法線の方向に少し移動する
    # またこれにより、裏面がなくなる
    bias = face_normal * max_value * 2

    P = point + bias
    A = verts + bias
    B = np.roll(A, -1, axis=0)

    # 各辺における側面の法線を計算する
    normals = normalize_vectors(np.cross(A, B), epsilon)

    # 各辺と P との距離の逆数を計算し、法線 normal を決定する
    distances = distances_to_edges(A, P)
    distances = np.where(
        distances < epsilon,
        epsilon,
        distances)
    distances_inv = 1 / distances

    normal = np.sum(distances_inv[:, np.newaxis] * normals, axis=0) / np.sum(distances_inv)

    # 平面と、各頂点と原点を結ぶ直線との交点を求め、これを weights とする
    dot_normal_A = np.sum(normal * A, axis=1)
    dot_normal_A = np.where(
        dot_normal_A < epsilon,
        epsilon,
        dot_normal_A)

    dot_normal_P = np.dot(normal, P)
    weights = dot_normal_P / dot_normal_A
    weights /= np.sum(weights)
    return weights

サンプル動画

おまけ。呼び方とか

Intersection-Based Barycentric Mapping という名前は、Chat-GPT くんに考えてもらいました。
日本語だと「交点法」とかが良いかしら？
平面を傾ける様子をワイングラスを傾けるようなイメージに見立てて「ワイングラス法」とか……はちょっとオシャレすぎますね(^^;