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
|
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
//! A simple occlusion culling algorithm for axis-aligned rectangles.
//!
//! ## Output
//!
//! Occlusion culling results in two lists of rectangles:
//!
//! - The opaque list should be rendered first. None of its rectangles overlap so order doesn't matter
//! within the opaque pass.
//! - The non-opaque list (or alpha list) which should be rendered in back-to-front order after the opaque pass.
//!
//! The output has minimal overdraw (no overdraw at all for opaque items and as little as possible for alpha ones).
//!
//! ## Algorithm overview
//!
//! The occlusion culling algorithm works in front-to-back order, accumulating rectangle in opaque and non-opaque lists.
//! Each time a rectangle is added, it is first tested against existing opaque rectangles and potentially split into visible
//! sub-rectangles, or even discarded completely. The front-to-back order ensures that once a rectangle is added it does not
//! have to be modified again, making the underlying data structure trivial (append-only).
//!
//! ## splitting
//!
//! Partially visible rectangles are split into up to 4 visible sub-rectangles by each intersecting occluder.
//!
//! ```ascii
//! +----------------------+ +----------------------+
//! | rectangle | | |
//! | | | |
//! | +-----------+ | +--+-----------+-------+
//! | |occluder | | --> | |\\\\\\\\\\\| |
//! | +-----------+ | +--+-----------+-------+
//! | | | |
//! +----------------------+ +----------------------+
//! ```
//!
//! In the example above the rectangle is split into 4 visible parts with the central occluded part left out.
//!
//! This implementation favors longer horizontal bands instead creating nine-patches to deal with the corners.
//! The advantage is that it produces less rectangles which is good for the performance of the algorithm and
//! for SWGL which likes long horizontal spans, however it would cause artifacts if the resulting rectangles
//! were to be drawn with a non-axis-aligned transformation.
//!
//! ## Performance
//!
//! The cost of the algorithm grows with the number of opaque rectangle as each new rectangle is tested against
//! all previously added opaque rectangles.
//!
//! Note that opaque rectangles can either be added as opaque or non-opaque. This means a trade-off between
//! overdraw and number of rectangles can be explored to adjust performance: Small opaque rectangles, especially
//! towards the front of the scene, could be added as non-opaque to avoid causing many splits while adding only
//! a small amount of overdraw.
//!
//! This implementation is intended to be used with a small number of (opaque) items. A similar implementation
//! could use a spatial acceleration structure for opaque rectangles to perform better with a large amount of
//! occluders.
//!
use euclid::point2;
use smallvec::SmallVec;
use api::units::*;
/// A visible part of a rectangle after occlusion culling.
#[derive(Debug, PartialEq)]
pub struct Item {
pub rectangle: DeviceBox2D,
pub key: usize,
}
/// A builder that applies occlusion culling with rectangles provided in front-to-back order.
pub struct FrontToBackBuilder {
opaque_items: Vec<Item>,
alpha_items: Vec<Item>,
}
impl FrontToBackBuilder {
/// Pre-allocating constructor.
pub fn with_capacity(opaque: usize, alpha: usize) -> Self {
FrontToBackBuilder {
opaque_items: Vec::with_capacity(opaque),
alpha_items: Vec::with_capacity(alpha),
}
}
/// Add a rectangle, potentially splitting it and discarding the occluded parts if any.
///
/// Returns true the rectangle is at least partially visible.
pub fn add(&mut self, rect: &DeviceBox2D, is_opaque: bool, key: usize) -> bool {
let mut fragments: SmallVec<[DeviceBox2D; 16]> = SmallVec::new();
fragments.push(*rect);
for item in &self.opaque_items {
if fragments.is_empty() {
break;
}
if item.rectangle.intersects(rect) {
apply_occluder(&item.rectangle, &mut fragments);
}
}
let list = if is_opaque {
&mut self.opaque_items
} else {
&mut self.alpha_items
};
for rect in &fragments {
list.push(Item {
rectangle: *rect,
key,
});
}
!fragments.is_empty()
}
/// Returns true if the provided rect is at least partially visible, without adding it.
pub fn test(&self, rect: &DeviceBox2D) -> bool {
let mut fragments: SmallVec<[DeviceBox2D; 16]> = SmallVec::new();
fragments.push(*rect);
for item in &self.opaque_items {
if item.rectangle.intersects(rect) {
apply_occluder(&item.rectangle, &mut fragments);
}
}
!fragments.is_empty()
}
/// The visible opaque rectangles (front-to-back order).
pub fn opaque_items(&self) -> &[Item] {
&self.opaque_items
}
/// The visible non-opaque rectangles (front-to-back order).
pub fn alpha_items(&self) -> &[Item] {
&self.alpha_items
}
}
// Split out the parts of the rects in the provided vector
fn apply_occluder(occluder: &DeviceBox2D, rects: &mut SmallVec<[DeviceBox2D; 16]>) {
// Iterate in reverse order so that we can push new rects at the back without
// visiting them;
let mut i = rects.len() - 1;
loop {
let r = rects[i];
if r.intersects(occluder) {
let top = r.min.y < occluder.min.y;
let bottom = r.max.y > occluder.max.y;
let left = r.min.x < occluder.min.x;
let right = r.max.x > occluder.max.x;
if top {
rects.push(DeviceBox2D {
min: r.min,
max: point2(r.max.x, occluder.min.y),
});
}
if bottom {
rects.push(DeviceBox2D {
min: point2(r.min.x, occluder.max.y),
max: r.max,
});
}
if left {
let min_y = r.min.y.max(occluder.min.y);
let max_y = r.max.y.min(occluder.max.y);
rects.push(DeviceBox2D {
min: point2(r.min.x, min_y),
max: point2(occluder.min.x, max_y),
});
}
if right {
let min_y = r.min.y.max(occluder.min.y);
let max_y = r.max.y.min(occluder.max.y);
rects.push(DeviceBox2D {
min: point2(occluder.max.x, min_y),
max: point2(r.max.x, max_y),
});
}
// Remove the original rectangle, replacing it with
// one of the new ones we just added, or popping it
// if it is the last item.
if i == rects.len() {
rects.pop();
} else {
rects.swap_remove(i);
}
}
if i == 0 {
break;
}
i -= 1;
}
}
|
