User:Phoenix/GSoc2012/Proposal

Project title

Implicit to NURBS conversion

Brief summary

At present, BRL-CAD has implemented lots of geometric primitives in a implicit form, but when it comes to interactive shaded displays and conversion to other formats, the disadvantages of implicit primitives come out. So we need a conversion to NURBS bundary representations. Lots of primitives have already been implemented as NURBS, but some are not robust and some still need to be improved. This summer, if I'm accepted, I'm going to accomplish the goal of converting all (if needed) implicit primitives to NURBS, fixing the bugs and correcting the errors existing now, and add new conversions that have not been implemented yet. Finally, I'd like to build a converter that converts primitives in a CSG model altogether to NURBS forms. The original version is a good starting point, and I will take the current routines of BRL-CAD.

Detailed description

Introduction

Although I have read a few books on Computer Graphics before, I'm not very familiar with NURBS/BREP before I started preparing for the application. These days I have read a lot of materials relevant and read the codes of BRL-CAD, so now I have a deeper understand of what I'm going to do in this project, and some patches related to this project have been made. Below is my detailed proposal for the project. In the first part I'd like to show what BRL-CAD has already done in the implicit to NURBS conversion. Then I will tell you detailed things I'm going to do in my summer.

Works already done in BRL-CAD

The conversion of implicit primitives to NURBS in BRL-CAD can be seen in functions rt_*_brep() in src/librt/primitives/, and the conversion of each primitive is done in a seperate function. The executable file csgbrep.exe can call most of them to produce NURBS represtations of many primitives together.

This work is significantly dependent on the OpenNURBS library as its basic NURBS support. The conversion of some implicit primitives such as sphere(sph), ellipsoid(ell), torus(tor), just call the relevant function in OpenNURBS to build the NURBS representation. The data structures to describe NURBS is based on OpenNURBS.

Although lots of work has been done in BRL-CAD already, some bugs still exist and some work is still located at the mathematical orgin. It may not work well if the parameters are changed in some occasions. And some primitives are still not included. The robustness need to be improved and the missing ones should be added.

For example,

• The primitives 'sph', 'ell', 'hyp', after converted to brep, always stay centered at the origin even if the centers of the implicit primitives are set to a non-origin point.
• When the implicit primitive 'eto' is converted to brep, its shape may change.
• The primitive 'extrude', has problems both in its position and shape after the conversion from implicit to brep.

Proposal ideas

As there has been a lot of work done in BRL-CAD already in this field, so I should continue the work following the current routines and try my best to make it better.

First of all, I'd like to fix the problems remained in the current version. Some are listed above, and more are going to be discovered and added to the list(like revolve, which seems quite strange now). For example, I should get primitives like pipe working for a wide variety of primitive dimensions. Besides, I should provide the conversion of primitives at locations other than the origin. As for this, I should deduce the transmation matrices that are needed to transform the BREP at the origin back to the 3-space location where the CSG implicit is, including scaling (most already done in BRL-CAD), rotating, shearing and translating. Matrix transformations are applied to the control points of the NURBS surfaces to make the changes. These days I have done some work on this and the results seem quiet good. The codes in other primitives that already work well can be referred to when I need help. In a word, to determine and apply the transmation matrices for non-origin CSG primitives is also an important part of this project. My background in linear algebra might offer me great help, I hope.:)

During my coding, I should always keep in mind writing maintainable, portable and complete code. To keep a good habit of coding is really important.

After doing something on the implemented conversions, I'd like to add more new conversions from implicit primitives to NURBS. For example, the conversions of implicit primitives like ars, half, part, grip, superell, metaball and so on. Study the current code as examples may be of great help. Implementation of conversions of different primitives still have lots of things in common, like creating a curve and rotate it, creating surfaces, etc. And the comments in librt/primitives can tell me the concrete algorithms I should use to deal with that kind of primitives. By the way, I should really learn more about the classes and functions in OpenNURBS, which provides basic support for our NURBS representation. I need to get full use of the library of OpenNURBS to implement my own methods, like bezier curves, surfaces, etc. As well as the others, the new implemented conversions should not be only for primitives located at the origin, and I should try my best to make the result as robust as possible.

To test the result of conversions, I am going to replace the implicit primitives in the CSG tree with the NURBS representation, raytrace the whole model to see whether it is changed. Once I found some mistakes in my conversion like overflows, I should modify my code immediately.

Finally, after finish all the rt_*_brep() functions for all primitives that would be included in a model, I am going to write a conversion function which walks the CSG tree and converts the implicit primitives to NURBS. The conversion function may be available in MGED, using an object or the whole model as its parameter.

The detailed schedule of my summer is as below.

Deliverables

• The remained problems with implemented conversions like ehy, hyp, revolve, sph, ell, tor, extrude, pipe, etc. are fixed. Patches will be updated promptly.
• Conversions of non-orgin located primitives are implemented (if they have not been implimented now)
• The missing conversions of implicit primitives are implemented.
• At last a converter working for a whole model is built.

Development schedule

• - 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

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

• June 19 - July 1 (~2 weeks)
  • Still work on existing conversions
  • Work on non-origin primitives
    • Deduce transformation matrices
    • Apply the transformation
    • Test whether it works well

• July 1 - July29 (~4 weeks)
  • Add new conversions to missing primitives
  • Test whether it works well
  • 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
    • Test the work and fix bugs

• August 5 - August 13 (~1 week)
  • Write a convert for whole

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

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

Time availability

I will have lots of free time during my summer vacation, so time is not a problem. I can work about 8 hours a day and 7 days a week. I'll have the final exams during June 11 to June 18, which takes about a week.

Things I have done now (Patches)

I have made patches related to the project I'm applying. The original revision(48890) of functions rt_ell_brep(), rt_ehy_brep() and rt_hyp_brep() cannot deal with objects centered at a non-origin point. I add rotation, translation and shearing matrices and apply them to do the transformation. They work quiet well in my tests. I hope it's a good start point for my work.

The patches have been uploaded to sourceforge.net.

Why BRL-CAD

I'm really interested in computer graphics, and BRL-CAD is an excellent open-source CAD software. I think working for BRL-CAD is an interesting and meaningful experience, and I can learn much from it.

Why me

I'm good at mathematics, and this project needs lots of math knowledge. I'm also good at programming in C++. And I have made some patches on the functions I'm going to deal with in this project, which makes me confident that I can do a good job in this project.

My opinions to GSoC

I think I will get lots of practice if I participate in this project, and I hope to continue work for BRL-CAD, because once I start I cannot stop myself. I am really interested in working for BRL-CAD, and I found open source is such an interesting place.