Merging r45936 through r46042 from trunk into soc-2011-tomato
[blender.git] / source / blender / editors / mesh / meshtools.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) 2004 by Blender Foundation
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/editors/mesh/meshtools.c
29  *  \ingroup edmesh
30  */
31
32
33 /*
34  * meshtools.c: no editmode (violated already :), tools operating on meshes
35  */
36
37 #include <stddef.h>
38 #include <stdlib.h>
39 #include <math.h>
40 #include <float.h>
41
42 #include "MEM_guardedalloc.h"
43
44 #include "DNA_mesh_types.h"
45 #include "DNA_key_types.h"
46 #include "DNA_material_types.h"
47 #include "DNA_meshdata_types.h"
48 #include "DNA_object_types.h"
49 #include "DNA_scene_types.h"
50
51 #include "BLI_math.h"
52 #include "BLI_blenlib.h"
53 #include "BLI_utildefines.h"
54 #include "BLI_ghash.h"
55 #include "BLI_rand.h" /* for randome face sorting */
56 #include "BLI_threads.h"
57
58
59 #include "BKE_context.h"
60 #include "BKE_depsgraph.h"
61 #include "BKE_deform.h"
62 #include "BKE_DerivedMesh.h"
63 #include "BKE_key.h"
64 #include "BKE_library.h"
65 #include "BKE_main.h"
66 #include "BKE_mesh.h"
67 #include "BKE_material.h"
68 #include "BKE_report.h"
69 #include "BKE_tessmesh.h"
70 #include "BKE_multires.h"
71
72 #include "BLO_sys_types.h" // for intptr_t support
73
74 #include "ED_mesh.h"
75 #include "ED_object.h"
76 #include "ED_view3d.h"
77
78 #include "WM_api.h"
79 #include "WM_types.h"
80
81 /* own include */
82 #include "mesh_intern.h"
83 #include "uvedit_intern.h"
84
85 /* * ********************** no editmode!!! *********** */
86
87 /*********************** JOIN ***************************/
88
89 /* join selected meshes into the active mesh, context sensitive
90  * return 0 if no join is made (error) and 1 if the join is done */
91
92 int join_mesh_exec(bContext *C, wmOperator *op)
93 {
94         Main *bmain = CTX_data_main(C);
95         Scene *scene = CTX_data_scene(C);
96         Object *ob = CTX_data_active_object(C);
97         Material **matar, *ma;
98         Mesh *me;
99         MVert *mvert, *mv;
100         MEdge *medge = NULL;
101         MPoly *mpoly = NULL;
102         MLoop *mloop = NULL;
103         Key *key, *nkey = NULL;
104         KeyBlock *kb, *okb, *kbn;
105         float imat[4][4], cmat[4][4], *fp1, *fp2, curpos;
106         int a, b, totcol, totmat = 0, totedge = 0, totvert = 0, ok = 0;
107         int totloop = 0, totpoly = 0, vertofs, *matmap = NULL;
108         int i, j, index, haskey = 0, edgeofs, loopofs, polyofs;
109         bDeformGroup *dg, *odg;
110         MDeformVert *dvert;
111         CustomData vdata, edata, fdata, ldata, pdata;
112
113         if (scene->obedit) {
114                 BKE_report(op->reports, RPT_WARNING, "Cant join while in editmode");
115                 return OPERATOR_CANCELLED;
116         }
117         
118         /* ob is the object we are adding geometry to */
119         if (!ob || ob->type != OB_MESH) {
120                 BKE_report(op->reports, RPT_WARNING, "Active object is not a mesh");
121                 return OPERATOR_CANCELLED;
122         }
123         
124         /* count & check */
125         CTX_DATA_BEGIN (C, Base *, base, selected_editable_bases) {
126                 if (base->object->type == OB_MESH) {
127                         me = base->object->data;
128
129                         totvert += me->totvert;
130                         totedge += me->totedge;
131                         totloop += me->totloop;
132                         totpoly += me->totpoly;
133                         totmat += base->object->totcol;
134                         
135                         if (base->object == ob)
136                                 ok = 1;
137                         
138                         /* check for shapekeys */
139                         if (me->key)
140                                 haskey++;
141                 }
142         }
143         CTX_DATA_END;
144         
145         /* that way the active object is always selected */ 
146         if (ok == 0) {
147                 BKE_report(op->reports, RPT_WARNING, "Active object is not a selected mesh");
148                 return OPERATOR_CANCELLED;
149         }
150         
151         /* only join meshes if there are verts to join, there aren't too many, and we only had one mesh selected */
152         me = (Mesh *)ob->data;
153         key = me->key;
154
155         if (totvert == 0 || totvert == me->totvert) {
156                 BKE_report(op->reports, RPT_WARNING, "No mesh data to join");
157                 return OPERATOR_CANCELLED;
158         }
159         
160         if (totvert > MESH_MAX_VERTS) {
161                 BKE_reportf(op->reports, RPT_WARNING, "Joining results in %d vertices, limit is " STRINGIFY(MESH_MAX_VERTS), totvert);
162                 return OPERATOR_CANCELLED;              
163         }
164
165         /* new material indices and material array */
166         matar = MEM_callocN(sizeof(void *) * totmat, "join_mesh matar");
167         if (totmat) matmap = MEM_callocN(sizeof(int) * totmat, "join_mesh matmap");
168         totcol = ob->totcol;
169         
170         /* obact materials in new main array, is nicer start! */
171         for (a = 0; a < ob->totcol; a++) {
172                 matar[a] = give_current_material(ob, a + 1);
173                 id_us_plus((ID *)matar[a]);
174                 /* increase id->us : will be lowered later */
175         }
176         
177         /* - if destination mesh had shapekeys, move them somewhere safe, and set up placeholders
178          *  with arrays that are large enough to hold shapekey data for all meshes
179          * -    if destination mesh didn't have shapekeys, but we encountered some in the meshes we're 
180          *      joining, set up a new keyblock and assign to the mesh
181          */
182         if (key) {
183                 /* make a duplicate copy that will only be used here... (must remember to free it!) */
184                 nkey = copy_key(key);
185                 
186                 /* for all keys in old block, clear data-arrays */
187                 for (kb = key->block.first; kb; kb = kb->next) {
188                         if (kb->data) MEM_freeN(kb->data);
189                         kb->data = MEM_callocN(sizeof(float) * 3 * totvert, "join_shapekey");
190                         kb->totelem = totvert;
191                         kb->weights = NULL;
192                 }
193         }
194         else if (haskey) {
195                 /* add a new key-block and add to the mesh */
196                 key = me->key = add_key((ID *)me);
197                 key->type = KEY_RELATIVE;
198         }
199         
200         /* first pass over objects - copying materials and vertexgroups across */
201         CTX_DATA_BEGIN (C, Base *, base, selected_editable_bases) {
202                 /* only act if a mesh, and not the one we're joining to */
203                 if ((ob != base->object) && (base->object->type == OB_MESH)) {
204                         me = base->object->data;
205                         
206                         /* Join this object's vertex groups to the base one's */
207                         for (dg = base->object->defbase.first; dg; dg = dg->next) {
208                                 /* See if this group exists in the object (if it doesn't, add it to the end) */
209                                 if (!defgroup_find_name(ob, dg->name)) {
210                                         odg = MEM_callocN(sizeof(bDeformGroup), "join deformGroup");
211                                         memcpy(odg, dg, sizeof(bDeformGroup));
212                                         BLI_addtail(&ob->defbase, odg);
213                                 }
214                         }
215                         if (ob->defbase.first && ob->actdef == 0)
216                                 ob->actdef = 1;
217                         
218                         
219                         if (me->totvert) {
220                                 /* Add this object's materials to the base one's if they don't exist already (but only if limits not exceeded yet) */
221                                 if (totcol < MAXMAT) {
222                                         for (a = 1; a <= base->object->totcol; a++) {
223                                                 ma = give_current_material(base->object, a);
224
225                                                 for (b = 0; b < totcol; b++) {
226                                                         if (ma == matar[b]) break;
227                                                 }
228                                                 if (b == totcol) {
229                                                         matar[b] = ma;
230                                                         if (ma) {
231                                                                 id_us_plus(&ma->id);
232                                                         }
233                                                         totcol++;
234                                                 }
235                                                 if (totcol >= MAXMAT)
236                                                         break;
237                                         }
238                                 }
239                                 
240                                 /* if this mesh has shapekeys, check if destination mesh already has matching entries too */
241                                 if (me->key && key) {
242                                         for (kb = me->key->block.first; kb; kb = kb->next) {
243                                                 /* if key doesn't exist in destination mesh, add it */
244                                                 if (key_get_named_keyblock(key, kb->name) == NULL) {
245                                                         /* copy this existing one over to the new shapekey block */
246                                                         kbn = MEM_dupallocN(kb);
247                                                         kbn->prev = kbn->next = NULL;
248                                                         
249                                                         /* adjust settings to fit (allocate a new data-array) */
250                                                         kbn->data = MEM_callocN(sizeof(float) * 3 * totvert, "joined_shapekey");
251                                                         kbn->totelem = totvert;
252                                                         kbn->weights = NULL;
253                                                         
254                                                         okb = key->block.last;
255                                                         curpos = (okb) ? okb->pos : -0.1f;
256                                                         if (key->type == KEY_RELATIVE)
257                                                                 kbn->pos = curpos + 0.1f;
258                                                         else
259                                                                 kbn->pos = curpos;
260                                                         
261                                                         BLI_addtail(&key->block, kbn);
262                                                         key->totkey++;
263                                                         if (key->totkey == 1) key->refkey = kbn;
264                                                         
265                                                         // XXX 2.5 Animato
266 #if 0
267                                                         /* also, copy corresponding ipo-curve to ipo-block if applicable */
268                                                         if (me->key->ipo && key->ipo) {
269                                                                 // FIXME... this is a luxury item!
270                                                                 puts("FIXME: ignoring IPO's when joining shapekeys on Meshes for now...");
271                                                         }
272 #endif
273                                                 }
274                                         }
275                                 }
276                         }
277                 }
278         }
279         CTX_DATA_END;
280         
281         /* setup new data for destination mesh */
282         memset(&vdata, 0, sizeof(vdata));
283         memset(&edata, 0, sizeof(edata));
284         memset(&fdata, 0, sizeof(fdata));
285         memset(&ldata, 0, sizeof(ldata));
286         memset(&pdata, 0, sizeof(pdata));
287         
288         mvert = CustomData_add_layer(&vdata, CD_MVERT, CD_CALLOC, NULL, totvert);
289         medge = CustomData_add_layer(&edata, CD_MEDGE, CD_CALLOC, NULL, totedge);
290         mloop = CustomData_add_layer(&ldata, CD_MLOOP, CD_CALLOC, NULL, totloop);
291         mpoly = CustomData_add_layer(&pdata, CD_MPOLY, CD_CALLOC, NULL, totpoly);
292
293         vertofs = 0;
294         edgeofs = 0;
295         loopofs = 0;
296         polyofs = 0;
297         
298         /* inverse transform for all selected meshes in this object */
299         invert_m4_m4(imat, ob->obmat);
300         
301         CTX_DATA_BEGIN (C, Base *, base, selected_editable_bases) {
302                 /* only join if this is a mesh */
303                 if (base->object->type == OB_MESH) {
304                         me = base->object->data;
305                         
306                         if (me->totvert) {
307                                 /* standard data */
308                                 CustomData_merge(&me->vdata, &vdata, CD_MASK_MESH, CD_DEFAULT, totvert);
309                                 CustomData_copy_data(&me->vdata, &vdata, 0, vertofs, me->totvert);
310                                 
311                                 /* vertex groups */
312                                 dvert = CustomData_get(&vdata, vertofs, CD_MDEFORMVERT);
313                                 
314                                 /* NB: vertex groups here are new version */
315                                 if (dvert) {
316                                         for (i = 0; i < me->totvert; i++) {
317                                                 for (j = 0; j < dvert[i].totweight; j++) {
318                                                         /*      Find the old vertex group */
319                                                         odg = BLI_findlink(&base->object->defbase, dvert[i].dw[j].def_nr);
320                                                         if (odg) {
321                                                                 /*      Search for a match in the new object, and set new index */
322                                                                 for (dg = ob->defbase.first, index = 0; dg; dg = dg->next, index++) {
323                                                                         if (!strcmp(dg->name, odg->name)) {
324                                                                                 dvert[i].dw[j].def_nr = index;
325                                                                                 break;
326                                                                         }
327                                                                 }
328                                                         }
329                                                 }
330                                         }
331                                 }
332                                 
333                                 /* if this is the object we're merging into, no need to do anything */
334                                 if (base->object != ob) {
335                                         /* watch this: switch matmul order really goes wrong */
336                                         mult_m4_m4m4(cmat, imat, base->object->obmat);
337                                         
338                                         /* transform vertex coordinates into new space */
339                                         for (a = 0, mv = mvert; a < me->totvert; a++, mv++) {
340                                                 mul_m4_v3(cmat, mv->co);
341                                         }
342                                         
343                                         /* for each shapekey in destination mesh:
344                                          *      - if there's a matching one, copy it across (will need to transform vertices into new space...)
345                                          *      - otherwise, just copy own coordinates of mesh (no need to transform vertex coordinates into new space)
346                                          */
347                                         if (key) {
348                                                 /* if this mesh has any shapekeys, check first, otherwise just copy coordinates */
349                                                 for (kb = key->block.first; kb; kb = kb->next) {
350                                                         /* get pointer to where to write data for this mesh in shapekey's data array */
351                                                         fp1 = ((float *)kb->data) + (vertofs * 3);
352                                                         
353                                                         /* check if this mesh has such a shapekey */
354                                                         okb = key_get_named_keyblock(me->key, kb->name);
355                                                         if (okb) {
356                                                                 /* copy this mesh's shapekey to the destination shapekey (need to transform first) */
357                                                                 fp2 = ((float *)(okb->data));
358                                                                 for (a = 0; a < me->totvert; a++, fp1 += 3, fp2 += 3) {
359                                                                         copy_v3_v3(fp1, fp2);
360                                                                         mul_m4_v3(cmat, fp1);
361                                                                 }
362                                                         }
363                                                         else {
364                                                                 /* copy this mesh's vertex coordinates to the destination shapekey */
365                                                                 mv = mvert;
366                                                                 for (a = 0; a < me->totvert; a++, fp1 += 3, mv++) {
367                                                                         copy_v3_v3(fp1, mv->co);
368                                                                 }
369                                                         }
370                                                 }
371                                         }
372                                 }
373                                 else {
374                                         /* for each shapekey in destination mesh:
375                                          *      - if it was an 'original', copy the appropriate data from nkey
376                                          *      - otherwise, copy across plain coordinates (no need to transform coordinates)
377                                          */
378                                         if (key) {
379                                                 for (kb = key->block.first; kb; kb = kb->next) {
380                                                         /* get pointer to where to write data for this mesh in shapekey's data array */
381                                                         fp1 = ((float *)kb->data) + (vertofs * 3);
382                                                         
383                                                         /* check if this was one of the original shapekeys */
384                                                         okb = key_get_named_keyblock(nkey, kb->name);
385                                                         if (okb) {
386                                                                 /* copy this mesh's shapekey to the destination shapekey */
387                                                                 fp2 = ((float *)(okb->data));
388                                                                 for (a = 0; a < me->totvert; a++, fp1 += 3, fp2 += 3) {
389                                                                         copy_v3_v3(fp1, fp2);
390                                                                 }
391                                                         }
392                                                         else {
393                                                                 /* copy base-coordinates to the destination shapekey */
394                                                                 mv = mvert;
395                                                                 for (a = 0; a < me->totvert; a++, fp1 += 3, mv++) {
396                                                                         copy_v3_v3(fp1, mv->co);
397                                                                 }
398                                                         }
399                                                 }
400                                         }
401                                 }
402                                 
403                                 /* advance mvert pointer to end of base mesh's data */
404                                 mvert += me->totvert;
405                         }
406                         
407                         if (me->totedge) {
408                                 CustomData_merge(&me->edata, &edata, CD_MASK_MESH, CD_DEFAULT, totedge);
409                                 CustomData_copy_data(&me->edata, &edata, 0, edgeofs, me->totedge);
410                                 
411                                 for (a = 0; a < me->totedge; a++, medge++) {
412                                         medge->v1 += vertofs;
413                                         medge->v2 += vertofs;
414                                 }
415                         }
416
417                         if (me->totloop) {
418                                 if (base->object != ob)
419                                         multiresModifier_prepare_join(scene, base->object, ob);
420                                 
421                                 CustomData_merge(&me->ldata, &ldata, CD_MASK_MESH, CD_DEFAULT, totloop);
422                                 CustomData_copy_data(&me->ldata, &ldata, 0, loopofs, me->totloop);
423                                 
424                                 for (a = 0; a < me->totloop; a++, mloop++) {
425                                         mloop->v += vertofs;
426                                         mloop->e += edgeofs;
427                                 }
428                         }
429                         
430                         if (me->totpoly) {
431                                 /* make mapping for materials */
432                                 for (a = 1; a <= base->object->totcol; a++) {
433                                         ma = give_current_material(base->object, a);
434
435                                         for (b = 0; b < totcol; b++) {
436                                                 if (ma == matar[b]) {
437                                                         matmap[a - 1] = b;
438                                                         break;
439                                                 }
440                                         }
441                                 }
442                                 
443                                 CustomData_merge(&me->pdata, &pdata, CD_MASK_MESH, CD_DEFAULT, totpoly);
444                                 CustomData_copy_data(&me->pdata, &pdata, 0, polyofs, me->totpoly);
445                                 
446                                 for (a = 0; a < me->totpoly; a++, mpoly++) {
447                                         mpoly->loopstart += loopofs;
448                                         mpoly->mat_nr = matmap ? matmap[(int)mpoly->mat_nr] : 0;
449                                 }
450                                 
451                                 polyofs += me->totpoly;
452                         }
453
454                         /* these are used for relinking (cannot be set earlier, 
455                          * or else reattaching goes wrong)
456                          */
457                         vertofs += me->totvert;
458                         edgeofs += me->totedge;
459                         loopofs += me->totloop;
460                         
461                         /* free base, now that data is merged */
462                         if (base->object != ob)
463                                 ED_base_object_free_and_unlink(bmain, scene, base);
464                 }
465         }
466         CTX_DATA_END;
467         
468         /* return to mesh we're merging to */
469         me = ob->data;
470         
471         CustomData_free(&me->vdata, me->totvert);
472         CustomData_free(&me->edata, me->totedge);
473         CustomData_free(&me->ldata, me->totloop);
474         CustomData_free(&me->pdata, me->totpoly);
475
476         me->totvert = totvert;
477         me->totedge = totedge;
478         me->totloop = totloop;
479         me->totpoly = totpoly;
480
481         me->vdata = vdata;
482         me->edata = edata;
483         me->ldata = ldata;
484         me->pdata = pdata;
485
486         mesh_update_customdata_pointers(me, TRUE); /* BMESH_TODO, check if this arg can be failse, non urgent - campbell */
487         
488         /* old material array */
489         for (a = 1; a <= ob->totcol; a++) {
490                 ma = ob->mat[a - 1];
491                 if (ma) ma->id.us--;
492         }
493         for (a = 1; a <= me->totcol; a++) {
494                 ma = me->mat[a - 1];
495                 if (ma) ma->id.us--;
496         }
497         if (ob->mat) MEM_freeN(ob->mat);
498         if (ob->matbits) MEM_freeN(ob->matbits);
499         if (me->mat) MEM_freeN(me->mat);
500         ob->mat = me->mat = NULL;
501         ob->matbits = NULL;
502         
503         if (totcol) {
504                 me->mat = matar;
505                 ob->mat = MEM_callocN(sizeof(void *) * totcol, "join obmatar");
506                 ob->matbits = MEM_callocN(sizeof(char) * totcol, "join obmatbits");
507         }
508         else
509                 MEM_freeN(matar);
510         
511         ob->totcol = me->totcol = totcol;
512
513         if (matmap) MEM_freeN(matmap);
514         
515         /* other mesh users */
516         test_object_materials((ID *)me);
517         
518         /* free temp copy of destination shapekeys (if applicable) */
519         if (nkey) {
520                 // XXX 2.5 Animato
521 #if 0
522                 /* free it's ipo too - both are not actually freed from memory yet as ID-blocks */
523                 if (nkey->ipo) {
524                         free_ipo(nkey->ipo);
525                         BLI_remlink(&bmain->ipo, nkey->ipo);
526                         MEM_freeN(nkey->ipo);
527                 }
528 #endif
529                 
530                 free_key(nkey);
531                 BLI_remlink(&bmain->key, nkey);
532                 MEM_freeN(nkey);
533         }
534         
535         DAG_scene_sort(bmain, scene);   // removed objects, need to rebuild dag before editmode call
536
537 #if 0
538         ED_object_enter_editmode(C, EM_WAITCURSOR);
539         ED_object_exit_editmode(C, EM_FREEDATA | EM_WAITCURSOR | EM_DO_UNDO);
540 #else
541         /* toggle editmode using lower level functions so this can be called from python */
542         EDBM_mesh_make(scene->toolsettings, scene, ob);
543         EDBM_mesh_load(ob);
544         EDBM_mesh_free(me->edit_btmesh);
545         MEM_freeN(me->edit_btmesh);
546         me->edit_btmesh = NULL;
547         DAG_id_tag_update(&ob->id, OB_RECALC_OB | OB_RECALC_DATA);
548 #endif
549         WM_event_add_notifier(C, NC_SCENE | ND_OB_ACTIVE, scene);
550
551         return OPERATOR_FINISHED;
552 }
553
554 /*********************** JOIN AS SHAPES ***************************/
555
556 /* Append selected meshes vertex locations as shapes of the active mesh, 
557  * return 0 if no join is made (error) and 1 of the join is done */
558
559 int join_mesh_shapes_exec(bContext *C, wmOperator *op)
560 {
561         Scene *scene = CTX_data_scene(C);
562         Object *ob = CTX_data_active_object(C);
563         Mesh *me = (Mesh *)ob->data;
564         Mesh *selme = NULL;
565         DerivedMesh *dm = NULL;
566         Key *key = me->key;
567         KeyBlock *kb;
568         int ok = 0, nonequal_verts = 0;
569         
570         CTX_DATA_BEGIN (C, Base *, base, selected_editable_bases) {
571                 if (base->object == ob) continue;
572                 
573                 if (base->object->type == OB_MESH) {
574                         selme = (Mesh *)base->object->data;
575                         
576                         if (selme->totvert == me->totvert)
577                                 ok++;
578                         else
579                                 nonequal_verts = 1;
580                 }
581         }
582         CTX_DATA_END;
583         
584         if (!ok) {
585                 if (nonequal_verts)
586                         BKE_report(op->reports, RPT_WARNING, "Selected meshes must have equal numbers of vertices");
587                 else
588                         BKE_report(op->reports, RPT_WARNING, "No additional selected meshes with equal vertex count to join");
589                 return OPERATOR_CANCELLED;
590         }
591         
592         if (key == NULL) {
593                 key = me->key = add_key((ID *)me);
594                 key->type = KEY_RELATIVE;
595
596                 /* first key added, so it was the basis. initialize it with the existing mesh */
597                 kb = add_keyblock(key, NULL);
598                 mesh_to_key(me, kb);
599         }
600         
601         /* now ready to add new keys from selected meshes */
602         CTX_DATA_BEGIN (C, Base *, base, selected_editable_bases) {
603                 if (base->object == ob) continue;
604                 
605                 if (base->object->type == OB_MESH) {
606                         selme = (Mesh *)base->object->data;
607                         
608                         if (selme->totvert == me->totvert) {
609                                 dm = mesh_get_derived_deform(scene, base->object, CD_MASK_BAREMESH);
610                                 
611                                 if (!dm) continue;
612                                         
613                                 kb = add_keyblock(key, base->object->id.name + 2);
614                                 
615                                 DM_to_meshkey(dm, me, kb);
616                                 
617                                 dm->release(dm);
618                         }
619                 }
620         }
621         CTX_DATA_END;
622         
623         WM_event_add_notifier(C, NC_SCENE | ND_OB_ACTIVE, scene);
624         
625         return OPERATOR_FINISHED;
626 }
627
628 /* ********************* MESH VERTEX OCTREE LOOKUP ************* */
629
630 /* important note; this is unfinished, needs better API for editmode, and custom threshold */
631
632 #define MOC_RES         8
633 #define MOC_NODE_RES    8
634 #define MOC_THRESH      0.00002f
635
636 typedef struct MocNode {
637         struct MocNode *next;
638         intptr_t index[MOC_NODE_RES];
639 } MocNode;
640
641 static int mesh_octree_get_base_offs(const float co[3], const float offs[3], const float div[3])
642 {
643         int vx, vy, vz;
644         
645         vx = floor( (co[0] - offs[0]) / div[0]);
646         vy = floor( (co[1] - offs[1]) / div[1]);
647         vz = floor( (co[2] - offs[2]) / div[2]);
648
649         CLAMP(vx, 0, MOC_RES - 1);
650         CLAMP(vy, 0, MOC_RES - 1);
651         CLAMP(vz, 0, MOC_RES - 1);
652
653         return (vx * MOC_RES * MOC_RES) + vy * MOC_RES + vz;
654 }
655
656 static void mesh_octree_add_node(MocNode **bt, intptr_t index)
657 {
658         if (*bt == NULL) {
659                 *bt = MEM_callocN(sizeof(MocNode), "MocNode");
660                 (*bt)->index[0] = index;
661         }
662         else {
663                 int a;
664                 for (a = 0; a < MOC_NODE_RES; a++) {
665                         if ((*bt)->index[a] == index)
666                                 return;
667                         else if ((*bt)->index[a] == 0) {
668                                 (*bt)->index[a] = index;
669                                 return;
670                         }
671                 }
672                 mesh_octree_add_node(&(*bt)->next, index);
673         }
674 }
675
676 static void mesh_octree_free_node(MocNode **bt)
677 {
678         if ( (*bt)->next) {
679                 mesh_octree_free_node(&(*bt)->next);
680         }
681         MEM_freeN(*bt);
682 }
683
684
685 /* temporal define, just to make nicer code below */
686 #define MOC_INDEX(vx, vy, vz)  (((vx) * MOC_RES * MOC_RES) + (vy) * MOC_RES + (vz))
687
688 static void mesh_octree_add_nodes(MocNode **basetable, float *co, float *offs, float *div, intptr_t index)
689 {
690         float fx, fy, fz;
691         int vx, vy, vz;
692         
693         if (!finite(co[0]) ||
694             !finite(co[1]) ||
695             !finite(co[2]))
696         {
697                 return;
698         }
699         
700         fx = (co[0] - offs[0]) / div[0];
701         fy = (co[1] - offs[1]) / div[1];
702         fz = (co[2] - offs[2]) / div[2];
703         CLAMP(fx, 0.0f, MOC_RES - MOC_THRESH);
704         CLAMP(fy, 0.0f, MOC_RES - MOC_THRESH);
705         CLAMP(fz, 0.0f, MOC_RES - MOC_THRESH);
706
707         vx = (int)floorf(fx);
708         vy = (int)floorf(fy);
709         vz = (int)floorf(fz);
710
711         mesh_octree_add_node(basetable + MOC_INDEX(vx, vy, vz), index);
712
713         if (vx > 0)
714                 if (fx - ((float)vx) - MOC_THRESH < 0.0f)
715                         mesh_octree_add_node(basetable + MOC_INDEX(vx - 1, vy, vz), index);
716         if (vx < MOC_RES - 2)
717                 if (fx - ((float)vx) + MOC_THRESH > 1.0f)
718                         mesh_octree_add_node(basetable + MOC_INDEX(vx + 1, vy, vz), index);
719
720         if (vy > 0)
721                 if (fy - ((float)vy) - MOC_THRESH < 0.0f)
722                         mesh_octree_add_node(basetable + MOC_INDEX(vx, vy - 1, vz), index);
723         if (vy < MOC_RES - 2)
724                 if (fy - ((float)vy) + MOC_THRESH > 1.0f)
725                         mesh_octree_add_node(basetable + MOC_INDEX(vx, vy + 1, vz), index);
726
727         if (vz > 0)
728                 if (fz - ((float)vz) - MOC_THRESH < 0.0f)
729                         mesh_octree_add_node(basetable + MOC_INDEX(vx, vy, vz - 1), index);
730         if (vz < MOC_RES - 2)
731                 if (fz - ((float)vz) + MOC_THRESH > 1.0f)
732                         mesh_octree_add_node(basetable + MOC_INDEX(vx, vy, vz + 1), index);
733
734 }
735
736 static intptr_t mesh_octree_find_index(MocNode **bt, MVert *mvert, const float co[3])
737 {
738         float *vec;
739         int a;
740         
741         if (*bt == NULL)
742                 return -1;
743         
744         for (a = 0; a < MOC_NODE_RES; a++) {
745                 if ((*bt)->index[a]) {
746                         /* does mesh verts and editmode, code looks potential dangerous, octree should really be filled OK! */
747                         if (mvert) {
748                                 vec = (mvert + (*bt)->index[a] - 1)->co;
749                                 if (compare_v3v3(vec, co, MOC_THRESH))
750                                         return (*bt)->index[a] - 1;
751                         }
752                         else {
753                                 BMVert *eve = (BMVert *)((*bt)->index[a]);
754                                 if (compare_v3v3(eve->co, co, MOC_THRESH))
755                                         return (*bt)->index[a];
756                         }
757                 }
758                 else return -1;
759         }
760         if ( (*bt)->next)
761                 return mesh_octree_find_index(&(*bt)->next, mvert, co);
762         
763         return -1;
764 }
765
766 static struct {
767         MocNode **table;
768         float offs[3], div[3];
769 } MeshOctree = {NULL, {0, 0, 0}, {0, 0, 0}};
770
771 /* mode is 's' start, or 'e' end, or 'u' use */
772 /* if end, ob can be NULL */
773 intptr_t mesh_octree_table(Object *ob, BMEditMesh *em, const float co[3], char mode)
774 {
775         MocNode **bt;
776         
777         if (mode == 'u') {        /* use table */
778                 if (MeshOctree.table == NULL)
779                         mesh_octree_table(ob, em, NULL, 's');
780
781                 if (MeshOctree.table) {
782                         Mesh *me = ob->data;
783                         bt = MeshOctree.table + mesh_octree_get_base_offs(co, MeshOctree.offs, MeshOctree.div);
784                         if (em)
785                                 return mesh_octree_find_index(bt, NULL, co);
786                         else
787                                 return mesh_octree_find_index(bt, me->mvert, co);
788                 }
789                 return -1;
790         }
791         else if (mode == 's') {   /* start table */
792                 Mesh *me = ob->data;
793                 float min[3], max[3];
794
795                 /* we compute own bounding box and don't reuse ob->bb because
796                  * we are using the undeformed coordinates*/
797                 INIT_MINMAX(min, max);
798
799                 if (em && me->edit_btmesh == em) {
800                         BMIter iter;
801                         BMVert *eve;
802                         
803                         BM_ITER_MESH (eve, &iter, em->bm, BM_VERTS_OF_MESH) {
804                                 DO_MINMAX(eve->co, min, max);
805                         }
806                 }
807                 else {          
808                         MVert *mvert;
809                         int a;
810                         
811                         for (a = 0, mvert = me->mvert; a < me->totvert; a++, mvert++)
812                                 DO_MINMAX(mvert->co, min, max);
813                 }
814                 
815                 /* for quick unit coordinate calculus */
816                 copy_v3_v3(MeshOctree.offs, min);
817                 MeshOctree.offs[0] -= MOC_THRESH;        /* we offset it 1 threshold unit extra */
818                 MeshOctree.offs[1] -= MOC_THRESH;
819                 MeshOctree.offs[2] -= MOC_THRESH;
820                 
821                 sub_v3_v3v3(MeshOctree.div, max, min);
822                 MeshOctree.div[0] += 2 * MOC_THRESH;   /* and divide with 2 threshold unit more extra (try 8x8 unit grid on paint) */
823                 MeshOctree.div[1] += 2 * MOC_THRESH;
824                 MeshOctree.div[2] += 2 * MOC_THRESH;
825
826                 mul_v3_fl(MeshOctree.div, 1.0f / MOC_RES);
827                 if (MeshOctree.div[0] == 0.0f) MeshOctree.div[0] = 1.0f;
828                 if (MeshOctree.div[1] == 0.0f) MeshOctree.div[1] = 1.0f;
829                 if (MeshOctree.div[2] == 0.0f) MeshOctree.div[2] = 1.0f;
830                         
831                 if (MeshOctree.table) /* happens when entering this call without ending it */
832                         mesh_octree_table(ob, em, co, 'e');
833                 
834                 MeshOctree.table = MEM_callocN(MOC_RES * MOC_RES * MOC_RES * sizeof(void *), "sym table");
835                 
836                 if (em && me->edit_btmesh == em) {
837                         BMVert *eve;
838                         BMIter iter;
839
840                         BM_ITER_MESH (eve, &iter, em->bm, BM_VERTS_OF_MESH) {
841                                 mesh_octree_add_nodes(MeshOctree.table, eve->co, MeshOctree.offs, MeshOctree.div, (intptr_t)(eve));
842                         }
843                 }
844                 else {          
845                         MVert *mvert;
846                         int a;
847                         
848                         for (a = 0, mvert = me->mvert; a < me->totvert; a++, mvert++)
849                                 mesh_octree_add_nodes(MeshOctree.table, mvert->co, MeshOctree.offs, MeshOctree.div, a + 1);
850                 }
851         }
852         else if (mode == 'e') { /* end table */
853                 if (MeshOctree.table) {
854                         int a;
855                         
856                         for (a = 0, bt = MeshOctree.table; a < MOC_RES * MOC_RES * MOC_RES; a++, bt++) {
857                                 if (*bt) mesh_octree_free_node(bt);
858                         }
859                         MEM_freeN(MeshOctree.table);
860                         MeshOctree.table = NULL;
861                 }
862         }
863         return 0;
864 }
865
866 MirrTopoStore_t mesh_topo_store = {NULL, -1. - 1, -1};
867
868 /* mode is 's' start, or 'e' end, or 'u' use */
869 /* if end, ob can be NULL */
870 /* note, is supposed return -1 on error, which callers are currently checking for, but is not used so far */
871 int mesh_mirrtopo_table(Object *ob, char mode)
872 {
873         if (mode == 'u') {        /* use table */
874                 if (ED_mesh_mirrtopo_recalc_check(ob->data, ob->mode, &mesh_topo_store)) {
875                         mesh_mirrtopo_table(ob, 's');
876                 }
877         }
878         else if (mode == 's') { /* start table */
879                 ED_mesh_mirrtopo_init(ob->data, ob->mode, &mesh_topo_store, FALSE);
880         }
881         else if (mode == 'e') { /* end table */
882                 ED_mesh_mirrtopo_free(&mesh_topo_store);
883         }
884         return 0;
885 }
886
887 static int mesh_get_x_mirror_vert_spacial(Object *ob, int index)
888 {
889         Mesh *me = ob->data;
890         MVert *mvert;
891         float vec[3];
892         
893         mvert = me->mvert + index;
894         vec[0] = -mvert->co[0];
895         vec[1] = mvert->co[1];
896         vec[2] = mvert->co[2];
897         
898         return mesh_octree_table(ob, NULL, vec, 'u');
899 }
900
901 static int mesh_get_x_mirror_vert_topo(Object *ob, int index)
902 {
903         if (mesh_mirrtopo_table(ob, 'u') == -1)
904                 return -1;
905
906         return mesh_topo_store.index_lookup[index];
907 }
908
909 int mesh_get_x_mirror_vert(Object *ob, int index)
910 {
911         if (((Mesh *)ob->data)->editflag & ME_EDIT_MIRROR_TOPO) {
912                 return mesh_get_x_mirror_vert_topo(ob, index);
913         }
914         else {
915                 return mesh_get_x_mirror_vert_spacial(ob, index);
916         }
917         return 0;
918 }
919
920 static BMVert *editbmesh_get_x_mirror_vert_spacial(Object *ob, BMEditMesh *em, const float co[3])
921 {
922         float vec[3];
923         intptr_t poinval;
924         
925         /* ignore nan verts */
926         if (!finite(co[0]) ||
927             !finite(co[1]) ||
928             !finite(co[2]))
929         {
930                 return NULL;
931         }
932         
933         vec[0] = -co[0];
934         vec[1] = co[1];
935         vec[2] = co[2];
936         
937         poinval = mesh_octree_table(ob, em, vec, 'u');
938         if (poinval != -1)
939                 return (BMVert *)(poinval);
940         return NULL;
941 }
942
943 static BMVert *editbmesh_get_x_mirror_vert_topo(Object *ob, struct BMEditMesh *em, BMVert *eve, int index)
944 {
945         intptr_t poinval;
946         if (mesh_mirrtopo_table(ob, 'u') == -1)
947                 return NULL;
948
949         if (index == -1) {
950                 BMIter iter;
951                 BMVert *v;
952                 
953                 index = 0;
954                 BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
955                         if (v == eve)
956                                 break;
957                         index++;
958                 }
959                 
960                 if (index == em->bm->totvert) {
961                         return NULL;
962                 }
963         }
964
965         poinval = mesh_topo_store.index_lookup[index];
966
967         if (poinval != -1)
968                 return (BMVert *)(poinval);
969         return NULL;
970 }       
971
972 BMVert *editbmesh_get_x_mirror_vert(Object *ob, struct BMEditMesh *em, BMVert *eve, const float co[3], int index)
973 {
974         if (((Mesh *)ob->data)->editflag & ME_EDIT_MIRROR_TOPO) {
975                 return editbmesh_get_x_mirror_vert_topo(ob, em, eve, index);
976         }
977         else {
978                 return editbmesh_get_x_mirror_vert_spacial(ob, em, co);
979         }
980 }
981
982 #if 0
983
984 static float *editmesh_get_mirror_uv(BMEditMesh *em, int axis, float *uv, float *mirrCent, float *face_cent)
985 {
986         float vec[2];
987         float cent_vec[2];
988         float cent[2];
989
990         /* ignore nan verts */
991         if (isnan(uv[0]) || !finite(uv[0]) ||
992             isnan(uv[1]) || !finite(uv[1])
993             )
994                 return NULL;
995
996         if (axis) {
997                 vec[0] = uv[0];
998                 vec[1] = -((uv[1]) - mirrCent[1]) + mirrCent[1];
999
1000                 cent_vec[0] = face_cent[0];
1001                 cent_vec[1] = -((face_cent[1]) - mirrCent[1]) + mirrCent[1];
1002         }
1003         else {
1004                 vec[0] = -((uv[0]) - mirrCent[0]) + mirrCent[0];
1005                 vec[1] = uv[1];
1006
1007                 cent_vec[0] = -((face_cent[0]) - mirrCent[0]) + mirrCent[0];
1008                 cent_vec[1] = face_cent[1];
1009         }
1010
1011         /* TODO - Optimize */
1012         {
1013                 BMIter iter;
1014                 BMFace *efa;
1015                 
1016                 BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1017                         uv_poly_center(em, efa, cent);
1018                         
1019                         if ( (fabs(cent[0] - cent_vec[0]) < 0.001) && (fabs(cent[1] - cent_vec[1]) < 0.001) ) {
1020                                 BMIter liter;
1021                                 BMLoop *l;
1022                                 
1023                                 BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
1024                                         MLoopUV *luv = CustomData_bmesh_get(&em->bm->ldata, l->head.data, CD_MLOOPUV);
1025                                         if ( (fabs(luv->uv[0] - vec[0]) < 0.001) && (fabs(luv->uv[1] - vec[1]) < 0.001) ) {
1026                                                 return luv->uv;
1027                                                                 
1028                                         }
1029                                 }
1030                         }
1031                 }
1032         }
1033
1034         return NULL;
1035 }
1036
1037 #endif
1038
1039 static unsigned int mirror_facehash(const void *ptr)
1040 {
1041         const MFace *mf = ptr;
1042         int v0, v1;
1043
1044         if (mf->v4) {
1045                 v0 = MIN4(mf->v1, mf->v2, mf->v3, mf->v4);
1046                 v1 = MAX4(mf->v1, mf->v2, mf->v3, mf->v4);
1047         }
1048         else {
1049                 v0 = MIN3(mf->v1, mf->v2, mf->v3);
1050                 v1 = MAX3(mf->v1, mf->v2, mf->v3);
1051         }
1052
1053         return ((v0 * 39) ^ (v1 * 31));
1054 }
1055
1056 static int mirror_facerotation(MFace *a, MFace *b)
1057 {
1058         if (b->v4) {
1059                 if (a->v1 == b->v1 && a->v2 == b->v2 && a->v3 == b->v3 && a->v4 == b->v4)
1060                         return 0;
1061                 else if (a->v4 == b->v1 && a->v1 == b->v2 && a->v2 == b->v3 && a->v3 == b->v4)
1062                         return 1;
1063                 else if (a->v3 == b->v1 && a->v4 == b->v2 && a->v1 == b->v3 && a->v2 == b->v4)
1064                         return 2;
1065                 else if (a->v2 == b->v1 && a->v3 == b->v2 && a->v4 == b->v3 && a->v1 == b->v4)
1066                         return 3;
1067         }
1068         else {
1069                 if (a->v1 == b->v1 && a->v2 == b->v2 && a->v3 == b->v3)
1070                         return 0;
1071                 else if (a->v3 == b->v1 && a->v1 == b->v2 && a->v2 == b->v3)
1072                         return 1;
1073                 else if (a->v2 == b->v1 && a->v3 == b->v2 && a->v1 == b->v3)
1074                         return 2;
1075         }
1076         
1077         return -1;
1078 }
1079
1080 static int mirror_facecmp(const void *a, const void *b)
1081 {
1082         return (mirror_facerotation((MFace *)a, (MFace *)b) == -1);
1083 }
1084
1085 /* BMESH_TODO, convert to MPoly (functions above also) */
1086 int *mesh_get_x_mirror_faces(Object *ob, BMEditMesh *em)
1087 {
1088         Mesh *me = ob->data;
1089         MVert *mv, *mvert = me->mvert;
1090         MFace mirrormf, *mf, *hashmf, *mface = me->mface;
1091         GHash *fhash;
1092         int *mirrorverts, *mirrorfaces;
1093         int a;
1094
1095         mirrorverts = MEM_callocN(sizeof(int) * me->totvert, "MirrorVerts");
1096         mirrorfaces = MEM_callocN(sizeof(int) * 2 * me->totface, "MirrorFaces");
1097
1098         mesh_octree_table(ob, em, NULL, 's');
1099
1100         for (a = 0, mv = mvert; a < me->totvert; a++, mv++)
1101                 mirrorverts[a] = mesh_get_x_mirror_vert(ob, a);
1102
1103         mesh_octree_table(ob, em, NULL, 'e');
1104
1105         fhash = BLI_ghash_new(mirror_facehash, mirror_facecmp, "mirror_facehash gh");
1106         for (a = 0, mf = mface; a < me->totface; a++, mf++)
1107                 BLI_ghash_insert(fhash, mf, mf);
1108
1109         for (a = 0, mf = mface; a < me->totface; a++, mf++) {
1110                 mirrormf.v1 = mirrorverts[mf->v3];
1111                 mirrormf.v2 = mirrorverts[mf->v2];
1112                 mirrormf.v3 = mirrorverts[mf->v1];
1113                 mirrormf.v4 = (mf->v4) ? mirrorverts[mf->v4] : 0;
1114
1115                 /* make sure v4 is not 0 if a quad */
1116                 if (mf->v4 && mirrormf.v4 == 0) {
1117                         SWAP(unsigned int, mirrormf.v1, mirrormf.v3);
1118                         SWAP(unsigned int, mirrormf.v2, mirrormf.v4);
1119                 }
1120
1121                 hashmf = BLI_ghash_lookup(fhash, &mirrormf);
1122                 if (hashmf) {
1123                         mirrorfaces[a * 2] = hashmf - mface;
1124                         mirrorfaces[a * 2 + 1] = mirror_facerotation(&mirrormf, hashmf);
1125                 }
1126                 else
1127                         mirrorfaces[a * 2] = -1;
1128         }
1129
1130         BLI_ghash_free(fhash, NULL, NULL);
1131         MEM_freeN(mirrorverts);
1132         
1133         return mirrorfaces;
1134 }