fae815901ee06fdb2c1f65aa200a173e4997e752
[blender-staging.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 "render/camera.h"
18 #include "render/mesh.h"
19
20 #include "subd/subd_dice.h"
21 #include "subd/subd_patch.h"
22
23 #include "util/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)
45 {
46         Mesh *mesh = params.mesh;
47
48         vert_offset = mesh->verts.size();
49         tri_offset = mesh->num_triangles();
50
51         /* todo: optimize so we can reserve in advance, this is like push_back_slow() */
52         if(vert_offset + num_verts > mesh->verts.capacity()) {
53                 mesh->reserve_mesh(size_t((vert_offset + num_verts) * 1.2), mesh->num_triangles());
54         }
55
56         mesh->resize_mesh(vert_offset + num_verts, tri_offset);
57
58         Attribute *attr_vN = mesh->attributes.add(ATTR_STD_VERTEX_NORMAL);
59
60         mesh_P = mesh->verts.data();
61         mesh_N = attr_vN->data_float3();
62 }
63
64 int EdgeDice::add_vert(Patch *patch, float2 uv)
65 {
66         float3 P, N;
67
68         patch->eval(&P, NULL, NULL, &N, uv.x, uv.y);
69
70         assert(vert_offset < params.mesh->verts.size());
71
72         mesh_P[vert_offset] = P;
73         mesh_N[vert_offset] = N;
74         params.mesh->vert_patch_uv[vert_offset] = make_float2(uv.x, uv.y);
75
76         if(params.ptex) {
77                 Attribute *attr_ptex_uv = params.mesh->attributes.add(ATTR_STD_PTEX_UV);
78                 params.mesh->attributes.resize();
79
80                 float3 *ptex_uv = attr_ptex_uv->data_float3();
81                 ptex_uv[vert_offset] = make_float3(uv.x, uv.y, 0.0f);
82         }
83
84         params.mesh->num_subd_verts++;
85
86         return vert_offset++;
87 }
88
89 void EdgeDice::add_triangle(Patch *patch, int v0, int v1, int v2)
90 {
91         Mesh *mesh = params.mesh;
92
93         /* todo: optimize so we can reserve in advance, this is like push_back_slow() */
94         if(mesh->triangles.size() == mesh->triangles.capacity())
95                 mesh->reserve_mesh(mesh->verts.size(), size_t(max(mesh->num_triangles() + 1, 1) * 1.2));
96
97         mesh->add_triangle(v0, v1, v2, patch->shader, true);
98         params.mesh->triangle_patch[params.mesh->num_triangles()-1] = patch->patch_index;
99
100         if(params.ptex) {
101                 Attribute *attr_ptex_face_id = params.mesh->attributes.add(ATTR_STD_PTEX_FACE_ID);
102                 params.mesh->attributes.resize();
103
104                 float *ptex_face_id = attr_ptex_face_id->data_float();
105                 ptex_face_id[tri_offset] = (float)patch->ptex_face_id();
106         }
107
108         tri_offset++;
109 }
110
111 void EdgeDice::stitch_triangles(Patch *patch, vector<int>& outer, vector<int>& inner)
112 {
113         if(inner.size() == 0 || outer.size() == 0)
114                 return; // XXX avoid crashes for Mu or Mv == 1, missing polygons
115
116         /* stitch together two arrays of verts with triangles. at each step,
117          * we compare using the next verts on both sides, to find the split
118          * direction with the smallest diagonal, and use that in order to keep
119          * the triangle shape reasonable. */
120         for(size_t i = 0, j = 0; i+1 < inner.size() || j+1 < outer.size();) {
121                 int v0, v1, v2;
122
123                 v0 = inner[i];
124                 v1 = outer[j];
125
126                 if(j+1 == outer.size()) {
127                         v2 = inner[++i];
128                 }
129                 else if(i+1 == inner.size()) {
130                         v2 = outer[++j];
131                 }
132                 else {
133                         /* length of diagonals */
134                         float len1 = len_squared(mesh_P[inner[i]] - mesh_P[outer[j+1]]);
135                         float len2 = len_squared(mesh_P[outer[j]] - mesh_P[inner[i+1]]);
136
137                         /* use smallest diagonal */
138                         if(len1 < len2)
139                                 v2 = outer[++j];
140                         else
141                                 v2 = inner[++i];
142                 }
143
144                 add_triangle(patch, v0, v1, v2);
145         }
146 }
147
148 /* QuadDice */
149
150 QuadDice::QuadDice(const SubdParams& params_)
151 : EdgeDice(params_)
152 {
153 }
154
155 void QuadDice::reserve(EdgeFactors& ef, int Mu, int Mv)
156 {
157         /* XXX need to make this also work for edge factor 0 and 1 */
158         int num_verts = (ef.tu0 + ef.tu1 + ef.tv0 + ef.tv1) + (Mu - 1)*(Mv - 1);
159         EdgeDice::reserve(num_verts);
160 }
161
162 float2 QuadDice::map_uv(SubPatch& sub, float u, float v)
163 {
164         /* map UV from subpatch to patch parametric coordinates */
165         float2 d0 = interp(sub.P00, sub.P01, v);
166         float2 d1 = interp(sub.P10, sub.P11, v);
167         return interp(d0, d1, u);
168 }
169
170 float3 QuadDice::eval_projected(SubPatch& sub, float u, float v)
171 {
172         float2 uv = map_uv(sub, u, v);
173         float3 P;
174
175         sub.patch->eval(&P, NULL, NULL, NULL, uv.x, uv.y);
176         if(params.camera)
177                 P = transform_perspective(&params.camera->worldtoraster, P);
178
179         return P;
180 }
181
182 int QuadDice::add_vert(SubPatch& sub, float u, float v)
183 {
184         return EdgeDice::add_vert(sub.patch, map_uv(sub, u, v));
185 }
186
187 void QuadDice::add_side_u(SubPatch& sub,
188         vector<int>& outer, vector<int>& inner,
189         int Mu, int Mv, int tu, int side, int offset)
190 {
191         outer.clear();
192         inner.clear();
193
194         /* set verts on the edge of the patch */
195         outer.push_back(offset + ((side)? 2: 0));
196
197         for(int i = 1; i < tu; i++) {
198                 float u = i/(float)tu;
199                 float v = (side)? 1.0f: 0.0f;
200
201                 outer.push_back(add_vert(sub, u, v));
202         }
203
204         outer.push_back(offset + ((side)? 3: 1));
205
206         /* set verts on the edge of the inner grid */
207         for(int i = 0; i < Mu-1; i++) {
208                 int j = (side)? Mv-1-1: 0;
209                 inner.push_back(offset + 4 + i + j*(Mu-1));
210         }
211 }
212
213 void QuadDice::add_side_v(SubPatch& sub,
214         vector<int>& outer, vector<int>& inner,
215         int Mu, int Mv, int tv, int side, int offset)
216 {
217         outer.clear();
218         inner.clear();
219
220         /* set verts on the edge of the patch */
221         outer.push_back(offset + ((side)? 1: 0));
222
223         for(int j = 1; j < tv; j++) {
224                 float u = (side)? 1.0f: 0.0f;
225                 float v = j/(float)tv;
226
227                 outer.push_back(add_vert(sub, u, v));
228         }
229
230         outer.push_back(offset + ((side)? 3: 2));
231
232         /* set verts on the edge of the inner grid */
233         for(int j = 0; j < Mv-1; j++) {
234                 int i = (side)? Mu-1-1: 0;
235                 inner.push_back(offset + 4 + i + j*(Mu-1));
236         }
237 }
238
239 float QuadDice::quad_area(const float3& a, const float3& b, const float3& c, const float3& d)
240 {
241         return triangle_area(a, b, d) + triangle_area(a, d, c);
242 }
243
244 float QuadDice::scale_factor(SubPatch& sub, EdgeFactors& ef, int Mu, int Mv)
245 {
246         /* estimate area as 4x largest of 4 quads */
247         float3 P[3][3];
248
249         for(int i = 0; i < 3; i++)
250                 for(int j = 0; j < 3; j++)
251                         P[i][j] = eval_projected(sub, i*0.5f, j*0.5f);
252
253         float A1 = quad_area(P[0][0], P[1][0], P[0][1], P[1][1]);
254         float A2 = quad_area(P[1][0], P[2][0], P[1][1], P[2][1]);
255         float A3 = quad_area(P[0][1], P[1][1], P[0][2], P[1][2]);
256         float A4 = quad_area(P[1][1], P[2][1], P[1][2], P[2][2]);
257         float Apatch = max(A1, max(A2, max(A3, A4)))*4.0f;
258
259         /* solve for scaling factor */
260         float Atri = params.dicing_rate*params.dicing_rate*0.5f;
261         float Ntris = Apatch/Atri;
262
263         // XXX does the -sqrt solution matter
264         // XXX max(D, 0.0) is highly suspicious, need to test cases
265         // where D goes negative
266         float N = 0.5f*(Ntris - (ef.tu0 + ef.tu1 + ef.tv0 + ef.tv1));
267         float D = 4.0f*N*Mu*Mv + (Mu + Mv)*(Mu + Mv);
268         float S = (Mu + Mv + sqrtf(max(D, 0.0f)))/(2*Mu*Mv);
269
270         return S;
271 }
272
273 void QuadDice::add_corners(SubPatch& sub)
274 {
275         /* add verts for patch corners */
276         add_vert(sub, 0.0f, 0.0f);
277         add_vert(sub, 1.0f, 0.0f);
278         add_vert(sub, 0.0f, 1.0f);
279         add_vert(sub, 1.0f, 1.0f);
280 }
281
282 void QuadDice::add_grid(SubPatch& sub, int Mu, int Mv, int offset)
283 {
284         /* create inner grid */
285         float du = 1.0f/(float)Mu;
286         float dv = 1.0f/(float)Mv;
287
288         for(int j = 1; j < Mv; j++) {
289                 for(int i = 1; i < Mu; i++) {
290                         float u = i*du;
291                         float v = j*dv;
292
293                         add_vert(sub, u, v);
294
295                         if(i < Mu-1 && j < Mv-1) {
296                                 int i1 = offset + 4 + (i-1) + (j-1)*(Mu-1);
297                                 int i2 = offset + 4 + i + (j-1)*(Mu-1);
298                                 int i3 = offset + 4 + i + j*(Mu-1);
299                                 int i4 = offset + 4 + (i-1) + j*(Mu-1);
300
301                                 add_triangle(sub.patch, i1, i2, i3);
302                                 add_triangle(sub.patch, i1, i3, i4);
303                         }
304                 }
305         }
306 }
307
308 void QuadDice::dice(SubPatch& sub, EdgeFactors& ef)
309 {
310         /* compute inner grid size with scale factor */
311         int Mu = max(ef.tu0, ef.tu1);
312         int Mv = max(ef.tv0, ef.tv1);
313
314 #if 0 /* Doesnt work very well, especially at grazing angles. */
315         float S = scale_factor(sub, ef, Mu, Mv);
316 #else
317         float S = 1.0f;
318 #endif
319
320         Mu = max((int)ceil(S*Mu), 2); // XXX handle 0 & 1?
321         Mv = max((int)ceil(S*Mv), 2); // XXX handle 0 & 1?
322
323         /* reserve space for new verts */
324         int offset = params.mesh->verts.size();
325         reserve(ef, Mu, Mv);
326
327         /* corners and inner grid */
328         add_corners(sub);
329         add_grid(sub, Mu, Mv, offset);
330
331         /* bottom side */
332         vector<int> outer, inner;
333
334         add_side_u(sub, outer, inner, Mu, Mv, ef.tu0, 0, offset);
335         stitch_triangles(sub.patch, outer, inner);
336
337         /* top side */
338         add_side_u(sub, outer, inner, Mu, Mv, ef.tu1, 1, offset);
339         stitch_triangles(sub.patch, inner, outer);
340
341         /* left side */
342         add_side_v(sub, outer, inner, Mu, Mv, ef.tv0, 0, offset);
343         stitch_triangles(sub.patch, inner, outer);
344
345         /* right side */
346         add_side_v(sub, outer, inner, Mu, Mv, ef.tv1, 1, offset);
347         stitch_triangles(sub.patch, outer, inner);
348
349         assert(vert_offset == params.mesh->verts.size());
350 }
351
352 CCL_NAMESPACE_END
353