remove unused includes
[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
46 #include "ED_armature.h"
47 #include "armature_intern.h"
48 #include "BIF_generate.h"
49
50 void setBoneRollFromNormal(EditBone *bone, float *no, float invmat[][4], float tmat[][3])
51 {
52         if (no != NULL && !is_zero_v3(no))
53         {
54                 float tangent[3], vec[3], normal[3];
55
56                 VECCOPY(normal, no);    
57                 mul_m3_v3(tmat, normal);
58
59                 sub_v3_v3v3(tangent, bone->tail, bone->head);
60                 project_v3_v3v3(vec, tangent, normal);
61                 sub_v3_v3(normal, vec);
62                 
63                 normalize_v3(normal);
64                 
65                 bone->roll = ED_rollBoneToVector(bone, normal);
66         }
67 }
68
69 float calcArcCorrelation(BArcIterator *iter, int start, int end, float v0[3], float n[3])
70 {
71         int len = 2 + abs(end - start);
72         
73         if (len > 2)
74         {
75                 float avg_t = 0.0f;
76                 float s_t = 0.0f;
77                 float s_xyz = 0.0f;
78                 int i;
79                 
80                 /* First pass, calculate average */
81                 for (i = start; i <= end; i++)
82                 {
83                         float v[3];
84                         
85                         IT_peek(iter, i);
86                         sub_v3_v3v3(v, iter->p, v0);
87                         avg_t += dot_v3v3(v, n);
88                 }
89                 
90                 avg_t /= dot_v3v3(n, n);
91                 avg_t += 1.0f; /* adding start (0) and end (1) values */
92                 avg_t /= len;
93                 
94                 /* Second pass, calculate s_xyz and s_t */
95                 for (i = start; i <= end; i++)
96                 {
97                         float v[3], d[3];
98                         float dt;
99                         
100                         IT_peek(iter, i);
101                         sub_v3_v3v3(v, iter->p, v0);
102                         project_v3_v3v3(d, v, n);
103                         sub_v3_v3(v, d);
104                         
105                         dt = len_v3(d) - avg_t;
106                         
107                         s_t += dt * dt;
108                         s_xyz += dot_v3v3(v, v);
109                 }
110                 
111                 /* adding start(0) and end(1) values to s_t */
112                 s_t += (avg_t * avg_t) + (1 - avg_t) * (1 - avg_t);
113                 
114                 return 1.0f - s_xyz / s_t; 
115         }
116         else
117         {
118                 return 1.0f;
119         }
120 }
121
122 int nextFixedSubdivision(ToolSettings *toolsettings, BArcIterator *iter, int start, int end, float head[3], float p[3])
123 {
124         static float stroke_length = 0;
125         static float current_length;
126         static char n;
127         float *v1, *v2;
128         float length_threshold;
129         int i;
130         
131         if (stroke_length == 0)
132         {
133                 current_length = 0;
134
135                 IT_peek(iter, start);
136                 v1 = iter->p;
137                 
138                 for (i = start + 1; i <= end; i++)
139                 {
140                         IT_peek(iter, i);
141                         v2 = iter->p;
142
143                         stroke_length += len_v3v3(v1, v2);
144                         
145                         v1 = v2;
146                 }
147                 
148                 n = 0;
149                 current_length = 0;
150         }
151         
152         n++;
153         
154         length_threshold = n * stroke_length / toolsettings->skgen_subdivision_number;
155         
156         IT_peek(iter, start);
157         v1 = iter->p;
158
159         /* < and not <= because we don't care about end, it is P_EXACT anyway */
160         for (i = start + 1; i < end; i++)
161         {
162                 IT_peek(iter, i);
163                 v2 = iter->p;
164
165                 current_length += len_v3v3(v1, v2);
166
167                 if (current_length >= length_threshold)
168                 {
169                         VECCOPY(p, v2);
170                         return i;
171                 }
172                 
173                 v1 = v2;
174         }
175         
176         stroke_length = 0;
177         
178         return -1;
179 }
180 int nextAdaptativeSubdivision(ToolSettings *toolsettings, BArcIterator *iter, int start, int end, float head[3], float p[3])
181 {
182         float correlation_threshold = toolsettings->skgen_correlation_limit;
183         float *start_p;
184         float n[3];
185         int i;
186         
187         IT_peek(iter, start);
188         start_p = iter->p;
189
190         for (i = start + 2; i <= end; i++)
191         {
192                 /* Calculate normal */
193                 IT_peek(iter, i);
194                 sub_v3_v3v3(n, iter->p, head);
195
196                 if (calcArcCorrelation(iter, start, i, start_p, n) < correlation_threshold)
197                 {
198                         IT_peek(iter, i - 1);
199                         VECCOPY(p, iter->p);
200                         return i - 1;
201                 }
202         }
203         
204         return -1;
205 }
206
207 int nextLengthSubdivision(ToolSettings *toolsettings, BArcIterator *iter, int start, int end, float head[3], float p[3])
208 {
209         float lengthLimit = toolsettings->skgen_length_limit;
210         int same = 1;
211         int i;
212         
213         i = start + 1;
214         while (i <= end)
215         {
216                 float *vec0;
217                 float *vec1;
218                 
219                 IT_peek(iter, i - 1);
220                 vec0 = iter->p;
221
222                 IT_peek(iter, i);
223                 vec1 = iter->p;
224                 
225                 /* If lengthLimit hits the current segment */
226                 if (len_v3v3(vec1, head) > lengthLimit)
227                 {
228                         if (same == 0)
229                         {
230                                 float dv[3], off[3];
231                                 float a, b, c, f;
232                                 
233                                 /* Solve quadratic distance equation */
234                                 sub_v3_v3v3(dv, vec1, vec0);
235                                 a = dot_v3v3(dv, dv);
236                                 
237                                 sub_v3_v3v3(off, vec0, head);
238                                 b = 2 * dot_v3v3(dv, off);
239                                 
240                                 c = dot_v3v3(off, off) - (lengthLimit * lengthLimit);
241                                 
242                                 f = (-b + (float)sqrt(b * b - 4 * a * c)) / (2 * a);
243                                 
244                                 //printf("a %f, b %f, c %f, f %f\n", a, b, c, f);
245                                 
246                                 if (isnan(f) == 0 && f < 1.0f)
247                                 {
248                                         VECCOPY(p, dv);
249                                         mul_v3_fl(p, f);
250                                         add_v3_v3(p, vec0);
251                                 }
252                                 else
253                                 {
254                                         VECCOPY(p, vec1);
255                                 }
256                         }
257                         else
258                         {
259                                 float dv[3];
260                                 
261                                 sub_v3_v3v3(dv, vec1, vec0);
262                                 normalize_v3(dv);
263                                  
264                                 VECCOPY(p, dv);
265                                 mul_v3_fl(p, lengthLimit);
266                                 add_v3_v3(p, head);
267                         }
268                         
269                         return i - 1; /* restart at lower bound */
270                 }
271                 else
272                 {
273                         i++;
274                         same = 0; // Reset same
275                 }
276         }
277         
278         return -1;
279 }
280
281 EditBone * subdivideArcBy(ToolSettings *toolsettings, bArmature *arm, ListBase *editbones, BArcIterator *iter, float invmat[][4], float tmat[][3], NextSubdivisionFunc next_subdividion)
282 {
283         EditBone *lastBone = NULL;
284         EditBone *child = NULL;
285         EditBone *parent = NULL;
286         float *normal = NULL;
287         float size_buffer = 1.2;
288         int bone_start = 0;
289         int end = iter->length;
290         int index;
291         
292         IT_head(iter);
293         
294         parent = ED_armature_edit_bone_add(arm, "Bone");
295         VECCOPY(parent->head, iter->p);
296         
297         if (iter->size > 0)
298         {
299                 parent->rad_head = iter->size * size_buffer;
300         }
301         
302         normal = iter->no;
303         
304         index = next_subdividion(toolsettings, iter, bone_start, end, parent->head, parent->tail);
305         while (index != -1)
306         {
307                 IT_peek(iter, index);
308
309                 child = ED_armature_edit_bone_add(arm, "Bone");
310                 VECCOPY(child->head, parent->tail);
311                 child->parent = parent;
312                 child->flag |= BONE_CONNECTED;
313                 
314                 if (iter->size > 0)
315                 {
316                         child->rad_head = iter->size * size_buffer;
317                         parent->rad_tail = iter->size * size_buffer;
318                 }
319
320                 /* going to next bone, fix parent */
321                 mul_m4_v3(invmat, parent->tail);
322                 mul_m4_v3(invmat, parent->head);
323                 setBoneRollFromNormal(parent, normal, invmat, tmat);
324
325                 parent = child; // new child is next parent
326                 bone_start = index; // start next bone from current index
327
328                 normal = iter->no; /* use normal at head, not tail */
329
330                 index = next_subdividion(toolsettings, iter, bone_start, end, parent->head, parent->tail);
331         }
332         
333         iter->tail(iter);
334
335         VECCOPY(parent->tail, iter->p);
336         if (iter->size > 0)
337         {
338                 parent->rad_tail = iter->size * size_buffer;
339         }
340                 
341         /* fix last bone */
342         mul_m4_v3(invmat, parent->tail);
343         mul_m4_v3(invmat, parent->head);
344         setBoneRollFromNormal(parent, iter->no, invmat, tmat);
345         lastBone = parent;
346         
347         return lastBone;
348 }