Before you read on. Blogger is simply crap for posting code. I've done my best for formatting but if you see dodgy symbols or things that make no sense - blame blogger as this code is right out of the compiler.
Modellers seems to like quads. Catmull Clark subdivision smooths and maintains a quads only model. Doo-sabin introduces triangles. Loop works on triangles. So I decided to use Catmull clark in qoob. I got it working last night after spending a whole weekend when I should have been in the sun. The model above, I estimate, would be around 22 bytes to store compressed. Its approaching organic but is still embarressingly geometrical. Thats has to be the next goal, to produce some organic stuff.
Most code on the net works using winged edge data structures. Classes abound. The examples are no use for size coders. Fortunately iq tackled CCSD in his 2007 presentation for breakpoint, Tricks and techniques for RGBAs Past and Future Intros.
(By the way his normal a mesh trick in that presentation is without doubt the best piece of size coding I've seen.)
Firstly wikipedia has a description of the algorithm. Unfortunately, its not totally clear what an edge point is -the midpoint of an edge or the new displaced midpoint of the edge (its the first). But there are other references to clear this up. IQ proved its possible to do Catmull clark without winged edges but still he uses edge ids. I wanted to avoid this and did so but in doing so, each time I add a vertex I loop through all vertices to see if an identical one already exists. I think its a case of what I gain on the flat I lose on the hill. Here is the final code in old style C (ie no C++ operators for maths) which makes it look horrendous - thats why operators were introduced :-).
addVert is key. It checks all existing vertices for an exact duplicate (exact is fine in this case) and returns either the index to the existing one or adds the new vertex and returns its index. addquad adds a quad to the model. The last line deletes old quadsr. The routine supports subdivision without displacement and CCSD, hence the if(smooth) in places.
Vert disp[MAXSIZE]; // displacements
uint val[MAXSIZE]; // valences
void subdObj (Object *ob, uint smooth) {
Vert tmp,ep,fp;
uint eid[4],cni; //indices for new vertices, edges and centre
uint onq = ob->nq;
uint onv = ob->nv;
ZeroMemory(disp,MAXSIZE*sizeof(Vert));
ZeroMemory(val,MAXSIZE*sizeof(uint));
for (uint iq=0; iq < onq; iq++ ) {
centroid (ob, iq, &fp);
cni=addVert(ob,&fp);
for (uint v=0; v<4; v++ ) { // for each vertex in each quad quad
lerp(&(QV(ob,iq,v)), &(QV(ob,iq,(v 1)&3)), 0.5f, &ep);
copy(&ep,&tmp);
if (smooth) smul(&tmp,0.5f);
eid[v]=addVert(ob,&tmp); // orignal vertices of edge/4.0
// add contrib of face points to displacement for new edge points
smadd (&fp,0.25f, &(disp[eid[v]]), &(disp[eid[v]]) ); // add fp/4 to edge vector
// add face points to displacement for original point
add (&fp, &(disp[ob->q[iq][v]]),&(disp[ob->q[iq][v]]) );
// add 2x edge points to disp for original points
smadd (&ep, 2.0f, &(disp[ob->q[iq][v]]),&(disp[ob->q[iq][v]]) );
val[ob->q[iq][v]] ; // add up valences
}
// now construct four new quads
for (uint k=0;k<4;k++ ) addQuad (ob, ob->q[iq][k], eid[k], cni, eid[(k-1)&3], selected(iq));
}
// now displace all vertices...face points will be unaffected
if (smooth) for (uint v=0; v <q->nv; v++ ) {
if (v < onv) { // this must be an original point
smul (&(disp[v]), 1.0f/val[v]); // average the displacement values
smadd (&(ob->v[v]), val[v]-3.0f, &(disp[v]), &(ob->v[v]) ); // correct for extraordinary vertex
smul (&(ob->v[v]), 1.0f/val[v]); // divide through by valence
} else add (&(ob->v[v]), &(disp[v]), &(ob->v[v]));
}
for (uint iq=0; iq<onq; iq++ ) delQuad(ob,0);
}
Well depending how you count lines of code its 20-25. addVert and addQuad make it 25-30. So lets call it 30 lines of code Catmull Clark in C. C++ operators would make this a bit shorter. IQ claims 50 lines of code but if counted in the same way, his code is about the same 30-35.
The way the code works is a two pass algorithm first over quads of the original model and secondly over the vertices of the new model. The first pass subdivides and accumulates displacement in a seperate vector. This enables the first pass to calculate all the valences and store them before averaging the final displacement and applying it in the correct manner depending on the type of point (original, edge or face). There are a couple of gotchas but thats the basic idea. No winged edge, infact no edges at all.
Coding style sucks. Happy with result so thought I'd publish it.
One cool thing is the model pictures is about 22 bytes to store. A champfered cube is about 12 bytes and a sphere similar. It means we are looking at qoob providing a library of demo type objects in a few hundred bytes. The spheres are made of quads and do not suffer from peaks at top and bottom. Ther qoob library is a few kilo unfortunately. DX would help but I think I'll target 64k so not to worry.
