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