2D subdiv

subdivision surface再分割曲面といえば、Cat-mull Clark

その２次元版

極限はB-Spline曲線

CatmullClarkSubdiv2D.pde

PVector[] pts0, pts1, pts2, pts3;

void setup() {
  size(600, 600);
  pixelDensity(1);

  // 入力：閉ループ
  pts0 = new PVector[] {
    new PVector(-1, -1),
    new PVector( 1, -1),
    new PVector( 3, -1),
    new PVector( 3,  1),
    new PVector( 3,  3),
    new PVector( 1,  3),
    new PVector( 1,  1),
    new PVector(-1,  1),
    new PVector(-1,  3),
    new PVector(-3,  3),
    new PVector(-3,  1),
    new PVector(-3, -1),
    new PVector(-5, -1),
    new PVector(-5, -3),
    new PVector(-3, -3),
    new PVector(-1, -3),
  };
  for (PVector p : pts0) p.mult(50);
  
  pts1 = ccBoundarySubdiv(pts0);//println(pts1);
  pts2 = ccBoundarySubdiv(pts1);
  pts3 = ccBoundarySubdiv(pts2);

  noLoop();
}

void draw() {
  background(255);
  translate(width/2, height/2);

  noFill();
  stroke(0);
  drawPoly(pts3);
  stroke(128);
  drawPoly(pts0);
}

void drawPoly(PVector[] pts) {
  beginShape();
  for (PVector p : pts) vertex(p.x, p.y);
  endShape(CLOSE);
}

// ---- Catmull–Clark Subdivision ----
PVector[] ccBoundarySubdiv(PVector[] pts) {
  int n = pts.length;
  PVector[] out = new PVector[n * 2];

  for (int i = 0; i < n; i++) {
    PVector prev = pts[(i - 1 + n) % n];
    PVector curr = pts[i];
    PVector next = pts[(i + 1) % n];

    // V' = (prev + 6*curr + next) / 8
    PVector vPrime = new PVector();
    vPrime.add(prev);
    vPrime.add(PVector.mult(curr, 6));
    vPrime.add(next);
    vPrime.mult(1.0f / 8.0f);

    // E = (curr + next) / 2
    PVector edgeMid = PVector.add(curr, next);
    edgeMid.mult(0.5f);

    out[2 * i]     = vPrime;
    out[2 * i + 1] = edgeMid;
  }
  return out;
}

CatmullClarkSubdiv2D_ex

// --- modeling polygon (base control polygon) ---
ArrayList<PVector> poly = new ArrayList<PVector>();
ArrayList<ArrayList<PVector>> undoStack = new ArrayList<ArrayList<PVector>>();

// --- selection ---
int hoverEdge = -1;
float pickTol = 12; // px

void setup() {
  size(800, 800, P2D);
  pixelDensity(1);
  resetPoly();
}

void draw() {
  background(255);
  translate(width/2, height/2);

  // hover edge detect (in local coords)
  hoverEdge = findNearestEdge(poly, mouseX - width/2, mouseY - height/2, pickTol);

  // subdiv 3 times for display
  PVector[] pts0 = poly.toArray(new PVector[0]);
  PVector[] pts1 = ccBoundarySubdiv(pts0);
  PVector[] pts2 = ccBoundarySubdiv(pts1);
  PVector[] pts3 = ccBoundarySubdiv(pts2);

  // draw smooth (subdiv) curve
  noFill();
  stroke(0);
  strokeWeight(2);
  drawPoly(pts3);

  // draw base polygon
  stroke(160);
  strokeWeight(2);
  drawPoly(pts0);

  // draw hover edge highlight
  if (hoverEdge != -1) {
    int i = hoverEdge;
    int j = (i + 1) % poly.size();
    PVector a = poly.get(i), b = poly.get(j);
    stroke(255, 0, 0);
    strokeWeight(5);
    line(a.x, a.y, b.x, b.y);
  }

  // UI text
  resetMatrix();
  fill(0);
  text("Click an edge to extrude outward by its length.  r: reset  z: undo", 14, 22);
}

// --- mouse / key controls ---
void mousePressed() {
  float mx = mouseX - width/2;
  float my = mouseY - height/2;
  int ei = findNearestEdge(poly, mx, my, pickTol);
  if (ei == -1) return;

  pushUndo();

  extrudeEdge(poly, ei);

}

void keyPressed() {
  if (key == 'r') resetPoly();
  if (key == 'z') undo();
}

