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 to get a more robust one, I still need lots of work on it this summer. Lots of tests and verification are needed, and maybe a TDD (Test Driven Development) can be used in this step. To get the SSI working in all cases, no matter what the input is like is very important, otherwise it would be useless. |
− | + | The remaining part of evaluating NURBS was done in a rush last summer, with lots of features still missing (definitely cannot work now). So in this summer, if there is enough time, 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 partitioning a surface, and building the new NURBS geometry. If there's still some time remaining, I will tried to do more tests and verification to make the implementation better. | |
= Detailed description = | = Detailed description = | ||
Line 23: | Line 23: | ||
This are basis of SSI, and can be used in dealing with some degenerated issues in SSI. So I'd like to implement this in the very beginning of my schedule. Like the surface-surface intersection, the subdivision algorithm can be a good candidate in these intersection problems, as BRL-CAD already has the functionality of generating curve trees and surface trees (see src/libbrep/opennurbs_ext.cpp). So for example, in the C/C cases, we can generate the curve trees of the two curves, calculating the intersections of the bounding boxes, and get the intersection point with triangular approximations. In C/S cases, the intersections should be between curve trees and surface trees. | This are basis of SSI, and can be used in dealing with some degenerated issues in SSI. So I'd like to implement this in the very beginning of my schedule. Like the surface-surface intersection, the subdivision algorithm can be a good candidate in these intersection problems, as BRL-CAD already has the functionality of generating curve trees and surface trees (see src/libbrep/opennurbs_ext.cpp). So for example, in the C/C cases, we can generate the curve trees of the two curves, calculating the intersections of the bounding boxes, and get the intersection point with triangular approximations. In C/S cases, the intersections should be between curve trees and surface trees. | ||
− | The paper [3] is good reference on defining intersection problems, but its calculations are based on numerical analysis, which I think can be easily suffered from floating point precision and accuracy (for high dimension problems like C/C, C/S and S/S), so I would like to use the subdivision method instead, which already proves good functionality in the SSI implemented. | + | The paper [3] is good reference on defining intersection problems, but its calculations are based on numerical analysis, which I think can be easily suffered from floating point precision and accuracy (for high dimension problems like C/C, C/S and S/S), so I would like to use the subdivision method instead, which already proves good functionality in the SSI implemented. In the other hand, the openNURBS library has strong evaluation support which can be very helpful in P/P, P/C and P/S. |
Just like SSI, lots of tests and verification are needed in all these intersection problems. Some corner cases need to be considered as well. For example, two curves can touch at the endpoints, and a curve can have some part residing on the surface (that is, the intersection is a curve instead of a point, which is the general case). I should try to make the implementation as robust as possible, and it SHOULD work in all cases regardless of the input. Otherwise, the robustness of SSI can be affected, if it has some part based on lower dimensional intersection routines. | Just like SSI, lots of tests and verification are needed in all these intersection problems. Some corner cases need to be considered as well. For example, two curves can touch at the endpoints, and a curve can have some part residing on the surface (that is, the intersection is a curve instead of a point, which is the general case). I should try to make the implementation as robust as possible, and it SHOULD work in all cases regardless of the input. Otherwise, the robustness of SSI can be affected, if it has some part based on lower dimensional intersection routines. | ||
Line 43: | Line 43: | ||
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. A test driven development scheme can be adopted here. | 4) We should test more cases and find more problems in the intersection routine, and fix them to get better performance. A test driven development scheme can be adopted here. | ||
− | 5 | + | 5) Some code re-factoring is needed, and comments should be added to make the code more readable. |
− | |||
− | |||
The goal of this part is to get a robust routine of SSI that can work in all cases, so the most important parts are test, validation and verification. Until after the routine is proved to pass strict tests can we move to the next step. | The goal of this part is to get a robust routine of SSI that can work in all cases, so the most important parts are test, validation and verification. Until after the routine is proved to pass strict tests can we move to the next step. | ||
For more detailed in tests and verification, see the part below: More on tests and verification. | For more detailed in tests and verification, see the part below: More on tests and verification. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== 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 73: | ||
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. | ||
Line 99: | Line 79: | ||
As Cliff suggests, the code in src/librt/test_bot2nurbs.cpp may help illustrate how the structures can be built up. The brep structural assembly itself (curves/edges/surfaces/faces/etc.) may be helpful. | As Cliff suggests, the code in src/librt/test_bot2nurbs.cpp may help illustrate how the structures can be built up. The brep structural assembly itself (curves/edges/surfaces/faces/etc.) may be helpful. | ||
− | == | + | == 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 | + | 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. | 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. | ||
Line 124: | Line 90: | ||
[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 |
* Other intersection supports: P/P, P/C, P/S, C/C, and C/S | * Other intersection supports: P/P, P/C, P/S, C/C, and C/S | ||
* NURBS evaluation support | * NURBS evaluation support | ||
Line 140: | Line 98: | ||
= 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 | ||
** Some code clean up in the current SSI routine | ** Some code clean up in the current SSI routine | ||
− | + | * June 17 - June 30 (2 weeks) | |
− | * June 17 - June | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
** 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 | ||
Line 213: | Line 163: | ||
= Things I have done this year = | = Things I have done this year = | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |