trap.cpp

Android 一些工具

        y_bot = max(y_bot, edges[2].y_bot);
		if (edges[0].y_top > y_top) {
            other = &edges[0];
            left  = &edges[2];
		} else if (edges[1].y_top > y_top) {
            other = &edges[1];
            right = &edges[2];
		}
    }

    c->init_y(c, y_top >> TRI_FRACTION_BITS);

    int32_t y_mid = min(left->y_bot, right->y_bot);
    triangle_sweep_edges( left, right, y_top, y_mid, c );

    // second scanline sweep loop, if necessary
    y_mid += TRI_ONE;
    if (y_mid <= y_bot) {
        ((left->y_bot == y_bot) ? right : left) = other;
        if (other->y_top < y_mid) {
            other->x += other->x_incr;
        }
        triangle_sweep_edges( left, right, y_mid, y_bot, c );
    }
}

void aa_trianglex(void* con,
        const GGLcoord* a, const GGLcoord* b, const GGLcoord* c)
{
    GGLcoord pts[6] = { a[0], a[1], b[0], b[1], c[0], c[1] };
    aapolyx(con, pts, 3);
}

// ----------------------------------------------------------------------------
#if 0
#pragma mark -
#endif

struct AAEdge
{
    GGLfixed x;         // edge position in 12.16 coordinates
    GGLfixed x_incr;    // on each y step, increment x by that amount
    GGLfixed y_incr;    // on each x step, increment y by that amount
    int16_t y_top;      // starting scanline, 12.4 format
    int16_t y_bot;      // starting scanline, 12.4 format
    void dump();
};

void AAEdge::dump()
{
    float tri  = 1.0f / TRI_ONE;
    float iter = 1.0f / (1<<TRI_ITERATORS_BITS);
    float fix  = 1.0f / FIXED_ONE;
    LOGD(   "x=%08x (%.3f), "
            "x_incr=%08x (%.3f), y_incr=%08x (%.3f), "
            "y_top=%08x (%.3f), y_bot=%08x (%.3f) ",
        x, x*fix,
        x_incr, x_incr*iter,
        y_incr, y_incr*iter,
        y_top, y_top*tri,
        y_bot, y_bot*tri );
}

// the following function sets up an edge, it assumes
// that ymin and ymax are in already in the 'reduced'
// format
static __attribute__((noinline))
void aa_edge_setup(
        AAEdge*         edges,
        int*            pcount,
        const GGLcoord* p1,
        const GGLcoord* p2,
        int32_t         ymin,
        int32_t         ymax )
{
    const GGLfixed*  top = p1;
    const GGLfixed*  bot = p2;
    AAEdge* edge = edges + *pcount;

    if (top[1] > bot[1])
        swap(top, bot);

    int  y1 = top[1];
    int  y2 = bot[1];
    int  dy = y2 - y1;

    if (dy==0 || y1>ymax || y2<ymin)
        return;

    if (y1 > ymin)
        ymin = y1;
    
    if (y2 < ymax)
        ymax = y2;

    const int x1 = top[0];
    const int dx = bot[0] - x1;
    const int shift = FIXED_BITS - TRI_FRACTION_BITS;

    // setup edge fields
    edge->x      = x1 << shift;
    edge->x_incr = 0;
    edge->y_top  = ymin;
    edge->y_bot  = ymax;
    edge->y_incr = 0x7FFFFFFF;

    if (ggl_likely(ymin <= ymax && dx)) {
        edge->x_incr = gglDivQ16(dx, dy);
        if (dx != 0) {
            edge->y_incr = abs(gglDivQ16(dy, dx));
        }
    }
    if (ggl_likely(y1 < ymin)) {
        int32_t xadjust = (edge->x_incr * (ymin-y1))
                >> (TRI_FRACTION_BITS + TRI_ITERATORS_BITS - FIXED_BITS);
        edge->x += xadjust;
    }
  
    ++*pcount;
}


typedef int (*compar_t)(const void*, const void*);
static int compare_edges(const AAEdge *e0, const AAEdge *e1) {
    if (e0->y_top > e1->y_top)      return 1;
    if (e0->y_top < e1->y_top)      return -1;
    if (e0->x > e1->x)              return 1;
    if (e0->x < e1->x)              return -1;
    if (e0->x_incr > e1->x_incr)    return 1;
    if (e0->x_incr < e1->x_incr)    return -1;
    return 0; // same edges, should never happen
}

static inline 
void SET_COVERAGE(int16_t*& p, int32_t value, ssize_t n)
{
    android_memset16((uint16_t*)p, value, n*2);
    p += n;
}

static inline 
void ADD_COVERAGE(int16_t*& p, int32_t value)
{
    value = *p + value;
    if (value >= 0x8000)
        value = 0x7FFF;
    *p++ = value;
}

