Cycles microdisplacement: add max subdivision setting
[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 static float2 right_to_equilateral(float2 P)
116 {
117         static const float2 A = make_float2(1.0f, 0.5f);
118         static const float2 B = make_float2(0.0f, sinf(M_PI_F/3.0f));
119         return make_float2(dot(P, A), dot(P, B));
120 }
121
122 static void limit_edge_factors(const TriangleDice::SubPatch& sub, TriangleDice::EdgeFactors& ef, int max_t)
123 {
124         float2 Pu = sub.Pu;
125         float2 Pv = sub.Pv;
126         float2 Pw = sub.Pw;
127
128         if(sub.patch->is_triangle()) {
129                 Pu = right_to_equilateral(Pu);
130                 Pv = right_to_equilateral(Pv);
131                 Pw = right_to_equilateral(Pw);
132         }
133
134         int tu = int(max_t * len(Pw - Pv));
135         int tv = int(max_t * len(Pw - Pu));
136         int tw = int(max_t * len(Pv - Pu));
137
138         ef.tu = tu <= 1 ? 1 : min(ef.tu, tu);
139         ef.tv = tv <= 1 ? 1 : min(ef.tv, tv);
140         ef.tw = tw <= 1 ? 1 : min(ef.tw, tw);
141 }
142
143 static void limit_edge_factors(const QuadDice::SubPatch& sub, QuadDice::EdgeFactors& ef, int max_t)
144 {
145         float2 P00 = sub.P00;
146         float2 P01 = sub.P01;
147         float2 P10 = sub.P10;
148         float2 P11 = sub.P11;
149
150         if(sub.patch->is_triangle()) {
151                 P00 = right_to_equilateral(P00);
152                 P01 = right_to_equilateral(P01);
153                 P10 = right_to_equilateral(P10);
154                 P11 = right_to_equilateral(P11);
155         }
156
157         int tu0 = int(max_t * len(P10 - P00));
158         int tu1 = int(max_t * len(P11 - P01));
159         int tv0 = int(max_t * len(P01 - P00));
160         int tv1 = int(max_t * len(P11 - P10));
161
162         ef.tu0 = tu0 <= 1 ? 1 : min(ef.tu0, tu0);
163         ef.tu1 = tu1 <= 1 ? 1 : min(ef.tu1, tu1);
164         ef.tv0 = tv0 <= 1 ? 1 : min(ef.tv0, tv0);
165         ef.tv1 = tv1 <= 1 ? 1 : min(ef.tv1, tv1);
166 }
167
168 void DiagSplit::split(TriangleDice::SubPatch& sub, TriangleDice::EdgeFactors& ef, int depth)
169 {
170         if(depth > 32) {
171                 /* We should never get here, but just in case end recursion safely. */
172                 ef.tu = 1;
173                 ef.tv = 1;
174                 ef.tw = 1;
175
176                 dispatch(sub, ef);
177                 return;
178         }
179
180         assert(ef.tu == T(sub.patch, sub.Pv, sub.Pw));
181         assert(ef.tv == T(sub.patch, sub.Pw, sub.Pu));
182         assert(ef.tw == T(sub.patch, sub.Pu, sub.Pv));
183
184         int non_uniform_count = int(ef.tu == DSPLIT_NON_UNIFORM) +
185                                 int(ef.tv == DSPLIT_NON_UNIFORM) +
186                             int(ef.tw == DSPLIT_NON_UNIFORM);
187
188         switch(non_uniform_count) {
189                 case 1: {
190                         /* TODO(mai): one edge is non-uniform, split into two triangles */
191                         // fallthru
192                 }
193                 case 2: {
194                         /* TODO(mai): two edges are non-uniform, split into triangle and quad */
195                         // fallthru
196                 }
197                 case 3: {
198                         /* all three edges are non-uniform, split into three quads */
199
200                         /* partition edges */
201                         QuadDice::EdgeFactors ef0, ef1, ef2;
202                         float2 Pu, Pv, Pw, Pcenter;
203
204                         partition_edge(sub.patch, &Pu, &ef1.tv0, &ef2.tu0, sub.Pw, sub.Pv, ef.tu);
205                         partition_edge(sub.patch, &Pv, &ef0.tv0, &ef1.tu0, sub.Pu, sub.Pw, ef.tv);
206                         partition_edge(sub.patch, &Pw, &ef2.tv0, &ef0.tu0, sub.Pv, sub.Pu, ef.tw);
207                         Pcenter = (Pu + Pv + Pw) * (1.0f / 3.0f);
208
209                         /* split */
210                         int tsplit01 = T(sub.patch, Pv, Pcenter);
211                         int tsplit12 = T(sub.patch, Pu, Pcenter);
212                         int tsplit20 = T(sub.patch, Pw, Pcenter);
213
214                         ef0.tu1 = tsplit01;
215                         ef0.tv1 = tsplit20;
216
217                         ef1.tu1 = tsplit12;
218                         ef1.tv1 = tsplit01;
219
220                         ef2.tu1 = tsplit20;
221                         ef2.tv1 = tsplit12;
222
223                         /* create subpatches */
224                         QuadDice::SubPatch sub0 = {sub.patch, sub.Pu, Pw, Pv, Pcenter};
225                         QuadDice::SubPatch sub1 = {sub.patch, sub.Pw, Pv, Pu, Pcenter};
226                         QuadDice::SubPatch sub2 = {sub.patch, sub.Pv, Pu, Pw, Pcenter};
227
228                         limit_edge_factors(sub0, ef0, 1 << params.max_level);
229                         limit_edge_factors(sub1, ef1, 1 << params.max_level);
230                         limit_edge_factors(sub2, ef2, 1 << params.max_level);
231
232                         split(sub0, ef0, depth+1);
233                         split(sub1, ef1, depth+1);
234                         split(sub2, ef2, depth+1);
235
236                         break;
237                 }
238                 default: {
239                         /* all edges uniform, no splitting needed */
240                         dispatch(sub, ef);
241                         break;
242                 }
243         }
244 }
245
246 void DiagSplit::split(QuadDice::SubPatch& sub, QuadDice::EdgeFactors& ef, int depth)
247 {
248         if(depth > 32) {
249                 /* We should never get here, but just in case end recursion safely. */
250                 ef.tu0 = 1;
251                 ef.tu1 = 1;
252                 ef.tv0 = 1;
253                 ef.tv1 = 1;
254
255                 dispatch(sub, ef);
256                 return;
257         }
258
259         bool split_u = (ef.tu0 == DSPLIT_NON_UNIFORM || ef.tu1 == DSPLIT_NON_UNIFORM);
260         bool split_v = (ef.tv0 == DSPLIT_NON_UNIFORM || ef.tv1 == DSPLIT_NON_UNIFORM);
261
262         if(split_u && split_v) {
263                 split_u = depth % 2;
264         }
265
266         if(split_u) {
267                 /* partition edges */
268                 QuadDice::EdgeFactors ef0, ef1;
269                 float2 Pu0, Pu1;
270
271                 partition_edge(sub.patch,
272                         &Pu0, &ef0.tu0, &ef1.tu0, sub.P00, sub.P10, ef.tu0);
273                 partition_edge(sub.patch,
274                         &Pu1, &ef0.tu1, &ef1.tu1, sub.P01, sub.P11, ef.tu1);
275
276                 /* split */
277                 int tsplit = T(sub.patch, Pu0, Pu1);
278                 ef0.tv0 = ef.tv0;
279                 ef0.tv1 = tsplit;
280
281                 ef1.tv0 = tsplit;
282                 ef1.tv1 = ef.tv1;
283
284                 /* create subpatches */
285                 QuadDice::SubPatch sub0 = {sub.patch, sub.P00, Pu0, sub.P01, Pu1};
286                 QuadDice::SubPatch sub1 = {sub.patch, Pu0, sub.P10, Pu1, sub.P11};
287
288                 limit_edge_factors(sub0, ef0, 1 << params.max_level);
289                 limit_edge_factors(sub1, ef1, 1 << params.max_level);
290
291                 split(sub0, ef0, depth+1);
292                 split(sub1, ef1, depth+1);
293         }
294         else if(split_v) {
295                 /* partition edges */
296                 QuadDice::EdgeFactors ef0, ef1;
297                 float2 Pv0, Pv1;
298
299                 partition_edge(sub.patch,
300                         &Pv0, &ef0.tv0, &ef1.tv0, sub.P00, sub.P01, ef.tv0);
301                 partition_edge(sub.patch,
302                         &Pv1, &ef0.tv1, &ef1.tv1, sub.P10, sub.P11, ef.tv1);
303
304                 /* split */
305                 int tsplit = T(sub.patch, Pv0, Pv1);
306                 ef0.tu0 = ef.tu0;
307                 ef0.tu1 = tsplit;
308
309                 ef1.tu0 = tsplit;
310                 ef1.tu1 = ef.tu1;
311
312                 /* create subpatches */
313                 QuadDice::SubPatch sub0 = {sub.patch, sub.P00, sub.P10, Pv0, Pv1};
314                 QuadDice::SubPatch sub1 = {sub.patch, Pv0, Pv1, sub.P01, sub.P11};
315
316                 limit_edge_factors(sub0, ef0, 1 << params.max_level);
317                 limit_edge_factors(sub1, ef1, 1 << params.max_level);
318
319                 split(sub0, ef0, depth+1);
320                 split(sub1, ef1, depth+1);
321         }
322         else {
323                 dispatch(sub, ef);
324         }
325 }
326
327 void DiagSplit::split_triangle(Patch *patch)
328 {
329         TriangleDice::SubPatch sub_split;
330         TriangleDice::EdgeFactors ef_split;
331
332         sub_split.patch = patch;
333         sub_split.Pu = make_float2(1.0f, 0.0f);
334         sub_split.Pv = make_float2(0.0f, 1.0f);
335         sub_split.Pw = make_float2(0.0f, 0.0f);
336
337         ef_split.tu = T(patch, sub_split.Pv, sub_split.Pw);
338         ef_split.tv = T(patch, sub_split.Pw, sub_split.Pu);
339         ef_split.tw = T(patch, sub_split.Pu, sub_split.Pv);
340
341         limit_edge_factors(sub_split, ef_split, 1 << params.max_level);
342
343         split(sub_split, ef_split);
344
345         TriangleDice dice(params);
346
347         for(size_t i = 0; i < subpatches_triangle.size(); i++) {
348                 TriangleDice::SubPatch& sub = subpatches_triangle[i];
349                 TriangleDice::EdgeFactors& ef = edgefactors_triangle[i];
350
351                 ef.tu = max(ef.tu, 1);
352                 ef.tv = max(ef.tv, 1);
353                 ef.tw = max(ef.tw, 1);
354
355                 dice.dice(sub, ef);
356         }
357
358         subpatches_triangle.clear();
359         edgefactors_triangle.clear();
360
361         /* triangle might be split into quads so dice quad subpatches as well */
362         QuadDice qdice(params);
363
364         for(size_t i = 0; i < subpatches_quad.size(); i++) {
365                 QuadDice::SubPatch& sub = subpatches_quad[i];
366                 QuadDice::EdgeFactors& ef = edgefactors_quad[i];
367
368                 ef.tu0 = max(ef.tu0, 1);
369                 ef.tu1 = max(ef.tu1, 1);
370                 ef.tv0 = max(ef.tv0, 1);
371                 ef.tv1 = max(ef.tv1, 1);
372
373                 qdice.dice(sub, ef);
374         }
375
376         subpatches_quad.clear();
377         edgefactors_quad.clear();
378 }
379
380 void DiagSplit::split_quad(Patch *patch)
381 {
382         QuadDice::SubPatch sub_split;
383         QuadDice::EdgeFactors ef_split;
384
385         sub_split.patch = patch;
386         sub_split.P00 = make_float2(0.0f, 0.0f);
387         sub_split.P10 = make_float2(1.0f, 0.0f);
388         sub_split.P01 = make_float2(0.0f, 1.0f);
389         sub_split.P11 = make_float2(1.0f, 1.0f);
390
391         ef_split.tu0 = T(patch, sub_split.P00, sub_split.P10);
392         ef_split.tu1 = T(patch, sub_split.P01, sub_split.P11);
393         ef_split.tv0 = T(patch, sub_split.P00, sub_split.P01);
394         ef_split.tv1 = T(patch, sub_split.P10, sub_split.P11);
395
396         limit_edge_factors(sub_split, ef_split, 1 << params.max_level);
397
398         split(sub_split, ef_split);
399
400         QuadDice dice(params);
401
402         for(size_t i = 0; i < subpatches_quad.size(); i++) {
403                 QuadDice::SubPatch& sub = subpatches_quad[i];
404                 QuadDice::EdgeFactors& ef = edgefactors_quad[i];
405
406                 ef.tu0 = max(ef.tu0, 1);
407                 ef.tu1 = max(ef.tu1, 1);
408                 ef.tv0 = max(ef.tv0, 1);
409                 ef.tv1 = max(ef.tv1, 1);
410
411                 dice.dice(sub, ef);
412         }
413
414         subpatches_quad.clear();
415         edgefactors_quad.clear();
416 }
417
418 CCL_NAMESPACE_END
419