root/src/compositor/mesh_collide.c

DEFINITIONS

1. update_node_bounds
2. gf_vec_main_axis
3. tri_get_center
4. aabb_split
5. mesh_subdivide_aabbtree
6. gf_mesh_build_aabbtree
7. ray_hit_triangle_get_u_v
8. gf_mesh_aabb_ray_hit
9. gf_mesh_intersect_ray
10. mesh_collide_triangle
11. sphere_box_overlap
12. gf_mesh_closest_face_aabb
13. gf_mesh_closest_face

/*
 *                      GPAC - Multimedia Framework C SDK
 *
 *                      Authors: Jean Le Feuvre
 *                      Copyright (c) Telecom ParisTech 2000-2012
 *                                      All rights reserved
 *
 *  This file is part of GPAC / Scene Compositor sub-project
 *
 *  GPAC is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation; either version 2, or (at your option)
 *  any later version.
 *
 *  GPAC is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; see the file COPYING.  If not, write to
 *  the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */


#include <gpac/internal/mesh.h>

#ifndef GPAC_DISABLE_3D

/*
        AABB tree syntax&construction code is a quick extract from OPCODE (c) Pierre Terdiman, http://www.codercorner.com/Opcode.htm
*/

typedef struct
{
        /*max tree depth, 0 is unlimited*/
        u32 max_depth;
        /*min triangles at node to split. 0 is full split (one triangle per leaf)*/
        u32 min_tri_limit;
        /*one of the above type*/
        u32 split_type;
        u32 depth, nb_nodes;
} AABSplitParams;



static GFINLINE void update_node_bounds(GF_Mesh *mesh, AABBNode *node)
{
        u32 i, j;
        Fixed mx, my, mz, Mx, My, Mz;
        mx = my = mz = FIX_MAX;
        Mx = My = Mz = FIX_MIN;
        for (i=0; i<node->nb_idx; i++) {
                IDX_TYPE *idx = &mesh->indices[3*node->indices[i]];
                for (j=0; j<3; j++) {
                        SFVec3f *v = &mesh->vertices[idx[j]].pos;
                        if (mx>v->x) mx=v->x;
                        if (Mx<v->x) Mx=v->x;
                        if (my>v->y) my=v->y;
                        if (My<v->y) My=v->y;
                        if (mz>v->z) mz=v->z;
                        if (Mz<v->z) Mz=v->z;
                }
        }
        node->min.x = mx;
        node->min.y = my;
        node->min.z = mz;
        node->max.x = Mx;
        node->max.y = My;
        node->max.z = Mz;
}

static GFINLINE u32 gf_vec_main_axis(SFVec3f v)
{
        Fixed *vals = &v.x;
        u32 m = 0;
        if(vals[1] > vals[m]) m = 1;
        if(vals[2] > vals[m]) m = 2;
        return m;
}

static GFINLINE Fixed tri_get_center(GF_Mesh *mesh, u32 tri_idx, u32 axis)
{
        SFVec3f v;
        IDX_TYPE *idx = &mesh->indices[3*tri_idx];
        /*compute center*/
        gf_vec_add(v, mesh->vertices[idx[0]].pos, mesh->vertices[idx[1]].pos);
        gf_vec_add(v, v, mesh->vertices[idx[2]].pos);
        v = gf_vec_scale(v, FIX_ONE/3);
        return ((Fixed *)&v.x)[axis];
}

static GFINLINE u32 aabb_split(GF_Mesh *mesh, AABBNode *node, u32 axis)
{
        SFVec3f v;
        Fixed split_at;
        u32 num_pos, i;

        gf_vec_add(v, node->max, node->min);
        v = gf_vec_scale(v, FIX_ONE/2);

        split_at = ((Fixed *)&v.x)[axis];

        num_pos = 0;

        for (i=0; i<node->nb_idx; i++) {
                IDX_TYPE idx = node->indices[i];
                Fixed tri_val = tri_get_center(mesh, idx, axis);

                if (tri_val > split_at) {
                        /*swap*/
                        IDX_TYPE tmp_idx = node->indices[i];
                        node->indices[i] = node->indices[num_pos];
                        node->indices[num_pos] = tmp_idx;
                        num_pos++;
                }
        }
        return num_pos;
}

