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