Editing User:Phoenix/GSoc2013/Reports


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 181: Line 181:
*** Set the pointer to NULL after it's deleted otherwise Split() will failed if the pointer is passed in.
*** Set the pointer to NULL after it's deleted otherwise Split() will failed if the pointer is passed in.
** Tested on the an extreme geometry provided by Cliff, and figured out what I should do next for the overlap case of SSI.
** Tested on the an extreme geometry provided by Cliff, and figured out what I should do next for the overlap case of SSI.
* July 25
** Fix a bug in linking overlap segments (the index should start from 0)
** Use surface normals to help determine overlaps. The normals of the two surfaces should be parallel.
** Modified the CSI sub-division routine. The sub-division should only stops when the curve is linear AND the surface is planar. Otherwise there might be problems with csx_overlap.
** Continued to modify the surface-surface overlaps with the test case: extreme_ssi_test.g (added to source tree). The modification is not finished yet.
* July 26
** Improved SSI with the extreme test case.
*** Used a struct to represent the overlap segments. Split the curves with the intersection points (with other curves), so that we can get closed regions.
*** Fixed a bug that cause sub_curve() to crash.
== Week 7 ==
* July 28
** Removed debug messages.
** Uploaded test result (2D intersection curves) of extreme_ssi_test.g.
** Still some work needed before we can have the final result.
* July 29
** Generating 2D overlapping curves in CSI used to have a wrong ordered point list. Fixed this by ignoring some inner points.
** Removed the duplicated overlap curves.
** There is something wrong with the screen of my laptop. So I sent it to repair. Hope I can get it back soon and continue to work.
* July 30
** Struggled to build up the environment using virtual machines on our school's computer since I cannot use my own laptop now.
** Fixed the wrong logic of determining whether a bounding box (or a point) is inside an overlap region or not.
* July 31
** Discussed about r56303 on the mailing list.
** Take the tolerance into consideration when deciding whether a box is inside the overlap region.
** Delete the OverlapSegment when its curves are NULL.
** Some code clean up
*** Eliminate compiler warnings.
*** Avoid using dynamic memory allocation for the events.
*** Use build_curve_root() instead of duplicating that routine.
*** Use sub_curve() instead of repeating that routine.
* Aug 1
** Testing "brep arb8.brep intersect ehy.brep 0 1 on csgbrep.g" failed. It seemed that J.invert() doesn't work. Used explicit pseudo-inverse.
** Some code clean up.
** Tried to implement PSI in a similar fashion of other intersections, so that further the surface tree structures can be easily reused during different intersections.
* Aug 2
** Reuse the surface trees and curve trees during multiple intersections to reduce repeat computation.
** Tested the SSI and fixed several bugs:
*** The tests on the overlap cases failed again. Tracked the changed since the last correct routine to find the problem.
*** Found several slight bugs and fixed them, and the result is correct now.
*** Committed the changes separately.
* Aug 3
** More powerful handling for the direction of overlap curves. Try another two options if the mid point is not sufficient.
** Upload the final result of the extreme case.
== Mid-term summary ==
The week 7 is the mid-term evaluations. During the first half of GSoC, I focused on the NURBS intersections, implemented P/P, P/C, P/S, C/C, C/S intersections, and also made lots of improvements on the SSI implemented last year, e.g. Newton iterations, overlap cases. Now according to the schedule, we are going to the next half of GSoC next week, and I'll start working on evaluating NURBS booleans.
A friendly remind of how to tests my results. If you want to have a quick test on P/P, P/C and P/S, you can run src/libbrep/test_point_intersect, or src/libbrep/test_curve_intersect for C/C and C/S. If you want to test SSI, you need to run librt/tests/test_ssi, but it doesn't have build-in test cases, so you need to specify a .g file, and the objects in it. Also, you can use the brep command in MGED, which can test all of these six intersections.
== Week 8 ==
* Aug 5
** Start to work on evaluating NURBS booleans.
*** Move the existing code in librt (written last summer) to libbrep, and use a separated file libbrep/boolean.c.
*** Fixed a small bug in the existing code (m_curveA => m_curveB)
** Help eliminate compiler warnings (and errors) in other files.
* Aug 6
** Make sub_curve() a global export function, and mark all other functions that should be only used within intersect.cpp with HIDDEN.
** Revisited the code in libbrep/boolean.cpp, and lots of updates:
*** Used ON_Curve rather than ON_NurbsCurve for better generality.
*** Eliminated the polyline curve assumption.
** Tests the existed boolean evaluations, and found problems that I'm going to fix. (brep arb8.brep u ehy.brep union for csgbrep.g)
* Aug 7
** Modified split_trimmed_face() in libbrep/boolean.cpp
*** Fixed some bugs.
*** Used an enum to improve readablity of m_in_out.
*** Special handling for the first and last point.
*** Multiple inner loops (using std::vector)
*** Implemented IsPointInsideLoop() to help determine a curve is completely inside a loop or not.
** Fixed a bug in CCI
*** The result after the Newton iterations might be nan.
* Aug 8
** Modified add_elements()
*** Added vertexes correctly.
*** Use ON_Curve rather than ON_NurbsCurve to reduce unnecessary conversions.
** Fixed a bug in splitting surfaces - if the SSI event is not curves events, we don't need to do anything.
** Found some cases that SSI curves may intersect, and the surface splitting routine only assumes that they are non-intersecting chains. Struggled to find a way to deal with this.
* Aug 9
** Fixed two bugs in split_trimmed_surface()
*** Don't call Split() when t is on the boundary of domain.
*** The first point is not always on the first segment, so we might need to duplicate more than one segments.
** Linked the curves if they share an end point
*** They can be from intersections with different surfaces
*** Or they are discontinuous in the other surface's domain, so not linked originally.
== Week 9 ==
* Aug 12
** Continued working on splitting trimmed faces.
*** Implement a function to check the validity of the outer loop before adding a trimmed face.
** Some code clean up in libbrep/boolean.cpp.
* Aug 13
** Modified split_trimmed_face().
*** Take care of the intersection tolerance, and "fix" the "gaps" if necessary.
*** Fixed bugs - NormalizedParameterAt() => ParameterAt(); floating point comparisons.
*** Renamed a used macro (DEBUG => DEBUG_BREP_BOOLEAN)
* Aug 14
** Used a better method to determine m_in_out - don't always assume that the starting point is outside, but use IsPointInsideLoop() to check around that point to determine it's going inside or outside.
** Some other minor modifications - move link_curves() to ON_Boolean(), and ignore ssx_overlap curves when partitioning the face.
* Aug 15
** Tried improving surface partitioning
*** Handled the case when an SSI curve overlaps with the outer loop.
*** Implemented get_subcurve_inside_faces().
*** Ignored UNSET IntersectPoints when maintaining the stack.
* Aug 16
** Finished surface partitioning
*** Eliminated the usage of sorted_pointers[] - once the array intersect[] is enlarged (with a new capacity), the pointers stored in sorted_pointers[] is no longer valid.
*** Tests, verification, and some minor changes.
*** Code clean up and added comment.
== Week 10 ==
* Aug 19
** Studied the paper about connectivity graphs.
** Added basic support of connectivity graph. And built connectivity graphs for the original structure.
*** Tests and fixed bugs.
* Aug 20
** Struggled to find a way updating the connectivity graph after surface partitioning.
*** More information about the edge sharing during the splitting procedure is needed.
*** Tried several ways but sucked, and finally came out an awkward implementation.
* Aug 21
** Continued working on connectivity graphs
*** Defined a macro to make the connectivity graph an optional choice.
*** Use an array of intervals to represent which part of the parent's outer loop that a TrimmedFace occupies.
* Aug 22
** Code clean up - rename class members with "m_" prefix, use ON_ClassArray rather than "new" and "delete" operators.
** Keep the information of the usage of SSI curve, so that we can know the connection between two trimmed faces (split from two surfaces), and get the connectivity graph of the new geometry after boolean evaluation.
* Aug 23
** Keep the original curve segments in LinkedCurve so that we can then share an edge with a neighboring face after we get the final evaluated structure.
*** But this is still not enough. Maybe it should be postponed until we get to that stage, so that we can know actually what information are needed.
** Start to work on inside/outside tests
*** Use curve-surface intersections to determine a point is inside a Brep or not.
*** Sean suggests using rt_brep_shot(). I'll look into that routine in brep.cpp (using for NURBS ray tracing) and find what can be reused.
== Week 11 ==
* Aug 25
** Looked into rt_brep_shot(). It needs to build the whole surface tree before we can process. I think it's not a good option for our inside/outside test. With CSI, deciding whether a point is inside a brep is quite easy.
* Aug 26
** Implemented IsFaceInsideBrep() to decide whether a trimmed face is inside another brep.
*** Used randomly generated points.
*** Used it to decide whether the trimmed faces belong to the final structure according to type of the operation.
** Modified the brep command in MGED.
* Aug 27
** Flip the face if necessary (according to the operation and original face's bRev)
** Made use of the connectivity graph to reduce inside/outside tests (if the USE_CONNECTIVITY_GRAPH flag is set).
** Upload images to the wiki to show the result of NURBS boolean evaluations (intersection).
* Aug 28
** Tried to pass ON_Brep::IsValid().
*** Added seaming trims, using the methods similar to the checking code in IsValid().
*** Dealt with singular trims and closed trims.
*** Solved trim & vertex mismatch.
* Aug 29
** Some code clean up.
** Fixed wrong face direction.
** Added another boolean operation - XOR.
** Tested boolean evaluations and uploaded result images.
* Aug 30
** Began to implement comb -> brep conversion, as the NURBS evaluations are ready now.
*** Currently we need to pass the db_i* param all the way, because the comb tree only stores the names in the leaves, and we need the db to find the solid. Is there any more elegant way to deal with this?
== Week 12 ==
* Sept 2
** Solve some invalid ON_Brep representations
*** Avoid duplicated vertexes.
*** ISO type should be checked before we decide whether to share seam curves.
** Some code clean up.
* Sept 3
** Correctly reuse surface trees and curve trees.
* Sept 4
** Renamed some variables.
*** db => dbip
*** brep_conversion => single_conversion
** Performed Xform on the leaves.
** Checked 3D distance (not included in ON_Brep::IsValid()) when looking for seam trims.
** Generated the connectivity graph for the new solid (after evaluation)
** Discussions about db_i passing in rt_comb_brep().
* Sept 5
** Fixed wrong face direction of arbn => brep conversion
*** The problem existed in rt_nmg_brep().
** Fixed a bug in trimmed face splitting
*** Pointers may be invalid if the ON_SimpleArray's capacity is enlarged.
* Sept 6
** Tests and fixed some bugs in libbrep/boolean.cpp
*** get_subcurve_inside_face(): It should be the intersection of the two merged intervals, not union. And there might be no intersections (e.g. for an inner loop)
*** A slight bug: m_a => m_b (wrong param used)
*** Uploaded images to wiki.
== Week 13 ==
* Sept 9
** The school starts...
** Improved the boolean evaluations
*** Use the same surface if they are split from the same face.
*** Fix wrong vertex for the singular trims.
*** Detect whether the surfaces are the same - don't need SSI if they are the same.
* Sept 10
** Surface equality checking
*** Also checked their degree (order) and knots
** "Robustness Issues"
*** Improve inside/outside tests for the cases with overlap surfaces.
* Sept 11
** Some minor changes in libbrep/boolean.cpp
** Installed and studied valgrind
*** Fixed memory leaks in test_point_intersect and test_curve_intersect.
* Sept 12
** Continued using valgrind to fix the memory leaks.
*** boolean.cpp
*** SSI (intersect.cpp)
* Sept 13
** Still fixing memory leaks.
*** Face splitting.
*** Tree conversion.
*** Passed valgrind tests well after lots of efforts.
== Week 14 ==
* Sept 16
** Scheduled pencils down date...
** Begin to do some code clean up and improve documentations
*** Use rt_db_internal instead of ON_Brep for the interface between libged and librt.
* Sept 17
** Added an "--no-evaluation" option, using the old routine of converting comb without NURBS evaluations (CSG tree + brep)
** Scrub the code.
* Sept 18
** Scrub the code - src/libbrep/intersect.cpp
*** Reused sub_curve() and sub_surface().
*** Added and corrected some comments.
* Sept 19
** Rewrite the code of merging intervals in CCI and CSI
*** Use only one pending interval.
** Corrected some comments.
* Sept 20
** Added more comment to the code, to make it more understandable.
== Final summary ==
* During GSoC '13, I implemented 6 independent intersection routines (point/point, point/curve, point/surface, curve/curve, curve/surface and surface/surface), tested and verified them, and they proved to be robust with the input I gave (even the extreme case). The most challenging task is the overlap cases in SSI (the result is 2D rather than 1D), which takes several weeks and hundreds lines of code.
* After mid-term evaluation, I started to focus on NURBS boolean evaluations with the well-performed intersection routines. The main steps include splitting a trimmed face, inside/outside tests and forming the final b-rep structure. I'm pleased that I stayed on schedule during all these time, and finally finished a working NURBS evaluation routine and COMB conversion. Connectivity graphs take quite a lot of time to implement, and still not completed in some way (e.g. the information lost after the evaluation, because the edges are not shared), but it doesn't effect the performance a lot so finally we just disable this option. If it turns out to be useful later, we can enable it again, and do some modifications if needed.
= Test Results =
= Test Results =
Line 443: Line 218:
** We intersect two surfaces that are exactly the same. Maybe this case can be optimized (Detect it's a duplicated surface and return the boundary of the whole surface directly).
** We intersect two surfaces that are exactly the same. Maybe this case can be optimized (Detect it's a duplicated surface and return the boundary of the whole surface directly).
** [[Image:completely_overlap.png]]
** [[Image:completely_overlap.png]]
* The extreme test case (src/librt/tests/extreme_ssi_test.g):
** The 2D intersect curves generated as sketch primitives by test_ssi: test_ssi extreme_ssi_tests.g surface_1.s surface_2.s 0 0 (the 2D curves on surface A and those on surface B is the same). (New: the right one includes two intersection curves)
** [[Image:Five rec.png]]        [[Image:extreme_final.png]]
* NURBS boolean evaluations (intersection)
** An arb8 and an ehy (left: original structures; right: result of intersection)
** [[Image:arb8_ehy.png]]        [[Image:arb8_ehy_inter.png]]
** A sph and a torus (left: original structures; right: result of intersection)
** [[Image:ehy_tor.png]]        [[Image:ehy_tor_inter.png]]
** Two spheres (first: result of union; second: result of intersection; third: result of difference)
** [[Image:union_sph.png]]        [[Image:sph_sph_inter.png]]        [[Image:diff_sph.png]]
** Two arb8 (first: union, second: intersection, third: diff)
** [[Image:Arb union.png]]        [[Image:Arb intersect.png]]        [[Image:Arb diff.png]]
= Original development timeline =
= Original development timeline =

Please note that all contributions to BRL-CAD may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see BRL-CAD:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)