or how I learned to love binary search…
In this case, a customer uploaded a scene that always crashed at a certain point in the playback.
After poking around the scene for awhile, I deleted a model and that fixed the crash. The only problem was that the model contained a thousand (1000) objects, so deleting the model wasn’t really a solution. So my next step was to isolate the problem use a “divide and conquer” approach. Sort of like a binary search:
- delete half of the objects (eg objects 1 to 500)
- play back
- if crash, then the problem is one of the objects in the second half (501 to 1000)
- else the problem is one of the objects in the first half (1 to 500)
- Repeat as required… at most 10 times (1000,500,250,125,62,31,16,8,4,2,1)
In the end, I narrowed it down to a single mesh object. We weren’t able to save that mesh (it had to be deleted and then recreated), but we did save the scene.
A binary search halves the number of items to check with each iteration, so locating an item (or determining its absence) takes logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.