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
30 namespace android {
31
32 // ----------------------------------------------------------------------------
33
34 // enable to see triangles edges
35 #define DEBUG_TRANGLES 0
36
37 // ----------------------------------------------------------------------------
38
39 static void pointx_validate(void *con, const GGLcoord* c, GGLcoord r);
40 static void pointx(void *con, const GGLcoord* c, GGLcoord r);
41 static void aa_pointx(void *con, const GGLcoord* c, GGLcoord r);
42 static void aa_nice_pointx(void *con, const GGLcoord* c, GGLcoord r);
43
44 static void linex_validate(void *con, const GGLcoord* v0, const GGLcoord* v1, GGLcoord w);
45 static void linex(void *con, const GGLcoord* v0, const GGLcoord* v1, GGLcoord w);
46 static void aa_linex(void *con, const GGLcoord* v0, const GGLcoord* v1, GGLcoord w);
47
48 static void recti_validate(void* c, GGLint l, GGLint t, GGLint r, GGLint b);
49 static void recti(void* c, GGLint l, GGLint t, GGLint r, GGLint b);
50
51 static void trianglex_validate(void*,
52 const GGLcoord*, const GGLcoord*, const GGLcoord*);
53 static void trianglex_small(void*,
54 const GGLcoord*, const GGLcoord*, const GGLcoord*);
55 static void trianglex_big(void*,
56 const GGLcoord*, const GGLcoord*, const GGLcoord*);
57 static void aa_trianglex(void*,
58 const GGLcoord*, const GGLcoord*, const GGLcoord*);
59 static void trianglex_debug(void* con,
60 const GGLcoord*, const GGLcoord*, const GGLcoord*);
61
62 static void aapolyx(void* con,
63 const GGLcoord* pts, int count);
64
65 static inline int min(int a, int b) CONST;
66 static inline int max(int a, int b) CONST;
67 static inline int min(int a, int b, int c) CONST;
68 static 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
min(int a,int b)76 inline int min(int a, int b) {
77 return a<b ? a : b;
78 }
max(int a,int b)79 inline int max(int a, int b) {
80 return a<b ? b : a;
81 }
min(int a,int b,int c)82 inline int min(int a, int b, int c) {
83 return min(a,min(b,c));
84 }
max(int a,int b,int c)85 inline int max(int a, int b, int c) {
86 return max(a,max(b,c));
87 }
88
89 template <typename T>
swap(T & a,T & b)90 static inline void swap(T& a, T& b) {
91 T t(a);
92 a = b;
93 b = t;
94 }
95
96 static void
triangle_dump_points(const GGLcoord * v0,const GGLcoord * v1,const GGLcoord * v2)97 triangle_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
ggl_init_trap(context_t * c)116 void ggl_init_trap(context_t* c)
117 {
118 ggl_state_changed(c, GGL_PIXEL_PIPELINE_STATE|GGL_TMU_STATE|GGL_CB_STATE);
119 }
120
ggl_state_changed(context_t * c,int flags)121 void 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
pointx_validate(void * con,const GGLcoord * v,GGLcoord rad)138 void 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
pointx(void * con,const GGLcoord * v,GGLcoord rad)154 void 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.
coverageNice(GGLcoord x,GGLcoord y,GGLcoord rmin,GGLcoord rmax,GGLcoord rr)179 static 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
aa_nice_pointx(void * con,const GGLcoord * v,GGLcoord size)205 void 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
coverageFast(GGLcoord x,GGLcoord y,GGLcoord rmin,GGLcoord rmax,GGLcoord scale)261 static 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
aa_pointx(void * con,const GGLcoord * v,GGLcoord size)270 void 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
linex_validate(void * con,const GGLcoord * v0,const GGLcoord * v1,GGLcoord w)338 void 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
linex(void * con,const GGLcoord * v0,const GGLcoord * v1,GGLcoord width)350 static 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
aa_linex(void * con,const GGLcoord * v0,const GGLcoord * v1,GGLcoord width)378 static 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
recti_validate(void * con,GGLint l,GGLint t,GGLint r,GGLint b)413 void 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
recti(void * con,GGLint l,GGLint t,GGLint r,GGLint b)421 void 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
scanline_set(context_t * c)451 static 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
trianglex_debug(void * con,const GGLcoord * v0,const GGLcoord * v1,const GGLcoord * v2)464 static 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
trianglex_xor(void * con,const GGLcoord * v0,const GGLcoord * v1,const GGLcoord * v2)481 static 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
trianglex_validate(void * con,const GGLcoord * v0,const GGLcoord * v1,const GGLcoord * v2)494 void 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
trianglex_small(void * con,const GGLcoord * v0,const GGLcoord * v1,const GGLcoord * v2)509 void 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
631 const int TRI_ITERATORS_BITS = 16;
632
633 struct 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
641 static void
edge_dump(Edge * edge)642 edge_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
651 static void
triangle_dump_edges(Edge * edges,int count)652 triangle_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
663 static __attribute__((noinline))
edge_setup(Edge * edges,int * pcount,const GGLcoord * p1,const GGLcoord * p2,int32_t ymin,int32_t ymax)664 void 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
720 static void
triangle_sweep_edges(Edge * left,Edge * right,int ytop,int ybot,context_t * c)721 triangle_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
trianglex_big(void * con,const GGLcoord * v0,const GGLcoord * v1,const GGLcoord * v2)762 void 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
aa_trianglex(void * con,const GGLcoord * a,const GGLcoord * b,const GGLcoord * c)813 void 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
825 struct 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
dump()835 void 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
853 static __attribute__((noinline))
aa_edge_setup(AAEdge * edges,int * pcount,const GGLcoord * p1,const GGLcoord * p2,int32_t ymin,int32_t ymax)854 void 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
909 typedef int (*compar_t)(const void*, const void*);
compare_edges(const AAEdge * e0,const AAEdge * e1)910 static 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
920 static inline
SET_COVERAGE(int16_t * & p,int32_t value,ssize_t n)921 void 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
927 static inline
ADD_COVERAGE(int16_t * & p,int32_t value)928 void 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
936 static inline
SUB_COVERAGE(int16_t * & p,int32_t value)937 void SUB_COVERAGE(int16_t*& p, int32_t value)
938 {
939 value = *p - value;
940 value &= ~(value>>31);
941 *p++ = value;
942 }
943
aapolyx(void * con,const GGLcoord * pts,int count)944 void 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