메타볼 만들기 2부

세부 목차

msquare_3

지난 포스팅에 이어서, 이번에도 계속해서 메타볼을 만들어보겠다. 모든 픽셀을 샘플링하는 방식은 코드는 단순하지만, 원의 갯수가 늘어날수록, 화면 해상도가 커질수록 실행 속도가 급격하게 느려지는 것을 관찰할 수 있었다. 이번에는 자유로운 표현도에서는 조금 떨어질지 모르지만, 속도 면에서 훨씬 이득인 마칭 스퀘어 방식으로 메타볼을 만들어보자.

마칭 스퀘어 Marching Squares

이전 포스팅에서도 밝혔다시피, jamie-wong.com에 나와있는 설명을 바탕으로 공부한 내용을 정리해본다. 마칭 스퀘어는 모든 픽셀을 샘플링하는 대신에, 정사각형의 셀(cell)을 화면에 배열하고, 4개의 코너에서만 거리를 계산(샘플링)한다. 그리고 원이 얼마만큼 셀 안에 걸쳐있느냐에 따라서 미리 지정된 16가지 패턴 중에서 하나를 부여받는다. 원이 걸쳐있는 정도는 정사각형의 셀의 네 코너에서 원의 중심까지의 거리를 계산해서 알 수 있다. 물론, 픽셀을 일일히 계산하는 방식보다는 부정확하지만, 네 코너에서만 샘플링을 하기 때문에 훨씬 빠르다.

Corner 클래스

먼저, 각 코너의 데이터를 담을 수 있는 Corner 클래스를 만든다. 이 글을 작성하는 시점에서 드는 생각은, 굳이 코너 클래스를 만들 필요없이 Cell 안에 모든 데이터를 담을 수 있었을 것 같다. 오히려, 코드가 더 직관적이 될 수 있을 듯. 하지만, 클래스를 만드는 것은 나의 심리적인 부담감을 덜어주므로, 굳이 Corner 클래스를 만들어보겠다.

class Corner {
  float x;
  float y;
  float totalScore;

  Corner(float _x, float _y) {
    x = _x;
    y = _y;
    totalScore = 0;
  }
}

totalScore 변수에는 각 원과의 거리를 계산해서 나온 값 또는 점수를 저장할 것이다.

핵심 함수 만들기

코너가 원 내부에 위치하는지 판별하는 함수를 만들자. 원의 방정식 \( (x-a)^2 + (y-b)^2 = r^2 \) 을 사용하면, 원의 윤곽선을 따라 형성되는 점들을 알 수 있다. 이 때, \( (a, b) \) 는 원의 중심 좌표다. \( (x-a)^2 + (y-b)^2 <= r^2 \) 의 경우에는 원의 내부에 위치하는 모든 점의 좌표를 말한다.

boolean isInsideCircle(float _cx, float _cy, float _radius) {
    float sqDist = sq(x - _cx) + sq(y - _cy);
    float sqRadius = sq(_radius);
    return sq_dist <= sqRadius;
}

하지만, 이렇게 할 경우, 코너가 원의 내부에 있는지만 측정이 가능할 뿐, 메타볼의 형태를 만들기 위해 필요한 값을 누적할 수 없다는 사실을 발견했다. 따라서 boolean을 반환하는 대신에, 거리와 원의 크기에 따른 float 점수값을 반환하도록 다시 함수를 만든다. 그 과정을 살펴보면,

$$ (x-a)^2 + (y-b)^2 <= r^2 $$

각 변을 \( (x-a)^2 + (y-b)^2 \) 으로 나눠준다.

$$ 1 <= {r^2 \over (x-a)^2 + (y-b)^2} $$

좌우 순서를 바꿔주면,

$$ {r^2 \over (x-a)^2 + (y-b)^2} >= 1 $$

이제 좌변이 1과 같거나 큰 경우에는, 그 좌표가 원 안에 위치함을 알 수 있다. 단순한 boolean이 아니기 때문에, 1보다 값이 크거나 작은 경우도 누적을 해서 메타볼의 형태를 만드는데 영향을 미칠 수 있다.

