utils.cpp

Linux/windows 环境下跨平台开发程序

					//mp is the closest point
					AddToPolygon(cp, pts, &mp);
					return false;
					}
				}
			vis = IsInPolygon(&tr, tp, ntp) || IsCloseToPL(tr, tp, ntp);
			if(bPen && !vis) {
				AddToPolygon(cp, pts, &tr);
				return false;				//now leaving the polygon
				}
			if (tr.y == p2->y) return true;	//still inside
			if (d >= 0) {tr.x += sx;		d -= ay;}
			bPen = vis;		tr.y += sy;		d += ax;
			}
		}
}

//find sepment which is closest to point
int FindClosestSeg(POINT3D *pg, int npg, int x, int y, int start)
{
	int i, i1, j, tmp, idx = -2, dx, dy, d, dist = 10000;
	POINT p1, p2;

	if(start < 1) start = 1;
	for(j = start + npg, i1 = start; i1 < j; i1++) {
		i = ((i1-1)%npg)+1;
		if( i == npg) {
			p1.x = pg[i-1].x;	p1.y = pg[i-1].y;
			p2.x = pg[0].x;		p2.y = pg[0].y;
			}
		else {
			p1.x = pg[i-1].x;	p1.y = pg[i-1].y;
			p2.x = pg[i].x;		p2.y = pg[i].y;
			}
		if(p1.x != p2.x || p1.y != p2.y) {
			d = dist;
			if(abs(dx = (p2.x - p1.x)) < abs(dy = (p2.y - p1.y))) {	//y dominant
				if(dy && ((p1.y >= y && p2.y < y) || (p2.y > y && p1.y <= y))) {
					tmp = (p1.x + ((y - p1.y) * dx)/dy);	d = abs(x-tmp);
					}
				}
			else {								// x dominant
				if(dx && ((p1.x >= x && p2.x < x) || (p2.x > x && p1.x <= x))) {
					tmp = (p1.y + ((x - p1.x) * dy)/dx);	d = abs(y-tmp);
					}
				}
			if(d < dist) {
				dist = d;	idx = i;
				}
			}
		if(dist < 3) break;
		}
	return idx;
}