static void mesh_subdivide_aabbtree(GF_Mesh *mesh, AABBNode *node, AABSplitParams *aab_par)
{
        Bool do_split;
        u32 axis, num_pos, i, j;
        SFVec3f extend;

if (!mesh || !node) return;
        /*update mesh depth*/
        aab_par->depth ++;

        /*done*/
        if (node->nb_idx==1) return;
        if (node->nb_idx <= aab_par->min_tri_limit) return;
        if (aab_par->max_depth == aab_par->depth) {
                aab_par->depth --;
                return;
        }
        do_split = GF_TRUE;

        gf_vec_diff(extend, node->max, node->min);
        extend = gf_vec_scale(extend, FIX_ONE/2);
        axis = gf_vec_main_axis(extend);

        num_pos = 0;
        if (aab_par->split_type==AABB_LONGEST) {
                num_pos = aabb_split(mesh, node, axis);
        }
        else if (aab_par->split_type==AABB_BALANCED) {
                Fixed res[3];
                num_pos = aabb_split(mesh, node, 0);
                res[0] = gf_divfix(INT2FIX(num_pos), INT2FIX(node->nb_idx)) - FIX_ONE/2;
                res[0] = gf_mulfix(res[0], res[0]);
                num_pos = aabb_split(mesh, node, 1);
                res[1] = gf_divfix(INT2FIX(num_pos), INT2FIX(node->nb_idx)) - FIX_ONE/2;
                res[1] = gf_mulfix(res[1], res[1]);
                num_pos = aabb_split(mesh, node, 2);
                res[2] = gf_divfix(INT2FIX(num_pos), INT2FIX(node->nb_idx)) - FIX_ONE/2;
                res[2] = gf_mulfix(res[2], res[2]);;

                axis = 0;
                if (res[1] < res[axis]) axis = 1;
                if (res[2] < res[axis]) axis = 2;
                num_pos = aabb_split(mesh, node, axis);
        }
        else if (aab_par->split_type==AABB_BEST_AXIS) {
                u32 sorted[] = { 0, 1, 2 };
                Fixed *Keys = (Fixed *) &extend.x;
                for (j=0; j<3; j++) {
                        for (i=0; i<2; i++) {
                                if (Keys[sorted[i]] < Keys[sorted[i+1]]) {
                                        u32 tmp = sorted[i];
                                        sorted[i] = sorted[i+1];
                                        sorted[i+1] = tmp;
                                }
                        }
                }
                axis = 0;
                do_split = GF_FALSE;
                while (!do_split && (axis!=3)) {
                        num_pos = aabb_split(mesh, node, sorted[axis]);
                        // Check the subdivision has been successful
                        if (!num_pos || (num_pos==node->nb_idx)) axis++;
                        else do_split = GF_TRUE;
                }
        }
        else if (aab_par->split_type==AABB_SPLATTER) {
                SFVec3f means, vars;
                means.x = means.y = means.z = 0;
                for (i=0; i<node->nb_idx; i++) {
                        IDX_TYPE idx = node->indices[i];
                        means.x += tri_get_center(mesh, idx, 0);
                        means.y += tri_get_center(mesh, idx, 1);
                        means.z += tri_get_center(mesh, idx, 2);
                }
                means = gf_vec_scale(means, gf_invfix(node->nb_idx));

                vars.x = vars.y = vars.z = 0;
                for (i=0; i<node->nb_idx; i++) {
                        IDX_TYPE idx = node->indices[i];
                        Fixed cx = tri_get_center(mesh, idx, 0);
                        Fixed cy = tri_get_center(mesh, idx, 1);
                        Fixed cz = tri_get_center(mesh, idx, 2);
                        vars.x += gf_mulfix(cx - means.x, cx - means.x);
                        vars.y += gf_mulfix(cy - means.y, cy - means.y);
                        vars.z += gf_mulfix(cz - means.z, cz - means.z);
                }
                vars = gf_vec_scale(vars, gf_invfix(node->nb_idx-1) );
                axis = gf_vec_main_axis(vars);
                num_pos = aabb_split(mesh, node, axis);
        }
        else if (aab_par->split_type==AABB_FIFTY) {
                do_split = GF_FALSE;
        }

        if (!num_pos || (num_pos==node->nb_idx)) do_split = GF_FALSE;

        if (!do_split) {
                if (aab_par->split_type==AABB_FIFTY) {
                        num_pos = node->nb_idx/2;
                } else {
                        return;
                }
        }
        aab_par->nb_nodes += 2;

        GF_SAFEALLOC(node->pos, AABBNode);
        if (node->pos) {
                node->pos->indices = &node->indices[0];
                node->pos->nb_idx = num_pos;
                update_node_bounds(mesh, node->pos);
                mesh_subdivide_aabbtree(mesh, node->pos, aab_par);
        }

        GF_SAFEALLOC(node->neg, AABBNode);
        if (node->neg) {
                node->neg->indices = &node->indices[num_pos];
                node->neg->nb_idx = node->nb_idx - num_pos;
                update_node_bounds(mesh, node->neg);
                mesh_subdivide_aabbtree(mesh, node->neg, aab_par);
        }
        aab_par->depth --;
}


