/* AbiSource Program Utilities * Copyright (C) 2002 Francis James Franklin * Copyright (C) 2002 AbiSource, Inc. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA * 02111-1307, USA. */ #include UT_Canvas::CanvasPolygon::CanvasPolygon () : m_max(0), m_count(0), m_x(0), m_y(0), m_PolygonRule(pr_EvenOdd), m_lc_y_min(0), m_lc_y_max(0), m_lc_max(0), m_lc_count(0), m_lc_x1(0), m_lc_y1(0), m_lc_x2(0), m_lc_y2(0), m_lc_xi(0) { // } UT_Canvas::CanvasPolygon::~CanvasPolygon () { FREEP (m_x); FREEP (m_y); FREEP (m_lc_x1); FREEP (m_lc_y1); FREEP (m_lc_x2); FREEP (m_lc_y2); FREEP (m_lc_xi); } bool UT_Canvas::CanvasPolygon::reset () { clearLineCache (); m_count = 0; return grow (); } bool UT_Canvas::CanvasPolygon::addPoint (UT_uint32 xvi_x, UT_uint32 xvi_y) { if (!grow ()) return false; clearLineCache (); m_x[m_count] = xvi_x; m_y[m_count] = xvi_y; m_count++; return true; } bool UT_Canvas::CanvasPolygon::grow () { if (m_count < m_max) return true; if (m_max == 0) { m_x = (UT_uint32 *) malloc (16 * sizeof (UT_uint32)); if (m_x == 0) { return false; } m_y = (UT_uint32 *) malloc (16 * sizeof (UT_uint32)); if (m_y == 0) { FREEP (m_x); return false; } m_max = 16; return true; } UT_uint32 * more = 0; more = (UT_uint32 *) realloc ((void *) m_x, (m_max + 16) * sizeof (UT_uint32)); if (more == 0) return false; m_x = more; more = (UT_uint32 *) realloc ((void *) m_y, (m_max + 16) * sizeof (UT_uint32)); if (more == 0) return false; m_y = more; m_max += 16; return true; } unsigned char UT_Canvas::CanvasPolygon::getAlpha (UT_uint32 xvi_x_min, UT_uint32 xvi_y_min, UT_uint32 xvi_x_max, UT_uint32 xvi_y_max) { if (!resetLineCache (xvi_y_min, xvi_y_max)) return 0x00; unsigned char alpha = 0x00; for (UT_uint32 xvi_y = xvi_y_min; xvi_y <= xvi_y_max; xvi_y++) { if (!calcIntercepts (xvi_y)) break; sortIntercepts (); unsigned char line_alpha = getLineAlpha (xvi_y, xvi_x_min, xvi_x_max); // } return alpha; } unsigned char UT_Canvas::CanvasPolygon::getLineAlpha (UT_uint32 xvi_y, UT_uint32 xvi_x_min, UT_uint32 xvi_x_max) { if (m_lc_count == 0) return 0x00; UT_uint32 x; for (UT_uint32 i = 0; i < m_lc_count; i++) { bool up = false; UT_sint32 xi = m_lc_xi[i]; if (xi < 0) { xi = - xi; up = true; } // } switch (m_PolygonRule) { case pr_EvenOdd: case pr_NonExterior: case pr_NonzeroWinding: break; } return 0; } bool UT_Canvas::CanvasPolygon::calcIntercepts (UT_uint32 y) { if ((y < m_lc_y_min) || (y > m_lc_y_max)) return false; for (UT_uint32 i = 0; i < m_lc_count; i++) { if (m_lc_x1[i] == m_lc_x2[i]) m_lc_xi[i] = m_lc_x1[i]; else m_lc_xi[i] = m_lc_x1[i] + ((y - m_lc_y1[i]) * (m_lc_x2[i] - m_lc_x1[i])) / (m_lc_y2[i] - m_lc_y1[i]); if ((m_lc_y1[i] <= y) && (m_lc_y2[i] >= y)) // line crossing up { m_lc_xi[i] = - m_lc_xi[i]; // i.e., invert 'sense' } } return true; } void UT_Canvas::CanvasPolygon::sortIntercepts () { // I'm not very good at sorting, so this next bit probably sucks // Need to sort on absolute value; also, [+n] cancels a [-n], if you like for (UT_uint32 i1 = 0; i1 < m_lc_count - 1; i1++) { UT_sint32 v1 = m_lc_xi[i1]; if (v1 < 0) v1 = - v1; for (UT_uint32 i2 = i1 + 1; i2 < m_lc_count; i2++) { UT_sint32 v2 = m_lc_xi[i2]; if (v2 < 0) v2 = - v2; if (v2 < v1) // swap { v1 = v2; UT_sint32 t = m_lc_xi[i2]; m_lc_xi[i2] = m_lc_xi[i1]; m_lc_xi[i1] = t; } } } } void UT_Canvas::CanvasPolygon::sortLineCache () { // I'm not very good at sorting, so this next bit probably sucks // Sort on absolute value of intercept for (UT_uint32 i1 = 0; i1 < m_lc_count - 1; i1++) { UT_sint32 v1 = m_lc_xi[i1]; if (v1 < 0) v1 = - v1; for (UT_uint32 i2 = i1 + 1; i2 < m_lc_count; i2++) { UT_sint32 v2 = m_lc_xi[i2]; if (v2 < 0) v2 = - v2; if (v2 < v1) // swap { v1 = v2; UT_sint32 t = m_lc_xi[i2]; m_lc_xi[i2] = m_lc_xi[i1]; m_lc_xi[i1] = t; t = m_lc_x1[i2]; m_lc_x1[i2] = m_lc_x1[i1]; m_lc_x1[i1] = t; t = m_lc_y1[i2]; m_lc_y1[i2] = m_lc_y1[i1]; m_lc_y1[i1] = t; t = m_lc_x2[i2]; m_lc_x2[i2] = m_lc_x2[i1]; m_lc_x2[i1] = t; t = m_lc_y2[i2]; m_lc_y2[i2] = m_lc_y2[i1]; m_lc_y2[i1] = t; } } } } void UT_Canvas::CanvasPolygon::clearLineCache () { m_lc_y_min = 0; m_lc_y_max = 0; m_lc_count = 0; } bool UT_Canvas::CanvasPolygon::resetLineCache (UT_uint32 xvi_y_min, UT_uint32 xvi_y_max) { if (m_count < 3) return false; // not a polygon if (xvi_y_min >= xvi_y_max) return false; if ((xvi_y_min == m_lc_y_min) && (xvi_y_max == m_lc_y_max)) return true; // LineCache is valid m_lc_y_min = xvi_y_min; m_lc_y_max = xvi_y_max; /* Build line cache */ bool success = true; UT_uint32 x_prev = m_x[m_count-1]; UT_uint32 y_prev = m_y[m_count-1]; for (UT_uint32 i = 0; i < m_count; i++) { UT_uint32 x = m_x[i]; UT_uint32 y = m_y[i]; if (y != y_prev) // ignore horizontal lines if ( ((y_prev >= m_lc_y_min) && (y <= m_lc_y_max)) || ((y >= m_lc_y_min) && (y_prev <= m_lc_y_max)) ) { /* This polygon edge is in scope of the scanline; add it to the cache */ success = growLineCache (); if (!success) break; m_lc_x1[m_lc_count] = x_prev; m_lc_y1[m_lc_count] = y_prev; m_lc_x2[m_lc_count] = x; m_lc_y2[m_lc_count] = y; m_lc_count++; } x_prev = x; y_prev = y; } if (success) success = calcIntercepts (m_lc_y_min); if (success) { sortLineCache (); } else { clearLineCache (); } return success; } bool UT_Canvas::CanvasPolygon::growLineCache () { if (m_lc_count < m_lc_max) return true; if (m_lc_max == 0) { m_lc_x1 = (UT_uint32 *) malloc (16 * sizeof (UT_uint32)); if (m_lc_x1 == 0) { return false; } m_lc_y1 = (UT_uint32 *) malloc (16 * sizeof (UT_uint32)); if (m_lc_y1 == 0) { FREEP (m_lc_x1); return false; } m_lc_x2 = (UT_uint32 *) malloc (16 * sizeof (UT_uint32)); if (m_lc_x2 == 0) { FREEP (m_lc_x1); FREEP (m_lc_y1); return false; } m_lc_y2 = (UT_uint32 *) malloc (16 * sizeof (UT_uint32)); if (m_lc_y2 == 0) { FREEP (m_lc_x1); FREEP (m_lc_y1); FREEP (m_lc_x2); return false; } m_lc_xi = (UT_sint32 *) malloc (16 * sizeof (UT_sint32)); if (m_lc_xi == 0) { FREEP (m_lc_x1); FREEP (m_lc_y1); FREEP (m_lc_x2); FREEP (m_lc_y2); return false; } m_lc_max = 16; return true; } UT_uint32 * more = 0; more = (UT_uint32 *) realloc ((void *) m_lc_x1, (m_lc_max + 16) * sizeof (UT_uint32)); if (more == 0) return false; m_lc_x1 = more; more = (UT_uint32 *) realloc ((void *) m_lc_y1, (m_lc_max + 16) * sizeof (UT_uint32)); if (more == 0) return false; m_lc_y1 = more; more = (UT_uint32 *) realloc ((void *) m_lc_x2, (m_lc_max + 16) * sizeof (UT_uint32)); if (more == 0) return false; m_lc_x2 = more; more = (UT_uint32 *) realloc ((void *) m_lc_y2, (m_lc_max + 16) * sizeof (UT_uint32)); if (more == 0) return false; m_lc_y2 = more; more = (UT_uint32 *) realloc ((void *) m_lc_xi, (m_lc_max + 16) * sizeof (UT_uint32)); if (more == 0) return false; m_lc_xi = more; m_lc_max += 16; return true; }