c48e7686ca94c7e0a5eddd138572da67abd723a9
[blender-staging.git] / source / blender / editors / armature / editarmature_generate.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  * editarmature.c: Interface for creating and posing armature objects
29  */
30
31 #include <string.h>
32 #include <math.h>
33 #include <float.h>
34
35 #include "MEM_guardedalloc.h"
36
37 #include "DNA_scene_types.h"
38 #include "DNA_armature_types.h"
39
40 #include "BLI_blenlib.h"
41 #include "BLI_math.h"
42 #include "BLI_graph.h"
43  
44 #include "BKE_utildefines.h"
45 #include "BKE_global.h"
46 #include "BKE_context.h"
47
48 #include "ED_armature.h"
49 #include "armature_intern.h"
50 #include "BIF_generate.h"
51
52 void setBoneRollFromNormal(EditBone *bone, float *no, float invmat[][4], float tmat[][3])
53 {
54         if (no != NULL && !is_zero_v3(no))
55         {
56                 float tangent[3], vec[3], normal[3];
57
58                 VECCOPY(normal, no);    
59                 mul_m3_v3(tmat, normal);
60
61                 sub_v3_v3v3(tangent, bone->tail, bone->head);
62                 project_v3_v3v3(vec, tangent, normal);
63                 sub_v3_v3(normal, vec);
64                 
65                 normalize_v3(normal);
66                 
67                 bone->roll = ED_rollBoneToVector(bone, normal);
68         }
69 }
70
71 float calcArcCorrelation(BArcIterator *iter, int start, int end, float v0[3], float n[3])
72 {
73         int len = 2 + abs(end - start);
74         
75         if (len > 2)
76         {
77                 float avg_t = 0.0f;
78                 float s_t = 0.0f;
79                 float s_xyz = 0.0f;
80                 int i;
81                 
82                 /* First pass, calculate average */
83                 for (i = start; i <= end; i++)
84                 {
85                         float v[3];
86                         
87                         IT_peek(iter, i);
88                         sub_v3_v3v3(v, iter->p, v0);
89                         avg_t += dot_v3v3(v, n);
90                 }
91                 
92                 avg_t /= dot_v3v3(n, n);
93                 avg_t += 1.0f; /* adding start (0) and end (1) values */
94                 avg_t /= len;
95                 
96                 /* Second pass, calculate s_xyz and s_t */
97                 for (i = start; i <= end; i++)
98                 {
99                         float v[3], d[3];
100                         float dt;
101                         
102                         IT_peek(iter, i);
103                         sub_v3_v3v3(v, iter->p, v0);
104                         project_v3_v3v3(d, v, n);
105                         sub_v3_v3(v, d);
106                         
107                         dt = len_v3(d) - avg_t;
108                         
109                         s_t += dt * dt;
110                         s_xyz += dot_v3v3(v, v);
111                 }
112                 
113                 /* adding start(0) and end(1) values to s_t */
114                 s_t += (avg_t * avg_t) + (1 - avg_t) * (1 - avg_t);
115                 
116                 return 1.0f - s_xyz / s_t; 
117         }
118         else
119         {
120                 return 1.0f;
121         }
122 }
123
124 int nextFixedSubdivision(ToolSettings *toolsettings, BArcIterator *iter, int start, int end, float head[3], float p[3])
125 {
126         static float stroke_length = 0;
127         static float current_length;
128         static char n;
129         float *v1, *v2;
130         float length_threshold;
131         int i;
132         
133         if (stroke_length == 0)
134         {
135                 current_length = 0;
136
137                 IT_peek(iter, start);
138                 v1 = iter->p;
139                 
140                 for (i = start + 1; i <= end; i++)
141                 {
142                         IT_peek(iter, i);
143                         v2 = iter->p;
144
145                         stroke_length += len_v3v3(v1, v2);
146                         
147                         v1 = v2;
148                 }
149                 
150                 n = 0;
151                 current_length = 0;
152         }
153         
154         n++;
155         
156         length_threshold = n * stroke_length / toolsettings->skgen_subdivision_number;
157         
158         IT_peek(iter, start);
159         v1 = iter->p;
160
161         /* < and not <= because we don't care about end, it is P_EXACT anyway */
162         for (i = start + 1; i < end; i++)
163         {
164                 IT_peek(iter, i);
165                 v2 = iter->p;
166
167                 current_length += len_v3v3(v1, v2);
168
169                 if (current_length >= length_threshold)
170                 {
171                         VECCOPY(p, v2);
172                         return i;
173                 }
174                 
175                 v1 = v2;
176         }
177         
178         stroke_length = 0;
179         
180         return -1;
181 }
182 int nextAdaptativeSubdivision(ToolSettings *toolsettings, BArcIterator *iter, int start, int end, float head[3], float p[3])
183 {
184         float correlation_threshold = toolsettings->skgen_correlation_limit;
185         float *start_p;
186         float n[3];
187         int i;
188         
189         IT_peek(iter, start);
190         start_p = iter->p;
191
192         for (i = start + 2; i <= end; i++)
193         {
194                 /* Calculate normal */
195                 IT_peek(iter, i);
196                 sub_v3_v3v3(n, iter->p, head);
197
198                 if (calcArcCorrelation(iter, start, i, start_p, n) < correlation_threshold)
199                 {
200                         IT_peek(iter, i - 1);
201                         VECCOPY(p, iter->p);
202                         return i - 1;
203                 }
204         }
205         
206         return -1;
207 }
208
209 int nextLengthSubdivision(ToolSettings *toolsettings, BArcIterator *iter, int start, int end, float head[3], float p[3])
210 {
211         float lengthLimit = toolsettings->skgen_length_limit;
212         int same = 1;
213         int i;
214         
215         i = start + 1;
216         while (i <= end)
217         {
218                 float *vec0;
219                 float *vec1;
220                 
221                 IT_peek(iter, i - 1);
222                 vec0 = iter->p;
223
224                 IT_peek(iter, i);
225                 vec1 = iter->p;
226                 
227                 /* If lengthLimit hits the current segment */
228                 if (len_v3v3(vec1, head) > lengthLimit)
229                 {
230                         if (same == 0)
231                         {
232                                 float dv[3], off[3];
233                                 float a, b, c, f;
234                                 
235                                 /* Solve quadratic distance equation */
236                                 sub_v3_v3v3(dv, vec1, vec0);
237                                 a = dot_v3v3(dv, dv);
238                                 
239                                 sub_v3_v3v3(off, vec0, head);
240                                 b = 2 * dot_v3v3(dv, off);
241                                 
242                                 c = dot_v3v3(off, off) - (lengthLimit * lengthLimit);
243                                 
244                                 f = (-b + (float)sqrt(b * b - 4 * a * c)) / (2 * a);
245                                 
246                                 //printf("a %f, b %f, c %f, f %f\n", a, b, c, f);
247                                 
248                                 if (isnan(f) == 0 && f < 1.0f)
249                                 {
250                                         VECCOPY(p, dv);
251                                         mul_v3_fl(p, f);
252                                         add_v3_v3(p, vec0);
253                                 }
254                                 else
255                                 {
256                                         VECCOPY(p, vec1);
257                                 }
258                         }
259                         else
260                         {
261                                 float dv[3];
262                                 
263                                 sub_v3_v3v3(dv, vec1, vec0);
264                                 normalize_v3(dv);
265                                  
266                                 VECCOPY(p, dv);
267                                 mul_v3_fl(p, lengthLimit);
268                                 add_v3_v3(p, head);
269                         }
270                         
271                         return i - 1; /* restart at lower bound */
272                 }
273                 else
274                 {
275                         i++;
276                         same = 0; // Reset same
277                 }
278         }
279         
280         return -1;
281 }
282
283 EditBone * subdivideArcBy(ToolSettings *toolsettings, bArmature *arm, ListBase *editbones, BArcIterator *iter, float invmat[][4], float tmat[][3], NextSubdivisionFunc next_subdividion)
284 {
285         EditBone *lastBone = NULL;
286         EditBone *child = NULL;
287         EditBone *parent = NULL;
288         float *normal = NULL;
289         float size_buffer = 1.2;
290         int bone_start = 0;
291         int end = iter->length;
292         int index;
293         
294         IT_head(iter);
295         
296         parent = ED_armature_edit_bone_add(arm, "Bone");
297         VECCOPY(parent->head, iter->p);
298         
299         if (iter->size > 0)
300         {
301                 parent->rad_head = iter->size * size_buffer;
302         }
303         
304         normal = iter->no;
305         
306         index = next_subdividion(toolsettings, iter, bone_start, end, parent->head, parent->tail);
307         while (index != -1)
308         {
309                 IT_peek(iter, index);
310
311                 child = ED_armature_edit_bone_add(arm, "Bone");
312                 VECCOPY(child->head, parent->tail);
313                 child->parent = parent;
314                 child->flag |= BONE_CONNECTED;
315                 
316                 if (iter->size > 0)
317                 {
318                         child->rad_head = iter->size * size_buffer;
319                         parent->rad_tail = iter->size * size_buffer;
320                 }
321
322                 /* going to next bone, fix parent */
323                 mul_m4_v3(invmat, parent->tail);
324                 mul_m4_v3(invmat, parent->head);
325                 setBoneRollFromNormal(parent, normal, invmat, tmat);
326
327                 parent = child; // new child is next parent
328                 bone_start = index; // start next bone from current index
329
330                 normal = iter->no; /* use normal at head, not tail */
331
332                 index = next_subdividion(toolsettings, iter, bone_start, end, parent->head, parent->tail);
333         }
334         
335         iter->tail(iter);
336
337         VECCOPY(parent->tail, iter->p);
338         if (iter->size > 0)
339         {
340                 parent->rad_tail = iter->size * size_buffer;
341         }
342                 
343         /* fix last bone */
344         mul_m4_v3(invmat, parent->tail);
345         mul_m4_v3(invmat, parent->head);
346         setBoneRollFromNormal(parent, iter->no, invmat, tmat);
347         lastBone = parent;
348         
349         return lastBone;
350 }