float getScoreFromCircle(float _cx, float _cy, float _radius) {
  float sqDist = sq(x - _cx) + sq(y - _cy);
  if (sq_dist == 0) sq_dists = 0.01; // arbitrary value to avoid dividing by 0
  float sqRadius = sq(_radius);
  float score = sqRadius / sqDist;
  return score;
}

getScoreFromCircle()이라는 함수 이름은 보완의 여지가 있는 것 같다. 어쨌든... if (sq_dist == 0) sq_dists = 0.01; 구문은 분모가 0이 되는 상황을 방지하기 위해 넣었다. 이 부분도 좀 더 깔끔하게 해결할 방법이 있을 듯 하다.

Cell 클래스 만들기

Corner 클래스는 일단 마무리하고, 이를 활용하는 Cell 클래스를 만들어보자. Corner 오브젝트를 4개 만들고, 각각에 위치를 부여한다. 셀이 제 장소에 위치하는지 보기 위해서 display() 함수를 만들어준다.

class Cell {
  float x, y;
  int cellSize;
  Corner[] corners;

  Cell(float _x, float _y, int _cs) {
    x = _x;
    y = _y;
    cellSize = _cs;
    corners = new Corner[4];
    setupCorners();
  }

  void setupCorners() {
    corners[0] = new Corner(x, y);
    corners[1] = new Corner(x+cellSize, y);
    corners[2] = new Corner(x+cellSize, y+cellSize);
    corners[3] = new Corner(x, y+cellSize);
  }

  void display() {
    noFill();
    stroke(120);
    rectMode(CORNER);
    rect(x, y, cellSize, cellSize);
  }
}

Cell의 생성

메인 스케치로 돌아가서 Cell 오브젝트들을 만들어준다.

Cell[] cells;
int cellSize = 30;

void setup() {
  size(600, 200);

  int numX = ceil( width / (float) cellSize );
  int numY = ceil( height / (float) cellSize );
  cells = new Cell[ numX * numY ];
  for (int x = 0; x < numX; x++) {
    for (int y = 0; y < numY; y++) {
      int index = y * numX + x;
      cells[index] = new Cell(x*cellSize, y*cellSize, cellSize);
    }
  }
}

void draw() {
  background(0);

  for (int i = 0; i < cells.length; i++) {
    cells[i].display();
  }
}

int numX = ceil( width / (float) cellSize ); 이 구문은 화면의 너비가 cellSize로 딱 나누어떨어지지 않을 경우에도 셀을 채워넣기 위한 과정이다.

Mover 클래스

메타볼의 재료가 될 Mover 클래스 또한 생성하고 movers라는 ArrayList를 스케치에 추가해준다. 현재의 Mover 클래스는 가장 기본적인 바운싱 볼이며, 이후에 behavior를 추가해서 좀 더 그럴듯하게 만들어줄 수 있다.

class Mover {
  PVector loc;
  PVector vel;
  PVector acc;
  float moverRadius;

  Mover(float _x, float _y, float _r) {
    loc = new PVector(_x, _y);
    vel = PVector.random2D();
    //acc = new PVector();
    vel.mult(random(.5, 1));
    moverRadius = _r;
  }

  void run() {
    checkEdges();
    update();
    display();
  }

  void checkEdges() {
    if (loc.x < 0 || loc.x > width) vel.x *= -1;
    if (loc.y < 0 || loc.y > height) vel.y *= -1;
  }

  void update() {
    //vel.add(acc);
    loc.add(vel);
    //acc.mult(0); // reset
  }

  void display() {
    pushStyle();
    noFill();
    stroke(255, 0, 0);
    strokeWeight(2);
    ellipse(loc.x, loc.y, moverRadius*2, moverRadius*2);
    popStyle();
  }
}

셀 테스트

현재까지의 코드를 실행하면 아래와 같이 보인다.

Your browser does not support canvas.

코너의 값 계산

