Cuda use streams and async to avoid busywaiting
[blender.git] / intern / cycles / subd / subd_dice.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 "camera.h"
18 #include "mesh.h"
19
20 #include "subd_dice.h"
21 #include "subd_patch.h"
22
23 #include "util_debug.h"
24
25 CCL_NAMESPACE_BEGIN
26
27 /* EdgeDice Base */
28
29 EdgeDice::EdgeDice(const SubdParams& params_)
30 : params(params_)
31 {
32         mesh_P = NULL;
33         mesh_N = NULL;
34         vert_offset = 0;
35
36         params.mesh->attributes.add(ATTR_STD_VERTEX_NORMAL);
37
38         if(params.ptex) {
39                 params.mesh->attributes.add(ATTR_STD_PTEX_UV);
40                 params.mesh->attributes.add(ATTR_STD_PTEX_FACE_ID);
41         }
42 }
43
44 void EdgeDice::reserve(int num_verts, int num_tris)
45 {
46         Mesh *mesh = params.mesh;
47
48         vert_offset = mesh->verts.size();
49         tri_offset = mesh->triangles.size();
50
51         mesh->reserve(vert_offset + num_verts, tri_offset + num_tris, 0, 0);
52
53         Attribute *attr_vN = mesh->attributes.add(ATTR_STD_VERTEX_NORMAL);
54
55         mesh_P = &mesh->verts[0];
56         mesh_N = attr_vN->data_float3();
57 }
58
59 int EdgeDice::add_vert(Patch *patch, float2 uv)
60 {
61         float3 P, N, dPdu, dPdv;
62
63         patch->eval(&P, &dPdu, &dPdv, uv.x, uv.y);
64         N = normalize(cross(dPdu, dPdv));
65
66         assert(vert_offset < params.mesh->verts.size());
67
68         mesh_P[vert_offset] = P;
69         mesh_N[vert_offset] = N;
70
71         if(params.ptex) {
72                 Attribute *attr_ptex_uv = params.mesh->attributes.add(ATTR_STD_PTEX_UV);
73                 params.mesh->attributes.reserve();
74
75                 float3 *ptex_uv = attr_ptex_uv->data_float3();
76                 ptex_uv[vert_offset] = make_float3(uv.x, uv.y, 0.0f);
77         }
78
79         return vert_offset++;
80 }
81
82 void EdgeDice::add_triangle(Patch *patch, int v0, int v1, int v2)
83 {
84         params.mesh->add_triangle(v0, v1, v2, params.shader, params.smooth);
85
86         if(params.ptex) {
87                 Attribute *attr_ptex_face_id = params.mesh->attributes.add(ATTR_STD_PTEX_FACE_ID);
88                 params.mesh->attributes.reserve();
89
90                 float *ptex_face_id = attr_ptex_face_id->data_float();
91                 ptex_face_id[tri_offset] = (float)patch->ptex_face_id();
92         }
93
94         tri_offset++;
95 }
96
97 void EdgeDice::stitch_triangles(Patch *patch, vector<int>& outer, vector<int>& inner)
98 {
99         if(inner.size() == 0 || outer.size() == 0)
100                 return; // XXX avoid crashes for Mu or Mv == 1, missing polygons
101
102         /* stitch together two arrays of verts with triangles. at each step,
103          * we compare using the next verts on both sides, to find the split
104          * direction with the smallest diagonal, and use that in order to keep
105          * the triangle shape reasonable. */
106         for(size_t i = 0, j = 0; i+1 < inner.size() || j+1 < outer.size();) {
107                 int v0, v1, v2;
108
109                 v0 = inner[i];
110                 v1 = outer[j];
111
112                 if(j+1 == outer.size()) {
113                         v2 = inner[++i];
114                 }
115                 else if(i+1 == inner.size()) {
116                         v2 = outer[++j];
117                 }
118                 else {
119                         /* length of diagonals */
120                         float len1 = len(mesh_P[inner[i]] - mesh_P[outer[j+1]]);
121                         float len2 = len(mesh_P[outer[j]] - mesh_P[inner[i+1]]);
122
123                         /* use smallest diagonal */
124                         if(len1 < len2)
125                                 v2 = outer[++j];
126                         else
127                                 v2 = inner[++i];
128                 }
129
130                 add_triangle(patch, v0, v1, v2);
131         }
132 }
133
134 /* QuadDice */
135
136 QuadDice::QuadDice(const SubdParams& params_)
137 : EdgeDice(params_)
138 {
139 }
140
141 void QuadDice::reserve(EdgeFactors& ef, int Mu, int Mv)
142 {
143         /* XXX need to make this also work for edge factor 0 and 1 */
144         int num_verts = (ef.tu0 + ef.tu1 + ef.tv0 + ef.tv1) + (Mu - 1)*(Mv - 1);
145         int num_tris = 0;
146         EdgeDice::reserve(num_verts, num_tris);
147 }
148
149 float2 QuadDice::map_uv(SubPatch& sub, float u, float v)
150 {
151         /* map UV from subpatch to patch parametric coordinates */
152         float2 d0 = interp(sub.P00, sub.P01, v);
153         float2 d1 = interp(sub.P10, sub.P11, v);
154         return interp(d0, d1, u);
155 }
156
157 float3 QuadDice::eval_projected(SubPatch& sub, float u, float v)
158 {
159         float2 uv = map_uv(sub, u, v);
160         float3 P;
161
162         sub.patch->eval(&P, NULL, NULL, uv.x, uv.y);
163         if(params.camera)
164                 P = transform_perspective(&params.camera->worldtoraster, P);
165
166         return P;
167 }
168
169 int QuadDice::add_vert(SubPatch& sub, float u, float v)
170 {
171         return EdgeDice::add_vert(sub.patch, map_uv(sub, u, v));
172 }
173
174 void QuadDice::add_side_u(SubPatch& sub,
175         vector<int>& outer, vector<int>& inner,
176         int Mu, int Mv, int tu, int side, int offset)
177 {
178         outer.clear();
179         inner.clear();
180
181         /* set verts on the edge of the patch */
182         outer.push_back(offset + ((side)? 2: 0));
183
184         for(int i = 1; i < tu; i++) {
185                 float u = i/(float)tu;
186                 float v = (side)? 1.0f: 0.0f;
187
188                 outer.push_back(add_vert(sub, u, v));
189         }
190
191         outer.push_back(offset + ((side)? 3: 1));
192
193         /* set verts on the edge of the inner grid */
194         for(int i = 0; i < Mu-1; i++) {
195                 int j = (side)? Mv-1-1: 0;
196                 inner.push_back(offset + 4 + i + j*(Mu-1));
197         }
198 }
199
200 void QuadDice::add_side_v(SubPatch& sub,
201         vector<int>& outer, vector<int>& inner,
202         int Mu, int Mv, int tv, int side, int offset)
203 {
204         outer.clear();
205         inner.clear();
206
207         /* set verts on the edge of the patch */
208         outer.push_back(offset + ((side)? 1: 0));
209
210         for(int j = 1; j < tv; j++) {
211                 float u = (side)? 1.0f: 0.0f;
212                 float v = j/(float)tv;
213
214                 outer.push_back(add_vert(sub, u, v));
215         }
216
217         outer.push_back(offset + ((side)? 3: 2));
218
219         /* set verts on the edge of the inner grid */
220         for(int j = 0; j < Mv-1; j++) {
221                 int i = (side)? Mu-1-1: 0;
222                 inner.push_back(offset + 4 + i + j*(Mu-1));
223         }
224 }
225
226 float QuadDice::quad_area(const float3& a, const float3& b, const float3& c, const float3& d)
227 {
228         return triangle_area(a, b, d) + triangle_area(a, d, c);
229 }
230
231 float QuadDice::scale_factor(SubPatch& sub, EdgeFactors& ef, int Mu, int Mv)
232 {
233         /* estimate area as 4x largest of 4 quads */
234         float3 P[3][3];
235
236         for(int i = 0; i < 3; i++)
237                 for(int j = 0; j < 3; j++)
238                         P[i][j] = eval_projected(sub, i*0.5f, j*0.5f);
239
240         float A1 = quad_area(P[0][0], P[1][0], P[0][1], P[1][1]);
241         float A2 = quad_area(P[1][0], P[2][0], P[1][1], P[2][1]);
242         float A3 = quad_area(P[0][1], P[1][1], P[0][2], P[1][2]);
243         float A4 = quad_area(P[1][1], P[2][1], P[1][2], P[2][2]);
244         float Apatch = max(A1, max(A2, max(A3, A4)))*4.0f;
245
246         /* solve for scaling factor */
247         float Atri = params.dicing_rate*params.dicing_rate*0.5f;
248         float Ntris = Apatch/Atri;
249
250         // XXX does the -sqrt solution matter
251         // XXX max(D, 0.0) is highly suspicious, need to test cases
252         // where D goes negative
253         float N = 0.5f*(Ntris - (ef.tu0 + ef.tu1 + ef.tv0 + ef.tv1));
254         float D = 4.0f*N*Mu*Mv + (Mu + Mv)*(Mu + Mv);
255         float S = (Mu + Mv + sqrtf(max(D, 0.0f)))/(2*Mu*Mv);
256
257         return S;
258 }
259
260 void QuadDice::add_corners(SubPatch& sub)
261 {
262         /* add verts for patch corners */
263         if(sub.patch->is_triangle()) {
264                 add_vert(sub, 0.0f, 0.0f);
265                 add_vert(sub, 1.0f, 0.0f);
266                 add_vert(sub, 0.0f, 1.0f);
267         }
268         else {
269                 add_vert(sub, 0.0f, 0.0f);
270                 add_vert(sub, 1.0f, 0.0f);
271                 add_vert(sub, 0.0f, 1.0f);
272                 add_vert(sub, 1.0f, 1.0f);
273         }
274 }
275
276 void QuadDice::add_grid(SubPatch& sub, int Mu, int Mv, int offset)
277 {
278         /* create inner grid */
279         float du = 1.0f/(float)Mu;
280         float dv = 1.0f/(float)Mv;
281
282         for(int j = 1; j < Mv; j++) {
283                 for(int i = 1; i < Mu; i++) {
284                         float u = i*du;
285                         float v = j*dv;
286
287                         add_vert(sub, u, v);
288
289                         if(i < Mu-1 && j < Mv-1) {
290                                 int i1 = offset + 4 + (i-1) + (j-1)*(Mu-1);
291                                 int i2 = offset + 4 + i + (j-1)*(Mu-1);
292                                 int i3 = offset + 4 + i + j*(Mu-1);
293                                 int i4 = offset + 4 + (i-1) + j*(Mu-1);
294
295                                 add_triangle(sub.patch, i1, i2, i3);
296                                 add_triangle(sub.patch, i1, i3, i4);
297                         }
298                 }
299         }
300 }
301
302 void QuadDice::dice(SubPatch& sub, EdgeFactors& ef)
303 {
304         /* compute inner grid size with scale factor */
305         int Mu = max(ef.tu0, ef.tu1);
306         int Mv = max(ef.tv0, ef.tv1);
307
308         float S = scale_factor(sub, ef, Mu, Mv);
309         Mu = max((int)ceil(S*Mu), 2); // XXX handle 0 & 1?
310         Mv = max((int)ceil(S*Mv), 2); // XXX handle 0 & 1?
311
312         /* reserve space for new verts */
313         int offset = params.mesh->verts.size();
314         reserve(ef, Mu, Mv);
315
316         /* corners and inner grid */
317         add_corners(sub);
318         add_grid(sub, Mu, Mv, offset);
319
320         /* bottom side */
321         vector<int> outer, inner;
322
323         add_side_u(sub, outer, inner, Mu, Mv, ef.tu0, 0, offset);
324         stitch_triangles(sub.patch, outer, inner);
325
326         /* top side */
327         add_side_u(sub, outer, inner, Mu, Mv, ef.tu1, 1, offset);
328         stitch_triangles(sub.patch, inner, outer);
329
330         /* left side */
331         add_side_v(sub, outer, inner, Mu, Mv, ef.tv0, 0, offset);
332         stitch_triangles(sub.patch, inner, outer);
333
334         /* right side */
335         add_side_v(sub, outer, inner, Mu, Mv, ef.tv1, 1, offset);
336         stitch_triangles(sub.patch, outer, inner);
337
338         assert(vert_offset == params.mesh->verts.size());
339 }
340
341 /* TriangleDice */
342
343 TriangleDice::TriangleDice(const SubdParams& params_)
344 : EdgeDice(params_)
345 {
346 }
347
348 void TriangleDice::reserve(EdgeFactors& ef, int M)
349 {
350         int num_verts = ef.tu + ef.tv + ef.tw;
351
352         for(int m = M-2; m > 0; m -= 2)
353                 num_verts += 3 + (m-1)*3;
354         
355         if(!(M & 1))
356                 num_verts++;
357         
358         EdgeDice::reserve(num_verts, 0);
359 }
360
361 float2 TriangleDice::map_uv(SubPatch& sub, float2 uv)
362 {
363         /* map UV from subpatch to patch parametric coordinates */
364         return uv.x*sub.Pu + uv.y*sub.Pv + (1.0f - uv.x - uv.y)*sub.Pw;
365 }
366
367 int TriangleDice::add_vert(SubPatch& sub, float2 uv)
368 {
369         return EdgeDice::add_vert(sub.patch, map_uv(sub, uv));
370 }
371
372 void TriangleDice::add_grid(SubPatch& sub, EdgeFactors& ef, int M)
373 {
374         // XXX normals are flipped, why?
375
376         /* grid is constructed starting from the outside edges, and adding
377          * progressively smaller inner triangles that connected to the outer
378          * one, until M = 1 or 2, the we fill up the last part. */
379         vector<int> outer_u, outer_v, outer_w;
380         int m;
381
382         /* add outer corners vertices */
383         {
384                 float2 p_u = make_float2(1.0f, 0.0f);
385                 float2 p_v = make_float2(0.0f, 1.0f);
386                 float2 p_w = make_float2(0.0f, 0.0f);
387
388                 int corner_u = add_vert(sub, p_u);
389                 int corner_v = add_vert(sub, p_v);
390                 int corner_w = add_vert(sub, p_w);
391
392                 outer_u.push_back(corner_v);
393                 outer_v.push_back(corner_w);
394                 outer_w.push_back(corner_u);
395
396                 for(int i = 1; i < ef.tu; i++)
397                         outer_u.push_back(add_vert(sub, interp(p_v, p_w, i/(float)ef.tu)));
398                 for(int i = 1; i < ef.tv; i++)
399                         outer_v.push_back(add_vert(sub, interp(p_w, p_u, i/(float)ef.tv)));
400                 for(int i = 1; i < ef.tw; i++)
401                         outer_w.push_back(add_vert(sub, interp(p_u, p_v, i/(float)ef.tw)));
402
403                 outer_u.push_back(corner_w);
404                 outer_v.push_back(corner_u);
405                 outer_w.push_back(corner_v);
406         }
407
408         for(m = M-2; m > 0; m -= 2) {
409                 vector<int> inner_u, inner_v, inner_w;
410
411                 const float t0 = m / (float)M;
412                 float2 center = make_float2(1.0f/3.0f, 1.0f/3.0f);
413
414                 /* 3 corner vertices */
415                 float2 p_u = interp(center, make_float2(1.0f, 0.0f), t0);
416                 float2 p_v = interp(center, make_float2(0.0f, 1.0f), t0);
417                 float2 p_w = interp(center, make_float2(0.0f, 0.0f), t0);
418
419                 int corner_u = add_vert(sub, p_u);
420                 int corner_v = add_vert(sub, p_v);
421                 int corner_w = add_vert(sub, p_w);
422
423                 /* construct array of vertex indices for each side */
424                 inner_u.push_back(corner_v);
425                 inner_v.push_back(corner_w);
426                 inner_w.push_back(corner_u);
427
428                 for(int i = 1; i < m; i++) {
429                         /* add vertices between corners */
430                         const float t1 = i / (float)m;
431
432                         inner_u.push_back(add_vert(sub, interp(p_v, p_w, t1)));
433                         inner_v.push_back(add_vert(sub, interp(p_w, p_u, t1)));
434                         inner_w.push_back(add_vert(sub, interp(p_u, p_v, t1)));
435                 }
436
437                 inner_u.push_back(corner_w);
438                 inner_v.push_back(corner_u);
439                 inner_w.push_back(corner_v);
440
441                 /* stitch together inner/outer with triangles */
442                 stitch_triangles(sub.patch, outer_u, inner_u);
443                 stitch_triangles(sub.patch, outer_v, inner_v);
444                 stitch_triangles(sub.patch, outer_w, inner_w);
445
446                 outer_u = inner_u;
447                 outer_v = inner_v;
448                 outer_w = inner_w;
449         }
450
451         /* fill up last part */
452         if(m == -1) {
453                 /* single triangle */
454                 add_triangle(sub.patch, outer_w[0], outer_u[0], outer_v[0]);
455         }
456         else {
457                 /* center vertex + 6 triangles */
458                 int center = add_vert(sub, make_float2(1.0f/3.0f, 1.0f/3.0f));
459
460                 add_triangle(sub.patch, outer_w[0], outer_w[1], center);
461                 add_triangle(sub.patch, outer_w[1], outer_w[2], center);
462                 add_triangle(sub.patch, outer_u[0], outer_u[1], center);
463                 add_triangle(sub.patch, outer_u[1], outer_u[2], center);
464                 add_triangle(sub.patch, outer_v[0], outer_v[1], center);
465                 add_triangle(sub.patch, outer_v[1], outer_v[2], center);
466         }
467 }
468
469 void TriangleDice::dice(SubPatch& sub, EdgeFactors& ef)
470 {
471         /* todo: handle 2 1 1 resolution */
472         int M = max(ef.tu, max(ef.tv, ef.tw));
473
474         reserve(ef, M);
475         add_grid(sub, ef, M);
476
477         assert(vert_offset == params.mesh->verts.size());
478 }
479
480 CCL_NAMESPACE_END
481