| TGX 1.1.4 A tiny 2D/3D graphics library optimized for 32 bits microcontrollers.

Loading...
Searching...
No Matches
Rasterizer.h
Go to the documentation of this file.
1
5//
6// Copyright 2020 Arvind Singh
7//
8// This library is free software; you can redistribute it and/or
9// modify it under the terms of the GNU Lesser General Public
10// License as published by the Free Software Foundation; either
11// version 2.1 of the License, or (at your option) any later version.
12//
13// This library is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the GNU
16// Lesser General Public License for more details.
17//
18// You should have received a copy of the GNU Lesser General Public
19// License along with this library; If not, see <http://www.gnu.org/licenses/>.
20#ifndef _TGX_RASTERIZER_H_
21#define _TGX_RASTERIZER_H_
22
23
24// only C++, no plain C
25#ifdef __cplusplus
26
27
28#include "ShaderParams.h"
29
30 namespace tgx
31{
32
46#define TGX_RASTERIZE_SUBPIXEL_BITS (6)
47
48#define TGX_RASTERIZE_SUBPIXEL256 (1 << TGX_RASTERIZE_SUBPIXEL_BITS)
49#define TGX_RASTERIZE_SUBPIXEL128 (1 << (TGX_RASTERIZE_SUBPIXEL_BITS -1))
50#define TGX_RASTERIZE_MULT256(X) ((X) << (TGX_RASTERIZE_SUBPIXEL_BITS))
51#define TGX_RASTERIZE_MULT128(X) ((X) << (TGX_RASTERIZE_SUBPIXEL_BITS -1))
52#define TGX_RASTERIZE_DIV256(X) ((X) >> (TGX_RASTERIZE_SUBPIXEL_BITS))
53
54
55
56
57TGX_INLINE inline void minmax3_i32(const int32_t a, const int32_t b, const int32_t c, int32_t& mn, int32_t& mx)
58 {
59 if (a < b) { mn = a; mx = b; } else { mn = b; mx = a; }
60 if (c < mn) { mn = c; } else if (c > mx) { mx = c; }
61 }
62
63
64TGX_INLINE inline int32_t tgx_floor_div_subpixel_i32(const int32_t x)
65 {
66#if defined(__GNUC__) || defined(__clang__)
67 // Assumes arithmetic right shift for signed integers: his is what GCC/Clang generate on ARM, Xtensa, etc.
68 return x >> TGX_RASTERIZE_SUBPIXEL_BITS;
69#else
70 // Portable mathematical floor(x / S), S > 0.
71 const int32_t S = TGX_RASTERIZE_SUBPIXEL256;
72 return (x >= 0) ? (x / S) : -(((-x) + S - 1) / S);
73#endif
74 }
75
76
77TGX_INLINE inline int32_t tgx_ceil_div_subpixel_i32(const int32_t x)
78 {
79#if defined(__GNUC__) || defined(__clang__)
80 // ceil(x / S) == floor((x + S - 1) / S) for positive power-of-two S, assuming no overflow in x + S - 1.
81 return (x + (TGX_RASTERIZE_SUBPIXEL256 - 1)) >> TGX_RASTERIZE_SUBPIXEL_BITS;
82#else
83 // Portable mathematical ceil(x / S), S > 0.
84 const int32_t S = TGX_RASTERIZE_SUBPIXEL256;
85 return (x >= 0) ? ((x + S - 1) / S) : -((-x) / S);
86#endif
87 }
88
89
90
91
141 template<auto shader_function, typename RASTERIZER_PARAMS>
142 TGX_RASTERIZE_TRIANGLE_INLINE inline void rasterizeTriangle(const int LX, const int LY, const RasterizerVec4 & V0, const RasterizerVec4 & V1, const RasterizerVec4 & V2, const int32_t offset_x, const int32_t offset_y, const RASTERIZER_PARAMS & data)
143 {
144 // assuming that clipping was already perfomed and that V0, V1, V2 are in a reasonable "range" so no overflow will occur.
145 const int32_t hx = TGX_RASTERIZE_MULT128(LX);
146 const int32_t hy = TGX_RASTERIZE_MULT128(LY);
147 const float mx = (float)(hx);
148 const float my = (float)(hy);
149
150 const iVec2 P0(lfloorf(V0.x * mx), lfloorf(V0.y * my));
151 const iVec2 sP1(lfloorf(V1.x * mx), lfloorf(V1.y * my));
152 const iVec2 sP2(lfloorf(V2.x * mx), lfloorf(V2.y * my));
153
154 int32_t umx, uMx, umy, uMy;
155 minmax3_i32(P0.x, sP1.x, sP2.x, umx, uMx);
156 minmax3_i32(P0.y, sP1.y, sP2.y, umy, uMy);
157
158 const int32_t bx0 = umx + hx - TGX_RASTERIZE_SUBPIXEL128;
159 const int32_t bx1 = uMx + hx - TGX_RASTERIZE_SUBPIXEL128;
160 const int32_t by0 = umy + hy - TGX_RASTERIZE_SUBPIXEL128;
161 const int32_t by1 = uMy + hy - TGX_RASTERIZE_SUBPIXEL128;
162 int32_t xmin = tgx_ceil_div_subpixel_i32(bx0);
163 int32_t xmax = tgx_floor_div_subpixel_i32(bx1);
164 int32_t ymin = tgx_ceil_div_subpixel_i32(by0);
165 int32_t ymax = tgx_floor_div_subpixel_i32(by1);
166
167 //if ((xmin > xmax) || (ymin > ymax)) return;
168
169 // Intersect the sub-image with the triangle bounding box.
170 int32_t sx = data.im->lx();
171 int32_t sy = data.im->ly();
172 int32_t ox = offset_x;
173 int32_t oy = offset_y;
174
175 if (ox < xmin) { sx -= (xmin - ox); ox = xmin; }
176 if (ox + sx > xmax) { sx = xmax - ox + 1; }
177 if (sx <= 0) return;
178
179 if (oy < ymin) { sy -= (ymin - oy); oy = ymin; }
180 if (oy + sy > ymax) { sy = ymax - oy + 1; }
181 if (sy <= 0) return;
182
183 const uint32_t bw = (uint32_t)uMx - (uint32_t)umx;
184 const uint32_t bh = (uint32_t)uMy - (uint32_t)umy;
185 const bool c32 = ((bw < 32768u) && (bh < 32768u));
186 int32_t a;
187 if (c32)
188 { // 32 bits computation
189 a = (((sP2.x - P0.x) * (sP1.y - P0.y)) - ((sP2.y - P0.y) * (sP1.x - P0.x)));
190 if (a == 0) return;
191 }
192 else
193 { // 64 bits computations
194 const int64_t a64 = (((int64_t)(sP2.x - P0.x)) * ((int64_t)(sP1.y - P0.y))) - (((int64_t)(sP2.y - P0.y)) * ((int64_t)(sP1.x - P0.x)));
195 if (a64 == 0) return;
196 a = (a64 > 0) ? 1 : -1;
197 }
198
199 const RasterizerVec4& fP1 = (a > 0) ? V1 : V2;
200 const RasterizerVec4& fP2 = (a > 0) ? V2 : V1;
201 const iVec2& P1 = (a > 0) ? sP1 : sP2;
202 const iVec2& P2 = (a > 0) ? sP2 : sP1;
203
204 const int32_t us = TGX_RASTERIZE_MULT256(ox) - hx + TGX_RASTERIZE_SUBPIXEL128; // start pixel position
205 const int32_t vs = TGX_RASTERIZE_MULT256(oy) - hy + TGX_RASTERIZE_SUBPIXEL128; //
206
207 ox -= offset_x;
208 oy -= offset_y;
209
210 int32_t dx1 = P1.y - P0.y;
211 int32_t dy1 = P0.x - P1.x;
212 int32_t dx2 = P2.y - P1.y;
213 int32_t dy2 = P1.x - P2.x;
214 int32_t dx3 = P0.y - P2.y;
215 int32_t dy3 = P2.x - P0.x;
216
217 int32_t O1, O2, O3;
218
219 if (c32)
220 { // 32 bits computation
221 O1 = ((us - P0.x) * dx1) + ((vs - P0.y) * dy1);
222 O3 = ((us - P2.x) * dx3) + ((vs - P2.y) * dy3);
223
224 // Before top-left correction: O1 + O2 + O3 = A32. Use unsigned arithmetic to avoid signed-overflow UB in the reconstruction.
225 const int32_t A32 = (a > 0) ? a : -a;
226 O2 = (int32_t)((uint32_t)A32 - (uint32_t)O1 - (uint32_t)O3);
227
228 if ((dx1 < 0) || ((dx1 == 0) && (dy1 < 0))) O1--;
229 if ((dx2 < 0) || ((dx2 == 0) && (dy2 < 0))) O2--;
230 if ((dx3 < 0) || ((dx3 == 0) && (dy3 < 0))) O3--;
231
232 dx1 *= TGX_RASTERIZE_SUBPIXEL256;
233 dy1 *= TGX_RASTERIZE_SUBPIXEL256;
234 dx2 *= TGX_RASTERIZE_SUBPIXEL256;
235 dy2 *= TGX_RASTERIZE_SUBPIXEL256;
236 dx3 *= TGX_RASTERIZE_SUBPIXEL256;
237 dy3 *= TGX_RASTERIZE_SUBPIXEL256;
238 }
239 else
240 { // 64 bits computation
241 int64_t dO1 = (((int64_t)(us - P0.x)) * ((int64_t)dx1)) + (((int64_t)(vs - P0.y)) * ((int64_t)dy1));
242 if ((dx1 < 0) || ((dx1 == 0) && (dy1 < 0))) dO1--; // top left rule (beware, changes total aera).
243 O1 = (dO1 >= 0) ? ((int32_t)TGX_RASTERIZE_DIV256(dO1)) : -((int32_t)TGX_RASTERIZE_DIV256(-dO1 + (TGX_RASTERIZE_SUBPIXEL256 - 1)));
244
245 int64_t dO2 = (((int64_t)(us - P1.x)) * ((int64_t)dx2)) + (((int64_t)(vs - P1.y)) * ((int64_t)dy2));
246 if ((dx2 < 0) || ((dx2 == 0) && (dy2 < 0))) dO2--; // top left rule (beware, changes total aera).
247 O2 = (dO2 >= 0) ? ((int32_t)TGX_RASTERIZE_DIV256(dO2)) : -((int32_t)TGX_RASTERIZE_DIV256(-dO2 + (TGX_RASTERIZE_SUBPIXEL256 - 1)));
248
249 int64_t dO3 = (((int64_t)(us - P2.x)) * ((int64_t)dx3)) + (((int64_t)(vs - P2.y)) * ((int64_t)dy3));
250 if ((dx3 < 0) || ((dx3 == 0) && (dy3 < 0))) dO3--; // top left rule (beware, changes total aera).
251 O3 = (dO3 >= 0) ? ((int32_t)TGX_RASTERIZE_DIV256(dO3)) : -((int32_t)TGX_RASTERIZE_DIV256(-dO3 + (TGX_RASTERIZE_SUBPIXEL256 - 1)));
252 }
253
254 // beware that O1 + O2 + O3 = 0 is possible now but still we should not discard the triangle:
255 // this case must be dealt with inside the shader...
256 if (sx == 1)
257 {
258 while (((O1 | O2 | O3) < 0) && (sy > 0))
259 {
260 sy--;
261 oy++;
262 O1 += dy1;
263 O2 += dy2;
264 O3 += dy3;
265 }
266 if (sy == 0) return;
267 }
268 else if (sy == 1)
269 {
270 while (((O1 | O2 | O3) < 0) && (sx > 0))
271 {
272 sx--;
273 ox++;
274 O1 += dx1;
275 O2 += dx2;
276 O3 += dx3;
277 }
278 if (sx == 0) return;
279 }
280
281 const RasterizerVec4* F1 = &fP2;
282 const RasterizerVec4* F2 = &V0;
283 const RasterizerVec4* F3 = &fP1;
284
285 if (dx1 <= 0)
286 {
287 if (dx2 > 0)
288 {
289 // Rotate left: edge2, edge3, edge1
290 const int32_t tdx = dx1;
291 const int32_t tdy = dy1;
292 const int32_t tO = O1;
293 const RasterizerVec4* tF = F1;
294
295 dx1 = dx2;
296 dy1 = dy2;
297 O1 = O2;
298 F1 = F2;
299
300 dx2 = dx3;
301 dy2 = dy3;
302 O2 = O3;
303 F2 = F3;
304
305 dx3 = tdx;
306 dy3 = tdy;
307 O3 = tO;
308 F3 = tF;
309 }
310 else
311 {
312 // Rotate right: edge3, edge1, edge2
313 const int32_t tdx = dx3;
314 const int32_t tdy = dy3;
315 const int32_t tO = O3;
316 const RasterizerVec4* tF = F3;
317
318 dx3 = dx2;
319 dy3 = dy2;
320 O3 = O2;
321 F3 = F2;
322
323 dx2 = dx1;
324 dy2 = dy1;
325 O2 = O1;
326 F2 = F1;
327
328 dx1 = tdx;
329 dy1 = tdy;
330 O1 = tO;
331 F1 = tF;
332 }
333 }
334
335 shader_function(ox, oy, sx, sy, dx1, dy1, O1, *F1, dx2, dy2, O2, *F2, dx3, dy3, O3, *F3, data);
336
337 return;
338 }
339
340
341
342
343
344
345
346
347}
348
349#endif
350
351#endif
352
tgx::lfloorf
TGX_INLINE int32_t lfloorf(float x)
Compute (int32_t)floorf(x).
Definition: Misc.h:441
TGX_RASTERIZE_SUBPIXEL_BITS
#define TGX_RASTERIZE_SUBPIXEL_BITS
Sub-pixel precision bits.
Definition: Rasterizer.h:46
tgx::rasterizeTriangle
TGX_RASTERIZE_TRIANGLE_INLINE void rasterizeTriangle(const int LX, const int LY, const RasterizerVec4 &V0, const RasterizerVec4 &V1, const RasterizerVec4 &V2, const int32_t offset_x, const int32_t offset_y, const RASTERIZER_PARAMS &data)
Fast triangle rasterizer for 3D graphics:
Definition: Rasterizer.h:142
ShaderParams.h
Triangle shader parameters.
tgx::Vec2
Generic 2D vector [specializations iVec2, fVec2, dVec2].
Definition: Vec2.h:64
tgx::Vec2::x
T x
'x' coordinate (first dimension)
Definition: Vec2.h:72
tgx::Vec2::y
T y
'y' coordinate (second dimension)
Definition: Vec2.h:73