[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [16006] trunk/blender/source/blender: BVH-KDOP update (merge from shrinkwrap branch): supports raytracing, nearest neighbour, non-recursive now, faster than kdtree. c implementation normaly, divided into 2 sources: generla structure in blenlib, mesh/ derivedmesh depending interface stuff in blenkernel

Daniel Genrich daniel.genrich at gmx.net
Thu Aug 7 19:27:29 CEST 2008


Revision: 16006
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16006
Author:   genscher
Date:     2008-08-07 19:27:29 +0200 (Thu, 07 Aug 2008)

Log Message:
-----------
BVH-KDOP update (merge from shrinkwrap branch): supports raytracing, nearest neighbour, non-recursive now, faster than kdtree.c implementation normaly, divided into 2 sources: generla structure in blenlib, mesh/derivedmesh depending interface stuff in blenkernel

Modified Paths:
--------------
    trunk/blender/source/blender/blenlib/BLI_kdopbvh.h
    trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c

Added Paths:
-----------
    trunk/blender/source/blender/blenkernel/BKE_bvhutils.h
    trunk/blender/source/blender/blenkernel/intern/bvhutils.c

Added: trunk/blender/source/blender/blenkernel/BKE_bvhutils.h
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_bvhutils.h	                        (rev 0)
+++ trunk/blender/source/blender/blenkernel/BKE_bvhutils.h	2008-08-07 17:27:29 UTC (rev 16006)
@@ -0,0 +1,98 @@
+/**
+ *
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2006 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef BKE_BVHUTILS_H
+#define BKE_BVHUTILS_H
+
+#include "BLI_kdopbvh.h"
+
+/*
+ * This header encapsulates necessary code to buld a BVH
+ */
+
+struct DerivedMesh;
+struct MVert;
+struct MFace;
+
+/*
+ * struct that kepts basic information about a BVHTree build from a mesh
+ */
+typedef struct BVHTreeFromMesh
+{
+	struct BVHTree *tree;
+
+	/* default callbacks to bvh nearest and raycast */
+	BVHTree_NearestPointCallback nearest_callback;
+	BVHTree_RayCastCallback      raycast_callback;
+
+	/* Mesh represented on this BVHTree */
+	struct DerivedMesh *mesh; 
+
+	/* Vertex array, so that callbacks have instante access to data */
+	struct MVert *vert;
+	struct MFace *face;
+
+	/* radius for raycast */
+	float sphere_radius;
+
+} BVHTreeFromMesh;
+
+/*
+ * Builds a bvh tree where nodes are the vertexs of the given mesh.
+ * Configures BVHTreeFromMesh.
+ *
+ * The tree is build in mesh space coordinates, this means special care must be made on queries
+ * so that the coordinates and rays are first translated on the mesh local coordinates.
+ * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becames possible to reuse
+ * a BVHTree.
+ * 
+ * free_bvhtree_from_mesh should be called when the tree is no longer needed.
+ */
+void bvhtree_from_mesh_verts(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+
+/*
+ * Builds a bvh tree where nodes are the faces of the given mesh.
+ * Configures BVHTreeFromMesh.
+ *
+ * The tree is build in mesh space coordinates, this means special care must be made on queries
+ * so that the coordinates and rays are first translated on the mesh local coordinates.
+ * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becames possible to reuse
+ * a BVHTree.
+ * 
+ * free_bvhtree_from_mesh should be called when the tree is no longer needed.
+ */
+void bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+
+/*
+ * Frees data allocated by a call to bvhtree_from_mesh_*.
+ */
+void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data);
+
+#endif
+

Added: trunk/blender/source/blender/blenkernel/intern/bvhutils.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/bvhutils.c	                        (rev 0)
+++ trunk/blender/source/blender/blenkernel/intern/bvhutils.c	2008-08-07 17:27:29 UTC (rev 16006)
@@ -0,0 +1,426 @@
+/**
+ *
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+#include "BKE_bvhutils.h"
+
+#include "DNA_object_types.h"
+#include "DNA_modifier_types.h"
+#include "DNA_meshdata_types.h"
+
+#include "BKE_DerivedMesh.h"
+#include "BKE_utildefines.h"
+#include "BKE_deform.h"
+#include "BKE_cdderivedmesh.h"
+#include "BKE_displist.h"
+#include "BKE_global.h"
+
+#include "BLI_arithb.h"
+
+/* Math stuff for ray casting on mesh faces and for nearest surface */
+
+static float nearest_point_in_tri_surface(const float *point, const float *v0, const float *v1, const float *v2, float *nearest);
+
+#define ISECT_EPSILON 1e-6
+static float ray_tri_intersection(const BVHTreeRay *ray, const float m_dist, const float *v0, const float *v1, const float *v2)
+{
+	float dist;
+
+	if(RayIntersectsTriangle(ray->origin, ray->direction, v0, v1, v2, &dist, NULL))
+		return dist;
+
+	return FLT_MAX;
+}
+
+static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, const float m_dist, const float *v0, const float *v1, const float *v2)
+{
+	
+	float idist;
+	float p1[3];
+	float plane_normal[3], hit_point[3];
+
+	CalcNormFloat((float*)v0, (float*)v1, (float*)v2, plane_normal);
+
+	VECADDFAC( p1, ray->origin, ray->direction, m_dist);
+	if(SweepingSphereIntersectsTriangleUV(ray->origin, p1, radius, v0, v1, v2, &idist, &hit_point))
+	{
+		return idist * m_dist;
+	}
+
+	return FLT_MAX;
+}
+
+/*
+ * This calculates the distance from point to the plane
+ * Distance is negative if point is on the back side of plane
+ */
+static float point_plane_distance(const float *point, const float *plane_point, const float *plane_normal)
+{
+	float pp[3];
+	VECSUB(pp, point, plane_point);
+	return INPR(pp, plane_normal);
+}
+static float choose_nearest(const float v0[2], const float v1[2], const float point[2], float closest[2])
+{
+	float d[2][2], sdist[2];
+	VECSUB2D(d[0], v0, point);
+	VECSUB2D(d[1], v1, point);
+
+	sdist[0] = d[0][0]*d[0][0] + d[0][1]*d[0][1];
+	sdist[1] = d[1][0]*d[1][0] + d[1][1]*d[1][1];
+
+	if(sdist[0] < sdist[1])
+	{
+		if(closest)
+			VECCOPY2D(closest, v0);
+		return sdist[0];
+	}
+	else
+	{
+		if(closest)
+			VECCOPY2D(closest, v1);
+		return sdist[1];
+	}
+}
+/*
+ * calculates the closest point between point-tri (2D)
+ * returns that tri must be right-handed
+ * Returns square distance
+ */
+static float closest_point_in_tri2D(const float point[2], /*const*/ float tri[3][2], float closest[2])
+{
+	float edge_di[2];
+	float v_point[2];
+	float proj[2];					//point projected over edge-dir, edge-normal (witouth normalized edge)
+	const float *v0 = tri[2], *v1;
+	float edge_slen, d;				//edge squared length
+	int i;
+	const float *nearest_vertex = NULL;
+
+
+	//for each edge
+	for(i=0, v0=tri[2], v1=tri[0]; i < 3; v0=tri[i++], v1=tri[i])
+	{
+		VECSUB2D(edge_di,    v1, v0);
+		VECSUB2D(v_point, point, v0);
+
+		proj[1] =  v_point[0]*edge_di[1] - v_point[1]*edge_di[0];	//dot product with edge normal
+
+		//point inside this edge
+		if(proj[1] < 0)
+			continue;
+
+		proj[0] = v_point[0]*edge_di[0] + v_point[1]*edge_di[1];
+
+		//closest to this edge is v0
+		if(proj[0] < 0)
+		{
+			if(nearest_vertex == NULL || nearest_vertex == v0)
+				nearest_vertex = v0;
+			else
+			{
+				//choose nearest
+				return choose_nearest(nearest_vertex, v0, point, closest);
+			}
+			i++;	//We can skip next edge
+			continue;
+		}
+
+		edge_slen = edge_di[0]*edge_di[0] + edge_di[1]*edge_di[1];	//squared edge len
+		//closest to this edge is v1
+		if(proj[0] > edge_slen)
+		{
+			if(nearest_vertex == NULL || nearest_vertex == v1)
+				nearest_vertex = v1;
+			else
+			{
+				return choose_nearest(nearest_vertex, v1, point, closest);
+			}
+			continue;
+		}
+
+		//nearest is on this edge
+		d= proj[1] / edge_slen;
+		closest[0] = point[0] - edge_di[1] * d;
+		closest[1] = point[1] + edge_di[0] * d;
+
+		return proj[1]*proj[1]/edge_slen;
+	}
+
+	if(nearest_vertex)
+	{
+		VECSUB2D(v_point, nearest_vertex, point);
+		VECCOPY2D(closest, nearest_vertex);
+		return v_point[0]*v_point[0] + v_point[1]*v_point[1];
+	}
+	else
+	{
+		VECCOPY(closest, point);	//point is already inside
+		return 0.0f;
+	}
+}
+
+/*
+ * Returns the square of the minimum distance between the point and a triangle surface
+ * If nearest is not NULL the nearest surface point is written on it
+ */
+static float nearest_point_in_tri_surface(const float *point, const float *v0, const float *v1, const float *v2, float *nearest)
+{
+	//Lets solve the 2D problem (closest point-tri)
+	float normal_dist, plane_sdist, plane_offset;
+	float du[3], dv[3], dw[3];	//orthogonal axis (du=(v0->v1), dw=plane normal)
+
+	float p_2d[2], tri_2d[3][2], nearest_2d[2];
+
+	CalcNormFloat((float*)v0, (float*)v1, (float*)v2, dw);
+
+	//point-plane distance and calculate axis
+	normal_dist = point_plane_distance(point, v0, dw);
+
+	// OPTIMIZATION
+	//	if we are only interested in nearest distance if its closer than some distance already found
+	//  we can:
+	//		if(normal_dist*normal_dist >= best_dist_so_far) return FLOAT_MAX;
+	//
+
+	VECSUB(du, v1, v0);
+	Normalize(du);
+	Crossf(dv, dw, du);
+	plane_offset = INPR(v0, dw);
+
+	//project stuff to 2d
+	tri_2d[0][0] = INPR(du, v0);
+	tri_2d[0][1] = INPR(dv, v0);
+
+	tri_2d[1][0] = INPR(du, v1);
+	tri_2d[1][1] = INPR(dv, v1);
+
+	tri_2d[2][0] = INPR(du, v2);
+	tri_2d[2][1] = INPR(dv, v2);
+
+	p_2d[0] = INPR(du, point);
+	p_2d[1] = INPR(dv, point);
+
+	//we always have a right-handed tri
+	//this should always happen because of the way normal is calculated
+	plane_sdist = closest_point_in_tri2D(p_2d, tri_2d, nearest_2d);
+
+	//project back to 3d
+	if(nearest)
+	{

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list