old crufty ear clipping

gistfile1.txt

bool ccwN( sgVec2 dir1, sgVec2 dir2 ) {
	return (dir1[0]*dir2[1] - dir2[0]*dir1[1]) > 0;
}

bool ccw( sgVec2 dir1, sgVec2 dir2 ) {
	sgNormalizeVec2( dir1 );
	sgNormalizeVec2( dir2 );
	return ccwN(dir1,dir2);
}

bool ccw( sgVec2 a, sgVec2 b, sgVec2 c ) {
	sgVec2 d1, d2;
	sgSubVec2( d1, b, a );
	sgSubVec2( d2, c, b );
	return ccw( d1, d2 );
}

... ear clipping ...

		// first, do we need to reverse the order of the polygon?
		// check the signed area
		float area;
		area = 0.0;
		for (j=npnts-1,i=0; i < npnts; j = i++) {			
			area += (pnts[j][0]-pnts[i][0])*(pnts[j][2] + pnts[i][2])* 0.5;
		}		
				

		// tesselate it
		assert( npnts < 1000 );
		int used[1000];
		int pntsleft = npnts;
		for (i=0; i < npnts; i++) {
			pnts[i][1] = h;
			used[i] = 0;
		}

		int a, b, c;
		if (area < 0.0) {
			a=2; b = 1; c = 0;
		} else {
			a=0; b = 1; c = 2;
		}
		sgVec2 A, B, C;
		int iter = 1000; // should always converge, this is for bugs

		int good = 0;
		while( pntsleft > 2 ) {
			sgSetVec2( A, pnts[a][0], pnts[a][2] );
			sgSetVec2( B, pnts[b][0], pnts[b][2] );
			sgSetVec2( C, pnts[c][0], pnts[c][2] );


			good = 1;
			if (!ccw(A,B,C)) {
				good = 0;
			} else {
				// make sure no verts are inside
				sgVec2 pp;
				bool ca, cb, cc;
				for (i = 0; i < npnts; i++) {
					if ((i==a)||(i==b)||(i==c)||(used[i])) continue;

					sgSetVec2( pp, pnts[i][0], pnts[i][2] );
					ca = ccw( A, B, pp );
					cb = ccw( B, C, pp );
					cc = ccw( C, A, pp );								

					if ((ca==cb) && (cb==cc)) {
						good = 0;
						break;
					} 
				}
			}

			if (good) {
				// remove "ear"
				tri = new TessTri();
				sgCopyVec3( tri->a, pnts[a] );
				sgCopyVec3( tri->b, pnts[b] );
				sgCopyVec3( tri->c, pnts[c] );
				tess.push_back( tri );
				
				used[b] = 1;
				pntsleft--;
				if (pntsleft<=2) break;

				iter = 1000;

				b = c;
				do {
					if (area < 0.0) {
						c--;
						if (c<0) c=npnts-1;
					} else {
						c++;
						if (c==npnts) c=0;					
					}
				} while (used[c]);

			} else {
				
				//assert(iter);
				if (iter==0) {
					printf("Cannot dice polygon\n");
					break; // give up
				}

				iter--;

				// advance around the polygon
				a = b;
				b = c;
				do {
					if (area < 0.0) {
						c--;
						if (c<0) c=npnts-1;
					} else {
						c++;
						if (c==npnts) c=0;					
					}
				} while (used[c]);
			}
		}