Catmull Clark Subdivision / Claudio Esperança

Claudio Esperança

Computer Graphics & Visualization @ufrj.br

Workspace

Published

Edited

Dec 1, 2020

2 forks

5 stars

Paper implementations

Physical animation with shape matching 3D Apollonian Sphere Packings Random space-filling curves Simple Adaptive Mosaic Effects Hexagonal hierarchical cartogram for Brazil Platonic Solids Playground Dynadraw Vertex Lists Least Square Meshes Mocap Projection Browser Archimedean tilings Voronoi mosaics Shape matching 2D GJK and EPA algorithms Omohundro balltree construction algorithms

Catmull Clark Subdivision

Thinning

Also listed in…

Computer Graphics

mutable autorot = true

carp = loadMesh(await FileAttachment("carp_fish.obj").text())

// The object being shown at the moment

mutable obj = carp

function loadMesh (objfile) {

let model = parseObj(objfile);

let vtxIndex = new Map();

let cells = model.faces;

let positions = centralize(model.pos,3);

return {cells,positions}

}

view = mat4.lookAt([],[0,0,5],[0,0,0],[0,1,0])

projection = mat4.perspective ([], 40 * Math.PI/180, 1, 0.01, 100)

model = mat4.identity([])

draw = {

computeFaceNormals(obj);

computeEdges(obj);

let triMesh = triangleMesh(obj);

let drawFaces = makeTriMeshDraw(triMesh);

let drawEdges = makeMeshEdgeDraw(obj);

for (let frame = 0; ;frame++) {

regl.clear({

color: [0.8, 0.8, 1.0, 1],

depth: 1

})

if (mutable autorot) {

mat4.rotateY(model,model,Math.PI/180*0.5);

mat4.rotateX(model,model,Math.PI/180*0.2);

}

let conf = {modelview:mat4.mul([],view,model),

projection:projection};

drawFaces(conf);

drawEdges(conf)

yield frame;

}

// @returns the subdivision of an input mesh

// @param positions - array of points, each a 3-coordinate array

// @param faces - array of face circulations, each an array with n indices of positions

// @param catmull - if true, perform catmull-clarks subdivision, otherwise, regular (flat) subdivision

subdivide = function (positions,faces, catmull = true) {

let ds = HalfedgeDS.fromFaces(faces);

// Function to sum an array of points

let sum = pts => pts.reduce((p,q) => [p[0]+q[0],p[1]+q[1],p[2]+q[2]]);

// Function to average an array of points

let avg = pts => {

return sum(pts).map (x => x / pts.length);

}

// Multiplies all elements of v by s

let scale = (v,s) => v.map(x => x * s);

// Build face midpoints

let facePoints = ds.face.map(

(he,iface) => avg ([...ds.faceCirculator(iface)].map(he => positions[he.v]))

);

// Function to map an edge (a halfedge and its twin) to the edge midpoint

let edgeToMidpoint = (he,twin) => avg([positions[he.v],positions[twin.v]]);

// Function to map an edge to its catmull-clark new position, which takes

// into account the neighboring center points of neighbor points

let edgeToSubdivisionPoint =

(he,twin) => avg([positions[he.v],positions[twin.v],facePoints[he.f],facePoints[twin.f]]);

// Compute all edge points

let edgePoints = [];

let edgeMidPoints = []

ds.halfedge.forEach (

he => {

let twin = ds.halfedge[he.twin]

if (he.v < twin.v) { // Process each edge only once

he.iEdgePoint = twin.iEdgePoint = edgePoints.length;

let midpoint = edgeToMidpoint(he,twin)

edgeMidPoints.push (midpoint)

if (catmull) edgePoints.push (edgeToSubdivisionPoint(he,twin));

else edgePoints.push(midpoint)

}

});

// Compute the new position of vertex v in a Catmull-Clark subdivision

let newPosition = ivertex => {

let incidentHalfedges = [...ds.vertexCirculator(ivertex)];

let incidentFacePoints = incidentHalfedges.map(he=>facePoints[he.f]);

let incidentEdgePoints = incidentHalfedges.map(he=>edgeMidPoints[he.iEdgePoint]);

if (ivertex==0) console.log (incidentHalfedges, incidentFacePoints, incidentEdgePoints)

let n = incidentHalfedges.length;

return sum ([scale(positions[ivertex], (n-3)/n),

scale(avg(incidentFacePoints), 1/n),

scale(avg(incidentEdgePoints), 2/n)])

}

// Array with the new positions of the original vertices

let newPositions = (catmull ? positions.map((d,i) => newPosition(i)) : positions);

// Compute the new face circulations

let n = positions.length;

let m = edgePoints.length;

newPositions = newPositions.concat(edgePoints).concat(facePoints);

let newFaces = [];

ds.face.forEach((he,i) => {

let edgeIndices = []

for (let he of ds.faceCirculator(i)) edgeIndices.push(he.iEdgePoint+n, he.v,);

let ne = edgeIndices.length;

for (let k = 0; k < edgeIndices.length; k+= 2) {

newFaces.push([i+n+m,edgeIndices[k],edgeIndices[(k+1)%ne],edgeIndices[(k+2)%ne]]);

}

})

return {positions:newPositions, cells:newFaces}

}

import {tabbed,paged,combo} from "@esperanc/aggregated-inputs"

import {select,checkbox,button} from "@jashkenas/inputs"

createRegl = require('regl@1.4.2/dist/regl.js')

regl = createRegl(canvas)

One platform to build and deploy the best data apps

Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.

Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.

Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.

Learn more