ハーフエッジ①

アルちゃん

p5.jsとChatGPT4くんによる。
人類はたんぽぽを添えるがごとくコピペする。


ハーフエッジ

ハーフエッジ構造（またはハーフエッジデータ構造）は、3Dメッシュデータの処理や編集のためのトポロジカルなデータ構造の一つです。特に、連続した面の集まりからなる多面体の表現において、その面、エッジ、頂点の関係を効率的に表現するのに役立ちます。
このデータ構造の基本的な考え方は、各エッジを二つの「ハーフエッジ」として考えることです。各ハーフエッジは、エッジの片方の向きを持ち、その向きの端点となる頂点、隣接する面、対向するハーフエッジ、次のハーフエッジへの参照を持ちます。
以下は、ハーフエッジデータ構造の主なコンポーネントです：

モデル:
面の集合。
頂点の集合。

  1. 頂点: 3D座標を持つ点のデータ。また、その頂点から出るハーフエッジの1つへの参照を持ちます。

  2. 線分（稜線、ハーフエッジ）: これは実際のエッジを表現するための主要なコンポーネントです。以下の情報を持ちます：

    • そのハーフエッジの「始点」となる頂点への参照

    • そのハーフエッジが属する面（ハーフエッジの左）への参照

    • 対となる反対の向きのハーフエッジ（対ハーフエッジ）への参照

    • 同じ面に属する次のハーフエッジへの参照

  3. 面: メッシュ内の平面部分。その面を構成するハーフエッジの1つへの参照を持ちます。

ハーフエッジ構造の利点：

  1. 連続したトポロジーを効率的に表現します。隣接関係や隣接面の情報を効率的に取得できます。

  2. メッシュの変更や再構成が容易になります。例えば、エッジの分割や面の追加など。

点

// 頂点のクラス定義
class Vertex {
  constructor(x, y, z) {
    this.position = createVector(x, y, z); // p5.jsのベクトルを使用して3D座標を保存
    this.halfEdge = null; // この頂点から出るハーフエッジの1つ
  }
}

ハーフエッジ

class HalfEdge {
  constructor() {
    this.vertex = null; // このハーフエッジの端点となる頂点
    this.opposite = null; // 反対のハーフエッジ
    this.face = null; // このハーフエッジが属する面
    this.next = null; // 同じ面の次のハーフエッジ
  }
}

面

// 面のクラス定義
class Face {
  constructor() {
    this.halfEdge = null; // この面を構成するハーフエッジの1つ
  }
}

このコードは、ハーフエッジデータ構造の基本的な部分をp5.jsで表現するためのものです。完全な機能やメッシュ操作、描画機能を実装するためには、さらに多くのコードが必要となります。


ハーフエッジモデル

class HalfEdgeModel {
  constructor() {
    this.faces = null;
    this.vertices = null;
  }
}


// ハーフエッジのクラス定義
class HalfEdge {
  constructor() {
    this.vertex = null; // このハーフエッジの端点となる頂点
    this.opposite = null; // 反対のハーフエッジ
    this.face = null; // このハーフエッジが属する面
    this.next = null; // 同じ面の次のハーフエッジ
  }
}

// 頂点のクラス定義
class Vertex {
  constructor(x, y, z) {
    this.position = createVector(x, y, z); // p5.jsのベクトルを使用して3D座標を保存
    this.halfEdge = null; // この頂点から出るハーフエッジの1つ
  }
}

// 面のクラス定義
class Face {
  constructor() {
    this.halfEdge = null; // この面を構成するハーフエッジの1つ
  }
}


OBJフォーマット

OBJフォーマットは、3Dグラフィックスで使用されるジオメトリのテキスト表現をするためのシンプルなデータフォーマットです。1980年代にWavefront Technologies社によって開発され、その名前は同社のアドバンスド・ビジュアルライザーというツールの拡張子から取られました。主に3Dメッシュデータとそれに関連する情報（テクスチャマッピング、法線、マテリアルなど）を記述するために使用されます。

