Difference between revisions of "User:Cprecup/GSoC2012 progress"

(10-11/07/2012 - removed entries from the hash table; memory for *value* allocated outside the hash table; freed memory for these values)
(13/07/2012 - progress summary, updated milestones, and planning a user-visible feature)
Line 1: Line 1:
=Coding period=
=Coding period=
===''Week 8''===
===''Week 8''===
* Summarized the progress made so far
* Updated the future milestones for this project
* Currently figuring out a plan for a user-visible feature in Archer/MGED, i.e., a command that would open a window displaying the graph corresponding to the displayed geometry.
* Allocated space for each ''value'' of an entry of a hash table outside the hash table. In the ''value'' field of an entry I've just copied the pointer to this memory space.
* Allocated space for each ''value'' of an entry of a hash table outside the hash table. In the ''value'' field of an entry I've just copied the pointer to this memory space.

Revision as of 19:37, 13 July 2012

Coding period

Week 8


  • Summarized the progress made so far
  • Updated the future milestones for this project
  • Currently figuring out a plan for a user-visible feature in Archer/MGED, i.e., a command that would open a window displaying the graph corresponding to the displayed geometry.


  • Allocated space for each value of an entry of a hash table outside the hash table. In the value field of an entry I've just copied the pointer to this memory space.
  • Implemented a method that frees the space allocated for these values.


  • Removed entries from the solids hash table whenever an object is discovered to be a region or a group. Switched to working with pointers for bu_hash_tbl structures. Freed memory for each allocation.


  • Made some small modifications on the src/libged/dag.cpp related to memory allocation.
  • Tried to deallocate memory for a certain entry in a hash table but didn't find a proper solution to this. In the hash.c I've only found the function bu_hash_tbl_free(struct bu_hash_tbl *hsh_tbl) which is not what I need because I don't want to deallocate the memory for the whole table but, instead, just for one entry. Need to find out how it's supposed to be done.

Week 7


  • Introduced id's for each object in the database and finished memorizing the data.
  • Taking into account what hash table it belongs to, each object has now a corresponding shape and (if needed) links to the nodes of its 'subtree' in the graph.
  • Duplication is now avoided because each shape of the router has a corresponding id.
Here's the graphical output for the share/brlcad/7.22.1/db/axis.g (that was put in a .svg file, for now): Graph link nodes no duplications.png
Compared to the one mentioned on 01/07/2012, one can observe that the number of nodes has been reduced to a single one in case of duplications. The links between the nodes are overlapping for now. This needs to be taken care of.


  • Continued working on the code that is meant to memorize data related to each object in a database into the three below mentioned hash tables.


  • Replaced the bu_ptbl structures with bu_hash_tbl for the three kinds of tables: regions, groups and solids.
  • Implemented code for adding bu_hash_entrys into the hash tables. Encountered some problems on this part as well as where I have to establish the size of each lists field in a hash table.


  • Found a way to eliminate node duplications depending on their names - use the struct bu_hash_tbl.


  • Fixed the representation of solid objects: instead of dashed line they are represented by rectangles now.
  • Introduced a temporary method for positioning the nodes into the graph.
  • Cleaned up the code and committed the changes.

Week 6


  • Managed to link each COMB node with the nodes of its subtree.
Here's the graphical output (that was put in a .svg file, for now): Graph link nodes.png
One can observe that for some nodes there are branches that link to other nodes. As a helper, here is the listed output of what the algorithm is doing in the background.
The order in which they were outputted is the one in which the directory was traversed. The alignment is due to a linear function that I used for the coordinates of the rectangles that represent each node. This needs to be modified as well as the duplicated nodes and the representation of solids (here, they appear as a single dash line instead of a rectangle).


  • Looked for an example that would give me hints on how to find and traverse a subtree of a combination in order to create actual links between the nodes. Decided that src/conv/g-dot.c is a good starting point.
  • Worked on the implementation of a method called dag_comb that is meant to create links between the COMB node and the ones from its subtree. Didn't commit anything because it's not finished and the code needs to be cleaned up eventually.


  • Looked in the src/tclscripts/geometree folder with the purpose of understanding how the MVC (model, view, controller) pattern is applied there.
  • Been suggested that it would be a good idea to create a graph image instead (for now). Therefore, I started working on the connections between different nodes in the graph.


  • Committed my latest changes:
  1. Added special cases for when the Adaptagrams library is found or not found. Don't add dag.cpp to ged_ignore_files if the library is not found; i.e., always compile it. -- src/libged/CMakeLists.txt
  2. Use the #define HAVE_ADAPTAGRAMS in the src/libged/dag.cpp file in order to be compiled regardless of the fact that libavoid exists or no. Fixed indentation. -- src/libged/dag.cpp
  3. Added a compile-time preprocessor #define HAVE_ADAPTAGRAMGS -- CMakeLists.txt
  • Started looking for .tcl files that I could use as examples and from which I could get methods for implementing a view. My attemp is to print out the hierachy structure build with the dag.cpp's methods in a user's window.

