Balance geometry created by BRL-CAD's voxelize command
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.