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