style cleanup: follow style guide for formatting of if/for/while loops, and else...
[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                 }
140                 else {
141                         copy_v3_v3(cos[0], em->looptris[i][0]->v->co);
142                         copy_v3_v3(cos[1], em->looptris[i][1]->v->co);
143                         copy_v3_v3(cos[2], em->looptris[i][2]->v->co);
144                 }
145
146                 BLI_bvhtree_insert(tree->tree, i, (float *)cos, 3);
147         }
148         
149         BLI_bvhtree_balance(tree->tree);
150         BLI_smallhash_release(&shash);
151         
152         return tree;
153 }
154
155 void BMBVH_FreeBVH(BMBVHTree *tree)
156 {
157         BLI_bvhtree_free(tree->tree);
158         
159         if (tree->cagecos)
160                 MEM_freeN(tree->cagecos);
161         if (tree->cos)
162                 MEM_freeN(tree->cos);
163         
164         MEM_freeN(tree);
165 }
166
167 /* taken from bvhutils.c */
168 static float ray_tri_intersection(const BVHTreeRay *ray, const float UNUSED(m_dist), float *v0, 
169                                   float *v1, float *v2, float *uv, float UNUSED(e))
170 {
171         float dist;
172
173         if (isect_ray_tri_v3((float *)ray->origin, (float *)ray->direction, v0, v1, v2, &dist, uv)) {
174                 return dist;
175         }
176
177         return FLT_MAX;
178 }
179
180 static void raycallback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
181 {
182         BMBVHTree *tree = userdata;
183         BMLoop **ls = tree->em->looptris[index];
184         float dist, uv[2];
185          
186         if (!ls[0] || !ls[1] || !ls[2])
187                 return;
188         
189         dist = ray_tri_intersection(ray, hit->dist, ls[0]->v->co, ls[1]->v->co,
190                                     ls[2]->v->co, uv, tree->epsilon);
191         if (dist < hit->dist) {
192                 hit->dist = dist;
193                 hit->index = index;
194                 
195                 copy_v3_v3(hit->no, ls[0]->v->no);
196
197                 copy_v3_v3(hit->co, ray->direction);
198                 normalize_v3(hit->co);
199                 mul_v3_fl(hit->co, dist);
200                 add_v3_v3(hit->co, ray->origin);
201                 
202                 copy_v2_v2(tree->uv, uv);
203         }
204 }
205
206 BMFace *BMBVH_RayCast(BMBVHTree *tree, float *co, float *dir, float *hitout, float *cagehit)
207 {
208         BVHTreeRayHit hit;
209
210         hit.dist = FLT_MAX;
211         hit.index = -1;
212         
213         tree->uv[0] = tree->uv[1] = 0.0f;
214         
215         BLI_bvhtree_ray_cast(tree->tree, co, dir, 0.0f, &hit, raycallback, tree);
216         if (hit.dist != FLT_MAX && hit.index != -1) {
217                 if (hitout) {
218                         if (tree->flag & BMBVH_RETURN_ORIG) {
219                                 BMVert *v1, *v2, *v3;
220                                 float co[3];
221                                 int i;
222                                 
223                                 v1 = tree->em->looptris[hit.index][0]->v;
224                                 v2 = tree->em->looptris[hit.index][1]->v;
225                                 v3 = tree->em->looptris[hit.index][2]->v;
226                                 
227                                 for (i = 0; i < 3; i++) {
228                                         co[i] = v1->co[i] + ((v2->co[i] - v1->co[i]) * tree->uv[0]) +
229                                                             ((v3->co[i] - v1->co[i]) * tree->uv[1]);
230                                 }
231                                 copy_v3_v3(hitout, co);
232                         }
233                         else {
234                                 copy_v3_v3(hitout, hit.co);
235                         }
236
237                         if (cagehit)
238                                 copy_v3_v3(cagehit, hit.co);
239                 }
240
241                 return tree->em->looptris[hit.index][0]->f;
242         }
243
244         return NULL;
245 }
246
247 BVHTree *BMBVH_BVHTree(BMBVHTree *tree)
248 {
249         return tree->tree;
250 }
251
252 static void vertsearchcallback(void *userdata, int index, const float *UNUSED(co), BVHTreeNearest *hit)
253 {
254         BMBVHTree *tree = userdata;
255         BMLoop **ls = tree->em->looptris[index];
256         float dist, maxdist, v[3];
257         int i;
258
259         maxdist = tree->maxdist;
260
261         for (i = 0; i < 3; i++) {
262                 sub_v3_v3v3(v, hit->co, ls[i]->v->co);
263
264                 dist = len_v3(v);
265                 if (dist < hit->dist && dist < maxdist) {
266                         copy_v3_v3(hit->co, ls[i]->v->co);
267                         copy_v3_v3(hit->no, ls[i]->v->no);
268                         hit->dist = dist;
269                         hit->index = index;
270                 }
271         }
272 }
273
274 BMVert *BMBVH_FindClosestVert(BMBVHTree *tree, float *co, float maxdist)
275 {
276         BVHTreeNearest hit;
277
278         copy_v3_v3(hit.co, co);
279         hit.dist = maxdist * 5;
280         hit.index = -1;
281
282         tree->maxdist = maxdist;
283
284         BLI_bvhtree_find_nearest(tree->tree, co, &hit, vertsearchcallback, tree);
285         if (hit.dist != FLT_MAX && hit.index != -1) {
286                 BMLoop **ls = tree->em->looptris[hit.index];
287                 float dist, curdist = tree->maxdist, v[3];
288                 int cur = 0, i;
289
290                 maxdist = tree->maxdist;
291
292                 for (i = 0; i < 3; i++) {
293                         sub_v3_v3v3(v, hit.co, ls[i]->v->co);
294
295                         dist = len_v3(v);
296                         if (dist < curdist) {
297                                 cur = i;
298                                 curdist = dist;
299                         }
300                 }
301
302                 return ls[cur]->v;
303         }
304
305         return NULL;
306 }
307
308 typedef struct walklist {
309         BMVert *v;
310         int valence;
311         int depth;
312         float w, r;
313         int totwalked;
314
315         /* state data */
316         BMVert *lastv;
317         BMLoop *curl, *firstl;
318         BMEdge *cure;
319 } walklist;
320
321 /* UNUSED */
322 #if 0
323 static short winding(float *v1, float *v2, float *v3)
324 /* is v3 to the right of (v1 - v2) ? With exception: v3 == v1 || v3 == v2 */
325 {
326         double inp;
327
328         //inp = (v2[cox] - v1[cox]) * (v1[coy] - v3[coy]) + (v1[coy] - v2[coy]) * (v1[cox] - v3[cox]);
329         inp = (v2[0] - v1[0]) * (v1[1] - v3[1]) + (v1[1] - v2[1]) * (v1[0] - v3[0]);
330
331         if (inp < 0.0) {
332                 return 0;
333         }
334         else if (inp == 0) {
335                 if (v1[0] == v3[0] && v1[1] == v3[1]) return 0;
336                 if (v2[0] == v3[0] && v2[1] == v3[1]) return 0;
337         }
338         return 1;
339 }
340 #endif
341
342 #if 0 //BMESH_TODO: not implemented yet
343 int BMBVH_VertVisible(BMBVHTree *tree, BMEdge *e, RegionView3D *r3d)
344 {
345
346 }
347 #endif
348
349 static BMFace *edge_ray_cast(BMBVHTree *tree, float *co, float *dir, float *hitout, BMEdge *e)
350 {
351         BMFace *f = BMBVH_RayCast(tree, co, dir, hitout, NULL);
352         
353         if (f && BM_edge_in_face(f, e))
354                 return NULL;
355
356         return f;
357 }
358
359 static void scale_point(float *c1, float *p, float s)
360 {
361         sub_v3_v3(c1, p);
362         mul_v3_fl(c1, s);
363         add_v3_v3(c1, p);
364 }
365
366
367 int BMBVH_EdgeVisible(BMBVHTree *tree, BMEdge *e, ARegion *ar, View3D *v3d, Object *obedit)
368 {
369         BMFace *f;
370         float co1[3], co2[3], co3[3], dir1[4], dir2[4], dir3[4];
371         float origin[3], invmat[4][4];
372         float epsilon = 0.01f; 
373         float mval_f[2], end[3];
374         
375         if (!ar) {
376                 printf("error in BMBVH_EdgeVisible!\n");
377                 return 0;
378         }
379         
380         mval_f[0] = ar->winx / 2.0f;
381         mval_f[1] = ar->winy / 2.0f;
382         ED_view3d_win_to_segment_clip(ar, v3d, mval_f, origin, end);
383         
384         invert_m4_m4(invmat, obedit->obmat);
385         mul_m4_v3(invmat, origin);
386
387         copy_v3_v3(co1, e->v1->co);
388         add_v3_v3v3(co2, e->v1->co, e->v2->co);
389         mul_v3_fl(co2, 0.5f);
390         copy_v3_v3(co3, e->v2->co);
391         
392         scale_point(co1, co2, 0.99);
393         scale_point(co3, co2, 0.99);
394         
395         /* ok, idea is to generate rays going from the camera origin to the 
396          * three points on the edge (v1, mid, v2)*/
397         sub_v3_v3v3(dir1, origin, co1);
398         sub_v3_v3v3(dir2, origin, co2);
399         sub_v3_v3v3(dir3, origin, co3);
400         
401         normalize_v3(dir1);
402         normalize_v3(dir2);
403         normalize_v3(dir3);
404
405         mul_v3_fl(dir1, epsilon);
406         mul_v3_fl(dir2, epsilon);
407         mul_v3_fl(dir3, epsilon);
408         
409         /* offset coordinates slightly along view vectors, to avoid
410          * hitting the faces that own the edge.*/
411         add_v3_v3v3(co1, co1, dir1);
412         add_v3_v3v3(co2, co2, dir2);
413         add_v3_v3v3(co3, co3, dir3);
414
415         normalize_v3(dir1);
416         normalize_v3(dir2);
417         normalize_v3(dir3);
418
419         /* do three samplings: left, middle, right */
420         f = edge_ray_cast(tree, co1, dir1, NULL, e);
421         if (f && !edge_ray_cast(tree, co2, dir2, NULL, e))
422                 return 1;
423         else if (f && !edge_ray_cast(tree, co3, dir3, NULL, e))
424                 return 1;
425         else if (!f)
426                 return 1;
427
428         return 0;
429 }