Week 5


  • After accessing the distcheck-enableall_release.log file I found out that the error wasn't generated because of my changes. There are usages of strcmp in the src/conv/g-voxel.c file that have to be replaced by bu_strcmp. After making this change, running the command
make distcheck

ended well.

  • There was a problem caused by the duplicated existence of a variable named PARALLEL. It was included by both libavoid.h and common.h so I had to figure out a way in which my program would compile and none of these two values would be lost/modified during the execution.


  • Introduced a HAVE_ADAPTAGRAMS #define and wrapped most of the code in src/libged/dag.cpp in a #ifdef - #endif. Still need to add the #else case that would provide a useful note stating that the library is unavailable.
  • Altered the src/libged/CMakeLists.txt file correspondingly.

Compilation is ok but the command

make distcheck

generates an error. I haven't yet figured out what the problem is.


  • Found a potential solution that could solve the below issue: I've compiled Adaptagrams with the flag -fPIC.
  • Discussed it with one of the mentors (brlcad). I was recommended to rather add a compile-time preprocessor define like HAVE_AVOID and enable linkage against the LIBAVOID_LIBRARY in the src/libged/CMakeLists.txt file than add the file to ged_ignore_files.


  • Currently, BRL-CAD doesn't build because my src/libged/dag.cpp can't access elements from the avoid library. BRL-CAD built in the previous attempts because I added a main function inside dag.cpp for which I would add the line
BRLCAD_ADDEXEC(dag dag.cpp avoid)

inside the CMakeLists.txt file.

The main function was added just for testing purpose so I didn't commit it. Without the main function, and adding ${AVOID_LIBRARY} with the BRLCAD_ADDLIB command generates this error.

So far, after doing a little research I came to the conclusion that this is because the libavoid library is static.


  • Fixed src/libged/CMakeLists.txt because make distcheck wouldn't work.
  • Added reference to the dag.cpp file for the OLD build system.

Week 4


  • Implemented methods that are used for adding a rectangle to the construction of the graph for each object in the database (please see src/libged/dag.cpp file).

For this, I have modified my previous implementation, more exactly, simplified it.

  • Eliminated search for the libavoid library from src/conv/CMakeLists.txt and added it into the folder src/libged/CMakeLists.txt.


Started implementing the model for a directed acyclic graph in the src/libged folder. So far, it contains a structure and a method that initializes elements of such a structure.


Looked through the src/libged, src/gtools and src/tclscripts folders for MVC pattern implementation. Still have doubts about how to structure the pattern in BRL-CAD.


Corrected the implementation mentioned below. Had a discussion about the proper locations for MVC implementation files.

Week 3


Worked on the C++ implementation of a class that contains methods similar to the ones in src/conv/g-dot.c. This approach remains to be debated.


By using the src/conv/g-dot.c I generated a .svg file that contains information about the graph's nodes, i.e., for each node that appears in a .dot file I generated a corresponding one by using libavoid.

The .svg file was generated and opened in a visual mode for checkup purposes: one rectangle per object in the hierarchy can be observed.


Managed to run a C++ Adaptagrams example(that uses libavoid) inside BRL-CAD.


  • Added helper script misc/CMake/FindADAPTAGRAMS.cmake to check for libavoid's existence as a system-installed library and mark as advanced the set variables.
  • Modified the cmake check for libavoid in src/conv/CMakeLists.txt accordingly.


Added a cmake check in src/conv/CMakeLists.txt in order to find the system-installed version of libavoid. If it doesn't find it, it prints a status message saying it couldn't find it - no error occurs in either cases (found or not found).

Week 2


Compilation of BRL-CAD failed because of some 'set but unused variable' warnings treated as errors. Commited a fix for one of them.

Started work on checking the existence of the libavoid library as a system-installed dependecy.


Started working on a file that would take each element of the tree and process it with libavoid's methods. As a support example I found the src/conv/g-dot.c file.

Failed attempt to integrate libavoid into BRL-CAD. After further discussions (03/06/2012) it was established that it's best to do this after I have the functionality going, somewhere in late July.


Tried to recompile an example.cpp file where the Adaptagrams' library is used outside its main folder. Previous attempt to do this was unsuccessful. I Managed to compile it after all.

Looked for a location where I could implement functions that would traverse a tree and construct a DAG with Adaptagrams' library.

I'm still trying to understand how librt/db_tree.c and db_walk.c work in the background.


Adaptagrams will be used as the library of tools.

