VirtualBox

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

Last change on this file since 76690 was 69390, checked in by vboxsync, 7 years ago

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