基于Painter Algorithm的Canvas游戏多边形渲染排序逻辑矛盾问题求助

各位大佬好！我正在开发一个基于Canvas的游戏，用Painter算法处理3D风格多边形的渲染排序，但目前遇到了一个棘手的逻辑矛盾问题，折腾了好久都没解决，想请教下大家的思路！

一、场景对象说明 #

游戏世界里所有可渲染对象都是带高度的多边形，每个多边形的结构定义如下，顶点是相对于自身position的偏移坐标：

{
   position: {
      x: null,
      y: null,
      z: null
   },
   hitbox: {
      vertices: [
         [x,y],[x,y],[x,y]
      ],
      height: null,
      search_distance: null, // maximum possible distance across a polygon
   },
   max_vertice_y: null, // furthest top vertice y position
   min_vertice_y: null // lowest bottom vertice y position
}

这里有两个重要的坐标系和处理前提：

• 我已经实现了一个多边形拆分算法，确保任意两个多边形不会同时处于对方的前后方，也就是说任意两个多边形要么完全在前面，要么完全在后面
• 坐标系和常规不同：y值越小越靠近屏幕底部，y值越大越靠近屏幕顶部

二、核心问题描述 #

我试过各种排序方案，包括最近写的这个版本，但都存在同一个致命问题：
比如多边形A完全在B的下方（按照Painter算法应该先渲染A，再渲染B），但后续处理到多边形C时，因为C的z位置、高度和A的y位置组合，导致C被排在B的前面、A的后面——这就打乱了原本A和B的正确渲染顺序。

我没法找到一个能稳定保持多边形间前后关系的排序方法，每次调整判断逻辑，都会影响后续多边形的排序结果。目前我在研究拓扑排序，但卡壳在如何定义依赖关系上：感觉每个多边形都有一个“应该在它之前渲染”和“应该在它之后渲染”的列表，但后面出现的新多边形会打乱之前的关系。我也试过变种归并排序，但同样因为上述场景，判断条件直接失效了。

下面是这个矛盾场景的示意图：

三、我最近尝试的排序代码 #

这是我最近写的排序实现，包含排序逻辑、射线检测、相交判断等辅助函数：

function sortTerrain() {
    // terrain_ground and terrain_decor are objects with the properties mentioned above
    
    // create working "grab from list"
    let comp_work = [...terrain_ground, ...terrain_decor];
    
    // create sorted list
    let working = [comp_work.shift()];
    
    // while grab list isnt empty, take from and insert into sorted list
    while (comp_work.length > 0) {
        let current = comp_work.shift();
        
        // get index of insert position
        let insert = -1;
        
        // start from the furthest forward printed object in the sorted list and work backwards until a truth is found
        // **this was originally working from the start to end under the condition of when a truth is not found, exit and use last saved index ... this WORKS but, not as well as looking for a single truth. both still create the issue mentioned above
        for (let i=working.length-1; i>=0; i--) {
            let compare = working[i];
            
            if (sameZPlane(current, compare)) {
                // on same z plane, sort by y
                
                // if guaranteed infront of
                if (current.max_vertice_y < compare.min_vertice_y) {
                    insert = i;
                    break;
                }
                
                // if overlap on y
                if (current.min_vertice_y < compare.max_vertice_y && current.max_vertice_y > compare.min_vertice_y) {
                    
                    // check for ray cast to determine current is in front of compare
                    // also check rear-forward using rayCastInfrontOf(x, x, true) in case rear is smaller than the gap between a vertice pair of the front polygon
                    if (rayCastInfrontOf(current, compare) || rayCastInfrontOf(compare, current, true)) {
                        insert = i;
                        break;
                    } else if (current.min_vertice_y < compare.min_vertice_y) {
                        // if not, then check if current min is in front of compare min
                        insert = i;
                        break;
                    }
                    
                }
                
            } else {
                
                // sort by z index
                if (current.position.z > compare.position.z) {
                    insert = i;
                    break;
                } else if (current.position.z == compare.position.z) {
                    // shared z position yet failing sameZPlane is a 0 height terrain, sort by height 
                    // THIS IS UNLIKELY TO CONTRIBUTE TO ANY PRINT ERRORS
                    if (current.hitbox.height > compare.hitbox.height) {
                        insert = i;
                        break;
                    }
                }
                
            }

        }
        
        // no insert location found, add at start of the stack
        if (insert == -1) {
            working.unshift(current);
        } else {
            // insert after last found index
            working.splice(insert+1, 0, current);
        }

    }
}

function expandTerrainVertices() {
    // can of worms
}

function rayCastInfrontOf(front, rear, reverse = false) {
    // allow reverse check by sending truth boolean to reverse param
    // safe ray length
    let ray = (front.hitbox.search_distance + rear.hitbox.search_distance) * (reverse ? -1 : 1);
    
    // shrink vertices of "front" so that rays casted will not give false positive to polygons sharing a vertice point + position value
    let shrink_front_vertices = expandTerrainVertices(front, -1);
    
    // run ray from all vertice points of front backwards (or rear forwards if reverse param is true) and see if it intersects any vertice connections in rear
    // "middle" is used to get next safe vertice pair
    let middle = 0;
    for (let i=0; i<shrink_front_vertices.length; i++) {
        middle = i+1;
        if (middle == shrink_front_vertices.length) {
            middle = 0;
        }
        
        // cast from middle point of vertices rather than from the vertice position itself, this is safer
        let middle_point = {
            x: (front.position.x + shrink_front_vertices[i][0] + front.position.x + shrink_front_vertices[middle][0])/2,
            y: (front.position.y + shrink_front_vertices[i][1] + front.position.y + shrink_front_vertices[middle][1])/2
        }
        
        // loop rear vertice pairs
        let next = 0;
        for (let i2=0; i2<rear.hitbox.vertices.length; i2++) {
            next = i2+1;
            if (next == rear.hitbox.vertices.length) {
                next = 0;
            }
            
            // check if ray cast from the middle position of the "front" polygon intercepts any vertice pairs on "rear" polygon
            if (intercepts(
                middle_point.x, middle_point.y,
                middle_point.x, middle_point.y + ray,
                rear.position.x + rear.hitbox.vertices[i2][0], rear.position.y + rear.hitbox.vertices[i2][1],
                rear.position.x + rear.hitbox.vertices[next][0], rear.position.y + rear.hitbox.vertices[next][1]
            )) {
                return true;
            }
        }
    }
    
    return false;
}

// get intersection point of two lines
function intercepts(x1,y1,x2,y2,x3,y3,x4,y4) {
    let s1_x = x2 - x1
    let s1_y = y2 - y1
    let s2_x = x4 - x3
    let s2_y = y4 - y3
    let s = (-s1_y * (x1 - x3) + s1_x * (y1 - y3)) / (-s2_x * s1_y + s1_x * s2_y);
    let t = ( s2_x * (y1 - y3) - s2_y * (x1 - x3)) / (-s2_x * s1_y + s1_x * s2_y);
    if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
        return [precise(x1 + (t * s1_x)), precise(y1 + (t * s1_y))]
    }
    return false
}

function sameZPlane(a, b) {
    let a_top = precise(a.position.z + a.hitbox.height);
    let b_top = precise(b.position.z + b.hitbox.height);
    if (
        (a_top > b.position.z && a.position.z < b_top) ||
        (b_top > a.position.z && b.position.z < a_top)
    ) {
        return true;
    }
    return false;
}

备注：内容来源于stack exchange，提问作者Not a discord mod