Blender V5.3
zbuf.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2001-2002 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9/*---------------------------------------------------------------------------*/
10/* Common includes */
11/*---------------------------------------------------------------------------*/
12
13#include <algorithm>
14#include <cstring>
15
16#include "MEM_guardedalloc.h"
17
18#include "BLI_math_base.hh"
19#include "BLI_math_base_c.hh"
20
21/* own includes */
22#include "zbuf.h"
23
24namespace blender {
25
26/* could enable at some point but for now there are far too many conversions */
27#ifdef __GNUC__
28# pragma GCC diagnostic ignored "-Wdouble-promotion"
29#endif
30
31/* ****************** Spans ******************************* */
32
33void zbuf_alloc_span(ZSpan *zspan, int rectx, int recty)
34{
35 memset(zspan, 0, sizeof(ZSpan));
36
37 zspan->rectx = rectx;
38 zspan->recty = recty;
39
40 zspan->span1 = MEM_new_array_uninitialized<float>(recty, "zspan");
41 zspan->span2 = MEM_new_array_uninitialized<float>(recty, "zspan");
42}
43
45{
46 if (zspan) {
47 MEM_SAFE_DELETE(zspan->span1);
48 MEM_SAFE_DELETE(zspan->span2);
49 }
50}
51
52/* reset range for clipping */
53static void zbuf_init_span(ZSpan *zspan)
54{
55 zspan->miny1 = zspan->miny2 = zspan->recty + 1;
56 zspan->maxy1 = zspan->maxy2 = -1;
57 zspan->minp1 = zspan->maxp1 = zspan->minp2 = zspan->maxp2 = nullptr;
58}
59
60static void zbuf_add_to_span(ZSpan *zspan, const float v1[2], const float v2[2])
61{
62 const float *minv, *maxv;
63 float *span;
64 float xx1, dx0, xs0;
65 int y, my0, my2;
66
67 if (v1[1] < v2[1]) {
68 minv = v1;
69 maxv = v2;
70 }
71 else {
72 minv = v2;
73 maxv = v1;
74 }
75
76 my0 = ceil(minv[1]);
77 my2 = floor(maxv[1]);
78
79 if (my2 < 0 || my0 >= zspan->recty) {
80 return;
81 }
82
83 /* clip top */
84 if (my2 >= zspan->recty) {
85 my2 = zspan->recty - 1;
86 }
87 /* clip bottom */
88 my0 = std::max(my0, 0);
89
90 if (my0 > my2) {
91 return;
92 }
93 /* if (my0>my2) should still fill in, that way we get spans that skip nicely */
94
95 xx1 = maxv[1] - minv[1];
96 if (xx1 > FLT_EPSILON) {
97 dx0 = (minv[0] - maxv[0]) / xx1;
98 xs0 = dx0 * (minv[1] - my2) + minv[0];
99 }
100 else {
101 dx0 = 0.0f;
102 xs0 = min_ff(minv[0], maxv[0]);
103 }
104
105 /* empty span */
106 if (zspan->maxp1 == nullptr) {
107 span = zspan->span1;
108 }
109 else { /* does it complete left span? */
110 if (maxv == zspan->minp1 || minv == zspan->maxp1) {
111 span = zspan->span1;
112 }
113 else {
114 span = zspan->span2;
115 }
116 }
117
118 if (span == zspan->span1) {
119 // printf("left span my0 %d my2 %d\n", my0, my2);
120 if (zspan->minp1 == nullptr || zspan->minp1[1] > minv[1]) {
121 zspan->minp1 = minv;
122 }
123 if (zspan->maxp1 == nullptr || zspan->maxp1[1] < maxv[1]) {
124 zspan->maxp1 = maxv;
125 }
126 zspan->miny1 = std::min(my0, zspan->miny1);
127 zspan->maxy1 = std::max(my2, zspan->maxy1);
128 }
129 else {
130 // printf("right span my0 %d my2 %d\n", my0, my2);
131 if (zspan->minp2 == nullptr || zspan->minp2[1] > minv[1]) {
132 zspan->minp2 = minv;
133 }
134 if (zspan->maxp2 == nullptr || zspan->maxp2[1] < maxv[1]) {
135 zspan->maxp2 = maxv;
136 }
137 zspan->miny2 = std::min(my0, zspan->miny2);
138 zspan->maxy2 = std::max(my2, zspan->maxy2);
139 }
140
141 for (y = my2; y >= my0; y--, xs0 += dx0) {
142 /* xs0 is the X-coordinate! */
143 span[y] = xs0;
144 }
145}
146
147/*-----------------------------------------------------------*/
148/* Functions */
149/*-----------------------------------------------------------*/
150
151/* NOTE(@ideasman42): workaround for pixel aligned UVs which are common and can screw
152 * up our intersection tests where a pixel gets in between 2 faces or the middle of a
153 * quad, camera aligned quads also have this problem but they are less common. Add a
154 * small offset to the UVs, fixes bug #18685. */
155constexpr float ZSPAN_X_EPSILON = 0.001f;
156constexpr float ZSPAN_Y_EPSILON = 0.002f;
157constexpr float ZSPAN_X_OFFSET = 0.5f + ZSPAN_X_EPSILON;
158constexpr float ZSPAN_Y_OFFSET = 0.5f + ZSPAN_Y_EPSILON;
159
161 void *handle,
162 const float *v1_in,
163 const float *v2_in,
164 const float *v3_in,
165 void (*func)(void *, int, int, float, float))
166{
167 float x0, y0, x1, y1, x2, y2, z0, z1, z2;
168 float u, v, uxd, uyd, vxd, vyd, uy0, vy0, xx1;
169 const float *span1, *span2;
170 int i, j, x, y, sn1, sn2, rectx = zspan->rectx, my0, my2;
171
172 /* init */
173 zbuf_init_span(zspan);
174
175 const float v1[2] = {v1_in[0] - ZSPAN_X_OFFSET, v1_in[1] - ZSPAN_Y_OFFSET};
176 const float v2[2] = {v2_in[0] - ZSPAN_X_OFFSET, v2_in[1] - ZSPAN_Y_OFFSET};
177 const float v3[2] = {v3_in[0] - ZSPAN_X_OFFSET, v3_in[1] - ZSPAN_Y_OFFSET};
178
179 /* set spans */
180 zbuf_add_to_span(zspan, v1, v2);
181 zbuf_add_to_span(zspan, v2, v3);
182 zbuf_add_to_span(zspan, v3, v1);
183
184 /* clipped */
185 if (zspan->minp2 == nullptr || zspan->maxp2 == nullptr) {
186 return;
187 }
188
189 my0 = max_ii(zspan->miny1, zspan->miny2);
190 my2 = min_ii(zspan->maxy1, zspan->maxy2);
191
192 // printf("my %d %d\n", my0, my2);
193 if (my2 < my0) {
194 return;
195 }
196
197 /* ZBUF DX DY, in floats still */
198 x1 = v1[0] - v2[0];
199 x2 = v2[0] - v3[0];
200 y1 = v1[1] - v2[1];
201 y2 = v2[1] - v3[1];
202
203 z1 = 1.0f; /* (u1 - u2) */
204 z2 = 0.0f; /* (u2 - u3) */
205
206 x0 = y1 * z2 - z1 * y2;
207 y0 = z1 * x2 - x1 * z2;
208 z0 = x1 * y2 - y1 * x2;
209
210 if (z0 == 0.0f) {
211 return;
212 }
213
214 xx1 = (x0 * v1[0] + y0 * v1[1]) / z0 + 1.0f;
215 uxd = -double(x0) / double(z0);
216 uyd = -double(y0) / double(z0);
217 uy0 = double(my2) * uyd + double(xx1);
218
219 z1 = -1.0f; /* (v1 - v2) */
220 z2 = 1.0f; /* (v2 - v3) */
221
222 x0 = y1 * z2 - z1 * y2;
223 y0 = z1 * x2 - x1 * z2;
224
225 xx1 = (x0 * v1[0] + y0 * v1[1]) / z0;
226 vxd = -double(x0) / double(z0);
227 vyd = -double(y0) / double(z0);
228 vy0 = double(my2) * vyd + double(xx1);
229
230 /* correct span */
231 span1 = zspan->span1 + my2;
232 span2 = zspan->span2 + my2;
233
234 for (i = 0, y = my2; y >= my0; i++, y--, span1--, span2--) {
235
236 sn1 = floor(min_ff(*span1, *span2));
237 sn2 = floor(max_ff(*span1, *span2));
238 sn1++;
239
240 if (sn2 >= rectx) {
241 sn2 = rectx - 1;
242 }
243 sn1 = std::max(sn1, 0);
244
245 u = ((double(sn1) * uxd) + uy0) - (i * uyd);
246 v = ((double(sn1) * vxd) + vy0) - (i * vyd);
247
248 for (j = 0, x = sn1; x <= sn2; j++, x++) {
249 func(handle, x, y, u + (j * uxd), v + (j * vxd));
250 }
251 }
252}
253
255 void *handle,
256 const float *v1_in,
257 const float *v2_in,
258 const float *uv1,
259 const float *uv2,
260 void (*func)(void *, int, int, float, float))
261{
262 const float v1[2] = {v1_in[0] - ZSPAN_X_OFFSET, v1_in[1] - ZSPAN_Y_OFFSET};
263 const float v2[2] = {v2_in[0] - ZSPAN_X_OFFSET, v2_in[1] - ZSPAN_Y_OFFSET};
264
265 const float miny = std::min(v1[1], v2[1]);
266 const float maxy = std::max(v1[1], v2[1]);
267
268 int y0 = floor(miny + 0.5f);
269 int y1 = floor(maxy + 0.5f);
270
271 /* Clip and cull the line. */
272 y0 = std::max(y0, 0);
273 if (y1 >= zspan->recty) {
274 y1 = zspan->recty - 1;
275 }
276
277 if (y0 > y1) {
278 return;
279 }
280
281 /* Line direction divided by length for uv interpolation. */
282 float dir[2] = {v2[0] - v1[0], v2[1] - v1[1]};
283 float len_sqr = dir[0] * dir[0] + dir[1] * dir[1];
284
285 if (len_sqr > FLT_EPSILON) {
286 dir[0] /= len_sqr;
287 dir[1] /= len_sqr;
288 }
289
290 /* X coordinates of the line endpoints. */
291 const float x_miny = (v1[1] < v2[1]) ? v1[0] : v2[0];
292 const float x_maxy = (v1[1] < v2[1]) ? v2[0] : v1[0];
293 const float inv_dy = math::safe_divide(1.0f, maxy - miny);
294
295 for (; y0 <= y1; y0++) {
296 /* Compute line x range inside current scan-line, interpolating between endpoints. */
297 const float ta = (clamp_f(y0 - 0.5f, miny, maxy) - miny) * inv_dy;
298 const float tb = (maxy - clamp_f(y0 + 0.5f, miny, maxy)) * inv_dy;
299 const float xa = math::interpolate(x_miny, x_maxy, ta);
300 const float xb = math::interpolate(x_miny, x_maxy, 1.0f - tb);
301
302 const float minx = std::min(xa, xb);
303 const float maxx = std::max(xa, xb);
304
305 int x0 = floor(minx + 0.5f);
306 int x1 = floor(maxx + 0.5f);
307
308 /* Clip and cull scan-line. */
309 x0 = std::max(x0, 0);
310 if (x1 >= zspan->rectx) {
311 x1 = zspan->rectx - 1;
312 }
313
314 if (x0 > x1) {
315 continue;
316 }
317
318 for (; x0 <= x1; x0++) {
319 float w = (x0 - v1[0]) * dir[0] + (y0 - v1[1]) * dir[1];
320 w = clamp_f(w, 0, 1);
321
322 float u = (1 - w) * uv1[0] + w * uv2[0];
323 float v = (1 - w) * uv1[1] + w * uv2[1];
324
325 func(handle, x0, y0, u, v);
326 }
327 }
328}
329
331 void *handle,
332 const float *v1,
333 const float *v2,
334 const float *v3,
335 void (*func)(void *, int, int, float, float))
336{
337 float uv1[2] = {1, 0};
338 float uv2[2] = {0, 1};
339 float uv3[2] = {0, 0};
340
341 zspan_rasterize_conservative_line(zspan, handle, v1, v2, uv1, uv2, func);
342 zspan_rasterize_conservative_line(zspan, handle, v2, v3, uv2, uv3, func);
343 zspan_rasterize_conservative_line(zspan, handle, v3, v1, uv3, uv1, func);
344}
345
346} // namespace blender
Read Blender memory allocation and freeing.
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
#define FLT_EPSILON
#define floor
#define ceil
T safe_divide(const T &a, const T &b)
T interpolate(const T &a, const T &b, const FactorT &t)
BMesh Iterators.
MINLINE float min_ff(float a, float b)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void zspan_rasterize_conservative_wireframe(ZSpan *zspan, void *handle, const float *v1, const float *v2, const float *v3, void(*func)(void *, int, int, float, float))
Definition zbuf.cc:330
constexpr float ZSPAN_Y_OFFSET
Definition zbuf.cc:158
void zbuf_alloc_span(ZSpan *zspan, int rectx, int recty)
Definition zbuf.cc:33
static void zbuf_add_to_span(ZSpan *zspan, const float v1[2], const float v2[2])
Definition zbuf.cc:60
MINLINE int max_ii(int a, int b)
ATTR_WARN_UNUSED_RESULT const BMVert * v
void zbuf_free_span(ZSpan *zspan)
Definition zbuf.cc:44
static void zspan_rasterize_conservative_line(ZSpan *zspan, void *handle, const float *v1_in, const float *v2_in, const float *uv1, const float *uv2, void(*func)(void *, int, int, float, float))
Definition zbuf.cc:254
static void zbuf_init_span(ZSpan *zspan)
Definition zbuf.cc:53
constexpr float ZSPAN_Y_EPSILON
Definition zbuf.cc:156
constexpr float ZSPAN_X_OFFSET
Definition zbuf.cc:157
constexpr float ZSPAN_X_EPSILON
Definition zbuf.cc:155
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE float max_ff(float a, float b)
void zspan_rasterize_triangle(ZSpan *zspan, void *handle, const float *v1_in, const float *v2_in, const float *v3_in, void(*func)(void *, int, int, float, float))
Definition zbuf.cc:160
MINLINE int min_ii(int a, int b)
MINLINE float clamp_f(float value, float min, float max)
const float * minp1
Definition zbuf.h:18
int recty
Definition zbuf.h:15
int maxy1
Definition zbuf.h:17
int maxy2
Definition zbuf.h:17
float * span2
Definition zbuf.h:19
const float * maxp2
Definition zbuf.h:18
const float * minp2
Definition zbuf.h:18
int miny2
Definition zbuf.h:17
int miny1
Definition zbuf.h:17
int rectx
Definition zbuf.h:15
const float * maxp1
Definition zbuf.h:18
float * span1
Definition zbuf.h:19