Cycles: add cycles.merge_images operator for combing EXR renders.
[blender.git] / intern / cycles / blender / blender_util.h
1 /*
2  * Copyright 2011-2013 Blender Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 #ifndef __BLENDER_UTIL_H__
18 #define __BLENDER_UTIL_H__
19
20 #include "render/mesh.h"
21
22 #include "util/util_algorithm.h"
23 #include "util/util_array.h"
24 #include "util/util_map.h"
25 #include "util/util_path.h"
26 #include "util/util_set.h"
27 #include "util/util_transform.h"
28 #include "util/util_types.h"
29 #include "util/util_vector.h"
30
31 /* Hacks to hook into Blender API
32  * todo: clean this up ... */
33
34 extern "C" {
35 void BKE_image_user_frame_calc(void *iuser, int cfra, int fieldnr);
36 void BKE_image_user_file_path(void *iuser, void *ima, char *path);
37 unsigned char *BKE_image_get_pixels_for_frame(void *image, int frame);
38 float *BKE_image_get_float_pixels_for_frame(void *image, int frame);
39 }
40
41 CCL_NAMESPACE_BEGIN
42
43 void python_thread_state_save(void **python_thread_state);
44 void python_thread_state_restore(void **python_thread_state);
45
46 static inline BL::Mesh object_to_mesh(BL::BlendData& data,
47                                       BL::Object& object,
48                                       BL::Scene& scene,
49                                       bool apply_modifiers,
50                                       bool render,
51                                       bool calc_undeformed,
52                                       Mesh::SubdivisionType subdivision_type)
53 {
54         bool subsurf_mod_show_render = false;
55         bool subsurf_mod_show_viewport = false;
56
57         if(subdivision_type != Mesh::SUBDIVISION_NONE) {
58                 BL::Modifier subsurf_mod = object.modifiers[object.modifiers.length()-1];
59
60                 subsurf_mod_show_render = subsurf_mod.show_render();
61                 subsurf_mod_show_viewport = subsurf_mod.show_viewport();
62
63                 subsurf_mod.show_render(false);
64                 subsurf_mod.show_viewport(false);
65         }
66
67         BL::Mesh me = data.meshes.new_from_object(scene, object, apply_modifiers, (render)? 2: 1, false, calc_undeformed);
68
69         if(subdivision_type != Mesh::SUBDIVISION_NONE) {
70                 BL::Modifier subsurf_mod = object.modifiers[object.modifiers.length()-1];
71
72                 subsurf_mod.show_render(subsurf_mod_show_render);
73                 subsurf_mod.show_viewport(subsurf_mod_show_viewport);
74         }
75
76         if((bool)me) {
77                 if(me.use_auto_smooth()) {
78                         if(subdivision_type == Mesh::SUBDIVISION_CATMULL_CLARK) {
79                                 me.calc_normals_split();
80                         }
81                         else {
82                                 me.split_faces(false);
83                         }
84                 }
85                 if(subdivision_type == Mesh::SUBDIVISION_NONE) {
86                         me.calc_tessface(true);
87                 }
88         }
89         return me;
90 }
91
92 static inline void colorramp_to_array(BL::ColorRamp& ramp,
93                                       array<float3>& ramp_color,
94                                       array<float>& ramp_alpha,
95                                       int size)
96 {
97         ramp_color.resize(size);
98         ramp_alpha.resize(size);
99
100         for(int i = 0; i < size; i++) {
101                 float color[4];
102
103                 ramp.evaluate((float)i/(float)(size-1), color);
104                 ramp_color[i] = make_float3(color[0], color[1], color[2]);
105                 ramp_alpha[i] = color[3];
106         }
107 }
108
109 static inline void curvemap_minmax_curve(/*const*/ BL::CurveMap& curve,
110                                          float *min_x,
111                                          float *max_x)
112 {
113         *min_x = min(*min_x, curve.points[0].location()[0]);
114         *max_x = max(*max_x, curve.points[curve.points.length() - 1].location()[0]);
115 }
116
117 static inline void curvemapping_minmax(/*const*/ BL::CurveMapping& cumap,
118                                        bool rgb_curve,
119                                        float *min_x,
120                                        float *max_x)
121 {
122         /* const int num_curves = cumap.curves.length(); */  /* Gives linking error so far. */
123         const int num_curves = rgb_curve? 4: 3;
124         *min_x = FLT_MAX;
125         *max_x = -FLT_MAX;
126         for(int i = 0; i < num_curves; ++i) {
127                 BL::CurveMap map(cumap.curves[i]);
128                 curvemap_minmax_curve(map, min_x, max_x);
129         }
130 }
131
132 static inline void curvemapping_to_array(BL::CurveMapping& cumap,
133                                          array<float>& data,
134                                          int size)
135 {
136         cumap.update();
137         BL::CurveMap curve = cumap.curves[0];
138         data.resize(size);
139         for(int i = 0; i < size; i++) {
140                 float t = (float)i/(float)(size-1);
141                 data[i] = curve.evaluate(t);
142         }
143 }
144
145 static inline void curvemapping_color_to_array(BL::CurveMapping& cumap,
146                                                array<float3>& data,
147                                                int size,
148                                                bool rgb_curve)
149 {
150         float min_x = 0.0f, max_x = 1.0f;
151
152         /* TODO(sergey): There is no easy way to automatically guess what is
153          * the range to be used here for the case when mapping is applied on
154          * top of another mapping (i.e. R curve applied on top of common
155          * one).
156          *
157          * Using largest possible range form all curves works correct for the
158          * cases like vector curves and should be good enough heuristic for
159          * the color curves as well.
160          *
161          * There might be some better estimations here tho.
162          */
163         curvemapping_minmax(cumap, rgb_curve, &min_x, &max_x);
164
165         const float range_x = max_x - min_x;
166
167         cumap.update();
168
169         BL::CurveMap mapR = cumap.curves[0];
170         BL::CurveMap mapG = cumap.curves[1];
171         BL::CurveMap mapB = cumap.curves[2];
172
173         data.resize(size);
174
175         if(rgb_curve) {
176                 BL::CurveMap mapI = cumap.curves[3];
177                 for(int i = 0; i < size; i++) {
178                         const float t = min_x + (float)i/(float)(size-1) * range_x;
179                         data[i] = make_float3(mapR.evaluate(mapI.evaluate(t)),
180                                               mapG.evaluate(mapI.evaluate(t)),
181                                               mapB.evaluate(mapI.evaluate(t)));
182                 }
183         }
184         else {
185                 for(int i = 0; i < size; i++) {
186                         float t = min_x + (float)i/(float)(size-1) * range_x;
187                         data[i] = make_float3(mapR.evaluate(t),
188                                               mapG.evaluate(t),
189                                               mapB.evaluate(t));
190                 }
191         }
192 }
193
194 static inline bool BKE_object_is_modified(BL::Object& self,
195                                           BL::Scene& scene,
196                                           bool preview)
197 {
198         return self.is_modified(scene, (preview)? (1<<0): (1<<1))? true: false;
199 }
200
201 static inline bool BKE_object_is_deform_modified(BL::Object& self,
202                                                  BL::Scene& scene,
203                                                  bool preview)
204 {
205         return self.is_deform_modified(scene, (preview)? (1<<0): (1<<1))? true: false;
206 }
207
208 static inline int render_resolution_x(BL::RenderSettings& b_render)
209 {
210         return b_render.resolution_x()*b_render.resolution_percentage()/100;
211 }
212
213 static inline int render_resolution_y(BL::RenderSettings& b_render)
214 {
215         return b_render.resolution_y()*b_render.resolution_percentage()/100;
216 }
217
218 static inline string image_user_file_path(BL::ImageUser& iuser,
219                                           BL::Image& ima,
220                                           int cfra)
221 {
222         char filepath[1024];
223         BKE_image_user_frame_calc(iuser.ptr.data, cfra, 0);
224         BKE_image_user_file_path(iuser.ptr.data, ima.ptr.data, filepath);
225         return string(filepath);
226 }
227
228 static inline int image_user_frame_number(BL::ImageUser& iuser, int cfra)
229 {
230         BKE_image_user_frame_calc(iuser.ptr.data, cfra, 0);
231         return iuser.frame_current();
232 }
233
234 static inline unsigned char *image_get_pixels_for_frame(BL::Image& image,
235                                                         int frame)
236 {
237         return BKE_image_get_pixels_for_frame(image.ptr.data, frame);
238 }
239
240 static inline float *image_get_float_pixels_for_frame(BL::Image& image,
241                                                       int frame)
242 {
243         return BKE_image_get_float_pixels_for_frame(image.ptr.data, frame);
244 }
245
246 static inline void render_add_metadata(BL::RenderResult& b_rr, string name, string value)
247 {
248         b_rr.stamp_data_add_field(name.c_str(), value.c_str());
249 }
250
251
252 /* Utilities */
253
254 static inline Transform get_transform(const BL::Array<float, 16>& array)
255 {
256         ProjectionTransform projection;
257
258         /* We assume both types to be just 16 floats, and transpose because blender
259          * use column major matrix order while we use row major. */
260         memcpy((void *)&projection, &array, sizeof(float)*16);
261         projection = projection_transpose(projection);
262
263         /* Drop last row, matrix is assumed to be affine transform. */
264         return projection_to_transform(projection);
265 }
266
267 static inline float2 get_float2(const BL::Array<float, 2>& array)
268 {
269         return make_float2(array[0], array[1]);
270 }
271
272 static inline float3 get_float3(const BL::Array<float, 2>& array)
273 {
274         return make_float3(array[0], array[1], 0.0f);
275 }
276
277 static inline float3 get_float3(const BL::Array<float, 3>& array)
278 {
279         return make_float3(array[0], array[1], array[2]);
280 }
281
282 static inline float3 get_float3(const BL::Array<float, 4>& array)
283 {
284         return make_float3(array[0], array[1], array[2]);
285 }
286
287 static inline float4 get_float4(const BL::Array<float, 4>& array)
288 {
289         return make_float4(array[0], array[1], array[2], array[3]);
290 }
291
292 static inline int3 get_int3(const BL::Array<int, 3>& array)
293 {
294         return make_int3(array[0], array[1], array[2]);
295 }
296
297 static inline int4 get_int4(const BL::Array<int, 4>& array)
298 {
299         return make_int4(array[0], array[1], array[2], array[3]);
300 }
301
302 static inline uint get_layer(const BL::Array<bool, 20>& array)
303 {
304         uint layer = 0;
305
306         for(uint i = 0; i < 20; i++)
307                 if(array[i])
308                         layer |= (1 << i);
309
310         return layer;
311 }
312
313 static inline uint get_layer(const BL::Array<bool, 20>& array,
314                              const BL::Array<bool, 8>& local_array,
315                              bool is_light = false,
316                              uint scene_layers = (1 << 20) - 1)
317 {
318         uint layer = 0;
319
320         for(uint i = 0; i < 20; i++)
321                 if(array[i])
322                         layer |= (1 << i);
323
324         if(is_light) {
325                 /* Consider light is visible if it was visible without layer
326                  * override, which matches behavior of Blender Internal.
327                  */
328                 if(layer & scene_layers) {
329                         for(uint i = 0; i < 8; i++)
330                                 layer |= (1 << (20+i));
331                 }
332         }
333         else {
334                 for(uint i = 0; i < 8; i++)
335                         if(local_array[i])
336                                 layer |= (1 << (20+i));
337         }
338
339         return layer;
340 }
341
342 static inline float3 get_float3(PointerRNA& ptr, const char *name)
343 {
344         float3 f;
345         RNA_float_get_array(&ptr, name, &f.x);
346         return f;
347 }
348
349 static inline void set_float3(PointerRNA& ptr, const char *name, float3 value)
350 {
351         RNA_float_set_array(&ptr, name, &value.x);
352 }
353
354 static inline float4 get_float4(PointerRNA& ptr, const char *name)
355 {
356         float4 f;
357         RNA_float_get_array(&ptr, name, &f.x);
358         return f;
359 }
360
361 static inline void set_float4(PointerRNA& ptr, const char *name, float4 value)
362 {
363         RNA_float_set_array(&ptr, name, &value.x);
364 }
365
366 static inline bool get_boolean(PointerRNA& ptr, const char *name)
367 {
368         return RNA_boolean_get(&ptr, name)? true: false;
369 }
370
371 static inline void set_boolean(PointerRNA& ptr, const char *name, bool value)
372 {
373         RNA_boolean_set(&ptr, name, (int)value);
374 }
375
376 static inline float get_float(PointerRNA& ptr, const char *name)
377 {
378         return RNA_float_get(&ptr, name);
379 }
380
381 static inline void set_float(PointerRNA& ptr, const char *name, float value)
382 {
383         RNA_float_set(&ptr, name, value);
384 }
385
386 static inline int get_int(PointerRNA& ptr, const char *name)
387 {
388         return RNA_int_get(&ptr, name);
389 }
390
391 static inline void set_int(PointerRNA& ptr, const char *name, int value)
392 {
393         RNA_int_set(&ptr, name, value);
394 }
395
396 /* Get a RNA enum value with sanity check: if the RNA value is above num_values
397  * the function will return a fallback default value.
398  *
399  * NOTE: This function assumes that RNA enum values are a continuous sequence
400  * from 0 to num_values-1. Be careful to use it with enums where some values are
401  * deprecated!
402  */
403 static inline int get_enum(PointerRNA& ptr,
404                            const char *name,
405                            int num_values = -1,
406                            int default_value = -1)
407 {
408         int value = RNA_enum_get(&ptr, name);
409         if(num_values != -1 && value >= num_values) {
410                 assert(default_value != -1);
411                 value = default_value;
412         }
413         return value;
414 }
415
416 static inline string get_enum_identifier(PointerRNA& ptr, const char *name)
417 {
418         PropertyRNA *prop = RNA_struct_find_property(&ptr, name);
419         const char *identifier = "";
420         int value = RNA_property_enum_get(&ptr, prop);
421
422         RNA_property_enum_identifier(NULL, &ptr, prop, value, &identifier);
423
424         return string(identifier);
425 }
426
427 static inline void set_enum(PointerRNA& ptr, const char *name, int value)
428 {
429         RNA_enum_set(&ptr, name, value);
430 }
431
432 static inline void set_enum(PointerRNA& ptr, const char *name, const string &identifier)
433 {
434         RNA_enum_set_identifier(NULL, &ptr, name, identifier.c_str());
435 }
436
437 static inline string get_string(PointerRNA& ptr, const char *name)
438 {
439         char cstrbuf[1024];
440         char *cstr = RNA_string_get_alloc(&ptr, name, cstrbuf, sizeof(cstrbuf));
441         string str(cstr);
442         if(cstr != cstrbuf)
443                 MEM_freeN(cstr);
444
445         return str;
446 }
447
448 static inline void set_string(PointerRNA& ptr, const char *name, const string &value)
449 {
450         RNA_string_set(&ptr, name, value.c_str());
451 }
452
453 /* Relative Paths */
454
455 static inline string blender_absolute_path(BL::BlendData& b_data,
456                                            BL::ID& b_id,
457                                            const string& path)
458 {
459         if(path.size() >= 2 && path[0] == '/' && path[1] == '/') {
460                 string dirname;
461
462                 if(b_id.library()) {
463                         BL::ID b_library_id(b_id.library());
464                         dirname = blender_absolute_path(b_data,
465                                                         b_library_id,
466                                                         b_id.library().filepath());
467                 }
468                 else
469                         dirname = b_data.filepath();
470
471                 return path_join(path_dirname(dirname), path.substr(2));
472         }
473
474         return path;
475 }
476
477 static inline string get_text_datablock_content(const PointerRNA& ptr)
478 {
479         if(ptr.data == NULL) {
480                 return "";
481         }
482
483         string content;
484         BL::Text::lines_iterator iter;
485         for(iter.begin(ptr); iter; ++iter) {
486                 content += iter->body() + "\n";
487         }
488
489         return content;
490 }
491
492 /* Texture Space */
493
494 static inline void mesh_texture_space(BL::Mesh& b_mesh,
495                                       float3& loc,
496                                       float3& size)
497 {
498         loc = get_float3(b_mesh.texspace_location());
499         size = get_float3(b_mesh.texspace_size());
500
501         if(size.x != 0.0f) size.x = 0.5f/size.x;
502         if(size.y != 0.0f) size.y = 0.5f/size.y;
503         if(size.z != 0.0f) size.z = 0.5f/size.z;
504
505         loc = loc*size - make_float3(0.5f, 0.5f, 0.5f);
506 }
507
508 /* Object motion steps, returns 0 if no motion blur needed. */
509 static inline uint object_motion_steps(BL::Object& b_parent, BL::Object& b_ob)
510 {
511         /* Get motion enabled and steps from object itself. */
512         PointerRNA cobject = RNA_pointer_get(&b_ob.ptr, "cycles");
513         bool use_motion = get_boolean(cobject, "use_motion_blur");
514         if(!use_motion) {
515                 return 0;
516         }
517
518         uint steps = max(1, get_int(cobject, "motion_steps"));
519
520         /* Also check parent object, so motion blur and steps can be
521          * controlled by dupligroup duplicator for linked groups. */
522         if(b_parent.ptr.data != b_ob.ptr.data) {
523                 PointerRNA parent_cobject = RNA_pointer_get(&b_parent.ptr, "cycles");
524                 use_motion &= get_boolean(parent_cobject, "use_motion_blur");
525
526                 if(!use_motion) {
527                         return 0;
528                 }
529
530                 steps = max(steps, get_int(parent_cobject, "motion_steps"));
531         }
532
533         /* Use uneven number of steps so we get one keyframe at the current frame,
534          * and use 2^(steps - 1) so objects with more/fewer steps still have samples
535          * at the same times, to avoid sampling at many different times. */
536         return (2 << (steps - 1)) + 1;
537 }
538
539 /* object uses deformation motion blur */
540 static inline bool object_use_deform_motion(BL::Object& b_parent,
541                                             BL::Object& b_ob)
542 {
543         PointerRNA cobject = RNA_pointer_get(&b_ob.ptr, "cycles");
544         bool use_deform_motion = get_boolean(cobject, "use_deform_motion");
545         /* If motion blur is enabled for the object we also check
546          * whether it's enabled for the parent object as well.
547          *
548          * This way we can control motion blur from the dupligroup
549          * duplicator much easier.
550          */
551         if(use_deform_motion && b_parent.ptr.data != b_ob.ptr.data) {
552                 PointerRNA parent_cobject = RNA_pointer_get(&b_parent.ptr, "cycles");
553                 use_deform_motion &= get_boolean(parent_cobject, "use_deform_motion");
554         }
555         return use_deform_motion;
556 }
557
558 static inline BL::SmokeDomainSettings object_smoke_domain_find(BL::Object& b_ob)
559 {
560         BL::Object::modifiers_iterator b_mod;
561
562         for(b_ob.modifiers.begin(b_mod); b_mod != b_ob.modifiers.end(); ++b_mod) {
563                 if(b_mod->is_a(&RNA_SmokeModifier)) {
564                         BL::SmokeModifier b_smd(*b_mod);
565
566                         if(b_smd.smoke_type() == BL::SmokeModifier::smoke_type_DOMAIN)
567                                 return b_smd.domain_settings();
568                 }
569         }
570
571         return BL::SmokeDomainSettings(PointerRNA_NULL);
572 }
573
574 static inline BL::DomainFluidSettings object_fluid_domain_find(BL::Object b_ob)
575 {
576         BL::Object::modifiers_iterator b_mod;
577
578         for(b_ob.modifiers.begin(b_mod); b_mod != b_ob.modifiers.end(); ++b_mod) {
579                 if(b_mod->is_a(&RNA_FluidSimulationModifier)) {
580                         BL::FluidSimulationModifier b_fmd(*b_mod);
581                         BL::FluidSettings fss = b_fmd.settings();
582
583                         if(fss.type() == BL::FluidSettings::type_DOMAIN)
584                                 return (BL::DomainFluidSettings)b_fmd.settings();
585                 }
586         }
587
588         return BL::DomainFluidSettings(PointerRNA_NULL);
589 }
590
591 static inline Mesh::SubdivisionType object_subdivision_type(BL::Object& b_ob, bool preview, bool experimental)
592 {
593         PointerRNA cobj = RNA_pointer_get(&b_ob.ptr, "cycles");
594
595         if(cobj.data && b_ob.modifiers.length() > 0 && experimental) {
596                 BL::Modifier mod = b_ob.modifiers[b_ob.modifiers.length()-1];
597                 bool enabled = preview ? mod.show_viewport() : mod.show_render();
598
599                 if(enabled && mod.type() == BL::Modifier::type_SUBSURF && RNA_boolean_get(&cobj, "use_adaptive_subdivision")) {
600                         BL::SubsurfModifier subsurf(mod);
601
602                         if(subsurf.subdivision_type() == BL::SubsurfModifier::subdivision_type_CATMULL_CLARK) {
603                                 return Mesh::SUBDIVISION_CATMULL_CLARK;
604                         }
605                         else {
606                                 return Mesh::SUBDIVISION_LINEAR;
607                         }
608                 }
609         }
610
611         return Mesh::SUBDIVISION_NONE;
612 }
613
614 /* ID Map
615  *
616  * Utility class to keep in sync with blender data.
617  * Used for objects, meshes, lights and shaders. */
618
619 template<typename K, typename T>
620 class id_map {
621 public:
622         id_map(vector<T*> *scene_data_)
623         {
624                 scene_data = scene_data_;
625         }
626
627         T *find(const BL::ID& id)
628         {
629                 return find(id.ptr.id.data);
630         }
631
632         T *find(const K& key)
633         {
634                 if(b_map.find(key) != b_map.end()) {
635                         T *data = b_map[key];
636                         return data;
637                 }
638
639                 return NULL;
640         }
641
642         void set_recalc(const BL::ID& id)
643         {
644                 b_recalc.insert(id.ptr.data);
645         }
646
647         bool has_recalc()
648         {
649                 return !(b_recalc.empty());
650         }
651
652         void pre_sync()
653         {
654                 used_set.clear();
655         }
656
657         bool sync(T **r_data, const BL::ID& id)
658         {
659                 return sync(r_data, id, id, id.ptr.id.data);
660         }
661
662         bool sync(T **r_data, const BL::ID& id, const BL::ID& parent, const K& key)
663         {
664                 T *data = find(key);
665                 bool recalc;
666
667                 if(!data) {
668                         /* add data if it didn't exist yet */
669                         data = new T();
670                         scene_data->push_back(data);
671                         b_map[key] = data;
672                         recalc = true;
673                 }
674                 else {
675                         recalc = (b_recalc.find(id.ptr.data) != b_recalc.end());
676                         if(parent.ptr.data)
677                                 recalc = recalc || (b_recalc.find(parent.ptr.data) != b_recalc.end());
678                 }
679
680                 used(data);
681
682                 *r_data = data;
683                 return recalc;
684         }
685
686         bool is_used(const K& key)
687         {
688                 T *data = find(key);
689                 return (data) ? used_set.find(data) != used_set.end() : false;
690         }
691
692         void used(T *data)
693         {
694                 /* tag data as still in use */
695                 used_set.insert(data);
696         }
697
698         void set_default(T *data)
699         {
700                 b_map[NULL] = data;
701         }
702
703         bool post_sync(bool do_delete = true)
704         {
705                 /* remove unused data */
706                 vector<T*> new_scene_data;
707                 typename vector<T*>::iterator it;
708                 bool deleted = false;
709
710                 for(it = scene_data->begin(); it != scene_data->end(); it++) {
711                         T *data = *it;
712
713                         if(do_delete && used_set.find(data) == used_set.end()) {
714                                 delete data;
715                                 deleted = true;
716                         }
717                         else
718                                 new_scene_data.push_back(data);
719                 }
720
721                 *scene_data = new_scene_data;
722
723                 /* update mapping */
724                 map<K, T*> new_map;
725                 typedef pair<const K, T*> TMapPair;
726                 typename map<K, T*>::iterator jt;
727
728                 for(jt = b_map.begin(); jt != b_map.end(); jt++) {
729                         TMapPair& pair = *jt;
730
731                         if(used_set.find(pair.second) != used_set.end())
732                                 new_map[pair.first] = pair.second;
733                 }
734
735                 used_set.clear();
736                 b_recalc.clear();
737                 b_map = new_map;
738
739                 return deleted;
740         }
741
742 protected:
743         vector<T*> *scene_data;
744         map<K, T*> b_map;
745         set<T*> used_set;
746         set<void*> b_recalc;
747 };
748
749 /* Object Key */
750
751 enum { OBJECT_PERSISTENT_ID_SIZE = 16 };
752
753 struct ObjectKey {
754         void *parent;
755         int id[OBJECT_PERSISTENT_ID_SIZE];
756         void *ob;
757
758         ObjectKey(void *parent_, int id_[OBJECT_PERSISTENT_ID_SIZE], void *ob_)
759         : parent(parent_), ob(ob_)
760         {
761                 if(id_)
762                         memcpy(id, id_, sizeof(id));
763                 else
764                         memset(id, 0, sizeof(id));
765         }
766
767         bool operator<(const ObjectKey& k) const
768         {
769                 if(ob < k.ob) {
770                         return true;
771                 }
772                 else if(ob == k.ob) {
773                         if(parent < k.parent)
774                                 return true;
775                         else if(parent == k.parent)
776                                 return memcmp(id, k.id, sizeof(id)) < 0;
777                 }
778
779                 return false;
780         }
781 };
782
783 /* Particle System Key */
784
785 struct ParticleSystemKey {
786         void *ob;
787         int id[OBJECT_PERSISTENT_ID_SIZE];
788
789         ParticleSystemKey(void *ob_, int id_[OBJECT_PERSISTENT_ID_SIZE])
790         : ob(ob_)
791         {
792                 if(id_)
793                         memcpy(id, id_, sizeof(id));
794                 else
795                         memset(id, 0, sizeof(id));
796         }
797
798         bool operator<(const ParticleSystemKey& k) const
799         {
800                 /* first id is particle index, we don't compare that */
801                 if(ob < k.ob)
802                         return true;
803                 else if(ob == k.ob)
804                         return memcmp(id+1, k.id+1, sizeof(int)*(OBJECT_PERSISTENT_ID_SIZE-1)) < 0;
805
806                 return false;
807         }
808 };
809
810 class EdgeMap {
811 public:
812         EdgeMap() {
813         }
814
815         void clear() {
816                 edges_.clear();
817         }
818
819         void insert(int v0, int v1) {
820                 get_sorted_verts(v0, v1);
821                 edges_.insert(std::pair<int, int>(v0, v1));
822         }
823
824         bool exists(int v0, int v1) {
825                 get_sorted_verts(v0, v1);
826                 return edges_.find(std::pair<int, int>(v0, v1)) != edges_.end();
827         }
828
829 protected:
830         void get_sorted_verts(int& v0, int& v1) {
831                 if(v0 > v1) {
832                         swap(v0, v1);
833                 }
834         }
835
836         set< std::pair<int, int> > edges_;
837 };
838
839 CCL_NAMESPACE_END
840
841 #endif  /* __BLENDER_UTIL_H__ */