以下は、OBJフォーマットの主な特徴とそれを構成する要素です：

  1. 頂点データ:(vertex)

    • v x y z - 頂点の位置を示す。x, y, zは頂点の座標を表します。

    • vn x y z - 頂点の法線を示す。

    • vt u v - 頂点のテクスチャ座標を示す。

  2. 面データ:(face)

    • f v1/vt1/vn1 v2/vt2/vn2 v3/vt3/vn3 - 面を定義するための頂点のインデックス。vは頂点、vtはテクスチャ座標、vnは法線のインデックスを示す。

  3. マテリアルとテクスチャの参照:

    • usemtl material_name - 使用するマテリアルを指定する。

    • mtllib filename.mtl - マテリアル定義を含む外部MTLファイルを参照する。

  4. グループとオブジェクト:(group, object)

    • g groupname - 頂点や面のグループを定義する。

    • o objectname - オブジェクトの名前を定義する。

  5. スムージング:

    • s: スムージンググループを定義します。スムージングは、面の間の遷移が滑らかであることを示すためのもので、s 1のようにして有効にしたり、s offのようにして無効にすることができます。

v: この接頭辞の後に続く数値は、3D空間内の頂点の座標を示します。例: v 1.0 2.0 3.0 は、x=1.0、y=2.0、z=3.0 の位置にある頂点を示します。

vn: この接頭辞は、頂点の法線ベクトルを示します。法線は、3Dモデルの表面がどの方向を向いているかを示すベクトルであり、レンダリング時に光の反射や陰影を計算する際に使用されます。例: vn 0.0 1.0 0.0 は、上向きの法線ベクトルを示します。

vt: この接頭辞は、テクスチャマッピングに使用されるテクスチャ座標を示します。これにより、3Dモデルの表面に2Dテクスチャイメージがどのようにマッピングされるかが定義されます。例: vt 0.5 0.5 は、テクスチャイメージの中央点を示します。

これらの接頭辞を使用することで、OBJファイルのパーサー（読み取りプログラム）は、各行のデータが何を示しているのかを正確に理解し、適切に処理することができます。

OBJフォーマットはテキストベースのフォーマットなので、テキストエディタで開いて内容を確認したり、手動で編集したりすることができます。しかし、実際の3Dモデルは通常、大量のデータを含むため、大きなファイルを手動で編集するのは非効率的であることが多いです。

多くの3Dモデリングツールやレンダリングソフトウェアは、OBJフォーマットのインポートとエクスポートをサポートしています。そのシンプルさと幅広い採用により、OBJは3Dデータ交換の標準的なフォーマットの一つとして多くの場面で利用されています。

サンプル

サンプル立方体

# cube.obj

# Vertices
v -0.5 -0.5 -0.5
v 0.5 -0.5 -0.5
v 0.5 0.5 -0.5
v -0.5 0.5 -0.5
v -0.5 -0.5 0.5
v 0.5 -0.5 0.5
v 0.5 0.5 0.5
v -0.5 0.5 0.5

# Faces
f 1 2 3 4
f 5 6 7 8
f 1 2 6 5
f 2 3 7 6
f 3 4 8 7
f 4 1 5 8

p5.js

let vertices = [];
let faces = [];

