[Bf-blender-cvs] [01ec68f] gooseberry: Completed the convex hull calculation for child paths.
Lukas Tönne
noreply at git.blender.org
Thu Jan 22 19:51:24 CET 2015
Commit: 01ec68f45704cffb1c72a56649eaa3b436629c3d
Author: Lukas Tönne
Date: Thu Jan 22 18:03:36 2015 +0100
Branches: gooseberry
https://developer.blender.org/rB01ec68f45704cffb1c72a56649eaa3b436629c3d
Completed the convex hull calculation for child paths.
Parent index is only stored for hull children as a means of identifying
them in the drawing code.
===================================================================
M source/blender/blenkernel/BKE_particle.h
M source/blender/blenkernel/intern/particle.c
M source/blender/blenkernel/intern/particle_distribute.c
M source/blender/editors/space_view3d/drawobject.c
M source/blender/makesdna/DNA_particle_types.h
===================================================================
diff --git a/source/blender/blenkernel/BKE_particle.h b/source/blender/blenkernel/BKE_particle.h
index b84eff6..e5f9c79 100644
--- a/source/blender/blenkernel/BKE_particle.h
+++ b/source/blender/blenkernel/BKE_particle.h
@@ -131,7 +131,7 @@ typedef struct ParticleCacheKey {
float rot[4];
float col[3];
float time;
- int segments, parent;
+ int segments, hull_parent;
} ParticleCacheKey;
typedef struct ParticleThreadContext {
diff --git a/source/blender/blenkernel/intern/particle.c b/source/blender/blenkernel/intern/particle.c
index c17cd81..7070a3a 100644
--- a/source/blender/blenkernel/intern/particle.c
+++ b/source/blender/blenkernel/intern/particle.c
@@ -2242,7 +2242,7 @@ static void psys_thread_create_path(ParticleTask *task, struct ChildParticle *cp
psys_calc_child_parent_weights(task, cpa, orco, ornor, hairmat, &cpa_num, &cpa_fuv, &cpa_from, key, weight, off1);
child_keys->segments = ctx->segments;
- child_keys->parent = ctx->between ? cpa->pa[0] : cpa->parent;
+ child_keys->hull_parent = cpa->hull_parent;
/* get different child parameters from textures & vgroups */
get_child_modifier_parameters(part, ctx, cpa, cpa_from, cpa_num, cpa_fuv, orco, &ptex);
diff --git a/source/blender/blenkernel/intern/particle_distribute.c b/source/blender/blenkernel/intern/particle_distribute.c
index a721bf5..9cac8b2 100644
--- a/source/blender/blenkernel/intern/particle_distribute.c
+++ b/source/blender/blenkernel/intern/particle_distribute.c
@@ -1158,6 +1158,7 @@ typedef struct ChildParticleSort {
int index;
float x, y;
int parent;
+ bool is_hull;
} ChildParticleSort;
/* comparison function for sorting children.
@@ -1179,30 +1180,81 @@ static int psys_child_cmp(const void *a, const void *b)
return cpa_a->parent < cpa_b->parent ? -1 : 1;
}
-/* sort children by primary parent and relative emitter location,
- * then calculate convex hulls using Andrew's Monotone Chain algorithm
- * http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
- */
+BLI_INLINE bool ccw(const ChildParticleSort *p1, const ChildParticleSort *p2, const ChildParticleSort *p3)
+{
+ return (p2->x - p1->x) * (p3->y - p1->y) - (p2->y - p1->y) * (p3->x - p1->x) > 0.0f;
+}
+
+static int make_convex_child_hull(ChildParticleSort *childdata, int totchild, ChildParticleSort **hull)
+{
+ const int parent = childdata->parent;
+
+ int tothull, upper_start;
+ int i;
+
+ tothull = 0;
+ /* lower hull */
+ for (i = 0; i < totchild; ++i) {
+ ChildParticleSort *cdata = &childdata[i];
+ /* limit to the parent group */
+ if (cdata->parent != parent)
+ break;
+
+ while (tothull >= 2 && !ccw(hull[tothull-2], hull[tothull-1], cdata))
+ --tothull;
+ hull[tothull++] = cdata;
+ }
+ /* this is the actual size of the child group sharing the same parent */
+ totchild = i;
+
+ /* upper hull */
+ upper_start = tothull + 1;
+ for (i = totchild-2; i >= 0; --i) {
+ ChildParticleSort *cdata = &childdata[i];
+
+ while (tothull >= upper_start && !ccw(hull[tothull-2], hull[tothull-1], cdata))
+ --tothull;
+ hull[tothull++] = cdata;
+ }
+
+ return tothull - 1;
+}
+
+BLI_INLINE int count_child_group(ChildParticleSort *data, int start, int totchild)
+{
+ const int parent = data[start].parent;
+ int i;
+
+ i = start;
+ do {
+ ++i;
+ } while (i < totchild && data[i].parent == parent);
+
+ return i - start;
+}
+
+/* sort children by primary parent and relative emitter location, then calculate convex hulls */
static void psys_sort_children(ParticleSimulationData *sim)
{
ParticleSystem *psys = sim->psys;
ParticleSettings *part = psys->part;
+ const int totchild = psys->totchild;
const bool between = (part->childtype == PART_CHILD_FACES);
const int cpa_from = between ? PART_FROM_FACE : part->from;
- ChildParticleSort *childdata;
+ ChildParticleSort *sort;
int i;
- if (psys->totchild == 0)
+ if (totchild == 0)
return;
if (!sim->psmd->dm)
return;
- childdata = MEM_mallocN(sizeof(ChildParticleSort) * psys->totchild, "child sorting data");
+ sort = MEM_mallocN(sizeof(ChildParticleSort) * totchild, "child sorting data");
- for (i = 0; i < psys->totchild; ++i) {
+ for (i = 0; i < totchild; ++i) {
ChildParticle *cpa = &psys->child[i];
- ChildParticleSort *cdata = &childdata[i];
+ ChildParticleSort *cdata = &sort[i];
ParticleData *parent;
float co[3], hairmat[4][4], hairimat[4][4];
@@ -1219,22 +1271,61 @@ static void psys_sort_children(ParticleSimulationData *sim)
mul_m4_v3(hairimat, co);
cdata->x = co[0];
cdata->y = co[1];
+
+ cdata->is_hull = false;
}
- qsort(childdata, psys->totchild, sizeof(ChildParticleSort), psys_child_cmp);
+ qsort(sort, totchild, sizeof(ChildParticleSort), psys_child_cmp);
+ /* Calculate the convex hull of children for each parent using Andrew's Monotone Chain algorithm
+ * http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
+ */
{
- ChildParticle *nchild = MEM_mallocN(sizeof(ChildParticle) * psys->totchild, "sorted child particles");
+ ChildParticle *nchild = MEM_mallocN(sizeof(ChildParticle) * totchild, "sorted child particles");
+ ChildParticle *ncpa = nchild;
- for (i = 0; i < psys->totchild; ++i) {
- memcpy(nchild + i, psys->child + childdata[i].index, sizeof(ChildParticle));
+ /* note: the algorithm requires one additional element in the buffer in worst case */
+ ChildParticleSort **hull = MEM_mallocN(sizeof(ChildParticleSort*) * (totchild+1), "child convex hull points");
+
+ int groupstart = 0;
+ while (groupstart < totchild) {
+ int groupsize, tothull;
+
+ groupsize = count_child_group(sort, groupstart, totchild);
+ BLI_assert(groupstart + groupsize <= totchild);
+
+ tothull = make_convex_child_hull(sort + groupstart, groupsize, hull);
+
+ for (i = 0; i < tothull; ++i) {
+ ChildParticleSort *cdata = hull[i];
+ memcpy(ncpa, psys->child + cdata->index, sizeof(ChildParticle));
+ ncpa->hull_parent = cdata->parent;
+ ++ncpa;
+
+ /* tag actual hull children */
+ cdata->is_hull = true;
+ }
+
+ /* insert remaining child particles after the hull children */
+ for (i = groupstart; i < groupstart + groupsize; ++i) {
+ ChildParticleSort *cdata = &sort[i];
+ if (!cdata->is_hull) {
+ memcpy(ncpa, psys->child + cdata->index, sizeof(ChildParticle));
+ ncpa->hull_parent = -1;
+ ++ncpa;
+ }
+ }
+
+ groupstart += groupsize;
}
+ MEM_freeN(hull);
+
MEM_freeN(psys->child);
psys->child = nchild;
}
- MEM_freeN(childdata);
+ MEM_freeN(sort);
}
void distribute_particles(ParticleSimulationData *sim, int from)
diff --git a/source/blender/editors/space_view3d/drawobject.c b/source/blender/editors/space_view3d/drawobject.c
index 164fbea..4fece10 100644
--- a/source/blender/editors/space_view3d/drawobject.c
+++ b/source/blender/editors/space_view3d/drawobject.c
@@ -4531,10 +4531,18 @@ static void draw_particle_hair_hull(Scene *UNUSED(scene), View3D *v3d, RegionVie
cache = psys->childcache;
for (p = 0; p < totchild; ++p) {
- ParticleCacheKey *path = cache[p], *npath = p+1 < totchild ? cache[p+1] : NULL;
+ ParticleCacheKey *path, *npath;
int segments, k;
- if (npath && npath->parent == path->parent) {
+ path = cache[p];
+ if (path->hull_parent < 0) {
+ pstart = p+1;
+ continue;
+ }
+
+ npath = p+1 < totchild ? cache[p+1] : NULL;
+
+ if (npath && npath->hull_parent == path->hull_parent) {
segments = max_ii(path->segments, npath->segments);
for (k = 0; k < segments; ++k) {
diff --git a/source/blender/makesdna/DNA_particle_types.h b/source/blender/makesdna/DNA_particle_types.h
index 033cbb3..a03cfd29 100644
--- a/source/blender/makesdna/DNA_particle_types.h
+++ b/source/blender/makesdna/DNA_particle_types.h
@@ -75,6 +75,7 @@ typedef struct ChildParticle {
float w[4]; /* interpolation weights for the above particles */
float fuv[4], foffset; /* face vertex weights and offset */
float rt;
+ int hull_parent; /* parent index of hull children, -1 if child is not part of the convex hull */
} ChildParticle;
typedef struct ParticleTarget {
More information about the Bf-blender-cvs
mailing list