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.

wikipedia:

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.

Dividing and conquering the problem space: