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.
References:- 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
File name/URL | File size | Date submitted | |
---|---|---|---|
task-37-update-gdiam-obb-algorithm.diff | 5.4 KB | December 21 2014 23:09 UTC | |
task-37-update-gdiam-obb-algorithm.diff | 5.1 KB | December 21 2014 23:18 UTC |
I would like to work on this task.
This task has been assigned to Andromeda Galaxy. You have 100 hours to complete this task, good luck!
The work on this task is ready to be reviewed.
Sorry, the first diff contains a couple of extra debugging checks that I was using to make sure that out-of-bounds errors didn't occur that aren't actually necessary.
Congratulations, this task has been completed successfully.
Andromeda Galaxy,
On quick review, this looks good, but please run the patch by starseeker on IRC to make sure you got it working right if you haven't already.
Cheers!