290e19736bb8d4c34d19f330320d22e958c9bd1c
[blender-staging.git] / source / blender / modifiers / intern / MOD_screw.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
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  * The Original Code is Copyright (C) 2005 by the Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Daniel Dunbar
22  *                 Ton Roosendaal,
23  *                 Ben Batt,
24  *                 Brecht Van Lommel,
25  *                 Campbell Barton
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  *
29  */
30
31 /** \file blender/modifiers/intern/MOD_screw.c
32  *  \ingroup modifiers
33  */
34
35
36 /* Screw modifier: revolves the edges about an axis */
37 #include <limits.h>
38
39 #include "DNA_meshdata_types.h"
40 #include "DNA_object_types.h"
41
42 #include "BLI_math.h"
43 #include "BLI_alloca.h"
44 #include "BLI_utildefines.h"
45
46 #include "BKE_cdderivedmesh.h"
47 #include "BKE_library_query.h"
48
49 #include "depsgraph_private.h"
50 #include "DEG_depsgraph_build.h"
51
52 #include "MOD_modifiertypes.h"
53 #include "MEM_guardedalloc.h"
54
55 #include "BLI_strict_flags.h"
56
57 /* used for gathering edge connectivity */
58 typedef struct ScrewVertConnect {
59         float dist;  /* distance from the center axis */
60         float co[3]; /* loaction relative to the transformed axis */
61         float no[3]; /* calc normal of the vertex */
62         unsigned int v[2]; /* 2  verts on either side of this one */
63         MEdge *e[2]; /* edges on either side, a bit of a waste since each edge ref's 2 edges */
64         char flag;
65 } ScrewVertConnect;
66
67 typedef struct ScrewVertIter {
68         ScrewVertConnect *v_array;
69         ScrewVertConnect *v_poin;
70         unsigned int v, v_other;
71         MEdge *e;
72 } ScrewVertIter;
73
74 #define SV_UNUSED (UINT_MAX)
75 #define SV_INVALID ((UINT_MAX) - 1)
76 #define SV_IS_VALID(v) ((v) < SV_INVALID)
77
78 static void screwvert_iter_init(ScrewVertIter *iter, ScrewVertConnect *array, unsigned int v_init, unsigned int dir)
79 {
80         iter->v_array = array;
81         iter->v = v_init;
82
83         if (SV_IS_VALID(v_init)) {
84                 iter->v_poin = &array[v_init];
85                 iter->v_other = iter->v_poin->v[dir];
86                 iter->e = iter->v_poin->e[!dir];
87         }
88         else {
89                 iter->v_poin = NULL;
90                 iter->e = NULL;
91         }
92 }       
93
94
95 static void screwvert_iter_step(ScrewVertIter *iter)
96 {
97         if (iter->v_poin->v[0] == iter->v_other) {
98                 iter->v_other = iter->v;
99                 iter->v = iter->v_poin->v[1];
100         }
101         else if (iter->v_poin->v[1] == iter->v_other) {
102                 iter->v_other = iter->v;
103                 iter->v = iter->v_poin->v[0];
104         }
105         if (SV_IS_VALID(iter->v)) {
106                 iter->v_poin = &iter->v_array[iter->v];
107                 iter->e = iter->v_poin->e[(iter->v_poin->e[0] == iter->e)];
108         }
109         else {
110                 iter->e = NULL;
111                 iter->v_poin = NULL;
112         }
113 }
114
115
116 static void initData(ModifierData *md)
117 {
118         ScrewModifierData *ltmd = (ScrewModifierData *) md;
119         ltmd->ob_axis = NULL;
120         ltmd->angle = (float)(M_PI * 2.0);
121         ltmd->axis = 2;
122         ltmd->flag = MOD_SCREW_SMOOTH_SHADING;
123         ltmd->steps = 16;
124         ltmd->render_steps = 16;
125         ltmd->iter = 1;
126 }
127
128 static void copyData(ModifierData *md, ModifierData *target)
129 {
130 #if 0
131         ScrewModifierData *sltmd = (ScrewModifierData *) md;
132         ScrewModifierData *tltmd = (ScrewModifierData *) target;
133 #endif
134         modifier_copyData_generic(md, target);
135 }
136
137 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
138                                   DerivedMesh *derivedData,
139                                   ModifierApplyFlag flag)
140 {
141         DerivedMesh *dm = derivedData;
142         DerivedMesh *result;
143         ScrewModifierData *ltmd = (ScrewModifierData *) md;
144         const bool use_render_params = (flag & MOD_APPLY_RENDER) != 0;
145         
146         int *origindex;
147         int mpoly_index = 0;
148         unsigned int step;
149         unsigned int i, j;
150         unsigned int i1, i2;
151         unsigned int step_tot = use_render_params ? ltmd->render_steps : ltmd->steps;
152         const bool do_flip = (ltmd->flag & MOD_SCREW_NORMAL_FLIP) != 0;
153
154         const int quad_ord[4] = {
155             do_flip ? 3 : 0,
156             do_flip ? 2 : 1,
157             do_flip ? 1 : 2,
158             do_flip ? 0 : 3,
159         };
160         const int quad_ord_ofs[4] = {
161             do_flip ? 2 : 0,
162             1,
163             do_flip ? 0 : 2,
164             3,
165         };
166
167         unsigned int maxVerts = 0, maxEdges = 0, maxPolys = 0;
168         const unsigned int totvert = (unsigned int)dm->getNumVerts(dm);
169         const unsigned int totedge = (unsigned int)dm->getNumEdges(dm);
170         const unsigned int totpoly = (unsigned int)dm->getNumPolys(dm);
171
172         unsigned int *edge_poly_map = NULL;  /* orig edge to orig poly */
173         unsigned int *vert_loop_map = NULL;  /* orig vert to orig loop */
174
175         /* UV Coords */
176         const unsigned int mloopuv_layers_tot = (unsigned int)CustomData_number_of_layers(&dm->loopData, CD_MLOOPUV);
177         MLoopUV **mloopuv_layers = BLI_array_alloca(mloopuv_layers, mloopuv_layers_tot);
178         float uv_u_scale;
179         float uv_v_minmax[2] = {FLT_MAX, -FLT_MAX};
180         float uv_v_range_inv;
181         float uv_axis_plane[4];
182
183         char axis_char = 'X';
184         bool close;
185         float angle = ltmd->angle;
186         float screw_ofs = ltmd->screw_ofs;
187         float axis_vec[3] = {0.0f, 0.0f, 0.0f};
188         float tmp_vec1[3], tmp_vec2[3]; 
189         float mat3[3][3];
190         float mtx_tx[4][4]; /* transform the coords by an object relative to this objects transformation */
191         float mtx_tx_inv[4][4]; /* inverted */
192         float mtx_tmp_a[4][4];
193         
194         unsigned int vc_tot_linked = 0;
195         short other_axis_1, other_axis_2;
196         const float *tmpf1, *tmpf2;
197
198         unsigned int edge_offset;
199         
200         MPoly *mpoly_orig, *mpoly_new, *mp_new;
201         MLoop *mloop_orig, *mloop_new, *ml_new;
202         MEdge *medge_orig, *med_orig, *med_new, *med_new_firstloop, *medge_new;
203         MVert *mvert_new, *mvert_orig, *mv_orig, *mv_new, *mv_new_base;
204
205         ScrewVertConnect *vc, *vc_tmp, *vert_connect = NULL;
206
207         const char mpoly_flag = (ltmd->flag & MOD_SCREW_SMOOTH_SHADING) ? ME_SMOOTH : 0;
208
209         /* don't do anything? */
210         if (!totvert)
211                 return CDDM_from_template(dm, 0, 0, 0, 0, 0);
212
213         switch (ltmd->axis) {
214                 case 0:
215                         other_axis_1 = 1;
216                         other_axis_2 = 2;
217                         break;
218                 case 1:
219                         other_axis_1 = 0;
220                         other_axis_2 = 2;
221                         break;
222                 default: /* 2, use default to quiet warnings */
223                         other_axis_1 = 0;
224                         other_axis_2 = 1;
225                         break;
226         }
227
228         axis_vec[ltmd->axis] = 1.0f;
229
230         if (ltmd->ob_axis) {
231                 /* calc the matrix relative to the axis object */
232                 invert_m4_m4(mtx_tmp_a, ob->obmat);
233                 copy_m4_m4(mtx_tx_inv, ltmd->ob_axis->obmat);
234                 mul_m4_m4m4(mtx_tx, mtx_tmp_a, mtx_tx_inv);
235
236                 /* calc the axis vec */
237                 mul_mat3_m4_v3(mtx_tx, axis_vec); /* only rotation component */
238                 normalize_v3(axis_vec);
239
240                 /* screw */
241                 if (ltmd->flag & MOD_SCREW_OBJECT_OFFSET) {
242                         /* find the offset along this axis relative to this objects matrix */
243                         float totlen = len_v3(mtx_tx[3]);
244
245                         if (totlen != 0.0f) {
246                                 float zero[3] = {0.0f, 0.0f, 0.0f};
247                                 float cp[3];
248                                 screw_ofs = closest_to_line_v3(cp, mtx_tx[3], zero, axis_vec);
249                         }
250                         else {
251                                 screw_ofs = 0.0f;
252                         }
253                 }
254
255                 /* angle */
256
257 #if 0   /* cant incluide this, not predictable enough, though quite fun. */
258                 if (ltmd->flag & MOD_SCREW_OBJECT_ANGLE) {
259                         float mtx3_tx[3][3];
260                         copy_m3_m4(mtx3_tx, mtx_tx);
261
262                         float vec[3] = {0, 1, 0};
263                         float cross1[3];
264                         float cross2[3];
265                         cross_v3_v3v3(cross1, vec, axis_vec);
266
267                         mul_v3_m3v3(cross2, mtx3_tx, cross1);
268                         {
269                                 float c1[3];
270                                 float c2[3];
271                                 float axis_tmp[3];
272
273                                 cross_v3_v3v3(c1, cross2, axis_vec);
274                                 cross_v3_v3v3(c2, axis_vec, c1);
275
276
277                                 angle = angle_v3v3(cross1, c2);
278
279                                 cross_v3_v3v3(axis_tmp, cross1, c2);
280                                 normalize_v3(axis_tmp);
281
282                                 if (len_v3v3(axis_tmp, axis_vec) > 1.0f)
283                                         angle = -angle;
284
285                         }
286                 }
287 #endif
288         }
289         else {
290                 /* exis char is used by i_rotate*/
291                 axis_char = (char)(axis_char + ltmd->axis); /* 'X' + axis */
292
293                 /* useful to be able to use the axis vec in some cases still */
294                 zero_v3(axis_vec);
295                 axis_vec[ltmd->axis] = 1.0f;
296         }
297
298         /* apply the multiplier */
299         angle *= (float)ltmd->iter;
300         screw_ofs *= (float)ltmd->iter;
301         uv_u_scale = 1.0f / (float)(step_tot);
302
303         /* multiplying the steps is a bit tricky, this works best */
304         step_tot = ((step_tot + 1) * ltmd->iter) - (ltmd->iter - 1);
305
306         /* will the screw be closed?
307          * Note! smaller then FLT_EPSILON * 100 gives problems with float precision so its never closed. */
308         if (fabsf(screw_ofs) <= (FLT_EPSILON * 100.0f) &&
309             fabsf(fabsf(angle) - ((float)M_PI * 2.0f)) <= (FLT_EPSILON * 100.0f))
310         {
311                 close = 1;
312                 step_tot--;
313                 if (step_tot < 3) step_tot = 3;
314         
315                 maxVerts = totvert  * step_tot;   /* -1 because we're joining back up */
316                 maxEdges = (totvert * step_tot) + /* these are the edges between new verts */
317                            (totedge * step_tot);  /* -1 because vert edges join */
318                 maxPolys = totedge * step_tot;
319
320                 screw_ofs = 0.0f;
321         }
322         else {
323                 close = 0;
324                 if (step_tot < 3) step_tot = 3;
325
326                 maxVerts =  totvert  * step_tot; /* -1 because we're joining back up */
327                 maxEdges =  (totvert * (step_tot - 1)) + /* these are the edges between new verts */
328                            (totedge * step_tot);  /* -1 because vert edges join */
329                 maxPolys =  totedge * (step_tot - 1);
330         }
331
332         if ((ltmd->flag & MOD_SCREW_UV_STRETCH_U) == 0) {
333                 uv_u_scale = (uv_u_scale / (float)ltmd->iter) * (angle / ((float)M_PI * 2.0f));
334         }
335         
336         result = CDDM_from_template(dm, (int)maxVerts, (int)maxEdges, 0, (int)maxPolys * 4, (int)maxPolys);
337         
338         /* copy verts from mesh */
339         mvert_orig =    dm->getVertArray(dm);
340         medge_orig =    dm->getEdgeArray(dm);
341         
342         mvert_new =     result->getVertArray(result);
343         mpoly_new =     result->getPolyArray(result);
344         mloop_new =     result->getLoopArray(result);
345         medge_new =     result->getEdgeArray(result);
346
347         if (!CustomData_has_layer(&result->polyData, CD_ORIGINDEX)) {
348                 CustomData_add_layer(&result->polyData, CD_ORIGINDEX, CD_CALLOC, NULL, (int)maxPolys);
349         }
350
351         origindex = CustomData_get_layer(&result->polyData, CD_ORIGINDEX);
352
353         DM_copy_vert_data(dm, result, 0, 0, (int)totvert); /* copy first otherwise this overwrites our own vertex normals */
354
355         if (mloopuv_layers_tot) {
356                 float zero_co[3] = {0};
357                 plane_from_point_normal_v3(uv_axis_plane, zero_co, axis_vec);
358         }
359
360         if (mloopuv_layers_tot) {
361                 unsigned int uv_lay;
362                 for (uv_lay = 0; uv_lay < mloopuv_layers_tot; uv_lay++) {
363                         mloopuv_layers[uv_lay] = CustomData_get_layer_n(&result->loopData, CD_MLOOPUV, (int)uv_lay);
364                 }
365
366                 if (ltmd->flag & MOD_SCREW_UV_STRETCH_V) {
367                         for (i = 0, mv_orig = mvert_orig; i < totvert; i++, mv_orig++) {
368                                 const float v = dist_signed_squared_to_plane_v3(mv_orig->co, uv_axis_plane);
369                                 uv_v_minmax[0] = min_ff(v, uv_v_minmax[0]);
370                                 uv_v_minmax[1] = max_ff(v, uv_v_minmax[1]);
371                         }
372                         uv_v_minmax[0] = sqrtf_signed(uv_v_minmax[0]);
373                         uv_v_minmax[1] = sqrtf_signed(uv_v_minmax[1]);
374                 }
375
376                 uv_v_range_inv = uv_v_minmax[1] - uv_v_minmax[0];
377                 uv_v_range_inv = uv_v_range_inv ? 1.0f / uv_v_range_inv : 0.0f;
378         }
379
380         /* Set the locations of the first set of verts */
381         
382         mv_new = mvert_new;
383         mv_orig = mvert_orig;
384         
385         /* Copy the first set of edges */
386         med_orig = medge_orig;
387         med_new = medge_new;
388         for (i = 0; i < totedge; i++, med_orig++, med_new++) {
389                 med_new->v1 = med_orig->v1;
390                 med_new->v2 = med_orig->v2;
391                 med_new->crease = med_orig->crease;
392                 med_new->flag = med_orig->flag &  ~ME_LOOSEEDGE;
393         }
394         
395         /* build polygon -> edge map */
396         if (totpoly) {
397                 MPoly *mp_orig;
398
399                 mpoly_orig = dm->getPolyArray(dm);
400                 mloop_orig = dm->getLoopArray(dm);
401                 edge_poly_map = MEM_mallocN(sizeof(*edge_poly_map) * totedge, __func__);
402                 memset(edge_poly_map, 0xff, sizeof(*edge_poly_map) * totedge);
403
404                 vert_loop_map = MEM_mallocN(sizeof(*vert_loop_map) * totvert, __func__);
405                 memset(vert_loop_map, 0xff, sizeof(*vert_loop_map) * totvert);
406
407                 for (i = 0, mp_orig = mpoly_orig; i < totpoly; i++, mp_orig++) {
408                         unsigned int loopstart = (unsigned int)mp_orig->loopstart;
409                         unsigned int loopend = loopstart + (unsigned int)mp_orig->totloop;
410
411                         MLoop *ml_orig = &mloop_orig[loopstart];
412                         unsigned int k;
413                         for (k = loopstart; k < loopend; k++, ml_orig++) {
414                                 edge_poly_map[ml_orig->e] = i;
415                                 vert_loop_map[ml_orig->v] = k;
416
417                                 /* also order edges based on faces */
418                                 if (medge_new[ml_orig->e].v1 != ml_orig->v) {
419                                         SWAP(unsigned int, medge_new[ml_orig->e].v1, medge_new[ml_orig->e].v2);
420                                 }
421                         }
422                 }
423         }
424
425         if (ltmd->flag & MOD_SCREW_NORMAL_CALC) {
426                 /*
427                  * Normal Calculation (for face flipping)
428                  * Sort edge verts for correct face flipping
429                  * NOT REALLY NEEDED but face flipping is nice.
430                  *
431                  * */
432
433
434                 /* Notice!
435                  *
436                  * Since we are only ordering the edges here it can avoid mallocing the
437                  * extra space by abusing the vert array before its filled with new verts.
438                  * The new array for vert_connect must be at least sizeof(ScrewVertConnect) * totvert
439                  * and the size of our resulting meshes array is sizeof(MVert) * totvert * 3
440                  * so its safe to use the second 2 thrids of MVert the array for vert_connect,
441                  * just make sure ScrewVertConnect struct is no more than twice as big as MVert,
442                  * at the moment there is no chance of that being a problem,
443                  * unless MVert becomes half its current size.
444                  *
445                  * once the edges are ordered, vert_connect is not needed and it can be used for verts
446                  *
447                  * This makes the modifier faster with one less alloc.
448                  */
449
450                 vert_connect = MEM_mallocN(sizeof(ScrewVertConnect) * totvert, "ScrewVertConnect");
451                 //vert_connect = (ScrewVertConnect *) &medge_new[totvert];  /* skip the first slice of verts */
452                 vc = vert_connect;
453
454                 /* Copy Vert Locations */
455                 /* - We can do this in a later loop - only do here if no normal calc */
456                 if (!totedge) {
457                         for (i = 0; i < totvert; i++, mv_orig++, mv_new++) {
458                                 copy_v3_v3(mv_new->co, mv_orig->co);
459                                 normalize_v3_v3(vc->no, mv_new->co); /* no edges- this is really a dummy normal */
460                         }
461                 }
462                 else {
463                         /*printf("\n\n\n\n\nStarting Modifier\n");*/
464                         /* set edge users */
465                         med_new = medge_new;
466                         mv_new = mvert_new;
467
468                         if (ltmd->ob_axis) {
469                                 /*mtx_tx is initialized early on */
470                                 for (i = 0; i < totvert; i++, mv_new++, mv_orig++, vc++) {
471                                         vc->co[0] = mv_new->co[0] = mv_orig->co[0];
472                                         vc->co[1] = mv_new->co[1] = mv_orig->co[1];
473                                         vc->co[2] = mv_new->co[2] = mv_orig->co[2];
474
475                                         vc->flag = 0;
476                                         vc->e[0] = vc->e[1] = NULL;
477                                         vc->v[0] = vc->v[1] = SV_UNUSED;
478
479                                         mul_m4_v3(mtx_tx, vc->co);
480                                         /* length in 2d, don't sqrt because this is only for comparison */
481                                         vc->dist = vc->co[other_axis_1] * vc->co[other_axis_1] +
482                                                    vc->co[other_axis_2] * vc->co[other_axis_2];
483
484                                         /* printf("location %f %f %f -- %f\n", vc->co[0], vc->co[1], vc->co[2], vc->dist);*/
485                                 }
486                         }
487                         else {
488                                 for (i = 0; i < totvert; i++, mv_new++, mv_orig++, vc++) {
489                                         vc->co[0] = mv_new->co[0] = mv_orig->co[0];
490                                         vc->co[1] = mv_new->co[1] = mv_orig->co[1];
491                                         vc->co[2] = mv_new->co[2] = mv_orig->co[2];
492
493                                         vc->flag = 0;
494                                         vc->e[0] = vc->e[1] = NULL;
495                                         vc->v[0] = vc->v[1] = SV_UNUSED;
496
497                                         /* length in 2d, don't sqrt because this is only for comparison */
498                                         vc->dist = vc->co[other_axis_1] * vc->co[other_axis_1] +
499                                                    vc->co[other_axis_2] * vc->co[other_axis_2];
500
501                                         /* printf("location %f %f %f -- %f\n", vc->co[0], vc->co[1], vc->co[2], vc->dist);*/
502                                 }
503                         }
504
505                         /* this loop builds connectivity info for verts */
506                         for (i = 0; i < totedge; i++, med_new++) {
507                                 vc = &vert_connect[med_new->v1];
508
509                                 if (vc->v[0] == SV_UNUSED) { /* unused */
510                                         vc->v[0] = med_new->v2;
511                                         vc->e[0] = med_new;
512                                 }
513                                 else if (vc->v[1] == SV_UNUSED) {
514                                         vc->v[1] = med_new->v2;
515                                         vc->e[1] = med_new;
516                                 }
517                                 else {
518                                         vc->v[0] = vc->v[1] = SV_INVALID; /* error value  - don't use, 3 edges on vert */
519                                 }
520
521                                 vc = &vert_connect[med_new->v2];
522
523                                 /* same as above but swap v1/2 */
524                                 if (vc->v[0] == SV_UNUSED) { /* unused */
525                                         vc->v[0] = med_new->v1;
526                                         vc->e[0] = med_new;
527                                 }
528                                 else if (vc->v[1] == SV_UNUSED) {
529                                         vc->v[1] = med_new->v1;
530                                         vc->e[1] = med_new;
531                                 }
532                                 else {
533                                         vc->v[0] = vc->v[1] = SV_INVALID; /* error value  - don't use, 3 edges on vert */
534                                 }
535                         }
536
537                         /* find the first vert */
538                         vc = vert_connect;
539                         for (i = 0; i < totvert; i++, vc++) {
540                                 /* Now do search for connected verts, order all edges and flip them
541                                  * so resulting faces are flipped the right way */
542                                 vc_tot_linked = 0; /* count the number of linked verts for this loop */
543                                 if (vc->flag == 0) {
544                                         unsigned int v_best = SV_UNUSED, ed_loop_closed = 0; /* vert and vert new */
545                                         ScrewVertIter lt_iter;
546                                         float fl = -1.0f;
547
548                                         /* compiler complains if not initialized, but it should be initialized below */
549                                         bool ed_loop_flip = false;
550
551                                         /*printf("Loop on connected vert: %i\n", i);*/
552
553                                         for (j = 0; j < 2; j++) {
554                                                 /*printf("\tSide: %i\n", j);*/
555                                                 screwvert_iter_init(&lt_iter, vert_connect, i, j);
556                                                 if (j == 1) {
557                                                         screwvert_iter_step(&lt_iter);
558                                                 }
559                                                 while (lt_iter.v_poin) {
560                                                         /*printf("\t\tVERT: %i\n", lt_iter.v);*/
561                                                         if (lt_iter.v_poin->flag) {
562                                                                 /*printf("\t\t\tBreaking Found end\n");*/
563                                                                 //endpoints[0] = endpoints[1] = SV_UNUSED;
564                                                                 ed_loop_closed = 1; /* circle */
565                                                                 break;
566                                                         }
567                                                         lt_iter.v_poin->flag = 1;
568                                                         vc_tot_linked++;
569                                                         /*printf("Testing 2 floats %f : %f\n", fl, lt_iter.v_poin->dist);*/
570                                                         if (fl <= lt_iter.v_poin->dist) {
571                                                                 fl = lt_iter.v_poin->dist;
572                                                                 v_best = lt_iter.v;
573                                                                 /*printf("\t\t\tVERT BEST: %i\n", v_best);*/
574                                                         }
575                                                         screwvert_iter_step(&lt_iter);
576                                                         if (!lt_iter.v_poin) {
577                                                                 /*printf("\t\t\tFound End Also Num %i\n", j);*/
578                                                                 /*endpoints[j] = lt_iter.v_other;*/ /* other is still valid */
579                                                                 break;
580                                                         }
581                                                 }
582                                         }
583
584                                         /* now we have a collection of used edges. flip their edges the right way*/
585                                         /*if (v_best != SV_UNUSED) - */
586
587                                         /*printf("Done Looking - vc_tot_linked: %i\n", vc_tot_linked);*/
588
589                                         if (vc_tot_linked > 1) {
590                                                 float vf_1, vf_2, vf_best;
591
592                                                 vc_tmp = &vert_connect[v_best];
593
594                                                 tmpf1 = vert_connect[vc_tmp->v[0]].co;
595                                                 tmpf2 = vert_connect[vc_tmp->v[1]].co;
596
597
598                                                 /* edge connects on each side! */
599                                                 if (SV_IS_VALID(vc_tmp->v[0]) && SV_IS_VALID(vc_tmp->v[1])) {
600                                                         /*printf("Verts on each side (%i %i)\n", vc_tmp->v[0], vc_tmp->v[1]);*/
601                                                         /* find out which is higher */
602
603                                                         vf_1 = tmpf1[ltmd->axis];
604                                                         vf_2 = tmpf2[ltmd->axis];
605                                                         vf_best = vc_tmp->co[ltmd->axis];
606
607                                                         if (vf_1 < vf_best && vf_best < vf_2) {
608                                                                 ed_loop_flip = 0;
609                                                         }
610                                                         else if (vf_1 > vf_best && vf_best > vf_2) {
611                                                                 ed_loop_flip = 1;
612                                                         }
613                                                         else {
614                                                                 /* not so simple to work out which edge is higher */
615                                                                 sub_v3_v3v3(tmp_vec1, tmpf1, vc_tmp->co);
616                                                                 sub_v3_v3v3(tmp_vec2, tmpf2, vc_tmp->co);
617                                                                 normalize_v3(tmp_vec1);
618                                                                 normalize_v3(tmp_vec2);
619
620                                                                 if (tmp_vec1[ltmd->axis] < tmp_vec2[ltmd->axis]) {
621                                                                         ed_loop_flip = 1;
622                                                                 }
623                                                                 else {
624                                                                         ed_loop_flip = 0;
625                                                                 }
626                                                         }
627                                                 }
628                                                 else if (SV_IS_VALID(vc_tmp->v[0])) { /*vertex only connected on 1 side */
629                                                         /*printf("Verts on ONE side (%i %i)\n", vc_tmp->v[0], vc_tmp->v[1]);*/
630                                                         if (tmpf1[ltmd->axis] < vc_tmp->co[ltmd->axis]) { /* best is above */
631                                                                 ed_loop_flip = 1;
632                                                         }
633                                                         else { /* best is below or even... in even case we cant know whet  to do. */
634                                                                 ed_loop_flip = 0;
635                                                         }
636
637                                                 }
638 #if 0
639                                                 else {
640                                                         printf("No Connected ___\n");
641                                                 }
642 #endif
643
644                                                 /*printf("flip direction %i\n", ed_loop_flip);*/
645
646
647                                                 /* switch the flip option if set
648                                                  * note: flip is now done at face level so copying vgroup slizes is easier */
649 #if 0
650                                                 if (do_flip)
651                                                         ed_loop_flip = !ed_loop_flip;
652 #endif
653
654                                                 if (angle < 0.0f)
655                                                         ed_loop_flip = !ed_loop_flip;
656
657                                                 /* if its closed, we only need 1 loop */
658                                                 for (j = ed_loop_closed; j < 2; j++) {
659                                                         /*printf("Ordering Side J %i\n", j);*/
660
661                                                         screwvert_iter_init(&lt_iter, vert_connect, v_best, j);
662                                                         /*printf("\n\nStarting - Loop\n");*/
663                                                         lt_iter.v_poin->flag = 1; /* so a non loop will traverse the other side */
664
665
666                                                         /* If this is the vert off the best vert and
667                                                          * the best vert has 2 edges connected too it
668                                                          * then swap the flip direction */
669                                                         if (j == 1 && SV_IS_VALID(vc_tmp->v[0]) && SV_IS_VALID(vc_tmp->v[1]))
670                                                                 ed_loop_flip = !ed_loop_flip;
671
672                                                         while (lt_iter.v_poin && lt_iter.v_poin->flag != 2) {
673                                                                 /*printf("\tOrdering Vert V %i\n", lt_iter.v);*/
674
675                                                                 lt_iter.v_poin->flag = 2;
676                                                                 if (lt_iter.e) {
677                                                                         if (lt_iter.v == lt_iter.e->v1) {
678                                                                                 if (ed_loop_flip == 0) {
679                                                                                         /*printf("\t\t\tFlipping 0\n");*/
680                                                                                         SWAP(unsigned int, lt_iter.e->v1, lt_iter.e->v2);
681                                                                                 }
682                                                                                 /* else {
683                                                                                     printf("\t\t\tFlipping Not 0\n");
684                                                                                    }*/
685                                                                         }
686                                                                         else if (lt_iter.v == lt_iter.e->v2) {
687                                                                                 if (ed_loop_flip == 1) {
688                                                                                         /*printf("\t\t\tFlipping 1\n");*/
689                                                                                         SWAP(unsigned int, lt_iter.e->v1, lt_iter.e->v2);
690                                                                                 }
691                                                                                 /* else {
692                                                                                     printf("\t\t\tFlipping Not 1\n");
693                                                                                    }*/
694                                                                         }
695                                                                         /* else {
696                                                                             printf("\t\tIncorrect edge topology");
697                                                                            }*/
698                                                                 }
699                                                                 /* else {
700                                                                     printf("\t\tNo Edge at this point\n");
701                                                                    }*/
702                                                                 screwvert_iter_step(&lt_iter);
703                                                         }
704                                                 }
705                                         }
706                                 }
707
708                                 /* *VERTEX NORMALS*
709                                  * we know the surrounding edges are ordered correctly now
710                                  * so its safe to create vertex normals.
711                                  *
712                                  * calculate vertex normals that can be propagated on lathing
713                                  * use edge connectivity work this out */
714                                 if (SV_IS_VALID(vc->v[0])) {
715                                         if (SV_IS_VALID(vc->v[1])) {
716                                                 /* 2 edges connedted */
717                                                 /* make 2 connecting vert locations relative to the middle vert */
718                                                 sub_v3_v3v3(tmp_vec1, mvert_new[vc->v[0]].co, mvert_new[i].co);
719                                                 sub_v3_v3v3(tmp_vec2, mvert_new[vc->v[1]].co, mvert_new[i].co);
720                                                 /* normalize so both edges have the same influence, no matter their length */
721                                                 normalize_v3(tmp_vec1);
722                                                 normalize_v3(tmp_vec2);
723
724                                                 /* vc_no_tmp1 - this line is the average direction of both connecting edges
725                                                  *
726                                                  * Use the edge order to make the subtraction, flip the normal the right way
727                                                  * edge should be there but check just in case... */
728                                                 if (vc->e[0]->v1 == i) {
729                                                         sub_v3_v3(tmp_vec1, tmp_vec2);
730                                                 }
731                                                 else {
732                                                         sub_v3_v3v3(tmp_vec1, tmp_vec2, tmp_vec1);
733                                                 }
734                                         }
735                                         else {
736                                                 /* only 1 edge connected - same as above except
737                                                  * don't need to average edge direction */
738                                                 if (vc->e[0]->v2 == i) {
739                                                         sub_v3_v3v3(tmp_vec1, mvert_new[i].co, mvert_new[vc->v[0]].co);
740                                                 }
741                                                 else {
742                                                         sub_v3_v3v3(tmp_vec1, mvert_new[vc->v[0]].co, mvert_new[i].co);
743                                                 }
744                                         }
745
746                                         /* tmp_vec2 - is a line 90d from the pivot to the vec
747                                          * This is used so the resulting normal points directly away from the middle */
748                                         cross_v3_v3v3(tmp_vec2, axis_vec, vc->co);
749
750                                         if (UNLIKELY(is_zero_v3(tmp_vec2))) {
751                                                 /* we're _on_ the axis, so copy it based on our winding */
752                                                 if (vc->e[0]->v2 == i) {
753                                                         negate_v3_v3(vc->no, axis_vec);
754                                                 }
755                                                 else {
756                                                         copy_v3_v3(vc->no, axis_vec);
757                                                 }
758                                         }
759                                         else {
760                                                 /* edge average vector and right angle to the pivot make the normal */
761                                                 cross_v3_v3v3(vc->no, tmp_vec1, tmp_vec2);
762                                         }
763
764                                 }
765                                 else {
766                                         copy_v3_v3(vc->no, vc->co);
767                                 }
768
769                                 /* we wont be looping on this data again so copy normals here */
770                                 if ((angle < 0.0f) != do_flip)
771                                         negate_v3(vc->no);
772
773                                 normalize_v3(vc->no);
774                                 normal_float_to_short_v3(mvert_new[i].no, vc->no);
775
776                                 /* Done with normals */
777                         }
778                 }
779         }
780         else {
781                 mv_orig = mvert_orig;
782                 mv_new = mvert_new;
783
784                 for (i = 0; i < totvert; i++, mv_new++, mv_orig++) {
785                         copy_v3_v3(mv_new->co, mv_orig->co);
786                 }
787         }
788         /* done with edge connectivity based normal flipping */
789         
790         /* Add Faces */
791         for (step = 1; step < step_tot; step++) {
792                 const unsigned int varray_stride = totvert * step;
793                 float step_angle;
794                 float nor_tx[3];
795                 float mat[4][4];
796                 /* Rotation Matrix */
797                 step_angle = (angle / (float)(step_tot - (!close))) * (float)step;
798
799                 if (ltmd->ob_axis) {
800                         axis_angle_normalized_to_mat3(mat3, axis_vec, step_angle);
801                 }
802                 else {
803                         axis_angle_to_mat3_single(mat3, axis_char, step_angle);
804                 }
805                 copy_m4_m3(mat, mat3);
806
807                 if (screw_ofs)
808                         madd_v3_v3fl(mat[3], axis_vec, screw_ofs * ((float)step / (float)(step_tot - 1)));
809
810                 /* copy a slice */
811                 DM_copy_vert_data(dm, result, 0, (int)varray_stride, (int)totvert);
812                 
813                 mv_new_base = mvert_new;
814                 mv_new = &mvert_new[varray_stride]; /* advance to the next slice */
815                 
816                 for (j = 0; j < totvert; j++, mv_new_base++, mv_new++) {
817                         /* set normal */
818                         if (vert_connect) {
819                                 mul_v3_m3v3(nor_tx, mat3, vert_connect[j].no);
820
821                                 /* set the normal now its transformed */
822                                 normal_float_to_short_v3(mv_new->no, nor_tx);
823                         }
824                         
825                         /* set location */
826                         copy_v3_v3(mv_new->co, mv_new_base->co);
827                         
828                         /* only need to set these if using non cleared memory */
829                         /*mv_new->mat_nr = mv_new->flag = 0;*/
830                                 
831                         if (ltmd->ob_axis) {
832                                 sub_v3_v3(mv_new->co, mtx_tx[3]);
833
834                                 mul_m4_v3(mat, mv_new->co);
835
836                                 add_v3_v3(mv_new->co, mtx_tx[3]);
837                         }
838                         else {
839                                 mul_m4_v3(mat, mv_new->co);
840                         }
841                         
842                         /* add the new edge */
843                         med_new->v1 = varray_stride + j;
844                         med_new->v2 = med_new->v1 - totvert;
845                         med_new->flag = ME_EDGEDRAW | ME_EDGERENDER;
846                         med_new++;
847                 }
848         }
849
850         /* we can avoid if using vert alloc trick */
851         if (vert_connect) {
852                 MEM_freeN(vert_connect);
853                 vert_connect = NULL;
854         }
855
856         if (close) {
857                 /* last loop of edges, previous loop dosnt account for the last set of edges */
858                 const unsigned int varray_stride = (step_tot - 1) * totvert;
859
860                 for (i = 0; i < totvert; i++) {
861                         med_new->v1 = i;
862                         med_new->v2 = varray_stride + i;
863                         med_new->flag = ME_EDGEDRAW | ME_EDGERENDER;
864                         med_new++;
865                 }
866         }
867         
868         mp_new = mpoly_new;
869         ml_new = mloop_new;
870         med_new_firstloop = medge_new;
871         
872         /* more of an offset in this case */
873         edge_offset = totedge + (totvert * (step_tot - (close ? 0 : 1)));
874
875         for (i = 0; i < totedge; i++, med_new_firstloop++) {
876                 const unsigned int step_last = step_tot - (close ? 1 : 2);
877                 const unsigned int mpoly_index_orig = totpoly ? edge_poly_map[i] : UINT_MAX;
878                 const bool has_mpoly_orig = (mpoly_index_orig != UINT_MAX);
879                 float uv_v_offset_a, uv_v_offset_b;
880
881                 const unsigned int mloop_index_orig[2] = {
882                     vert_loop_map ? vert_loop_map[medge_new[i].v1] : UINT_MAX,
883                     vert_loop_map ? vert_loop_map[medge_new[i].v2] : UINT_MAX,
884                 };
885                 const bool has_mloop_orig = mloop_index_orig[0] != UINT_MAX;
886
887                 short mat_nr;
888
889                 /* for each edge, make a cylinder of quads */
890                 i1 = med_new_firstloop->v1;
891                 i2 = med_new_firstloop->v2;
892
893                 if (has_mpoly_orig) {
894                         mat_nr = mpoly_orig[mpoly_index_orig].mat_nr;
895                 }
896                 else {
897                         mat_nr = 0;
898                 }
899
900                 if (has_mloop_orig == false && mloopuv_layers_tot) {
901                         uv_v_offset_a = dist_signed_to_plane_v3(mvert_new[medge_new[i].v1].co, uv_axis_plane);
902                         uv_v_offset_b = dist_signed_to_plane_v3(mvert_new[medge_new[i].v2].co, uv_axis_plane);
903
904                         if (ltmd->flag & MOD_SCREW_UV_STRETCH_V) {
905                                 uv_v_offset_a = (uv_v_offset_a - uv_v_minmax[0]) * uv_v_range_inv;
906                                 uv_v_offset_b = (uv_v_offset_b - uv_v_minmax[0]) * uv_v_range_inv;
907                         }
908                 }
909
910                 for (step = 0; step <= step_last; step++) {
911
912                         /* Polygon */
913                         if (has_mpoly_orig) {
914                                 DM_copy_poly_data(dm, result, (int)mpoly_index_orig, (int)mpoly_index, 1);
915                                 origindex[mpoly_index] = (int)mpoly_index_orig;
916                         }
917                         else {
918                                 origindex[mpoly_index] = ORIGINDEX_NONE;
919                                 mp_new->flag = mpoly_flag;
920                                 mp_new->mat_nr = mat_nr;
921                         }
922                         mp_new->loopstart = mpoly_index * 4;
923                         mp_new->totloop = 4;
924
925
926                         /* Loop-Custom-Data */
927                         if (has_mloop_orig) {
928                                 int l_index = (int)(ml_new - mloop_new);
929                                 DM_copy_loop_data(dm, result, (int)mloop_index_orig[0], l_index + 0, 1);
930                                 DM_copy_loop_data(dm, result, (int)mloop_index_orig[1], l_index + 1, 1);
931                                 DM_copy_loop_data(dm, result, (int)mloop_index_orig[1], l_index + 2, 1);
932                                 DM_copy_loop_data(dm, result, (int)mloop_index_orig[0], l_index + 3, 1);
933
934                                 if (mloopuv_layers_tot) {
935                                         unsigned int uv_lay;
936                                         const float uv_u_offset_a = (float)(step)     * uv_u_scale;
937                                         const float uv_u_offset_b = (float)(step + 1) * uv_u_scale;
938                                         for (uv_lay = 0; uv_lay < mloopuv_layers_tot; uv_lay++) {
939                                                 MLoopUV *mluv = &mloopuv_layers[uv_lay][l_index];
940
941                                                 mluv[quad_ord[0]].uv[0] += uv_u_offset_a;
942                                                 mluv[quad_ord[1]].uv[0] += uv_u_offset_a;
943                                                 mluv[quad_ord[2]].uv[0] += uv_u_offset_b;
944                                                 mluv[quad_ord[3]].uv[0] += uv_u_offset_b;
945                                         }
946                                 }
947                         }
948                         else {
949                                 if (mloopuv_layers_tot) {
950                                         int l_index = (int)(ml_new - mloop_new);
951
952                                         unsigned int uv_lay;
953                                         const float uv_u_offset_a = (float)(step)     * uv_u_scale;
954                                         const float uv_u_offset_b = (float)(step + 1) * uv_u_scale;
955                                         for (uv_lay = 0; uv_lay < mloopuv_layers_tot; uv_lay++) {
956                                                 MLoopUV *mluv = &mloopuv_layers[uv_lay][l_index];
957
958                                                 copy_v2_fl2(mluv[quad_ord[0]].uv, uv_u_offset_a, uv_v_offset_a);
959                                                 copy_v2_fl2(mluv[quad_ord[1]].uv, uv_u_offset_a, uv_v_offset_b);
960                                                 copy_v2_fl2(mluv[quad_ord[2]].uv, uv_u_offset_b, uv_v_offset_b);
961                                                 copy_v2_fl2(mluv[quad_ord[3]].uv, uv_u_offset_b, uv_v_offset_a);
962                                         }
963                                 }
964                         }
965
966                         /* Loop-Data */
967                         if (!(close && step == step_last)) {
968                                 /* regular segments */
969                                 ml_new[quad_ord[0]].v = i1;
970                                 ml_new[quad_ord[1]].v = i2;
971                                 ml_new[quad_ord[2]].v = i2 + totvert;
972                                 ml_new[quad_ord[3]].v = i1 + totvert;
973
974                                 ml_new[quad_ord_ofs[0]].e = step == 0 ? i : (edge_offset + step + (i * (step_tot - 1))) - 1;
975                                 ml_new[quad_ord_ofs[1]].e = totedge + i2;
976                                 ml_new[quad_ord_ofs[2]].e = edge_offset + step + (i * (step_tot - 1));
977                                 ml_new[quad_ord_ofs[3]].e = totedge + i1;
978
979
980                                 /* new vertical edge */
981                                 if (step) { /* The first set is already done */
982                                         med_new->v1 = i1;
983                                         med_new->v2 = i2;
984                                         med_new->flag = med_new_firstloop->flag;
985                                         med_new->crease = med_new_firstloop->crease;
986                                         med_new++;
987                                 }
988                                 i1 += totvert;
989                                 i2 += totvert;
990                         }
991                         else {
992                                 /* last segment */
993                                 ml_new[quad_ord[0]].v = i1;
994                                 ml_new[quad_ord[1]].v = i2;
995                                 ml_new[quad_ord[2]].v = med_new_firstloop->v2;
996                                 ml_new[quad_ord[3]].v = med_new_firstloop->v1;
997
998                                 ml_new[quad_ord_ofs[0]].e = (edge_offset + step + (i * (step_tot - 1))) - 1;
999                                 ml_new[quad_ord_ofs[1]].e = totedge + i2;
1000                                 ml_new[quad_ord_ofs[2]].e = i;
1001                                 ml_new[quad_ord_ofs[3]].e = totedge + i1;
1002                         }
1003
1004                         mp_new++;
1005                         ml_new += 4;
1006                         mpoly_index++;
1007                 }
1008                 
1009                 /* new vertical edge */
1010                 med_new->v1 = i1;
1011                 med_new->v2 = i2;
1012                 med_new->flag = med_new_firstloop->flag & ~ME_LOOSEEDGE;
1013                 med_new->crease = med_new_firstloop->crease;
1014                 med_new++;
1015         }
1016
1017         /* validate loop edges */
1018 #if 0
1019         {
1020                 unsigned i = 0;
1021                 printf("\n");
1022                 for (; i < maxPolys * 4; i += 4) {
1023                         unsigned int ii;
1024                         ml_new = mloop_new + i;
1025                         ii = findEd(medge_new, maxEdges, ml_new[0].v, ml_new[1].v);
1026                         printf("%d %d -- ", ii, ml_new[0].e);
1027                         ml_new[0].e = ii;
1028
1029                         ii = findEd(medge_new, maxEdges, ml_new[1].v, ml_new[2].v);
1030                         printf("%d %d -- ", ii, ml_new[1].e);
1031                         ml_new[1].e = ii;
1032
1033                         ii = findEd(medge_new, maxEdges, ml_new[2].v, ml_new[3].v);
1034                         printf("%d %d -- ", ii, ml_new[2].e);
1035                         ml_new[2].e = ii;
1036
1037                         ii = findEd(medge_new, maxEdges, ml_new[3].v, ml_new[0].v);
1038                         printf("%d %d\n", ii, ml_new[3].e);
1039                         ml_new[3].e = ii;
1040
1041                 }
1042         }
1043 #endif
1044
1045         if (edge_poly_map) {
1046                 MEM_freeN(edge_poly_map);
1047         }
1048
1049         if (vert_loop_map) {
1050                 MEM_freeN(vert_loop_map);
1051         }
1052
1053         if ((ltmd->flag & MOD_SCREW_NORMAL_CALC) == 0) {
1054                 result->dirty |= DM_DIRTY_NORMALS;
1055         }
1056
1057         return result;
1058 }
1059
1060
1061 static void updateDepgraph(ModifierData *md, DagForest *forest,
1062                            struct Main *UNUSED(bmain),
1063                            struct Scene *UNUSED(scene),
1064                            Object *UNUSED(ob),
1065                            DagNode *obNode)
1066 {
1067         ScrewModifierData *ltmd = (ScrewModifierData *) md;
1068
1069         if (ltmd->ob_axis) {
1070                 DagNode *curNode = dag_get_node(forest, ltmd->ob_axis);
1071
1072                 dag_add_relation(forest, curNode, obNode,
1073                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA,
1074                                  "Screw Modifier");
1075         }
1076 }
1077
1078 static void updateDepsgraph(ModifierData *md,
1079                             struct Main *UNUSED(bmain),
1080                             struct Scene *UNUSED(scene),
1081                             Object *UNUSED(ob),
1082                             struct DepsNodeHandle *node)
1083 {
1084         ScrewModifierData *ltmd = (ScrewModifierData *)md;
1085         if (ltmd->ob_axis != NULL) {
1086                 DEG_add_object_relation(node, ltmd->ob_axis, DEG_OB_COMP_TRANSFORM, "Screw Modifier");
1087         }
1088 }
1089
1090 static void foreachObjectLink(
1091         ModifierData *md, Object *ob,
1092         ObjectWalkFunc walk, void *userData)
1093 {
1094         ScrewModifierData *ltmd = (ScrewModifierData *) md;
1095
1096         walk(userData, ob, &ltmd->ob_axis, IDWALK_NOP);
1097 }
1098
1099 ModifierTypeInfo modifierType_Screw = {
1100         /* name */              "Screw",
1101         /* structName */        "ScrewModifierData",
1102         /* structSize */        sizeof(ScrewModifierData),
1103         /* type */              eModifierTypeType_Constructive,
1104
1105         /* flags */             eModifierTypeFlag_AcceptsMesh |
1106                                 eModifierTypeFlag_AcceptsCVs |
1107                                 eModifierTypeFlag_SupportsEditmode |
1108                                 eModifierTypeFlag_EnableInEditmode,
1109
1110         /* copyData */          copyData,
1111         /* deformVerts */       NULL,
1112         /* deformMatrices */    NULL,
1113         /* deformVertsEM */     NULL,
1114         /* deformMatricesEM */  NULL,
1115         /* applyModifier */     applyModifier,
1116         /* applyModifierEM */   NULL,
1117         /* initData */          initData,
1118         /* requiredDataMask */  NULL,
1119         /* freeData */          NULL,
1120         /* isDisabled */        NULL,
1121         /* updateDepgraph */    updateDepgraph,
1122         /* updateDepsgraph */   updateDepsgraph,
1123         /* dependsOnTime */     NULL,
1124         /* dependsOnNormals */  NULL,
1125         /* foreachObjectLink */ foreachObjectLink,
1126         /* foreachIDLink */     NULL,
1127         /* foreachTexLink */    NULL,
1128 };