이제 각 코너에서 모든 원들까지의 거리에 대한 값을 계산한다. 애초에는 이 함수를 Cell 클래스에 넣어줬으나, 작성하는 시점에서 Corner 클래스로 옮겨주었다. 각각의 코너가 이를 처리하는 것이 낫다고 판단했기 때문이다. 하지만, 메인 스케치에서 만들어진 Mover 객체들이 Cell을 거쳐서 Corner까지 전달이 되는 것이 아직 완전히 만족스럽지는 않다.

// Corner methods

void setTotalScore() {
  float sum = 0.0;
  for (int i = 0; i < movers.size(); i++) {
    Mover m = movers.get(i);
    sum += getScoreFromCircle(m.loc.x, m.loc.y, m.moverRadius);
  }
  totalScore = sum;
}

float getTotalScore() {
  return totalScore;
}

이제 이 함수들을 셀이 활용할 수 있다.

// Cell methods

int getConfig() {
  int[] states = new int[corners.length]; 
  for (int i = 0; i < states.length; i++) {
    corners[i].setTotalScore();
    if (corners[i].getTotalScore() >= 1) states[i] = 1;
  }
  String bin = str(states[0]) + str(states[1]) + str(states[2]) + str(states[3]); 
  return unbinary(bin);
}

void update() {
  config = getConfig();
}

위의 코드에는 나오지 않았지만, Cell 클래스에 전역변수 int config 또한 추가해준다. 이 변수가 현재의 셀이 어떤 방식으로 화면에 표시해야하는지 그 조합의 종류를 담고 있다.

String bin = str(states[0]) + str(states[1]) + str(states[2]) + str(states[3]); 
return unbinary(bin);

위의 구문은 2진수로 받은 코너의 현 상태를 10진수로 변환하는 과정이다. 그렇게 하면 이후에 어떤 조합을 보여줘야할지 switch 구문에서 활용하기 편하다.

16가지 조합 만들기

셀의 일부분을 원이 걸치고 있을 경우의 수를 따져보면 16가지가 나온다. 2가지 상태(닿았거나 닿지 않았거나)를 가진 4개의 코너, 즉, 2의 4승은 16. 이를 그림으로 표현해보면 다음과 같다.

Marchingsquaresisoline
"Marching-squares-isoline". Licensed under CC BY 3.0 via Wikipedia.

16가지 조합에 대응하도록 display() 함수를 수정한다.

// Cell method

void display() {
  noFill();
  stroke(120);
  strokeWeight(1);
  rectMode(CORNER);
  rect(x, y, cellSize, cellSize);

  stroke(255);
  switch(config) {
  case 0:
    break;
  case 1:
    line(x, y+cellSize/2, x+cellSize/2, y+cellSize);
    break;
  case 2:
    line(x+cellSize/2, y+cellSize, x+cellSize, y+cellSize/2);
    break;
  case 3:
    line(x, y+cellSize/2, x+cellSize, y+cellSize/2);
    break;
  case 4:
    line(x+cellSize/2, y, x+cellSize, y+cellSize/2);
    break;
  case 5:
    line(x, y+cellSize/2, x+cellSize/2, y+cellSize);
    line(x+cellSize/2, y, x+cellSize, y+cellSize/2);
    break;
  case 6:
    line(x+cellSize/2, y, x+cellSize/2, y+cellSize);
    break;
  case 7:
    line(x, y+cellSize/2, x+cellSize/2, y);
    break;
  case 8:
    line(x, y+cellSize/2, x+cellSize/2, y);
    break;
  case 9:
    line(x+cellSize/2, y, x+cellSize/2, y+cellSize);
    break;
  case 10:
    line(x, y+cellSize/2, x+cellSize/2, y);
    line(x+cellSize/2, y+cellSize, x+cellSize, y+cellSize/2);
    break;
  case 11:
    line(x+cellSize/2, y, x+cellSize, y+cellSize/2);
    break;
  case 12:
    line(x, y+cellSize/2, x+cellSize, y+cellSize/2);
    break;
  case 13:
    line(x+cellSize/2, y+cellSize, x+cellSize, y+cellSize/2);
    break;
  case 14:
    line(x, y+cellSize/2, x+cellSize/2, y+cellSize);
    break;
  case 15:
    break;
  }
}

조합 테스트

이렇게 해서 마칭 스퀘어가 작동하는 모습을 볼 수 있다.

Your browser does not support canvas.

선형보간

현재로서는, 셀과 셀 사이를 건너뛸 때, 어떤 부드러운 전환도 없기 때문에 뚝뚝 끊겨보인다. 셀의 크기를 줄여줄 수는 있지만, 그렇게 하면 마칭 스퀘어를 사용하는 의미가 사라진다.

마칭 스퀘어를 활용하면서도 조금 더 부드러운 형태를 연출하기 위해서 선형보간(linear interpolation)을 해준다. 16가지 조합을 살펴보면, 결국에는 4개의 모서리 중 두 곳을 교차하는 직선의 위치에 따라 조합들이 생성됨을 알 수 있다. 그리고 우리는 각 코너의 원과의 거리에 따른 점수값도 알고 있다. 따라서, 어느 한 모서리의 시작점과 끝점을 놓고 그 직선(모서리) 상에 원이 교차하는 지점을 (거의) 찾을 수 있다. 그리고 매 프레임마다 그 값을 업데이트해주면, 훨씬 부드러운 움직임을 만들어낼 수 있다. 구체적인 수식은 이곳에서 확인하자...

링크의 수식을 우리의 코드에 대입해보자. 먼저, 오른쪽 모서리 위를 교차하는 어느 점 (x, y)의 좌표를 구하는 수식은 다음과 같이 표현된다.

x = corners[1].x;
y = corners[1].y + 
  (corners[2].y - corners[1].y) * 
  ( (1-corners[1].getTotalScore())/(corners[2].getTotalScore()-corners[1].getTotalScore()) );

결국, 한 모서리의 시작점과 끝점의 좌표를 알면 (위의 경우에는 cornsers[1]corners[2]) 그 위를 움직이는 점의 좌표를 구할 수 있다. 이를 함수로 표현해본다.

// Cell method

PVector interpolate(Corner one, Corner two) {
  float x, y = 0;
  float delta = two.getTotalScore() - one.getTotalScore();
  if (one.x == two.x) {
    x = one.x;
    if (delta == 0) y = abs(two.y - one.y) * 0.5;
    else y = one.y + (two.y-one.y) * (1-one.getTotalScore()) / delta;
  } else {
    y = one.y;
    if (delta == 0) x = abs(two.x - one.x) * 0.5;
    else x = one.x + (two.x-one.x) * (1-one.getTotalScore()) / delta;
  }
  PVector result = new PVector(x, y);
  return result;
}

PVector를 사용한 것은 xy의 좌표를 한데 묶어서 처리하기 위한 방법이다. if (one.x == two.x) 구문은 모서리의 두 끝점의 x좌표가 같다면, 즉, 세로 모서리인 경우는 y 값만 보간해주기 위한 것이다. 반대의 상황도 마찬가지이다. if (delta == 0) 구문은 delta0인 경우, 분모를 0으로 놓을 수 없기 때문에 추가한 부분이다. 이 부분도 좀 더 깔끔하게 처리할 수 있는 방법이 있을 것 같다.

이제 이 함수를 display() 함수에 적용한다.

// Cell method