void gf_mesh_build_aabbtree(GF_Mesh *mesh)
{
        u32 i, nb_idx;
        AABSplitParams pars;

        memset(&pars, 0, sizeof(pars));
        pars.min_tri_limit = 8;
        pars.max_depth = 0;
        pars.split_type = AABB_BALANCED;

        if (mesh->i_count <= pars.min_tri_limit) return;

        nb_idx = mesh->i_count / 3;
        mesh->aabb_indices = (IDX_TYPE*)gf_malloc(sizeof(IDX_TYPE) * nb_idx);
        for (i=0; i<nb_idx; i++) mesh->aabb_indices[i] = i;

        GF_SAFEALLOC(mesh->aabb_root, AABBNode);
        if (mesh->aabb_root) {
                mesh->aabb_root->min = mesh->bounds.min_edge;
                mesh->aabb_root->max = mesh->bounds.max_edge;
                mesh->aabb_root->indices = mesh->aabb_indices;
                mesh->aabb_root->nb_idx = nb_idx;
        }
        pars.nb_nodes = 1;
        pars.depth = 0;
        mesh_subdivide_aabbtree(mesh, mesh->aabb_root, &pars);

        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));
}


static void ray_hit_triangle_get_u_v(GF_Ray *ray, GF_Vec *v0, GF_Vec *v1, GF_Vec *v2, Fixed *u, Fixed *v)
{
        Fixed det;
        GF_Vec edge1, edge2, tvec, pvec, qvec;
        /* find vectors for two edges sharing vert0 */
        gf_vec_diff(edge1, *v1, *v0);
        gf_vec_diff(edge2, *v2, *v0);
        /* begin calculating determinant - also used to calculate U parameter */
        pvec = gf_vec_cross(ray->dir, edge2);
        /* if determinant is near zero, ray lies in plane of triangle */
        det = gf_vec_dot(edge1, pvec);
        /* calculate distance from vert0 to ray origin */
        gf_vec_diff(tvec, ray->orig, *v0);
        /* calculate U parameter and test bounds */
        (*u) = gf_divfix(gf_vec_dot(tvec, pvec), det);
        /* prepare to test V parameter */
        qvec = gf_vec_cross(tvec, edge1);
        /* calculate V parameter and test bounds */
        (*v) = gf_divfix(gf_vec_dot(ray->dir, qvec), det);
}

