Re: 正在開發新遊戲：星•球
发表于 ： 2026年 5月 17日 20:48
如果一個面的邊跟另一個面的邊相交或相接，則不可用這條邊來判定它們的前後關係。
代码： 全选
// === Use manual Bubble Sort to handle front-facing polygons ===
for (let i = 0; i < frontFaces.length - 1; i++) {
for (let j = 0; j < frontFaces.length - 1 - i; j++) {
// Get adjacent faces for comparison
const a = frontFaces[j];
const b = frontFaces[j + 1];
// Initialize using the traditional Z-depth average difference
let shouldSwap = false;
const zDiff = a.avgZ - b.avgZ;
if (Math.abs(zDiff) < 1.0) {
if (this.check2DOverlap(a.pts, b.pts)) {
let foundRelation = false;
// 1. Test the relative position of projected edges of Face A to the normal vector of Face B
for (let k = 0; k < a.pts.length; k++) {
const p1_2d = a.pts[k], p2_2d = a.pts[(k + 1) % a.pts.length];
if (edgeProjects(p1_2d, p2_2d, b)) {
const p1_3d = a.pts3D[k], p2_3d = a.pts3D[(k + 1) % a.pts.length];
// Check if the entire edge of Face A lies on the plane/surface of Face B
const qB = b.pts3D[0];
const dotP1_B = (p1_3d.x - qB.x) * b.normal3D.x + (p1_3d.y - qB.y) * b.normal3D.y + (p1_3d.z - qB.z) * b.normal3D.z;
const dotP2_B = (p2_3d.x - qB.x) * b.normal3D.x + (p2_3d.y - qB.y) * b.normal3D.y + (p2_3d.z - qB.z) * b.normal3D.z;
// If both endpoints are on Face B's plane, the edge lies on Face B. Skip it.
if (Math.abs(dotP1_B) < 1e-4 && Math.abs(dotP2_B) < 1e-4) {
continue;
}
// NEW: Check if this edge intersects or touches any edge of Face B
let edgeIntersectionDetected = false;
for (let m = 0; m < b.pts3D.length; m++) {
const bp1 = b.pts3D[m];
const bp2 = b.pts3D[(m + 1) % b.pts3D.length];
if (this.areEdgesIntersectingOrTouching(p1_3d, p2_3d, bp1, bp2)) {
edgeIntersectionDetected = true;
break;
}
}
// If an intersection or touch is found, this edge is invalid for depth sorting. Skip it.
if (edgeIntersectionDetected) {
continue;
}
const midX = (p1_3d.x + p2_3d.x) / 2;
const midY = (p1_3d.y + p2_3d.y) / 2;
const midZ = (p1_3d.z + p2_3d.z) / 2;
const dot = (midX - qB.x) * b.normal3D.x + (midY - qB.y) * b.normal3D.y + (midZ - qB.z) * b.normal3D.z;
if (Math.abs(dot) > 1e-4) {
// dot > 0 means Face A is in front of Face B (A occludes B), so A must be drawn later.
// The original order is [a, b] (a drawn first, b drawn later), so they need to be swapped to [b, a].
shouldSwap = dot > 0;
foundRelation = true;
break;
}
}
}
// 2. If no conclusive relation is found from Face A, test the projected edges of Face B relative to the normal vector of Face A
if (!foundRelation) {
for (let k = 0; k < b.pts.length; k++) {
const p1_2d = b.pts[k], p2_2d = b.pts[(k + 1) % b.pts.length];
if (edgeProjects(p1_2d, p2_2d, a)) {
const p1_3d = b.pts3D[k], p2_3d = b.pts3D[(k + 1) % b.pts.length];
// Check if the entire edge of Face B lies on the plane/surface of Face A
const qA = a.pts3D[0];
const dotP1_A = (p1_3d.x - qA.x) * a.normal3D.x + (p1_3d.y - qA.y) * a.normal3D.y + (p1_3d.z - qA.z) * a.normal3D.z;
const dotP2_A = (p2_3d.x - qA.x) * a.normal3D.x + (p2_3d.y - qA.y) * a.normal3D.y + (p2_3d.z - qA.z) * a.normal3D.z;
// If both endpoints are on Face A's plane, the edge lies on Face A. Skip it.
if (Math.abs(dotP1_A) < 1e-4 && Math.abs(dotP2_A) < 1e-4) {
continue;
}
// NEW: Check if this edge intersects or touches any edge of Face A
let edgeIntersectionDetected = false;
for (let m = 0; m < a.pts3D.length; m++) {
const ap1 = a.pts3D[m];
const ap2 = a.pts3D[(m + 1) % a.pts3D.length];
if (this.areEdgesIntersectingOrTouching(p1_3d, p2_3d, ap1, ap2)) {
edgeIntersectionDetected = true;
break;
}
}
// If an intersection or touch is found, this edge is invalid for depth sorting. Skip it.
if (edgeIntersectionDetected) {
continue;
}
const midX = (p1_3d.x + p2_3d.x) / 2;
const midY = (p1_3d.y + p2_3d.y) / 2;
const midZ = (p1_3d.z + p2_3d.z) / 2;
const dot = (midX - qA.x) * a.normal3D.x + (midY - qA.y) * a.normal3D.y + (midZ - qA.z) * a.normal3D.z;
if (Math.abs(dot) > 1e-4) {
// dot > 0 means Face B is in front of Face A (B occludes A), so B must be drawn later.
// The original order is [a, b] where B is already drawn later, so NO swap is needed when dot > 0; swap when dot < 0.
shouldSwap = dot < 0;
foundRelation = true;
break;
}
}
}
}
// 3. If dot product tests cannot determine the order, fall back to pure Z-depth to decide swapping
if (!foundRelation) {
shouldSwap = a.avgZ > b.avgZ;
}
} else {
// No 2D overlap, determine by pure Z-depth
shouldSwap = zDiff > 0;
}
} else {
// Clear depth boundary: larger Z means closer to camera and should be drawn later; swap if a > b
shouldSwap = zDiff > 0;
}
// Perform swap for adjacent elements
if (shouldSwap) {
const temp = frontFaces[j];
frontFaces[j] = frontFaces[j + 1];
frontFaces[j + 1] = temp;
}
}
}代码： 全选
/**
* Checks if two 3D line segments (p1->p2) and (q1->q2) intersect or touch.
*/
areEdgesIntersectingOrTouching(p1, p2, q1, q2) {
const d1x = p2.x - p1.x, d1y = p2.y - p1.y, d1z = p2.z - p1.z;
const d2x = q2.x - q1.x, d2y = q2.y - q1.y, d2z = q2.z - q1.z;
const rX = p1.x - q1.x, rY = p1.y - q1.y, rZ = p1.z - q1.z;
const a = d1x * d1x + d1y * d1y + d1z * d1z; // Squared length of segment 1
const e = d2x * d2x + d2y * d2y + d2z * d2z; // Squared length of segment 2
const f = d2x * rX + d2y * rY + d2z * rZ;
const b = d1x * d2x + d1y * d2y + d1z * d2z;
const c = d1x * rX + d1y * rY + d1z * rZ;
const denom = a * e - b * b;
let s = 0, t = 0;
// If lines are not parallel
if (Math.abs(denom) > 1e-6) {
s = (b * f - c * e) / denom;
t = (a f - b * c) / denom;
} else {
// Parallel lines case
s = 0;
t = e > 1e-6 ? f / e : 0;
}
// Clamp constraints to segment lengths
s = Math.max(0, Math.min(1, s));
t = Math.max(0, Math.min(1, t));
// Find the closest points on both segments
const closeP_x = p1.x + s * d1x, closeP_y = p1.y + s * d1y, closeP_z = p1.z + s * d1z;
const closeQ_x = q1.x + t * d2x, closeQ_y = q1.y + t * d2y, closeQ_z = q1.z + t * d2z;
// Calculate distance squared between the two closest points
const distSq = (closeP_x - closeQ_x) ** 2 + (closeP_y - closeQ_y) ** 2 + (closeP_z - closeQ_z) ** 2;
// Returns true if the segments intersect or touch (within threshold)
return distSq < 1e-4;
}