Open14

Blenderのカーブオブジェクト調査

hzuikahzuika

Bézier曲線やNURBS曲線について少しずつ調べます

hzuikahzuika

データ構造の調べ方

BlenderのPython API Document (bpy.types) url

↓ メンバ名や説明文で検索

source/blender/makesrna/ github

↓ Pythonのデータ(RNA)とCのデータ(DNA)の対応関係がわかる。

source/blender/makesdna/ github
Cのデータ(構造体)の定義が書かれたファイル群。

hzuikahzuika

Spline(Nurb)のtype

CU_TYPE

Splineのアルゴリズムを決める。

  • CU_POLY = 0,
  • CU_BEZIER = 1,
  • CU_BSPLINE = 2,
  • CU_CARDINAL = 3,
  • CU_NURBS = 4,
  • CU_TYPE = (CU_POLY | CU_BEZIER | CU_BSPLINE | CU_CARDINAL | CU_NURBS),
  • CU_BSPLINEとCU_CARDINALは未実装
  • CU_TYPEはビットマスクとして使う
  • 0xFFまで定義できる

CU_PRIMITIVE

SplineやSurfaceの形状を決める。

  • CU_PRIMITIVE = 0xF00,
  • CU_PRIM_CURVE = 0x100,
  • CU_PRIM_CIRCLE = 0x200,
  • CU_PRIM_PATCH = 0x300,
  • CU_PRIM_TUBE = 0x400,
  • CU_PRIM_SPHERE = 0x500,
  • CU_PRIM_DONUT = 0x600,
  • CU_PRIM_PATH = 0x700,

CU_PRIMITIVEはビットマスクとして使う

hzuikahzuika

新しいカーブを追加するには(WIP)

UI

オペレータのUIへの追加

space_view_3d.pyのVIEW3D_MT_curve_adddrawメソッドにオペレータを追加して,UIに表示させる.

layout.separator()layout.operator()を追加するだけでは表示されない?
buildディレクトリでninjaコマンドなどを使用してビルドしていると,pythonファイルの更新が反映されない.
ソースコードのディレクトリでmake ccache ninjaコマンドなどを使用して再びビルドする.

オペレータ

オペレータの定義

editcurve_add.cあたりにオペレータの関数定義をする.

void CURVE_OT_primitive_newspline_curve_add(wmOperatorType *ot)

オペレータの宣言

curve_intern.hにオペレータの関数を宣言する.

オペレータの登録

curve_ops.cにオペレータの関数を登録する.

実装

新しいカーブタイプの追加

DNAに新しいカーブのタイプを追加する.

オペレータのexecコールバック関数の定義

editcurve_add.cにオペレータのexecコールバック関数を定義する.
カーブタイプと形状のタイプを引数に入れてcurve_prim_add関数を呼び出す.

static int add_primitive_newspline_exec(bContext *C, wmOperator *op)
{
  return curve_prim_add(C, op, CU_NEWSPLINE | CU_PRIM_CURVE);
}

curve_prim_add関数はcurvesurf_prim_add関数を呼び出す.

既存の関数の中に新しいカーブの処理を追加する.

curvesurf_prim_add関数内で実行される,
get_curve_defname関数と,ED_curve_add_nurbs_primitive関数に新しいカーブのための処理を追加する.

  • get_curve_defnameはUIに表示されるオブジェクト名を返す(翻訳あり).
  • ED_curve_add_nurbs_primitiveはスプラインの頂点座標等の情報を格納する.

else if (cutype == CU_NEWSPLINE) {
  nu->pntsu = // 制御点の数
  nu->bp = (BPoint *)MEM_callocN(sizeof(BPoint) * nu->pntsu, "addNewSplineprim3"); //ハンドルなし

// 全選択とスケールとソフトボディ用のウェイト
  bp = nu->bp;
  for (a = 0; a < nu->pntsu; a++, bp++) {
          bp->f1 = SELECT;
          bp->radius = bp->weight = 1.0;
  }

// 座標の代入

//原点の座標変換

        bp = nu->bp;
        for (a = 0; a < 4; a++, bp++) {
          mul_m4_v3(mat, bp->vec);
        }

}

curve_to_displistCurveからDispListへの変換を実装する(スプライン曲線のアルゴリズム)

