Line data Source code
1 : /*
2 : * GPAC - Multimedia Framework C SDK
3 : *
4 : * Authors: Jean Le Feuvre
5 : * Copyright (c) Telecom ParisTech 2000-2012
6 : * All rights reserved
7 : *
8 : * This file is part of GPAC / Scene Compositor sub-project
9 : *
10 : * GPAC is free software; you can redistribute it and/or modify
11 : * it under the terms of the GNU Lesser General Public License as published by
12 : * the Free Software Foundation; either version 2, or (at your option)
13 : * any later version.
14 : *
15 : * GPAC is distributed in the hope that it will be useful,
16 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 : * GNU Lesser General Public License for more details.
19 : *
20 : * You should have received a copy of the GNU Lesser General Public
21 : * License along with this library; see the file COPYING. If not, write to
22 : * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
23 : *
24 : */
25 :
26 :
27 : #include <gpac/internal/mesh.h>
28 :
29 : #ifndef GPAC_DISABLE_3D
30 :
31 : /*
32 : AABB tree syntax&construction code is a quick extract from OPCODE (c) Pierre Terdiman, http://www.codercorner.com/Opcode.htm
33 : */
34 :
35 : typedef struct
36 : {
37 : /*max tree depth, 0 is unlimited*/
38 : u32 max_depth;
39 : /*min triangles at node to split. 0 is full split (one triangle per leaf)*/
40 : u32 min_tri_limit;
41 : /*one of the above type*/
42 : u32 split_type;
43 : u32 depth, nb_nodes;
44 : } AABSplitParams;
45 :
46 :
47 :
48 100416 : static GFINLINE void update_node_bounds(GF_Mesh *mesh, AABBNode *node)
49 : {
50 : u32 i, j;
51 : Fixed mx, my, mz, Mx, My, Mz;
52 : mx = my = mz = FIX_MAX;
53 : Mx = My = Mz = FIX_MIN;
54 2428300 : for (i=0; i<node->nb_idx; i++) {
55 2428300 : IDX_TYPE *idx = &mesh->indices[3*node->indices[i]];
56 7284900 : for (j=0; j<3; j++) {
57 7284900 : SFVec3f *v = &mesh->vertices[idx[j]].pos;
58 7284900 : if (mx>v->x) mx=v->x;
59 7284900 : if (Mx<v->x) Mx=v->x;
60 7284900 : if (my>v->y) my=v->y;
61 7284900 : if (My<v->y) My=v->y;
62 7284900 : if (mz>v->z) mz=v->z;
63 7284900 : if (Mz<v->z) Mz=v->z;
64 : }
65 : }
66 100416 : node->min.x = mx;
67 100416 : node->min.y = my;
68 100416 : node->min.z = mz;
69 100416 : node->max.x = Mx;
70 100416 : node->max.y = My;
71 100416 : node->max.z = Mz;
72 100416 : }
73 :
74 : static GFINLINE u32 gf_vec_main_axis(SFVec3f v)
75 : {
76 : Fixed *vals = &v.x;
77 : u32 m = 0;
78 50305 : if(vals[1] > vals[m]) m = 1;
79 50305 : if(vals[2] > vals[m]) m = 2;
80 : return m;
81 : }
82 :
83 9718236 : static GFINLINE Fixed tri_get_center(GF_Mesh *mesh, u32 tri_idx, u32 axis)
84 : {
85 : SFVec3f v;
86 9718236 : IDX_TYPE *idx = &mesh->indices[3*tri_idx];
87 : /*compute center*/
88 9718236 : gf_vec_add(v, mesh->vertices[idx[0]].pos, mesh->vertices[idx[1]].pos);
89 9718236 : gf_vec_add(v, v, mesh->vertices[idx[2]].pos);
90 9718236 : v = gf_vec_scale(v, FIX_ONE/3);
91 9718236 : return ((Fixed *)&v.x)[axis];
92 : }
93 :
94 201220 : static GFINLINE u32 aabb_split(GF_Mesh *mesh, AABBNode *node, u32 axis)
95 : {
96 : SFVec3f v;
97 : Fixed split_at;
98 : u32 num_pos, i;
99 :
100 201220 : gf_vec_add(v, node->max, node->min);
101 201220 : v = gf_vec_scale(v, FIX_ONE/2);
102 :
103 201220 : split_at = ((Fixed *)&v.x)[axis];
104 :
105 : num_pos = 0;
106 :
107 9919456 : for (i=0; i<node->nb_idx; i++) {
108 9718236 : IDX_TYPE idx = node->indices[i];
109 9718236 : Fixed tri_val = tri_get_center(mesh, idx, axis);
110 :
111 9718236 : if (tri_val > split_at) {
112 : /*swap*/
113 5355095 : IDX_TYPE tmp_idx = node->indices[i];
114 5355095 : node->indices[i] = node->indices[num_pos];
115 5355095 : node->indices[num_pos] = tmp_idx;
116 5355095 : num_pos++;
117 : }
118 : }
119 201220 : return num_pos;
120 : }
121 :
122 100707 : static void mesh_subdivide_aabbtree(GF_Mesh *mesh, AABBNode *node, AABSplitParams *aab_par)
123 : {
124 : Bool do_split;
125 : u32 axis, num_pos, i, j;
126 : SFVec3f extend;
127 :
128 151206 : if (!mesh || !node) return;
129 : /*update mesh depth*/
130 100707 : aab_par->depth ++;
131 :
132 : /*done*/
133 100707 : if (node->nb_idx==1) return;
134 100224 : if (node->nb_idx <= aab_par->min_tri_limit) return;
135 50305 : if (aab_par->max_depth == aab_par->depth) {
136 0 : aab_par->depth --;
137 0 : return;
138 : }
139 : do_split = GF_TRUE;
140 :
141 50305 : gf_vec_diff(extend, node->max, node->min);
142 50305 : extend = gf_vec_scale(extend, FIX_ONE/2);
143 : axis = gf_vec_main_axis(extend);
144 :
145 : num_pos = 0;
146 50305 : if (aab_par->split_type==AABB_LONGEST) {
147 0 : num_pos = aabb_split(mesh, node, axis);
148 : }
149 50305 : else if (aab_par->split_type==AABB_BALANCED) {
150 : Fixed res[3];
151 50305 : num_pos = aabb_split(mesh, node, 0);
152 50305 : res[0] = gf_divfix(INT2FIX(num_pos), INT2FIX(node->nb_idx)) - FIX_ONE/2;
153 50305 : res[0] = gf_mulfix(res[0], res[0]);
154 50305 : num_pos = aabb_split(mesh, node, 1);
155 50305 : res[1] = gf_divfix(INT2FIX(num_pos), INT2FIX(node->nb_idx)) - FIX_ONE/2;
156 50305 : res[1] = gf_mulfix(res[1], res[1]);
157 50305 : num_pos = aabb_split(mesh, node, 2);
158 50305 : res[2] = gf_divfix(INT2FIX(num_pos), INT2FIX(node->nb_idx)) - FIX_ONE/2;
159 50305 : res[2] = gf_mulfix(res[2], res[2]);
160 :
161 : axis = 0;
162 50305 : if (res[1] < res[axis]) axis = 1;
163 50305 : if (res[2] < res[axis]) axis = 2;
164 50305 : num_pos = aabb_split(mesh, node, axis);
165 : }
166 0 : else if (aab_par->split_type==AABB_BEST_AXIS) {
167 0 : u32 sorted[] = { 0, 1, 2 };
168 : Fixed *Keys = (Fixed *) &extend.x;
169 0 : for (j=0; j<3; j++) {
170 0 : for (i=0; i<2; i++) {
171 0 : if (Keys[sorted[i]] < Keys[sorted[i+1]]) {
172 : u32 tmp = sorted[i];
173 0 : sorted[i] = sorted[i+1];
174 0 : sorted[i+1] = tmp;
175 : }
176 : }
177 : }
178 : axis = 0;
179 : do_split = GF_FALSE;
180 0 : while (!do_split && (axis!=3)) {
181 0 : num_pos = aabb_split(mesh, node, sorted[axis]);
182 : // Check the subdivision has been successful
183 0 : if (!num_pos || (num_pos==node->nb_idx)) axis++;
184 : else do_split = GF_TRUE;
185 : }
186 : }
187 0 : else if (aab_par->split_type==AABB_SPLATTER) {
188 : SFVec3f means, vars;
189 : means.x = means.y = means.z = 0;
190 0 : for (i=0; i<node->nb_idx; i++) {
191 0 : IDX_TYPE idx = node->indices[i];
192 0 : means.x += tri_get_center(mesh, idx, 0);
193 0 : means.y += tri_get_center(mesh, idx, 1);
194 0 : means.z += tri_get_center(mesh, idx, 2);
195 : }
196 0 : means = gf_vec_scale(means, gf_invfix(node->nb_idx));
197 :
198 : vars.x = vars.y = vars.z = 0;
199 0 : for (i=0; i<node->nb_idx; i++) {
200 0 : IDX_TYPE idx = node->indices[i];
201 0 : Fixed cx = tri_get_center(mesh, idx, 0);
202 0 : Fixed cy = tri_get_center(mesh, idx, 1);
203 0 : Fixed cz = tri_get_center(mesh, idx, 2);
204 0 : vars.x += gf_mulfix(cx - means.x, cx - means.x);
205 0 : vars.y += gf_mulfix(cy - means.y, cy - means.y);
206 0 : vars.z += gf_mulfix(cz - means.z, cz - means.z);
207 : }
208 0 : vars = gf_vec_scale(vars, gf_invfix(node->nb_idx-1) );
209 : axis = gf_vec_main_axis(vars);
210 0 : num_pos = aabb_split(mesh, node, axis);
211 : }
212 : else if (aab_par->split_type==AABB_FIFTY) {
213 : do_split = GF_FALSE;
214 : }
215 :
216 50305 : if (!num_pos || (num_pos==node->nb_idx)) do_split = GF_FALSE;
217 :
218 50208 : if (!do_split) {
219 97 : if (aab_par->split_type==AABB_FIFTY) {
220 0 : num_pos = node->nb_idx/2;
221 : } else {
222 : return;
223 : }
224 : }
225 50208 : aab_par->nb_nodes += 2;
226 :
227 50208 : GF_SAFEALLOC(node->pos, AABBNode);
228 50208 : if (node->pos) {
229 50208 : node->pos->indices = &node->indices[0];
230 50208 : node->pos->nb_idx = num_pos;
231 50208 : update_node_bounds(mesh, node->pos);
232 50208 : mesh_subdivide_aabbtree(mesh, node->pos, aab_par);
233 : }
234 :
235 50208 : GF_SAFEALLOC(node->neg, AABBNode);
236 50208 : if (node->neg) {
237 50208 : node->neg->indices = &node->indices[num_pos];
238 50208 : node->neg->nb_idx = node->nb_idx - num_pos;
239 50208 : update_node_bounds(mesh, node->neg);
240 50208 : mesh_subdivide_aabbtree(mesh, node->neg, aab_par);
241 : }
242 50208 : aab_par->depth --;
243 : }
244 :
245 :
246 292 : void gf_mesh_build_aabbtree(GF_Mesh *mesh)
247 : {
248 : u32 i, nb_idx;
249 : AABSplitParams pars;
250 :
251 : memset(&pars, 0, sizeof(pars));
252 292 : pars.min_tri_limit = 8;
253 : pars.max_depth = 0;
254 292 : pars.split_type = AABB_BALANCED;
255 :
256 293 : if (mesh->i_count <= pars.min_tri_limit) return;
257 :
258 291 : nb_idx = mesh->i_count / 3;
259 291 : mesh->aabb_indices = (IDX_TYPE*)gf_malloc(sizeof(IDX_TYPE) * nb_idx);
260 291 : for (i=0; i<nb_idx; i++) mesh->aabb_indices[i] = i;
261 :
262 291 : GF_SAFEALLOC(mesh->aabb_root, AABBNode);
263 291 : if (mesh->aabb_root) {
264 291 : mesh->aabb_root->min = mesh->bounds.min_edge;
265 291 : mesh->aabb_root->max = mesh->bounds.max_edge;
266 291 : mesh->aabb_root->indices = mesh->aabb_indices;
267 291 : mesh->aabb_root->nb_idx = nb_idx;
268 : }
269 291 : pars.nb_nodes = 1;
270 291 : pars.depth = 0;
271 291 : mesh_subdivide_aabbtree(mesh, mesh->aabb_root, &pars);
272 :
273 291 : GF_LOG(GF_LOG_DEBUG, GF_LOG_COMPOSE, ("[Mesh] AABB tree done - %d nodes depth %d - size %d bytes\n", pars.nb_nodes, pars.depth, sizeof(AABBNode)*pars.nb_nodes));
274 : }
275 :
276 :
277 267 : static void ray_hit_triangle_get_u_v(GF_Ray *ray, GF_Vec *v0, GF_Vec *v1, GF_Vec *v2, Fixed *u, Fixed *v)
278 : {
279 : Fixed det;
280 : GF_Vec edge1, edge2, tvec, pvec, qvec;
281 : /* find vectors for two edges sharing vert0 */
282 267 : gf_vec_diff(edge1, *v1, *v0);
283 267 : gf_vec_diff(edge2, *v2, *v0);
284 : /* begin calculating determinant - also used to calculate U parameter */
285 267 : pvec = gf_vec_cross(ray->dir, edge2);
286 : /* if determinant is near zero, ray lies in plane of triangle */
287 267 : det = gf_vec_dot(edge1, pvec);
288 : /* calculate distance from vert0 to ray origin */
289 267 : gf_vec_diff(tvec, ray->orig, *v0);
290 : /* calculate U parameter and test bounds */
291 267 : (*u) = gf_divfix(gf_vec_dot(tvec, pvec), det);
292 : /* prepare to test V parameter */
293 267 : qvec = gf_vec_cross(tvec, edge1);
294 : /* calculate V parameter and test bounds */
295 267 : (*v) = gf_divfix(gf_vec_dot(ray->dir, qvec), det);
296 267 : }
297 :
298 125431 : Bool gf_mesh_aabb_ray_hit(GF_Mesh *mesh, AABBNode *n, GF_Ray *ray, Fixed *closest, SFVec3f *outPoint, SFVec3f *outNormal, SFVec2f *outTexCoords)
299 : {
300 : Bool inters;
301 : Fixed dist;
302 : SFVec3f v1, v2;
303 : u32 i, inters_idx;
304 :
305 : /*check bbox intersection*/
306 125431 : inters = gf_ray_hit_box(ray, n->min, n->max, NULL);
307 125431 : if (!inters) return GF_FALSE;
308 :
309 121158 : if (n->pos) {
310 : /*we really want to check all possible intersections to get the closest point on ray*/
311 62262 : Bool res = gf_mesh_aabb_ray_hit(mesh, n->pos, ray, closest, outPoint, outNormal, outTexCoords);
312 62262 : res += gf_mesh_aabb_ray_hit(mesh, n->neg, ray, closest, outPoint, outNormal, outTexCoords);
313 62262 : return res;
314 :
315 : }
316 :
317 :
318 : inters_idx = 0;
319 : inters = GF_FALSE;
320 58896 : dist = (*closest);
321 :
322 : /*leaf, check for all faces*/
323 409785 : for (i=0; i<n->nb_idx; i++) {
324 : Fixed res;
325 350889 : IDX_TYPE *idx = &mesh->indices[3*n->indices[i]];
326 350889 : if (gf_ray_hit_triangle(ray,
327 350889 : &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
328 : &res)) {
329 467 : if ((res>0) && (res<dist)) {
330 : dist = res;
331 : inters_idx = i;
332 : inters = GF_TRUE;
333 : }
334 : }
335 : }
336 :
337 58896 : if (inters) {
338 267 : (*closest) = dist;
339 267 : if (outPoint) {
340 267 : *outPoint = gf_vec_scale(ray->dir, dist);
341 267 : gf_vec_add(*outPoint, ray->orig, *outPoint);
342 : }
343 267 : if (outNormal) {
344 267 : IDX_TYPE *idx = &mesh->indices[3*n->indices[inters_idx]];
345 267 : if (mesh->flags & MESH_IS_SMOOTHED) {
346 16 : gf_vec_diff(v1, mesh->vertices[idx[1]].pos, mesh->vertices[idx[0]].pos);
347 16 : gf_vec_diff(v2, mesh->vertices[idx[2]].pos, mesh->vertices[idx[0]].pos);
348 16 : *outNormal = gf_vec_cross(v1, v2);
349 16 : gf_vec_norm(outNormal);
350 : } else {
351 251 : MESH_GET_NORMAL((*outNormal), mesh->vertices[idx[0]]);
352 : }
353 : }
354 267 : if (outTexCoords) {
355 267 : IDX_TYPE *idx = &mesh->indices[3*n->indices[inters_idx]];
356 534 : ray_hit_triangle_get_u_v(ray,
357 267 : &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
358 : &outTexCoords->x, &outTexCoords->y);
359 : }
360 : }
361 : return inters;
362 : }
363 :
364 907 : Bool gf_mesh_intersect_ray(GF_Mesh *mesh, GF_Ray *ray, SFVec3f *outPoint, SFVec3f *outNormal, SFVec2f *outTexCoords)
365 : {
366 : Bool inters;
367 : u32 i, inters_idx;
368 : Fixed closest;
369 : /*no intersection on linesets/pointsets*/
370 907 : if (mesh->mesh_type != MESH_TRIANGLES) return GF_FALSE;
371 :
372 : /*use aabbtree*/
373 907 : if (mesh->aabb_root) {
374 907 : closest = FIX_MAX;
375 907 : return gf_mesh_aabb_ray_hit(mesh, mesh->aabb_root, ray, &closest, outPoint, outNormal, outTexCoords);
376 : }
377 :
378 : /*check bbox intersection*/
379 0 : inters = gf_ray_hit_box(ray, mesh->bounds.min_edge, mesh->bounds.max_edge, NULL);
380 0 : if (!inters) return GF_FALSE;
381 :
382 : inters_idx = 0;
383 : inters = GF_FALSE;
384 0 : closest = FIX_MAX;
385 0 : for (i=0; i<mesh->i_count; i+=3) {
386 : Fixed res;
387 0 : IDX_TYPE *idx = &mesh->indices[i];
388 0 : if (gf_ray_hit_triangle(ray,
389 0 : &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
390 : &res)) {
391 0 : if ((res>0) && (res<closest)) {
392 0 : closest = res;
393 : inters_idx = i;
394 : inters = GF_TRUE;
395 : }
396 : }
397 : }
398 :
399 0 : if (inters) {
400 0 : if (outPoint) {
401 0 : *outPoint = gf_vec_scale(ray->dir, closest);
402 0 : gf_vec_add(*outPoint, ray->orig, *outPoint);
403 : }
404 0 : if (outNormal) {
405 0 : IDX_TYPE *idx = &mesh->indices[inters_idx];
406 0 : if (mesh->flags & MESH_IS_SMOOTHED) {
407 : SFVec3f v1, v2;
408 0 : gf_vec_diff(v1, mesh->vertices[idx[1]].pos, mesh->vertices[idx[0]].pos);
409 0 : gf_vec_diff(v2, mesh->vertices[idx[2]].pos, mesh->vertices[idx[0]].pos);
410 0 : *outNormal = gf_vec_cross(v1, v2);
411 0 : gf_vec_norm(outNormal);
412 : } else {
413 0 : MESH_GET_NORMAL((*outNormal), mesh->vertices[idx[0]]);
414 : }
415 : }
416 0 : if (outTexCoords) {
417 : SFVec2f txres;
418 0 : IDX_TYPE *idx = &mesh->indices[inters_idx];
419 : txres.x = txres.y = 0;
420 0 : txres.x += mesh->vertices[idx[0]].texcoords.x;
421 0 : txres.x += mesh->vertices[idx[1]].texcoords.x;
422 0 : txres.x += mesh->vertices[idx[2]].texcoords.x;
423 0 : txres.y += mesh->vertices[idx[0]].texcoords.y;
424 0 : txres.y += mesh->vertices[idx[1]].texcoords.y;
425 0 : txres.y += mesh->vertices[idx[2]].texcoords.y;
426 0 : outTexCoords->x = txres.x / 3;
427 0 : outTexCoords->y = txres.y / 3;
428 : }
429 : }
430 : return inters;
431 : }
432 :
433 :
434 712 : static GFINLINE Bool mesh_collide_triangle(GF_Ray *ray, SFVec3f *v0, SFVec3f *v1, SFVec3f *v2, Fixed *dist)
435 : {
436 : Fixed u, v, det;
437 : SFVec3f edge1, edge2, tvec, pvec, qvec;
438 : /* find vectors for two edges sharing vert0 */
439 712 : gf_vec_diff(edge1, *v1, *v0);
440 712 : gf_vec_diff(edge2, *v2, *v0);
441 : /* begin calculating determinant - also used to calculate U parameter */
442 712 : pvec = gf_vec_cross(ray->dir, edge2);
443 : /* if determinant is near zero, ray lies in plane of triangle */
444 712 : det = gf_vec_dot(edge1, pvec);
445 712 : if (ABS(det) < FIX_EPSILON) return GF_FALSE;
446 : /* calculate distance from vert0 to ray origin */
447 712 : gf_vec_diff(tvec, ray->orig, *v0);
448 : /* calculate U parameter and test bounds */
449 712 : u = gf_divfix(gf_vec_dot(tvec, pvec), det);
450 712 : if ((u < 0) || (u > FIX_ONE)) return GF_FALSE;
451 : /* prepare to test V parameter */
452 344 : qvec = gf_vec_cross(tvec, edge1);
453 : /* calculate V parameter and test bounds */
454 344 : v = gf_divfix(gf_vec_dot(ray->dir, qvec), det);
455 344 : if ((v < 0) || (u + v > FIX_ONE)) return GF_FALSE;
456 : /* calculate t, ray intersects triangle */
457 119 : *dist = gf_divfix(gf_vec_dot(edge2, qvec), det);
458 119 : return GF_TRUE;
459 : }
460 :
461 :
462 1219 : static GFINLINE Bool sphere_box_overlap(SFVec3f sc, Fixed sq_rad, SFVec3f bmin, SFVec3f bmax)
463 : {
464 : Fixed tmp, s, d, ext;
465 : d = 0;
466 1219 : tmp = sc.x - (bmin.x + bmax.x)/2;
467 1219 : ext = (bmax.x-bmin.x)/2;
468 1219 : s = tmp + ext;
469 1219 : if (s<0) d += gf_mulfix(s, s);
470 : else {
471 1123 : s = tmp - ext;
472 1123 : if (s>0) d += gf_mulfix(s, s);
473 : }
474 1219 : tmp = sc.y - (bmin.y + bmax.y)/2;
475 1219 : ext = (bmax.y-bmin.y)/2;
476 1219 : s = tmp + ext;
477 1219 : if (s<0) d += gf_mulfix(s, s);
478 : else {
479 1100 : s = tmp - ext;
480 1100 : if (s>0) d += gf_mulfix(s, s);
481 : }
482 1219 : tmp = sc.z - (bmin.z + bmax.z)/2;
483 1219 : ext = (bmax.z-bmin.z)/2;
484 1219 : s = tmp + ext;
485 1219 : if (s<0) d += gf_mulfix(s, s);
486 : else {
487 1040 : s = tmp - ext;
488 1040 : if (s>0) d += gf_mulfix(s, s);
489 : }
490 1219 : return (d<=sq_rad) ? GF_TRUE : GF_FALSE;
491 : }
492 :
493 1219 : Bool gf_mesh_closest_face_aabb(GF_Mesh *mesh, AABBNode *node, SFVec3f pos, Fixed min_dist, Fixed min_sq_dist, Fixed *min_col_dist, SFVec3f *outPoint)
494 : {
495 : GF_Ray r;
496 : u32 i;
497 : SFVec3f v1, v2, n, resn;
498 : Bool inters, has_inter, need_norm = GF_FALSE;
499 : Fixed d;
500 1219 : if (!sphere_box_overlap(pos, min_sq_dist, node->min, node->max)) return GF_FALSE;
501 679 : if (node->pos) {
502 549 : if (gf_mesh_closest_face_aabb(mesh, node->pos, pos, min_dist, min_sq_dist, min_col_dist, outPoint)) return GF_TRUE;
503 548 : return gf_mesh_closest_face_aabb(mesh, node->neg, pos, min_dist, min_sq_dist, min_col_dist, outPoint);
504 : }
505 :
506 130 : need_norm = (mesh->flags & MESH_IS_SMOOTHED) ? GF_TRUE : GF_FALSE;
507 130 : r.orig = pos;
508 : has_inter = GF_FALSE;
509 842 : for (i=0; i<node->nb_idx; i++) {
510 712 : IDX_TYPE *idx = &mesh->indices[3*node->indices[i]];
511 712 : if (need_norm) {
512 712 : gf_vec_diff(v1, mesh->vertices[idx[1]].pos, mesh->vertices[idx[0]].pos);
513 712 : gf_vec_diff(v2, mesh->vertices[idx[2]].pos, mesh->vertices[idx[0]].pos);
514 712 : n = gf_vec_cross(v1, v2);
515 712 : gf_vec_norm(&n);
516 : } else {
517 0 : MESH_GET_NORMAL(n, mesh->vertices[idx[0]]);
518 : }
519 :
520 : /*intersect inverse normal from position to face with face*/
521 712 : r.dir = n;
522 712 : gf_vec_rev(r.dir);
523 2136 : inters = mesh_collide_triangle(&r,
524 2136 : &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
525 : &d);
526 :
527 712 : if (inters) {
528 : /*we're behind the face, get inverse normal*/
529 119 : if (d<0) {
530 119 : d*= -1;
531 119 : n = r.dir;
532 : }
533 119 : if (d<=(*min_col_dist)) {
534 : has_inter = GF_TRUE;
535 1 : (*min_col_dist) = d;
536 1 : resn = n;
537 : }
538 : }
539 : }
540 130 : if (has_inter) {
541 1 : resn = gf_vec_scale(resn, -(*min_col_dist));
542 1 : gf_vec_add(*outPoint, pos, resn);
543 : }
544 : return has_inter;
545 : }
546 :
547 3933 : Bool gf_mesh_closest_face(GF_Mesh *mesh, SFVec3f pos, Fixed min_dist, SFVec3f *outPoint)
548 : {
549 : GF_Ray r;
550 : u32 i;
551 : SFVec3f v1, v2, n, resn;
552 : Bool inters, has_inter, need_norm;
553 : Fixed d, dmax;
554 :
555 : /*check bounds*/
556 3933 : gf_vec_diff(v1, mesh->bounds.center, pos);
557 3933 : if (gf_vec_len(v1)>min_dist+mesh->bounds.radius) return GF_FALSE;
558 :
559 122 : if (mesh->aabb_root) {
560 122 : d = min_dist * min_dist;
561 122 : dmax = min_dist;
562 122 : return gf_mesh_closest_face_aabb(mesh, mesh->aabb_root, pos, min_dist, d, &dmax, outPoint);
563 : }
564 :
565 0 : need_norm = (mesh->flags & MESH_IS_SMOOTHED) ? GF_TRUE : GF_FALSE;
566 :
567 0 : r.orig = pos;
568 : has_inter = GF_FALSE;
569 0 : dmax = min_dist;
570 0 : for (i=0; i<mesh->i_count; i+=3) {
571 0 : IDX_TYPE *idx = &mesh->indices[i];
572 0 : if (need_norm) {
573 0 : gf_vec_diff(v1, mesh->vertices[idx[1]].pos, mesh->vertices[idx[0]].pos);
574 0 : gf_vec_diff(v2, mesh->vertices[idx[2]].pos, mesh->vertices[idx[0]].pos);
575 0 : n = gf_vec_cross(v1, v2);
576 0 : gf_vec_norm(&n);
577 : } else {
578 0 : MESH_GET_NORMAL(n, mesh->vertices[idx[0]]);
579 0 : n.x = mesh->vertices[idx[0]].normal.x;
580 0 : n.y = mesh->vertices[idx[0]].normal.y;
581 0 : n.z = mesh->vertices[idx[0]].normal.z;
582 : }
583 :
584 0 : d = -gf_vec_dot(mesh->vertices[idx[0]].pos, n);
585 0 : d += gf_vec_dot(r.orig, n);
586 0 : if (fabs(d)>min_dist) continue;
587 :
588 : /*intersect inverse normal from position to face with face*/
589 0 : r.dir = n;
590 0 : gf_vec_rev(r.dir);
591 0 : inters = mesh_collide_triangle(&r,
592 0 : &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
593 : &d);
594 :
595 0 : if (inters) {
596 : /*we're behind the face, get inverse normal*/
597 0 : if (d<0) {
598 0 : d*= -1;
599 0 : n = r.dir;
600 : }
601 0 : if (d<=dmax) {
602 : has_inter = GF_TRUE;
603 0 : dmax = d;
604 0 : resn = n;
605 : }
606 : }
607 : }
608 0 : if (has_inter) {
609 0 : resn = gf_vec_scale(resn, -dmax);
610 0 : gf_vec_add(*outPoint, pos, resn);
611 : }
612 : return has_inter;
613 : }
614 :
615 : #endif /*GPAC_DISABLE_3D*/
|
