/** ** tesselate_polyhedron - tesselate a polyhedron ** ** CREATED: 2023.05.15 ABS copied from col_ed ** MODIFIED: 2023.05.16 ABS gutted; added structs ** MODIFIED: 2023.05.17 ABS hacked ** MODIFIED: 2023.05.18 ABS hacked; got working manually ** MODIFIED: 2023.05.19 ABS hacked; got working semi-automatically to frequency 3 ** MODIFIED: 2023.05.20 ABS got working semi-automatically to frequency 5; got file read working ** MODIFIED: 2023.05.21 ABS tweaked ** MODIFIED: 2023.05.22 ABS tweaked ** MODIFIED: 2023.05.28 ABS got fully automated ** MODIFIED: 2023.07.05 ABS renamed triangulate -> tesselate_polyhedron ** **/ /*************************** polyh file format example --------------------------- facet 12 0.000000 1.000000 0.000000 0.894427 0.447214 0.000000 0.276393 0.447214 0.850651 -0.723607 0.447214 0.525731 -0.723607 0.447214 -0.525731 0.276393 0.447214 -0.850651 0.723607 -0.447214 0.525731 -0.276393 -0.447214 0.850651 -0.894427 -0.447214 0.000000 -0.276393 -0.447214 -0.850651 0.723607 -0.447214 -0.525731 0.000000 -1.000000 0.000000 3 1 3 2 3 1 4 3 3 1 5 4 3 1 6 5 3 1 2 6 3 2 3 7 3 3 4 8 3 4 5 9 3 5 6 10 3 6 2 11 3 8 7 3 3 9 8 4 3 10 9 5 3 11 10 6 3 7 11 2 3 12 7 8 3 12 8 9 3 12 9 10 3 12 10 11 3 12 11 7 ***************************/ #include "tesselate_polyhedron.h" /* * defaultParms() - initialize global variables */ void defaultParms() { Debug = FALSE; Colors = FALSE; Puff = FALSE; Frequency = 2; strcpy(PolyFile, "icos.polyhc"); } /* end defaultParms() */ /* * parseArgs() - parse arguments into global variables */ void parseArgs(argc, argv) int argc; char** argv; { int i, c; int help(); int usage(); for (i = 0; i < argc; i++) { if (argv[i][0] == '-') { switch (argv[i][1]) { case 'D' : Debug = TRUE; break; case 'C' : Colors = TRUE; break; case 'f' : Frequency = atoi(&argv[++i][0]); break; case 'P' : Puff = TRUE; break; case 'p' : strcpy(PolyFile, &argv[++i][0]); break; case 'h' : Junk = help(argv); exit(0); break; case 'u' : Junk = usage(argv); exit(0); break; default: fprintf(stderr, "%s: ERROR: illegal flag: %s\n", ProgName, argv[i]); usage(argv); exit(0); break; } /* end switch */ } /* end if */ } /* end for i */ } /* end parseArgs() */ /* * createPolygon() - create a polygon structure */ int createPolygon(p_array, vert_a, vert_b, vert_c) struct Polygon p_array[MAX_POLYS]; int vert_a; int vert_b; int vert_c; { int result; /* new polygon */ p_array[NumPolys].polygon_number = NumPolys; p_array[NumPolys].vertex_list[0] = vert_a; p_array[NumPolys].vertex_list[1] = vert_b; p_array[NumPolys].vertex_list[2] = vert_c; NumPolys++; return(NumPolys - 1); } /* end createPolygon() */ /* * interp() - interpolate (weighed average) between two verices */ int interp(x0, y0, z0, x1, y1, z1, p_x_out, p_y_out, p_z_out, num, den) double x0, y0, z0; double x1, y1, z1; double* p_x_out; double* p_y_out; double* p_z_out; int num, den; { double xd, yd, zd, fraction; xd = x1 - x0; yd = y1 - y0; zd = z1 - z0; fraction = (double)num/(double)den; *p_x_out = x0 + xd*fraction; *p_y_out = y0 + yd*fraction; *p_z_out = z0 + zd*fraction; return(0); } /* end interp() */ /* * puff() - "puff out" coordinates to be one unit from origin */ int puff(x, y, z, p_x_out, p_y_out, p_z_out) double x, y, z; double* p_x_out; double* p_y_out; double* p_z_out; { double r; r = sqrt(x*x + y*y + z*z); if (r == 0.0) { *p_x_out = x; *p_y_out = y; *p_z_out = z; return(0); } *p_x_out = x/r; *p_y_out = y/r; *p_z_out = z/r; return(0); } /* end puff() */ /* * attemptToCreateVertex() - attempt to create a vertex structure */ int attemptToCreateVertex(v_array, e_flag, min_v, max_v, nu, de, x, y, z, p_created_flag) struct Vertex v_array[MAX_VERTS]; int e_flag; int min_v; int max_v; int nu; int de; double x; double y; double z; int* p_created_flag; { int result; int findVertex(); if (min_v < 0 || max_v < 0) { fprintf(stderr, "%s: ERROR: attemptToCreateVertex() called with negative vertex number\n", ProgName); exit(0); } if (min_v > max_v) { int temp; #ifdef SUPER_DEBUG if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: swapped = %d and %d\n", ProgName, min_v, max_v); fprintf(stderr, "%s: DEBUG: old nu = %d\n", ProgName, nu); fflush(stderr); } #endif temp = min_v; min_v = max_v; max_v = temp; nu = de - nu; #ifdef SUPER_DEBUG if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: nu = %d\n", ProgName, nu); fprintf(stderr, "%s: DEBUG: de = %d\n", ProgName, de); fflush(stderr); } #endif } if (e_flag) { /* elder vertex */ *p_created_flag = TRUE; v_array[min_v].min_vertex = min_v; v_array[min_v].max_vertex = max_v; v_array[min_v].numerator = nu; v_array[min_v].denominator = de; v_array[min_v].coordinates[X] = x; v_array[min_v].coordinates[Y] = y; v_array[min_v].coordinates[Z] = z; v_array[min_v].elder_flag = TRUE; NumVerts++; return(min_v); } /* possibly new vertex */ result = findVertex(v_array, min_v, max_v, nu, de, MAX_VERTS); if (result != NOT_FOUND) { /* return vertex number */ *p_created_flag = FALSE; return(result); } /* really create vertex */ v_array[NumVerts].min_vertex = min_v; v_array[NumVerts].max_vertex = max_v; v_array[NumVerts].numerator = nu; v_array[NumVerts].denominator = de; v_array[NumVerts].coordinates[X] = x; v_array[NumVerts].coordinates[Y] = y; v_array[NumVerts].coordinates[Z] = z; v_array[NumVerts].elder_flag = FALSE; *p_created_flag = TRUE; NumVerts++; return(NumVerts - 1); } /* end attemptToCreateVertex() */ /* * findVertex() - find a vertex structure */ int findVertex(v_array, min_v, max_v, nu, de, nv) struct Vertex v_array[MAX_VERTS]; int min_v; int max_v; int nu; int de; int nv; { int vertex_index; for (vertex_index = 0; vertex_index < nv; vertex_index++) { if ((v_array[vertex_index].min_vertex == min_v) && (v_array[vertex_index].max_vertex == max_v) && (v_array[vertex_index].numerator == nu) && (v_array[vertex_index].denominator == de)) { return(vertex_index); /* found */ } } return(NOT_FOUND); } /* end findVertex() */ /* * computeCoords() - compute coordinates of new verices */ int computeCoords(v_array) struct Vertex v_array[MAX_VERTS]; { int i, j, k; double ix, iy, iz; for (i = 0; i < NumVerts; i++) { if (v_array[i].elder_flag == FALSE) { j = v_array[i].min_vertex; k = v_array[i].max_vertex; Junk = interp( v_array[j].coordinates[X], v_array[j].coordinates[Y], v_array[j].coordinates[Z], v_array[k].coordinates[X], v_array[k].coordinates[Y], v_array[k].coordinates[Z], &ix, &iy, &iz, v_array[i].numerator, v_array[i].denominator); v_array[i].coordinates[X] = ix; v_array[i].coordinates[Y] = iy; v_array[i].coordinates[Z] = iz; } } return(0); } /* end computeCoords() */ /* * writeVerts() - write vertices to stdout */ int writeVerts(v_array) struct Vertex v_array[MAX_VERTS]; { int i; double re, gr, bl; fprintf(stdout, "facet\n"); fprintf(stdout, "%d\n", NumVerts); for (i = 0; i < NumVerts; i++) { if (Colors) { re = fabs(v_array[i].coordinates[X]); gr = fabs(v_array[i].coordinates[Y]); bl = fabs(v_array[i].coordinates[Z]); } else { re = gr = bl = 1.0; } fprintf(stdout, "%f %f %f %f %f %f\n", v_array[i].coordinates[X], v_array[i].coordinates[Y], v_array[i].coordinates[Z], re, gr, bl); } return(0); } /* end writeVerts() */ /* * writePolys() - write polygons to stdout */ int writePolys(p_array) struct Polygon p_array[MAX_VERTS]; { int i; for (i = 0; i < NumPolys; i++) { fprintf(stdout, "%d\n", 3); /* ToDo: add web3d format (this is AVS polyh) */ fprintf(stdout, "%d %d %d\n", p_array[i].vertex_list[0] + 1, p_array[i].vertex_list[1] + 1, p_array[i].vertex_list[2] + 1); } return(0); } /* end writePolys() */ /* * tess_tri() - tesselate one triangle */ int tess_tri(v_array, p_array, freq, a, b, c) /* tess 1 facet, mk verts & polys */ struct Vertex v_array[MAX_VERTS]; struct Polygon p_array[MAX_POLYS]; int freq; int a, b, c; /* elder vert ids */ { int i_row_y, i_col_x; int max_col_x; int created_flag; int facet[MAX_DEGREE + 1][MAX_DEGREE + 1]; double x_coord; int x0, x1, y0, y1; int row; /* unused cells */ for (i_row_y = 0; i_row_y <= freq; i_row_y++) { for (i_col_x = 0; i_col_x <= freq; i_col_x++) { if (i_col_x > i_row_y) { facet[i_col_x][i_row_y] = UNUSED; } } } /* corners */ facet[0][0] = a; /* upper left */ facet[0][freq] = b; /* lower left */ facet[freq][freq] = c; /* lower right */ /* edges ignoring corners */ /* diagonal edge (top left to bottom right) */ for (i_row_y = 1; i_row_y < freq; i_row_y++) { facet[i_row_y][i_row_y] = attemptToCreateVertex(v_array, FALSE, a, c, i_row_y, freq, 0.0, 0.0, 0.0, &created_flag); } /* bottom edge (right to left) */ for (i_col_x = 1; i_col_x < freq; i_col_x++) { facet[i_col_x][freq] = attemptToCreateVertex(v_array, FALSE, b, c, i_col_x, freq, 0.0, 0.0, 0.0, &created_flag); } /* left edge (top to bottom) */ for (i_row_y = 1; i_row_y < freq; i_row_y++) { facet[0][i_row_y] = attemptToCreateVertex(v_array, FALSE, a, b, i_row_y, freq, 0.0, 0.0, 0.0, &created_flag); } /* interior */ for (i_row_y = 2; i_row_y < freq; i_row_y++) { max_col_x = i_row_y; for (i_col_x = 1; i_col_x < max_col_x; i_col_x++) { facet[i_col_x][i_row_y] = attemptToCreateVertex(v_array, FALSE, facet[0][i_row_y], facet[max_col_x][i_row_y], i_col_x, max_col_x, 0.0, 0.0, 0.0, &created_flag); if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: interior: i_col_x: %d i_row_y: %d\n", ProgName, i_col_x, i_row_y); fprintf(stderr, "%s: DEBUG: interior: v_min: %d v_max: %d\n", ProgName, facet[0][i_row_y], facet[max_col_x][i_row_y]); fprintf(stderr, "%s: DEBUG: interior: nu: %d de: %d\n", ProgName, i_col_x, max_col_x); } } } if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: :::::::: facet[][]:\n", ProgName); Junk = computeCoords(v_array); for (i_row_y = 0; i_row_y <= freq; i_row_y++) { for (i_col_x = 0; i_col_x <= freq; i_col_x++) { x_coord = v_array[facet[i_col_x][i_row_y]].coordinates[X]; fprintf(stderr, "%d %f\t", facet[i_col_x][i_row_y], x_coord); } fprintf(stderr, "\n"); } } /* create polygons */ if (Frequency < 1) { fprintf(stderr, "%s: ERROR: attemptToCreateVertex() non-positive frequency\n", ProgName); exit(0); } /* AVS wants vetices listed counter-clockwise */ /*------------------------------------ * 0,0 |\ *-* 0,1 1,1 |\|\ *-*-* 0,2 1,2 2,2 |\|\|\ *-*-*-* 0,3 1,3 2,3 3,3 |\|\|\|\ *-*-*-*-* 0,4 1,4 2,4 3,4 4,4 |\|\|\|\|\ *-*-*-*-*-* 0,5 1,5 2,5 3,5 4,5 5,5 ------------------------------------*/ /* I don't want to mess with this right now */ row = 0; /* downward facing */ for (x0 = 0; x0 < row; x0++) { if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: can't happen\n", ProgName); } } /* upward facing */ y0 = row; y1 = y0 + 1; for (x0 = 0; x0 < row + 1; x0++) { x1 = x0 + 1; Junk = createPolygon(p_array, facet[x0][y0], facet[x0][y1], facet[x1][y1]); /* U OK */ if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: U: row = %d ; NumPolys = %d\n", ProgName, row, NumPolys); } } if (freq == 1) { return(0); } for (row = 1; row < Frequency; row++) { /*------------------------------------------------------------------------------*/ y0 = row; y1 = y0 + 1; /* downward facing */ for (x0 = 0; x0 < row; x0++) { x1 = x0 + 1; Junk = createPolygon(p_array, facet[x0][y0], facet[x1][y1], facet[x1][y0]); /* D OK */ if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: D: row = %d ; NumPolys = %d\n", ProgName, row, NumPolys); } } /* upward facing */ for (x0 = 0; x0 < row + 1; x0++) { x1 = x0 + 1; Junk = createPolygon(p_array, facet[x0][y0], facet[x0][y1], facet[x1][y1]); /* U OK */ if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: U: row = %d ; NumPolys = %d\n", ProgName, row, NumPolys); } } } return(0); } /* end tess_tri() */ /* * lines_in_file() - from Stacktrace */ int lines_in_file(filename) char filename[]; { FILE *fp; /* */ int c; /* Nb. int (not char) for the EOF */ unsigned long newline_count = 0; /* count the newline characters */ fp = fopen(filename, "r"); if (fp == NULL) { fprintf(stderr, "%s: ERROR: file open of %s failed, error: %s\n", ProgName, filename, strerror(errno)); exit(0); } while ( (c=fgetc(fp)) != EOF ) { if ( c == '\n' ) { newline_count++; } } fclose(fp); return newline_count; } /* end lines_in_file() */ /* * extract_filename() */ char * extract_filename(char *str) { int ch = '/'; size_t len; char *pdest; char *inpfile = NULL; // Search backwards for last backslash in filepath pdest = strrchr(str, ch); // if backslash not found in filepath if(pdest == NULL ) { printf( "Result:\t%c not found\n", ch ); pdest = str; // The whole name is a file in current path? } else { pdest++; // Skip the backslash itself. } // extract filename from file path len = strlen(pdest); inpfile = malloc(len+1); // Make space for the zero. strncpy(inpfile, pdest, len+1); // Copy including zero. return inpfile; } int main(argc, argv) int argc; char** argv; { /* declare functions */ void defualtParms(); void parseArgs(); /* declare and initialize local variables */ FILE* poly_fp; char line_buffer[MAX_LINE]; int line_len; int comparison1; int comparison2; int num_elder_verts; int num_facets; int p_size, lif; int a, b, c, i, n; double x, y, z; double red, grn, blu; int created_flag; /* Boolean */ int np; int nv; int pn; int temp_vertex_number, found_vertex_number; struct Polygon poly_array[MAX_POLYS]; struct Vertex vert_array[MAX_VERTS]; NumPolys = 0; NumVerts = 0; for (nv = 0; nv < MAX_VERTS; nv++) { vert_array[nv].elder_flag = FALSE; } /* initialize global variables (including parameters) */ defaultParms(); parseArgs(argc, argv); ProgName = extract_filename(argv[0]); if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: Debug = %d\n", ProgName, Debug); fprintf(stderr, "%s: DEBUG: PolyFile = %s\n", ProgName, PolyFile); fprintf(stderr, "%s: DEBUG: Frequency = %d\n", ProgName, Frequency); fflush(stderr); } /* read polygon file */ poly_fp = fopen(PolyFile, "r"); fscanf(poly_fp, "%s", line_buffer); if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: line_buffer = %s\n", ProgName, line_buffer); } comparison1 = strcmp(line_buffer, "facet"); comparison2 = strcmp(line_buffer, "smooth"); if ((comparison1 != 0) && (comparison2 != 0)) { fprintf(stderr, "%s: ERROR: first line of polyh file is \'%s\', must be \'facet\' or \'smooth\'\n", ProgName, line_buffer); exit(0); } /* create elder vetices */ fscanf(poly_fp, "%d", &num_elder_verts); if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: num_elder_verts = %d\n", ProgName, num_elder_verts); } /* read vertices */ for (n = 0; n < num_elder_verts; n++) { fscanf(poly_fp, "%lf %lf %lf %lf %lf %lf", &x, &y, &z, &red, &grn, &blu); if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: x = %f y = %f z = %f\n", ProgName, x, y, z); fprintf(stderr, "%s: DEBUG: red = %f grn = %f blu = %f\n", ProgName, red, grn, blu); } Junk = attemptToCreateVertex(vert_array, TRUE, n, n, 0, 1, x, y, z, &created_flag); if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: n = %d Junk = %d\n", ProgName, n, Junk); } } /* process polygons */ lif = lines_in_file(PolyFile); num_facets = (lif - NumVerts - 2)/2; if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: lif = %d NumVerts = %d num_facets = %d\n", ProgName, lif, NumVerts, num_facets); } for (i = 0; i < num_facets; i++) { /* read polygon size */ fscanf(poly_fp, "%d", &p_size); if (p_size != 3) { fprintf(stderr, "%s: ERROR: polygon size must be 3, got %d\n", ProgName, p_size); exit(0); } /* read polygons */ fscanf(poly_fp, "%d %d %d", &a, &b, &c); if (Debug != FALSE) { fprintf(stderr, "%s: DEBUG: a = %d b = %d c = %d\n", ProgName, a, b, c); } Junk = tess_tri(vert_array, poly_array, Frequency, a - 1, b - 1, c - 1); } /* compute needed coordinates by interpolating */ /* Junk = computeCoords(vert_array); */ Junk = computeCoords(vert_array); /* puffing */ if (Puff) { int i; double x, y, z; double x_out; double y_out; double z_out; for (i = 0; i < NumVerts; i++) { x = vert_array[i].coordinates[X]; y = vert_array[i].coordinates[Y]; z = vert_array[i].coordinates[Z]; puff(x, y, z, &x_out, &y_out, &z_out); vert_array[i].coordinates[X] = x_out; vert_array[i].coordinates[Y] = y_out; vert_array[i].coordinates[Z] = z_out; } } /* write vertices */ Junk = writeVerts(vert_array); /* write polygons */ Junk = writePolys(poly_array); } /* end main */