remove BKE_array_mallocn.h, replace use with BLI_array.h, also removed
[blender.git] / source / blender / editors / mesh / editmesh_loop.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/editmesh_loop.c
29  *  \ingroup edmesh
30  */
31
32
33 /*
34
35 editmesh_loop: tools with own drawing subloops, select, knife, subdiv
36
37 */
38
39 #include <stdlib.h>
40 #include <string.h>
41 #include <math.h>
42
43 #include "MEM_guardedalloc.h"
44
45
46 #include "DNA_object_types.h"
47 #include "DNA_scene_types.h"
48 #include "DNA_screen_types.h"
49
50 #include "BLI_blenlib.h"
51 #include "BLI_math.h"
52 #include "BLI_utildefines.h"
53 #include "BLI_editVert.h"
54 #include "BLI_ghash.h"
55
56 #include "BKE_context.h"
57 #include "BKE_depsgraph.h"
58 #include "BKE_mesh.h"
59
60 #include "PIL_time.h"
61
62 #include "BIF_gl.h"
63
64 #include "RNA_access.h"
65 #include "RNA_define.h"
66
67 #include "WM_api.h"
68 #include "WM_types.h"
69
70 #include "ED_mesh.h"
71 #include "ED_view3d.h"
72
73 #include "mesh_intern.h"
74
75 /* **** XXX ******** */
76 static void error(const char *UNUSED(arg)) {}
77 /* **** XXX ******** */
78
79 /*   ***************** TRAIL ************************
80
81 Read a trail of mouse coords and return them as an array of CutCurve structs
82 len returns number of mouse coords read before commiting with RETKEY   
83 It is up to the caller to free the block when done with it,
84
85 XXX Is only used here, so local inside this file (ton)
86  */
87
88 #define TRAIL_POLYLINE 1 /* For future use, They don't do anything yet */
89 #define TRAIL_FREEHAND 2
90 #define TRAIL_MIXED    3 /* (1|2) */
91 #define TRAIL_AUTO     4 
92 #define TRAIL_MIDPOINTS 8
93
94 typedef struct CutCurve {
95         float  x; 
96         float  y;
97 } CutCurve;
98
99
100 /* ******************************************************************** */
101 /* Knife Subdivide Tool.  Subdivides edges intersected by a mouse trail
102         drawn by user.
103         
104         Currently mapped to KKey when in MeshEdit mode.
105         Usage:
106                 Hit Shift K, Select Centers or Exact
107                 Hold LMB down to draw path, hit RETKEY.
108                 ESC cancels as expected.
109    
110         Contributed by Robert Wenzlaff (Det. Thorn).
111
112         2.5 revamp:
113         - non modal (no menu before cutting)
114         - exit on mouse release
115         - polygon/segment drawing can become handled by WM cb later
116
117 */
118
119 #define KNIFE_EXACT             1
120 #define KNIFE_MIDPOINT  2
121 #define KNIFE_MULTICUT  3
122
123 static EnumPropertyItem knife_items[]= {
124         {KNIFE_EXACT, "EXACT", 0, "Exact", ""},
125         {KNIFE_MIDPOINT, "MIDPOINTS", 0, "Midpoints", ""},
126         {KNIFE_MULTICUT, "MULTICUT", 0, "Multicut", ""},
127         {0, NULL, 0, NULL, NULL}
128 };
129
130 /* seg_intersect() Determines if and where a mouse trail intersects an EditEdge */
131
132 static float seg_intersect(EditEdge *e, CutCurve *c, int len, char mode, struct GHash *gh)
133 {
134 #define MAXSLOPE 100000
135         float  x11, y11, x12=0, y12=0, x2max, x2min, y2max;
136         float  y2min, dist, lastdist=0, xdiff2, xdiff1;
137         float  m1, b1, m2, b2, x21, x22, y21, y22, xi;
138         float  yi, x1min, x1max, y1max, y1min, perc=0; 
139         float  *scr;
140         float  threshold;
141         int  i;
142         
143         threshold = 0.000001; /*tolerance for vertex intersection*/
144         // XXX  threshold = scene->toolsettings->select_thresh / 100;
145         
146         /* Get screen coords of verts */
147         scr = BLI_ghash_lookup(gh, e->v1);
148         x21=scr[0];
149         y21=scr[1];
150         
151         scr = BLI_ghash_lookup(gh, e->v2);
152         x22=scr[0];
153         y22=scr[1];
154         
155         xdiff2=(x22-x21);  
156         if (xdiff2) {
157                 m2=(y22-y21)/xdiff2;
158                 b2= ((x22*y21)-(x21*y22))/xdiff2;
159         }
160         else {
161                 m2=MAXSLOPE;  /* Verticle slope  */
162                 b2=x22;      
163         }
164         
165         /*check for *exact* vertex intersection first*/
166         if(mode!=KNIFE_MULTICUT){
167                 for (i=0; i<len; i++){
168                         if (i>0){
169                                 x11=x12;
170                                 y11=y12;
171                         }
172                         else {
173                                 x11=c[i].x;
174                                 y11=c[i].y;
175                         }
176                         x12=c[i].x;
177                         y12=c[i].y;
178                         
179                         /*test e->v1*/
180                         if((x11 == x21 && y11 == y21) || (x12 == x21 && y12 == y21)){
181                                 e->v1->f1 = 1;
182                                 perc = 0;
183                                 return(perc);
184                         }
185                         /*test e->v2*/
186                         else if((x11 == x22 && y11 == y22) || (x12 == x22 && y12 == y22)){
187                                 e->v2->f1 = 1;
188                                 perc = 0;
189                                 return(perc);
190                         }
191                 }
192         }
193         
194         /*now check for edge interesect (may produce vertex intersection as well)*/
195         for (i=0; i<len; i++){
196                 if (i>0){
197                         x11=x12;
198                         y11=y12;
199                 }
200                 else {
201                         x11=c[i].x;
202                         y11=c[i].y;
203                 }
204                 x12=c[i].x;
205                 y12=c[i].y;
206                 
207                 /* Perp. Distance from point to line */
208                 if (m2!=MAXSLOPE) dist=(y12-m2*x12-b2);/* /sqrt(m2*m2+1); Only looking for */
209                         /* change in sign.  Skip extra math */  
210                 else dist=x22-x12;      
211                 
212                 if (i==0) lastdist=dist;
213                 
214                 /* if dist changes sign, and intersect point in edge's Bound Box*/
215                 if ((lastdist*dist)<=0){
216                         xdiff1=(x12-x11); /* Equation of line between last 2 points */
217                         if (xdiff1){
218                                 m1=(y12-y11)/xdiff1;
219                                 b1= ((x12*y11)-(x11*y12))/xdiff1;
220                         }
221                         else{
222                                 m1=MAXSLOPE;
223                                 b1=x12;
224                         }
225                         x2max=MAX2(x21,x22)+0.001f; /* prevent missed edges   */
226                         x2min=MIN2(x21,x22)-0.001f; /* due to round off error */
227                         y2max=MAX2(y21,y22)+0.001f;
228                         y2min=MIN2(y21,y22)-0.001f;
229                         
230                         /* Found an intersect,  calc intersect point */
231                         if (m1==m2){ /* co-incident lines */
232                                 /* cut at 50% of overlap area*/
233                                 x1max=MAX2(x11, x12);
234                                 x1min=MIN2(x11, x12);
235                                 xi= (MIN2(x2max,x1max)+MAX2(x2min,x1min))/2.0f;
236                                 
237                                 y1max=MAX2(y11, y12);
238                                 y1min=MIN2(y11, y12);
239                                 yi= (MIN2(y2max,y1max)+MAX2(y2min,y1min))/2.0f;
240                         }                       
241                         else if (m2==MAXSLOPE){ 
242                                 xi=x22;
243                                 yi=m1*x22+b1;
244                         }
245                         else if (m1==MAXSLOPE){ 
246                                 xi=x12;
247                                 yi=m2*x12+b2;
248                         }
249                         else {
250                                 xi=(b1-b2)/(m2-m1);
251                                 yi=(b1*m2-m1*b2)/(m2-m1);
252                         }
253                         
254                         /* Intersect inside bounding box of edge?*/
255                         if ((xi>=x2min)&&(xi<=x2max)&&(yi<=y2max)&&(yi>=y2min)){
256                                 /*test for vertex intersect that may be 'close enough'*/
257                                 if(mode!=KNIFE_MULTICUT){
258                                         if(xi <= (x21 + threshold) && xi >= (x21 - threshold)){
259                                                 if(yi <= (y21 + threshold) && yi >= (y21 - threshold)){
260                                                         e->v1->f1 = 1;
261                                                         perc = 0;
262                                                         break;
263                                                 }
264                                         }
265                                         if(xi <= (x22 + threshold) && xi >= (x22 - threshold)){
266                                                 if(yi <= (y22 + threshold) && yi >= (y22 - threshold)){
267                                                         e->v2->f1 = 1;
268                                                         perc = 0;
269                                                         break;
270                                                 }
271                                         }
272                                 }
273                                 if ((m2 <= 1.0f) && (m2 >= -1.0f)) perc = (xi-x21)/(x22-x21);
274                                 else perc=(yi-y21)/(y22-y21); /*lower slope more accurate*/
275                                 //isect=32768.0*(perc+0.0000153); /* Percentage in 1/32768ths */
276                                 
277                                 break;
278                         }
279                 }       
280                 lastdist=dist;
281         }
282         return(perc);
283
284
285 /* for multicut */
286 #define MAX_CUTS 256
287
288 /* for amount of edges */
289 #define MAX_CUT_EDGES 1024
290
291 static int knife_cut_exec(bContext *C, wmOperator *op)
292 {
293         Object *obedit= CTX_data_edit_object(C);
294         EditMesh *em= BKE_mesh_get_editmesh(((Mesh *)obedit->data));
295         ARegion *ar= CTX_wm_region(C);
296         EditEdge *eed;
297         EditVert *eve;
298         CutCurve curve[MAX_CUT_EDGES];
299         struct GHash *gh;
300         float isect=0.0;
301         float  *scr, co[4];
302         int len=0;
303         short numcuts= RNA_int_get(op->ptr, "num_cuts"); 
304         short mode= RNA_enum_get(op->ptr, "type");
305 //      int corner_cut_pattern= RNA_enum_get(op->ptr,"corner_cut_pattern");
306         
307         /* edit-object needed for matrix, and ar->regiondata for projections to work */
308         if (ELEM3(NULL, obedit, ar, ar->regiondata))
309                 return OPERATOR_CANCELLED;
310         
311         if (EM_nvertices_selected(em) < 2) {
312                 error("No edges are selected to operate on");
313                 BKE_mesh_end_editmesh(obedit->data, em);
314                 return OPERATOR_CANCELLED;
315         }
316
317         /* get the cut curve */
318         RNA_BEGIN(op->ptr, itemptr, "path") {
319                 
320                 RNA_float_get_array(&itemptr, "loc", (float *)&curve[len]);
321                 len++;
322                 if(len>= MAX_CUT_EDGES) break;
323         }
324         RNA_END;
325         
326         if(len<2) {
327                 BKE_mesh_end_editmesh(obedit->data, em);
328                 return OPERATOR_CANCELLED;
329         }
330
331         /*store percentage of edge cut for KNIFE_EXACT here.*/
332         for(eed=em->edges.first; eed; eed= eed->next) 
333                 eed->tmp.fp = 0.0; 
334         
335         /*the floating point coordinates of verts in screen space will be stored in a hash table according to the vertices pointer*/
336         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife_cut_exec gh");
337         for(eve=em->verts.first; eve; eve=eve->next){
338                 scr = MEM_mallocN(sizeof(float)*2, "Vertex Screen Coordinates");
339                 VECCOPY(co, eve->co);
340                 co[3]= 1.0;
341                 mul_m4_v4(obedit->obmat, co);
342                 project_float(ar, co, scr);
343                 BLI_ghash_insert(gh, eve, scr);
344                 eve->f1 = 0; /*store vertex intersection flag here*/
345         
346         }
347         
348         eed= em->edges.first;           
349         while(eed) {    
350                 if( eed->v1->f & eed->v2->f & SELECT ){         // NOTE: uses vertex select, subdiv doesnt do edges yet
351                         isect= seg_intersect(eed, curve, len, mode, gh);
352                         if (isect!=0.0f) eed->f2= 1;
353                         else eed->f2=0;
354                         eed->tmp.fp= isect;
355                 }
356                 else {
357                         eed->f2=0;
358                         eed->f1=0;
359                 }
360                 eed= eed->next;
361         }
362         
363         if (mode==KNIFE_MIDPOINT) esubdivideflag(obedit, em, SELECT, 0, 0, B_KNIFE, 1, SUBDIV_CORNER_INNERVERT, SUBDIV_SELECT_INNER);
364         else if (mode==KNIFE_MULTICUT) esubdivideflag(obedit, em, SELECT, 0, 0, B_KNIFE, numcuts, SUBDIV_CORNER_INNERVERT, SUBDIV_SELECT_INNER);
365         else esubdivideflag(obedit, em, SELECT, 0, 0, B_KNIFE|B_PERCENTSUBD, 1, SUBDIV_CORNER_INNERVERT, SUBDIV_SELECT_INNER);
366
367         eed=em->edges.first;
368         while(eed){
369                 eed->f2=0;
370                 eed->f1=0;
371                 eed=eed->next;
372         }       
373         
374         BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);
375         
376         BKE_mesh_end_editmesh(obedit->data, em);
377
378         DAG_id_tag_update(obedit->data, 0);
379         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
380
381         return OPERATOR_FINISHED;
382 }
383
384
385 void MESH_OT_knife_cut(wmOperatorType *ot)
386 {
387         PropertyRNA *prop;
388         
389         ot->name= "Knife Cut";
390         ot->description= "Cut selected edges and faces into parts";
391         ot->idname= "MESH_OT_knife_cut";
392         
393         ot->invoke= WM_gesture_lines_invoke;
394         ot->modal= WM_gesture_lines_modal;
395         ot->exec= knife_cut_exec;
396         ot->cancel= WM_gesture_lines_cancel;
397         
398         ot->poll= EM_view3d_poll;
399         
400         /* flags */
401         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
402         
403         RNA_def_enum(ot->srna, "type", knife_items, KNIFE_EXACT, "Type", "");
404         prop= RNA_def_property(ot->srna, "path", PROP_COLLECTION, PROP_NONE);
405         RNA_def_property_struct_runtime(prop, &RNA_OperatorMousePath);
406         RNA_def_int(ot->srna, "num_cuts", 1, 1, MAX_CUTS, "Number of Cuts", "Only for Multi-Cut", 1, MAX_CUTS);
407         // doesn't work atm.. RNA_def_enum(ot->srna, "corner_cut_pattern", corner_type_items, SUBDIV_CORNER_INNERVERT, "Corner Cut Pattern", "Topology pattern to use to fill a face after cutting across its corner");
408         
409         /* internal */
410         RNA_def_int(ot->srna, "cursor", BC_KNIFECURSOR, 0, INT_MAX, "Cursor", "", 0, INT_MAX);
411 }
412
413 /* ******************************************************* */
414