NinePatches, backgrounds, paddings, relayouts and some headache

UPDATE: I've moved my whole blog to a new domain. That's why the comments section is closed here. The new URL for this post is http://www.leonardofischer.com/ninepatches-backgrounds-paddings-relayouts-and-some-headache/. If you have any question, post it there.

Hi,

A few days ago I got stuck into a so called "bug". A developed a small NinePatch to use in an Android app. I wanted it to highlight a ViewGroup object, and then remove the background later. But the first time I set the NinePatch, the view appears to move a little bit. Weird!


Let's start from the beginning: what is a NinePatch?

It is a special image file. In the Android SDK, it is a file with the extension .9.png that you can open in any image editor. What makes it special is a border around the image that has a special meaning for the Android system. If you ask to draw this image with a different size than its width*height dimensions, the image will stretch only in some pre-defined areas and the others will keep their original size. Why you would use this?? A practical way to explain this is to show you a NinePatch in use:

There is a NinePatch on the left (with a lot of zoom, and a yellow line to the actual NinePatch dimensions). On the right, two buttons with different dimensions. You got it? The NinePatch is very stretched on the big button, but still look very good! There is a lot of material explaining how to get this effect on the web. I recommend you the official Android SDK for this (which also is the source of the image with the buttons, modified by me). The Android SDK also have a very simple tool that let's you generate these NinePatches.


The Symptom

So far, so good, the NinePatch works pretty well. Until you put it behind a view as its background. What happens? Let's see.

After I set the NinePatch as the background of the FrameLayout root_layout, the text is moved some pixels down (I drew a blue line so you can see that it moved exactly 4 pixels). Not too much, but it should move 0 pixels, no more, no less!


The Research for the Cure of the Headache

Well, actually the "bug" is not a "bug", but a feature! After researching the Android source a little bit, I understood that the optional padding that you should set in the NinePatch also gets into account when you set the ViewGroup's background. Let's look at the source of the method View.setBackgroundDrawable(Drawable d).

public void setBackgroundDrawable(Drawable d) {
    //some other code
    if (d != null) {
        Rect padding = sThreadLocal.get();
        //more intermediate code
        if (d.getPadding(padding)) {
            setPadding(padding.left, padding.top, 
                padding.right, padding.bottom);
        }
        //more code
    }
    //and the finishing code
}

The Medicine

As you can see, the view literally gets the padding that you set into the NinePatch and sets onto the view, changing its dimension. That is why you set the background and the view changes its position. If you do not set the optional padding, the padding of the NinePatch will be computed from the stretchable area, and will mess with your beautiful layout.

Optionally, you can get the padding before set the background, set your custom background, and then set the old padding. Example:

//backup the old padding
Rect padding = new Rect();
padding.left = rootLayout.getLeft();
padding.top = rootLayout.getTop();
padding.right = rootLayout.getRight();
padding.bottom = rootLayout.getPaddingBottom();
//set the new background
rootLayout.setBackgroundResource(R.drawable.nine_patch);
//restore the old padding
rootLayout.setPadding(padding.left, padding.top, 
    padding.right, padding.bottom);

This one is not as good as just set the padding on the NinePatch, as you need to run some extra code every time you set a background onto a view. But this hack may let you do something that I did not though of yet  ツ


The Side-Effects

Finally, I want to show you a side effect of using a NinePatch. Let's go back to the Android source code:

public void setBackgroundDrawable(Drawable d) {
    boolean requestLayout = false;
    //some initial code
    if (d != null) {
        // some other code, including the one presented above
        if (mBGDrawable == null || 
                mBGDrawable.getMinimumHeight() != d.getMinimumHeight() ||
                mBGDrawable.getMinimumWidth() != d.getMinimumWidth()) {
            requestLayout = true;
        }
        // more code
    }
    // pre-requestLayout code
    if (requestLayout) {
        requestLayout();
    }
    //finishing code
}

As you can see, if the previous background has different minimum width or height from the new one, the method will force a requestLayout() call. This is ok if you set the background during the application initialization. But if you start to swap your view's background, then you need to take care of these properties too. If not, your application may suffer from "hiccups" from the re-layout of your views.


Finishing, this is the source code that I developed for this post. It contains the "Hello World" example you saw above. If you click on the text, the background is added, so you can see for yourself this Android feature.

