BREP TODO ========= Included below is a basic work breakdown related to the implementation of boundary representation (BREP) support in BRL-CAD. Feel free to add to or expand this list and/or embellish it with additional information as appropriate. If you would like to work on the BREP implementation, send a note to the brlcad-devel mailing list. This file is a general scratch pad for categorizing and itemizing BREP implementation tasks. It is not an implementation plan. This is a work in progress. Geometry Entities ----------------- point line (e.g., line segment, ray, bidirectionally infinite line) line set (e.g., polyline, polygon) curve (e.g., spline, arc, circle, ellipse) plane surface (e.g., spline, polygonal) surface+curve (i.e. a trimmed surface) solid Geometry Evaluation ------------------- point -> point point -> line point -> curve point -> plane point -> surface point -> surface+curve point -> solid line -> line line -> curve line -> plane line -> surface line -> surface+curve line -> solid curve -> curve curve -> plane curve -> surface curve -> surface+curve curve -> solid plane -> plane plane -> surface plane -> surface+curve plane -> solid surface -> surface surface -> surface+curve surface -> solid surface+curve -> surface+curve surface+curve -> solid solid -> solid Geometry Queries ---------------- [ geometric properties ] intersects inside outside on intersectionSet firstIntersectionSet closestDistance closestSet (e.g., closestPoint) booleanEvaluation insideSet (e.g., insideSolid, insideLoop (trimmed)) outsideSet onSet [ parametric properties ] uvSpace <--> ImageSpace Mapping (for ALL primitive types) curvatures normalSet (e.g., normalVector, normalPlane) tangentSet (e.g., tangentVectors, tangentPlanes) [ checks ] isValid isSolid isManifold isFlat [ bounding volumes ] boundingBox boundingSphere Geometry Modifiers ------------------ scale rotate translate shear mirror copy/clone delete invertRepresentation evaluateBoolean (i.e. CSG) snapTogether (e.g., | -) sweep extrude revolve extend/stretch trim (e.g., cutting plane) split (i.e. copy and two trims) fillet chamfer Ray Tracing ----------- intersectionSet query boundingBox line -> solid evaluation normalSet query line -> solid evaluation line->solid evaluation line->surface || line->plane line->plane line->line line->surface line->curve || line->line closestDistance closestDistance point->plane point->point line->curve line->point line->line line->point line->point point->point Interactive Visualization ------------------------- implicit primitive to solid conversion solid on solid CSG evaluation (i.e. unevaluated to evaluated BREP) solid tessellation Conversion ---------- 3DM to BRL-CAD BRL-CAD to 3DM STEP to BRL-CAD IGES to BRL-CAD BRL-CAD to STEP BRL-CAD to IGES ******************************************************************************** Below are some thoughts and notes about specific issues related to the above topics - may be useful as comments at some point, or at least food for thought. ******************************************************************************** /* * Point-Point Evaluation * * Answer Evaluation Questions involving two points: * * 1. Intersection - for a point, there are three possible categories of of intersection: * * Identical - point values identical and all bound values identical * * * * * * * * * * * * * * * 1 2 * * * * * * * * * * * * * * * * * * * * * * * Contained - values not all identical but bounds of the point of interest all smaller than bounds of * point it is being compared to * * * * * * * * * * * * * * * * * * * * * * * * * 1 * * * * * * * * * * * * * * * * * * * * * * * * * 1 * * * * * 2 * * * * * * * * * * * * * 2 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Overlapping - values not all identical but bounds of the point of interest all overlap bounds of * the point it is being compared to. (Note: a corner case is when the value of the upper * bound of one point is equal to the lower bound of the other - this is defined to be * overlapping.) * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 * * * * 1 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 2 * * * * 2 * * 2 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 2. Outside - "If the points are not identical in value and/or error bounds, is the point of interest and its error * bounds contained or overlapping with the comparison point, or vice versa? If not, the point of interest is * outside the comparison point. * * Contained and Overlapping points present a problem. Take the case where two points have an overlapping bound * and a third point must decide its relationship with each of them: * * * * * * * * * * * * * * * 1 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 2 * * 3 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Point 1 and Point 2 overlap and may intersect. When Point 3 evaluates its relationships with Point 1 and * Point 2, it finds that it overlaps and may intersect Point 1, but it does NOT overlap Point 3. This means * that Point 1 may intersect Point 2 OR Point 3, but NOT both at the same time. Any assumption of equality * involving any of these three points must decide how to handle this situation, and the decision must be both * consistent and reproducible. The possible decisions are: * * 1 = 2, 1 != 3 * 1 != 2, 1 = 3 * * In order to have a concrete method for deciding this question, point evaluation cannot be a local, two point * only test. It is necessary to search out all points which overlap the two points in question (i.e. the only * points which might impact the decisions of which points are identical in this particular case) and resolve the * question amongst all of them. One possibility would be to assemble all the guaranteed non-equalities among * the set, search for the shortest distance between values among the remaining possible relationships, and assign * intersection status based on those results. (This may not be sufficient - bounding box size may also be * important.) For the original two points supplied, the question of intersection or non-intersection is now * resolved as long as no geometry changes are made to any element that has bounds overlapping their individual * bound. * * Once this near space evaluation is done, each point's list of intersecting and non-intersecting points is updated. * A query routine with two points can first check the points' own intersection/non-intersection lists to see if * the answer is already pre-determined. If it is not, determining via the bounds inside/outside is straightforward * and deterministic and it cannot be intersecting. * * One question is what to do when the geometry DOES change. New geometry may potentially change the decisions * on what is and is not intersecting - perhaps it should? Potential trouble there with overlapping vs. non- * overlapping regions. */ SOLID NURBS RAYTRACING ROBUSTNESS IMPROVEMENT/REFINEMENT One of the difficult tasks with solid raytracing is determining reliably when we're inside or outside in cases where BRep edges don't exactly join up geometrically. OpenNURBS has tolerances which define such shapes as "valid", but the mathematics of the ray interesection will still report wonky results once hit points get inside those tolerance regions. We have resolution logic that tries to handle ambiguous cases, but one potential technique we are not currently using would use the bounding box information from the NURBS prep trees to augment that logic's robustness (or, more precisely, bound the portions of the ray segment within which point ambiguities need to be resolved.) The current thought is to use the not-on-surface-point bounding box points (which we can categorize as inside or outside relative to the surface they are bounding by construting vectors from on surface points to those points and comparing them to the surface normal vectors) and the surface points themselves to construct an outer and inner bounding volume for the BRep (to be reliable, we would also have to take care that we refine enough to avoid self intersections in those volumes.) The overall bounding box of the outer volume should always be larger than that of the inner volume, 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 surface normals. (Might actually also allow us to reliably detect and fix such BReps, but that's a different topic.) Once we have the outer bounding volume, we intersect that along with the NURBS BRep itself and use the ray segments from the outer bounding volume as bounding regions within which we resolve any point ambiguities. This should allow us to "locally" resolve issues in such a way that doesn't accidentally flag (say) a grazing corner hit as the in hit for a clean hit pair much further down the shotline (which will result in a long "solid" segment through empty space.)