Cleanup: pass lattice directly vertex coord utilities
[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(const Lattice *lt, int *r_numVerts))[3]
1059 {
1060   int i, numVerts;
1061   float(*vertexCos)[3];
1062
1063   if (lt->editlatt) {
1064     lt = lt->editlatt->latt;
1065   }
1066   numVerts = *r_numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1067
1068   vertexCos = MEM_mallocN(sizeof(*vertexCos) * numVerts, "lt_vcos");
1069
1070   for (i = 0; i < numVerts; i++) {
1071     copy_v3_v3(vertexCos[i], lt->def[i].vec);
1072   }
1073
1074   return vertexCos;
1075 }
1076
1077 void BKE_lattice_vertexcos_apply(Lattice *lt, const float (*vertexCos)[3])
1078 {
1079   int i, numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1080
1081   for (i = 0; i < numVerts; i++) {
1082     copy_v3_v3(lt->def[i].vec, vertexCos[i]);
1083   }
1084 }
1085
1086 void BKE_lattice_modifiers_calc(struct Depsgraph *depsgraph, Scene *scene, Object *ob)
1087 {
1088   Lattice *lt = ob->data;
1089   /* Get vertex coordinates from the original copy;
1090    * otherwise we get already-modified coordinates. */
1091   Object *ob_orig = DEG_get_original_object(ob);
1092   VirtualModifierData virtualModifierData;
1093   ModifierData *md = modifiers_getVirtualModifierList(ob, &virtualModifierData);
1094   float(*vertexCos)[3] = NULL;
1095   int numVerts, editmode = (lt->editlatt != NULL);
1096   const ModifierEvalContext mectx = {depsgraph, ob, 0};
1097
1098   if (ob->runtime.curve_cache) {
1099     BKE_displist_free(&ob->runtime.curve_cache->disp);
1100   }
1101   else {
1102     ob->runtime.curve_cache = MEM_callocN(sizeof(CurveCache), "CurveCache for lattice");
1103   }
1104
1105   for (; md; md = md->next) {
1106     const ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1107
1108     if (!(mti->flags & eModifierTypeFlag_AcceptsLattice)) {
1109       continue;
1110     }
1111     if (!(md->mode & eModifierMode_Realtime)) {
1112       continue;
1113     }
1114     if (editmode && !(md->mode & eModifierMode_Editmode)) {
1115       continue;
1116     }
1117     if (mti->isDisabled && mti->isDisabled(scene, md, 0)) {
1118       continue;
1119     }
1120     if (mti->type != eModifierTypeType_OnlyDeform) {
1121       continue;
1122     }
1123
1124     if (!vertexCos) {
1125       vertexCos = BKE_lattice_vertexcos_get(ob_orig->data, &numVerts);
1126     }
1127     mti->deformVerts(md, &mectx, NULL, vertexCos, numVerts);
1128   }
1129
1130   if (ob->id.tag & LIB_TAG_COPIED_ON_WRITE) {
1131     if (vertexCos) {
1132       BKE_lattice_vertexcos_apply(ob->data, vertexCos);
1133       MEM_freeN(vertexCos);
1134     }
1135   }
1136   else {
1137     /* Displist won't do anything; this is just for posterity's sake until we remove it. */
1138     if (!vertexCos) {
1139       vertexCos = BKE_lattice_vertexcos_get(ob_orig->data, &numVerts);
1140     }
1141
1142     DispList *dl = MEM_callocN(sizeof(*dl), "lt_dl");
1143     dl->type = DL_VERTS;
1144     dl->parts = 1;
1145     dl->nr = numVerts;
1146     dl->verts = (float *)vertexCos;
1147
1148     BLI_addtail(&ob->runtime.curve_cache->disp, dl);
1149   }
1150 }
1151
1152 struct MDeformVert *BKE_lattice_deform_verts_get(struct Object *oblatt)
1153 {
1154   Lattice *lt = (Lattice *)oblatt->data;
1155   BLI_assert(oblatt->type == OB_LATTICE);
1156   if (lt->editlatt) {
1157     lt = lt->editlatt->latt;
1158   }
1159   return lt->dvert;
1160 }
1161
1162 struct BPoint *BKE_lattice_active_point_get(Lattice *lt)
1163 {
1164   BLI_assert(GS(lt->id.name) == ID_LT);
1165
1166   if (lt->editlatt) {
1167     lt = lt->editlatt->latt;
1168   }
1169
1170   BLI_assert(lt->actbp < lt->pntsu * lt->pntsv * lt->pntsw);
1171
1172   if ((lt->actbp != LT_ACTBP_NONE) && (lt->actbp < lt->pntsu * lt->pntsv * lt->pntsw)) {
1173     return &lt->def[lt->actbp];
1174   }
1175   else {
1176     return NULL;
1177   }
1178 }
1179
1180 void BKE_lattice_center_median(Lattice *lt, float cent[3])
1181 {
1182   int i, numVerts;
1183
1184   if (lt->editlatt) {
1185     lt = lt->editlatt->latt;
1186   }
1187   numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1188
1189   zero_v3(cent);
1190
1191   for (i = 0; i < numVerts; i++) {
1192     add_v3_v3(cent, lt->def[i].vec);
1193   }
1194
1195   mul_v3_fl(cent, 1.0f / (float)numVerts);
1196 }
1197
1198 static void boundbox_lattice(Object *ob)
1199 {
1200   BoundBox *bb;
1201   Lattice *lt;
1202   float min[3], max[3];
1203
1204   if (ob->runtime.bb == NULL) {
1205     ob->runtime.bb = MEM_callocN(sizeof(BoundBox), "Lattice boundbox");
1206   }
1207
1208   bb = ob->runtime.bb;
1209   lt = ob->data;
1210
1211   INIT_MINMAX(min, max);
1212   BKE_lattice_minmax_dl(ob, lt, min, max);
1213   BKE_boundbox_init_from_minmax(bb, min, max);
1214
1215   bb->flag &= ~BOUNDBOX_DIRTY;
1216 }
1217
1218 BoundBox *BKE_lattice_boundbox_get(Object *ob)
1219 {
1220   boundbox_lattice(ob);
1221
1222   return ob->runtime.bb;
1223 }
1224
1225 void BKE_lattice_minmax_dl(Object *ob, Lattice *lt, float min[3], float max[3])
1226 {
1227   DispList *dl = ob->runtime.curve_cache ?
1228                      BKE_displist_find(&ob->runtime.curve_cache->disp, DL_VERTS) :
1229                      NULL;
1230
1231   if (!dl) {
1232     BKE_lattice_minmax(lt, min, max);
1233   }
1234   else {
1235     int i, numVerts;
1236
1237     if (lt->editlatt) {
1238       lt = lt->editlatt->latt;
1239     }
1240     numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1241
1242     for (i = 0; i < numVerts; i++) {
1243       minmax_v3v3_v3(min, max, &dl->verts[i * 3]);
1244     }
1245   }
1246 }
1247
1248 void BKE_lattice_minmax(Lattice *lt, float min[3], float max[3])
1249 {
1250   int i, numVerts;
1251
1252   if (lt->editlatt) {
1253     lt = lt->editlatt->latt;
1254   }
1255   numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1256
1257   for (i = 0; i < numVerts; i++) {
1258     minmax_v3v3_v3(min, max, lt->def[i].vec);
1259   }
1260 }
1261
1262 void BKE_lattice_center_bounds(Lattice *lt, float cent[3])
1263 {
1264   float min[3], max[3];
1265
1266   INIT_MINMAX(min, max);
1267
1268   BKE_lattice_minmax(lt, min, max);
1269   mid_v3_v3v3(cent, min, max);
1270 }
1271
1272 void BKE_lattice_transform(Lattice *lt, float mat[4][4], bool do_keys)
1273 {
1274   BPoint *bp = lt->def;
1275   int i = lt->pntsu * lt->pntsv * lt->pntsw;
1276
1277   while (i--) {
1278     mul_m4_v3(mat, bp->vec);
1279     bp++;
1280   }
1281
1282   if (do_keys && lt->key) {
1283     KeyBlock *kb;
1284
1285     for (kb = lt->key->block.first; kb; kb = kb->next) {
1286       float *fp = kb->data;
1287       for (i = kb->totelem; i--; fp += 3) {
1288         mul_m4_v3(mat, fp);
1289       }
1290     }
1291   }
1292 }
1293
1294 void BKE_lattice_translate(Lattice *lt, float offset[3], bool do_keys)
1295 {
1296   int i, numVerts;
1297
1298   numVerts = lt->pntsu * lt->pntsv * lt->pntsw;
1299
1300   if (lt->def) {
1301     for (i = 0; i < numVerts; i++) {
1302       add_v3_v3(lt->def[i].vec, offset);
1303     }
1304   }
1305
1306   if (lt->editlatt) {
1307     for (i = 0; i < numVerts; i++) {
1308       add_v3_v3(lt->editlatt->latt->def[i].vec, offset);
1309     }
1310   }
1311
1312   if (do_keys && lt->key) {
1313     KeyBlock *kb;
1314
1315     for (kb = lt->key->block.first; kb; kb = kb->next) {
1316       float *fp = kb->data;
1317       for (i = kb->totelem; i--; fp += 3) {
1318         add_v3_v3(fp, offset);
1319       }
1320     }
1321   }
1322 }
1323
1324 bool BKE_lattice_is_any_selected(const Lattice *lt)
1325 {
1326   /* Intentionally don't handle 'lt->editlatt' (caller must do this). */
1327   const BPoint *bp = lt->def;
1328   int a = lt->pntsu * lt->pntsv * lt->pntsw;
1329   while (a--) {
1330     if (bp->hide == 0) {
1331       if (bp->f1 & SELECT) {
1332         return true;
1333       }
1334     }
1335     bp++;
1336   }
1337   return false;
1338 }
1339
1340 /* **** Depsgraph evaluation **** */
1341
1342 void BKE_lattice_eval_geometry(struct Depsgraph *UNUSED(depsgraph), Lattice *UNUSED(latt))
1343 {
1344 }
1345
1346 /* Draw Engine */
1347 void (*BKE_lattice_batch_cache_dirty_tag_cb)(Lattice *lt, int mode) = NULL;
1348 void (*BKE_lattice_batch_cache_free_cb)(Lattice *lt) = NULL;
1349
1350 void BKE_lattice_batch_cache_dirty_tag(Lattice *lt, int mode)
1351 {
1352   if (lt->batch_cache) {
1353     BKE_lattice_batch_cache_dirty_tag_cb(lt, mode);
1354   }
1355 }
1356 void BKE_lattice_batch_cache_free(Lattice *lt)
1357 {
1358   if (lt->batch_cache) {
1359     BKE_lattice_batch_cache_free_cb(lt);
1360   }
1361 }