VirtualBox

source: vbox/trunk/src/VBox/HostServices/SharedOpenGL/crserverlib/server_clip.c@ 28197

Last change on this file since 28197 was 15532, checked in by vboxsync, 16 years ago

crOpenGL: export to OSE
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 11.6 KB
Line 
1/* Copyright (c) 2001, Stanford University
2 * All rights reserved
3 *
4 * See the file LICENSE.txt for information on redistributing this software.
5 */
6
7/*
8 * This code contributed by Karl Rasche <[email protected]>
9 */
10
11
12#include <math.h>
13#include "cr_server.h"
14#include "cr_mem.h"
15#include "server.h"
16
17
18static void
19__find_intersection(double *s, double *e, double *clp, double *clp_next,
20 double *intr)
21{
22 double v1[2], v2[2];
23 double A, B, T;
24
25 v1[0] = e[0] - s[0];
26 v1[1] = e[1] - s[1];
27 v2[0] = clp_next[0] - clp[0];
28 v2[1] = clp_next[1] - clp[1];
29
30 if ((v1[1]) && (v2[0]))
31 {
32 A = (clp[1]-s[1])/v1[1] + (v2[1]/v1[1])*(s[0]-clp[0])/v2[0];
33 B = 1.-(v2[1]/v1[1])*(v1[0]/v2[0]);
34 if (B)
35 T = A/B;
36 else
37 {
38 T = 0;
39 }
40
41 intr[0] = s[0]+T*v1[0];
42 intr[1] = s[1]+T*v1[1];
43 }
44 else
45 if (v1[1])
46 {
47 /* clp -> clp_next is vertical */
48 T = (clp[0]-s[0])/v1[0];
49
50 intr[0] = s[0]+T*v1[0];
51 intr[1] = s[1]+T*v1[1];
52 }
53 else
54 {
55 /* s -> e is horizontal */
56 T = (s[1]-clp[1])/v2[1];
57
58 intr[0] = clp[0]+T*v2[0];
59 intr[1] = clp[1]+T*v2[1];
60 }
61
62}
63
64static void
65 __clip_one_side(double *poly, int npnts, double *clp, double *clp_next,
66 double *norm,
67 double **new_poly_in, int *new_npnts_in,
68 double **new_poly_out, int *new_npnts_out)
69{
70 int a, sin, ein;
71 double *s, *e, intr[2];
72
73 *new_poly_in = (double *)crAlloc(2*npnts*2*sizeof(double));
74 *new_npnts_in = 0;
75
76 *new_poly_out = (double *)crAlloc(2*npnts*2*sizeof(double));
77 *new_npnts_out = 0;
78
79 s = poly;
80
81 for (a=0; a<npnts; a++)
82 {
83 e = poly+2*((a+1)%npnts);
84
85 if (((e[0]-clp[0])*norm[0]) + ((e[1]-clp[1])*norm[1]) >= 0)
86 ein = 0;
87 else
88 ein = 1;
89
90 if (((s[0]-clp[0])*norm[0]) + ((s[1]-clp[1])*norm[1]) >= 0)
91 sin = 0;
92 else
93 sin = 1;
94
95 if (sin && ein)
96 {
97 /* case 1: */
98 crMemcpy(*new_poly_in+2*(*new_npnts_in), e, 2*sizeof(double));
99 (*new_npnts_in)++;
100 }
101 else
102 if (sin && (!ein))
103 {
104 /* case 2: */
105
106 __find_intersection(s, e, clp, clp_next, intr);
107
108 crMemcpy(*new_poly_in+2*(*new_npnts_in), intr, 2*sizeof(double));
109 (*new_npnts_in)++;
110
111 crMemcpy(*new_poly_out+2*(*new_npnts_out), intr, 2*sizeof(double));
112 (*new_npnts_out)++;
113 crMemcpy(*new_poly_out+2*(*new_npnts_out), e, 2*sizeof(double));
114 (*new_npnts_out)++;
115 }
116 else
117 if ((!sin) && ein)
118 {
119 /* case 4: */
120 __find_intersection(s, e, clp, clp_next, intr);
121
122 crMemcpy((*new_poly_in)+2*(*new_npnts_in), intr, 2*sizeof(double));
123 (*new_npnts_in)++;
124 crMemcpy((*new_poly_in)+2*(*new_npnts_in), e, 2*sizeof(double));
125 (*new_npnts_in)++;
126
127 crMemcpy(*new_poly_out+2*(*new_npnts_out), intr, 2*sizeof(double));
128 (*new_npnts_out)++;
129 }
130 else
131 {
132 crMemcpy(*new_poly_out+2*(*new_npnts_out), e, 2*sizeof(double));
133 (*new_npnts_out)++;
134 }
135
136 s = e;
137 }
138}
139
140/*
141 * Sutherland/Hodgman clipping for interior & exterior regions.
142 * length_of((*new_vert_out)[a]) == nclip_to_vert
143 */
144static void
145__clip(double *poly, int nvert, double *clip_to_poly, int nclip_to_vert,
146 double **new_vert_in, int *nnew_vert_in,
147 double ***new_vert_out, int **nnew_vert_out)
148{
149 int a, side, *nout;
150 double *clip_normals, *s, *e, *n, *new_vert_src;
151 double *norm, *clp, *clp_next;
152 double **out;
153
154 *new_vert_out = (double **)crAlloc(nclip_to_vert*sizeof(double *));
155 *nnew_vert_out = (int *)crAlloc(nclip_to_vert*sizeof(int));
156
157 /*
158 * First, compute normals for the clip poly. This
159 * breaks for multiple (3+) adjacent colinear verticies
160 */
161 clip_normals = (double *)crAlloc(nclip_to_vert*2*sizeof(double));
162 for (a=0; a<nclip_to_vert; a++)
163 {
164 s = clip_to_poly+2*a;
165 e = clip_to_poly+2*((a+1)%nclip_to_vert);
166 n = clip_to_poly+2*((a+2)%nclip_to_vert);
167
168 norm = clip_normals+2*a;
169 norm[0] = e[1]-s[1];
170 norm[1] = -1*(e[0]-s[0]);
171
172 /*
173 * if dot(norm, n-e) > 0), the normals are backwards,
174 * assuming the clip region is convex
175 */
176 if (norm[0]*(n[0]-e[0]) + norm[1]*(n[1]-e[1]) > 0)
177 {
178 norm[0] *= -1;
179 norm[1] *= -1;
180 }
181 }
182
183 new_vert_src = (double *)crAlloc(nvert*nclip_to_vert*2*sizeof(double));
184 crMemcpy(new_vert_src, poly, 2*nvert*sizeof(double));
185
186 for (side=0; side<nclip_to_vert; side++)
187 {
188 clp = clip_to_poly+2*side;
189 clp_next = clip_to_poly+2*((side+1)%nclip_to_vert);
190 norm = clip_normals+2*side;
191 *nnew_vert_in = 0;
192
193 nout = (*nnew_vert_out)+side;
194 out = (*new_vert_out)+side;
195
196 __clip_one_side(new_vert_src, nvert, clp, clp_next, norm,
197 new_vert_in, nnew_vert_in,
198 out, nout);
199
200 crMemcpy(new_vert_src, (*new_vert_in), 2*(*nnew_vert_in)*sizeof(double));
201 if (side != nclip_to_vert-1)
202 crFree(*new_vert_in);
203 nvert = *nnew_vert_in;
204 }
205}
206
207/*
208 * Given a bitmap and a group of 'base' polygons [the quads we are testing],
209 * perform the unions and differences specified by the map and return
210 * the resulting geometry
211 */
212static void
213__execute_combination(CRPoly **base, int n, int *mask, CRPoly **head)
214{
215 int a, b, got_intr;
216 int nin, *nout, last;
217 double *in, **out;
218 CRPoly *intr, *diff, *p;
219
220 *head = NULL;
221
222 intr = (CRPoly *)crAlloc(sizeof(CRPoly));
223 intr->next = NULL;
224
225 got_intr = 0;
226
227 /* first, intersect the first 2 polys marked */
228 for (a=0; a<n; a++)
229 if (mask[a]) break;
230 for (b=a+1; b<n; b++)
231 if (mask[b]) break;
232
233 __clip(base[a]->points, base[a]->npoints,
234 base[b]->points, base[b]->npoints,
235 &in, &nin, &out, &nout);
236 last = b;
237
238 crFree (nout);
239 for (a=0; a<base[last]->npoints; a++)
240 if (out[a])
241 crFree(out[a]);
242 crFree(out);
243
244
245 if (nin)
246 {
247 intr->npoints = nin;
248 intr->points = in;
249 got_intr = 1;
250 }
251
252 while (1)
253 {
254 for (a=last+1; a<n; a++)
255 if (mask[a]) break;
256
257 if (a == n) break;
258
259 if (got_intr)
260 {
261 __clip(base[a]->points, base[a]->npoints,
262 intr->points, intr->npoints,
263 &in, &nin, &out, &nout);
264
265 crFree (nout);
266 for (b=0; b<intr->npoints; b++)
267 if (out[b])
268 crFree(out[b]);
269 crFree(out);
270
271 if (nin)
272 {
273 intr->npoints = nin;
274 intr->points = in;
275 }
276 else
277 {
278 got_intr = 0;
279 break;
280 }
281 }
282 else
283 {
284 __clip(base[a]->points, base[a]->npoints,
285 base[last]->points, base[last]->npoints,
286 &in, &nin, &out, &nout);
287
288 crFree (nout);
289 for (b=0; b<base[last]->npoints; b++)
290 {
291 if (out[b])
292 crFree(out[b]);
293 }
294 crFree(out);
295
296
297 if (nin)
298 {
299 intr->npoints = nin;
300 intr->points = in;
301 got_intr = 1;
302 }
303 }
304
305 last = a;
306 if (a == n) break;
307 }
308
309 /* can't subract something from nothing! */
310 if (got_intr)
311 *head = intr;
312 else
313 return;
314
315 /* find the first item to subtract */
316 for (a=0; a<n; a++)
317 if (!mask[a]) break;
318
319 if (a == n) return;
320 last = a;
321
322 /* and subtract it */
323 diff = NULL;
324 __clip(intr->points, intr->npoints,
325 base[last]->points, base[last]->npoints,
326 &in, &nin, &out, &nout);
327
328 crFree(in);
329
330 for (a=0; a<base[last]->npoints; a++)
331 {
332 if (!nout[a]) continue;
333
334 p = (CRPoly *)crAlloc(sizeof(CRPoly));
335 p->npoints = nout[a];
336 p->points = out[a];
337 p->next = diff;
338 diff = p;
339 }
340 *head = diff;
341
342 while (1)
343 {
344 intr = diff;
345 diff = NULL;
346
347 for (a=last+1; a<n; a++)
348 if (!mask[a]) break;
349 if (a == n) return;
350
351 last = a;
352
353 /* subtract mask[a] from everything in intr and
354 * plop it into diff */
355 while (intr)
356 {
357 __clip(intr->points, intr->npoints,
358 base[last]->points, base[last]->npoints,
359 &in, &nin, &out, &nout);
360
361 crFree(in);
362
363 for (a=0; a<base[last]->npoints; a++)
364 {
365 if (!nout[a]) continue;
366
367 p = (CRPoly *)crAlloc(sizeof(CRPoly));
368 p->npoints = nout[a];
369 p->points = out[a];
370 p->next = diff;
371 diff = p;
372 }
373
374 intr = intr->next;
375 }
376
377 *head = diff;
378 }
379
380}
381
382/*
383 * Here we generate all valid bitmaps to represent union/difference
384 * conbinations. Each bitmap is N elements long, where N is the
385 * number of polys [quads] that we are testing for overlap
386 */
387static void
388__generate_masks(int n, int ***mask, int *nmasks)
389{
390 int a, b, c, d, e;
391 int i, idx, isec_size, add;
392
393 *mask = (int **)crAlloc((unsigned int)pow(2, n)*sizeof(int));
394 for (a=0; a<pow(2, n); a++)
395 (*mask)[a] = (int *)crAlloc(n*sizeof(int));
396
397 /* compute combinations */
398 idx = 0;
399 for (isec_size=1; isec_size<n; isec_size++)
400 {
401 for (a=0; a<n; a++)
402 {
403 for (b=a+1; b<n; b++)
404 {
405 crMemset((*mask)[idx], 0, n*sizeof(int));
406 (*mask)[idx][a] = 1;
407
408 add = 1;
409 for (c=0; c<isec_size; c++)
410 {
411 i = (b+c) % n;
412 if (i == a) add = 0;
413
414 (*mask)[idx][i] = 1;
415 }
416
417 /* dup check */
418 if ((add) && (idx))
419 {
420 for (d=0; d<idx; d++)
421 {
422 add = 0;
423 for (e=0; e<n; e++)
424 {
425 if ((*mask)[idx][e] != (*mask)[d][e])
426 add = 1;
427 }
428
429 if (!add)
430 break;
431 }
432 }
433
434 if (add)
435 idx++;
436 }
437 }
438 }
439
440 *nmasks = idx;
441}
442
443/*
444 * To compute the overlap between a series of quads (This should work
445 * for n-gons, but we'll only need quads..), first generate a series of
446 * bitmaps that represent which elements to union together, and which
447 * to difference. This goes into 'mask'. We then evaluate each bitmap with
448 * Sutherland-Hodgman clipping to find the interior (union) and exterior
449 * (difference) regions.
450 *
451 * In the map, 1 == union, 0 == difference
452 *
453 * (*res)[a] is the head of a poly list for all the polys that conver
454 * regions of overlap between a+1 polys ((*res)[0] == NULL)
455 */
456void
457crComputeOverlapGeom(double *quads, int nquad, CRPoly ***res)
458{
459 int a, b, idx, isec_size, **mask;
460 CRPoly *p, *next, **base;
461
462 base = (CRPoly **)crAlloc(nquad*sizeof(CRPoly *));
463 for (a=0; a<nquad; a++)
464 {
465 p = (CRPoly *)crAlloc(sizeof(CRPoly));
466 p->npoints = 4;
467 p->points = (double *)crAlloc(8*sizeof(double));
468 for (b=0; b<8; b++)
469 {
470 p->points[b] = quads[8*a+b];
471 }
472 p->next = NULL;
473 base[a] = p;
474 }
475
476 *res = (CRPoly **)crAlloc(nquad*sizeof(CRPoly *));
477 for (a=0; a<nquad; a++)
478 (*res)[a] = NULL;
479
480 __generate_masks(nquad, &mask, &idx);
481
482 for (a=0; a<idx; a++)
483 {
484 isec_size = 0;
485 for (b=0; b<nquad; b++)
486 if (mask[a][b]) isec_size++;
487 isec_size--;
488
489 __execute_combination(base, nquad, mask[a], &p);
490
491 while (p)
492 {
493 next = p->next;
494
495 p->next = (*res)[isec_size];
496 (*res)[isec_size] = p;
497
498 p = next;
499 }
500 }
501
502 for (a=0; a<nquad; a++)
503 {
504 crFree(base[a]->points);
505 crFree(base[a]);
506 }
507 crFree(base);
508
509}
510
511/*
512 * This is similar to ComputeOverlapGeom above, but for "knockout"
513 * edge blending.
514 *
515 * my_quad_idx is an index of quads indicating which display tile
516 * we are computing geometry for. From this, we either generate
517 * geometry, or not, such that all geometry can be drawn in black
518 * and only one tile will show through the blend as non-black.
519 *
520 * To add a combination to our set of geom, we must test that:
521 * + mask[a][my_quad_idx] is set
522 * + mask[a][my_quad_idx] is not the first element set in
523 * mask[a].
524 * If these conditions hold, execute mask[a] and draw the resulting
525 * geometry in black
526 *
527 * Unlike ComputeOverlapGeom, res is just a list of polys to draw in black
528 */
529void
530crComputeKnockoutGeom(double *quads, int nquad, int my_quad_idx, CRPoly **res)
531{
532 int a, b, idx, first, **mask;
533 CRPoly *p, *next, **base;
534
535 base = (CRPoly **) crAlloc(nquad*sizeof(CRPoly *));
536 for (a=0; a<nquad; a++)
537 {
538 p = (CRPoly *) crAlloc(sizeof(CRPoly));
539 p->npoints = 4;
540 p->points = (double *) crAlloc(8*sizeof(double));
541 for (b=0; b<8; b++)
542 {
543 p->points[b] = quads[8*a+b];
544 }
545 p->next = NULL;
546 base[a] = p;
547 }
548
549 (*res) = NULL;
550
551 __generate_masks(nquad, &mask, &idx);
552
553 for (a=0; a<idx; a++)
554 {
555 /* test for above conditions */
556 if (!mask[a][my_quad_idx]) continue;
557
558 first = -1;
559 for (b=0; b<nquad; b++)
560 if (mask[a][b])
561 {
562 first = b;
563 break;
564 }
565 if (first == my_quad_idx) continue;
566
567
568 __execute_combination(base, nquad, mask[a], &p);
569
570 while (p)
571 {
572 next = p->next;
573
574 p->next = *res;
575 *res = p;
576
577 p = next;
578 }
579 }
580
581 for (a=0; a<nquad; a++)
582 {
583 crFree(base[a]->points);
584 crFree(base[a]);
585 }
586 crFree(base);
587}
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette