/*
 *	clipint.c
 *
 *	整数演算ライブラリ
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2009 Naoyuki Sawa
 *
 *	* Sat Sep 12 20:19:17 JST 2009 Naoyuki Sawa
 *	- 新規作成。
 *	- clipflt.hモジュール互換仕様の整数版です。
 *	  今回はrender_vec2i_alternate_concaves()だけが必要だったので、そのための最小限の関数以外はほとんど未実装です。
 *	* Sun Sep 13 15:47:06 JST 2009 Naoyuki Sawa
 *	- vec2i_is_point_in_concave()をアセンブラ化し、高速化しました。
 */
#include "clip.h"

#ifndef PIECE
#define NOASM	// このシンポルを定義すると、C言語版を使用します。 */
#endif /*PIECE*/

/****************************************************************************
 *	整数ベクトル(2D)
 ****************************************************************************/

#define vec2i_sub(vec1, vec2)	\
	(vec1)->x -= (vec2)->x;	\
	(vec1)->y -= (vec2)->y;

#define vec2i_cross(vec1, vec2)	\
	(((vec1)->x * (vec2)->y) - ((vec1)->y * (vec2)->x))

/*--------------------------------------------------------------------------*/

/* 点pと、v[nv]を頂点とする凹多角形の内外判定 */
#ifdef NOASM
int vec2i_is_point_in_concave(const vec2i* p, const vec2i* v/*[nv]*/, int nv) {
	int i;
	int j;
	int n;
	const vec2i* vi;
	const vec2i* vj;
	int xmin;
	int xmax;
	int ymin;
	int ymax;
	int prev;
	int f;
	vec2i v0;
	vec2i v1;

	/* いちばん上の頂点を検索しながら、同時に境界ボックスを求め、おおまかな当り判定を行います。 */
	i = j = nv;
	vi = vj = v;
	xmin = xmax = vj->x;
	ymin = ymax = vj->y;
	vj++;
	j--;
	do {
		if((vj->x < xmin)) {
			xmin = vj->x;
		} else if(vj->x > xmax) {
			xmax = vj->x;
		}
		if((vj->y < ymin)) {
			ymin = vj->y;
			i = j;
			vi = vj;
		} else if(vj->y > ymax) {
			ymax = vj->y;
		}
		vj++;
	} while(--j);
	if((p->x < xmin) || (p->x > xmax) ||
	   (p->y < ymin) || (p->y > ymax)) {
		return 0;
	}

	/* 点を始点とする半直線と、多角形の辺の交差回数が、奇数ならば内側、偶数ならば外側です。 */
	prev = 0;
	n = 0;
	j = nv;
	do {
		v0 = *vi;
		v1 = *vi;
		vi++;
		if(!--i) {
			vi = v;
		}
		vec2i_sub(&v0, p);
		vec2i_sub(&v1, vi);
		f = vec2i_cross(&v0, &v1);
		if(!f) {					/* 点pが辺の直線上にある場合の特別処理 */
			if(v0.x) {				/* 点pが辺の始点上でなく、 */
				if(v0.x < 0) {			/* 点pが辺の始点よりも右で、 */
					if(v0.x < v1.x) {	/* 点pが辺の終点よりも右なら、 */
						goto NOT_ON_LS;	/* 点pは辺の線分上ではないので処理継続 */
					}
				} else/*if(v0.x > 0)*/ {	/* 点pが辺の始点よりも左で、 */
					if(v0.x > v1.x) {	/* 点pが辺の終点よりも左なら、 */
						goto NOT_ON_LS;	/* 点pは辺の線分上ではないので処理継続 */
					}
				}
			}
			if(v0.y) {				/* 点pが辺の始点上でなく、 */
				if(v0.y < 0) {			/* 点pが辺の始点よりも下で、 */
					if(v0.y < v1.y) {	/* 点pが辺の終点よりも下なら、 */
						goto NOT_ON_LS;	/* 点pは辺の線分上ではないので処理継続 */
					}
				} else/*if(v0.y > 0)*/ {	/* 点pが辺の始点よりも上で、 */
					if(v0.y > v1.y) {	/* 点pが辺の終点よりも上なら、 */
						goto NOT_ON_LS;	/* 点pは辺の線分上ではないので処理継続 */
					}
				}
			}
			return -1;				/* 点pは辺の線分上である */
NOT_ON_LS:							/* 点pは辺の線分上ではないので処理継続 */
		}
		if(v1.y) {
			if(v1.y < 0) {
				if((f < 0) && (v1.y <= v0.y)) {
					if(prev < 0) {
						if(v0.y < 0) {
							n ^= 1;
						}
					} else {
						if(v0.y <= 0) {
							n ^= 1;
						}
					}
				}
			} else /* if(v1.y > 0) */ {
				if((f > 0) && (v1.y >= v0.y)) {
					if(prev > 0) {
						if(v0.y > 0) {
							n ^= 1;
						}
					} else {
						if(v0.y >= 0) {
							n ^= 1;
						}
					}
				}
			}
			prev = v1.y;
		}
	} while(--j);
	return n; /* 0 or 1 */
}
#else /*NOASM*/
asm("
		.code
		.align		1
		.global		vec2i_is_point_in_concave
vec2i_is_point_in_concave:
		pushn		%r3
		;// %r12 := p
		;// %r13 := v
		;// %r14 := nv
		;//-----------------------------------------------------;
		ld.w		%r2, %r14				;// %r2  := j = nv
		ld.w		%r3, %r13				;// %r3  := vj = v
		ld.w		%r4, [%r3]+				;// %r4  := xmin = vj->x
		ld.w		%r5, [%r3]+				;// %r5  := ymin = vj->y, %r3  := vj++
		ld.w		%r6, %r4				;// %r6  := xmax = vj->x
		ld.w		%r7, %r5				;// %r7  := ymax = vj->y
		sub		%r2, 1					;// %r2  := j--
		ld.w		%r0, %r2				;// %r0  :=  i - 1 =  j ( iは1つ減った値を保持しておき、確定後に戻す。高速化)
		ld.w		%r1, %r3				;// %r1  := vi + 1 = vj (viは1つ進んだ値を保持しておき、確定後に戻す。高速化)
		;// %r0  :=  i - 1
		;// %r1  := vi + 1
		;// %r2  := j
		;// %r3  := vj
		;// %r4  := xmin
		;// %r5  := ymin
		;// %r6  := xmax
		;// %r7  := ymax
		;// %r12 := p
		;// %r13 := v
		;// %r14 := nv
vec2i_is_point_in_concave_LOOP1:					;// do {
		ld.w		%r10, [%r3]+				;//   %r10  := vj->x
		ld.w		%r11, [%r3]+				;//   %r11  := vj->y, %r3  := vj++
		;//
		cmp		%r10, %r4				;//   if(vj->x < xmin)
		jrge.d		3
		cmp		%r10, %r6				;//   <-------------------------+	*delay*
		 ld.w		%r4, %r10				;//     %r4  := xmin = vj->x	|
		;//							;//				|
;//		cmp		%r10, %r6				;//   if(vj->x > xmax) ---------+
		jrle.d		3
		cmp		%r11, %r5				;//   <-------------------------+	*delay*
		 ld.w		%r6, %r10				;//     %r6  := xmax = vj->x	|
		;//							;//				|
;//		cmp		%r11, %r5				;//   if(vj->y < ymin) ---------+
		jrge.d		3
		cmp		%r11, %r7				;//   <-------------------------+	*delay*
		 ld.w		%r5, %r11				;//     %r5  := ymin = vj->y	|
		;//							;//				|
;//		cmp		%r11, %r7				;//   if(vj->y > ymax) ---------+
		jrle.d		5
		sub		%r2, 1					;//   <-------------------------+	*delay*
		 ld.w		%r7, %r11				;//     %r7  := ymax = vj->y	|
		 ld.w		%r0, %r2				;//     %r0  :=  i - 1 =  j	|
		 ld.w		%r1, %r3				;//     %r1  := vi + 1 = vj	|
		;//							;//				|
;//		sub		%r2, 1					;//   %r2  := j-- --------------+
		jrne		vec2i_is_point_in_concave_LOOP1		;// } while(j)
		;//
		ld.w		%r2, [%r12]+				;// %r2  := p->x
		ld.w		%r3, [%r12]				;// %r3  := p->y
		;//
		cmp		%r2, %r4				;// if(p->x < xmin)
		jrlt		vec2i_is_point_in_concave_RET0		;//   return 0
		;//
		cmp		%r2, %r6				;// if(p->x > xmax)
		jrgt		vec2i_is_point_in_concave_RET0		;//   return 0
		;//
		cmp		%r3, %r5				;// if(p->y < ymin)
		jrlt		vec2i_is_point_in_concave_RET0		;//   return 0
		;//
		cmp		%r3, %r7				;// if(p->y > ymax)
		jrgt		vec2i_is_point_in_concave_RET0		;//   return 0
		;//
		add		%r0, 1					;// %r0  :=  i ( iは1つ減った値を保持している。 iが確定したので、ここで戻す)
		sub		%r1, 8					;// %r1  := vi (viは1つ進んだ値を保持している。viが確定したので、ここで戻す)
		;// %r0  := i
		;// %r1  := vi
		;// %r2  := p->x
		;// %r3  := p->y
		;// %r13 := v
		;// %r14 := nv
		;//-----------------------------------------------------;
		ld.w		%r10, 0					;// %r10 := n = 0
		ld.w		%r11, 0					;// %r11 := prev = 0
		;// %r0  := i
		;// %r1  := vi
		;// %r2  := p->x
		;// %r3  := p->y
		;// %r10 := n
		;// %r11 := prev
		;// %r13 := v
		;// %r14 := j = nv
vec2i_is_point_in_concave_LOOP2:					;// do {
		ld.w		%r4, [%r1]+				;//   %r4  := v0.x = vi->x
		ld.w		%r5, [%r1]+				;//   %r5  := v0.y = vi->y, %r1  := vi++
		ld.w		%r6, %r4				;//   %r6  := v1.x = vi->x
		ld.w		%r7, %r5				;//   %r7  := v1.y = vi->y
		;// %r0  := i
		;// %r1  := vi
		;// %r2  := p->x
		;// %r3  := p->y
		;// %r4  := v0.x
		;// %r5  := v0.y
		;// %r6  := v1.x
		;// %r7  := v1.y
		;// %r10 := n
		;// %r11 := prev
		;// %r13 := v
		;// %r14 := j
		sub		%r0, 1					;//   %r0  := i--
		jrne.d		3					;//   if(!i)
		sub		%r4, %r2				;//   <-------------------------+	*delay*
		 ld.w		%r1, %r13				;//     %r1  := vi = v		|
		;//							;//				|
;//		sub		%r4, %r2				;//   %r4  := v0.x -= p->x -----+
		sub		%r5, %r3				;//   %r5  := v0.y -= p->y
		;//
		xld.w		%r12, [%r1+0]				;//   %r12 :=         vi->x
		xld.w		%r15, [%r1+4]				;//   %r15 :=         vi->y
		sub		%r6, %r12				;//   %r6  := v1.x -= vi->x
		sub		%r7, %r15				;//   %r7  := v1.y -= vi->y
		;//
		mlt.w		%r4, %r7				;//   %alr :=     v0.x * v1.y
		ld.w		%r12, %alr				;//   %r12 :=     v0.x * v1.y
		mlt.w		%r5, %r6				;//   %alr :=                   v0.y * v1.x
		ld.w		%r15, %alr				;//   %r13 :=                   v0.y * v1.x
		sub		%r12, %r15				;//   %r12 := f = v0.x * v1.y - v0.y * v1.x
		jrne		vec2i_is_point_in_concave_NOT_ON_LS	;//   if(!f)
		;//- - - - - - - - - - - - - - - - - - - - - - - - - - -;
		cmp		%r4, 0					;//     if(v0.x) {
		jreq		vec2i_is_point_in_concave_X_ON_LS
		jrgt		vec2i_is_point_in_concave_V0X_GT_0	;//       if(v0.x < 0)
		cmp		%r4, %r6				;//         if(v0.x < v1.x)
		jrlt		vec2i_is_point_in_concave_NOT_ON_LS	;//           goto NOT_ON_LS
		jp		vec2i_is_point_in_concave_X_ON_LS
vec2i_is_point_in_concave_V0X_GT_0:					;//       else
		cmp		%r4, %r6				;//         if(v0.x > v1.x)
		jrgt		vec2i_is_point_in_concave_NOT_ON_LS	;//           goto NOT_ON_LS
vec2i_is_point_in_concave_X_ON_LS:					;//     }
		cmp		%r5, 0					;//     if(v0.y) {
		jreq		vec2i_is_point_in_concave_RET_1
		jrgt		vec2i_is_point_in_concave_V0Y_GT_0	;//       if(v0.y < 0)
		cmp		%r5, %r7				;//         if(v0.y < v1.y)
		jrlt		vec2i_is_point_in_concave_NOT_ON_LS	;//           goto NOT_ON_LS
		jp		vec2i_is_point_in_concave_RET_1
vec2i_is_point_in_concave_V0Y_GT_0:					;//       else
		cmp		%r5, %r7				;//         if(v0.y > v1.y)
		jrgt		vec2i_is_point_in_concave_NOT_ON_LS	;//           goto NOT_ON_LS
		jp		vec2i_is_point_in_concave_RET_1
vec2i_is_point_in_concave_NOT_ON_LS:					;//     }
		;//- - - - - - - - - - - - - - - - - - - - - - - - - - -;
		cmp		%r7, 0					;//   if(v1.y)
		jreq		vec2i_is_point_in_concave_NEXT
		jrgt.d		vec2i_is_point_in_concave_V1Y_GT_0	;//     if(v1.y < 0)
		cmp		%r12, 0					;//     %psr := f - 0				*delay*
;//vec2i_is_point_in_concave_V1Y_LT_0:
		jrge		vec2i_is_point_in_concave_PREV_V1Y	;//       if(f < 0)
		cmp		%r7, %r5				;//         if(v1.y <= v0.y)
		jrgt		vec2i_is_point_in_concave_PREV_V1Y
		cmp		%r11, 0					;//           if(prev < 0) {
		jrge.d		4
		 cmp		%r5, 0					;//           %psr := v0.y - 0			*delay*
		 jrge		vec2i_is_point_in_concave_PREV_V1Y	;//             if(v0.y < 0)
		 jp		vec2i_is_point_in_concave_N_TOGGLE	;//               n ^= 1
		;//							;//           } else {
		jrgt		vec2i_is_point_in_concave_PREV_V1Y	;//             if(v0.y <= 0)
		jp		vec2i_is_point_in_concave_N_TOGGLE	;//               n ^= 1
		;//							;//           }
vec2i_is_point_in_concave_V1Y_GT_0:					;//     } else {
		jrle		vec2i_is_point_in_concave_PREV_V1Y	;//       if(f > 0)
		cmp		%r7, %r5				;//         if(v1.y >= v0.y)
		jrlt		vec2i_is_point_in_concave_PREV_V1Y
		cmp		%r11, 0					;//           if(prev < 0) {
		jrle.d		4
		 cmp		%r5, 0					;//           %psr := v0.y - 0			*delay*
		 jrle		vec2i_is_point_in_concave_PREV_V1Y	;//             if(v0.y > 0)
		 jp		vec2i_is_point_in_concave_N_TOGGLE	;//               n ^= 1
		;//							;//           } else {
		jrlt		vec2i_is_point_in_concave_PREV_V1Y	;//             if(v0.y >= 0)
;//		jp		vec2i_is_point_in_concave_N_TOGGLE	;//               n ^= 1
		;//							;//           }
vec2i_is_point_in_concave_N_TOGGLE:					;//     }
		xor		%r10, 1					;//   %r10 := n ^= 1
vec2i_is_point_in_concave_PREV_V1Y:
		ld.w		%r11, %r7				;//   %r3  := prev = v1.y
		;// %r0  := i
		;// %r1  := vi
		;// %r2  := p->x
		;// %r3  := p->y
		;// %r10 := n
		;// %r11 := prev
		;// %r13 := v
		;// %r14 := j
vec2i_is_point_in_concave_NEXT:
		sub		%r14, 1					;//   %r14 := j--
		jrne		vec2i_is_point_in_concave_LOOP2		;// } while(j)
		;//-----------------------------------------------------;
vec2i_is_point_in_concave_RET:
		popn		%r3
		ret
vec2i_is_point_in_concave_RET0:
		jp.d		vec2i_is_point_in_concave_RET
		ld.w		%r10, 0					;// %r10 := n = 0	*delay*
vec2i_is_point_in_concave_RET_1:
		jp.d		vec2i_is_point_in_concave_RET
		ld.w		%r10, -1				;// %r10 := n = -1	*delay*
");
#endif /*NOASM*/

/*--------------------------------------------------------------------------*/

int
vec2i_is_point_in_alternate_concaves(const vec2i* p, const vec2i* v/*[sum(nv[0...n-1])]*/, const int* nv/*[n]*/, int n)
{
	int c = 0;
	do {
		int f = vec2i_is_point_in_concave(p, v, *nv);
		if(f) {
			/* どれかの多角形の辺上ならば、即座に"内"と見なす */
			if(f == -1) {
				return f;
			}
			/* 多角形の内部ならば、回数の偶数奇数をトグルする */
			c ^= 1;
		}
		v += *nv++;
	} while(--n);
	return c;
}

/*--------------------------------------------------------------------------*/

void
render_vec2i_alternate_concaves(RENDER* render, const vec2i* v/*[sum(nv[0...n-1])]*/, const int* nv/*[n]*/, int n, int c) /* ←cliprend.h */
{
	int i;
	int j;
	int xmin;
	int xmax;
	int ymin;
	int ymax;
	const vec2i* pv;
	vec2i p;

	/* 境界矩形を求める */
	pv = v;
	xmin = xmax = pv->x; /* 少なくとも一つは座標が有ると仮定 */
	ymin = ymax = pv->y; /* 少なくとも一つは座標が有ると仮定 */
	for(i = 0; i < n; i++) {
		for(j = 0; j < nv[i]; j++) {
			if(pv->x < xmin) xmin = pv->x;
			if(pv->x > xmax) xmax = pv->x;
			if(pv->y < ymin) ymin = pv->y;
			if(pv->y > ymax) ymax = pv->y;
			pv++;
		}
	}

	/* 境界矩形をクリッピングする */
	if(xmin < render->left      ) xmin = render->left      ;
	if(xmax > render->right  - 1) xmax = render->right  - 1;
	if(ymin < render->top       ) ymin = render->top       ;
	if(ymax > render->bottom - 1) ymax = render->bottom - 1;

	/* 境界矩形内のピクセルを描く */
	for(p.y = ymin; p.y <= ymax; p.y++) {
		for(p.x = xmin; p.x <= xmax; p.x++) {
			if(vec2i_is_point_in_alternate_concaves(&p, v, nv, n)) {
				render_point(render, p.x, p.y, c);
			}
		}
	}
}

