[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [29098] branches/soc-2010-jwilkins/source/ blender: * doubled strength of clay brush
Jason Wilkins
Jason.A.Wilkins at gmail.com
Mon May 31 07:46:16 CEST 2010
Revision: 29098
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=29098
Author: jwilkins
Date: 2010-05-31 07:46:16 +0200 (Mon, 31 May 2010)
Log Message:
-----------
* doubled strength of clay brush
* tweaked isect_ray_tri_epsilon_v3 (only does second cross product if result is needed, which is rare, according to profile)
* simplified ray_face_intersection
* tweaked isect_line_tri_v3 and isect_ray_tri_v3 eliminate cases in the same order as isect_ray_tri_epsilon_v3, they are nearly the same now, should consider unifying
* changed raycasting of brush location to search bounding box tree from the top down instead of bottom up
* Raycasting of brush location now sorts all bounding volumes by distance and skips any that are further away than the closest result so far. In my testing this meant that for most cases only one node was ever raycast in detail. The others in the line of the ray were eliminted by distance.
Modified Paths:
--------------
branches/soc-2010-jwilkins/source/blender/blenlib/BLI_pbvh.h
branches/soc-2010-jwilkins/source/blender/blenlib/intern/math_geom.c
branches/soc-2010-jwilkins/source/blender/blenlib/intern/pbvh.c
branches/soc-2010-jwilkins/source/blender/editors/sculpt_paint/sculpt.c
Modified: branches/soc-2010-jwilkins/source/blender/blenlib/BLI_pbvh.h
===================================================================
--- branches/soc-2010-jwilkins/source/blender/blenlib/BLI_pbvh.h 2010-05-31 05:41:30 UTC (rev 29097)
+++ branches/soc-2010-jwilkins/source/blender/blenlib/BLI_pbvh.h 2010-05-31 05:46:16 UTC (rev 29098)
@@ -42,6 +42,7 @@
typedef int (*BLI_pbvh_SearchCallback)(PBVHNode *node, void *data);
typedef void (*BLI_pbvh_HitCallback)(PBVHNode *node, void *data);
+typedef void (*BLI_pbvh_HitOccludedCallback)(PBVHNode *node, void *data, float* tmin);
/* Building */
@@ -70,7 +71,7 @@
it's up to the callback to find the primitive within the leaves that is
hit first */
-void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
+void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data,
float ray_start[3], float ray_normal[3], int original);
int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
float ray_start[3], float ray_normal[3], float *dist);
@@ -106,6 +107,8 @@
void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
+float BLI_pbvh_node_get_tmin(PBVHNode* node);
+
/* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
Modified: branches/soc-2010-jwilkins/source/blender/blenlib/intern/math_geom.c
===================================================================
--- branches/soc-2010-jwilkins/source/blender/blenlib/intern/math_geom.c 2010-05-31 05:41:30 UTC (rev 29097)
+++ branches/soc-2010-jwilkins/source/blender/blenlib/intern/math_geom.c 2010-05-31 05:46:16 UTC (rev 29098)
@@ -62,7 +62,8 @@
n[0]= n1[1]*n2[2]-n1[2]*n2[1];
n[1]= n1[2]*n2[0]-n1[0]*n2[2];
n[2]= n1[0]*n2[1]-n1[1]*n2[0];
- return normalize_v3(n);
+
+ return normalize_v3(n);
}
float normal_quad_v3(float n[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
@@ -82,7 +83,7 @@
n[1]= n1[2]*n2[0]-n1[0]*n2[2];
n[2]= n1[0]*n2[1]-n1[1]*n2[0];
- return normalize_v3(n);
+ return normalize_v3(n);
}
float area_tri_v2(const float v1[2], const float v2[2], const float v3[2])
@@ -401,16 +402,17 @@
sub_v3_v3v3(s, p1, v0);
- cross_v3_v3v3(q, s, e1);
- *lambda = f * dot_v3v3(e2, q);
- if ((*lambda < 0.0)||(*lambda > 1.0)) return 0;
-
u = f * dot_v3v3(s, p);
if ((u < 0.0)||(u > 1.0)) return 0;
- v = f * dot_v3v3(d, q);
+ cross_v3_v3v3(q, s, e1);
+
+ v = f * dot_v3v3(d, q);
if ((v < 0.0)||((u + v) > 1.0)) return 0;
+ *lambda = f * dot_v3v3(e2, q);
+ if ((*lambda < 0.0)||(*lambda > 1.0)) return 0;
+
if(uv) {
uv[0]= u;
uv[1]= v;
@@ -440,17 +442,18 @@
sub_v3_v3v3(s, p1, v0);
- cross_v3_v3v3(q, s, e1);
- *lambda = f * dot_v3v3(e2, q);
- if ((*lambda < 0.0)) return 0;
-
u = f * dot_v3v3(s, p);
if ((u < 0.0)||(u > 1.0)) return 0;
+ cross_v3_v3v3(q, s, e1);
+
v = f * dot_v3v3(d, q);
if ((v < 0.0)||((u + v) > 1.0)) return 0;
- if(uv) {
+ *lambda = f * dot_v3v3(e2, q);
+ if ((*lambda < 0.0)) return 0;
+
+ if(uv) {
uv[0]= u;
uv[1]= v;
}
@@ -458,38 +461,79 @@
return 1;
}
+//int isect_ray_tri_epsilon_v3(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float epsilon)
+//{
+// float p[3], s[3], e1[3], e2[3], q[3];
+// float a, f, t, u, v;
+// float epsilon0, epsilon1;
+//
+// sub_v3_v3v3(e1, v1, v0);
+// sub_v3_v3v3(e2, v2, v0);
+//
+// cross_v3_v3v3(p, d, e2);
+// a = dot_v3v3(e1, p);
+// if (a == 0.0f) return 0;
+//
+// epsilon0 = a * -epsilon;
+// epsilon1 = a + -epsilon0;
+//
+// sub_v3_v3v3(s, p1, v0);
+//
+// u = dot_v3v3(s, p);
+// if ((u < epsilon0)||(u > epsilon1)) return 0;
+//
+// cross_v3_v3v3(q, s, e1);
+//
+// v = dot_v3v3(d, q);
+// if ((v < epsilon0)||((u + v) > epsilon1)) return 0;
+//
+// t = dot_v3v3(e2, q);
+// if ((t < 0.0f)) return 0;
+//
+// f = 1.0f/a;
+//
+// *lambda = f*t;
+//
+// if(uv) {
+// uv[0]= f*u;
+// uv[1]= f*v;
+// }
+//
+// return 1;
+//}
+
int isect_ray_tri_epsilon_v3(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float epsilon)
{
- float p[3], s[3], e1[3], e2[3], q[3];
- float a, f, u, v;
-
- sub_v3_v3v3(e1, v1, v0);
- sub_v3_v3v3(e2, v2, v0);
-
- cross_v3_v3v3(p, d, e2);
- a = dot_v3v3(e1, p);
- if (a == 0.0f) return 0;
- f = 1.0f/a;
-
- sub_v3_v3v3(s, p1, v0);
-
- cross_v3_v3v3(q, s, e1);
+ float p[3], s[3], e1[3], e2[3], q[3];
+ float a, f, u, v;
- u = f * dot_v3v3(s, p);
- if ((u < -epsilon)||(u > 1.0f+epsilon)) return 0;
-
- v = f * dot_v3v3(d, q);
- if ((v < -epsilon)||((u + v) > 1.0f+epsilon)) return 0;
+ sub_v3_v3v3(e1, v1, v0);
+ sub_v3_v3v3(e2, v2, v0);
- *lambda = f * dot_v3v3(e2, q);
- if ((*lambda < 0.0f)) return 0;
+ cross_v3_v3v3(p, d, e2);
+ a = dot_v3v3(e1, p);
+ if (a == 0.0f) return 0;
+ f = 1.0f/a;
- if(uv) {
- uv[0]= u;
- uv[1]= v;
- }
-
- return 1;
+ sub_v3_v3v3(s, p1, v0);
+
+ u = f * dot_v3v3(s, p);
+ if ((u < -epsilon)||(u > 1.0f+epsilon)) return 0;
+
+ cross_v3_v3v3(q, s, e1);
+
+ v = f * dot_v3v3(d, q);
+ if ((v < -epsilon)||((u + v) > 1.0f+epsilon)) return 0;
+
+ *lambda = f * dot_v3v3(e2, q);
+ if ((*lambda < 0.0f)) return 0;
+
+ if(uv) {
+ uv[0]= u;
+ uv[1]= v;
+ }
+
+ return 1;
}
int isect_ray_tri_threshold_v3(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float threshold)
Modified: branches/soc-2010-jwilkins/source/blender/blenlib/intern/pbvh.c
===================================================================
--- branches/soc-2010-jwilkins/source/blender/blenlib/intern/pbvh.c 2010-05-31 05:41:30 UTC (rev 29097)
+++ branches/soc-2010-jwilkins/source/blender/blenlib/intern/pbvh.c 2010-05-31 05:46:16 UTC (rev 29098)
@@ -90,6 +90,8 @@
unsigned int uniq_verts, face_verts;
char flag;
+
+ float tmin;
};
struct PBVH {
@@ -624,13 +626,12 @@
{
PBVHNode *node;
int revisiting;
- void *search_data;
/* purpose here is to traverse tree, visiting child nodes before their
parents, this order is necessary for e.g. computing bounding boxes */
while(iter->stacksize) {
- /* pop node */
+ /* pop node */
iter->stacksize--;
node= iter->stack[iter->stacksize].node;
@@ -645,10 +646,7 @@
if(revisiting)
return node;
- /* check search callback */
- search_data= iter->search_data;
-
- if(iter->scb && !iter->scb(node, search_data))
+ if(iter->scb && !iter->scb(node, iter->search_data))
continue; /* don't traverse, outside of search zone */
if(node->flag & PBVH_Leaf) {
@@ -668,6 +666,34 @@
return NULL;
}
+static PBVHNode *pbvh_iter_next_occluded(PBVHIter *iter)
+{
+ PBVHNode *node;
+
+ while(iter->stacksize) {
+ /* pop node */
+ iter->stacksize--;
+ node= iter->stack[iter->stacksize].node;
+
+ /* on a mesh with no faces this can happen
+ * can remove this check if we know meshes have at least 1 face */
+ if(node==NULL) return NULL;
+
+ if(iter->scb && !iter->scb(node, iter->search_data)) continue; /* don't traverse, outside of search zone */
+
+ if(node->flag & PBVH_Leaf) {
+ /* immediately hit leaf node */
+ return node;
+ }
+ else {
+ pbvh_stack_push(iter, iter->bvh->nodes+node->children_offset+1, 0);
+ pbvh_stack_push(iter, iter->bvh->nodes+node->children_offset, 0);
+ }
+ }
+
+ return NULL;
+}
+
void BLI_pbvh_search_gather(PBVH *bvh,
BLI_pbvh_SearchCallback scb, void *search_data,
PBVHNode ***r_array, int *r_tot)
@@ -719,12 +745,106 @@
pbvh_iter_begin(&iter, bvh, scb, search_data);
while((node=pbvh_iter_next(&iter)))
- if(node->flag & PBVH_Leaf)
- hcb(node, hit_data);
+ if(node->flag & PBVH_Leaf) {
+ hcb(node, hit_data);
+ }
pbvh_iter_end(&iter);
}
+typedef struct node_tree {
+ PBVHNode* data;
+
+ struct node_tree* left;
+ struct node_tree* right;
+} node_tree;
+
+static void node_tree_insert(node_tree* tree, node_tree* new_node)
+{
+ if (new_node->data->tmin < tree->data->tmin) {
+ if (tree->left) {
+ node_tree_insert(tree->left, new_node);
+ }
+ else {
+ tree->left = new_node;
+ }
+ }
+ else {
+ if (tree->right) {
+ node_tree_insert(tree->right, new_node);
+ }
+ else {
+ tree->right = new_node;
+ }
+ }
+}
+
+static void traverse_tree(node_tree* tree, BLI_pbvh_HitOccludedCallback hcb, void* hit_data, float* tmin)
+{
+ if (tree->left) traverse_tree(tree->left, hcb, hit_data, tmin);
+
+ hcb(tree->data, hit_data, tmin);
+
+ if (tree->right) traverse_tree(tree->right, hcb, hit_data, tmin);
+}
+
+static void free_tree(node_tree* tree)
+{
+ if (tree->left) {
+ free_tree(tree->left);
+ tree->left = 0;
+ }
+
+ if (tree->right) {
+ free_tree(tree->right);
+ tree->right = 0;
+ }
+
+ free(tree);
+}
+
+float BLI_pbvh_node_get_tmin(PBVHNode* node)
+{
+ return node->tmin;
+}
+
+void BLI_pbvh_search_callback_occluded(PBVH *bvh,
+ BLI_pbvh_SearchCallback scb, void *search_data,
+ BLI_pbvh_HitOccludedCallback hcb, void *hit_data)
+{
+ PBVHIter iter;
+ PBVHNode *node;
+ node_tree *tree = 0;
+ float tmin = FLT_MAX;
+
+ pbvh_iter_begin(&iter, bvh, scb, search_data);
+
+ while((node=pbvh_iter_next_occluded(&iter))) {
+ if(node->flag & PBVH_Leaf) {
+ node_tree* new_node = malloc(sizeof(node_tree));
+
+ new_node->data = node;
+
+ new_node->left = NULL;
+ new_node->right = NULL;
+
+ if (tree) {
+ node_tree_insert(tree, new_node);
+ }
+ else {
+ tree = new_node;
+ }
+ }
+ }
+
+ pbvh_iter_end(&iter);
+
+ if (tree) {
+ traverse_tree(tree, hcb, hit_data, &tmin);
+ free_tree(tree);
+ }
+}
+
static int update_search_cb(PBVHNode *node, void *data_v)
{
int flag= GET_INT_FROM_POINTER(data_v);
@@ -968,7 +1088,8 @@
GHashIterator *hiter;
GHash *map;
void *face, **faces;
- int i, tot;
+ unsigned i;
+ int tot;
map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "pbvh_get_grid_updates gh");
@@ -1082,50 +1203,44 @@
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list