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