UPDATE: I've moved my whole blog to a new domain. That's why the comments section is closed here. The new URL for this post is http://www.leonardofischer.com/ninepatches-backgrounds-paddings-relayouts-and-some-headache/. If you have any question, post it there.

The DCEL data structure: a C++ implementation

UPDATE: I've moved my whole blog to a new domain. That's why the comments section is closed here. The new URL for this post is http://www.leonardofischer.com/dcel-data-structure-c-plus-plus-implementation/. If you have any question, post it there.

Hi,

When working with computer graphics, it's very common to deal with discrete surfaces (for example, triangle meshes). The simplest approach is to store a triangle mesh as a list of vertices and the indices that define the triangles, and it is very efficient if you just need to draw the scene. But it doesn't work very well if you need to answer advanced queries, such as what are the edges that start on a given vertex or what are the neighbor faces of one given face

During my master thesis I needed to answer such queries. And I found that the DCEL Data Structure would be perfect for my case. But I didn't like the implementations that I found. For example, this one couples too much the DCEL implementation with the data that I need to store within the DCEL. And this one is a powerfully monster that should do everything I need, but only after tame de monster.

I decided to write my own DCEL. I tried to keep it simple to understand, but complete enough to do all the things that I need. Basically, the vertices, edges and faces in my DCEL are containers. I also implemented a mesh template that receives the types that you want to put inside these objects. Finally, the mesh has lots of helper methods that very simple to use to manipulate the DCEL in the most common cases. I tried to keep its use in the same way that you would use a std::list.


But what is this DCEL I don't stop talking about?

The Doubly-Connected Edge List is a data structure to store the topological structure (i.e. the relation between faces, edges and vertices) of a surface. It doesn't solve every problem on earth, but is heavily used in algorithms that deal with surface operations. I will not go deep into how it works, but I will try to scratch its surface. It works like a double-linked list.

A DCEL is a set of faces, half-edges and vertices. Yes, an edge divided by two. A pair of half-edges forms an edge, and they are called twins. So, each half-edge has a pointer to its twin half-edge, in order to reconstruct the whole edge. But why divide an edge by two? Each half edge is associated to one face on one side of the edge, and one vertex on one end of the edge. In other words, a half-edge has a face pointer and an origin pointer. And where is the "doubly-connected" thing? Each half-edge has a next pointer and a previous pointer. The contour of a face is defined by a sequence of half-edges linked by their next and previous pointers. Finally, a face has the boundary pointer which points to one half-edge on its contour. And the vertex has an incident pointer that points to one half-edge that starts on that vertex.

But why this data structure is so interesting? If you inspect it carefully, you will see that everything is connected to everything in a very organized way. From one face, you can walk through his contour by following the next (or previous) pointers of its boundary. From one half-edge, you can access one vertex through the origin pointer and the other vertex following its twin->origin pointers. In the same way, from a half-edge you can access the face on which it is part of the contour (by its face pointer), and the other face by its twin half-edge (twin->face pointer).

As you can see, it is easy to answer the questions from the beginning of the post. What are the edges that start on a given vertex? Pick the vertex. The first half-edge is in its incident pointer. Call it current. For the next half-edge, pick the previous->twin half-edge of the current half-edge (and call this new one the new current). Keep getting these previous->twin pointers until you reach the first half-edge, and you did it!!! What are the neighbor faces of one given face? This one I left as exercise ツ

If you want to dive in the DCEL data structure, I recommend you this page. Or this book.


Building a DCEL using templates

From now on, I'll assume that you are an expert on DCEL, and I'll focus on the DCEL implementation. Let's start by creating a template for the three main objects: FaceT, HalfEdgeT and VertexT (don't worry about the "T" in the names. It will "disappear" latter). These templates will hold the objects that the face, vertex and half-edge should hold as an internal data pointer. I could put a void* on these objects, but this way the object and the data associated will be in the same region of the memory (thus, improving cache hit). Also, it still allows you to use a pointer to any type want.

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class FaceT {
public:
    inline FaceDataT& getData() {
        return data;
    };
private:
    FaceDataT data;
};

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class HalfEdgeT {
public:
    inline HalfEdgeDataT& getData() {
        return data;
    };
private:
    HalfEdgeDataT data;
};

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class VertexT {
public:
    inline VertexDataT& getData() {
        return data;
    };
private:
    VertexDataT data;
};

Now, let's fill the pointers between the objects. Before we add the pointers itself, I need to create forward declarations for the templates.

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class FaceT;

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class HalfEdgeT;

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class VertexT;

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class FaceT {
    typedef HalfEdgeT<VertexDataT, HalfEdgeDataT, FaceDataT> HalfEdge;
    typedef FaceT<VertexDataT, HalfEdgeDataT, FaceDataT> Face;
public:
    //getters and setters, with an inline tip to the compiler =)
private:
    HalfEdge* boundary;
    FaceDataT data;
};

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class HalfEdgeT {
    typedef VertexT<VertexDataT, HalfEdgeDataT, FaceDataT> Vertex;
    typedef HalfEdgeT<VertexDataT, HalfEdgeDataT, FaceDataT> HalfEdge;
    typedef FaceT<VertexDataT, HalfEdgeDataT, FaceDataT> Face;
public:
    inline void setTwin(HalfEdge* newTwin) {
        this->twin = newTwin;
        newTwin->twin = this;
    };
    inline void setNext(HalfEdge* newNext) {
        this->next = newNext;
        newNext->prev = this;
    };
    inline void setPrev(HalfEdge* newPrev) {
        this->prev = newPrev;
        newPrev->next = this;
    };
    // all the other getters and setters as usual
private:
    HalfEdge* twin;
    HalfEdge* next;
    HalfEdge* prev;
    Vertex* origin;
    Face* face;
    HalfEdgeDataT data;
};

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class VertexT {
    typedef VertexT<VertexDataT, HalfEdgeDataT, FaceDataT> Vertex;
    typedef HalfEdgeT<VertexDataT, HalfEdgeDataT, FaceDataT> HalfEdge;
public:
    //all the getters and setters as usual
protected:
private:
    HalfEdge* incidentEdge;
    VertexDataT data;
};

Finally, let's create the Mesh holder to keep all these objects. It will receive as template parameter all the three data types that the other objects will hold. Also, is here that the "T" from the VertexT, ..., will disappear.

template<class VertexDataT, class HalfEdgeDataT, class FaceDataT>
class Mesh {
    typedef Mesh<VertexDataT, HalfEdgeDataT, FaceDataT> MeshT;
public:
    typedef VertexT<VertexDataT, HalfEdgeDataT, FaceDataT> Vertex;
    typedef HalfEdgeT<VertexDataT, HalfEdgeDataT, FaceDataT> HalfEdge;
    typedef FaceT<VertexDataT, HalfEdgeDataT, FaceDataT> Face;

    typedef VertexDataT VertexData;
    typedef HalfEdgeDataT HalfEdgeData;
    typedef FaceDataT FaceData;
    
    // Several helper methods to deal with these objects.
    // Also, the getters and setters.

private:
    std::vector<Vertex> vertices;
    std::vector<Face> faces;
    std::vector<HalfEdge> edges;
};

Voilá!!! But this is everything? No.

The basis of my DCEL implementation is here. But over it, I've implemented several other helper methods to deal with the DCEL. It was designed to deal with faces of any shape, such as triangles, squares or megagons. But triangles are so common and used in computer graphics that I developed only the method that creates triangular faces on it. So, instead of creating the vertices, faces and edges and link everything together, you can just create the vertices and call an createTriangularFace() method on the Mesh class that the needed faces and half-edges are created and linked for you.

I also developed some helper classes. One is an EdgeIterator. If it receives a Face pointer in the constructor, it will iterate over the half-edges of the contour of that face. And if it receives a Vertex pointer, it will iterate over the half-edges that starts on that vertex. Also I developed two loaders for it, which can load common .OBJ files and some .PLY files (through this library). Finally, I developed methods to load and save DCEL structures into files, which is able to deal with the DCEL structure and the data stored in it.

You can download the entire source files here. This file contains all the headers and .cpp files for this DCEL. It also contains the main.cpp, which has some examples of how to use it. The code works on the Visual Studio 2008 and 2010. And if you have any doubt or suggestion, please leave a comment bellow ツ

UPDATE: I've moved my whole blog to a new domain. That's why the comments section is closed here. The new URL for this post is http://www.leonardofischer.com/dcel-data-structure-c-plus-plus-implementation/. If you have any question, post it there.