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