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