// --- initialize ---
void resetPoly() {
  poly.clear();
  undoStack.clear();

  float s = 50;
  poly.add(new PVector(-s, -s));
  poly.add(new PVector( s, -s));
  poly.add(new PVector( s,  s));
  poly.add(new PVector(-s,  s));
}

// --- undo helpers ---
void pushUndo() {
  ArrayList<PVector> snap = new ArrayList<PVector>();
  for (PVector p : poly) snap.add(p.copy());
  undoStack.add(snap);
  if (undoStack.size() > 50) undoStack.remove(0);
}
void undo() {
  if (undoStack.size() == 0) return;
  poly = undoStack.remove(undoStack.size() - 1);
}

// =========================================================
//  Edge extrusion (2D polygon)
//  Replace edge (vi -> vj) by: vi, vi+off, vj+off, vj
//  off direction = outward normal * edgeLength
// =========================================================
void extrudeEdge(ArrayList<PVector> P, int i) {
  int n = P.size();
  int j = (i + 1) % n;

  PVector vi = P.get(i);
  PVector vj = P.get(j);

  PVector d = PVector.sub(vj, vi);
  float L = d.mag();
  if (L < 1e-6) return;

  // polygon orientation (CCW -> signed area > 0)
  float area = signedArea(P);
  boolean ccw = area > 0;

  // outward normal:
  // edge direction d = (dx,dy)
  // right normal = (dy, -dx), left normal = (-dy, dx)
  PVector nrm = ccw ? new PVector(d.y, -d.x) : new PVector(-d.y, d.x);
  nrm.normalize();

  // offset amount = edge length
  PVector off = PVector.mult(nrm, L);

  PVector vi2 = PVector.add(vi, off);
  PVector vj2 = PVector.add(vj, off);

  // insert between i and j:
  // P: ... vi, [vi2, vj2], vj ...
  // Note: j is i+1 mod n. In ArrayList insertion, handle wrap
  if (j == 0) {
    // edge is last->first, append before first => easiest: add at end
    P.add(vi2);
    P.add(vj2);
  } else {
    P.add(j, vj2);
    P.add(j, vi2);
  }
}

// =========================================================
//  Edge picking: nearest segment to mouse
// =========================================================
int findNearestEdge(ArrayList<PVector> P, float mx, float my, float tol) {
  int n = P.size();
  if (n < 2) return -1;

  float bestD = tol;
  int bestI = -1;

  PVector m = new PVector(mx, my);
  for (int i = 0; i < n; i++) {
    PVector a = P.get(i);
    PVector b = P.get((i + 1) % n);
    float d = distPointToSegment(m, a, b);
    if (d < bestD) {
      bestD = d;
      bestI = i;
    }
  }
  return bestI;
}

float distPointToSegment(PVector p, PVector a, PVector b) {
  PVector ab = PVector.sub(b, a);
  float ab2 = ab.magSq();
  if (ab2 < 1e-9) return PVector.dist(p, a);

  float t = PVector.sub(p, a).dot(ab) / ab2;
  t = constrain(t, 0, 1);
  PVector q = PVector.add(a, PVector.mult(ab, t));
  return PVector.dist(p, q);
}

float signedArea(ArrayList<PVector> P) {
  double s = 0;
  int n = P.size();
  for (int i = 0; i < n; i++) {
    PVector a = P.get(i);
    PVector b = P.get((i + 1) % n);
    s += (double)a.x * (double)b.y - (double)b.x * (double)a.y;
  }
  return (float)(0.5 * s);
}

// =========================================================
//  Drawing + boundary Catmull–Clark subdivision
// =========================================================
void drawPoly(PVector[] pts) {
  beginShape();
  for (PVector p : pts) vertex(p.x, p.y);
  endShape(CLOSE);
}

// boundary CC: out = [V0', E01, V1', E12, ...]
PVector[] ccBoundarySubdiv(PVector[] pts) {
  int n = pts.length;
  PVector[] out = new PVector[n * 2];

  for (int i = 0; i < n; i++) {
    PVector prev = pts[(i - 1 + n) % n];
    PVector curr = pts[i];
    PVector next = pts[(i + 1) % n];

    // V' = (prev + 6*curr + next) / 8
    PVector vPrime = new PVector();
    vPrime.add(prev);
    vPrime.add(PVector.mult(curr, 6));
    vPrime.add(next);
    vPrime.mult(1.0f / 8.0f);

    // E = (curr + next) / 2
    PVector edgeMid = PVector.add(curr, next);
    edgeMid.mult(0.5f);

    out[2 * i]     = vPrime;
    out[2 * i + 1] = edgeMid;
  }
  return out;
}