Initial revision
[blender.git] / source / blender / radiosity / intern / source / radnode.c
1 /* ***************************************
2  *
3  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version. The Blender
9  * Foundation also sells licenses for use in proprietary software under
10  * the Blender License.  See http://www.blender.org/BL/ for information
11  * about this.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL/BL DUAL LICENSE BLOCK *****
30
31
32
33     node.c      nov/dec 1992
34                         may 1999
35
36     $Id$
37
38  *************************************** */
39
40 #include <stdio.h>
41 #include <math.h>
42 #include <string.h>
43
44 #include "MEM_guardedalloc.h"
45
46 #include "BLI_blenlib.h"
47 #include "BLI_arithb.h"
48
49 #include "BKE_global.h"
50 #include "BKE_main.h"
51
52 #include "BIF_toolbox.h"
53
54 #include "radio.h"
55
56 /* locals */
57 void *malloc_fast(int size);
58 void *calloc_fast(int size);
59 void free_fast(void *poin, int siz);
60 void deleteTriNodes(RNode *node);
61 /* lower because of local type define */
62 /*  void check_mallocgroup(MallocGroup *mg); */
63
64
65 /* ********** fastmalloc ************** */
66
67 #define MAL_GROUPSIZE   256
68 #define MAL_AVAILABLE   1
69 #define MAL_FULL                2
70
71
72
73
74 ListBase MallocBase= {0, 0};
75 int totfastmem= 0;
76
77 typedef struct MallocGroup {
78         struct MallocGroup *next, *prev;
79         short size, flag;
80         short curfree, tot;
81         char flags[MAL_GROUPSIZE];
82         char *data;
83 } MallocGroup;
84
85 /* one more local */
86 void check_mallocgroup(MallocGroup *mg);
87
88 void check_mallocgroup(MallocGroup *mg)
89 {
90         int a;
91         char *cp;
92         
93         if(mg->tot==MAL_GROUPSIZE) {
94                 mg->flag= MAL_FULL;
95                 return;
96         }
97         
98         cp= mg->flags;
99         
100         if(mg->curfree<MAL_GROUPSIZE-1) {
101                 if(cp[mg->curfree+1]==0) {
102                         mg->curfree++;
103                         return;
104                 }
105         }
106         if(mg->curfree>0) {
107                 if(cp[mg->curfree-1]==0) {
108                         mg->curfree--;
109                         return;
110                 }
111         }
112
113         for(a=0; a<MAL_GROUPSIZE; a++) {
114                 if(cp[a]==0) {
115                         mg->curfree= a;
116                         return;
117                 }
118         }
119         printf("fastmalloc: shouldnt be here\n");
120 }
121
122 void *malloc_fast(int size)
123 {
124         MallocGroup *mg;
125         void *retval;
126         
127         mg= MallocBase.last;
128         while(mg) {
129                 if(mg->size==size) {
130                         if(mg->flag & MAL_AVAILABLE) {
131                                 mg->flags[mg->curfree]= 1;
132                                 mg->tot++;
133                                 retval= mg->data+mg->curfree*mg->size;
134                                 check_mallocgroup(mg);
135                                 return retval;
136                         }
137                 }
138                 mg= mg->prev;
139         }
140
141         /* no free block found */
142         mg= MEM_callocN(sizeof(MallocGroup), "mallocgroup");
143         BLI_addtail(&MallocBase, mg);
144         mg->data= MEM_mallocN(MAL_GROUPSIZE*size, "mallocgroupdata");
145         mg->flag= MAL_AVAILABLE;
146         mg->flags[0]= 1;
147         mg->curfree= 1;
148         mg->size= size;
149         mg->tot= 1;
150         
151         totfastmem+= sizeof(MallocGroup)+MAL_GROUPSIZE*size;
152
153         return mg->data;
154 }
155
156 void *calloc_fast(int size)
157 {
158         void *poin;
159         
160         poin= malloc_fast(size);
161         memset(poin, 0, size);
162         
163         return poin;
164 }
165
166 void free_fast(void *poin, int size)
167 {
168         MallocGroup *mg;
169         long val;
170
171         mg= MallocBase.last;
172         while(mg) {
173                 if(mg->size==size) {
174                         if( ((long)poin) >= ((long)mg->data) ) {
175                                 if( ((long)poin) < ((long)(mg->data+MAL_GROUPSIZE*size)) ) {
176                                         val= ((long)poin) - ((long)mg->data);
177                                         val/= size;
178                                         mg->curfree= val;
179                                         mg->flags[val]= 0;
180                                         mg->flag= MAL_AVAILABLE;
181                                         
182                                         mg->tot--;
183                                         if(mg->tot==0) {
184                                                 BLI_remlink(&MallocBase, mg);
185                                                 MEM_freeN(mg->data);
186                                                 MEM_freeN(mg);
187                                                 totfastmem-= sizeof(MallocGroup)+MAL_GROUPSIZE*size;
188                                         }
189                                         return;
190                                 }
191                         }
192                 }
193                 mg= mg->prev;
194         }
195         printf("fast free: pointer not in memlist %p size %d\n",
196                    poin, size);
197 }
198
199 /* security: only one function in a time can use it */
200 static char *fastmallocstr= 0;
201
202 void free_fastAll()
203 {
204         MallocGroup *mg;
205         
206         mg= MallocBase.first;
207         while(mg) {
208                 BLI_remlink(&MallocBase, mg);
209                 MEM_freeN(mg->data);
210                 MEM_freeN(mg);
211                 mg= MallocBase.first;
212         }
213         totfastmem= 0;
214         fastmallocstr= 0;
215 }
216
217 void start_fastmalloc(char *str)
218 {
219         if(fastmallocstr) {
220                 error("Fastmalloc in use: %s", fastmallocstr);
221                 return;
222         }
223         fastmallocstr= str;
224 }
225
226 /* **************************************** */
227
228 float nodelimit;
229
230 void setnodelimit(float limit)
231 {
232         nodelimit= limit;
233
234 }
235
236 /* ************  GEHEUGENBEHEER ***********  */
237
238 int Ntotvert=0, Ntotnode=0, Ntotpatch=0;
239
240 float *mallocVert()
241 {
242         Ntotvert++;
243         return (float *)malloc_fast(16);
244 }
245
246 float *callocVert()
247 {
248         Ntotvert++;
249         return (float *)calloc_fast(16);
250 }
251
252 void freeVert(float *vert)
253 {
254         free_fast(vert, 16);
255         Ntotvert--;
256 }
257
258 RNode *mallocNode()
259 {
260         Ntotnode++;
261         return (RNode *)malloc_fast(sizeof(RNode));
262 }
263
264 RNode *callocNode()
265 {
266         Ntotnode++;
267         return (RNode *)calloc_fast(sizeof(RNode));
268 }
269
270 void freeNode(RNode *node)
271 {
272         free_fast(node, sizeof(RNode));
273         Ntotnode--;
274 }
275
276 void freeNode_recurs(RNode *node)
277 {
278
279         if(node->down1) {
280                 freeNode_recurs(node->down1);
281                 freeNode_recurs(node->down2);
282         }
283
284         node->down1= node->down2= 0;
285         freeNode(node);
286
287 }
288
289 RPatch *mallocPatch()
290 {
291         Ntotpatch++;
292         return (RPatch *)malloc_fast(sizeof(RPatch));
293 }
294
295 RPatch *callocPatch()
296 {
297         Ntotpatch++;
298         return (RPatch *)calloc_fast(sizeof(RPatch));
299 }
300
301 void freePatch(RPatch *patch)
302 {
303         free_fast(patch, sizeof(RPatch));
304         Ntotpatch--;
305 }
306
307 /* ************  SUBDIVIDE  ***********  */
308
309
310 void replaceAllNode(RNode *neighb, RNode *newn)
311 {
312         /* verandert van alle buren de edgepointers die naar newn->up wijzen in new */
313         int ok= 0;
314         
315         
316         if(neighb==0) return;
317         if(newn->up==0) return;
318         
319         if(neighb->ed1==newn->up) {
320                 neighb->ed1= newn;
321                 ok= 1;
322         }
323         else if(neighb->ed2==newn->up) {
324                 neighb->ed2= newn;
325                 ok= 1;
326         }
327         else if(neighb->ed3==newn->up) {
328                 neighb->ed3= newn;
329                 ok= 1;
330         }
331         else if(neighb->ed4==newn->up) {
332                 neighb->ed4= newn;
333                 ok= 1;
334         }
335         
336         if(ok && neighb->down1) {
337                 replaceAllNode(neighb->down1, newn);
338                 replaceAllNode(neighb->down2, newn);
339         }
340 }
341
342 void replaceAllNodeInv(RNode *neighb, RNode *old)
343 {
344         /* verandert van alle buren de edgepointers die naar old wijzen in old->up */
345         if(neighb==0) return;
346         if(old->up==0) return;
347         
348         if(neighb->ed1==old) {
349                 neighb->ed1= old->up;
350         }
351         else if(neighb->ed2==old) {
352                 neighb->ed2= old->up;
353         }
354         else if(neighb->ed3==old) {
355                 neighb->ed3= old->up;
356         }
357         else if(neighb->ed4==old) {
358                 neighb->ed4= old->up;
359         }
360         
361         if(neighb->down1) {
362                 replaceAllNodeInv(neighb->down1, old);
363                 replaceAllNodeInv(neighb->down2, old);
364         }
365 }
366
367 void replaceAllNodeUp(RNode *neighb, RNode *old)
368 {
369         /* verandert van alle buren de edgepointers die naar old wijzen in old->up */
370         if(neighb==0) return;
371         if(old->up==0) return;
372         neighb= neighb->up;
373         if(neighb==0) return;
374         
375         if(neighb->ed1==old) {
376                 neighb->ed1= old->up;
377         }
378         else if(neighb->ed2==old) {
379                 neighb->ed2= old->up;
380         }
381         else if(neighb->ed3==old) {
382                 neighb->ed3= old->up;
383         }
384         else if(neighb->ed4==old) {
385                 neighb->ed4= old->up;
386         }
387         
388         if(neighb->up) {
389                 replaceAllNodeUp(neighb, old);
390         }
391 }
392
393
394 void replaceTestNode(RNode *neighb, RNode **edpp, RNode *newn, int level, float *vert)
395 {
396         /*      IF neighb->ed wijst naar newn->up
397          *              IF edgelevels gelijk
398                                 IF testvert zit in neighb->ed
399                                         pointers beide kanten op veranderen
400                                 ELSE
401                                         RETURN
402                         ELSE
403                                 IF neighb edgelevel is dieper
404                                         verander neighb pointer
405                 
406          */
407         int ok= 0;
408         
409         if(neighb==0) return;
410         if(newn->up==0) return;
411         
412         if(neighb->ed1==newn->up) {
413                 if(neighb->lev1==level) {
414                         if(vert==neighb->v1 || vert==neighb->v2) {
415                                 *edpp= neighb;
416                                 neighb->ed1= newn;
417                         }
418                         else return;
419                 }
420                 else if(neighb->lev1>level) {
421                         neighb->ed1= newn;
422                 }
423                 ok= 1;
424         }
425         else if(neighb->ed2==newn->up) {
426                 if(neighb->lev2==level) {
427                         if(vert==neighb->v2 || vert==neighb->v3) {
428                                 *edpp= neighb;
429                                 neighb->ed2= newn;
430                         }
431                         else return;
432                 }
433                 else if(neighb->lev2>level) {
434                         neighb->ed2= newn;
435                 }
436                 ok= 1;
437         }
438         else if(neighb->ed3==newn->up) {
439                 if(neighb->lev3==level) {
440                         if(neighb->type==3) {
441                                 if(vert==neighb->v3 || vert==neighb->v1) {
442                                         *edpp= neighb;
443                                         neighb->ed3= newn;
444                                 }
445                                 else return;
446                         }
447                         else {
448                                 if(vert==neighb->v3 || vert==neighb->v4) {
449                                         *edpp= neighb;
450                                         neighb->ed3= newn;
451                                 }
452                                 else return;
453                         }
454                 }
455                 else if(neighb->lev3>level) {
456                         neighb->ed3= newn;
457                 }
458                 ok= 1;
459         }
460         else if(neighb->ed4==newn->up) {
461                 if(neighb->lev4==level) {
462                         if(vert==neighb->v4 || vert==neighb->v1) {
463                                 *edpp= neighb;
464                                 neighb->ed4= newn;
465                         }
466                         else return;
467                 }
468                 else if(neighb->lev4>level) {
469                         neighb->ed4= newn;
470                 }
471                 ok= 1;
472         }
473         
474         if(ok && neighb->down1) {
475                 replaceTestNode(neighb->down1, edpp, newn, level, vert);
476                 replaceTestNode(neighb->down2, edpp, newn, level, vert);
477         }
478         
479 }
480
481 int setvertexpointersNode(RNode *neighb, RNode *node, int level, float **v1, float **v2)
482 {
483         /* vergelijkt edgelevels , als gelijk zet het de vertexpointers */
484         
485         if(neighb==0) return 0;
486         
487         if(neighb->ed1==node) {
488                 if(neighb->lev1==level) {
489                         *v1= neighb->v1;
490                         *v2= neighb->v2;
491                         return 1;
492                 }
493         }
494         else if(neighb->ed2==node) {
495                 if(neighb->lev2==level) {
496                         *v1= neighb->v2;
497                         *v2= neighb->v3;
498                         return 1;
499                 }
500         }
501         else if(neighb->ed3==node) {
502                 if(neighb->lev3==level) {
503                         if(neighb->type==3) {
504                                 *v1= neighb->v3;
505                                 *v2= neighb->v1;
506                         }
507                         else {
508                                 *v1= neighb->v3;
509                                 *v2= neighb->v4;
510                         }
511                         return 1;
512                 }
513         }
514         else if(neighb->ed4==node) {
515                 if(neighb->lev4==level) {
516                         *v1= neighb->v4;
517                         *v2= neighb->v1;
518                         return 1;
519                 }
520         }
521         return 0;
522 }
523
524 float edlen(float *v1, float *v2)
525 {
526         return (v1[0]-v2[0])*(v1[0]-v2[0])+ (v1[1]-v2[1])*(v1[1]-v2[1])+ (v1[2]-v2[2])*(v1[2]-v2[2]);
527 }
528
529
530 void subdivideTriNode(RNode *node, RNode *edge)
531 {
532         RNode *n1, *n2, *up;
533         float fu, fv, fl, *v1, *v2; /*  , AreaT3Dfl(); ... from arithb... */
534         int uvl;
535         
536         if(node->down1 || node->down2) {
537                 /* printf("trinode: subd already done\n"); */
538                 return;
539         }
540         
541         /* bepaal subdivide richting */
542
543         if(edge==0) {
544                 /* areathreshold */
545                 if(node->area<nodelimit) return;
546
547                 fu= edlen(node->v1, node->v2);
548                 fv= edlen(node->v2, node->v3);
549                 fl= edlen(node->v3, node->v1);
550
551                 if(fu>fv && fu>fl) uvl= 1;
552                 else if(fv>fu && fv>fl) uvl= 2;
553                 else uvl= 3;
554         }
555         else {
556                 
557                 if(edge==node->ed1) uvl= 1;
558                 else if(edge==node->ed2) uvl= 2;
559                 else uvl= 3;
560         }
561         
562         /*  moeten naastliggende nodes dieper? Recursief! */
563         n1= 0; 
564         if(uvl==1) {
565                 if(node->ed1 && node->ed1->down1==0) n1= node->ed1;
566         }
567         else if(uvl==2) {
568                 if(node->ed2 && node->ed2->down1==0) n1= node->ed2;
569         }
570         else {
571                 if(node->ed3 && node->ed3->down1==0) n1= node->ed3;
572         }
573         if(n1) {
574                 up= node->up;
575                 while(up) {                                                     /* ook testen op ed4 !!! */
576                         if(n1->ed1==up || n1->ed2==up || n1->ed3==up || n1->ed4==up) {
577                                 subdivideNode(n1, up);
578                                 break;
579                         }
580                         up= up->up;
581                 }
582         }
583         
584         /* Het subdividen */
585         n1= mallocNode();
586         memcpy(n1, node, sizeof(RNode));
587         n2= mallocNode();
588         memcpy(n2, node, sizeof(RNode));
589
590         n1->up= node;
591         n2->up= node;
592         
593         node->down1= n1;
594         node->down2= n2;
595
596         /* subdivide edge 1 */
597         if(uvl==1) {
598         
599                 /* EERSTE NODE  krijgt edge 2 */
600                 n1->ed3= n2;
601                 n1->lev3= 0;
602                 replaceAllNode(n1->ed2, n1);
603                 n1->lev1++;
604                 replaceTestNode(n1->ed1, &(n1->ed1), n1, n1->lev1, n1->v2);
605
606                 /* TWEEDE NODE  krijgt edge 3 */
607                 n2->ed2= n1;
608                 n2->lev2= 0;
609                 replaceAllNode(n2->ed3, n2);
610                 n2->lev1++;
611                 replaceTestNode(n2->ed1, &(n2->ed1), n2, n2->lev1, n2->v1);
612                 
613                 /* NIEUWE VERTEX uit edge 1 */
614                 if( setvertexpointersNode(n1->ed1, n1, n1->lev1, &v1, &v2) ) {  /* nodes hebben gelijke levels */
615                         if(v1== n1->v2) {
616                                 n1->v1= v2;
617                                 n2->v2= v2;
618                         }
619                         else {
620                                 n1->v1= v1;
621                                 n2->v2= v1;
622                         }
623                 }
624                 else {
625                         n1->v1= n2->v2= mallocVert();
626                         n1->v1[0]= 0.5*(node->v1[0]+ node->v2[0]);
627                         n1->v1[1]= 0.5*(node->v1[1]+ node->v2[1]);
628                         n1->v1[2]= 0.5*(node->v1[2]+ node->v2[2]);
629                         n1->v1[3]= node->v1[3]; /* color */
630                 }
631         }
632         else if(uvl==2) {
633         
634                 /* EERSTE NODE  krijgt edge 1 */
635                 n1->ed3= n2;
636                 n1->lev3= 0;
637                 replaceAllNode(n1->ed1, n1);
638                 n1->lev2++;
639                 replaceTestNode(n1->ed2, &(n1->ed2), n1, n1->lev2, n1->v2);
640
641                 /* TWEEDE NODE  krijgt edge 3 */
642                 n2->ed1= n1;
643                 n2->lev1= 0;
644                 replaceAllNode(n2->ed3, n2);
645                 n2->lev2++;
646                 replaceTestNode(n2->ed2, &(n2->ed2), n2, n2->lev2, n2->v3);
647                 
648                 /* NIEUWE VERTEX uit edge 2 */
649                 if( setvertexpointersNode(n1->ed2, n1, n1->lev2, &v1, &v2) ) {  /* nodes hebben gelijke levels */
650                         if(v1== n1->v2) {
651                                 n1->v3= v2;
652                                 n2->v2= v2;
653                         }
654                         else {
655                                 n1->v3= v1;
656                                 n2->v2= v1;
657                         }
658                 }
659                 else {
660                         n1->v3= n2->v2= mallocVert();
661                         n1->v3[0]= 0.5*(node->v2[0]+ node->v3[0]);
662                         n1->v3[1]= 0.5*(node->v2[1]+ node->v3[1]);
663                         n1->v3[2]= 0.5*(node->v2[2]+ node->v3[2]);
664                         n1->v3[3]= node->v1[3]; /* color */
665                 }
666         }
667         else if(uvl==3) {
668         
669                 /* EERSTE NODE  krijgt edge 1 */
670                 n1->ed2= n2;
671                 n1->lev2= 0;
672                 replaceAllNode(n1->ed1, n1);
673                 n1->lev3++;
674                 replaceTestNode(n1->ed3, &(n1->ed3), n1, n1->lev3, n1->v1);
675
676                 /* TWEEDE NODE  krijgt edge 2 */
677                 n2->ed1= n1;
678                 n2->lev1= 0;
679                 replaceAllNode(n2->ed2, n2);
680                 n2->lev3++;
681                 replaceTestNode(n2->ed3, &(n2->ed3), n2, n2->lev3, n2->v3);
682                 
683                 /* NIEUWE VERTEX uit edge 3 */
684                 if( setvertexpointersNode(n1->ed3, n1, n1->lev3, &v1, &v2) ) {  /* nodes hebben gelijke levels */
685                         if(v1== n1->v1) {
686                                 n1->v3= v2;
687                                 n2->v1= v2;
688                         }
689                         else {
690                                 n1->v3= v1;
691                                 n2->v1= v1;
692                         }
693                 }
694                 else {
695                         n1->v3= n2->v1= mallocVert();
696                         n1->v3[0]= 0.5*(node->v1[0]+ node->v3[0]);
697                         n1->v3[1]= 0.5*(node->v1[1]+ node->v3[1]);
698                         n1->v3[2]= 0.5*(node->v1[2]+ node->v3[2]);
699                         n1->v3[3]= node->v3[3]; /* color */
700                 }
701         }
702         n1->area= AreaT3Dfl(n1->v1, n1->v2, n1->v3);
703         n2->area= AreaT3Dfl(n2->v1, n2->v2, n2->v3);
704
705 }
706
707
708 void subdivideNode(RNode *node, RNode *edge)
709 {
710         RNode *n1, *n2, *up;
711         float fu, fv, *v1, *v2;/*, AreaQ3Dfl(); ... from arithb... */
712         int uvl;
713         
714         if(Ntotnode>RG.maxnode) return;
715         
716         if(node->type==3) {
717                 subdivideTriNode(node, edge);
718                 return;
719         }
720
721         if(node->down1 || node->down2) {
722                 /* printf("subdivide Node: already done \n"); */
723                 return;
724         }
725         
726         /* bepaal subdivide richting */
727
728         if(edge==0) {
729                 /* areathreshold */
730                 if(node->area<nodelimit) {
731                         return;
732                 }
733                 fu= fabs(node->v1[0]- node->v2[0])+ fabs(node->v1[1]- node->v2[1]) +fabs(node->v1[2]- node->v2[2]);
734                 fv= fabs(node->v1[0]- node->v4[0])+ fabs(node->v1[1]- node->v4[1]) +fabs(node->v1[2]- node->v4[2]);
735                 if(fu>fv) uvl= 1;
736                 else uvl= 2;
737         }
738         else {
739                 if(edge==node->ed1 || edge==node->ed3) uvl= 1;
740                 else uvl= 2;
741         }
742         
743         /*  moeten naastliggende nodes dieper? Recursief! */
744         n1= n2= 0; 
745         if(uvl==1) {
746                 if(node->ed1 && node->ed1->down1==0) n1= node->ed1;
747                 if(node->ed3 && node->ed3->down1==0) n2= node->ed3;
748         }
749         else {
750                 if(node->ed2 && node->ed2->down1==0) n1= node->ed2;
751                 if(node->ed4 && node->ed4->down1==0) n2= node->ed4;
752         }
753         if(n1) {
754                 up= node->up;
755                 while(up) {
756                         if(n1->ed1==up || n1->ed2==up || n1->ed3==up || n1->ed4==up) {
757                                 /* printf("recurs subd\n"); */
758                                 subdivideNode(n1, up);
759                                 break;
760                         }
761                         up= up->up;
762                 }
763         }
764         if(n2) {
765                 up= node->up;
766                 while(up) {
767                         if(n2->ed1==up || n2->ed2==up || n2->ed3==up || n2->ed4==up) {
768                                 /* printf("recurs subd\n"); */
769                                 subdivideNode(n2, up);
770                                 break;
771                         }
772                         up= up->up;
773                 }
774         }
775
776         /* Het subdividen */
777         n1= mallocNode();
778         memcpy(n1, node, sizeof(RNode));
779         n2= mallocNode();
780         memcpy(n2, node, sizeof(RNode));
781
782         n1->up= node;
783         n2->up= node;
784         
785         node->down1= n1;
786         node->down2= n2;
787
788         /* subdivide edge 1 en 3 */
789         if(uvl==1) {
790                 
791                 /* EERSTE NODE  krijgt edge 2 */
792                 n1->ed4= n2;
793                 n1->lev4= 0;
794                 replaceAllNode(n1->ed2, n1);
795                 n1->lev1++;
796                 n1->lev3++;
797                 replaceTestNode(n1->ed1, &(n1->ed1), n1, n1->lev1, n1->v2);
798                 replaceTestNode(n1->ed3, &(n1->ed3), n1, n1->lev3, n1->v3);
799
800                 /* TWEEDE NODE  krijgt edge 4 */
801                 n2->ed2= n1;
802                 n2->lev2= 0;
803                 replaceAllNode(n2->ed4, n2);
804                 n2->lev1++;
805                 n2->lev3++;
806                 replaceTestNode(n2->ed1, &(n2->ed1), n2, n2->lev1, n2->v1);
807                 replaceTestNode(n2->ed3, &(n2->ed3), n2, n2->lev3, n2->v4);
808                 
809                 /* NIEUWE VERTEX uit edge 1 */
810                 if( setvertexpointersNode(n1->ed1, n1, n1->lev1, &v1, &v2) ) {  /* nodes hebben gelijke levels */
811                         if(v1== n1->v2) {
812                                 n1->v1= v2;
813                                 n2->v2= v2;
814                         }
815                         else {
816                                 n1->v1= v1;
817                                 n2->v2= v1;
818                         }
819                 }
820                 else {
821                         n1->v1= n2->v2= mallocVert();
822                         n1->v1[0]= 0.5*(node->v1[0]+ node->v2[0]);
823                         n1->v1[1]= 0.5*(node->v1[1]+ node->v2[1]);
824                         n1->v1[2]= 0.5*(node->v1[2]+ node->v2[2]);
825                         n1->v1[3]= node->v1[3]; /* color */
826                 }
827                 
828                 /* NIEUWE VERTEX uit edge 3 */
829                 if( setvertexpointersNode(n1->ed3, n1, n1->lev3, &v1, &v2) ) {  /* nodes hebben gelijke levels */
830                         if(v1== n1->v3) {
831                                 n1->v4= v2;
832                                 n2->v3= v2;
833                         }
834                         else {
835                                 n1->v4= v1;
836                                 n2->v3= v1;
837                         }
838                 }
839                 else {
840                         n1->v4= n2->v3= mallocVert();
841                         n1->v4[0]= 0.5*(node->v3[0]+ node->v4[0]);
842                         n1->v4[1]= 0.5*(node->v3[1]+ node->v4[1]);
843                         n1->v4[2]= 0.5*(node->v3[2]+ node->v4[2]);
844                         n1->v4[3]= node->v4[3]; /* color */
845                 }
846         }
847         /* subdivide edge 2 en 4 */
848         else if(uvl==2) {
849                 
850                 /* EERSTE NODE  krijgt edge 1 */
851                 n1->ed3= n2;
852                 n1->lev3= 0;
853                 replaceAllNode(n1->ed1, n1);
854                 n1->lev2++;
855                 n1->lev4++;
856                 replaceTestNode(n1->ed2, &(n1->ed2), n1, n1->lev2, n1->v2);
857                 replaceTestNode(n1->ed4, &(n1->ed4), n1, n1->lev4, n1->v1);
858
859                 /* TWEEDE NODE  krijgt edge 3 */
860                 n2->ed1= n1;
861                 n2->lev1= 0;
862                 replaceAllNode(n2->ed3, n2);
863                 n2->lev2++;
864                 n2->lev4++;
865                 replaceTestNode(n2->ed2, &(n2->ed2), n2, n2->lev2, n2->v3);
866                 replaceTestNode(n2->ed4, &(n2->ed4), n2, n2->lev4, n2->v4);
867
868                 /* NIEUWE VERTEX uit edge 2 */
869                 if( setvertexpointersNode(n1->ed2, n1, n1->lev2, &v1, &v2) ) {  /* nodes hebben gelijke levels */
870                         if(v1== n1->v2) {
871                                 n1->v3= v2;
872                                 n2->v2= v2;
873                         }
874                         else {
875                                 n1->v3= v1;
876                                 n2->v2= v1;
877                         }
878                 }
879                 else {
880                         n1->v3= n2->v2= mallocVert();
881                         n1->v3[0]= 0.5*(node->v2[0]+ node->v3[0]);
882                         n1->v3[1]= 0.5*(node->v2[1]+ node->v3[1]);
883                         n1->v3[2]= 0.5*(node->v2[2]+ node->v3[2]);
884                         n1->v3[3]= node->v3[3]; /* color */
885                 }
886
887                 /* NIEUWE VERTEX uit edge 4 */
888                 if( setvertexpointersNode(n1->ed4, n1, n1->lev4, &v1, &v2) ) {  /* nodes hebben gelijke levels */
889                         if(v1== n1->v1) {
890                                 n1->v4= v2;
891                                 n2->v1= v2;
892                         }
893                         else {
894                                 n1->v4= v1;
895                                 n2->v1= v1;
896                         }
897                 }
898                 else {
899                         n1->v4= n2->v1= mallocVert();
900                         n1->v4[0]= 0.5*(node->v1[0]+ node->v4[0]);
901                         n1->v4[1]= 0.5*(node->v1[1]+ node->v4[1]);
902                         n1->v4[2]= 0.5*(node->v1[2]+ node->v4[2]);
903                         n1->v4[3]= node->v4[3]; /* color */
904                 }
905
906         }
907         
908         n1->area= AreaQ3Dfl(n1->v1, n1->v2, n1->v3, n1->v4);
909         n2->area= AreaQ3Dfl(n2->v1, n2->v2, n2->v3, n2->v4);
910
911 }
912
913 int comparelevel(RNode *node, RNode *nb, int level)
914 {
915         /* recursief afdalen: bij diepste node testen */
916         /* return 1 is gelijk of hoger */
917         
918         if(nb==0) return 1;
919         
920         if(nb->down1) {
921                 return 0;
922                 
923                 /*              HIER ZIT EEN FOUT, MAAR WELKE?  (zonder dit werkt 't ook, maar langzamer)
924                 n1= nb->down1;
925                 if(n1->ed1==node) return comparelevel(node, n1, level);
926                 if(n1->ed2==node) return comparelevel(node, n1, level);
927                 if(n1->ed3==node) return comparelevel(node, n1, level);
928                 if(n1->ed4==node) return comparelevel(node, n1, level);
929                 n1= nb->down2;
930                 if(n1->ed1==node) return comparelevel(node, n1, level);
931                 if(n1->ed2==node) return comparelevel(node, n1, level);
932                 if(n1->ed3==node) return comparelevel(node, n1, level);
933                 if(n1->ed4==node) return comparelevel(node, n1, level);
934                 printf(" dit kan niet ");
935                 return 0;
936                 */
937                 
938         }
939         
940         if(nb->down1==0) {
941                 /* if(nb->ed1==node) return (nb->lev1<=level); */
942                 /* if(nb->ed2==node) return (nb->lev2<=level); */
943                 /* if(nb->ed3==node) return (nb->lev3<=level); */
944                 /* if(nb->ed4==node) return (nb->lev4<=level); */
945                 
946                 return 1;       /* is hogere node */
947         }
948         return 1;
949 }
950
951 void deleteTriNodes(RNode *node)        /* beide kinderen van node */
952 {
953         RNode *n1, *n2;
954         
955         /* als naastliggende nodes dieper zijn: geen delete */
956         /* enkel twee nodes testen, van andere verandert level niet */
957         
958         n1= node->down1;
959         n2= node->down2;
960
961         if(n1==0 || n2==0) return;
962         
963         if(n1->down1 || n2->down1) return;
964         
965         /* aan edges mag geen gesubdivide node zitten */
966
967         if(n1->ed1 && n1->ed1->down1) return;
968         if(n1->ed2 && n1->ed2->down1) return;
969         if(n1->ed3 && n1->ed3->down1) return;
970
971         if(n2->ed1 && n2->ed1->down1) return;
972         if(n2->ed2 && n2->ed2->down1) return;
973         if(n2->ed3 && n2->ed3->down1) return;
974                                 
975         replaceAllNodeInv(n1->ed1, n1);
976         replaceAllNodeInv(n1->ed2, n1);
977         replaceAllNodeInv(n1->ed3, n1);
978
979         replaceAllNodeUp(n1->ed1, n1);
980         replaceAllNodeUp(n1->ed2, n1);
981         replaceAllNodeUp(n1->ed3, n1);
982
983         replaceAllNodeInv(n2->ed1, n2);
984         replaceAllNodeInv(n2->ed2, n2);
985         replaceAllNodeInv(n2->ed3, n2);
986
987         replaceAllNodeUp(n2->ed1, n2);
988         replaceAllNodeUp(n2->ed2, n2);
989         replaceAllNodeUp(n2->ed3, n2);
990
991         n1->down1= (RNode *)12; /* voor debug */
992         n2->down1= (RNode *)12;
993         
994         freeNode(n1);
995         freeNode(n2);
996         node->down1= node->down2= 0;
997         
998 }
999
1000         /* beide kinderen van node */
1001 void deleteNodes(RNode *node)
1002 {
1003         RNode *n1, *n2;
1004         
1005         /* als naastliggende nodes dieper zijn: geen delete */
1006         /* enkel twee nodes testen, van andere verandert level niet */
1007
1008         if(node->type==3) {
1009                 deleteTriNodes(node);
1010                 return;
1011         }
1012         
1013         n1= node->down1;
1014         n2= node->down2;
1015
1016         if(n1==0 || n2==0) return;
1017         
1018         if(n1->down1 || n2->down1) return;
1019         
1020         if(n1->ed3==n2) {
1021
1022                 /* aan edges mag geen gesubdivide node zitten */
1023
1024                 if(n1->ed1 && n1->ed1->down1) return;
1025                 if(n1->ed2 && n1->ed2->down1) return;
1026                 if(n1->ed4 && n1->ed4->down1) return;
1027
1028                 if(n2->ed2 && n2->ed2->down1) return;
1029                 if(n2->ed3 && n2->ed3->down1) return;
1030                 if(n2->ed4 && n2->ed4->down1) return;
1031                                         
1032                 replaceAllNodeInv(n1->ed1, n1);
1033                 replaceAllNodeInv(n1->ed2, n1);
1034                 replaceAllNodeInv(n1->ed4, n1);
1035
1036                 replaceAllNodeUp(n1->ed1, n1);
1037                 replaceAllNodeUp(n1->ed2, n1);
1038                 replaceAllNodeUp(n1->ed4, n1);
1039
1040                 replaceAllNodeInv(n2->ed2, n2);
1041                 replaceAllNodeInv(n2->ed3, n2);
1042                 replaceAllNodeInv(n2->ed4, n2);
1043
1044                 replaceAllNodeUp(n2->ed2, n2);
1045                 replaceAllNodeUp(n2->ed3, n2);
1046                 replaceAllNodeUp(n2->ed4, n2);
1047
1048                 n1->down1= (RNode *)12; /* voor debug */
1049                 n2->down1= (RNode *)12;
1050                 
1051                 freeNode(n1);
1052                 freeNode(n2);
1053                 node->down1= node->down2= 0;
1054                 
1055                 return;
1056         }
1057         else if(n1->ed4==n2) {
1058
1059                 if(n1->ed1 && n1->ed1->down1) return;
1060                 if(n1->ed2 && n1->ed2->down1) return;
1061                 if(n1->ed3 && n1->ed3->down1) return;
1062
1063                 if(n2->ed1 && n2->ed1->down1) return;
1064                 if(n2->ed3 && n2->ed3->down1) return;
1065                 if(n2->ed4 && n2->ed4->down1) return;
1066                                         
1067                 replaceAllNodeInv(n1->ed1, n1);
1068                 replaceAllNodeInv(n1->ed2, n1);
1069                 replaceAllNodeInv(n1->ed3, n1);
1070
1071                 replaceAllNodeUp(n1->ed1, n1);
1072                 replaceAllNodeUp(n1->ed2, n1);
1073                 replaceAllNodeUp(n1->ed3, n1);
1074
1075                 replaceAllNodeInv(n2->ed1, n2);
1076                 replaceAllNodeInv(n2->ed3, n2);
1077                 replaceAllNodeInv(n2->ed4, n2);
1078
1079                 replaceAllNodeUp(n2->ed1, n2);
1080                 replaceAllNodeUp(n2->ed3, n2);
1081                 replaceAllNodeUp(n2->ed4, n2);
1082
1083                 n1->down1= (RNode *)12; /* voor debug */
1084                 n2->down1= (RNode *)12;
1085                 
1086                 freeNode(n1);
1087                 freeNode(n2);
1088                 node->down1= node->down2= 0;
1089                 
1090                 return;
1091         }
1092
1093 }
1094
1095