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