1/* libs/pixelflinger/trap.cpp 2** 3** Copyright 2006, The Android Open Source Project 4** 5** Licensed under the Apache License, Version 2.0 (the "License"); 6** you may not use this file except in compliance with the License. 7** You may obtain a copy of the License at 8** 9** http://www.apache.org/licenses/LICENSE-2.0 10** 11** Unless required by applicable law or agreed to in writing, software 12** distributed under the License is distributed on an "AS IS" BASIS, 13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14** See the License for the specific language governing permissions and 15** limitations under the License. 16*/ 17 18#define LOG_TAG "pixelflinger-trap" 19 20#include <assert.h> 21#include <stdio.h> 22#include <stdlib.h> 23 24#include <cutils/memory.h> 25#include <log/log.h> 26 27#include "trap.h" 28#include "picker.h" 29 30namespace android { 31 32// ---------------------------------------------------------------------------- 33 34// enable to see triangles edges 35#define DEBUG_TRANGLES 0 36 37// ---------------------------------------------------------------------------- 38 39static void pointx_validate(void *con, const GGLcoord* c, GGLcoord r); 40static void pointx(void *con, const GGLcoord* c, GGLcoord r); 41static void aa_pointx(void *con, const GGLcoord* c, GGLcoord r); 42static void aa_nice_pointx(void *con, const GGLcoord* c, GGLcoord r); 43 44static void linex_validate(void *con, const GGLcoord* v0, const GGLcoord* v1, GGLcoord w); 45static void linex(void *con, const GGLcoord* v0, const GGLcoord* v1, GGLcoord w); 46static void aa_linex(void *con, const GGLcoord* v0, const GGLcoord* v1, GGLcoord w); 47 48static void recti_validate(void* c, GGLint l, GGLint t, GGLint r, GGLint b); 49static void recti(void* c, GGLint l, GGLint t, GGLint r, GGLint b); 50 51static void trianglex_validate(void*, 52 const GGLcoord*, const GGLcoord*, const GGLcoord*); 53static void trianglex_small(void*, 54 const GGLcoord*, const GGLcoord*, const GGLcoord*); 55static void trianglex_big(void*, 56 const GGLcoord*, const GGLcoord*, const GGLcoord*); 57static void aa_trianglex(void*, 58 const GGLcoord*, const GGLcoord*, const GGLcoord*); 59static void trianglex_debug(void* con, 60 const GGLcoord*, const GGLcoord*, const GGLcoord*); 61 62static void aapolyx(void* con, 63 const GGLcoord* pts, int count); 64 65static inline int min(int a, int b) CONST; 66static inline int max(int a, int b) CONST; 67static inline int min(int a, int b, int c) CONST; 68static inline int max(int a, int b, int c) CONST; 69 70// ---------------------------------------------------------------------------- 71#if 0 72#pragma mark - 73#pragma mark Tools 74#endif 75 76inline int min(int a, int b) { 77 return a<b ? a : b; 78} 79inline int max(int a, int b) { 80 return a<b ? b : a; 81} 82inline int min(int a, int b, int c) { 83 return min(a,min(b,c)); 84} 85inline int max(int a, int b, int c) { 86 return max(a,max(b,c)); 87} 88 89template <typename T> 90static inline void swap(T& a, T& b) { 91 T t(a); 92 a = b; 93 b = t; 94} 95 96static void 97triangle_dump_points( const GGLcoord* v0, 98 const GGLcoord* v1, 99 const GGLcoord* v2 ) 100{ 101 float tri = 1.0f / TRI_ONE; 102 ALOGD(" P0=(%.3f, %.3f) [%08x, %08x]\n" 103 " P1=(%.3f, %.3f) [%08x, %08x]\n" 104 " P2=(%.3f, %.3f) [%08x, %08x]\n", 105 v0[0]*tri, v0[1]*tri, v0[0], v0[1], 106 v1[0]*tri, v1[1]*tri, v1[0], v1[1], 107 v2[0]*tri, v2[1]*tri, v2[0], v2[1] ); 108} 109 110// ---------------------------------------------------------------------------- 111#if 0 112#pragma mark - 113#pragma mark Misc 114#endif 115 116void ggl_init_trap(context_t* c) 117{ 118 ggl_state_changed(c, GGL_PIXEL_PIPELINE_STATE|GGL_TMU_STATE|GGL_CB_STATE); 119} 120 121void ggl_state_changed(context_t* c, int flags) 122{ 123 if (ggl_likely(!c->dirty)) { 124 c->procs.pointx = pointx_validate; 125 c->procs.linex = linex_validate; 126 c->procs.recti = recti_validate; 127 c->procs.trianglex = trianglex_validate; 128 } 129 c->dirty |= uint32_t(flags); 130} 131 132// ---------------------------------------------------------------------------- 133#if 0 134#pragma mark - 135#pragma mark Point 136#endif 137 138void pointx_validate(void *con, const GGLcoord* v, GGLcoord rad) 139{ 140 GGL_CONTEXT(c, con); 141 ggl_pick(c); 142 if (c->state.needs.p & GGL_NEED_MASK(P_AA)) { 143 if (c->state.enables & GGL_ENABLE_POINT_AA_NICE) { 144 c->procs.pointx = aa_nice_pointx; 145 } else { 146 c->procs.pointx = aa_pointx; 147 } 148 } else { 149 c->procs.pointx = pointx; 150 } 151 c->procs.pointx(con, v, rad); 152} 153 154void pointx(void *con, const GGLcoord* v, GGLcoord rad) 155{ 156 GGL_CONTEXT(c, con); 157 GGLcoord halfSize = TRI_ROUND(rad) >> 1; 158 if (halfSize == 0) 159 halfSize = TRI_HALF; 160 GGLcoord xc = v[0]; 161 GGLcoord yc = v[1]; 162 if (halfSize & TRI_HALF) { // size odd 163 xc = TRI_FLOOR(xc) + TRI_HALF; 164 yc = TRI_FLOOR(yc) + TRI_HALF; 165 } else { // size even 166 xc = TRI_ROUND(xc); 167 yc = TRI_ROUND(yc); 168 } 169 GGLint l = (xc - halfSize) >> TRI_FRACTION_BITS; 170 GGLint t = (yc - halfSize) >> TRI_FRACTION_BITS; 171 GGLint r = (xc + halfSize) >> TRI_FRACTION_BITS; 172 GGLint b = (yc + halfSize) >> TRI_FRACTION_BITS; 173 recti(c, l, t, r, b); 174} 175 176// This way of computing the coverage factor, is more accurate and gives 177// better results for small circles, but it is also a lot slower. 178// Here we use super-sampling. 179static int32_t coverageNice(GGLcoord x, GGLcoord y, 180 GGLcoord rmin, GGLcoord rmax, GGLcoord rr) 181{ 182 const GGLcoord d2 = x*x + y*y; 183 if (d2 >= rmax) return 0; 184 if (d2 < rmin) return 0x7FFF; 185 186 const int kSamples = 4; 187 const int kInc = 4; // 1/4 = 0.25 188 const int kCoverageUnit = 1; // 1/(4^2) = 0.0625 189 const GGLcoord kCoordOffset = -6; // -0.375 190 191 int hits = 0; 192 int x_sample = x + kCoordOffset; 193 for (int i=0 ; i<kSamples ; i++, x_sample += kInc) { 194 const int xval = rr - (x_sample * x_sample); 195 int y_sample = y + kCoordOffset; 196 for (int j=0 ; j<kSamples ; j++, y_sample += kInc) { 197 if (xval - (y_sample * y_sample) > 0) 198 hits += kCoverageUnit; 199 } 200 } 201 return min(0x7FFF, hits << (15 - kSamples)); 202} 203 204 205void aa_nice_pointx(void *con, const GGLcoord* v, GGLcoord size) 206{ 207 GGL_CONTEXT(c, con); 208 209 GGLcoord rad = ((size + 1)>>1); 210 GGLint l = (v[0] - rad) >> TRI_FRACTION_BITS; 211 GGLint t = (v[1] - rad) >> TRI_FRACTION_BITS; 212 GGLint r = (v[0] + rad + (TRI_ONE-1)) >> TRI_FRACTION_BITS; 213 GGLint b = (v[1] + rad + (TRI_ONE-1)) >> TRI_FRACTION_BITS; 214 GGLcoord xstart = TRI_FROM_INT(l) - v[0] + TRI_HALF; 215 GGLcoord ystart = TRI_FROM_INT(t) - v[1] + TRI_HALF; 216 217 // scissor... 218 if (l < GGLint(c->state.scissor.left)) { 219 xstart += TRI_FROM_INT(c->state.scissor.left-l); 220 l = GGLint(c->state.scissor.left); 221 } 222 if (t < GGLint(c->state.scissor.top)) { 223 ystart += TRI_FROM_INT(c->state.scissor.top-t); 224 t = GGLint(c->state.scissor.top); 225 } 226 if (r > GGLint(c->state.scissor.right)) { 227 r = GGLint(c->state.scissor.right); 228 } 229 if (b > GGLint(c->state.scissor.bottom)) { 230 b = GGLint(c->state.scissor.bottom); 231 } 232 233 int xc = r - l; 234 int yc = b - t; 235 if (xc>0 && yc>0) { 236 int16_t* covPtr = c->state.buffers.coverage; 237 const int32_t sqr2Over2 = 0xC; // rounded up 238 GGLcoord rr = rad*rad; 239 GGLcoord rmin = (rad - sqr2Over2)*(rad - sqr2Over2); 240 GGLcoord rmax = (rad + sqr2Over2)*(rad + sqr2Over2); 241 GGLcoord y = ystart; 242 c->iterators.xl = l; 243 c->iterators.xr = r; 244 c->init_y(c, t); 245 do { 246 // compute coverage factors for each pixel 247 GGLcoord x = xstart; 248 for (int i=l ; i<r ; i++) { 249 covPtr[i] = coverageNice(x, y, rmin, rmax, rr); 250 x += TRI_ONE; 251 } 252 y += TRI_ONE; 253 c->scanline(c); 254 c->step_y(c); 255 } while (--yc); 256 } 257} 258 259// This is a cheap way of computing the coverage factor for a circle. 260// We just lerp between the circles of radii r-sqrt(2)/2 and r+sqrt(2)/2 261static inline int32_t coverageFast(GGLcoord x, GGLcoord y, 262 GGLcoord rmin, GGLcoord rmax, GGLcoord scale) 263{ 264 const GGLcoord d2 = x*x + y*y; 265 if (d2 >= rmax) return 0; 266 if (d2 < rmin) return 0x7FFF; 267 return 0x7FFF - (d2-rmin)*scale; 268} 269 270void aa_pointx(void *con, const GGLcoord* v, GGLcoord size) 271{ 272 GGL_CONTEXT(c, con); 273 274 GGLcoord rad = ((size + 1)>>1); 275 GGLint l = (v[0] - rad) >> TRI_FRACTION_BITS; 276 GGLint t = (v[1] - rad) >> TRI_FRACTION_BITS; 277 GGLint r = (v[0] + rad + (TRI_ONE-1)) >> TRI_FRACTION_BITS; 278 GGLint b = (v[1] + rad + (TRI_ONE-1)) >> TRI_FRACTION_BITS; 279 GGLcoord xstart = TRI_FROM_INT(l) - v[0] + TRI_HALF; 280 GGLcoord ystart = TRI_FROM_INT(t) - v[1] + TRI_HALF; 281 282 // scissor... 283 if (l < GGLint(c->state.scissor.left)) { 284 xstart += TRI_FROM_INT(c->state.scissor.left-l); 285 l = GGLint(c->state.scissor.left); 286 } 287 if (t < GGLint(c->state.scissor.top)) { 288 ystart += TRI_FROM_INT(c->state.scissor.top-t); 289 t = GGLint(c->state.scissor.top); 290 } 291 if (r > GGLint(c->state.scissor.right)) { 292 r = GGLint(c->state.scissor.right); 293 } 294 if (b > GGLint(c->state.scissor.bottom)) { 295 b = GGLint(c->state.scissor.bottom); 296 } 297 298 int xc = r - l; 299 int yc = b - t; 300 if (xc>0 && yc>0) { 301 int16_t* covPtr = c->state.buffers.coverage; 302 rad <<= 4; 303 const int32_t sqr2Over2 = 0xB5; // fixed-point 24.8 304 GGLcoord rmin = rad - sqr2Over2; 305 GGLcoord rmax = rad + sqr2Over2; 306 GGLcoord scale; 307 rmin *= rmin; 308 rmax *= rmax; 309 scale = 0x800000 / (rmax - rmin); 310 rmin >>= 8; 311 rmax >>= 8; 312 313 GGLcoord y = ystart; 314 c->iterators.xl = l; 315 c->iterators.xr = r; 316 c->init_y(c, t); 317 318 do { 319 // compute coverage factors for each pixel 320 GGLcoord x = xstart; 321 for (int i=l ; i<r ; i++) { 322 covPtr[i] = coverageFast(x, y, rmin, rmax, scale); 323 x += TRI_ONE; 324 } 325 y += TRI_ONE; 326 c->scanline(c); 327 c->step_y(c); 328 } while (--yc); 329 } 330} 331 332// ---------------------------------------------------------------------------- 333#if 0 334#pragma mark - 335#pragma mark Line 336#endif 337 338void linex_validate(void *con, const GGLcoord* v0, const GGLcoord* v1, GGLcoord w) 339{ 340 GGL_CONTEXT(c, con); 341 ggl_pick(c); 342 if (c->state.needs.p & GGL_NEED_MASK(P_AA)) { 343 c->procs.linex = aa_linex; 344 } else { 345 c->procs.linex = linex; 346 } 347 c->procs.linex(con, v0, v1, w); 348} 349 350static void linex(void *con, const GGLcoord* v0, const GGLcoord* v1, GGLcoord width) 351{ 352 GGL_CONTEXT(c, con); 353 GGLcoord v[4][2]; 354 v[0][0] = v0[0]; v[0][1] = v0[1]; 355 v[1][0] = v1[0]; v[1][1] = v1[1]; 356 v0 = v[0]; 357 v1 = v[1]; 358 const GGLcoord dx = abs(v0[0] - v1[0]); 359 const GGLcoord dy = abs(v0[1] - v1[1]); 360 GGLcoord nx, ny; 361 nx = ny = 0; 362 363 GGLcoord halfWidth = TRI_ROUND(width) >> 1; 364 if (halfWidth == 0) 365 halfWidth = TRI_HALF; 366 367 ((dx > dy) ? ny : nx) = halfWidth; 368 v[2][0] = v1[0]; v[2][1] = v1[1]; 369 v[3][0] = v0[0]; v[3][1] = v0[1]; 370 v[0][0] += nx; v[0][1] += ny; 371 v[1][0] += nx; v[1][1] += ny; 372 v[2][0] -= nx; v[2][1] -= ny; 373 v[3][0] -= nx; v[3][1] -= ny; 374 trianglex_big(con, v[0], v[1], v[2]); 375 trianglex_big(con, v[0], v[2], v[3]); 376} 377 378static void aa_linex(void *con, const GGLcoord* v0, const GGLcoord* v1, GGLcoord width) 379{ 380 GGL_CONTEXT(c, con); 381 GGLcoord v[4][2]; 382 v[0][0] = v0[0]; v[0][1] = v0[1]; 383 v[1][0] = v1[0]; v[1][1] = v1[1]; 384 v0 = v[0]; 385 v1 = v[1]; 386 387 const GGLcoord dx = v0[0] - v1[0]; 388 const GGLcoord dy = v0[1] - v1[1]; 389 GGLcoord nx = -dy; 390 GGLcoord ny = dx; 391 392 // generally, this will be well below 1.0 393 const GGLfixed norm = gglMulx(width, gglSqrtRecipx(nx*nx+ny*ny), 4); 394 nx = gglMulx(nx, norm, 21); 395 ny = gglMulx(ny, norm, 21); 396 397 v[2][0] = v1[0]; v[2][1] = v1[1]; 398 v[3][0] = v0[0]; v[3][1] = v0[1]; 399 v[0][0] += nx; v[0][1] += ny; 400 v[1][0] += nx; v[1][1] += ny; 401 v[2][0] -= nx; v[2][1] -= ny; 402 v[3][0] -= nx; v[3][1] -= ny; 403 aapolyx(con, v[0], 4); 404} 405 406 407// ---------------------------------------------------------------------------- 408#if 0 409#pragma mark - 410#pragma mark Rect 411#endif 412 413void recti_validate(void *con, GGLint l, GGLint t, GGLint r, GGLint b) 414{ 415 GGL_CONTEXT(c, con); 416 ggl_pick(c); 417 c->procs.recti = recti; 418 c->procs.recti(con, l, t, r, b); 419} 420 421void recti(void* con, GGLint l, GGLint t, GGLint r, GGLint b) 422{ 423 GGL_CONTEXT(c, con); 424 425 // scissor... 426 if (l < GGLint(c->state.scissor.left)) 427 l = GGLint(c->state.scissor.left); 428 if (t < GGLint(c->state.scissor.top)) 429 t = GGLint(c->state.scissor.top); 430 if (r > GGLint(c->state.scissor.right)) 431 r = GGLint(c->state.scissor.right); 432 if (b > GGLint(c->state.scissor.bottom)) 433 b = GGLint(c->state.scissor.bottom); 434 435 int xc = r - l; 436 int yc = b - t; 437 if (xc>0 && yc>0) { 438 c->iterators.xl = l; 439 c->iterators.xr = r; 440 c->init_y(c, t); 441 c->rect(c, yc); 442 } 443} 444 445// ---------------------------------------------------------------------------- 446#if 0 447#pragma mark - 448#pragma mark Triangle / Debugging 449#endif 450 451static void scanline_set(context_t* c) 452{ 453 int32_t x = c->iterators.xl; 454 size_t ct = c->iterators.xr - x; 455 int32_t y = c->iterators.y; 456 surface_t* cb = &(c->state.buffers.color); 457 const GGLFormat* fp = &(c->formats[cb->format]); 458 uint8_t* dst = reinterpret_cast<uint8_t*>(cb->data) + 459 (x + (cb->stride * y)) * fp->size; 460 const size_t size = ct * fp->size; 461 memset(dst, 0xFF, size); 462} 463 464static void trianglex_debug(void* con, 465 const GGLcoord* v0, const GGLcoord* v1, const GGLcoord* v2) 466{ 467 GGL_CONTEXT(c, con); 468 if (c->state.needs.p & GGL_NEED_MASK(P_AA)) { 469 aa_trianglex(con,v0,v1,v2); 470 } else { 471 trianglex_big(con,v0,v1,v2); 472 } 473 void (*save_scanline)(context_t*) = c->scanline; 474 c->scanline = scanline_set; 475 linex(con, v0, v1, TRI_ONE); 476 linex(con, v1, v2, TRI_ONE); 477 linex(con, v2, v0, TRI_ONE); 478 c->scanline = save_scanline; 479} 480 481static void trianglex_xor(void* con, 482 const GGLcoord* v0, const GGLcoord* v1, const GGLcoord* v2) 483{ 484 trianglex_big(con,v0,v1,v2); 485 trianglex_small(con,v0,v1,v2); 486} 487 488// ---------------------------------------------------------------------------- 489#if 0 490#pragma mark - 491#pragma mark Triangle 492#endif 493 494void trianglex_validate(void *con, 495 const GGLcoord* v0, const GGLcoord* v1, const GGLcoord* v2) 496{ 497 GGL_CONTEXT(c, con); 498 ggl_pick(c); 499 if (c->state.needs.p & GGL_NEED_MASK(P_AA)) { 500 c->procs.trianglex = DEBUG_TRANGLES ? trianglex_debug : aa_trianglex; 501 } else { 502 c->procs.trianglex = DEBUG_TRANGLES ? trianglex_debug : trianglex_big; 503 } 504 c->procs.trianglex(con, v0, v1, v2); 505} 506 507// ---------------------------------------------------------------------------- 508 509void trianglex_small(void* con, 510 const GGLcoord* v0, const GGLcoord* v1, const GGLcoord* v2) 511{ 512 GGL_CONTEXT(c, con); 513 514 // vertices are in 28.4 fixed point, which allows 515 // us to use 32 bits multiplies below. 516 int32_t x0 = v0[0]; 517 int32_t y0 = v0[1]; 518 int32_t x1 = v1[0]; 519 int32_t y1 = v1[1]; 520 int32_t x2 = v2[0]; 521 int32_t y2 = v2[1]; 522 523 int32_t dx01 = x0 - x1; 524 int32_t dy20 = y2 - y0; 525 int32_t dy01 = y0 - y1; 526 int32_t dx20 = x2 - x0; 527 528 // The code below works only with CCW triangles 529 // so if we get a CW triangle, we need to swap two of its vertices 530 if (dx01*dy20 < dy01*dx20) { 531 swap(x0, x1); 532 swap(y0, y1); 533 dx01 = x0 - x1; 534 dy01 = y0 - y1; 535 dx20 = x2 - x0; 536 dy20 = y2 - y0; 537 } 538 int32_t dx12 = x1 - x2; 539 int32_t dy12 = y1 - y2; 540 541 // bounding box & scissor 542 const int32_t bminx = TRI_FLOOR(min(x0, x1, x2)) >> TRI_FRACTION_BITS; 543 const int32_t bminy = TRI_FLOOR(min(y0, y1, y2)) >> TRI_FRACTION_BITS; 544 const int32_t bmaxx = TRI_CEIL( max(x0, x1, x2)) >> TRI_FRACTION_BITS; 545 const int32_t bmaxy = TRI_CEIL( max(y0, y1, y2)) >> TRI_FRACTION_BITS; 546 const int32_t minx = max(bminx, c->state.scissor.left); 547 const int32_t miny = max(bminy, c->state.scissor.top); 548 const int32_t maxx = min(bmaxx, c->state.scissor.right); 549 const int32_t maxy = min(bmaxy, c->state.scissor.bottom); 550 if ((minx >= maxx) || (miny >= maxy)) 551 return; // too small or clipped out... 552 553 // step equations to the bounding box and snap to pixel center 554 const int32_t my = (miny << TRI_FRACTION_BITS) + TRI_HALF; 555 const int32_t mx = (minx << TRI_FRACTION_BITS) + TRI_HALF; 556 int32_t ey0 = dy01 * (x0 - mx) - dx01 * (y0 - my); 557 int32_t ey1 = dy12 * (x1 - mx) - dx12 * (y1 - my); 558 int32_t ey2 = dy20 * (x2 - mx) - dx20 * (y2 - my); 559 560 // right-exclusive fill rule, to avoid rare cases 561 // of over drawing 562 if (dy01<0 || (dy01 == 0 && dx01>0)) ey0++; 563 if (dy12<0 || (dy12 == 0 && dx12>0)) ey1++; 564 if (dy20<0 || (dy20 == 0 && dx20>0)) ey2++; 565 566 c->init_y(c, miny); 567 for (int32_t y = miny; y < maxy; y++) { 568 int32_t ex0 = ey0; 569 int32_t ex1 = ey1; 570 int32_t ex2 = ey2; 571 int32_t xl, xr; 572 for (xl=minx ; xl<maxx ; xl++) { 573 if (ex0>0 && ex1>0 && ex2>0) 574 break; // all strictly positive 575 ex0 -= dy01 << TRI_FRACTION_BITS; 576 ex1 -= dy12 << TRI_FRACTION_BITS; 577 ex2 -= dy20 << TRI_FRACTION_BITS; 578 } 579 xr = xl; 580 for ( ; xr<maxx ; xr++) { 581 if (!(ex0>0 && ex1>0 && ex2>0)) 582 break; // not all strictly positive 583 ex0 -= dy01 << TRI_FRACTION_BITS; 584 ex1 -= dy12 << TRI_FRACTION_BITS; 585 ex2 -= dy20 << TRI_FRACTION_BITS; 586 } 587 588 if (xl < xr) { 589 c->iterators.xl = xl; 590 c->iterators.xr = xr; 591 c->scanline(c); 592 } 593 c->step_y(c); 594 595 ey0 += dx01 << TRI_FRACTION_BITS; 596 ey1 += dx12 << TRI_FRACTION_BITS; 597 ey2 += dx20 << TRI_FRACTION_BITS; 598 } 599} 600 601// ---------------------------------------------------------------------------- 602#if 0 603#pragma mark - 604#endif 605 606// the following routine fills a triangle via edge stepping, which 607// unfortunately requires divisions in the setup phase to get right, 608// it should probably only be used for relatively large trianges 609 610 611// x = y*DX/DY (ou DX and DY are constants, DY > 0, et y >= 0) 612// 613// for an equation of the type: 614// x' = y*K/2^p (with K and p constants "carefully chosen") 615// 616// We can now do a DDA without precision loss. We define 'e' by: 617// x' - x = y*(DX/DY - K/2^p) = y*e 618// 619// If we choose K = round(DX*2^p/DY) then, 620// abs(e) <= 1/2^(p+1) by construction 621// 622// therefore abs(x'-x) = y*abs(e) <= y/2^(p+1) <= DY/2^(p+1) <= DMAX/2^(p+1) 623// 624// which means that if DMAX <= 2^p, therefore abs(x-x') <= 1/2, including 625// at the last line. In fact, it's even a strict inequality except in one 626// extrem case (DY == DMAX et e = +/- 1/2) 627// 628// Applying that to our coordinates, we need 2^p >= 4096*16 = 65536 629// so p = 16 is enough, we're so lucky! 630 631const int TRI_ITERATORS_BITS = 16; 632 633struct Edge 634{ 635 int32_t x; // edge position in 16.16 coordinates 636 int32_t x_incr; // on each step, increment x by that amount 637 int32_t y_top; // starting scanline, 16.4 format 638 int32_t y_bot; 639}; 640 641static void 642edge_dump( Edge* edge ) 643{ 644 ALOGI( " top=%d (%.3f) bot=%d (%.3f) x=%d (%.3f) ix=%d (%.3f)", 645 edge->y_top, edge->y_top/float(TRI_ONE), 646 edge->y_bot, edge->y_bot/float(TRI_ONE), 647 edge->x, edge->x/float(FIXED_ONE), 648 edge->x_incr, edge->x_incr/float(FIXED_ONE) ); 649} 650 651static void 652triangle_dump_edges( Edge* edges, 653 int count ) 654{ 655 ALOGI( "%d edge%s:\n", count, count == 1 ? "" : "s" ); 656 for ( ; count > 0; count--, edges++ ) 657 edge_dump( edges ); 658} 659 660// the following function sets up an edge, it assumes 661// that ymin and ymax are in already in the 'reduced' 662// format 663static __attribute__((noinline)) 664void edge_setup( 665 Edge* edges, 666 int* pcount, 667 const GGLcoord* p1, 668 const GGLcoord* p2, 669 int32_t ymin, 670 int32_t ymax ) 671{ 672 const GGLfixed* top = p1; 673 const GGLfixed* bot = p2; 674 Edge* edge = edges + *pcount; 675 676 if (top[1] > bot[1]) { 677 swap(top, bot); 678 } 679 680 int y1 = top[1] | 1; 681 int y2 = bot[1] | 1; 682 int dy = y2 - y1; 683 684 if ( dy == 0 || y1 > ymax || y2 < ymin ) 685 return; 686 687 if ( y1 > ymin ) 688 ymin = TRI_SNAP_NEXT_HALF(y1); 689 690 if ( y2 < ymax ) 691 ymax = TRI_SNAP_PREV_HALF(y2); 692 693 if ( ymin > ymax ) // when the edge doesn't cross any scanline 694 return; 695 696 const int x1 = top[0]; 697 const int dx = bot[0] - x1; 698 const int shift = TRI_ITERATORS_BITS - TRI_FRACTION_BITS; 699 700 // setup edge fields 701 // We add 0.5 to edge->x here because it simplifies the rounding 702 // in triangle_sweep_edges() -- this doesn't change the ordering of 'x' 703 edge->x = (x1 << shift) + (1LU << (TRI_ITERATORS_BITS-1)); 704 edge->x_incr = 0; 705 edge->y_top = ymin; 706 edge->y_bot = ymax; 707 708 if (ggl_likely(ymin <= ymax && dx)) { 709 edge->x_incr = gglDivQ16(dx, dy); 710 } 711 if (ggl_likely(y1 < ymin)) { 712 int32_t xadjust = (edge->x_incr * (ymin-y1)) >> TRI_FRACTION_BITS; 713 edge->x += xadjust; 714 } 715 716 ++*pcount; 717} 718 719 720static void 721triangle_sweep_edges( Edge* left, 722 Edge* right, 723 int ytop, 724 int ybot, 725 context_t* c ) 726{ 727 int count = ((ybot - ytop)>>TRI_FRACTION_BITS) + 1; 728 if (count<=0) return; 729 730 // sort the edges horizontally 731 if ((left->x > right->x) || 732 ((left->x == right->x) && (left->x_incr > right->x_incr))) { 733 swap(left, right); 734 } 735 736 int left_x = left->x; 737 int right_x = right->x; 738 const int left_xi = left->x_incr; 739 const int right_xi = right->x_incr; 740 left->x += left_xi * count; 741 right->x += right_xi * count; 742 743 const int xmin = c->state.scissor.left; 744 const int xmax = c->state.scissor.right; 745 do { 746 // horizontal scissoring 747 const int32_t xl = max(left_x >> TRI_ITERATORS_BITS, xmin); 748 const int32_t xr = min(right_x >> TRI_ITERATORS_BITS, xmax); 749 left_x += left_xi; 750 right_x += right_xi; 751 // invoke the scanline rasterizer 752 if (ggl_likely(xl < xr)) { 753 c->iterators.xl = xl; 754 c->iterators.xr = xr; 755 c->scanline(c); 756 } 757 c->step_y(c); 758 } while (--count); 759} 760 761 762void trianglex_big(void* con, 763 const GGLcoord* v0, const GGLcoord* v1, const GGLcoord* v2) 764{ 765 GGL_CONTEXT(c, con); 766 767 Edge edges[3]; 768 int num_edges = 0; 769 int32_t ymin = TRI_FROM_INT(c->state.scissor.top) + TRI_HALF; 770 int32_t ymax = TRI_FROM_INT(c->state.scissor.bottom) - TRI_HALF; 771 772 edge_setup( edges, &num_edges, v0, v1, ymin, ymax ); 773 edge_setup( edges, &num_edges, v0, v2, ymin, ymax ); 774 edge_setup( edges, &num_edges, v1, v2, ymin, ymax ); 775 776 if (ggl_unlikely(num_edges<2)) // for really tiny triangles that don't 777 return; // cross any scanline centers 778 779 Edge* left = &edges[0]; 780 Edge* right = &edges[1]; 781 Edge* other = &edges[2]; 782 int32_t y_top = min(left->y_top, right->y_top); 783 int32_t y_bot = max(left->y_bot, right->y_bot); 784 785 if (ggl_likely(num_edges==3)) { 786 y_top = min(y_top, edges[2].y_top); 787 y_bot = max(y_bot, edges[2].y_bot); 788 if (edges[0].y_top > y_top) { 789 other = &edges[0]; 790 left = &edges[2]; 791 } else if (edges[1].y_top > y_top) { 792 other = &edges[1]; 793 right = &edges[2]; 794 } 795 } 796 797 c->init_y(c, y_top >> TRI_FRACTION_BITS); 798 799 int32_t y_mid = min(left->y_bot, right->y_bot); 800 triangle_sweep_edges( left, right, y_top, y_mid, c ); 801 802 // second scanline sweep loop, if necessary 803 y_mid += TRI_ONE; 804 if (y_mid <= y_bot) { 805 ((left->y_bot == y_bot) ? right : left) = other; 806 if (other->y_top < y_mid) { 807 other->x += other->x_incr; 808 } 809 triangle_sweep_edges( left, right, y_mid, y_bot, c ); 810 } 811} 812 813void aa_trianglex(void* con, 814 const GGLcoord* a, const GGLcoord* b, const GGLcoord* c) 815{ 816 GGLcoord pts[6] = { a[0], a[1], b[0], b[1], c[0], c[1] }; 817 aapolyx(con, pts, 3); 818} 819 820// ---------------------------------------------------------------------------- 821#if 0 822#pragma mark - 823#endif 824 825struct AAEdge 826{ 827 GGLfixed x; // edge position in 12.16 coordinates 828 GGLfixed x_incr; // on each y step, increment x by that amount 829 GGLfixed y_incr; // on each x step, increment y by that amount 830 int16_t y_top; // starting scanline, 12.4 format 831 int16_t y_bot; // starting scanline, 12.4 format 832 void dump(); 833}; 834 835void AAEdge::dump() 836{ 837 float tri = 1.0f / TRI_ONE; 838 float iter = 1.0f / (1<<TRI_ITERATORS_BITS); 839 float fix = 1.0f / FIXED_ONE; 840 ALOGD( "x=%08x (%.3f), " 841 "x_incr=%08x (%.3f), y_incr=%08x (%.3f), " 842 "y_top=%08x (%.3f), y_bot=%08x (%.3f) ", 843 x, x*fix, 844 x_incr, x_incr*iter, 845 y_incr, y_incr*iter, 846 y_top, y_top*tri, 847 y_bot, y_bot*tri ); 848} 849 850// the following function sets up an edge, it assumes 851// that ymin and ymax are in already in the 'reduced' 852// format 853static __attribute__((noinline)) 854void aa_edge_setup( 855 AAEdge* edges, 856 int* pcount, 857 const GGLcoord* p1, 858 const GGLcoord* p2, 859 int32_t ymin, 860 int32_t ymax ) 861{ 862 const GGLfixed* top = p1; 863 const GGLfixed* bot = p2; 864 AAEdge* edge = edges + *pcount; 865 866 if (top[1] > bot[1]) 867 swap(top, bot); 868 869 int y1 = top[1]; 870 int y2 = bot[1]; 871 int dy = y2 - y1; 872 873 if (dy==0 || y1>ymax || y2<ymin) 874 return; 875 876 if (y1 > ymin) 877 ymin = y1; 878 879 if (y2 < ymax) 880 ymax = y2; 881 882 const int x1 = top[0]; 883 const int dx = bot[0] - x1; 884 const int shift = FIXED_BITS - TRI_FRACTION_BITS; 885 886 // setup edge fields 887 edge->x = x1 << shift; 888 edge->x_incr = 0; 889 edge->y_top = ymin; 890 edge->y_bot = ymax; 891 edge->y_incr = 0x7FFFFFFF; 892 893 if (ggl_likely(ymin <= ymax && dx)) { 894 edge->x_incr = gglDivQ16(dx, dy); 895 if (dx != 0) { 896 edge->y_incr = abs(gglDivQ16(dy, dx)); 897 } 898 } 899 if (ggl_likely(y1 < ymin)) { 900 int32_t xadjust = (edge->x_incr * (ymin-y1)) 901 >> (TRI_FRACTION_BITS + TRI_ITERATORS_BITS - FIXED_BITS); 902 edge->x += xadjust; 903 } 904 905 ++*pcount; 906} 907 908 909typedef int (*compar_t)(const void*, const void*); 910static int compare_edges(const AAEdge *e0, const AAEdge *e1) { 911 if (e0->y_top > e1->y_top) return 1; 912 if (e0->y_top < e1->y_top) return -1; 913 if (e0->x > e1->x) return 1; 914 if (e0->x < e1->x) return -1; 915 if (e0->x_incr > e1->x_incr) return 1; 916 if (e0->x_incr < e1->x_incr) return -1; 917 return 0; // same edges, should never happen 918} 919 920static inline 921void SET_COVERAGE(int16_t*& p, int32_t value, ssize_t n) 922{ 923 android_memset16((uint16_t*)p, value, n*2); 924 p += n; 925} 926 927static inline 928void ADD_COVERAGE(int16_t*& p, int32_t value) 929{ 930 value = *p + value; 931 if (value >= 0x8000) 932 value = 0x7FFF; 933 *p++ = value; 934} 935 936static inline 937void SUB_COVERAGE(int16_t*& p, int32_t value) 938{ 939 value = *p - value; 940 value &= ~(value>>31); 941 *p++ = value; 942} 943 944void aapolyx(void* con, 945 const GGLcoord* pts, int count) 946{ 947 /* 948 * NOTE: This routine assumes that the polygon has been clipped to the 949 * viewport already, that is, no vertex lies outside of the framebuffer. 950 * If this happens, the code below won't corrupt memory but the 951 * coverage values may not be correct. 952 */ 953 954 GGL_CONTEXT(c, con); 955 956 // we do only quads for now (it's used for thick lines) 957 if ((count>4) || (count<2)) return; 958 959 // take scissor into account 960 const int xmin = c->state.scissor.left; 961 const int xmax = c->state.scissor.right; 962 if (xmin >= xmax) return; 963 964 // generate edges from the vertices 965 int32_t ymin = TRI_FROM_INT(c->state.scissor.top); 966 int32_t ymax = TRI_FROM_INT(c->state.scissor.bottom); 967 if (ymin >= ymax) return; 968 969 AAEdge edges[4]; 970 int num_edges = 0; 971 GGLcoord const * p = pts; 972 for (int i=0 ; i<count-1 ; i++, p+=2) { 973 aa_edge_setup(edges, &num_edges, p, p+2, ymin, ymax); 974 } 975 aa_edge_setup(edges, &num_edges, p, pts, ymin, ymax ); 976 if (ggl_unlikely(num_edges<2)) 977 return; 978 979 // sort the edge list top to bottom, left to right. 980 qsort(edges, num_edges, sizeof(AAEdge), (compar_t)compare_edges); 981 982 int16_t* const covPtr = c->state.buffers.coverage; 983 memset(covPtr+xmin, 0, (xmax-xmin)*sizeof(*covPtr)); 984 985 // now, sweep all edges in order 986 // start with the 2 first edges. We know that they share their top 987 // vertex, by construction. 988 int i = 2; 989 AAEdge* left = &edges[0]; 990 AAEdge* right = &edges[1]; 991 int32_t yt = left->y_top; 992 GGLfixed l = left->x; 993 GGLfixed r = right->x; 994 int retire = 0; 995 int16_t* coverage; 996 997 // at this point we can initialize the rasterizer 998 c->init_y(c, yt>>TRI_FRACTION_BITS); 999 c->iterators.xl = xmax; 1000 c->iterators.xr = xmin; 1001 1002 do { 1003 int32_t y = min(min(left->y_bot, right->y_bot), TRI_FLOOR(yt + TRI_ONE)); 1004 const int32_t shift = TRI_FRACTION_BITS + TRI_ITERATORS_BITS - FIXED_BITS; 1005 const int cf_shift = (1 + TRI_FRACTION_BITS*2 + TRI_ITERATORS_BITS - 15); 1006 1007 // compute xmin and xmax for the left edge 1008 GGLfixed l_min = gglMulAddx(left->x_incr, y - left->y_top, left->x, shift); 1009 GGLfixed l_max = l; 1010 l = l_min; 1011 if (l_min > l_max) 1012 swap(l_min, l_max); 1013 1014 // compute xmin and xmax for the right edge 1015 GGLfixed r_min = gglMulAddx(right->x_incr, y - right->y_top, right->x, shift); 1016 GGLfixed r_max = r; 1017 r = r_min; 1018 if (r_min > r_max) 1019 swap(r_min, r_max); 1020 1021 // make sure we're not touching coverage values outside of the 1022 // framebuffer 1023 l_min &= ~(l_min>>31); 1024 r_min &= ~(r_min>>31); 1025 l_max &= ~(l_max>>31); 1026 r_max &= ~(r_max>>31); 1027 if (gglFixedToIntFloor(l_min) >= xmax) l_min = gglIntToFixed(xmax)-1; 1028 if (gglFixedToIntFloor(r_min) >= xmax) r_min = gglIntToFixed(xmax)-1; 1029 if (gglFixedToIntCeil(l_max) >= xmax) l_max = gglIntToFixed(xmax)-1; 1030 if (gglFixedToIntCeil(r_max) >= xmax) r_max = gglIntToFixed(xmax)-1; 1031 1032 // compute the integer versions of the above 1033 const GGLfixed l_min_i = gglFloorx(l_min); 1034 const GGLfixed l_max_i = gglCeilx (l_max); 1035 const GGLfixed r_min_i = gglFloorx(r_min); 1036 const GGLfixed r_max_i = gglCeilx (r_max); 1037 1038 // clip horizontally using the scissor 1039 const int xml = max(xmin, gglFixedToIntFloor(l_min_i)); 1040 const int xmr = min(xmax, gglFixedToIntFloor(r_max_i)); 1041 1042 // if we just stepped to a new scanline, render the previous one. 1043 // and clear the coverage buffer 1044 if (retire) { 1045 if (c->iterators.xl < c->iterators.xr) 1046 c->scanline(c); 1047 c->step_y(c); 1048 memset(covPtr+xmin, 0, (xmax-xmin)*sizeof(*covPtr)); 1049 c->iterators.xl = xml; 1050 c->iterators.xr = xmr; 1051 } else { 1052 // update the horizontal range of this scanline 1053 c->iterators.xl = min(c->iterators.xl, xml); 1054 c->iterators.xr = max(c->iterators.xr, xmr); 1055 } 1056 1057 coverage = covPtr + gglFixedToIntFloor(l_min_i); 1058 if (l_min_i == gglFloorx(l_max)) { 1059 1060 /* 1061 * fully traverse this pixel vertically 1062 * l_max 1063 * +-----/--+ yt 1064 * | / | 1065 * | / | 1066 * | / | 1067 * +-/------+ y 1068 * l_min (l_min_i + TRI_ONE) 1069 */ 1070 1071 GGLfixed dx = l_max - l_min; 1072 int32_t dy = y - yt; 1073 int cf = gglMulx((dx >> 1) + (l_min_i + FIXED_ONE - l_max), dy, 1074 FIXED_BITS + TRI_FRACTION_BITS - 15); 1075 ADD_COVERAGE(coverage, cf); 1076 // all pixels on the right have cf = 1.0 1077 } else { 1078 /* 1079 * spans several pixels in one scanline 1080 * l_max 1081 * +--------+--/-----+ yt 1082 * | |/ | 1083 * | /| | 1084 * | / | | 1085 * +---/----+--------+ y 1086 * l_min (l_min_i + TRI_ONE) 1087 */ 1088 1089 // handle the first pixel separately... 1090 const int32_t y_incr = left->y_incr; 1091 int32_t dx = TRI_FROM_FIXED(l_min_i - l_min) + TRI_ONE; 1092 int32_t cf = (dx * dx * y_incr) >> cf_shift; 1093 ADD_COVERAGE(coverage, cf); 1094 1095 // following pixels get covered by y_incr, but we need 1096 // to fix-up the cf to account for previous partial pixel 1097 dx = TRI_FROM_FIXED(l_min - l_min_i); 1098 cf -= (dx * dx * y_incr) >> cf_shift; 1099 for (int x = l_min_i+FIXED_ONE ; x < l_max_i-FIXED_ONE ; x += FIXED_ONE) { 1100 cf += y_incr >> (TRI_ITERATORS_BITS-15); 1101 ADD_COVERAGE(coverage, cf); 1102 } 1103 1104 // and the last pixel 1105 dx = TRI_FROM_FIXED(l_max - l_max_i) - TRI_ONE; 1106 cf += (dx * dx * y_incr) >> cf_shift; 1107 ADD_COVERAGE(coverage, cf); 1108 } 1109 1110 // now, fill up all fully covered pixels 1111 coverage = covPtr + gglFixedToIntFloor(l_max_i); 1112 int cf = ((y - yt) << (15 - TRI_FRACTION_BITS)); 1113 if (ggl_likely(cf >= 0x8000)) { 1114 SET_COVERAGE(coverage, 0x7FFF, ((r_max - l_max_i)>>FIXED_BITS)+1); 1115 } else { 1116 for (int x=l_max_i ; x<r_max ; x+=FIXED_ONE) { 1117 ADD_COVERAGE(coverage, cf); 1118 } 1119 } 1120 1121 // subtract the coverage of the right edge 1122 coverage = covPtr + gglFixedToIntFloor(r_min_i); 1123 if (r_min_i == gglFloorx(r_max)) { 1124 GGLfixed dx = r_max - r_min; 1125 int32_t dy = y - yt; 1126 int cf = gglMulx((dx >> 1) + (r_min_i + FIXED_ONE - r_max), dy, 1127 FIXED_BITS + TRI_FRACTION_BITS - 15); 1128 SUB_COVERAGE(coverage, cf); 1129 // all pixels on the right have cf = 1.0 1130 } else { 1131 // handle the first pixel separately... 1132 const int32_t y_incr = right->y_incr; 1133 int32_t dx = TRI_FROM_FIXED(r_min_i - r_min) + TRI_ONE; 1134 int32_t cf = (dx * dx * y_incr) >> cf_shift; 1135 SUB_COVERAGE(coverage, cf); 1136 1137 // following pixels get covered by y_incr, but we need 1138 // to fix-up the cf to account for previous partial pixel 1139 dx = TRI_FROM_FIXED(r_min - r_min_i); 1140 cf -= (dx * dx * y_incr) >> cf_shift; 1141 for (int x = r_min_i+FIXED_ONE ; x < r_max_i-FIXED_ONE ; x += FIXED_ONE) { 1142 cf += y_incr >> (TRI_ITERATORS_BITS-15); 1143 SUB_COVERAGE(coverage, cf); 1144 } 1145 1146 // and the last pixel 1147 dx = TRI_FROM_FIXED(r_max - r_max_i) - TRI_ONE; 1148 cf += (dx * dx * y_incr) >> cf_shift; 1149 SUB_COVERAGE(coverage, cf); 1150 } 1151 1152 // did we reach the end of an edge? if so, get a new one. 1153 if (y == left->y_bot || y == right->y_bot) { 1154 // bail out if we're done 1155 if (i>=num_edges) 1156 break; 1157 if (y == left->y_bot) 1158 left = &edges[i++]; 1159 if (y == right->y_bot) 1160 right = &edges[i++]; 1161 } 1162 1163 // next scanline 1164 yt = y; 1165 1166 // did we just finish a scanline? 1167 retire = (y << (32-TRI_FRACTION_BITS)) == 0; 1168 } while (true); 1169 1170 // render the last scanline 1171 if (c->iterators.xl < c->iterators.xr) 1172 c->scanline(c); 1173} 1174 1175}; // namespace android 1176