Debian Codegraph @

dune/uggrid/gm/GenerateRules.cc

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 /****************************************************************************/
6 /* */
7 /* File: GenerateRules.c */
8 /* */
9 /* Purpose: generate the rules for ug3d */
10 /* */
11 /* Author: Henrik Reichert */
12 /* Institut fuer Angewandte Mathematik */
13 /* Universitaet Heidelberg */
14 /* Im Neuenheimer Feld 294 */
15 /* 6900 Heidelberg */
16 /* */
17 /* History: 10.9.1993 begin */
18 /* */
19 /****************************************************************************/
20
21 #include <config.h>
22 #include <cstring>
23 #include <cstdio>
24 #include <cstdlib>
25 #include <cassert>
26
27 #include "GenerateRules.h"
28
29 #include "gm.h"
30 #include "simplex.h"
31 #include "ugrefine3d.h"
32
33 #include <dune/uggrid/low/general.h>
34
35 /* only compile for 3D version */
36 #ifdef UG_DIM_3
37
38 /****************************************************************************/
39 /* */
40 /* defines and macros */
41 /* */
42 /****************************************************************************/
43
44 #define PATTERNFILTER 0x3F /* mask for the first 6 digits of pattern: 00111111 */
45 #define NOFATHERSIDE 5 /* has to be just greater than MAX_SIDES_OF_ELEM */
46
47 #define NRULES 242
48 #define MAXCORNERS 11 /* max no. of new corners (incl. center) */
49
50 #define NOTDONE -1 /* SHORT has to be signed! */
51 #define DONE 0
52 #define TOUCHED 1 /* has been visited by FindPathForNeighbours*/
53
54 /****************************************************************************/
55 /* */
56 /* data structures used in this source file (exported data structures are */
57 /* in the corresponding include file!) */
58 /* */
59 /****************************************************************************/
60
61
62 /****************************************************************************/
63 /* */
64 /* global variables */
65 /* */
66 /****************************************************************************/
67
68 static EDGEDATA EdgeData[MAXCORNERS][MAXCORNERS] =
69 {
70 {{0,0,0,0},{0,0,1,0},{0,0,2,0},{0,0,3,0},{0,0,4,0},{2,0,5,0},{0,0,6,0},{0,0,7,0},{2,0,8,3},{2,0,9,2},{1,0,10,0}},
71 {{0,0,1,0},{0,1,1,0},{0,1,2,0},{0,1,3,0},{0,1,4,0},{0,1,5,0},{2,1,6,0},{2,1,7,3},{0,1,8,0},{2,1,9,1},{1,1,10,0}},
72 {{0,0,2,0},{0,1,2,0},{0,2,2,0},{0,2,3,0},{2,2,4,0},{0,2,5,0},{0,2,6,0},{2,2,7,2},{2,2,8,1},{0,2,9,0},{1,2,10,0}},
73 {{0,0,3,0},{0,1,3,0},{0,2,3,0},{0,3,3,0},{2,3,4,3},{2,3,5,1},{2,3,6,2},{0,3,7,0},{0,3,8,0},{0,3,9,0},{1,3,10,0}},
74 {{0,0,4,0},{0,1,4,0},{2,2,4,0},{2,3,4,3},{0,4,4,0},{2,4,5,0},{2,4,6,0},{2,4,7,3},{2,4,8,3},{1,4,9,0},{1,4,10,0}},
75 {{2,0,5,0},{0,1,5,0},{0,2,5,0},{2,3,5,1},{2,4,5,0},{0,5,5,0},{2,5,6,0},{1,5,7,0},{2,5,8,1},{2,5,9,1},{1,5,10,0}},
76 {{0,0,6,0},{2,1,6,0},{0,2,6,0},{2,3,6,2},{2,4,6,0},{2,5,6,0},{0,6,6,0},{2,6,7,2},{1,6,8,0},{2,6,9,2},{1,6,10,0}},
77 {{0,0,7,0},{2,1,7,3},{2,2,7,2},{0,3,7,0},{2,4,7,3},{1,5,7,0},{2,6,7,2},{0,7,7,0},{2,7,8,3},{2,7,9,2},{1,7,10,0}},
78 {{2,0,8,3},{0,1,8,0},{2,2,8,1},{0,3,8,0},{2,4,8,3},{2,5,8,1},{1,6,8,0},{2,7,8,3},{0,8,8,0},{2,8,9,1},{1,8,10,0}},
79 {{2,0,9,2},{2,1,9,1},{0,2,9,0},{0,3,9,0},{1,4,9,0},{2,5,9,1},{2,6,9,2},{2,7,9,2},{2,8,9,1},{0,9,9,0},{1,9,10,0}},
80 {{1,0,10,0},{1,1,10,0},{1,2,10,0},{1,3,10,0},{1,4,10,0},{1,5,10,0},{1,6,10,0},{1,7,10,0},{1,8,10,0},{1,9,10,0},{0,10,10,0}}
81 };
82
83 static SHORT CornerOfSonSide[MAX_SIDES_OF_ELEM][3] = {{0,1,2},{1,2,3},{0,2,3},{0,1,3}};
84 static SHORT IsOnSide[MAX_SIDES_OF_ELEM][MAXCORNERS] = {{1,1,1,0,1,1,1,0,0,0,0},
85 {0,1,1,1,0,1,0,0,1,1,0},
86 {1,0,1,1,0,0,1,1,0,1,0},
87 {1,1,0,1,1,0,0,1,1,0,0}};
88
89 static int nRulesTh; /* total number of theoretical refinement rules */
90 static int nRules; /* total number of generated refinement rules */
91 static int FirstRuleWithEdgePattern; /* Rule no. of first of several SidePatterns */
92 static REFRULE *RuleList; /* list is allocated in main program */
93 static SHORT *PatternToRefrule; /* vector is allocated in main program */
94 static bool Output; /* if true output of generated rules */
95
96 /* prototype for new rules without any data */
97 static REFRULE EmptyRule =
98 {0,{0,0,0,0,0,0},0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}},
99
100 {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},
101 {0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},
102 {0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},
103 {0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}},
104
105 {{{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
106 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
107 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
108 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
109 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
110 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
111 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
112 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
113 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
114 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
115 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
116 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}}};
117
118 /****************************************************************************/
119 /* */
120 /* functions */
121 /* */
122 /****************************************************************************/
123
124 static SHORT SideWithCorners (SHORT C0,SHORT C1,SHORT C2)
125 {
126 SHORT Side;
127
128 for (Side=0; Side<MAX_SIDES_OF_ELEM; Side++)
129 if (IsOnSide[Side][C0] && IsOnSide[Side][C1] &&IsOnSide[Side][C2])
130 break;
131
132 if (Side<MAX_SIDES_OF_ELEM)
133 return (Side+FATHER_SIDE_OFFSET);
134 else
135 return (NOFATHERSIDE);
136 }
137
138 /* definition of the rotations of the tetrahedron indices */
139 static SHORT Ax0Left [MAXCORNERS] = {0,3,1,2,7,8,4,6,9,5,10};
140 static SHORT Ax0Right[MAXCORNERS] = {0,2,3,1,6,9,7,4,5,8,10};
141 static SHORT Ax1Left [MAXCORNERS] = {2,1,3,0,5,8,9,6,4,7,10};
142 static SHORT Ax1Right[MAXCORNERS] = {3,1,0,2,8,4,7,9,5,6,10};
143 static SHORT Ax2Left [MAXCORNERS] = {3,0,2,1,7,6,9,8,4,5,10};
144 static SHORT Ax2Right[MAXCORNERS] = {1,3,2,0,8,9,5,4,7,6,10};
145 static SHORT Ax3Left [MAXCORNERS] = {1,2,0,3,5,6,4,8,9,7,10};
146 static SHORT Ax3Right[MAXCORNERS] = {2,0,1,3,6,4,5,9,7,8,10};
147
148 static int RotateCorners (REFRULE *theRule, SHORT ReplaceBy[MAXCORNERS])
149 {
150 SONDATA *theSon;
151 SHORT i,j;
152
153 for (i=0; i<theRule->nsons; i++)
154 for (theSon = theRule->sons+i, j=0; j<CORNERS_OF_ELEM; j++)
155 theSon->corners[j] = ReplaceBy[theSon->corners[j]];
156
157 return (0);
158 }
159
160 static int PrintRule (REFRULE *theRule, SHORT nEdges)
161 {
162 SHORT i,j;
163
164 printf("nsons %d; pattern %d%d%d%d%d%d; ",(int)theRule->nsons, (int)theRule->pattern[5],
165 (int)theRule->pattern[4],
166 (int)theRule->pattern[3],
167 (int)theRule->pattern[2],
168 (int)theRule->pattern[1],
169 (int)theRule->pattern[0]);
170
171 printf("pat %#04x; (nedges %d)\n",(int)theRule->pat,(int)nEdges);
172
173 printf("edges: ");
174 for (i=0; i<8; i++)
175 printf("{%d,%d,%d,%d}",(int)theRule->edges[i].type,(int)theRule->edges[i].from,
176 (int)theRule->edges[i].to,(int)theRule->edges[i].side);
177 printf("\n\t");
178 for (; i<MAXEDGES; i++)
179 printf("{%d,%d,%d,%d}",(int)theRule->edges[i].type,(int)theRule->edges[i].from,
180 (int)theRule->edges[i].to,(int)theRule->edges[i].side);
181
182 printf("\nsons: ");
183 for (i=0; i<6; i++)
184 printf("{{%d,%d,%d,%d}{%d,%d,%d,%d}}",(int)theRule->sons[i].corners[0],(int)theRule->sons[i].corners[1],
185 (int)theRule->sons[i].corners[2],(int)theRule->sons[i].corners[3],
186 (int)theRule->sons[i].nb[0],(int)theRule->sons[i].nb[1],
187 (int)theRule->sons[i].nb[2],(int)theRule->sons[i].nb[3]);
188 printf("\n\t");
189 for (; i<SONS; i++)
190 printf("{{%d,%d,%d,%d}{%d,%d,%d,%d}}",(int)theRule->sons[i].corners[0],(int)theRule->sons[i].corners[1],
191 (int)theRule->sons[i].corners[2],(int)theRule->sons[i].corners[3],
192 (int)theRule->sons[i].nb[0],(int)theRule->sons[i].nb[1],
193 (int)theRule->sons[i].nb[2],(int)theRule->sons[i].nb[3]);
194 for (i=1; i<theRule->nsons; i++)
195 {
196 printf("\npath to %d: son0",i);
197 for (j=0; j<PATHDEPTH(theRule->sons[i].path); j++)
198 printf("-->nb%d",(int) NEXTSIDE(theRule->sons[i].path,j));
199
200 printf(" (%d steps)",(int) PATHDEPTH(theRule->sons[i].path));
201 }
202
203 printf("\nsonandnode:");
204 for (i=0; i<NEWCORNERS; i++)
205 printf(" %d->(%d,%d)",(int)(i+CORNERS_OF_ELEM),(int)theRule->sonandnode[i][0],(int)theRule->sonandnode[i][1]);
206
207 printf("\n");
208
209 return (0);
210 }
211
212 static int CopySonsIntoRule (REFRULE *theRule,SONDATA sons[SONS])
213 {
214 SHORT i;
215
216 for (i=0; i<SONS; i++)
217 theRule->sons[i] = sons[i];
218
219 return (0);
220 }
221
222 static int CompareEdgesForSides (const void *Edge1, const void *Edge2)
223 {
224 EDGEDATA *theEdge1,*theEdge2;
225
226 theEdge1 = (EDGEDATA *) Edge1;
227 theEdge2 = (EDGEDATA *) Edge2;
228
229 /* leave type==0 at end of the list */
230 if ((theEdge1->type)==0)
231 return (1);
232 if ((theEdge2->type)==0)
233 return (-1);
234
235 if ((theEdge1->side)==(theEdge2->side))
236 return (0);
237 else if ((theEdge1->side)>(theEdge2->side))
238 return (1);
239 else
240 return (-1);
241 }
242
243 static int CompareEdges (const void *theEdge1, const void *theEdge2)
244 {
245 if (((EDGEDATA *)theEdge1)->from==((EDGEDATA *)theEdge2)->from)
246 {
247 if (((EDGEDATA *)theEdge1)->to>((EDGEDATA *)theEdge2)->to)
248 return (1);
249 else if (((EDGEDATA *)theEdge1)->to<((EDGEDATA *)theEdge2)->to)
250 return (-1);
251 else
252 return (0);
253 }
254 else if (((EDGEDATA *)theEdge1)->from>((EDGEDATA *)theEdge2)->from)
255 return (1);
256 else
257 return (-1);
258 }
259
260 static int CompareCorners (const void *theCorner1, const void *theCorner2)
261 {
262 SHORT C1,C2;
263
264 C1 = * ((SHORT *) theCorner1);
265 C2 = * ((SHORT *) theCorner2);
266
267 assert(C1!=C2);
268
269 if (C1>C2)
270 return (1);
271 else
272 return (-1);
273 }
274
275 static int NewEdgesAreEqual (EDGEDATA *NewEdges0, EDGEDATA *NewEdges1)
276 {
277 SHORT i;
278
279 for (i=0; i<MAXEDGES; i++)
280 if ((NewEdges0[i].from!=NewEdges1[i].from)||(NewEdges0[i].to!=NewEdges1[i].to))
281 break;
282
283 if (i<MAXEDGES)
284 return (0); /* EDGEDATA are not equal */
285 else
286 return (1); /* EDGEDATA are equal */
287 }
288
289 static int FindPathForNeighbours (REFRULE *theRule, SHORT myID, SHORT Status[SONS])
290 {
291 SHORT i,nbID;
292 SHORT nbPATHDEPTH;
293 INT *nbPath;
294
295 for (i=0; i<MAX_SIDES_OF_ELEM; i++)
296 if (((nbID=theRule->sons[myID].nb[i])<FATHER_SIDE_OFFSET) && (Status[nbID]==NOTDONE))
297 {
298 nbPath = &(theRule->sons[nbID].path);
299
300 /* copy myPath to nbPath */
301 *nbPath = theRule->sons[myID].path;
302
303 /* complete nbPath */
304 nbPATHDEPTH = PATHDEPTH(*nbPath);
305 SETNEXTSIDE(*nbPath,nbPATHDEPTH,i);
306 SETPATHDEPTH(*nbPath,++nbPATHDEPTH);
307 Status[nbID] = TOUCHED;
308 }
309
310 /* recursive call for TOUCHED sons */
311 for (nbID=1; nbID<theRule->nsons; nbID++)
312 if (Status[nbID]==TOUCHED)
313 {
314 Status[nbID] = DONE;
315 FindPathForNeighbours (theRule,nbID,Status);
316 }
317
318 return (0);
319 }
320
321 /****************************************************************************/
322 /* */
323 /* AddRuleIfNew */
324 /* called by most of the main functions */
325 /* */
326 /* the additional data fields of the refrule are filled and the */
327 /* rule is stored if not already there */
328 /* */
329 /****************************************************************************/
330
331 static int AddRuleIfNew (REFRULE *theRule)
332 {
333 EDGEDATA theEdgeData,*InnerEdge[2];
334 SONDATA *SONi,*SONj,*theSon;
335 SHORT i,j,nEdges,theEdge,FatherSide,newcorner,corner,son,edge,found,SidePattern;
336 SHORT SIDEi,SIDEj,side,SideBit,Status[SONS];
337
338 assert(nRules<NRULES);
339
340 /* search new inner edges (one or two corners > 3) and fill edges field */
341 nEdges = 0;
342 for (son=0; son<theRule->nsons; son++)
343 for (i=0; i<CORNERS_OF_ELEM; i++)
344 for (j=i+1; j<CORNERS_OF_ELEM; j++)
345 if ((theEdgeData=EdgeData [theRule->sons[son].corners[i]]
346 [theRule->sons[son].corners[j]]).type)
347 {
348 /* (From,To) is a new edge: already stored? */
349 for (theEdge=0; theEdge<nEdges; theEdge++)
350 if ((theRule->edges[theEdge].from==theEdgeData.from)&&(theRule->edges[theEdge].to==theEdgeData.to))
351 break;
352 if (theEdge>=nEdges)
353 theRule->edges[nEdges++] = theEdgeData;
354 }
355
356 /* sort edges for corner IDs (necessary for fast comparison of SidePatterns) */
357 qsort((void *)theRule->edges,nEdges,sizeof(EDGEDATA),CompareEdges);
358
359 /* if this SidePattern is not already in RuleList: store it */
360 for (i=FirstRuleWithEdgePattern; i<nRules; i++)
361 if (NewEdgesAreEqual(theRule->edges,RuleList[i].edges))
362 break;
363
364 if (i<nRules)
365 return (1); /* rule is already in RuleList */
366
367 /* sort corners of sons to make searching for neighbour sides easier */
368 for (i=0; i<theRule->nsons; i++)
369 qsort((void *)theRule->sons[i].corners,4,sizeof(SHORT),CompareCorners);
370
371 /* fill entries of nb field in the SONDATA */
372 for (i=0; i<theRule->nsons; i++)
373 for (SONi=theRule->sons+i, SIDEi=0; SIDEi<MAX_SIDES_OF_ELEM; SIDEi++)
374 if (SONi->nb[SIDEi] == NOTDONE)
375 {
376 /* outer face? */
377 if ((FatherSide=SideWithCorners(SONi->corners[CornerOfSonSide[SIDEi][0]],
378 SONi->corners[CornerOfSonSide[SIDEi][1]],
379 SONi->corners[CornerOfSonSide[SIDEi][2]]))!=NOFATHERSIDE)
380 {
381 SONi->nb[SIDEi] = FatherSide;
382 continue;
383 }
384
385 for (j=i+1; j<theRule->nsons; j++)
386 for (SONj=theRule->sons+j, SIDEj=0; SIDEj<MAX_SIDES_OF_ELEM; SIDEj++)
387 if ( (SONi->corners[CornerOfSonSide[SIDEi][0]]==SONj->corners[CornerOfSonSide[SIDEj][0]])
388 && (SONi->corners[CornerOfSonSide[SIDEi][1]]==SONj->corners[CornerOfSonSide[SIDEj][1]])
389 && (SONi->corners[CornerOfSonSide[SIDEi][2]]==SONj->corners[CornerOfSonSide[SIDEj][2]]))
390 {
391 /* neighbour found */
392 SONi->nb[SIDEi] = j;
393 SONj->nb[SIDEj] = i;
394
395 j=SONS;
396 break;
397 }
398 }
399
400 /* clear the remaining NOTDONEs */
401 for (i=theRule->nsons; i<SONS; i++)
402 for (SONi=theRule->sons+i, SIDEi=0; SIDEi<MAX_SIDES_OF_ELEM; SIDEi++)
403 SONi->nb[SIDEi] = 0;
404
405 /* fill the sonandnode field */
406 for (newcorner=0; newcorner<NEWCORNERS; newcorner++)
407 theRule->sonandnode[newcorner][0] = NOTUSED;
408
409 for (newcorner=CORNERS_OF_ELEM; newcorner<(NEWCORNERS+CORNERS_OF_ELEM); newcorner++)
410 for (son=0; son<SONS; son++)
411 for (theSon=theRule->sons+son, corner=0; corner<CORNERS_OF_ELEM; corner++)
412 if (theSon->corners[corner]==newcorner)
413 {
414 theRule->sonandnode[newcorner-CORNERS_OF_ELEM][0] = son;
415 theRule->sonandnode[newcorner-CORNERS_OF_ELEM][1] = corner;
416
417 son = SONS;
418 break;
419 }
420
421 /* make a consistence check: newcorners in sondata indicate the refined edges */
422 for (newcorner=0; newcorner<EDGES; newcorner++)
423 if (theRule->sonandnode[newcorner][0]==NOTUSED)
424 {
425 assert(theRule->pattern[newcorner]==0);
426 assert((theRule->pat & (1<<newcorner))==0);
427 }
428 else
429 {
430 assert(theRule->pattern[newcorner]==1);
431 assert((theRule->pat & (1<<newcorner))>0);
432 }
433
434 /* find the SidePattern of theRule */
435 SidePattern = 0;
436 for (side=0; side<MAX_SIDES_OF_ELEM; side++)
437 if (TriSectionEdge[theRule->pat & CondensedEdgeOfSide[side]][0] >= 0)
438 {
439 /* here we have a side with a trisection edge */
440 for (found=0, edge=0; edge<MAXEDGES; edge++)
441 if ((theRule->edges[edge].type==2) && (theRule->edges[edge].side==side))
442 {
443 /* we have an inner edge of side (which has a trisection node) */
444 InnerEdge[found++] = theRule->edges+edge;
445 }
446 assert(found==2);
447
448 if (InnerEdge[0]->from==InnerEdge[1]->from)
449 theEdge = InnerEdge[0]->from - CORNERS_OF_ELEM;
450 else if (InnerEdge[0]->from==InnerEdge[1]->to)
451 theEdge = InnerEdge[0]->from - CORNERS_OF_ELEM;
452 else if (InnerEdge[0]->to==InnerEdge[1]->from)
453 theEdge = InnerEdge[0]->to - CORNERS_OF_ELEM;
454 else if (InnerEdge[0]->to==InnerEdge[1]->to)
455 theEdge = InnerEdge[0]->to - CORNERS_OF_ELEM;
456 else
457 assert(0);
458
459 if (TriSectionEdge[theRule->pat & CondensedEdgeOfSide[side]][0] == theEdge)
460 SideBit = 0;
461 else if (TriSectionEdge[theRule->pat & CondensedEdgeOfSide[side]][1] == theEdge)
462 SideBit = 1;
463 else
464 assert(0);
465
466 if (SideBit)
467 SidePattern |= (1<<side);
468
469 if (Output)
470 printf("trisection side is %d, edge %d\n",(int)side,(int)theEdge);
471 }
472
473 /* find path from son_1 to son_i */
474 Status[0] = DONE;
475 for (i=1; i<theRule->nsons; i++)
476 Status[i] = NOTDONE;
477
478 FindPathForNeighbours (theRule,0,Status);
479
480 /* put the new rule into the RuleList */
481 PatternToRefrule[theRule->pat | (SidePattern<<EDGES)] = nRules;
482 RuleList[nRules++] = *theRule;
483
484 /* print data for check purposes */
485 if (Output)
486 {
487 printf("### rule no %3d ###\n",nRules-1);
488 PrintRule(RuleList+(nRules-1),nEdges);
489
490 printf("SidePattern is %#04x\n",(int)SidePattern);
491 printf("### end of rule ###\n");
492 }
493
494 return (0);
495 }
496
497 static int BisectSon (SHORT theSon, SHORT Corner0ID, SHORT Corner1ID, SHORT theEdge, SONDATA *theSD, SHORT nsons)
498 {
499 SHORT i;
500
501 /* copy old son into new son */
502 for (i=0; i<CORNERS_OF_ELEM; i++)
503 theSD[nsons].corners[i] = theSD[theSon].corners[i];
504
505 theSD[theSon].corners[Corner0ID] = MidNodeOfEdge[theEdge];
506 theSD[nsons].corners[Corner1ID] = MidNodeOfEdge[theEdge];
507
508 return (0);
509 }
510
511 static int BisectEdge (SHORT EdgePattern[EDGES], REFRULE theRule)
512 {
513 REFRULE theNewRule;
514 SHORT SonID[2],CornerID0[2],CornerID1[2];
515 SHORT theEdge,nEdges,found,Corner0,Corner1,theSon,i,j;
516
517 for (nEdges=0,theEdge=0; theEdge<EDGES; theEdge++)
518 if (EdgePattern[theEdge])
519 {
520 ++nEdges;
521
522 /* refine son(s) containing theEdge by bisection */
523 if (Output)
524 printf("\trefining edge %d\n",(int)theEdge);
525
526 /* first we need a copy of the original rule */
527 theNewRule = theRule;
528
529 found = 0;
530 Corner0 = CornerOfEdge[theEdge][0];
531 Corner1 = CornerOfEdge[theEdge][1];
532 for (theSon=0; theSon<theNewRule.nsons; theSon++)
533 for (i=0; i<CORNERS_OF_ELEM; i++)
534 if (theNewRule.sons[theSon].corners[i]==Corner0)
535 for (j=0; j<CORNERS_OF_ELEM; j++)
536 if (theNewRule.sons[theSon].corners[j]==Corner1)
537 {
538 SonID[found] = theSon;
539 CornerID0[found] = i;
540 CornerID1[found] = j;
541 ++found;
542 }
543
544 assert(found==1 || found==2);
545
546 for (--found; found>=0; found--)
547 BisectSon(SonID[found],CornerID0[found],CornerID1[found],theEdge,theNewRule.sons,theNewRule.nsons++);
548
549 /* recursively refine the remaining edges: */
550 EdgePattern[theEdge] = 0;
551 BisectEdge(EdgePattern,theNewRule);
552 EdgePattern[theEdge] = 1;
553 }
554
555 if (nEdges==0)
556 AddRuleIfNew(&theRule);
557
558 return (0);
559 }
560
561
562 /****************************************************************************/
563 /****************************************************************************/
564 /* */
565 /* main functions: */
566 /* MakeRule... */
567 /* */
568 /* the Rules refining n edges are generated */
569 /* */
570 /****************************************************************************/
571 /****************************************************************************/
572
573
574 /****************************************************************************/
575 /* */
576 /* MakeRuleByBisection */
577 /* generates rules by recursive bisection of the father */
578 /* */
579 /****************************************************************************/
580
581 static int MakeRuleByBisection (SHORT pattern)
582 {
583 REFRULE NewRule;
584 SONDATA father = {{0,1,2,3},{NOTDONE,NOTDONE,NOTDONE,NOTDONE}};
585 SHORT EdgePattern[EDGES],RefEdgesPerSide[MAX_SIDES_OF_ELEM];
586 SHORT i,nTrapezoid;
587
588 NewRule = EmptyRule;
589 NewRule.nsons = 1;
590 NewRule.sons[0] = father;
591
592 NewRule.pat = pattern;
593
594 /* make extended pattern */
595 for (i=0; i<EDGES; i++)
596 NewRule.pattern[i] = EdgePattern[i] = (((1<<i)&pattern)>0);
597
598 /* find the number of trapezoids for check purposes */
599 for (i=0; i<MAX_SIDES_OF_ELEM; i++)
600 RefEdgesPerSide[i] = 0;
601
602 for (i=0; i<EDGES; i++)
603 if (EdgePattern[i])
604 {
605 ++RefEdgesPerSide[(SideWithEdge[i][0])];
606 ++RefEdgesPerSide[(SideWithEdge[i][1])];
607 }
608
609 for (nTrapezoid=0,i=0; i<MAX_SIDES_OF_ELEM; i++)
610 if (RefEdgesPerSide[i]==2)
611 ++nTrapezoid;
612
613 printf(" make rule by bisection: %d Rules\n",(int)(1<<nTrapezoid));
614
615 /* refine tetrahedron with this pattern */
616 BisectEdge(EdgePattern,NewRule);
617
618 if (Output)
619 printf(" %d trapezoids found ==> %d SidePatterns\n",(int)nTrapezoid,(int)(1<<nTrapezoid));
620
621 nRulesTh += 1<<nTrapezoid;
622
623 return (0);
624 }
625
626 static int MakeRule0 (SHORT pattern)
627 {
628 REFRULE CopyRule =
629 {1,{0,0,0,0,0,0},0,{{NOTUSED,0},{NOTUSED,0},{NOTUSED,0},{NOTUSED,0},{NOTUSED,0},{NOTUSED,0},{NOTUSED,0}},
630
631 {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},
632 {0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},
633 {0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}},
634
635 {{{0,1,2,3},{FATHER_SIDE_OFFSET+0,FATHER_SIDE_OFFSET+1,FATHER_SIDE_OFFSET+2,FATHER_SIDE_OFFSET+3},0},
636 {{0,0,0,0},{0,0,0,0},0},
637 {{0,0,0,0},{0,0,0,0},0},
638 {{0,0,0,0},{0,0,0,0},0},
639 {{0,0,0,0},{0,0,0,0},0},
640 {{0,0,0,0},{0,0,0,0},0},
641 {{0,0,0,0},{0,0,0,0},0},
642 {{0,0,0,0},{0,0,0,0},0},
643 {{0,0,0,0},{0,0,0,0},0},
644 {{0,0,0,0},{0,0,0,0},0},
645 {{0,0,0,0},{0,0,0,0},0},
646 {{0,0,0,0},{0,0,0,0},0}}};
647 REFRULE NoRefRule =
648 {0,{0,0,0,0,0,0},0,{{NOTUSED,0},{NOTUSED,0},{NOTUSED,0},{NOTUSED,0},{NOTUSED,0},{NOTUSED,0},{NOTUSED,0}},
649
650 {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},
651 {0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},
652 {0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}},
653
654 {{{0,0,0,0},{0,0,0,0},0},
655 {{0,0,0,0},{0,0,0,0},0},
656 {{0,0,0,0},{0,0,0,0},0},
657 {{0,0,0,0},{0,0,0,0},0},
658 {{0,0,0,0},{0,0,0,0},0},
659 {{0,0,0,0},{0,0,0,0},0},
660 {{0,0,0,0},{0,0,0,0},0},
661 {{0,0,0,0},{0,0,0,0},0},
662 {{0,0,0,0},{0,0,0,0},0},
663 {{0,0,0,0},{0,0,0,0},0},
664 {{0,0,0,0},{0,0,0,0},0},
665 {{0,0,0,0},{0,0,0,0},0}}};
666
667 assert(pattern==0); /* just to suppress 'not used' warning */
668
669 printf(" rule 0: no ref and copy: 2 Rules\n");
670 nRulesTh += 2;
671
672 PatternToRefrule[NoRefRule.pat] = nRules;
673 RuleList[nRules++] = NoRefRule;
674 RuleList[nRules++] = CopyRule;
675
676 return (0);
677 }
678
679
680 #define IDENTITY NULL
681
682 #define RULE3_CORNER 1
683 #define RULE3CORNER_PROTO 2
684
685 #define RULE3_SIDE 2
686
687 static int MakeRule3 (SHORT pattern)
688 {
689 SONDATA CornerPrototype[RULE3CORNER_PROTO][SONS] =
690 {
691 {{{0,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
692 {{4,6,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
693 {{1,2,3,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
694 {{1,3,4,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
695 {{3,4,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
696 {{1,2,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
697 {{1,4,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
698 {{2,6,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
699 {{2,3,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
700 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
701 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
702 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}},
703
704 {{{0,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
705 {{4,6,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
706 {{1,2,3,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
707 {{1,3,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
708 {{1,4,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
709 {{1,2,4,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
710 {{2,4,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
711 {{2,3,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
712 {{3,6,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
713 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
714 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
715 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}}
716 };
717 SONDATA SidePrototype[SONS] =
718 {{{0,4,2,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
719 {{1,4,2,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
720 {{4,2,7,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
721 {{7,8,2,3},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
722 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
723 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
724 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
725 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
726 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
727 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
728 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
729 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}};
730
731 REFRULE theRule;
732 SHORT *Rot;
733 SHORT theRule3,i,j;
734
735 /* see whether Rule3 is to apply */
736 theRule3 = 0;
737 switch (pattern)
738 {
739 /* the edges to be refined share one node */
740
741 case 0x0D : /* 3 edges (0,2,3) at node 0: 001101 */
742 Rot = IDENTITY; theRule3 = RULE3_CORNER; break;
743
744 case 0x13 : /* 3 edges (0,1,4) at node 1: 010011 */
745 Rot = Ax3Left; theRule3 = RULE3_CORNER; break;
746
747 case 0x26 : /* 3 edges (1,2,5) at node 2: 100110 */
748 Rot = Ax3Right; theRule3 = RULE3_CORNER; break;
749
750 case 0x38 : /* 3 edges (3,4,5) at node 3: 111000 */
751 Rot = Ax1Right; theRule3 = RULE3_CORNER; break;
752
753
754 /* the edges to be refined lie on one side */
755
756 case 0x07 : /* 3 edges (0,1,2) at side 0: 000111 */
757 Rot = Ax1Left; theRule3 = RULE3_SIDE; break;
758
759 case 0x32 : /* 3 edges (1,4,5) at side 1: 110010 */
760 Rot = Ax3Left; theRule3 = RULE3_SIDE; break;
761
762 case 0x2C : /* 3 edges (2,3,5) at side 2: 101100 */
763 Rot = Ax3Right; theRule3 = RULE3_SIDE; break;
764
765 case 0x19 : /* 3 edges (0,3,4) at side 3: 010001 */
766 Rot = IDENTITY; theRule3 = RULE3_SIDE; break;
767 }
768
769 if (!theRule3)
770 return (1);
771
772 /* apply theRule3 */
773
774 /* rotate the Prototype son patterns into the pattern position and copy them into the rule */
775 if (theRule3==RULE3_CORNER)
776 {
777 printf(" rule 3: 3 next to one node: 2 Rules (extra center-node)\n");
778 /* nRulesTh += 2; will be counted by MakeRuleByBisection */
779
780 for (i=0; i<RULE3CORNER_PROTO; i++)
781 {
782 theRule = EmptyRule;
783 theRule.nsons = 9;
784 CopySonsIntoRule(&theRule,CornerPrototype[i]);
785
786 if (Rot!=IDENTITY)
787 RotateCorners(&theRule,Rot);
788
789 theRule.pat = pattern;
790
791 /* fill extended pattern */
792 for (j=0; j<EDGES; j++)
793 theRule.pattern[j] = (((1<<j)&pattern)>0);
794
795 if (AddRuleIfNew(&theRule)==1)
796 printf("MakeRule3: already there\n");
797 }
798 return (1);
799 }
800 else
801 {
802 printf(" rule 3: 3 on one side: 1 Rule\n");
803 nRulesTh += 1;
804
805 theRule = EmptyRule;
806 theRule.nsons = 4;
807
808 CopySonsIntoRule(&theRule,SidePrototype);
809
810 if (Rot!=IDENTITY)
811 RotateCorners(&theRule,Rot);
812
813 theRule.pat = pattern;
814
815 /* fill extended pattern */
816 for (j=0; j<EDGES; j++)
817 theRule.pattern[j] = (((1<<j)&pattern)>0);
818
819 if (AddRuleIfNew(&theRule)==1)
820 printf("MakeRule3: already there\n");
821
822 return (0);
823 }
824 }
825
826 #define RULE4CORNER 1
827 #define RULE4CORNER_PROTO 4
828
829 #define RULE4PLANE 2
830 #define RULE4PLANE_PROTO 2
831
832 static int MakeRule4 (SHORT pattern)
833 {
834 SONDATA CornerPrototype[RULE4CORNER_PROTO][SONS] =
835 {
836 {{{0,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
837 {{5,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
838 {{3,4,7,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
839 {{3,4,1,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
840 {{6,3,7,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
841 {{6,3,2,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
842 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
843 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
844 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
845 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
846 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
847 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}},
848 {{{0,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
849 {{5,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
850 {{3,4,7,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
851 {{3,4,1,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
852 {{2,7,3,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
853 {{2,7,6,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
854 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
855 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
856 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
857 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
858 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
859 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}},
860 {{{0,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
861 {{5,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
862 {{1,7,4,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
863 {{1,7,3,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
864 {{2,7,3,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
865 {{2,7,6,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
866 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
867 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
868 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
869 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
870 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
871 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}},
872 {{{0,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
873 {{5,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
874 {{1,7,4,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
875 {{1,7,3,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
876 {{6,3,7,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
877 {{6,3,2,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
878 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
879 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
880 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
881 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
882 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
883 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}}
884 };
885 SONDATA PlanePrototype[RULE4PLANE_PROTO][SONS] =
886 {
887 {{{1,8,5,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
888 {{1,8,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
889 {{0,6,5,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
890 {{0,6,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
891 {{0,1,5,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
892 {{0,1,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
893 {{2,5,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
894 {{2,5,8,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
895 {{3,7,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
896 {{3,7,8,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
897 {{3,2,8,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
898 {{3,2,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}},
899 {{{1,5,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
900 {{1,5,8,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
901 {{0,7,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
902 {{0,7,8,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
903 {{0,1,6,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
904 {{0,1,8,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
905 {{2,6,5,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
906 {{2,6,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
907 {{3,8,5,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
908 {{3,8,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
909 {{2,3,5,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
910 {{2,3,7,10},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}}
911 };
912 SHORT *Rot0,*Rot1;
913 REFRULE theRule;
914 SHORT i,j,theRule4;
915
916
917 if ((pattern&0x0D)==0x0D)
918 switch (pattern&~0x0D) /* corner 0 */
919 {
920 case (1<<1) : Rot0 = IDENTITY; Rot1 = IDENTITY; theRule4 = RULE4CORNER; break;
921 case (1<<4) : Rot0 = IDENTITY; Rot1 = Ax0Left; theRule4 = RULE4CORNER; break;
922 case (1<<5) : Rot0 = IDENTITY; Rot1 = Ax0Right; theRule4 = RULE4CORNER; break;
923 }
924 else if ((pattern&0x13)==0x13)
925 switch (pattern&~0x13) /* corner 1 */
926 {
927 case (1<<2) : Rot0 = Ax3Left; Rot1 = IDENTITY; theRule4 = RULE4CORNER; break;
928 case (1<<3) : Rot0 = Ax3Left; Rot1 = Ax1Right; theRule4 = RULE4CORNER; break;
929 case (1<<5) : Rot0 = Ax3Left; Rot1 = Ax1Left; theRule4 = RULE4CORNER; break;
930 }
931 else if ((pattern&0x26)==0x26)
932 switch (pattern&~0x26) /* corner 2 */
933 {
934 case (1<<0) : Rot0 = Ax3Right; Rot1 = IDENTITY; theRule4 = RULE4CORNER; break;
935 case (1<<3) : Rot0 = Ax3Right; Rot1 = Ax2Left; theRule4 = RULE4CORNER; break;
936 case (1<<4) : Rot0 = Ax3Right; Rot1 = Ax2Right; theRule4 = RULE4CORNER; break;
937 }
938 else if ((pattern&0x38)==0x38)
939 switch (pattern&~0x38) /* corner 3 */
940 {
941 case (1<<0) : Rot0 = Ax1Right; Rot1 = IDENTITY; theRule4 = RULE4CORNER; break;
942 case (1<<1) : Rot0 = Ax1Right; Rot1 = Ax3Left; theRule4 = RULE4CORNER; break;
943 case (1<<2) : Rot0 = Ax1Right; Rot1 = Ax3Right; theRule4 = RULE4CORNER; break;
944 }
945 else if (pattern==0x1E) /* plane 5,6,7,8 (011110) */
946 {
947 Rot0 = IDENTITY; theRule4 = RULE4PLANE;
948 }
949 else if (pattern==0x35) /* plane 4,6,8,9 (110101) */
950 {
951 Rot0 = Ax3Left; theRule4 = RULE4PLANE;
952 }
953 else if (pattern==0x2B) /* plane 4,5,7,9 (101011) */
954 {
955 Rot0 = Ax3Right; theRule4 = RULE4PLANE;
956 }
957 else
958 assert(0); /* should not happen */
959
960 /* rotate the Prototype son patterns into the pattern position and copy them into the rule */
961 if (theRule4==RULE4CORNER)
962 {
963 printf(" rule 4: 3 next to one node: 4 Rules\n");
964 nRulesTh += 4;
965
966 for (i=0; i<RULE4CORNER_PROTO; i++)
967 {
968 theRule = EmptyRule;
969 theRule.nsons = 6;
970 CopySonsIntoRule(&theRule,CornerPrototype[i]);
971
972 if (Rot0!=IDENTITY)
973 RotateCorners(&theRule,Rot0);
974 if (Rot1!=IDENTITY)
975 RotateCorners(&theRule,Rot1);
976
977 theRule.pat = pattern;
978
979 /* fill extended pattern */
980 for (j=0; j<EDGES; j++)
981 theRule.pattern[j] = (((1<<j)&pattern)>0);
982
983 if (AddRuleIfNew(&theRule)==1)
984 printf("MakeRule4: already there\n");
985 }
986 return (0);
987 }
988 else
989 {
990 printf(" rule 4: 4 on a plane: 2 Rules\n");
991 /* nRulesTh += 2; will be counted by MakeRuleByBisection */
992
993 for (i=0; i<RULE4PLANE_PROTO; i++)
994 {
995 theRule = EmptyRule;
996 theRule.nsons = 12;
997 CopySonsIntoRule(&theRule,PlanePrototype[i]);
998
999 if (Rot0!=IDENTITY)
1000 RotateCorners(&theRule,Rot0);
1001
1002 theRule.pat = pattern;
1003
1004 /* fill extended pattern */
1005 for (j=0; j<EDGES; j++)
1006 theRule.pattern[j] = (((1<<j)&pattern)>0);
1007
1008 if (AddRuleIfNew(&theRule)==1)
1009 printf("MakeRule4: already there\n");
1010 }
1011 return (1);
1012 }
1013 }
1014
1015 #define RULE5_PROTO 4
1016
1017 static int MakeRule5 (SHORT pattern)
1018 {
1019 SONDATA CornerPrototype[RULE5_PROTO][SONS] =
1020 {
1021 {{{3,7,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1022 {{2,9,6,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1023 {{6,7,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1024 {{5,6,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1025 {{0,6,7,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1026 {{0,6,5,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1027 {{0,1,5,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1028 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1029 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1030 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1031 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1032 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}},
1033 {{{3,7,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1034 {{2,9,6,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1035 {{6,7,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1036 {{5,6,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1037 {{1,6,8,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1038 {{1,6,8,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1039 {{0,1,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1040 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1041 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1042 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1043 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1044 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}},
1045 {{{3,7,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1046 {{2,9,6,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1047 {{6,7,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1048 {{5,6,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1049 {{1,6,8,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1050 {{0,1,6,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1051 {{0,7,6,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1052 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1053 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1054 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1055 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1056 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}},
1057 {{{3,7,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1058 {{2,9,6,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1059 {{9,7,5,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1060 {{9,7,5,6},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1061 {{0,7,6,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1062 {{0,1,7,5},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1063 {{1,7,5,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1064 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1065 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1066 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1067 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1068 {{0,0,0,0},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0}}
1069 };
1070 SHORT *Rot0,*Rot1;
1071 REFRULE theRule;
1072 SHORT i,j;
1073
1074 printf(" rule 5: 4 Rules\n");
1075 nRulesTh += 4;
1076
1077 switch (~pattern&PATTERNFILTER)
1078 {
1079 case (1<<0) : Rot0 = IDENTITY; Rot1 = IDENTITY; break; /* all but edge 0 (111110) */
1080 case (1<<1) : Rot0 = Ax3Left; Rot1 = IDENTITY; break; /* all but edge 1 (111101) */
1081 case (1<<2) : Rot0 = Ax3Right; Rot1 = IDENTITY; break; /* all but edge 2 (111011) */
1082 case (1<<3) : Rot0 = Ax2Left; Rot1 = IDENTITY; break; /* all but edge 3 (110111) */
1083 case (1<<4) : Rot0 = Ax2Right; Rot1 = IDENTITY; break; /* all but edge 4 (101111) */
1084 case (1<<5) : Rot0 = Ax2Left; Rot1 = Ax1Right; break; /* all but edge 5 (011111) */
1085
1086 default : assert (0); /* should not happen */
1087 }
1088
1089 /* rotate the Prototype son patterns into the pattern position and copy them into the rule */
1090 for (i=0; i<RULE5_PROTO; i++)
1091 {
1092 theRule = EmptyRule;
1093 theRule.nsons = 7;
1094 CopySonsIntoRule(&theRule,CornerPrototype[i]);
1095
1096 if (Rot0!=IDENTITY)
1097 RotateCorners(&theRule,Rot0);
1098
1099 if (Rot1!=IDENTITY)
1100 RotateCorners(&theRule,Rot1);
1101
1102 theRule.pat = pattern;
1103
1104 /* fill extended pattern */
1105 for (j=0; j<EDGES; j++)
1106 theRule.pattern[j] = (((1<<j)&pattern)>0);
1107
1108 if (AddRuleIfNew(&theRule)==1)
1109 printf("MakeRule5: already there\n");
1110 }
1111
1112 return (0);
1113 }
1114
1115 static int MakeRule6 (SHORT pattern)
1116 {
1117 SONDATA FullRefPrototype[SONS] =
1118 {{{0,4,6,7},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1119 {{4,1,5,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1120 {{6,5,2,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1121 {{7,8,9,3},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1122 {{4,6,7,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1123 {{4,6,5,8},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1124 {{6,5,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1125 {{6,7,8,9},{NOTDONE,NOTDONE,NOTDONE,NOTDONE},0},
1126 {{0,0,0,0},{0,0,0,0},0},
1127 {{0,0,0,0},{0,0,0,0},0},
1128 {{0,0,0,0},{0,0,0,0},0},
1129 {{0,0,0,0},{0,0,0,0},0}};
1130
1131 REFRULE theRule;
1132 SHORT j;
1133
1134 printf(" rule 6: 3 Rules\n");
1135 nRulesTh += 3;
1136
1137 /* inner edge 6-8 */
1138 theRule = EmptyRule;
1139 theRule.nsons = 8;
1140 theRule.pat = pattern;
1141 for (j=0; j<EDGES; j++)
1142 theRule.pattern[j] = (((1<<j)&pattern)>0);
1143 CopySonsIntoRule(&theRule,FullRefPrototype);
1144 AddRuleIfNew(&theRule);
1145
1146 /* inner edge 4-9 */
1147 theRule = EmptyRule;
1148 theRule.nsons = 8;
1149 theRule.pat = pattern;
1150 for (j=0; j<EDGES; j++)
1151 theRule.pattern[j] = (((1<<j)&pattern)>0);
1152 CopySonsIntoRule(&theRule,FullRefPrototype);
1153 RotateCorners(&theRule,Ax1Left);
1154 FirstRuleWithEdgePattern = nRules;
1155 AddRuleIfNew(&theRule);
1156
1157 /* inner edge 5-7 */
1158 theRule = EmptyRule;
1159 theRule.nsons = 8;
1160 theRule.pat = pattern;
1161 for (j=0; j<EDGES; j++)
1162 theRule.pattern[j] = (((1<<j)&pattern)>0);
1163 CopySonsIntoRule(&theRule,FullRefPrototype);
1164 RotateCorners(&theRule,Ax1Right);
1165 FirstRuleWithEdgePattern = nRules;
1166 AddRuleIfNew(&theRule);
1167
1168 /* reset PatternToRefrule[111111] to the first of the FullRefRules */
1169 PatternToRefrule[pattern] = nRules-3;
1170
1171 return (0);
1172 }
1173
1174 int main ([[maybe_unused]] int argc, [[maybe_unused]] char **argv)
1175 {
1176 FILE *stream;
1177 SHORT pattern,nRefEdge,nRE,i;
1178 int MINnRefEdge,MAXnRefEdge,j,err,SaveList;
1179
1180 MINnRefEdge = 0;
1181 MAXnRefEdge = EDGES;
1182
1183 Output = false;
1184 SaveList = 1;
1185
1186 #ifdef TEST_GR
1187 if (argc<3)
1188 {
1189 printf("usage: GenerateRules <min # of refined edges> <max # of refined edges> [-o] [-s]\n");
1190 return (1);
1191 }
1192
1193 /* scan args for options */
1194 if (sscanf(argv[1],"%d",&MINnRefEdge)!=1)
1195 return (1);
1196
1197 if (sscanf(argv[2],"%d",&MAXnRefEdge)!=1)
1198 return (1);
1199
1200 for (i=3; i<argc; i++)
1201 if ((argv[i][0]=='-') && (argv[i][1]=='o'))
1202 {
1203 Output = true;
1204 break;
1205 }
1206
1207 SaveList = 0;
1208 for (i=3; i<argc; i++)
1209 if ((argv[i][0]=='-') && (argv[i][1]=='s'))
1210 {
1211 SaveList = 1;
1212 break;
1213 }
1214
1215 #endif
1216
1217 if ((MINnRefEdge<0) || (MINnRefEdge>EDGES))
1218 {
1219 printf("ERROR: min # of refined edges out of range\n");
1220 return (1);
1221 }
1222
1223 if ((MAXnRefEdge<0) || (MAXnRefEdge>EDGES))
1224 {
1225 printf("ERROR: min # of refined edges out of range\n");
1226 return (1);
1227 }
1228
1229 if (MAXnRefEdge<MINnRefEdge)
1230 {
1231 printf("ERROR: min # of refined edges > max\n");
1232 return (1);
1233 }
1234
1235 /* get storage for RuleList */
1236 RuleList = (REFRULE *) malloc(NRULES*sizeof(REFRULE));
1237 if (RuleList==NULL)
1238 {
1239 printf("ERROR: no storage for RuleList\n");
1240 return (1);
1241 }
1242
1243 /* get storage for PatternToRefrule */
1244 PatternToRefrule = (SHORT *) malloc((1<<(EDGES+MAX_SIDES_OF_ELEM))*sizeof(SHORT));
1245 if (PatternToRefrule==NULL)
1246 {
1247 printf("ERROR: no storage for PatternToRefrule\n");
1248 return (1);
1249 }
1250 for (j=0; j<(1<<(EDGES+MAX_SIDES_OF_ELEM)); j++)
1251 PatternToRefrule[j] = NOTUSED;
1252
1253 nRules = nRulesTh = 0;
1254
1255 for (nRefEdge=MINnRefEdge; nRefEdge<=MAXnRefEdge; nRefEdge++)
1256 {
1257 printf("\n### %d refined edges ###\n",(int)nRefEdge);
1258
1259 for (pattern=0; pattern < (1<<EDGES); pattern++)
1260 {
1261 /* count refined edges */
1262 for (nRE=0, i=0; i<EDGES; i++)
1263 nRE += ((1<<i)&pattern)>0;
1264
1265 /* take only pattern with nRE==nRefEdge */
1266 if (nRE!=nRefEdge) continue;
1267
1268 /* set begin of possibly identical SidePatterns for AddRuleIfNew () */
1269 FirstRuleWithEdgePattern = nRules;
1270
1271 for (i=0; i<EDGES; i++)
1272 printf("%1d",(((1<<i)&pattern)>0));
1273
1274 switch (nRefEdge)
1275 {
1276 case 0 :
1277 MakeRule0(pattern);
1278 break;
1279
1280 case 1 :
1281 MakeRuleByBisection(pattern);
1282 break;
1283
1284 case 2 :
1285 MakeRuleByBisection(pattern);
1286 break;
1287
1288 case 3 :
1289 if (MakeRule3(pattern))
1290 MakeRuleByBisection(pattern);
1291 break;
1292
1293 case 4 :
1294 if (MakeRule4(pattern))
1295 MakeRuleByBisection(pattern);
1296 break;
1297
1298 case 5 :
1299 MakeRule5(pattern);
1300 break;
1301
1302 case 6 :
1303 MakeRule6(pattern);
1304 break;
1305 }
1306 }
1307 }
1308
1309 /* sort edges for sides (necessary for ugrefine) */
1310 for (i=2; i<nRules; i++)
1311 qsort((void *)(RuleList[i].edges),MAXEDGES,sizeof(EDGEDATA),CompareEdgesForSides);
1312
1313 printf("\n#######################\n");
1314 printf("%d rules generated\n%d rules theoretically\n",nRules,nRulesTh);
1315 printf("#######################\n");
1316
1317 if (SaveList)
1318 {
1319 /* open file */
1320 stream = fopen("RefRules.data","w");
1321 if (stream==NULL)
1322 {
1323 printf("ERROR: could not open file 'RefRules.data'\n");
1324 return (1);
1325 }
1326
1327 /* save RuleList and PatternToRefrule to file */
1328 err = fwrite(&nRules,sizeof(int),1,stream); /* no. of RefRules */
1329 if (err!=1) goto exit;
1330 err = fwrite(RuleList,nRules*sizeof(REFRULE),1,stream); /* RefRules */
1331 if (err!=1) goto exit;
1332 j = 1<<(EDGES+MAX_SIDES_OF_ELEM);
1333 err = fwrite(&j,sizeof(int),1,stream); /* no. of patterns */
1334 if (err!=1) goto exit;
1335 err = fwrite(PatternToRefrule,j*sizeof(SHORT),1,stream); /* pattern -> RefRules */
1336 if (err!=1) goto exit;
1337 fclose(stream);
1338
1339 printf("\nRuleList saved to 'RefRules.data'\n");
1340 }
1341
1342 printf("\n######## DONE #########\n");
1343
1344 return (0);
1345
1346 exit:
1347 fclose(stream);
1348 return (1);
1349 }
1350
1351 #endif