677ae69d4adb801abefd45e9dfb50b2f7b1bb5c7
[blender.git] / source / blender / src / meshtools.c
1 /**
2  * $Id: 
3  *
4  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2004 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  */
32
33 /*
34
35 meshtools.c: no editmode, tools operating on meshes
36
37 int join_mesh(void);
38
39 void fasterdraw(void);
40 void slowerdraw(void);
41
42 void sort_faces(void);
43
44 */
45
46 #include <stdlib.h>
47 #include <string.h>
48 #include <math.h>
49
50 #ifdef HAVE_CONFIG_H
51 #include <config.h>
52 #endif
53
54 #include "MEM_guardedalloc.h"
55
56 #include "DNA_mesh_types.h"
57 #include "DNA_meshdata_types.h"
58 #include "DNA_object_types.h"
59 #include "DNA_material_types.h"
60 #include "DNA_scene_types.h"
61 #include "DNA_screen_types.h"
62 #include "DNA_view3d_types.h"
63
64 #include "BLI_blenlib.h"
65 #include "BLI_arithb.h"
66
67 #include "BKE_depsgraph.h"
68 #include "BKE_global.h"
69 #include "BKE_library.h"
70 #include "BKE_main.h"
71 #include "BKE_mesh.h"
72 #include "BKE_material.h"
73 #include "BKE_object.h"
74 #include "BKE_utildefines.h"
75
76 #include "BIF_editmesh.h"
77 #include "BIF_graphics.h"
78 #include "BIF_mywindow.h"
79 #include "BIF_screen.h"
80 #include "BIF_space.h"
81 #include "BIF_toolbox.h"
82 #include "BIF_editconstraint.h"
83
84 #include "BDR_editobject.h" 
85 #include "BDR_editface.h" 
86
87 #include "BLI_editVert.h"
88
89 #include "mydevice.h"
90 #include "blendef.h"
91
92 #include "BIF_meshtools.h" /* include ourself for prototypes */
93
94
95 /* * ********************** no editmode!!! *********** */
96
97
98 /** tests whether selected mesh objects have tfaces */
99 static int testSelected_TfaceMesh(void)
100 {
101         Base *base;
102         Mesh *me;
103
104         base = FIRSTBASE;
105         while (base) {
106                 if TESTBASE(base) {
107                         if(base->object->type==OB_MESH) {
108                                 me= base->object->data;
109                                 if (me->tface) 
110                                         return 1;
111                         }               
112                 }                       
113                 base= base->next;
114         }       
115         return 0;
116 }       
117
118 /* join selected meshes into the active mesh, context sensitive
119 return 0 if no join is made (error) and 1 of the join is done */
120 int join_mesh(void)
121 {
122         Base *base, *nextb;
123         Object *ob;
124         Material **matar, *ma;
125         Mesh *me;
126         MVert *mvert, *mvertmain;
127         MEdge *medge = NULL, *medgemain;
128         MFace *mface = NULL, *mfacemain;
129         TFace *tface = NULL, *tfacemain;
130         unsigned int *mcol=NULL, *mcolmain;
131         float imat[4][4], cmat[4][4];
132         int a, b, totcol, totedge=0, totvert=0, totface=0, ok=0, vertofs, map[MAXMAT];
133         int     i, j, index, haskey=0, hasdefgroup=0;
134         bDeformGroup *dg, *odg;
135         MDeformVert *dvert, *dvertmain;
136         
137         if(G.obedit) return 0;
138         
139         ob= OBACT;
140         if(!ob || ob->type!=OB_MESH) return 0;
141
142 #ifdef WITH_VERSE
143         /* it isn't allowed to join shared object at verse server
144          * this function will be implemented as soon as possible */
145         base= FIRSTBASE;
146         while(base) {
147                 if TESTBASELIB(base) {
148                         if(base->object->type==OB_MESH) {
149                                 if(base->object->vnode) {
150                                         haskey= 1;
151                                         break;
152                                 }
153                         }
154                 }
155                 base= base->next;
156         }
157         if(haskey) {
158                 error("Can't join meshes shared at verse server");
159                 return 0;
160         }
161 #endif
162
163         /* count */
164         base= FIRSTBASE;
165         while(base) {
166                 if TESTBASELIB(base) {
167                         if(base->object->type==OB_MESH) {
168                                 me= base->object->data;
169                                 totvert+= me->totvert;
170                                 totface+= me->totface;
171
172                                 if(base->object == ob) ok= 1;
173
174                                 if(me->key) {
175                                         haskey= 1;
176                                         break;
177                                 }
178                         }
179                 }
180                 base= base->next;
181         }
182         
183         if(haskey) {
184                 error("Can't join meshes with vertex keys");
185                 return 0;
186         }
187         /* that way the active object is always selected */ 
188         if(ok==0) return 0;
189         
190         if(totvert==0 || totvert>MESH_MAX_VERTS) return 0;
191         
192
193
194         /* if needed add edges to other meshes */
195         for(base= FIRSTBASE; base; base= base->next) {
196                 if TESTBASELIB(base) {
197                         if(base->object->type==OB_MESH) {
198                                 me= base->object->data;
199                                 totedge += me->totedge;
200                         }
201                 }
202         }
203         
204         /* new material indices and material array */
205         matar= MEM_callocN(sizeof(void *)*MAXMAT, "join_mesh");
206         totcol= ob->totcol;
207         
208         /* obact materials in new main array, is nicer start! */
209         for(a=1; a<=ob->totcol; a++) {
210                 matar[a-1]= give_current_material(ob, a);
211                 id_us_plus((ID *)matar[a-1]);
212                 /* increase id->us : will be lowered later */
213         }
214         
215         base= FIRSTBASE;
216         while(base) {
217                 if TESTBASELIB(base) {
218                         if(ob!=base->object && base->object->type==OB_MESH) {
219                                 me= base->object->data;
220
221                                 // Join this object's vertex groups to the base one's
222                                 for (dg=base->object->defbase.first; dg; dg=dg->next){
223                                         hasdefgroup= 1;
224                                         
225                                         /* See if this group exists in the object */
226                                         for (odg=ob->defbase.first; odg; odg=odg->next){
227                                                 if (!strcmp(odg->name, dg->name)){
228                                                         break;
229                                                 }
230                                         }
231                                         if (!odg){
232                                                 odg = MEM_callocN (sizeof(bDeformGroup), "join deformGroup");
233                                                 memcpy (odg, dg, sizeof(bDeformGroup));
234                                                 BLI_addtail(&ob->defbase, odg);
235                                         }
236
237                                 }
238                                 if (ob->defbase.first && ob->actdef==0)
239                                         ob->actdef=1;
240
241                                 if(me->totvert) {
242                                         for(a=1; a<=base->object->totcol; a++) {
243                                                 ma= give_current_material(base->object, a);
244                                                 if(ma) {
245                                                         for(b=0; b<totcol; b++) {
246                                                                 if(ma == matar[b]) break;
247                                                         }
248                                                         if(b==totcol) {
249                                                                 matar[b]= ma;
250                                                                 ma->id.us++;
251                                                                 totcol++;
252                                                         }
253                                                         if(totcol>=MAXMAT-1) break;
254                                                 }
255                                         }
256                                 }
257                         }
258                         if(totcol>=MAXMAT-1) break;
259                 }
260                 base= base->next;
261         }
262
263         me= ob->data;
264         mvert= mvertmain= MEM_mallocN(totvert*sizeof(MVert), "joinmesh vert");
265
266         if(totedge) medge= medgemain= MEM_callocN(totedge*sizeof(MEdge), "joinmesh edge");
267         else medgemain= NULL;
268         
269         if (totface) mface= mfacemain= MEM_mallocN(totface*sizeof(MFace), "joinmesh face");
270         else mfacemain= NULL;
271
272         if(me->mcol) mcol= mcolmain= MEM_callocN(totface*4*sizeof(int), "joinmesh mcol");
273         else mcolmain= NULL;
274
275         /* if active object doesn't have Tfaces, but one in the selection does,
276            make TFaces for active, so we don't lose texture information in the
277            join process */
278         if(me->tface || testSelected_TfaceMesh()) tface= tfacemain= MEM_callocN(totface*4*sizeof(TFace), "joinmesh4");
279         else tfacemain= NULL;
280
281         if(me->dvert || hasdefgroup)
282                 dvert= dvertmain= MEM_callocN(totvert*sizeof(MDeformVert), "joinmesh5");
283         else dvert=dvertmain= NULL;
284
285         vertofs= 0;
286         
287         /* inverse transorm all selected meshes in this object */
288         Mat4Invert(imat, ob->obmat);
289         
290         base= FIRSTBASE;
291         while(base) {
292                 nextb= base->next;
293                 if TESTBASELIB(base) {
294                         if(base->object->type==OB_MESH) {
295                                 
296                                 me= base->object->data;
297                                 
298                                 if(me->totvert) {
299                                         
300                                         memcpy(mvert, me->mvert, me->totvert*sizeof(MVert));
301                                         
302                                         copy_dverts(dvert, me->dvert, me->totvert);
303
304                                         /* NEW VERSION */
305                                         if (dvertmain){
306                                                 for (i=0; i<me->totvert; i++){
307                                                         for (j=0; j<dvert[i].totweight; j++){
308                                                                 //      Find the old vertex group
309                                                                 odg = BLI_findlink (&base->object->defbase, dvert[i].dw[j].def_nr);
310                                                                 if(odg) {
311                                                                         //      Search for a match in the new object
312                                                                         for (dg=ob->defbase.first, index=0; dg; dg=dg->next, index++){
313                                                                                 if (!strcmp(dg->name, odg->name)){
314                                                                                         dvert[i].dw[j].def_nr = index;
315                                                                                         break;
316                                                                                 }
317                                                                         }
318                                                                 }
319                                                         }
320                                                 }
321                                                 dvert+=me->totvert;
322                                         }
323
324                                         if(base->object != ob) {
325                                                 /* watch this: switch matmul order really goes wrong */
326                                                 Mat4MulMat4(cmat, base->object->obmat, imat);
327                                                 
328                                                 a= me->totvert;
329                                                 while(a--) {
330                                                         Mat4MulVecfl(cmat, mvert->co);
331                                                         mvert++;
332                                                 }
333                                         }
334                                         else mvert+= me->totvert;
335                                         
336                                         if(mcolmain) {
337                                                 if(me->mcol) memcpy(mcol, me->mcol, me->totface*4*4);
338                                                 mcol+= 4*me->totface;
339                                         }
340                                 }
341                                 if(me->totface) {
342                                 
343                                         /* make mapping for materials */
344                                         memset(map, 0, 4*MAXMAT);
345                                         for(a=1; a<=base->object->totcol; a++) {
346                                                 ma= give_current_material(base->object, a);
347                                                 if(ma) {
348                                                         for(b=0; b<totcol; b++) {
349                                                                 if(ma == matar[b]) {
350                                                                         map[a-1]= b;
351                                                                         break;
352                                                                 }
353                                                         }
354                                                 }
355                                         }
356
357                                         memcpy(mface, me->mface, me->totface*sizeof(MFace));
358                                         
359                                         a= me->totface;
360                                         while(a--) {
361                                                 mface->v1+= vertofs;
362                                                 mface->v2+= vertofs;
363                                                 mface->v3+= vertofs;
364                                                 if(mface->v4) mface->v4+= vertofs;
365                                                 
366                                                 mface->mat_nr= map[(int)mface->mat_nr];
367                                                 
368                                                 mface++;
369                                         }
370                                         
371                                         if(tfacemain) {
372                                                 if(me->tface) {
373                                                         memcpy(tface, me->tface, me->totface*sizeof(TFace));
374                                                         tface+= me->totface;
375                                                 }
376                                                 else {
377                                                         for(a=0; a<me->totface; a++, tface++) {
378                                                                 default_tface(tface);
379                                                         }
380                                                 }
381                                         }
382                                         
383                                 }
384                                 
385                                 if(me->totedge) {
386                                         memcpy(medge, me->medge, me->totedge*sizeof(MEdge));
387                                         
388                                         a= me->totedge;
389                                         while(a--) {
390                                                 medge->v1+= vertofs;
391                                                 medge->v2+= vertofs;
392                                                 medge++;
393                                         }
394                                 }
395                                 
396                                 vertofs+= me->totvert;
397                                 
398                                 if(base->object!=ob) {
399                                         free_and_unlink_base(base);
400                                 }
401                         }
402                 }
403                 base= nextb;
404         }
405         
406         me= ob->data;
407         
408         if(me->mvert) MEM_freeN(me->mvert);
409         me->mvert= mvertmain;
410
411         if(me->medge) MEM_freeN(me->medge);
412         me->medge= medgemain;
413
414         if(me->mface) MEM_freeN(me->mface);
415         me->mface= mfacemain;
416
417         if(me->dvert) free_dverts(me->dvert, me->totvert);
418         me->dvert = dvertmain;
419
420         if(me->mcol) MEM_freeN(me->mcol);
421         me->mcol= (MCol *)mcolmain;
422         
423         if(me->tface) MEM_freeN(me->tface);
424         me->tface= tfacemain;
425         
426         me->totvert= totvert;
427         me->totedge= totedge;
428         me->totface= totface;
429         
430         /* old material array */
431         for(a=1; a<=ob->totcol; a++) {
432                 ma= ob->mat[a-1];
433                 if(ma) ma->id.us--;
434         }
435         for(a=1; a<=me->totcol; a++) {
436                 ma= me->mat[a-1];
437                 if(ma) ma->id.us--;
438         }
439         if(ob->mat) MEM_freeN(ob->mat);
440         if(me->mat) MEM_freeN(me->mat);
441         ob->mat= me->mat= 0;
442         
443         if(totcol) {
444                 me->mat= matar;
445                 ob->mat= MEM_callocN(sizeof(void *)*totcol, "join obmatar");
446         }
447         else MEM_freeN(matar);
448         
449         ob->totcol= me->totcol= totcol;
450         ob->colbits= 0;
451         
452         /* other mesh users */
453         test_object_materials((ID *)me);
454         
455         DAG_scene_sort(G.scene);        // removed objects, need to rebuild dag before editmode call
456         
457         enter_editmode(EM_WAITCURSOR);
458         exit_editmode(EM_FREEDATA|EM_WAITCURSOR);       // freedata, but no undo
459         
460         allqueue(REDRAWVIEW3D, 0);
461         allqueue(REDRAWBUTSSHADING, 0);
462
463         BIF_undo_push("Join Mesh");
464         return 1;
465 }
466
467
468 void fasterdraw(void)
469 {
470         Base *base;
471         Mesh *me;
472         int toggle, a;
473
474         if(G.obedit || G.vd==NULL) return;
475
476         /* reset flags */
477         me= G.main->mesh.first;
478         while(me) {
479                 me->flag &= ~ME_ISDONE;
480                 me= me->id.next;
481         }
482
483         base= FIRSTBASE;
484         while(base) {
485                 if( TESTBASELIB(base) && (base->object->type==OB_MESH)) {
486                         me= base->object->data;
487                         if(me->id.lib==0 && (me->flag & ME_ISDONE)==0) {
488                                 me->flag |= ME_ISDONE;
489                                 toggle= 0;
490                                 for(a=0; a<me->totedge; a++) {
491                                         MEdge *med = &me->medge[a];
492
493                                         if( (med->flag & ME_EDGEDRAW) && !( (toggle++) & 3) ) {
494                                                 med->flag ^= ME_EDGEDRAW;
495                                         }
496                                 }
497                         }
498                 }
499                 base= base->next;
500         }
501
502         /* important?: reset flags again */
503         me= G.main->mesh.first;
504         while(me) {
505                 me->flag &= ~ME_ISDONE;
506                 me= me->id.next;
507         }
508
509         allqueue(REDRAWVIEW3D, 0);
510 }
511
512 void slowerdraw(void)           /* reset fasterdraw */
513 {
514         Base *base;
515         Mesh *me;
516         int a;
517
518         if(G.obedit || G.vd==NULL) return;
519
520         base= FIRSTBASE;
521         while(base) {
522                 if( TESTBASELIB(base) && (base->object->type==OB_MESH)) {
523                         me= base->object->data;
524                         if(me->id.lib==0) {
525                                 for(a=0; a<me->totedge; a++) {
526                                         me->medge[a].flag |= ME_EDGEDRAW;
527                                 }
528                         }
529                 }
530                 base= base->next;
531         }
532
533         allqueue(REDRAWVIEW3D, 0);
534 }
535
536 /* ********************** SORT FACES ******************* */
537
538 static void permutate(void *list, int num, int size, int *index)
539 {
540         void *buf;
541         int len;
542         int i;
543
544         len = num * size;
545
546         buf = MEM_mallocN(len, "permutate");
547         memcpy(buf, list, len);
548         
549         for (i = 0; i < num; i++) {
550                 memcpy((char *)list + (i * size), (char *)buf + (index[i] * size), size);
551         }
552         MEM_freeN(buf);
553 }
554
555 static MVert *mvertbase;
556 static MFace *mfacebase;
557
558 static int verg_mface(const void *v1, const void *v2)
559 {
560         MFace *x1, *x2;
561
562         MVert *ve1, *ve2;
563         int i1, i2;
564
565         i1 = ((int *) v1)[0];
566         i2 = ((int *) v2)[0];
567         
568         x1 = mfacebase + i1;
569         x2 = mfacebase + i2;
570
571         ve1= mvertbase+x1->v1;
572         ve2= mvertbase+x2->v1;
573         
574         if( ve1->co[2] > ve2->co[2] ) return 1;
575         else if( ve1->co[2] < ve2->co[2]) return -1;
576         return 0;
577 }
578
579
580 void sort_faces(void)
581 {
582         Object *ob= OBACT;
583         Mesh *me;
584         
585         int i, *index;
586         
587         if(ob==0) return;
588         if(G.obedit) return;
589         if(ob->type!=OB_MESH) return;
590         
591         if(okee("Sort faces in Z axis")==0) return;
592         me= ob->data;
593         if(me->totface==0) return;
594
595 /*      create index list */
596         index = (int *) MEM_mallocN(sizeof(int) * me->totface, "sort faces");
597         for (i = 0; i < me->totface; i++) {
598                 index[i] = i;
599         }
600         mvertbase= me->mvert;
601         mfacebase = me->mface;
602
603 /* sort index list instead of faces itself 
604    and apply this permutation to the face list plus
605    to the texture faces */
606         qsort(index, me->totface, sizeof(int), verg_mface);
607
608         permutate(mfacebase, me->totface, sizeof(MFace), index);
609         if (me->tface) 
610                 permutate(me->tface, me->totface, sizeof(TFace), index);
611
612         MEM_freeN(index);
613
614         allqueue(REDRAWVIEW3D, 0);
615         DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
616 }
617
618 /* ********************* MESH VERTEX OCTREE LOOKUP ************* */
619
620 /* important note; this is unfinished, needs better API for editmode, and custom threshold */
621
622 #define MOC_RES                 8
623 #define MOC_NODE_RES    8
624 #define MOC_THRESH              0.0002f
625
626 typedef struct MocNode {
627         struct MocNode *next;
628         long index[MOC_NODE_RES];
629 } MocNode;
630
631 static int mesh_octree_get_base_offs(float *co, float *offs, float *div)
632 {
633         int vx, vy, vz;
634         
635         vx= floor( (co[0]-offs[0])/div[0] );
636         vy= floor( (co[1]-offs[1])/div[1] );
637         vz= floor( (co[2]-offs[2])/div[2] );
638         
639         CLAMP(vx, 0, MOC_RES-1);
640         CLAMP(vy, 0, MOC_RES-1);
641         CLAMP(vz, 0, MOC_RES-1);
642
643         return (vx*MOC_RES*MOC_RES) + vy*MOC_RES + vz;
644 }
645
646 static void mesh_octree_add_node(MocNode **bt, long index)
647 {
648         if(*bt==NULL) {
649                 *bt= MEM_callocN(sizeof(MocNode), "MocNode");
650                 (*bt)->index[0]= index;
651         }
652         else {
653                 int a;
654                 for(a=0; a<MOC_NODE_RES; a++) {
655                         if((*bt)->index[a]==index)
656                                 return;
657                         else if((*bt)->index[a]==0) {
658                                 (*bt)->index[a]= index;
659                                 return;
660                         }
661                 }
662                 mesh_octree_add_node(&(*bt)->next, index);
663         }
664 }
665
666 static void mesh_octree_free_node(MocNode **bt)
667 {
668         if( (*bt)->next ) {
669                 mesh_octree_free_node(&(*bt)->next);
670         }
671         MEM_freeN(*bt);
672 }
673
674
675 /* temporal define, just to make nicer code below */
676 #define MOC_ADDNODE(vx, vy, vz) mesh_octree_add_node(basetable + ((vx)*MOC_RES*MOC_RES) + (vy)*MOC_RES + (vz), index)
677
678 static void mesh_octree_add_nodes(MocNode **basetable, float *co, float *offs, float *div, long index)
679 {
680         float fx, fy, fz;
681         int vx, vy, vz;
682         
683         fx= (co[0]-offs[0])/div[0];
684         fy= (co[1]-offs[1])/div[1];
685         fz= (co[2]-offs[2])/div[2];
686         CLAMP(fx, 0.0f, MOC_RES-MOC_THRESH);
687         CLAMP(fy, 0.0f, MOC_RES-MOC_THRESH);
688         CLAMP(fz, 0.0f, MOC_RES-MOC_THRESH);
689         
690         vx= floor(fx);
691         vy= floor(fy);
692         vz= floor(fz);
693         
694         MOC_ADDNODE(vx, vy, vz);
695         
696         if( vx>0 )
697                 if( fx-((float)vx)-MOC_THRESH < 0.0f)
698                         MOC_ADDNODE(vx-1, vy, vz);
699         if( vx<MOC_RES-2 )
700                 if( fx-((float)vx)+MOC_THRESH > 1.0f)
701                         MOC_ADDNODE(vx+1, vy, vz);
702
703         if( vy>0 )
704                 if( fy-((float)vy)-MOC_THRESH < 0.0f) 
705                         MOC_ADDNODE(vx, vy-1, vz);
706         if( vy<MOC_RES-2 )
707                 if( fy-((float)vy)+MOC_THRESH > 1.0f) 
708                         MOC_ADDNODE(vx, vy+1, vz);
709
710         if( vz>0 )
711                 if( fz-((float)vz)-MOC_THRESH < 0.0f) 
712                         MOC_ADDNODE(vx, vy, vz-1);
713         if( vz<MOC_RES-2 )
714                 if( fz-((float)vz)+MOC_THRESH > 1.0f) 
715                         MOC_ADDNODE(vx, vy, vz+1);
716         
717 }
718
719 static long mesh_octree_find_index(MocNode **bt, MVert *mvert, float *co)
720 {
721         float *vec;
722         int a;
723         
724         if(*bt==NULL)
725                 return -1;
726         
727         for(a=0; a<MOC_NODE_RES; a++) {
728                 if((*bt)->index[a]) {
729                         /* does mesh verts and editmode, code looks potential dangerous, octree should really be filled OK! */
730                         if(mvert) {
731                                 vec= (mvert+(*bt)->index[a]-1)->co;
732                                 if(FloatCompare(vec, co, MOC_THRESH))
733                                         return (*bt)->index[a]-1;
734                         }
735                         else {
736                                 EditVert *eve= (EditVert *)((*bt)->index[a]);
737                                 if(FloatCompare(eve->co, co, MOC_THRESH))
738                                         return (*bt)->index[a];
739                         }
740                 }
741                 else return -1;
742         }
743         if( (*bt)->next)
744                 return mesh_octree_find_index(&(*bt)->next, mvert, co);
745         
746         return -1;
747 }
748
749
750 /* mode is 's' start, or 'e' end, or 'u' use */
751 /* if end, ob can be NULL */
752 long mesh_octree_table(Object *ob, float *co, char mode)
753 {
754         MocNode **bt;
755         static MocNode **basetable= NULL;
756         static float offs[3], div[3];
757         
758         if(mode=='u') {         /* use table */
759                 if(basetable==NULL)
760                         mesh_octree_table(ob, NULL, 's');
761            
762                 if(basetable) {
763                         Mesh *me= ob->data;
764                         bt= basetable + mesh_octree_get_base_offs(co, offs, div);
765                         if(ob==G.obedit)
766                                 return mesh_octree_find_index(bt, NULL, co);
767                         else
768                                 return mesh_octree_find_index(bt, me->mvert, co);
769                 }
770                 return -1;
771         }
772         else if(mode=='s') {    /* start table */
773                 Mesh *me= ob->data;
774                 BoundBox *bb = mesh_get_bb(me);
775                 
776                 /* for quick unit coordinate calculus */
777                 VECCOPY(offs, bb->vec[0]);
778                 offs[0]-= MOC_THRESH;           /* we offset it 1 threshold unit extra */
779                 offs[1]-= MOC_THRESH;
780                 offs[2]-= MOC_THRESH;
781                         
782                 VecSubf(div, bb->vec[6], bb->vec[0]);
783                 div[0]+= 2*MOC_THRESH;          /* and divide with 2 threshold unit more extra (try 8x8 unit grid on paint) */
784                 div[1]+= 2*MOC_THRESH;
785                 div[2]+= 2*MOC_THRESH;
786                 
787                 VecMulf(div, 1.0f/MOC_RES);
788                 if(div[0]==0.0f) div[0]= 1.0f;
789                 if(div[1]==0.0f) div[1]= 1.0f;
790                 if(div[2]==0.0f) div[2]= 1.0f;
791                         
792                 if(basetable) /* happens when entering this call without ending it */
793                         mesh_octree_table(ob, co, 'e');
794                 
795                 basetable= MEM_callocN(MOC_RES*MOC_RES*MOC_RES*sizeof(void *), "sym table");
796                 
797                 if(ob==G.obedit) {
798                         EditVert *eve;
799                         
800                         for(eve= G.editMesh->verts.first; eve; eve= eve->next) {
801                                 mesh_octree_add_nodes(basetable, eve->co, offs, div, (long)(eve));
802                         }
803                 }
804                 else {          
805                         MVert *mvert;
806                         long a;
807                         
808                         for(a=1, mvert= me->mvert; a<=me->totvert; a++, mvert++) {
809                                 mesh_octree_add_nodes(basetable, mvert->co, offs, div, a);
810                         }
811                 }
812         }
813         else if(mode=='e') { /* end table */
814                 if(basetable) {
815                         int a;
816                         
817                         for(a=0, bt=basetable; a<MOC_RES*MOC_RES*MOC_RES; a++, bt++) {
818                                 if(*bt) mesh_octree_free_node(bt);
819                         }
820                         MEM_freeN(basetable);
821                         basetable= NULL;
822                 }
823         }
824         return 0;
825 }
826
827 int mesh_get_x_mirror_vert(Object *ob, int index)
828 {
829         Mesh *me= ob->data;
830         MVert *mvert= me->mvert+index;
831         float vec[3];
832         
833         vec[0]= -mvert->co[0];
834         vec[1]= mvert->co[1];
835         vec[2]= mvert->co[2];
836         
837         return mesh_octree_table(ob, vec, 'u');
838 }
839
840 EditVert *editmesh_get_x_mirror_vert(Object *ob, float *co)
841 {
842         float vec[3];
843         long poinval;
844         
845         vec[0]= -co[0];
846         vec[1]= co[1];
847         vec[2]= co[2];
848         
849         poinval= mesh_octree_table(ob, vec, 'u');
850         if(poinval != -1)
851                 return (EditVert *)(poinval);
852         return NULL;
853 }
854