多边形裁剪中的多边形

Question

从此处编写原始代码：https://www.khanacademy.org/cs/i/6630051796746240

我有一个程序，其中将盒子的面递归地从原始盒子中投射出来，并裁剪到最后的面孔尺寸。虽然，当播放器位于盒子的中央时，多边形裁剪功能inters不会产生正确的形状，而空白区域会水平出现故障。

代码]

var inters=function(p0, p1){
    var p2=[], i,j,k, n0=p0.length,n1=p1.length,n2, cx,cy, dx,dy, x0,y0, x1,y1, m,m0,m1;
    for(k=0; k < n1; k+=2){
        cx=p1[k]; cy=p1[k + 1];
        dy=p1[(k + 2)%n1] - cx;
        dx=cy - p1[(k + 3)%n1];
        p2=[]; n2=0;
        for(i=0; i<n0 + 2; i+=2){
            j=i*(i - n0 >>> 31);
            x0=x1; y0=y1; m0=m1;
            x1=p0[j]; y1=p0[j + 1];
            m1=(x1 - cx)*dx + (y1 - cy)*dy;
            if(!i){continue;}
            if(m0*m1 < 0){
                m=m0/(m0 - m1);
                p2[n2    ]=x0 + (x1 - x0)*m;
                p2[n2 + 1]=y0 + (y1 - y0)*m;
                n2+=2;
            }
            if(m1 >= 0){
                p2[n2]=x1; p2[n2 + 1]=y1;
                n2+=2;
            }
        }
        if(n2 < 6){return [];}
        p0=p2; n0=n2;
    }
    return p0;
};
我不确定为什么会这样，两个程序（我的和原始的）都会创建相同的视觉效果。

我的程序代码：

