User:Phoenix/GSoc2012/Reports

Log

Community Bonding

• May 2
  • Downloaded the source code of the latest revision from svn checkout and got more familiar with subversion.
  • Compiled and built the source both in Ubuntu and Windows (Visual Studio 2010) successfully.
• May 13
  • Found and fixed a small bug in eto_brep (the rotation axis of eto is wrong), and submitted a patch on sourceforge.net.
• May 15
  • Modified the eto_brep patch with the test case provided by Cliff.
• May 16
  • Continued working on the conversion of eto.
  • Tested the brep conversion of hyp, but found the raytrace result of implicit CSG hyp quite strange.
• May 17
  • The raytrace of implicit hyp is wrong when H is not perpendicular to A.
  • Fixed the conversion to brep of hyp (havn't commited yet).
• May 18
  • My first SVN Commit: fixed the shearing direction of hyp.

Week 1

• May 21
  • Fixed the bug of wrong id & od for pipe b-rep, by changing some prevp to curp.
  • Dealt with duplicated points by deleting them from the linklist.
• May 22
  • Added some control to deal with special cases in pipe_brep.cpp and add a few comments.
• May 23
  • Read and tried to understood the code in revolve_brep.cpp, but got confused by the implicit definition.
  • Changed the revolution axis and origin of the sketch plane of revolve_brep.
• May 24
  • Changed the position of the sketch in extrude_brep according to the parameters.
  • Fixed the plane direction of circle arcs in sketch_brep as well as in revolve_brep.
• May 25
  • Dealt with non-full revolution of revolve_brep. It took a long time to get the expected result, but I got more familiar to NURBS/BREP during that procedure.

Week 2

• May 27
  • Tested and examined the implemented brep conversions. Checked the current status of my work.
• May 28
  • Added the implicit -> brep conversion to conversion.sh, so that massive testing will be more convenient.
• May 29
  • Tested the functionality of conversion.sh and brep conversions. Made a small change.
  • Modified brep.c in libged to check whether the conversion is successful.
• May 30
  • Read the code in clone.c, and began to implement the temporary unevaluated conversion of comb in the brep command in MGED.
• May 31
  • Extended the functionality of the brep command in MGED to deal with comb. Unevaluated breps are generated. More tests are needed.
• June 1
  • The unevaluated conversion for comb has been implemented. Changed conversion.sh accordingly. And the whole elasped time for each object is evaluated.
  • Handled some exceptions in brep_debug.cpp.
  • Freed memories and corrected the "name existed" output in brep.c in libged.
• June 2
  • Tested the brep conversion on ktank.g, m35.g, etc. with conversion.sh.
  • Modified brep_debug.cpp to deal with empty combs.

Week 3

• June 3
  • Fixed the wrong malloc size and freed tmpname before returning in brep_debug.cpp.
• June 4
  • Modified openNUBRS_ext.cpp to quell set-but-unused warnings.
  • Tested brep conversion of all /db/*.g files. Looked into the log to find out what to do next.
  • Found a bug in pipe_brep.cpp dealing with colinear points.
• June 5
  • Modified pipe_brep.cpp. It's much better now, but problems still remain.
• June 6
  • Fixed a concealed bug in pipe_brep.cpp. Now it works properly.
• June 7
  • Fixed the destruction failure in pipe_brep.cpp by duplicating the curves.
• June 8
  • Modified brep_debug.cpp to skip the conversion of half when converting a comb. The implicit primitive of half remains in the hierarchy.
  • Explored the usage of ON_BrepRegion to represent an infinite halfspace, but had no good luck.

Week 4

• June 11 - June 18
  • Final examination week in our school.

Week 5

• June 18
  • Final exams finished. Started to work!
  • Added pnts to the ignore list when converting a comb.
  • Modified the describe and ifree functions in pnts.c checking whether count==0 to avoid segmentation fault.
• June 19
  • Corrected the wrong comments in arb8_brep.cpp and arbn_brep.cpp.
  • Add a brep conversion function to ars, which first converts it to an nmg and then to b-rep.
• June 20
  • Use ft_brep functions for half and pnts, returning a NULL brep pointer, and check within brep_conversion() and brep_conversion_tree().
• June 21
  • Tried implementing rt_part_brep() for primitive part. Things get much closer now after much tests and modifications.
• June 22
  • Finished a raw version of brep conversion for part. Some special cases need to be considered later.
• June 23
  • Enhanced some special cases (sphere) in part_brep.cpp.

Week 6

• June 24
  • Fixed the wrong normal direction of the brep form of part.
• June 25
  • Studied the primitive metaball. Found it quite hard to get started.
• June 26
  • Studied the two papers Cliff provided on metaballs, but still cannot find the answer.
  • Copied the transformation matrix when converting the leaves in a tree. (Later adjusted to copying all data from the old tree first)
• June 27
  • Evaluated the results and uploaded the screenshots to the log page. (See "Test Results")
  • Modified dsp_brep.cpp, using the dsp_stom matrix to do the transformation, instead of using the magic numbers.
• June 28
  • Implemented a b-rep conversion function for superell.
• June 29
  • Tested the results of conversion of superell. (See below)
• June 30
  • Uploaded the raytracing results of superells with e or n > 2.

Week 7

• July 2
  • Added conversion functions to cline. We first convert cline to an implicit pipe, and then convert the pipe to b-rep.
• July 3
  • Modified superell_brep.cpp to generate multiple surfaces for superells with e or n > 2.
  • Uploaded images with the modified b-rep conversion routine for superell.
• July 4
  • Uploaded images of the raytrace results of cline (both implicit and b-rep).
  • Fixed the wrong weight when the center (origin) is set to be control points (superell_brep.cpp).
• July 5
  • Some minor modifications on brep_debug.cpp, half_brep.cpp and pnts_brep.cpp.
  • Add a b-rep conversion function to grip, but it just returns a NULL ON_Brep pointer because grip is a pseudo solid and doesn't have its own shape.
• July 6
  • Implemented degree reduction to Bezier curves to simplify the representation of the dsp top surface. But still a long way to go. As I tested it with terra.g, the result made me very upset. There were great differences in the middle of the curves. For dsp with smaller xcnt & ycnt, the result was quite accurate. But it's big xcnt & ycnt that counts, because this is introduced to shorten the raytrace time of dsp with large maps.
  • TODO: Calculate the accumulated deviation. A torelance value TOL might be used to decide whether the result is acceptable or not. Or replace it with a better algorithm. (e.g. The specific way for DSP Cliff mentioned in E-mail)
• July 7
  • Thought over the specific way to reduce control points on the dsp top surface, but found that finding local minimum and maximum is not quite suitable for Bezier surfaces as this results in non-uniform control points (cannot form a rectangular grid). To keep it uniform may result in even nothing reduced at last. So I'd like to go on with the corrent routines at present.

Week 8

• July 8
  • Added b-rep conversion function to hf: hf -> dsp -> brep.
• July 9
  • Added a tolerance variable to control the max error in degree reduction in dsp_brep.cpp.
  • Tested the results of b-rep conversion for dsp. For the 30*30 displacement map, it can be reduced to 16*26 within the tolerance (see the images below), while the 256*256 map in terra.g can only reduced to 254*254 within the tolerance (maybe a bigger tolerance value should be used).
  • Next step for my project: start studying and implementing NURBS surface-surface intersection. (http://brlcad.org/wiki/NURBS_Intersections) Even if I cannot completely finished this project as there is not much time left in this summer, adding some useful "pieces" of it can still be helpful.
• July 10
  • Read some papers on surface-surface intersection. It's really a HARD project. Two approaches came to mind:
  • 1. Using subdivision methods. The two surfaces can be decomposed into small parts, and the calculation turns to the intersection of these small parts. Two papers Cliff offered seem to use this method (One uses surface triangulation, the other uses small bounding boxes). It might be a rather simple approach, but I'm worried about the performance and accuracy of this method.
  • 2. Using marching algorithms. This approach usually achieve good performance, but lots of math is required. After I went through several papers, I still cannot come up with a complete solution of the first step: Finding starting points using curve-surface intersection. So although this method sounds quite ideal, but the reality is that it's not easy to implement it.
• July 11
  • No longer used dynamic memory allocations in hf_brep.cpp.
  • Add comment to mark the unused functions in primitives/brep/brep.cpp.
  • Went on studying papers on NURBS surface-surface intersection and read the existing code in brep.cpp as well as opennurbs_ext.cpp(h). Things got much closer, but discussions are still needed before a final solution is formed.

Test Results

The brep conversion has been tested on several db/*.g files. Below are the screenshots of the raytrace results.

• m35.g: component (left: implicit + csg, right: brep + csg)

• ktank.g: tank (left: implicit + csg, right: brep + csg)

• havoc.g: havoc (the raytrace of brep+csg takes a too long time, so the result hasn't been generated yet)

• A DSP primitive with a 30*30 map: (first: implicit, second: brep, third: reduced to a 16*26 map (sorry for the slightly different views))

• Brep form of superell primitives with axes of the same magnitude: (left: n = 0.8, e = 0.2, right: n = 1.0, e = 2.0)
  • Reference page: http://paulbourke.net/geometry/superellipse/

• • There is still some problems when n > 2 or e > 2. (left: n = 0.2, e = 3.0, right: n = e = 3.0)

• • The problem above was fixed in r51405. (first: n = 0.2, e = 3.0, second: n = e = 3.0, third: n = 3.0, e = 0.2)

• A cline primitive raytraced in different views. You can see that it's a primitive whose raytrace is view-dependent. We use a pipe to represent it when it's converted to b-rep, whose raytrace is view-independent. The shape of the pipe is according to what we see when plotting a cline with the draw command in MGED. (Two different views, left: implicit, right: brep)

Original development timeline

• - May 21 (~4 weeks)
  • Study materials on NURBS/BREP etc
  • Read the codes in librt/primitives
  • Get familiar to OpenNURBS
  • Fix some bugs and make patches
  • Implement a method for convenient testing (finished)

• May 21 - June 10 (~3 weeks)
  • Modify implemented conversions if not finished
    • pipe
    • sph, ell, tor, hyp
    • eto, extrude, revolve, etc.

• June 11 - June 18 (~1 week)
  • Final examination week in our school

• June 19 - July 1 (~2 weeks)
  • Still work on existing conversions
  • Work on non-origin primitives
    • Deduce transformation matrices
    • Apply the transformation
    • Test the results and write documents

• July 1 - July 29 (~4 weeks)
  • Add new conversions to missing primitives
    • Test whether it works well
    • Write clear documents
    • From easy ones to hard ones
  • July 1 - July 8 (1 week)
    • rec
    • ars
    • half
    • ell1
  • July 8 - July 15 (1 week)
    • metaball
    • pnts
    • part
    • grip
  • July 15 - July 22 (1 week)
    • superell
    • cline
  • July 22 - July 29 (1 week)
    • hf
    • other missing primitives

• July 29 - August 13 (~2 week)
  • Write a convert for whole
    • Write a function to walk the tree
    • Add a command to MGED
    • Discussions and documents
  • Test the work and fix bugs

• August 13 - August 20 (~1 week)
  • Pencil down data
    • Improve documentation
    • Evaluations

• Post-GSoc
  • Further involvement with BRL-CAD :)