fillpoly.c 10 KB

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