Editing User:Phoenix/GSoc2013/Proposal
From BRL-CAD
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
= Project title = | = Project title = | ||
− | NURBS Intersection | + | NURBS Intersection & Evaluation |
= Brief summary = | = Brief summary = | ||
− | BRL-CAD | + | Last summer I tried to do something on NURBS surface-surface intersection for BRL-CAD, but due to the limitation of time I cannot completely finish this project. I have implemented a routine to compute the intersection curves of two NURBS surfaces, and in general cases it works well, but some improvement are still needed. And the remaining part was done in a rush, with lots of features still missing. So in this summer, I would like to continue to work on this project, finishing the remaining parts, and finally offer a routine to convert CSG combination objects to evaluated NURBS objects. The work includes but is not limited to: (1) improve the current SSI routine to deal with special cases; (2) split the surfaces with the intersection curves we get in (1); (3) combine the new trimmed faces to get a new evaluated model. If there's still some time remaining, I will tried some other interesting topics, like NURBS editing in mged/archer, or anything that have great priority in BRL-CAD. |
− | |||
− | |||
= Detailed description = | = Detailed description = | ||
== Introduction == | == Introduction == | ||
− | NURBS surface-surface intersection is still a high-priority project in BRL-CAD. NURBS is a dominant geometric representation format in CADs, so we need to have enough support for it in BRL-CAD. Currently most objects in BRL-CAD are modeled in CSG, when converted to NURBS representations, the primitives are first converted to NURBS primitives, which BRL-CAD supports, but the next step is missing - evaluate the boolean operations on NURBS primitives, and then get | + | NURBS surface-surface intersection is still a high-priority project in BRL-CAD. NURBS is a dominant geometric representation format in CADs, so we need to have enough support for it in BRL-CAD. Currently most objects in BRL-CAD are modeled in CSG, when converted to NURBS representations, the primitives are first converted to NURBS primitives, which BRL-CAD supports, but the next step is missing - evaluate the boolean operations on NURBS primitives, and then get a evaluated NURBS combination as the original CSG combination object. Currently BRL-CAD only gives ``CSG tree + unevaluated NURBS primitives", so we need NURBS intersections and evaluations. |
− | Below is my detailed proposal for this summer's project. In the first part, I'd like to mention the current status of this | + | Below is my detailed proposal for this summer's project. In the first part, I'd like to mention the current status of this part left out last summer. Then I list my plan on how to implement the remaining parts, dividing into three parts. In addition, something I want to do if I have additional time will be listed. At last, I'd like to show you the schedule and what I have already done this year about this project. |
== The current status of NURBS intersections & evaluations == | == The current status of NURBS intersections & evaluations == | ||
− | Last year I spent about a month on NURBS intersections after I almost finished the Implicit to NURBS conversion project. I implemented a surface-surface intersection routine, using the sub-division method referred in a paper [1]. Now it can give us the intersection curves of two NURBS surfaces in both 3D spaces and 2D uv spaces. If the two inputs are in good condition, the result is quite reasonable (For detailed information, please see my last year's development log, there will be some convincing figures). But when the two surfaces have some coincides | + | Last year I spent about a month on NURBS intersections after I almost finished the Implicit to NURBS conversion project. I implemented a surface-surface intersection routine, using the sub-division method referred in a paper [1]. Now it can give us the intersection curves of two NURBS surfaces in both 3D spaces and 2D uv spaces. If the two inputs are in good condition, the result is quite reasonable (For detailed information, please see my last year's development log, there will be some convincing figures). But when the two surfaces have some coincides, the routine may have problems, because it first calculates the intersection of surfaces' bounding boxes, and then use polylines to approximate the curves, however, in this case, we should get a surface, not some curves. And for some strange shaped surfaces, the accuracy of the output may be not ideal. (max_dis can be inputted manually to get a better result, but it's a burden for users) |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | And I also tried to calculate boolean operations on NURBS. I just focus on the union of two spheres, which is a well-conditioning problem, and tried to get a evaluated model which can pass the IsValid check offered by openNURBS, but failed. So this part only have many lines of code written, but doesn't have enough functionality, and lots of work ahead should be done. | ||
== Calculating surface-surface intersection curves == | == Calculating surface-surface intersection curves == | ||
The function calculating NURBS surface-surface intersection curves is in /src/libbrep/opennurbs_ext.cpp: | The function calculating NURBS surface-surface intersection curves is in /src/libbrep/opennurbs_ext.cpp: | ||
Line 43: | Line 31: | ||
1) If we detect there are many intersection points that seems to form a surface, not just curves, that it seems that these may exist an intersection 'surface'. But finding out this is quite confusing, because that may be some cases where two surfaces have many intersection curves that are very close to each other, but they don't have anywhere coincide. (The paper [2] considers such degenerate overlap issues in Part 4.3 Robustness issues) | 1) If we detect there are many intersection points that seems to form a surface, not just curves, that it seems that these may exist an intersection 'surface'. But finding out this is quite confusing, because that may be some cases where two surfaces have many intersection curves that are very close to each other, but they don't have anywhere coincide. (The paper [2] considers such degenerate overlap issues in Part 4.3 Robustness issues) | ||
− | 2) There should be some detection related to the two surfaces when merging polylines (the 3rd step of SSI), not just using the max_dis parameter. In some cases, there may be two segments that should be in one intersection curve have bigger distance than two segments that exists in two nearby intersection curves, but we tend to merge the latter two segments instead of the former, without that detection. | + | 2) There should be some detection related to the two surfaces when merging polylines (the 3rd step of SSI), not just using the max_dis parameter. In some cases, there may be two segments that should be in one intersection curve have bigger distance than two segments that exists in two nearby intersection curves, but we tend to merge the latter two segments instead of the former, without that detection. |
− | + | 3)Detecting loops. Note: only loops in the 2D uv space is of interest, those in 3D space is just for displaying, not very useful in the later evaluation process. A loop in the 3D space may not be a loop in the 2D space. | |
− | 4) We should test more cases and find more problems in the intersection routine, and fix them to get better performance. | + | 4) We should test more cases and find more problems in the intersection routine, and fix them to get better performance. For example, two surfaces have many parts that intersects, resulting in many strange-shaped intersection curves. |
− | 5 | + | 5) Some code re-factoring is needed, and comments should be added to make the code more readable. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== Split the surfaces and generate new trimmed sub-surfaces using intersection curves == | == Split the surfaces and generate new trimmed sub-surfaces using intersection curves == | ||
Line 93: | Line 57: | ||
As for how to perform inside/outside tests - we use curve-surface intersection - computing the number of intersections of a semi-infinite ray emanating from a point with the solid, and if the number is odd, the point is inside the solid, otherwise it's outside. | As for how to perform inside/outside tests - we use curve-surface intersection - computing the number of intersections of a semi-infinite ray emanating from a point with the solid, and if the number is odd, the point is inside the solid, otherwise it's outside. | ||
− | Operations include: union, difference, intersection. | + | Operations include: union, difference, intersection. |
Finally we generate the ON_Brep object. Lots of elements should be added - edges, curves, trims, etc. and the ON_Brep::IsValid() will check. Read the code in IsValid() functions will help us know what a valid ON_Brep shbuld look like. The code in add_elements() in /src/librt/primitives/brep/brep.cpp has some basic routine but is far from complete. | Finally we generate the ON_Brep object. Lots of elements should be added - edges, curves, trims, etc. and the ON_Brep::IsValid() will check. Read the code in IsValid() functions will help us know what a valid ON_Brep shbuld look like. The code in add_elements() in /src/librt/primitives/brep/brep.cpp has some basic routine but is far from complete. | ||
− | + | == Tests == | |
+ | First, some basic tests - e.g. two spheres have some part intersecting, an arb8 and a sph, etc. | ||
− | + | If the evaluation on basic primitives is satisfiable, more complicate tests should be performed. Finally, we should test on the /share/db/*.g files, and tried to convert the big models (m35, havoc) into evaluated NURBS models. | |
− | |||
− | + | Besides, the brep command in MGED should be extended, to support evaluations of NURBS objects (Don't forget the manual page). Maybe this command can also be migrated into archer. The conversion script (conversion.sh) should also be modified to generate evaluated NURBS. | |
− | + | == Other ideas == | |
− | + | If I finish my project beyond my schedule (just like last year), I will tried other projects, such as the NURBS related ones: [http://brlcad.org/wiki/NURBS_Editing_Support NURBS Editing support], [http://brlcad.org/wiki/Vector_Drawings_from_NURBS Vector Drawing from NURBS], etc. I'm quite familiar with NURBS after some projects, so I think I would be a good candidate for them. If BRL-CAD have other high-priority project, I would also like to have a try. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
= Links = | = Links = | ||
Line 124: | Line 75: | ||
[2] S. Krishnan, A. Narkhede, and D. Manocha. BOOLE: A System to Compute Boolean Combinations of Sculptured Solids. Technical Report TR95-008. Department of Computer Science, University of North Carolina, 1995. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.88 | [2] S. Krishnan, A. Narkhede, and D. Manocha. BOOLE: A System to Compute Boolean Combinations of Sculptured Solids. Technical Report TR95-008. Department of Computer Science, University of North Carolina, 1995. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.88 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
= Deliverables = | = Deliverables = | ||
− | * | + | * NURBS surface-surface intersection routines |
− | |||
* NURBS evaluation support | * NURBS evaluation support | ||
* CSG model to evaluated NURBS conversion | * CSG model to evaluated NURBS conversion | ||
= Development schedule = | = Development schedule = | ||
+ | As far as I'm concerned, I would like to focus on the second and third steps in the first part, as they are far from complete at present. I'm going to have a routine that 'can' work first, and then modify it to work 'well'. | ||
* - June 17 (~4 weeks) | * - June 17 (~4 weeks) | ||
** Study the papers on this topic | ** Study the papers on this topic | ||
− | ** Discuss with other | + | ** Discuss with other developer on implementations |
− | ** | + | ** Read the code in librt/libbrep/openNURBS |
− | + | ** Fix the bugs in the intersection curve computation | |
− | + | * June 17 - June 30 (2 weeks) | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | * | ||
− | |||
− | |||
− | |||
− | |||
** Finish the surface partitioning | ** Finish the surface partitioning | ||
*** Polygon partitioning | *** Polygon partitioning | ||
*** Curve-curve intersection | *** Curve-curve intersection | ||
** Tests | ** Tests | ||
− | * | + | * July 1 - July 7 (1 week) |
− | |||
** Add connectivity graph support | ** Add connectivity graph support | ||
*** Generate connectivity graphs for objects | *** Generate connectivity graphs for objects | ||
*** Design proper data structures for the graph | *** Design proper data structures for the graph | ||
− | * | + | * July 8 - July 14 (1 week) |
** Inside-outside tests | ** Inside-outside tests | ||
*** Curve-surface intersection | *** Curve-surface intersection | ||
*** BFS of the graph to determine inside/outside | *** BFS of the graph to determine inside/outside | ||
− | * | + | * July 15 - July 28 (2 weeks) |
** Generate valid ON_Brep objects | ** Generate valid ON_Brep objects | ||
*** Read code in IsValid() functions | *** Read code in IsValid() functions | ||
*** Add elements (trim, edge, etc.) | *** Add elements (trim, edge, etc.) | ||
*** Try to pass the validation | *** Try to pass the validation | ||
+ | * July 29 - Aug. 4 (1 week) | ||
+ | ** Mid-term evaluation | ||
+ | ** Some basic tests | ||
+ | *** Fix bugs | ||
+ | *** We have a routine that 'can' work | ||
** Extend the brep command in MGED | ** Extend the brep command in MGED | ||
− | * | + | * Aug. 5 - Aug. 18 (2 weeks) |
** Robustness Issues | ** Robustness Issues | ||
*** Deal with the degenerated cases | *** Deal with the degenerated cases | ||
*** All 3 steps should be modified | *** All 3 steps should be modified | ||
− | ** | + | * Aug. 19 - Sept. 1 (2 weeks) |
+ | ** More complicated tests | ||
*** Fix bugs | *** Fix bugs | ||
*** Improve performance | *** Improve performance | ||
+ | * Sept. 2 - Sept. 8 (1 week) | ||
+ | ** Evaluate a whole NURBS model | ||
+ | ** Convert large CSG models to evaluated NURBS | ||
+ | *** havoc, m35 | ||
+ | * Sept. 9 - Sept. 15 (1 week) | ||
+ | ** The conversion.sh script | ||
+ | *** Support evaluate NURBS conversion | ||
+ | ** Migrate the brep command to archer (optional) | ||
* Sept. 16 - Sept. 22 (1 week) | * Sept. 16 - Sept. 22 (1 week) | ||
** Pencils down | ** Pencils down | ||
*** Code clean up | *** Code clean up | ||
*** Documentation (wiki pages) | *** Documentation (wiki pages) | ||
− | * Sept. 23 - Sept. 27 | + | * Sept. 23 - Sept. 27 |
** Final evaluation | ** Final evaluation | ||
** Submit code to Google | ** Submit code to Google | ||
= Time availability = | = Time availability = | ||
− | |||
= Why BRL-CAD = | = Why BRL-CAD = | ||
− | |||
= Why me = | = Why me = | ||
− | |||
− | |||
= Things I have done this year = | = Things I have done this year = | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |