Difference between revisions of "Mesh library cleanup"

From BRL-CAD
m
(libnmg was pulled out of librt - work needed now is docs, cleanup, robustness testing and algorithm improvements.)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
−
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.
+
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.
  
−
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 maybe some 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.
+
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.
  
 
=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=

Latest revision as of 09:05, 9 February 2017

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.

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.

References[edit]

For the problem of boolean operations on NMG structures, recent papers should be studied. Some examples:

Requirements[edit]

  • Ability to read and refactor complex C
  • Ability to write API unit tests
Retrieved from "https://brlcad.org/w/index.php?title=Mesh_library_cleanup&oldid=9859"