1 | /*! |
2 | * \file colorstop_atlas.cpp |
3 | * \brief file colorstop_atlas.cpp |
4 | * |
5 | * Copyright 2016 by Intel. |
6 | * |
7 | * Contact: kevin.rogovin@gmail.com |
8 | * |
9 | * This Source Code Form is subject to the |
10 | * terms of the Mozilla Public License, v. 2.0. |
11 | * If a copy of the MPL was not distributed with |
12 | * this file, You can obtain one at |
13 | * http://mozilla.org/MPL/2.0/. |
14 | * |
15 | * \author Kevin Rogovin <kevin.rogovin@gmail.com> |
16 | * |
17 | */ |
18 | |
19 | |
20 | #include <vector> |
21 | #include <algorithm> |
22 | #include <mutex> |
23 | #include <fastuidraw/colorstop_atlas.hpp> |
24 | #include <fastuidraw/util/math.hpp> |
25 | #include <private/interval_allocator.hpp> |
26 | #include <private/util_private.hpp> |
27 | |
28 | namespace |
29 | { |
30 | class ColorInterpolator |
31 | { |
32 | public: |
33 | ColorInterpolator(const fastuidraw::ColorStop &begin, |
34 | const fastuidraw::ColorStop &end): |
35 | m_start(begin.m_place), |
36 | m_coeff(1.0f / (end.m_place - begin.m_place)), |
37 | m_startColor(begin.m_color), |
38 | m_deltaColor(fastuidraw::vec4(end.m_color) - fastuidraw::vec4(begin.m_color)) |
39 | {} |
40 | |
41 | fastuidraw::u8vec4 |
42 | interpolate(float t) |
43 | { |
44 | float s; |
45 | fastuidraw::vec4 value; |
46 | |
47 | s = (t - m_start) * m_coeff; |
48 | s = std::min(1.0f, std::max(0.0f, s)); |
49 | value = m_startColor + s * m_deltaColor; |
50 | |
51 | return fastuidraw::u8vec4(value); |
52 | }; |
53 | |
54 | private: |
55 | float m_start, m_coeff; |
56 | fastuidraw::vec4 m_startColor, m_deltaColor; |
57 | }; |
58 | |
59 | typedef std::pair<fastuidraw::ivec2, int> delayed_free_entry; |
60 | |
61 | class ColorStopAtlasPrivate |
62 | { |
63 | public: |
64 | explicit |
65 | ColorStopAtlasPrivate(fastuidraw::reference_counted_ptr<fastuidraw::ColorStopBackingStore> pbacking_store); |
66 | |
67 | void |
68 | remove_entry_from_available_layers(std::map<int, std::set<int> >::iterator, int y); |
69 | |
70 | void |
71 | add_bookkeeping(int new_size); |
72 | |
73 | void |
74 | deallocate_implement(fastuidraw::ivec2 location, int width); |
75 | |
76 | mutable std::mutex m_mutex; |
77 | int m_delayed_interval_freeing_counter; |
78 | std::vector<delayed_free_entry> m_delayed_freed_intervals; |
79 | |
80 | fastuidraw::reference_counted_ptr<fastuidraw::ColorStopBackingStore> m_backing_store; |
81 | int m_allocated; |
82 | |
83 | /* Each layer has an interval allocator to allocate |
84 | * and free "color stop arrays" |
85 | */ |
86 | std::vector<fastuidraw::interval_allocator*> m_layer_allocator; |
87 | |
88 | /* m_available_layers[key] gives indices into m_layer_allocator |
89 | * for those layers for which largest_free_interval() returns |
90 | * key. |
91 | */ |
92 | std::map<int, std::set<int> > m_available_layers; |
93 | }; |
94 | |
95 | class ColorStopBackingStorePrivate |
96 | { |
97 | public: |
98 | ColorStopBackingStorePrivate(int w, int num_layers): |
99 | m_dimensions(w, num_layers), |
100 | m_width_times_height(m_dimensions.x() * m_dimensions.y()) |
101 | {} |
102 | |
103 | fastuidraw::ivec2 m_dimensions; |
104 | int m_width_times_height; |
105 | }; |
106 | |
107 | class ColorStopSequencePrivate |
108 | { |
109 | public: |
110 | fastuidraw::reference_counted_ptr<fastuidraw::ColorStopAtlas> m_atlas; |
111 | fastuidraw::ivec2 m_texel_location; |
112 | int m_width; |
113 | int m_start_slack, m_end_slack; |
114 | }; |
115 | } |
116 | |
117 | //////////////////////////////////////// |
118 | // ColorStopAtlasPrivate methods |
119 | ColorStopAtlasPrivate:: |
120 | ColorStopAtlasPrivate(fastuidraw::reference_counted_ptr<fastuidraw::ColorStopBackingStore> pbacking_store): |
121 | m_delayed_interval_freeing_counter(0), |
122 | m_backing_store(pbacking_store), |
123 | m_allocated(0) |
124 | { |
125 | FASTUIDRAWassert(m_backing_store); |
126 | if (m_backing_store->dimensions().y() > 0) |
127 | { |
128 | add_bookkeeping(m_backing_store->dimensions().y()); |
129 | } |
130 | } |
131 | |
132 | void |
133 | ColorStopAtlasPrivate:: |
134 | remove_entry_from_available_layers(std::map<int, std::set<int> >::iterator iter, int y) |
135 | { |
136 | FASTUIDRAWassert(iter != m_available_layers.end()); |
137 | FASTUIDRAWassert(iter->second.find(y) != iter->second.end()); |
138 | iter->second.erase(y); |
139 | if (iter->second.empty()) |
140 | { |
141 | m_available_layers.erase(iter); |
142 | } |
143 | } |
144 | |
145 | void |
146 | ColorStopAtlasPrivate:: |
147 | add_bookkeeping(int new_size) |
148 | { |
149 | int width(m_backing_store->dimensions().x()); |
150 | int old_size(m_layer_allocator.size()); |
151 | std::set<int> &S(m_available_layers[width]); |
152 | |
153 | FASTUIDRAWassert(new_size > old_size); |
154 | m_layer_allocator.resize(new_size, nullptr); |
155 | for(int y = old_size; y < new_size; ++y) |
156 | { |
157 | m_layer_allocator[y] = FASTUIDRAWnew fastuidraw::interval_allocator(width); |
158 | S.insert(y); |
159 | } |
160 | } |
161 | |
162 | void |
163 | ColorStopAtlasPrivate:: |
164 | deallocate_implement(fastuidraw::ivec2 location, int width) |
165 | { |
166 | int y(location.y()); |
167 | FASTUIDRAWassert(m_layer_allocator[y]); |
168 | FASTUIDRAWassert(m_delayed_interval_freeing_counter == 0); |
169 | |
170 | int old_max, new_max; |
171 | |
172 | old_max = m_layer_allocator[y]->largest_free_interval(); |
173 | m_layer_allocator[y]->free_interval(location.x(), width); |
174 | new_max = m_layer_allocator[y]->largest_free_interval(); |
175 | |
176 | if (old_max != new_max) |
177 | { |
178 | std::map<int, std::set<int> >::iterator iter; |
179 | |
180 | iter = m_available_layers.find(old_max); |
181 | remove_entry_from_available_layers(iter, y); |
182 | m_available_layers[new_max].insert(y); |
183 | } |
184 | m_allocated -= width; |
185 | } |
186 | |
187 | ///////////////////////////////////// |
188 | // fastuidraw::ColorStopBackingStore methods |
189 | fastuidraw::ColorStopBackingStore:: |
190 | ColorStopBackingStore(int w, int num_layers) |
191 | { |
192 | m_d = FASTUIDRAWnew ColorStopBackingStorePrivate(w, num_layers); |
193 | } |
194 | |
195 | fastuidraw::ColorStopBackingStore:: |
196 | ColorStopBackingStore(ivec2 wl) |
197 | { |
198 | m_d = FASTUIDRAWnew ColorStopBackingStorePrivate(wl.x(), wl.y()); |
199 | } |
200 | |
201 | fastuidraw::ColorStopBackingStore:: |
202 | ~ColorStopBackingStore() |
203 | { |
204 | ColorStopBackingStorePrivate *d; |
205 | d = static_cast<ColorStopBackingStorePrivate*>(m_d); |
206 | FASTUIDRAWdelete(d); |
207 | m_d = nullptr; |
208 | } |
209 | |
210 | fastuidraw::ivec2 |
211 | fastuidraw::ColorStopBackingStore:: |
212 | dimensions(void) const |
213 | { |
214 | ColorStopBackingStorePrivate *d; |
215 | d = static_cast<ColorStopBackingStorePrivate*>(m_d); |
216 | return d->m_dimensions; |
217 | } |
218 | |
219 | int |
220 | fastuidraw::ColorStopBackingStore:: |
221 | width_times_height(void) const |
222 | { |
223 | ColorStopBackingStorePrivate *d; |
224 | d = static_cast<ColorStopBackingStorePrivate*>(m_d); |
225 | return d->m_width_times_height; |
226 | } |
227 | |
228 | void |
229 | fastuidraw::ColorStopBackingStore:: |
230 | resize(int new_num_layers) |
231 | { |
232 | ColorStopBackingStorePrivate *d; |
233 | d = static_cast<ColorStopBackingStorePrivate*>(m_d); |
234 | FASTUIDRAWassert(new_num_layers > d->m_dimensions.y()); |
235 | resize_implement(new_num_layers); |
236 | d->m_dimensions.y() = new_num_layers; |
237 | d->m_width_times_height = d->m_dimensions.x() * d->m_dimensions.y(); |
238 | } |
239 | |
240 | /////////////////////////////////////// |
241 | // fastuidraw::ColorStopAtlas methods |
242 | fastuidraw::ColorStopAtlas:: |
243 | ColorStopAtlas(reference_counted_ptr<ColorStopBackingStore> pbacking_store) |
244 | { |
245 | m_d = FASTUIDRAWnew ColorStopAtlasPrivate(pbacking_store); |
246 | } |
247 | |
248 | fastuidraw::ColorStopAtlas:: |
249 | ~ColorStopAtlas() |
250 | { |
251 | ColorStopAtlasPrivate *d; |
252 | d = static_cast<ColorStopAtlasPrivate*>(m_d); |
253 | |
254 | FASTUIDRAWassert(d->m_delayed_interval_freeing_counter == 0); |
255 | FASTUIDRAWassert(d->m_allocated == 0); |
256 | for(interval_allocator *q : d->m_layer_allocator) |
257 | { |
258 | FASTUIDRAWdelete(q); |
259 | } |
260 | FASTUIDRAWdelete(d); |
261 | m_d = nullptr; |
262 | } |
263 | |
264 | fastuidraw::reference_counted_ptr<fastuidraw::ColorStopSequence> |
265 | fastuidraw::ColorStopAtlas:: |
266 | create(const ColorStopArray &color_stops, unsigned int pwidth) |
267 | { |
268 | pwidth = t_min(pwidth, max_width()); |
269 | if (pwidth == 0) |
270 | { |
271 | return nullptr; |
272 | } |
273 | return FASTUIDRAWnew ColorStopSequence(color_stops, *this, pwidth); |
274 | } |
275 | |
276 | void |
277 | fastuidraw::ColorStopAtlas:: |
278 | lock_resources(void) |
279 | { |
280 | ColorStopAtlasPrivate *d; |
281 | d = static_cast<ColorStopAtlasPrivate*>(m_d); |
282 | |
283 | std::lock_guard<std::mutex> m(d->m_mutex); |
284 | ++d->m_delayed_interval_freeing_counter; |
285 | } |
286 | |
287 | void |
288 | fastuidraw::ColorStopAtlas:: |
289 | unlock_resources(void) |
290 | { |
291 | ColorStopAtlasPrivate *d; |
292 | d = static_cast<ColorStopAtlasPrivate*>(m_d); |
293 | |
294 | std::lock_guard<std::mutex> m(d->m_mutex); |
295 | FASTUIDRAWassert(d->m_delayed_interval_freeing_counter >= 1); |
296 | --d->m_delayed_interval_freeing_counter; |
297 | if (d->m_delayed_interval_freeing_counter == 0) |
298 | { |
299 | for(unsigned int i = 0, endi = d->m_delayed_freed_intervals.size(); i < endi; ++i) |
300 | { |
301 | d->deallocate_implement(d->m_delayed_freed_intervals[i].first, |
302 | d->m_delayed_freed_intervals[i].second); |
303 | } |
304 | d->m_delayed_freed_intervals.clear(); |
305 | } |
306 | } |
307 | |
308 | void |
309 | fastuidraw::ColorStopAtlas:: |
310 | deallocate(ivec2 location, int width) |
311 | { |
312 | ColorStopAtlasPrivate *d; |
313 | d = static_cast<ColorStopAtlasPrivate*>(m_d); |
314 | |
315 | std::lock_guard<std::mutex> m(d->m_mutex); |
316 | if (d->m_delayed_interval_freeing_counter == 0) |
317 | { |
318 | d->deallocate_implement(location, width); |
319 | } |
320 | else |
321 | { |
322 | d->m_delayed_freed_intervals.push_back(delayed_free_entry(location, width)); |
323 | } |
324 | } |
325 | |
326 | void |
327 | fastuidraw::ColorStopAtlas:: |
328 | flush(void) const |
329 | { |
330 | ColorStopAtlasPrivate *d; |
331 | d = static_cast<ColorStopAtlasPrivate*>(m_d); |
332 | |
333 | std::lock_guard<std::mutex> m(d->m_mutex); |
334 | d->m_backing_store->flush(); |
335 | } |
336 | |
337 | int |
338 | fastuidraw::ColorStopAtlas:: |
339 | total_available(void) const |
340 | { |
341 | ColorStopAtlasPrivate *d; |
342 | d = static_cast<ColorStopAtlasPrivate*>(m_d); |
343 | |
344 | std::lock_guard<std::mutex> m(d->m_mutex); |
345 | return d->m_backing_store->width_times_height() - d->m_allocated; |
346 | } |
347 | |
348 | fastuidraw::ivec2 |
349 | fastuidraw::ColorStopAtlas:: |
350 | allocate(c_array<const u8vec4> data) |
351 | { |
352 | ColorStopAtlasPrivate *d; |
353 | d = static_cast<ColorStopAtlasPrivate*>(m_d); |
354 | |
355 | std::lock_guard<std::mutex> m(d->m_mutex); |
356 | |
357 | std::map<int, std::set<int> >::iterator iter; |
358 | ivec2 return_value; |
359 | unsigned int width(data.size()); |
360 | |
361 | FASTUIDRAWassert(width > 0); |
362 | FASTUIDRAWassert(width <= max_width()); |
363 | |
364 | iter = d->m_available_layers.lower_bound(width); |
365 | if (iter == d->m_available_layers.end()) |
366 | { |
367 | /* TODO: what should the resize algorithm be? |
368 | * Right now we double the size, but that might |
369 | * be excessive. |
370 | */ |
371 | int new_size, old_size; |
372 | old_size = d->m_backing_store->dimensions().y(); |
373 | new_size = std::max(1, old_size * 2); |
374 | d->m_backing_store->resize(new_size); |
375 | d->add_bookkeeping(new_size); |
376 | |
377 | iter = d->m_available_layers.lower_bound(width); |
378 | FASTUIDRAWassert(iter != d->m_available_layers.end()); |
379 | } |
380 | |
381 | FASTUIDRAWassert(!iter->second.empty()); |
382 | |
383 | int y(*iter->second.begin()); |
384 | int old_max, new_max; |
385 | |
386 | old_max = d->m_layer_allocator[y]->largest_free_interval(); |
387 | return_value.x() = d->m_layer_allocator[y]->allocate_interval(width); |
388 | FASTUIDRAWassert(return_value.x() >= 0); |
389 | new_max = d->m_layer_allocator[y]->largest_free_interval(); |
390 | |
391 | if (old_max != new_max) |
392 | { |
393 | d->remove_entry_from_available_layers(iter, y); |
394 | d->m_available_layers[new_max].insert(y); |
395 | } |
396 | return_value.y() = y; |
397 | |
398 | d->m_backing_store->set_data(return_value.x(), return_value.y(), |
399 | width, data); |
400 | d->m_allocated += width; |
401 | return return_value; |
402 | } |
403 | |
404 | unsigned int |
405 | fastuidraw::ColorStopAtlas:: |
406 | max_width(void) const |
407 | { |
408 | ColorStopAtlasPrivate *d; |
409 | d = static_cast<ColorStopAtlasPrivate*>(m_d); |
410 | return d->m_backing_store->dimensions().x(); |
411 | } |
412 | |
413 | fastuidraw::reference_counted_ptr<const fastuidraw::ColorStopBackingStore> |
414 | fastuidraw::ColorStopAtlas:: |
415 | backing_store(void) const |
416 | { |
417 | ColorStopAtlasPrivate *d; |
418 | d = static_cast<ColorStopAtlasPrivate*>(m_d); |
419 | return d->m_backing_store; |
420 | } |
421 | |
422 | /////////////////////////////////////////// |
423 | // fastuidraw::ColorStopSequence methods |
424 | fastuidraw::ColorStopSequence:: |
425 | ColorStopSequence(const ColorStopArray &pcolor_stops, |
426 | ColorStopAtlas &atlas, unsigned int pwidth) |
427 | { |
428 | ColorStopSequencePrivate *d; |
429 | d = FASTUIDRAWnew ColorStopSequencePrivate(); |
430 | m_d = d; |
431 | |
432 | d->m_atlas = &atlas; |
433 | d->m_width = pwidth; |
434 | |
435 | c_array<const ColorStop> color_stops(pcolor_stops.values()); |
436 | FASTUIDRAWassert(d->m_atlas); |
437 | FASTUIDRAWassert(pwidth>0); |
438 | |
439 | if (pwidth >= d->m_atlas->max_width()) |
440 | { |
441 | d->m_width = d->m_atlas->max_width(); |
442 | d->m_start_slack = 0; |
443 | d->m_end_slack = 0; |
444 | } |
445 | else if (pwidth == d->m_atlas->max_width() - 1) |
446 | { |
447 | d->m_start_slack = 0; |
448 | d->m_end_slack = 1; |
449 | } |
450 | else |
451 | { |
452 | d->m_start_slack = 1; |
453 | d->m_end_slack = 1; |
454 | } |
455 | |
456 | std::vector<u8vec4> data(d->m_width + d->m_start_slack + d->m_end_slack); |
457 | |
458 | /* Discretize and interpolate color_stops into data */ |
459 | { |
460 | unsigned int data_i, color_stops_i; |
461 | float current_t, delta_t; |
462 | |
463 | delta_t = 1.0f / static_cast<float>(d->m_width); |
464 | current_t = static_cast<float>(-d->m_start_slack) * delta_t; |
465 | |
466 | for(data_i = 0; current_t <= color_stops[0].m_place; ++data_i, current_t += delta_t) |
467 | { |
468 | data[data_i] = color_stops[0].m_color; |
469 | } |
470 | |
471 | for(color_stops_i = 1; color_stops_i < color_stops.size(); ++color_stops_i) |
472 | { |
473 | ColorStop prev_color(color_stops[color_stops_i-1]); |
474 | ColorStop next_color(color_stops[color_stops_i]); |
475 | |
476 | /* There are cases where an application might |
477 | * add two color stops with the same stop location; |
478 | * these are for the purpose of changing color |
479 | * immediately at the named location. Adding the |
480 | * check avoids a divide error. The next texel |
481 | * in the gradient will observe the dramatic change. |
482 | * However, passing an interpolate between the |
483 | * immediate change and the texel after it will |
484 | * have the gradient interpolate from before the |
485 | * change to after the change sadly. |
486 | * |
487 | * The only way to really handle "fast immediate" |
488 | * changes is to make an array of (stop, color) |
489 | * pair values packed into an array readable from |
490 | * the shader and the fragment shader does the |
491 | * search. This means that rather than a single |
492 | * texture() command we would have multiple buffer |
493 | * look up value in the frag shader to get the |
494 | * interpolate. We can optimize it some where we |
495 | * increase the array size to the nearest power of 2 |
496 | * so that within a triangle there is no branching |
497 | * in the hunt, but that would mean log2(N) buffer |
498 | * reads per pixel. ICK. |
499 | */ |
500 | if (current_t < next_color.m_place) |
501 | { |
502 | ColorInterpolator color_interpolate(prev_color, next_color); |
503 | |
504 | for(; current_t < next_color.m_place && data_i < data.size(); |
505 | ++data_i, current_t += delta_t) |
506 | { |
507 | data[data_i] = color_interpolate.interpolate(current_t); |
508 | } |
509 | } |
510 | } |
511 | |
512 | for(;data_i < data.size(); ++data_i) |
513 | { |
514 | data[data_i] = color_stops.back().m_color; |
515 | } |
516 | } |
517 | |
518 | |
519 | d->m_texel_location = d->m_atlas->allocate(make_c_array(data)); |
520 | |
521 | /* Adjust m_texel_location to remove the start slack |
522 | */ |
523 | d->m_texel_location.x() += d->m_start_slack; |
524 | } |
525 | |
526 | fastuidraw::ColorStopSequence:: |
527 | ~ColorStopSequence(void) |
528 | { |
529 | ColorStopSequencePrivate *d; |
530 | d = static_cast<ColorStopSequencePrivate*>(m_d); |
531 | |
532 | ivec2 loc(d->m_texel_location); |
533 | |
534 | loc.x() -= d->m_start_slack; |
535 | d->m_atlas->deallocate(loc, d->m_width + d->m_start_slack + d->m_end_slack); |
536 | FASTUIDRAWdelete(d); |
537 | m_d = nullptr; |
538 | } |
539 | |
540 | fastuidraw::ivec2 |
541 | fastuidraw::ColorStopSequence:: |
542 | texel_location(void) const |
543 | { |
544 | ColorStopSequencePrivate *d; |
545 | d = static_cast<ColorStopSequencePrivate*>(m_d); |
546 | return d->m_texel_location; |
547 | } |
548 | |
549 | int |
550 | fastuidraw::ColorStopSequence:: |
551 | width(void) const |
552 | { |
553 | ColorStopSequencePrivate *d; |
554 | d = static_cast<ColorStopSequencePrivate*>(m_d); |
555 | return d->m_width; |
556 | } |
557 | |
558 | fastuidraw::ColorStopAtlas& |
559 | fastuidraw::ColorStopSequence:: |
560 | atlas(void) const |
561 | { |
562 | ColorStopSequencePrivate *d; |
563 | d = static_cast<ColorStopSequencePrivate*>(m_d); |
564 | return *d->m_atlas; |
565 | } |
566 | |