void display() {
  noFill();
  stroke(120);
  strokeWeight(1);
  rectMode(CORNER);
  rect(x, y, cellSize, cellSize);

  // top, right, bottom, left
  PVector t = interpolate(corners[0], corners[1]);
  PVector r = interpolate(corners[1], corners[2]);
  PVector b = interpolate(corners[2], corners[3]);
  PVector l = interpolate(corners[3], corners[0]);

  stroke(255);
  switch(config) {
  case 0:
    break;
  case 1:
    line(l.x, l.y, b.x, b.y);
    break;
  case 2:
    line(b.x, b.y, r.x, r.y);
    break;
  case 3:
    line(l.x, l.y, r.x, r.y);
    break;
  case 4:
    line(t.x, t.y, r.x, r.y);
    break;
  case 5:
    line(l.x, l.y, b.x, b.y);
    line(t.x, t.y, r.x, r.y);
    break;
  case 6:
    line(t.x, t.y, b.x, b.y);
    break;
  case 7:
    line(l.x, l.y, t.x, t.y);
    break;
  case 8:
    line(l.x, l.y, t.x, t.y);
    break;
  case 9:
    line(t.x, t.y, b.x, b.y);
    break;
  case 10:
    line(l.x, l.y, t.x, t.y);
    line(b.x, b.y, r.x, r.y);
    break;
  case 11:
    line(t.x, t.y, r.x, r.y);
    break;
  case 12:
    line(l.x, l.y, r.x, r.y);
    break;
  case 13:
    line(b.x, b.y, r.x, r.y);
    break;
  case 14:
    line(l.x, l.y, b.x, b.y);
    break;
  case 15:
    break;
  }
}

마무리

이렇게 해서 끈적끈적한 메타볼이 완성되었다. 마칭스퀘어의 각 셀들은 서로에 대해서 전혀 모르고 있으며, 단순한 직선으로 표현된다. 이렇게 셀들이 단순한 규칙을 가지고 한데 모였을 때 유기적이고 부드러운 형태를 만들어낸다는 사실이 재미있다. 아래의 예제는 cellSize10으로 놓았고, float extraBlobby 변수를 추가하여, 너무 큰 덩어리가 생기지 않도록 했다. 전체 소스코드는 아래에 첨부한다.

Your browser does not support canvas.

소스코드

Cell[] cells;
int cellSize = 10;
float extraBlobby = -0.02;

int numMovers = 20;
ArrayList<Mover> movers = new ArrayList<Mover>();

void setup() {
  size(600, 200);

  int numX = ceil( width / (float) cellSize );
  int numY = ceil( height / (float) cellSize );
  cells = new Cell[ numX * numY ];
  for (int x = 0; x < numX; x++) {
    for (int y = 0; y < numY; y++) {
      int index = y * numX + x;
      cells[index] = new Cell(x*cellSize, y*cellSize, cellSize);
    }
  }

  for (int i = 0; i < numMovers; i++) {
    movers.add( new Mover(random(width), random(height), random(20, 40)) );
  }
}

void draw() {
  background(0);

  for (int i = 0; i < cells.length; i++) {
    cells[i].update();
    cells[i].display();
  }

  for (int i = 0; i < movers.size(); i++) {
    Mover m = movers.get(i);
    m.run();
  }
}

class Cell {
  float x, y;
  int cellSize;
  Corner[] corners;

  int config;

  Cell(float _x, float _y, int _cs) {
    x = _x;
    y = _y;
    cellSize = _cs;
    corners = new Corner[4];
    setupCorners();
  }

  void setupCorners() {
    corners[0] = new Corner(x, y);
    corners[1] = new Corner(x+cellSize, y);
    corners[2] = new Corner(x+cellSize, y+cellSize);
    corners[3] = new Corner(x, y+cellSize);
  }

  int getConfig() {
    int[] states = new int[corners.length]; 
    for (int i = 0; i < states.length; i++) {
      corners[i].setTotalScore();
      if (corners[i].getTotalScore() >= 1) states[i] = 1;
    }
    String bin = str(states[0]) + str(states[1]) + str(states[2]) + str(states[3]); 
    return unbinary(bin);
  }

  PVector interpolate(Corner one, Corner two) {
    float x, y = 0;
    float delta = two.getTotalScore() - one.getTotalScore();
    if (one.x == two.x) {
      x = one.x;
      if (delta == 0) y = abs(two.y - one.y) * 0.5;
      else y = one.y + (two.y-one.y) * (1-one.getTotalScore()) / delta;
    } else {
      y = one.y;
      if (delta == 0) x = abs(two.x - one.x) * 0.5;
      else x = one.x + (two.x-one.x) * (1-one.getTotalScore()) / delta;
    }
    PVector result = new PVector(x, y);
    return result;
  }

