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