User:Phoenix/GSoc2013/Reports

Log

Community bonding

• May 28
  • Create the log page
  • Things have done:
    • Test program for SSI and a test geometry file
    • Some improvement with SSI and API design
• June 3
  • As I will have my final exams during the first week that coding begins, so I'd like to move some work ahead.
  • Begin to add P/P, P/C and P/S support. Implement ON_PX_EVENT for reporting the intersections.
  • TODO: Implement P/C, P/S and ON_PX_EVENT::IsValid().
• June 4
  • Eliminate max_dis in the brep command for SSI.
  • Extended the brep command to handle P/P, P/C, P/S, C/C and C/S.
  • Modified the wiki page of the brep command.
  • Fix the format of ON_PX_EVENT::Dump(). (Add "\n")
• June 7
  • Try to add PS support using get_closest_point().
  • Test the functionality of the PS function - it seems that there's a problem when try (0,0,5) on a sphere of radius 5 and centered at the origin (it should be an intersect, but get_closest_point() returns (0,0,-5) resulting in no intersections).
• June 12
  • Calculate point-curve intersection using sub-division.
  • Do some simple testing on PCI. It works.

Week 1

• June 17
  • Coding period begins!
  • Put the tolerance into consideration in the IsPointIn() test in PCI.
  • Write a test program on sphere to test P/P, P/C and P/S.
    • It seems that get_closest_point() is not always robust. :( Maybe it's not a good choice for P/S.
• June 18
  • Use macros to represent default tolerance and change it to 0.001 (the same as the default tolerance of curve/curve, curve/surface, surface/surface defined by openNURBS)
  • Consider the input u_domain and v_domain for the result of point-surface intersection.
• June 19
  • Busy with the course projects and preparing a final exam. Didn't have much time for BRL-CAD.
• June 20
  • Found the problem causing get_closest_point() to fail
    • get_closest_point() sometimes give us the 'farthest' point.
    • => getClosestPointEstimate() didn't work.
    • => The surface tree are not built correctly.
    • => It seems that we inappropriately prepTrims when m_removeTrimmed is false, causing get_closest_point() to fail. Someone who wrote this code needs to check whether this change is correct.
  • Use a smaller depth for PSI to improve performance.
• June 21
  • Added Newton-Raphson iteration in PCI to improve accuracy (using the one from subdivision and linear approximation as a starting point)
    • After test, it can work with tolerance set to ON_ZERO_TOLERANCE!

Week 2

• June 24
  • The plane was delayed for a long time. It took almost the whole day to get to Beijing. :(
  • Set removeTrimmed to false, otherwise the surface tree cannot be built correctly - since the last change raised a raytrace problem.
• June 25
  • Began to implement curve-curve intersections.
    • First using sub-division to find the intersecting bounding boxes.
    • Then use Newton-Raphson iterations to get an accurate result.
    • Finally check the validity of the solutions and check overlap.
  • More tests and improvements are needed.
  • Added the new CCI and CSI functions to brep_debug.cpp.
• June 26
  • Improvements and bug fixing of curve-curve intersection
    • Add tolerance value in the bounding box intersections.
    • Check duplication before appending to the array x.
    • In the Newton-Raphson iterations, if the inverse fails, we try another two directions.
    • More work on the tolerance value to get a more accurate and correct result.
  • Add a test program for curve-curve intersections.
• June 27
  • Continued improving curve-curve intersection
    • Merge the overlap events that are continuous.
    • Eliminate the intersection points that are inside the overlap events.
    • Some special handling for linear curves.
  • Add another test for overlaps.
• June 28
  • More work on CCI
    • Assign values to m_a[1], m_A[1], etc. even if it's ccx_point event (according to openNURBS declarations in other/openNURBS/opennurbs_x.h)
    • Fixed the wrong curve used in detecting overlaps.
  • Added more comments to document the intersection approaches.
  • Studied materials on curve-surface intersections and ready to get started.

Week 3

• July 1
  • Began to implement curve-surface intersections
    • Use sub-division and Newton-Raphson iterations.
    • It's similar to curve-curve intersections.
• July 2
  • Added tests for curve-surface intersections.
  • Improved curve-surface intersections
    • Check the endpoints of the line segment when computing its intersection with a boundary plane.
    • Consider NaN.
    • Add fabs() when calculating the line_t.
  • Fixed a typo in brep.c ("CS" for curve-surface rather than "PC").
• July 3
  • Added another test for CSI (line & torus).
  • Continued improving curve-surface intersections.
    • Reused surface tree - avoid generating the surface tree again and again.
    • Added some special splitting machanism for polylines.
    • Comparing doubles cannot use minus directly.
    • If the starting point is good enough, we don't need Newton iterations.
    • When merging, m_b should be consistent with m_a.
    • Values of 3D and 2D spaces should have different tolerances. And consider the 2D tolerance when merging.
• July 4
  • Started to work on surface-surface intersections (TDD)
    • Did some clean up to the original code.
    • Split the two steps (intersecting bounding boxes and triangular approximation).
    • Dealt with single points, and checked validity of the solutions.
  • Using tests (csgbrep.g): brep sph.brep intersect tor.brep 0 0
• July 5
  • Improve SSI
    • Dealt with surface boundaries (using CSI).
    • Some special handling for closed surfaces - added function closed_domain().
    • Eliminated duplicated points using a naive approach.

Week 4

• July 8
  • Continued SSI
    • Fixed bugs of triangle intersections - wrong line_normal for B, floating point issues (== is not sufficient), coincident planes cases, and calculate the barycentric coordination with ON_Solve2x2() in case that the inversion fails.
    • Calculate max_dis using the length of bounding box diagonal, in case that both volumes are zero.
  • Modified brep_debug.cpp and test_ssi.cpp to deal with intersection points (use spheres to represent the points).
• July 9
  • Uploaded some test images to this log with arb_intersect.g.

Test Results

• src/librt/tests/arb_intersect.g
  • Intersection point: brep A_brep intersect B_brep 0 4 (The intersection point is marked with a sphere)
    • 
  • Intersection curve (a line segment): brep A_brep intersect B_brep 0 1 (The intersection line is marked as green and purple)
    • 
• csgbrep.g
  • brep tor.brep intersect sph.brep 0 0
    • 2 intersection curves (2 circles)
    • 
    • 3D intersection curves (generated by test_ssi as pipe primitives)
    • 
    • 2D intersection curves (generated by test_ssi as sketch primitives): as you can see, they are two line segments.
    • 
    • Intersection event 1:

m_type: ssx_transverse

SurfaceA: ON_LineCurve: domain = [0,1] start = (0, 0.36691490883042999, 0) end = (1, 0.36691712614187172, 0) length = 1 SurfaceB: ON_LineCurve: domain = [0,31.4159] start = (2.4074124304840448e-035, 8.9939819000822325, 0) end = (31.415926535897931, 8.9939878497144115, 0) length = 31.4159 3D curves: ON_PolylineCurve: domain = [0,1025] point[ 0] = (4.5999999999999996, 0, -1.9595917942265422), 0 point[ 1] = (4.5998905557122152, 0.020185674600015011, -1.9595567114130974), 1 point[ 2] = (4.5997202800800228, 0.050938325997351139, -1.9595567114130974), 2

Original development timeline

• - June 17 (~4 weeks)
  • Study the papers on this topic
  • Discuss with other developers
  • Some code clean up in the current SSI routine
  • Write a test program to test SSI
• June 17 - June 23 (1 week)
  • Lower dimension intersections
    • P/P, P/C, P/S
    • With the support of openNURBS
  • Tests and documentations
• June 24 - July 7 (2 weeks)
  • Intersections regarding curves
    • C/C, C/S
    • Subdivision - curve trees, surface trees
  • Tests and documentations
• July 7 - Aug. 4 (4 weeks)
  • TDD on SSI
    • Test the SSI
    • Find the problems
    • Fix the bugs
    • Find more bugs and fix them
    • Degenerated cases
  • Try to get the code faster
    • Fit the curve to a lower order if possible
  • Documentations
    • Comment in code
    • Write some extra document on SSI (algorithms, problems, TODOs...)
  • Mid-term evaluation in July 29 - Aug. 2
• Aug. 5 - Aug. 18 (2 weeks)
  • Finish the surface partitioning
    • Polygon partitioning
    • Curve-curve intersection
  • Tests
    • Trims may intersect
• Aug. 19 - Aug. 25 (1 week)
  • Add connectivity graph support
    • Generate connectivity graphs for objects
    • Design proper data structures for the graph
• Aug. 26 - Sept. 1 (1 week)
  • Inside-outside tests
    • Curve-surface intersection
    • BFS of the graph to determine inside/outside
• Sept. 2 - Sept. 8 (1 week)
  • Generate valid ON_Brep objects
    • Read code in IsValid() functions
    • Add elements (trim, edge, etc.)
    • Try to pass the validation
  • Extend the brep command in MGED
• Sept. 9 - Sept. 15
  • Robustness Issues
    • Deal with the degenerated cases
    • All 3 steps should be modified
  • Tests
    • Fix bugs
    • Improve performance
• Sept. 16 - Sept. 22 (1 week)
  • Pencils down
    • Code clean up
    • Documentation (wiki pages)
• Sept. 23 - Sept. 27 (1 week)
  • Final evaluation
  • Submit code to Google