Bool gf_mesh_aabb_ray_hit(GF_Mesh *mesh, AABBNode *n, GF_Ray *ray, Fixed *closest, SFVec3f *outPoint, SFVec3f *outNormal, SFVec2f *outTexCoords)
{
        Bool inters;
        Fixed dist;
        SFVec3f v1, v2;
        u32 i, inters_idx;

        /*check bbox intersection*/
        inters = gf_ray_hit_box(ray, n->min, n->max, NULL);
        if (!inters) return GF_FALSE;

        if (n->pos) {
                /*we really want to check all possible intersections to get the closest point on ray*/
                Bool res = gf_mesh_aabb_ray_hit(mesh, n->pos, ray, closest, outPoint, outNormal, outTexCoords);
                res += gf_mesh_aabb_ray_hit(mesh, n->neg, ray, closest, outPoint, outNormal, outTexCoords);
                return res;

        }


        inters_idx = 0;
        inters = GF_FALSE;
        dist = (*closest);

        /*leaf, check for all faces*/
        for (i=0; i<n->nb_idx; i++) {
                Fixed res;
                IDX_TYPE *idx = &mesh->indices[3*n->indices[i]];
                if (gf_ray_hit_triangle(ray,
                                        &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
                                        &res)) {
                        if ((res>0) && (res<dist)) {
                                dist = res;
                                inters_idx = i;
                                inters = GF_TRUE;
                        }
                }
        }

        if (inters) {
                (*closest) = dist;
                if (outPoint) {
                        *outPoint = gf_vec_scale(ray->dir, dist);
                        gf_vec_add(*outPoint, ray->orig, *outPoint);
                }
                if (outNormal) {
                        IDX_TYPE *idx = &mesh->indices[3*n->indices[inters_idx]];;
                        if (mesh->flags & MESH_IS_SMOOTHED) {
                                gf_vec_diff(v1, mesh->vertices[idx[1]].pos, mesh->vertices[idx[0]].pos);
                                gf_vec_diff(v2, mesh->vertices[idx[2]].pos, mesh->vertices[idx[0]].pos);
                                *outNormal = gf_vec_cross(v1, v2);
                                gf_vec_norm(outNormal);
                        } else {
                                MESH_GET_NORMAL((*outNormal), mesh->vertices[idx[0]]);
                        }
                }
                if (outTexCoords) {
                        IDX_TYPE *idx = &mesh->indices[3*n->indices[inters_idx]];;
                        ray_hit_triangle_get_u_v(ray,
                                                 &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
                                                 &outTexCoords->x, &outTexCoords->y);
                }
        }
        return inters;
}

Bool gf_mesh_intersect_ray(GF_Mesh *mesh, GF_Ray *ray, SFVec3f *outPoint, SFVec3f *outNormal, SFVec2f *outTexCoords)
{
        Bool inters;
        u32 i, inters_idx;
        Fixed closest;
        /*no intersection on linesets/pointsets*/
        if (mesh->mesh_type != MESH_TRIANGLES) return GF_FALSE;

        /*use aabbtree*/
        if (mesh->aabb_root) {
                closest = FIX_MAX;
                return gf_mesh_aabb_ray_hit(mesh, mesh->aabb_root, ray, &closest, outPoint, outNormal, outTexCoords);
        }

        /*check bbox intersection*/
        inters = gf_ray_hit_box(ray, mesh->bounds.min_edge, mesh->bounds.max_edge, NULL);
        if (!inters) return GF_FALSE;

        inters_idx = 0;
        inters = GF_FALSE;
        closest = FIX_MAX;
        for (i=0; i<mesh->i_count; i+=3) {
                Fixed res;
                IDX_TYPE *idx = &mesh->indices[i];
                if (gf_ray_hit_triangle(ray,
                                        &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
                                        &res)) {
                        if ((res>0) && (res<closest)) {
                                closest = res;
                                inters_idx = i;
                                inters = GF_TRUE;
                        }
                }
        }

        if (inters) {
                if (outPoint) {
                        *outPoint = gf_vec_scale(ray->dir, closest);
                        gf_vec_add(*outPoint, ray->orig, *outPoint);
                }
                if (outNormal) {
                        IDX_TYPE *idx = &mesh->indices[inters_idx];
                        if (mesh->flags & MESH_IS_SMOOTHED) {
                                SFVec3f v1, v2;
                                gf_vec_diff(v1, mesh->vertices[idx[1]].pos, mesh->vertices[idx[0]].pos);
                                gf_vec_diff(v2, mesh->vertices[idx[2]].pos, mesh->vertices[idx[0]].pos);
                                *outNormal = gf_vec_cross(v1, v2);
                                gf_vec_norm(outNormal);
                        } else {
                                MESH_GET_NORMAL((*outNormal), mesh->vertices[idx[0]]);
                        }
                }
                if (outTexCoords) {
                        SFVec2f txres;
                        IDX_TYPE *idx = &mesh->indices[inters_idx];
                        txres.x = txres.y = 0;
                        txres.x += mesh->vertices[idx[0]].texcoords.x;
                        txres.x += mesh->vertices[idx[1]].texcoords.x;
                        txres.x += mesh->vertices[idx[2]].texcoords.x;
                        txres.y += mesh->vertices[idx[0]].texcoords.y;
                        txres.y += mesh->vertices[idx[1]].texcoords.y;
                        txres.y += mesh->vertices[idx[2]].texcoords.y;
                        outTexCoords->x = txres.x / 3;
                        outTexCoords->y = txres.y / 3;
                }
        }
        return inters;
}


