/* Last edited on 2024-12-21 11:34:30 by stolfi */{ /* Program to find what type of geometric degeneration exists in a given arbitrary topology (triangulation or not). The "detail" option allows to print detail information about the degeneracies. Otherwise only an abstract information is printed. */ #define WhatDegenerations_C_author \ "Created by L. Lozada, 1999-2000.\n" \ "Modified by L.A.P.Lozada on 2000-02-07." #include #include #include #include #include CONST double INIT_STACK_SIZE = 1024; VAR Edge_vec_t estack = Edge_vec_new(INIT_STACK_SIZE); Edge_vec_t estackT = Edge_vec_new(INIT_STACK_SIZE); Edge_vec_t estackF = Edge_vec_new(INIT_STACK_SIZE); Wall_vec_t fstack = Wall_vec_new(INIT_STACK_SIZE); Wall_vec_t fstackT = Wall_vec_new(INIT_STACK_SIZE); Wall_vec_t fstackF = Wall_vec_new(INIT_STACK_SIZE); pstack = Cell_vec_new(INIT_STACK_SIZE); etop,etopT,etopF,ftop,ftopT,ftopF,ptop,eetop,fftop,pptop: uint = 0; TYPE typedef struct Options_t { inFile: char *; bool_t detail; } /* Initial guess file name (minus ".tp") */ Options_t *GetOptions(int argc, char **argv); int main(int argc, char **argv) VAR bool_t @{edge->?}s,walls, cells = FALSE; e1,e2,f1,f2,p1,p2: REF ARRAY OF INTEGER; { Options_t *o = GetOptions(argc, argv); char *topo_cmt = jsprintf("Created by %s on %s", PROG_NAME, Today()); /* Random_t coins = MakeRandomSource(4615); */ ??? tc = Triangulation.ReadToMa(o->inFile); ??? top = tc.top; { /* Clean the marks for the attribute degenerate */ for (i = 0; i < top->NE; i++){ deg[i] = FALSE; } for (i = 0; i < top->NE; i++) { for (j = i+1; j < top->NE; j++) { ??? ei = NARROW(top->edge[i], Edge_t); { double ej = NARROW(top->edge[j], Edge_t); double ei0 = ei.node[0]->num; double ei1 = ei.node[1]->num; double ej0 = ej.node[0]->num; double ej1 = ej.node[1]->num ){ e1 = NEW(REF ARRAY OF INTEGER, 2); e1[0] = ei0; e1[1] = ei1; Mis.InsertionSort(1,e1); e2 = NEW(REF ARRAY OF INTEGER, 2); e2[0] = ej0; e2[1] = ej1; Mis.InsertionSort(1,e2); if ((e1[0] == e2[0]) && (e1[1] == e2[1])) { if (! deg[i]) { deg[i] = TRUE; estack.el[etop] = ei; etop++; if (ei->exists) { estackT[etopT] = ei; etopT++; } else { estackF[etopF] = ei; etopF++; } } if (! deg[j]) { deg[j] = TRUE; estack.el[etop] = ej; etop++; if (ej->exists) { estackT[etopT] = ej; etopT++; } else { estackF[etopF] = ej; etopF++; } } @{edge->?}s = TRUE; } } } } /* Clean the marks for the attribute degenerate */ for (i = 0; i < top->wall.nel; i++){ fdeg[i] = FALSE; } if (top->der == 3) { for (i = 0; i < top->wall.nel; i++) { for (j = i+1; j < top->wall.nel; j++) { ??? fi = top->wall[i]; ??? fj = top->wall[j]; ??? fi0 = fi.node^[0]->num; ??? fi1 = fi.node^[1]->num; ??? fi2 = fi.node^[2]->num; ??? fj0 = fj.node^[0]->num; ??? fj1 = fj.node^[1]->num; ??? fj2 = fj.node^[2]->num; { f1 = NEW(REF ARRAY OF INTEGER, 3); f1[0] = fi0; f1[1] = fi1; f1[2] = fi2; Mis.InsertionSort(2,f1); f2 = NEW(REF ARRAY OF INTEGER, 3); f2[0] = fj0; f2[1] = fj1; f2[2] = fj2; Mis.InsertionSort(2,f2); if ((f1[0] == f2[0]) && (f1[1] == f2[1]) && (f1[2] == f2[2])) { if (! fdeg[i]) { fdeg[i] = TRUE; fstack.el[ftop] = fi; ftop++; if (fi->exists) { fstackT[ftopT] = fi; ftopT++; } else { fstackF[ftopF] = fi; ftopF++; } } if (! fdeg[j]) { fdeg[j] = TRUE; fstack.el[ftop] = fj; ftop++; if (fj->exists) { fstackT[ftopT] = fj; ftopT++; } else { fstackF[ftopF] = fj; ftopF++; } } walls = TRUE; } } } } } else if (top->der == 4){ for (i = 0; i < top->wall.nel; i++) { for (j = i+1; j < top->wall.nel; j++) { ??? fi = top->wall[i]; ??? fj = top->wall[j]; ??? fi0 = fi.node^[0]->num; ??? fi1 = fi.node^[1]->num; ??? fi2 = fi.node^[2]->num; ??? fi3 = fi.node^[3]->num; ??? fj0 = fj.node^[0]->num; ??? fj1 = fj.node^[1]->num; ??? fj2 = fj.node^[2]->num; ??? fj3 = fj.node^[3]->num; { f1 = NEW(REF ARRAY OF INTEGER, 4); f1[0] = fi0; f1[1] = fi1; f1[2] = fi2; f1[3] = fi3; Mis.InsertionSort(3,f1); f2 = NEW(REF ARRAY OF INTEGER, 4); f2[0] = fj0; f2[1] = fj1; f2[2] = fj2; f2[3] = fj3; Mis.InsertionSort(3,f2); if (((f1[0] == f2[0]) && (f1[1] == f2[1]) && ((f1[2] == f2[2]) ) && (f1[3] == f2[3]))){ if (! fdeg[i]) { fdeg[i] = TRUE; fstack.el[ftop] = fi; ftop++; } if (! fdeg[j]) { fdeg[j] = TRUE; fstack.el[ftop] = fj; ftop++; } walls = TRUE; } } } } } else if (top->der == 2){ for (i = 0; i < top->wall.nel; i++) { for (j = i+1; j < top->wall.nel; j++) { ??? fi = top->wall[i]; ??? fj = top->wall[j]; ??? fi0 = fi.node^[0]->num; ??? fi1 = fi.node^[1]->num; ??? fj0 = fj.node^[0]->num; ??? fj1 = fj.node^[1]->num; { f1 = NEW(REF ARRAY OF INTEGER, 2); f1[0] = fi0; f1[1] = fi1; Mis.InsertionSort(1,f1); f2 = NEW(REF ARRAY OF INTEGER, 2); f2[0] = fj0; f2[1] = fj1; Mis.InsertionSort(1,f2); if ((f1[0] == f2[0]) && (f1[1] == f2[1])) { if (! fdeg[i]) { fdeg[i] = TRUE; fstack.el[ftop] = fi; ftop++; } if (! fdeg[j]) { fdeg[j] = TRUE; fstack.el[ftop] = fj; ftop++; } walls = TRUE; } } } } } /* Clean the marks for the attribute degenerate */ for (i = 0; i < top->cell.nel; i++){ pdeg[i] = FALSE; } if (top->der == 3) { for (i = 0; i < top->cell.nel; i++) { for (j = i+1; j < top->cell.nel; j++) { ??? pi = top->cell[i]; ??? pj = top->cell[j]; ??? pi0 = pi.node^[0]->num; ??? pi1 = pi.node^[1]->num; ??? pi2 = pi.node^[2]->num; ??? pi3 = pi.node^[3]->num; ??? pj0 = pj.node^[0]->num; ??? pj1 = pj.node^[1]->num; ??? pj2 = pj.node^[2]->num; ??? pj3 = pj.node^[3]->num; { p1 = NEW(REF ARRAY OF INTEGER, 4); p1[0] = pi0; p1[1] = pi1; p1[2] = pi2; p1[3] = pi3; Mis.InsertionSort(3,p1); p2 = NEW(REF ARRAY OF INTEGER, 4); p2[0] = pj0; p2[1] = pj1; p2[2] = pj2; p2[3] = pj3; Mis.InsertionSort(3,p2); if ((p1[0]==p2[0]) && (p1[1]==p2[1]) && ((p1[2]==p2[2]) AND (p1[3]==p2[3]))){ if (! pdeg[i]) { pdeg[i] = TRUE; pstack.el[ptop] = pi; ptop++; } if (! pdeg[j]) { pdeg[j] = TRUE; pstack.el[ptop] = pj; ptop++; } cells = TRUE; } } } } } else if (top->der == 4){ for (i = 0; i < top->cell.nel; i++) { for (j = i+1; j < top->cell.nel; j++) { ??? pi = top->cell[i]; ??? pj = top->cell[j]; ??? pi0 = pi.node^[0]->num; ??? pi1 = pi.node^[1]->num; ??? pi2 = pi.node^[2]->num; ??? pi3 = pi.node^[3]->num; ??? pi4 = pi.node^[4]->num; ??? pi5 = pi.node^[5]->num; ??? pi6 = pi.node^[6]->num; ??? pi7 = pi.node^[7]->num; ??? pj0 = pj.node^[0]->num; ??? pj1 = pj.node^[1]->num; ??? pj2 = pj.node^[2]->num; ??? pj3 = pj.node^[3]->num; ??? pj4 = pj.node^[4]->num; ??? pj5 = pj.node^[5]->num; ??? pj6 = pj.node^[6]->num; ??? pj7 = pj.node^[7]->num; { p1 = NEW(REF ARRAY OF INTEGER, 8); p1[0] = pi0; p1[1] = pi1; p1[2] = pi2; p1[3] = pi3; p1[4] = pi4; p1[5] = pi5; p1[6] = pi6; p1[7] = pi7; Mis.InsertionSort(7,p1); p2 = NEW(REF ARRAY OF INTEGER, 8); p2[0] = pj0; p2[1] = pj1; p2[2] = pj2; p2[3] = pj3; p2[4] = pj4; p2[5] = pj5; p2[6] = pj6; p2[7] = pj7; Mis.InsertionSort(7,p2); IF( (p1[0]==p2[0])) && ((p1[1]==p2[1]) AND (p1[2]==p2[2])) && ((p1[3]==p2[3]) AND (p1[4]==p2[4])) && ((p1[5]==p2[5]) AND (p1[6]==p2[6])) && (p1[7]==p2[7]) )){ if (pdeg[i]) { pstack.el[ptop] = pi; ptop++; } if (pdeg[j]) { pdeg[j] = TRUE; pstack.el[ptop] = pj; ptop++; } cells = TRUE; } } } } } if (@{edge->?}s) { fprintf(stderr, "there are " & Fmt.Int(etop) & " @{edge->?} degeneracies:\n"); fprintf(stderr, " " & Fmt.Int(etopT) & " existing\n"); fprintf(stderr, " " & Fmt.Int(etopF) & " not existing\n"); assert(etop == etopF + etopT); if (o->detail) { fprintf(stderr, "---------------------------------\n"); fprintf(stderr, " @{edge->?} node node\n"); eetop = etop; while (eetop > 0) { eetop = eetop-1; ??? @{edge->?} = estack.el[eetop]; ??? en = @{edge->?}->num; ??? a = @{edge->?}.pa; Node_t v0 = OrgV(a)->num; ??? v1 = OrgV(Clock(a))->num; { fprintf(stderr, Fmt.Pad(Fmt.Int(en), 4) & ":"); fprintf(stderr, Fmt.Pad(Fmt.Int(v0), 6) & " "); fprintf(stderr, Fmt.Pad(Fmt.Int(v1), 6) & "\n"); } } } } else { fprintf(stderr, "there aren't @{edge->?} degeneracies\n"); } if (walls) { fprintf(stderr, "there are "&Fmt.Int(ftop)&" wall degeneracies:\n"); fprintf(stderr, " " & Fmt.Int(ftopT) & " existing\n"); fprintf(stderr, " " & Fmt.Int(ftopF) & " not existing\n"); assert(ftop == ftopF + ftopT); if (o->detail) { fprintf(stderr, "---------------------------------\n"); fprintf(stderr, " wall @{edge->?} @{edge->?} @{edge->?}\n"); fftop = ftop; while (fftop > 0) { fftop = fftop-1; ??? wall = fstack.el[fftop]; ??? fn = wall->num; ??? a = wall.pa; Place_t b = NextE(a); Place_t c = NextE(b); ??? e0 = PEdge(a)->num; ??? e1 = PEdge(b)->num; ??? e2 = PEdge(c)->num; ??? i0 = ScanStack@{Edge->?}(e0); ??? i1 = ScanStack@{Edge->?}(e1); ??? i2 = ScanStack@{Edge->?}(e2); { fprintf(stderr, Fmt.Pad(Fmt.Int(fn), 3) & ":"); if (i0) { fprintf(stderr, Fmt.Pad(Fmt.Int(e0), 6) & "T"); } else { fprintf(stderr, Fmt.Pad(Fmt.Int(e0), 6) & "F"); } if (i1) { fprintf(stderr, Fmt.Pad(Fmt.Int(e1), 6)& "T"); } else { fprintf(stderr, Fmt.Pad(Fmt.Int(e1), 6) & "F"); } if (i2) { fprintf(stderr, Fmt.Pad(Fmt.Int(e2), 6) & "T\n"); } else { fprintf(stderr, Fmt.Pad(Fmt.Int(e2), 6) & "F\n"); } } } } } else { fprintf(stderr, "there aren't wall degeneracies\n"); } if (cells) { fprintf(stderr, "there are "&Fmt.Int(ptop)&" cell degeneracies\n"); if (o->detail) { fprintf(stderr, "-------------------------------------\n"); fprintf(stderr, "poly wall wall wall wall\n"); pptop = ptop; while (pptop > 0) { pptop = pptop-1; ??? cell = pstack.el[pptop]; ??? np = cell->num; ??? p = Srot(top->cell[np]); Place_t a = Tors(p); ??? walls = Triangulation.TetraWalls(a); ??? f0 = walls[0]->num; ??? f1 = walls[1]->num; ??? f2 = walls[2]->num; ??? f3 = walls[3]->num; ??? i0 = ScanStackWall(f0); ??? i1 = ScanStackWall(f1); ??? i2 = ScanStackWall(f2); ??? i3 = ScanStackWall(f3); { fprintf(stderr, Fmt.Pad(Fmt.Int(np), 3) & ":"); if (i0) { fprintf(stderr, Fmt.Pad(Fmt.Int(f0), 6) & "T"); } else { fprintf(stderr, Fmt.Pad(Fmt.Int(f0), 6) & "F"); } if (i1) { fprintf(stderr, Fmt.Pad(Fmt.Int(f1), 6) & "T"); } else { fprintf(stderr, Fmt.Pad(Fmt.Int(f1), 6) & "F"); } if (i2) { fprintf(stderr, Fmt.Pad(Fmt.Int(f2), 6) & "T"); } else { fprintf(stderr, Fmt.Pad(Fmt.Int(f2), 6) & "F"); } if (i3) { fprintf(stderr, Fmt.Pad(Fmt.Int(f3), 6) & "T\n"); } else { fprintf(stderr, Fmt.Pad(Fmt.Int(f3), 6) & "F\n"); } } } } } else { fprintf(stderr, "there aren't cell degeneracies\n"); } } } DoIt; void FindDegeneracies(ElemTableRec_t *top) /* Finds geometric degeneracies. Update the attribute "degenerate" of the elements: @{edge->?}, wall and cell. */ Edge_vec_t estack = Edge_vec_new(top->NE); bool_vec_t edeg = bool_vec_new(top->NE); Wall_vec_t fstack = Wall_vec_new(top->wall.nel); bool_vec_t fdeg = bool_vec_new(top->wall.nel); pstack = NEW(REF ARRAY OF Cell, top->cell.nel); bool_vec_t pdeg = bool_vec_new(top->cell.nel); etop,ftop,ptop: uint = 0; { Find@{Edge->?}Degeneracies(top, estack^, etop); FindWallDegeneracies(top, fstack^, ftop); FindCellDegeneracies(top-> pstack^, ptop); } /* END FindDegeneracies */ PROCEDURE Find@{Edge->?}Degeneracies(ElemTableRec_t *top, Edge_vec_t estack; VAR uint *etop; ) == /* Find @places of @{edge->?}s with same nodes. */ { etop = 0; for (i = 0; i < top->NE; i++){ edeg[i] = FALSE; } for (i = 0; i < top->NE; i++) { ??? ei = top->edge[i]; with ( @{Edge->?}, double ei0 = OrgV(ei)->num; double ei1 = OrgV(Clock(ei))->num) { for (j = i+1; j < top->NE; j++) { ??? ej = top->edge[j]; Node_t ej0 = OrgV(ej)->num; ??? ej1 = OrgV(Clock(ej))->num; { if (((ei0 == ej0) && (ei1 == ej1) ) || ((ei0 == ej1) && (ei1 == ej0))){ if (! deg[i]) { deg[i] = TRUE; estack.el[etop] = ei; etop++; } if (! deg[j]) { deg[j] = TRUE; estack.el[etop] = ej; etop++; } } } } } } } /* END Find@{Edge->?}Degeneracies */ PROCEDURE FindWallDegeneracies(ElemTableRec_t *top, Wall_vec_t fstack; VAR uint *ftop; ) /* Find @places of walls with same nodes */ rvfi, rvfj: REF uint_vec_t; uint dgi, dgj; { ftop = 0; for (i = 0; i < top->wall.nel; i++){ fdeg[i] = FALSE; } for (i = 0; i < top->wall.nel; i++) { CollectWallNodes(top->wall[i], rvfi, dgi); ??? fi = top->wall[i], vfi == SUBARRAY(rvfi^, 0, dgi); { Mis.SortCardinals(vfi); for (j = i+1; j < top->wall.nel; j++) { CollectWallNodes(top->wall[j], rvfj, dgj); ??? fj = top->wall[j], vfj == SUBARRAY(rvfj^, 0, dgj); { Mis.SortCardinals(vfj); if (vfi == vfj) { if (! fdeg[i]) { fdeg[i] = TRUE; fstack.el[ftop] = fi; ftop++; } if (! fdeg[j]) { fdeg[j] = TRUE; fstack.el[ftop] = fj; ftop++; } } } } } } } /* END FindWallDegeneracies */ PROCEDURE FindCellDegeneracies(ElemTableRec_t *top, ARRAY OF Cell pstack ; uint *ptop; ) /* Finds @places of cells with same nodes. */ rvpi, rvpj: REF uint_vec_t; uint dgi, dgj; { ptop = 0; for (i = 0; i < top->cell.nel; i++){ pdeg[i] = FALSE; } ClearXMarks(top); for (i = 0; i < top->cell.nel; i++) { Place_t ai = Tors(Srot(top.cell[i])), pi == PnegP(ai); { assert(pi->num == i); CollectCellNodes(ai, rvpi, dgi); ??? vpi = SUBARRAY(rvpi^, 0, dgi); { Mis.SortCardinals(vpi); for (j = i+1; j < top->cell.nel; j++) { Place_t aj = Tors(Srot(top->cell[j])), pj == PnegP(aj); { assert(pj->num == j); CollectCellNodes(aj, rvpj, dgj); ??? vpj = SUBARRAY(rvpj^, 0, dgj); { Mis.SortCardinals(vpj); if (vpi == vpj) { if (! pdeg[i]) { pdeg[i] = TRUE; pstack.el[ptop] = pi; ptop++; } if (! pdeg[j]) { pdeg[j] = TRUE; pstack.el[ptop] = pj; ptop++; } } } } } } } } } /* END FindDegenerateCells */ Options_t *GetOptions(int argc, char **argv) { Options_t *o = (Options_t *)malloc(sizeof(Options_t)); argparser_t *pp = argparser_new(stderr, argc, argv); argparser_set_help(pp, PROG_NAME " version " PROG_VERS ", usage:\n" PROG_HELP); argparser_set_info(pp, PROG_INFO); argparser_process_help_info_options(pp); argparser_get_keyword(pp, "-inFile"); o->inFile = argparser_get_next(pp); o->detail = argparser_keyword_present(pp, "-detail"); argparser_finish(pp); ----------------------------------- #define _HELP \ fprintf(stderr, "Usage: WhatDegenerations" \ " -inFile [ -detail ]\n"); END¦ } } return o; } /* END GetOptions */ PROCEDURE ScanStack@{Edge->?}(uint n): bool_t == uint counter = 0; { counter = etop; while (counter > 0) { counter = counter-1; if (estack.el[counter]->num == n){ return TRUE; } } return FALSE; } /* END ScanStack@{Edge->?} */ bool_t ScanStackWall(num: uint) uint counter = 0; { counter = ftop; while (counter > 0) { counter = counter-1; if (fstack.el[counter]->num == num){ return TRUE; } } return FALSE; } /* END ScanStackWall */ { DoIt() } WhatDegenerations. /* Copyright © 2000 Universidade Estadual de Campinas (UNICAMP) */