line.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486
  1. #include <u.h>
  2. #include <libc.h>
  3. #include <draw.h>
  4. #include <memdraw.h>
  5. #include <memlayer.h>
  6. enum
  7. {
  8. Arrow1 = 8,
  9. Arrow2 = 10,
  10. Arrow3 = 3,
  11. };
  12. static
  13. int
  14. lmin(int a, int b)
  15. {
  16. if(a < b)
  17. return a;
  18. return b;
  19. }
  20. static
  21. int
  22. lmax(int a, int b)
  23. {
  24. if(a > b)
  25. return a;
  26. return b;
  27. }
  28. #ifdef NOTUSED
  29. /*
  30. * Rather than line clip, we run the Bresenham loop over the full line,
  31. * and clip on each pixel. This is more expensive but means that
  32. * lines look the same regardless of how the windowing has tiled them.
  33. * For speed, we check for clipping outside the loop and make the
  34. * test easy when possible.
  35. */
  36. static
  37. void
  38. horline1(Memimage *dst, Point p0, Point p1, int srcval, Rectangle clipr)
  39. {
  40. int x, y, dy, deltay, deltax, maxx;
  41. int dd, easy, e, bpp, m, m0;
  42. uchar *d;
  43. deltax = p1.x - p0.x;
  44. deltay = p1.y - p0.y;
  45. dd = dst->width*sizeof(ulong);
  46. dy = 1;
  47. if(deltay < 0){
  48. dd = -dd;
  49. deltay = -deltay;
  50. dy = -1;
  51. }
  52. maxx = lmin(p1.x, clipr.max.x-1);
  53. bpp = dst->depth;
  54. m0 = 0xFF^(0xFF>>bpp);
  55. m = m0 >> (p0.x&(7/dst->depth))*bpp;
  56. easy = ptinrect(p0, clipr) && ptinrect(p1, clipr);
  57. e = 2*deltay - deltax;
  58. y = p0.y;
  59. d = byteaddr(dst, p0);
  60. deltay *= 2;
  61. deltax = deltay - 2*deltax;
  62. for(x=p0.x; x<=maxx; x++){
  63. if(easy || (clipr.min.x<=x && clipr.min.y<=y && y<clipr.max.y))
  64. *d ^= (*d^srcval) & m;
  65. if(e > 0){
  66. y += dy;
  67. d += dd;
  68. e += deltax;
  69. }else
  70. e += deltay;
  71. d++;
  72. m >>= bpp;
  73. if(m == 0)
  74. m = m0;
  75. }
  76. }
  77. static
  78. void
  79. verline1(Memimage *dst, Point p0, Point p1, int srcval, Rectangle clipr)
  80. {
  81. int x, y, deltay, deltax, maxy;
  82. int easy, e, bpp, m, m0, dd;
  83. uchar *d;
  84. deltax = p1.x - p0.x;
  85. deltay = p1.y - p0.y;
  86. dd = 1;
  87. if(deltax < 0){
  88. dd = -1;
  89. deltax = -deltax;
  90. }
  91. maxy = lmin(p1.y, clipr.max.y-1);
  92. bpp = dst->depth;
  93. m0 = 0xFF^(0xFF>>bpp);
  94. m = m0 >> (p0.x&(7/dst->depth))*bpp;
  95. easy = ptinrect(p0, clipr) && ptinrect(p1, clipr);
  96. e = 2*deltax - deltay;
  97. x = p0.x;
  98. d = byteaddr(dst, p0);
  99. deltax *= 2;
  100. deltay = deltax - 2*deltay;
  101. for(y=p0.y; y<=maxy; y++){
  102. if(easy || (clipr.min.y<=y && clipr.min.x<=x && x<clipr.max.x))
  103. *d ^= (*d^srcval) & m;
  104. if(e > 0){
  105. x += dd;
  106. d += dd;
  107. e += deltay;
  108. }else
  109. e += deltax;
  110. d += dst->width*sizeof(ulong);
  111. m >>= bpp;
  112. if(m == 0)
  113. m = m0;
  114. }
  115. }
  116. static
  117. void
  118. horliner(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr)
  119. {
  120. int x, y, sx, sy, deltay, deltax, minx, maxx;
  121. int bpp, m, m0;
  122. uchar *d, *s;
  123. deltax = p1.x - p0.x;
  124. deltay = p1.y - p0.y;
  125. sx = drawreplxy(src->r.min.x, src->r.max.x, p0.x+dsrc.x);
  126. minx = lmax(p0.x, clipr.min.x);
  127. maxx = lmin(p1.x, clipr.max.x-1);
  128. bpp = dst->depth;
  129. m0 = 0xFF^(0xFF>>bpp);
  130. m = m0 >> (minx&(7/dst->depth))*bpp;
  131. for(x=minx; x<=maxx; x++){
  132. y = p0.y + (deltay*(x-p0.x)+deltax/2)/deltax;
  133. if(clipr.min.y<=y && y<clipr.max.y){
  134. d = byteaddr(dst, Pt(x, y));
  135. sy = drawreplxy(src->r.min.y, src->r.max.y, y+dsrc.y);
  136. s = byteaddr(src, Pt(sx, sy));
  137. *d ^= (*d^*s) & m;
  138. }
  139. if(++sx >= src->r.max.x)
  140. sx = src->r.min.x;
  141. m >>= bpp;
  142. if(m == 0)
  143. m = m0;
  144. }
  145. }
  146. static
  147. void
  148. verliner(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr)
  149. {
  150. int x, y, sx, sy, deltay, deltax, miny, maxy;
  151. int bpp, m, m0;
  152. uchar *d, *s;
  153. deltax = p1.x - p0.x;
  154. deltay = p1.y - p0.y;
  155. sy = drawreplxy(src->r.min.y, src->r.max.y, p0.y+dsrc.y);
  156. miny = lmax(p0.y, clipr.min.y);
  157. maxy = lmin(p1.y, clipr.max.y-1);
  158. bpp = dst->depth;
  159. m0 = 0xFF^(0xFF>>bpp);
  160. for(y=miny; y<=maxy; y++){
  161. if(deltay == 0) /* degenerate line */
  162. x = p0.x;
  163. else
  164. x = p0.x + (deltax*(y-p0.y)+deltay/2)/deltay;
  165. if(clipr.min.x<=x && x<clipr.max.x){
  166. m = m0 >> (x&(7/dst->depth))*bpp;
  167. d = byteaddr(dst, Pt(x, y));
  168. sx = drawreplxy(src->r.min.x, src->r.max.x, x+dsrc.x);
  169. s = byteaddr(src, Pt(sx, sy));
  170. *d ^= (*d^*s) & m;
  171. }
  172. if(++sy >= src->r.max.y)
  173. sy = src->r.min.y;
  174. }
  175. }
  176. static
  177. void
  178. horline(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr)
  179. {
  180. int x, y, deltay, deltax, minx, maxx;
  181. int bpp, m, m0;
  182. uchar *d, *s;
  183. deltax = p1.x - p0.x;
  184. deltay = p1.y - p0.y;
  185. minx = lmax(p0.x, clipr.min.x);
  186. maxx = lmin(p1.x, clipr.max.x-1);
  187. bpp = dst->depth;
  188. m0 = 0xFF^(0xFF>>bpp);
  189. m = m0 >> (minx&(7/dst->depth))*bpp;
  190. for(x=minx; x<=maxx; x++){
  191. y = p0.y + (deltay*(x-p0.x)+deltay/2)/deltax;
  192. if(clipr.min.y<=y && y<clipr.max.y){
  193. d = byteaddr(dst, Pt(x, y));
  194. s = byteaddr(src, addpt(dsrc, Pt(x, y)));
  195. *d ^= (*d^*s) & m;
  196. }
  197. m >>= bpp;
  198. if(m == 0)
  199. m = m0;
  200. }
  201. }
  202. static
  203. void
  204. verline(Memimage *dst, Point p0, Point p1, Memimage *src, Point dsrc, Rectangle clipr)
  205. {
  206. int x, y, deltay, deltax, miny, maxy;
  207. int bpp, m, m0;
  208. uchar *d, *s;
  209. deltax = p1.x - p0.x;
  210. deltay = p1.y - p0.y;
  211. miny = lmax(p0.y, clipr.min.y);
  212. maxy = lmin(p1.y, clipr.max.y-1);
  213. bpp = dst->depth;
  214. m0 = 0xFF^(0xFF>>bpp);
  215. for(y=miny; y<=maxy; y++){
  216. if(deltay == 0) /* degenerate line */
  217. x = p0.x;
  218. else
  219. x = p0.x + deltax*(y-p0.y)/deltay;
  220. if(clipr.min.x<=x && x<clipr.max.x){
  221. m = m0 >> (x&(7/dst->depth))*bpp;
  222. d = byteaddr(dst, Pt(x, y));
  223. s = byteaddr(src, addpt(dsrc, Pt(x, y)));
  224. *d ^= (*d^*s) & m;
  225. }
  226. }
  227. }
  228. #endif /* NOTUSED */
  229. static Memimage*
  230. membrush(int radius)
  231. {
  232. static Memimage *brush;
  233. static int brushradius;
  234. if(brush==nil || brushradius!=radius){
  235. freememimage(brush);
  236. brush = allocmemimage(Rect(0, 0, 2*radius+1, 2*radius+1), memopaque->chan);
  237. if(brush != nil){
  238. memfillcolor(brush, DTransparent); /* zeros */
  239. memellipse(brush, Pt(radius, radius), radius, radius, -1, memopaque, Pt(radius, radius), S);
  240. }
  241. brushradius = radius;
  242. }
  243. return brush;
  244. }
  245. static
  246. void
  247. discend(Point p, int radius, Memimage *dst, Memimage *src, Point dsrc, int op)
  248. {
  249. Memimage *disc;
  250. Rectangle r;
  251. disc = membrush(radius);
  252. if(disc != nil){
  253. r.min.x = p.x - radius;
  254. r.min.y = p.y - radius;
  255. r.max.x = p.x + radius+1;
  256. r.max.y = p.y + radius+1;
  257. memdraw(dst, r, src, addpt(r.min, dsrc), disc, Pt(0,0), op);
  258. }
  259. }
  260. static
  261. void
  262. arrowend(Point tip, Point *pp, int end, int sin, int cos, int radius)
  263. {
  264. int x1, x2, x3;
  265. /* before rotation */
  266. if(end == Endarrow){
  267. x1 = Arrow1;
  268. x2 = Arrow2;
  269. x3 = Arrow3;
  270. }else{
  271. x1 = (end>>5) & 0x1FF; /* distance along line from end of line to tip */
  272. x2 = (end>>14) & 0x1FF; /* distance along line from barb to tip */
  273. x3 = (end>>23) & 0x1FF; /* distance perpendicular from edge of line to barb */
  274. }
  275. /* comments follow track of right-facing arrowhead */
  276. pp->x = tip.x+((2*radius+1)*sin/2-x1*cos); /* upper side of shaft */
  277. pp->y = tip.y-((2*radius+1)*cos/2+x1*sin);
  278. pp++;
  279. pp->x = tip.x+((2*radius+2*x3+1)*sin/2-x2*cos); /* upper barb */
  280. pp->y = tip.y-((2*radius+2*x3+1)*cos/2+x2*sin);
  281. pp++;
  282. pp->x = tip.x;
  283. pp->y = tip.y;
  284. pp++;
  285. pp->x = tip.x+(-(2*radius+2*x3+1)*sin/2-x2*cos); /* lower barb */
  286. pp->y = tip.y-(-(2*radius+2*x3+1)*cos/2+x2*sin);
  287. pp++;
  288. pp->x = tip.x+(-(2*radius+1)*sin/2-x1*cos); /* lower side of shaft */
  289. pp->y = tip.y+((2*radius+1)*cos/2-x1*sin);
  290. }
  291. void
  292. _memimageline(Memimage *dst, Point p0, Point p1, int end0, int end1, int radius, Memimage *src, Point sp, Rectangle clipr, int op)
  293. {
  294. /*
  295. * BUG: We should really really pick off purely horizontal and purely
  296. * vertical lines and handle them separately with calls to memimagedraw
  297. * on rectangles.
  298. */
  299. int hor;
  300. int sin, cos, dx, dy, t;
  301. Rectangle oclipr, r;
  302. Point q, pts[10], *pp, d;
  303. if(radius < 0)
  304. return;
  305. if(rectclip(&clipr, dst->r) == 0)
  306. return;
  307. if(rectclip(&clipr, dst->clipr) == 0)
  308. return;
  309. d = subpt(sp, p0);
  310. if(rectclip(&clipr, rectsubpt(src->clipr, d)) == 0)
  311. return;
  312. if((src->flags&Frepl)==0 && rectclip(&clipr, rectsubpt(src->r, d))==0)
  313. return;
  314. /* this means that only verline() handles degenerate lines (p0==p1) */
  315. hor = (abs(p1.x-p0.x) > abs(p1.y-p0.y));
  316. /*
  317. * Clipping is a little peculiar. We can't use Sutherland-Cohen
  318. * clipping because lines are wide. But this is probably just fine:
  319. * we do all math with the original p0 and p1, but clip when deciding
  320. * what pixels to draw. This means the layer code can call this routine,
  321. * using clipr to define the region being written, and get the same set
  322. * of pixels regardless of the dicing.
  323. */
  324. if((hor && p0.x>p1.x) || (!hor && p0.y>p1.y)){
  325. q = p0;
  326. p0 = p1;
  327. p1 = q;
  328. t = end0;
  329. end0 = end1;
  330. end1 = t;
  331. }
  332. if((p0.x == p1.x || p0.y == p1.y) && (end0&0x1F) == Endsquare && (end1&0x1F) == Endsquare){
  333. r.min = p0;
  334. r.max = p1;
  335. if(p0.x == p1.x){
  336. r.min.x -= radius;
  337. r.max.x += radius+1;
  338. }
  339. else{
  340. r.min.y -= radius;
  341. r.max.y += radius+1;
  342. }
  343. oclipr = dst->clipr;
  344. sp = addpt(r.min, d);
  345. dst->clipr = clipr;
  346. memimagedraw(dst, r, src, sp, memopaque, sp, op);
  347. dst->clipr = oclipr;
  348. return;
  349. }
  350. /* Hard: */
  351. /* draw thick line using polygon fill */
  352. icossin2(p1.x-p0.x, p1.y-p0.y, &cos, &sin);
  353. dx = (sin*(2*radius+1))/2;
  354. dy = (cos*(2*radius+1))/2;
  355. pp = pts;
  356. oclipr = dst->clipr;
  357. dst->clipr = clipr;
  358. q.x = ICOSSCALE*p0.x+ICOSSCALE/2-cos/2;
  359. q.y = ICOSSCALE*p0.y+ICOSSCALE/2-sin/2;
  360. switch(end0 & 0x1F){
  361. case Enddisc:
  362. discend(p0, radius, dst, src, d, op);
  363. /* fall through */
  364. case Endsquare:
  365. default:
  366. pp->x = q.x-dx;
  367. pp->y = q.y+dy;
  368. pp++;
  369. pp->x = q.x+dx;
  370. pp->y = q.y-dy;
  371. pp++;
  372. break;
  373. case Endarrow:
  374. arrowend(q, pp, end0, -sin, -cos, radius);
  375. _memfillpolysc(dst, pts, 5, ~0, src, addpt(pts[0], mulpt(d, ICOSSCALE)), 1, 10, 1, op);
  376. pp[1] = pp[4];
  377. pp += 2;
  378. }
  379. q.x = ICOSSCALE*p1.x+ICOSSCALE/2+cos/2;
  380. q.y = ICOSSCALE*p1.y+ICOSSCALE/2+sin/2;
  381. switch(end1 & 0x1F){
  382. case Enddisc:
  383. discend(p1, radius, dst, src, d, op);
  384. /* fall through */
  385. case Endsquare:
  386. default:
  387. pp->x = q.x+dx;
  388. pp->y = q.y-dy;
  389. pp++;
  390. pp->x = q.x-dx;
  391. pp->y = q.y+dy;
  392. pp++;
  393. break;
  394. case Endarrow:
  395. arrowend(q, pp, end1, sin, cos, radius);
  396. _memfillpolysc(dst, pp, 5, ~0, src, addpt(pp[0], mulpt(d, ICOSSCALE)), 1, 10, 1, op);
  397. pp[1] = pp[4];
  398. pp += 2;
  399. }
  400. _memfillpolysc(dst, pts, pp-pts, ~0, src, addpt(pts[0], mulpt(d, ICOSSCALE)), 0, 10, 1, op);
  401. dst->clipr = oclipr;
  402. return;
  403. }
  404. void
  405. memimageline(Memimage *dst, Point p0, Point p1, int end0, int end1, int radius, Memimage *src, Point sp, int op)
  406. {
  407. _memimageline(dst, p0, p1, end0, end1, radius, src, sp, dst->clipr, op);
  408. }
  409. /*
  410. * Simple-minded conservative code to compute bounding box of line.
  411. * Result is probably a little larger than it needs to be.
  412. */
  413. static
  414. void
  415. addbbox(Rectangle *r, Point p)
  416. {
  417. if(r->min.x > p.x)
  418. r->min.x = p.x;
  419. if(r->min.y > p.y)
  420. r->min.y = p.y;
  421. if(r->max.x < p.x+1)
  422. r->max.x = p.x+1;
  423. if(r->max.y < p.y+1)
  424. r->max.y = p.y+1;
  425. }
  426. int
  427. memlineendsize(int end)
  428. {
  429. int x3;
  430. if((end&0x3F) != Endarrow)
  431. return 0;
  432. if(end == Endarrow)
  433. x3 = Arrow3;
  434. else
  435. x3 = (end>>23) & 0x1FF;
  436. return x3;
  437. }
  438. Rectangle
  439. memlinebbox(Point p0, Point p1, int end0, int end1, int radius)
  440. {
  441. Rectangle r, r1;
  442. int extra;
  443. r.min.x = 10000000;
  444. r.min.y = 10000000;
  445. r.max.x = -10000000;
  446. r.max.y = -10000000;
  447. extra = lmax(memlineendsize(end0), memlineendsize(end1));
  448. r1 = insetrect(canonrect(Rpt(p0, p1)), -(radius+extra));
  449. addbbox(&r, r1.min);
  450. addbbox(&r, r1.max);
  451. return r;
  452. }