function preload() {
    let lines = loadStrings('cube.obj');  // cube.obj ファイルを読み込む
    for (let line of lines) {
        let parts = line.split(/\s+/);
        if (parts[0] === "v") {
            let v = createVector(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
            vertices.push(v);
        } else if (parts[0] === "f") {
            faces.push([parseInt(parts[1]) - 1, parseInt(parts[2]) - 1, parseInt(parts[3]) - 1, parseInt(parts[4]) - 1]);
        }
    }
}

function setup() {
    createCanvas(400, 400, WEBGL);
}

function draw() {
    background(200);

    rotateX(frameCount * 0.01);
    rotateY(frameCount * 0.01);

    for (let face of faces) {
        beginShape();
        for (let idx of face) {
            let v = vertices[idx];
            vertex(v.x, v.y, v.z);
        }
        endShape(CLOSE);
    }
}

ソース直書き

let vertices = [];
let faces = [];

let objData = `
v -0.5 -0.5 -0.5
v 0.5 -0.5 -0.5
v 0.5 0.5 -0.5
v -0.5 0.5 -0.5
v -0.5 -0.5 0.5
v 0.5 -0.5 0.5
v 0.5 0.5 0.5
v -0.5 0.5 0.5
f 1 2 3 4
f 5 6 7 8
f 1 2 6 5
f 2 3 7 6
f 3 4 8 7
f 4 1 5 8
`;

function setup() {
    createCanvas(400, 400, WEBGL);
    
    // OBJデータの解析
    let lines = objData.split('\n');
    for (let line of lines) {
        let parts = line.trim().split(/\s+/);
        if (parts[0] === "v") {
            let v = createVector(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
            vertices.push(v);
        } else if (parts[0] === "f") {
            faces.push([parseInt(parts[1]) - 1, parseInt(parts[2]) - 1, parseInt(parts[3]) - 1, parseInt(parts[4]) - 1]);
        }
    }
}

function draw() {
    background(200);

    rotateX(frameCount * 0.01);
    rotateY(frameCount * 0.01);

    scale(200); // ここで立方体のサイズを調整

    for (let face of faces) {
        beginShape();
        for (let idx of face) {
            let v = vertices[idx];
            vertex(v.x, v.y, v.z);
        }
        endShape(CLOSE);
    }
}

p5.jsのloadStrings

ソースの場所
p5.js/src/io/files.js


テキストデータを行に分割して文字列の配列にする。

  1. HTTPリクエストを使用してテキストファイルの内容を非同期に取得します。

  2. 取得したテキストデータを、各行を要素とする文字列の配列に変換します。このとき、さまざまなオペレーティングシステムの行の終わりの文字（改行コード）に対応するための正規表現を使用しています。

  3. この配列を返却します。また、成功時と失敗時には、それぞれのコールバック関数も実行されるようになっています。

p5.prototype.loadStrings = function(...args) {
  p5._validateParameters('loadStrings', args);

  const ret = [];
  let callback, errorCallback;

  for (let i = 1; i < args.length; i++) {
    const arg = args[i];
    if (typeof arg === 'function') {
      if (typeof callback === 'undefined') {
        callback = arg;
      } else if (typeof errorCallback === 'undefined') {
        errorCallback = arg;
      }
    }
  }

  const self = this;
  p5.prototype.httpDo.call(
    this,
    args[0],
    'GET',
    'text',
    data => {
      // split lines handling mac/windows/linux endings
      const lines = data
        .replace(/\r\n/g, '\r')
        .replace(/\n/g, '\r')
        .split(/\r/);

      // safe insert approach which will not blow up stack when inserting
      // >100k lines, but still be faster than iterating line-by-line. based on
      // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function/apply#Examples
      const QUANTUM = 32768;
      for (let i = 0, len = lines.length; i < len; i += QUANTUM) {
        Array.prototype.push.apply(
          ret,
          lines.slice(i, Math.min(i + QUANTUM, len))
        );
      }

      if (typeof callback !== 'undefined') {
        callback(ret);
      }

      self._decrementPreload();
    },
    function(err) {
      // Error handling
      p5._friendlyFileLoadError(3, arguments[0]);

      if (errorCallback) {
        errorCallback(err);
      } else {
        throw err;
      }
    }
  );

  return ret;
};


p5._validateParameters('loadStrings', args);

loadStrings関数の引数を検証します。これは、関数が正しいタイプと数の引数で呼び出されているかを確認するためのものです。


  for (let i = 1; i < args.length; i++) {
    const arg = args[i];
    if (typeof arg === 'function') {
      if (typeof callback === 'undefined') {
        callback = arg;
      } else if (typeof errorCallback === 'undefined') {
        errorCallback = arg;
      }
    }
  }

このループは、関数の引数として渡されたコールバック関数を特定して、それぞれの変数に代入します。


const self = this;
p5.prototype.httpDo.call(
  ...
);

httpDo関数は、HTTPリクエストを実行するp5のヘルパー関数です。callを使用して、現在のthisコンテキスト（通常はp5のインスタンス）を引き継ぎつつ関数を呼び出します。


data => {
  ...
}

これは、HTTPリクエストが成功したときに実行されるコールバック関数です。この関数内では、取得したテキストデータを行に分割し、それをret配列に格納しています。


OBJ→ハーフエッジ

function objToHalfEdgeModel(objString) {
  const lines = objString.split('\n');
  const vertices = [];
  const faces = [];
  const halfEdges = [];

  for (const line of lines) {
    const parts = line.split(' ').filter(Boolean);  // 空白文字を除外

    switch (parts[0]) {
      case 'v':
        const vertex = new Vertex(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
        vertices.push(vertex);
        break;

      case 'f':
        const face = new Face();
        const faceEdges = [];
        for (let i = 1; i < parts.length; i++) {
          const vertexIndex = parseInt(parts[i]) - 1;
          const he = new HalfEdge();
          he.vertex = vertices[vertexIndex];
          he.face = face;
          faceEdges.push(he);

          if (i > 1) {
            faceEdges[i - 2].next = he;
          }
        }
        faceEdges[faceEdges.length - 1].next = faceEdges[0];  // close the loop

        face.halfEdge = faceEdges[0];
        faces.push(face);
        halfEdges.push(...faceEdges);
        break;
    }
  }

  // Pairing opposite half edges (省略: ペアリング部分を追加する必要があります)

  const model = new HalfEdgeModel();
  model.faces = faces;
  model.vertices = vertices;

  return model;
}


ハーフエッジのペアリング例

function objToHalfEdgeModel(objString) {
  const lines = objString.split('\n');
  const vertices = [];
  const faces = [];
  const halfEdges = [];

  for (const line of lines) {
    const parts = line.split(' ').filter(Boolean);  // 空白文字を除外

    switch (parts[0]) {
      case 'v':
        const vertex = new Vertex(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
        vertices.push(vertex);
        break;

      case 'f':
        const face = new Face();
        const faceEdges = [];
        for (let i = 1; i < parts.length; i++) {
          const vertexIndex = parseInt(parts[i]) - 1;
          const he = new HalfEdge();
          he.vertex = vertices[vertexIndex];
          he.face = face;
          faceEdges.push(he);

          if (i > 1) {
            faceEdges[i - 2].next = he;
          }
        }
        faceEdges[faceEdges.length - 1].next = faceEdges[0];  // close the loop

        face.halfEdge = faceEdges[0];
        faces.push(face);
        halfEdges.push(...faceEdges);
        break;
    }
  }

  // Pairing opposite half edges
  for (let he1 of halfEdges) {
    if (!he1.opposite) {
      for (let he2 of halfEdges) {
        if (he2 !== he1 && !he2.opposite && he2.vertex === he1.next.vertex && he1.vertex === he2.next.vertex) {
          he1.opposite = he2;
          he2.opposite = he1;
          break;
        }
      }
    }
  }

  const model = new HalfEdgeModel();
  model.faces = faces;
  model.vertices = vertices;

  return model;
}


ハーフエッジ→OBJ

function halfEdgeModelToObj(model) {
  let objString = '';

  for (const vertex of model.vertices) {
    const pos = vertex.position;
    objString += `v ${pos.x} ${pos.y} ${pos.z}\n`;
  }

  for (const face of model.faces) {
    objString += 'f';

    let currentHalfEdge = face.halfEdge;
    do {
      objString += ` ${model.vertices.indexOf(currentHalfEdge.vertex) + 1}`;
      currentHalfEdge = currentHalfEdge.next;
    } while (currentHalfEdge !== face.halfEdge);

    objString += '\n';
  }

  return objString;
}

Displayハーフエッジ


class HalfEdgeModel {
  constructor() {
    this.faces = [];
    this.vertices = [];
  }

  display() {
    for (const face of this.faces) {
      beginShape();

      let currentHalfEdge = face.halfEdge;
      do {
        const pos = currentHalfEdge.vertex.position;
        vertex(pos.x, pos.y, pos.z);
        currentHalfEdge = currentHalfEdge.next;
      } while (currentHalfEdge !== face.halfEdge);

      endShape(CLOSE);
    }
  }
}

サンプル

let model;

function setup() {
  createCanvas(800, 600, WEBGL);
  
  // ここでハーフエッジモデルを読み込むか、モデルの頂点と面を手動で設定します
  model = new HalfEdgeModel();
  
  // 例として、簡単な三角形を作成します（実際のデータに応じて変更してください）
  const v1 = new Vertex(0, 50, 0);
  const v2 = new Vertex(-50, -50, 0);
  const v3 = new Vertex(50, -50, 0);
  
  model.vertices = [v1, v2, v3];
  
  const f = new Face();
  const he1 = new HalfEdge();
  const he2 = new HalfEdge();
  const he3 = new HalfEdge();

  he1.vertex = v1;
  he1.next = he2;
  he1.face = f;

  he2.vertex = v2;
  he2.next = he3;
  he2.face = f;

  he3.vertex = v3;
  he3.next = he1;
  he3.face = f;

  f.halfEdge = he1;

  model.faces = [f];
}

function draw() {
  background(220);
  rotateX(frameCount * 0.01);
  rotateY(frameCount * 0.01);
  
  model.display();
}


// ハーフエッジのクラス定義
class HalfEdge {
  constructor() {
    this.vertex = null; // このハーフエッジの端点となる頂点
    this.opposite = null; // 反対のハーフエッジ
    this.face = null; // このハーフエッジが属する面
    this.next = null; // 同じ面の次のハーフエッジ
  }
}

// 頂点のクラス定義
class Vertex {
  constructor(x, y, z) {
    this.position = createVector(x, y, z); // p5.jsのベクトルを使用して3D座標を保存
    this.halfEdge = null; // この頂点から出るハーフエッジの1つ
  }
}

// 面のクラス定義
class Face {
  constructor() {
    this.halfEdge = null; // この面を構成するハーフエッジの1つ
  }
}

class HalfEdgeModel {
  constructor() {
    this.faces = [];
    this.vertices = [];
  }

  display() {
    for (const face of this.faces) {
      beginShape();

      let currentHalfEdge = face.halfEdge;
      do {
        const pos = currentHalfEdge.vertex.position;
        vertex(pos.x, pos.y, pos.z);
        currentHalfEdge = currentHalfEdge.next;
      } while (currentHalfEdge !== face.halfEdge);

      endShape(CLOSE);
    }
  }
}

テキスト（OBJフォーマット）→ハーフエッジ

三角

let model;

function setup() {
  createCanvas(800, 600, WEBGL);
  
  const objString = `
    v 0 50 0
    v -50 -50 0
    v 50 -50 0
    f 1 2 3
  `;
  
  model = objToHalfEdgeModel(objString);
}

function draw() {
  background(220);
  rotateX(frameCount * 0.01);
  rotateY(frameCount * 0.01);
  
  model.display();
}


function objToHalfEdgeModel(objString) {
  const lines = objString.split('\n');
  const vertices = [];
  const faces = [];
  const halfEdges = [];

  for (const line of lines) {
    const parts = line.split(' ').filter(Boolean);  // 空白文字を除外

    switch (parts[0]) {
      case 'v':
        const vertex = new Vertex(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
        vertices.push(vertex);
        break;

      case 'f':
        const face = new Face();
        const faceEdges = [];
        for (let i = 1; i < parts.length; i++) {
          const vertexIndex = parseInt(parts[i]) - 1;
          const he = new HalfEdge();
          he.vertex = vertices[vertexIndex];
          he.face = face;
          faceEdges.push(he);

          if (i > 1) {
            faceEdges[i - 2].next = he;
          }
        }
        faceEdges[faceEdges.length - 1].next = faceEdges[0];  // close the loop

        face.halfEdge = faceEdges[0];
        faces.push(face);
        halfEdges.push(...faceEdges);
        break;
    }
  }

  // Pairing opposite half edges (省略: ペアリング部分を追加する必要があります)

  const model = new HalfEdgeModel();
  model.faces = faces;
  model.vertices = vertices;

  return model;
}



// ハーフエッジのクラス定義
class HalfEdge {
  constructor() {
    this.vertex = null; // このハーフエッジの端点となる頂点
    this.opposite = null; // 反対のハーフエッジ
    this.face = null; // このハーフエッジが属する面
    this.next = null; // 同じ面の次のハーフエッジ
  }
}

// 頂点のクラス定義
class Vertex {
  constructor(x, y, z) {
    this.position = createVector(x, y, z); // p5.jsのベクトルを使用して3D座標を保存
    this.halfEdge = null; // この頂点から出るハーフエッジの1つ
  }
}

// 面のクラス定義
class Face {
  constructor() {
    this.halfEdge = null; // この面を構成するハーフエッジの1つ
  }
}

class HalfEdgeModel {
  constructor() {
    this.faces = null;
    this.vertices = null;
  }
  display() {
    for (const face of this.faces) {
      beginShape();

      let currentHalfEdge = face.halfEdge;
      do {
        const pos = currentHalfEdge.vertex.position;
        vertex(pos.x, pos.y, pos.z);
        currentHalfEdge = currentHalfEdge.next;
      } while (currentHalfEdge !== face.halfEdge);

      endShape(CLOSE);
    }
  }  
}

立方体

let model;

const objString = `
v -0.5 -0.5 -0.5
v 0.5 -0.5 -0.5
v 0.5 0.5 -0.5
v -0.5 0.5 -0.5
v -0.5 -0.5 0.5
v 0.5 -0.5 0.5
v 0.5 0.5 0.5
v -0.5 0.5 0.5
f 1 2 3 4
f 5 6 7 8
f 1 2 6 5
f 2 3 7 6
f 3 4 8 7
f 4 1 5 8
`;

function setup() {
  createCanvas(800, 600, WEBGL);
  model = objToHalfEdgeModel(objString);
}

function draw() {
  background(220);
  rotateX(frameCount * 0.01);
  rotateY(frameCount * 0.01);
  
  scale(200); // ここで立方体のサイズを調整
  
  model.display();
}


function objToHalfEdgeModel(objString) {
  const lines = objString.split('\n');
  const vertices = [];
  const faces = [];
  const halfEdges = [];

  for (const line of lines) {
    const parts = line.split(' ').filter(Boolean);  // 空白文字を除外

    switch (parts[0]) {
      case 'v':
        const vertex = new Vertex(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
        vertices.push(vertex);
        break;

      case 'f':
        const face = new Face();
        const faceEdges = [];
        for (let i = 1; i < parts.length; i++) {
          const vertexIndex = parseInt(parts[i]) - 1;
          const he = new HalfEdge();
          he.vertex = vertices[vertexIndex];
          he.face = face;
          faceEdges.push(he);

          if (i > 1) {
            faceEdges[i - 2].next = he;
          }
        }
        faceEdges[faceEdges.length - 1].next = faceEdges[0];  // close the loop

        face.halfEdge = faceEdges[0];
        faces.push(face);
        halfEdges.push(...faceEdges);
        break;
    }
  }

  // Pairing opposite half edges (省略: ペアリング部分を追加する必要があります)

  const model = new HalfEdgeModel();
  model.faces = faces;
  model.vertices = vertices;

  return model;
}



// ハーフエッジのクラス定義
class HalfEdge {
  constructor() {
    this.vertex = null; // このハーフエッジの端点となる頂点
    this.opposite = null; // 反対のハーフエッジ
    this.face = null; // このハーフエッジが属する面
    this.next = null; // 同じ面の次のハーフエッジ
  }
}

// 頂点のクラス定義
class Vertex {
  constructor(x, y, z) {
    this.position = createVector(x, y, z); // p5.jsのベクトルを使用して3D座標を保存
    this.halfEdge = null; // この頂点から出るハーフエッジの1つ
  }
}

// 面のクラス定義
class Face {
  constructor() {
    this.halfEdge = null; // この面を構成するハーフエッジの1つ
  }
}

class HalfEdgeModel {
  constructor() {
    this.faces = null;
    this.vertices = null;
  }
  display() {
    for (const face of this.faces) {
      beginShape();

      let currentHalfEdge = face.halfEdge;
      do {
        const pos = currentHalfEdge.vertex.position;
        vertex(pos.x, pos.y, pos.z);
        currentHalfEdge = currentHalfEdge.next;
      } while (currentHalfEdge !== face.halfEdge);

      endShape(CLOSE);
    }
  }  
}

この記事が気に入ったらサポートをしてみませんか？