static inline
void SUB_COVERAGE(int16_t*& p, int32_t value)
{
    value = *p - value;
    value &= ~(value>>31);
    *p++ = value;
}

void aapolyx(void* con,
        const GGLcoord* pts, int count)
{
    /*
     * NOTE: This routine assumes that the polygon has been clipped to the
     * viewport already, that is, no vertex lies outside of the framebuffer.
     * If this happens, the code below won't corrupt memory but the 
     * coverage values may not be correct.
     */
    
    GGL_CONTEXT(c, con);

    // we do only quads for now (it's used for thick lines)
    if ((count>4) || (count<2)) return;

    // take scissor into account
    const int xmin = c->state.scissor.left;
    const int xmax = c->state.scissor.right;
    if (xmin >= xmax) return;

    // generate edges from the vertices
    int32_t ymin = TRI_FROM_INT(c->state.scissor.top);
    int32_t ymax = TRI_FROM_INT(c->state.scissor.bottom);
    if (ymin >= ymax) return;

    AAEdge edges[4];
    int num_edges = 0;
    GGLcoord const * p = pts;
    for (int i=0 ; i<count-1 ; i++, p+=2) {
        aa_edge_setup(edges, &num_edges, p, p+2, ymin, ymax);
    }
    aa_edge_setup(edges, &num_edges, p, pts, ymin, ymax );
    if (ggl_unlikely(num_edges<2))
        return;

    // sort the edge list top to bottom, left to right.
    qsort(edges, num_edges, sizeof(AAEdge), (compar_t)compare_edges);

    int16_t* const covPtr = c->state.buffers.coverage;
    memset(covPtr+xmin, 0, (xmax-xmin)*sizeof(*covPtr));

    // now, sweep all edges in order
    // start with the 2 first edges. We know that they share their top
    // vertex, by construction.
    int i = 2;
    AAEdge* left  = &edges[0];
    AAEdge* right = &edges[1];
    int32_t yt = left->y_top;
    GGLfixed l = left->x;
    GGLfixed r = right->x;
    int retire = 0;
    int16_t* coverage;

    // at this point we can initialize the rasterizer    
    c->init_y(c, yt>>TRI_FRACTION_BITS);
    c->iterators.xl = xmax;
    c->iterators.xr = xmin;

    do {
        int32_t y = min(min(left->y_bot, right->y_bot), TRI_FLOOR(yt + TRI_ONE));
        const int32_t shift = TRI_FRACTION_BITS + TRI_ITERATORS_BITS - FIXED_BITS;
        const int cf_shift = (1 + TRI_FRACTION_BITS*2 + TRI_ITERATORS_BITS - 15);

        // compute xmin and xmax for the left edge
        GGLfixed l_min = gglMulAddx(left->x_incr, y - left->y_top, left->x, shift);
        GGLfixed l_max = l;
        l = l_min;
        if (l_min > l_max)
            swap(l_min, l_max);

        // compute xmin and xmax for the right edge
        GGLfixed r_min = gglMulAddx(right->x_incr, y - right->y_top, right->x, shift);
        GGLfixed r_max = r;
        r = r_min;
        if (r_min > r_max)
            swap(r_min, r_max);

        // make sure we're not touching coverage values outside of the
        // framebuffer
        l_min &= ~(l_min>>31);
        r_min &= ~(r_min>>31);
        l_max &= ~(l_max>>31);
        r_max &= ~(r_max>>31);
        if (gglFixedToIntFloor(l_min) >= xmax) l_min = gglIntToFixed(xmax)-1;
        if (gglFixedToIntFloor(r_min) >= xmax) r_min = gglIntToFixed(xmax)-1;
        if (gglFixedToIntCeil(l_max) >= xmax)  l_max = gglIntToFixed(xmax)-1;
        if (gglFixedToIntCeil(r_max) >= xmax)  r_max = gglIntToFixed(xmax)-1;

        // compute the integer versions of the above
        const GGLfixed l_min_i = gglFloorx(l_min);
        const GGLfixed l_max_i = gglCeilx (l_max);
        const GGLfixed r_min_i = gglFloorx(r_min);
        const GGLfixed r_max_i = gglCeilx (r_max);

        // clip horizontally using the scissor
        const int xml = max(xmin, gglFixedToIntFloor(l_min_i));
        const int xmr = min(xmax, gglFixedToIntFloor(r_max_i));

        // if we just stepped to a new scanline, render the previous one.
        // and clear the coverage buffer
        if (retire) {
            if (c->iterators.xl < c->iterators.xr)
                c->scanline(c);
            c->step_y(c);
            memset(covPtr+xmin, 0, (xmax-xmin)*sizeof(*covPtr));
            c->iterators.xl = xml;
            c->iterators.xr = xmr;
        } else {
            // update the horizontal range of this scanline
            c->iterators.xl = min(c->iterators.xl, xml);
            c->iterators.xr = max(c->iterators.xr, xmr);
        }

        coverage = covPtr + gglFixedToIntFloor(l_min_i);
        if (l_min_i == gglFloorx(l_max)) {
            
            /*
             *  fully traverse this pixel vertically
             *       l_max
             *  +-----/--+  yt
             *  |    /   |  
             *  |   /    |
             *  |  /     |
             *  +-/------+  y
             *   l_min  (l_min_i + TRI_ONE)
             */
              
            GGLfixed dx = l_max - l_min;
            int32_t dy = y - yt;
            int cf = gglMulx((dx >> 1) + (l_min_i + FIXED_ONE - l_max), dy,
                FIXED_BITS + TRI_FRACTION_BITS - 15);
            ADD_COVERAGE(coverage, cf);
            // all pixels on the right have cf = 1.0
        } else {
            /*
             *  spans several pixels in one scanline
             *            l_max
             *  +--------+--/-----+  yt
             *  |        |/       |
             *  |       /|        |
             *  |     /  |        |
             *  +---/----+--------+  y
             *   l_min (l_min_i + TRI_ONE)
             */

            // handle the first pixel separately...
            const int32_t y_incr = left->y_incr;
            int32_t dx = TRI_FROM_FIXED(l_min_i - l_min) + TRI_ONE;
            int32_t cf = (dx * dx * y_incr) >> cf_shift;
            ADD_COVERAGE(coverage, cf);

            // following pixels get covered by y_incr, but we need
            // to fix-up the cf to account for previous partial pixel
            dx = TRI_FROM_FIXED(l_min - l_min_i);
            cf -= (dx * dx * y_incr) >> cf_shift;
            for (int x = l_min_i+FIXED_ONE ; x < l_max_i-FIXED_ONE ; x += FIXED_ONE) {
                cf += y_incr >> (TRI_ITERATORS_BITS-15);
                ADD_COVERAGE(coverage, cf);
            }
            
            // and the last pixel
            dx = TRI_FROM_FIXED(l_max - l_max_i) - TRI_ONE;
            cf += (dx * dx * y_incr) >> cf_shift;
            ADD_COVERAGE(coverage, cf);
        }
        
        // now, fill up all fully covered pixels
        coverage = covPtr + gglFixedToIntFloor(l_max_i);
        int cf = ((y - yt) << (15 - TRI_FRACTION_BITS));
        if (ggl_likely(cf >= 0x8000)) {
            SET_COVERAGE(coverage, 0x7FFF, ((r_max - l_max_i)>>FIXED_BITS)+1);
        } else {
            for (int x=l_max_i ; x<r_max ; x+=FIXED_ONE) {
                ADD_COVERAGE(coverage, cf);
            }
        }
        
        // subtract the coverage of the right edge
        coverage = covPtr + gglFixedToIntFloor(r_min_i); 
        if (r_min_i == gglFloorx(r_max)) {
            GGLfixed dx = r_max - r_min;
            int32_t dy = y - yt;
            int cf = gglMulx((dx >> 1) + (r_min_i + FIXED_ONE - r_max), dy,
                FIXED_BITS + TRI_FRACTION_BITS - 15);
            SUB_COVERAGE(coverage, cf);
            // all pixels on the right have cf = 1.0
        } else {
            // handle the first pixel separately...
            const int32_t y_incr = right->y_incr;
            int32_t dx = TRI_FROM_FIXED(r_min_i - r_min) + TRI_ONE;
            int32_t cf = (dx * dx * y_incr) >> cf_shift;
            SUB_COVERAGE(coverage, cf);
            
            // following pixels get covered by y_incr, but we need
            // to fix-up the cf to account for previous partial pixel
            dx = TRI_FROM_FIXED(r_min - r_min_i);
            cf -= (dx * dx * y_incr) >> cf_shift;
            for (int x = r_min_i+FIXED_ONE ; x < r_max_i-FIXED_ONE ; x += FIXED_ONE) {
                cf += y_incr >> (TRI_ITERATORS_BITS-15);
                SUB_COVERAGE(coverage, cf);
            }
            
            // and the last pixel
            dx = TRI_FROM_FIXED(r_max - r_max_i) - TRI_ONE;
            cf += (dx * dx * y_incr) >> cf_shift;
            SUB_COVERAGE(coverage, cf);
        }

        // did we reach the end of an edge? if so, get a new one.
        if (y == left->y_bot || y == right->y_bot) {
            // bail out if we're done
            if (i>=num_edges)
                break;
            if (y == left->y_bot)
                left = &edges[i++];
            if (y == right->y_bot)
                right = &edges[i++];
        }

        // next scanline
        yt = y;
        
        // did we just finish a scanline?        
        retire = (y << (32-TRI_FRACTION_BITS)) == 0;
    } while (true);

    // render the last scanline
    if (c->iterators.xl < c->iterators.xr)
        c->scanline(c);
}

}; // namespace android