"Fossies" - the Fresh Open Source Software Archive

Member "brlcad-7.32.4/doc/notes/brep.txt" (29 Jul 2021, 9121 Bytes) of package /linux/misc/brlcad-7.32.4.tar.bz2:


As a special service "Fossies" has tried to format the requested text file into HTML format (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 BRL-CAD Boundary-Representation Primitive
    2 -----------------------------------------
    3 
    4 -- Introduction --
    5 
    6 This document describes the new Boundary-representation (BREP)
    7 primitive that has been implemented in BRL-CAD for use with external
    8 geometry import and improved visualisation.
    9 
   10 The primitive is not yet complete, and is currently quite buggy, so
   11 this document also serves to describe the current state of
   12 development, and the knowledge a developer needs to continue working
   13 on this primitive.
   14 
   15 
   16 -- BREP Description --
   17 
   18 A boundary-representation is a method of representing solid geometry
   19 by describing its topology and corresponding geometry. In other words,
   20 the vertexes, edges, and faces as well as the points, curves, and
   21 surfaces belonging to those topological elements.
   22 
   23 For example, a cube has 8 vertexes each mapping to 1 point in space, 6
   24 faces each mapping to 1 surface, and 8 edges each shared by two faces
   25 and sharing its two vertexes with two other faces and owning 1 real
   26 curve.
   27 
   28 Actually creating/using a BREP requires keeping track of a lot of details,
   29 including everything mentioned above, plus curve / face orientations
   30 (a CCW edge/vertex ordering is usually used for determining front/back
   31 designations.)
   32 
   33 BRL-CAD has/had an existing BREP structure: the NMG (non-manifold
   34 geometry) primitive/library.
   35 
   36 [[describe reasons for not using the existing library]]
   37 
   38 One can use many types of surface and curve geometry, but generally a
   39 small subset are used by any particular implementation: e.g. having
   40 converted a few pieces of Pro/E through IGES to the new BRL-CAD BREP
   41 primitive, I've seen the following curve and surface types used:
   42 
   43 * Line
   44 * Arc
   45 * NURBS curve
   46 * Surface of revolution
   47 * NURBS surface
   48 
   49 The simple IGES converter used to import and test new geometry handles
   50 those types already. Other limitations of the converter are described
   51 later in the document.
   52 
   53 
   54 -- Primitive Implementation --
   55 
   56 openNURBS was chosen to represent the geometry within BRL-CAD. This
   57 turned out to be a good and bad choice at the same time:
   58 
   59 * contains a lot of solid functionality
   60 * missing a lot of useful and important functionality
   61 
   62 In other words, the openNURBS API provided methods of functions for
   63 several pieces of functionality that had implementations removed when
   64 McNeil and Associates released openNURBS as essentially public domain
   65 code. This slowed development somewhat and meant the functionality had
   66 to be reimplemented by hand.
   67 
   68 The API is relatively straightforward C++, and it is used to evaluate
   69 geometry and represent/store BREPs in the BRL-CAD geometry file,
   70 through the built-in serialization facility (i.e. 3DM files).
   71 
   72 
   73 -- Raytracing BREPs --
   74 
   75 See Abert et al. (raytracing 06 paper: Direct and Fast Ray Tracing of NURBS
   76 Surfaces).
   77 
   78 We use a two-dimensional root-finding technique: we represent the ray
   79 as two orthogonal planes (the intersection of the planes includes the
   80 ray), and then find the root of an equation that represents the
   81 gradient of the distance from the point to the intersection of the ray
   82 planes. When this gradient becomes zero (we found a root), we've also
   83 found the uv parameters for the intersection point.
   84 
   85 Newton iteration is used, mostly since it is simple, displays
   86 quadratic convergence when using good guesses, and is amenable to
   87 acceleration using SIMD instructions.
   88 
   89 Evaluation of the surface and its derivatives is done by the openNURBS
   90 library at this point. The Abert paper gives some information on how
   91 to do the evaluation using SIMD instructions (needed for speeding
   92 things up).
   93 
   94 A simple SIMD vector class has been implemented (see vector.h)
   95 supporting both SSE2 and FPU vector operations. This is currently only
   96 lightly used, since no optimization work has taken place yet
   97 (correctness before optimization).
   98 
   99 After intersection, we need to trim the surface. Every edge of a BREP
  100 is part of a loop "within" a face. Loops define boundaries on
  101 faces. In our cube example above, the four edges of a each face
  102 comprise a single loop (in this case an outer boundary). The surface
  103 may be defined as an infinite plane, but this outer boundary loop
  104 limits it to the area enclosed within those edges. As you may imagine,
  105 a face may have more than one loop and these additional loops will
  106 always be internal. All loops can also be considered trims, although
  107 this term seems to be reserved for actual geometric curves that are
  108 parameterized within the domain of an individual surface.
  109 
  110 Properly ray tracing a BREP is difficult (thus, the obvious
  111 explanation why this primitive is incomplete). There are several facts
  112 about BREPs that result in problematic situations during ray tracing:
  113 BREPs are not like implicit solid geometry: there is no nice equation
  114 to simply solve (a lot of numerical techniques are used); surfaces,
  115 curves and point geometry may not be aligned; there can be gaps
  116 between two mated surfaces... and the list goes on.
  117 
  118 Since it's possible to miss a surface but *need* a hit (i.e. it hit an
  119 edge but passed between surfaces that did not mate up or overlap), we
  120 need to do edge checks: at some point, we find out how far an
  121 intersection point or a ray is from some set of edges
  122 
  123 
  124 -- Current Capabilities & Limitations --
  125 
  126 Developing a BRL-CAD primitive requires a minimum of 4 basic
  127 capabilities: reading from a geom db, writing to a geom db, providing
  128 a plot of the primitive (for MGED display), and handling shot
  129 intersection, which involves finding all intersections with the
  130 primitive and returning the results as a list of "segments" (these
  131 segments will later be used by BRL-CAD to do its boolean weaving).
  132 
  133 This primitive currently handles the first 3 capabilities fine, but
  134 has problems with the intersections (the most important part!)
  135 
  136 Issues:
  137 
  138 * bad acne (possibly caused by missing surfaces? duplicate
  139   intersections (making an odd number of hits along the ray), trimming
  140   errors?
  141 
  142 * problems with trimming (not completely sure the bezier clipping is
  143   correct)
  144 
  145 * possible problems with tolerances (been working with a very small
  146   (~2mm) object that has a moderate number of faces/edges)
  147 
  148 * no optimization, bad algorithms: bounding boxes (subsurface bounding
  149   boxes) should contain correct metadata concerning the need for
  150   trimming within the box, also a list of edges touched by the box for
  151   more efficient edge checking, evaluation optimization, etc...
  152 
  153 
  154 The current issue seems to be that we're missing surfaces altogether or
  155 getting extra intersections! or something funky is happening during
  156 trimming and edge checking. (BTW Pro/E seems to output overlapping
  157 surfaces, relying on the outer boundary loop to trim it - this implies
  158 that it should be quite difficult to actually miss both surfaces at an
  159 edge (since would have to get at least one intersection if they
  160 overlap at the edge!)
  161 
  162 [[ some pictures may be useful here ]]
  163 
  164 See all instances of "XXX" in the code (some may be out of date, but
  165 if something was fishy or I was being stupid/lazy/ignorant or some
  166 other bit of code was causing a problem, I tried to mark it with XXX.
  167 
  168 
  169 -- Conceptual/Implementation Issues --
  170 
  171 model-space curve pullback to surface domain for trimming (introduces
  172 possible errors while trimming (i.e. at an edge it's possible both
  173 surfaces can be trimmed because of inaccuracies of sampling)...
  174 
  175 multiple intersections found
  176 
  177 handling edge/surface grazing consistently
  178 
  179 bezier conversion of nurbs curves for trimming
  180 
  181 subsurface bounding boxes: when subdividing a surface domain and
  182 testing for flatness, hard to create a perfect bounding box around the
  183 subdomain (i.e. such that all points on the surface lie within the
  184 bounding box.) For the most part this may not be a problem, but
  185 oblique shots cause problems here (an image would help). Either way,
  186 the problem of better fitting bounding boxes (without just arbitrarily
  187 increasing the size which would seriously affect performance) needs to
  188 be considered... currently attempting to sample an additional 5 points
  189 (instead of just the corners). This should serve to handle the current
  190 problem.
  191 
  192 Close-up axis aligned rendering of a cylinder from the circular ends
  193 produces a halo of spurious points. Ugh!
  194 
  195 Optimize for small objects (there are some fixed size adjustments in
  196 the bounding box/subsurface code).
  197 
  198 
  199 -- IGES converter --
  200 
  201 A significant bit of time was spent writing the skeleton for a new
  202 IGES converter in order to get non-trivial BREP geometry from an
  203 external package into BRL-CAD for testing purposes (have been using
  204 the piston head part from one of the Pro/E tutorial models).
  205 
  206 I believe this converter can be made production-ready with some work:
  207 
  208 * polish options for output
  209 
  210 * handle assemblies and their proper mapping to BRL-CAD
  211 
  212 * handle naming? (don't know if IGES carries names, or if Pro/E adds
  213   them)
  214 
  215 * handle units properly!
  216 
  217 * tolerances when converting are still flaky (fix it) (cause BREP
  218   validity problems). Trims endpoint are not within zero tolerance
  219   (1e-12), so they "don't match" but they are very very close
  220   (1e-11)... so need to go through and call ON_Brep::CloseTrimGap() on
  221   each pair of trims in a loop.
  222 
  223 * Run lots of test cases!!!