I've been trying to teach myself the Catmull-Clark algorithm:
http://en.wikipedia.org/wiki/Catmull-Clark_subdivision_surface
So far I'm just working in 2D getting faces to subdivide. The linked wiki page has steps for how to do the algorithm and the first one says to find the centroid of a face. I've never tried to do that, and I have a hunch my method (highlighted in red below) is not finding the centroid. Can anyone verify this and help if I am doing it wrong?
Note:
- I know I am not moving the original vertices of the faces in the code below (one of the steps of the wiki article says to do that). I'm not worried about that step yet.
- It took me a long time to figure out the subdividing recursion. The data structure I'm using is something I made up that works but may not be the best. I'd gladly take suggestions on improvement.
Code (centroid attempt in red):
- int faceVerts = 4;
- ArrayList<Face> faces = new ArrayList<Face>();
- ArrayList<Vert> verts = new ArrayList<Vert>();
- void setup() {
- size(800, 800);
- smooth();
- noFill();
- int[] vList = new int[faceVerts];
- for (int i = 0; i < faceVerts; i++) {
- float ang = TWO_PI/faceVerts*i;
- verts.add(new Vert(width/2+cos(ang)*350, height/2+sin(ang)*350, i));
- vList[i] = i;
- }
- faces.add(new Face(vList));
- }
- void draw() {
- background(255);
- for (int i = 0; i < faces.size(); i++) {
- Face iFace = faces.get(i);
- beginShape();
- for (int j = 0; j < iFace.num; j++) vertex(iFace.x[j], iFace.y[j]);
- endShape(CLOSE);
- }
- for (int i = 0; i < verts.size(); i++) {
- Vert iVert = verts.get(i);
- ellipse(iVert.x, iVert.y, 5, 5);
- }
- }
- class Face {
- int num;
- float[] x;
- float[] y;
- int[] id;
- Face(int[] inIDs) {
- num = inIDs.length;
- x = new float[num];
- y = new float[num];
- id = new int[num];
- for (int i = 0; i < num; i++) {
- Vert iVert = verts.get(inIDs[i]);
- x[i] = iVert.x;
- y[i] = iVert.y;
- id[i] = inIDs[i];
- }
- }
- }
- class Vert {
- float x, y;
- int id;
- Vert(float inX, float inY, int inID) {
- x = inX;
- y = inY;
- id = inID;
- }
- }
- void mousePressed() {
- for (int i = faces.size()-1; i > -1; i--) {
- Face iFace = faces.get(i);
- // Place vertex at center of face
- float newX = 0;
- float newY = 0;
- for (int j = 0; j < iFace.num; j++) {
- newX += iFace.x[j];
- newY += iFace.y[j];
- }
- verts.add(new Vert(newX/iFace.num, newY/iFace.num, verts.size()-1));
- // Place vertices at midpoint of each edge
- for (int j = 0; j < iFace.num-1; j++) verts.add(new Vert((iFace.x[j]+iFace.x[j+1])/2, (iFace.y[j]+iFace.y[j+1])/2, verts.size()-1));
- verts.add(new Vert((iFace.x[0]+iFace.x[iFace.num-1])/2, (iFace.y[0]+iFace.y[iFace.num-1])/2, verts.size()-1));
- // Add new faces and remove the original face
- int[] vList = {
- iFace.id[0], verts.size()-iFace.num, verts.size()-iFace.num-1, verts.size()-1
- };
- faces.add(new Face(vList));
- for (int j = 0; j < iFace.num-1; j++) {
- vList[0] = iFace.id[j+1];
- vList[1] = verts.size()-iFace.num+j+1;
- vList[2] = verts.size()-iFace.num-1;
- vList[3] = verts.size()-iFace.num+j;
- faces.add(new Face(vList));
- }
- faces.remove(i);
- }
- }
1