static GFINLINE Bool mesh_collide_triangle(GF_Ray *ray, SFVec3f *v0, SFVec3f *v1, SFVec3f *v2, Fixed *dist)
{
        Fixed u, v, det;
        SFVec3f edge1, edge2, tvec, pvec, qvec;
        /* find vectors for two edges sharing vert0 */
        gf_vec_diff(edge1, *v1, *v0);
        gf_vec_diff(edge2, *v2, *v0);
        /* begin calculating determinant - also used to calculate U parameter */
        pvec = gf_vec_cross(ray->dir, edge2);
        /* if determinant is near zero, ray lies in plane of triangle */
        det = gf_vec_dot(edge1, pvec);
        if (ABS(det) < FIX_EPSILON) return GF_FALSE;
        /* calculate distance from vert0 to ray origin */
        gf_vec_diff(tvec, ray->orig, *v0);
        /* calculate U parameter and test bounds */
        u = gf_divfix(gf_vec_dot(tvec, pvec), det);
        if ((u < 0) || (u > FIX_ONE)) return GF_FALSE;
        /* prepare to test V parameter */
        qvec = gf_vec_cross(tvec, edge1);
        /* calculate V parameter and test bounds */
        v = gf_divfix(gf_vec_dot(ray->dir, qvec), det);
        if ((v < 0) || (u + v > FIX_ONE)) return GF_FALSE;
        /* calculate t, ray intersects triangle */
        *dist = gf_divfix(gf_vec_dot(edge2, qvec), det);
        return GF_TRUE;
}


static GFINLINE Bool sphere_box_overlap(SFVec3f sc, Fixed sq_rad, SFVec3f bmin, SFVec3f bmax)
{
        Fixed tmp, s, d, ext;
        d = 0;
        tmp = sc.x  - (bmin.x + bmax.x)/2;
        ext = (bmax.x-bmin.x)/2;
        s = tmp + ext;
        if (s<0) d += gf_mulfix(s, s);
        else {
                s = tmp - ext;
                if (s>0) d += gf_mulfix(s, s);
        }
        tmp = sc.y  - (bmin.y + bmax.y)/2;
        ext = (bmax.y-bmin.y)/2;
        s = tmp + ext;
        if (s<0) d += gf_mulfix(s, s);
        else {
                s = tmp - ext;
                if (s>0) d += gf_mulfix(s, s);
        }
        tmp = sc.z  - (bmin.z + bmax.z)/2;
        ext = (bmax.z-bmin.z)/2;
        s = tmp + ext;
        if (s<0) d += gf_mulfix(s, s);
        else {
                s = tmp - ext;
                if (s>0) d += gf_mulfix(s, s);
        }
        return (d<=sq_rad) ? GF_TRUE : GF_FALSE;
}

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)
{
        GF_Ray r;
        u32 i;
        SFVec3f v1, v2, n, resn;
        Bool inters, has_inter, need_norm = GF_FALSE;
        Fixed d;
        if (!sphere_box_overlap(pos, min_sq_dist, node->min, node->max)) return GF_FALSE;
        if (node->pos) {
                if (gf_mesh_closest_face_aabb(mesh, node->pos, pos, min_dist, min_sq_dist, min_col_dist, outPoint)) return GF_TRUE;
                return gf_mesh_closest_face_aabb(mesh, node->neg, pos, min_dist, min_sq_dist, min_col_dist, outPoint);
        }

        need_norm = (mesh->flags & MESH_IS_SMOOTHED) ? GF_TRUE : GF_FALSE,
        r.orig = pos;
        has_inter = GF_FALSE;
        for (i=0; i<node->nb_idx; i++) {
                IDX_TYPE *idx = &mesh->indices[3*node->indices[i]];
                if (need_norm) {
                        gf_vec_diff(v1, mesh->vertices[idx[1]].pos, mesh->vertices[idx[0]].pos);
                        gf_vec_diff(v2, mesh->vertices[idx[2]].pos, mesh->vertices[idx[0]].pos);
                        n = gf_vec_cross(v1, v2);
                        gf_vec_norm(&n);
                } else {
                        MESH_GET_NORMAL(n, mesh->vertices[idx[0]]);
                }

                /*intersect inverse normal from position to face with face*/
                r.dir = n;
                gf_vec_rev(r.dir);
                inters = mesh_collide_triangle(&r,
                                               &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
                                               &d);

                if (inters) {
                        /*we're behind the face, get inverse normal*/
                        if (d<0) {
                                d*= -1;
                                n = r.dir;
                        }
                        if (d<=(*min_col_dist)) {
                                has_inter = GF_TRUE;
                                (*min_col_dist) = d;
                                resn = n;
                        }
                }
        }
        if (has_inter) {
                resn = gf_vec_scale(resn, -(*min_col_dist));
                gf_vec_add(*outPoint, pos, resn);
        }
        return has_inter;
}