  void update() {
    config = getConfig();
  }

  void display() {
    /*
    noFill();
    stroke(120);
    strokeWeight(1);
    rectMode(CORNER);
    rect(x, y, cellSize, cellSize);
    */

    // top, right, bottom, left
    PVector t = interpolate(corners[0], corners[1]);
    PVector r = interpolate(corners[1], corners[2]);
    PVector b = interpolate(corners[2], corners[3]);
    PVector l = interpolate(corners[3], corners[0]);

    stroke(255);
    switch(config) {
    case 0:
      break;
    case 1:
      line(l.x, l.y, b.x, b.y);
      break;
    case 2:
      line(b.x, b.y, r.x, r.y);
      break;
    case 3:
      line(l.x, l.y, r.x, r.y);
      break;
    case 4:
      line(t.x, t.y, r.x, r.y);
      break;
    case 5:
      line(l.x, l.y, b.x, b.y);
      line(t.x, t.y, r.x, r.y);
      break;
    case 6:
      line(t.x, t.y, b.x, b.y);
      break;
    case 7:
      line(l.x, l.y, t.x, t.y);
      break;
    case 8:
      line(l.x, l.y, t.x, t.y);
      break;
    case 9:
      line(t.x, t.y, b.x, b.y);
      break;
    case 10:
      line(l.x, l.y, t.x, t.y);
      line(b.x, b.y, r.x, r.y);
      break;
    case 11:
      line(t.x, t.y, r.x, r.y);
      break;
    case 12:
      line(l.x, l.y, r.x, r.y);
      break;
    case 13:
      line(b.x, b.y, r.x, r.y);
      break;
    case 14:
      line(l.x, l.y, b.x, b.y);
      break;
    case 15:
      break;
    }
  }
}

class Corner {
  float x;
  float y;
  float totalScore;

  Corner(float _x, float _y) {
    x = _x;
    y = _y;
    totalScore = 0;
  }

  boolean isInsideCircle(float _cx, float _cy, float _radius) {
    float sqDist = sq(x - _cx) + sq(y - _cy);
    float sqRadius = sq(_radius);
    return sqDist <= sqRadius;
  }

  float getScoreFromCircle(float _cx, float _cy, float _radius) {
    float sqDist = sq(x - _cx) + sq(y - _cy);
    if (sqDist == 0) sqDist = 0.01; // arbitrary value to avoid dividing by 0
    float sqRadius = sq(_radius);
    float score = extraBlobby + (sqRadius / sqDist);
    return score;
  }

  void setTotalScore() {
    float sum = 0.0;
    for (int i = 0; i < movers.size(); i++) {
      Mover m = movers.get(i);
      sum += getScoreFromCircle(m.loc.x, m.loc.y, m.moverRadius);
    }
    totalScore = sum;
  }

  float getTotalScore() {
    return totalScore;
  }
}

class Mover {
  PVector loc;
  PVector vel;
  PVector acc;
  float moverRadius;

  Mover(float _x, float _y, float _r) {
    loc = new PVector(_x, _y);
    vel = PVector.random2D();
    //acc = new PVector();
    vel.mult(random(.5, 1));
    moverRadius = _r;
  }

  void run() {
    checkEdges();
    update();
    //display();
  }

  void checkEdges() {
    if (loc.x < 0 || loc.x > width) vel.x *= -1;
    if (loc.y < 0 || loc.y > height) vel.y *= -1;
  }

  void update() {
    //vel.add(acc);
    loc.add(vel);
    //acc.mult(0); // reset
  }

  void display() {
    pushStyle();
    noFill();
    stroke(255, 0, 0);
    strokeWeight(2);
    ellipse(loc.x, loc.y, moverRadius*2, moverRadius*2);
    popStyle();
  }
}

탐구 가능성