ハーフエッジ②~とりあえず表示するとこまでやるべーよの巻~
ChatGPT4くんはこのへんくらいから既にポンコツです。
OBJフォーマット
OBJフォーマットは比較的シンプルなテキストベースのフォーマットですが、多くの異なるオプションや構造をサポートしています。以下は、実際のOBJファイルの扱いにおいて考慮すべきいくつかのエッジケースや機能です:
ノーマルベクトル (vn): 各頂点には、面の方向を示すノーマルベクトルが関連付けられる場合があります。これは、シェーディングやレンダリングの際に使用されます。
頂点の再利用:同じ頂点が異なる面で再利用されることがよくあります。メモリ効率を考慮して頂点を再利用する必要があります。
ライン要素 (l): OBJファイルは、三角形や四角形だけでなく、ラインセグメントもサポートしています。
グループとオブジェクト (g と o): これにより、シングルのOBJファイル内で複数のメッシュやサブオブジェクトを定義できます。
マテリアルライブラリの参照 (mtllib): OBJファイルは、別のMTLファイルにマテリアルの定義を参照することができます。
スムージンググループ (s): これは、どの面が一緒にスムーズにレンダリングされるかを制御するためのものです。
コメント (#): OBJファイル内にはコメント行が含まれる場合があり、これらは解析中に無視されるべきです。
異なる面のトポロジー: たとえば、三角形、四角形、そしてそれ以上の多角形など、異なる種類の面をサポートする必要があるかもしれません。
頂点インデックスのネガティブ値: これは現在の頂点リストの終端からの相対的なインデックスを示しています。
頂点、テクスチャ、ノーマルの組み合わせ: たとえば、f 1/2/3 4/5/6 7/8/9のように、各頂点がテクスチャ座標とノーマルの両方を持っている場合や、ノーマルやテクスチャ座標が欠落している場合があります。
エラーハンドリング: 不完全なデータ、予期しないフォーマットの行、予期しない行の終了など、さまざまなエラーケースを適切に処理する必要があります。
最適化とパフォーマンス: 大きなOBJファイルを扱う場合、メモリ使用量や解析速度など、パフォーマンスの問題も考慮する必要があります。
テクスチャ座標
テクスチャ座標(しばしばUV座標とも呼ばれます)は、3Dモデルの表面に2Dテクスチャイメージをマッピングするための座標系です。テクスチャ座標は、2Dの座標系で、通常、Uが水平方向、Vが垂直方向になります。
OBJファイルフォーマットにおいて、テクスチャ座標はvtキーワードに続く2つの数値で表されます。これは2Dの座標値で、通常、0から1の間の範囲に収まりますが、その範囲を超えることも可能です。
例えば、以下の行はテクスチャ座標の定義を示しています:
vt 0.5 0.5
この場合、U(水平座標)は0.5、V(垂直座標)は0.5となります。
OBJファイルの面定義部分(fキーワードに続く部分)では、頂点のインデックスとその頂点に対応するテクスチャ座標のインデックスが/で区切られて結びつけられます。例:
f 1/1 2/2 3/3 4/4
この例では、1番目の頂点に1番目のテクスチャ座標が、2番目の頂点に2番目のテクスチャ座標が、というように関連付けられています。
要するに、テクスチャ座標のインデックスは、どの頂点がどの2Dテクスチャ座標にマッピングされるかを指定するためのものです。これにより、3Dモデルの任意の頂点に、2Dテクスチャイメージの特定の部分(ピクセル)を関連付けることができます。
テクスチャ座標を追加
の、例。
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
vt 0 0
vt 1 0
vt 1 1
vt 0 1
f 1/1 2/2 3/3 4/4
f 5/1 6/2 7/3 8/4
f 1/1 2/2 6/2 5/1
f 2/2 3/3 7/3 6/2
f 3/3 4/4 8/4 7/3
f 4/4 1/1 5/1 8/4
`;
テクスチャサンプル
画像ロードテスト
let img;
function preload() {
img = loadImage('001.png');
}
function setup() {
createCanvas(800, 600);
image(img, 0, 0, 800, 600);
}
テクスチャ反映テスト
let img;
function preload() {
img = loadImage('001.png');
}
function setup() {
createCanvas(800, 600, WEBGL);
}
function draw() {
background(220);
texture(img);
textureMode(NORMAL);
beginShape();
vertex(-100, -100, 0, 0, 0);
vertex(100, -100, 0, 1, 0);
vertex(100, 100, 0, 1, 1);
vertex(-100, 100, 0, 0, 1);
endShape(CLOSE);
}
立方体張り付け
現状頂点とテクスチャ座標は全部1対1。
ある頂点に4面が接している場合、頂点が4つ複製されることになり、
理解してないと結構な欠陥。
注意:プラスマイナス前後左右前奥、全部逆の可能性があります。
0.5(右), 0.5(下), 0.5(手前)
-0.5(左), -0.5(上), -0.5(奥)
vt 0 0(画像左上)
vt 1 0(画像右上)
vt 1 1(画像右下)
vt 0 1(画像左下)
f
時計回りで法線外
// 1. objStringにテクスチャ座標を追加
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
vt 0 0
vt 1 0
vt 1 1
vt 0 1
f 1/1 2/2 3/3 4/4
f 8/1 7/2 6/3 5/4
f 5/1 6/2 2/3 1/4
f 2/1 6/2 7/3 3/4
f 4/1 3/2 7/3 8/4
f 5/1 1/2 4/3 8/4
`;
let img;
function preload() {
img = loadImage('001.png'); // テクスチャ画像をプリロード
}
function setup() {
createCanvas(800, 600, WEBGL);
myModel = objToHalfEdgeModel(objString);
//myModel.display(img);
}
function draw() {
background(220);
rotateX(frameCount * 0.01);
rotateY(frameCount * 0.01);
scale(200); // ここで立方体のサイズを調整
myModel.display(img);
//noLoop();
}
function objToHalfEdgeModel(objString) {
const lines = objString.split('\n');
const vertices = [];
const faces = [];
const halfEdges = [];
const textureCoords = []; // 2. テクスチャ座標のための配列を追加
let faceCount = 0;
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 'vt': // テクスチャ座標の場合
textureCoords.push(createVector(parseFloat(parts[1]), parseFloat(parts[2])));
break;
case 'f':
const face = new Face(`face${++faceCount}`); // 2. 名前を付けてFaceインスタンスを生成
const faceEdges = [];
for (let i = 1; i < parts.length; i++) {
const indices = parts[i].split('/');
const vertexIndex = parseInt(indices[0]) - 1;
const textureIndex = parseInt(indices[1]) - 1;
const he = new HalfEdge();
const v = vertices[vertexIndex];
he.vertex = new Vertex(v.position.x, v.position.y, v.position.z);
he.face = face;
he.vertex.textureCoord = textureCoords[textureIndex]; // テクスチャ座標をハーフエッジの頂点に設定
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つ
this.textureCoord = createVector(0, 0); // テクスチャ座標を保存
}
}
// 面のクラス定義
class Face {
constructor(name) {
this.name = name; // 1. Faceクラスにname属性を追加
this.halfEdge = null; // この面を構成するハーフエッジの1つ
}
}
class HalfEdgeModel {
constructor() {
this.faces = null;
this.vertices = null;
}
display(imgTexture) {
texture(imgTexture); // ここでテクスチャを設定
textureMode(NORMAL);
for (const face of this.faces) {
//console.log(`Drawing ${face.name}`); // 3. faceの名前をログに表示
beginShape();
let currentHalfEdge = face.halfEdge;
do {
const pos = currentHalfEdge.vertex.position;
const tex = currentHalfEdge.vertex.textureCoord;
//console.log(`Position: (${pos.x}, ${pos.y}, ${pos.z}), Texture: (${tex.x}, ${tex.y})`);
vertex(pos.x, pos.y, pos.z, tex.x, tex.y);
currentHalfEdge = currentHalfEdge.next;
} while (currentHalfEdge !== face.halfEdge);
endShape(CLOSE);
}
}
}
座標反対の場合
// 1. objStringにテクスチャ座標を追加
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
vt 0 0
vt 1 0
vt 1 1
vt 0 1
f 2/1 1/2 4/3 3/4
f 5/1 6/2 7/3 8/4
f 6/1 5/2 1/3 2/4
f 6/1 2/2 3/3 7/4
f 3/1 4/2 8/3 7/4
f 1/1 5/2 8/3 4/4
`;
let img;
function preload() {
img = loadImage('001.png'); // テクスチャ画像をプリロード
}
function setup() {
createCanvas(800, 600, WEBGL);
myModel = objToHalfEdgeModel(objString);
//myModel.display(img);
}
function draw() {
background(220);
rotateX(frameCount * 0.01);
rotateY(frameCount * 0.01);
scale(200); // ここで立方体のサイズを調整
myModel.display(img);
//noLoop();
}
function objToHalfEdgeModel(objString) {
const lines = objString.split('\n');
const vertices = [];
const faces = [];
const halfEdges = [];
const textureCoords = []; // 2. テクスチャ座標のための配列を追加
let faceCount = 0;
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 'vt': // テクスチャ座標の場合
textureCoords.push(createVector(parseFloat(parts[1]), parseFloat(parts[2])));
break;
case 'f':
const face = new Face(`face${++faceCount}`); // 2. 名前を付けてFaceインスタンスを生成
const faceEdges = [];
for (let i = 1; i < parts.length; i++) {
const indices = parts[i].split('/');
const vertexIndex = parseInt(indices[0]) - 1;
const textureIndex = parseInt(indices[1]) - 1;
const he = new HalfEdge();
const v = vertices[vertexIndex];
he.vertex = new Vertex(v.position.x, v.position.y, v.position.z);
he.face = face;
he.vertex.textureCoord = textureCoords[textureIndex]; // テクスチャ座標をハーフエッジの頂点に設定
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つ
this.textureCoord = createVector(0, 0); // テクスチャ座標を保存
}
}
// 面のクラス定義
class Face {
constructor(name) {
this.name = name; // 1. Faceクラスにname属性を追加
this.halfEdge = null; // この面を構成するハーフエッジの1つ
}
}
class HalfEdgeModel {
constructor() {
this.faces = null;
this.vertices = null;
}
display(imgTexture) {
texture(imgTexture); // ここでテクスチャを設定
textureMode(NORMAL);
for (const face of this.faces) {
//console.log(`Drawing ${face.name}`); // 3. faceの名前をログに表示
beginShape();
let currentHalfEdge = face.halfEdge;
do {
const pos = currentHalfEdge.vertex.position;
const tex = currentHalfEdge.vertex.textureCoord;
//console.log(`Position: (${pos.x}, ${pos.y}, ${pos.z}), Texture: (${tex.x}, ${tex.y})`);
vertex(pos.x, pos.y, pos.z, tex.x, tex.y);
currentHalfEdge = currentHalfEdge.next;
} while (currentHalfEdge !== face.halfEdge);
endShape(CLOSE);
}
}
}
行ごと解説
split, filter
const parts = line.split(' ').filter(Boolean);
split(' '):文字列を空白文字(スペース)で分割します。これにより、例えば"v 0.0 0.1 0.2"という行は["v", "0.0", "0.1", "0.2"]のような配列になります。
filter(Boolean):配列の要素のうち、空文字列やundefinedなど"falsy"な値をフィルタリング(除外)します。これは、入力データにおいて連続する空白や行末の余計な空白を取り除くために使用されます。JavaScriptにおいて、Booleanをfilterに渡すと、その配列の要素がBooleanコンテキストで真と評価されるかどうかに基づいてフィルタリングを行います。
例として、"v 0.0 0.1 0.2 "というように余計なスペースが含まれる行があった場合、split(' ')だけで処理すると["v", "", "", "0.0", "", "0.1", "", "0.2", "", "", ""]という配列になります。このような不要な空文字列を取り除くために、filter(Boolean)が使用されます。
したがって、結果として得られるpartsは、その行の意味ある部分だけを含む配列となります。この配列を基に、行が頂点を示すのか、テクスチャ座標を示すのか、面を示すのかを判別し、それぞれのデータを解析しています。
parseFloat
const vertex = new Vertex(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
parseFloat は JavaScript における組み込みの関数で、文字列を浮動小数点数に変換します。以下に parseFloat の基本的な仕様を示します:
引数:parseFloat は一つの引数、つまり変換対象となる文字列を受け取ります。
戻り値:関数は文字列の先頭から数値として認識できる最長の連続した文字列を浮動小数点数として返します。文字列に数値が含まれていない場合や、数値に変換できない場合は NaN (Not a Number) を返します。
いくつかの例を示します:
parseFloat("3.14") => 3.14
parseFloat("-3.14") => -3.14
parseFloat("3.14abc") => 3.14 (文字列 "abc" は無視されます)
parseFloat("abc3.14") => NaN (文字列の先頭が数値でないので、変換は失敗します)
parseFloat(" 3.14 ") => 3.14 (先頭および末尾の空白は無視されます)
この関数は特に 3D モデリングのような分野でファイルを解析する際に役立ちます。OBJ ファイルフォーマットのように、テキストベースで数値データを保存しているファイルから数値を読み取る際に、この関数を使用して文字列から数値への変換を行うことができます。
インデックス化
Vertexクラスに座標情報を持たせず、インデックスのみ持たせた場合。
つまりある程度気軽にVertexクラスを複製したい場合。
座標、およびテクスチャ座標はモデルクラスが持つ。
(正しいふるまいかどうか不明)
// 1. objStringにテクスチャ座標を追加
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
vt 0 0
vt 1 0
vt 1 1
vt 0 1
f 1/1 2/2 3/3 4/4
f 8/1 7/2 6/3 5/4
f 5/1 6/2 2/3 1/4
f 2/1 6/2 7/3 3/4
f 4/1 3/2 7/3 8/4
f 5/1 1/2 4/3 8/4
`;
let img;
function preload() {
img = loadImage('001.jpg'); // テクスチャ画像をプリロード
}
function setup() {
createCanvas(800, 600, WEBGL);
myModel = objToHalfEdgeModel(objString);
//myModel.display(img);
}
function draw() {
background(220);
rotateX(frameCount * 0.01);
rotateY(frameCount * 0.01);
scale(200); // ここで立方体のサイズを調整
myModel.display(img);
//noLoop();
}
function objToHalfEdgeModel(objString) {
const lines = objString.split('\n');
const vertexClasses = [];
const faceClasses = [];
const halfEdgeClasses = [];
const vertices = [];
const textureCoords = [];
let vertexCount = 0;
let faceCount = 0;
for (const line of lines) {
const parts = line.split(' ').filter(Boolean); // 空白文字を除外
switch (parts[0]) {
case 'v':
const vertex = createVector(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
vertices.push(vertex);
const vertexClass = new Vertex(vertexCount);
vertexClasses.push(vertexClass);
vertexCount++;
break;
case 'vt': // テクスチャ座標の場合
textureCoords.push(createVector(parseFloat(parts[1]), parseFloat(parts[2])));
break;
case 'f':
const face = new Face(`face${++faceCount}`);
const faceEdges = [];
for (let i = 1; i < parts.length; i++) {
const indices = parts[i].split('/');
const vertexIndex = parseInt(indices[0]) - 1;
const textureIndex = parseInt(indices[1]) - 1;
const he = new HalfEdge();
const v = vertexClasses[vertexIndex];
he.vertex = Vertex.copy(v);
he.face = face;
he.vertex.textureCoordIndex = textureIndex;
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];
faceClasses.push(face);
halfEdgeClasses.push(...faceEdges);
break;
}
}
// Pairing opposite half edges (省略: ペアリング部分を追加する必要があります)
const model = new HalfEdgeModel();
model.faces = faceClasses;
model.vertices = vertices;
model.textureCoords = textureCoords;
return model;
}
// ハーフエッジのクラス定義
class HalfEdge {
constructor() {
this.vertex = null; // このハーフエッジの端点となる頂点
this.opposite = null; // 反対のハーフエッジ
this.face = null; // このハーフエッジが属する面
this.next = null; // 同じ面の次のハーフエッジ
}
}
// 頂点のクラス定義
class Vertex {
constructor(index) {
this.vertexIndex = index;
this.halfEdge = null; // この頂点から出るハーフエッジの1つ
this.textureCoordIndex = -1; // テクスチャ座標を保存
}
// コピーメソッドを追加
static copy(vertex) {
const copiedVertex = new Vertex(vertex.vertexIndex);
copiedVertex.halfEdge = vertex.halfEdge; // 注意: これは参照コピーです
copiedVertex.textureCoordIndex = vertex.textureCoordIndex;
return copiedVertex;
}
}
// 面のクラス定義
class Face {
constructor(name) {
this.name = name; // 1. Faceクラスにname属性を追加
this.halfEdge = null; // この面を構成するハーフエッジの1つ
}
}
class HalfEdgeModel {
constructor() {
this.faces = null;
this.vertices = null;
this.textureCoords = null;
}
display(imgTexture) {
texture(imgTexture); // ここでテクスチャを設定
textureMode(NORMAL);
for (const face of this.faces) {
//console.log(`Drawing ${face.name}`); // 3. faceの名前をログに表示
beginShape();
let currentHalfEdge = face.halfEdge;
do {
const verIndex = currentHalfEdge.vertex.vertexIndex;
const texIndex = currentHalfEdge.vertex.textureCoordIndex;
let v = this.vertices[verIndex];
let tv = this.textureCoords[texIndex];
//console.log(`Position: (${pos.x}, ${pos.y}, ${pos.z}), Texture: (${tex.x}, ${tex.y})`);
vertex(v.x, v.y, v.z, tv.x, tv.y);
currentHalfEdge = currentHalfEdge.next;
} while (currentHalfEdge !== face.halfEdge);
endShape(CLOSE);
}
}
}
ペアリング機構
全探索
ChatGPT4くんの答え。
計算量は O(n^2)。未テスト。
// Pairing opposite half edges
for (const he1 of halfEdgeClasses) {
if (!he1.opposite) { // Already paired
for (const he2 of halfEdgeClasses) {
if (!he2.opposite && he1 !== he2) { // Not the same edge and not already paired
const v1Origin = he1.vertex.vertexIndex;
const v1Dest = he1.next.vertex.vertexIndex;
const v2Origin = he2.vertex.vertexIndex;
const v2Dest = he2.next.vertex.vertexIndex;
// Check if they are opposites
if (v1Origin === v2Dest && v1Dest === v2Origin) {
he1.opposite = he2;
he2.opposite = he1;
break; // Break out of inner loop once a pair is found
}
}
}
}
}
ハッシュ
計算量はO(n)
ハッシュ(または辞書や連想配列とも呼ばれる)を使用することで、対応するハーフエッジのペアリングを大幅に高速化することができます。
ここでは、ハーフエッジの両端の頂点のIDをキーとしたハッシュを作成し、それを使用してハーフエッジをペアリングする方法を示します。
以下の手順に従います:
ハーフエッジを作成するたびに、ハッシュにそのハーフエッジを追加します。キーはハーフエッジの始点と終点の頂点IDから生成されます。
ハーフエッジの逆を見つけるためには、ハッシュを使用して終点と始点の頂点IDのキーを検索します。
と、ChatGPT4くんはいうものの、提出された下記のコードをみるに
ハッシュ検索時に
const oppKey = `${he.next.vertex.vertexIndex}-${he.vertex.vertexIndex}`;
を用いていることから、これはnext-currentである。つまり終点と始点である。ということは生成時にcurrent-prevであるかcurrent-nextでなければならず(ループの状況による)、これは始点と終点である。みると
const key = `${vertexIndex}-${faceEdges[(i - 1 + parts.length - 1) % (parts.length - 1)].vertex.vertexIndex}`;
は確かにcurrent-prevっぽくはある。
// Create a hash to store half edges
const halfEdgeHash = {};
// ... (objToHalfEdgeModel関数内のコード)
// When creating the half edges:
for (let i = 1; i < parts.length; i++) {
// ... (既存のハーフエッジ作成コード)
// Store the half edge in the hash using vertex indices as key
const key = `${vertexIndex}-${faceEdges[(i - 1 + parts.length - 1) % (parts.length - 1)].vertex.vertexIndex}`;
halfEdgeHash[key] = he;
}
// Pairing opposite half edges
for (const he of halfEdgeClasses) {
if (!he.opposite) { // Not already paired
const oppKey = `${he.next.vertex.vertexIndex}-${he.vertex.vertexIndex}`;
if (halfEdgeHash.hasOwnProperty(oppKey)) {
he.opposite = halfEdgeHash[oppKey];
he.opposite.opposite = he;
}
}
}
とりあえず組み込んだもの
function objToHalfEdgeModel(objString) {
const lines = objString.split('\n');
const vertexClasses = [];
const faceClasses = [];
const halfEdgeClasses = [];
const vertices = [];
const textureCoords = [];
let vertexCount = 0;
let faceCount = 0;
// Create a hash to store half edges
const halfEdgeHash = {};
for (const line of lines) {
const parts = line.split(' ').filter(Boolean); // Remove whitespace
switch (parts[0]) {
case 'v':
const vertex = createVector(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
vertices.push(vertex);
const vertexClass = new Vertex(vertexCount);
vertexClasses.push(vertexClass);
vertexCount++;
break;
case 'vt':
textureCoords.push(createVector(parseFloat(parts[1]), parseFloat(parts[2])));
break;
case 'f':
const face = new Face(`face${++faceCount}`);
const faceEdges = [];
for (let i = 1; i < parts.length; i++) {
const indices = parts[i].split('/');
const vertexIndex = parseInt(indices[0]) - 1;
const textureIndex = parseInt(indices[1]) - 1;
const he = new HalfEdge();
const v = vertexClasses[vertexIndex];
he.vertex = Vertex.copy(v);
he.face = face;
he.vertex.textureCoordIndex = textureIndex;
faceEdges.push(he);
if (i > 1) {
faceEdges[i - 2].next = he;
}
// Store the half edge in the hash using vertex indices as key
const key = `${vertexIndex}-${faceEdges[(i - 1 + parts.length - 1) % (parts.length - 1)].vertex.vertexIndex}`;
halfEdgeHash[key] = he;
}
faceEdges[faceEdges.length - 1].next = faceEdges[0]; // close the loop
face.halfEdge = faceEdges[0];
faceClasses.push(face);
halfEdgeClasses.push(...faceEdges);
break;
}
}
// Pairing opposite half edges
for (const he of halfEdgeClasses) {
if (!he.opposite) { // Not already paired
const oppKey = `${he.next.vertex.vertexIndex}-${he.vertex.vertexIndex}`;
if (halfEdgeHash.hasOwnProperty(oppKey)) {
he.opposite = halfEdgeHash[oppKey];
he.opposite.opposite = he;
}
}
}
const model = new HalfEdgeModel();
model.faces = faceClasses;
model.vertices = vertices;
model.textureCoords = textureCoords;
return model;
}
ハッシュ[ChatGPT4くんの解説]
for (let i = 1; i < parts.length; i++) {
const indices = parts[i].split('/');
const vertexIndex = parseInt(indices[0]) - 1;
const textureIndex = parseInt(indices[1]) - 1;
const he = new HalfEdge();
const v = vertexClasses[vertexIndex];
he.vertex = Vertex.copy(v);
he.face = face;
he.vertex.textureCoordIndex = textureIndex;
faceEdges.push(he);
if (i > 1) {
faceEdges[i - 2].next = he;
}
// Store the half edge in the hash using vertex indices as key
const key = `${vertexIndex}-${faceEdges[(i - 1 + parts.length - 1) % (parts.length - 1)].vertex.vertexIndex}`;
halfEdgeHash[key] = he;
}
faceEdges[faceEdges.length - 1].next = faceEdges[0]; // close the loop
const key = `${vertexIndex}-${faceEdges[(i - 1 + parts.length - 1) % (parts.length - 1)].vertex.vertexIndex}`;
始点:${vertexIndex}
終点:${faceEdges[(i - 1 + parts.length - 1) % (parts.length - 1)].vertex.vertexIndex}
つまりこの時点で逆向きのハーフエッジのハッシュを作っておき、後の検索で順向きのハッシュを使用するということ。
${faceEdges[(i - 1 + parts.length - 1) % (parts.length - 1)].vertex.vertexIndex}
は
${faceEdges[(i - 1 + faceEdges.length) % (faceEdges.length)].vertex.vertexIndex}
での意味である。
ハッシュの元になる座標(の、今の仕組みではインデックス情報)を格納しているのはparts(OBJ形式の入力文字列から切り出されたインデックス情報)とfaceEdges(partsのループ中に生成されていくfaceごとのHalfEdge)である。
partsからprevの座標情報にアクセスするには、
現状parts[0]にはラベル情報が格納されていて、これを無視しなければならない。iのループインデックスが1から始まるのはそのためで、prevにしろnextにしろ、インデックス[0]を飛ばす機構が必要。
faceEdgesからアクセスする場合、この配列はiとともに生成されたHalfEdgeが格納されていく。なのでprevを求める場合は初回を飛ばすなり別に計算する必要がある。nextの場合は最後に別計算が必要となる。
ChatGPTくんのコードでは、ペアリング設定時、実際のハッシュ検索時は順方向で検索する。そのためハッシュキー生成時、ハッシュ格納時は逆方向でキーを作っておかないとこの時にヒットしない。
// Pairing opposite half edges
for (const he of halfEdgeClasses) {
if (!he.opposite) { // Not already paired
const oppKey = `${he.next.vertex.vertexIndex}-${he.vertex.vertexIndex}`;
if (halfEdgeHash.hasOwnProperty(oppKey)) {
he.opposite = halfEdgeHash[oppKey];
he.opposite.opposite = he;
}
}
テンプレートリテラル (${...})
ここではテンプレートリテラルを使用して文字列を生成しています。${...} の中の式は評価され、その結果が文字列に組み込まれます。
${vertexIndex}-:
vertexIndexは現在のハーフエッジの始点の頂点IDです。これをキーの最初の部分として使用します。
faceEdges[(i - 1 + parts.length - 1) % (parts.length - 1)].vertex.vertexIndex:
これは現在のハーフエッジの終点(逆向き、一個前の)の頂点IDを取得するためのコードです。(このまま実装しても失敗する)
(i-1+(length-1))%(length-1)はインデックスを1つ戻す操作。
本来モジュロをもちいたインデックス戻しは(i-1+length)%lengthでよいが、parts.length - 1とすることでOBJファイルの形式に対応している、とはChatGPT4くんの言い分。
インデックスが0の時は-1およびモジュロによって末尾のインデックスを取得するのが通常。しかしOBJファイルの形式の場合、インデックス0は通常アクセスしない(iのループインデックスは1から始まる)
//これが
f 1/1 2/2 3/3 4/4
//こうなってる
parts = ["f", "1/1", "2/2", "3/3", "4/4"]
parts.length - 1は座標の数を正確に表す。つまり今の場合、fの分はカウントしない。 ["1/1", "2/2", "3/3", "4/4"]である。
一方でvertexIndex もfaceEdgesはインデックスがズレる。
i==1の時vertexIndex==0, faceEdgesからprevを取得するにはvertexIndexからさらに-1であるから、よって
${faceEdges[(i - 2 + faceEdges.length) %(faceEdges.length)].vertex.vertexIndex}
あたりが適切と思われる。
ただしfaceEdgesは長さが変化するので、
parts.length-1を利用すると
${faceEdges[(i - 2 + parts.length-1) %(parts.length-1)].vertex.vertexIndex}
実際にやってみるとうまく動かない。
多分、faceEdgesが生成されてないうちからprevを取得しようとしているから。つまり初回スキップで解決できる可能性がある。
試しにテスト中のうまく動かないコード
// 1. objStringにテクスチャ座標を追加
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
vt 0 0
vt 1 0
vt 1 1
vt 0 1
f 1/1 2/2 3/3 4/4
f 8/1 7/2 6/3 5/4
f 5/1 6/2 2/3 1/4
f 2/1 6/2 7/3 3/4
f 4/1 3/2 7/3 8/4
f 5/1 1/2 4/3 8/4
`;
let img;
function preload() {
img = loadImage('001.jpg'); // テクスチャ画像をプリロード
}
function setup() {
createCanvas(800, 600, WEBGL);
myModel = objToHalfEdgeModel(objString);
//myModel.display(img);
}
function draw() {
background(220);
rotateX(frameCount * 0.01);
rotateY(frameCount * 0.01);
scale(200); // ここで立方体のサイズを調整
myModel.display(img);
//noLoop();
}
function objToHalfEdgeModel(objString) {
const lines = objString.split('\n');
const vertexClasses = [];
const faceClasses = [];
const halfEdgeClasses = [];
const vertices = [];
const textureCoords = [];
let vertexCount = 0;
let faceCount = 0;
// Create a hash to store half edges
const halfEdgeHash = {};
for (const line of lines) {
const parts = line.split(' ').filter(Boolean); // Remove whitespace
switch (parts[0]) {
case 'v':
const vertex = createVector(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
vertices.push(vertex);
const vertexClass = new Vertex(vertexCount);
vertexClasses.push(vertexClass);
vertexCount++;
break;
case 'vt':
textureCoords.push(createVector(parseFloat(parts[1]), parseFloat(parts[2])));
break;
case 'f':
const face = new Face(`face${++faceCount}`);
const faceEdges = [];
for (let i = 1; i < parts.length; i++) {
const indices = parts[i].split('/');
const vertexIndex = parseInt(indices[0]) - 1;
const textureIndex = parseInt(indices[1]) - 1;
const he = new HalfEdge();
const v = vertexClasses[vertexIndex];
he.vertex = Vertex.copy(v);
he.face = face;
he.vertex.textureCoordIndex = textureIndex;
faceEdges.push(he);
if (i > 1) {
faceEdges[i - 2].next = he;
}
// Store the half edge in the hash using vertex indices as key
const calculatedIndex = (i - 2 + parts.length-1) % (parts.length-1);
if (faceEdges[calculatedIndex] && faceEdges[calculatedIndex].vertex) {
const key = `${faceEdges[calculatedIndex].vertex.vertexIndex}-${vertexIndex}`;
}
halfEdgeHash[key] = he;
}
faceEdges[faceEdges.length - 1].next = faceEdges[0]; // close the loop
face.halfEdge = faceEdges[0];
faceClasses.push(face);
halfEdgeClasses.push(...faceEdges);
break;
}
}
// Pairing opposite half edges
for (const he of halfEdgeClasses) {
if (!he.opposite) { // Not already paired
const oppKey = `${he.next.vertex.vertexIndex}-${he.vertex.vertexIndex}`;
if (halfEdgeHash.hasOwnProperty(oppKey)) {
he.opposite = halfEdgeHash[oppKey];
he.opposite.opposite = he;
}
}
}
const model = new HalfEdgeModel();
model.faces = faceClasses;
model.vertices = vertices;
model.textureCoords = textureCoords;
return model;
}
// ハーフエッジのクラス定義
class HalfEdge {
constructor() {
this.vertex = null; // このハーフエッジの端点となる頂点
this.opposite = null; // 反対のハーフエッジ
this.face = null; // このハーフエッジが属する面
this.next = null; // 同じ面の次のハーフエッジ
}
}
// 頂点のクラス定義
class Vertex {
constructor(index) {
this.vertexIndex = index;
this.halfEdge = null; // この頂点から出るハーフエッジの1つ
this.textureCoordIndex = -1; // テクスチャ座標を保存
}
// コピーメソッドを追加
static copy(vertex) {
const copiedVertex = new Vertex(vertex.vertexIndex);
copiedVertex.halfEdge = vertex.halfEdge; // 注意: これは参照コピーです
copiedVertex.textureCoordIndex = vertex.textureCoordIndex;
return copiedVertex;
}
}
// 面のクラス定義
class Face {
constructor(name) {
this.name = name; // 1. Faceクラスにname属性を追加
this.halfEdge = null; // この面を構成するハーフエッジの1つ
}
}
class HalfEdgeModel {
constructor() {
this.faces = null;
this.vertices = null;
this.textureCoords = null;
}
display(imgTexture) {
texture(imgTexture); // ここでテクスチャを設定
textureMode(NORMAL);
for (const face of this.faces) {
//console.log(`Drawing ${face.name}`); // 3. faceの名前をログに表示
beginShape();
let currentHalfEdge = face.halfEdge;
do {
const verIndex = currentHalfEdge.vertex.vertexIndex;
const texIndex = currentHalfEdge.vertex.textureCoordIndex;
let v = this.vertices[verIndex];
let tv = this.textureCoords[texIndex];
//console.log(`Position: (${pos.x}, ${pos.y}, ${pos.z}), Texture: (${tex.x}, ${tex.y})`);
vertex(v.x, v.y, v.z, tv.x, tv.y);
currentHalfEdge = currentHalfEdge.next;
} while (currentHalfEdge !== face.halfEdge);
endShape(CLOSE);
}
}
}
結局全然うまくいかないので強引に自分で書いたコード
partsからnextを切り出し、
生成時にnext-currentのキーを作成。
検索時にcurrent-nextとした。
// 1. objStringにテクスチャ座標を追加
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
vt 0 0
vt 1 0
vt 1 1
vt 0 1
f 1/1 2/2 3/3 4/4
f 8/1 7/2 6/3 5/4
f 5/1 6/2 2/3 1/4
f 2/1 6/2 7/3 3/4
f 4/1 3/2 7/3 8/4
f 5/1 1/2 4/3 8/4
`;
let img;
function preload() {
img = loadImage('001.jpg'); // テクスチャ画像をプリロード
}
function setup() {
createCanvas(800, 600, WEBGL);
myModel = objToHalfEdgeModel(objString);
//myModel.display(img);
}
function draw() {
background(220);
rotateX(frameCount * 0.01);
rotateY(frameCount * 0.01);
scale(200); // ここで立方体のサイズを調整
myModel.display(img);
listPairingStatus(myModel.halfEdges); // この行を追加
noLoop(); // 無限ループを防ぐために追加
//noLoop();
}
function objToHalfEdgeModel(objString) {
const lines = objString.split('\n');
const vertexClasses = [];
const faceClasses = [];
const halfEdgeClasses = [];
const vertices = [];
const textureCoords = [];
let vertexCount = 0;
let faceCount = 0;
// Create a hash to store half edges
const halfEdgeHash = {};
for (const line of lines) {
const parts = line.split(' ').filter(Boolean); // Remove whitespace
switch (parts[0]) {
case 'v':
const vertex = createVector(parseFloat(parts[1]), parseFloat(parts[2]), parseFloat(parts[3]));
vertices.push(vertex);
const vertexClass = new Vertex(vertexCount);
vertexClasses.push(vertexClass);
vertexCount++;
break;
case 'vt':
textureCoords.push(createVector(parseFloat(parts[1]), parseFloat(parts[2])));
break;
case 'f':
const face = new Face(`face${++faceCount}`);
const faceEdges = [];
for (let i = 1; i < parts.length; i++) {
const indices = parts[i].split('/');
const vertexIndex = parseInt(indices[0]) - 1;
const textureIndex = parseInt(indices[1]) - 1;
let nextVertexIndex = parseInt(parts[((i+1)%parts.length)].split('/'))-1;
if(i===parts.length-1)
{
nextVertexIndex=parseInt(parts[1].split('/'))-1;
}
const he = new HalfEdge();
const v = vertexClasses[vertexIndex];
he.vertex = Vertex.copy(v);
he.face = face;
he.vertex.textureCoordIndex = textureIndex;
faceEdges.push(he);
if (i > 1) {
faceEdges[i - 2].next = he;
}
const key = `${nextVertexIndex}-${vertexIndex}`;
halfEdgeHash[key] = he;
console.log(`vertexIndex is:${vertexIndex}, oppIndex is:${nextVertexIndex}, Key is: ${key}`);
// const calculatedIndex = (vertexIndex+1)%(parts.length-1);
// const key = `${calculatedIndex}-${vertexIndex}`;
// halfEdgeHash[key] = he;
// console.log(`vertexIndex is:${vertexIndex}, oppIndex is:${calculatedIndex}, Key is: ${key}, parts.length:${parts.length-1}`);
// Store the half edge in the hash using vertex indices as key
// const calculatedIndex = (i - 2 + parts.length-1) % (parts.length-1);
// if (faceEdges[calculatedIndex] && faceEdges[calculatedIndex].vertex) {
// const key = `${faceEdges[calculatedIndex].vertex.vertexIndex}-${vertexIndex}`;
// halfEdgeHash[key] = he;
// console.log(`vertexIndex is:${vertexIndex}, oppIndex is:${calculatedIndex}, Key is: ${key}`);
// }
}
faceEdges[faceEdges.length - 1].next = faceEdges[0]; // close the loop
face.halfEdge = faceEdges[0];
faceClasses.push(face);
halfEdgeClasses.push(...faceEdges);
break;
}
}
// Pairing opposite half edges
let halfEdgeCount = 0; // ハーフエッジの数をカウント
for (const he of halfEdgeClasses) {
he.id = `he${++halfEdgeCount}`; // 一意のIDを設定
if (!he.opposite) { // Not already paired
//const oppKey = `${he.next.vertex.vertexIndex}-${he.vertex.vertexIndex}`;
const oppKey = `${he.vertex.vertexIndex}-${he.next.vertex.vertexIndex}`;
console.log(`PvertexIndex is:${he.vertex.vertexIndex}, PoppIndex is:${he.next.vertex.vertexIndex}, Key is: ${oppKey}`);
if (halfEdgeHash.hasOwnProperty(oppKey)) {
he.opposite = halfEdgeHash[oppKey];
he.opposite.opposite = he;
}
}
}
const model = new HalfEdgeModel();
model.faces = faceClasses;
model.vertices = vertices;
model.textureCoords = textureCoords;
model.halfEdges = halfEdgeClasses;//test用
return model;
}
// 新しいメソッド:ペアリングが正しく行われているか確認
function validatePairing(halfEdgeClasses) {
for (const he of halfEdgeClasses) {
if (!he.opposite || he.opposite.opposite !== he) {
console.error(`Pairing error in half edge: ${he.id}`);
return false;
}
}
console.log("All half edges are paired correctly!");
return true;
}
// 新しいメソッド:各ハーフエッジのペアリング状態を列挙
function listPairingStatus(halfEdgeClasses) {
console.log("Listing pairing status for all half edges:");
for (const he of halfEdgeClasses) {
if (he.opposite) {
console.log(`face: ${he.face.name}, Half edge: ${he.id} is paired with ${he.opposite.id}`);
} else {
console.log(`face: ${he.face.name}, Half edge: ${he.id} is not paired`);
}
}
}
// ハーフエッジのクラス定義
class HalfEdge {
constructor() {
this.id = null; // 追加: ハーフエッジの一意のID
this.vertex = null; // このハーフエッジの端点となる頂点
this.opposite = null; // 反対のハーフエッジ
this.face = null; // このハーフエッジが属する面
this.next = null; // 同じ面の次のハーフエッジ
}
}
// 頂点のクラス定義
class Vertex {
constructor(index) {
this.vertexIndex = index;
this.halfEdge = null; // この頂点から出るハーフエッジの1つ
this.textureCoordIndex = -1; // テクスチャ座標を保存
}
// コピーメソッドを追加
static copy(vertex) {
const copiedVertex = new Vertex(vertex.vertexIndex);
copiedVertex.halfEdge = vertex.halfEdge; // 注意: これは参照コピーです
copiedVertex.textureCoordIndex = vertex.textureCoordIndex;
return copiedVertex;
}
}
// 面のクラス定義
class Face {
constructor(name) {
this.name = name; // 1. Faceクラスにname属性を追加
this.halfEdge = null; // この面を構成するハーフエッジの1つ
}
}
class HalfEdgeModel {
constructor() {
this.faces = null;
this.vertices = null;
this.textureCoords = null;
this.halfEdges = null;//test用
}
display(imgTexture) {
texture(imgTexture); // ここでテクスチャを設定
textureMode(NORMAL);
for (const face of this.faces) {
//console.log(`Drawing ${face.name}`); // 3. faceの名前をログに表示
beginShape();
let currentHalfEdge = face.halfEdge;
do {
const verIndex = currentHalfEdge.vertex.vertexIndex;
const texIndex = currentHalfEdge.vertex.textureCoordIndex;
let v = this.vertices[verIndex];
let tv = this.textureCoords[texIndex];
//console.log(`Position: (${pos.x}, ${pos.y}, ${pos.z}), Texture: (${tex.x}, ${tex.y})`);
vertex(v.x, v.y, v.z, tv.x, tv.y);
currentHalfEdge = currentHalfEdge.next;
} while (currentHalfEdge !== face.halfEdge);
endShape(CLOSE);
}
}
}
ハッシュ[このハッシュは一意か?]
作成されるキーは一意ではありません。それは、同じ始点と終点を共有するハーフエッジが複数存在する場合に同じキーが生成されるためです。これはペアリングを行う際に問題となります。
提供されたコードでは、ハーフエッジを生成する際に始点と終点の頂点インデックスを組み合わせてキーを作成しています。しかし、3Dモデルの辺は、多くの場合、2つの異なる面に属しているため、それらの辺には2つの異なるハーフエッジが存在します。これらのハーフエッジは同じ始点と終点を共有しているため、現在の方法では同じキーが生成されます。
この問題を解決するためには、ハーフエッジがどの面に属しているかもキーに組み込む方法が考えられます。ただし、これはペアリングのロジックを複雑にする可能性があります。
もう一つのシンプルな方法として、ハッシュを2つ使用する方法が考えられます。1つは始点から終点へのハーフエッジを格納するためのもの、もう1つは終点から始点へのハーフエッジを格納するためのものです。これにより、ペアリングを行う際に反対のハーフエッジを迅速に検索できます。
要するに、提供されたコードの方法だけでは、キーが一意になることは保証されません。そのため、ユニークなキーを生成するための追加の方法や情報を組み込む必要があります。
ハッシュ[改良版]
// ...
for (let i = 1; i < parts.length; i++) {
const indices = parts[i].split('/');
const vertexIndex = parseInt(indices[0]) - 1;
const textureIndex = parseInt(indices[1]) - 1;
const he = new HalfEdge();
const v = vertexClasses[vertexIndex];
he.vertex = Vertex.copy(v);
he.face = face;
he.vertex.textureCoordIndex = textureIndex;
faceEdges.push(he);
// ...
// 新しいキーの生成方法
const prevVertexIndex = faceEdges[(i - 1 + parts.length - 1) % (parts.length - 1)].vertex.vertexIndex;
const key = `f${faceCount}_${prevVertexIndex}-${vertexIndex}`;
// ...
}
// ...
この記事が気に入ったらサポートをしてみませんか?