// DispListを用意
DispList *dl = (DispList *)MEM_callocN(sizeof(DispList), __func__);
// サンプリング点の数だけ頂点を作成
dl->verts = (float *)MEM_mallocN(len * sizeof(float[3]), __func__);

BLI_addtail(r_dispbase, dl);
dl->parts = 1; //
dl->nr = len;  // サンプル数
dl->col = nu->mat_nr;  // マテリアルインデックス
dl->charidx = nu->charidx;
dl->type = (is_cyclic && (dl->nr != 2)) ? DL_POLY : DL_SEGM;  // 開いているか閉じているか?

// `dl->verts` にサンプル点の座標を格納する

CU_BEZIERの場合
BKE_curve_forward_diff_bezier

CU_NURBSの場合
BKE_nurb_makeCurve

CU_POLYの場合
copy_v3_v3 (BPoint->vecの座標をそのまま代入)

hzuikahzuika

Blenderのソースコードをブラウザで確認する方法


Sourcegraphの使い方

検索欄で次のように入力するとblender/blenderリポジトリのsource/blender内のディレクトリとファイルが表示される.

repo:^github\.com/blender/blender$ file:^source/blender

^が行の始まりを表し,$が行の終わりを表す.

hzuikahzuika

ED_curve_add_nurbs_primitive

  • ED_curve_add_nurbs_primitiveはスプラインの頂点座標等の情報を格納する.
    • Bezier曲線の場合は,BezTriple
      • 全ハンドルタイプはHD_ALIGN
      • 1つめの制御点の座標は(-1, 0, 0), 左ハンドルの座標は(-1.5, -0.5, 0), 右ハンドルの座標は(-0.5, 0.5, 0)
      • 2つめの制御点の座標は(1, 0, 0), 左ハンドルの座標は(0, 0, 0), 右ハンドルの座標は(2, 0, 0)
      • そのあと,BKE_nurb_handles_calcが実行される.
    • NURBS曲線の場合は,BPoint
      • 全制御点のweightは1
      • 制御点1の座標(-1.5, 0, 0)
      • 制御点2の座標(-1, 1, 0)
      • 制御点3の座標(1, 1, 0)
      • 制御点4の座標(1.5, 0, 0)
      • そのあと,BKE_nurb_knot_calc_uが実行される.
hzuikahzuika

BKE_nurb_handles_calc

  1. calchandlesNurb_intern(nu, SELECT, false);
  2. calchandleNurb_intern(bezt, prev, next, handle_sel_flag, 0, skip_align, 0);

calchandleNurb_intern

  • HD_ALIGN, HD_AUTO, HD_VECTの場合は制御ハンドルを移動させる必要がある.
  • HD_FREEの場合は制御ハンドルを移動させる必要がない.
hzuikahzuika

描画関係の処理

オブジェクト追加時のWM_event_add_notifier(C, NC_OBJECT | ND_DRAW, obedit);

WM_event_add_notifierの定義.

  • NCはcategory
  • NDはdata

ND_DRAW

space_view3d.cで処理されて、ED_region_tag_redraw(region);が実行される

view3d_main_region_listenerNC_OBJECTND_DRAWを処理する.

ED_region_tag_redraw内の処理.

region->do_draw |= RGN_DRAW;

DistListはDisplacementではなくて、Displayのリスト。

https://github.com/blender/blender/blob/v2.93.0/source/blender/blenkernel/BKE_displist.h#L69

BKE_displist_make_curveTypes

https://github.com/blender/blender/blob/v2.93.0/source/blender/blenkernel/intern/object_update.c#L163

https://github.com/blender/blender/blob/v2.93.0/source/blender/blenkernel/intern/object_update.c#L380

hzuikahzuika

Bezier

https://github.com/blender/blender/blob/master/source/blender/blenkernel/intern/curve.c#L1789:6

/source/blender/blenkernel/intern/displist.cc
            BKE_curve_forward_diff_bezier(prevbezt->vec[1][j],  // 制御点
                                          prevbezt->vec[2][j],  // ハンドル
                                          bezt->vec[0][j],  // ハンドル
                                          bezt->vec[1][j],  // 制御点
                                          data + j,  // 出力
                                          resolution,  // 分割数
                                          sizeof(float[3]));

