Vertex Paint: apply when cursor isn't over faces

This behavior makes more sense for sculpt, less so for painting.
Restores non PBVH behavior, adding `BKE_pbvh_find_nearest_to_ray` -
similar to ray-cast except it finds the closest point on the surface.

5 files changed, 368 insertions, 0 deletions

diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h
index 08959e79740..c6b9b6a4de6 100644
--- a/source/blender/blenkernel/BKE_pbvh.h
+++ b/source/blender/blenkernel/BKE_pbvh.h
@@ -59,6 +59,8 @@ typedef bool (*BKE_pbvh_SearchCallback)(PBVHNode *node, void *data);
 typedef void (*BKE_pbvh_HitCallback)(PBVHNode *node, void *data);
 typedef void (*BKE_pbvh_HitOccludedCallback)(PBVHNode *node, void *data, float *tmin);
 
+typedef void (*BKE_pbvh_SearchNearestCallback)(PBVHNode *node, void *data, float *tmin);
+
 /* Building */
 
 PBVH *BKE_pbvh_new(void);
@@ -114,6 +116,16 @@ void BKE_pbvh_raycast_project_ray_root(
         PBVH *bvh, bool original,
         float ray_start[3], float ray_end[3], float ray_normal[3]);
 
+void BKE_pbvh_find_nearest_to_ray(
+        PBVH *bvh, BKE_pbvh_HitOccludedCallback cb, void *data,
+        const float ray_start[3], const float ray_normal[3],
+        bool original);
+
+bool BKE_pbvh_node_find_nearest_to_ray(
+        PBVH *bvh, PBVHNode *node, float (*origco)[3], bool use_origco,
+        const float ray_start[3], const float ray_normal[3],
+        float *depth, float *dist_sq);
+
 /* Drawing */
 
 void BKE_pbvh_node_draw(PBVHNode *node, void *data);
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c
index bc93aa5678a..9b6c5f05a3d 100644
--- a/source/blender/blenkernel/intern/pbvh.c
+++ b/source/blender/blenkernel/intern/pbvh.c
@@ -1572,6 +1572,74 @@ bool ray_face_intersection_tri(
 	}
 }
 
+/* Take advantage of the fact we know this wont be an intersection.
+ * Just handle ray-tri edges. */
+static float dist_squared_ray_to_tri_v3_fast(
+        const float ray_origin[3], const float ray_direction[3],
+        const float v0[3], const float v1[3], const float v2[3],
+        float r_point[3], float *r_depth)
+{
+	const float *tri[3] = {v0, v1, v2};
+	float dist_sq_best = FLT_MAX;
+	for (int i = 0, j = 2; i < 3; j = i++) {
+		float point_test[3], depth_test = FLT_MAX;
+		const float dist_sq_test = dist_squared_ray_to_seg_v3(
+		        ray_origin, ray_direction, tri[i], tri[j], point_test, &depth_test);
+		if (dist_sq_test < dist_sq_best || i == 0) {
+			copy_v3_v3(r_point, point_test);
+			*r_depth = depth_test;
+			dist_sq_best = dist_sq_test;
+		}
+	}
+	return dist_sq_best;
+}
+
+bool ray_face_nearest_quad(
+        const float ray_start[3], const float ray_normal[3],
+        const float t0[3], const float t1[3], const float t2[3], const float t3[3],
+        float *depth, float *dist_sq)
+{
+	float dist_sq_test;
+	float co[3], depth_test;
+
+	if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
+	         ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq))
+	{
+		*dist_sq = dist_sq_test;
+		*depth = depth_test;
+		if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
+		         ray_start, ray_normal, t0, t2, t3, co, &depth_test)) < *dist_sq))
+		{
+			*dist_sq = dist_sq_test;
+			*depth = depth_test;
+		}
+		return true;
+	}
+	else {
+		return false;
+	}
+}
+
+bool ray_face_nearest_tri(
+        const float ray_start[3], const float ray_normal[3],
+        const float t0[3], const float t1[3], const float t2[3],
+        float *depth, float *dist_sq)
+{
+	float dist_sq_test;
+	float co[3], depth_test;
+
+	if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
+	         ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq))
+	{
+		*dist_sq = dist_sq_test;
+		*depth = depth_test;
+		return true;
+	}
+	else {
+		return false;
+	}
+}
+
 static bool pbvh_faces_node_raycast(
         PBVH *bvh, const PBVHNode *node,
         float (*origco)[3],
@@ -1743,6 +1811,176 @@ void BKE_pbvh_raycast_project_ray_root(
 	}
 }
 
