User:Clouddrift/GSoC2014

Personal Information

Name: Zhao Anqing

E-mail: zaqcloud@hotmail.com

IRC Username: Zhao_Anqing

Project Title

Mesh Library Cleanup

Synopsis

BRL-CAD has an extensive n-manifold (NMG) polygonal mesh library presently embedded within LIBRT. N-manifold can provide an arbitrary boundary representation structure. This part in BRL-CAD runs good but not perfect, for it is far from, as is expected, stable, rubost and easy-read. Sometimes it causes some awkward performance problem and some algorithm based on current NMG is inefficient. The purpose of this project is to clean, validate and verify relevant source code about NMG, and then add the missing Euler Operation to it.

Concepts

Some important concepts should be clarified before starting this project.

Manifold

Manifold representation is commonly used in many commercial boundary based solid modeling systems. Kinds of data structures are useful to describe manifold solid. In early years, wing-edge data structure is widely accepted by researchers and companies. With the development of related theories, the half-edge data structure appeared. Splitting an edge into two half-edge makes it more flexible than wing-edge, especially when iterating elements.

As a general solid representation, half-edge data structure is enough. The lower operations named Euler Operation can make sure the completeness and validity of the solid, and the higher operations such as sweeping, fillet and others enhance the usability. But in a CAD system, we will give a proper representation for other situation which can appear as the result of the standard and the regularized Bool Operation. For instance, several volumes or faces are only connected by a single vertex.

Non-manifold

To support the structure mentioned above, the core concept of this project, non-manifold is put forward. Unlike manifold, Non-manifold is a geometric modeling term referring to topological situations which are not restricted to be two-manifold. It can define not only volume but also surface, curve and point in a single uniform representation.

Compared with half-edge data structure, Weiler (the author of the paper[1]) proposes a new representation method, Radial Edge data structure, which extends half element from only edge to vertex, loop and face. Such change is worthy, though it makes the data structure more complex. The boundary elements may range from a surface(2D), an edge(1D), and a vertex(0D).

Detailed description

The current status of NMG

Now, this part of NMG is mainly located in raytrace.h and nmg.h where it is mixed with other irrelevant structs, macros and functions. It seems that these codes are moved to here and stacked together temporarily. The organization is not ideal for other developers to read, use and maintain.

Codes in nmg.h

Core NMG structure and relevant macros are defined in this file. Including:

• NMG elements (7): The basic parts of Radial Edge Data Structure, containing model, region, shell, face, loop, edge and vertex.
• NMG using elements (4): The using parts of Radial Edge Data Structure, containing faceuse, loopuse, edgeuse and vertexuse.
• Geometry structure: Bounding box information and kinds of geometric description for locating and shaping NMG elements.
• Allocation and Release macros: Memory management for NMG elements.
• Some test cases.

Codes in raytrace.h

The routines about NMG here are mainly operations or functions acting on basic NMG structure. Including:

• Creation: Create a new NMG element without geometry information.
• Removal: Remove specific element from an existing NMG element.
• Assignment: Assign geometry information to the specific topology.
• Modification: Modify the specific topology.
• Print: Give some information about the specific NMG element in form of string.
• Classification: Compute the relationship between two NMG elements, such as point and face, point and solid, and so on.
• Intersection: Compute the intersection result between two NMG elements, such as getting a point from two edges or a line from two faces.
• Count: Count the specific element in a NMG element.
• Other Functions.

Remove redundant code

For some reason, the NMG primitive is originally designed and implemented for a stand-alone NMG CAD. But the situation changed. Some levels of current NMG become redundant, since they are able to be replaced by some parts in database structure now. Including:

• model: represents the whole geometry, which is similar to the content of BRL-CAD *.g file.

• nmgregion: sub-level structure beneath model, which is similar to the BRL-CAD region struct.

• Maybe others.

I will remove them as well as relevant macros and functions to simplify the problem. In the process, I should make sure there is no side-effect or new trouble introduced.

Extract NMG to be a stand-alone library

The concept of manifold is critical to many parts of geometry and mathematical physics because it allows more complicated structures to be described and understood in a more understandable way. So it can and should be combined into a function-independent library. I will check each line of the code in LIBRT, then move the NMG parts into a new stand-alone library named LIBNMG.

Besides, just like what has been done in LIBBU, it will be more reasonable to divide the whole content into several header and code files, because accurate division can make code organization more clear.

Add comments

Complement some proper comments for each header file in the new-built LIBNMG library. I will obey following rules when writing comments.

• Header file: Entirely functional description.
• Struct: Complete description for whole struct and each member.
• Macro: Complete description for its function and purpose.
• Function: Complete description for input parameters, output parameters and main algorithm theories.

Unit test