前進差分法による3次ベジエ曲線

/source/blender/blenkernel/intern/curve.c
void BKE_curve_forward_diff_bezier(
    float q0, float q1, float q2, float q3, float *p, int it, int stride)
{
  float rt0, rt1, rt2, rt3, f;
  int a;

  f = (float)it;
  rt0 = q0; // t^0 の係数
  rt1 = 3.0f * (q1 - q0) / f; // t^1 の係数
  f *= f;
  rt2 = 3.0f * (q0 - 2.0f * q1 + q2) / f; // t^2 の係数
  f *= it;
  rt3 = (q3 - q0 + 3.0f * (q1 - q2)) / f; // t^3 の係数

  q0 = rt0;
  q1 = rt1 + rt2 + rt3;
  q2 = 2 * rt2 + 6 * rt3;
  q3 = 6 * rt3;

  for (a = 0; a <= it; a++) {  // サンプル数だけ微小区間を適宜加算していく処理
    *p = q0;
    p = POINTER_OFFSET(p, stride);
    q0 += q1;
    q1 += q2;
    q2 += q3;
  }
}

3次ベジエ曲線

\begin{aligned} b(t) &= (1-t)^3 p_0 + 3(1-t)^2tp_1 + 3(1-t)t^2p_2 + t^3p_3\\ &= (1 -3t + 3t^2 - t^3)p_0 + 3(t-2t^2+t^3)p_1 + 3(t^2-t^3)p_2 + t^3 p_3\\ &= (-p_0 + 3p_1 - 3p_2 + p_3)t^3 + (3p_0 -6p_1 +3p_2)t^2 + (-3p_0 +3p_1)t + p_0\\ &= R_3t^3 + R_2t^2 + R_1t + r_0\\ b'(t) &= 3(1-t)^2 (p_1-p_0)+6(1-t)t(p_2-p_1)+3t^2(p_3-p_2)\\ &= 3R_3 t^2 + 2R_2t + R_1\\ b''(t) &= 6(1-t)(p_2-2p_1+p_0)+6t(p_3-2p_2+p_1)\\ &= 6R_3 t + 2R_2\\ b'''(t) &= 6R_3 \end{aligned}

参考 https://en.wikipedia.org/wiki/Bézier_curve#Cubic_Bézier_curves