//finish a partially visible 3D polygon by its shadow of the above
//   3D polygon
bool AddShadowPolygon(POINT3D *pnt, POINT3D *ep, int cidx) {
	int us, ls, i, j, k, x1, x2, y1, y2, z1, z2, idx_clppg_line;
	long cpg1 = 0, d, d1, d2, ntp=0, ntp1=0, ntp2=0;
	POINT *pg1 = 0L, np, *tp=0L, *tp1, *tp2, lim;	
	POINT3D nep;
	bool bRet = false;

	d = ((d1 = (ep->x - pnt->x))*d1);
	d += ((d1 = (ep->y - pnt->y))*d1);
	if(d < 4) {			//propably too close
		if(d) ppg_par->Command(CMD_ADDTOLINE, ep, 0L);
		return true;	//connect
		}
	lim.x = ep->x;		lim.y = ep->y;
	idx_clppg_line = FindClosestSeg(clp_pg, nclp_pg, pnt->x, pnt->y, cidx);
	//create track from hiding polygon
	//the ppoint 'pnt' is expected to be on the line
	//   clp_pg[idx_clpgg_line] and clp_pg[idx_clpgg_line - 1]
	if(!(pg1 = (POINT*)calloc(nclp_pg +4, sizeof(POINT))))return true;
	np.x = pnt->x;	np.y = pnt->y;	AddToPolygon(&cpg1, pg1, &np);
	j = idx_clppg_line + nclp_pg;
	for(i = idx_clppg_line; i < j; i++) {
		np.x = clp_pg[k = (i%nclp_pg)].x;		np.y = clp_pg[k].y;
		AddToPolygon(&cpg1, pg1, &np);
		}
	//close polygon
	np.x = pnt->x;	np.y = pnt->y;	AddToPolygon(&cpg1, pg1, &np);
	//calculate two possible solutions
	tp1 = (POINT*)calloc(nclp_pg+4, sizeof(POINT));
	tp2 = (POINT*)calloc(nclp_pg+4, sizeof(POINT));
	if(!tp1 || !tp2) {			//memory allocation error
		free(pg1);	free(ppg_mask);	return false;
		}
	ShadowPolygon(&pg1[0], &pg1[1], ppg_mask, (int)ppg_nmask, tp1, &ntp1, &lim);
	if(ntp1 == 1){				//more than one segment
		for(i = 2; i < cpg1; i++) {
			if(!ShadowPolygon(&pg1[i-1], &pg1[i], ppg_mask, (int)ppg_nmask, tp1, &ntp1, &lim))
				break;
			}
		}
	if(i == cpg1) {				//last segment required
		ShadowPolygon(&pg1[i-1], &pg1[0], ppg_mask, (int)ppg_nmask, tp1, &ntp1, &lim);
		}
	ShadowPolygon(&pg1[0], &pg1[cpg1-1], ppg_mask, (int)ppg_nmask, tp2, &ntp2, &lim);
	if(ntp2 == 1){				//more than one segment
		for(i = cpg1-1; i > 1; i--) {
			if(!ShadowPolygon(&pg1[i], &pg1[i-1], ppg_mask, (int)ppg_nmask, tp2, &ntp2, &lim))
				break;
			}
		}
	//find better solution
	d1 = ((d = (ep->x - tp1[ntp1-1].x))*d);		d1 += ((d = (ep->y - tp1[ntp1-1].y))*d);
	d2 = ((d = (ep->x - tp2[ntp2-1].x))*d);		d2 += ((d = (ep->y - tp2[ntp2-1].y))*d);
	if(d1 < d2 && d1 < 5) {			//use solution 1
		tp = tp1;	ntp = ntp1;
		}
	else if(d2 < d1 && d2 < 5) {	//use solution 2
		tp = tp2;	ntp = ntp2;
		}
	else if (d1 == d2 && d1 < 5) {			//ambiguous result: connect stright 
		if(d) ppg_par->Command(CMD_ADDTOLINE, ep, 0L);
		}
	else {							//no valid solution;
		if(cidx >= 0) return AddShadowPolygon(pnt, ep, -2);
		bRet = false;
		}
	if(tp && ntp>1) {				//create shadow line
		bRet = true;
		for(i = 1; i < ntp; i++) {
			if(i == ntp -1) {
				d = ((d1 = tp[i].x - ep->x) * d1);
				d += ((d1 = tp[i].y - ep->y) * d1);
				if(d < 2){						//too close to end point
					nep.x = ep->x = tp[i].x;	nep.y = ep->y = tp[i].y;
					nep.z = ep->z;
					break;
					}
				}
			np.x = nep.x = tp[i].x;	np.y = nep.y = tp[i].y;
			nep.z = pnt->z > ep->z ? ep->z : pnt->z;
			if(IsInPolygon(&np, ppg_mask, ppg_nmask) || 
				IsCloseToPL(np, ppg_mask, ppg_nmask)){
				if(ppg_vec) {					//valid plane eqation
					nep.z = iround((nep.x * ppg_vec[0] + nep.y * ppg_vec[1] - ppg_vec[3])/ppg_vec[2]);
					ppg_par->Command(CMD_ADDTOLINE, &nep, 0L);
					}
				else if(IsInPolygon3D(nep.x, nep.y, ppg_act, ppg_nact, &us, &ls)) {
					if(us == ls) if(ls){	//point is on the line
						j = nep.z;
						if(ppg_act[ls].x == ppg_act[ls-1].x && ppg_act[ls].y == ppg_act[ls-1].y){
							nep.z = (ppg_act[ls].z + ppg_act[ls-1].z)>>1; //impropable
							}
						else if(abs(ppg_act[ls].x - ppg_act[ls-1].x) > 
							abs(ppg_act[ls].y - ppg_act[ls-1].y)){	// x dominant
							line3D_z(&ppg_act[ls-1], &ppg_act[ls], nep.x, -1, &k, &k, &j);
							}
						else {										// y dominant
							line3D_z(&ppg_act[ls-1], &ppg_act[ls], -1, nep.y, &k, &k, &j);
							}
						nep.z = j;
						}
					else {
						if(line3D_z(&ppg_act[ls-1], &ppg_act[ls], nep.x, -1, &x1, &y1, &z1) &&
							line3D_z(&ppg_act[us-1], &ppg_act[us], nep.x, -1, &x2, &y2, &z2)){
							nep.z = (z1 + z2)>>1;					//impropable
							}
						}
					ppg_par->Command(CMD_ADDTOLINE, &nep, 0L);
					}
				else {
					//point is inside by one algorithm but outside with another
					//try without this point
					}
				}
			}
		if(nep.x != ep->x || nep.y != ep->y) ppg_par->Command(CMD_ADDTOLINE, ep, 0L);
		}
	free(pg1);	free(tp1);	free(tp2);
	return bRet;
}

