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