mesh_collide.c

一个用于智能手机的多媒体库适合S60 WinCE的跨平台开发库

/*
 *			GPAC - Multimedia Framework C SDK
 *
 *			Copyright (c) Jean Le Feuvre 2000-2005
 *					All rights reserved
 *
 *  This file is part of GPAC / 3D rendering module
 *
 *  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 "mesh.h"


/*
	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;

	/*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 = 1;

	gf_vec_diff(extend, node->max, node->max);
	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 = 0;
		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 = 1;
		}
	}
	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 = 0;
	}

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

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

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

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

	GF_SAFEALLOC(mesh->aabb_root, AABBNode);
	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_RENDER, ("[Render 3D] 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 0;
	
	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;

	}