1/**************************************************************************/
2/* renderer_scene_occlusion_cull.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef RENDERER_SCENE_OCCLUSION_CULL_H
32#define RENDERER_SCENE_OCCLUSION_CULL_H
33
34#include "core/math/projection.h"
35#include "core/templates/local_vector.h"
36#include "servers/rendering_server.h"
37
38class RendererSceneOcclusionCull {
39protected:
40 static RendererSceneOcclusionCull *singleton;
41
42public:
43 class HZBuffer {
44 protected:
45 static const Vector3 corners[8];
46
47 LocalVector<float> data;
48 LocalVector<Size2i> sizes;
49 LocalVector<float *> mips;
50
51 RID debug_texture;
52 Ref<Image> debug_image;
53 PackedByteArray debug_data;
54 float debug_tex_range = 0.0f;
55
56 public:
57 bool is_empty() const;
58 virtual void clear();
59 virtual void resize(const Size2i &p_size);
60
61 void update_mips();
62
63 _FORCE_INLINE_ bool is_occluded(const real_t p_bounds[6], const Vector3 &p_cam_position, const Transform3D &p_cam_inv_transform, const Projection &p_cam_projection, real_t p_near) const {
64 if (is_empty()) {
65 return false;
66 }
67
68 Vector3 closest_point = Vector3(CLAMP(p_cam_position.x, p_bounds[0], p_bounds[3]), CLAMP(p_cam_position.y, p_bounds[1], p_bounds[4]), CLAMP(p_cam_position.z, p_bounds[2], p_bounds[5]));
69
70 if (closest_point == p_cam_position) {
71 return false;
72 }
73
74 Vector3 closest_point_view = p_cam_inv_transform.xform(closest_point);
75 if (closest_point_view.z > -p_near) {
76 return false;
77 }
78
79 float min_depth = -closest_point_view.z * 0.95f;
80
81 Vector2 rect_min = Vector2(FLT_MAX, FLT_MAX);
82 Vector2 rect_max = Vector2(FLT_MIN, FLT_MIN);
83
84 for (int j = 0; j < 8; j++) {
85 const Vector3 &c = RendererSceneOcclusionCull::HZBuffer::corners[j];
86 Vector3 nc = Vector3(1, 1, 1) - c;
87 Vector3 corner = Vector3(p_bounds[0] * c.x + p_bounds[3] * nc.x, p_bounds[1] * c.y + p_bounds[4] * nc.y, p_bounds[2] * c.z + p_bounds[5] * nc.z);
88 Vector3 view = p_cam_inv_transform.xform(corner);
89
90 Plane vp = Plane(view, 1.0);
91 Plane projected = p_cam_projection.xform4(vp);
92
93 float w = projected.d;
94 if (w < 1.0) {
95 rect_min = Vector2(0.0f, 0.0f);
96 rect_max = Vector2(1.0f, 1.0f);
97 break;
98 }
99
100 Vector2 normalized = Vector2(projected.normal.x / w * 0.5f + 0.5f, projected.normal.y / w * 0.5f + 0.5f);
101 rect_min = rect_min.min(normalized);
102 rect_max = rect_max.max(normalized);
103 }
104
105 rect_max = rect_max.min(Vector2(1, 1));
106 rect_min = rect_min.max(Vector2(0, 0));
107
108 int mip_count = mips.size();
109
110 Vector2 screen_diagonal = (rect_max - rect_min) * sizes[0];
111 float size = MAX(screen_diagonal.x, screen_diagonal.y);
112 float l = Math::ceil(Math::log2(size));
113 int lod = CLAMP(l, 0, mip_count - 1);
114
115 const int max_samples = 512;
116 int sample_count = 0;
117 bool visible = true;
118
119 for (; lod >= 0; lod--) {
120 int w = sizes[lod].x;
121 int h = sizes[lod].y;
122
123 int minx = CLAMP(rect_min.x * w - 1, 0, w - 1);
124 int maxx = CLAMP(rect_max.x * w + 1, 0, w - 1);
125
126 int miny = CLAMP(rect_min.y * h - 1, 0, h - 1);
127 int maxy = CLAMP(rect_max.y * h + 1, 0, h - 1);
128
129 sample_count += (maxx - minx + 1) * (maxy - miny + 1);
130
131 if (sample_count > max_samples) {
132 return false;
133 }
134
135 visible = false;
136 for (int y = miny; y <= maxy; y++) {
137 for (int x = minx; x <= maxx; x++) {
138 float depth = mips[lod][y * w + x];
139 if (depth > min_depth) {
140 visible = true;
141 break;
142 }
143 }
144 if (visible) {
145 break;
146 }
147 }
148
149 if (!visible) {
150 return true;
151 }
152 }
153
154 return !visible;
155 }
156
157 RID get_debug_texture();
158
159 virtual ~HZBuffer(){};
160 };
161
162 static RendererSceneOcclusionCull *get_singleton() { return singleton; }
163
164 void _print_warning() {
165 WARN_PRINT_ONCE("Occlusion culling is disabled at build-time.");
166 }
167
168 virtual bool is_occluder(RID p_rid) { return false; }
169 virtual RID occluder_allocate() { return RID(); }
170 virtual void occluder_initialize(RID p_occluder) {}
171 virtual void free_occluder(RID p_occluder) { _print_warning(); }
172 virtual void occluder_set_mesh(RID p_occluder, const PackedVector3Array &p_vertices, const PackedInt32Array &p_indices) { _print_warning(); }
173
174 virtual void add_scenario(RID p_scenario) {}
175 virtual void remove_scenario(RID p_scenario) {}
176 virtual void scenario_set_instance(RID p_scenario, RID p_instance, RID p_occluder, const Transform3D &p_xform, bool p_enabled) { _print_warning(); }
177 virtual void scenario_remove_instance(RID p_scenario, RID p_instance) { _print_warning(); }
178
179 virtual void add_buffer(RID p_buffer) { _print_warning(); }
180 virtual void remove_buffer(RID p_buffer) { _print_warning(); }
181 virtual HZBuffer *buffer_get_ptr(RID p_buffer) {
182 return nullptr;
183 }
184 virtual void buffer_set_scenario(RID p_buffer, RID p_scenario) { _print_warning(); }
185 virtual void buffer_set_size(RID p_buffer, const Vector2i &p_size) { _print_warning(); }
186 virtual void buffer_update(RID p_buffer, const Transform3D &p_cam_transform, const Projection &p_cam_projection, bool p_cam_orthogonal) {}
187
188 virtual RID buffer_get_debug_texture(RID p_buffer) {
189 _print_warning();
190 return RID();
191 }
192
193 virtual void set_build_quality(RS::ViewportOcclusionCullingBuildQuality p_quality) {}
194
195 RendererSceneOcclusionCull() {
196 singleton = this;
197 };
198
199 virtual ~RendererSceneOcclusionCull() {
200 singleton = nullptr;
201 };
202};
203
204#endif // RENDERER_SCENE_OCCLUSION_CULL_H
205