//calculate the clipping line between two planes
bool CuttingEdge(POINT3D* pt, POINT3D* np)
{
	int i, j, us1, ls1, us2, ls2;
	long d, di[2];
	POINT3D res[2];
	double v[3], s[2][3];

	if(!vclp_pg || !ppg_vec) return false;
	v[0] = vclp_pg[1]*ppg_vec[2] - vclp_pg[2]*ppg_vec[1];
	v[1] = vclp_pg[2]*ppg_vec[0] - vclp_pg[0]*ppg_vec[2];
	v[2] = vclp_pg[0]*ppg_vec[1] - vclp_pg[1]*ppg_vec[0];
	if(fabs(v[0]) < 1e-5 || fabs(v[1]) < 1e-5 || fabs(v[2]) < 1e-5) return false;
	v[0] *= (v[2]*2048.0);	v[1] *= (v[2]*2048.0);	v[2] *= (v[2]*2048.0);
	//find two solutions +/- vector
	for(i = 0; i < 2; i++) {
		s[i][0] = (double)(pt->x);	s[i][1] = (double)(pt->y);	s[i][2] = (double)(pt->z);
		for(j = 0; j < 5; j++) {
			do {
				s[i][0] += v[0];			s[i][1] += v[1];			s[i][2] += v[2];
				}while(IsInPolygon3D(s[i][0], s[i][1], ppg_act, ppg_nact, &us1, &ls1) 
						&& IsInPolygon3D(s[i][0], s[i][1], clp_pg, nclp_pg, &us2, &ls2));
			s[i][0] -= v[0];			s[i][1] -= v[1];			s[i][2] -= v[2];
			v[0] /= 4.0;	v[1] /= 4.0;	v[2] /= 4.0;
			}
		s[i][0] += v[0];			s[i][1] += v[1];			s[i][2] += v[2];
		v[0] *= -1024.0;	v[1] *= -1024.0;	v[2] *= -1024.0;
		res[i].x = iround(s[i][0]);	res[i].y = iround(s[i][1]);	res[i].z = iround(s[i][2]);
		di[i] = (d=(res[i].x - pt->x))*d;		di[i] += ((d=(res[i].y - pt->y))*d);
		}
	if(di[0] > 1 && di[0] > di[1]) {
		//first solution has longer projection
		np->x = res[0].x;	np->y = res[0].y;	np->z = res[0].z;
		return true;
		}
	if(di[1] > 1 && di[1] > di[0]) {
		//second solution has longer projection
		np->x = res[1].x;	np->y = res[1].y;	np->z = res[1].z;
		return true;
		}
	return false;
}

