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