Blender V5.3
draw_intersect.bsl.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2022-2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#pragma once
10
15
16#include "draw_shader_shared.hh"
17#include "draw_shape.bsl.hh"
21
22/* ---------------------------------------------------------------------- */
25
28{
29 float3 normal_to_plane = normalize(cross(v1, v2));
30 return float4(normal_to_plane, -dot(normal_to_plane, p));
31}
32
37
39{
40 float3 A1 = shape.corners[1] - shape.corners[0];
41 float3 A2 = shape.corners[2] - shape.corners[0];
42 float3 A3 = shape.corners[3] - shape.corners[0];
43 float3 A4 = shape.corners[4] - shape.corners[0];
44 float3 S4 = shape.corners[4] - shape.corners[1];
45 float3 S2 = shape.corners[2] - shape.corners[1];
46
47 IsectPyramid data;
48 data.planes[0] = isect_plane_setup(shape.corners[0], A2, A1);
49 data.planes[1] = isect_plane_setup(shape.corners[0], A3, A2);
50 data.planes[2] = isect_plane_setup(shape.corners[0], A4, A3);
51 data.planes[3] = isect_plane_setup(shape.corners[0], A1, A4);
52 data.planes[4] = isect_plane_setup(shape.corners[1], S2, S4);
53 for (int i = 0; i < 5; i++) {
54 data.corners[i] = shape.corners[i];
55 }
56 return data;
57}
58
63
65{
66 float3 A1 = shape.corners[1] - shape.corners[0];
67 float3 A3 = shape.corners[3] - shape.corners[0];
68 float3 A4 = shape.corners[4] - shape.corners[0];
69
70 IsectBox data;
71 data.planes[0] = isect_plane_setup(shape.corners[0], A3, A1);
72 data.planes[1] = isect_plane_setup(shape.corners[0], A4, A3);
73 data.planes[2] = isect_plane_setup(shape.corners[0], A1, A4);
74 /* Assumes that the box is actually a box! */
75 data.planes[3] = float4(-data.planes[0].xyz, -dot(-data.planes[0].xyz, shape.corners[6]));
76 data.planes[4] = float4(-data.planes[1].xyz, -dot(-data.planes[1].xyz, shape.corners[6]));
77 data.planes[5] = float4(-data.planes[2].xyz, -dot(-data.planes[2].xyz, shape.corners[6]));
78 for (int i = 0; i < 8; i++) {
79 data.corners[i] = shape.corners[i];
80 }
81 return data;
82}
83
84/* Construct box from 1 corner point + 3 side vectors. */
85IsectBox isect_box_setup(float3 origin, float3 side_x, float3 side_y, float3 side_z)
86{
87 IsectBox data;
88 data.corners[0] = origin;
89 data.corners[1] = origin + side_x;
90 data.corners[2] = origin + side_y + side_x;
91 data.corners[3] = origin + side_y;
92 data.corners[4] = data.corners[0] + side_z;
93 data.corners[5] = data.corners[1] + side_z;
94 data.corners[6] = data.corners[2] + side_z;
95 data.corners[7] = data.corners[3] + side_z;
96
97 data.planes[0] = isect_plane_setup(data.corners[0], side_y, side_z);
98 data.planes[1] = isect_plane_setup(data.corners[0], side_x, side_y);
99 data.planes[2] = isect_plane_setup(data.corners[0], side_z, side_x);
100 /* Assumes that the box is actually a box! */
101 data.planes[3] = float4(-data.planes[0].xyz, -dot(-data.planes[0].xyz, data.corners[6]));
102 data.planes[4] = float4(-data.planes[1].xyz, -dot(-data.planes[1].xyz, data.corners[6]));
103 data.planes[5] = float4(-data.planes[2].xyz, -dot(-data.planes[2].xyz, data.corners[6]));
104
105 return data;
106}
107
112
114{
115 float3 A1 = shape.corners[1] - shape.corners[0];
116 float3 A3 = shape.corners[3] - shape.corners[0];
117 float3 A4 = shape.corners[4] - shape.corners[0];
118 float3 B5 = shape.corners[5] - shape.corners[6];
119 float3 B7 = shape.corners[7] - shape.corners[6];
120 float3 B2 = shape.corners[2] - shape.corners[6];
121
122 IsectFrustum data;
123 data.planes[0] = isect_plane_setup(shape.corners[0], A3, A1);
124 data.planes[1] = isect_plane_setup(shape.corners[0], A4, A3);
125 data.planes[2] = isect_plane_setup(shape.corners[0], A1, A4);
126 data.planes[3] = isect_plane_setup(shape.corners[6], B7, B5);
127 data.planes[4] = isect_plane_setup(shape.corners[6], B5, B2);
128 data.planes[5] = isect_plane_setup(shape.corners[6], B2, B7);
129 for (int i = 0; i < 8; i++) {
130 data.corners[i] = shape.corners[i];
131 }
132 return data;
133}
134
136
137/* ---------------------------------------------------------------------- */
140
141namespace draw {
142
145
146 ViewCullingData get(uint view_id) const
147 {
148 return drw_view_culling_buf[view_id];
149 }
150
151 bool intersect_view(Pyramid pyramid, uint view_id) const
152 {
153 bool intersects = true;
154
155 /* WORKAROUND: There is a GLSL compiler bug on legacy AMD GPU drivers that returns an incorrect
156 * computation if `drw_view_culling_buf[]` is called in both of the loops below (see #143336).
157 */
158 ViewCullingData culling = drw_view_culling_buf[view_id];
159
160 /* Do Pyramid vertices vs Frustum planes. */
161 for (int p = 0; p < 6; ++p) {
162 bool is_any_vertex_on_positive_side = false;
163 for (int v = 0; v < 5; ++v) {
164 float test = dot(culling.frustum_planes.planes[p], float4(pyramid.corners[v], 1.0f));
165 if (test > 0.0f) {
166 is_any_vertex_on_positive_side = true;
167 break;
168 }
169 }
170 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
171 if (all_vertex_on_negative_side) {
172 intersects = false;
173 break;
174 }
175 }
176
177 if (!intersects) {
178 return intersects;
179 }
180
181 /* Now do Frustum vertices vs Pyramid planes. */
182 IsectPyramid i_pyramid = isect_pyramid_setup(pyramid);
183 for (int p = 0; p < 5; ++p) {
184 bool is_any_vertex_on_positive_side = false;
185 for (int v = 0; v < 8; ++v) {
186 float test = dot(i_pyramid.planes[p],
187 float4(culling.frustum_corners.corners[v].xyz, 1.0f));
188 if (test > 0.0f) {
189 is_any_vertex_on_positive_side = true;
190 break;
191 }
192 }
193 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
194 if (all_vertex_on_negative_side) {
195 intersects = false;
196 break;
197 }
198 }
199 return intersects;
200 }
201
202 bool intersect_view(Box box, uint view_id) const
203 {
204 bool intersects = true;
205
206 /* WORKAROUND: There is a GLSL compiler bug on legacy AMD GPU drivers that returns an incorrect
207 * computation if `drw_view_culling_buf[]` is called in both of the loops below (see #143336).
208 */
209 ViewCullingData culling = drw_view_culling_buf[view_id];
210
211 /* Do Box vertices vs Frustum planes. */
212 for (int p = 0; p < 6; ++p) {
213 bool is_any_vertex_on_positive_side = false;
214 for (int v = 0; v < 8; ++v) {
215 float test = dot(culling.frustum_planes.planes[p], float4(box.corners[v], 1.0f));
216 if (test > 0.0f) {
217 is_any_vertex_on_positive_side = true;
218 break;
219 }
220 }
221 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
222 if (all_vertex_on_negative_side) {
223 intersects = false;
224 break;
225 }
226 }
227
228 if (!intersects) {
229 return intersects;
230 }
231
232 /* Now do Frustum vertices vs Box planes. */
233 IsectBox i_box = isect_box_setup(box);
234 for (int p = 0; p < 6; ++p) {
235 bool is_any_vertex_on_positive_side = false;
236 for (int v = 0; v < 8; ++v) {
237 float test = dot(i_box.planes[p], float4(culling.frustum_corners.corners[v].xyz, 1.0f));
238 if (test > 0.0f) {
239 is_any_vertex_on_positive_side = true;
240 break;
241 }
242 }
243 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
244 if (all_vertex_on_negative_side) {
245 intersects = false;
246 break;
247 }
248 }
249
250 return intersects;
251 }
252
253 bool intersect_view(IsectBox i_box, uint view_id) const
254 {
255 bool intersects = true;
256
257 /* WORKAROUND: There is a GLSL compiler bug on legacy AMD GPU drivers that returns an incorrect
258 * computation if `drw_view_culling_buf[]` is called in both of the loops below (see #143336).
259 */
260 ViewCullingData culling = drw_view_culling_buf[view_id];
261
262 /* Do Box vertices vs Frustum planes. */
263 for (int p = 0; p < 6; ++p) {
264 bool is_any_vertex_on_positive_side = false;
265 for (int v = 0; v < 8; ++v) {
266 float test = dot(culling.frustum_planes.planes[p], float4(i_box.corners[v], 1.0f));
267 if (test > 0.0f) {
268 is_any_vertex_on_positive_side = true;
269 break;
270 }
271 }
272 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
273 if (all_vertex_on_negative_side) {
274 intersects = false;
275 break;
276 }
277 }
278
279 if (!intersects) {
280 return intersects;
281 }
282
283 for (int p = 0; p < 6; ++p) {
284 bool is_any_vertex_on_positive_side = false;
285 for (int v = 0; v < 8; ++v) {
286 float test = dot(i_box.planes[p], float4(culling.frustum_corners.corners[v].xyz, 1.0f));
287 if (test > 0.0f) {
288 is_any_vertex_on_positive_side = true;
289 break;
290 }
291 }
292 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
293 if (all_vertex_on_negative_side) {
294 intersects = false;
295 break;
296 }
297 }
298
299 return intersects;
300 }
301
302 bool intersect_view(Sphere sphere, uint view_id) const
303 {
304 bool intersects = true;
305
306 /* WORKAROUND: There is a GLSL compiler bug on legacy AMD GPU drivers that returns an incorrect
307 * computation if `drw_view_culling_buf[]` is called in both of the loops below (see #143336).
308 */
309 ViewCullingData culling = drw_view_culling_buf[view_id];
310
311 for (int p = 0; p < 6 && intersects; ++p) {
312 float dist_to_plane = dot(culling.frustum_planes.planes[p], float4(sphere.center, 1.0f));
313 if (dist_to_plane < -sphere.radius) {
314 intersects = false;
315 }
316 }
317 /* TODO reject false positive. */
318 return intersects;
319 }
320};
321
322} // namespace draw
323
325
326/* ---------------------------------------------------------------------- */
329
330bool intersect(IsectPyramid i_pyramid, Box box)
331{
332 bool intersects = true;
333
334 /* Do Box vertices vs Pyramid planes. */
335 for (int p = 0; p < 5; ++p) {
336 bool is_any_vertex_on_positive_side = false;
337 for (int v = 0; v < 8; ++v) {
338 float test = dot(i_pyramid.planes[p], float4(box.corners[v], 1.0f));
339 if (test > 0.0f) {
340 is_any_vertex_on_positive_side = true;
341 break;
342 }
343 }
344 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
345 if (all_vertex_on_negative_side) {
346 intersects = false;
347 break;
348 }
349 }
350
351 if (!intersects) {
352 return intersects;
353 }
354
355 /* Now do Pyramid vertices vs Box planes. */
356 IsectBox i_box = isect_box_setup(box);
357 for (int p = 0; p < 6; ++p) {
358 bool is_any_vertex_on_positive_side = false;
359 for (int v = 0; v < 5; ++v) {
360 float test = dot(i_box.planes[p], float4(i_pyramid.corners[v], 1.0f));
361 if (test > 0.0f) {
362 is_any_vertex_on_positive_side = true;
363 break;
364 }
365 }
366 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
367 if (all_vertex_on_negative_side) {
368 intersects = false;
369 break;
370 }
371 }
372 return intersects;
373}
374
375bool intersect(IsectPyramid i_pyramid, IsectBox i_box)
376{
377 bool intersects = true;
378
379 /* Do Box vertices vs Pyramid planes. */
380 for (int p = 0; p < 5; ++p) {
381 bool is_any_vertex_on_positive_side = false;
382 for (int v = 0; v < 8; ++v) {
383 float test = dot(i_pyramid.planes[p], float4(i_box.corners[v], 1.0f));
384 if (test > 0.0f) {
385 is_any_vertex_on_positive_side = true;
386 break;
387 }
388 }
389 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
390 if (all_vertex_on_negative_side) {
391 intersects = false;
392 break;
393 }
394 }
395
396 if (!intersects) {
397 return intersects;
398 }
399
400 /* Now do Pyramid vertices vs Box planes. */
401 for (int p = 0; p < 6; ++p) {
402 bool is_any_vertex_on_positive_side = false;
403 for (int v = 0; v < 5; ++v) {
404 float test = dot(i_box.planes[p], float4(i_pyramid.corners[v], 1.0f));
405 if (test > 0.0f) {
406 is_any_vertex_on_positive_side = true;
407 break;
408 }
409 }
410 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
411 if (all_vertex_on_negative_side) {
412 intersects = false;
413 break;
414 }
415 }
416 return intersects;
417}
418
419bool intersect(IsectFrustum i_frustum, Pyramid pyramid)
420{
421 bool intersects = true;
422
423 /* Do Pyramid vertices vs Frustum planes. */
424 for (int p = 0; p < 6; ++p) {
425 bool is_any_vertex_on_positive_side = false;
426 for (int v = 0; v < 5; ++v) {
427 float test = dot(i_frustum.planes[p], float4(pyramid.corners[v], 1.0f));
428 if (test > 0.0f) {
429 is_any_vertex_on_positive_side = true;
430 break;
431 }
432 }
433 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
434 if (all_vertex_on_negative_side) {
435 intersects = false;
436 break;
437 }
438 }
439
440 if (!intersects) {
441 return intersects;
442 }
443
444 /* Now do Frustum vertices vs Pyramid planes. */
445 IsectPyramid i_pyramid = isect_pyramid_setup(pyramid);
446 for (int p = 0; p < 5; ++p) {
447 bool is_any_vertex_on_positive_side = false;
448 for (int v = 0; v < 8; ++v) {
449 float test = dot(i_pyramid.planes[p], float4(i_frustum.corners[v].xyz, 1.0f));
450 if (test > 0.0f) {
451 is_any_vertex_on_positive_side = true;
452 break;
453 }
454 }
455 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
456 if (all_vertex_on_negative_side) {
457 intersects = false;
458 break;
459 }
460 }
461 return intersects;
462}
463
464bool intersect(IsectFrustum i_frustum, Box box)
465{
466 bool intersects = true;
467
468 /* Do Box vertices vs Frustum planes. */
469 for (int p = 0; p < 6; ++p) {
470 bool is_any_vertex_on_positive_side = false;
471 for (int v = 0; v < 8; ++v) {
472 float test = dot(i_frustum.planes[p], float4(box.corners[v], 1.0f));
473 if (test > 0.0f) {
474 is_any_vertex_on_positive_side = true;
475 break;
476 }
477 }
478 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
479 if (all_vertex_on_negative_side) {
480 intersects = false;
481 break;
482 }
483 }
484
485 if (!intersects) {
486 return intersects;
487 }
488
489 /* Now do Frustum vertices vs Box planes. */
490 IsectBox i_box = isect_box_setup(box);
491 for (int p = 0; p < 6; ++p) {
492 bool is_any_vertex_on_positive_side = false;
493 for (int v = 0; v < 8; ++v) {
494 float test = dot(i_box.planes[p], float4(i_frustum.corners[v].xyz, 1.0f));
495 if (test > 0.0f) {
496 is_any_vertex_on_positive_side = true;
497 break;
498 }
499 }
500 bool all_vertex_on_negative_side = !is_any_vertex_on_positive_side;
501 if (all_vertex_on_negative_side) {
502 intersects = false;
503 break;
504 }
505 }
506
507 return intersects;
508}
509
510bool intersect(IsectFrustum i_frustum, Sphere sphere)
511{
512 bool intersects = true;
513 for (int p = 0; p < 6; ++p) {
514 float dist_to_plane = dot(i_frustum.planes[p], float4(sphere.center, 1.0f));
515 if (dist_to_plane < -sphere.radius) {
516 intersects = false;
517 break;
518 }
519 }
520 return intersects;
521}
522
523bool intersect(Cone cone, Sphere sphere)
524{
530 float sphere_distance = length(sphere.center);
531 float sphere_distance_rcp = safe_rcp(sphere_distance);
532 float sphere_sin = saturate(sphere.radius * sphere_distance_rcp);
533 float sphere_cos = sqrt(1.0f - sphere_sin * sphere_sin);
534 float cone_aperture_sin = sqrt(1.0f - cone.angle_cos * cone.angle_cos);
535
536 float cone_sphere_center_cos = dot(sphere.center * sphere_distance_rcp, cone.direction);
537 /* cos(A+B) = cos(A) * cos(B) - sin(A) * sin(B). */
538 float cone_sphere_angle_sum_cos = (sphere.radius > sphere_distance) ?
539 -1.0f :
540 (cone.angle_cos * sphere_cos -
541 cone_aperture_sin * sphere_sin);
542 /* Comparing cosines instead of angles since we are interested
543 * only in the monotonic region [0 .. M_PI / 2]. This saves costly `acos()` calls. */
544 bool intersects = (cone_sphere_center_cos >= cone_sphere_angle_sum_cos);
545
546 return intersects;
547}
548
549bool intersect(Circle circle_a, Circle circle_b)
550{
551 return distance_squared(circle_a.center, circle_b.center) <
552 square(circle_a.radius + circle_b.radius);
553}
554
#define A2
Definition RandGen.cpp:28
#define A1
Definition RandGen.cpp:27
#define DRW_VIEW_CULLING_UBO_SLOT
float4 isect_plane_setup(float3 p, float3 v1, float3 v2)
IsectBox isect_box_setup(Box shape)
IsectPyramid isect_pyramid_setup(Pyramid shape)
IsectFrustum isect_frustum_setup(Frustum shape)
bool intersect(IsectPyramid i_pyramid, Box box)
#define uniform(slot)
VecBase< float, D > normalize(VecOp< float, D >) RET
float dot(VecOp< float, D >, VecOp< float, D >) RET
#define sqrt
VecBase< float, 3 > cross(VecOp< float, 3 >, VecOp< float, 3 >) RET
float length(VecOp< float, D >) RET
float square(float v)
float safe_rcp(float a)
float distance_squared(VecT a, VecT b)
VecBase< float, 4 > float4
VecBase< float, 3 > float3
#define saturate(a)
Definition smaa.cc:319
float3 corners[8]
float radius
float2 center
float angle_cos
float3 direction
float3 corners[8]
float3 corners[8]
float4 planes[6]
float3 corners[5]
float3 center
float radius
struct FrustumPlanes frustum_planes
struct FrustumCorners frustum_corners
const ViewCullingData(& drw_view_culling_buf)[64]
bool intersect_view(Box box, uint view_id) const
ViewCullingData get(uint view_id) const
bool intersect_view(IsectBox i_box, uint view_id) const
bool intersect_view(Sphere sphere, uint view_id) const
bool intersect_view(Pyramid pyramid, uint view_id) const