//come here from clip_line_3D to process changes in visibility when
//   clipping one polygon with another
void proc_polygon(int vis, POINT3D *pnt, POINT3D *last)
{
	static POINT3D np, lp;
	long d, d1;
	bool spg_valid;

	switch(ppg_level){
	case 0:						//searching first visible point of polygon
		if(vis == 3) vis = 1;						//on line is visible
		if(!ppg_vis && vis && !ppg_nowvis){			//found it !
			ppg_nowvis = true;			ppg_first.x = pnt->x;
			ppg_first.y = pnt->y;		ppg_first.z = pnt->z;
			ppg_reason = vis;
			}
		else if(!vis && ppg_nowvis) {	//check if too short
			d = (d1 = pnt->x - ppg_first.x) * d1;
			d += (d1 = pnt->y - ppg_first.y) * d1;
			if(d < 3) ppg_nowvis = false;	//cancel first point
			}
		ppg_vis = vis;
		break;
	case 1:
		if(vis == 3) vis = 1;						//on line: visible
		if(ppg_first.x < 0 && ppg_first.y < 0 && vis) {
			memcpy(&ppg_first, pnt, sizeof(POINT3D));
			ppg_firstvis = vis;			lp.x = pnt->x;
			lp.y = pnt->y;				lp.z = pnt->z;
			ppg_par->Command(CMD_STARTLINE, pnt, 0L);
			}
		else if (ppg_vis) {			//leaving visibility or continue
			spg_valid = false;
			if(lp.x == pnt->x && lp.y == pnt->y && lp.z == pnt->z) break;
			if(vis) ppg_par->Command(CMD_ADDTOLINE, pnt, 0L);
			else ppg_par->Command(CMD_ADDTOLINE, last, 0L);
			if(!vis){				//leaving visibility
				ppg_vis = test_plane(last->x, last->y, last->z);
				if(ppg_vis == 3) ppg_vis = 1;
				if(ppg_firstvis == 1 && ppg_vis == 1) {
					//from below surface to below surface
					spg_valid = AddShadowPolygon(last, &ppg_first, -2);
					}
				else if(ppg_firstvis == 1 && ppg_vis == 2) {
					//from below surface enter inside surface
					if(CuttingEdge(last, &np)){
						ppg_par->Command(CMD_ADDTOLINE, &np, 0L);
						spg_valid = AddShadowPolygon(&np, &ppg_first, seg_x_seg);
						}
					else spg_valid = AddShadowPolygon(last, &ppg_first, seg_x_seg);
					}
				else if(ppg_firstvis == 2 && ppg_vis == 1) {
					//from inside surface to below surface
					if(CuttingEdge(&ppg_first, &np)){
						if(!(spg_valid = AddShadowPolygon(last, &np, seg_x_seg)))
							ppg_par->Command(CMD_REQ_POINT, &ppg_first, 0L);
						ppg_par->Command(CMD_ADDTOLINE, &np, 0L);
						}
					else spg_valid = AddShadowPolygon(last, &ppg_first, seg_x_seg);
					}
				else if(ppg_firstvis == 2 && ppg_vis == 2) {
					//from inside surface to inside surface
					// nothing to do: connect straight
					spg_valid = true;
					}
				//prepare for new polygon
				if(spg_valid) {
					ppg_first.x = ppg_first.y = ppg_first.z = -1;
					}
				else {
					//we could not find a proper connection between the two points
					//   probably due to high complexity of graph or shape.
					//   We ignore part of the polygon and continue with the
					//   started shape.
					vis = ppg_vis;
					}
				}
			}
		ppg_vis = vis;				lp.x = pnt->x;
		lp.y = pnt->y;				lp.z = pnt->z;
		break;
		}
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//test if line is available in 3D-polygons: determine shared edges
bool LineInPolgon(POINT3D *p1, POINT3D *p2, POINT3D *tpg, int ntpg)
{
	int i;

	for(i = 1; i < ntpg; i++) {
		if(p2->x == tpg[i].x && p2->y == tpg[i].y && p2->z == tpg[i].z) {
			if(p1->x == tpg[i-1].x && p1->y == tpg[i-1].y && p1->z == tpg[i-1].z) return true;
			}
		if(p1->x == tpg[i].x && p1->y == tpg[i].y && p1->z == tpg[i].z) {
			if(p2->x == tpg[i-1].x && p2->y == tpg[i-1].y && p2->z == tpg[i-1].z) return true;
			}
		}
	i = ntpg -1;
	if(p1->x == tpg[i].x && p1->y == tpg[i].y && p1->z == tpg[i].z &&
		p2->x == tpg[0].x && p2->y == tpg[0].y && p2->z == tpg[0].z) return true;
	if(p2->x == tpg[i].x && p2->y == tpg[i].y && p2->z == tpg[i].z &&
		p1->x == tpg[0].x && p1->y == tpg[0].y && p1->z == tpg[0].z) return true;
	return false;
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//entry points for clipping requests

void clip_line_sphere(GraphObj *par, POINT3D **li, int r, int cx, int cy, int cz)
{
	sph_r2 = r*r;	sph_x = cx;		sph_y = cy;		sph_z = cz;
	if(test_sphere(li[0]->x, li[0]->y, li[0]->z)) par->Command(CMD_STARTLINE, li[0], 0L);
	clip_line_3D(par, &li[0][0], &li[0][1], test_sphere);
}

void clip_line_plane(GraphObj *par, POINT3D **li, POINT3D *pg, int np, double *vec)
{
	nclp_pg = np;		clp_pg = pg;	vclp_pg = vec;
	if(test_plane(li[0]->x, li[0]->y, li[0]->z)) par->Command(CMD_STARTLINE, li[0], 0L);
	clip_line_3D(par, &li[0][0], &li[0][1], test_plane);
	vclp_pg = 0L;
}

void clip_sphline_sphere(GraphObj *par, POINT3D *lim1, POINT3D *lim2, POINT3D *cent, 
	int r1, int r2, int cx, int cy, int cz)
{
	sphlim1 = lim1;		sphlim2 = lim2;
	sph_r2 = r2*r2;	sph_x = cx;		sph_y = cy;		sph_z = cz;	
	clip_spher_line(par, cent, r1, lim1->x == lim2->x, test_sphere);
}

void clip_sphline_plane(GraphObj *par, POINT3D *lim1, POINT3D *lim2, POINT3D *cent, 
	int r1, POINT3D *pg, int np, double *vec)
{
	sphlim1 = lim1;		sphlim2 = lim2;		nclp_pg = np;
	clp_pg = pg;		vclp_pg = vec;
	clip_spher_line(par, cent, r1, lim1->x == lim2->x, test_planeandline);
	vclp_pg = 0L;
}

void clip_plane_plane(GraphObj *par, POINT3D *pg1, int n1, double *v1, POINT3D *pg2, 
	int n2, double *v2, POINT *mask, int nmask)
{
	int i, j;
	POINT3D sp;

	nclp_pg = n2;	clp_pg = pg2;	ppg_level = 0;	ppg_nowvis = false;
	ppg_reason = 0;	vclp_pg = v2;
    ppg_vis = test_plane(pg1[0].x, pg1[0].y, pg1[0].z);
	ppg_act = pg1;	ppg_nact = n1;	ppg_vec = v1;
	for(i = 1; i < n1 && !ppg_nowvis; i++){		//assume first pnt == last pnt
		if(!LineInPolgon(&pg1[i-1], &pg1[i], pg2, n2))
			clip_line_3D(0L, &pg1[i-1], &pg1[i], test_plane);
		}
	if(!ppg_nowvis && !ppg_vis) {				//complete pg hidden
		ppg_vec = vclp_pg = 0L;		return;
		}
	if(ppg_nowvis) {							//clip this polygon
		ppg_mask = mask;		ppg_nmask = nmask;
		ppg_level = 1;			ppg_par = par;
		sp.x = ppg_first.x;		sp.y = ppg_first.y;
		sp.z = ppg_first.z;		ppg_first.x = ppg_first.y = ppg_first.z = -1;
		ppg_vis = test_plane(sp.x, sp.y, sp.z);
		proc_polygon(ppg_vis, &sp, &sp);
		clip_line_3D(0L, &sp, &pg1[i-1], test_plane);
		for(j = i+n1-1; i < j; i++) {
			seg_x_seg = -2;
			clip_line_3D(0L, &pg1[(i-1)%n1], &pg1[i%n1], test_plane);
			}
		clip_line_3D(0L, &pg1[(i-1)%n1], &sp, test_plane);
		}
	else {										//all visible
		par->Command(CMD_STARTLINE, pg1, 0L);
		for(i = 1; i < n1; i++) {
			par->Command(CMD_ADDTOLINE, &pg1[i], 0L);
			}
		}
	ppg_vec = vclp_pg = 0L;
}