[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [35614] trunk/blender/source/blender: New particle collisions code:
Janne Karhu
jhkarh at gmail.com
Fri Mar 18 16:31:32 CET 2011
Revision: 35614
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=35614
Author: jhk
Date: 2011-03-18 15:31:32 +0000 (Fri, 18 Mar 2011)
Log Message:
-----------
New particle collisions code:
* The old collisions code detected particle collisions by calculating the
collision times analytically from the collision mesh faces. This was
pretty accurate, but didn't support rotating/deforming faces at all, as
the equations for these quickly become quite nasty.
* The new code uses a simple "distance to plane/edge/vert" function and
iterates this with the Newton-Rhapson method to find the closest particle
distance during a simulation step.
* The advantage in this is that the collision object can now move, rotate,
scale or even deform freely and collisions are still detected reliably.
* For some extreme movements the calculation errors could stack up so much
that the detection fails, but this can be easily fixed by increasing the
particle size or simulation substeps.
* As a side note the algorithm doesn't really do point particles anymore,
but uses a very small radius as the particle size when "size deflect" isn't
selected.
* I've also updated the collision response code a bit, so now the particles
shouldn't leak even from tight corners.
All in all the collisions code is now much cleaner and more robust than before!
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/BKE_particle.h
trunk/blender/source/blender/blenkernel/intern/boids.c
trunk/blender/source/blender/blenkernel/intern/particle_system.c
trunk/blender/source/blender/blenloader/intern/readfile.c
trunk/blender/source/blender/editors/physics/particle_edit.c
trunk/blender/source/blender/makesdna/DNA_modifier_types.h
trunk/blender/source/blender/modifiers/intern/MOD_collision.c
Modified: trunk/blender/source/blender/blenkernel/BKE_particle.h
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_particle.h 2011-03-18 14:06:13 UTC (rev 35613)
+++ trunk/blender/source/blender/blenkernel/BKE_particle.h 2011-03-18 15:31:32 UTC (rev 35614)
@@ -155,19 +155,57 @@
short align, uv_split, anim, split_offset;
} ParticleBillboardData;
+typedef struct ParticleCollisionElement
+{
+ Object *ob;
+
+ /* pointers to original data */
+ float *x[4], *v[4];
+
+ /* values interpolated from original data*/
+ float x0[3], x1[3], x2[3], p[3];
+
+ /* results for found intersection point */
+ float nor[3], vel[3], uv[2];
+
+ /* count of original data (1-4) */
+ int tot;
+
+ /* flags for inversed normal / particle already inside element at start */
+ short inv_nor, inside;
+} ParticleCollisionElement;
+
/* container for moving data between deflet_particle and particle_intersect_face */
typedef struct ParticleCollision
{
- struct Object *ob, *hit_ob; // collided and current objects
- struct CollisionModifierData *md, *hit_md; // collision modifiers for current and hit object;
- float nor[3]; // normal at collision point
- float vel[3]; // velocity of collision point
- float co1[3], co2[3]; // ray start and end points
- float ve1[3], ve2[3]; // particle velocities
- float ray_len; // original length of co2-co1, needed for collision time evaluation
+ struct Object *current;
+ struct Object *hit;
+ struct Object *prev;
+ struct Object *skip;
+ struct Object *emitter;
+
+ struct CollisionModifierData *md; // collision modifier for current object;
+
float f; // time factor of previous collision, needed for substracting face velocity
- float cfra; // start of the timestep (during frame change, since previous integer frame)
- float dfra; // duration of timestep in frames
+ float fac1, fac2;
+
+ float cfra, old_cfra;
+
+ float original_ray_length; //original length of co2-co1, needed for collision time evaluation
+
+ int prev_index;
+
+ ParticleCollisionElement pce;
+
+ float total_time, inv_timestep;
+
+ float radius;
+ float co1[3], co2[3];
+ float ve1[3], ve2[3];
+
+ float acc[3], boid_z;
+
+ int boid;
} ParticleCollision;
typedef struct ParticleDrawData {
@@ -289,10 +327,8 @@
float psys_particle_value_from_verts(struct DerivedMesh *dm, short from, struct ParticleData *pa, float *values);
void psys_get_from_key(struct ParticleKey *key, float *loc, float *vel, float *rot, float *time);
-/* only in edisparticle.c*/
-int psys_intersect_dm(struct Scene *scene, struct Object *ob, struct DerivedMesh *dm, float *vert_cos, float *co1, float* co2, float *min_d, int *min_face, float *min_uv, float *face_minmax, float *pa_minmax, float radius, float *ipoint);
/* BLI_bvhtree_ray_cast callback */
-void particle_intersect_face(void *userdata, int index, const struct BVHTreeRay *ray, struct BVHTreeRayHit *hit);
+void BKE_psys_collision_neartest_cb(void *userdata, int index, const struct BVHTreeRay *ray, struct BVHTreeRayHit *hit);
void psys_particle_on_dm(struct DerivedMesh *dm, int from, int index, int index_dmcache, float *fw, float foffset, float *vec, float *nor, float *utan, float *vtan, float *orco, float *ornor);
/* particle_system.c */
Modified: trunk/blender/source/blender/blenkernel/intern/boids.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/boids.c 2011-03-18 14:06:13 UTC (rev 35613)
+++ trunk/blender/source/blender/blenkernel/intern/boids.c 2011-03-18 15:31:32 UTC (rev 35614)
@@ -213,10 +213,8 @@
sub_v3_v3v3(ray_dir, col.co2, col.co1);
mul_v3_fl(ray_dir, acbr->look_ahead);
col.f = 0.0f;
- col.cfra = fmod(bbd->cfra-bbd->dfra, 1.0f);
- col.dfra = bbd->dfra;
hit.index = -1;
- hit.dist = col.ray_len = len_v3(ray_dir);
+ hit.dist = col.original_ray_length = len_v3(ray_dir);
/* find out closest deflector object */
for(coll = bbd->sim->colliders->first; coll; coll=coll->next) {
@@ -224,18 +222,18 @@
if(coll->ob == bpa->ground)
continue;
- col.ob = coll->ob;
+ col.current = coll->ob;
col.md = coll->collmd;
if(col.md && col.md->bvhtree)
- BLI_bvhtree_ray_cast(col.md->bvhtree, col.co1, ray_dir, radius, &hit, particle_intersect_face, &col);
+ BLI_bvhtree_ray_cast(col.md->bvhtree, col.co1, ray_dir, radius, &hit, BKE_psys_collision_neartest_cb, &col);
}
/* then avoid that object */
if(hit.index>=0) {
- t = hit.dist/col.ray_len;
+ t = hit.dist/col.original_ray_length;
/* avoid head-on collision */
- if(dot_v3v3(col.nor, pa->prev_state.ave) < -0.99) {
+ if(dot_v3v3(col.pce.nor, pa->prev_state.ave) < -0.99) {
/* don't know why, but uneven range [0.0,1.0] */
/* works much better than even [-1.0,1.0] */
bbd->wanted_co[0] = BLI_frand();
@@ -243,7 +241,7 @@
bbd->wanted_co[2] = BLI_frand();
}
else {
- VECCOPY(bbd->wanted_co, col.nor);
+ copy_v3_v3(bbd->wanted_co, col.pce.nor);
}
mul_v3_fl(bbd->wanted_co, (1.0f - t) * val->personal_space * pa->size);
@@ -779,27 +777,26 @@
/* first try to find below boid */
copy_v3_v3(col.co1, pa->state.co);
sub_v3_v3v3(col.co2, pa->state.co, zvec);
- sub_v3_v3(col.co2, zvec);
sub_v3_v3v3(ray_dir, col.co2, col.co1);
col.f = 0.0f;
- col.cfra = fmod(bbd->cfra-bbd->dfra, 1.0f);
- col.dfra = bbd->dfra;
hit.index = -1;
- hit.dist = col.ray_len = len_v3(ray_dir);
+ hit.dist = col.original_ray_length = len_v3(ray_dir);
+ col.pce.inside = 0;
for(coll = bbd->sim->colliders->first; coll; coll = coll->next){
- col.ob = coll->ob;
+ col.current = coll->ob;
col.md = coll->collmd;
+ col.fac1 = col.fac2 = 0.f;
if(col.md && col.md->bvhtree)
- BLI_bvhtree_ray_cast(col.md->bvhtree, col.co1, ray_dir, radius, &hit, particle_intersect_face, &col);
+ BLI_bvhtree_ray_cast(col.md->bvhtree, col.co1, ray_dir, radius, &hit, BKE_psys_collision_neartest_cb, &col);
}
/* then use that object */
if(hit.index>=0) {
- t = hit.dist/col.ray_len;
+ t = hit.dist/col.original_ray_length;
interp_v3_v3v3(ground_co, col.co1, col.co2, t);
- normalize_v3_v3(ground_nor, col.nor);
- return col.hit_ob;
+ normalize_v3_v3(ground_nor, col.pce.nor);
+ return col.hit;
}
/* couldn't find below, so find upmost deflector object */
@@ -808,24 +805,22 @@
sub_v3_v3(col.co2, zvec);
sub_v3_v3v3(ray_dir, col.co2, col.co1);
col.f = 0.0f;
- col.cfra = fmod(bbd->cfra-bbd->dfra, 1.0f);
- col.dfra = bbd->dfra;
hit.index = -1;
- hit.dist = col.ray_len = len_v3(ray_dir);
+ hit.dist = col.original_ray_length = len_v3(ray_dir);
for(coll = bbd->sim->colliders->first; coll; coll = coll->next){
- col.ob = coll->ob;
+ col.current = coll->ob;
col.md = coll->collmd;
if(col.md && col.md->bvhtree)
- BLI_bvhtree_ray_cast(col.md->bvhtree, col.co1, ray_dir, radius, &hit, particle_intersect_face, &col);
+ BLI_bvhtree_ray_cast(col.md->bvhtree, col.co1, ray_dir, radius, &hit, BKE_psys_collision_neartest_cb, &col);
}
/* then use that object */
if(hit.index>=0) {
- t = hit.dist/col.ray_len;
+ t = hit.dist/col.original_ray_length;
interp_v3_v3v3(ground_co, col.co1, col.co2, t);
- normalize_v3_v3(ground_nor, col.nor);
- return col.hit_ob;
+ normalize_v3_v3(ground_nor, col.pce.nor);
+ return col.hit;
}
/* default to z=0 */
Modified: trunk/blender/source/blender/blenkernel/intern/particle_system.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/particle_system.c 2011-03-18 14:06:13 UTC (rev 35613)
+++ trunk/blender/source/blender/blenkernel/intern/particle_system.c 2011-03-18 15:31:32 UTC (rev 35614)
@@ -2607,466 +2607,691 @@
/************************************************/
/* Collisions */
/************************************************/
-/* convert from triangle barycentric weights to quad mean value weights */
-static void intersect_dm_quad_weights(float *v1, float *v2, float *v3, float *v4, float *w)
+#define COLLISION_MAX_COLLISIONS 10
+#define COLLISION_MIN_RADIUS 0.001f
+#define COLLISION_MIN_DISTANCE 0.0001f
+#define COLLISION_ZERO 0.00001f
+typedef float (*NRDistanceFunc)(float *p, float radius, ParticleCollisionElement *pce, float *nor);
+static float nr_signed_distance_to_plane(float *p, float radius, ParticleCollisionElement *pce, float *nor)
{
- float co[3], vert[4][3];
+ float p0[3], e1[3], e2[3], d;
- VECCOPY(vert[0], v1);
- VECCOPY(vert[1], v2);
- VECCOPY(vert[2], v3);
- VECCOPY(vert[3], v4);
+ sub_v3_v3v3(e1, pce->x1, pce->x0);
+ sub_v3_v3v3(e2, pce->x2, pce->x0);
+ sub_v3_v3v3(p0, p, pce->x0);
- co[0]= v1[0]*w[0] + v2[0]*w[1] + v3[0]*w[2] + v4[0]*w[3];
- co[1]= v1[1]*w[0] + v2[1]*w[1] + v3[1]*w[2] + v4[1]*w[3];
- co[2]= v1[2]*w[0] + v2[2]*w[1] + v3[2]*w[2] + v4[2]*w[3];
+ cross_v3_v3v3(nor, e1, e2);
+ normalize_v3(nor);
- interp_weights_poly_v3( w,vert, 4, co);
+ d = dot_v3v3(p0, nor);
+
+ if(pce->inv_nor == -1) {
+ if(d < 0.f)
+ pce->inv_nor = 1;
+ else
+ pce->inv_nor = 0;
+ }
+
+ if(pce->inv_nor == 1) {
+ mul_v3_fl(nor, -1.f);
+ d = -d;
+ }
+
+ return d - radius;
}
+static float nr_distance_to_edge(float *p, float radius, ParticleCollisionElement *pce, float *nor)
+{
+ float v0[3], v1[3], v2[3], c[3];
-/* check intersection with a derivedmesh */
-int psys_intersect_dm(Scene *scene, Object *ob, DerivedMesh *dm, float *vert_cos, float *co1, float* co2, float *min_d, int *min_face, float *min_w,
- float *face_minmax, float *pa_minmax, float radius, float *ipoint)
+ sub_v3_v3v3(v0, pce->x1, pce->x0);
+ sub_v3_v3v3(v1, p, pce->x0);
+ sub_v3_v3v3(v2, p, pce->x1);
+
+ cross_v3_v3v3(c, v1, v2);
+
+ return fabs(len_v3(c)/len_v3(v0)) - radius;
+}
+static float nr_distance_to_vert(float *p, float radius, ParticleCollisionElement *pce, float *nor)
{
- MFace *mface=0;
- MVert *mvert=0;
- int i, totface, intersect=0;
- float cur_d, cur_uv[2], v1[3], v2[3], v3[3], v4[3], min[3], max[3], p_min[3],p_max[3];
- float cur_ipoint[3];
-
- if(dm==0){
- psys_disable_all(ob);
+ return len_v3v3(p, pce->x0) - radius;
+}
+static void collision_interpolate_element(ParticleCollisionElement *pce, float t, float fac, ParticleCollision *col)
+{
+ /* t is the current time for newton rhapson */
+ /* fac is the starting factor for current collision iteration */
+ /* the col->fac's are factors for the particle subframe step start and end during collision modifier step */
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list