According to the experience from other developers in community, it is absolute that lots of bugs are hidden in LIBNMG. So it is necessary to write a systematic set of test case. With more bugs discovered and fixed, the new-built library will be more readable and stable.

There is some similar work done in src/libbu/tests. Finishing the test cases by consulting these samples will help me avoid many unnecessary mistakes. And what's more important, it must be assured that they can operate normally in CMake which BRL-CAD use to build system.

Add Euler Operation

Euler operators are useful to manipulate manifold boundary graph based topology representations. It provides a flexible base for higher level operators while insulating them from the details and complexities of the data structures utilized. Euler operation is useful but is missed in current BRL-CAD. After the successful migration and reorganization of LIBNMG, adding Euler operation for BRL-CAD is necessary.

I will reliably add Euler Operation to the system and test them. I have experience in writing Euler Operation for an implement of manifold data structure before, so it will not baffle me. All types of Euler Operation will be included.

Construction Operators

• MVSF( v, f ): Create a new topology structure for manifold.
• MEV( v1, v2, e ): Create a new vertex v2 and connect it with an existing one v1 by edge e.
• MEF( v1, v2, f1, f2, e ): Connect two exist vertices, v1 and v2, on face f1, then create a new face f2 and a new edge e.
• MEKR( v1, v2, e ): Create a new edge e to connect two existing vertices, v1 and v2, then remove an inner loop from the face.
• MFKRH( f1, f2 ): Remove an inner loop on face f1, then create a new face f2 as well as remove a hole from model.

Destruction Operators

• KVSF(): Remove an existing topology structure which contains only one vertex.
• KEV( e, v ): Remove an existing edge e and an endpoint v of it.
• KEF( e ) : Remove an existing edge e and its adjacent face.
• KEMR( e ): Remove an existing edge e, then create a inner loop of its adjacent face.
• KFMRH( f1, f2 ): Remove an existing face f2 which is adjacent to face f1, then create an inner loop.

Auxiliary Operators

• SEMV( e1, v, e2 ): Split edge e1 into two segments to create a new vertex v1 and a new edge e2.
• JEKV( e1, e2 ): merge two adjacent edges, e1 and e2, then remove the common vertex.

Documentation

I referred to lots of date during my writing of this proposal. In the last part, for others who might be interested, I will explain how I approached this project and give some useful linked as well as a change list.

Schedule

• Preparation Step 1 (1 April - 18 April): Deeply understanding current logic relationship and program architecture concerning NMG.

• Preparation Step 2 (19 April - 18 May): Discuss with mentors/developers about the solution for removing redundant structs, moving into a stand-alone library, and so on. Try as much as possible to test and verify all possibilities.

• Week 1 (19 May - 25 May): Estimate completely the influence of removing abundant structs. Make sure nothing misses attention.

• Week 2 (26 May - 1 June): Remove the abundant structs and test briefly.

• Week 3 (2 June - 8 June): Move the NMG parts from LIBRT into a new-built library, LIBNMG.

• Week 4 - 5 (9 June - 22 June): Write test case, and make sure everything goes well just like before and to fix bugs found.

• Week 6 (23 June - 29 June): Prepare for the mid-evaluation.

• Week 7 - 9 (30 June - 20 July): Add Euler Operation.

• Week 10 (21 July - 27 July): Complement the comments for the new library.

• Week 11 (28 July - 3 August): Writing relevant documents.

• Week 12 - 13 (4 August - 17 August): Prepare for final-evaluation.

Brief background

I am a graduate student in State Key Lab of CAD & CG, School of Computer Science, Zhejiang University, China. I have 3 years' work experience in programming a CAD module for an Optical Critical Dimension system in a conductor measurement company using Open Cascade. Now, my main research direction is something about hexahedral mesh.

Why BRL-CAD

There is no doubt that an amount of commercial CAD software is outstanding and amazing, but their high price of each copy decides that not everyone could get such a CAD tool to try and improve their unconstrained idea. We need open source software to make people free, free, and free more. I like this open source CAD system and community. I believe it is worthy to contribute efforts for BRL-CAD. At the meantime, I can learn rich and irreplaceable experience in connection with CAD from this project and other developers.

Why me

I'm a graduate student of Zhejiang University, which is famous for its reputation in the field of CAD&CG research. I have good background in CAD theories and programming skills. Moreover, this project is mainly about NMG mesh which is to a large extent related to my research and work experience. I have written a CAD module for an optical measurement system, whose user-friendly interface promoted the company's sales. I am sure it is no problem for me to finish it with high quality in time.

And, I make sure I can dedicate at least 40 hours per week in this summer holiday. I understand clearly the importance of adequate communication with other experienced developers and theory experts, whose valuable suggestions can enormously save twists and turns.

References

[1] http://www.scorec.rpi.edu/REPORTS/1986-1.pdf

[2] http://sourceforge.net/p/brlcad/mailman/message/28536100