"Fossies" - the Fresh Open Source Software Archive

Member "brlcad-7.32.4/doc/notes/TODO.BREP" (29 Jul 2021, 11542 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 BREP TODO
    2 =========
    3 
    4 Included below is a basic work breakdown related to the implementation
    5 of boundary representation (BREP) support in BRL-CAD.  Feel free to
    6 add to or expand this list and/or embellish it with additional
    7 information as appropriate.  If you would like to work on the BREP
    8 implementation, send a note to the brlcad-devel mailing list.
    9 
   10 This file is a general scratch pad for categorizing and itemizing BREP
   11 implementation tasks.  It is not an implementation plan.
   12 
   13 This is a work in progress.
   14 
   15 
   16 Geometry Entities
   17 -----------------
   18 
   19 point
   20 line  (e.g., line segment, ray, bidirectionally infinite line)
   21 line set  (e.g., polyline, polygon)
   22 curve  (e.g., spline, arc, circle, ellipse)
   23 plane
   24 surface (e.g., spline, polygonal)
   25 surface+curve  (i.e. a trimmed surface)
   26 solid
   27 
   28 
   29 Geometry Evaluation
   30 -------------------
   31 
   32 point -> point
   33 point -> line
   34 point -> curve
   35 point -> plane
   36 point -> surface
   37 point -> surface+curve
   38 point -> solid
   39 
   40 line -> line
   41 line -> curve
   42 line -> plane
   43 line -> surface
   44 line -> surface+curve
   45 line -> solid
   46 
   47 curve -> curve
   48 curve -> plane
   49 curve -> surface
   50 curve -> surface+curve
   51 curve -> solid
   52 
   53 plane -> plane
   54 plane -> surface
   55 plane -> surface+curve
   56 plane -> solid
   57 
   58 surface -> surface
   59 surface -> surface+curve
   60 surface -> solid
   61 
   62 surface+curve -> surface+curve
   63 surface+curve -> solid
   64 
   65 solid -> solid
   66 
   67 
   68 Geometry Queries
   69 ----------------
   70 
   71 [ geometric properties ]
   72 intersects
   73 inside
   74 outside
   75 on
   76 intersectionSet
   77 firstIntersectionSet
   78 closestDistance
   79 closestSet  (e.g., closestPoint)
   80 booleanEvaluation
   81 insideSet  (e.g., insideSolid, insideLoop (trimmed))
   82 outsideSet
   83 onSet
   84 
   85 [ parametric properties ]
   86 uvSpace <--> ImageSpace Mapping (for ALL primitive types)
   87 curvatures
   88 normalSet  (e.g., normalVector, normalPlane)
   89 tangentSet  (e.g., tangentVectors, tangentPlanes)
   90 
   91 [ checks ]
   92 isValid
   93 isSolid
   94 isManifold
   95 isFlat
   96 
   97 [ bounding volumes ]
   98 boundingBox
   99 boundingSphere
  100 
  101 
  102 Geometry Modifiers
  103 ------------------
  104 
  105 scale
  106 rotate
  107 translate
  108 shear
  109 
  110 mirror
  111 copy/clone
  112 delete
  113 
  114 invertRepresentation
  115 evaluateBoolean  (i.e. CSG)
  116 snapTogether  (e.g., | -)
  117 
  118 sweep
  119 extrude
  120 revolve
  121 extend/stretch
  122 
  123 trim  (e.g., cutting plane)
  124 split  (i.e. copy and two trims)
  125 
  126 fillet
  127 chamfer
  128 
  129 
  130 Ray Tracing
  131 -----------
  132 
  133 intersectionSet query
  134   boundingBox
  135   line -> solid evaluation
  136 normalSet query
  137   line -> solid evaluation
  138 
  139 line->solid evaluation
  140   line->surface || line->plane
  141 
  142 line->plane
  143   line->line
  144 
  145 line->surface
  146   line->curve || line->line
  147   closestDistance
  148 
  149 closestDistance
  150   point->plane
  151   point->point
  152 
  153 line->curve
  154   line->point
  155 
  156 line->line
  157   line->point
  158 
  159 line->point
  160   point->point
  161 
  162 
  163 Interactive Visualization
  164 -------------------------
  165 
  166 implicit primitive to solid conversion
  167 solid on solid CSG evaluation  (i.e. unevaluated to evaluated BREP)
  168 solid tessellation
  169 
  170 
  171 Conversion
  172 ----------
  173 
  174 3DM to BRL-CAD
  175 BRL-CAD to 3DM
  176 STEP to BRL-CAD
  177 IGES to BRL-CAD
  178 BRL-CAD to STEP
  179 BRL-CAD to IGES
  180 
  181 
  182 ********************************************************************************
  183  Below are some thoughts and notes about specific issues related to the above
  184  topics - may be useful as comments at some point, or at least food for thought.
  185 ********************************************************************************
  186 
  187 /*
  188  *   Point-Point Evaluation
  189  *
  190  *   Answer Evaluation Questions involving two points:
  191  *
  192  *   1.  Intersection - for a point, there are three possible categories of of intersection:
  193  *   	    * Identical - point values identical and all bound values identical
  194  *
  195  *                                              * * * * * * * *
  196  *                                              *             *
  197  *                                              *    1   2    *
  198  *                                              *      *      *
  199  *                                              *             *
  200  *                                              *             *
  201  *                                              * * * * * * * *
  202  *
  203  *   	    * Contained - values not all identical but bounds of the point of interest all smaller than bounds of
  204  *   	                  point it is being compared to
  205  *
  206  *
  207  *                            * * * * * * * * * *             * * * * * * * * * *
  208  *                            *        1        *             *                 *
  209  *                            *       * * * * * *             *     * * * * *   *
  210  *                            *       *       * *             *     *  1    *   *
  211  *                            *       *   2   * *             *     *       *   *
  212  *                            *       *       * *             *     *    2  *   *
  213  *                            *       * * * * * *             *     * * * * *   *
  214  *                            * * * * * * * * * *             * * * * * * * * * *
  215  *
  216  *
  217  *   	    * Overlapping - values not all identical but bounds of the point of interest all overlap bounds of
  218  *   	    		  the point it is being compared to.  (Note:  a corner case is when the value of the upper
  219  *   	    		  bound of one point is equal to the lower bound of the other - this is defined to be
  220  *   	    		  overlapping.)
  221  *
  222  *
  223  *             	        * * * * * * * *              * * * * * * * *              * * * * * * * *
  224  *             	        *             *              *             *              *             *
  225  *                      *      1      *              *   * * * * * * * * *        *   * * * * * * * * *
  226  *                      *     * * * * * * * *        *   *  1      *     *        *   *  1      *     *
  227  *                      *     *       *     *        *   *         *     *        *   *         *     *
  228  *                      * * * * * * * *     *        * * * * * * * *     *        *   *      2  *     *
  229  *                            *      2      *            *        2      *        * * * * * * * *     *
  230  *                            *             *            *               *            *               *
  231  *                            * * * * * * * *            * * * * * * * * *            * * * * * * * * *
  232  *
  233  *
  234  *   2.  Outside - "If the points are not identical in value and/or error bounds, is the point of interest and its error
  235  *       bounds contained or overlapping with the comparison point, or vice versa?  If not, the point of interest is
  236  *       outside the comparison point.
  237  *
  238  *       Contained and Overlapping points present a problem.  Take the case where two points have an overlapping bound
  239  *       and a third point must decide its relationship with each of them:
  240  *
  241  *                                              * * * * * * * *
  242  *                                              *             *
  243  *                                              *      1      *
  244  *                                              *             *
  245  *                            	        * * * * * * * *   * * * * * * * *
  246  *                            	        *       *     *   *   *         *
  247  *                            	        *       * * * * * * * *         *
  248  *                            	        *     2       *   *      3      *
  249  *                            	        *             *   *             *
  250  *                            	        *             *   *             *
  251  *                            	        * * * * * * * *   * * * * * * * *
  252  *
  253  *       Point 1 and Point 2 overlap and may intersect.  When Point 3 evaluates its relationships with Point 1 and
  254  *       Point 2, it finds that it overlaps and may intersect Point 1, but it does NOT overlap Point 3.  This means
  255  *       that Point 1 may intersect Point 2 OR Point 3, but NOT both at the same time.  Any assumption of equality
  256  *       involving any of these three points must decide how to handle this situation, and the decision must be both
  257  *       consistent and reproducible.  The possible decisions are:
  258  *
  259  *       1 = 2, 1 != 3
  260  *       1 != 2, 1 = 3
  261  *
  262  *       In order to have a concrete method for deciding this question, point evaluation cannot be a local, two point
  263  *       only test.  It is necessary to search out all points which overlap the two points in question (i.e. the only
  264  *       points which might impact the decisions of which points are identical in this particular case) and resolve the
  265  *       question amongst all of them.  One possibility would be to assemble all the guaranteed non-equalities among
  266  *       the set, search for the shortest distance between values among the remaining possible relationships, and assign
  267  *       intersection status based on those results.  (This may not be sufficient - bounding box size may also be
  268  *       important.)  For the original two points supplied, the question of intersection or non-intersection is now
  269  *       resolved as long as no geometry changes are made to any element that has bounds overlapping their individual
  270  *       bound.
  271  *
  272  *       Once this near space evaluation is done, each point's list of intersecting and non-intersecting points is updated.
  273  *       A query routine with two points can first check the points' own intersection/non-intersection lists to see if
  274  *       the answer is already pre-determined.  If it is not, determining via the bounds inside/outside is straightforward
  275  *       and deterministic and it cannot be intersecting.
  276  *
  277  *       One question is what to do when the geometry DOES change. New geometry may potentially change the decisions
  278  *       on what is and is not intersecting - perhaps it should?  Potential trouble there with overlapping vs. non-
  279  *       overlapping regions.
  280  */
  281 
  282 SOLID NURBS RAYTRACING ROBUSTNESS IMPROVEMENT/REFINEMENT
  283 
  284 One of the difficult tasks with solid raytracing is determining reliably when we're inside or outside in cases where
  285 BRep edges don't exactly join up geometrically.  OpenNURBS has tolerances which define such shapes as "valid", but the
  286 mathematics of the ray interesection will still report wonky results once hit points get inside those tolerance regions.
  287 
  288 We have resolution logic that tries to handle ambiguous cases, but one potential technique we are not currently using
  289 would use the bounding box information from the NURBS prep trees to augment that logic's robustness (or, more precisely,
  290 bound the portions of the ray segment within which point ambiguities need to be resolved.)
  291 
  292 The current thought is to use the not-on-surface-point bounding box points (which we can categorize as inside or outside
  293 relative to the surface they are bounding by construting vectors from on surface points to those points and comparing
  294 them to the surface normal vectors) and the surface points themselves to construct an outer and inner bounding volume
  295 for the BRep (to be reliable, we would also have to take care that we refine enough to avoid self intersections in
  296 those volumes.)  The overall bounding box of the outer volume should always be larger than that of the inner volume,
  297 so a comparison of those would allow us to flip them if the "wrong" box is too big to deal with a BRep with inverted
  298 surface normals.  (Might actually also allow us to reliably detect and fix such BReps, but that's a different topic.)
  299 
  300 Once we have the outer bounding volume, we intersect that along with the NURBS BRep itself and use the ray segments
  301 from the outer bounding volume as bounding regions within which we resolve any point ambiguities.  This should allow
  302 us to "locally" resolve issues in such a way that doesn't accidentally flag (say) a grazing corner hit as the in
  303 hit for a clean hit pair much further down the shotline (which will result in a long "solid" segment through empty
  304 space.)