Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. #include "fitz.h"
  2.  
  3. /*
  4.  * polygon clipping
  5.  */
  6.  
  7. enum { IN, OUT, ENTER, LEAVE };
  8. enum { MAXV = 3 + 4 };
  9. enum { MAXN = 2 + FZ_MAX_COLORS };
  10.  
  11. static int clipx(float val, int ismax, float *v1, float *v2, int n)
  12. {
  13.         float t;
  14.         int i;
  15.         int v1o = ismax ? v1[0] > val : v1[0] < val;
  16.         int v2o = ismax ? v2[0] > val : v2[0] < val;
  17.         if (v1o + v2o == 0)
  18.                 return IN;
  19.         if (v1o + v2o == 2)
  20.                 return OUT;
  21.         if (v2o)
  22.         {
  23.                 t = (val - v1[0]) / (v2[0] - v1[0]);
  24.                 v2[0] = val;
  25.                 v2[1] = v1[1] + t * (v2[1] - v1[1]);
  26.                 for (i = 2; i < n; i++)
  27.                         v2[i] = v1[i] + t * (v2[i] - v1[i]);
  28.                 return LEAVE;
  29.         }
  30.         else
  31.         {
  32.                 t = (val - v2[0]) / (v1[0] - v2[0]);
  33.                 v1[0] = val;
  34.                 v1[1] = v2[1] + t * (v1[1] - v2[1]);
  35.                 for (i = 2; i < n; i++)
  36.                         v1[i] = v2[i] + t * (v1[i] - v2[i]);
  37.                 return ENTER;
  38.         }
  39. }
  40.  
  41. static int clipy(float val, int ismax, float *v1, float *v2, int n)
  42. {
  43.         float t;
  44.         int i;
  45.         int v1o = ismax ? v1[1] > val : v1[1] < val;
  46.         int v2o = ismax ? v2[1] > val : v2[1] < val;
  47.         if (v1o + v2o == 0)
  48.                 return IN;
  49.         if (v1o + v2o == 2)
  50.                 return OUT;
  51.         if (v2o)
  52.         {
  53.                 t = (val - v1[1]) / (v2[1] - v1[1]);
  54.                 v2[0] = v1[0] + t * (v2[0] - v1[0]);
  55.                 v2[1] = val;
  56.                 for (i = 2; i < n; i++)
  57.                         v2[i] = v1[i] + t * (v2[i] - v1[i]);
  58.                 return LEAVE;
  59.         }
  60.         else
  61.         {
  62.                 t = (val - v2[1]) / (v1[1] - v2[1]);
  63.                 v1[0] = v2[0] + t * (v1[0] - v2[0]);
  64.                 v1[1] = val;
  65.                 for (i = 2; i < n; i++)
  66.                         v1[i] = v2[i] + t * (v1[i] - v2[i]);
  67.                 return ENTER;
  68.         }
  69. }
  70.  
  71. static inline void copy_vert(float *dst, float *src, int n)
  72. {
  73.         while (n--)
  74.                 *dst++ = *src++;
  75. }
  76.  
  77. static int clip_poly(float src[MAXV][MAXN],
  78.         float dst[MAXV][MAXN], int len, int n,
  79.         float val, int isy, int ismax)
  80. {
  81.         float cv1[MAXN];
  82.         float cv2[MAXN];
  83.         int v1, v2, cp;
  84.         int r;
  85.  
  86.         v1 = len - 1;
  87.         cp = 0;
  88.  
  89.         for (v2 = 0; v2 < len; v2++)
  90.         {
  91.                 copy_vert(cv1, src[v1], n);
  92.                 copy_vert(cv2, src[v2], n);
  93.  
  94.                 if (isy)
  95.                         r = clipy(val, ismax, cv1, cv2, n);
  96.                 else
  97.                         r = clipx(val, ismax, cv1, cv2, n);
  98.  
  99.                 switch (r)
  100.                 {
  101.                 case IN:
  102.                         copy_vert(dst[cp++], cv2, n);
  103.                         break;
  104.                 case OUT:
  105.                         break;
  106.                 case LEAVE:
  107.                         copy_vert(dst[cp++], cv2, n);
  108.                         break;
  109.                 case ENTER:
  110.                         copy_vert(dst[cp++], cv1, n);
  111.                         copy_vert(dst[cp++], cv2, n);
  112.                         break;
  113.                 }
  114.                 v1 = v2;
  115.         }
  116.  
  117.         return cp;
  118. }
  119.  
  120. /*
  121.  * gouraud shaded polygon scan conversion
  122.  */
  123.  
  124. static void paint_scan(fz_pixmap *pix, int y, int x1, int x2, int *v1, int *v2, int n)
  125. {
  126.         unsigned char *p = pix->samples + ((y - pix->y) * pix->w + (x1 - pix->x)) * pix->n;
  127.         int v[FZ_MAX_COLORS];
  128.         int dv[FZ_MAX_COLORS];
  129.         int w = x2 - x1;
  130.         int k;
  131.  
  132.         assert(w >= 0);
  133.         assert(y >= pix->y);
  134.         assert(y < pix->y + pix->h);
  135.         assert(x1 >= pix->x);
  136.         assert(x2 <= pix->x + pix->w);
  137.  
  138.         if (w == 0)
  139.                 return;
  140.  
  141.         for (k = 0; k < n; k++)
  142.         {
  143.                 v[k] = v1[k];
  144.                 dv[k] = (v2[k] - v1[k]) / w;
  145.         }
  146.  
  147.         while (w--)
  148.         {
  149.                 for (k = 0; k < n; k++)
  150.                 {
  151.                         *p++ = v[k] >> 16;
  152.                         v[k] += dv[k];
  153.                 }
  154.                 *p++ = 255;
  155.         }
  156. }
  157.  
  158. static int find_next(int gel[MAXV][MAXN], int len, int a, int *s, int *e, int d)
  159. {
  160.         int b;
  161.  
  162.         while (1)
  163.         {
  164.                 b = a + d;
  165.                 if (b == len)
  166.                         b = 0;
  167.                 if (b == -1)
  168.                         b = len - 1;
  169.  
  170.                 if (gel[b][1] == gel[a][1])
  171.                 {
  172.                         a = b;
  173.                         continue;
  174.                 }
  175.  
  176.                 if (gel[b][1] > gel[a][1])
  177.                 {
  178.                         *s = a;
  179.                         *e = b;
  180.                         return 0;
  181.                 }
  182.  
  183.                 return 1;
  184.         }
  185. }
  186.  
  187. static void load_edge(int gel[MAXV][MAXN], int s, int e, int *ael, int *del, int n)
  188. {
  189.         int swp, k, dy;
  190.  
  191.         if (gel[s][1] > gel[e][1])
  192.         {
  193.                 swp = s; s = e; e = swp;
  194.         }
  195.  
  196.         dy = gel[e][1] - gel[s][1];
  197.  
  198.         ael[0] = gel[s][0];
  199.         del[0] = (gel[e][0] - gel[s][0]) / dy;
  200.         for (k = 2; k < n; k++)
  201.         {
  202.                 ael[k] = gel[s][k];
  203.                 del[k] = (gel[e][k] - gel[s][k]) / dy;
  204.         }
  205. }
  206.  
  207. static inline void step_edge(int *ael, int *del, int n)
  208. {
  209.         int k;
  210.         ael[0] += del[0];
  211.         for (k = 2; k < n; k++)
  212.                 ael[k] += del[k];
  213. }
  214.  
  215. static void
  216. fz_paint_triangle(fz_pixmap *pix, float *av, float *bv, float *cv, int n, fz_bbox bbox)
  217. {
  218.         float poly[MAXV][MAXN];
  219.         float temp[MAXV][MAXN];
  220.         float cx0 = bbox.x0;
  221.         float cy0 = bbox.y0;
  222.         float cx1 = bbox.x1;
  223.         float cy1 = bbox.y1;
  224.  
  225.         int gel[MAXV][MAXN];
  226.         int ael[2][MAXN];
  227.         int del[2][MAXN];
  228.         int y, s0, s1, e0, e1;
  229.         int top, bot, len;
  230.  
  231.         int i, k;
  232.  
  233.         copy_vert(poly[0], av, n);
  234.         copy_vert(poly[1], bv, n);
  235.         copy_vert(poly[2], cv, n);
  236.  
  237.         len = clip_poly(poly, temp, 3, n, cx0, 0, 0);
  238.         len = clip_poly(temp, poly, len, n, cx1, 0, 1);
  239.         len = clip_poly(poly, temp, len, n, cy0, 1, 0);
  240.         len = clip_poly(temp, poly, len, n, cy1, 1, 1);
  241.  
  242.         if (len < 3)
  243.                 return;
  244.  
  245.         for (i = 0; i < len; i++)
  246.         {
  247.                 gel[i][0] = floorf(poly[i][0] + 0.5f) * 65536; /* trunc and fix */
  248.                 gel[i][1] = floorf(poly[i][1] + 0.5f);  /* y is not fixpoint */
  249.                 for (k = 2; k < n; k++)
  250.                         gel[i][k] = poly[i][k] * 65536; /* fix with precision */
  251.         }
  252.  
  253.         top = bot = 0;
  254.         for (i = 0; i < len; i++)
  255.         {
  256.                 if (gel[i][1] < gel[top][1])
  257.                         top = i;
  258.                 if (gel[i][1] > gel[bot][1])
  259.                         bot = i;
  260.         }
  261.  
  262.         if (gel[bot][1] - gel[top][1] == 0)
  263.                 return;
  264.  
  265.         y = gel[top][1];
  266.  
  267.         if (find_next(gel, len, top, &s0, &e0, 1))
  268.                 return;
  269.         if (find_next(gel, len, top, &s1, &e1, -1))
  270.                 return;
  271.  
  272.         load_edge(gel, s0, e0, ael[0], del[0], n);
  273.         load_edge(gel, s1, e1, ael[1], del[1], n);
  274.  
  275.         while (1)
  276.         {
  277.                 int x0 = ael[0][0] >> 16;
  278.                 int x1 = ael[1][0] >> 16;
  279.  
  280.                 if (ael[0][0] < ael[1][0])
  281.                         paint_scan(pix, y, x0, x1, ael[0]+2, ael[1]+2, n-2);
  282.                 else
  283.                         paint_scan(pix, y, x1, x0, ael[1]+2, ael[0]+2, n-2);
  284.  
  285.                 step_edge(ael[0], del[0], n);
  286.                 step_edge(ael[1], del[1], n);
  287.                 y ++;
  288.  
  289.                 if (y >= gel[e0][1])
  290.                 {
  291.                         if (find_next(gel, len, e0, &s0, &e0, 1))
  292.                                 return;
  293.                         load_edge(gel, s0, e0, ael[0], del[0], n);
  294.                 }
  295.  
  296.                 if (y >= gel[e1][1])
  297.                 {
  298.                         if (find_next(gel, len, e1, &s1, &e1, -1))
  299.                                 return;
  300.                         load_edge(gel, s1, e1, ael[1], del[1], n);
  301.                 }
  302.         }
  303. }
  304.  
  305. static void
  306. fz_paint_quad(fz_pixmap *pix,
  307.                 fz_point p0, fz_point p1, fz_point p2, fz_point p3,
  308.                 float c0, float c1, float c2, float c3,
  309.                 int n, fz_bbox bbox)
  310. {
  311.         float v[4][3];
  312.  
  313.         v[0][0] = p0.x;
  314.         v[0][1] = p0.y;
  315.         v[0][2] = c0;
  316.  
  317.         v[1][0] = p1.x;
  318.         v[1][1] = p1.y;
  319.         v[1][2] = c1;
  320.  
  321.         v[2][0] = p2.x;
  322.         v[2][1] = p2.y;
  323.         v[2][2] = c2;
  324.  
  325.         v[3][0] = p3.x;
  326.         v[3][1] = p3.y;
  327.         v[3][2] = c3;
  328.  
  329.         fz_paint_triangle(pix, v[0], v[2], v[3], n, bbox);
  330.         fz_paint_triangle(pix, v[0], v[3], v[1], n, bbox);
  331. }
  332.  
  333. /*
  334.  * linear, radial and mesh painting
  335.  */
  336.  
  337. #define HUGENUM 32000 /* how far to extend axial/radial shadings */
  338. #define RADSEGS 32 /* how many segments to generate for radial meshes */
  339.  
  340. static fz_point
  341. fz_point_on_circle(fz_point p, float r, float theta)
  342. {
  343.         p.x = p.x + cosf(theta) * r;
  344.         p.y = p.y + sinf(theta) * r;
  345.  
  346.         return p;
  347. }
  348.  
  349. static void
  350. fz_paint_linear(fz_shade *shade, fz_matrix ctm, fz_pixmap *dest, fz_bbox bbox)
  351. {
  352.         fz_point p0, p1;
  353.         fz_point v0, v1, v2, v3;
  354.         fz_point e0, e1;
  355.         float theta;
  356.  
  357.         p0.x = shade->mesh[0];
  358.         p0.y = shade->mesh[1];
  359.         p0 = fz_transform_point(ctm, p0);
  360.  
  361.         p1.x = shade->mesh[3];
  362.         p1.y = shade->mesh[4];
  363.         p1 = fz_transform_point(ctm, p1);
  364.  
  365.         theta = atan2f(p1.y - p0.y, p1.x - p0.x);
  366.         theta += (float)M_PI * 0.5f;
  367.  
  368.         v0 = fz_point_on_circle(p0, HUGENUM, theta);
  369.         v1 = fz_point_on_circle(p1, HUGENUM, theta);
  370.         v2 = fz_point_on_circle(p0, -HUGENUM, theta);
  371.         v3 = fz_point_on_circle(p1, -HUGENUM, theta);
  372.  
  373.         fz_paint_quad(dest, v0, v1, v2, v3, 0, 255, 0, 255, 3, bbox);
  374.  
  375.         if (shade->extend[0])
  376.         {
  377.                 e0.x = v0.x - (p1.x - p0.x) * HUGENUM;
  378.                 e0.y = v0.y - (p1.y - p0.y) * HUGENUM;
  379.  
  380.                 e1.x = v2.x - (p1.x - p0.x) * HUGENUM;
  381.                 e1.y = v2.y - (p1.y - p0.y) * HUGENUM;
  382.  
  383.                 fz_paint_quad(dest, e0, e1, v0, v2, 0, 0, 0, 0, 3, bbox);
  384.         }
  385.  
  386.         if (shade->extend[1])
  387.         {
  388.                 e0.x = v1.x + (p1.x - p0.x) * HUGENUM;
  389.                 e0.y = v1.y + (p1.y - p0.y) * HUGENUM;
  390.  
  391.                 e1.x = v3.x + (p1.x - p0.x) * HUGENUM;
  392.                 e1.y = v3.y + (p1.y - p0.y) * HUGENUM;
  393.  
  394.                 fz_paint_quad(dest, e0, e1, v1, v3, 255, 255, 255, 255, 3, bbox);
  395.         }
  396. }
  397.  
  398. static void
  399. fz_paint_annulus(fz_matrix ctm,
  400.                 fz_point p0, float r0, float c0,
  401.                 fz_point p1, float r1, float c1,
  402.                 fz_pixmap *dest, fz_bbox bbox)
  403. {
  404.         fz_point t0, t1, t2, t3, b0, b1, b2, b3;
  405.         float theta, step;
  406.         int i;
  407.  
  408.         theta = atan2f(p1.y - p0.y, p1.x - p0.x);
  409.         step = (float)M_PI * 2 / RADSEGS;
  410.  
  411.         for (i = 0; i < RADSEGS / 2; i++)
  412.         {
  413.                 t0 = fz_point_on_circle(p0, r0, theta + i * step);
  414.                 t1 = fz_point_on_circle(p0, r0, theta + i * step + step);
  415.                 t2 = fz_point_on_circle(p1, r1, theta + i * step);
  416.                 t3 = fz_point_on_circle(p1, r1, theta + i * step + step);
  417.                 b0 = fz_point_on_circle(p0, r0, theta - i * step);
  418.                 b1 = fz_point_on_circle(p0, r0, theta - i * step - step);
  419.                 b2 = fz_point_on_circle(p1, r1, theta - i * step);
  420.                 b3 = fz_point_on_circle(p1, r1, theta - i * step - step);
  421.  
  422.                 t0 = fz_transform_point(ctm, t0);
  423.                 t1 = fz_transform_point(ctm, t1);
  424.                 t2 = fz_transform_point(ctm, t2);
  425.                 t3 = fz_transform_point(ctm, t3);
  426.                 b0 = fz_transform_point(ctm, b0);
  427.                 b1 = fz_transform_point(ctm, b1);
  428.                 b2 = fz_transform_point(ctm, b2);
  429.                 b3 = fz_transform_point(ctm, b3);
  430.  
  431.                 fz_paint_quad(dest, t0, t1, t2, t3, c0, c0, c1, c1, 3, bbox);
  432.                 fz_paint_quad(dest, b0, b1, b2, b3, c0, c0, c1, c1, 3, bbox);
  433.         }
  434. }
  435.  
  436. static void
  437. fz_paint_radial(fz_shade *shade, fz_matrix ctm, fz_pixmap *dest, fz_bbox bbox)
  438. {
  439.         fz_point p0, p1;
  440.         float r0, r1;
  441.         fz_point e;
  442.         float er, rs;
  443.  
  444.         p0.x = shade->mesh[0];
  445.         p0.y = shade->mesh[1];
  446.         r0 = shade->mesh[2];
  447.  
  448.         p1.x = shade->mesh[3];
  449.         p1.y = shade->mesh[4];
  450.         r1 = shade->mesh[5];
  451.  
  452.         if (shade->extend[0])
  453.         {
  454.                 if (r0 < r1)
  455.                         rs = r0 / (r0 - r1);
  456.                 else
  457.                         rs = -HUGENUM;
  458.  
  459.                 e.x = p0.x + (p1.x - p0.x) * rs;
  460.                 e.y = p0.y + (p1.y - p0.y) * rs;
  461.                 er = r0 + (r1 - r0) * rs;
  462.  
  463.                 fz_paint_annulus(ctm, e, er, 0, p0, r0, 0, dest, bbox);
  464.         }
  465.  
  466.         fz_paint_annulus(ctm, p0, r0, 0, p1, r1, 255, dest, bbox);
  467.  
  468.         if (shade->extend[1])
  469.         {
  470.                 if (r0 > r1)
  471.                         rs = r1 / (r1 - r0);
  472.                 else
  473.                         rs = -HUGENUM;
  474.  
  475.                 e.x = p1.x + (p0.x - p1.x) * rs;
  476.                 e.y = p1.y + (p0.y - p1.y) * rs;
  477.                 er = r1 + (r0 - r1) * rs;
  478.  
  479.                 fz_paint_annulus(ctm, p1, r1, 255, e, er, 255, dest, bbox);
  480.         }
  481. }
  482.  
  483. static void
  484. fz_paint_mesh(fz_shade *shade, fz_matrix ctm, fz_pixmap *dest, fz_bbox bbox)
  485. {
  486.         float tri[3][MAXN];
  487.         fz_point p;
  488.         float *mesh;
  489.         int ntris;
  490.         int i, k;
  491.  
  492.         mesh = shade->mesh;
  493.  
  494.         if (shade->use_function)
  495.                 ntris = shade->mesh_len / 9;
  496.         else
  497.                 ntris = shade->mesh_len / ((2 + shade->colorspace->n) * 3);
  498.  
  499.         while (ntris--)
  500.         {
  501.                 for (k = 0; k < 3; k++)
  502.                 {
  503.                         p.x = *mesh++;
  504.                         p.y = *mesh++;
  505.                         p = fz_transform_point(ctm, p);
  506.                         tri[k][0] = p.x;
  507.                         tri[k][1] = p.y;
  508.                         if (shade->use_function)
  509.                                 tri[k][2] = *mesh++ * 255;
  510.                         else
  511.                         {
  512.                                 fz_convert_color(shade->colorspace, mesh, dest->colorspace, tri[k] + 2);
  513.                                 for (i = 0; i < dest->colorspace->n; i++)
  514.                                         tri[k][i + 2] *= 255;
  515.                                 mesh += shade->colorspace->n;
  516.                         }
  517.                 }
  518.                 fz_paint_triangle(dest, tri[0], tri[1], tri[2], 2 + dest->colorspace->n, bbox);
  519.         }
  520. }
  521.  
  522. void
  523. fz_paint_shade(fz_shade *shade, fz_matrix ctm, fz_pixmap *dest, fz_bbox bbox)
  524. {
  525.         unsigned char clut[256][FZ_MAX_COLORS];
  526.         fz_pixmap *temp, *conv;
  527.         float color[FZ_MAX_COLORS];
  528.         int i, k;
  529.  
  530.         ctm = fz_concat(shade->matrix, ctm);
  531.  
  532.         if (shade->use_function)
  533.         {
  534.                 for (i = 0; i < 256; i++)
  535.                 {
  536.                         fz_convert_color(shade->colorspace, shade->function[i], dest->colorspace, color);
  537.                         for (k = 0; k < dest->colorspace->n; k++)
  538.                                 clut[i][k] = color[k] * 255;
  539.                         clut[i][k] = shade->function[i][shade->colorspace->n] * 255;
  540.                 }
  541.                 conv = fz_new_pixmap_with_rect(dest->colorspace, bbox);
  542.                 temp = fz_new_pixmap_with_rect(fz_device_gray, bbox);
  543.                 fz_clear_pixmap(temp);
  544.         }
  545.         else
  546.         {
  547.                 temp = dest;
  548.         }
  549.  
  550.         switch (shade->type)
  551.         {
  552.         case FZ_LINEAR: fz_paint_linear(shade, ctm, temp, bbox); break;
  553.         case FZ_RADIAL: fz_paint_radial(shade, ctm, temp, bbox); break;
  554.         case FZ_MESH: fz_paint_mesh(shade, ctm, temp, bbox); break;
  555.         }
  556.  
  557.         if (shade->use_function)
  558.         {
  559.                 unsigned char *s = temp->samples;
  560.                 unsigned char *d = conv->samples;
  561.                 int len = temp->w * temp->h;
  562.                 while (len--)
  563.                 {
  564.                         int v = *s++;
  565.                         int a = fz_mul255(*s++, clut[v][conv->n - 1]);
  566.                         for (k = 0; k < conv->n - 1; k++)
  567.                                 *d++ = fz_mul255(clut[v][k], a);
  568.                         *d++ = a;
  569.                 }
  570.                 fz_paint_pixmap(dest, conv, 255);
  571.                 fz_drop_pixmap(conv);
  572.                 fz_drop_pixmap(temp);
  573.         }
  574. }
  575.