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 3: | Line 3: | ||
= 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. | ||
Line 69: | Line 67: | ||
The newer version of openNURBS has removed the code related to ON_X_EVENT. So I'd like to put all this code in libbrep (move the existed one in openNURBS to libbrep, and add the extensions to libbrep), so that we won't need to worry about conflicts with the newer openNURBS. | The newer version of openNURBS has removed the code related to ON_X_EVENT. So I'd like to put all this code in libbrep (move the existed one in openNURBS to libbrep, and add the extensions to libbrep), so that we won't need to worry about conflicts with the newer openNURBS. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
== 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 128: | Line 121: | ||
[4] http://www.math.uiuc.edu/~nmd/temp/hass3.pdf | [4] http://www.math.uiuc.edu/~nmd/temp/hass3.pdf | ||
− | |||
− | |||
− | |||
− | |||
= Deliverables = | = Deliverables = | ||
Line 214: | Line 203: | ||
= Things I have done this year = | = Things I have done this year = | ||
* Add a test program in librt to test the functionality of SSI. (Commit revision 55252) | * Add a test program in librt to test the functionality of SSI. (Commit revision 55252) | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |