Annecy 2008

After the SBIM'08 workshop and during the last day of the Annecy Animation Film Festival, Saturday, I used some spare time to enjoy the city and its surroundings. In my rollerblades I went to Duingt, a small town in the left margin of the lake, a dozen kilometers south of Annecy. It was a quite pleasant trip in a cycleway by the lake. During that day I rollerbladed more than forty kilometers, the longest distance I have ever ride in a single day. But the conditions for that were great. If you're planning to visit Annecy I strongly recommend to consider taking your bike or skates with you. It's worthy.

Rollerblading in Annecy (France) surroundings

LSketchIt

Last week I've been in the fifth Eurographics workshop on sketch-based interfaces and modeling (SBIM'08). The workshop took place during the famous Annecy Animation Film Festival and was held together with the premier conference for techniques in expressive rendering and animation: the non photo realistic animation and rendering conference (NPAR'2008).

At the SBIM'08, I presented our more recent work on sketch based modeling (see paper "Using Sketches and Retrieval to Create LEGO Models"). The LSketchIt is a calligraphic tool for creating LEGO models that uses sketches and retrieval to ease and speed up the modeling process. Check out LSketchIt working in the demonstration video below.

LSketchIt demonstration video

Deleting VirusScan Enterprise quarantine files

I am using the Networks Associate VirusScan Enterprise 8.0 with patch 10 and found out that it was using more than 400MB to store the quarantined files. Version 8.5 provides a tool that allows users to manage these files, the Quarantine Manager. However, version 8.0 don't have such tool and I was not even able to manually delete the corresponding ".Vir" files, since they were locked by the application.

Fortunately, I found a solution to overcome this problem in the McAfee Support Forums. Indeed it is quite simple.To delete files in the Quarantine directory, on must disable the On-Access Scanner, and delete the file. After that it is important to remember to enable it again. Although it can be done using GUI, I present bellow the corresponding console commands:

% cd \quarantine
% net stop mcshield
% del *.Vir
% net start mcshield

Model complexity in ESB

I need to study the complexity of models in the PRECISE engineering shape benchmark (ESB) collection. Although such approximation is not always true, I considered that more complex objects contain more faces, while meshes with less triangles represent simpler models. Indeed, a simpler object might contain more faces than a more complex one, depending on the mesh. However, this is not common in the ESB collection and the face count is easy to estimate. From this estimation, I concluded that the majority of the models in this collection contain more than ten thousand polygons, as illustrated in chart below.

Distribution of models from ESB collection according to face count

Counting faces in STL files

To help me creating statistics on collections of 3D models I developed a small application that counts the faces of models stored in STL files. It can be used to analyze a single model or a collection of models. The first is done by specifying the corresponding STL file and the second by specifying the folder that contains the collection. If you think such application might be useful, you can download the windows binary [ZIP 71KB] or ask me the cross-platform source code.

Output produced by FaceCounter application

CAS name change

From discussions with colleagues from SMG at IMATI-Ge, we concluded that the name originally given to the decomposition algorithm was not the most appropriate. Indeed, it might lead to some confusion and misinterpretation. Therefore, we decided to change the algorithm name to "Collection-Aware Segmentation".

Goodbye Genoa

My fellowship at CNR IMATI-Ge finished last Friday. Thus, on Saturday morning I was packing and in the afternoon embarking on a ferry to Barcelona, from where I rode to Lisbon.

I want to thank everybody at the Shape Modeling Group for the way they welcomed and supported me: it was a pleasure to work with you, guys.

Waiting, with other motorcyclists, to went on board.

Godbye Genova.

In practice it is not so bad

After making some changes in the CAS algorithm and improving the prototype (basically, I write its core from scratch) I could study its behavior with larger collections. The results were positive because the growth of the shape pool is far below the simulated worst case. Indeed, after the third iteration the number of segments to add to shape pool decreases and within seventh iteration is very low. The chart bellow illustrates exactly this.

Shape pool growth (using a set of 273 models extracted from ESB)

CAS shape pool segment growth

As I was expecting, the context-aware segmentation (CAS) approach can potentially led to an exponential growth of the number of segments in the shape pool. Theoretically, if all the branches of the segmentation tree are expanded, after seven iterations the number of segments can grow so much that will be impossible to store in memory all their signatures. The charts below illustrate the worst case for two distinct collections with one and eight hundred models respectively.

Number of segments in shape pool

Memory necessary to store segment signatures

Writing CAS/HFP on XML file

Since I will now test the CAS/HFP algorithm with larger collections, I needed to devise a way to store the segmentation in order to be able to re-use it without having to process it again. Thus, I have implemented a feature that allows writing to (and reading from) a XML file the segmented collection. Moreover, the computed signatures for segments and corresponding similarities are also saved. Below is an excerpt of a XML file describing a collection decomposition.

Excerpt of XML decomposition file.

CAS/HFP versus HFP

During the last weeks I've been implementing the context-aware decomposition based on hierarchical fitting primitives (CAS/HFP) algorithm. Now that I finally have a working prototype, I was able to compare the result produced by CAS/HFP with the ones produced by applying only the hierarchical fiting primitives (HFP) segmentation. To that end I use a very small collection extracted from the PRECISE Engineering Shape Benchmark. Below I show the segmentation trees produced by the two algorithms for the same shape.

Decomposition tree produced by HFP

Decomposition tree produced by CAS/HFP

Me and C++, a love/hate relationship

It is not something new. It has always been like that. These last two days were just another example of this. Yesterday, I was cursing C++. I have been fighting to solve some major memory leaks on my code... and it was hard... I hate C++!!! Today I finally finished solving that problem and moved forward. Moved to a completely different issue. In this I apply the flexibility and power of C++ to implement an algorithm that can be compiled using only standard libraries or using wxWidgets (and taking advantage of it). The most beautiful point is that I did it in just a couple of hours and the only thing I now have to do, if I want to switch, is change a single line of code. Indeed, I love C++!!!

First approach to context-aware segmentation

In a first approach to context-aware segmentation (CAS), I have implemented a prototype that uses spherical harmonics descriptor and cord-and-angle histogram to estimate similarities between segments. This prototype decomposes all models in a given collection according to all others. Bellow is an example of a model extracted from the PRECISE Engineering Shape Benchmark and decomposed along with others from this benchmark using the CAS approach.

View of 3D model decomposed using CAS

I have took a few days off to spent with my family here in Genoa. Now they returned home and I'm back to work. Nevertheless, there were a short but very good vacations, where we had lots of fun. At least my son enjoyed everything. Specially the children's race track at Corso Italia.

My son riding on the children's race track

Shape Segmentation with HFP

I have just combined the fitting primitives mesh clustering (HFP) algorithm proposed by Marco Attene in is paper "Hierarchical mesh segmentation based on fitting primitives" with the prototype that produces the spherical harmonics descriptor (SHA) and cord and angle histogram (CAH) for a 3D model. The result is an application that decomposes a model using the HFP approach and then computes for each segment the corresponding descriptors. This application produces a navigable VRML file containing the segmented model. By clicking on segments it is possible to see the descriptors for that segment and even the segment alone or a possible random sampling. To view an example based on a model extracted from the ESB click on screen-shot below.

Screen-shot of shape description page.

Listing directory contents with C++

Listing the contents of a directory is a basic functionality. However, there are no standard C++ function to do it. Usually, for this purpose additional libraries are used, such as Boost or wxWidgets, since they provide lots of useful functionalities. But this time I just needed that my code was able to get the directory contents in both Windows and Linux. I was not interested including a bunch of unnecessary stuff.

Thus, based on a article by Daniel Schuller, I wrote a small piece of portable code that read the contents of a directory. A link for downloading the source file are available bellow:

• C++ code for listing directory contents
  

Computing Spherical Harmonics Descriptor

Based on work by Michael Kazhdan, I implemented a prototype that produces the spherical harmonics descriptor (SHA) for a 3D model. To that end I used not only the executables for computing SHA representations provided by Kazhdan, but also some code developed by Simone Marini to read the binary signatures. The results produced by my prototype for shape m87 from the PSB (the dog model I often use) are illustrated below. You can also take a look at the VRML file containing the 3D SHA representation of this model.

2D chart of SHA representation of dog model

3D view of SHA representation

Cold front but pleasant view

During the last few days a cold front hit Italy, making the thermometers show unusually low temperatures for this time of the year, together with strong winds. Despite off all the problems and inconvenience created by this bad weather, I am enjoying pretty much the pleasant view from my office at IMATI-Ge, where I'm currently working with the Shape Modelling Group.

Sampierdarena viewed from the IMATI-Ge offices


My workplace

Polygon Detector v0.1

More that four years after the publication of the algorithm in the paper "Polygon Detection from a Set of Lines", I finally found time to re-write the code. Since it was implemented within a larger project, it was sharing several pieces of code and dependent of classes containing lots of functionalities unnecessary for this purpose.

The "Polygon Detector" prototype takes as input an SVG file containing a set of lines and produces another SVG file with the corresponding polygon set. Note that the polygon detection algorithm runs in O(n^4), where "n" is the number of lines obtained after intersection removal. Thus, for a complex line set, it may take a while to detect the polygons. For instance, processing the line set depicted below took around twelve minutes in a Intel Pentium M 2GHz 1MB RAM computer running Windows XP.

Line set with 100 random lines, corresponding to 2286 non-intersecting lines

The polygon detection algorithm created, from the line set illustrated above, a set of almost one thousand polygons depicted below. The current version of the prototype produces an SVG file containing colored polygons, however the coloring algorithm used is quite simple and still needs some improvements, namely to avoid (or at least minimize) color repetition. Something to be solved in a future version.

Set of detected polygons, containing 995 elements.

If interested, you can download the current stable version of the prototype [ZIP 434KB] or the paper where the algorithm was initially paper, "Polygon Detection from a Set of Lines", Ferreira, A., Fonseca, M.J. and Jorge, J.A., Actas do 12º Encontro Português de Computação Gráfica (12th EPCG), pages 159-162, Porto, Portugal, Oct 2003 [PDF 86KB].

Decomposing 3D models

Moving forward into my main goal, I am now concerned with model segmentation. In my first approach to this problem I used the fitting primitives mesh clustering algorithm proposed by Marco Attene in is paper "Hierarchical mesh segmentation based on fitting primitives". A result obtained from a model extracted from the ESB with a preliminary prototype is depicted below, different colors representing distinct segments.

Segmented model