I've made a plan that sketches what will happend on each side of the MVC pattern for this project.

The process behind the, let's call it for now, 'igl' (Interactive Graph Layout) command that lauches the GUI is the following:

  • access the geometry's hierarchy by using the 'tree' command with an additional option 'g' that returns the corresponding DAG.
  • traverse this graph and construct it with the help of Adaptagram's library libavoid. Libavoid provides polyline connector routing in order to avoid obstacle objects. The result is passed on to the Tcl/Tk implementation where it will be outputted (View).
  • on user action (for example: 'move' or 'delete' command is called), announce the Controller, apply modifications onto the graph by using libavoid.

Remark: other uses of Adaptagram's libraries should/may be added.


Used Adaptagrams' static libraries as external ones by creating a source code file that calls methods from these libraries.

Week 1


Studied Adaptagrams' documentation. Listed strong and weak points of both graph libraries, GOBLIN and Adaptagrams.


Compiled Adaptagrams; studied and ran examples provided for libcola and libavoid.


  1. Worked on compiling GOBLIN. However, I get a lot of errors. You can find them here. I am assuming it's because of the c++ standard and their latest update which was made in 2010. Submitted a bug on their sourceforge bug tracker and am waiting for a reply.
  2. Meanwhile, I'm having a look at the Adaptagrams' source code.


Made comparisons between Adaptagrams and GOBLIN.


Discussed with one of the mentors how to approach the implementation behind the command that would launch the GUI.

Talked about the possible locations where command-line functionality can be developed.

As a first step, looked for proper already existent functions in BRL-CAD that would allow me to ge the directed acyclic graph structure of a tree.


Read about Adaptagrams library.

Community bonding period

General progress


Studied some aspects of the GOBLIN graph library.


Commit access was gained. My first commit was for the src/libbu/test_booleanize.c file; it included style and formatting corrections.


Patch for the file src/libbu/booleanize.c was accepted and applied in the revision r50566.


I have modified my first patch, the one meant to create a test_booleanize.c with unit tests for the file src/libbu/booleanize.c. At the same time, I found a small bug in the booleanize.c code. The patch can be found here.


I have created an alternative patch for the one that is meant to separate out LIBNMG from LIBRT. This one 'moves' the files from the src/primitives/nmg location to src/libnmg without being needed an extra help from someone with commit access.

Here is a link to a temporary location for the patch since it exceeds the size limit provided by Sourceforge.


I have finished a patch meant to separate out LIBNMG from LIBRT. You can find the patch here. Build system modifications have been made in the following files:

  • src/librt/CMakeLists.txt
  • src/librt/Makefile.am

and the following 2 files have been correspondingly added for libnmg:

  • src/libnmg/CMakeLists.txt
  • src/librt/Makefile.am

One thing needs to be made by a person with commit access: move the src/librt/primitives/nmg source code into src/libnmg and apply the provided patch.

Reminder: there's also this patch that I've made and needs to be reviewed. It contains unit tests for the src/libbu/booleanize.c file and it fixes a small bug that wouldn't have passed one of the tests.


I've studied the src/mged, src/librt and src/conv folders, looking for methods that can be used to access the elements of a CSG tree.

Methods that got my attention:

  • in the src/librt/db_tree.c file:
int db_tree_list(struct bu_vls *vls, const union tree *tp)

which fills a bu_vls with a representation of a given tree appropriate for processing by Tcl scripts. Could be useful in constructing the interactive graph.

union tree *db_tree_parse(struct bu_vls *vls, const char *str, struct resource *resp)

which takes a TCL-style string description of a binary tree, as produced * by db_tree_list(), and reconstruct the in-memory form of that tree. Could be useful after the structure of the graph is modified and the CSG needs to be updated.

2. Get commit access


Worked on the patch for the NMG migration task (create a separate library LIBNMG outside LIBRT). This time, because BRL-CAD previously built without errors, things go smoother.

1. Compile & install BRL-CAD


After discussing my problem with one of the mentors and finding the cause for these errors, BRL-CAD completely built.


I created my first patch for BRL-CAD by using the virtual machine disk image so now I want to compile and install BRL-CAD from source (from a svn checkout).

I've followed the instructions with respect to the dependencies (the ones from here http://brlcad.org/wiki/Compiling and from the doc/README.Linux). I've used the command


but after using


, I kept getting these errors http://pastebin.mozilla.org/1602696.

Afterwards, I decided to try the command

cmake -DCMAKE_BUILD_TYPE=Debug .

but then I encountered another error while running it: http://pastebin.mozilla.org/1602697. I managed to solve the problem by installing itk3 and itk3-dev. However, while running the make command I bumped into the previously mentioned make errors and this one: http://pastebin.mozilla.org/1602700. The first ones refer to fontconfig symbols.