f サンプル数 (t\in [0, 1] = [0, \tfrac{1}{f}, \tfrac{2}{f}, \ldots, \tfrac{f-1}{f}, \tfrac{f}{f})
\Delta t = 1/f
q_0, q_1, q_2, q_3 制御点

\begin{aligned} r_0 &= q_0\\ r_1 &= 3 (q_1 - q_0)\frac{1}{f} = 3 (q_1 - q_0) \Delta t\\ r_2 &= 3 (q_0 - 2q_1 + q_2)\frac{1}{f^2} = 3 (q_0 - 2q_1 + q_2) (\Delta t)^2\\ r_3 &= (q_3 - q_0 + 3(q_1 - q_2))\frac{1}{f^3} = (q_3 - q_0 + 3(q_1 - q_2)) (\Delta t)^3\\ \end{aligned}
\begin{aligned} a_0 &= r_0 = q_0\\ b_0 &= r_1 + r_2 + r_3 = R_1 (\Delta t) + R_2 (\Delta t)^2 + R_3 (\Delta t)^3\\ c_0 &= 2r_2 + 6r_3 = 2R_2 (\Delta t)^2 + 6 R_3 (\Delta t)^3\\ d &= 6r_3 = 6 R_3 (\Delta t)^3\\ \end{aligned}
\begin{aligned} p_0 &= a_0\\ a_1 &= a_0 + b_0 = a_0 + r_1 + r_2 + r_3 = a_0 + R_1 (\Delta t) + R_2 (\Delta t)^2 + R_3 (\Delta t)^3\\ b_1 &= b_0 + c_0 = b_0 + 2r_2 + 6r_3 = b_0 + 2R_2 (\Delta t)^2 + 6 R_3 (\Delta t)^3\\ c_1 &= c_0 + d = c_0 + 6r_3 = c_0 + 6 R_3 (\Delta t)^3\\ \end{aligned}

hzuikahzuika

NURBS

https://github.com/blender/blender/blob/master/source/blender/blenkernel/intern/curve.c#L1576:6

/source/blender/blenkernel/intern/displist.cc
      BKE_nurb_makeCurve(nu, dl->verts, nullptr, nullptr, nullptr, resolution, sizeof(float[3]));
/source/blender/blenkernel/intern/curve.c
void BKE_nurb_makeCurve(const Nurb *nu,
                        float *coord_array,
                        float *tilt_array,
                        float *radius_array,
                        float *weight_array,
                        int resolu,
                        int stride)
{
  const float eps = 1e-6f;
  BPoint *bp;
  float u, ustart, uend, ustep, sumdiv;
  float *basisu, *sum, *fp;
  float *coord_fp = coord_array, *tilt_fp = tilt_array, *radius_fp = radius_array,
        *weight_fp = weight_array;
  int i, len, istart, iend, cycl;

  if (nu->knotsu == NULL) {
    return;
  }
  if (nu->orderu > nu->pntsu) {
    return;
  }
  if (coord_array == NULL) {
    return;
  }

  /* allocate and initialize */
  len = nu->pntsu;
  if (len == 0) {
    return;
  }
  sum = (float *)MEM_calloc_arrayN(len, sizeof(float), "makeNurbcurve1");

  resolu = (resolu * SEGMENTSU(nu));

  if (resolu == 0) {
    MEM_freeN(sum);
    return;
  }

  fp = nu->knotsu;
  ustart = fp[nu->orderu - 1];
  if (nu->flagu & CU_NURB_CYCLIC) {
    uend = fp[nu->pntsu + nu->orderu - 1];
  }
  else {
    uend = fp[nu->pntsu];
  }
  ustep = (uend - ustart) / (resolu - ((nu->flagu & CU_NURB_CYCLIC) ? 0 : 1));

  basisu = (float *)MEM_malloc_arrayN(KNOTSU(nu), sizeof(float), "makeNurbcurve3");

  if (nu->flagu & CU_NURB_CYCLIC) {
    cycl = nu->orderu - 1;
  }
  else {
    cycl = 0;
  }

  u = ustart;
  while (resolu--) {
    basisNurb(u, nu->orderu, nu->pntsu + cycl, nu->knotsu, basisu, &istart, &iend);

    /* calc sum */
    sumdiv = 0.0;
    fp = sum;
    bp = nu->bp + istart - 1;
    for (i = istart; i <= iend; i++, fp++) {
      if (i >= nu->pntsu) {
        bp = nu->bp + (i - nu->pntsu);
      }
      else {
        bp++;
      }

      *fp = basisu[i] * bp->vec[3];
      sumdiv += *fp;
    }
    if ((sumdiv != 0.0f) && (sumdiv < 1.0f - eps || sumdiv > 1.0f + eps)) {
      /* is normalizing needed? */
      fp = sum;
      for (i = istart; i <= iend; i++, fp++) {
        *fp /= sumdiv;
      }
    }

    zero_v3(coord_fp);

    /* one! (1.0) real point */
    fp = sum;
    bp = nu->bp + istart - 1;
    for (i = istart; i <= iend; i++, fp++) {
      if (i >= nu->pntsu) {
        bp = nu->bp + (i - nu->pntsu);
      }
      else {
        bp++;
      }

      if (*fp != 0.0f) {
        madd_v3_v3fl(coord_fp, bp->vec, *fp);

        if (tilt_fp) {
          (*tilt_fp) += (*fp) * bp->tilt;
        }

        if (radius_fp) {
          (*radius_fp) += (*fp) * bp->radius;
        }

        if (weight_fp) {
          (*weight_fp) += (*fp) * bp->weight;
        }
      }
    }

    coord_fp = POINTER_OFFSET(coord_fp, stride);

    if (tilt_fp) {
      tilt_fp = POINTER_OFFSET(tilt_fp, stride);
    }
    if (radius_fp) {
      radius_fp = POINTER_OFFSET(radius_fp, stride);
    }
    if (weight_fp) {
      weight_fp = POINTER_OFFSET(weight_fp, stride);
    }

    u += ustep;
  }

  /* free */
  MEM_freeN(sum);
  MEM_freeN(basisu);
}