fillpoly.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520
  1. /*
  2. * This file is part of the UCB release of Plan 9. It is subject to the license
  3. * terms in the LICENSE file found in the top-level directory of this
  4. * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
  5. * part of the UCB release of Plan 9, including this file, may be copied,
  6. * modified, propagated, or distributed except according to the terms contained
  7. * in the LICENSE file.
  8. */
  9. #include <u.h>
  10. #include <libc.h>
  11. #include <draw.h>
  12. #include <memdraw.h>
  13. #include <memlayer.h>
  14. typedef struct Seg Seg;
  15. struct Seg
  16. {
  17. Point p0;
  18. Point p1;
  19. int32_t num;
  20. int32_t den;
  21. int32_t dz;
  22. int32_t dzrem;
  23. int32_t z;
  24. int32_t zerr;
  25. int32_t d;
  26. };
  27. static void zsort(Seg **seg, Seg **ep);
  28. static int ycompare(const void*, const void*);
  29. static int xcompare(const void*, const void*);
  30. static int zcompare(const void*, const void*);
  31. static void xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int, int, int);
  32. static void yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int);
  33. static void
  34. fillline(Memimage *dst, int left, int right, int y, Memimage *src, Point p, int op)
  35. {
  36. Rectangle r;
  37. r.min.x = left;
  38. r.min.y = y;
  39. r.max.x = right;
  40. r.max.y = y+1;
  41. p.x += left;
  42. p.y += y;
  43. memdraw(dst, r, src, p, memopaque, p, op);
  44. }
  45. static void
  46. fillpoint(Memimage *dst, int x, int y, Memimage *src, Point p, int op)
  47. {
  48. Rectangle r;
  49. r.min.x = x;
  50. r.min.y = y;
  51. r.max.x = x+1;
  52. r.max.y = y+1;
  53. p.x += x;
  54. p.y += y;
  55. memdraw(dst, r, src, p, memopaque, p, op);
  56. }
  57. void
  58. memfillpoly(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int op)
  59. {
  60. _memfillpolysc(dst, vert, nvert, w, src, sp, 0, 0, 0, op);
  61. }
  62. void
  63. _memfillpolysc(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
  64. {
  65. Seg **seg, *segtab;
  66. Point p0;
  67. int i;
  68. if(nvert == 0)
  69. return;
  70. seg = malloc((nvert+2)*sizeof(Seg*));
  71. if(seg == nil)
  72. return;
  73. segtab = malloc((nvert+1)*sizeof(Seg));
  74. if(segtab == nil) {
  75. free(seg);
  76. return;
  77. }
  78. sp.x = (sp.x - vert[0].x) >> fixshift;
  79. sp.y = (sp.y - vert[0].y) >> fixshift;
  80. p0 = vert[nvert-1];
  81. if(!fixshift) {
  82. p0.x <<= 1;
  83. p0.y <<= 1;
  84. }
  85. for(i = 0; i < nvert; i++) {
  86. segtab[i].p0 = p0;
  87. p0 = vert[i];
  88. if(!fixshift) {
  89. p0.x <<= 1;
  90. p0.y <<= 1;
  91. }
  92. segtab[i].p1 = p0;
  93. segtab[i].d = 1;
  94. }
  95. if(!fixshift)
  96. fixshift = 1;
  97. xscan(dst, seg, segtab, nvert, w, src, sp, detail, fixshift, clipped, op);
  98. if(detail)
  99. yscan(dst, seg, segtab, nvert, w, src, sp, fixshift, op);
  100. free(seg);
  101. free(segtab);
  102. }
  103. static int32_t
  104. mod(int32_t x, int32_t y)
  105. {
  106. int32_t z;
  107. z = x%y;
  108. if((int32_t)(((uint32_t)z)^((uint32_t)y)) > 0 || z == 0)
  109. return z;
  110. return z + y;
  111. }
  112. static int32_t
  113. sdiv(int32_t x, int32_t y)
  114. {
  115. if((int32_t)(((uint32_t)x)^((uint32_t)y)) >= 0 || x == 0)
  116. return x/y;
  117. return (x+((y>>30)|1))/y-1;
  118. }
  119. static int32_t
  120. smuldivmod(int32_t x, int32_t y, int32_t z, int32_t *mod)
  121. {
  122. int64_t vx;
  123. if(x == 0 || y == 0){
  124. *mod = 0;
  125. return 0;
  126. }
  127. vx = x;
  128. vx *= y;
  129. *mod = vx % z;
  130. if(*mod < 0)
  131. *mod += z; /* z is always >0 */
  132. if((vx < 0) == (z < 0))
  133. return vx/z;
  134. return -((-vx)/z);
  135. }
  136. static void
  137. xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
  138. {
  139. int32_t y, maxy, x, x2, xerr, xden, onehalf;
  140. Seg **ep, **next, **p, **q, *s;
  141. int32_t n, i, iy, cnt, ix, ix2, minx, maxx;
  142. Point pt;
  143. void (*fill)(Memimage*, int, int, int, Memimage*, Point, int);
  144. fill = fillline;
  145. /*
  146. * This can only work on 8-bit destinations, since fillcolor is
  147. * just using memset on sp.x.
  148. *
  149. * I'd rather not even enable it then, since then if the general
  150. * code is too slow, someone will come up with a better improvement
  151. * than this sleazy hack. -rsc
  152. *
  153. if(clipped && (src->flags&Frepl) && src->depth==8 && Dx(src->r)==1 && Dy(src->r)==1) {
  154. fill = fillcolor;
  155. sp.x = membyteval(src);
  156. }
  157. *
  158. */
  159. USED(clipped);
  160. for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
  161. *p = s;
  162. if(s->p0.y == s->p1.y)
  163. continue;
  164. if(s->p0.y > s->p1.y) {
  165. pt = s->p0;
  166. s->p0 = s->p1;
  167. s->p1 = pt;
  168. s->d = -s->d;
  169. }
  170. s->num = s->p1.x - s->p0.x;
  171. s->den = s->p1.y - s->p0.y;
  172. s->dz = sdiv(s->num, s->den) << fixshift;
  173. s->dzrem = mod(s->num, s->den) << fixshift;
  174. s->dz += sdiv(s->dzrem, s->den);
  175. s->dzrem = mod(s->dzrem, s->den);
  176. p++;
  177. }
  178. n = p-seg;
  179. if(n == 0)
  180. return;
  181. *p = 0;
  182. qsort(seg, p-seg , sizeof(Seg*), ycompare);
  183. onehalf = 0;
  184. if(fixshift)
  185. onehalf = 1 << (fixshift-1);
  186. minx = dst->clipr.min.x;
  187. maxx = dst->clipr.max.x;
  188. y = seg[0]->p0.y;
  189. if(y < (dst->clipr.min.y << fixshift))
  190. y = dst->clipr.min.y << fixshift;
  191. iy = (y + onehalf) >> fixshift;
  192. y = (iy << fixshift) + onehalf;
  193. maxy = dst->clipr.max.y << fixshift;
  194. ep = next = seg;
  195. while(y<maxy) {
  196. for(q = p = seg; p < ep; p++) {
  197. s = *p;
  198. if(s->p1.y < y)
  199. continue;
  200. s->z += s->dz;
  201. s->zerr += s->dzrem;
  202. if(s->zerr >= s->den) {
  203. s->z++;
  204. s->zerr -= s->den;
  205. if(s->zerr < 0 || s->zerr >= s->den)
  206. print("bad ratzerr1: %ld den %ld dzrem %ld\n", s->zerr, s->den, s->dzrem);
  207. }
  208. *q++ = s;
  209. }
  210. for(p = next; *p; p++) {
  211. s = *p;
  212. if(s->p0.y >= y)
  213. break;
  214. if(s->p1.y < y)
  215. continue;
  216. s->z = s->p0.x;
  217. s->z += smuldivmod(y - s->p0.y, s->num, s->den, &s->zerr);
  218. if(s->zerr < 0 || s->zerr >= s->den)
  219. print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
  220. *q++ = s;
  221. }
  222. ep = q;
  223. next = p;
  224. if(ep == seg) {
  225. if(*next == 0)
  226. break;
  227. iy = (next[0]->p0.y + onehalf) >> fixshift;
  228. y = (iy << fixshift) + onehalf;
  229. continue;
  230. }
  231. zsort(seg, ep);
  232. for(p = seg; p < ep; p++) {
  233. cnt = 0;
  234. x = p[0]->z;
  235. xerr = p[0]->zerr;
  236. xden = p[0]->den;
  237. ix = (x + onehalf) >> fixshift;
  238. if(ix >= maxx)
  239. break;
  240. if(ix < minx)
  241. ix = minx;
  242. cnt += p[0]->d;
  243. p++;
  244. for(;;) {
  245. if(p == ep) {
  246. print("xscan: fill to infinity");
  247. return;
  248. }
  249. cnt += p[0]->d;
  250. if((cnt&wind) == 0)
  251. break;
  252. p++;
  253. }
  254. x2 = p[0]->z;
  255. ix2 = (x2 + onehalf) >> fixshift;
  256. if(ix2 <= minx)
  257. continue;
  258. if(ix2 > maxx)
  259. ix2 = maxx;
  260. if(ix == ix2 && detail) {
  261. if(xerr*p[0]->den + p[0]->zerr*xden > p[0]->den*xden)
  262. x++;
  263. ix = (x + x2) >> (fixshift+1);
  264. ix2 = ix+1;
  265. }
  266. (*fill)(dst, ix, ix2, iy, src, sp, op);
  267. }
  268. y += (1<<fixshift);
  269. iy++;
  270. }
  271. }
  272. static void
  273. yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int fixshift, int op)
  274. {
  275. int32_t x, maxx, y, y2, yerr, yden, onehalf;
  276. Seg **ep, **next, **p, **q, *s;
  277. int n, i, ix, cnt, iy, iy2, miny, maxy;
  278. Point pt;
  279. for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
  280. *p = s;
  281. if(s->p0.x == s->p1.x)
  282. continue;
  283. if(s->p0.x > s->p1.x) {
  284. pt = s->p0;
  285. s->p0 = s->p1;
  286. s->p1 = pt;
  287. s->d = -s->d;
  288. }
  289. s->num = s->p1.y - s->p0.y;
  290. s->den = s->p1.x - s->p0.x;
  291. s->dz = sdiv(s->num, s->den) << fixshift;
  292. s->dzrem = mod(s->num, s->den) << fixshift;
  293. s->dz += sdiv(s->dzrem, s->den);
  294. s->dzrem = mod(s->dzrem, s->den);
  295. p++;
  296. }
  297. n = p-seg;
  298. if(n == 0)
  299. return;
  300. *p = 0;
  301. qsort(seg, n , sizeof(Seg*), xcompare);
  302. onehalf = 0;
  303. if(fixshift)
  304. onehalf = 1 << (fixshift-1);
  305. miny = dst->clipr.min.y;
  306. maxy = dst->clipr.max.y;
  307. x = seg[0]->p0.x;
  308. if(x < (dst->clipr.min.x << fixshift))
  309. x = dst->clipr.min.x << fixshift;
  310. ix = (x + onehalf) >> fixshift;
  311. x = (ix << fixshift) + onehalf;
  312. maxx = dst->clipr.max.x << fixshift;
  313. ep = next = seg;
  314. while(x<maxx) {
  315. for(q = p = seg; p < ep; p++) {
  316. s = *p;
  317. if(s->p1.x < x)
  318. continue;
  319. s->z += s->dz;
  320. s->zerr += s->dzrem;
  321. if(s->zerr >= s->den) {
  322. s->z++;
  323. s->zerr -= s->den;
  324. if(s->zerr < 0 || s->zerr >= s->den)
  325. print("bad ratzerr1: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
  326. }
  327. *q++ = s;
  328. }
  329. for(p = next; *p; p++) {
  330. s = *p;
  331. if(s->p0.x >= x)
  332. break;
  333. if(s->p1.x < x)
  334. continue;
  335. s->z = s->p0.y;
  336. s->z += smuldivmod(x - s->p0.x, s->num, s->den, &s->zerr);
  337. if(s->zerr < 0 || s->zerr >= s->den)
  338. print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
  339. *q++ = s;
  340. }
  341. ep = q;
  342. next = p;
  343. if(ep == seg) {
  344. if(*next == 0)
  345. break;
  346. ix = (next[0]->p0.x + onehalf) >> fixshift;
  347. x = (ix << fixshift) + onehalf;
  348. continue;
  349. }
  350. zsort(seg, ep);
  351. for(p = seg; p < ep; p++) {
  352. cnt = 0;
  353. y = p[0]->z;
  354. yerr = p[0]->zerr;
  355. yden = p[0]->den;
  356. iy = (y + onehalf) >> fixshift;
  357. if(iy >= maxy)
  358. break;
  359. if(iy < miny)
  360. iy = miny;
  361. cnt += p[0]->d;
  362. p++;
  363. for(;;) {
  364. if(p == ep) {
  365. print("yscan: fill to infinity");
  366. return;
  367. }
  368. cnt += p[0]->d;
  369. if((cnt&wind) == 0)
  370. break;
  371. p++;
  372. }
  373. y2 = p[0]->z;
  374. iy2 = (y2 + onehalf) >> fixshift;
  375. if(iy2 <= miny)
  376. continue;
  377. if(iy2 > maxy)
  378. iy2 = maxy;
  379. if(iy == iy2) {
  380. if(yerr*p[0]->den + p[0]->zerr*yden > p[0]->den*yden)
  381. y++;
  382. iy = (y + y2) >> (fixshift+1);
  383. fillpoint(dst, ix, iy, src, sp, op);
  384. }
  385. }
  386. x += (1<<fixshift);
  387. ix++;
  388. }
  389. }
  390. static void
  391. zsort(Seg **seg, Seg **ep)
  392. {
  393. int done;
  394. Seg **q, **p, *s;
  395. if(ep-seg < 20) {
  396. /* bubble sort by z - they should be almost sorted already */
  397. q = ep;
  398. do {
  399. done = 1;
  400. q--;
  401. for(p = seg; p < q; p++) {
  402. if(p[0]->z > p[1]->z) {
  403. s = p[0];
  404. p[0] = p[1];
  405. p[1] = s;
  406. done = 0;
  407. }
  408. }
  409. } while(!done);
  410. } else {
  411. q = ep-1;
  412. for(p = seg; p < q; p++) {
  413. if(p[0]->z > p[1]->z) {
  414. qsort(seg, ep-seg, sizeof(Seg*), zcompare);
  415. break;
  416. }
  417. }
  418. }
  419. }
  420. static int
  421. ycompare(const void *a, const void *b)
  422. {
  423. Seg **s0, **s1;
  424. int32_t y0, y1;
  425. s0 = (Seg **)a;
  426. s1 = (Seg **)b;
  427. y0 = (*s0)->p0.y;
  428. y1 = (*s1)->p0.y;
  429. if(y0 < y1)
  430. return -1;
  431. if(y0 == y1)
  432. return 0;
  433. return 1;
  434. }
  435. static int
  436. xcompare(const void *a, const void *b)
  437. {
  438. Seg **s0, **s1;
  439. int32_t x0, x1;
  440. s0 = (Seg **)a;
  441. s1 = (Seg **)b;
  442. x0 = (*s0)->p0.x;
  443. x1 = (*s1)->p0.x;
  444. if(x0 < x1)
  445. return -1;
  446. if(x0 == x1)
  447. return 0;
  448. return 1;
  449. }
  450. static int
  451. zcompare(const void *a, const void *b)
  452. {
  453. Seg **s0, **s1;
  454. int32_t z0, z1;
  455. s0 = (Seg **)a;
  456. s1 = (Seg **)b;
  457. z0 = (*s0)->z;
  458. z1 = (*s1)->z;
  459. if(z0 < z1)
  460. return -1;
  461. if(z0 == z1)
  462. return 0;
  463. return 1;
  464. }