Fix for [#25544] Blender crashes when changing the particles emission amount
authorJanne Karhu <jhkarh@gmail.com>
Sun, 9 Jan 2011 07:41:51 +0000 (07:41 +0000)
committerJanne Karhu <jhkarh@gmail.com>
Sun, 9 Jan 2011 07:41:51 +0000 (07:41 +0000)
* I've getting bad feelings about the point cache index_array for a while (cause for this bug too), so from now on memory cache uses a simple binary search directly on the index data to handle queries to specific data points.
* This is a bit slower than just checking from a dedicated array, but it's much less error prone, uses less memory and makes the code more readable too, so it's not a tough choice.

source/blender/blenkernel/BKE_pointcache.h
source/blender/blenkernel/intern/particle.c
source/blender/blenkernel/intern/pointcache.c
source/blender/blenloader/intern/readfile.c
source/blender/blenloader/intern/writefile.c
source/blender/editors/physics/particle_edit.c
source/blender/makesdna/DNA_object_force.h

index f35488881687eb3f95464f1a9747bd8c3a17e100..c7f76c033c83cd9ede60b3a4215fc89768d1b459 100644 (file)
@@ -89,7 +89,7 @@ struct SoftBody;
 
 /* temp structure for read/write */
 typedef struct PTCacheData {
-       int index;
+       uint32_t index;
        float loc[3];
        float vel[3];
        float rot[4];
@@ -270,6 +270,9 @@ void BKE_ptcache_update_info(PTCacheID *pid);
 /* Size of cache data type. */
 int            BKE_ptcache_data_size(int data_type);
 
+/* Is point with indes in memory cache */
+int BKE_ptcache_mem_index_find(struct PTCacheMem *pm, int index);
+
 /* Memory cache read/write helpers. */
 void BKE_ptcache_mem_pointers_init(struct PTCacheMem *pm);
 void BKE_ptcache_mem_pointers_incr(struct PTCacheMem *pm);
index 018b882f7a2a5c9d569961a03f94f9bf88564a7c..26f96d0c30487343a61b7e1c9201d4c64aee165b 100644 (file)
@@ -1056,6 +1056,7 @@ typedef struct ParticleInterpolationData {
 static void get_pointcache_keys_for_time(Object *UNUSED(ob), PointCache *cache, PTCacheMem **cur, int index, float t, ParticleKey *key1, ParticleKey *key2)
 {
        static PTCacheMem *pm = NULL;
+       int index1, index2;
 
        if(index < 0) { /* initialize */
                *cur = cache->mem_cache.first;
@@ -1070,15 +1071,19 @@ static void get_pointcache_keys_for_time(Object *UNUSED(ob), PointCache *cache,
 
                        pm = *cur;
 
-                       BKE_ptcache_make_particle_key(key2, pm->index_array ? pm->index_array[index] - 1 : index, pm->data, (float)pm->frame);
-                       if(pm->prev->index_array && pm->prev->index_array[index] == 0)
+                       index2 = BKE_ptcache_mem_index_find(pm, index);
+                       index1 = BKE_ptcache_mem_index_find(pm->prev, index);
+
+                       BKE_ptcache_make_particle_key(key2, index2, pm->data, (float)pm->frame);
+                       if(index1 < 0)
                                copy_particle_key(key1, key2, 1);
                        else
-                               BKE_ptcache_make_particle_key(key1, pm->prev->index_array ? pm->prev->index_array[index] - 1 : index, pm->prev->data, (float)pm->prev->frame);
+                               BKE_ptcache_make_particle_key(key1, index1, pm->prev->data, (float)pm->prev->frame);
                }
                else if(cache->mem_cache.first) {
                        pm = cache->mem_cache.first;
-                       BKE_ptcache_make_particle_key(key2, pm->index_array ? pm->index_array[index] - 1 : index, pm->data, (float)pm->frame);
+                       index2 = BKE_ptcache_mem_index_find(pm, index);
+                       BKE_ptcache_make_particle_key(key2, index2, pm->data, (float)pm->frame);
                        copy_particle_key(key1, key2, 1);
                }
        }
@@ -1089,14 +1094,7 @@ static int get_pointcache_times_for_particle(PointCache *cache, int index, float
        int ret = 0;
 
        for(pm=cache->mem_cache.first; pm; pm=pm->next) {
-               if(pm->index_array) {
-                       if(pm->index_array[index]) {
-                               *start = pm->frame;
-                               ret++;
-                               break;
-                       }
-               }
-               else {
+               if(BKE_ptcache_mem_index_find(pm, index) >= 0) {
                        *start = pm->frame;
                        ret++;
                        break;
@@ -1104,14 +1102,7 @@ static int get_pointcache_times_for_particle(PointCache *cache, int index, float
        }
 
        for(pm=cache->mem_cache.last; pm; pm=pm->prev) {
-               if(pm->index_array) {
-                       if(pm->index_array[index]) {
-                               *end = pm->frame;
-                               ret++;
-                               break;
-                       }
-               }
-               else {
+               if(BKE_ptcache_mem_index_find(pm, index) >= 0) {
                        *end = pm->frame;
                        ret++;
                        break;
@@ -1126,13 +1117,8 @@ float psys_get_dietime_from_cache(PointCache *cache, int index) {
        int dietime = 10000000; /* some max value so that we can default to pa->time+lifetime */
 
        for(pm=cache->mem_cache.last; pm; pm=pm->prev) {
-               if(pm->index_array) {
-                       if(pm->index_array[index])
-                               return (float)pm->frame;
-               }
-               else {
+               if(BKE_ptcache_mem_index_find(pm, index) >= 0)
                        return (float)pm->frame;
-               }
        }
 
        return (float)dietime;
index 317723aef7fb12f6ca8ba6bc04b1bfe1b3319c80..1d58f2761170bcd9a8cd9aee801b8d10eac53d18 100644 (file)
@@ -1161,6 +1161,39 @@ static void ptcache_file_pointers_init(PTCacheFile *pf)
        pf->cur[BPHYS_DATA_BOIDS] =             (data_types & (1<<BPHYS_DATA_BOIDS))    ?               &pf->data.boids : NULL;
 }
 
+/* Check to see if point number "index" is in pm, uses binary search for index data. */
+int BKE_ptcache_mem_index_find(PTCacheMem *pm, int index)
+{
+       if(pm->data[BPHYS_DATA_INDEX]) {
+               uint32_t key = index;
+               uint32_t *data = pm->data[BPHYS_DATA_INDEX];
+               uint32_t mid, low = 0, high = pm->totpoint - 1;
+
+               if(key < *data || key > *(data+high))
+                       return -1;
+
+               /* check simple case for continuous indexes first */
+               if(data[key-*data]==key)
+                       return key-*data;
+
+               while(low <= high) {
+                       mid= (low + high)/2;
+
+                       if(data[mid] > key)
+                               high = mid - 1;
+                       else if(data[mid] < key)
+                               low = mid + 1;
+                       else
+                               return mid;
+               }
+
+               return -1;
+       }
+       else {
+               return (index < pm->totpoint ? index : -1);
+       }
+}
+
 void BKE_ptcache_mem_pointers_init(PTCacheMem *pm)
 {
        int data_types = pm->data_types;
@@ -1182,9 +1215,9 @@ void BKE_ptcache_mem_pointers_incr(PTCacheMem *pm)
 int  BKE_ptcache_mem_pointers_seek(int point_index, PTCacheMem *pm)
 {
        int data_types = pm->data_types;
-       int i, index = pm->index_array ? pm->index_array[point_index] - 1 : point_index;
+       int i, index = BKE_ptcache_mem_index_find(pm, point_index);
 
-       if(index < 0 || point_index >= MEM_allocN_len(pm->index_array)/sizeof(int)) {
+       if(index < 0) {
                /* Can't give proper location without reallocation, so don't give any location.
                 * Some points will be cached improperly, but this only happens with simulation
                 * steps bigger than cache->step, so the cache has to be recalculated anyways
@@ -1218,11 +1251,6 @@ static void ptcache_data_free(PTCacheMem *pm)
                if(data[i])
                        MEM_freeN(data[i]);
        }
-
-       if(pm->index_array) {
-               MEM_freeN(pm->index_array);
-               pm->index_array = NULL;
-       }
 }
 static void ptcache_data_copy(void *from[], void *to[])
 {
@@ -1306,24 +1334,6 @@ static void ptcache_find_frames_around(PTCacheID *pid, int frame, int *fra1, int
                }
        }
 }
-static void ptcache_make_index_array(PTCacheMem *pm, int totpoint)
-{
-       int i, *index;
-
-       if(pm->index_array) {
-               MEM_freeN(pm->index_array);
-               pm->index_array = NULL;
-       }
-
-       if(!pm->data[BPHYS_DATA_INDEX])
-               return;
-
-       pm->index_array = MEM_callocN(totpoint * sizeof(int), "PTCacheMem index_array");
-       index = pm->data[BPHYS_DATA_INDEX];
-
-       for(i=0; i<pm->totpoint; i++, index++)
-               pm->index_array[*index] = i + 1;
-}
 
 static PTCacheMem *ptcache_disk_frame_to_mem(PTCacheID *pid, int cfra)
 {
@@ -1398,9 +1408,6 @@ static PTCacheMem *ptcache_disk_frame_to_mem(PTCacheID *pid, int cfra)
                }
        }
 
-       if(!error)
-               ptcache_make_index_array(pm, pid->totpoint(pid->calldata, pm->frame));
-
        if(error && pm) {
                ptcache_data_free(pm);
                ptcache_extra_free(pm);
@@ -1806,7 +1813,6 @@ static int ptcache_write(PTCacheID *pid, int cfra, int overwrite)
                }
        }
        else {
-               ptcache_make_index_array(pm, pid->totpoint(pid->calldata, cfra));
                BLI_addtail(&cache->mem_cache, pm);
        }
 
@@ -2989,7 +2995,6 @@ void BKE_ptcache_update_info(PTCacheID *pid)
                                bytes += sizeof(PTCacheExtra);
                        }
 
-                       bytes += MEM_allocN_len(pm->index_array);
                        bytes += sizeof(PTCacheMem);
                        
                        totframes++;
index f3bd91d12ed6d73d67039f561dce54e2e23ac2ff..9772074207d4cdb6654b2d67736bfe49a3e8bb02 100644 (file)
@@ -2936,15 +2936,6 @@ static void direct_link_pointcache(FileData *fd, PointCache *cache)
                pm = cache->mem_cache.first;
 
                for(; pm; pm=pm->next) {
-                       if(pm->index_array)
-                               pm->index_array = newdataadr(fd, pm->index_array);
-                       
-                       /* writedata saved array of ints */
-                       if(pm->index_array && (fd->flags & FD_FLAGS_SWITCH_ENDIAN)) {
-                               for(i=0; i<pm->totpoint; i++)
-                                       SWITCH_INT(pm->index_array[i]);
-                       }
-                       
                        for(i=0; i<BPHYS_TOT_DATA; i++) {
                                pm->data[i] = newdataadr(fd, pm->data[i]);
                                
index dd6d56572e80158adceaccf63ceb9996bd721868..050fd5bcaf167bfbe17e90cca50828a60d5b7ba2 100644 (file)
@@ -784,8 +784,6 @@ static void write_pointcaches(WriteData *wd, ListBase *ptcaches)
 
                        for(; pm; pm=pm->next) {
                                writestruct(wd, DATA, "PTCacheMem", 1, pm);
-                               if(pm->index_array)
-                                       writedata(wd, DATA, MEM_allocN_len(pm->index_array), pm->index_array);
                                
                                for(i=0; i<BPHYS_TOT_DATA; i++) {
                                        if(pm->data[i] && pm->data_types & (1<<i))
index cca5df501183e27549968c2b364d688d296826b3..4ac4bf9fa9b1f2d5e511393e9a1ce2c96e5cff36 100644 (file)
@@ -3719,8 +3719,6 @@ static void make_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
                for(; pm; pm=pm->next) {
                        for(i=0; i<BPHYS_TOT_DATA; i++)
                                pm->data[i] = MEM_dupallocN(pm->data[i]);
-
-                       pm->index_array = MEM_dupallocN(pm->index_array);
                }
        }
 
@@ -3795,8 +3793,6 @@ static void get_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
                        for(i=0; i<BPHYS_TOT_DATA; i++)
                                pm->data[i] = MEM_dupallocN(pm->data[i]);
 
-                       pm->index_array = MEM_dupallocN(pm->index_array);
-
                        BKE_ptcache_mem_pointers_init(pm);
 
                        LOOP_POINTS {
@@ -4061,25 +4057,9 @@ static void PE_create_particle_edit(Scene *scene, Object *ob, PointCache *cache,
                                totframe++;
 
                        for(pm=cache->mem_cache.first; pm; pm=pm->next) {
-                               BKE_ptcache_mem_pointers_init(pm);
-
                                LOOP_POINTS {
-                                       if(psys) {
-                                               if(pm->index_array) {
-                                                       if(pm->index_array[p])
-                                                               BKE_ptcache_mem_pointers_seek(p, pm);
-                                                       else
-                                                               continue;
-                                               }
-                                               else {
-                                                       pa = psys->particles + p;
-                                                       if((pm->next && pm->next->frame < pa->time)
-                                                               || (pm->prev && pm->prev->frame >= pa->dietime)) {
-                                                                       BKE_ptcache_mem_pointers_incr(pm);
-                                                                       continue;
-                                                               }
-                                               }
-                                       }
+                                       if(BKE_ptcache_mem_pointers_seek(p, pm) == 0)
+                                               continue;
 
                                        if(!point->totkey) {
                                                key = point->keys = MEM_callocN(totframe*sizeof(PTCacheEditKey),"ParticleEditKeys");
index 96f2c1ccc79e54c5c134e67f449f6702eb0f11a0..1d1ad6ad021f346b5d63fe9c1ac960d867b380cf 100644 (file)
@@ -152,7 +152,6 @@ typedef struct PTCacheMem {
        struct PTCacheMem *next, *prev;
        int frame, totpoint;
        unsigned int data_types, flag;
-       int *index_array; /* quick access to stored points with index */
 
        void *data[8]; /* BPHYS_TOT_DATA */
        void *cur[8]; /* BPHYS_TOT_DATA */