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