1 /*
2 Copyright (C) 2003 Cedric Cellier, Dominique Lavault
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */
18 #include <stdio.h>
19 #include <ctype.h>
20 #include <assert.h>
21 #include <string.h>
22 #include "csg.h"
23 #include "memspool.h"
24 #include "geom.h"
25 #include "log.h"
26
27 const char operator[] = { 'X', '/', '|', '&' };
28
substr(char * s,unsigned l)29 static char *substr(char *s, unsigned l)
30 {
31 static char str[NB_MAX_PRIMS_IN_TREE*3];
32 memcpy(str, s, l);
33 str[l] = '\0';
34 return str;
35 }
36
csg_print_tree(csg_node * node)37 void csg_print_tree(csg_node *node)
38 {
39 if (NULL==node) {
40 printf("csg_print_tree: Cannot print NULL tree\n");
41 return;
42 }
43 switch (node->type) {
44 case CSG_STRING:
45 printf("Type String : '%s'\n", substr(node->u.s.string, node->u.s.len));
46 break;
47 case CSG_PRIM:
48 printf("Prim(%s)\n", node->u.prim.m->name);
49 break;
50 case CSG_OP:
51 printf("Operator %c\n", operator[node->u.op.op]);
52 printf("Left :\n");
53 csg_print_tree(node->u.op.left);
54 printf("Right :\n");
55 csg_print_tree(node->u.op.right);
56 break;
57 }
58 return;
59 }
60
csg_node_new(char * string,unsigned len)61 static csg_node *csg_node_new(char *string, unsigned len)
62 {
63 csg_node *node = gltv_memspool_alloc(sizeof(*node));
64 gltv_log_warning(GLTV_LOG_DEBUG, "creation of a node at %p\n", node);
65 if (!node) return NULL;
66 node->type = CSG_STRING;
67 node->u.s.string = string;
68 node->u.s.len = len;
69 return node;
70 }
71
csg_node_del_this_one_only(csg_node * node)72 static void csg_node_del_this_one_only(csg_node *node)
73 {
74 gltv_log_warning(GLTV_LOG_DEBUG, "deletion of a node at %p\n", node);
75 gltv_memspool_unregister(node);
76 }
77
csg_node_del(csg_node * node)78 void csg_node_del(csg_node *node)
79 {
80 if (node->type == CSG_OP) {
81 if (NULL != node->u.op.left) csg_node_del(node->u.op.left);
82 if (NULL != node->u.op.right) csg_node_del(node->u.op.right);
83 }
84 csg_node_del_this_one_only(node);
85 }
86
csg_node_copy(csg_node * orig)87 static csg_node *csg_node_copy(csg_node *orig)
88 {
89 csg_node *copy = csg_node_new(NULL, 0);
90 if (NULL == copy) return NULL;
91 memcpy(copy, orig, sizeof(*orig));
92 if (CSG_OP == copy->type) {
93 copy->u.op.left = csg_node_copy(orig->u.op.left);
94 copy->u.op.right = csg_node_copy(orig->u.op.right);
95 if (NULL==copy->u.op.left || NULL==copy->u.op.right) {
96 csg_node_del(copy);
97 return NULL;
98 }
99 }
100 return copy;
101 }
102
csg_string_parenth_ok(char * str,unsigned len)103 static int csg_string_parenth_ok(char *str, unsigned len)
104 {
105 unsigned i;
106 int p_count;
107 for (i=0, p_count=0; i<len; i++) {
108 if (str[i]=='(') p_count++;
109 else if (str[i]==')') p_count--;
110 if (p_count<0) return 0;
111 }
112 return p_count==0;
113 }
114
csg_parse(csg_node * node,unsigned nb_prims,mesh ** meshes)115 static int csg_parse(csg_node *node, unsigned nb_prims, mesh **meshes)
116 {
117 unsigned len;
118 char *str;
119 int p_count;
120 int c;
121 if (node->type!=CSG_STRING) return 1;
122 str = node->u.s.string;
123 len = node->u.s.len;
124 /* verifs */
125 if (len==0) {
126 gltv_log_warning(GLTV_LOG_OPTIONAL, "Bad string '%s'\n",substr(str,len));
127 return 0;
128 }
129 if (!csg_string_parenth_ok(str, len)) {
130 gltv_log_warning(GLTV_LOG_OPTIONAL, "Bad parenthesis in '%s'\n", substr(str,len));
131 return 0;
132 }
133 /* virer �ventuelement des parenth�ses ext�rieures */
134 if (str[0]=='(' && str[len-1]==')' && csg_string_parenth_ok(str+1,len-2)) {
135 node->u.s.string ++;
136 node->u.s.len -= 2;
137 return csg_parse(node, nb_prims, meshes);
138 }
139 /* chercher le dernier op�rateur ext�rieur - so that operators are all left associative */
140 for (c=len-1, p_count=0; c>=0 && (p_count!=0 || (str[c]!=operator[CSG_MINUS] && str[c]!=operator[CSG_UNION] && str[c]!=operator[CSG_AND])); c--) {
141 if (str[c]=='(') p_count++;
142 else if (str[c]==')') p_count--;
143 }
144 if (c>0) {
145 csg_op op;
146 if (str[c]==operator[CSG_MINUS]) {
147 op = CSG_MINUS;
148 } else if (str[c]==operator[CSG_UNION]) {
149 op = CSG_UNION;
150 } else if (str[c]==operator[CSG_AND]) {
151 op = CSG_AND;
152 }
153 node->type = CSG_OP;
154 node->u.op.op = op;
155 node->u.op.left = csg_node_new(str, c);
156 node->u.op.right = csg_node_new(str+c+1, len-c-1);
157 return csg_parse(node->u.op.left, nb_prims, meshes) && csg_parse(node->u.op.right, nb_prims, meshes);
158 } else {
159 /* pas d'op ext�rieur, on a donc normalement une primitive seule */
160 int i;
161 /* lit le No de la primitive */
162 i = str[0]-'a';
163 if (i<0 || (unsigned)i>=nb_prims) {
164 gltv_log_fatal("csg_parse: Unknown primitive : '%d'", i);
165 }
166 node->type = CSG_PRIM;
167 node->u.prim.m = meshes[i];
168 if (len>1) {
169 gltv_log_fatal("csg_parse: pending chars : '%s'\n", str+1);
170 } else {
171 return 1;
172 }
173 }
174 }
175
csg_normalize_node(csg_node * node)176 static int csg_normalize_node(csg_node *node)
177 {
178 csg_op op, opl, opr;
179 csg_node *x, *y, *z;
180 op = node->u.op.op;
181 opr = CSG_NOOP;
182 if (node->u.op.right->type == CSG_OP) opr = node->u.op.right->u.op.op;
183 /* rule 1 : X-(Y|Z) -> (X-Y)-Z */
184 if (op==CSG_MINUS && opr==CSG_UNION) {
185 x = node->u.op.left;
186 y = node->u.op.right->u.op.left;
187 z = node->u.op.right->u.op.right;
188 node->u.op.left = node->u.op.right;
189 node->u.op.left->u.op.op = CSG_MINUS;
190 node->u.op.left->u.op.left = x;
191 node->u.op.left->u.op.right = y;
192 node->u.op.right = z;
193 return 1;
194 }
195 /* rule 2 : X&(Y|Z) -> (X&Y)|(X&Z) */
196 if (op==CSG_AND && opr==CSG_UNION) {
197 csg_node *new_node = csg_node_new(NULL, 0);
198 if (NULL==new_node) return 2;
199 x = node->u.op.left;
200 y = node->u.op.right->u.op.left;
201 z = node->u.op.right->u.op.right;
202 node->u.op.op = CSG_UNION;
203 node->u.op.left = new_node;
204 node->u.op.right->u.op.op = CSG_AND;
205 if ((node->u.op.right->u.op.left = csg_node_copy(x))==NULL) return 2;
206 new_node->type = CSG_OP;
207 new_node->u.op.op = CSG_AND;
208 new_node->u.op.left = x;
209 new_node->u.op.right = y;
210 return 1;
211 }
212 /* rule 3 : X-(Y&Z) -> (X-Y)|(X-Z) */
213 if (op==CSG_MINUS && opr==CSG_AND) {
214 csg_node *new_node = csg_node_new(NULL, 0);
215 if (NULL==new_node) return 2;
216 x = node->u.op.left;
217 y = node->u.op.right->u.op.left;
218 z = node->u.op.right->u.op.right;
219 node->u.op.op = CSG_UNION;
220 node->u.op.left = new_node;
221 node->u.op.right->u.op.op = CSG_MINUS;
222 if ((node->u.op.right->u.op.left = csg_node_copy(x))==NULL) return 2;
223 new_node->type = CSG_OP;
224 new_node->u.op.op = CSG_MINUS;
225 new_node->u.op.left = x;
226 new_node->u.op.right = y;
227 return 1;
228 }
229 /* rule 4 : X&(Y&Z) -> (X&Y)&Z */
230 if (op==CSG_AND && opr==CSG_AND) {
231 csg_node *tmp = node->u.op.left;
232 x = node->u.op.left;
233 y = node->u.op.right->u.op.left;
234 z = node->u.op.right->u.op.right;
235 node->u.op.left = node->u.op.right;
236 node->u.op.right = tmp;
237 node->u.op.left->u.op.left = x;
238 node->u.op.left->u.op.right = y;
239 node->u.op.right = z;
240 return 1;
241 }
242 /* rule 5 : X-(Y-Z) -> (X-Y)|(X&Z) */
243 if (op==CSG_MINUS && opr==CSG_MINUS) {
244 csg_node *new_node = csg_node_new(NULL, 0);
245 if (NULL==new_node) return 2;
246 x = node->u.op.left;
247 y = node->u.op.right->u.op.left;
248 z = node->u.op.right->u.op.right;
249 node->u.op.op = CSG_UNION;
250 node->u.op.left = new_node;
251 node->u.op.right->u.op.op = CSG_AND;
252 if ((node->u.op.right->u.op.left = csg_node_copy(x))==NULL) return 2;
253 new_node->type = CSG_OP;
254 new_node->u.op.op = CSG_MINUS;
255 new_node->u.op.left = x;
256 new_node->u.op.right = y;
257 return 1;
258 }
259 /* rule 6 : X&(Y-Z) -> (X&Y)-Z */
260 if (op==CSG_AND && opr==CSG_MINUS) {
261 csg_node *tmp = node->u.op.left;
262 x = node->u.op.left;
263 y = node->u.op.right->u.op.left;
264 z = node->u.op.right->u.op.right;
265 node->u.op.left = node->u.op.right;
266 node->u.op.right = tmp;
267 node->u.op.left->u.op.left = x;
268 node->u.op.left->u.op.right = y;
269 node->u.op.right = z;
270 node->u.op.op = CSG_MINUS;
271 node->u.op.left->u.op.op = CSG_AND;
272 return 1;
273 }
274 /* rule 7 : (X-Y)&Z -> (X&Z)-Y */
275 opl = CSG_NOOP;
276 if (node->u.op.left->type == CSG_OP) opl = node->u.op.left->u.op.op;
277 if (op==CSG_AND && opl==CSG_MINUS) {
278 y = node->u.op.left->u.op.right;
279 z = node->u.op.right;
280 node->u.op.op = CSG_MINUS;
281 node->u.op.left->u.op.op = CSG_AND;
282 node->u.op.left->u.op.right = z;
283 node->u.op.right = y;
284 return 1;
285 }
286 /* rule 8 : (X|Y)-Z -> (X-Z)|(Y-Z) */
287 if (op==CSG_MINUS && opl==CSG_UNION) {
288 csg_node *new_node = csg_node_new(NULL, 0);
289 if (NULL==new_node) return 2;
290 x = node->u.op.left->u.op.left;
291 y = node->u.op.left->u.op.right;
292 z = node->u.op.right;
293 node->u.op.op = CSG_UNION;
294 node->u.op.right = new_node;
295 node->u.op.left->u.op.op = CSG_MINUS;
296 if ((node->u.op.left->u.op.right = csg_node_copy(z))==NULL) return 2;
297 new_node->type = CSG_OP;
298 new_node->u.op.op = CSG_MINUS;
299 new_node->u.op.left = y;
300 new_node->u.op.right = z;
301 return 1;
302 }
303 /* rule 9 : (X|Y)&Z -> (X&Z)|(Y&Z) */
304 if (op==CSG_AND && opl==CSG_UNION) {
305 csg_node *new_node = csg_node_new(NULL, 0);
306 if (NULL==new_node) return 2;
307 x = node->u.op.left->u.op.left;
308 y = node->u.op.left->u.op.right;
309 z = node->u.op.right;
310 node->u.op.op = CSG_UNION;
311 node->u.op.right = new_node;
312 node->u.op.left->u.op.op = CSG_AND;
313 if ((node->u.op.left->u.op.right = csg_node_copy(z))==NULL) return 2;
314 new_node->type = CSG_OP;
315 new_node->u.op.op = CSG_AND;
316 new_node->u.op.left = y;
317 new_node->u.op.right = z;
318 return 1;
319 }
320 return 0;
321 }
322
csg_normalize_tree(csg_node * node)323 static int csg_normalize_tree(csg_node *node)
324 {
325 int ret;
326 if (CSG_OP != node->type) return 1;
327 do {
328 while ((ret=csg_normalize_node(node))==1);
329 if (ret==2) return 0;
330 if (!csg_normalize_tree(node->u.op.left)) return 0;
331 } while (!(node->u.op.op==CSG_UNION || (node->u.op.right->type==CSG_PRIM && !(node->u.op.left->type==CSG_OP && node->u.op.left->u.op.op==CSG_UNION))));
332 return csg_normalize_tree(node->u.op.right);
333 }
334
csg_get_b_box(csg_node * node,b_box * dest_bb)335 void csg_get_b_box(csg_node *node, b_box *dest_bb)
336 {
337 /* compute the b_box of a node, even a non-terminal one */
338 if (node==NULL) {
339 dest_bb->vide = 1;
340 return;
341 }
342 if (CSG_PRIM == node->type) {
343 /* cas facile */
344 geom_get_b_box(node, dest_bb);
345 return;
346 } else if (CSG_OP == node->type) {
347 b_box bb_left, bb_right;
348 csg_get_b_box(node->u.op.left, &bb_left);
349 csg_get_b_box(node->u.op.right, &bb_right);
350 switch (node->u.op.op) {
351 case CSG_UNION:
352 geom_b_box_union(dest_bb, &bb_left, &bb_right);
353 break;
354 case CSG_AND:
355 geom_b_box_intersection(dest_bb, &bb_left, &bb_right);
356 break;
357 case CSG_MINUS:
358 memcpy(dest_bb, &bb_left, sizeof(*dest_bb));
359 break;
360 default:
361 gltv_log_fatal("csg_get_b_box: unknown csg_op");
362 break;
363 }
364 return;
365 } else {
366 gltv_log_fatal("csg_get_b_box: call for an invalid csg_node type");
367 }
368 }
369
csg_prune_tree(csg_node * node)370 static csg_node *csg_prune_tree(csg_node *node)
371 {
372 /* toute op�ration - ou & de deux primitives sans point commun est inutile */
373 char recurs = 0;
374 if (CSG_OP != node->type) return node;
375 if (CSG_UNION == node->u.op.op) {
376 recurs = 1;
377 } else {
378 b_box p_left, p_right;
379 csg_get_b_box(node->u.op.left, &p_left);
380 csg_get_b_box(node->u.op.right, &p_right);
381 if (geom_b_box_intersects(&p_left, &p_right)) {
382 recurs = 1;
383 } else {
384 if (CSG_AND == node->u.op.op) {
385 csg_node_del(node);
386 return NULL;
387 } else {
388 /* MINUS : discard right, promote left */
389 csg_node *temp = node->u.op.left;
390 csg_node_del(node->u.op.right);
391 csg_node_del_this_one_only(node);
392 return temp;
393 }
394 }
395 }
396 if (recurs) {
397 node->u.op.left = csg_prune_tree(node->u.op.left);
398 if (NULL==node->u.op.left) {
399 if ((CSG_AND==node->u.op.op) || (CSG_MINUS==node->u.op.op)) {
400 /* discard the whole node */
401 csg_node_del(node);
402 return NULL;
403 } else {
404 /* union : discard this node and promote right */
405 csg_node *temp = node->u.op.right;
406 csg_node_del_this_one_only(node);
407 return csg_prune_tree(temp);
408 }
409 }
410 node->u.op.right = csg_prune_tree(node->u.op.right);
411 if (NULL==node->u.op.right) {
412 if ((CSG_AND==node->u.op.op)) {
413 /* discard the whole node */
414 csg_node_del(node);
415 return NULL;
416 } else {
417 /* union or minus : discard this node and promote left */
418 csg_node *temp = node->u.op.left;
419 csg_node_del_this_one_only(node);
420 return temp;
421 }
422 }
423 }
424 return node;
425 }
426
csg_build_tree(char * string,unsigned nb_prims,mesh ** meshes)427 csg_node *csg_build_tree(char *string, unsigned nb_prims, mesh **meshes)
428 {
429 csg_node *node = csg_node_new(string, strlen(string));
430 if (NULL==node) return NULL;
431 if (!csg_parse(node, nb_prims, meshes)) {
432 csg_node_del(node);
433 return NULL;
434 } else {
435 if (!csg_normalize_tree(node)) {
436 csg_node_del(node);
437 return NULL;
438 } else {
439 node = csg_prune_tree(node);
440 return node;
441 }
442 }
443 }
444
feed_union_of_products(csg_union_of_products * uop,csg_node * node)445 static int feed_union_of_products(csg_union_of_products *uop, csg_node *node)
446 {
447 /* this adds a product to a union of products */
448 gltv_log_warning(GLTV_LOG_DEBUG, "feed node at %p\n", node);
449 if (node->type==CSG_OP && node->u.op.op==CSG_UNION) {
450 int ret1 = feed_union_of_products(uop, node->u.op.left);
451 int ret2 = 0;
452 if (ret1) ret2 = feed_union_of_products(uop, node->u.op.right);
453 return ret1 && ret2;
454 }
455 /* here we are not in a union : we are then at the begening of a product.
456 * Lets go straight to the last left leaf, and write the whole product */
457 /* in normal form, a non-union operator have only simple primitive on right side */
458 {
459 csg_node *node_tmp;
460 unsigned nb = 1;
461 for (node_tmp = node; node_tmp->type!=CSG_PRIM; node_tmp = node_tmp->u.op.left) {
462 if (node_tmp->type!=CSG_OP || node_tmp->u.op.right->type!=CSG_PRIM) return 0;
463 nb ++;
464 }
465 uop->unions[uop->nb_unions].nb_products = nb;
466 nb--;
467 for (node_tmp = node; node_tmp->type!=CSG_PRIM; node_tmp = node_tmp->u.op.left) {
468 uop->unions[uop->nb_unions].products[nb].node = node_tmp->u.op.right;
469 uop->unions[uop->nb_unions].products[nb-1].op_to_next = node_tmp->u.op.op;
470 nb--;
471 }
472 uop->unions[uop->nb_unions].products[0].node = node_tmp;
473 uop->nb_unions++;
474 return 1;
475 }
476 }
477
csg_union_of_products_reset(csg_union_of_products * uop,csg_node * node)478 int csg_union_of_products_reset(csg_union_of_products *uop, csg_node *node)
479 {
480 uop->nb_unions = 0;
481 if (!feed_union_of_products(uop, node)) {
482 return 0;
483 } else {
484 return 1;
485 }
486 }
487
csg_union_of_products_new(csg_node * node)488 csg_union_of_products *csg_union_of_products_new(csg_node *node)
489 {
490 /* given a pruned, normilized csg_tree, compute the flat union of products,
491 * or NULL if error */
492 csg_union_of_products *csg_uop;
493 csg_uop = gltv_memspool_alloc(sizeof(*csg_uop));
494 if (!csg_uop) return NULL;
495 if (!csg_union_of_products_reset(csg_uop, node)) {
496 gltv_memspool_unregister(csg_uop);
497 return NULL;
498 }
499 return csg_uop;
500 }
501
csg_union_of_products_del(csg_union_of_products * uop)502 void csg_union_of_products_del(csg_union_of_products *uop)
503 {
504 gltv_memspool_unregister(uop);
505 }
506
csg_union_of_products_print(csg_union_of_products * uop)507 void csg_union_of_products_print(csg_union_of_products *uop)
508 {
509 unsigned u, p;
510 for (u=0; u<uop->nb_unions; u++) {
511 if (u>0) putchar('|');
512 printf(" ( ");
513 for (p=0; p<uop->unions[u].nb_products; p++) {
514 printf(" Prim(%s) ", uop->unions[u].products[p].node->u.prim.m->name);
515 if (p<uop->unions[u].nb_products-1) putchar(operator[uop->unions[u].products[p].op_to_next]);
516 }
517 printf(" ) ");
518 }
519 putchar('\n');
520 }
521
csg_union_of_partial_products_reset(csg_union_of_partial_products * uopp,csg_union_of_products * uop)522 int csg_union_of_partial_products_reset(csg_union_of_partial_products *uopp, csg_union_of_products *uop)
523 {
524 unsigned uop_u;
525 uopp->nb_unions = 0;
526 for (uop_u=0; uop_u<uop->nb_unions; uop_u++) {
527 /* faire autant d'unions partielles que de primitives dans l'union de produit */
528 unsigned uop_p;
529 for (uop_p=0; uop_p<uop->unions[uop_u].nb_products; uop_p++) {
530 unsigned p, pp;
531 /* chaque union partielle contient autant de primitives que l'union de produit (fo suivre) */
532 uopp->unions[uopp->nb_unions].nb_products = uop->unions[uop_u].nb_products;
533 uopp->unions[uopp->nb_unions].group_id = uop_u;
534 uopp->unions[uopp->nb_unions].products[0].node = uop->unions[uop_u].products[uop_p].node;
535 if (uop_p==0 || uop->unions[uop_u].products[uop_p-1].op_to_next==CSG_AND)
536 uopp->unions[uopp->nb_unions].products[0].frontal = 1; /* si uop_p==0 ou si op�rateur pr�c�dent=and */
537 else
538 uopp->unions[uopp->nb_unions].products[0].frontal = 0;
539 for (p=0, pp=1; p<uop->unions[uop_u].nb_products; p++) {
540 if (p==uop_p) continue;
541 uopp->unions[uopp->nb_unions].products[pp].node = uop->unions[uop_u].products[p].node;
542 if (p==0 || uop->unions[uop_u].products[p-1].op_to_next==CSG_AND)
543 uopp->unions[uopp->nb_unions].products[pp].frontal = 1; /* si uop_p==0 ou si op�rateur pr�c�dent=and */
544 else
545 uopp->unions[uopp->nb_unions].products[pp].frontal = 0;
546 pp++;
547 }
548 uopp->nb_unions++;
549 }
550 }
551 return 1;
552 }
553
csg_union_of_partial_products_new(csg_union_of_products * uop)554 csg_union_of_partial_products *csg_union_of_partial_products_new(csg_union_of_products *uop)
555 {
556 csg_union_of_partial_products *csg_uopp;
557 csg_uopp = gltv_memspool_alloc(sizeof(*csg_uopp));
558 if (!csg_uopp) return NULL;
559 if (!csg_union_of_partial_products_reset(csg_uopp, uop)) {
560 gltv_memspool_unregister(csg_uopp);
561 return NULL;
562 } else {
563 return csg_uopp;
564 }
565 }
566
csg_union_of_partial_products_del(csg_union_of_partial_products * uopp)567 void csg_union_of_partial_products_del(csg_union_of_partial_products *uopp)
568 {
569 gltv_memspool_unregister(uopp);
570 }
571
csg_union_of_partial_products_resize(csg_union_of_partial_products * uopp)572 void csg_union_of_partial_products_resize(csg_union_of_partial_products *uopp)
573 {
574 /* now, compute max2ds, max 2dbox amongst targets partials for each group */
575 unsigned u=0, g=0;
576 while (u<uopp->nb_unions) { /* loop on g, group id */
577 b_box_2d box2d;
578 /* compute boxes of the prims used in the group */
579 if (u==0 || g!=uopp->unions[u-1].group_id) {
580 unsigned p;
581 for (p=0; p<uopp->unions[u].nb_products; p++) {
582 geom_get_b_box(uopp->unions[u].products[p].node, &uopp->unions[u].products[p].node->u.prim.box3d);
583 geom_get_b_box_2d(&uopp->unions[u].products[p].node->u.prim.box3d, &uopp->unions[u].products[p].node->u.prim.box2d);
584 }
585 }
586 memcpy(&box2d, &uopp->unions[u].products[0].node->u.prim.box2d, sizeof(box2d));
587 u++;
588 while (u<uopp->nb_unions && uopp->unions[u].group_id==g) {
589 if (box2d.vide) {
590 memcpy(&box2d, &uopp->unions[u].products[0].node->u.prim.box2d, sizeof(box2d));
591 u++;
592 continue;
593 }
594 if (uopp->unions[u].products[0].node->u.prim.box2d.xmin<box2d.xmin) box2d.xmin=uopp->unions[u].products[0].node->u.prim.box2d.xmin;
595 if (uopp->unions[u].products[0].node->u.prim.box2d.ymin<box2d.ymin) box2d.ymin=uopp->unions[u].products[0].node->u.prim.box2d.ymin;
596 if (uopp->unions[u].products[0].node->u.prim.box2d.xmax>box2d.xmax) box2d.xmax=uopp->unions[u].products[0].node->u.prim.box2d.xmax;
597 if (uopp->unions[u].products[0].node->u.prim.box2d.ymax>box2d.ymax) box2d.ymax=uopp->unions[u].products[0].node->u.prim.box2d.ymax;
598 u++;
599 }
600 memcpy(&uopp->max2d_group[g], &box2d, sizeof(box2d));
601 if (u<uopp->nb_unions) g=uopp->unions[u].group_id;
602 }
603 }
604
csg_union_of_partial_products_print(csg_union_of_partial_products * uopp)605 void csg_union_of_partial_products_print(csg_union_of_partial_products *uopp)
606 {
607 unsigned u, p;
608 for (u=0; u<uopp->nb_unions; u++) {
609 if (u>0) putchar('|');
610 printf(" ( ");
611 for (p=0; p<uopp->unions[u].nb_products; p++) {
612 if (!uopp->unions[u].products[p].frontal) putchar('!');
613 printf(" Prim(%s) ", uopp->unions[u].products[p].node->u.prim.m->name);
614 if (p<uopp->unions[u].nb_products-1) putchar('&');
615 }
616 printf(" ) ");
617 }
618 putchar('\n');
619 }
620
uopp_identiqual(csg_union_of_partial_products * uopp_1,int g1,csg_union_of_partial_products * uopp_2,int g2)621 static int uopp_identiqual(csg_union_of_partial_products *uopp_1, int g1, csg_union_of_partial_products *uopp_2, int g2)
622 {
623 /* tells wether two uopps are the same */
624 /* 2 uopps of a given group are the same if every subgroup are present in both.
625 * (at least, i think so :-p) */
626 unsigned gg1, gg2;
627 if (uopp_1->unions[g1].nb_products != uopp_2->unions[g2].nb_products) return 0;
628 gg1 = g1;
629 while (gg1<uopp_1->nb_unions && uopp_1->unions[gg1].group_id==uopp_1->unions[g1].group_id) {
630 char ident = 0;
631 gltv_log_warning(GLTV_LOG_DEBUG, "\tfor subgroup %u", gg1);
632 gg2 = g2;
633 while (gg2<uopp_2->nb_unions && uopp_2->unions[gg2].group_id==uopp_2->unions[g2].group_id) {
634 unsigned p,pp;
635 assert(uopp_1->unions[gg1].nb_products==uopp_2->unions[gg2].nb_products && uopp_1->unions[gg1].nb_products==uopp_1->unions[g1].nb_products); /* every uopp of the same group should have the same nb_products ! */
636 gltv_log_warning(GLTV_LOG_DEBUG, "\t...watch if subgroup of uopp2 %u matche", gg2);
637 /* two unions of pp are equals if : same target and same "fromtality" of target,
638 * and same trimming prims/frontality, in any order */
639 p = 0;
640 if (uopp_1->unions[gg1].products[p].node->u.prim.m->prim==uopp_2->unions[gg2].products[p].node->u.prim.m->prim && uopp_1->unions[gg1].products[p].frontal==uopp_2->unions[gg2].products[p].frontal) {
641 for (p=1; p<uopp_1->unions[g1].nb_products; p++) {
642 for (pp=1; pp<uopp_1->unions[g1].nb_products; pp++) {
643 gltv_log_warning(GLTV_LOG_DEBUG, "\t\tcomparing %s with %s and %d with %d",
644 uopp_1->unions[gg1].products[p].node->u.prim.m->prim->name,uopp_2->unions[gg2].products[pp].node->u.prim.m->prim->name,
645 (int)uopp_1->unions[gg1].products[p].frontal,(int)uopp_2->unions[gg2].products[pp].frontal);
646 if (uopp_1->unions[gg1].products[p].node->u.prim.m->prim!=uopp_2->unions[gg2].products[pp].node->u.prim.m->prim || uopp_1->unions[gg1].products[p].frontal!=uopp_2->unions[gg2].products[pp].frontal)
647 break;
648 }
649 if (pp==uopp_1->unions[g1].nb_products) {
650 gltv_log_warning(GLTV_LOG_DEBUG, "\t\tfound");
651 p = pp;
652 break;
653 }
654 }
655 } else {
656 gltv_log_warning(GLTV_LOG_DEBUG, "\t\tno same targets");
657 }
658 if (p==uopp_1->unions[g1].nb_products) {
659 ident = 1;
660 gltv_log_warning(GLTV_LOG_DEBUG, "\tyes");
661 break;
662 } else gltv_log_warning(GLTV_LOG_DEBUG, "\tno - mismatch at %u",p);
663 gg2++;
664 }
665 if (!ident) return 0;
666 gg1++;
667 }
668 return 1;
669 }
670
csg_is_equivalent(csg_union_of_partial_products * uopp_1,csg_union_of_partial_products * uopp_2)671 int csg_is_equivalent(csg_union_of_partial_products *uopp_1, csg_union_of_partial_products *uopp_2)
672 {
673 /* 2 csg are identiqual iff all groups are identiqual (ordering of groups is irrelevant) */
674 unsigned g1, g2;
675 if (uopp_1->nb_unions != uopp_2->nb_unions) return 0;
676 g1 = 0;
677 while (g1<uopp_1->nb_unions) {
678 char ident = 0;
679 gltv_log_warning(GLTV_LOG_DEBUG, "for group beginning at %u",g1);
680 g2 = 0;
681 while (g2<uopp_2->nb_unions) {
682 gltv_log_warning(GLTV_LOG_DEBUG, "...watch if group in uopp2 beginning at %u matche", g2);
683 if (uopp_identiqual(uopp_1, g1, uopp_2, g2)) {
684 ident = 1;
685 gltv_log_warning(GLTV_LOG_DEBUG, "yes");
686 break;
687 } else gltv_log_warning(GLTV_LOG_DEBUG, "no");
688 /* look for next group in uopp_2 */
689 do { g2++; } while (g2<uopp_2->nb_unions && uopp_2->unions[g2].group_id==uopp_2->unions[g2-1].group_id);
690 }
691 if (!ident) return 0;
692 /* look for next group in uopp_1 */
693 do { g1++; } while (g1<uopp_1->nb_unions && uopp_1->unions[g1].group_id==uopp_1->unions[g1-1].group_id);
694 }
695 return 1;
696 }
697
698