BRL-CAD's bb command has a feature to generate oriented bounding boxes (the smallest box containing a geometric object) that makes use of a library called "gdiam". This library is fast, but is unreliable when dealing with simpler shapes. One possibility for improvement is to switch the algorithm being used internally by gdiam for convex hull generation. In this context, a convex hull is a bounding polygonal mesh that creates an envelope around the geometry. That envelope is convex, ie.., all mesh line segments have angles >=180 degrees with their neighbors.

You should obtain BRL-CAD source code from our Subversion repository: svn checkout https://svn.code.sf.net/p/brlcad/code/brlcad/trunk brlcad

The goal for this task is to make the code for Monotone Chain convex hull construction by Dan Sunday get used by the gdiam library. The code is already present in the file src/other/libgdiam/gdiam.cpp at line 1603, and the code it is intended to replace is above it at line 1549. The task is to determine what changes are necessary to allow the new code to substitute successfully for the old code, and test the results in MGED using the bb command with the -o option. Here are commands that may be run in mged that will create a rotated mesh box, then create an oriented bounding box around it:

make arbn.s arbn; sed arbn.s; rot 30 30 30; accept; facetize arbn.bot arbn.s; bb -o -c box.s arbn.bot; draw box.s

Submit a patch to gdiam.cpp that enables the new convex hull algorithm successfully.

• http://sarielhp.org/research/papers/00/diameter/diam_prog.html
• http://geomalgorithms.com/a10-_hull-1.html
• src/other/libgdiam

• src/other/libgdiam/gdiam.cpp