44ab4b066c1599cdd15ce928201c5087cc032b92
[blender.git] / source / blender / blenkernel / intern / lattice.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #include <stdio.h>
25 #include <string.h>
26 #include <math.h>
27 #include <stdlib.h>
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_utildefines.h"
32 #include "BLI_listbase.h"
33 #include "BLI_bitmap.h"
34 #include "BLI_math.h"
35 #include "BLI_task.h"
36
37 #include "DNA_mesh_types.h"
38 #include "DNA_meshdata_types.h"
39 #include "DNA_scene_types.h"
40 #include "DNA_object_types.h"
41 #include "DNA_lattice_types.h"
42 #include "DNA_curve_types.h"
43 #include "DNA_key_types.h"
44
45 #include "BKE_animsys.h"
46 #include "BKE_anim.h"
47 #include "BKE_cdderivedmesh.h"
48 #include "BKE_curve.h"
49 #include "BKE_displist.h"
50 #include "BKE_key.h"
51 #include "BKE_lattice.h"
52 #include "BKE_library.h"
53 #include "BKE_main.h"
54 #include "BKE_modifier.h"
55 #include "BKE_object.h"
56
57 #include "BKE_deform.h"
58
59 #include "DEG_depsgraph_query.h"
60
61 int BKE_lattice_index_from_uvw(Lattice *lt, const int u, const int v, const int w)
62 {
63   const int totu = lt->pntsu;
64   const int totv = lt->pntsv;
65
66   return (w * (totu * totv) + (v * totu) + u);
67 }
68
69 void BKE_lattice_index_to_uvw(Lattice *lt, const int index, int *r_u, int *r_v, int *r_w)
70 {
71   const int totu = lt->pntsu;
72   const int totv = lt->pntsv;
73
74   *r_u = (index % totu);
75   *r_v = (index / totu) % totv;
76   *r_w = (index / (totu * totv));
77 }
78
79 int BKE_lattice_index_flip(
80     Lattice *lt, const int index, const bool flip_u, const bool flip_v, const bool flip_w)
81 {
82   int u, v, w;
83
84   BKE_lattice_index_to_uvw(lt, index, &u, &v, &w);
85
86   if (flip_u) {
87     u = (lt->pntsu - 1) - u;
88   }
89
90   if (flip_v) {
91     v = (lt->pntsv - 1) - v;
92   }
93
94   if (flip_w) {
95     w = (lt->pntsw - 1) - w;
96   }
97
98   return BKE_lattice_index_from_uvw(lt, u, v, w);
99 }
100
101 void BKE_lattice_bitmap_from_flag(
102     Lattice *lt, BLI_bitmap *bitmap, const short flag, const bool clear, const bool respecthide)
103 {
104   const unsigned int tot = lt->pntsu * lt->pntsv * lt->pntsw;
105   unsigned int i;
106   BPoint *bp;
107
108   bp = lt->def;
109   for (i = 0; i < tot; i++, bp++) {
110     if ((bp->f1 & flag) && (!respecthide || !bp->hide)) {
111       BLI_BITMAP_ENABLE(bitmap, i);
112     }
113     else {
114       if (clear) {
115         BLI_BITMAP_DISABLE(bitmap, i);
116       }
117     }
118   }
119 }
120
121 void calc_lat_fudu(int flag, int res, float *r_fu, float *r_du)
122 {
123   if (res == 1) {
124     *r_fu = 0.0;
125     *r_du = 0.0;
126   }
127   else if (flag & LT_GRID) {
128     *r_fu = -0.5f * (res - 1);
129     *r_du = 1.0f;
130   }
131   else {
132     *r_fu = -1.0f;
133     *r_du = 2.0f / (res - 1);
134   }
135 }
136
137 void BKE_lattice_resize(Lattice *lt, int uNew, int vNew, int wNew, Object *ltOb)
138 {
139   BPoint *bp;
140   int i, u, v, w;
141   float fu, fv, fw, uc, vc, wc, du = 0.0, dv = 0.0, dw = 0.0;
142   float *co, (*vertexCos)[3] = NULL;
143
144   /* vertex weight groups are just freed all for now */
145   if (lt->dvert) {
146     BKE_defvert_array_free(lt->dvert, lt->pntsu * lt->pntsv * lt->pntsw);
147     lt->dvert = NULL;
148   }
149
150   while (uNew * vNew * wNew > 32000) {
151     if (uNew >= vNew && uNew >= wNew) {
152       uNew--;
153     }
154     else if (vNew >= uNew && vNew >= wNew) {
155       vNew--;
156     }
157     else {
158       wNew--;
159     }
160   }
161
162   vertexCos = MEM_mallocN(sizeof(*vertexCos) * uNew * vNew * wNew, "tmp_vcos");
163
164   calc_lat_fudu(lt->flag, uNew, &fu, &du);
165   calc_lat_fudu(lt->flag, vNew, &fv, &dv);
166   calc_lat_fudu(lt->flag, wNew, &fw, &dw);
167
168   /* If old size is different then resolution changed in interface,
169    * try to do clever reinit of points. Pretty simply idea, we just
170    * deform new verts by old lattice, but scaling them to match old
171    * size first.
172    */
173   if (ltOb) {
174     if (uNew != 1 && lt->pntsu != 1) {
175       fu = lt->fu;
176       du = (lt->pntsu - 1) * lt->du / (uNew - 1);
177     }
178
179     if (vNew != 1 && lt->pntsv != 1) {
180       fv = lt->fv;
181       dv = (lt->pntsv - 1) * lt->dv / (vNew - 1);
182     }
183
184     if (wNew != 1 && lt->pntsw != 1) {
185       fw = lt->fw;
186       dw = (lt->pntsw - 1) * lt->dw / (wNew - 1);
187     }
188   }
189
190   co = vertexCos[0];
191   for (w = 0, wc = fw; w < wNew; w++, wc += dw) {
192     for (v = 0, vc = fv; v < vNew; v++, vc += dv) {
193       for (u = 0, uc = fu; u < uNew; u++, co += 3, uc += du) {
194         co[0] = uc;
195         co[1] = vc;
196         co[2] = wc;
197       }
198     }
199   }
200
201   if (ltOb) {
202     float mat[4][4];
203     int typeu = lt->typeu, typev = lt->typev, typew = lt->typew;
204
205     /* works best if we force to linear type (endpoints match) */
206     lt->typeu = lt->typev = lt->typew = KEY_LINEAR;
207
208     if (ltOb->runtime.curve_cache) {
209       /* prevent using deformed locations */
210       BKE_displist_free(&ltOb->runtime.curve_cache->disp);
211     }
212
213     copy_m4_m4(mat, ltOb->obmat);
214     unit_m4(ltOb->obmat);
215     lattice_deform_verts(ltOb, NULL, NULL, vertexCos, uNew * vNew * wNew, NULL, 1.0f);
216     copy_m4_m4(ltOb->obmat, mat);
217
218     lt->typeu = typeu;
219     lt->typev = typev;
220     lt->typew = typew;
221   }
222
223   lt->fu = fu;
224   lt->fv = fv;
225   lt->fw = fw;
226   lt->du = du;
227   lt->dv = dv;
228   lt->dw = dw;
229
230   lt->pntsu = uNew;
231   lt->pntsv = vNew;
232   lt->pntsw = wNew;
233
234   lt->actbp = LT_ACTBP_NONE;
235   MEM_freeN(lt->def);
236   lt->def = MEM_callocN(lt->pntsu * lt->pntsv * lt->pntsw * sizeof(BPoint), "lattice bp");
237
238   bp = lt->def;
239
240   for (i = 0; i < lt->pntsu * lt->pntsv * lt->pntsw; i++, bp++) {
241     copy_v3_v3(bp->vec, vertexCos[i]);
242   }
243
244   MEM_freeN(vertexCos);
245 }
246
247 void BKE_lattice_init(Lattice *lt)
248 {
249   BLI_assert(MEMCMP_STRUCT_AFTER_IS_ZERO(lt, id));
250
251   lt->flag = LT_GRID;
252
253   lt->typeu = lt->typev = lt->typew = KEY_BSPLINE;
254
255   lt->def = MEM_callocN(sizeof(BPoint), "lattvert"); /* temporary */
256   BKE_lattice_resize(lt, 2, 2, 2, NULL);             /* creates a uniform lattice */
257   lt->actbp = LT_ACTBP_NONE;
258 }
259
260 Lattice *BKE_lattice_add(Main *bmain, const char *name)
261 {
262   Lattice *lt;
263
264   lt = BKE_libblock_alloc(bmain, ID_LT, name, 0);
265
266   BKE_lattice_init(lt);
267
268   return lt;
269 }
270
271 /**
272  * Only copy internal data of Lattice ID from source
273  * to already allocated/initialized destination.
274  * You probably never want to use that directly,
275  * use #BKE_id_copy or #BKE_id_copy_ex for typical needs.
276  *
277  * WARNING! This function will not handle ID user count!
278  *
279  * \param flag: Copying options (see BKE_library.h's LIB_ID_COPY_... flags for more).
280  */
281 void BKE_lattice_copy_data(Main *bmain, Lattice *lt_dst, const Lattice *lt_src, const int flag)
282 {
283   lt_dst->def = MEM_dupallocN(lt_src->def);
284
285   if (lt_src->key && (flag & LIB_ID_COPY_SHAPEKEY)) {
286     BKE_id_copy_ex(bmain, &lt_src->key->id, (ID **)&lt_dst->key, flag);
287   }
288
289   if (lt_src->dvert) {
290     int tot = lt_src->pntsu * lt_src->pntsv * lt_src->pntsw;
291     lt_dst->dvert = MEM_mallocN(sizeof(MDeformVert) * tot, "Lattice MDeformVert");
292     BKE_defvert_array_copy(lt_dst->dvert, lt_src->dvert, tot);
293   }
294
295   lt_dst->editlatt = NULL;
296 }
297
298 Lattice *BKE_lattice_copy(Main *bmain, const Lattice *lt)
299 {
300   Lattice *lt_copy;
301   BKE_id_copy(bmain, &lt->id, (ID **)&lt_copy);
302   return lt_copy;
303 }
304
305 /** Free (or release) any data used by this lattice (does not free the lattice itself). */
306 void BKE_lattice_free(Lattice *lt)
307 {
308   BKE_animdata_free(&lt->id, false);
309
310   BKE_lattice_batch_cache_free(lt);
311
312   MEM_SAFE_FREE(lt->def);
313   if (lt->dvert) {
314     BKE_defvert_array_free(lt->dvert, lt->pntsu * lt->pntsv * lt->pntsw);
315     lt->dvert = NULL;
316   }
317   if (lt->editlatt) {
318     Lattice *editlt = lt->editlatt->latt;
319
320     if (editlt->def) {
321       MEM_freeN(editlt->def);
322     }
323     if (editlt->dvert) {
324       BKE_defvert_array_free(editlt->dvert, lt->pntsu * lt->pntsv * lt->pntsw);
325     }
326
327     MEM_freeN(editlt);
328     MEM_freeN(lt->editlatt);
329     lt->editlatt = NULL;
330   }
331 }
332
333 void BKE_lattice_make_local(Main *bmain, Lattice *lt, const bool lib_local)
334 {
335   BKE_id_make_local_generic(bmain, &lt->id, true, lib_local);
336 }
337
338 typedef struct LatticeDeformData {
339   Object *object;
340   float *latticedata;
341   float latmat[4][4];
342 } LatticeDeformData;
343
344 LatticeDeformData *init_latt_deform(Object *oblatt, Object *ob)
345 {
346   /* we make an array with all differences */
347   Lattice *lt = oblatt->data;
348   BPoint *bp;
349   DispList *dl = oblatt->runtime.curve_cache ?
350                      BKE_displist_find(&oblatt->runtime.curve_cache->disp, DL_VERTS) :
351                      NULL;
352   const float *co = dl ? dl->verts : NULL;
353   float *fp, imat[4][4];
354   float fu, fv, fw;
355   int u, v, w;
356   float *latticedata;
357   float latmat[4][4];
358   LatticeDeformData *lattice_deform_data;
359
360   if (lt->editlatt) {
361     lt = lt->editlatt->latt;
362   }
363   bp = lt->def;
364
365   fp = latticedata = MEM_mallocN(sizeof(float) * 3 * lt->pntsu * lt->pntsv * lt->pntsw,
366                                  "latticedata");
367
368   /* for example with a particle system: (ob == NULL) */
369   if (ob == NULL) {
370     /* in deformspace, calc matrix  */
371     invert_m4_m4(latmat, oblatt->obmat);
372
373     /* back: put in deform array */
374     invert_m4_m4(imat, latmat);
375   }
376   else {
377     /* in deformspace, calc matrix */
378     invert_m4_m4(imat, oblatt->obmat);
379     mul_m4_m4m4(latmat, imat, ob->obmat);
380
381     /* back: put in deform array */
382     invert_m4_m4(imat, latmat);
383   }
384
385   for (w = 0, fw = lt->fw; w < lt->pntsw; w++, fw += lt->dw) {
386     for (v = 0, fv = lt->fv; v < lt->pntsv; v++, fv += lt->dv) {
387       for (u = 0, fu = lt->fu; u < lt->pntsu; u++, bp++, co += 3, fp += 3, fu += lt->du) {
388         if (dl) {
389           fp[0] = co[0] - fu;
390           fp[1] = co[1] - fv;
391           fp[2] = co[2] - fw;
392         }
393         else {
394           fp[0] = bp->vec[0] - fu;
395           fp[1] = bp->vec[1] - fv;
396           fp[2] = bp->vec[2] - fw;
397         }
398
399         mul_mat3_m4_v3(imat, fp);
400       }
401     }
402   }
403
404   lattice_deform_data = MEM_mallocN(sizeof(LatticeDeformData), "Lattice Deform Data");
405   lattice_deform_data->latticedata = latticedata;
406   lattice_deform_data->object = oblatt;
407   copy_m4_m4(lattice_deform_data->latmat, latmat);
408
409   return lattice_deform_data;
410 }
411
412 void calc_latt_deform(LatticeDeformData *lattice_deform_data, float co[3], float weight)
413 {
414   Object *ob = lattice_deform_data->object;
415   Lattice *lt = ob->data;
416   float u, v, w, tu[4], tv[4], tw[4];
417   float vec[3];
418   int idx_w, idx_v, idx_u;
419   int ui, vi, wi, uu, vv, ww;
420
421   /* vgroup influence */
422   int defgrp_index = -1;
423   float co_prev[3], weight_blend = 0.0f;
424   MDeformVert *dvert = BKE_lattice_deform_verts_get(ob);
425   float *__restrict latticedata = lattice_deform_data->latticedata;
426
427   if (lt->editlatt) {
428     lt = lt->editlatt->latt;
429   }
430   if (latticedata == NULL) {
431     return;
432   }
433
434   if (lt->vgroup[0] && dvert) {
435     defgrp_index = defgroup_name_index(ob, lt->vgroup);
436     copy_v3_v3(co_prev, co);
437   }
438
439   /* co is in local coords, treat with latmat */
440   mul_v3_m4v3(vec, lattice_deform_data->latmat, co);
441
442   /* u v w coords */
443
444   if (lt->pntsu > 1) {
445     u = (vec[0] - lt->fu) / lt->du;
446     ui = (int)floor(u);
447     u -= ui;
448     key_curve_position_weights(u, tu, lt->typeu);
449   }
450   else {
451     tu[0] = tu[2] = tu[3] = 0.0;
452     tu[1] = 1.0;
453     ui = 0;
454   }
455
456   if (lt->pntsv > 1) {
457     v = (vec[1] - lt->fv) / lt->dv;
458     vi = (int)floor(v);
459     v -= vi;
460     key_curve_position_weights(v, tv, lt->typev);
461   }
462   else {
463     tv[0] = tv[2] = tv[3] = 0.0;
464     tv[1] = 1.0;
465     vi = 0;
466   }
467
468   if (lt->pntsw > 1) {
469     w = (vec[2] - lt->fw) / lt->dw;
470     wi = (int)floor(w);
471     w -= wi;
472     key_curve_position_weights(w, tw, lt->typew);
473   }
474   else {
475     tw[0] = tw[2] = tw[3] = 0.0;
476     tw[1] = 1.0;
477     wi = 0;
478   }
479
480   for (ww = wi - 1; ww <= wi + 2; ww++) {
481     w = tw[ww - wi + 1];
482
483     if (w != 0.0f) {
484       if (ww > 0) {
485         if (ww < lt->pntsw) {
486           idx_w = ww * lt->pntsu * lt->pntsv;
487         }
488         else {
489           idx_w = (lt->pntsw - 1) * lt->pntsu * lt->pntsv;
490         }
491       }
492       else {
493         idx_w = 0;
494       }
495
496       for (vv = vi - 1; vv <= vi + 2; vv++) {
497         v = w * tv[vv - vi + 1];
498
499         if (v != 0.0f) {
500           if (vv > 0) {
501             if (vv < lt->pntsv) {
502               idx_v = idx_w + vv * lt->pntsu;
503             }
504             else {
505               idx_v = idx_w + (lt->pntsv - 1) * lt->pntsu;
506             }
507           }
508           else {
509             idx_v = idx_w;
510           }
511
512           for (uu = ui - 1; uu <= ui + 2; uu++) {
513             u = weight * v * tu[uu - ui + 1];
514
515             if (u != 0.0f) {
516               if (uu > 0) {
517                 if (uu < lt->pntsu) {
518                   idx_u = idx_v + uu;
519                 }
520                 else {
521                   idx_u = idx_v + (lt->pntsu - 1);
522                 }
523               }
524               else {
525                 idx_u = idx_v;
526               }
527
528               madd_v3_v3fl(co, &latticedata[idx_u * 3], u);
529
530               if (defgrp_index != -1) {
531                 weight_blend += (u * defvert_find_weight(dvert + idx_u, defgrp_index));
532               }
533             }
534           }
535         }
536       }
537     }
538   }
539
540   if (defgrp_index != -1) {
541     interp_v3_v3v3(co, co_prev, co, weight_blend);
542   }
543 }
544
545 void end_latt_deform(LatticeDeformData *lattice_deform_data)
546 {
547   if (lattice_deform_data->latticedata) {
548     MEM_freeN(lattice_deform_data->latticedata);
549   }
550
551   MEM_freeN(lattice_deform_data);
552 }
553
554 /* calculations is in local space of deformed object
555  * so we store in latmat transform from path coord inside object
556  */
557 typedef struct {
558   float dmin[3], dmax[3];
559   float curvespace[4][4], objectspace[4][4], objectspace3[3][3];
560   int no_rot_axis;
561 } CurveDeform;
562
563 static void init_curve_deform(Object *par, Object *ob, CurveDeform *cd)
564 {
565   invert_m4_m4(ob->imat, ob->obmat);
566   mul_m4_m4m4(cd->objectspace, ob->imat, par->obmat);
567   invert_m4_m4(cd->curvespace, cd->objectspace);
568   copy_m3_m4(cd->objectspace3, cd->objectspace);
569   cd->no_rot_axis = 0;
570 }
571
572 /* this makes sure we can extend for non-cyclic.
573  *
574  * returns OK: 1/0
575  */
576 static bool where_on_path_deform(
577     Object *ob, float ctime, float vec[4], float dir[3], float quat[4], float *radius)
578 {
579   BevList *bl;
580   float ctime1;
581   int cycl = 0;
582
583   /* test for cyclic */
584   bl = ob->runtime.curve_cache->bev.first;
585   if (!bl->nr) {
586     return false;
587   }
588   if (bl->poly > -1) {
589     cycl = 1;
590   }
591
592   if (cycl == 0) {
593     ctime1 = CLAMPIS(ctime, 0.0f, 1.0f);
594   }
595   else {
596     ctime1 = ctime;
597   }
598
599   /* vec needs 4 items */
600   if (where_on_path(ob, ctime1, vec, dir, quat, radius, NULL)) {
601
602     if (cycl == 0) {
603       Path *path = ob->runtime.curve_cache->path;
604       float dvec[3];
605
606       if (ctime < 0.0f) {
607         sub_v3_v3v3(dvec, path->data[1].vec, path->data[0].vec);
608         mul_v3_fl(dvec, ctime * (float)path->len);
609         add_v3_v3(vec, dvec);
610         if (quat) {
611           copy_qt_qt(quat, path->data[0].quat);
612         }
613         if (radius) {
614           *radius = path->data[0].radius;
615         }
616       }
617       else if (ctime > 1.0f) {
618         sub_v3_v3v3(dvec, path->data[path->len - 1].vec, path->data[path->len - 2].vec);
619         mul_v3_fl(dvec, (ctime - 1.0f) * (float)path->len);
620         add_v3_v3(vec, dvec);
621         if (quat) {
622           copy_qt_qt(quat, path->data[path->len - 1].quat);
623         }
624         if (radius) {
625           *radius = path->data[path->len - 1].radius;
626         }
627         /* weight - not used but could be added */
628       }
629     }
630     return true;
631   }
632   return false;
633 }
634
635 /* for each point, rotate & translate to curve */
636 /* use path, since it has constant distances */
637 /* co: local coord, result local too */
638 /* returns quaternion for rotation, using cd->no_rot_axis */
639 /* axis is using another define!!! */
640 static bool calc_curve_deform(
641     Object *par, float co[3], const short axis, CurveDeform *cd, float r_quat[4])
642 {
643   Curve *cu = par->data;
644   float fac, loc[4], dir[3], new_quat[4], radius;
645   short index;
646   const bool is_neg_axis = (axis > 2);
647
648   if (par->runtime.curve_cache == NULL) {
649     /* Happens with a cyclic dependencies. */
650     return false;
651   }
652
653   if (par->runtime.curve_cache->path == NULL) {
654     return false; /* happens on append, cyclic dependencies and empty curves */
655   }
656
657   /* options */
658   if (is_neg_axis) {
659     index = axis - 3;
660     if (cu->flag & CU_STRETCH) {
661       fac = -(co[index] - cd->dmax[index]) / (cd->dmax[index] - cd->dmin[index]);
662     }
663     else {
664       fac = -(co[index] - cd->dmax[index]) / (par->runtime.curve_cache->path->totdist);
665     }
666   }
667   else {
668     index = axis;
669     if (cu->flag & CU_STRETCH) {
670       fac = (co[index] - cd->dmin[index]) / (cd->dmax[index] - cd->dmin[index]);
671     }
672     else {
673       if (LIKELY(par->runtime.curve_cache->path->totdist > FLT_EPSILON)) {
674         fac = +(co[index] - cd->dmin[index]) / (par->runtime.curve_cache->path->totdist);
675       }
676       else {
677         fac = 0.0f;
678       }
679     }
680   }
681
682   if (where_on_path_deform(par, fac, loc, dir, new_quat, &radius)) { /* returns OK */
683     float quat[4], cent[3];
684
685     if (cd->no_rot_axis) { /* set by caller */
686
687       /* This is not exactly the same as 2.4x, since the axis is having rotation removed rather
688        * than changing the axis before calculating the tilt but serves much the same purpose. */
689       float dir_flat[3] = {0, 0, 0}, q[4];
690       copy_v3_v3(dir_flat, dir);
691       dir_flat[cd->no_rot_axis - 1] = 0.0f;
692
693       normalize_v3(dir);
694       normalize_v3(dir_flat);
695
696       rotation_between_vecs_to_quat(q, dir, dir_flat); /* Could this be done faster? */
697
698       mul_qt_qtqt(new_quat, q, new_quat);
699     }
700
701     /* Logic for 'cent' orientation *
702      *
703      * The way 'co' is copied to 'cent' may seem to have no meaning, but it does.
704      *
705      * Use a curve modifier to stretch a cube out, color each side RGB,
706      * positive side light, negative dark.
707      * view with X up (default), from the angle that you can see 3 faces RGB colors (light),
708      * anti-clockwise
709      * Notice X,Y,Z Up all have light colors and each ordered CCW.
710      *
711      * Now for Neg Up XYZ, the colors are all dark, and ordered clockwise - Campbell
712      *
713      * note: moved functions into quat_apply_track/vec_apply_track
714      * */
715     copy_qt_qt(quat, new_quat);
716     copy_v3_v3(cent, co);
717
718     /* zero the axis which is not used,
719      * the big block of text above now applies to these 3 lines */
720     quat_apply_track(
721         quat,
722         axis,
723         (axis == 0 || axis == 2) ? 1 : 0); /* up flag is a dummy, set so no rotation is done */
724     vec_apply_track(cent, axis);
725     cent[index] = 0.0f;
726
727     /* scale if enabled */
728     if (cu->flag & CU_PATH_RADIUS) {
729       mul_v3_fl(cent, radius);
730     }
731
732     /* local rotation */
733     normalize_qt(quat);
734     mul_qt_v3(quat, cent);
735
736     /* translation */
737     add_v3_v3v3(co, cent, loc);
738
739     if (r_quat) {
740       copy_qt_qt(r_quat, quat);
741     }
742
743     return true;
744   }
745   return false;
746 }
747
748 void curve_deform_verts(Object *cuOb,
749                         Object *target,
750                         float (*vertexCos)[3],
751                         int numVerts,
752                         MDeformVert *dvert,
753                         const int defgrp_index,
754                         short defaxis)
755 {
756   Curve *cu;
757   int a;
758   CurveDeform cd;
759   const bool is_neg_axis = (defaxis > 2);
760
761   if (cuOb->type != OB_CURVE) {
762     return;
763   }
764
765   cu = cuOb->data;
766
767   init_curve_deform(cuOb, target, &cd);
768
769   /* dummy bounds, keep if CU_DEFORM_BOUNDS_OFF is set */
770   if (is_neg_axis == false) {
771     cd.dmin[0] = cd.dmin[1] = cd.dmin[2] = 0.0f;
772     cd.dmax[0] = cd.dmax[1] = cd.dmax[2] = 1.0f;
773   }
774   else {
775     /* negative, these bounds give a good rest position */
776     cd.dmin[0] = cd.dmin[1] = cd.dmin[2] = -1.0f;
777     cd.dmax[0] = cd.dmax[1] = cd.dmax[2] = 0.0f;
778   }
779
780   if (dvert) {
781     MDeformVert *dvert_iter;
782     float vec[3];
783
784     if (cu->flag & CU_DEFORM_BOUNDS_OFF) {
785       for (a = 0, dvert_iter = dvert; a < numVerts; a++, dvert_iter++) {
786         const float weight = defvert_find_weight(dvert_iter, defgrp_index);
787
788         if (weight > 0.0f) {
789           mul_m4_v3(cd.curvespace, vertexCos[a]);
790           copy_v3_v3(vec, vertexCos[a]);
791           calc_curve_deform(cuOb, vec, defaxis, &cd, NULL);
792           interp_v3_v3v3(vertexCos[a], vertexCos[a], vec, weight);
793           mul_m4_v3(cd.objectspace, vertexCos[a]);
794         }
795       }
796     }
797     else {
798       /* set mesh min/max bounds */
799       INIT_MINMAX(cd.dmin, cd.dmax);
800
801       for (a = 0, dvert_iter = dvert; a < numVerts; a++, dvert_iter++) {
802         if (defvert_find_weight(dvert_iter, defgrp_index) > 0.0f) {
803           mul_m4_v3(cd.curvespace, vertexCos[a]);
804           minmax_v3v3_v3(cd.dmin, cd.dmax, vertexCos[a]);
805         }
806       }
807
808       for (a = 0, dvert_iter = dvert; a < numVerts; a++, dvert_iter++) {
809         const float weight = defvert_find_weight(dvert_iter, defgrp_index);
810
811         if (weight > 0.0f) {
812           /* already in 'cd.curvespace', prev for loop */
813           copy_v3_v3(vec, vertexCos[a]);
814           calc_curve_deform(cuOb, vec, defaxis, &cd, NULL);
815           interp_v3_v3v3(vertexCos[a], vertexCos[a], vec, weight);
816           mul_m4_v3(cd.objectspace, vertexCos[a]);
817         }
818       }
819     }
820   }
821   else {
822     if (cu->flag & CU_DEFORM_BOUNDS_OFF) {
823       for (a = 0; a < numVerts; a++) {
824         mul_m4_v3(cd.curvespace, vertexCos[a]);
825         calc_curve_deform(cuOb, vertexCos[a], defaxis, &cd, NULL);
826         mul_m4_v3(cd.objectspace, vertexCos[a]);
827       }
828     }
829     else {
830       /* set mesh min max bounds */
831       INIT_MINMAX(cd.dmin, cd.dmax);
832
833       for (a = 0; a < numVerts; a++) {
834         mul_m4_v3(cd.curvespace, vertexCos[a]);
835         minmax_v3v3_v3(cd.dmin, cd.dmax, vertexCos[a]);
836       }
837
838       for (a = 0; a < numVerts; a++) {
839         /* already in 'cd.curvespace', prev for loop */
840         calc_curve_deform(cuOb, vertexCos[a], defaxis, &cd, NULL);
841         mul_m4_v3(cd.objectspace, vertexCos[a]);
842       }
843     }
844   }
845 }
846
847 /* input vec and orco = local coord in armature space */
848 /* orco is original not-animated or deformed reference point */
849 /* result written in vec and mat */
850 void curve_deform_vector(
851     Object *cuOb, Object *target, float orco[3], float vec[3], float mat[3][3], int no_rot_axis)
852 {
853   CurveDeform cd;
854   float quat[4];
855
856   if (cuOb->type != OB_CURVE) {
857     unit_m3(mat);
858     return;
859   }
860
861   init_curve_deform(cuOb, target, &cd);
862   cd.no_rot_axis = no_rot_axis; /* option to only rotate for XY, for example */
863
864   copy_v3_v3(cd.dmin, orco);
865   copy_v3_v3(cd.dmax, orco);
866
867   mul_m4_v3(cd.curvespace, vec);
868
869   if (calc_curve_deform(cuOb, vec, target->trackflag, &cd, quat)) {
870     float qmat[3][3];
871
872     quat_to_mat3(qmat, quat);
873     mul_m3_m3m3(mat, qmat, cd.objectspace3);
874   }
875   else {
876     unit_m3(mat);
877   }
878
879   mul_m4_v3(cd.objectspace, vec);
880 }
881
882 typedef struct LatticeDeformUserdata {
883   LatticeDeformData *lattice_deform_data;
884   float (*vertexCos)[3];
885   MDeformVert *dvert;
886   int defgrp_index;
887   float fac;
888 } LatticeDeformUserdata;
889
890 static void lattice_deform_vert_task(void *__restrict userdata,
891                                      const int index,
892                                      const TaskParallelTLS *__restrict UNUSED(tls))
893 {
894   const LatticeDeformUserdata *data = userdata;
895
896   if (data->dvert != NULL) {
897     const float weight = defvert_find_weight(data->dvert + index, data->defgrp_index);
898     if (weight > 0.0f) {
899       calc_latt_deform(data->lattice_deform_data, data->vertexCos[index], weight * data->fac);
900     }
901   }
902   else {
903     calc_latt_deform(data->lattice_deform_data, data->vertexCos[index], data->fac);
904   }
905 }
906
907 void lattice_deform_verts(Object *laOb,
908                           Object *target,
909                           Mesh *mesh,
910                           float (*vertexCos)[3],
911                           int numVerts,
912                           const char *vgroup,
913                           float fac)
914 {
915   LatticeDeformData *lattice_deform_data;
916   MDeformVert *dvert = NULL;
917   int defgrp_index = -1;
918
919   if (laOb->type != OB_LATTICE) {
920     return;
921   }
922
923   lattice_deform_data = init_latt_deform(laOb, target);
924
925   /* Check whether to use vertex groups (only possible if target is a Mesh or Lattice).
926    * We want either a Mesh/Lattice with no derived data, or derived data with deformverts.
927    */
928   if (vgroup && vgroup[0] && target && ELEM(target->type, OB_MESH, OB_LATTICE)) {
929     defgrp_index = defgroup_name_index(target, vgroup);
930
931     if (defgrp_index != -1) {
932       /* if there's derived data without deformverts, don't use vgroups */
933       if (mesh) {
934         dvert = CustomData_get_layer(&mesh->vdata, CD_MDEFORMVERT);
935       }
936       else if (target->type == OB_LATTICE) {
937         dvert = ((Lattice *)target->data)->dvert;
938       }
939       else {
940         dvert = ((Mesh *)target->data)->dvert;
941       }
942     }
943   }
944
945   LatticeDeformUserdata data = {.lattice_deform_data = lattice_deform_data,
946                                 .vertexCos = vertexCos,
947                                 .dvert = dvert,
948                                 .defgrp_index = defgrp_index,
949                                 .fac = fac};
950
951   TaskParallelSettings settings;
952   BLI_parallel_range_settings_defaults(&settings);
953   settings.min_iter_per_thread = 32;
954   BLI_task_parallel_range(0, numVerts, &data, lattice_deform_vert_task, &settings);
955
956   end_latt_deform(lattice_deform_data);
957 }
958
959 bool object_deform_mball(Object *ob, ListBase *dispbase)
960 {
961   if (ob->parent && ob->parent->type == OB_LATTICE && ob->partype == PARSKEL) {
962     DispList *dl;
963
964     for (dl = dispbase->first; dl; dl = dl->next) {
965       lattice_deform_verts(ob->parent, ob, NULL, (float(*)[3])dl->verts, dl->nr, NULL, 1.0f);
966     }
967
968     return true;
969   }
970   else {
971     return false;
972   }
973 }
974
975 static BPoint *latt_bp(Lattice *lt, int u, int v, int w)
976 {
977   return &lt->def[BKE_lattice_index_from_uvw(lt, u, v, w)];
978 }
979
980 void outside_lattice(Lattice *lt)
981 {
982   BPoint *bp, *bp1, *bp2;
983   int u, v, w;
984   float fac1, du = 0.0, dv = 0.0, dw = 0.0;
985
986   if (lt->flag & LT_OUTSIDE) {
987     bp = lt->def;
988
989     if (lt->pntsu > 1) {
990       du = 1.0f / ((float)lt->pntsu - 1);
991     }
992     if (lt->pntsv > 1) {
993       dv = 1.0f / ((float)lt->pntsv - 1);
994     }
995     if (lt->pntsw > 1) {
996       dw = 1.0f / ((float)lt->pntsw - 1);
997     }
998
999     for (w = 0; w < lt->pntsw; w++) {
1000
1001       for (v = 0; v < lt->pntsv; v++) {
1002
1003         for (u = 0; u < lt->pntsu; u++, bp++) {
1004           if (u == 0 || v == 0 || w == 0 || u == lt->pntsu - 1 || v == lt->pntsv - 1 ||
1005               w == lt->pntsw - 1) {
1006             /* pass */
1007           }
1008           else {
1009             bp->hide = 1;
1010             bp->f1 &= ~SELECT;
1011
1012             /* u extrema */
1013             bp1 = latt_bp(lt, 0, v, w);
1014             bp2 = latt_bp(lt, lt->pntsu - 1, v, w);
1015
1016             fac1 = du * u;
1017             bp->vec[0] = (1.0f - fac1) * bp1->vec[0] + fac1 * bp2->vec[0];
1018             bp->vec[1] = (1.0f - fac1) * bp1->vec[1] + fac1 * bp2->vec[1];
1019             bp->vec[2] = (1.0f - fac1) * bp1->vec[2] + fac1 * bp2->vec[2];
1020
1021             /* v extrema */
1022             bp1 = latt_bp(lt, u, 0, w);
1023             bp2 = latt_bp(lt, u, lt->pntsv - 1, w);
1024
1025             fac1 = dv * v;
1026             bp->vec[0] += (1.0f - fac1) * bp1->vec[0] + fac1 * bp2->vec[0];
1027             bp->vec[1] += (1.0f - fac1) * bp1->vec[1] + fac1 * bp2->vec[1];
1028             bp->vec[2] += (1.0f - fac1) * bp1->vec[2] + fac1 * bp2->vec[2];
1029
1030             /* w extrema */
1031             bp1 = latt_bp(lt, u, v, 0);
1032             bp2 = latt_bp(lt, u, v, lt->pntsw - 1);
1033
1034             fac1 = dw * w;
1035             bp->vec[0] += (1.0f - fac1) * bp1->vec[0] + fac1 * bp2->vec[0];
1036             bp->vec[1] += (1.0f - fac1) * bp1->vec[1] + fac1 * bp2->vec[1];
1037             bp->vec[2] += (1.0f - fac1) * bp1->vec[2] + fac1 * bp2->vec[2];
1038
1039             mul_v3_fl(bp->vec, 1.0f / 3.0f);
1040           }
1041         }
1042       }
1043     }
1044   }
1045   else {
1046     bp = lt->def;
1047
1048     for (w = 0; w < lt->pntsw; w++) {
1049       for (v = 0; v < lt->pntsv; v++) {
1050         for (u = 0; u < lt->pntsu; u++, bp++) {
1051           bp->hide = 0;
1052         }
1053       }
1054     }
1055   }
1056 }
1057
1058 float (*BKE_lattice_vertexcos_get(struct Object *ob, int *r_numVerts))[3]
1059 {
1060   Lattice *lt = ob->data;
1061   int i, numVerts;
1062   float(*vertexCos)[3];
1063
1064   if (lt->editlatt) {
1065     lt = lt->editlatt->latt;
1066   }
1067   numVerts = *r_numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1068
1069   vertexCos = MEM_mallocN(sizeof(*vertexCos) * numVerts, "lt_vcos");
1070
1071   for (i = 0; i < numVerts; i++) {
1072     copy_v3_v3(vertexCos[i], lt->def[i].vec);
1073   }
1074
1075   return vertexCos;
1076 }
1077
1078 void BKE_lattice_vertexcos_apply(struct Object *ob, const float (*vertexCos)[3])
1079 {
1080   Lattice *lt = ob->data;
1081   int i, numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1082
1083   for (i = 0; i < numVerts; i++) {
1084     copy_v3_v3(lt->def[i].vec, vertexCos[i]);
1085   }
1086 }
1087
1088 void BKE_lattice_modifiers_calc(struct Depsgraph *depsgraph, Scene *scene, Object *ob)
1089 {
1090   Lattice *lt = ob->data;
1091   /* Get vertex coordinates from the original copy;
1092    * otherwise we get already-modified coordinates. */
1093   Object *ob_orig = DEG_get_original_object(ob);
1094   VirtualModifierData virtualModifierData;
1095   ModifierData *md = modifiers_getVirtualModifierList(ob, &virtualModifierData);
1096   float(*vertexCos)[3] = NULL;
1097   int numVerts, editmode = (lt->editlatt != NULL);
1098   const ModifierEvalContext mectx = {depsgraph, ob, 0};
1099
1100   if (ob->runtime.curve_cache) {
1101     BKE_displist_free(&ob->runtime.curve_cache->disp);
1102   }
1103   else {
1104     ob->runtime.curve_cache = MEM_callocN(sizeof(CurveCache), "CurveCache for lattice");
1105   }
1106
1107   for (; md; md = md->next) {
1108     const ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1109
1110     if (!(mti->flags & eModifierTypeFlag_AcceptsLattice)) {
1111       continue;
1112     }
1113     if (!(md->mode & eModifierMode_Realtime)) {
1114       continue;
1115     }
1116     if (editmode && !(md->mode & eModifierMode_Editmode)) {
1117       continue;
1118     }
1119     if (mti->isDisabled && mti->isDisabled(scene, md, 0)) {
1120       continue;
1121     }
1122     if (mti->type != eModifierTypeType_OnlyDeform) {
1123       continue;
1124     }
1125
1126     if (!vertexCos) {
1127       vertexCos = BKE_lattice_vertexcos_get(ob_orig, &numVerts);
1128     }
1129     mti->deformVerts(md, &mectx, NULL, vertexCos, numVerts);
1130   }
1131
1132   if (ob->id.tag & LIB_TAG_COPIED_ON_WRITE) {
1133     if (vertexCos) {
1134       BKE_lattice_vertexcos_apply(ob, vertexCos);
1135       MEM_freeN(vertexCos);
1136     }
1137   }
1138   else {
1139     /* Displist won't do anything; this is just for posterity's sake until we remove it. */
1140     if (!vertexCos) {
1141       vertexCos = BKE_lattice_vertexcos_get(ob_orig, &numVerts);
1142     }
1143
1144     DispList *dl = MEM_callocN(sizeof(*dl), "lt_dl");
1145     dl->type = DL_VERTS;
1146     dl->parts = 1;
1147     dl->nr = numVerts;
1148     dl->verts = (float *)vertexCos;
1149
1150     BLI_addtail(&ob->runtime.curve_cache->disp, dl);
1151   }
1152 }
1153
1154 struct MDeformVert *BKE_lattice_deform_verts_get(struct Object *oblatt)
1155 {
1156   Lattice *lt = (Lattice *)oblatt->data;
1157   BLI_assert(oblatt->type == OB_LATTICE);
1158   if (lt->editlatt) {
1159     lt = lt->editlatt->latt;
1160   }
1161   return lt->dvert;
1162 }
1163
1164 struct BPoint *BKE_lattice_active_point_get(Lattice *lt)
1165 {
1166   BLI_assert(GS(lt->id.name) == ID_LT);
1167
1168   if (lt->editlatt) {
1169     lt = lt->editlatt->latt;
1170   }
1171
1172   BLI_assert(lt->actbp < lt->pntsu * lt->pntsv * lt->pntsw);
1173
1174   if ((lt->actbp != LT_ACTBP_NONE) && (lt->actbp < lt->pntsu * lt->pntsv * lt->pntsw)) {
1175     return &lt->def[lt->actbp];
1176   }
1177   else {
1178     return NULL;
1179   }
1180 }
1181
1182 void BKE_lattice_center_median(Lattice *lt, float cent[3])
1183 {
1184   int i, numVerts;
1185
1186   if (lt->editlatt) {
1187     lt = lt->editlatt->latt;
1188   }
1189   numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1190
1191   zero_v3(cent);
1192
1193   for (i = 0; i < numVerts; i++) {
1194     add_v3_v3(cent, lt->def[i].vec);
1195   }
1196
1197   mul_v3_fl(cent, 1.0f / (float)numVerts);
1198 }
1199
1200 static void boundbox_lattice(Object *ob)
1201 {
1202   BoundBox *bb;
1203   Lattice *lt;
1204   float min[3], max[3];
1205
1206   if (ob->runtime.bb == NULL) {
1207     ob->runtime.bb = MEM_callocN(sizeof(BoundBox), "Lattice boundbox");
1208   }
1209
1210   bb = ob->runtime.bb;
1211   lt = ob->data;
1212
1213   INIT_MINMAX(min, max);
1214   BKE_lattice_minmax_dl(ob, lt, min, max);
1215   BKE_boundbox_init_from_minmax(bb, min, max);
1216
1217   bb->flag &= ~BOUNDBOX_DIRTY;
1218 }
1219
1220 BoundBox *BKE_lattice_boundbox_get(Object *ob)
1221 {
1222   boundbox_lattice(ob);
1223
1224   return ob->runtime.bb;
1225 }
1226
1227 void BKE_lattice_minmax_dl(Object *ob, Lattice *lt, float min[3], float max[3])
1228 {
1229   DispList *dl = ob->runtime.curve_cache ?
1230                      BKE_displist_find(&ob->runtime.curve_cache->disp, DL_VERTS) :
1231                      NULL;
1232
1233   if (!dl) {
1234     BKE_lattice_minmax(lt, min, max);
1235   }
1236   else {
1237     int i, numVerts;
1238
1239     if (lt->editlatt) {
1240       lt = lt->editlatt->latt;
1241     }
1242     numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1243
1244     for (i = 0; i < numVerts; i++) {
1245       minmax_v3v3_v3(min, max, &dl->verts[i * 3]);
1246     }
1247   }
1248 }
1249
1250 void BKE_lattice_minmax(Lattice *lt, float min[3], float max[3])
1251 {
1252   int i, numVerts;
1253
1254   if (lt->editlatt) {
1255     lt = lt->editlatt->latt;
1256   }
1257   numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1258
1259   for (i = 0; i < numVerts; i++) {
1260     minmax_v3v3_v3(min, max, lt->def[i].vec);
1261   }
1262 }
1263
1264 void BKE_lattice_center_bounds(Lattice *lt, float cent[3])
1265 {
1266   float min[3], max[3];
1267
1268   INIT_MINMAX(min, max);
1269
1270   BKE_lattice_minmax(lt, min, max);
1271   mid_v3_v3v3(cent, min, max);
1272 }
1273
1274 void BKE_lattice_transform(Lattice *lt, float mat[4][4], bool do_keys)
1275 {
1276   BPoint *bp = lt->def;
1277   int i = lt->pntsu * lt->pntsv * lt->pntsw;
1278
1279   while (i--) {
1280     mul_m4_v3(mat, bp->vec);
1281     bp++;
1282   }
1283
1284   if (do_keys && lt->key) {
1285     KeyBlock *kb;
1286
1287     for (kb = lt->key->block.first; kb; kb = kb->next) {
1288       float *fp = kb->data;
1289       for (i = kb->totelem; i--; fp += 3) {
1290         mul_m4_v3(mat, fp);
1291       }
1292     }
1293   }
1294 }
1295
1296 void BKE_lattice_translate(Lattice *lt, float offset[3], bool do_keys)
1297 {
1298   int i, numVerts;
1299
1300   numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1301
1302   if (lt->def) {
1303     for (i = 0; i < numVerts; i++) {
1304       add_v3_v3(lt->def[i].vec, offset);
1305     }
1306   }
1307
1308   if (lt->editlatt) {
1309     for (i = 0; i < numVerts; i++) {
1310       add_v3_v3(lt->editlatt->latt->def[i].vec, offset);
1311     }
1312   }
1313
1314   if (do_keys && lt->key) {
1315     KeyBlock *kb;
1316
1317     for (kb = lt->key->block.first; kb; kb = kb->next) {
1318       float *fp = kb->data;
1319       for (i = kb->totelem; i--; fp += 3) {
1320         add_v3_v3(fp, offset);
1321       }
1322     }
1323   }
1324 }
1325
1326 bool BKE_lattice_is_any_selected(const Lattice *lt)
1327 {
1328   /* Intentionally don't handle 'lt->editlatt' (caller must do this). */
1329   const BPoint *bp = lt->def;
1330   int a = lt->pntsu * lt->pntsv * lt->pntsw;
1331   while (a--) {
1332     if (bp->hide == 0) {
1333       if (bp->f1 & SELECT) {
1334         return true;
1335       }
1336     }
1337     bp++;
1338   }
1339   return false;
1340 }
1341
1342 /* **** Depsgraph evaluation **** */
1343
1344 void BKE_lattice_eval_geometry(struct Depsgraph *UNUSED(depsgraph), Lattice *UNUSED(latt))
1345 {
1346 }
1347
1348 /* Draw Engine */
1349 void (*BKE_lattice_batch_cache_dirty_tag_cb)(Lattice *lt, int mode) = NULL;
1350 void (*BKE_lattice_batch_cache_free_cb)(Lattice *lt) = NULL;
1351
1352 void BKE_lattice_batch_cache_dirty_tag(Lattice *lt, int mode)
1353 {
1354   if (lt->batch_cache) {
1355     BKE_lattice_batch_cache_dirty_tag_cb(lt, mode);
1356   }
1357 }
1358 void BKE_lattice_batch_cache_free(Lattice *lt)
1359 {
1360   if (lt->batch_cache) {
1361     BKE_lattice_batch_cache_free_cb(lt);
1362   }
1363 }