1 /*
2 * Copyright 2018 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can
5 * be found in the LICENSE file.
6 *
7 */
8
9 #include "transform_stack.h"
10
11 //
12 //
13 //
14
15 #include <stdlib.h>
16 #include <math.h>
17
18 //
19 //
20 //
21
22 #undef NDEBUG
23 #include <assert.h>
24
25 //
26 //
27 //
28
29 #define TS_TRANSFORM_SUFFIX_EVAL(a) a
30
31 #define TS_TRANSFORM_SUFFIX_CONCAT(func) \
32 TS_TRANSFORM_SUFFIX_EVAL(func)##TS_TRANSFORM_SUFFIX_EVAL(TS_TRANSFORM_FLOAT_SUFFIX)
33
34 //
35 //
36 //
37
38 #define TS_TRANSFORM_SIN(x) TS_TRANSFORM_SUFFIX_CONCAT(sin)(x)
39 #define TS_TRANSFORM_COS(x) TS_TRANSFORM_SUFFIX_CONCAT(cos)(x)
40 #define TS_TRANSFORM_TAN(x) TS_TRANSFORM_SUFFIX_CONCAT(tan)(x)
41
42 //
43 //
44 //
45 #define TS_TRANSFORM_ZERO ((ts_transform_float_t)0.0)
46 #define TS_TRANSFORM_ONE ((ts_transform_float_t)1.0)
47 #define TS_TRANSFORM_RCP(f) (TS_TRANSFORM_ONE / (f))
48
49
50 //
51 //
52 //
53
54 union ts_transform_stack_3x3_u
55 {
56 ts_transform_float_t a8[8];
57
58 struct {
59 ts_transform_float_t sx;
60 ts_transform_float_t shx;
61 ts_transform_float_t tx;
62
63 ts_transform_float_t shy;
64 ts_transform_float_t sy;
65 ts_transform_float_t ty;
66
67 ts_transform_float_t w0;
68 ts_transform_float_t w1;
69 // w2 is always 1.0
70 };
71
72 struct {
73 ts_transform_float_t a;
74 ts_transform_float_t b;
75 ts_transform_float_t c;
76
77 ts_transform_float_t d;
78 ts_transform_float_t e;
79 ts_transform_float_t f;
80
81 ts_transform_float_t g;
82 ts_transform_float_t h;
83 // i is always 1.0
84 };
85 };
86
87 //
88 //
89 //
90
91 struct ts_transform_stack
92 {
93 uint32_t size;
94 uint32_t count;
95
96 ts_transform_weakref_t * weakrefs;
97 union ts_transform_stack_3x3_u * transforms;
98 };
99
100 //
101 //
102 //
103
104 static
105 void
ts_transform_stack_resize(struct ts_transform_stack * const ts,uint32_t const size)106 ts_transform_stack_resize(struct ts_transform_stack * const ts, uint32_t const size)
107 {
108 ts->size = size;
109 ts->weakrefs = realloc(ts->weakrefs, size * sizeof(*ts->weakrefs));
110 ts->transforms = realloc(ts->transforms,size * sizeof(*ts->transforms));
111 }
112
113 static
114 void
ts_transform_stack_ensure(struct ts_transform_stack * const ts)115 ts_transform_stack_ensure(struct ts_transform_stack * const ts)
116 {
117 if (ts->count < ts->size)
118 return;
119
120 // increase by 50% and by at least 8
121 ts_transform_stack_resize(ts,ts->size + max(ts->size/2,8));
122 }
123
124 //
125 //
126 //
127
128 struct ts_transform_stack *
ts_transform_stack_create(uint32_t const size)129 ts_transform_stack_create(uint32_t const size)
130 {
131 struct ts_transform_stack * ts = malloc(sizeof(*ts));
132
133 ts->size = size;
134 ts->count = 0;
135
136 ts->transforms = NULL;
137 ts->weakrefs = NULL;
138
139 ts_transform_stack_resize(ts,size);
140
141 return ts;
142 }
143
144 void
ts_transform_stack_release(struct ts_transform_stack * const ts)145 ts_transform_stack_release(struct ts_transform_stack * const ts)
146 {
147 free(ts->transforms);
148 free(ts->weakrefs);
149
150 free(ts);
151 }
152
153 //
154 //
155 //
156
157 uint32_t
ts_transform_stack_save(struct ts_transform_stack * const ts)158 ts_transform_stack_save(struct ts_transform_stack * const ts)
159 {
160 return ts->count;
161 }
162
163 void
ts_transform_stack_restore(struct ts_transform_stack * const ts,uint32_t const restore)164 ts_transform_stack_restore(struct ts_transform_stack * const ts,
165 uint32_t const restore)
166 {
167 ts->count = restore;
168 }
169
170 //
171 //
172 //
173
174 static
175 union ts_transform_stack_3x3_u *
ts_transform_stack_tos(struct ts_transform_stack * const ts)176 ts_transform_stack_tos(struct ts_transform_stack * const ts)
177 {
178 return ts->transforms + ts->count - 1;
179 }
180
181 //
182 //
183 //
184
185 static
186 void
ts_transform_stack_3x3_u_copy(union ts_transform_stack_3x3_u * const __restrict dst,union ts_transform_stack_3x3_u const * const __restrict src)187 ts_transform_stack_3x3_u_copy(union ts_transform_stack_3x3_u * const __restrict dst,
188 union ts_transform_stack_3x3_u const * const __restrict src)
189 {
190 *dst = *src;
191 }
192
193 //
194 // C = A * B
195 //
196 // FIXME -- can save affine vs. projective flags and save a few ops
197 //
198
199 #define TS_TRANSFORM_MULTIPLY(A,B) \
200 A->sx * B->sx + A->shx * B->shy + A->tx * B->w0, \
201 A->sx * B->shx + A->shx * B->sy + A->tx * B->w1, \
202 A->sx * B->tx + A->shx * B->ty + A->tx, \
203 A->shy * B->sx + A->sy * B->shy + A->ty * B->w0, \
204 A->shy * B->shx + A->sy * B->sy + A->ty * B->w1, \
205 A->shy * B->tx + A->sy * B->ty + A->ty, \
206 A->w0 * B->sx + A->w1 * B->shy + B->w0, \
207 A->w0 * B->shx + A->w1 * B->sy + B->w1, \
208 A->w0 * B->tx + A->w1 * B->ty + TS_TRANSFORM_ONE
209
210 //
211 //
212 //
213
214 #define TS_IS_AFFINE(t) ((t->w0 == TS_TRANSFORM_ZERO) && (t->w1 == TS_TRANSFORM_ZERO))
215
216 static
217 ts_transform_type_e
ts_transform_stack_classify(struct ts_transform_stack * const ts)218 ts_transform_stack_classify(struct ts_transform_stack * const ts)
219 {
220 union ts_transform_stack_3x3_u const * const t = ts_transform_stack_tos(ts);
221
222 if (TS_IS_AFFINE(t))
223 return TS_TRANSFORM_TYPE_AFFINE;
224 else
225 return TS_TRANSFORM_TYPE_PROJECTIVE;
226 }
227
228 //
229 //
230 //
231
232 ts_transform_float_t *
ts_transform_stack_top_transform(struct ts_transform_stack * const ts)233 ts_transform_stack_top_transform(struct ts_transform_stack * const ts)
234 {
235 return ts_transform_stack_tos(ts)->a8;
236 }
237
238 ts_transform_weakref_t *
ts_transform_stack_top_weakref(struct ts_transform_stack * const ts)239 ts_transform_stack_top_weakref(struct ts_transform_stack * const ts)
240 {
241 return ts->weakrefs + ts->count - 1;
242 }
243
244 //
245 //
246 //
247
248 void
ts_transform_stack_dup(struct ts_transform_stack * const ts)249 ts_transform_stack_dup(struct ts_transform_stack * const ts)
250 {
251 ts_transform_stack_ensure(ts);
252
253 union ts_transform_stack_3x3_u * const tos = ts_transform_stack_tos(ts);
254
255 ts_transform_stack_3x3_u_copy(tos+1,tos);
256
257 ts->weakrefs[ts->count] = ts->weakrefs[ts->count-1];
258
259 ts->count += 1;
260 }
261
262 void
ts_transform_stack_drop(struct ts_transform_stack * const ts)263 ts_transform_stack_drop(struct ts_transform_stack * const ts)
264 {
265 assert(ts->count >= 1);
266
267 ts->count -= 1;
268 }
269
270 //
271 //
272 //
273
274 static
275 void
ts_transform_stack_swap_drop(struct ts_transform_stack * const ts)276 ts_transform_stack_swap_drop(struct ts_transform_stack * const ts)
277 {
278 assert(ts->count >= 2);
279
280 union ts_transform_stack_3x3_u * const tos = ts_transform_stack_tos(ts);
281
282 ts_transform_stack_3x3_u_copy(tos-1,tos);
283
284 ts->weakrefs[ts->count-2] = ts->weakrefs[ts->count-1];
285
286 ts->count -= 1;
287 }
288
289 //
290 //
291 //
292
293 static
294 void
ts_transform_stack_store_matrix_8(struct ts_transform_stack * const ts,uint32_t const idx,ts_transform_float_t const sx,ts_transform_float_t const shx,ts_transform_float_t const tx,ts_transform_float_t const shy,ts_transform_float_t const sy,ts_transform_float_t const ty,ts_transform_float_t const w0,ts_transform_float_t const w1)295 ts_transform_stack_store_matrix_8(struct ts_transform_stack * const ts,
296 uint32_t const idx,
297 ts_transform_float_t const sx,
298 ts_transform_float_t const shx,
299 ts_transform_float_t const tx,
300 ts_transform_float_t const shy,
301 ts_transform_float_t const sy,
302 ts_transform_float_t const ty,
303 ts_transform_float_t const w0,
304 ts_transform_float_t const w1)
305 {
306 union ts_transform_stack_3x3_u * t = ts->transforms + idx;
307
308 t->sx = sx;
309 t->shx = shx;
310 t->tx = tx;
311
312 t->shy = shy;
313 t->sy = sy;
314 t->ty = ty;
315
316 t->w0 = w0;
317 t->w1 = w1;
318
319 ts->weakrefs[idx] = TS_TRANSFORM_WEAKREF_INVALID;
320 }
321
322 //
323 //
324 //
325
326 static
327 void
ts_transform_stack_store_matrix(struct ts_transform_stack * const ts,uint32_t const idx,ts_transform_float_t const sx,ts_transform_float_t const shx,ts_transform_float_t const tx,ts_transform_float_t const shy,ts_transform_float_t const sy,ts_transform_float_t const ty,ts_transform_float_t const w0,ts_transform_float_t const w1,ts_transform_float_t const w2)328 ts_transform_stack_store_matrix(struct ts_transform_stack * const ts,
329 uint32_t const idx,
330 ts_transform_float_t const sx,
331 ts_transform_float_t const shx,
332 ts_transform_float_t const tx,
333 ts_transform_float_t const shy,
334 ts_transform_float_t const sy,
335 ts_transform_float_t const ty,
336 ts_transform_float_t const w0,
337 ts_transform_float_t const w1,
338 ts_transform_float_t const w2)
339 {
340 if (w2 == TS_TRANSFORM_ONE)
341 {
342 ts_transform_stack_store_matrix_8(ts,idx,
343 sx, shx,tx,
344 shy,sy, ty,
345 w0, w1);
346 }
347 else
348 {
349 // normalize
350 ts_transform_float_t d = TS_TRANSFORM_RCP(w2);
351
352 ts_transform_stack_store_matrix_8(ts,idx,
353 sx * d, shx * d, tx * d,
354 shy * d, sy * d, ty * d,
355 w0 * d, w1 * d);
356 }
357 }
358
359 //
360 //
361 //
362
363 static
364 void
ts_transform_stack_push_matrix_8(struct ts_transform_stack * const ts,ts_transform_float_t const sx,ts_transform_float_t const shx,ts_transform_float_t const tx,ts_transform_float_t const shy,ts_transform_float_t const sy,ts_transform_float_t const ty,ts_transform_float_t const w0,ts_transform_float_t const w1)365 ts_transform_stack_push_matrix_8(struct ts_transform_stack * const ts,
366 ts_transform_float_t const sx,
367 ts_transform_float_t const shx,
368 ts_transform_float_t const tx,
369 ts_transform_float_t const shy,
370 ts_transform_float_t const sy,
371 ts_transform_float_t const ty,
372 ts_transform_float_t const w0,
373 ts_transform_float_t const w1)
374 {
375 ts_transform_stack_ensure(ts);
376
377 ts_transform_stack_store_matrix_8(ts,ts->count++,
378 sx, shx,tx,
379 shy,sy, ty,
380 w0, w1);
381 }
382
383 //
384 //
385 //
386
387 void
ts_transform_stack_push_matrix(struct ts_transform_stack * const ts,ts_transform_float_t const sx,ts_transform_float_t const shx,ts_transform_float_t const tx,ts_transform_float_t const shy,ts_transform_float_t const sy,ts_transform_float_t const ty,ts_transform_float_t const w0,ts_transform_float_t const w1,ts_transform_float_t const w2)388 ts_transform_stack_push_matrix(struct ts_transform_stack * const ts,
389 ts_transform_float_t const sx,
390 ts_transform_float_t const shx,
391 ts_transform_float_t const tx,
392 ts_transform_float_t const shy,
393 ts_transform_float_t const sy,
394 ts_transform_float_t const ty,
395 ts_transform_float_t const w0,
396 ts_transform_float_t const w1,
397 ts_transform_float_t const w2)
398 {
399 if (w2 == TS_TRANSFORM_ONE)
400 {
401 ts_transform_stack_push_matrix_8(ts,
402 sx, shx,tx,
403 shy,sy, ty,
404 w0, w1);
405 }
406 else
407 {
408 // normalize
409 ts_transform_float_t d = TS_TRANSFORM_RCP(w2);
410
411 ts_transform_stack_push_matrix_8(ts,
412 sx * d, shx * d, tx * d,
413 shy * d, sy * d, ty * d,
414 w0 * d, w1 * d);
415 }
416 }
417
418 //
419 //
420 //
421
422 void
ts_transform_stack_push_identity(struct ts_transform_stack * const ts)423 ts_transform_stack_push_identity(struct ts_transform_stack * const ts)
424 {
425 ts_transform_stack_push_matrix_8(ts,
426 1.0, 0.0, 0.0,
427 0.0, 1.0, 0.0,
428 0.0, 0.0);
429 }
430
431 void
ts_transform_stack_push_affine(struct ts_transform_stack * const ts,ts_transform_float_t const sx,ts_transform_float_t const shx,ts_transform_float_t const tx,ts_transform_float_t const shy,ts_transform_float_t const sy,ts_transform_float_t const ty)432 ts_transform_stack_push_affine(struct ts_transform_stack * const ts,
433 ts_transform_float_t const sx,
434 ts_transform_float_t const shx,
435 ts_transform_float_t const tx,
436 ts_transform_float_t const shy,
437 ts_transform_float_t const sy,
438 ts_transform_float_t const ty)
439 {
440 ts_transform_stack_push_matrix_8(ts,
441 sx, shx, tx,
442 shy, sy, ty,
443 0.0, 0.0);
444 }
445
446 void
ts_transform_stack_push_translate(struct ts_transform_stack * const ts,ts_transform_float_t const tx,ts_transform_float_t const ty)447 ts_transform_stack_push_translate(struct ts_transform_stack * const ts,
448 ts_transform_float_t const tx,
449 ts_transform_float_t const ty)
450 {
451 ts_transform_stack_push_matrix_8(ts,
452 1.0, 0.0, tx,
453 0.0, 1.0, ty,
454 0.0, 0.0);
455 }
456
457 void
ts_transform_stack_push_scale(struct ts_transform_stack * const ts,ts_transform_float_t const sx,ts_transform_float_t const sy)458 ts_transform_stack_push_scale(struct ts_transform_stack * const ts,
459 ts_transform_float_t const sx,
460 ts_transform_float_t const sy)
461 {
462 ts_transform_stack_push_matrix_8(ts,
463 sx, 0.0, 0.0,
464 0.0, sy, 0.0,
465 0.0, 0.0);
466 }
467
468 void
ts_transform_stack_push_shear(struct ts_transform_stack * const ts,ts_transform_float_t const shx,ts_transform_float_t const shy)469 ts_transform_stack_push_shear(struct ts_transform_stack * const ts,
470 ts_transform_float_t const shx,
471 ts_transform_float_t const shy)
472 {
473 ts_transform_stack_push_matrix_8(ts,
474 1.0, shx, 0.0,
475 shy, 1.0, 0.0,
476 0.0, 0.0);
477 }
478
479 void
ts_transform_stack_push_skew_x(struct ts_transform_stack * const ts,ts_transform_float_t const theta)480 ts_transform_stack_push_skew_x(struct ts_transform_stack * const ts,
481 ts_transform_float_t const theta)
482 {
483 ts_transform_float_t const tan_theta = TS_TRANSFORM_TAN(theta); // replace with tanpi if available
484
485 ts_transform_stack_push_matrix_8(ts,
486 1.0, tan_theta,0.0,
487 0.0, 1.0, 0.0,
488 0.0, 0.0);
489 }
490
491 void
ts_transform_stack_push_skew_y(struct ts_transform_stack * const ts,ts_transform_float_t const theta)492 ts_transform_stack_push_skew_y(struct ts_transform_stack * const ts,
493 ts_transform_float_t const theta)
494 {
495 ts_transform_float_t const tan_theta = TS_TRANSFORM_TAN(theta); // replace with tanpi if available
496
497 ts_transform_stack_push_matrix_8(ts,
498 1.0, 0.0, 0.0,
499 tan_theta, 1.0, 0.0,
500 0.0, 0.0);
501 }
502
503 void
ts_transform_stack_push_rotate(struct ts_transform_stack * const ts,ts_transform_float_t const theta)504 ts_transform_stack_push_rotate(struct ts_transform_stack * const ts,
505 ts_transform_float_t const theta)
506 {
507 ts_transform_float_t const cos_theta = TS_TRANSFORM_COS(theta); // replace with cospi if available
508 ts_transform_float_t const sin_theta = TS_TRANSFORM_SIN(theta); // replace with sinpi if available
509
510 ts_transform_stack_push_matrix_8(ts,
511 cos_theta,-sin_theta, 0.0,
512 sin_theta, cos_theta, 0.0,
513 0.0, 0.0);
514 }
515
516 void
ts_transform_stack_push_rotate_xy2(struct ts_transform_stack * const ts,ts_transform_float_t const theta,ts_transform_float_t const cx,ts_transform_float_t const cy,ts_transform_float_t const tx,ts_transform_float_t const ty)517 ts_transform_stack_push_rotate_xy2(struct ts_transform_stack * const ts,
518 ts_transform_float_t const theta,
519 ts_transform_float_t const cx,
520 ts_transform_float_t const cy,
521 ts_transform_float_t const tx,
522 ts_transform_float_t const ty)
523 {
524 ts_transform_float_t const cos_theta = TS_TRANSFORM_COS(theta); // replace with cospi if available
525 ts_transform_float_t const sin_theta = TS_TRANSFORM_SIN(theta); // replace with sinpi if available
526
527 ts_transform_stack_push_matrix_8(ts,
528 cos_theta,-sin_theta, tx - (cx * cos_theta) + (cy * sin_theta),
529 sin_theta, cos_theta, ty - (cx * sin_theta) - (cy * cos_theta),
530 0.0, 0.0);
531 }
532
533 void
ts_transform_stack_push_rotate_xy(struct ts_transform_stack * const ts,ts_transform_float_t const theta,ts_transform_float_t const cx,ts_transform_float_t const cy)534 ts_transform_stack_push_rotate_xy(struct ts_transform_stack * const ts,
535 ts_transform_float_t const theta,
536 ts_transform_float_t const cx,
537 ts_transform_float_t const cy)
538 {
539 ts_transform_stack_push_rotate_xy2(ts,theta,cx,cy,cx,cy);
540 }
541
542 void
ts_transform_stack_push_rotate_scale_xy(struct ts_transform_stack * const ts,ts_transform_float_t const theta,ts_transform_float_t const sx,ts_transform_float_t const sy,ts_transform_float_t const cx,ts_transform_float_t const cy)543 ts_transform_stack_push_rotate_scale_xy(struct ts_transform_stack * const ts,
544 ts_transform_float_t const theta,
545 ts_transform_float_t const sx,
546 ts_transform_float_t const sy,
547 ts_transform_float_t const cx,
548 ts_transform_float_t const cy)
549 {
550 ts_transform_float_t const cos_theta = TS_TRANSFORM_COS(theta); // replace with cospi if available
551 ts_transform_float_t const sin_theta = TS_TRANSFORM_SIN(theta); // replace with sinpi if available
552
553 ts_transform_stack_push_matrix_8(ts,
554 sx*cos_theta,-sx*sin_theta, cx - cx*sx*cos_theta + cy*sy*sin_theta,
555 sy*sin_theta, sy*cos_theta, cy - cy*sy*cos_theta - cx*sx*sin_theta,
556 0.0, 0.0);
557 }
558
559 //
560 // See: "Fundamentals of Texture Mapping and Image Warping" by Paul S. Heckbert (1989)
561 //
562
563 #define DET(a,b,c,d) (a * d - b * c)
564
565 #define X(v,i) v[i*2]
566 #define Y(v,i) v[i*2+1]
567
568 //
569 //
570 //
571
572 ts_transform_type_e
ts_transform_stack_adjoint(struct ts_transform_stack * const ts)573 ts_transform_stack_adjoint(struct ts_transform_stack * const ts)
574 {
575 union ts_transform_stack_3x3_u * const t = ts_transform_stack_tos(ts);
576
577 #if 0
578 // save for determinant
579 ts_transform_float_t const a = t->a;
580 ts_transform_float_t const b = t->b;
581 ts_transform_float_t const c = t->c;
582 #endif
583
584 ts_transform_stack_store_matrix(ts,ts->count-1,
585
586 +DET(t->e, t->f, t->h, TS_TRANSFORM_ONE),
587 -DET(t->b, t->c, t->h, TS_TRANSFORM_ONE),
588 +DET(t->b, t->c, t->e, t->f),
589
590 -DET(t->d, t->f, t->g, TS_TRANSFORM_ONE),
591 +DET(t->a, t->c, t->g, TS_TRANSFORM_ONE),
592 -DET(t->a, t->c, t->d, t->f),
593
594 +DET(t->d, t->e, t->g, t->h),
595 -DET(t->a, t->b, t->g, t->h),
596 +DET(t->a, t->b, t->d, t->e));
597
598 #if 0
599 // determinant of t
600 ts_transform_float_t const det = a * t->a + b * t->d + c * t->g;
601 #endif
602
603 return ts_transform_stack_classify(ts);
604 }
605
606 //
607 //
608 //
609
610 ts_transform_type_e
ts_transform_stack_push_unit_to_quad(struct ts_transform_stack * const ts,ts_transform_float_t const quad[8])611 ts_transform_stack_push_unit_to_quad(struct ts_transform_stack * const ts,
612 ts_transform_float_t const quad[8])
613 {
614 ts_transform_float_t const x0 = X(quad,0);
615 ts_transform_float_t const y0 = Y(quad,0);
616
617 ts_transform_float_t const x1 = X(quad,1);
618 ts_transform_float_t const y1 = Y(quad,1);
619
620 ts_transform_float_t const x2 = X(quad,2);
621 ts_transform_float_t const y2 = Y(quad,2);
622
623 ts_transform_float_t const x3 = X(quad,3);
624 ts_transform_float_t const y3 = Y(quad,3);
625
626 ts_transform_float_t sx = x1 - x0;
627 ts_transform_float_t shy = y1 - y0;
628
629 ts_transform_float_t const dx2 = x3 - x2;
630 ts_transform_float_t const dy2 = y3 - y2;
631
632 ts_transform_float_t const dx3 = -sx - dx2;
633 ts_transform_float_t const dy3 = -shy - dy2;
634
635 // if both zero then quad_dst is a parallelogram and affine
636 if ((dx3 == TS_TRANSFORM_ZERO) && (dy3 == TS_TRANSFORM_ZERO))
637 {
638 ts_transform_float_t const shx = x2 - x1;
639 ts_transform_float_t const sy = y2 - y1;
640
641 ts_transform_stack_push_matrix_8(ts,
642 sx, shx, x0,
643 shy, sy, y0,
644 0.0, 0.0);
645
646 return TS_TRANSFORM_TYPE_AFFINE;
647 }
648 else
649 {
650 ts_transform_float_t const dx1 = x1 - x2;
651 ts_transform_float_t const dy1 = y1 - y2;
652
653 ts_transform_float_t const wx_den = dx1 * dy2 - dx2 * dy1;
654
655 if (wx_den == TS_TRANSFORM_ZERO)
656 return TS_TRANSFORM_TYPE_INVALID;
657
658 ts_transform_float_t const w0_num = dx3 * dy2 - dx2 * dy3;
659 ts_transform_float_t const w1_num = dx1 * dy3 - dx3 * dy1;
660
661 ts_transform_float_t const w0 = w0_num / wx_den;
662 ts_transform_float_t const w1 = w1_num / wx_den;
663
664 sx += w0 * x1;
665 ts_transform_float_t const shx = x3 - x0 + w1 * x3;
666
667 shy += w0 * y1;
668 ts_transform_float_t const sy = y3 - y0 + w1 * y3;
669
670 ts_transform_stack_push_matrix_8(ts,
671 sx, shx, x0,
672 shy, sy, y0,
673 w0, w1);
674
675 return TS_TRANSFORM_TYPE_PROJECTIVE;
676 }
677 }
678
679 //
680 //
681 //
682
683 ts_transform_type_e
ts_transform_stack_push_quad_to_unit(struct ts_transform_stack * const ts,float const quad[8])684 ts_transform_stack_push_quad_to_unit(struct ts_transform_stack * const ts,
685 float const quad[8])
686 {
687 if (ts_transform_stack_push_unit_to_quad(ts,quad) == TS_TRANSFORM_TYPE_INVALID)
688 return TS_TRANSFORM_TYPE_INVALID;
689
690 return ts_transform_stack_adjoint(ts);
691 }
692
693 //
694 //
695 //
696
697 ts_transform_type_e
ts_transform_stack_push_quad_to_quad(struct ts_transform_stack * const ts,ts_transform_float_t const quad_src[8],ts_transform_float_t const quad_dst[8])698 ts_transform_stack_push_quad_to_quad(struct ts_transform_stack * const ts,
699 ts_transform_float_t const quad_src[8],
700 ts_transform_float_t const quad_dst[8])
701 {
702 if (ts_transform_stack_push_unit_to_quad(ts,quad_dst) == TS_TRANSFORM_TYPE_INVALID)
703 return TS_TRANSFORM_TYPE_INVALID;
704
705 if (ts_transform_stack_push_quad_to_unit(ts,quad_src) == TS_TRANSFORM_TYPE_INVALID)
706 return TS_TRANSFORM_TYPE_INVALID;
707
708 ts_transform_stack_multiply(ts);
709
710 return ts_transform_stack_classify(ts);
711 }
712
713 //
714 //
715 //
716
717 ts_transform_type_e
ts_transform_stack_push_rect_to_quad(struct ts_transform_stack * const ts,ts_transform_float_t const x0,ts_transform_float_t const y0,ts_transform_float_t const x1,ts_transform_float_t const y1,ts_transform_float_t const quad_dst[8])718 ts_transform_stack_push_rect_to_quad(struct ts_transform_stack * const ts,
719 ts_transform_float_t const x0,
720 ts_transform_float_t const y0,
721 ts_transform_float_t const x1,
722 ts_transform_float_t const y1,
723 ts_transform_float_t const quad_dst[8])
724 {
725 if (ts_transform_stack_push_unit_to_quad(ts,quad_dst) == TS_TRANSFORM_TYPE_INVALID)
726 return TS_TRANSFORM_TYPE_INVALID;
727
728 ts_transform_stack_push_matrix_8(ts,
729 TS_TRANSFORM_RCP(x1-x0),
730 0.0,
731 -x0,
732 0.0,
733 TS_TRANSFORM_RCP(y1-y0),
734 -y0,
735 0.0,
736 0.0);
737
738 ts_transform_stack_multiply(ts);
739
740 return ts_transform_stack_classify(ts);
741 }
742
743 //
744 // The second matrix on the stack (TOS[-1]) is post-multiplied by the
745 // top matrix on the stack (TOS[0]).
746 //
747 // The result replaces TOS[0] and TOS[-1] is unmodified.
748 //
749 // The stack effect of concat is:
750 //
751 // | B | | A*B |
752 // | A | | A |
753 // | . | => | . |
754 // | . | | . |
755 // | . | | . |
756 //
757 void
ts_transform_stack_concat(struct ts_transform_stack * const ts)758 ts_transform_stack_concat(struct ts_transform_stack * const ts)
759 {
760 assert(ts->count >= 2);
761
762 // get A and B
763 union ts_transform_stack_3x3_u const * const B = ts_transform_stack_tos(ts);
764 union ts_transform_stack_3x3_u const * const A = B - 1;
765
766 ts_transform_stack_store_matrix(ts,ts->count-1,TS_TRANSFORM_MULTIPLY(A,B));
767 }
768
769 //
770 // The second matrix on the stack (TOS[-1]) is post-multiplied by the
771 // top matrix on the stack (TOS[0]).
772 //
773 // The result replaces both matrices.
774 //
775 // The stack effect of multiply is:
776 //
777 // | B | | A*B |
778 // | A | | . |
779 // | . | => | . |
780 // | . | | . |
781 // | . | | . |
782 //
783 void
ts_transform_stack_multiply(struct ts_transform_stack * const ts)784 ts_transform_stack_multiply(struct ts_transform_stack * const ts)
785 {
786 assert(ts->count >= 2);
787
788 // get A and B
789 union ts_transform_stack_3x3_u const * const B = ts_transform_stack_tos(ts);
790 union ts_transform_stack_3x3_u const * const A = B - 1;
791
792 ts_transform_stack_store_matrix(ts,ts->count-- - 2,TS_TRANSFORM_MULTIPLY(A,B));
793 }
794
795 //
796 //
797 //
798
799 void
ts_transform_stack_transform_xy(struct ts_transform_stack * const ts,ts_transform_float_t const x,ts_transform_float_t const y,ts_transform_float_t * const xp,ts_transform_float_t * const yp)800 ts_transform_stack_transform_xy(struct ts_transform_stack * const ts,
801 ts_transform_float_t const x,
802 ts_transform_float_t const y,
803 ts_transform_float_t * const xp,
804 ts_transform_float_t * const yp)
805 {
806 union ts_transform_stack_3x3_u const * const t = ts_transform_stack_tos(ts);
807
808 *xp = x * t->sx + y * t->shx + t->tx;
809 *yp = x * t->shy + y * t->sy + t->ty;
810
811 if (!TS_IS_AFFINE(t))
812 {
813 ts_transform_float_t const d = TS_TRANSFORM_RCP(x * t->w0 + y * t->w1 + TS_TRANSFORM_ONE);
814
815 *xp *= d;
816 *yp *= d;
817 }
818 }
819
820 //
821 // test it!
822 //
823
824 #ifdef TS_DEBUG
825
826 #include <stdio.h>
827
828 #define TS_DEBUG_SCALE 32.0
829
830 //
831 //
832 //
833
834 void
ts_transform_stack_tos_debug(struct ts_transform_stack * const ts)835 ts_transform_stack_tos_debug(struct ts_transform_stack * const ts)
836 {
837 union ts_transform_stack_3x3_u const * const t = ts_transform_stack_tos(ts);
838
839 printf("{ { %13.5f, %13.5f, %13.5f },\n"
840 " { %13.5f, %13.5f, %13.5f },\n"
841 " { %13.5f, %13.5f, %13.5f } }\n",
842 t->a8[0],
843 t->a8[1],
844 t->a8[2],
845 t->a8[3],
846 t->a8[4],
847 t->a8[5],
848 t->a8[6],
849 t->a8[7],
850 TS_TRANSFORM_ONE);
851 }
852
853 //
854 //
855 //
856
857 void
ts_debug(struct ts_transform_stack * const ts,ts_transform_float_t const quad[8])858 ts_debug(struct ts_transform_stack * const ts,
859 ts_transform_float_t const quad[8])
860 {
861 ts_transform_stack_tos_debug(ts);
862
863 for (int ii=0; ii<8; ii+=2)
864 {
865 ts_transform_float_t xp,yp;
866
867 ts_transform_stack_transform_xy(ts,
868 quad[ii],quad[ii+1],
869 &xp,&yp);
870
871 printf("( %13.2f, %13.2f ) \t-> ( %13.2f, %13.2f )\n",
872 xp,yp,xp/TS_DEBUG_SCALE,yp/TS_DEBUG_SCALE);
873 }
874 }
875
876 //
877 //
878 //
879
880 int
main(int argc,char * argv[])881 main(int argc, char * argv[])
882 {
883 struct ts_transform_stack * const ts = ts_transform_stack_create(32);
884
885 ts_transform_float_t const w = 1000;
886 ts_transform_float_t const h = 1000;
887
888 #if 1
889 ts_transform_stack_push_scale(ts,TS_DEBUG_SCALE,TS_DEBUG_SCALE);
890
891 // OpenGL'ism
892 ts_transform_stack_push_affine(ts,
893 1.0f, 0.0f,0.0f,
894 0.0f,-1.0f,h);
895 // multiply
896 ts_transform_stack_concat(ts);
897 #else
898 ts_transform_stack_push_identity(ts);
899 #endif
900
901 uint32_t const restore = ts_transform_stack_save(ts);
902
903 //
904 //
905 //
906 ts_transform_float_t const quad_src[8] = { 0.0f,0.0f,
907 w, 0.0f,
908 w, h,
909 0.0f,h };
910
911 ts_transform_float_t const quad_dst[8] = { 300.0f, 0.0f,
912 w-300.0f, 0.0f,
913 w, h,
914 0.0f, h };
915
916 ts_transform_float_t const quad_tst[8] = { 50, 50,
917 1550, 50,
918 1550, 1550,
919 50, 1550 };
920 //
921 // RECT TO QUAD
922 //
923 printf("type = %d\n",
924 ts_transform_stack_push_rect_to_quad(ts,
925 0.0, 0.0,
926 w, h,
927 quad_dst));
928 ts_transform_stack_concat(ts);
929
930 ts_debug(ts,quad_src);
931
932 //
933 // QUAD TO QUAD
934 //
935 ts_transform_stack_restore(ts,restore);
936
937 printf("type = %d\n",
938 ts_transform_stack_push_quad_to_quad(ts,
939 quad_src,
940 quad_dst));
941 ts_transform_stack_concat(ts);
942
943 ts_debug(ts,quad_src);
944
945 //
946 // DIRECT
947 //
948 ts_transform_stack_restore(ts,restore);
949
950 ts_transform_stack_push_matrix(ts,
951 0.87004626f, -0.35519487f, 72.14745f,
952 0.0f, 0.2600208f, 86.16314f,
953 0.0f, -0.0029599573f, 1.0f);
954
955 ts_transform_stack_concat(ts);
956
957 ts_transform_float_t const quad_foo[8] = { -10, 10,
958 130, 10,
959 130, 110,
960 -10, 110 };
961
962 ts_debug(ts,quad_foo);
963
964 return EXIT_SUCCESS;
965 }
966
967 #endif
968
969 //
970 //
971 //
972