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