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