+/* -------------------------------------------------------------------- */
+
+typedef struct {
+	struct DistRayAABB_Precalc dist_ray_to_aabb_precalc;
+	bool original;
+} FindNearestRayData;
+
+static bool nearest_to_ray_aabb_dist_sq(PBVHNode *node, void *data_v)
+{
+	FindNearestRayData *rcd = data_v;
+	const float *bb_min, *bb_max;
+
+	if (rcd->original) {
+		/* BKE_pbvh_node_get_original_BB */
+		bb_min = node->orig_vb.bmin;
+		bb_max = node->orig_vb.bmax;
+	}
+	else {
+		/* BKE_pbvh_node_get_BB */
+		bb_min = node->vb.bmin;
+		bb_max = node->vb.bmax;
+	}
+
+	float co_dummy[3], depth;
+	node->tmin = dist_squared_ray_to_aabb(&rcd->dist_ray_to_aabb_precalc, bb_min, bb_max, co_dummy, &depth);
+	/* Ideally we would skip distances outside the range. */
+	return depth > 0.0f;
+}
+
+void BKE_pbvh_find_nearest_to_ray(
+        PBVH *bvh, BKE_pbvh_SearchNearestCallback cb, void *data,
+        const float ray_start[3], const float ray_normal[3],
+        bool original)
+{
+	FindNearestRayData ncd;
+
+	dist_squared_ray_to_aabb_precalc(&ncd.dist_ray_to_aabb_precalc, ray_start, ray_normal);
+	ncd.original = original;
+
+	BKE_pbvh_search_callback_occluded(bvh, nearest_to_ray_aabb_dist_sq, &ncd, cb, data);
+}
+
+
+static bool pbvh_faces_node_nearest_to_ray(
+        PBVH *bvh, const PBVHNode *node,
+        float (*origco)[3],
+        const float ray_start[3], const float ray_normal[3],
+        float *depth, float *dist_sq)
+{
+	const MVert *vert = bvh->verts;
+	const MLoop *mloop = bvh->mloop;
+	const int *faces = node->prim_indices;
+	int i, totface = node->totprim;
+	bool hit = false;
+
+	for (i = 0; i < totface; ++i) {
+		const MLoopTri *lt = &bvh->looptri[faces[i]];
+		const int *face_verts = node->face_vert_indices[i];
+
+		if (paint_is_face_hidden(lt, vert, mloop))
+			continue;
+
+		if (origco) {
+			/* intersect with backuped original coordinates */
+			hit |= ray_face_nearest_tri(
+			        ray_start, ray_normal,
+			        origco[face_verts[0]],
+			        origco[face_verts[1]],
+			        origco[face_verts[2]],
+			        depth, dist_sq);
+		}
+		else {
+			/* intersect with current coordinates */
+			hit |= ray_face_nearest_tri(
+			        ray_start, ray_normal,
+			        vert[mloop[lt->tri[0]].v].co,
+			        vert[mloop[lt->tri[1]].v].co,
+			        vert[mloop[lt->tri[2]].v].co,
+			        depth, dist_sq);
+		}
+	}
+
+	return hit;
+}
+
+static bool pbvh_grids_node_nearest_to_ray(
+        PBVH *bvh, PBVHNode *node,
+        float (*origco)[3],
+        const float ray_start[3], const float ray_normal[3],
+        float *depth, float *dist_sq)
+{
+	const int totgrid = node->totprim;
+	const int gridsize = bvh->gridkey.grid_size;
+	bool hit = false;
+
+	for (int i = 0; i < totgrid; ++i) {
+		CCGElem *grid = bvh->grids[node->prim_indices[i]];
+		BLI_bitmap *gh;
+
+		if (!grid)
+			continue;
+
+		gh = bvh->grid_hidden[node->prim_indices[i]];
+
+		for (int y = 0; y < gridsize - 1; ++y) {
+			for (int x = 0; x < gridsize - 1; ++x) {
+				/* check if grid face is hidden */
+				if (gh) {
+					if (paint_is_grid_face_hidden(gh, gridsize, x, y))
+						continue;
+				}
+
+				if (origco) {
+					hit |= ray_face_nearest_quad(
+					        ray_start, ray_normal,
+					        origco[y * gridsize + x],
+					        origco[y * gridsize + x + 1],
+					        origco[(y + 1) * gridsize + x + 1],
+					        origco[(y + 1) * gridsize + x],
+					        depth, dist_sq);
+				}
+				else {
+					hit |= ray_face_nearest_quad(
+					        ray_start, ray_normal,
+					        CCG_grid_elem_co(&bvh->gridkey, grid, x, y),
+					        CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y),
+					        CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y + 1),
+					        CCG_grid_elem_co(&bvh->gridkey, grid, x, y + 1),
+					        depth, dist_sq);
+				}
+			}
+		}
+
+		if (origco)
+			origco += gridsize * gridsize;
+	}
+
+	return hit;
+}
+
+bool BKE_pbvh_node_find_nearest_to_ray(
+        PBVH *bvh, PBVHNode *node, float (*origco)[3], bool use_origco,
+        const float ray_start[3], const float ray_normal[3],
+        float *depth, float *dist_sq)
+{
+	bool hit = false;
+
+	if (node->flag & PBVH_FullyHidden)
+		return false;
+
+	switch (bvh->type) {
+		case PBVH_FACES:
+			hit |= pbvh_faces_node_nearest_to_ray(
+			        bvh, node, origco,
+			        ray_start, ray_normal, depth, dist_sq);
+			break;
+		case PBVH_GRIDS:
+			hit |= pbvh_grids_node_nearest_to_ray(
+			        bvh, node, origco,
+			        ray_start, ray_normal, depth, dist_sq);
+			break;
+		case PBVH_BMESH:
+			hit = pbvh_bmesh_node_nearest_to_ray(
+			        node, ray_start, ray_normal, depth, dist_sq, use_origco);
+			break;
+	}
+
+	return hit;
+}
+
 typedef struct {
 	DMSetMaterial setMaterial;
 	bool wireframe;
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
index 529dfae05e2..4bfda8ebf28 100644
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@ -1554,6 +1554,47 @@ bool BKE_pbvh_bmesh_node_raycast_detail(
 	return hit;
 }
 
+bool pbvh_bmesh_node_nearest_to_ray(
+        PBVHNode *node, const float ray_start[3],
+        const float ray_normal[3], float *depth, float *dist_sq,
+        bool use_original)
+{
+	bool hit = false;
+
+	if (use_original && node->bm_tot_ortri) {
+		for (int i = 0; i < node->bm_tot_ortri; i++) {
+			const int *t = node->bm_ortri[i];
+			hit |= ray_face_nearest_tri(
+			        ray_start, ray_normal,
+			        node->bm_orco[t[0]],
+			        node->bm_orco[t[1]],
+			        node->bm_orco[t[2]],
+			        depth, dist_sq);
+		}
+	}
+	else {
+		GSetIterator gs_iter;
+
+		GSET_ITER (gs_iter, node->bm_faces) {
+			BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
+
+			BLI_assert(f->len == 3);
+			if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
+				BMVert *v_tri[3];
+
+				BM_face_as_array_vert_tri(f, v_tri);
+				hit |= ray_face_nearest_tri(
+				        ray_start, ray_normal,
+				        v_tri[0]->co,
+				        v_tri[1]->co,
+				        v_tri[2]->co,
+				        depth, dist_sq);
+			}
+		}
+	}
+
+	return hit;
+}
 
 void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode)
 {
diff --git a/source/blender/blenkernel/intern/pbvh_intern.h b/source/blender/blenkernel/intern/pbvh_intern.h
index 7d75930b3c6..e05a3068682 100644
--- a/source/blender/blenkernel/intern/pbvh_intern.h
+++ b/source/blender/blenkernel/intern/pbvh_intern.h
@@ -190,6 +190,16 @@ bool ray_face_intersection_tri(
         const float ray_start[3], const float ray_normal[3],
         const float *t0, const float *t1, const float *t2,
         float *depth);
+
+bool ray_face_nearest_quad(
+        const float ray_start[3], const float ray_normal[3],
+        const float *t0, const float *t1, const float *t2, const float *t3,
+        float *r_depth, float *r_dist_sq);
+bool ray_face_nearest_tri(
+        const float ray_start[3], const float ray_normal[3],
+        const float *t0, const float *t1, const float *t2,
+        float *r_depth, float *r_dist_sq);
+
 void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes, int totnode, int flag);
 
 /* pbvh_bmesh.c */
@@ -197,6 +207,10 @@ bool pbvh_bmesh_node_raycast(
         PBVHNode *node, const float ray_start[3],
         const float ray_normal[3], float *dist,
         bool use_original);
+bool pbvh_bmesh_node_nearest_to_ray(
+        PBVHNode *node, const float ray_start[3],
+        const float ray_normal[3], float *depth, float *dist_sq,
+        bool use_original);
 
 void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode);
 
diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c
index 1bff1f460ea..f74ac68262f 100644
--- a/source/blender/editors/sculpt_paint/sculpt.c
+++ b/source/blender/editors/sculpt_paint/sculpt.c
@@ -1549,6 +1549,15 @@ typedef struct {
 	float detail;
 } SculptDetailRaycastData;
 
+typedef struct {
+	SculptSession *ss;
+	const float *ray_start, *ray_normal;
+	bool hit;
+	float depth;
+	float dist_sq_to_ray;
+	bool original;
+} SculptFindNearestToRayData;
+
 static void do_smooth_brush_mesh_task_cb_ex(
         void *userdata, void *UNUSED(userdata_chunk), const int n, const int thread_id)
 {
@@ -4330,6 +4339,36 @@ static void sculpt_raycast_cb(PBVHNode *node, void *data_v, float *tmin)
 	}
 }
 
+static void sculpt_find_nearest_to_ray_cb(PBVHNode *node, void *data_v, float *tmin)
+{
+	if (BKE_pbvh_node_get_tmin(node) < *tmin) {
+		SculptFindNearestToRayData *srd = data_v;
+		float (*origco)[3] = NULL;
+		bool use_origco = false;
+
+		if (srd->original && srd->ss->cache) {
+			if (BKE_pbvh_type(srd->ss->pbvh) == PBVH_BMESH) {
+				use_origco = true;
+			}
+			else {
+				/* intersect with coordinates from before we started stroke */
+				SculptUndoNode *unode = sculpt_undo_get_node(node);
+				origco = (unode) ? unode->co : NULL;
+				use_origco = origco ? true : false;
+			}
+		}
+
+		if (BKE_pbvh_node_find_nearest_to_ray(
+		        srd->ss->pbvh, node, origco, use_origco,
+		        srd->ray_start, srd->ray_normal,
+		        &srd->depth, &srd->dist_sq_to_ray))
+		{
+			srd->hit = 1;
+			*tmin = srd->dist_sq_to_ray;
+		}
+	}
+}
+
 static void sculpt_raycast_detail_cb(PBVHNode *node, void *data_v, float *tmin)
 {
 	if (BKE_pbvh_node_get_tmin(node) < *tmin) {
@@ -4422,6 +4461,30 @@ bool sculpt_stroke_get_location(bContext *C, float out[3], const float mouse[2])
 		}
 	}
 
+	/* We may want to move this into a brush option, it could be useful in sculpt mode too. */
+	const bool use_nearest = ((ob->mode & (OB_MODE_VERTEX_PAINT | OB_MODE_WEIGHT_PAINT)) != 0);
+
+	if (hit == false && use_nearest) {
+		SculptFindNearestToRayData srd = {
+			.original = original,
+			.ss = ob->sculpt,
+			.hit = 0,
+			.ray_start = ray_start,
+			.ray_normal = ray_normal,
+			.depth = FLT_MAX,
+			.dist_sq_to_ray = FLT_MAX,
+		};
+		BKE_pbvh_find_nearest_to_ray(
+		        ss->pbvh, sculpt_find_nearest_to_ray_cb, &srd,
+		        ray_start, ray_normal, srd.original);
+		if (srd.hit) {
+			hit = true;
+			copy_v3_v3(out, ray_normal);
+			mul_v3_fl(out, srd.depth);
+			add_v3_v3(out, ray_start);
+		}
+	}
+
 	//used in vwpaint
 	if (cache && hit){
 		copy_v3_v3(cache->true_location, out);