code cleanup: rename BKE_tessmesh -> BKE_editmesh, rename EditDerivedBMesh.tc ->...
[blender-staging.git] / source / blender / editors / mesh / editmesh_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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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
28 /** \file blender/editors/mesh/editmesh_bvh.c
29  *  \ingroup edmesh
30  */
31
32 #include "MEM_guardedalloc.h"
33
34 #include "DNA_scene_types.h"
35 #include "DNA_object_types.h"
36 #include "DNA_screen_types.h"
37 #include "DNA_view3d_types.h"
38
39 #include "BLI_math.h"
40 #include "BLI_smallhash.h"
41
42 #include "BKE_DerivedMesh.h"
43 #include "BKE_editmesh.h"
44
45 #include "ED_view3d.h"
46
47 #define IN_EDITMESHBVH     /* needed for typedef workaround */
48 #include "editmesh_bvh.h"  /* own include */
49
50
51 typedef struct BMBVHTree {
52         BMEditMesh *em;
53         BMesh *bm;
54         BVHTree *tree;
55         float epsilon;
56         float maxdist; /* for nearest point search */
57         float uv[2];
58         
59         /* stuff for topological vert search */
60         BMVert *v, *curv;
61         GHash *gh;
62         float curw, curd;
63         float co[3], (*cagecos)[3], (*cos)[3];
64         int curtag, flag;
65         
66         Object *ob;
67         Scene *scene;
68 } BMBVHTree;
69
70 static void cage_mapped_verts_callback(void *userData, int index, const float co[3],
71                                        const float UNUSED(no_f[3]), const short UNUSED(no_s[3]))
72 {
73         void **data = userData;
74         BMEditMesh *em = data[0];
75         float (*cagecos)[3] = data[1];
76         SmallHash *hash = data[2];
77         
78         if (index >= 0 && index < em->bm->totvert && !BLI_smallhash_haskey(hash, index)) {
79                 BLI_smallhash_insert(hash, index, NULL);
80                 copy_v3_v3(cagecos[index], co);
81         }
82 }
83
84 BMBVHTree *BMBVH_NewBVH(BMEditMesh *em, int flag, Scene *scene, Object *obedit)
85 {
86         BMBVHTree *tree = MEM_callocN(sizeof(*tree), "BMBVHTree");
87         DerivedMesh *cage, *final;
88         SmallHash shash;
89         float cos[3][3], (*cagecos)[3] = NULL;
90         int i;
91         int tottri;
92
93         /* when initializing cage verts, we only want the first cage coordinate for each vertex,
94          * so that e.g. mirror or array use original vertex coordinates and not mirrored or duplicate */
95         BLI_smallhash_init(&shash);
96         
97         BMEdit_RecalcTessellation(em);
98
99         tree->ob = obedit;
100         tree->scene = scene;
101         tree->em = em;
102         tree->bm = em->bm;
103         tree->epsilon = FLT_EPSILON * 2.0f;
104         tree->flag = flag;
105
106         if (flag & (BMBVH_RESPECT_SELECT)) {
107                 tottri = 0;
108                 for (i = 0; i < em->tottri; i++) {
109                         if (BM_elem_flag_test(em->looptris[i][0]->f, BM_ELEM_SELECT)) {
110                                 tottri++;
111                         }
112                 }
113         }
114         else if (flag & (BMBVH_RESPECT_HIDDEN)) {
115                 tottri = 0;
116                 for (i = 0; i < em->tottri; i++) {
117                         if (!BM_elem_flag_test(em->looptris[i][0]->f, BM_ELEM_HIDDEN)) {
118                                 tottri++;
119                         }
120                 }
121         }
122         else {
123                 tottri = em->tottri;
124         }
125
126         tree->tree = BLI_bvhtree_new(tottri, tree->epsilon, 8, 8);
127         
128         if (flag & BMBVH_USE_CAGE) {
129                 BMIter iter;
130                 BMVert *v;
131                 void *data[3];
132                 
133                 tree->cos = MEM_callocN(sizeof(float) * 3 * em->bm->totvert, "bmbvh cos");
134                 BM_ITER_MESH_INDEX (v, &iter, em->bm, BM_VERTS_OF_MESH, i) {
135                         BM_elem_index_set(v, i); /* set_inline */
136                         copy_v3_v3(tree->cos[i], v->co);
137                 }
138                 em->bm->elem_index_dirty &= ~BM_VERT;
139
140
141                 cage = editbmesh_get_derived_cage_and_final(scene, obedit, em, &final, CD_MASK_DERIVEDMESH);
142                 cagecos = MEM_callocN(sizeof(float) * 3 * em->bm->totvert, "bmbvh cagecos");
143                 
144                 data[0] = em;
145                 data[1] = cagecos;
146                 data[2] = &shash;
147                 
148                 cage->foreachMappedVert(cage, cage_mapped_verts_callback, data);
149         }
150         
151         tree->cagecos = cagecos;
152         
153         for (i = 0; i < em->tottri; i++) {
154
155
156                 if (flag & BMBVH_RESPECT_SELECT) {
157                         /* note, the arrays wont align now! take care */
158                         if (!BM_elem_flag_test(em->looptris[i][0]->f, BM_ELEM_SELECT)) {
159                                 continue;
160                         }
161                 }
162                 else if (flag & BMBVH_RESPECT_HIDDEN) {
163                         /* note, the arrays wont align now! take care */
164                         if (BM_elem_flag_test(em->looptris[i][0]->f, BM_ELEM_HIDDEN)) {
165                                 continue;
166                         }
167                 }
168
169                 if (flag & BMBVH_USE_CAGE) {
170                         copy_v3_v3(cos[0], cagecos[BM_elem_index_get(em->looptris[i][0]->v)]);
171                         copy_v3_v3(cos[1], cagecos[BM_elem_index_get(em->looptris[i][1]->v)]);
172                         copy_v3_v3(cos[2], cagecos[BM_elem_index_get(em->looptris[i][2]->v)]);
173                 }
174                 else {
175                         copy_v3_v3(cos[0], em->looptris[i][0]->v->co);
176                         copy_v3_v3(cos[1], em->looptris[i][1]->v->co);
177                         copy_v3_v3(cos[2], em->looptris[i][2]->v->co);
178                 }
179
180                 BLI_bvhtree_insert(tree->tree, i, (float *)cos, 3);
181         }
182         
183         BLI_bvhtree_balance(tree->tree);
184         BLI_smallhash_release(&shash);
185         
186         return tree;
187 }
188
189 void BMBVH_FreeBVH(BMBVHTree *tree)
190 {
191         BLI_bvhtree_free(tree->tree);
192         
193         if (tree->cagecos)
194                 MEM_freeN(tree->cagecos);
195         if (tree->cos)
196                 MEM_freeN(tree->cos);
197         
198         MEM_freeN(tree);
199 }
200
201 /* taken from bvhutils.c */
202 static float ray_tri_intersection(const BVHTreeRay *ray, const float UNUSED(m_dist),
203                                   const float v0[3],  const float v1[3], const float v2[3],
204                                   float r_uv[2], float UNUSED(e))
205 {
206         float dist;
207
208         if (isect_ray_tri_v3((float *)ray->origin, (float *)ray->direction, v0, v1, v2, &dist, r_uv)) {
209                 return dist;
210         }
211
212         return FLT_MAX;
213 }
214
215 static void raycallback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
216 {
217         BMBVHTree *tree = userdata;
218         BMLoop **ls = tree->em->looptris[index];
219         float dist, uv[2];
220          
221         if (!ls[0] || !ls[1] || !ls[2])
222                 return;
223         
224         dist = ray_tri_intersection(ray, hit->dist, ls[0]->v->co, ls[1]->v->co,
225                                     ls[2]->v->co, uv, tree->epsilon);
226         if (dist < hit->dist) {
227                 hit->dist = dist;
228                 hit->index = index;
229                 
230                 copy_v3_v3(hit->no, ls[0]->v->no);
231
232                 copy_v3_v3(hit->co, ray->direction);
233                 normalize_v3(hit->co);
234                 mul_v3_fl(hit->co, dist);
235                 add_v3_v3(hit->co, ray->origin);
236                 
237                 copy_v2_v2(tree->uv, uv);
238         }
239 }
240
241 BMFace *BMBVH_RayCast(BMBVHTree *tree, const float co[3], const float dir[3],
242                       float r_hitout[3], float r_cagehit[3])
243 {
244         BVHTreeRayHit hit;
245
246         hit.dist = FLT_MAX;
247         hit.index = -1;
248         
249         tree->uv[0] = tree->uv[1] = 0.0f;
250         
251         BLI_bvhtree_ray_cast(tree->tree, co, dir, 0.0f, &hit, raycallback, tree);
252         if (hit.dist != FLT_MAX && hit.index != -1) {
253                 if (r_hitout) {
254                         if (tree->flag & BMBVH_RETURN_ORIG) {
255                                 BMVert *v1, *v2, *v3;
256                                 int i;
257                                 
258                                 v1 = tree->em->looptris[hit.index][0]->v;
259                                 v2 = tree->em->looptris[hit.index][1]->v;
260                                 v3 = tree->em->looptris[hit.index][2]->v;
261                                 
262                                 for (i = 0; i < 3; i++) {
263                                         r_hitout[i] = v1->co[i] + ((v2->co[i] - v1->co[i]) * tree->uv[0]) +
264                                                                   ((v3->co[i] - v1->co[i]) * tree->uv[1]);
265                                 }
266                         }
267                         else {
268                                 copy_v3_v3(r_hitout, hit.co);
269                         }
270
271                         if (r_cagehit) {
272                                 copy_v3_v3(r_cagehit, hit.co);
273                         }
274                 }
275
276                 return tree->em->looptris[hit.index][0]->f;
277         }
278
279         return NULL;
280 }
281
282 BVHTree *BMBVH_BVHTree(BMBVHTree *tree)
283 {
284         return tree->tree;
285 }
286
287 static void vertsearchcallback(void *userdata, int index, const float *UNUSED(co), BVHTreeNearest *hit)
288 {
289         BMBVHTree *tree = userdata;
290         BMLoop **ls = tree->em->looptris[index];
291         float dist, maxdist, v[3];
292         int i;
293
294         maxdist = tree->maxdist;
295
296         for (i = 0; i < 3; i++) {
297                 sub_v3_v3v3(v, hit->co, ls[i]->v->co);
298
299                 dist = len_v3(v);
300                 if (dist < hit->dist && dist < maxdist) {
301                         copy_v3_v3(hit->co, ls[i]->v->co);
302                         copy_v3_v3(hit->no, ls[i]->v->no);
303                         hit->dist = dist;
304                         hit->index = index;
305                 }
306         }
307 }
308
309 BMVert *BMBVH_FindClosestVert(BMBVHTree *tree, const float co[3], const float maxdist)
310 {
311         BVHTreeNearest hit;
312
313         copy_v3_v3(hit.co, co);
314         hit.dist = maxdist * 5;
315         hit.index = -1;
316
317         tree->maxdist = maxdist;
318
319         BLI_bvhtree_find_nearest(tree->tree, co, &hit, vertsearchcallback, tree);
320         if (hit.dist != FLT_MAX && hit.index != -1) {
321                 BMLoop **ls = tree->em->looptris[hit.index];
322                 float dist, curdist = tree->maxdist, v[3];
323                 int cur = 0, i;
324
325                 /* maxdist = tree->maxdist; */  /* UNUSED */
326
327                 for (i = 0; i < 3; i++) {
328                         sub_v3_v3v3(v, hit.co, ls[i]->v->co);
329
330                         dist = len_v3(v);
331                         if (dist < curdist) {
332                                 cur = i;
333                                 curdist = dist;
334                         }
335                 }
336
337                 return ls[cur]->v;
338         }
339
340         return NULL;
341 }
342
343 /* UNUSED */
344 #if 0
345 static short winding(const float v1[3], const float v2[3], const float v3[3])
346 /* is v3 to the right of (v1 - v2) ? With exception: v3 == v1 || v3 == v2 */
347 {
348         double inp;
349
350         //inp = (v2[cox] - v1[cox]) * (v1[coy] - v3[coy]) + (v1[coy] - v2[coy]) * (v1[cox] - v3[cox]);
351         inp = (v2[0] - v1[0]) * (v1[1] - v3[1]) + (v1[1] - v2[1]) * (v1[0] - v3[0]);
352
353         if (inp < 0.0) {
354                 return 0;
355         }
356         else if (inp == 0) {
357                 if (v1[0] == v3[0] && v1[1] == v3[1]) return 0;
358                 if (v2[0] == v3[0] && v2[1] == v3[1]) return 0;
359         }
360         return 1;
361 }
362 #endif
363
364 #if 0 //BMESH_TODO: not implemented yet
365 int BMBVH_VertVisible(BMBVHTree *tree, BMEdge *e, RegionView3D *r3d)
366 {
367
368 }
369 #endif
370
371 static BMFace *edge_ray_cast(BMBVHTree *tree, const float co[3], const float dir[3], float *r_hitout, BMEdge *e)
372 {
373         BMFace *f = BMBVH_RayCast(tree, co, dir, r_hitout, NULL);
374         
375         if (f && BM_edge_in_face(f, e))
376                 return NULL;
377
378         return f;
379 }
380
381 static void scale_point(float c1[3], const float p[3], const float s)
382 {
383         sub_v3_v3(c1, p);
384         mul_v3_fl(c1, s);
385         add_v3_v3(c1, p);
386 }
387
388
389 int BMBVH_EdgeVisible(BMBVHTree *tree, BMEdge *e, ARegion *ar, View3D *v3d, Object *obedit)
390 {
391         BMFace *f;
392         float co1[3], co2[3], co3[3], dir1[3], dir2[3], dir3[3];
393         float origin[3], invmat[4][4];
394         float epsilon = 0.01f; 
395         float end[3];
396         const float mval_f[2] = {ar->winx / 2.0f,
397                                  ar->winy / 2.0f};
398
399         ED_view3d_win_to_segment(ar, v3d, mval_f, origin, end);
400         
401         invert_m4_m4(invmat, obedit->obmat);
402         mul_m4_v3(invmat, origin);
403
404         copy_v3_v3(co1, e->v1->co);
405         mid_v3_v3v3(co2, e->v1->co, e->v2->co);
406         copy_v3_v3(co3, e->v2->co);
407         
408         scale_point(co1, co2, 0.99);
409         scale_point(co3, co2, 0.99);
410         
411         /* ok, idea is to generate rays going from the camera origin to the 
412          * three points on the edge (v1, mid, v2)*/
413         sub_v3_v3v3(dir1, origin, co1);
414         sub_v3_v3v3(dir2, origin, co2);
415         sub_v3_v3v3(dir3, origin, co3);
416         
417         normalize_v3(dir1);
418         normalize_v3(dir2);
419         normalize_v3(dir3);
420
421         mul_v3_fl(dir1, epsilon);
422         mul_v3_fl(dir2, epsilon);
423         mul_v3_fl(dir3, epsilon);
424         
425         /* offset coordinates slightly along view vectors, to avoid
426          * hitting the faces that own the edge.*/
427         add_v3_v3v3(co1, co1, dir1);
428         add_v3_v3v3(co2, co2, dir2);
429         add_v3_v3v3(co3, co3, dir3);
430
431         normalize_v3(dir1);
432         normalize_v3(dir2);
433         normalize_v3(dir3);
434
435         /* do three samplings: left, middle, right */
436         f = edge_ray_cast(tree, co1, dir1, NULL, e);
437         if (f && !edge_ray_cast(tree, co2, dir2, NULL, e))
438                 return 1;
439         else if (f && !edge_ray_cast(tree, co3, dir3, NULL, e))
440                 return 1;
441         else if (!f)
442                 return 1;
443
444         return 0;
445 }