Merge branch 'master' into temp_remove_particles
[blender.git] / intern / cycles / subd / subd_split.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 #include "subd_split.h"
23
24 #include "util_debug.h"
25 #include "util_math.h"
26 #include "util_types.h"
27
28 CCL_NAMESPACE_BEGIN
29
30 /* DiagSplit */
31
32 DiagSplit::DiagSplit(const SubdParams& params_)
33 : params(params_)
34 {
35 }
36
37 void DiagSplit::dispatch(QuadDice::SubPatch& sub, QuadDice::EdgeFactors& ef)
38 {
39         subpatches_quad.push_back(sub);
40         edgefactors_quad.push_back(ef);
41 }
42
43 void DiagSplit::dispatch(TriangleDice::SubPatch& sub, TriangleDice::EdgeFactors& ef)
44 {
45         subpatches_triangle.push_back(sub);
46         edgefactors_triangle.push_back(ef);
47 }
48
49 float3 DiagSplit::to_world(Patch *patch, float2 uv)
50 {
51         float3 P;
52
53         patch->eval(&P, NULL, NULL, NULL, uv.x, uv.y);
54         if(params.camera)
55                 P = transform_point(&params.objecttoworld, P);
56
57         return P;
58 }
59
60 int DiagSplit::T(Patch *patch, float2 Pstart, float2 Pend)
61 {
62         float3 Plast = make_float3(0.0f, 0.0f, 0.0f);
63         float Lsum = 0.0f;
64         float Lmax = 0.0f;
65
66         for(int i = 0; i < params.test_steps; i++) {
67                 float t = i/(float)(params.test_steps-1);
68
69                 float3 P = to_world(patch, Pstart + t*(Pend - Pstart));
70
71                 if(i > 0) {
72                         float L;
73
74                         if(!params.camera) {
75                                 L = len(P - Plast);
76                         }
77                         else {
78                                 Camera* cam = params.camera;
79
80                                 float pixel_width = cam->world_to_raster_size((P + Plast) * 0.5f);
81                                 L = len(P - Plast) / pixel_width;
82                         }
83
84                         Lsum += L;
85                         Lmax = max(L, Lmax);
86                 }
87
88                 Plast = P;
89         }
90
91         int tmin = (int)ceil(Lsum/params.dicing_rate);
92         int tmax = (int)ceil((params.test_steps-1)*Lmax/params.dicing_rate); // XXX paper says N instead of N-1, seems wrong?
93
94         if(tmax - tmin > params.split_threshold)
95                 return DSPLIT_NON_UNIFORM;
96         
97         return tmax;
98 }
99
100 void DiagSplit::partition_edge(Patch *patch, float2 *P, int *t0, int *t1, float2 Pstart, float2 Pend, int t)
101 {
102         if(t == DSPLIT_NON_UNIFORM) {
103                 *P = (Pstart + Pend)*0.5f;
104                 *t0 = T(patch, Pstart, *P);
105                 *t1 = T(patch, *P, Pend);
106         }
107         else {
108                 int I = (int)floor((float)t*0.5f);
109                 *P = interp(Pstart, Pend, (t == 0)? 0: I/(float)t); /* XXX is t faces or verts */
110                 *t0 = I;
111                 *t1 = t - I;
112         }
113 }
114
115 void DiagSplit::split(TriangleDice::SubPatch& sub, TriangleDice::EdgeFactors& ef, int depth)
116 {
117         if(depth > 32) {
118                 /* We should never get here, but just in case end recursion safely. */
119                 ef.tu = 1;
120                 ef.tv = 1;
121                 ef.tw = 1;
122
123                 dispatch(sub, ef);
124                 return;
125         }
126
127         assert(ef.tu == T(sub.patch, sub.Pv, sub.Pw));
128         assert(ef.tv == T(sub.patch, sub.Pw, sub.Pu));
129         assert(ef.tw == T(sub.patch, sub.Pu, sub.Pv));
130
131         if(depth == 0) {
132                 dispatch(sub, ef);
133                 return;
134         }
135
136         if(ef.tu == DSPLIT_NON_UNIFORM) {
137                 /* partition edges */
138                 TriangleDice::EdgeFactors ef0, ef1;
139                 float2 Psplit;
140
141                 partition_edge(sub.patch,
142                         &Psplit, &ef1.tu, &ef0.tu, sub.Pv, sub.Pw, ef.tu);
143
144                 /* split */
145                 int tsplit = T(sub.patch, sub.Pu, Psplit);
146                 ef0.tv = ef.tv;
147                 ef0.tw = tsplit;
148
149                 ef1.tv = tsplit;
150                 ef1.tw = ef.tw;
151
152                 /* create subpatches */
153                 TriangleDice::SubPatch sub0 = {sub.patch, sub.Pu, Psplit, sub.Pw};
154                 TriangleDice::SubPatch sub1 = {sub.patch, sub.Pu, sub.Pv, Psplit};
155
156                 split(sub0, ef0, depth+1);
157                 split(sub1, ef1, depth+1);
158         }
159         else if(ef.tv == DSPLIT_NON_UNIFORM) {
160                 /* partition edges */
161                 TriangleDice::EdgeFactors ef0, ef1;
162                 float2 Psplit;
163
164                 partition_edge(sub.patch,
165                         &Psplit, &ef1.tu, &ef0.tu, sub.Pw, sub.Pu, ef.tv);
166
167                 /* split */
168                 int tsplit = T(sub.patch, sub.Pv, Psplit);
169                 ef0.tv = ef.tw;
170                 ef0.tw = tsplit;
171
172                 ef1.tv = tsplit;
173                 ef1.tw = ef.tu;
174
175                 /* create subpatches */
176                 TriangleDice::SubPatch sub0 = {sub.patch, sub.Pv, Psplit, sub.Pu};
177                 TriangleDice::SubPatch sub1 = {sub.patch, sub.Pv, sub.Pw, Psplit};
178
179                 split(sub0, ef0, depth+1);
180                 split(sub1, ef1, depth+1);
181         }
182         else if(ef.tw == DSPLIT_NON_UNIFORM) {
183                 /* partition edges */
184                 TriangleDice::EdgeFactors ef0, ef1;
185                 float2 Psplit;
186
187                 partition_edge(sub.patch,
188                         &Psplit, &ef1.tu, &ef0.tu, sub.Pu, sub.Pv, ef.tw);
189
190                 /* split */
191                 int tsplit = T(sub.patch, sub.Pw, Psplit);
192                 ef0.tv = ef.tu;
193                 ef0.tw = tsplit;
194
195                 ef1.tv = tsplit;
196                 ef1.tw = ef.tv;
197
198                 /* create subpatches */
199                 TriangleDice::SubPatch sub0 = {sub.patch, sub.Pw, Psplit, sub.Pv};
200                 TriangleDice::SubPatch sub1 = {sub.patch, sub.Pw, sub.Pu, Psplit};
201
202                 split(sub0, ef0, depth+1);
203                 split(sub1, ef1, depth+1);
204         }
205         else
206                 dispatch(sub, ef);
207 }
208
209 void DiagSplit::split(QuadDice::SubPatch& sub, QuadDice::EdgeFactors& ef, int depth)
210 {
211         if(depth > 32) {
212                 /* We should never get here, but just in case end recursion safely. */
213                 ef.tu0 = 1;
214                 ef.tu1 = 1;
215                 ef.tv0 = 1;
216                 ef.tv1 = 1;
217
218                 dispatch(sub, ef);
219                 return;
220         }
221
222         bool split_u = (ef.tu0 == DSPLIT_NON_UNIFORM || ef.tu1 == DSPLIT_NON_UNIFORM);
223         bool split_v = (ef.tv0 == DSPLIT_NON_UNIFORM || ef.tv1 == DSPLIT_NON_UNIFORM);
224
225         if(split_u && split_v) {
226                 split_u = depth % 2;
227         }
228
229         if(split_u) {
230                 /* partition edges */
231                 QuadDice::EdgeFactors ef0, ef1;
232                 float2 Pu0, Pu1;
233
234                 partition_edge(sub.patch,
235                         &Pu0, &ef0.tu0, &ef1.tu0, sub.P00, sub.P10, ef.tu0);
236                 partition_edge(sub.patch,
237                         &Pu1, &ef0.tu1, &ef1.tu1, sub.P01, sub.P11, ef.tu1);
238
239                 /* split */
240                 int tsplit = T(sub.patch, Pu0, Pu1);
241                 ef0.tv0 = ef.tv0;
242                 ef0.tv1 = tsplit;
243
244                 ef1.tv0 = tsplit;
245                 ef1.tv1 = ef.tv1;
246
247                 /* create subpatches */
248                 QuadDice::SubPatch sub0 = {sub.patch, sub.P00, Pu0, sub.P01, Pu1};
249                 QuadDice::SubPatch sub1 = {sub.patch, Pu0, sub.P10, Pu1, sub.P11};
250
251                 split(sub0, ef0, depth+1);
252                 split(sub1, ef1, depth+1);
253         }
254         else if(split_v) {
255                 /* partition edges */
256                 QuadDice::EdgeFactors ef0, ef1;
257                 float2 Pv0, Pv1;
258
259                 partition_edge(sub.patch,
260                         &Pv0, &ef0.tv0, &ef1.tv0, sub.P00, sub.P01, ef.tv0);
261                 partition_edge(sub.patch,
262                         &Pv1, &ef0.tv1, &ef1.tv1, sub.P10, sub.P11, ef.tv1);
263
264                 /* split */
265                 int tsplit = T(sub.patch, Pv0, Pv1);
266                 ef0.tu0 = ef.tu0;
267                 ef0.tu1 = tsplit;
268
269                 ef1.tu0 = tsplit;
270                 ef1.tu1 = ef.tu1;
271
272                 /* create subpatches */
273                 QuadDice::SubPatch sub0 = {sub.patch, sub.P00, sub.P10, Pv0, Pv1};
274                 QuadDice::SubPatch sub1 = {sub.patch, Pv0, Pv1, sub.P01, sub.P11};
275
276                 split(sub0, ef0, depth+1);
277                 split(sub1, ef1, depth+1);
278         }
279         else {
280                 dispatch(sub, ef);
281         }
282 }
283
284 void DiagSplit::split_triangle(Patch *patch)
285 {
286         TriangleDice::SubPatch sub_split;
287         TriangleDice::EdgeFactors ef_split;
288
289         sub_split.patch = patch;
290         sub_split.Pu = make_float2(1.0f, 0.0f);
291         sub_split.Pv = make_float2(0.0f, 1.0f);
292         sub_split.Pw = make_float2(0.0f, 0.0f);
293
294         ef_split.tu = T(patch, sub_split.Pv, sub_split.Pw);
295         ef_split.tv = T(patch, sub_split.Pw, sub_split.Pu);
296         ef_split.tw = T(patch, sub_split.Pu, sub_split.Pv);
297
298         split(sub_split, ef_split);
299
300         TriangleDice dice(params);
301
302         for(size_t i = 0; i < subpatches_triangle.size(); i++) {
303                 TriangleDice::SubPatch& sub = subpatches_triangle[i];
304                 TriangleDice::EdgeFactors& ef = edgefactors_triangle[i];
305
306                 ef.tu = 4;
307                 ef.tv = 4;
308                 ef.tw = 4;
309
310                 ef.tu = max(ef.tu, 1);
311                 ef.tv = max(ef.tv, 1);
312                 ef.tw = max(ef.tw, 1);
313
314                 dice.dice(sub, ef);
315         }
316
317         subpatches_triangle.clear();
318         edgefactors_triangle.clear();
319 }
320
321 void DiagSplit::split_quad(Patch *patch)
322 {
323         QuadDice::SubPatch sub_split;
324         QuadDice::EdgeFactors ef_split;
325
326         sub_split.patch = patch;
327         sub_split.P00 = make_float2(0.0f, 0.0f);
328         sub_split.P10 = make_float2(1.0f, 0.0f);
329         sub_split.P01 = make_float2(0.0f, 1.0f);
330         sub_split.P11 = make_float2(1.0f, 1.0f);
331
332         ef_split.tu0 = T(patch, sub_split.P00, sub_split.P10);
333         ef_split.tu1 = T(patch, sub_split.P01, sub_split.P11);
334         ef_split.tv0 = T(patch, sub_split.P00, sub_split.P01);
335         ef_split.tv1 = T(patch, sub_split.P10, sub_split.P11);
336
337         split(sub_split, ef_split);
338
339         QuadDice dice(params);
340
341         for(size_t i = 0; i < subpatches_quad.size(); i++) {
342                 QuadDice::SubPatch& sub = subpatches_quad[i];
343                 QuadDice::EdgeFactors& ef = edgefactors_quad[i];
344
345                 ef.tu0 = max(ef.tu0, 1);
346                 ef.tu1 = max(ef.tu1, 1);
347                 ef.tv0 = max(ef.tv0, 1);
348                 ef.tv1 = max(ef.tv1, 1);
349
350                 dice.dice(sub, ef);
351         }
352
353         subpatches_quad.clear();
354         edgefactors_quad.clear();
355 }
356
357 CCL_NAMESPACE_END
358