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