//This will work perfectly xD
//frameRate(0);
noiseSeed(0);
var keys = [];
var p = {
    x: 8.5,
    y: 8.5,
    z: 0.5,
    vx: 0,
    vy: 0,
    vz: 0,
    pit: 0,
    yaw: 0
};
p.setOrthogonal = function(){
    var sy=Math.sin(this.yaw), cy=Math.cos(this.yaw),
        sp=Math.sin(this.pit), cp=Math.cos(this.pit);
    this.v0x=sy*cp;
    this.v0y=cy*cp;
    this.v0z=-sp;
    this.v1x=cy;
    this.v1y=-sy;
    this.v1z=0;
    this.v2x=sy*sp;
    this.v2y=cy*sp;
    this.v2z=cp;
};
p.setOrthogonal();
//https://www.khanacademy.org/cs/-/4700070684278784
var clip=function(p0){
    var p1=[], i,j,k,n0=p0.length,n1, x0,y0,z0, x1,y1,z1, m,m0,m1;
    for(k=0; k < 4; k++){
        p1=[]; n1=0;
        for(i=0; i<n0 + 3; i+=3){
            j=i*(i - n0 >>> 31);
            x0=x1; y0=y1; z0=z1; m0=m1;
            x1=p0[j]; y1=p0[j + 1]; z1=p0[j + 2];
            m1=z1 - ((k & 2) - 1)*((k & 1)*x1 + (~k & 1)*y1);
            if(!i){continue;}
            if(m0*m1 < 0){
                m=m0/(m0 - m1);
                p1[n1    ]=x0 + (x1 - x0)*m;
                p1[n1 + 1]=y0 + (y1 - y0)*m;
                p1[n1 + 2]=z0 + (z1 - z0)*m;
                n1+=3;
            }
            if(m1 >= 0){
                p1[n1]=x1; p1[n1 + 1]=y1; p1[n1 + 2]=z1;
                n1+=3;
            }
        }
        if(n1 < 9){return [];}
        p0=p1; n0=n1;
    }
    return p0;
};
//https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
var inters=function(p0, p1){
    var p2=[], i,j,k, n0=p0.length,n1=p1.length,n2, cx,cy, dx,dy, x0,y0, x1,y1, m,m0,m1;
    for(k=0; k < n1; k+=2){
        cx=p1[k]; cy=p1[k + 1];
        dy=p1[(k + 2)%n1] - cx;
        dx=cy - p1[(k + 3)%n1];
        p2=[]; n2=0;
        for(i=0; i<n0 + 2; i+=2){
            j=i*(i - n0 >>> 31);
            x0=x1; y0=y1; m0=m1;
            x1=p0[j]; y1=p0[j + 1];
            //cx+dyt = x0 + (x1-x0)t
            //cy-dxt = y0 + (y1-y0)t
            //x| t = (x0-cx)/(dy-x1+x0)
            //y| t = (y0-cy)/(y0-y1-dx)
            //(x0-cx)/(dy-x1+x0) = (y0-cy)/(y0-y1-dx)
            //(y0-y1-dx)(x0-cx) = (dy-x1+x0)(y0-cy)
            //(y0-y1-dx)(x0-cx) - (dy-x1+x0)(y0-cy) = 0
            //(x0+(x1-x0)t-cx)*dx + (y0+(y1-y0)t-cy)*dy = 0
            
            m1=(x1 - cx)*dx + (y1 - cy)*dy;
            if(!i){continue;}
            if(m0*m1 < 0){
                m=m0/(m0 - m1);
                p2[n2    ]=x0 + (x1 - x0)*m;
                p2[n2 + 1]=y0 + (y1 - y0)*m;
                n2+=2;
            }
            if(m1 >= 0){
                p2[n2]=x1; p2[n2 + 1]=y1;
                n2+=2;
            }
        }
        if(n2 < 6){return [];}
        p0=p2; n0=n2;
    }
    return p0;
};
var World = (function(){
    //some stuff that is local to World
    var shift = 4;//binary shift
    var value = 1 << shift;//value of shift (16)
    var minus = value - 1;//can't think of cool name
    var depth = shift << 1;//z shift (32)
    var area = value*value*value;//area of chunck (4096)
    var noiseScale = 0.15;
    //create world object
    var World = function(){
        this.chunks = [];
        this.rd = [];
        this.boxFaces = [];
    };
    World.prototype.createChunk = function(ox, oy, oz){
        for(var y = 0; y < value; y ++){
            for(var x = 0; x < value; x ++){
                var cap = value*noise(x*noiseScale,y*noiseScale)|0;
                for(var z = 0; z < value; z ++){
                    this.chunks[z<<depth|y<<shift|x] = z>cap ? 1 : 0;
                }
            }
        }
    };
    World.prototype.recursiveFetching = function(cx, cy, cz, poly, step){
        if(step>10){return;}
        var dx,dy,dz,xp,yp,zp,x,y,z,i,j,j,k,m,nx,ny,nz,v;
        dx = cx - p.x;
        dy = cy - p.y;
        dz = cz - p.z;
        for(i = 0; i < 5; i ++){
            //cull backface
            if([dx, dy, dz][i >> 1]*(1 - (i*2 & 2)) + (~i & 1) < 0){continue;}
            
            //create face
            var poly3=[];
            for(j=0; j < 4; j++){
                k = i*4 + j;
                xp=dx+(0x96960f>>k&1);
                yp=dy+(0x330f69>>k&1);
                zp=dz+(0x0fcccc>>k&1);
                x=xp*p.v1x+yp*p.v1y+zp*p.v1z;
                y=xp*p.v2x+yp*p.v2y+zp*p.v2z;
                z=xp*p.v0x+yp*p.v0y+zp*p.v0z;
                poly3[j*3    ]=x;
                poly3[j*3 + 1]=y;
                poly3[j*3 + 2]=z;
            }
            
            //check if behind camera
            if((dx+0.5)*p.v0x + (dy+0.5)*p.v0y + (dz+0.5)*p.v0z < 2){
                poly3=clip(poly3);
                if(!poly3 || poly3.length < 9){continue;}
            }
            
            //convert to clip space
            var poly2 = [];
            for(j=k=0; j<poly3.length; j+=3, k+=2){
                m = 400/poly3[j + 2];
                poly2[k] = 200 + m*poly3[j];
                poly2[k + 1] = 200 + m*poly3[j + 1];
            }
            
            //constrain to poly
            poly2=inters(poly2, poly);
            if(!poly2 || poly2.length < 6){continue;}
            
            //area of polygon
            for(m=j=0, k=poly2.length; j < k; j+=2){
                m+=(poly2[j] + poly2[(j + 2)%k])*(poly2[(j + 3)%k] - poly2[j + 1]);
            }
            if(m <= 1e-4){continue;}
            
            //check value of border
            j = i << 1;
            nx = cx+(0x552>>j&3)-1;
            ny = cy+(0x525>>j&3)-1;
            nz = cz+(0x255>>j&3)-1;
            v = this.chunks[nz<<depth|ny<<shift|nx];
            if(((nx|ny|nz)>>shift)||v){
                if((nx|ny|nz)>>shift){
                    //this.rd.push([poly2.slice(),1,6]);
                }else{
                    this.rd.push([poly2.slice(),v,i]);
                }
                continue;
            }
            this.recursiveFetching(nx,ny,nz,poly2.slice(),step+1);
        }
    };
    World.prototype.raster = function(){
        this.rd = [];
        this.boxFaces = [];
        this.recursiveFetching(p.x|0,p.y|0,p.z|0,[0,0,400,0,400,400,0,400],0);
        for(var i = 0; i < this.rd.length; i ++){
            var data = this.rd[i];
            var poly = data[0];
            var ef = 255*data[2]/6;
            stroke(0,0,0);
            switch(data[1]){
                case 1:
                fill(ef, 0, 0);
                //stroke(ef,0,0);
                break;
                case 2:
                fill(0, 0, ef);
                //stroke(0,0,ef);
                break;
            }
            beginShape();
            for(var j = 0; j < poly.length; j +=2){
                vertex(poly[j],poly[j+1]);
            }
            endShape(CLOSE);
        }
    };
    World.prototype.getValue = function(x, y, z){
        return this.chunks[z<<depth|y<<shift|x];
    };
    //return world object
    return World;
})();
var world = new World();
world.createChunk();
draw = function() {
    background(0,150,255);
    world.raster();
    var newx = p.x, newy = p.y, newz = p.z;
    newz += p.vz;
    var spd = 0.1;
    if(keys[UP]||keys.w){
        newx += p.v0x*spd;
        newy += p.v0y*spd;
    }
    if(keys[DOWN]||keys.s){
        newx -= p.v0x*spd;
        newy -= p.v0y*spd;
    }
    if(keys[LEFT]||keys.a){
        newx -= p.v0y*spd;
        newy += p.v0x*spd;
    }
    if(keys[RIGHT]||keys.d){
        newx += p.v0y*spd;
        newy -= p.v0x*spd;
    }
    newx = constrain(newx, 0.1, 15.9);
	newy = constrain(newy, 0.1, 15.9);
	newz = constrain(newz, 0.1, 15.9);
    var nx = newx|0, ny = newy|0, nz = newz|0;
    var cx = p.x|0, cy = p.y|0, cz = p.z|0;
    if(world.getValue(cx,cy,nz+1)===0){
        p.z = newz;
        p.vz += 0.01;
        cz = nz;
    }else{
        if(keys[" "]){
            p.vz = -0.15;
        }
    }
    if(world.getValue(nx,cy,cz)===0&&world.getValue(nx,cy,cz+1)===0){
        p.x = newx;
        cx = nx;
    }
    if(world.getValue(cx,ny,cz)===0&&world.getValue(nx,ny,cz+1)===0){
        p.y = newy;
        cy = ny;
    }
    fill(255);
    noStroke();
    textSize(20);
    rect(0,0,40,25);
    fill(0,0,0);
    textAlign(LEFT,TOP);
    text(this.__frameRate|0,10,0);
};
keyPressed = function(){
    keys[keyCode] = keys[(key.toString()).toLowerCase()] = 1;
};
keyReleased = function(){
    keys[keyCode] = keys[(key.toString()).toLowerCase()]=0;
};
mouseDragged = function(){
    p.yaw += (mouseX - pmouseX) / 20;
	p.pit += (pmouseY - mouseY) / 20;
	p.setOrthogonal();
};
<script src="https://cdn.jsdelivr.net/processing.js/1.4.8/processing.min.js"></script> 

我确定问题在于多边形裁剪中的多边形，任何不会产生相同异常的新算法都将被排除为答案

从此处编写原始代码：https://www.khanacademy.org/cs/i/6630051796746240我有一个程序，其中将框的面递归地从原始框中剔除并剪切到最后的面...

Answer 1

精确错误，我将屏幕坐标四舍五入以解决问题。