svn merge -r41655:41715 ^/trunk/blender --- this is the real cycles merge, needs...
[blender.git] / intern / cycles / subd / subd_split.cpp
1 /*
2  * Copyright 2011, Blender Foundation.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  */
18
19 #include "camera.h"
20 #include "mesh.h"
21
22 #include "subd_dice.h"
23 #include "subd_patch.h"
24 #include "subd_split.h"
25
26 #include "util_debug.h"
27 #include "util_math.h"
28 #include "util_types.h"
29
30 CCL_NAMESPACE_BEGIN
31
32 /* DiagSplit */
33
34 DiagSplit::DiagSplit()
35 {
36         test_steps = 3;
37         split_threshold = 1;
38         dicing_rate = 0.1f;
39         camera = NULL;
40 }
41
42 void DiagSplit::dispatch(QuadDice::SubPatch& sub, QuadDice::EdgeFactors& ef)
43 {
44         subpatches_quad.push_back(sub);
45         edgefactors_quad.push_back(ef);
46 }
47
48 void DiagSplit::dispatch(TriangleDice::SubPatch& sub, TriangleDice::EdgeFactors& ef)
49 {
50         subpatches_triangle.push_back(sub);
51         edgefactors_triangle.push_back(ef);
52 }
53
54 float3 DiagSplit::project(Patch *patch, float2 uv)
55 {
56         float3 P;
57
58         patch->eval(&P, NULL, NULL, uv.x, uv.y);
59         if(camera)
60                 P = transform(&camera->worldtoraster, P);
61
62         return P;
63 }
64
65 int DiagSplit::T(Patch *patch, float2 Pstart, float2 Pend)
66 {
67         float3 Plast = make_float3(0.0f, 0.0f, 0.0f);
68         float Lsum = 0.0f;
69         float Lmax = 0.0f;
70
71         for(int i = 0; i < test_steps; i++) {
72                 float t = i/(float)(test_steps-1);
73
74                 float3 P = project(patch, Pstart + t*(Pend - Pstart));
75
76                 if(i > 0) {
77                         float L = len(P - Plast);
78                         Lsum += L;
79                         Lmax = max(L, Lmax);
80                 }
81
82                 Plast = P;
83         }
84
85         int tmin = (int)ceil(Lsum/dicing_rate);
86         int tmax = (int)ceil((test_steps-1)*Lmax/dicing_rate); // XXX paper says N instead of N-1, seems wrong?
87
88         if(tmax - tmin > split_threshold)
89                 return DSPLIT_NON_UNIFORM;
90         
91         return tmax;
92 }
93
94 void DiagSplit::partition_edge(Patch *patch, float2 *P, int *t0, int *t1, float2 Pstart, float2 Pend, int t)
95 {
96         if(t == DSPLIT_NON_UNIFORM) {
97                 *P = (Pstart + Pend)*0.5f;
98                 *t0 = T(patch, Pstart, *P);
99                 *t1 = T(patch, *P, Pend);
100         }
101         else {
102                 int I = floor(t*0.5f);
103                 *P = interp(Pstart, Pend, (t == 0)? 0: I/(float)t); /* XXX is t faces or verts */
104                 *t0 = I;
105                 *t1 = t - I;
106         }
107 }
108
109 void DiagSplit::split(TriangleDice::SubPatch& sub, TriangleDice::EdgeFactors& ef, int depth)
110 {
111         assert(ef.tu == T(sub.patch, sub.Pv, sub.Pw));
112         assert(ef.tv == T(sub.patch, sub.Pw, sub.Pu));
113         assert(ef.tw == T(sub.patch, sub.Pu, sub.Pv));
114
115         if(depth == 0) {
116                 dispatch(sub, ef);
117                 return;
118         }
119
120         if(ef.tu == DSPLIT_NON_UNIFORM) {
121                 /* partition edges */
122                 TriangleDice::EdgeFactors ef0, ef1;
123                 float2 Psplit;
124
125                 partition_edge(sub.patch,
126                         &Psplit, &ef1.tu, &ef0.tu, sub.Pv, sub.Pw, ef.tu);
127
128                 /* split */
129                 int tsplit = T(sub.patch, sub.Pu, Psplit);
130                 ef0.tv = ef.tv;
131                 ef0.tw = tsplit;
132
133                 ef1.tv = tsplit;
134                 ef1.tw = ef.tw;
135
136                 /* create subpatches */
137                 TriangleDice::SubPatch sub0 = {sub.patch, sub.Pu, Psplit, sub.Pw};
138                 TriangleDice::SubPatch sub1 = {sub.patch, sub.Pu, sub.Pv, Psplit};
139
140                 split(sub0, ef0, depth+1);
141                 split(sub1, ef1, depth+1);
142         }
143         else if(ef.tv == DSPLIT_NON_UNIFORM) {
144                 /* partition edges */
145                 TriangleDice::EdgeFactors ef0, ef1;
146                 float2 Psplit;
147
148                 partition_edge(sub.patch,
149                         &Psplit, &ef1.tu, &ef0.tu, sub.Pw, sub.Pu, ef.tv);
150
151                 /* split */
152                 int tsplit = T(sub.patch, sub.Pv, Psplit);
153                 ef0.tv = ef.tw;
154                 ef0.tw = tsplit;
155
156                 ef1.tv = tsplit;
157                 ef1.tw = ef.tu;
158
159                 /* create subpatches */
160                 TriangleDice::SubPatch sub0 = {sub.patch, sub.Pv, Psplit, sub.Pu};
161                 TriangleDice::SubPatch sub1 = {sub.patch, sub.Pv, sub.Pw, Psplit};
162
163                 split(sub0, ef0, depth+1);
164                 split(sub1, ef1, depth+1);
165         }
166         else if(ef.tw == DSPLIT_NON_UNIFORM) {
167                 /* partition edges */
168                 TriangleDice::EdgeFactors ef0, ef1;
169                 float2 Psplit;
170
171                 partition_edge(sub.patch,
172                         &Psplit, &ef1.tu, &ef0.tu, sub.Pu, sub.Pv, ef.tw);
173
174                 /* split */
175                 int tsplit = T(sub.patch, sub.Pw, Psplit);
176                 ef0.tv = ef.tu;
177                 ef0.tw = tsplit;
178
179                 ef1.tv = tsplit;
180                 ef1.tw = ef.tv;
181
182                 /* create subpatches */
183                 TriangleDice::SubPatch sub0 = {sub.patch, sub.Pw, Psplit, sub.Pv};
184                 TriangleDice::SubPatch sub1 = {sub.patch, sub.Pw, sub.Pu, Psplit};
185
186                 split(sub0, ef0, depth+1);
187                 split(sub1, ef1, depth+1);
188         }
189         else
190                 dispatch(sub, ef);
191 }
192
193 void DiagSplit::split(QuadDice::SubPatch& sub, QuadDice::EdgeFactors& ef, int depth)
194 {
195         if((ef.tu0 == DSPLIT_NON_UNIFORM || ef.tu1 == DSPLIT_NON_UNIFORM)) {
196                 /* partition edges */
197                 QuadDice::EdgeFactors ef0, ef1;
198                 float2 Pu0, Pu1;
199
200                 partition_edge(sub.patch,
201                         &Pu0, &ef0.tu0, &ef1.tu0, sub.P00, sub.P10, ef.tu0);
202                 partition_edge(sub.patch,
203                         &Pu1, &ef0.tu1, &ef1.tu1, sub.P01, sub.P11, ef.tu1);
204
205                 /* split */
206                 int tsplit = T(sub.patch, Pu0, Pu1);
207                 ef0.tv0 = ef.tv0;
208                 ef0.tv1 = tsplit;
209
210                 ef1.tv0 = tsplit;
211                 ef1.tv1 = ef.tv1;
212
213                 /* create subpatches */
214                 QuadDice::SubPatch sub0 = {sub.patch, sub.P00, Pu0, sub.P01, Pu1};
215                 QuadDice::SubPatch sub1 = {sub.patch, Pu0, sub.P10, Pu1, sub.P11};
216
217                 split(sub0, ef0, depth+1);
218                 split(sub1, ef1, depth+1);
219         }
220         else if(ef.tv0 == DSPLIT_NON_UNIFORM || ef.tv1 == DSPLIT_NON_UNIFORM) {
221                 /* partition edges */
222                 QuadDice::EdgeFactors ef0, ef1;
223                 float2 Pv0, Pv1;
224
225                 partition_edge(sub.patch,
226                         &Pv0, &ef0.tv0, &ef1.tv0, sub.P00, sub.P01, ef.tv0);
227                 partition_edge(sub.patch,
228                         &Pv1, &ef0.tv1, &ef1.tv1, sub.P10, sub.P11, ef.tv1);
229
230                 /* split */
231                 int tsplit = T(sub.patch, Pv0, Pv1);
232                 ef0.tu0 = ef.tu0;
233                 ef0.tu1 = tsplit;
234
235                 ef1.tu0 = tsplit;
236                 ef1.tu1 = ef.tu1;
237
238                 /* create subpatches */
239                 QuadDice::SubPatch sub0 = {sub.patch, sub.P00, sub.P10, Pv0, Pv1};
240                 QuadDice::SubPatch sub1 = {sub.patch, Pv0, Pv1, sub.P01, sub.P11};
241
242                 split(sub0, ef0, depth+1);
243                 split(sub1, ef1, depth+1);
244         }
245         else
246                 dispatch(sub, ef);
247 }
248
249 void DiagSplit::split_triangle(Mesh *mesh, Patch *patch, int shader, bool smooth)
250 {
251         TriangleDice::SubPatch sub;
252         TriangleDice::EdgeFactors ef;
253
254         sub.patch = patch;
255         sub.Pu = make_float2(1.0f, 0.0f);
256         sub.Pv = make_float2(0.0f, 1.0f);
257         sub.Pw = make_float2(0.0f, 0.0f);
258
259         ef.tu = T(patch, sub.Pv, sub.Pw);
260         ef.tv = T(patch, sub.Pw, sub.Pu);
261         ef.tw = T(patch, sub.Pu, sub.Pv);
262
263         split(sub, ef);
264
265         TriangleDice dice(mesh, shader, smooth, dicing_rate);
266         dice.camera = camera;
267
268         for(size_t i = 0; i < subpatches_triangle.size(); i++) {
269                 TriangleDice::SubPatch& sub = subpatches_triangle[i];
270                 TriangleDice::EdgeFactors& ef = edgefactors_triangle[i];
271
272                 ef.tu = 4;
273                 ef.tv = 4;
274                 ef.tw = 4;
275
276                 ef.tu = max(ef.tu, 1);
277                 ef.tv = max(ef.tv, 1);
278                 ef.tw = max(ef.tw, 1);
279
280                 dice.dice(sub, ef);
281         }
282
283         subpatches_triangle.clear();
284         edgefactors_triangle.clear();
285 }
286
287 void DiagSplit::split_quad(Mesh *mesh, Patch *patch, int shader, bool smooth)
288 {
289         QuadDice::SubPatch sub;
290         QuadDice::EdgeFactors ef;
291
292         sub.patch = patch;
293         sub.P00 = make_float2(0.0f, 0.0f);
294         sub.P10 = make_float2(1.0f, 0.0f);
295         sub.P01 = make_float2(0.0f, 1.0f);
296         sub.P11 = make_float2(1.0f, 1.0f);
297
298         ef.tu0 = T(patch, sub.P00, sub.P10);
299         ef.tu1 = T(patch, sub.P01, sub.P11);
300         ef.tv0 = T(patch, sub.P00, sub.P01);
301         ef.tv1 = T(patch, sub.P10, sub.P11);
302
303         split(sub, ef);
304
305         QuadDice dice(mesh, shader, smooth, dicing_rate);
306         dice.camera = camera;
307
308         for(size_t i = 0; i < subpatches_quad.size(); i++) {
309                 QuadDice::SubPatch& sub = subpatches_quad[i];
310                 QuadDice::EdgeFactors& ef = edgefactors_quad[i];
311
312                 ef.tu0 = max(ef.tu0, 1);
313                 ef.tu1 = max(ef.tu1, 1);
314                 ef.tv0 = max(ef.tv0, 1);
315                 ef.tv1 = max(ef.tv1, 1);
316
317                 dice.dice(sub, ef);
318         }
319
320         subpatches_quad.clear();
321         edgefactors_quad.clear();
322 }
323
324 CCL_NAMESPACE_END
325