Google Code-in

The goal of this task is to make the voxelize command considerably more efficient.

BRL-CAD's voxelize command takes a given object and chops it up into a bunch of voxels (small boxes) and groups them together. When it groups them together, it currently creates a heavily imbalanced tree. Grouped geometry in BRL-CAD is represented as a directed acyclic graph.

If you naively group objects in code (for example "A u B u C u D"), they end up looking like "(A u (B u (C u D)))" instead of this form that is more spatially efficient to calculate in 3D: "((A u B) u (C u D))". (Note "u" implies a "union" grouping operation). This gets really bad when grouping hundreds or thousands of objects.

Change the voxelize command implementation, which you can test using MGED or Archer, to create a balanced tree.

References:

• src/libged/voxelize.c

SUBMIT working code changes as a patch file.