5bd22bf1de8da53a46bc7a9fbe827355dafaf53c
[blender-staging.git] / intern / cycles / render / mesh.cpp
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 #include "bvh.h"
18 #include "bvh_build.h"
19
20 #include "camera.h"
21 #include "curves.h"
22 #include "device.h"
23 #include "graph.h"
24 #include "shader.h"
25 #include "light.h"
26 #include "mesh.h"
27 #include "nodes.h"
28 #include "object.h"
29 #include "scene.h"
30
31 #include "osl_globals.h"
32
33 #include "subd_split.h"
34 #include "subd_patch_table.h"
35
36 #include "util_foreach.h"
37 #include "util_logging.h"
38 #include "util_progress.h"
39 #include "util_set.h"
40
41 CCL_NAMESPACE_BEGIN
42
43 /* Triangle */
44
45 void Mesh::Triangle::bounds_grow(const float3 *verts, BoundBox& bounds) const
46 {
47         bounds.grow(verts[v[0]]);
48         bounds.grow(verts[v[1]]);
49         bounds.grow(verts[v[2]]);
50 }
51
52 /* Curve */
53
54 void Mesh::Curve::bounds_grow(const int k, const float3 *curve_keys, const float *curve_radius, BoundBox& bounds) const
55 {
56         float3 P[4];
57
58         P[0] = curve_keys[max(first_key + k - 1,first_key)];
59         P[1] = curve_keys[first_key + k];
60         P[2] = curve_keys[first_key + k + 1];
61         P[3] = curve_keys[min(first_key + k + 2, first_key + num_keys - 1)];
62
63         float3 lower;
64         float3 upper;
65
66         curvebounds(&lower.x, &upper.x, P, 0);
67         curvebounds(&lower.y, &upper.y, P, 1);
68         curvebounds(&lower.z, &upper.z, P, 2);
69
70         float mr = max(curve_radius[first_key + k], curve_radius[first_key + k + 1]);
71
72         bounds.grow(lower, mr);
73         bounds.grow(upper, mr);
74 }
75
76 void Mesh::Curve::bounds_grow(const int k,
77                               const float3 *curve_keys,
78                               const float *curve_radius,
79                               const Transform& aligned_space,
80                               BoundBox& bounds) const
81 {
82         float3 P[4];
83
84         P[0] = curve_keys[max(first_key + k - 1,first_key)];
85         P[1] = curve_keys[first_key + k];
86         P[2] = curve_keys[first_key + k + 1];
87         P[3] = curve_keys[min(first_key + k + 2, first_key + num_keys - 1)];
88
89         P[0] = transform_point(&aligned_space, P[0]);
90         P[1] = transform_point(&aligned_space, P[1]);
91         P[2] = transform_point(&aligned_space, P[2]);
92         P[3] = transform_point(&aligned_space, P[3]);
93
94         float3 lower;
95         float3 upper;
96
97         curvebounds(&lower.x, &upper.x, P, 0);
98         curvebounds(&lower.y, &upper.y, P, 1);
99         curvebounds(&lower.z, &upper.z, P, 2);
100
101         float mr = max(curve_radius[first_key + k], curve_radius[first_key + k + 1]);
102
103         bounds.grow(lower, mr);
104         bounds.grow(upper, mr);
105 }
106
107 /* SubdFace */
108
109 float3 Mesh::SubdFace::normal(const Mesh *mesh) const
110 {
111         float3 v0 = mesh->verts[mesh->subd_face_corners[start_corner+0]];
112         float3 v1 = mesh->verts[mesh->subd_face_corners[start_corner+1]];
113         float3 v2 = mesh->verts[mesh->subd_face_corners[start_corner+2]];
114
115         return safe_normalize(cross(v1 - v0, v2 - v0));
116 }
117
118 /* Mesh */
119
120 NODE_DEFINE(Mesh)
121 {
122         NodeType* type = NodeType::add("mesh", create);
123
124         SOCKET_UINT(motion_steps, "Motion Steps", 3);
125         SOCKET_BOOLEAN(use_motion_blur, "Use Motion Blur", false);
126
127         SOCKET_INT_ARRAY(triangles, "Triangles", array<int>());
128         SOCKET_POINT_ARRAY(verts, "Vertices", array<float3>());
129         SOCKET_INT_ARRAY(shader, "Shader", array<int>());
130         SOCKET_BOOLEAN_ARRAY(smooth, "Smooth", array<bool>());
131
132         SOCKET_POINT_ARRAY(curve_keys, "Curve Keys", array<float3>());
133         SOCKET_FLOAT_ARRAY(curve_radius, "Curve Radius", array<float>());
134         SOCKET_INT_ARRAY(curve_first_key, "Curve First Key", array<int>());
135         SOCKET_INT_ARRAY(curve_shader, "Curve Shader", array<int>());
136
137         return type;
138 }
139
140 Mesh::Mesh()
141 : Node(node_type)
142 {
143         need_update = true;
144         need_update_rebuild = false;
145         transform_applied = false;
146         transform_negative_scaled = false;
147         transform_normal = transform_identity();
148         bounds = BoundBox::empty;
149
150         bvh = NULL;
151
152         tri_offset = 0;
153         vert_offset = 0;
154
155         curve_offset = 0;
156         curvekey_offset = 0;
157
158         patch_offset = 0;
159         face_offset = 0;
160         corner_offset = 0;
161
162         num_subd_verts = 0;
163
164         attributes.triangle_mesh = this;
165         curve_attributes.curve_mesh = this;
166         subd_attributes.subd_mesh = this;
167
168         geometry_flags = GEOMETRY_NONE;
169
170         has_volume = false;
171         has_surface_bssrdf = false;
172
173         num_ngons = 0;
174
175         subdivision_type = SUBDIVISION_NONE;
176         subd_params = NULL;
177
178         patch_table = NULL;
179 }
180
181 Mesh::~Mesh()
182 {
183         delete bvh;
184         delete patch_table;
185         delete subd_params;
186 }
187
188 void Mesh::resize_mesh(int numverts, int numtris)
189 {
190         verts.resize(numverts);
191         triangles.resize(numtris * 3);
192         shader.resize(numtris);
193         smooth.resize(numtris);
194
195         if(subd_faces.size()) {
196                 triangle_patch.resize(numtris);
197                 vert_patch_uv.resize(numverts);
198         }
199
200         attributes.resize();
201 }
202
203 void Mesh::reserve_mesh(int numverts, int numtris)
204 {
205         /* reserve space to add verts and triangles later */
206         verts.reserve(numverts);
207         triangles.reserve(numtris * 3);
208         shader.reserve(numtris);
209         smooth.reserve(numtris);
210
211         if(subd_faces.size()) {
212                 triangle_patch.reserve(numtris);
213                 vert_patch_uv.reserve(numverts);
214         }
215
216         attributes.resize(true);
217 }
218
219 void Mesh::resize_curves(int numcurves, int numkeys)
220 {
221         curve_keys.resize(numkeys);
222         curve_radius.resize(numkeys);
223         curve_first_key.resize(numcurves);
224         curve_shader.resize(numcurves);
225
226         curve_attributes.resize();
227 }
228
229 void Mesh::reserve_curves(int numcurves, int numkeys)
230 {
231         curve_keys.reserve(numkeys);
232         curve_radius.reserve(numkeys);
233         curve_first_key.reserve(numcurves);
234         curve_shader.reserve(numcurves);
235
236         curve_attributes.resize(true);
237 }
238
239 void Mesh::resize_subd_faces(int numfaces, int num_ngons_, int numcorners)
240 {
241         subd_faces.resize(numfaces);
242         subd_face_corners.resize(numcorners);
243         num_ngons = num_ngons_;
244
245         subd_attributes.resize();
246 }
247
248 void Mesh::reserve_subd_faces(int numfaces, int num_ngons_, int numcorners)
249 {
250         subd_faces.reserve(numfaces);
251         subd_face_corners.reserve(numcorners);
252         num_ngons = num_ngons_;
253
254         subd_attributes.resize(true);
255 }
256
257 void Mesh::clear()
258 {
259         /* clear all verts and triangles */
260         verts.clear();
261         triangles.clear();
262         shader.clear();
263         smooth.clear();
264
265         triangle_patch.clear();
266         vert_patch_uv.clear();
267
268         curve_keys.clear();
269         curve_radius.clear();
270         curve_first_key.clear();
271         curve_shader.clear();
272
273         subd_faces.clear();
274         subd_face_corners.clear();
275
276         num_subd_verts = 0;
277
278         subd_creases.clear();
279
280         attributes.clear();
281         curve_attributes.clear();
282         subd_attributes.clear();
283         used_shaders.clear();
284
285         transform_applied = false;
286         transform_negative_scaled = false;
287         transform_normal = transform_identity();
288         geometry_flags = GEOMETRY_NONE;
289
290         delete patch_table;
291         patch_table = NULL;
292 }
293
294 int Mesh::split_vertex(int vertex)
295 {
296         /* copy vertex location and vertex attributes */
297         add_vertex_slow(verts[vertex]);
298
299         foreach(Attribute& attr, attributes.attributes) {
300                 if(attr.element == ATTR_ELEMENT_VERTEX) {
301                         array<char> tmp(attr.data_sizeof());
302                         memcpy(tmp.data(), attr.data() + tmp.size()*vertex, tmp.size());
303                         attr.add(tmp.data());
304                 }
305         }
306
307         foreach(Attribute& attr, subd_attributes.attributes) {
308                 if(attr.element == ATTR_ELEMENT_VERTEX) {
309                         array<char> tmp(attr.data_sizeof());
310                         memcpy(tmp.data(), attr.data() + tmp.size()*vertex, tmp.size());
311                         attr.add(tmp.data());
312                 }
313         }
314
315         return verts.size() - 1;
316 }
317
318 void Mesh::add_vertex(float3 P)
319 {
320         verts.push_back_reserved(P);
321
322         if(subd_faces.size()) {
323                 vert_patch_uv.push_back_reserved(make_float2(0.0f, 0.0f));
324         }
325 }
326
327 void Mesh::add_vertex_slow(float3 P)
328 {
329         verts.push_back_slow(P);
330
331         if(subd_faces.size()) {
332                 vert_patch_uv.push_back_slow(make_float2(0.0f, 0.0f));
333         }
334 }
335
336 void Mesh::add_triangle(int v0, int v1, int v2, int shader_, bool smooth_)
337 {
338         triangles.push_back_reserved(v0);
339         triangles.push_back_reserved(v1);
340         triangles.push_back_reserved(v2);
341         shader.push_back_reserved(shader_);
342         smooth.push_back_reserved(smooth_);
343
344         if(subd_faces.size()) {
345                 triangle_patch.push_back_reserved(-1);
346         }
347 }
348
349 void Mesh::add_curve_key(float3 co, float radius)
350 {
351         curve_keys.push_back_reserved(co);
352         curve_radius.push_back_reserved(radius);
353 }
354
355 void Mesh::add_curve(int first_key, int shader)
356 {
357         curve_first_key.push_back_reserved(first_key);
358         curve_shader.push_back_reserved(shader);
359 }
360
361 void Mesh::add_subd_face(int* corners, int num_corners, int shader_, bool smooth_)
362 {
363         int start_corner = subd_face_corners.size();
364
365         for(int i = 0; i < num_corners; i++) {
366                 subd_face_corners.push_back_reserved(corners[i]);
367         }
368
369         int ptex_offset = 0;
370
371         if(subd_faces.size()) {
372                 SubdFace& s = subd_faces[subd_faces.size()-1];
373                 ptex_offset = s.ptex_offset + s.num_ptex_faces();
374         }
375
376         SubdFace face = {start_corner, num_corners, shader_, smooth_, ptex_offset};
377         subd_faces.push_back_reserved(face);
378 }
379
380 void Mesh::compute_bounds()
381 {
382         BoundBox bnds = BoundBox::empty;
383         size_t verts_size = verts.size();
384         size_t curve_keys_size = curve_keys.size();
385
386         if(verts_size + curve_keys_size > 0) {
387                 for(size_t i = 0; i < verts_size; i++)
388                         bnds.grow(verts[i]);
389
390                 for(size_t i = 0; i < curve_keys_size; i++)
391                         bnds.grow(curve_keys[i], curve_radius[i]);
392
393                 Attribute *attr = attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
394                 if(use_motion_blur && attr) {
395                         size_t steps_size = verts.size() * (motion_steps - 1);
396                         float3 *vert_steps = attr->data_float3();
397         
398                         for(size_t i = 0; i < steps_size; i++)
399                                 bnds.grow(vert_steps[i]);
400                 }
401
402                 Attribute *curve_attr = curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
403                 if(use_motion_blur && curve_attr) {
404                         size_t steps_size = curve_keys.size() * (motion_steps - 1);
405                         float3 *key_steps = curve_attr->data_float3();
406         
407                         for(size_t i = 0; i < steps_size; i++)
408                                 bnds.grow(key_steps[i]);
409                 }
410
411                 if(!bnds.valid()) {
412                         bnds = BoundBox::empty;
413
414                         /* skip nan or inf coordinates */
415                         for(size_t i = 0; i < verts_size; i++)
416                                 bnds.grow_safe(verts[i]);
417
418                         for(size_t i = 0; i < curve_keys_size; i++)
419                                 bnds.grow_safe(curve_keys[i], curve_radius[i]);
420                         
421                         if(use_motion_blur && attr) {
422                                 size_t steps_size = verts.size() * (motion_steps - 1);
423                                 float3 *vert_steps = attr->data_float3();
424                 
425                                 for(size_t i = 0; i < steps_size; i++)
426                                         bnds.grow_safe(vert_steps[i]);
427                         }
428
429                         if(use_motion_blur && curve_attr) {
430                                 size_t steps_size = curve_keys.size() * (motion_steps - 1);
431                                 float3 *key_steps = curve_attr->data_float3();
432                 
433                                 for(size_t i = 0; i < steps_size; i++)
434                                         bnds.grow_safe(key_steps[i]);
435                         }
436                 }
437         }
438
439         if(!bnds.valid()) {
440                 /* empty mesh */
441                 bnds.grow(make_float3(0.0f, 0.0f, 0.0f));
442         }
443
444         bounds = bnds;
445 }
446
447 static float3 compute_face_normal(const Mesh::Triangle& t, float3 *verts)
448 {
449         float3 v0 = verts[t.v[0]];
450         float3 v1 = verts[t.v[1]];
451         float3 v2 = verts[t.v[2]];
452
453         float3 norm = cross(v1 - v0, v2 - v0);
454         float normlen = len(norm);
455
456         if(normlen == 0.0f)
457                 return make_float3(1.0f, 0.0f, 0.0f);
458
459         return norm / normlen;
460 }
461
462 void Mesh::add_face_normals()
463 {
464         /* don't compute if already there */
465         if(attributes.find(ATTR_STD_FACE_NORMAL))
466                 return;
467         
468         /* get attributes */
469         Attribute *attr_fN = attributes.add(ATTR_STD_FACE_NORMAL);
470         float3 *fN = attr_fN->data_float3();
471
472         /* compute face normals */
473         size_t triangles_size = num_triangles();
474         bool flip = transform_negative_scaled;
475
476         if(triangles_size) {
477                 float3 *verts_ptr = verts.data();
478
479                 for(size_t i = 0; i < triangles_size; i++) {
480                         fN[i] = compute_face_normal(get_triangle(i), verts_ptr);
481
482                         if(flip)
483                                 fN[i] = -fN[i];
484                 }
485         }
486
487         /* expected to be in local space */
488         if(transform_applied) {
489                 Transform ntfm = transform_inverse(transform_normal);
490
491                 for(size_t i = 0; i < triangles_size; i++)
492                         fN[i] = normalize(transform_direction(&ntfm, fN[i]));
493         }
494 }
495
496 void Mesh::add_vertex_normals()
497 {
498         bool flip = transform_negative_scaled;
499         size_t verts_size = verts.size();
500         size_t triangles_size = num_triangles();
501
502         /* static vertex normals */
503         if(!attributes.find(ATTR_STD_VERTEX_NORMAL) && triangles_size) {
504                 /* get attributes */
505                 Attribute *attr_fN = attributes.find(ATTR_STD_FACE_NORMAL);
506                 Attribute *attr_vN = attributes.add(ATTR_STD_VERTEX_NORMAL);
507
508                 float3 *fN = attr_fN->data_float3();
509                 float3 *vN = attr_vN->data_float3();
510
511                 /* compute vertex normals */
512                 memset(vN, 0, verts.size()*sizeof(float3));
513
514                 if(triangles_size) {
515
516                         for(size_t i = 0; i < triangles_size; i++)
517                                 for(size_t j = 0; j < 3; j++)
518                                         vN[get_triangle(i).v[j]] += fN[i];
519                 }
520
521                 for(size_t i = 0; i < verts_size; i++) {
522                         vN[i] = normalize(vN[i]);
523                         if(flip)
524                                 vN[i] = -vN[i];
525                 }
526         }
527
528         /* motion vertex normals */
529         Attribute *attr_mP = attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
530         Attribute *attr_mN = attributes.find(ATTR_STD_MOTION_VERTEX_NORMAL);
531
532         if(has_motion_blur() && attr_mP && !attr_mN && triangles_size) {
533                 /* create attribute */
534                 attr_mN = attributes.add(ATTR_STD_MOTION_VERTEX_NORMAL);
535
536                 for(int step = 0; step < motion_steps - 1; step++) {
537                         float3 *mP = attr_mP->data_float3() + step*verts.size();
538                         float3 *mN = attr_mN->data_float3() + step*verts.size();
539
540                         /* compute */
541                         memset(mN, 0, verts.size()*sizeof(float3));
542
543                         if(triangles_size) {
544                                 for(size_t i = 0; i < triangles_size; i++) {
545                                         for(size_t j = 0; j < 3; j++) {
546                                                 float3 fN = compute_face_normal(get_triangle(i), mP);
547                                                 mN[get_triangle(i).v[j]] += fN;
548                                         }
549                                 }
550                         }
551
552                         for(size_t i = 0; i < verts_size; i++) {
553                                 mN[i] = normalize(mN[i]);
554                                 if(flip)
555                                         mN[i] = -mN[i];
556                         }
557                 }
558         }
559
560         /* subd vertex normals */
561         if(!subd_attributes.find(ATTR_STD_VERTEX_NORMAL) && subd_faces.size()) {
562                 /* get attributes */
563                 Attribute *attr_vN = subd_attributes.add(ATTR_STD_VERTEX_NORMAL);
564                 float3 *vN = attr_vN->data_float3();
565
566                 /* compute vertex normals */
567                 memset(vN, 0, verts.size()*sizeof(float3));
568
569                 for(size_t i = 0; i < subd_faces.size(); i++) {
570                         SubdFace& face = subd_faces[i];
571
572                         for(size_t j = 0; j < face.num_corners; j++) {
573                                 size_t corner = subd_face_corners[face.start_corner+j];
574                                 vN[corner] += verts[corner];
575                         }
576                 }
577
578                 for(size_t i = 0; i < verts_size; i++) {
579                         vN[i] = normalize(vN[i]);
580                         if(flip) {
581                                 vN[i] = -vN[i];
582                         }
583                 }
584         }
585 }
586
587 void Mesh::pack_normals(Scene *scene, uint *tri_shader, float4 *vnormal)
588 {
589         Attribute *attr_vN = attributes.find(ATTR_STD_VERTEX_NORMAL);
590         if(attr_vN == NULL) {
591                 /* Happens on objects with just hair. */
592                 return;
593         }
594
595         float3 *vN = attr_vN->data_float3();
596         uint shader_id = 0;
597         uint last_shader = -1;
598         bool last_smooth = false;
599
600         size_t triangles_size = num_triangles();
601         int *shader_ptr = shader.data();
602
603         bool do_transform = transform_applied;
604         Transform ntfm = transform_normal;
605
606         /* save shader */
607         for(size_t i = 0; i < triangles_size; i++) {
608                 if(shader_ptr[i] != last_shader || last_smooth != smooth[i]) {
609                         last_shader = shader_ptr[i];
610                         last_smooth = smooth[i];
611                         Shader *shader = (last_shader < used_shaders.size()) ?
612                                 used_shaders[last_shader] : scene->default_surface;
613                         shader_id = scene->shader_manager->get_shader_id(shader, this, last_smooth);
614                 }
615
616                 tri_shader[i] = shader_id;
617         }
618
619         size_t verts_size = verts.size();
620
621         for(size_t i = 0; i < verts_size; i++) {
622                 float3 vNi = vN[i];
623
624                 if(do_transform)
625                         vNi = normalize(transform_direction(&ntfm, vNi));
626
627                 vnormal[i] = make_float4(vNi.x, vNi.y, vNi.z, 0.0f);
628         }
629 }
630
631 void Mesh::pack_verts(const vector<uint>& tri_prim_index,
632                       uint4 *tri_vindex,
633                       uint *tri_patch,
634                       float2 *tri_patch_uv,
635                       size_t vert_offset,
636                       size_t tri_offset)
637 {
638         size_t verts_size = verts.size();
639
640         if(verts_size && subd_faces.size()) {
641                 float2 *vert_patch_uv_ptr = vert_patch_uv.data();
642
643                 for(size_t i = 0; i < verts_size; i++) {
644                         tri_patch_uv[i] = vert_patch_uv_ptr[i];
645                 }
646         }
647
648         size_t triangles_size = num_triangles();
649
650         if(triangles_size) {
651                 for(size_t i = 0; i < triangles_size; i++) {
652                         Triangle t = get_triangle(i);
653                         tri_vindex[i] = make_uint4(t.v[0] + vert_offset,
654                                                    t.v[1] + vert_offset,
655                                                    t.v[2] + vert_offset,
656                                                    tri_prim_index[i + tri_offset]);
657
658                         tri_patch[i] = (!subd_faces.size()) ? -1 : (triangle_patch[i]*8 + patch_offset);
659                 }
660         }
661 }
662
663 void Mesh::pack_curves(Scene *scene, float4 *curve_key_co, float4 *curve_data, size_t curvekey_offset)
664 {
665         size_t curve_keys_size = curve_keys.size();
666
667         /* pack curve keys */
668         if(curve_keys_size) {
669                 float3 *keys_ptr = curve_keys.data();
670                 float *radius_ptr = curve_radius.data();
671
672                 for(size_t i = 0; i < curve_keys_size; i++)
673                         curve_key_co[i] = make_float4(keys_ptr[i].x, keys_ptr[i].y, keys_ptr[i].z, radius_ptr[i]);
674         }
675
676         /* pack curve segments */
677         size_t curve_num = num_curves();
678
679         if(curve_num) {
680                 for(size_t i = 0; i < curve_num; i++) {
681                         Curve curve = get_curve(i);
682                         int shader_id = curve_shader[i];
683                         Shader *shader = (shader_id < used_shaders.size()) ?
684                                 used_shaders[shader_id] : scene->default_surface;
685                         shader_id = scene->shader_manager->get_shader_id(shader, this, false);
686
687                         curve_data[i] = make_float4(
688                                 __int_as_float(curve.first_key + curvekey_offset),
689                                 __int_as_float(curve.num_keys),
690                                 __int_as_float(shader_id),
691                                 0.0f);
692                 }
693         }
694 }
695
696 void Mesh::pack_patches(uint *patch_data, uint vert_offset, uint face_offset, uint corner_offset)
697 {
698         size_t num_faces = subd_faces.size();
699         int ngons = 0;
700
701         if(num_faces) {
702                 for(size_t f = 0; f < num_faces; f++) {
703                         SubdFace face = subd_faces[f];
704
705                         if(face.is_quad()) {
706                                 int c[4];
707                                 memcpy(c, &subd_face_corners[face.start_corner], sizeof(int)*4);
708
709                                 *(patch_data++) = c[0] + vert_offset;
710                                 *(patch_data++) = c[1] + vert_offset;
711                                 *(patch_data++) = c[2] + vert_offset;
712                                 *(patch_data++) = c[3] + vert_offset;
713
714                                 *(patch_data++) = f+face_offset;
715                                 *(patch_data++) = face.num_corners;
716                                 *(patch_data++) = face.start_corner + corner_offset;
717                                 *(patch_data++) = 0;
718                         }
719                         else {
720                                 for(int i = 0; i < face.num_corners; i++) {
721                                         int c[4];
722                                         c[0] = subd_face_corners[face.start_corner + mod(i + 0, face.num_corners)];
723                                         c[1] = subd_face_corners[face.start_corner + mod(i + 1, face.num_corners)];
724                                         c[2] = verts.size() - num_subd_verts + ngons;
725                                         c[3] = subd_face_corners[face.start_corner + mod(i - 1, face.num_corners)];
726
727                                         *(patch_data++) = c[0] + vert_offset;
728                                         *(patch_data++) = c[1] + vert_offset;
729                                         *(patch_data++) = c[2] + vert_offset;
730                                         *(patch_data++) = c[3] + vert_offset;
731
732                                         *(patch_data++) = f+face_offset;
733                                         *(patch_data++) = face.num_corners | (i << 16);
734                                         *(patch_data++) = face.start_corner + corner_offset;
735                                         *(patch_data++) = subd_face_corners.size() + ngons + corner_offset;
736                                 }
737
738                                 ngons++;
739                         }
740                 }
741         }
742 }
743
744 void Mesh::compute_bvh(DeviceScene *dscene,
745                        SceneParams *params,
746                        Progress *progress,
747                        int n,
748                        int total)
749 {
750         if(progress->get_cancel())
751                 return;
752
753         compute_bounds();
754
755         if(need_build_bvh()) {
756                 string msg = "Updating Mesh BVH ";
757                 if(name == "")
758                         msg += string_printf("%u/%u", (uint)(n+1), (uint)total);
759                 else
760                         msg += string_printf("%s %u/%u", name.c_str(), (uint)(n+1), (uint)total);
761
762                 Object object;
763                 object.mesh = this;
764
765                 vector<Object*> objects;
766                 objects.push_back(&object);
767
768                 if(bvh && !need_update_rebuild) {
769                         progress->set_status(msg, "Refitting BVH");
770                         bvh->objects = objects;
771                         bvh->refit(*progress);
772                 }
773                 else {
774                         progress->set_status(msg, "Building BVH");
775
776                         BVHParams bparams;
777                         bparams.use_spatial_split = params->use_bvh_spatial_split;
778                         bparams.use_qbvh = params->use_qbvh;
779                         bparams.use_unaligned_nodes = dscene->data.bvh.have_curves &&
780                                                       params->use_bvh_unaligned_nodes;
781
782                         delete bvh;
783                         bvh = BVH::create(bparams, objects);
784                         MEM_GUARDED_CALL(progress, bvh->build, *progress);
785                 }
786         }
787
788         need_update = false;
789         need_update_rebuild = false;
790 }
791
792 void Mesh::tag_update(Scene *scene, bool rebuild)
793 {
794         need_update = true;
795
796         if(rebuild) {
797                 need_update_rebuild = true;
798                 scene->light_manager->need_update = true;
799         }
800         else {
801                 foreach(Shader *shader, used_shaders)
802                         if(shader->has_surface_emission)
803                                 scene->light_manager->need_update = true;
804         }
805
806         scene->mesh_manager->need_update = true;
807         scene->object_manager->need_update = true;
808 }
809
810 bool Mesh::has_motion_blur() const
811 {
812         return (use_motion_blur &&
813                 (attributes.find(ATTR_STD_MOTION_VERTEX_POSITION) ||
814                  curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION)));
815 }
816
817 bool Mesh::has_true_displacement() const
818 {
819         foreach(Shader *shader, used_shaders) {
820                 if(shader->has_displacement && shader->displacement_method != DISPLACE_BUMP) {
821                         return true;
822                 }
823         }
824
825         return false;
826 }
827
828 bool Mesh::need_build_bvh() const
829 {
830         return !transform_applied || has_surface_bssrdf;
831 }
832
833 bool Mesh::is_instanced() const
834 {
835         /* Currently we treat subsurface objects as instanced.
836          *
837          * While it might be not very optimal for ray traversal, it avoids having
838          * duplicated BVH in the memory, saving quite some space.
839          */
840         return !transform_applied || has_surface_bssrdf;
841 }
842
843 /* Mesh Manager */
844
845 MeshManager::MeshManager()
846 {
847         bvh = NULL;
848         need_update = true;
849         need_flags_update = true;
850 }
851
852 MeshManager::~MeshManager()
853 {
854         delete bvh;
855 }
856
857 void MeshManager::update_osl_attributes(Device *device, Scene *scene, vector<AttributeRequestSet>& mesh_attributes)
858 {
859 #ifdef WITH_OSL
860         /* for OSL, a hash map is used to lookup the attribute by name. */
861         OSLGlobals *og = (OSLGlobals*)device->osl_memory();
862
863         og->object_name_map.clear();
864         og->attribute_map.clear();
865         og->object_names.clear();
866
867         og->attribute_map.resize(scene->objects.size()*ATTR_PRIM_TYPES);
868
869         for(size_t i = 0; i < scene->objects.size(); i++) {
870                 /* set object name to object index map */
871                 Object *object = scene->objects[i];
872                 og->object_name_map[object->name] = i;
873                 og->object_names.push_back(object->name);
874
875                 /* set object attributes */
876                 foreach(ParamValue& attr, object->attributes) {
877                         OSLGlobals::Attribute osl_attr;
878
879                         osl_attr.type = attr.type();
880                         osl_attr.desc.element = ATTR_ELEMENT_OBJECT;
881                         osl_attr.value = attr;
882                         osl_attr.desc.offset = 0;
883                         osl_attr.desc.flags = 0;
884
885                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_TRIANGLE][attr.name()] = osl_attr;
886                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_CURVE][attr.name()] = osl_attr;
887                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_SUBD][attr.name()] = osl_attr;
888                 }
889
890                 /* find mesh attributes */
891                 size_t j;
892
893                 for(j = 0; j < scene->meshes.size(); j++)
894                         if(scene->meshes[j] == object->mesh)
895                                 break;
896
897                 AttributeRequestSet& attributes = mesh_attributes[j];
898
899                 /* set object attributes */
900                 foreach(AttributeRequest& req, attributes.requests) {
901                         OSLGlobals::Attribute osl_attr;
902
903                         if(req.triangle_desc.element != ATTR_ELEMENT_NONE) {
904                                 osl_attr.desc = req.triangle_desc;
905
906                                 if(req.triangle_type == TypeDesc::TypeFloat)
907                                         osl_attr.type = TypeDesc::TypeFloat;
908                                 else if(req.triangle_type == TypeDesc::TypeMatrix)
909                                         osl_attr.type = TypeDesc::TypeMatrix;
910                                 else
911                                         osl_attr.type = TypeDesc::TypeColor;
912
913                                 if(req.std != ATTR_STD_NONE) {
914                                         /* if standard attribute, add lookup by geom: name convention */
915                                         ustring stdname(string("geom:") + string(Attribute::standard_name(req.std)));
916                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_TRIANGLE][stdname] = osl_attr;
917                                 }
918                                 else if(req.name != ustring()) {
919                                         /* add lookup by mesh attribute name */
920                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_TRIANGLE][req.name] = osl_attr;
921                                 }
922                         }
923
924                         if(req.curve_desc.element != ATTR_ELEMENT_NONE) {
925                                 osl_attr.desc = req.curve_desc;
926
927                                 if(req.curve_type == TypeDesc::TypeFloat)
928                                         osl_attr.type = TypeDesc::TypeFloat;
929                                 else if(req.curve_type == TypeDesc::TypeMatrix)
930                                         osl_attr.type = TypeDesc::TypeMatrix;
931                                 else
932                                         osl_attr.type = TypeDesc::TypeColor;
933
934                                 if(req.std != ATTR_STD_NONE) {
935                                         /* if standard attribute, add lookup by geom: name convention */
936                                         ustring stdname(string("geom:") + string(Attribute::standard_name(req.std)));
937                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_CURVE][stdname] = osl_attr;
938                                 }
939                                 else if(req.name != ustring()) {
940                                         /* add lookup by mesh attribute name */
941                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_CURVE][req.name] = osl_attr;
942                                 }
943                         }
944
945                         if(req.subd_desc.element != ATTR_ELEMENT_NONE) {
946                                 osl_attr.desc = req.subd_desc;
947
948                                 if(req.subd_type == TypeDesc::TypeFloat)
949                                         osl_attr.type = TypeDesc::TypeFloat;
950                                 else if(req.subd_type == TypeDesc::TypeMatrix)
951                                         osl_attr.type = TypeDesc::TypeMatrix;
952                                 else
953                                         osl_attr.type = TypeDesc::TypeColor;
954
955                                 if(req.std != ATTR_STD_NONE) {
956                                         /* if standard attribute, add lookup by geom: name convention */
957                                         ustring stdname(string("geom:") + string(Attribute::standard_name(req.std)));
958                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_SUBD][stdname] = osl_attr;
959                                 }
960                                 else if(req.name != ustring()) {
961                                         /* add lookup by mesh attribute name */
962                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_SUBD][req.name] = osl_attr;
963                                 }
964                         }
965                 }
966         }
967 #else
968         (void)device;
969         (void)scene;
970         (void)mesh_attributes;
971 #endif
972 }
973
974 void MeshManager::update_svm_attributes(Device *device, DeviceScene *dscene, Scene *scene, vector<AttributeRequestSet>& mesh_attributes)
975 {
976         /* for SVM, the attributes_map table is used to lookup the offset of an
977          * attribute, based on a unique shader attribute id. */
978
979         /* compute array stride */
980         int attr_map_stride = 0;
981
982         for(size_t i = 0; i < scene->meshes.size(); i++)
983                 attr_map_stride = max(attr_map_stride, (mesh_attributes[i].size() + 1)*ATTR_PRIM_TYPES);
984
985         if(attr_map_stride == 0)
986                 return;
987         
988         /* create attribute map */
989         uint4 *attr_map = dscene->attributes_map.resize(attr_map_stride*scene->objects.size());
990         memset(attr_map, 0, dscene->attributes_map.size()*sizeof(uint));
991
992         for(size_t i = 0; i < scene->objects.size(); i++) {
993                 Object *object = scene->objects[i];
994                 Mesh *mesh = object->mesh;
995
996                 /* find mesh attributes */
997                 size_t j;
998
999                 for(j = 0; j < scene->meshes.size(); j++)
1000                         if(scene->meshes[j] == mesh)
1001                                 break;
1002
1003                 AttributeRequestSet& attributes = mesh_attributes[j];
1004
1005                 /* set object attributes */
1006                 int index = i*attr_map_stride;
1007
1008                 foreach(AttributeRequest& req, attributes.requests) {
1009                         uint id;
1010
1011                         if(req.std == ATTR_STD_NONE)
1012                                 id = scene->shader_manager->get_attribute_id(req.name);
1013                         else
1014                                 id = scene->shader_manager->get_attribute_id(req.std);
1015
1016                         if(mesh->num_triangles()) {
1017                                 attr_map[index].x = id;
1018                                 attr_map[index].y = req.triangle_desc.element;
1019                                 attr_map[index].z = as_uint(req.triangle_desc.offset);
1020
1021                                 if(req.triangle_type == TypeDesc::TypeFloat)
1022                                         attr_map[index].w = NODE_ATTR_FLOAT;
1023                                 else if(req.triangle_type == TypeDesc::TypeMatrix)
1024                                         attr_map[index].w = NODE_ATTR_MATRIX;
1025                                 else
1026                                         attr_map[index].w = NODE_ATTR_FLOAT3;
1027
1028                                 attr_map[index].w |= req.triangle_desc.flags << 8;
1029                         }
1030
1031                         index++;
1032
1033                         if(mesh->num_curves()) {
1034                                 attr_map[index].x = id;
1035                                 attr_map[index].y = req.curve_desc.element;
1036                                 attr_map[index].z = as_uint(req.curve_desc.offset);
1037
1038                                 if(req.curve_type == TypeDesc::TypeFloat)
1039                                         attr_map[index].w = NODE_ATTR_FLOAT;
1040                                 else if(req.curve_type == TypeDesc::TypeMatrix)
1041                                         attr_map[index].w = NODE_ATTR_MATRIX;
1042                                 else
1043                                         attr_map[index].w = NODE_ATTR_FLOAT3;
1044
1045                                 attr_map[index].w |= req.curve_desc.flags << 8;
1046                         }
1047
1048                         index++;
1049
1050                         if(mesh->subd_faces.size()) {
1051                                 attr_map[index].x = id;
1052                                 attr_map[index].y = req.subd_desc.element;
1053                                 attr_map[index].z = as_uint(req.subd_desc.offset);
1054
1055                                 if(req.subd_type == TypeDesc::TypeFloat)
1056                                         attr_map[index].w = NODE_ATTR_FLOAT;
1057                                 else if(req.subd_type == TypeDesc::TypeMatrix)
1058                                         attr_map[index].w = NODE_ATTR_MATRIX;
1059                                 else
1060                                         attr_map[index].w = NODE_ATTR_FLOAT3;
1061
1062                                 attr_map[index].w |= req.subd_desc.flags << 8;
1063                         }
1064
1065                         index++;
1066                 }
1067
1068                 /* terminator */
1069                 for(int i = 0; i < ATTR_PRIM_TYPES; i++) {
1070                         attr_map[index].x = ATTR_STD_NONE;
1071                         attr_map[index].y = 0;
1072                         attr_map[index].z = 0;
1073                         attr_map[index].w = 0;
1074
1075                         index++;
1076                 }
1077         }
1078
1079         /* copy to device */
1080         dscene->data.bvh.attributes_map_stride = attr_map_stride;
1081         device->tex_alloc("__attributes_map", dscene->attributes_map);
1082 }
1083
1084 static void update_attribute_element_size(Mesh *mesh,
1085                                           Attribute *mattr,
1086                                           AttributePrimitive prim,
1087                                           size_t *attr_float_size,
1088                                           size_t *attr_float3_size,
1089                                           size_t *attr_uchar4_size)
1090 {
1091         if(mattr) {
1092                 size_t size = mattr->element_size(mesh, prim);
1093
1094                 if(mattr->element == ATTR_ELEMENT_VOXEL) {
1095                         /* pass */
1096                 }
1097                 else if(mattr->element == ATTR_ELEMENT_CORNER_BYTE) {
1098                         *attr_uchar4_size += size;
1099                 }
1100                 else if(mattr->type == TypeDesc::TypeFloat) {
1101                         *attr_float_size += size;
1102                 }
1103                 else if(mattr->type == TypeDesc::TypeMatrix) {
1104                         *attr_float3_size += size * 4;
1105                 }
1106                 else {
1107                         *attr_float3_size += size;
1108                 }
1109         }
1110 }
1111
1112 static void update_attribute_element_offset(Mesh *mesh,
1113                                             vector<float>& attr_float,
1114                                             size_t& attr_float_offset,
1115                                             vector<float4>& attr_float3,
1116                                             size_t& attr_float3_offset,
1117                                             vector<uchar4>& attr_uchar4,
1118                                             size_t& attr_uchar4_offset,
1119                                             Attribute *mattr,
1120                                             AttributePrimitive prim,
1121                                             TypeDesc& type,
1122                                             AttributeDescriptor& desc)
1123 {
1124         if(mattr) {
1125                 /* store element and type */
1126                 desc.element = mattr->element;
1127                 desc.flags = mattr->flags;
1128                 type = mattr->type;
1129
1130                 /* store attribute data in arrays */
1131                 size_t size = mattr->element_size(mesh, prim);
1132
1133                 AttributeElement& element = desc.element;
1134                 int& offset = desc.offset;
1135
1136                 if(mattr->element == ATTR_ELEMENT_VOXEL) {
1137                         /* store slot in offset value */
1138                         VoxelAttribute *voxel_data = mattr->data_voxel();
1139                         offset = voxel_data->slot;
1140                 }
1141                 else if(mattr->element == ATTR_ELEMENT_CORNER_BYTE) {
1142                         uchar4 *data = mattr->data_uchar4();
1143                         offset = attr_uchar4_offset;
1144
1145                         assert(attr_uchar4.capacity() >= offset + size);
1146                         for(size_t k = 0; k < size; k++) {
1147                                 attr_uchar4[offset+k] = data[k];
1148                         }
1149                         attr_uchar4_offset += size;
1150                 }
1151                 else if(mattr->type == TypeDesc::TypeFloat) {
1152                         float *data = mattr->data_float();
1153                         offset = attr_float_offset;
1154
1155                         assert(attr_float.capacity() >= offset + size);
1156                         for(size_t k = 0; k < size; k++) {
1157                                 attr_float[offset+k] = data[k];
1158                         }
1159                         attr_float_offset += size;
1160                 }
1161                 else if(mattr->type == TypeDesc::TypeMatrix) {
1162                         Transform *tfm = mattr->data_transform();
1163                         offset = attr_float3_offset;
1164
1165                         assert(attr_float3.capacity() >= offset + size * 4);
1166                         for(size_t k = 0; k < size*4; k++) {
1167                                 attr_float3[offset+k] = (&tfm->x)[k];
1168                         }
1169                         attr_float3_offset += size * 4;
1170                 }
1171                 else {
1172                         float4 *data = mattr->data_float4();
1173                         offset = attr_float3_offset;
1174
1175                         assert(attr_float3.capacity() >= offset + size);
1176                         for(size_t k = 0; k < size; k++) {
1177                                 attr_float3[offset+k] = data[k];
1178                         }
1179                         attr_float3_offset += size;
1180                 }
1181
1182                 /* mesh vertex/curve index is global, not per object, so we sneak
1183                  * a correction for that in here */
1184                 if(mesh->subdivision_type == Mesh::SUBDIVISION_CATMULL_CLARK && desc.flags & ATTR_SUBDIVIDED) {
1185                         /* indices for subdivided attributes are retrieved
1186                          * from patch table so no need for correction here*/
1187                 }
1188                 else if(element == ATTR_ELEMENT_VERTEX)
1189                         offset -= mesh->vert_offset;
1190                 else if(element == ATTR_ELEMENT_VERTEX_MOTION)
1191                         offset -= mesh->vert_offset;
1192                 else if(element == ATTR_ELEMENT_FACE) {
1193                         if(prim == ATTR_PRIM_TRIANGLE)
1194                                 offset -= mesh->tri_offset;
1195                         else
1196                                 offset -= mesh->face_offset;
1197                 }
1198                 else if(element == ATTR_ELEMENT_CORNER || element == ATTR_ELEMENT_CORNER_BYTE) {
1199                         if(prim == ATTR_PRIM_TRIANGLE)
1200                                 offset -= 3*mesh->tri_offset;
1201                         else
1202                                 offset -= mesh->corner_offset;
1203                 }
1204                 else if(element == ATTR_ELEMENT_CURVE)
1205                         offset -= mesh->curve_offset;
1206                 else if(element == ATTR_ELEMENT_CURVE_KEY)
1207                         offset -= mesh->curvekey_offset;
1208                 else if(element == ATTR_ELEMENT_CURVE_KEY_MOTION)
1209                         offset -= mesh->curvekey_offset;
1210         }
1211         else {
1212                 /* attribute not found */
1213                 desc.element = ATTR_ELEMENT_NONE;
1214                 desc.offset = 0;
1215         }
1216 }
1217
1218 void MeshManager::device_update_attributes(Device *device, DeviceScene *dscene, Scene *scene, Progress& progress)
1219 {
1220         progress.set_status("Updating Mesh", "Computing attributes");
1221
1222         /* gather per mesh requested attributes. as meshes may have multiple
1223          * shaders assigned, this merges the requested attributes that have
1224          * been set per shader by the shader manager */
1225         vector<AttributeRequestSet> mesh_attributes(scene->meshes.size());
1226
1227         for(size_t i = 0; i < scene->meshes.size(); i++) {
1228                 Mesh *mesh = scene->meshes[i];
1229
1230                 scene->need_global_attributes(mesh_attributes[i]);
1231
1232                 foreach(Shader *shader, mesh->used_shaders) {
1233                         mesh_attributes[i].add(shader->attributes);
1234                 }
1235         }
1236
1237         /* mesh attribute are stored in a single array per data type. here we fill
1238          * those arrays, and set the offset and element type to create attribute
1239          * maps next */
1240
1241         /* Pre-allocate attributes to avoid arrays re-allocation which would
1242          * take 2x of overall attribute memory usage.
1243          */
1244         size_t attr_float_size = 0;
1245         size_t attr_float3_size = 0;
1246         size_t attr_uchar4_size = 0;
1247         for(size_t i = 0; i < scene->meshes.size(); i++) {
1248                 Mesh *mesh = scene->meshes[i];
1249                 AttributeRequestSet& attributes = mesh_attributes[i];
1250                 foreach(AttributeRequest& req, attributes.requests) {
1251                         Attribute *triangle_mattr = mesh->attributes.find(req);
1252                         Attribute *curve_mattr = mesh->curve_attributes.find(req);
1253                         Attribute *subd_mattr = mesh->subd_attributes.find(req);
1254
1255                         update_attribute_element_size(mesh,
1256                                                       triangle_mattr,
1257                                                       ATTR_PRIM_TRIANGLE,
1258                                                       &attr_float_size,
1259                                                       &attr_float3_size,
1260                                                       &attr_uchar4_size);
1261                         update_attribute_element_size(mesh,
1262                                                       curve_mattr,
1263                                                       ATTR_PRIM_CURVE,
1264                                                       &attr_float_size,
1265                                                       &attr_float3_size,
1266                                                       &attr_uchar4_size);
1267                         update_attribute_element_size(mesh,
1268                                                       subd_mattr,
1269                                                       ATTR_PRIM_SUBD,
1270                                                       &attr_float_size,
1271                                                       &attr_float3_size,
1272                                                       &attr_uchar4_size);
1273                 }
1274         }
1275
1276         vector<float> attr_float(attr_float_size);
1277         vector<float4> attr_float3(attr_float3_size);
1278         vector<uchar4> attr_uchar4(attr_uchar4_size);
1279
1280         size_t attr_float_offset = 0;
1281         size_t attr_float3_offset = 0;
1282         size_t attr_uchar4_offset = 0;
1283
1284         /* Fill in attributes. */
1285         for(size_t i = 0; i < scene->meshes.size(); i++) {
1286                 Mesh *mesh = scene->meshes[i];
1287                 AttributeRequestSet& attributes = mesh_attributes[i];
1288
1289                 /* todo: we now store std and name attributes from requests even if
1290                  * they actually refer to the same mesh attributes, optimize */
1291                 foreach(AttributeRequest& req, attributes.requests) {
1292                         Attribute *triangle_mattr = mesh->attributes.find(req);
1293                         Attribute *curve_mattr = mesh->curve_attributes.find(req);
1294                         Attribute *subd_mattr = mesh->subd_attributes.find(req);
1295
1296                         update_attribute_element_offset(mesh,
1297                                                         attr_float, attr_float_offset,
1298                                                         attr_float3, attr_float3_offset,
1299                                                         attr_uchar4, attr_uchar4_offset,
1300                                                         triangle_mattr,
1301                                                         ATTR_PRIM_TRIANGLE,
1302                                                         req.triangle_type,
1303                                                         req.triangle_desc);
1304
1305                         update_attribute_element_offset(mesh,
1306                                                         attr_float, attr_float_offset,
1307                                                         attr_float3, attr_float3_offset,
1308                                                         attr_uchar4, attr_uchar4_offset,
1309                                                         curve_mattr,
1310                                                         ATTR_PRIM_CURVE,
1311                                                         req.curve_type,
1312                                                         req.curve_desc);
1313
1314                         update_attribute_element_offset(mesh,
1315                                                         attr_float, attr_float_offset,
1316                                                         attr_float3, attr_float3_offset,
1317                                                         attr_uchar4, attr_uchar4_offset,
1318                                                         subd_mattr,
1319                                                         ATTR_PRIM_SUBD,
1320                                                         req.subd_type,
1321                                                         req.subd_desc);
1322
1323                         if(progress.get_cancel()) return;
1324                 }
1325         }
1326
1327         /* create attribute lookup maps */
1328         if(scene->shader_manager->use_osl())
1329                 update_osl_attributes(device, scene, mesh_attributes);
1330
1331         update_svm_attributes(device, dscene, scene, mesh_attributes);
1332
1333         if(progress.get_cancel()) return;
1334
1335         /* copy to device */
1336         progress.set_status("Updating Mesh", "Copying Attributes to device");
1337
1338         if(attr_float.size()) {
1339                 dscene->attributes_float.copy(&attr_float[0], attr_float.size());
1340                 device->tex_alloc("__attributes_float", dscene->attributes_float);
1341         }
1342         if(attr_float3.size()) {
1343                 dscene->attributes_float3.copy(&attr_float3[0], attr_float3.size());
1344                 device->tex_alloc("__attributes_float3", dscene->attributes_float3);
1345         }
1346         if(attr_uchar4.size()) {
1347                 dscene->attributes_uchar4.copy(&attr_uchar4[0], attr_uchar4.size());
1348                 device->tex_alloc("__attributes_uchar4", dscene->attributes_uchar4);
1349         }
1350 }
1351
1352 void MeshManager::mesh_calc_offset(Scene *scene)
1353 {
1354         size_t vert_size = 0;
1355         size_t tri_size = 0;
1356
1357         size_t curve_key_size = 0;
1358         size_t curve_size = 0;
1359
1360         size_t patch_size = 0;
1361         size_t face_size = 0;
1362         size_t corner_size = 0;
1363
1364         foreach(Mesh *mesh, scene->meshes) {
1365                 mesh->vert_offset = vert_size;
1366                 mesh->tri_offset = tri_size;
1367
1368                 mesh->curvekey_offset = curve_key_size;
1369                 mesh->curve_offset = curve_size;
1370
1371                 mesh->patch_offset = patch_size;
1372                 mesh->face_offset = face_size;
1373                 mesh->corner_offset = corner_size;
1374
1375                 vert_size += mesh->verts.size();
1376                 tri_size += mesh->num_triangles();
1377
1378                 curve_key_size += mesh->curve_keys.size();
1379                 curve_size += mesh->num_curves();
1380
1381                 if(mesh->subd_faces.size()) {
1382                         Mesh::SubdFace& last = mesh->subd_faces[mesh->subd_faces.size()-1];
1383                         patch_size += (last.ptex_offset + last.num_ptex_faces()) * 8;
1384
1385                         /* patch tables are stored in same array so include them in patch_size */
1386                         if(mesh->patch_table) {
1387                                 mesh->patch_table_offset = patch_size;
1388                                 patch_size += mesh->patch_table->total_size();
1389                         }
1390                 }
1391                 face_size += mesh->subd_faces.size();
1392                 corner_size += mesh->subd_face_corners.size();
1393         }
1394 }
1395
1396 void MeshManager::device_update_mesh(Device *device,
1397                                      DeviceScene *dscene,
1398                                      Scene *scene,
1399                                      bool for_displacement,
1400                                      Progress& progress)
1401 {
1402         /* Count. */
1403         size_t vert_size = 0;
1404         size_t tri_size = 0;
1405
1406         size_t curve_key_size = 0;
1407         size_t curve_size = 0;
1408
1409         size_t patch_size = 0;
1410
1411         foreach(Mesh *mesh, scene->meshes) {
1412                 vert_size += mesh->verts.size();
1413                 tri_size += mesh->num_triangles();
1414
1415                 curve_key_size += mesh->curve_keys.size();
1416                 curve_size += mesh->num_curves();
1417
1418                 if(mesh->subd_faces.size()) {
1419                         Mesh::SubdFace& last = mesh->subd_faces[mesh->subd_faces.size()-1];
1420                         patch_size += (last.ptex_offset + last.num_ptex_faces()) * 8;
1421
1422                         /* patch tables are stored in same array so include them in patch_size */
1423                         if(mesh->patch_table) {
1424                                 mesh->patch_table_offset = patch_size;
1425                                 patch_size += mesh->patch_table->total_size();
1426                         }
1427                 }
1428         }
1429
1430         /* Create mapping from triangle to primitive triangle array. */
1431         vector<uint> tri_prim_index(tri_size);
1432         if(for_displacement) {
1433                 /* For displacement kernels we do some trickery to make them believe
1434                  * we've got all required data ready. However, that data is different
1435                  * from final render kernels since we don't have BVH yet, so can't
1436                  * really use same semantic of arrays.
1437                  */
1438                 foreach(Mesh *mesh, scene->meshes) {
1439                         for(size_t i = 0; i < mesh->num_triangles(); ++i) {
1440                                 tri_prim_index[i + mesh->tri_offset] = 3 * (i + mesh->tri_offset);
1441                         }
1442                 }
1443         }
1444         else {
1445                 PackedBVH& pack = bvh->pack;
1446                 for(size_t i = 0; i < pack.prim_index.size(); ++i) {
1447                         if ((pack.prim_type[i] & PRIMITIVE_ALL_TRIANGLE) != 0) {
1448                                 tri_prim_index[pack.prim_index[i]] = pack.prim_tri_index[i];
1449                         }
1450                 }
1451         }
1452
1453         /* Fill in all the arrays. */
1454         if(tri_size != 0) {
1455                 /* normals */
1456                 progress.set_status("Updating Mesh", "Computing normals");
1457
1458                 uint *tri_shader = dscene->tri_shader.resize(tri_size);
1459                 float4 *vnormal = dscene->tri_vnormal.resize(vert_size);
1460                 uint4 *tri_vindex = dscene->tri_vindex.resize(tri_size);
1461                 uint *tri_patch = dscene->tri_patch.resize(tri_size);
1462                 float2 *tri_patch_uv = dscene->tri_patch_uv.resize(vert_size);
1463
1464                 foreach(Mesh *mesh, scene->meshes) {
1465                         mesh->pack_normals(scene,
1466                                            &tri_shader[mesh->tri_offset],
1467                                            &vnormal[mesh->vert_offset]);
1468                         mesh->pack_verts(tri_prim_index,
1469                                          &tri_vindex[mesh->tri_offset],
1470                                          &tri_patch[mesh->tri_offset],
1471                                          &tri_patch_uv[mesh->vert_offset],
1472                                          mesh->vert_offset,
1473                                          mesh->tri_offset);
1474                         if(progress.get_cancel()) return;
1475                 }
1476
1477                 /* vertex coordinates */
1478                 progress.set_status("Updating Mesh", "Copying Mesh to device");
1479
1480                 device->tex_alloc("__tri_shader", dscene->tri_shader);
1481                 device->tex_alloc("__tri_vnormal", dscene->tri_vnormal);
1482                 device->tex_alloc("__tri_vindex", dscene->tri_vindex);
1483                 device->tex_alloc("__tri_patch", dscene->tri_patch);
1484                 device->tex_alloc("__tri_patch_uv", dscene->tri_patch_uv);
1485         }
1486
1487         if(curve_size != 0) {
1488                 progress.set_status("Updating Mesh", "Copying Strands to device");
1489
1490                 float4 *curve_keys = dscene->curve_keys.resize(curve_key_size);
1491                 float4 *curves = dscene->curves.resize(curve_size);
1492
1493                 foreach(Mesh *mesh, scene->meshes) {
1494                         mesh->pack_curves(scene, &curve_keys[mesh->curvekey_offset], &curves[mesh->curve_offset], mesh->curvekey_offset);
1495                         if(progress.get_cancel()) return;
1496                 }
1497
1498                 device->tex_alloc("__curve_keys", dscene->curve_keys);
1499                 device->tex_alloc("__curves", dscene->curves);
1500         }
1501
1502         if(patch_size != 0) {
1503                 progress.set_status("Updating Mesh", "Copying Patches to device");
1504
1505                 uint *patch_data = dscene->patches.resize(patch_size);
1506
1507                 foreach(Mesh *mesh, scene->meshes) {
1508                         mesh->pack_patches(&patch_data[mesh->patch_offset], mesh->vert_offset, mesh->face_offset, mesh->corner_offset);
1509
1510                         if(mesh->patch_table) {
1511                                 mesh->patch_table->copy_adjusting_offsets(&patch_data[mesh->patch_table_offset], mesh->patch_table_offset);
1512                         }
1513
1514                         if(progress.get_cancel()) return;
1515                 }
1516
1517                 device->tex_alloc("__patches", dscene->patches);
1518         }
1519
1520         if(for_displacement) {
1521                 float4 *prim_tri_verts = dscene->prim_tri_verts.resize(tri_size * 3);
1522                 foreach(Mesh *mesh, scene->meshes) {
1523                         for(size_t i = 0; i < mesh->num_triangles(); ++i) {
1524                                 Mesh::Triangle t = mesh->get_triangle(i);
1525                                 size_t offset = 3 * (i + mesh->tri_offset);
1526                                 prim_tri_verts[offset + 0] = float3_to_float4(mesh->verts[t.v[0]]);
1527                                 prim_tri_verts[offset + 1] = float3_to_float4(mesh->verts[t.v[1]]);
1528                                 prim_tri_verts[offset + 2] = float3_to_float4(mesh->verts[t.v[2]]);
1529                         }
1530                 }
1531                 device->tex_alloc("__prim_tri_verts", dscene->prim_tri_verts);
1532         }
1533 }
1534
1535 void MeshManager::device_update_bvh(Device *device, DeviceScene *dscene, Scene *scene, Progress& progress)
1536 {
1537         /* bvh build */
1538         progress.set_status("Updating Scene BVH", "Building");
1539
1540         VLOG(1) << (scene->params.use_qbvh ? "Using QBVH optimization structure"
1541                                            : "Using regular BVH optimization structure");
1542
1543         BVHParams bparams;
1544         bparams.top_level = true;
1545         bparams.use_qbvh = scene->params.use_qbvh;
1546         bparams.use_spatial_split = scene->params.use_bvh_spatial_split;
1547         bparams.use_unaligned_nodes = dscene->data.bvh.have_curves &&
1548                                       scene->params.use_bvh_unaligned_nodes;
1549
1550         delete bvh;
1551         bvh = BVH::create(bparams, scene->objects);
1552         bvh->build(progress);
1553
1554         if(progress.get_cancel()) return;
1555
1556         /* copy to device */
1557         progress.set_status("Updating Scene BVH", "Copying BVH to device");
1558
1559         PackedBVH& pack = bvh->pack;
1560
1561         if(pack.nodes.size()) {
1562                 dscene->bvh_nodes.reference((float4*)&pack.nodes[0], pack.nodes.size());
1563                 device->tex_alloc("__bvh_nodes", dscene->bvh_nodes);
1564         }
1565         if(pack.leaf_nodes.size()) {
1566                 dscene->bvh_leaf_nodes.reference((float4*)&pack.leaf_nodes[0], pack.leaf_nodes.size());
1567                 device->tex_alloc("__bvh_leaf_nodes", dscene->bvh_leaf_nodes);
1568         }
1569         if(pack.object_node.size()) {
1570                 dscene->object_node.reference((uint*)&pack.object_node[0], pack.object_node.size());
1571                 device->tex_alloc("__object_node", dscene->object_node);
1572         }
1573         if(pack.prim_tri_index.size()) {
1574                 dscene->prim_tri_index.reference((uint*)&pack.prim_tri_index[0], pack.prim_tri_index.size());
1575                 device->tex_alloc("__prim_tri_index", dscene->prim_tri_index);
1576         }
1577         if(pack.prim_tri_verts.size()) {
1578                 dscene->prim_tri_verts.reference((float4*)&pack.prim_tri_verts[0], pack.prim_tri_verts.size());
1579                 device->tex_alloc("__prim_tri_verts", dscene->prim_tri_verts);
1580         }
1581         if(pack.prim_type.size()) {
1582                 dscene->prim_type.reference((uint*)&pack.prim_type[0], pack.prim_type.size());
1583                 device->tex_alloc("__prim_type", dscene->prim_type);
1584         }
1585         if(pack.prim_visibility.size()) {
1586                 dscene->prim_visibility.reference((uint*)&pack.prim_visibility[0], pack.prim_visibility.size());
1587                 device->tex_alloc("__prim_visibility", dscene->prim_visibility);
1588         }
1589         if(pack.prim_index.size()) {
1590                 dscene->prim_index.reference((uint*)&pack.prim_index[0], pack.prim_index.size());
1591                 device->tex_alloc("__prim_index", dscene->prim_index);
1592         }
1593         if(pack.prim_object.size()) {
1594                 dscene->prim_object.reference((uint*)&pack.prim_object[0], pack.prim_object.size());
1595                 device->tex_alloc("__prim_object", dscene->prim_object);
1596         }
1597
1598         dscene->data.bvh.root = pack.root_index;
1599         dscene->data.bvh.use_qbvh = scene->params.use_qbvh;
1600 }
1601
1602 void MeshManager::device_update_flags(Device * /*device*/,
1603                                       DeviceScene * /*dscene*/,
1604                                       Scene * scene,
1605                                       Progress& /*progress*/)
1606 {
1607         if(!need_update && !need_flags_update) {
1608                 return;
1609         }
1610         /* update flags */
1611         foreach(Mesh *mesh, scene->meshes) {
1612                 mesh->has_volume = false;
1613                 foreach(const Shader *shader, mesh->used_shaders) {
1614                         if(shader->has_volume) {
1615                                 mesh->has_volume = true;
1616                         }
1617                         if(shader->has_surface_bssrdf) {
1618                                 mesh->has_surface_bssrdf = true;
1619                         }
1620                 }
1621         }
1622         need_flags_update = false;
1623 }
1624
1625 void MeshManager::device_update_displacement_images(Device *device,
1626                                                     DeviceScene *dscene,
1627                                                     Scene *scene,
1628                                                     Progress& progress)
1629 {
1630         progress.set_status("Updating Displacement Images");
1631         TaskPool pool;
1632         ImageManager *image_manager = scene->image_manager;
1633         set<int> bump_images;
1634         foreach(Mesh *mesh, scene->meshes) {
1635                 if(mesh->need_update) {
1636                         foreach(Shader *shader, mesh->used_shaders) {
1637                                 if(shader->graph_bump == NULL) {
1638                                         continue;
1639                                 }
1640                                 foreach(ShaderNode* node, shader->graph_bump->nodes) {
1641                                         if(node->special_type != SHADER_SPECIAL_TYPE_IMAGE_SLOT) {
1642                                                 continue;
1643                                         }
1644                                         if(device->info.pack_images) {
1645                                                 /* If device requires packed images we need to update all
1646                                                  * images now, even if they're not used for displacement.
1647                                                  */
1648                                                 image_manager->device_update(device,
1649                                                                              dscene,
1650                                                                              progress);
1651                                                 return;
1652                                         }
1653                                         ImageSlotTextureNode *image_node = static_cast<ImageSlotTextureNode*>(node);
1654                                         int slot = image_node->slot;
1655                                         if(slot != -1) {
1656                                                 bump_images.insert(slot);
1657                                         }
1658                                 }
1659                         }
1660                 }
1661         }
1662         foreach(int slot, bump_images) {
1663                 pool.push(function_bind(&ImageManager::device_update_slot,
1664                                         image_manager,
1665                                         device,
1666                                         dscene,
1667                                         slot,
1668                                         &progress));
1669         }
1670         pool.wait_work();
1671 }
1672
1673 void MeshManager::device_update(Device *device, DeviceScene *dscene, Scene *scene, Progress& progress)
1674 {
1675         if(!need_update)
1676                 return;
1677
1678         VLOG(1) << "Total " << scene->meshes.size() << " meshes.";
1679
1680         /* Update normals. */
1681         foreach(Mesh *mesh, scene->meshes) {
1682                 foreach(Shader *shader, mesh->used_shaders) {
1683                         if(shader->need_update_attributes)
1684                                 mesh->need_update = true;
1685                 }
1686
1687                 if(mesh->need_update) {
1688                         mesh->add_face_normals();
1689                         mesh->add_vertex_normals();
1690
1691                         if(progress.get_cancel()) return;
1692                 }
1693         }
1694
1695         /* Tessellate meshes that are using subdivision */
1696         size_t total_tess_needed = 0;
1697         foreach(Mesh *mesh, scene->meshes) {
1698                 if(mesh->need_update &&
1699                    mesh->subdivision_type != Mesh::SUBDIVISION_NONE &&
1700                    mesh->num_subd_verts == 0 &&
1701                    mesh->subd_params)
1702                 {
1703                         total_tess_needed++;
1704                 }
1705         }
1706
1707         size_t i = 0;
1708         foreach(Mesh *mesh, scene->meshes) {
1709                 if(mesh->need_update &&
1710                    mesh->subdivision_type != Mesh::SUBDIVISION_NONE &&
1711                    mesh->num_subd_verts == 0 &&
1712                    mesh->subd_params)
1713                 {
1714                         string msg = "Tessellating ";
1715                         if(mesh->name == "")
1716                                 msg += string_printf("%u/%u", (uint)(i+1), (uint)total_tess_needed);
1717                         else
1718                                 msg += string_printf("%s %u/%u", mesh->name.c_str(), (uint)(i+1), (uint)total_tess_needed);
1719
1720                         progress.set_status("Updating Mesh", msg);
1721
1722                         DiagSplit dsplit(*mesh->subd_params);
1723                         mesh->tessellate(&dsplit);
1724
1725                         i++;
1726
1727                         if(progress.get_cancel()) return;
1728                 }
1729         }
1730
1731         /* Update images needed for true displacement. */
1732         bool true_displacement_used = false;
1733         bool old_need_object_flags_update = false;
1734         foreach(Mesh *mesh, scene->meshes) {
1735                 if(mesh->need_update &&
1736                    mesh->has_true_displacement())
1737                 {
1738                         true_displacement_used = true;
1739                         break;
1740                 }
1741         }
1742         if(true_displacement_used) {
1743                 VLOG(1) << "Updating images used for true displacement.";
1744                 device_update_displacement_images(device, dscene, scene, progress);
1745                 old_need_object_flags_update = scene->object_manager->need_flags_update;
1746                 scene->object_manager->device_update_flags(device,
1747                                                            dscene,
1748                                                            scene,
1749                                                            progress,
1750                                                            false);
1751         }
1752
1753         /* Device update. */
1754         device_free(device, dscene);
1755
1756         mesh_calc_offset(scene);
1757         if(true_displacement_used) {
1758                 device_update_mesh(device, dscene, scene, true, progress);
1759         }
1760         if(progress.get_cancel()) return;
1761
1762         /* after mesh data has been copied to device memory we need to update
1763          * offsets for patch tables as this can't be known before hand */
1764         scene->object_manager->device_update_patch_map_offsets(device, dscene, scene);
1765
1766         device_update_attributes(device, dscene, scene, progress);
1767         if(progress.get_cancel()) return;
1768
1769         /* Update displacement. */
1770         bool displacement_done = false;
1771         foreach(Mesh *mesh, scene->meshes) {
1772                 if(mesh->need_update &&
1773                    displace(device, dscene, scene, mesh, progress))
1774                 {
1775                         displacement_done = true;
1776                 }
1777         }
1778
1779         /* TODO: properly handle cancel halfway displacement */
1780         if(progress.get_cancel()) return;
1781
1782         /* Device re-update after displacement. */
1783         if(displacement_done) {
1784                 device_free(device, dscene);
1785
1786                 device_update_attributes(device, dscene, scene, progress);
1787                 if(progress.get_cancel()) return;
1788         }
1789
1790         /* Update bvh. */
1791         size_t num_bvh = 0;
1792         foreach(Mesh *mesh, scene->meshes) {
1793                 if(mesh->need_update && mesh->need_build_bvh()) {
1794                         num_bvh++;
1795                 }
1796         }
1797
1798         TaskPool pool;
1799
1800         i = 0;
1801         foreach(Mesh *mesh, scene->meshes) {
1802                 if(mesh->need_update) {
1803                         pool.push(function_bind(&Mesh::compute_bvh,
1804                                                 mesh,
1805                                                 dscene,
1806                                                 &scene->params,
1807                                                 &progress,
1808                                                 i,
1809                                                 num_bvh));
1810                         if(mesh->need_build_bvh()) {
1811                                 i++;
1812                         }
1813                 }
1814         }
1815
1816         TaskPool::Summary summary;
1817         pool.wait_work(&summary);
1818         VLOG(2) << "Objects BVH build pool statistics:\n"
1819                 << summary.full_report();
1820
1821         foreach(Shader *shader, scene->shaders) {
1822                 shader->need_update_attributes = false;
1823         }
1824
1825 #ifdef __OBJECT_MOTION__
1826         Scene::MotionType need_motion = scene->need_motion(device->info.advanced_shading);
1827         bool motion_blur = need_motion == Scene::MOTION_BLUR;
1828 #else
1829         bool motion_blur = false;
1830 #endif
1831
1832         /* Update objects. */
1833         vector<Object *> volume_objects;
1834         foreach(Object *object, scene->objects) {
1835                 object->compute_bounds(motion_blur);
1836         }
1837
1838         if(progress.get_cancel()) return;
1839
1840         device_update_bvh(device, dscene, scene, progress);
1841         if(progress.get_cancel()) return;
1842
1843         device_update_mesh(device, dscene, scene, false, progress);
1844         if(progress.get_cancel()) return;
1845
1846         need_update = false;
1847
1848         if(true_displacement_used) {
1849                 /* Re-tag flags for update, so they're re-evaluated
1850                  * for meshes with correct bounding boxes.
1851                  *
1852                  * This wouldn't cause wrong results, just true
1853                  * displacement might be less optimal ot calculate.
1854                  */
1855                 scene->object_manager->need_flags_update = old_need_object_flags_update;
1856         }
1857 }
1858
1859 void MeshManager::device_free(Device *device, DeviceScene *dscene)
1860 {
1861         device->tex_free(dscene->bvh_nodes);
1862         device->tex_free(dscene->bvh_leaf_nodes);
1863         device->tex_free(dscene->object_node);
1864         device->tex_free(dscene->prim_tri_verts);
1865         device->tex_free(dscene->prim_tri_index);
1866         device->tex_free(dscene->prim_type);
1867         device->tex_free(dscene->prim_visibility);
1868         device->tex_free(dscene->prim_index);
1869         device->tex_free(dscene->prim_object);
1870         device->tex_free(dscene->tri_shader);
1871         device->tex_free(dscene->tri_vnormal);
1872         device->tex_free(dscene->tri_vindex);
1873         device->tex_free(dscene->tri_patch);
1874         device->tex_free(dscene->tri_patch_uv);
1875         device->tex_free(dscene->curves);
1876         device->tex_free(dscene->curve_keys);
1877         device->tex_free(dscene->patches);
1878         device->tex_free(dscene->attributes_map);
1879         device->tex_free(dscene->attributes_float);
1880         device->tex_free(dscene->attributes_float3);
1881         device->tex_free(dscene->attributes_uchar4);
1882
1883         dscene->bvh_nodes.clear();
1884         dscene->object_node.clear();
1885         dscene->prim_tri_verts.clear();
1886         dscene->prim_tri_index.clear();
1887         dscene->prim_type.clear();
1888         dscene->prim_visibility.clear();
1889         dscene->prim_index.clear();
1890         dscene->prim_object.clear();
1891         dscene->tri_shader.clear();
1892         dscene->tri_vnormal.clear();
1893         dscene->tri_vindex.clear();
1894         dscene->tri_patch.clear();
1895         dscene->tri_patch_uv.clear();
1896         dscene->curves.clear();
1897         dscene->curve_keys.clear();
1898         dscene->patches.clear();
1899         dscene->attributes_map.clear();
1900         dscene->attributes_float.clear();
1901         dscene->attributes_float3.clear();
1902         dscene->attributes_uchar4.clear();
1903
1904 #ifdef WITH_OSL
1905         OSLGlobals *og = (OSLGlobals*)device->osl_memory();
1906
1907         if(og) {
1908                 og->object_name_map.clear();
1909                 og->attribute_map.clear();
1910                 og->object_names.clear();
1911         }
1912 #endif
1913 }
1914
1915 void MeshManager::tag_update(Scene *scene)
1916 {
1917         need_update = true;
1918         scene->object_manager->need_update = true;
1919 }
1920
1921 bool Mesh::need_attribute(Scene *scene, AttributeStandard std)
1922 {
1923         if(std == ATTR_STD_NONE)
1924                 return false;
1925         
1926         if(scene->need_global_attribute(std))
1927                 return true;
1928
1929         foreach(Shader *shader, used_shaders)
1930                 if(shader->attributes.find(std))
1931                         return true;
1932         
1933         return false;
1934 }
1935
1936 bool Mesh::need_attribute(Scene * /*scene*/, ustring name)
1937 {
1938         if(name == ustring())
1939                 return false;
1940
1941         foreach(Shader *shader, used_shaders)
1942                 if(shader->attributes.find(name))
1943                         return true;
1944         
1945         return false;
1946 }
1947
1948 CCL_NAMESPACE_END
1949