1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|
#include <stdio.h>
#include <math.h>
#include <pixman.h>
#include <gtk/gtk.h>
typedef pixman_fixed_16_16_t fixed_t;
#define fixed_e ((fixed_t) 1)
#define fixed_1 (int_to_fixed(1))
#define fixed_1_minus_e (fixed_1 - fixed_e)
#define fixed_to_int(f) ((int) ((f) >> 16))
#define int_to_fixed(i) ((fixed_t) ((i) << 16))
#define fixed_frac(f) ((f) & pixman_fixed_1_minus_e)
#define fixed_floor(f) ((f) & ~pixman_fixed_1_minus_e)
#define fixed_ceil(f) pixman_fixed_floor ((f) + pixman_fixed_1_minus_e)
#define fixed_mod_2(f) ((f) & (pixman_fixed1 | pixman_fixed_1_minus_e))
#define fixed_to_double(f) (double) ((f) / (double) pixman_fixed_1)
#define double_to_fixed(d) ((pixman_fixed_t) ((d) * 65536.0))
/*
* +--------------------------------------------------+
* | <Y_FRAC_FIRST> |
* | <X_FRAC_FIRST> * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | * * * * * * * * * * * * * * * * * |
* | | <BIG_STEP> |
* +--------------------------------------------------+
*/
#define MAX_ALPHA(n) ((1 << (n)) - 1)
#define N_Y_FRAC(n) ((n) == 1 ? 1 : (1 << ((n)/2)) - 1)
#define N_X_FRAC(n) ((n) == 1 ? 1 : (1 << ((n)/2)) + 1)
#define STEP_Y_SMALL(n) (fixed_1 / N_Y_FRAC(n))
#define STEP_Y_BIG(n) (fixed_1 - (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))
#define Y_FRAC_FIRST(n) (STEP_Y_SMALL(n) / 2)
#define Y_FRAC_LAST(n) (Y_FRAC_FIRST(n) + (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))
#define STEP_X_SMALL(n) (pixman_fixed_1 / N_X_FRAC(n))
#define STEP_X_BIG(n) (pixman_fixed_1 - (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))
#define X_FRAC_FIRST(n) (STEP_X_SMALL(n) / 2)
#define X_FRAC_LAST(n) (X_FRAC_FIRST(n) + (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))
typedef struct edge_t edge_t;
struct edge_t
{
fixed_t x0;
fixed_t y0;
fixed_t x1;
fixed_t y1;
};
#define N_GRID_X 17
#define N_GRID_Y 15
static fixed_t
next_sample_x (fixed_t x)
{
pixman_fixed_t f = pixman_fixed_frac(x);
pixman_fixed_t i = pixman_fixed_floor(x);
f = ((f + Y_FRAC_FIRST(N_GRID_X)) / STEP_Y_SMALL(N_GRID_X)) * STEP_Y_SMALL(N_GRID_X) + Y_FRAC_FIRST(N_GRID_X);
if (f > Y_FRAC_LAST(N_GRID_X))
{
f = Y_FRAC_FIRST(N_GRID_X);
i += pixman_fixed_1;
}
return (i | f);
}
static fixed_t
next_sample_y (fixed_t y)
{
pixman_fixed_t f = pixman_fixed_frac(y);
pixman_fixed_t i = pixman_fixed_floor(y);
f = ((f + Y_FRAC_FIRST(N_GRID_Y)) / STEP_Y_SMALL(N_GRID_Y)) * STEP_Y_SMALL(N_GRID_Y) + Y_FRAC_FIRST(N_GRID_Y);
if (f > Y_FRAC_LAST(N_GRID_Y))
{
f = Y_FRAC_FIRST(N_GRID_Y);
i += pixman_fixed_1;
}
return (i | f);
}
static fixed_t
sample_step_x (fixed_t x)
{
(void)x;
return 1.0;
}
static fixed_t
sample_step_y (fixed_t y)
{
if (pixman_fixed_frac (y) == Y_FRAC_LAST (N_GRID_Y))
{
return STEP_Y_BIG (N_GRID_Y);
}
else
{
return STEP_Y_SMALL (N_GRID_Y);
}
}
static void
dda (fixed x0, fixed y0, fixed x1, fixed y1)
{
fixed dx = x1 - x0;
fixed dy = y1 - y0;
int steep = fabs (dy) > fabs (dx);
fixed dx_sign;
fixed dy_sign;
fixed derror;
fixed xi;
fixed err;
fixed yi;
printf ("line: (%f %f) -> (%f %f) %s\n", x0, y0, x1, y1, steep? "[steep]" : "");
if (steep)
{
fixed t;
t = x0; x0 = y0; y0 = t;
t = x1; x1 = y1; y1 = t;
}
if (x0 > x1)
{
fixed t;
t = x0; x0 = x1; x1 = x0;
t = y0; y0 = y1; y1 = y0;
}
yi = next_sample_y (y0);
xi = next_sample_x (x0);
err = (yi - y0) * dx - (xi - x0) * dy;
dx_sign = (dx > 0) ? 1 : -1;
dy_sign = (dy > 0) ? 1 : -1;
derror = dx_sign * dy;
while (xi < next_sample_x (x1))
{
fixed px, py;
if (steep)
{
px = yi;
py = xi;
}
else
{
px = xi;
py = yi;
}
printf (" (%f %f) (err: %f) (de: %f)\n", px, py, err, derror);
err += derror;
if (err > dx || err < -dx)
{
yi += dy_sign * sample_step_y (yi);
err -= dx;
}
xi += sample_step_x (xi);
}
}
static void
ddda (double x0, double y0, double x1, double y1)
{
dda (pixman_double_to_fixed (x0),
pixman_double_to_fixed (y0),
pixman_double_to_fixed (x1),
pixman_double_to_fixed (y1));
}
int
main (int argc, char **argv)
{
gtk_init (&argc, &argv);
ddda (0.5, 0.5, 2.5, 1.6);
ddda (0.3, 0.2, 3.7, 2.2);
ddda (3.7, 2.2, 7.2, 2.8);
ddda (3.7, 2.2, 4.2, 7.2);
ddda (0.5, 0.5, 1.5, 1.5);
ddda (0.5, 0.5, 2.5, 2.5);
return 0;
}
|
