[Bf-blender-cvs] [f61f7e2] strand_gpu: Generic raycast method for generating mesh surface samples.

Lukas Tönne noreply at git.blender.org
Tue Jul 5 09:56:33 CEST 2016


Commit: f61f7e2d579348b7509390cc1d368e04f91a8964
Author: Lukas Tönne
Date:   Sun Nov 30 15:52:05 2014 +0100
Branches: strand_gpu
https://developer.blender.org/rBf61f7e2d579348b7509390cc1d368e04f91a8964

Generic raycast method for generating mesh surface samples.

===================================================================

M	source/blender/blenkernel/BKE_mesh_sample.h
M	source/blender/blenkernel/intern/mesh_sample.c
M	source/blender/blenlib/BLI_math_geom.h
M	source/blender/blenlib/intern/math_geom.c

===================================================================

diff --git a/source/blender/blenkernel/BKE_mesh_sample.h b/source/blender/blenkernel/BKE_mesh_sample.h
index fa747c7..0fdc0b7 100644
--- a/source/blender/blenkernel/BKE_mesh_sample.h
+++ b/source/blender/blenkernel/BKE_mesh_sample.h
@@ -50,6 +50,9 @@ typedef struct MSurfaceSampleStorage {
 void BKE_mesh_sample_storage_array(struct MSurfaceSampleStorage *storage, struct MSurfaceSample *samples, int capacity);
 void BKE_mesh_sample_storage_release(struct MSurfaceSampleStorage *storage);
 
-void BKE_mesh_sample_generate_random(MSurfaceSampleStorage *dst, struct DerivedMesh *dm, unsigned int seed, int totsample);
+void BKE_mesh_sample_generate_random(struct MSurfaceSampleStorage *dst, struct DerivedMesh *dm, unsigned int seed, int totsample);
+
+typedef bool (*MeshSampleRayCallback)(void *userdata, float ray_start[3], float ray_end[3]);
+void BKE_mesh_sample_generate_raycast(struct MSurfaceSampleStorage *dst, struct DerivedMesh *dm, MeshSampleRayCallback ray_cb, void *userdata);
 
 #endif  /* __BKE_MESH_SAMPLE_H__ */
diff --git a/source/blender/blenkernel/intern/mesh_sample.c b/source/blender/blenkernel/intern/mesh_sample.c
index 8fb564b..d2391ba 100644
--- a/source/blender/blenkernel/intern/mesh_sample.c
+++ b/source/blender/blenkernel/intern/mesh_sample.c
@@ -34,6 +34,7 @@
 #include "BLI_math.h"
 #include "BLI_rand.h"
 
+#include "BKE_bvhutils.h"
 #include "BKE_mesh_sample.h"
 #include "BKE_customdata.h"
 #include "BKE_DerivedMesh.h"
@@ -99,6 +100,31 @@ bool BKE_mesh_sample_shapekey(Key *key, KeyBlock *kb, const MSurfaceSample *samp
 }
 
 
+/* ==== Sampling Utilities ==== */
+
+BLI_INLINE void mesh_sample_weights_from_loc(MSurfaceSample *sample, DerivedMesh *dm, int face_index, const float loc[3])
+{
+	MFace *face = &dm->getTessFaceArray(dm)[face_index];
+	unsigned int index[4] = { face->v1, face->v2, face->v3, face->v4 };
+	MVert *mverts = dm->getVertArray(dm);
+	
+	float *v1 = mverts[face->v1].co;
+	float *v2 = mverts[face->v2].co;
+	float *v3 = mverts[face->v3].co;
+	float *v4 = face->v4 ? mverts[face->v4].co : NULL;
+	float w[4];
+	int tri[3];
+	
+	interp_weights_face_v3_index(tri, w, v1, v2, v3, v4, loc);
+	
+	sample->orig_verts[0] = index[tri[0]];
+	sample->orig_verts[1] = index[tri[1]];
+	sample->orig_verts[2] = index[tri[2]];
+	sample->orig_weights[0] = w[tri[0]];
+	sample->orig_weights[1] = w[tri[1]];
+	sample->orig_weights[2] = w[tri[2]];
+}
+
 /* ==== Sampling ==== */
 
 static bool mesh_sample_store_array_sample(void *vdata, int capacity, int index, const MSurfaceSample *sample)
@@ -173,3 +199,54 @@ void BKE_mesh_sample_generate_random(MSurfaceSampleStorage *dst, DerivedMesh *dm
 	
 	BLI_rng_free(rng);
 }
+
+
+static bool sample_bvh_raycast(MSurfaceSample *sample, DerivedMesh *dm, BVHTreeFromMesh *bvhdata, const float ray_start[3], const float ray_end[3])
+{
+	BVHTreeRayHit hit;
+	float ray_normal[3], dist;
+
+	sub_v3_v3v3(ray_normal, ray_end, ray_start);
+	dist = normalize_v3(ray_normal);
+	
+	hit.index = -1;
+	hit.dist = dist;
+
+	if (BLI_bvhtree_ray_cast(bvhdata->tree, ray_start, ray_normal, 0.0f,
+	                         &hit, bvhdata->raycast_callback, bvhdata) >= 0) {
+		
+		mesh_sample_weights_from_loc(sample, dm, hit.index, hit.co);
+		
+		return true;
+	}
+	else
+		return false;
+}
+
+void BKE_mesh_sample_generate_raycast(MSurfaceSampleStorage *dst, DerivedMesh *dm, MeshSampleRayCallback ray_cb, void *userdata)
+{
+	BVHTreeFromMesh bvhdata;
+	float ray_start[3], ray_end[3];
+	int i;
+	
+	DM_ensure_tessface(dm);
+	
+	memset(&bvhdata, 0, sizeof(BVHTreeFromMesh));
+	bvhtree_from_mesh_faces(&bvhdata, dm, 0.0f, 4, 6);
+	
+	if (bvhdata.tree) {
+		i = 0;
+		while (ray_cb(userdata, ray_start, ray_end)) {
+			MSurfaceSample sample;
+			
+			sample_bvh_raycast(&sample, dm, &bvhdata, ray_start, ray_end);
+			
+			if (!dst->store_sample(dst->data, dst->capacity, i, &sample))
+				break;
+			
+			++i;
+		}
+	}
+	
+	free_bvhtree_from_mesh(&bvhdata);
+}
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index ba32b29..24d5527 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -212,6 +212,8 @@ void fill_poly_v2i_n(
 /* tri or quad, d can be NULL */
 void interp_weights_face_v3(float w[4],
                             const float a[3], const float b[3], const float c[3], const float d[3], const float p[3]);
+/* also returns three indices of the triangle actually used */
+void interp_weights_face_v3_index(int tri[3], float w[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3], const float co[3]);
 void interp_weights_poly_v3(float w[], float v[][3], const int n, const float co[3]);
 void interp_weights_poly_v2(float w[], float v[][2], const int n, const float co[2]);
 
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index 6037345..69603c8 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -2310,6 +2310,71 @@ void interp_weights_face_v3(float w[4], const float v1[3], const float v2[3], co
 	}
 }
 
+void interp_weights_face_v3_index(int tri[3], float w[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3], const float co[3])
+{
+	float w2[3];
+
+	w[0] = w[1] = w[2] = w[3] = 0.0f;
+	tri[0] = tri[1] = tri[2] = -1;
+
+	/* first check for exact match */
+	if (equals_v3v3(co, v1)) {
+		w[0] = 1.0f;
+		tri[0] = 0; tri[1] = 1; tri[2] = 3;
+	}
+	else if (equals_v3v3(co, v2)) {
+		w[1] = 1.0f;
+		tri[0] = 0; tri[1] = 1; tri[2] = 3;
+	}
+	else if (equals_v3v3(co, v3)) {
+		w[2] = 1.0f;
+		tri[0] = 1; tri[1] = 2; tri[2] = 3;
+	}
+	else if (v4 && equals_v3v3(co, v4)) {
+		w[3] = 1.0f;
+		tri[0] = 1; tri[1] = 2; tri[2] = 3;
+	}
+	else {
+		/* otherwise compute barycentric interpolation weights */
+		float n1[3], n2[3], n[3];
+		bool degenerate;
+
+		sub_v3_v3v3(n1, v1, v3);
+		if (v4) {
+			sub_v3_v3v3(n2, v2, v4);
+		}
+		else {
+			sub_v3_v3v3(n2, v2, v3);
+		}
+		cross_v3_v3v3(n, n1, n2);
+
+		/* OpenGL seems to split this way, so we do too */
+		if (v4) {
+			degenerate = barycentric_weights(v1, v2, v4, co, n, w);
+			SWAP(float, w[2], w[3]);
+			tri[0] = 0; tri[1] = 1; tri[2] = 3;
+
+			if (degenerate || (w[0] < 0.0f)) {
+				/* if w[1] is negative, co is on the other side of the v1-v3 edge,
+				 * so we interpolate using the other triangle */
+				degenerate = barycentric_weights(v2, v3, v4, co, n, w2);
+
+				if (!degenerate) {
+					w[0] = 0.0f;
+					w[1] = w2[0];
+					w[2] = w2[1];
+					w[3] = w2[2];
+					tri[0] = 1; tri[1] = 2; tri[2] = 3;
+				}
+			}
+		}
+		else {
+			barycentric_weights(v1, v2, v3, co, n, w);
+			tri[0] = 0; tri[1] = 1; tri[2] = 2;
+		}
+	}
+}
+
 /* return 1 of point is inside triangle, 2 if it's on the edge, 0 if point is outside of triangle */
 int barycentric_inside_triangle_v2(const float w[3])
 {




More information about the Bf-blender-cvs mailing list