중앙에서 선을 사용하여 원을 올바르게 채우는 알고리즘을 어떻게 작성할 수 있습니까?
현재 저는 Between Us와 같이 화면에서 볼 수있는 부분과 2D에서 빛을 차단하는 물체 때문에 볼 수없는 부분을 계산하는 코드를 작성하려고합니다.
코드는 사양이 매우 낮은 프로세서 (최소한 2020 년) 인 C64에서 실행되어야합니다. 이렇게 단순한 CPU에서는 게임에 대해 충분히 빠르게 복잡한 수학을 수행 할 수 없기 때문에 아이디어가 떠 올랐습니다. 우선 모든 것을 타일 기반으로 만들어 처리를 더 쉽게 만들고 전체를 변경할 수 있음을 의미합니다. 문자 또는 색상 셀. 그런 다음 처리중인 PC 용 코드 (Java와 비슷하지만 사용하기 더 쉬운 코딩 언어)를 작성하여 광선이 이동하는 방식을 계산합니다 (다음 그래픽은이를 더 이해하기 쉽게 만들 수 있음). 먼저 직사각형 (그리고 단일 사분면) :
그런 다음 기록 된 좌표를 사용하여 타일이 물체에 닿을 때까지 광선에 현재 그려지는 광선의 수에 따라 반전 된 문자로 타일을 계속 채우는 완전히 지저분한 어셈블러 코드를 작성했습니다 (채울 타일은 반전되지 않고 공간이 아닙니다) 다음 광선으로 이동하십시오. 반경을 7로 줄여 ASM에 유용한 256 바이트 만 차지합니다. 그리고 그것은 완전히 효과가 있었고 모든 버그를 수정할 수 있었고 그 결과는 상당히 인상적이었습니다. pause 문을 추가해야하거나 모든 것이 너무 빨리 실행되어 아무것도 볼 수 없었기 때문입니다.
그 후, 나는이 코드를 사용하여 포인트를 설정하면서 원으로 시도했습니다.
int pointNum = ceil(radius * PI * 2); // calculates the circumference
for(int i = 0;i < pointNum;i++){
float angle = map(i, 0, pointNum, 0, PI*2);
setPixel(sin(angle) * radius, cos(angle) * radius);
}
이전에 Bresenham 서클 알고리즘을 사용했지만 제대로 작동하지 않아 더 간단한 방법을 시도했습니다. 그래서 ...
표시된 검은 색 타일은 모두 빛에 맞지 않는데, 이는 게임에서 그 타일을 볼 수 없다는 것이별로 의미가 없기 때문에 매우 큰 문제입니다. Processing 에서 작성한 코드 는 다음과 같습니다.
float[] xPoints = new float[0];
float[] yPoints = new float[0];
float[] xPointsT;
float[] yPointsT;
float[] xPointsHad = new float[0];
float[] yPointsHad = new float[0];
int pos = 0;
float interpolPos = 0;
int radius = 12;
float tileSize = 800.0 / (2*radius+1);
String output = " !byte ";
int pointNum = ceil(radius * PI * 2);
void setup() {
size(800, 800);
frameRate(60);
xPointsT = new float[0];
yPointsT = new float[0];
/*for(int i = 0;i <= radius;i++){
setPixel(radius, i);
setPixel(i, radius);
}*/ //Uncomment this and comment the next 4 lines to get the rectangle version
for(int i = 0;i < pointNum;i++){
float angle = map(i, 0, pointNum, 0, PI*2);
setPixel(sin(angle) * radius, cos(angle) * radius);
}
xPoints = concat(xPoints, xPointsT);
yPoints = concat(yPoints, yPointsT);
}
void draw(){
if(interpolPos > radius){
pos++;
interpolPos = 0;
println(output);
output = " !byte ";
}
float x=0, y=0;
float interpolMul = interpolPos / radius;
x = xPoints[pos] * interpolMul;
y = yPoints[pos] * interpolMul;
interpolPos+=1;//sorta the resolution
background(0);
stroke(255);
for(int i = 0;i < 2*radius+1;i++){
for(int j = 0;j < 2*radius+1;j++){
if((round(x) + radius) == i && (round(y) + radius) == j){
fill(0, 255, 0);
if(output != " !byte ")
output += ", ";
output += i-radius;
output += ", ";
output += j-radius;
xPointsHad = append(xPointsHad, i);
yPointsHad = append(yPointsHad, j);
}
else{
int fillVal = 0;
for(int k = 0; k < xPoints.length;k++){
if(round(xPoints[k])+radius == i && round(yPoints[k])+radius == j){
fillVal += 64;
}
}
fill(0, 0, fillVal);
if(fillVal == 0){
for(int k = 0; k < xPointsHad.length;k++){
if(round(xPointsHad[k]) == i && round(yPointsHad[k]) == j){
fill(128, 0, 0);
}
}
}
}
rect(i * tileSize, j * tileSize, tileSize, tileSize);
}
}
strokeWeight(3);
stroke(0, 255, 255, 64);
for(int i = 0;i < xPoints.length;i++){
line((float(radius)+0.5) * tileSize, (float(radius)+0.5) * tileSize, (float(radius)+0.5+xPoints[i]) * tileSize, (float(radius)+0.5+yPoints[i]) * tileSize);
}
strokeWeight(1);
fill(255, 255, 0);
ellipse((x + radius + 0.5) * tileSize, (y + radius + 0.5) * tileSize, 10, 10);
}
void setPixel(float _x, float _y){
for(int i = 0; i < xPoints.length;i++){
if(_x == xPoints[i] && _y == yPoints[i]){
return;
}
}
for(int i = 0; i < xPointsT.length;i++){
if(_x == xPointsT[i] && _y == yPointsT[i]){
return;
}
}
xPointsT = append(xPointsT, _x);
yPointsT = append(yPointsT, _y);
}
(사각형을 얻는 방법은 코드에 있습니다.) 위에 언급 된 타일은 광선이 그 위로 점프하기 때문에 절대 맞지 않는 것 같습니다.하지만이를 방지하려면 어떻게해야합니까? interpolPos + = x를 줄일 수 있습니다. 더 많은 타일을 치는 방법은 단계가 더 작기 때문입니다. 그러나 그것은 상당한 공간을 낭비하기 때문에 좋은 해결책이라고 생각하지 않습니다. 이상적으로는 더 작은 시야를 얻기 위해 그리는 좌표의 수를 줄일 수도 있습니다. 누구든지 그렇게하는 방법을 알고 있습니까?
답변
터치 된 모든 셀을 찾기 위해 잘못된 방법을 선택했습니다. 점 기반 방식 대신 셀 (사각형) 기반 접근 방식이 필요합니다. 광선은 점이 아닌 직사각형을 교차합니다.
Amanatides와 Woo의 2D 용 "레이 트레이싱을위한 빠른 복셀 탐색 알고리즘" 기사가 있습니다 .
실용적인 구현 .
예:
빠른 추적 예제. 왼쪽 상단 모서리에서 방출되는 광선은 파란색 점으로 이동합니다. 광선이 흑색 세포 장애물을 만나면 멈 춥니 다. 분홍색 세포는 광선으로 비추고 회색 세포는 그렇지 않습니다.
좋아요, 제 상황에서 저에게 도움이되는 것을 찾았습니다. 완전히 작동하는 부분 (사각형)을 사용한 다음 광원에서 더 멀리 떨어진 모든 타일 히트를 무시하고 반경 + 0.5를 무시하여 원을 만듭니다. + .5가 없으면 원이 이상해 보입니다. 직접 시도해 볼 수 있습니다. 코드는 다음과 같습니다.
float[] xPoints = new float[0];
float[] yPoints = new float[0];
float[] xPointsT;
float[] yPointsT;
float[] xPointsHad = new float[0];
float[] yPointsHad = new float[0];
int pos = 0;
float interpolPos = 0;
int radius = 7;
float tileSize = 800.0 / (2*radius+1);
int pointNum = ceil(radius * PI * 2);
String standardOutput = " !align 15,0\n !byte ";
void setup() {
size(800, 800);
frameRate(60);
xPointsT = new float[0];
yPointsT = new float[0];
for(int i = 0;i <= radius;i++){
setPixel(radius, i);
setPixel(i, radius);
} //Uncomment this and comment the next 4 lines to get the rectangle version
/*for(int i = 0;i < pointNum;i++){
float angle = map(i, 0, pointNum, 0, PI*2);
setPixel(sin(angle) * radius, cos(angle) * radius);
}*/
xPoints = concat(xPoints, xPointsT);
yPoints = concat(yPoints, yPointsT);
xPointsT = new float[0];
yPointsT = new float[0];
}
void draw(){
if(interpolPos > radius){
pos++;
interpolPos = 0;
String output = standardOutput;
for(int i = 0;i < radius + 1;i++){
int indexPos = floor(map(i, 0, radius + 1, 0, xPointsT.length));
output += round(xPointsT[indexPos]);
output += ",";
output += round(yPointsT[indexPos]);
if(i < radius){
output += ", ";
}
}
println(output);
xPointsT = new float[0];
yPointsT = new float[0];
}
float x=0, y=0;
float interpolMul = interpolPos / radius;
x = xPoints[pos] * interpolMul;
y = yPoints[pos] * interpolMul;
interpolPos+=1;//sorta the resolution
background(0);
stroke(255);
for(int i = 0;i < 2*radius+1;i++){
for(int j = 0;j < 2*radius+1;j++){
if((round(x) + radius) == i && (round(y) + radius) == j && sqrt(sq(round(x)) + sq(round(y))) < radius + 0.5){
fill(0, 255, 0);
xPointsT = append(xPointsT, i-radius);
yPointsT = append(yPointsT, j-radius);
xPointsHad = append(xPointsHad, i);
yPointsHad = append(yPointsHad, j);
}
else{
int fillVal = 0;
for(int k = 0; k < xPoints.length;k++){
if(round(xPoints[k])+radius == i && round(yPoints[k])+radius == j){
fillVal += 64;
}
}
fill(0, 0, fillVal);
if(fillVal == 0){
for(int k = 0; k < xPointsHad.length;k++){
if(round(xPointsHad[k]) == i && round(yPointsHad[k]) == j){
fill(128, 0, 0);
}
}
}
}
rect(i * tileSize, j * tileSize, tileSize, tileSize);
}
}
strokeWeight(3);
stroke(0, 255, 255, 64);
for(int i = 0;i < xPoints.length;i++){
line((float(radius)+0.5) * tileSize, (float(radius)+0.5) * tileSize, (float(radius)+0.5+xPoints[i]) * tileSize, (float(radius)+0.5+yPoints[i]) * tileSize);
}
strokeWeight(1);
fill(255, 255, 0);
ellipse((x + radius + 0.5) * tileSize, (y + radius + 0.5) * tileSize, 10, 10);
}
void setPixel(float _x, float _y){
for(int i = 0; i < xPoints.length;i++){
if(_x == xPoints[i] && _y == yPoints[i]){
return;
}
}
for(int i = 0; i < xPointsT.length;i++){
if(_x == xPointsT[i] && _y == yPointsT[i]){
return;
}
}
xPointsT = append(xPointsT, _x);
yPointsT = append(yPointsT, _y);
}
원 안에 있지 않은 타일을 무시하는 주요 차이점 외에도 좌표를 문자열이 아닌 두 개의 배열에 저장하도록 변경했습니다. 왜냐하면 반경 + 1 포인트보다 적을 때 코드를 사용하여 늘이기 때문입니다. C64의 RAM에 크기가 다른 여러 개의 원을 저장할 필요가 없으므로 주요 요구 사항을 충족합니다. 모든 타일을 채우고 광선 끝의 일부 지점을 무시하여 축소 할 수 있어야합니다. 그리고 효율적이라면? 어 ... 더 적은 수의 광선으로 원을 채우는 더 나은 솔루션이있을 수 있지만, 저는 그다지 신경 쓰지 않습니다. 그래도 아이디어가 있다면 말해 주면 좋겠지 만 그렇지 않으면이 질문이 해결됩니다.
편집 : 사진을 추가하는 것을 잊었습니다. 혼동하지 마세요. 게시 한 후 코드를 수정하여 원의 파란색 타일도 볼 수 있습니다.
