保利保利裁剪
Poly in poly clipping
从这里编写原始代码：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
我有一个程序，其中盒子的面递归地从原始盒子中取出并剪裁到最后的面尺寸。虽然，当玩家位于盒子的中心时，多边形裁剪功能 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>
我确定问题出在多边形剪裁中，任何不产生相同异常的新算法都将被排除在答案之外
精度错误，我四舍五入屏幕坐标来解决问题。