Editing Mesh library cleanup

From BRL-CAD

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 1: Line 1:
BRL-CAD has an extensive n-manifold (NMG) polygonal mesh library called LIBNMG.  N-manifold is mostly a fancy way of saying it provides an arbitrary boundary representation structure.  This library is used for a wide range of tasks but is commonly interacted with during geometry export to polygonal formats (e.g., g-stl).  The library goes to extensive lengths to ensure that geometry is "correct" at every step along the way, that solidity is preserved, that topology is preserved, and more.  All of that work means that the library can be slow and over time has become even more "unrobust" to real geometry.  There are lots of O(n^2) and O(n^3) algorithms with dynamic memory allocations that make performance suboptimal.  The source code is the documentation.  It's one of the best at what it does, but far from good enough.
+
BRL-CAD has an extensive n-manifold (NMG) polygonal mesh library presently embedded within LIBRT.  N-manifold is mostly a fancy way of saying it provides an arbitrary boundary representation structure.  This library is used for a wide range of tasks but is commonly interacted with during geometry export to polygonal formats (e.g., g-stl).  The library goes to extensive lengths to ensure that geometry is "correct" at every step along the way, that solidity is preserved, that topology is preserved, and more.  All of that work means that the library can be slow and over time has become even more "unrobust" to real geometry.  There are lots of O(n^2) and O(n^3) algorithms with dynamic memory allocations that make performance suboptimal.  The source code is the documentation.  It's one of the best at what it does, but far from good enough.
  
This project entails basic source code cleanup, validation, and verification.  The first step is documentation cleanup pulling all of the source code comments into the nmg.h public header (or sub-header thereof) to become familiarized with the API.  Then begin testing the lowest-level functions to make sure they do exactly what they are supposed to do by creating API unit tests.  Test-driven development is a must here.
+
This project entails basic source code cleanup, validation, and verification.  As the library code is embedded into LIBRT, the first step is to extricate it to its own directory.  That will require some header reshuffling and a lot of work to formally split LIBNMG's API entirely from LIBRT.  With that complete, the next step is documentation cleanup pulling all of the source code comments into the nmg.h public header (or sub-header thereof) to become familiarized with the API.  Then begin testing the lowest-level functions to make sure they do exactly what they are supposed to do by creating API unit tests.  Test-driven development is a must here.
  
 
=References=
 
=References=
Line 11: Line 11:
 
* include/nmg.h
 
* include/nmg.h
 
* include/raytrace.h
 
* include/raytrace.h
 
For the problem of boolean operations on NMG structures, recent papers should be studied.  Some examples:
 
 
* Fast, Exact, Linear Booleans: http://www.gilbertbernstein.com/resources/booleans2009.pdf
 
* Exact and Efficient Booleans for Polyhedra: http://liris.cnrs.fr/Documents/Liris-4883.pdf
 
* Fast and robust Booleans on polyhedra: http://www.sciencedirect.com/science/article/pii/S0010448512002412
 
* Exact, robust, and efficient regularized Booleans on general 3D meshes: http://www.sciencedirect.com/science/article/pii/S0898122115003028
 
* Fast, Exact and Robust Set Operations on Polyhedrons Using Localized Constructive Solid Geometry Trees:  http://wwwen.zte.com.cn/endata/magazine/ztecommunications/2015/3/articles/201510/P020151021364587175341.pdf
 
  
 
= Requirements=
 
= Requirements=

Please note that all contributions to BRL-CAD may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see BRL-CAD:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)