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.)