minor warning/fixes
[blender-staging.git] / source / blender / editors / mesh / editbmesh_bvh.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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
17  *
18  * The Original Code is Copyright (C) 2010 by Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Joseph Eagar
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27 #define IN_EDITMESHBVH
28
29 #include <stdlib.h>
30 #include <stdarg.h>
31 #include <string.h>
32 #include <math.h>
33 #include <float.h>
34
35 #include "MEM_guardedalloc.h"
36 #include "PIL_time.h"
37
38 #include "BLO_sys_types.h" // for intptr_t support
39
40 #include "DNA_mesh_types.h"
41 #include "DNA_material_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_modifier_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_scene_types.h"
46 #include "DNA_screen_types.h"
47 #include "DNA_view3d_types.h"
48 #include "DNA_key_types.h"
49
50 #include "RNA_types.h"
51 #include "RNA_define.h"
52 #include "RNA_access.h"
53
54 #include "BLI_utildefines.h"
55 #include "BLI_blenlib.h"
56 #include "BLI_math.h"
57 #include "BLI_editVert.h"
58 #include "BLI_rand.h"
59 #include "BLI_ghash.h"
60 #include "BLI_linklist.h"
61 #include "BLI_heap.h"
62 #include "BLI_array.h"
63 #include "BLI_kdopbvh.h"
64 #include "BLI_smallhash.h"
65
66 #include "BKE_DerivedMesh.h"
67 #include "BKE_context.h"
68 #include "BKE_customdata.h"
69 #include "BKE_depsgraph.h"
70 #include "BKE_global.h"
71 #include "BKE_library.h"
72 #include "BKE_mesh.h"
73 #include "BKE_object.h"
74 #include "BKE_bmesh.h"
75 #include "BKE_report.h"
76 #include "BKE_tessmesh.h"
77
78 #include "BIF_gl.h"
79 #include "BIF_glutil.h"
80
81 #include "WM_api.h"
82 #include "WM_types.h"
83
84 #include "ED_mesh.h"
85 #include "ED_view3d.h"
86 #include "ED_util.h"
87 #include "ED_screen.h"
88 #include "ED_transform.h"
89
90 #include "UI_interface.h"
91
92 #include "mesh_intern.h"
93 #include "bmesh.h"
94
95 #include "editbmesh_bvh.h"
96
97 typedef struct BMBVHTree {
98         BMEditMesh *em;
99         BMesh *bm;
100         BVHTree *tree;
101         float epsilon;
102         float maxdist; //for nearest point search
103         float uv[2];
104         
105         /*stuff for topological vert search*/
106         BMVert *v, *curv;
107         GHash *gh;
108         float curw, curd;
109         float co[3], (*cagecos)[3], (*cos)[3];
110         int curtag, flag;
111         
112         Object *ob;
113         Scene *scene;
114 } BMBVHTree;
115
116 static void cage_mapped_verts_callback(void *userData, int index, float *co, 
117         float *UNUSED(no_f), short *UNUSED(no_s))
118 {
119         void **data = userData;
120         BMEditMesh *em = data[0];
121         float (*cagecos)[3] = data[1];
122         SmallHash *hash = data[2];
123         
124         if (index >= 0 && index < em->bm->totvert && !BLI_smallhash_haskey(hash, index)) {
125                 BLI_smallhash_insert(hash, index, NULL);
126                 copy_v3_v3(cagecos[index], co);
127         }
128 }
129
130 BMBVHTree *BMBVH_NewBVH(BMEditMesh *em, int flag, Scene *scene, Object *obedit)
131 {
132         BMBVHTree *tree = MEM_callocN(sizeof(*tree), "BMBVHTree");
133         DerivedMesh *cage, *final;
134         SmallHash shash;
135         float cos[3][3], (*cagecos)[3] = NULL;
136         int i;
137
138         /*when initializing cage verts, we only want the first cage coordinate for each vertex,
139           so that e.g. mirror or array use original vertex coordiantes and not mirrored or duplicate*/
140         BLI_smallhash_init(&shash);
141         
142         BMEdit_RecalcTesselation(em);
143
144         tree->ob = obedit;
145         tree->scene = scene;
146         tree->em = em;
147         tree->bm = em->bm;
148         tree->epsilon = FLT_EPSILON*2.0f;
149         tree->flag = flag;
150         
151         tree->tree = BLI_bvhtree_new(em->tottri, tree->epsilon, 8, 8);
152         
153         if (flag & BMBVH_USE_CAGE) {
154                 BMIter iter;
155                 BMVert *v;
156                 void *data[3];
157                 
158                 tree->cos = MEM_callocN(sizeof(float)*3*em->bm->totvert, "bmbvh cos");
159                 BM_ITER_INDEX(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL, i) {
160                         BM_SetIndex(v, i); /* set_inline */
161                         copy_v3_v3(tree->cos[i], v->co);
162                 }
163                 em->bm->elem_index_dirty &= ~BM_VERT;
164
165
166                 cage = editbmesh_get_derived_cage_and_final(scene, obedit, em, &final, CD_MASK_DERIVEDMESH);
167                 cagecos = MEM_callocN(sizeof(float)*3*em->bm->totvert, "bmbvh cagecos");
168                 
169                 data[0] = em;
170                 data[1] = cagecos;
171                 data[2] = &shash;
172                 
173                 cage->foreachMappedVert(cage, cage_mapped_verts_callback, data);
174         }
175         
176         tree->cagecos = cagecos;
177         
178         for (i=0; i<em->tottri; i++) {
179                 if (flag & BMBVH_USE_CAGE) {
180                         copy_v3_v3(cos[0], cagecos[BM_GetIndex(em->looptris[i][0]->v)]);
181                         copy_v3_v3(cos[1], cagecos[BM_GetIndex(em->looptris[i][1]->v)]);
182                         copy_v3_v3(cos[2], cagecos[BM_GetIndex(em->looptris[i][2]->v)]);
183                 } else {
184                         copy_v3_v3(cos[0], em->looptris[i][0]->v->co);
185                         copy_v3_v3(cos[1], em->looptris[i][1]->v->co);
186                         copy_v3_v3(cos[2], em->looptris[i][2]->v->co);
187                 }
188
189                 BLI_bvhtree_insert(tree->tree, i, (float*)cos, 3);
190         }
191         
192         BLI_bvhtree_balance(tree->tree);
193         BLI_smallhash_release(&shash);
194         
195         return tree;
196 }
197
198 void BMBVH_FreeBVH(BMBVHTree *tree)
199 {
200         BLI_bvhtree_free(tree->tree);
201         
202         if (tree->cagecos)
203                 MEM_freeN(tree->cagecos);
204         if (tree->cos)
205                 MEM_freeN(tree->cos);
206         
207         MEM_freeN(tree);
208 }
209
210 /*taken from bvhutils.c*/
211 static float ray_tri_intersection(const BVHTreeRay *ray, const float UNUSED(m_dist), float *v0, 
212                                   float *v1, float *v2, float *uv, float UNUSED(e))
213 {
214         float dist;
215
216         if(isect_ray_tri_v3((float*)ray->origin, (float*)ray->direction, v0, v1, v2, &dist, uv))
217                 return dist;
218
219         return FLT_MAX;
220 }
221
222 static void raycallback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
223 {
224         BMBVHTree *tree = userdata;
225         BMLoop **ls = tree->em->looptris[index];
226         float dist, uv[2];
227          
228         if (!ls[0] || !ls[1] || !ls[2])
229                 return;
230         
231         dist = ray_tri_intersection(ray, hit->dist, ls[0]->v->co, ls[1]->v->co,
232                                     ls[2]->v->co, uv, tree->epsilon);
233         if (dist < hit->dist) {
234                 hit->dist = dist;
235                 hit->index = index;
236                 
237                 copy_v3_v3(hit->no, ls[0]->v->no);
238
239                 copy_v3_v3(hit->co, ray->direction);
240                 normalize_v3(hit->co);
241                 mul_v3_fl(hit->co, dist);
242                 add_v3_v3(hit->co, ray->origin);
243                 
244                 copy_v2_v2(tree->uv, uv);
245         }
246 }
247
248 BMFace *BMBVH_RayCast(BMBVHTree *tree, float *co, float *dir, float *hitout, float *cagehit)
249 {
250         BVHTreeRayHit hit;
251
252         hit.dist = FLT_MAX;
253         hit.index = -1;
254         
255         tree->uv[0] = tree->uv[1] = 0.0f;
256         
257         BLI_bvhtree_ray_cast(tree->tree, co, dir, 0.0f, &hit, raycallback, tree);
258         if (hit.dist != FLT_MAX && hit.index != -1) {
259                 if (hitout) {
260                         if (tree->flag & BMBVH_RETURN_ORIG) {
261                                 BMVert *v1, *v2, *v3;
262                                 float co[3];
263                                 int i;
264                                 
265                                 v1 = tree->em->looptris[hit.index][0]->v;
266                                 v2 = tree->em->looptris[hit.index][1]->v;
267                                 v3 = tree->em->looptris[hit.index][2]->v;
268                                 
269                                 for (i=0; i<3; i++) {
270                                         co[i] = v1->co[i] + (v2->co[i] - v1->co[i])*tree->uv[0] + (v3->co[i]-v1->co[i])*tree->uv[1];
271                                 }
272                                 copy_v3_v3(hitout, co);
273                         } else {
274                                 copy_v3_v3(hitout, hit.co);
275                         }
276
277                         if (cagehit)
278                                 copy_v3_v3(cagehit, hit.co);
279                 }
280
281                 return tree->em->looptris[hit.index][0]->f;
282         }
283
284         return NULL;
285 }
286
287 BVHTree *BMBVH_BVHTree(BMBVHTree *tree)
288 {
289         return tree->tree;
290 }
291
292 static void vertsearchcallback(void *userdata, int index, const float *UNUSED(co), BVHTreeNearest *hit)
293 {
294         BMBVHTree *tree = userdata;
295         BMLoop **ls = tree->em->looptris[index];
296         float dist, maxdist, v[3];
297         int i;
298
299         maxdist = tree->maxdist;
300
301         for (i=0; i<3; i++) {
302                 sub_v3_v3v3(v, hit->co, ls[i]->v->co);
303
304                 dist = sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
305                 if (dist < hit->dist && dist < maxdist) {
306                         copy_v3_v3(hit->co, ls[i]->v->co);
307                         copy_v3_v3(hit->no, ls[i]->v->no);
308                         hit->dist = dist;
309                         hit->index = index;
310                 }
311         }
312 }
313
314 BMVert *BMBVH_FindClosestVert(BMBVHTree *tree, float *co, float maxdist)
315 {
316         BVHTreeNearest hit;
317
318         copy_v3_v3(hit.co, co);
319         hit.dist = maxdist*5;
320         hit.index = -1;
321
322         tree->maxdist = maxdist;
323
324         BLI_bvhtree_find_nearest(tree->tree, co, &hit, vertsearchcallback, tree);
325         if (hit.dist != FLT_MAX && hit.index != -1) {
326                 BMLoop **ls = tree->em->looptris[hit.index];
327                 float dist, curdist = tree->maxdist, v[3];
328                 int cur=0, i;
329
330                 maxdist = tree->maxdist;
331
332                 for (i=0; i<3; i++) {
333                         sub_v3_v3v3(v, hit.co, ls[i]->v->co);
334
335                         dist = sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
336                         if (dist < curdist) {
337                                 cur = i;
338                                 curdist = dist;
339                         }
340                 }
341
342                 return ls[cur]->v;
343         }
344
345         return NULL;
346 }
347
348 typedef struct walklist {
349         BMVert *v;
350         int valence;
351         int depth;
352         float w, r;
353         int totwalked;
354
355         /*state data*/
356         BMVert *lastv;
357         BMLoop *curl, *firstl;
358         BMEdge *cure;
359 } walklist;
360
361 /* UNUSED */
362 #if 0
363 static short winding(float *v1, float *v2, float *v3)
364 /* is v3 to the right of v1-v2 ? With exception: v3==v1 || v3==v2 */
365 {
366         double inp;
367
368         //inp= (v2[cox]-v1[cox])*(v1[coy]-v3[coy]) +(v1[coy]-v2[coy])*(v1[cox]-v3[cox]);
369         inp= (v2[0]-v1[0])*(v1[1]-v3[1]) +(v1[1]-v2[1])*(v1[0]-v3[0]);
370
371         if(inp<0.0) return 0;
372         else if(inp==0) {
373                 if(v1[0]==v3[0] && v1[1]==v3[1]) return 0;
374                 if(v2[0]==v3[0] && v2[1]==v3[1]) return 0;
375         }
376         return 1;
377 }
378 #endif
379
380 #if 0 //BMESH_TODO: not implemented yet
381 int BMBVH_VertVisible(BMBVHTree *tree, BMEdge *e, RegionView3D *r3d)
382 {
383
384 }
385 #endif
386
387 static BMFace *edge_ray_cast(BMBVHTree *tree, float *co, float *dir, float *hitout, BMEdge *e)
388 {
389         BMFace *f = BMBVH_RayCast(tree, co, dir, hitout, NULL);
390         
391         if (f && BM_Edge_In_Face(f, e))
392                 return NULL;
393
394         return f;
395 }
396
397 static void scale_point(float *c1, float *p, float s)
398 {
399         sub_v3_v3(c1, p);
400         mul_v3_fl(c1, s);
401         add_v3_v3(c1, p);
402 }
403
404
405 int BMBVH_EdgeVisible(BMBVHTree *tree, BMEdge *e, ARegion *ar, View3D *v3d, Object *obedit)
406 {
407         BMFace *f;
408         float co1[3], co2[3], co3[3], dir1[4], dir2[4], dir3[4];
409         float origin[3], invmat[4][4];
410         float epsilon = 0.01f; 
411         float mval_f[2], end[3];
412         
413         if (!ar) {
414                 printf("error in BMBVH_EdgeVisible!\n");
415                 return 0;
416         }
417         
418         mval_f[0] = ar->winx/2.0;
419         mval_f[1] = ar->winy/2.0;
420         ED_view3d_win_to_segment_clip(ar, v3d, mval_f, origin, end);
421         
422         invert_m4_m4(invmat, obedit->obmat);
423         mul_m4_v3(invmat, origin);
424
425         copy_v3_v3(co1, e->v1->co);
426         add_v3_v3v3(co2, e->v1->co, e->v2->co);
427         mul_v3_fl(co2, 0.5f);
428         copy_v3_v3(co3, e->v2->co);
429         
430         scale_point(co1, co2, 0.99);
431         scale_point(co3, co2, 0.99);
432         
433         /*ok, idea is to generate rays going from the camera origin to the 
434           three points on the edge (v1, mid, v2)*/
435         sub_v3_v3v3(dir1, origin, co1);
436         sub_v3_v3v3(dir2, origin, co2);
437         sub_v3_v3v3(dir3, origin, co3);
438         
439         normalize_v3(dir1);
440         normalize_v3(dir2);
441         normalize_v3(dir3);
442
443         mul_v3_fl(dir1, epsilon);
444         mul_v3_fl(dir2, epsilon);
445         mul_v3_fl(dir3, epsilon);
446         
447         /*offset coordinates slightly along view vectors, to avoid
448           hitting the faces that own the edge.*/
449         add_v3_v3v3(co1, co1, dir1);
450         add_v3_v3v3(co2, co2, dir2);
451         add_v3_v3v3(co3, co3, dir3);
452
453         normalize_v3(dir1);
454         normalize_v3(dir2);
455         normalize_v3(dir3);
456
457         /*do three samplings: left, middle, right*/
458         f = edge_ray_cast(tree, co1, dir1, NULL, e);
459         if (f && !edge_ray_cast(tree, co2, dir2, NULL, e))
460                 return 1;
461         else if (f && !edge_ray_cast(tree, co3, dir3, NULL, e))
462                 return 1;
463         else if (!f)
464                 return 1;
465
466         return 0;
467 }