Bool gf_mesh_closest_face(GF_Mesh *mesh, SFVec3f pos, Fixed min_dist, SFVec3f *outPoint)
{
        GF_Ray r;
        u32 i;
        SFVec3f v1, v2, n, resn;
        Bool inters, has_inter, need_norm;
        Fixed d, dmax;

        /*check bounds*/
        gf_vec_diff(v1, mesh->bounds.center, pos);
        if (gf_vec_len(v1)>min_dist+mesh->bounds.radius) return GF_FALSE;

        if (mesh->aabb_root) {
                d = min_dist * min_dist;
                dmax = min_dist;
                return gf_mesh_closest_face_aabb(mesh, mesh->aabb_root, pos, min_dist, d, &dmax, outPoint);
        }

        need_norm = (mesh->flags & MESH_IS_SMOOTHED) ? GF_TRUE : GF_FALSE,

        r.orig = pos;
        has_inter = GF_FALSE;
        dmax = min_dist;
        for (i=0; i<mesh->i_count; i+=3) {
                IDX_TYPE *idx = &mesh->indices[i];
                if (need_norm) {
                        gf_vec_diff(v1, mesh->vertices[idx[1]].pos, mesh->vertices[idx[0]].pos);
                        gf_vec_diff(v2, mesh->vertices[idx[2]].pos, mesh->vertices[idx[0]].pos);
                        n = gf_vec_cross(v1, v2);
                        gf_vec_norm(&n);
                } else {
                        MESH_GET_NORMAL(n, mesh->vertices[idx[0]]);
                        n.x = mesh->vertices[idx[0]].normal.x;
                        n.y = mesh->vertices[idx[0]].normal.y;
                        n.z = mesh->vertices[idx[0]].normal.z;
                }

                d = -gf_vec_dot(mesh->vertices[idx[0]].pos, n);
                d += gf_vec_dot(r.orig, n);
                if (fabs(d)>min_dist) continue;

                /*intersect inverse normal from position to face with face*/
                r.dir = n;
                gf_vec_rev(r.dir);
                inters = mesh_collide_triangle(&r,
                                               &mesh->vertices[idx[0]].pos, &mesh->vertices[idx[1]].pos, &mesh->vertices[idx[2]].pos,
                                               &d);

                if (inters) {
                        /*we're behind the face, get inverse normal*/
                        if (d<0) {
                                d*= -1;
                                n = r.dir;
                        }
                        if (d<=dmax) {
                                has_inter = GF_TRUE;
                                dmax = d;
                                resn = n;
                        }
                }
        }
        if (has_inter) {
                resn = gf_vec_scale(resn, -dmax);
                gf_vec_add(*outPoint, pos, resn);
        }
        return has_inter;
}

#endif  /*GPAC_DISABLE_3D*/