this someone didn't get committed
[blender.git] / source / blender / editors / mesh / editbmesh_bvh.c
1  /* $Id:
2  *
3  * ***** BEGIN GPL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18  *
19  * The Original Code is Copyright (C) 2004 by Blender Foundation.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): Joseph Eagar
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28 #include <stdlib.h>
29 #include <stdarg.h>
30 #include <string.h>
31 #include <math.h>
32 #include <float.h>
33
34 #include "MEM_guardedalloc.h"
35 #include "PIL_time.h"
36
37 #include "BLO_sys_types.h" // for intptr_t support
38
39 #include "DNA_mesh_types.h"
40 #include "DNA_material_types.h"
41 #include "DNA_meshdata_types.h"
42 #include "DNA_modifier_types.h"
43 #include "DNA_object_types.h"
44 #include "DNA_scene_types.h"
45 #include "DNA_screen_types.h"
46 #include "DNA_view3d_types.h"
47 #include "DNA_key_types.h"
48 #include "DNA_windowmanager_types.h"
49
50 #include "RNA_types.h"
51 #include "RNA_define.h"
52 #include "RNA_access.h"
53
54 #include "BLI_blenlib.h"
55 #include "BLI_math.h"
56 #include "BLI_editVert.h"
57 #include "BLI_rand.h"
58 #include "BLI_ghash.h"
59 #include "BLI_linklist.h"
60 #include "BLI_heap.h"
61 #include "BLI_array.h"
62 #include "BLI_kdopbvh.h"
63
64 #include "BKE_context.h"
65 #include "BKE_customdata.h"
66 #include "BKE_depsgraph.h"
67 #include "BKE_global.h"
68 #include "BKE_library.h"
69 #include "BKE_mesh.h"
70 #include "BKE_object.h"
71 #include "BKE_utildefines.h"
72 #include "BKE_bmesh.h"
73 #include "BKE_report.h"
74 #include "BKE_tessmesh.h"
75
76 #include "BIF_gl.h"
77 #include "BIF_glutil.h"
78
79 #include "WM_api.h"
80 #include "WM_types.h"
81
82 #include "ED_mesh.h"
83 #include "ED_view3d.h"
84 #include "ED_util.h"
85 #include "ED_screen.h"
86 #include "ED_transform.h"
87
88 #include "UI_interface.h"
89
90 #include "mesh_intern.h"
91 #include "bmesh.h"
92
93 #define IN_EDITMESHBVH
94 #include "editbmesh_bvh.h"
95
96 typedef struct BMBVHTree {
97         BMEditMesh *em;
98         BMesh *bm;
99         BVHTree *tree;
100         float epsilon;
101 } BMBVHTree;
102
103 BMBVHTree *BMBVH_NewBVH(BMEditMesh *em)
104 {
105         BMBVHTree *tree = MEM_callocN(sizeof(*tree), "BMBVHTree");
106         float cos[3][3];
107         int i;
108
109         BMEdit_RecalcTesselation(em);
110
111         tree->em = em;
112         tree->bm = em->bm;
113         tree->epsilon = FLT_EPSILON*2.0f;
114
115         tree->tree = BLI_bvhtree_new(em->tottri, tree->epsilon, 8, 8);
116
117         for (i=0; i<em->tottri; i++) {
118                 VECCOPY(cos[0], em->looptris[i][0]->v->co);
119                 VECCOPY(cos[1], em->looptris[i][1]->v->co);
120                 VECCOPY(cos[2], em->looptris[i][2]->v->co);
121
122                 BLI_bvhtree_insert(tree->tree, i, (float*)cos, 3);
123         }
124         
125         BLI_bvhtree_balance(tree->tree);
126         
127         return tree;
128 }
129
130 void BMBVH_FreeBVH(BMBVHTree *tree)
131 {
132         BLI_bvhtree_free(tree->tree);
133         MEM_freeN(tree);
134 }
135
136 /*taken from bvhutils.c*/
137 static float ray_tri_intersection(const BVHTreeRay *ray, const float m_dist, float *v0, 
138                                   float *v1, float *v2, float *uv, float e)
139 {
140         float dist;
141 #if 0
142         float vv1[3], vv2[3], vv3[3], cent[3];
143
144         /*expand triangle by an epsilon.  this is probably a really stupid
145           way of doing it, but I'm too tired to do better work.*/
146         VECCOPY(vv1, v0);
147         VECCOPY(vv2, v1);
148         VECCOPY(vv3, v2);
149
150         add_v3_v3v3(cent, vv1, vv2);
151         add_v3_v3v3(cent, cent, vv3);
152         mul_v3_fl(cent, 1.0f/3.0f);
153
154         sub_v3_v3v3(vv1, vv1, cent);
155         sub_v3_v3v3(vv2, vv2, cent);
156         sub_v3_v3v3(vv3, vv3, cent);
157
158         mul_v3_fl(vv1, 1.0f + e);
159         mul_v3_fl(vv2, 1.0f + e);
160         mul_v3_fl(vv3, 1.0f + e);
161
162         add_v3_v3v3(vv1, vv1, cent);
163         add_v3_v3v3(vv2, vv2, cent);
164         add_v3_v3v3(vv3, vv3, cent);
165
166         if(isect_ray_tri_v3((float*)ray->origin, (float*)ray->direction, vv1, vv2, vv3, &dist, uv))
167                 return dist;
168 #else
169         if(isect_ray_tri_v3((float*)ray->origin, (float*)ray->direction, v0, v1, v2, &dist, uv))
170                 return dist;
171 #endif
172
173         return FLT_MAX;
174 }
175
176 static void raycallback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
177 {
178         BMBVHTree *tree = userdata;
179         BMLoop **ls = tree->em->looptris[index];
180         float dist, uv[2], co1[3], co2[3], co3[3];
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                 VECCOPY(hit->no, ls[0]->v->no);
189
190                 VECCOPY(co1, ls[0]->v->co);
191                 VECCOPY(co2, ls[1]->v->co);
192                 VECCOPY(co3, ls[2]->v->co);
193
194                 mul_v3_fl(co1, uv[0]);
195                 mul_v3_fl(co2, uv[1]);
196                 mul_v3_fl(co3, 1.0f-uv[0]-uv[1]);
197
198                 add_v3_v3v3(hit->co, co1, co2);
199                 add_v3_v3v3(hit->co, hit->co, co3);
200         }
201 }
202
203 BMFace *BMBVH_RayCast(BMBVHTree *tree, float *co, float *dir, float *hitout)
204 {
205         BVHTreeRayHit hit;
206
207         hit.dist = FLT_MAX;
208         hit.index = -1;
209
210         BLI_bvhtree_ray_cast(tree->tree, co, dir, FLT_MAX, &hit, raycallback, tree);
211         if (hit.dist != FLT_MAX && hit.index != -1) {
212                 if (hitout) {
213                         VECCOPY(hitout, hit.co);
214                 }
215
216                 return tree->em->looptris[hit.index][0]->f;
217         }
218
219         return NULL;
220 }
221
222 #if 0 //BMESH_TODO: not implemented yet
223 int BMBVH_VertVisible(BMBVHTree *tree, BMEdge *e, RegionView3D *r3d)
224 {
225
226 }
227 #endif
228
229 static BMFace *edge_ray_cast(BMBVHTree *tree, float *co, float *dir, float *hitout, BMEdge *e)
230 {
231         BMFace *f = BMBVH_RayCast(tree, co, dir, hitout);
232         
233         if (f && BM_Edge_In_Face(f, e))
234                 return NULL;
235
236         return f;
237 }
238
239 int BMBVH_EdgeVisible(BMBVHTree *tree, BMEdge *e, RegionView3D *r3d, Object *obedit)
240 {
241         BMFace *f;
242         float co1[3], co2[3], co3[3], dir1[4], dir2[4], dir3[4];
243         float origin[3], invmat[4][4];
244         float epsilon = 0.01f; 
245         
246         VECCOPY(origin, r3d->viewinv[3]);
247         invert_m4_m4(invmat, obedit->obmat);
248         mul_m4_v3(invmat, origin);
249
250         VECCOPY(co1, e->v1->co);
251         add_v3_v3v3(co2, e->v1->co, e->v2->co);
252         mul_v3_fl(co2, 0.5f);
253         VECCOPY(co3, e->v2->co);
254         
255         /*ok, idea is to generate rays going from the camera origin to the 
256           three points on the edge (v1, mid, v2)*/
257         sub_v3_v3v3(dir1, origin, co1);
258         sub_v3_v3v3(dir2, origin, co2);
259         sub_v3_v3v3(dir3, origin, co3);
260         
261         normalize_v3(dir1);
262         normalize_v3(dir2);
263         normalize_v3(dir3);
264
265         mul_v3_fl(dir1, epsilon);
266         mul_v3_fl(dir2, epsilon);
267         mul_v3_fl(dir3, epsilon);
268         
269         /*offset coordinates slightly along view vectors, to avoid
270           hitting the faces that own the edge.*/
271         add_v3_v3v3(co1, co1, dir1);
272         add_v3_v3v3(co2, co2, dir2);
273         add_v3_v3v3(co3, co3, dir3);
274
275         normalize_v3(dir1);
276         normalize_v3(dir2);
277         normalize_v3(dir3);
278
279         /*do three samplings: left, middle, right*/
280         f = edge_ray_cast(tree, co1, dir1, NULL, e);
281         if (f && !edge_ray_cast(tree, co2, dir2, NULL, e))
282                 return 1;
283         else if (f && !edge_ray_cast(tree, co3, dir3, NULL, e))
284                 return 1;
285         else if (!f)
286                 return 1;
287
288         return 0;
289 }