e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync/* Copyright (c) 2001, Stanford University
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * All rights reserved
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * See the file LICENSE.txt for information on redistributing this software.
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync/*
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * This code contributed by Karl Rasche <rkarl@vr.clemson.edu>
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync#include <math.h>
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync#include "cr_server.h"
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync#include "cr_mem.h"
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync#include "server.h"
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncstatic void
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync__find_intersection(double *s, double *e, double *clp, double *clp_next,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double *intr)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync{
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double v1[2], v2[2];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double A, B, T;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync v1[0] = e[0] - s[0];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync v1[1] = e[1] - s[1];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync v2[0] = clp_next[0] - clp[0];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync v2[1] = clp_next[1] - clp[1];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if ((v1[1]) && (v2[0]))
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync A = (clp[1]-s[1])/v1[1] + (v2[1]/v1[1])*(s[0]-clp[0])/v2[0];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync B = 1.-(v2[1]/v1[1])*(v1[0]/v2[0]);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (B)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync T = A/B;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync T = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr[0] = s[0]+T*v1[0];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr[1] = s[1]+T*v1[1];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (v1[1])
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* clp -> clp_next is vertical */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync T = (clp[0]-s[0])/v1[0];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr[0] = s[0]+T*v1[0];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr[1] = s[1]+T*v1[1];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* s -> e is horizontal */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync T = (s[1]-clp[1])/v2[1];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr[0] = clp[0]+T*v2[0];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr[1] = clp[1]+T*v2[1];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync}
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncstatic void
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __clip_one_side(double *poly, int npnts, double *clp, double *clp_next,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double *norm,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double **new_poly_in, int *new_npnts_in,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double **new_poly_out, int *new_npnts_out)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync{
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync int a, sin, ein;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double *s, *e, intr[2];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *new_poly_in = (double *)crAlloc(2*npnts*2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *new_npnts_in = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *new_poly_out = (double *)crAlloc(2*npnts*2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *new_npnts_out = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync s = poly;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<npnts; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync e = poly+2*((a+1)%npnts);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (((e[0]-clp[0])*norm[0]) + ((e[1]-clp[1])*norm[1]) >= 0)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync ein = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync ein = 1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (((s[0]-clp[0])*norm[0]) + ((s[1]-clp[1])*norm[1]) >= 0)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync sin = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync sin = 1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (sin && ein)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* case 1: */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy(*new_poly_in+2*(*new_npnts_in), e, 2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*new_npnts_in)++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (sin && (!ein))
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* case 2: */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __find_intersection(s, e, clp, clp_next, intr);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy(*new_poly_in+2*(*new_npnts_in), intr, 2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*new_npnts_in)++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy(*new_poly_out+2*(*new_npnts_out), intr, 2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*new_npnts_out)++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy(*new_poly_out+2*(*new_npnts_out), e, 2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*new_npnts_out)++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if ((!sin) && ein)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* case 4: */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __find_intersection(s, e, clp, clp_next, intr);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy((*new_poly_in)+2*(*new_npnts_in), intr, 2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*new_npnts_in)++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy((*new_poly_in)+2*(*new_npnts_in), e, 2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*new_npnts_in)++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy(*new_poly_out+2*(*new_npnts_out), intr, 2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*new_npnts_out)++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy(*new_poly_out+2*(*new_npnts_out), e, 2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*new_npnts_out)++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync s = e;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync}
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync/*
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Sutherland/Hodgman clipping for interior & exterior regions.
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * length_of((*new_vert_out)[a]) == nclip_to_vert
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncstatic void
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync__clip(double *poly, int nvert, double *clip_to_poly, int nclip_to_vert,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double **new_vert_in, int *nnew_vert_in,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double ***new_vert_out, int **nnew_vert_out)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync{
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync int a, side, *nout;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double *clip_normals, *s, *e, *n, *new_vert_src;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double *norm, *clp, *clp_next;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double **out;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *new_vert_out = (double **)crAlloc(nclip_to_vert*sizeof(double *));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *nnew_vert_out = (int *)crAlloc(nclip_to_vert*sizeof(int));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /*
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * First, compute normals for the clip poly. This
ad27e1d5e48ca41245120c331cc88b50464813cevboxsync * breaks for multiple (3+) adjacent colinear vertices
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync clip_normals = (double *)crAlloc(nclip_to_vert*2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<nclip_to_vert; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync s = clip_to_poly+2*a;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync e = clip_to_poly+2*((a+1)%nclip_to_vert);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync n = clip_to_poly+2*((a+2)%nclip_to_vert);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync norm = clip_normals+2*a;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync norm[0] = e[1]-s[1];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync norm[1] = -1*(e[0]-s[0]);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /*
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * if dot(norm, n-e) > 0), the normals are backwards,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * assuming the clip region is convex
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (norm[0]*(n[0]-e[0]) + norm[1]*(n[1]-e[1]) > 0)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync norm[0] *= -1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync norm[1] *= -1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync new_vert_src = (double *)crAlloc(nvert*nclip_to_vert*2*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy(new_vert_src, poly, 2*nvert*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (side=0; side<nclip_to_vert; side++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync clp = clip_to_poly+2*side;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync clp_next = clip_to_poly+2*((side+1)%nclip_to_vert);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync norm = clip_normals+2*side;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *nnew_vert_in = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync nout = (*nnew_vert_out)+side;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync out = (*new_vert_out)+side;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __clip_one_side(new_vert_src, nvert, clp, clp_next, norm,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync new_vert_in, nnew_vert_in,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync out, nout);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemcpy(new_vert_src, (*new_vert_in), 2*(*nnew_vert_in)*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (side != nclip_to_vert-1)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(*new_vert_in);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync nvert = *nnew_vert_in;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync}
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync/*
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Given a bitmap and a group of 'base' polygons [the quads we are testing],
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * perform the unions and differences specified by the map and return
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * the resulting geometry
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncstatic void
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync__execute_combination(CRPoly **base, int n, int *mask, CRPoly **head)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync{
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync int a, b, got_intr;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync int nin, *nout, last;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync double *in, **out;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync CRPoly *intr, *diff, *p;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *head = NULL;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr = (CRPoly *)crAlloc(sizeof(CRPoly));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr->next = NULL;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync got_intr = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* first, intersect the first 2 polys marked */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<n; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (mask[a]) break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (b=a+1; b<n; b++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (mask[b]) break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __clip(base[a]->points, base[a]->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync base[b]->points, base[b]->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync &in, &nin, &out, &nout);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync last = b;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree (nout);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<base[last]->npoints; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (out[a])
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(out[a]);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(out);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (nin)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr->npoints = nin;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr->points = in;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync got_intr = 1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync while (1)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=last+1; a<n; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (mask[a]) break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (a == n) break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (got_intr)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __clip(base[a]->points, base[a]->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr->points, intr->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync &in, &nin, &out, &nout);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree (nout);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (b=0; b<intr->npoints; b++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (out[b])
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(out[b]);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(out);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (nin)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr->npoints = nin;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr->points = in;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync got_intr = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __clip(base[a]->points, base[a]->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync base[last]->points, base[last]->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync &in, &nin, &out, &nout);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree (nout);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (b=0; b<base[last]->npoints; b++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (out[b])
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(out[b]);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(out);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (nin)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr->npoints = nin;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr->points = in;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync got_intr = 1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync last = a;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (a == n) break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
ad27e1d5e48ca41245120c331cc88b50464813cevboxsync /* can't subtract something from nothing! */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (got_intr)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *head = intr;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync else
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync return;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* find the first item to subtract */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<n; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (!mask[a]) break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (a == n) return;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync last = a;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* and subtract it */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync diff = NULL;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __clip(intr->points, intr->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync base[last]->points, base[last]->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync &in, &nin, &out, &nout);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(in);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<base[last]->npoints; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (!nout[a]) continue;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p = (CRPoly *)crAlloc(sizeof(CRPoly));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->npoints = nout[a];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->points = out[a];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->next = diff;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync diff = p;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *head = diff;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync while (1)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr = diff;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync diff = NULL;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=last+1; a<n; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (!mask[a]) break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (a == n) return;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync last = a;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* subtract mask[a] from everything in intr and
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * plop it into diff */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync while (intr)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __clip(intr->points, intr->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync base[last]->points, base[last]->npoints,
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync &in, &nin, &out, &nout);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(in);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<base[last]->npoints; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (!nout[a]) continue;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p = (CRPoly *)crAlloc(sizeof(CRPoly));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->npoints = nout[a];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->points = out[a];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->next = diff;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync diff = p;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync intr = intr->next;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *head = diff;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync}
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync/*
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Here we generate all valid bitmaps to represent union/difference
ad27e1d5e48ca41245120c331cc88b50464813cevboxsync * combinations. Each bitmap is N elements long, where N is the
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * number of polys [quads] that we are testing for overlap
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncstatic void
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync__generate_masks(int n, int ***mask, int *nmasks)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync{
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync int a, b, c, d, e;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync int i, idx, isec_size, add;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *mask = (int **)crAlloc((unsigned int)pow(2, n)*sizeof(int));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<pow(2, n); a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*mask)[a] = (int *)crAlloc(n*sizeof(int));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* compute combinations */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync idx = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (isec_size=1; isec_size<n; isec_size++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<n; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (b=a+1; b<n; b++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crMemset((*mask)[idx], 0, n*sizeof(int));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*mask)[idx][a] = 1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync add = 1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (c=0; c<isec_size; c++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync i = (b+c) % n;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (i == a) add = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*mask)[idx][i] = 1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* dup check */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if ((add) && (idx))
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (d=0; d<idx; d++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync add = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (e=0; e<n; e++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if ((*mask)[idx][e] != (*mask)[d][e])
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync add = 1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (!add)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (add)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync idx++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *nmasks = idx;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync}
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync/*
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * To compute the overlap between a series of quads (This should work
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * for n-gons, but we'll only need quads..), first generate a series of
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * bitmaps that represent which elements to union together, and which
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * to difference. This goes into 'mask'. We then evaluate each bitmap with
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Sutherland-Hodgman clipping to find the interior (union) and exterior
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * (difference) regions.
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * In the map, 1 == union, 0 == difference
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *
ad27e1d5e48ca41245120c331cc88b50464813cevboxsync * (*res)[a] is the head of a poly list for all the polys that convert
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * regions of overlap between a+1 polys ((*res)[0] == NULL)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncvoid
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsynccrComputeOverlapGeom(double *quads, int nquad, CRPoly ***res)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync{
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync int a, b, idx, isec_size, **mask;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync CRPoly *p, *next, **base;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync base = (CRPoly **)crAlloc(nquad*sizeof(CRPoly *));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<nquad; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p = (CRPoly *)crAlloc(sizeof(CRPoly));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->npoints = 4;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->points = (double *)crAlloc(8*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (b=0; b<8; b++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->points[b] = quads[8*a+b];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->next = NULL;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync base[a] = p;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *res = (CRPoly **)crAlloc(nquad*sizeof(CRPoly *));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<nquad; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*res)[a] = NULL;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __generate_masks(nquad, &mask, &idx);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<idx; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync isec_size = 0;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (b=0; b<nquad; b++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (mask[a][b]) isec_size++;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync isec_size--;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __execute_combination(base, nquad, mask[a], &p);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync while (p)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync next = p->next;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->next = (*res)[isec_size];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*res)[isec_size] = p;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p = next;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<nquad; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(base[a]->points);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(base[a]);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(base);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync}
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync/*
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * This is similar to ComputeOverlapGeom above, but for "knockout"
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * edge blending.
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * my_quad_idx is an index of quads indicating which display tile
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * we are computing geometry for. From this, we either generate
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * geometry, or not, such that all geometry can be drawn in black
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * and only one tile will show through the blend as non-black.
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * To add a combination to our set of geom, we must test that:
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * + mask[a][my_quad_idx] is set
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * + mask[a][my_quad_idx] is not the first element set in
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * mask[a].
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * If these conditions hold, execute mask[a] and draw the resulting
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * geometry in black
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync * Unlike ComputeOverlapGeom, res is just a list of polys to draw in black
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsyncvoid
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsynccrComputeKnockoutGeom(double *quads, int nquad, int my_quad_idx, CRPoly **res)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync{
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync int a, b, idx, first, **mask;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync CRPoly *p, *next, **base;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync base = (CRPoly **) crAlloc(nquad*sizeof(CRPoly *));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<nquad; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p = (CRPoly *) crAlloc(sizeof(CRPoly));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->npoints = 4;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->points = (double *) crAlloc(8*sizeof(double));
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (b=0; b<8; b++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->points[b] = quads[8*a+b];
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->next = NULL;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync base[a] = p;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync (*res) = NULL;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __generate_masks(nquad, &mask, &idx);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<idx; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync /* test for above conditions */
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (!mask[a][my_quad_idx]) continue;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync first = -1;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (b=0; b<nquad; b++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (mask[a][b])
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync first = b;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync break;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync if (first == my_quad_idx) continue;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync __execute_combination(base, nquad, mask[a], &p);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync while (p)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync next = p->next;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p->next = *res;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync *res = p;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync p = next;
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync for (a=0; a<nquad; a++)
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync {
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(base[a]->points);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(base[a]);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync }
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync crFree(base);
e0e0c19eefceaf5d4ec40f9466b58a771f50e799vboxsync}