Cycles: Remove some redundant checks
[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                 for(size_t i = 0; i < triangles_size; i++) {
515                         for(size_t j = 0; j < 3; j++) {
516                                 vN[get_triangle(i).v[j]] += fN[i];
517                         }
518                 }
519
520                 for(size_t i = 0; i < verts_size; i++) {
521                         vN[i] = normalize(vN[i]);
522                         if(flip) {
523                                 vN[i] = -vN[i];
524                         }
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                         for(size_t i = 0; i < triangles_size; i++) {
544                                 for(size_t j = 0; j < 3; j++) {
545                                         float3 fN = compute_face_normal(get_triangle(i), mP);
546                                         mN[get_triangle(i).v[j]] += fN;
547                                 }
548                         }
549
550                         for(size_t i = 0; i < verts_size; i++) {
551                                 mN[i] = normalize(mN[i]);
552                                 if(flip) {
553                                         mN[i] = -mN[i];
554                                 }
555                         }
556                 }
557         }
558
559         /* subd vertex normals */
560         if(!subd_attributes.find(ATTR_STD_VERTEX_NORMAL) && subd_faces.size()) {
561                 /* get attributes */
562                 Attribute *attr_vN = subd_attributes.add(ATTR_STD_VERTEX_NORMAL);
563                 float3 *vN = attr_vN->data_float3();
564
565                 /* compute vertex normals */
566                 memset(vN, 0, verts.size()*sizeof(float3));
567
568                 for(size_t i = 0; i < subd_faces.size(); i++) {
569                         SubdFace& face = subd_faces[i];
570
571                         for(size_t j = 0; j < face.num_corners; j++) {
572                                 size_t corner = subd_face_corners[face.start_corner+j];
573                                 vN[corner] += verts[corner];
574                         }
575                 }
576
577                 for(size_t i = 0; i < verts_size; i++) {
578                         vN[i] = normalize(vN[i]);
579                         if(flip) {
580                                 vN[i] = -vN[i];
581                         }
582                 }
583         }
584 }
585
586 void Mesh::pack_normals(Scene *scene, uint *tri_shader, float4 *vnormal)
587 {
588         Attribute *attr_vN = attributes.find(ATTR_STD_VERTEX_NORMAL);
589         if(attr_vN == NULL) {
590                 /* Happens on objects with just hair. */
591                 return;
592         }
593
594         float3 *vN = attr_vN->data_float3();
595         uint shader_id = 0;
596         uint last_shader = -1;
597         bool last_smooth = false;
598
599         size_t triangles_size = num_triangles();
600         int *shader_ptr = shader.data();
601
602         bool do_transform = transform_applied;
603         Transform ntfm = transform_normal;
604
605         /* save shader */
606         for(size_t i = 0; i < triangles_size; i++) {
607                 if(shader_ptr[i] != last_shader || last_smooth != smooth[i]) {
608                         last_shader = shader_ptr[i];
609                         last_smooth = smooth[i];
610                         Shader *shader = (last_shader < used_shaders.size()) ?
611                                 used_shaders[last_shader] : scene->default_surface;
612                         shader_id = scene->shader_manager->get_shader_id(shader, this, last_smooth);
613                 }
614
615                 tri_shader[i] = shader_id;
616         }
617
618         size_t verts_size = verts.size();
619
620         for(size_t i = 0; i < verts_size; i++) {
621                 float3 vNi = vN[i];
622
623                 if(do_transform)
624                         vNi = normalize(transform_direction(&ntfm, vNi));
625
626                 vnormal[i] = make_float4(vNi.x, vNi.y, vNi.z, 0.0f);
627         }
628 }
629
630 void Mesh::pack_verts(const vector<uint>& tri_prim_index,
631                       uint4 *tri_vindex,
632                       uint *tri_patch,
633                       float2 *tri_patch_uv,
634                       size_t vert_offset,
635                       size_t tri_offset)
636 {
637         size_t verts_size = verts.size();
638
639         if(verts_size && subd_faces.size()) {
640                 float2 *vert_patch_uv_ptr = vert_patch_uv.data();
641
642                 for(size_t i = 0; i < verts_size; i++) {
643                         tri_patch_uv[i] = vert_patch_uv_ptr[i];
644                 }
645         }
646
647         size_t triangles_size = num_triangles();
648
649         for(size_t i = 0; i < triangles_size; i++) {
650                 Triangle t = get_triangle(i);
651                 tri_vindex[i] = make_uint4(t.v[0] + vert_offset,
652                                            t.v[1] + vert_offset,
653                                            t.v[2] + vert_offset,
654                                            tri_prim_index[i + tri_offset]);
655
656                 tri_patch[i] = (!subd_faces.size()) ? -1 : (triangle_patch[i]*8 + patch_offset);
657         }
658 }
659
660 void Mesh::pack_curves(Scene *scene, float4 *curve_key_co, float4 *curve_data, size_t curvekey_offset)
661 {
662         size_t curve_keys_size = curve_keys.size();
663
664         /* pack curve keys */
665         if(curve_keys_size) {
666                 float3 *keys_ptr = curve_keys.data();
667                 float *radius_ptr = curve_radius.data();
668
669                 for(size_t i = 0; i < curve_keys_size; i++)
670                         curve_key_co[i] = make_float4(keys_ptr[i].x, keys_ptr[i].y, keys_ptr[i].z, radius_ptr[i]);
671         }
672
673         /* pack curve segments */
674         size_t curve_num = num_curves();
675
676         for(size_t i = 0; i < curve_num; i++) {
677                 Curve curve = get_curve(i);
678                 int shader_id = curve_shader[i];
679                 Shader *shader = (shader_id < used_shaders.size()) ?
680                         used_shaders[shader_id] : scene->default_surface;
681                 shader_id = scene->shader_manager->get_shader_id(shader, this, false);
682
683                 curve_data[i] = make_float4(
684                         __int_as_float(curve.first_key + curvekey_offset),
685                         __int_as_float(curve.num_keys),
686                         __int_as_float(shader_id),
687                         0.0f);
688         }
689 }
690
691 void Mesh::pack_patches(uint *patch_data, uint vert_offset, uint face_offset, uint corner_offset)
692 {
693         size_t num_faces = subd_faces.size();
694         int ngons = 0;
695
696         for(size_t f = 0; f < num_faces; f++) {
697                 SubdFace face = subd_faces[f];
698
699                 if(face.is_quad()) {
700                         int c[4];
701                         memcpy(c, &subd_face_corners[face.start_corner], sizeof(int)*4);
702
703                         *(patch_data++) = c[0] + vert_offset;
704                         *(patch_data++) = c[1] + vert_offset;
705                         *(patch_data++) = c[2] + vert_offset;
706                         *(patch_data++) = c[3] + vert_offset;
707
708                         *(patch_data++) = f+face_offset;
709                         *(patch_data++) = face.num_corners;
710                         *(patch_data++) = face.start_corner + corner_offset;
711                         *(patch_data++) = 0;
712                 }
713                 else {
714                         for(int i = 0; i < face.num_corners; i++) {
715                                 int c[4];
716                                 c[0] = subd_face_corners[face.start_corner + mod(i + 0, face.num_corners)];
717                                 c[1] = subd_face_corners[face.start_corner + mod(i + 1, face.num_corners)];
718                                 c[2] = verts.size() - num_subd_verts + ngons;
719                                 c[3] = subd_face_corners[face.start_corner + mod(i - 1, face.num_corners)];
720
721                                 *(patch_data++) = c[0] + vert_offset;
722                                 *(patch_data++) = c[1] + vert_offset;
723                                 *(patch_data++) = c[2] + vert_offset;
724                                 *(patch_data++) = c[3] + vert_offset;
725
726                                 *(patch_data++) = f+face_offset;
727                                 *(patch_data++) = face.num_corners | (i << 16);
728                                 *(patch_data++) = face.start_corner + corner_offset;
729                                 *(patch_data++) = subd_face_corners.size() + ngons + corner_offset;
730                         }
731
732                         ngons++;
733                 }
734         }
735 }
736
737 void Mesh::compute_bvh(DeviceScene *dscene,
738                        SceneParams *params,
739                        Progress *progress,
740                        int n,
741                        int total)
742 {
743         if(progress->get_cancel())
744                 return;
745
746         compute_bounds();
747
748         if(need_build_bvh()) {
749                 string msg = "Updating Mesh BVH ";
750                 if(name == "")
751                         msg += string_printf("%u/%u", (uint)(n+1), (uint)total);
752                 else
753                         msg += string_printf("%s %u/%u", name.c_str(), (uint)(n+1), (uint)total);
754
755                 Object object;
756                 object.mesh = this;
757
758                 vector<Object*> objects;
759                 objects.push_back(&object);
760
761                 if(bvh && !need_update_rebuild) {
762                         progress->set_status(msg, "Refitting BVH");
763                         bvh->objects = objects;
764                         bvh->refit(*progress);
765                 }
766                 else {
767                         progress->set_status(msg, "Building BVH");
768
769                         BVHParams bparams;
770                         bparams.use_spatial_split = params->use_bvh_spatial_split;
771                         bparams.use_qbvh = params->use_qbvh;
772                         bparams.use_unaligned_nodes = dscene->data.bvh.have_curves &&
773                                                       params->use_bvh_unaligned_nodes;
774
775                         delete bvh;
776                         bvh = BVH::create(bparams, objects);
777                         MEM_GUARDED_CALL(progress, bvh->build, *progress);
778                 }
779         }
780
781         need_update = false;
782         need_update_rebuild = false;
783 }
784
785 void Mesh::tag_update(Scene *scene, bool rebuild)
786 {
787         need_update = true;
788
789         if(rebuild) {
790                 need_update_rebuild = true;
791                 scene->light_manager->need_update = true;
792         }
793         else {
794                 foreach(Shader *shader, used_shaders)
795                         if(shader->has_surface_emission)
796                                 scene->light_manager->need_update = true;
797         }
798
799         scene->mesh_manager->need_update = true;
800         scene->object_manager->need_update = true;
801 }
802
803 bool Mesh::has_motion_blur() const
804 {
805         return (use_motion_blur &&
806                 (attributes.find(ATTR_STD_MOTION_VERTEX_POSITION) ||
807                  curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION)));
808 }
809
810 bool Mesh::has_true_displacement() const
811 {
812         foreach(Shader *shader, used_shaders) {
813                 if(shader->has_displacement && shader->displacement_method != DISPLACE_BUMP) {
814                         return true;
815                 }
816         }
817
818         return false;
819 }
820
821 bool Mesh::need_build_bvh() const
822 {
823         return !transform_applied || has_surface_bssrdf;
824 }
825
826 bool Mesh::is_instanced() const
827 {
828         /* Currently we treat subsurface objects as instanced.
829          *
830          * While it might be not very optimal for ray traversal, it avoids having
831          * duplicated BVH in the memory, saving quite some space.
832          */
833         return !transform_applied || has_surface_bssrdf;
834 }
835
836 /* Mesh Manager */
837
838 MeshManager::MeshManager()
839 {
840         bvh = NULL;
841         need_update = true;
842         need_flags_update = true;
843 }
844
845 MeshManager::~MeshManager()
846 {
847         delete bvh;
848 }
849
850 void MeshManager::update_osl_attributes(Device *device, Scene *scene, vector<AttributeRequestSet>& mesh_attributes)
851 {
852 #ifdef WITH_OSL
853         /* for OSL, a hash map is used to lookup the attribute by name. */
854         OSLGlobals *og = (OSLGlobals*)device->osl_memory();
855
856         og->object_name_map.clear();
857         og->attribute_map.clear();
858         og->object_names.clear();
859
860         og->attribute_map.resize(scene->objects.size()*ATTR_PRIM_TYPES);
861
862         for(size_t i = 0; i < scene->objects.size(); i++) {
863                 /* set object name to object index map */
864                 Object *object = scene->objects[i];
865                 og->object_name_map[object->name] = i;
866                 og->object_names.push_back(object->name);
867
868                 /* set object attributes */
869                 foreach(ParamValue& attr, object->attributes) {
870                         OSLGlobals::Attribute osl_attr;
871
872                         osl_attr.type = attr.type();
873                         osl_attr.desc.element = ATTR_ELEMENT_OBJECT;
874                         osl_attr.value = attr;
875                         osl_attr.desc.offset = 0;
876                         osl_attr.desc.flags = 0;
877
878                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_TRIANGLE][attr.name()] = osl_attr;
879                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_CURVE][attr.name()] = osl_attr;
880                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_SUBD][attr.name()] = osl_attr;
881                 }
882
883                 /* find mesh attributes */
884                 size_t j;
885
886                 for(j = 0; j < scene->meshes.size(); j++)
887                         if(scene->meshes[j] == object->mesh)
888                                 break;
889
890                 AttributeRequestSet& attributes = mesh_attributes[j];
891
892                 /* set object attributes */
893                 foreach(AttributeRequest& req, attributes.requests) {
894                         OSLGlobals::Attribute osl_attr;
895
896                         if(req.triangle_desc.element != ATTR_ELEMENT_NONE) {
897                                 osl_attr.desc = req.triangle_desc;
898
899                                 if(req.triangle_type == TypeDesc::TypeFloat)
900                                         osl_attr.type = TypeDesc::TypeFloat;
901                                 else if(req.triangle_type == TypeDesc::TypeMatrix)
902                                         osl_attr.type = TypeDesc::TypeMatrix;
903                                 else
904                                         osl_attr.type = TypeDesc::TypeColor;
905
906                                 if(req.std != ATTR_STD_NONE) {
907                                         /* if standard attribute, add lookup by geom: name convention */
908                                         ustring stdname(string("geom:") + string(Attribute::standard_name(req.std)));
909                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_TRIANGLE][stdname] = osl_attr;
910                                 }
911                                 else if(req.name != ustring()) {
912                                         /* add lookup by mesh attribute name */
913                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_TRIANGLE][req.name] = osl_attr;
914                                 }
915                         }
916
917                         if(req.curve_desc.element != ATTR_ELEMENT_NONE) {
918                                 osl_attr.desc = req.curve_desc;
919
920                                 if(req.curve_type == TypeDesc::TypeFloat)
921                                         osl_attr.type = TypeDesc::TypeFloat;
922                                 else if(req.curve_type == TypeDesc::TypeMatrix)
923                                         osl_attr.type = TypeDesc::TypeMatrix;
924                                 else
925                                         osl_attr.type = TypeDesc::TypeColor;
926
927                                 if(req.std != ATTR_STD_NONE) {
928                                         /* if standard attribute, add lookup by geom: name convention */
929                                         ustring stdname(string("geom:") + string(Attribute::standard_name(req.std)));
930                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_CURVE][stdname] = osl_attr;
931                                 }
932                                 else if(req.name != ustring()) {
933                                         /* add lookup by mesh attribute name */
934                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_CURVE][req.name] = osl_attr;
935                                 }
936                         }
937
938                         if(req.subd_desc.element != ATTR_ELEMENT_NONE) {
939                                 osl_attr.desc = req.subd_desc;
940
941                                 if(req.subd_type == TypeDesc::TypeFloat)
942                                         osl_attr.type = TypeDesc::TypeFloat;
943                                 else if(req.subd_type == TypeDesc::TypeMatrix)
944                                         osl_attr.type = TypeDesc::TypeMatrix;
945                                 else
946                                         osl_attr.type = TypeDesc::TypeColor;
947
948                                 if(req.std != ATTR_STD_NONE) {
949                                         /* if standard attribute, add lookup by geom: name convention */
950                                         ustring stdname(string("geom:") + string(Attribute::standard_name(req.std)));
951                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_SUBD][stdname] = osl_attr;
952                                 }
953                                 else if(req.name != ustring()) {
954                                         /* add lookup by mesh attribute name */
955                                         og->attribute_map[i*ATTR_PRIM_TYPES + ATTR_PRIM_SUBD][req.name] = osl_attr;
956                                 }
957                         }
958                 }
959         }
960 #else
961         (void)device;
962         (void)scene;
963         (void)mesh_attributes;
964 #endif
965 }
966
967 void MeshManager::update_svm_attributes(Device *device, DeviceScene *dscene, Scene *scene, vector<AttributeRequestSet>& mesh_attributes)
968 {
969         /* for SVM, the attributes_map table is used to lookup the offset of an
970          * attribute, based on a unique shader attribute id. */
971
972         /* compute array stride */
973         int attr_map_stride = 0;
974
975         for(size_t i = 0; i < scene->meshes.size(); i++)
976                 attr_map_stride = max(attr_map_stride, (mesh_attributes[i].size() + 1)*ATTR_PRIM_TYPES);
977
978         if(attr_map_stride == 0)
979                 return;
980         
981         /* create attribute map */
982         uint4 *attr_map = dscene->attributes_map.resize(attr_map_stride*scene->objects.size());
983         memset(attr_map, 0, dscene->attributes_map.size()*sizeof(uint));
984
985         for(size_t i = 0; i < scene->objects.size(); i++) {
986                 Object *object = scene->objects[i];
987                 Mesh *mesh = object->mesh;
988
989                 /* find mesh attributes */
990                 size_t j;
991
992                 for(j = 0; j < scene->meshes.size(); j++)
993                         if(scene->meshes[j] == mesh)
994                                 break;
995
996                 AttributeRequestSet& attributes = mesh_attributes[j];
997
998                 /* set object attributes */
999                 int index = i*attr_map_stride;
1000
1001                 foreach(AttributeRequest& req, attributes.requests) {
1002                         uint id;
1003
1004                         if(req.std == ATTR_STD_NONE)
1005                                 id = scene->shader_manager->get_attribute_id(req.name);
1006                         else
1007                                 id = scene->shader_manager->get_attribute_id(req.std);
1008
1009                         if(mesh->num_triangles()) {
1010                                 attr_map[index].x = id;
1011                                 attr_map[index].y = req.triangle_desc.element;
1012                                 attr_map[index].z = as_uint(req.triangle_desc.offset);
1013
1014                                 if(req.triangle_type == TypeDesc::TypeFloat)
1015                                         attr_map[index].w = NODE_ATTR_FLOAT;
1016                                 else if(req.triangle_type == TypeDesc::TypeMatrix)
1017                                         attr_map[index].w = NODE_ATTR_MATRIX;
1018                                 else
1019                                         attr_map[index].w = NODE_ATTR_FLOAT3;
1020
1021                                 attr_map[index].w |= req.triangle_desc.flags << 8;
1022                         }
1023
1024                         index++;
1025
1026                         if(mesh->num_curves()) {
1027                                 attr_map[index].x = id;
1028                                 attr_map[index].y = req.curve_desc.element;
1029                                 attr_map[index].z = as_uint(req.curve_desc.offset);
1030
1031                                 if(req.curve_type == TypeDesc::TypeFloat)
1032                                         attr_map[index].w = NODE_ATTR_FLOAT;
1033                                 else if(req.curve_type == TypeDesc::TypeMatrix)
1034                                         attr_map[index].w = NODE_ATTR_MATRIX;
1035                                 else
1036                                         attr_map[index].w = NODE_ATTR_FLOAT3;
1037
1038                                 attr_map[index].w |= req.curve_desc.flags << 8;
1039                         }
1040
1041                         index++;
1042
1043                         if(mesh->subd_faces.size()) {
1044                                 attr_map[index].x = id;
1045                                 attr_map[index].y = req.subd_desc.element;
1046                                 attr_map[index].z = as_uint(req.subd_desc.offset);
1047
1048                                 if(req.subd_type == TypeDesc::TypeFloat)
1049                                         attr_map[index].w = NODE_ATTR_FLOAT;
1050                                 else if(req.subd_type == TypeDesc::TypeMatrix)
1051                                         attr_map[index].w = NODE_ATTR_MATRIX;
1052                                 else
1053                                         attr_map[index].w = NODE_ATTR_FLOAT3;
1054
1055                                 attr_map[index].w |= req.subd_desc.flags << 8;
1056                         }
1057
1058                         index++;
1059                 }
1060
1061                 /* terminator */
1062                 for(int i = 0; i < ATTR_PRIM_TYPES; i++) {
1063                         attr_map[index].x = ATTR_STD_NONE;
1064                         attr_map[index].y = 0;
1065                         attr_map[index].z = 0;
1066                         attr_map[index].w = 0;
1067
1068                         index++;
1069                 }
1070         }
1071
1072         /* copy to device */
1073         dscene->data.bvh.attributes_map_stride = attr_map_stride;
1074         device->tex_alloc("__attributes_map", dscene->attributes_map);
1075 }
1076
1077 static void update_attribute_element_size(Mesh *mesh,
1078                                           Attribute *mattr,
1079                                           AttributePrimitive prim,
1080                                           size_t *attr_float_size,
1081                                           size_t *attr_float3_size,
1082                                           size_t *attr_uchar4_size)
1083 {
1084         if(mattr) {
1085                 size_t size = mattr->element_size(mesh, prim);
1086
1087                 if(mattr->element == ATTR_ELEMENT_VOXEL) {
1088                         /* pass */
1089                 }
1090                 else if(mattr->element == ATTR_ELEMENT_CORNER_BYTE) {
1091                         *attr_uchar4_size += size;
1092                 }
1093                 else if(mattr->type == TypeDesc::TypeFloat) {
1094                         *attr_float_size += size;
1095                 }
1096                 else if(mattr->type == TypeDesc::TypeMatrix) {
1097                         *attr_float3_size += size * 4;
1098                 }
1099                 else {
1100                         *attr_float3_size += size;
1101                 }
1102         }
1103 }
1104
1105 static void update_attribute_element_offset(Mesh *mesh,
1106                                             vector<float>& attr_float,
1107                                             size_t& attr_float_offset,
1108                                             vector<float4>& attr_float3,
1109                                             size_t& attr_float3_offset,
1110                                             vector<uchar4>& attr_uchar4,
1111                                             size_t& attr_uchar4_offset,
1112                                             Attribute *mattr,
1113                                             AttributePrimitive prim,
1114                                             TypeDesc& type,
1115                                             AttributeDescriptor& desc)
1116 {
1117         if(mattr) {
1118                 /* store element and type */
1119                 desc.element = mattr->element;
1120                 desc.flags = mattr->flags;
1121                 type = mattr->type;
1122
1123                 /* store attribute data in arrays */
1124                 size_t size = mattr->element_size(mesh, prim);
1125
1126                 AttributeElement& element = desc.element;
1127                 int& offset = desc.offset;
1128
1129                 if(mattr->element == ATTR_ELEMENT_VOXEL) {
1130                         /* store slot in offset value */
1131                         VoxelAttribute *voxel_data = mattr->data_voxel();
1132                         offset = voxel_data->slot;
1133                 }
1134                 else if(mattr->element == ATTR_ELEMENT_CORNER_BYTE) {
1135                         uchar4 *data = mattr->data_uchar4();
1136                         offset = attr_uchar4_offset;
1137
1138                         assert(attr_uchar4.capacity() >= offset + size);
1139                         for(size_t k = 0; k < size; k++) {
1140                                 attr_uchar4[offset+k] = data[k];
1141                         }
1142                         attr_uchar4_offset += size;
1143                 }
1144                 else if(mattr->type == TypeDesc::TypeFloat) {
1145                         float *data = mattr->data_float();
1146                         offset = attr_float_offset;
1147
1148                         assert(attr_float.capacity() >= offset + size);
1149                         for(size_t k = 0; k < size; k++) {
1150                                 attr_float[offset+k] = data[k];
1151                         }
1152                         attr_float_offset += size;
1153                 }
1154                 else if(mattr->type == TypeDesc::TypeMatrix) {
1155                         Transform *tfm = mattr->data_transform();
1156                         offset = attr_float3_offset;
1157
1158                         assert(attr_float3.capacity() >= offset + size * 4);
1159                         for(size_t k = 0; k < size*4; k++) {
1160                                 attr_float3[offset+k] = (&tfm->x)[k];
1161                         }
1162                         attr_float3_offset += size * 4;
1163                 }
1164                 else {
1165                         float4 *data = mattr->data_float4();
1166                         offset = attr_float3_offset;
1167
1168                         assert(attr_float3.capacity() >= offset + size);
1169                         for(size_t k = 0; k < size; k++) {
1170                                 attr_float3[offset+k] = data[k];
1171                         }
1172                         attr_float3_offset += size;
1173                 }
1174
1175                 /* mesh vertex/curve index is global, not per object, so we sneak
1176                  * a correction for that in here */
1177                 if(mesh->subdivision_type == Mesh::SUBDIVISION_CATMULL_CLARK && desc.flags & ATTR_SUBDIVIDED) {
1178                         /* indices for subdivided attributes are retrieved
1179                          * from patch table so no need for correction here*/
1180                 }
1181                 else if(element == ATTR_ELEMENT_VERTEX)
1182                         offset -= mesh->vert_offset;
1183                 else if(element == ATTR_ELEMENT_VERTEX_MOTION)
1184                         offset -= mesh->vert_offset;
1185                 else if(element == ATTR_ELEMENT_FACE) {
1186                         if(prim == ATTR_PRIM_TRIANGLE)
1187                                 offset -= mesh->tri_offset;
1188                         else
1189                                 offset -= mesh->face_offset;
1190                 }
1191                 else if(element == ATTR_ELEMENT_CORNER || element == ATTR_ELEMENT_CORNER_BYTE) {
1192                         if(prim == ATTR_PRIM_TRIANGLE)
1193                                 offset -= 3*mesh->tri_offset;
1194                         else
1195                                 offset -= mesh->corner_offset;
1196                 }
1197                 else if(element == ATTR_ELEMENT_CURVE)
1198                         offset -= mesh->curve_offset;
1199                 else if(element == ATTR_ELEMENT_CURVE_KEY)
1200                         offset -= mesh->curvekey_offset;
1201                 else if(element == ATTR_ELEMENT_CURVE_KEY_MOTION)
1202                         offset -= mesh->curvekey_offset;
1203         }
1204         else {
1205                 /* attribute not found */
1206                 desc.element = ATTR_ELEMENT_NONE;
1207                 desc.offset = 0;
1208         }
1209 }
1210
1211 void MeshManager::device_update_attributes(Device *device, DeviceScene *dscene, Scene *scene, Progress& progress)
1212 {
1213         progress.set_status("Updating Mesh", "Computing attributes");
1214
1215         /* gather per mesh requested attributes. as meshes may have multiple
1216          * shaders assigned, this merges the requested attributes that have
1217          * been set per shader by the shader manager */
1218         vector<AttributeRequestSet> mesh_attributes(scene->meshes.size());
1219
1220         for(size_t i = 0; i < scene->meshes.size(); i++) {
1221                 Mesh *mesh = scene->meshes[i];
1222
1223                 scene->need_global_attributes(mesh_attributes[i]);
1224
1225                 foreach(Shader *shader, mesh->used_shaders) {
1226                         mesh_attributes[i].add(shader->attributes);
1227                 }
1228         }
1229
1230         /* mesh attribute are stored in a single array per data type. here we fill
1231          * those arrays, and set the offset and element type to create attribute
1232          * maps next */
1233
1234         /* Pre-allocate attributes to avoid arrays re-allocation which would
1235          * take 2x of overall attribute memory usage.
1236          */
1237         size_t attr_float_size = 0;
1238         size_t attr_float3_size = 0;
1239         size_t attr_uchar4_size = 0;
1240         for(size_t i = 0; i < scene->meshes.size(); i++) {
1241                 Mesh *mesh = scene->meshes[i];
1242                 AttributeRequestSet& attributes = mesh_attributes[i];
1243                 foreach(AttributeRequest& req, attributes.requests) {
1244                         Attribute *triangle_mattr = mesh->attributes.find(req);
1245                         Attribute *curve_mattr = mesh->curve_attributes.find(req);
1246                         Attribute *subd_mattr = mesh->subd_attributes.find(req);
1247
1248                         update_attribute_element_size(mesh,
1249                                                       triangle_mattr,
1250                                                       ATTR_PRIM_TRIANGLE,
1251                                                       &attr_float_size,
1252                                                       &attr_float3_size,
1253                                                       &attr_uchar4_size);
1254                         update_attribute_element_size(mesh,
1255                                                       curve_mattr,
1256                                                       ATTR_PRIM_CURVE,
1257                                                       &attr_float_size,
1258                                                       &attr_float3_size,
1259                                                       &attr_uchar4_size);
1260                         update_attribute_element_size(mesh,
1261                                                       subd_mattr,
1262                                                       ATTR_PRIM_SUBD,
1263                                                       &attr_float_size,
1264                                                       &attr_float3_size,
1265                                                       &attr_uchar4_size);
1266                 }
1267         }
1268
1269         vector<float> attr_float(attr_float_size);
1270         vector<float4> attr_float3(attr_float3_size);
1271         vector<uchar4> attr_uchar4(attr_uchar4_size);
1272
1273         size_t attr_float_offset = 0;
1274         size_t attr_float3_offset = 0;
1275         size_t attr_uchar4_offset = 0;
1276
1277         /* Fill in attributes. */
1278         for(size_t i = 0; i < scene->meshes.size(); i++) {
1279                 Mesh *mesh = scene->meshes[i];
1280                 AttributeRequestSet& attributes = mesh_attributes[i];
1281
1282                 /* todo: we now store std and name attributes from requests even if
1283                  * they actually refer to the same mesh attributes, optimize */
1284                 foreach(AttributeRequest& req, attributes.requests) {
1285                         Attribute *triangle_mattr = mesh->attributes.find(req);
1286                         Attribute *curve_mattr = mesh->curve_attributes.find(req);
1287                         Attribute *subd_mattr = mesh->subd_attributes.find(req);
1288
1289                         update_attribute_element_offset(mesh,
1290                                                         attr_float, attr_float_offset,
1291                                                         attr_float3, attr_float3_offset,
1292                                                         attr_uchar4, attr_uchar4_offset,
1293                                                         triangle_mattr,
1294                                                         ATTR_PRIM_TRIANGLE,
1295                                                         req.triangle_type,
1296                                                         req.triangle_desc);
1297
1298                         update_attribute_element_offset(mesh,
1299                                                         attr_float, attr_float_offset,
1300                                                         attr_float3, attr_float3_offset,
1301                                                         attr_uchar4, attr_uchar4_offset,
1302                                                         curve_mattr,
1303                                                         ATTR_PRIM_CURVE,
1304                                                         req.curve_type,
1305                                                         req.curve_desc);
1306
1307                         update_attribute_element_offset(mesh,
1308                                                         attr_float, attr_float_offset,
1309                                                         attr_float3, attr_float3_offset,
1310                                                         attr_uchar4, attr_uchar4_offset,
1311                                                         subd_mattr,
1312                                                         ATTR_PRIM_SUBD,
1313                                                         req.subd_type,
1314                                                         req.subd_desc);
1315
1316                         if(progress.get_cancel()) return;
1317                 }
1318         }
1319
1320         /* create attribute lookup maps */
1321         if(scene->shader_manager->use_osl())
1322                 update_osl_attributes(device, scene, mesh_attributes);
1323
1324         update_svm_attributes(device, dscene, scene, mesh_attributes);
1325
1326         if(progress.get_cancel()) return;
1327
1328         /* copy to device */
1329         progress.set_status("Updating Mesh", "Copying Attributes to device");
1330
1331         if(attr_float.size()) {
1332                 dscene->attributes_float.copy(&attr_float[0], attr_float.size());
1333                 device->tex_alloc("__attributes_float", dscene->attributes_float);
1334         }
1335         if(attr_float3.size()) {
1336                 dscene->attributes_float3.copy(&attr_float3[0], attr_float3.size());
1337                 device->tex_alloc("__attributes_float3", dscene->attributes_float3);
1338         }
1339         if(attr_uchar4.size()) {
1340                 dscene->attributes_uchar4.copy(&attr_uchar4[0], attr_uchar4.size());
1341                 device->tex_alloc("__attributes_uchar4", dscene->attributes_uchar4);
1342         }
1343 }
1344
1345 void MeshManager::mesh_calc_offset(Scene *scene)
1346 {
1347         size_t vert_size = 0;
1348         size_t tri_size = 0;
1349
1350         size_t curve_key_size = 0;
1351         size_t curve_size = 0;
1352
1353         size_t patch_size = 0;
1354         size_t face_size = 0;
1355         size_t corner_size = 0;
1356
1357         foreach(Mesh *mesh, scene->meshes) {
1358                 mesh->vert_offset = vert_size;
1359                 mesh->tri_offset = tri_size;
1360
1361                 mesh->curvekey_offset = curve_key_size;
1362                 mesh->curve_offset = curve_size;
1363
1364                 mesh->patch_offset = patch_size;
1365                 mesh->face_offset = face_size;
1366                 mesh->corner_offset = corner_size;
1367
1368                 vert_size += mesh->verts.size();
1369                 tri_size += mesh->num_triangles();
1370
1371                 curve_key_size += mesh->curve_keys.size();
1372                 curve_size += mesh->num_curves();
1373
1374                 if(mesh->subd_faces.size()) {
1375                         Mesh::SubdFace& last = mesh->subd_faces[mesh->subd_faces.size()-1];
1376                         patch_size += (last.ptex_offset + last.num_ptex_faces()) * 8;
1377
1378                         /* patch tables are stored in same array so include them in patch_size */
1379                         if(mesh->patch_table) {
1380                                 mesh->patch_table_offset = patch_size;
1381                                 patch_size += mesh->patch_table->total_size();
1382                         }
1383                 }
1384                 face_size += mesh->subd_faces.size();
1385                 corner_size += mesh->subd_face_corners.size();
1386         }
1387 }
1388
1389 void MeshManager::device_update_mesh(Device *device,
1390                                      DeviceScene *dscene,
1391                                      Scene *scene,
1392                                      bool for_displacement,
1393                                      Progress& progress)
1394 {
1395         /* Count. */
1396         size_t vert_size = 0;
1397         size_t tri_size = 0;
1398
1399         size_t curve_key_size = 0;
1400         size_t curve_size = 0;
1401
1402         size_t patch_size = 0;
1403
1404         foreach(Mesh *mesh, scene->meshes) {
1405                 vert_size += mesh->verts.size();
1406                 tri_size += mesh->num_triangles();
1407
1408                 curve_key_size += mesh->curve_keys.size();
1409                 curve_size += mesh->num_curves();
1410
1411                 if(mesh->subd_faces.size()) {
1412                         Mesh::SubdFace& last = mesh->subd_faces[mesh->subd_faces.size()-1];
1413                         patch_size += (last.ptex_offset + last.num_ptex_faces()) * 8;
1414
1415                         /* patch tables are stored in same array so include them in patch_size */
1416                         if(mesh->patch_table) {
1417                                 mesh->patch_table_offset = patch_size;
1418                                 patch_size += mesh->patch_table->total_size();
1419                         }
1420                 }
1421         }
1422
1423         /* Create mapping from triangle to primitive triangle array. */
1424         vector<uint> tri_prim_index(tri_size);
1425         if(for_displacement) {
1426                 /* For displacement kernels we do some trickery to make them believe
1427                  * we've got all required data ready. However, that data is different
1428                  * from final render kernels since we don't have BVH yet, so can't
1429                  * really use same semantic of arrays.
1430                  */
1431                 foreach(Mesh *mesh, scene->meshes) {
1432                         for(size_t i = 0; i < mesh->num_triangles(); ++i) {
1433                                 tri_prim_index[i + mesh->tri_offset] = 3 * (i + mesh->tri_offset);
1434                         }
1435                 }
1436         }
1437         else {
1438                 PackedBVH& pack = bvh->pack;
1439                 for(size_t i = 0; i < pack.prim_index.size(); ++i) {
1440                         if ((pack.prim_type[i] & PRIMITIVE_ALL_TRIANGLE) != 0) {
1441                                 tri_prim_index[pack.prim_index[i]] = pack.prim_tri_index[i];
1442                         }
1443                 }
1444         }
1445
1446         /* Fill in all the arrays. */
1447         if(tri_size != 0) {
1448                 /* normals */
1449                 progress.set_status("Updating Mesh", "Computing normals");
1450
1451                 uint *tri_shader = dscene->tri_shader.resize(tri_size);
1452                 float4 *vnormal = dscene->tri_vnormal.resize(vert_size);
1453                 uint4 *tri_vindex = dscene->tri_vindex.resize(tri_size);
1454                 uint *tri_patch = dscene->tri_patch.resize(tri_size);
1455                 float2 *tri_patch_uv = dscene->tri_patch_uv.resize(vert_size);
1456
1457                 foreach(Mesh *mesh, scene->meshes) {
1458                         mesh->pack_normals(scene,
1459                                            &tri_shader[mesh->tri_offset],
1460                                            &vnormal[mesh->vert_offset]);
1461                         mesh->pack_verts(tri_prim_index,
1462                                          &tri_vindex[mesh->tri_offset],
1463                                          &tri_patch[mesh->tri_offset],
1464                                          &tri_patch_uv[mesh->vert_offset],
1465                                          mesh->vert_offset,
1466                                          mesh->tri_offset);
1467                         if(progress.get_cancel()) return;
1468                 }
1469
1470                 /* vertex coordinates */
1471                 progress.set_status("Updating Mesh", "Copying Mesh to device");
1472
1473                 device->tex_alloc("__tri_shader", dscene->tri_shader);
1474                 device->tex_alloc("__tri_vnormal", dscene->tri_vnormal);
1475                 device->tex_alloc("__tri_vindex", dscene->tri_vindex);
1476                 device->tex_alloc("__tri_patch", dscene->tri_patch);
1477                 device->tex_alloc("__tri_patch_uv", dscene->tri_patch_uv);
1478         }
1479
1480         if(curve_size != 0) {
1481                 progress.set_status("Updating Mesh", "Copying Strands to device");
1482
1483                 float4 *curve_keys = dscene->curve_keys.resize(curve_key_size);
1484                 float4 *curves = dscene->curves.resize(curve_size);
1485
1486                 foreach(Mesh *mesh, scene->meshes) {
1487                         mesh->pack_curves(scene, &curve_keys[mesh->curvekey_offset], &curves[mesh->curve_offset], mesh->curvekey_offset);
1488                         if(progress.get_cancel()) return;
1489                 }
1490
1491                 device->tex_alloc("__curve_keys", dscene->curve_keys);
1492                 device->tex_alloc("__curves", dscene->curves);
1493         }
1494
1495         if(patch_size != 0) {
1496                 progress.set_status("Updating Mesh", "Copying Patches to device");
1497
1498                 uint *patch_data = dscene->patches.resize(patch_size);
1499
1500                 foreach(Mesh *mesh, scene->meshes) {
1501                         mesh->pack_patches(&patch_data[mesh->patch_offset], mesh->vert_offset, mesh->face_offset, mesh->corner_offset);
1502
1503                         if(mesh->patch_table) {
1504                                 mesh->patch_table->copy_adjusting_offsets(&patch_data[mesh->patch_table_offset], mesh->patch_table_offset);
1505                         }
1506
1507                         if(progress.get_cancel()) return;
1508                 }
1509
1510                 device->tex_alloc("__patches", dscene->patches);
1511         }
1512
1513         if(for_displacement) {
1514                 float4 *prim_tri_verts = dscene->prim_tri_verts.resize(tri_size * 3);
1515                 foreach(Mesh *mesh, scene->meshes) {
1516                         for(size_t i = 0; i < mesh->num_triangles(); ++i) {
1517                                 Mesh::Triangle t = mesh->get_triangle(i);
1518                                 size_t offset = 3 * (i + mesh->tri_offset);
1519                                 prim_tri_verts[offset + 0] = float3_to_float4(mesh->verts[t.v[0]]);
1520                                 prim_tri_verts[offset + 1] = float3_to_float4(mesh->verts[t.v[1]]);
1521                                 prim_tri_verts[offset + 2] = float3_to_float4(mesh->verts[t.v[2]]);
1522                         }
1523                 }
1524                 device->tex_alloc("__prim_tri_verts", dscene->prim_tri_verts);
1525         }
1526 }
1527
1528 void MeshManager::device_update_bvh(Device *device, DeviceScene *dscene, Scene *scene, Progress& progress)
1529 {
1530         /* bvh build */
1531         progress.set_status("Updating Scene BVH", "Building");
1532
1533         VLOG(1) << (scene->params.use_qbvh ? "Using QBVH optimization structure"
1534                                            : "Using regular BVH optimization structure");
1535
1536         BVHParams bparams;
1537         bparams.top_level = true;
1538         bparams.use_qbvh = scene->params.use_qbvh;
1539         bparams.use_spatial_split = scene->params.use_bvh_spatial_split;
1540         bparams.use_unaligned_nodes = dscene->data.bvh.have_curves &&
1541                                       scene->params.use_bvh_unaligned_nodes;
1542
1543         delete bvh;
1544         bvh = BVH::create(bparams, scene->objects);
1545         bvh->build(progress);
1546
1547         if(progress.get_cancel()) return;
1548
1549         /* copy to device */
1550         progress.set_status("Updating Scene BVH", "Copying BVH to device");
1551
1552         PackedBVH& pack = bvh->pack;
1553
1554         if(pack.nodes.size()) {
1555                 dscene->bvh_nodes.reference((float4*)&pack.nodes[0], pack.nodes.size());
1556                 device->tex_alloc("__bvh_nodes", dscene->bvh_nodes);
1557         }
1558         if(pack.leaf_nodes.size()) {
1559                 dscene->bvh_leaf_nodes.reference((float4*)&pack.leaf_nodes[0], pack.leaf_nodes.size());
1560                 device->tex_alloc("__bvh_leaf_nodes", dscene->bvh_leaf_nodes);
1561         }
1562         if(pack.object_node.size()) {
1563                 dscene->object_node.reference((uint*)&pack.object_node[0], pack.object_node.size());
1564                 device->tex_alloc("__object_node", dscene->object_node);
1565         }
1566         if(pack.prim_tri_index.size()) {
1567                 dscene->prim_tri_index.reference((uint*)&pack.prim_tri_index[0], pack.prim_tri_index.size());
1568                 device->tex_alloc("__prim_tri_index", dscene->prim_tri_index);
1569         }
1570         if(pack.prim_tri_verts.size()) {
1571                 dscene->prim_tri_verts.reference((float4*)&pack.prim_tri_verts[0], pack.prim_tri_verts.size());
1572                 device->tex_alloc("__prim_tri_verts", dscene->prim_tri_verts);
1573         }
1574         if(pack.prim_type.size()) {
1575                 dscene->prim_type.reference((uint*)&pack.prim_type[0], pack.prim_type.size());
1576                 device->tex_alloc("__prim_type", dscene->prim_type);
1577         }
1578         if(pack.prim_visibility.size()) {
1579                 dscene->prim_visibility.reference((uint*)&pack.prim_visibility[0], pack.prim_visibility.size());
1580                 device->tex_alloc("__prim_visibility", dscene->prim_visibility);
1581         }
1582         if(pack.prim_index.size()) {
1583                 dscene->prim_index.reference((uint*)&pack.prim_index[0], pack.prim_index.size());
1584                 device->tex_alloc("__prim_index", dscene->prim_index);
1585         }
1586         if(pack.prim_object.size()) {
1587                 dscene->prim_object.reference((uint*)&pack.prim_object[0], pack.prim_object.size());
1588                 device->tex_alloc("__prim_object", dscene->prim_object);
1589         }
1590
1591         dscene->data.bvh.root = pack.root_index;
1592         dscene->data.bvh.use_qbvh = scene->params.use_qbvh;
1593 }
1594
1595 void MeshManager::device_update_flags(Device * /*device*/,
1596                                       DeviceScene * /*dscene*/,
1597                                       Scene * scene,
1598                                       Progress& /*progress*/)
1599 {
1600         if(!need_update && !need_flags_update) {
1601                 return;
1602         }
1603         /* update flags */
1604         foreach(Mesh *mesh, scene->meshes) {
1605                 mesh->has_volume = false;
1606                 foreach(const Shader *shader, mesh->used_shaders) {
1607                         if(shader->has_volume) {
1608                                 mesh->has_volume = true;
1609                         }
1610                         if(shader->has_surface_bssrdf) {
1611                                 mesh->has_surface_bssrdf = true;
1612                         }
1613                 }
1614         }
1615         need_flags_update = false;
1616 }
1617
1618 void MeshManager::device_update_displacement_images(Device *device,
1619                                                     DeviceScene *dscene,
1620                                                     Scene *scene,
1621                                                     Progress& progress)
1622 {
1623         progress.set_status("Updating Displacement Images");
1624         TaskPool pool;
1625         ImageManager *image_manager = scene->image_manager;
1626         set<int> bump_images;
1627         foreach(Mesh *mesh, scene->meshes) {
1628                 if(mesh->need_update) {
1629                         foreach(Shader *shader, mesh->used_shaders) {
1630                                 if(shader->graph_bump == NULL) {
1631                                         continue;
1632                                 }
1633                                 foreach(ShaderNode* node, shader->graph_bump->nodes) {
1634                                         if(node->special_type != SHADER_SPECIAL_TYPE_IMAGE_SLOT) {
1635                                                 continue;
1636                                         }
1637                                         if(device->info.pack_images) {
1638                                                 /* If device requires packed images we need to update all
1639                                                  * images now, even if they're not used for displacement.
1640                                                  */
1641                                                 image_manager->device_update(device,
1642                                                                              dscene,
1643                                                                              progress);
1644                                                 return;
1645                                         }
1646                                         ImageSlotTextureNode *image_node = static_cast<ImageSlotTextureNode*>(node);
1647                                         int slot = image_node->slot;
1648                                         if(slot != -1) {
1649                                                 bump_images.insert(slot);
1650                                         }
1651                                 }
1652                         }
1653                 }
1654         }
1655         foreach(int slot, bump_images) {
1656                 pool.push(function_bind(&ImageManager::device_update_slot,
1657                                         image_manager,
1658                                         device,
1659                                         dscene,
1660                                         slot,
1661                                         &progress));
1662         }
1663         pool.wait_work();
1664 }
1665
1666 void MeshManager::device_update(Device *device, DeviceScene *dscene, Scene *scene, Progress& progress)
1667 {
1668         if(!need_update)
1669                 return;
1670
1671         VLOG(1) << "Total " << scene->meshes.size() << " meshes.";
1672
1673         /* Update normals. */
1674         foreach(Mesh *mesh, scene->meshes) {
1675                 foreach(Shader *shader, mesh->used_shaders) {
1676                         if(shader->need_update_attributes)
1677                                 mesh->need_update = true;
1678                 }
1679
1680                 if(mesh->need_update) {
1681                         mesh->add_face_normals();
1682                         mesh->add_vertex_normals();
1683
1684                         if(progress.get_cancel()) return;
1685                 }
1686         }
1687
1688         /* Tessellate meshes that are using subdivision */
1689         size_t total_tess_needed = 0;
1690         foreach(Mesh *mesh, scene->meshes) {
1691                 if(mesh->need_update &&
1692                    mesh->subdivision_type != Mesh::SUBDIVISION_NONE &&
1693                    mesh->num_subd_verts == 0 &&
1694                    mesh->subd_params)
1695                 {
1696                         total_tess_needed++;
1697                 }
1698         }
1699
1700         size_t i = 0;
1701         foreach(Mesh *mesh, scene->meshes) {
1702                 if(mesh->need_update &&
1703                    mesh->subdivision_type != Mesh::SUBDIVISION_NONE &&
1704                    mesh->num_subd_verts == 0 &&
1705                    mesh->subd_params)
1706                 {
1707                         string msg = "Tessellating ";
1708                         if(mesh->name == "")
1709                                 msg += string_printf("%u/%u", (uint)(i+1), (uint)total_tess_needed);
1710                         else
1711                                 msg += string_printf("%s %u/%u", mesh->name.c_str(), (uint)(i+1), (uint)total_tess_needed);
1712
1713                         progress.set_status("Updating Mesh", msg);
1714
1715                         DiagSplit dsplit(*mesh->subd_params);
1716                         mesh->tessellate(&dsplit);
1717
1718                         i++;
1719
1720                         if(progress.get_cancel()) return;
1721                 }
1722         }
1723
1724         /* Update images needed for true displacement. */
1725         bool true_displacement_used = false;
1726         bool old_need_object_flags_update = false;
1727         foreach(Mesh *mesh, scene->meshes) {
1728                 if(mesh->need_update &&
1729                    mesh->has_true_displacement())
1730                 {
1731                         true_displacement_used = true;
1732                         break;
1733                 }
1734         }
1735         if(true_displacement_used) {
1736                 VLOG(1) << "Updating images used for true displacement.";
1737                 device_update_displacement_images(device, dscene, scene, progress);
1738                 old_need_object_flags_update = scene->object_manager->need_flags_update;
1739                 scene->object_manager->device_update_flags(device,
1740                                                            dscene,
1741                                                            scene,
1742                                                            progress,
1743                                                            false);
1744         }
1745
1746         /* Device update. */
1747         device_free(device, dscene);
1748
1749         mesh_calc_offset(scene);
1750         if(true_displacement_used) {
1751                 device_update_mesh(device, dscene, scene, true, progress);
1752         }
1753         if(progress.get_cancel()) return;
1754
1755         /* after mesh data has been copied to device memory we need to update
1756          * offsets for patch tables as this can't be known before hand */
1757         scene->object_manager->device_update_patch_map_offsets(device, dscene, scene);
1758
1759         device_update_attributes(device, dscene, scene, progress);
1760         if(progress.get_cancel()) return;
1761
1762         /* Update displacement. */
1763         bool displacement_done = false;
1764         foreach(Mesh *mesh, scene->meshes) {
1765                 if(mesh->need_update &&
1766                    displace(device, dscene, scene, mesh, progress))
1767                 {
1768                         displacement_done = true;
1769                 }
1770         }
1771
1772         /* TODO: properly handle cancel halfway displacement */
1773         if(progress.get_cancel()) return;
1774
1775         /* Device re-update after displacement. */
1776         if(displacement_done) {
1777                 device_free(device, dscene);
1778
1779                 device_update_attributes(device, dscene, scene, progress);
1780                 if(progress.get_cancel()) return;
1781         }
1782
1783         /* Update bvh. */
1784         size_t num_bvh = 0;
1785         foreach(Mesh *mesh, scene->meshes) {
1786                 if(mesh->need_update && mesh->need_build_bvh()) {
1787                         num_bvh++;
1788                 }
1789         }
1790
1791         TaskPool pool;
1792
1793         i = 0;
1794         foreach(Mesh *mesh, scene->meshes) {
1795                 if(mesh->need_update) {
1796                         pool.push(function_bind(&Mesh::compute_bvh,
1797                                                 mesh,
1798                                                 dscene,
1799                                                 &scene->params,
1800                                                 &progress,
1801                                                 i,
1802                                                 num_bvh));
1803                         if(mesh->need_build_bvh()) {
1804                                 i++;
1805                         }
1806                 }
1807         }
1808
1809         TaskPool::Summary summary;
1810         pool.wait_work(&summary);
1811         VLOG(2) << "Objects BVH build pool statistics:\n"
1812                 << summary.full_report();
1813
1814         foreach(Shader *shader, scene->shaders) {
1815                 shader->need_update_attributes = false;
1816         }
1817
1818 #ifdef __OBJECT_MOTION__
1819         Scene::MotionType need_motion = scene->need_motion(device->info.advanced_shading);
1820         bool motion_blur = need_motion == Scene::MOTION_BLUR;
1821 #else
1822         bool motion_blur = false;
1823 #endif
1824
1825         /* Update objects. */
1826         vector<Object *> volume_objects;
1827         foreach(Object *object, scene->objects) {
1828                 object->compute_bounds(motion_blur);
1829         }
1830
1831         if(progress.get_cancel()) return;
1832
1833         device_update_bvh(device, dscene, scene, progress);
1834         if(progress.get_cancel()) return;
1835
1836         device_update_mesh(device, dscene, scene, false, progress);
1837         if(progress.get_cancel()) return;
1838
1839         need_update = false;
1840
1841         if(true_displacement_used) {
1842                 /* Re-tag flags for update, so they're re-evaluated
1843                  * for meshes with correct bounding boxes.
1844                  *
1845                  * This wouldn't cause wrong results, just true
1846                  * displacement might be less optimal ot calculate.
1847                  */
1848                 scene->object_manager->need_flags_update = old_need_object_flags_update;
1849         }
1850 }
1851
1852 void MeshManager::device_free(Device *device, DeviceScene *dscene)
1853 {
1854         device->tex_free(dscene->bvh_nodes);
1855         device->tex_free(dscene->bvh_leaf_nodes);
1856         device->tex_free(dscene->object_node);
1857         device->tex_free(dscene->prim_tri_verts);
1858         device->tex_free(dscene->prim_tri_index);
1859         device->tex_free(dscene->prim_type);
1860         device->tex_free(dscene->prim_visibility);
1861         device->tex_free(dscene->prim_index);
1862         device->tex_free(dscene->prim_object);
1863         device->tex_free(dscene->tri_shader);
1864         device->tex_free(dscene->tri_vnormal);
1865         device->tex_free(dscene->tri_vindex);
1866         device->tex_free(dscene->tri_patch);
1867         device->tex_free(dscene->tri_patch_uv);
1868         device->tex_free(dscene->curves);
1869         device->tex_free(dscene->curve_keys);
1870         device->tex_free(dscene->patches);
1871         device->tex_free(dscene->attributes_map);
1872         device->tex_free(dscene->attributes_float);
1873         device->tex_free(dscene->attributes_float3);
1874         device->tex_free(dscene->attributes_uchar4);
1875
1876         dscene->bvh_nodes.clear();
1877         dscene->object_node.clear();
1878         dscene->prim_tri_verts.clear();
1879         dscene->prim_tri_index.clear();
1880         dscene->prim_type.clear();
1881         dscene->prim_visibility.clear();
1882         dscene->prim_index.clear();
1883         dscene->prim_object.clear();
1884         dscene->tri_shader.clear();
1885         dscene->tri_vnormal.clear();
1886         dscene->tri_vindex.clear();
1887         dscene->tri_patch.clear();
1888         dscene->tri_patch_uv.clear();
1889         dscene->curves.clear();
1890         dscene->curve_keys.clear();
1891         dscene->patches.clear();
1892         dscene->attributes_map.clear();
1893         dscene->attributes_float.clear();
1894         dscene->attributes_float3.clear();
1895         dscene->attributes_uchar4.clear();
1896
1897 #ifdef WITH_OSL
1898         OSLGlobals *og = (OSLGlobals*)device->osl_memory();
1899
1900         if(og) {
1901                 og->object_name_map.clear();
1902                 og->attribute_map.clear();
1903                 og->object_names.clear();
1904         }
1905 #endif
1906 }
1907
1908 void MeshManager::tag_update(Scene *scene)
1909 {
1910         need_update = true;
1911         scene->object_manager->need_update = true;
1912 }
1913
1914 bool Mesh::need_attribute(Scene *scene, AttributeStandard std)
1915 {
1916         if(std == ATTR_STD_NONE)
1917                 return false;
1918         
1919         if(scene->need_global_attribute(std))
1920                 return true;
1921
1922         foreach(Shader *shader, used_shaders)
1923                 if(shader->attributes.find(std))
1924                         return true;
1925         
1926         return false;
1927 }
1928
1929 bool Mesh::need_attribute(Scene * /*scene*/, ustring name)
1930 {
1931         if(name == ustring())
1932                 return false;
1933
1934         foreach(Shader *shader, used_shaders)
1935                 if(shader->attributes.find(name))
1936                         return true;
1937         
1938         return false;
1939 }
1940
1941 CCL_NAMESPACE_END
1942