Tag Archive | C++

Showtime: library to be proposed as Boost.Http!

It’s been two months already since my last post on this blog. All this time (and more), I’ve been (among other tasks) working on my 2014 GSoC project, an HTTP server proposal to Boost. I’ve finally reached a point where I feel it’s ready for major review/feedback.

If you’re a C++ programmer, a native speaker or an HTTP researcher (or just a little of everything) and you want to help, I’d like to ask you to review the project (interface-wise) and give me feedback.

You can find all the documentation and code at github.

Experience

This isn’t my first time on GSoC, but the experience was very different. The communities, development model, targeted audience, knowledge domain, to name a few, were completely different. Also, this year’s project wasn’t as challenging as the last one (although this is very subjective).

I improved as a programmer, but this is limiting. Once you become able to write algorithms for turing-machine compatible devices, there isn’t much room for improvement and you need to hunt other skills to continue improving (e.g. security, parallelism…). Coding for the sake of coding solves no problems. I decided to take a break (not exactly now, but in a few weeks) to make a shift and start to increase the efforts I dedicate to my academic skills.

Next step

I aim to integrate this library into Boost, so I still want to invest effort in this project.

Arquivos portáveis, protocolos portáveis… em C!

Um hábito que me faz desprezar imediatamente TODAS as habilidades que um programador afirme ter, é ele fazer um formato de arquivo ou protocolo binário que não é portável, então resolvi fazer esse artigo para ajudar a diminuir essa prática, expondo os seus perigos.

Mas antes, lembro que na época que eu usava Flash Player, eu era um usuário burro e aceitava cegamente a desculpa das versões de diferentes sistemas operacionais serem dessincronizadas (sistema operacional X recebe versão nova antes de Y e Z, em vez de lançamento simultâneo). Isso é um ato que eu até consigo entender tendo em mente os objetivos da empresa, mas outro lugar onde a dessincronização de versões ocorria era em arquiteturas diferentes (32bit e 64bit). E o único fator para justificar isso é pura incompetência dos programadores, que ganharam para sempre o meu desprezo. Dito isso, não acompanho ou uso mais o Flash Player e não sei se esse problema já foi corrigido.

Para não comentarem que sou extremista e só exponho os erros técnicos de softwares proprietários, aqui e aqui você vai encontrar um erro que pode ocasionar o mesmo problema, no futuro, mas é completamente ignorado, no projeto Enlightenment, que é software livre. Aliás, eu nem posso afirmar que expus erros técnicos do software Flash Player, pois é assim que funciona com software proprietário, você simplesmente não sabe.

Citando, para motivos de reflexão, antes do começar a parte séria do texto, a frase de alguns padrões da IETF, em tradução livre: “seja liberal no que você aceita, mas conservador no que você produz”.

Fluxos de bytes binários

O computador trabalha usando binários, mas esse fato é abstraído na linguagem de programação e esquecemos isso enquanto estamos focando no problema que queremos resolver de verdade, em vez de ficarmos nos preocupando com o opcode da instrução da arquitetura do processador que é necessária para implementar várias camadas de algoritmos até chegar no problema que realmente queremos resolver. Entretanto, quando é hora de fazer o programa se comunicar com o mundo externo, através de arquivos ou sockets, é hora de nos preocuparmos com a representação interna das estruturas do programa, pois nesse momento elas importam.

<stdint.h> e <inttypes.h>

Começando pelo mais simples, C não exige/garante que os tipos short, int, long, long long tenham a mesma quantidade de bits para todas implementações, ou mesmo que o tipo char tenha sinal. Isso significa que se você fizer um programa que leia um long de um arquivo ou da rede, você está errado. Quando você compilar o seu programa em uma implementação que usa um long de 32 bits, ele não se comunicará adequadamente com o mesmo programa compilado em uma implementação que usa um long de 64 bits, pois a estrutura de fluxo de bytes que ele gera não é definida e varia de implementação para implementação.

A solução para esse problema é você usar tipos para os quais existe a garantia de tamanho específico, independente de implementação. Se um compilador não cumprir com esse requisito, ele não é um compilador da linguagem C, pois ele não cumpre com a especificação da linguagem. Esses inteiros estão disponíveis nos cabeçalhos <stdint.h> e <inttypes.h>. O cabeçalho <stdint.h> possui todos os nomes necessário para declarar inteiros de tamanho fixo, enquanto o <inttypes.h>, além dos nomes introduzidos pelo <stdint.h>, introduz nomes para ajudar a trabalhar com printf, scanf e conversões entre strings e inteiros de tamanho fixo.

Mais uma coisa a aprender é que o padrão mais comum para representar números negativos usando binários é o complemento de 2, mas a especificação da linguagem não exige/garante o padrão por trás do mesmo e, inclusive, define integer overflow como undefined behaviour. Mas nada tema, pois o padrão exige que os inteiros com sinal declarados no cabeçalho <stdint.h> sejam armazenados usando complemento de dois. Então se você está seguindo as soluções até aqui, você já se livrou do problema.

Uma última nota que tenho a adicionar é: só use inteiros de tamanho fixo quando eles forem necessários.

Ordem dos bytes

Outro problema que atinge a portabilidade do fluxo de bytes é que não há garantias em relação a ordem dos bytes que compõem um mesmo inteiro. Isto é, em 16 bits, é legal representar 16 bits como 0000’0001’0000’0000 ou 0000’0000’0000’0001. As duas ordenações que costumamos encontrar são Little Endian e Big Endian (também conhecido com Network Byte Order).

Não há solução embutida na especificação da linguagem C para esse problema, então você vai ter que implementar suas funções ou usar alguma biblioteca externa como essa ou essa.

EBML/Matroska

Um formato que eu quero citar brevemente, pois possui uma característica que eu acho bem legal, é o EBML. O EBML é binário e possui uma representação eficiente, sendo usado, por exemplo, no formato de arquivo Matroska. Mas o EBML é também extensível, o que me dá confiança para acreditar que não seria surpresa continuarmos a utilizar esse formato por, sei lá, mais 20 anos.

Imagine que lhe seja dada a tarefa de criar uma representação binária para datas. Você decide especificar a quantidade de bits necessários para dias (que variam entre 1 e 31) e meses, mas chega então no problema de especificar a representação para armazenar o ano. Você sente a vontade de especificar um tamanho fixo grande o suficiente para que o problema não seja exposto enquanto você estiver vivo, mas algo dentro de você grita para que você lute e acabe com o problema. Esse algo dentro de você, gritando para que você resolva o problema, se chama competência. Você decide usar caracteres ASCII no topo do formato binário, para usar texto e ter uma quantidade infinita de caracteres, que pode ser usada para representar qualquer data, mas surge a questão de como definir o tamanho para armazenar essa cadeia de caracteres. Se você especificar um inteiro de 32 bits ou qualquer outro tamanho no começo da sequência, a representação continuará limitada.

A linguagem C define cadeias de caracteres de tamanho arbitrários (na verdade, ainda limitados pelo intervalo enumerável dos ponteiros) através de um delimitador no final da sequência. A mesma solução de usar um delimitador pode ser trazida ao universo dos inteiros binários e, de fato, é usada no formato EBML. Vale ressaltar que o EBML não sofre o gargalo e ineficiência de usar caracteres ASCII convertidos lexicalmente (no sentido do lexical_cast existente na Boost) para inteiros em sua representação.

Baseado em texto puro (legível por humanos)

Não, seus problemas não acabam com você indo para texto puro! Mas nada tema, pois você usa uma linguagem que requer a presença de acentos, está usando um locale diferente do padrão e já possui vantagem sobre outros programadores, detectando mais cedo qualquer quebra de internacionalização!

Se o fluxo de bytes que você está definindo é baseado em texto puro, você deve responder algumas perguntas como “o conjunto de caracteres ASCII é suficiente?”, “como adicionar estrutura de uma forma extensível?” e “dados binários serão suficientes?”.

O primeiro problema a resolver é que, caso abra um arquivo em modo de texto, em C, o final de linha será interceptado e convertido, a depender do sistema operacional (“\n” no sistema pai, o Unix, “\r\n” no Windows e “\r” no sistema da empresa que gosta de quebrar padrões para eventualmente causar dependência). Então, ou você escolhe e usa apenas uma dessas opções (como acontece com o HTTP), ou se prepara para tratar todas elas (como acontece com o gcc e editores de texto decentes). Mas um comportamento deve ser definido (assim como suas consequências refletidas) e a implementação deve cumprir com tal.

Se eventualmente for necessário adicionar suporte a dados binários, pesquise pelos padrões base64 e base91 e faça preparativos para que não haja conflitos de caracteres especiais sendo utilizados em áreas diferentes das planejadas.

Se o conjunto de caracteres ASCII não for suficiente, use Unicode. Vou apenas lhe informar para começar por aqui.

Problemas em XML e arquivos estruturados em geral

O XML é um formato de arquivo que carrega a palavra extensibilidade em seu nome (eXtensible Markup Language) e ele é bastante usado em alguns locais onde manter interoperabilidade é um requisito importante. Os problemas que podem aparecer aqui não são de baixo nível, específicos de arquitetura de computadores ou da linguagem C, mas já que comecei a comentar sobre interoperabilidade, decidi estender o texto e fugir do escopo inicial só um pouco.

Um problema que costuma afetar o XML e formatos estruturados como um todo, é que algumas implementações, não-conformantes, costumam usar a estratégia ingênua de mapear o arquivo para suas próprias estruturas e trabalhar daí, em vez de manipular o arquivo original. Acontece que normalmente essa estratégia ingênua irá descartar todos os atributos, tags, elementos e por aí vai do arquivo original, que não forem reconhecidas pela implementação. Isso aconteceu com algumas implementações do ODF e houve até a teoria conspiratória que a infratora tentava minar o padrão.

Mesmo que você argumente em optar pela abordagem ingênua, por sua implementação suportar todos os nomes definidos na especificação, você deve ter em mente que formatos evoluem e extensões são adicionadas no topo do formato original (isso acontece com o OpenGL, com o XML SVG do Inkscape e em tantos outros por aí).

Uma abordagem mais legal do que criar abstrações que retornam o elemento processado (que só contém as propriedades que a implementação conhece), é criar abstrações que realizem operações em cima da representação original, como acontece com a API do MongoDB, onde você só especifica os atributos que devem ser modificados, mas os atributos não-especificados continuam a existir.

Caso você não seja um guerreiro incorruptível e se desvie do caminho correto, pelo menos tenha a decência de explicitamente proibir, na especificação do padrão, o uso de propriedades adicionais. Tal exigência pode ser especificada como “additionalProperties: false” em JSON Schema.

Final

No final do texto eu fiquei com preguiça e passei a só explicar quais deveriam ser suas preocupações, adicionando referências para você pesquisar mais. Foi diferente do começo do texto, onde eu estava com paciência até para explicar os problemas com detalhes.

Se eu esqueci de alguma coisa ou você tem alguma informação relevante a acrescentar, comente!

GSoC 2014/Boost

I was accepted for GSoC 2014 and I’ll be working on the Boost project.

I created a new category on this blog to track the progress, so you’ll be able to have a separate rss feed for these posts. The new category URL is http://vinipsmaker.wordpress.com/category/computacao/gsoc2014-boost/.

Meu erro favorito de C/C++: Falha de segmentação

Resolvi criar esse curto post para comentar sobre qual o meu erro favorito na linguagem de programação C, que na minha universidade é relativamente comum devido a ela ser a linguagem usada para introduzir os alunos ao universo da programação.

O quê?

O erro falha de segmentação acontece, principalmente, quando você desreferencia um ponteiro inválido. Quando uma falha de segmentação acontece, o programa é encerrado imediatamente.

Por quê?

Esse é o meu erro favorito, pois quando esse é o erro com o qual você se depara, provavelmente não irá gastar muito tempo com o mesmo.

Tudo que você precisa para identificar exatamente esse erro é (1) identificar o conjunto de ações que ocasionará a falha de segmentação, (2) executar o programa através de um depurador e (3) fazer o backtrace, que lhe dará toda a corrente de chamadas de funções que provocou a falha de segmentação, apontando exatamente para a linha de código que ocasionou o problema, além de outras informações úteis como o valor de cada variável.

Perspectiva

Talvez ironicamente o meu erro favorito é o que eu menos presencio. Dependendo de como eu veja, isso pode ser algo bom (eu me tornei um programador melhor) ou algo ruim (as coisas que eu gosto vão embora), mas uma informação que contribui para o valor desse post é o provável verdadeiro motivo desse fato: Eu uso C++. Com C++, eu raramente utilizo ponteiros (que normalmente são substituídos por referências e, quando gerenciamento manual de memória torna-se necessário, por smart pointers), eliminando grande parte das falhas de segmentação.

Uma questão de perspectiva também é que para as pessoas que não conhecem um depurador, esse pode ser um dos erros mais chatos, não o favorito (como eu acho que seja).

O contra-ataque!

(essa seção foi adicionada a pedido dos leitores, 2 dias após o artigo ser publicado)

Eu criei o seguinte código-fonte que apresenta um erro. De acordo com o padrão de C++ o seu comportamento é indefinido e o compilador tem a liberdade de fazer elefantes rosas aparecerem na tela do seu computador sem perder o título de “compilador de C++”. Entretanto, o que provavelmente irá ocorrer é uma falha de segmentação. Baixe o código-fonte e siga para a próxima etapa, onde irei mostrar como erros desse tipo podem ser descobertos de forma simples.

EDIT(2014/02/23): Eu sempre achei que o texto abaixo seria confuso, pois não representava precisamente como uma sessão do gdb realmente é, então, devido (1) a isso e (2) a descoberta do asciinema, resolvi adicionar mais esse pequeno texto no artigo. Basicamente, recomendo que você veja esse asciicast no asciinema antes de prosseguir para os detalhes.

O primeiro passo é compilar o programa junto com as informações de depuração. Leia o manual do seu compilador para descobrir como fazer isso. Caso utilize uma IDE ou qualquer outro intermediário para compilar o programa, provavelmente isso pode ser feito escolhendo um perfil de debug. No gcc, a opção que habilita os símbolos de depuração é a opção “-g”:

Após isso você pode executar o programa através de um depurador e ficar brincando com o programa até o erro acontecer. Aqui, utilizo o gdb, sem nenhuma interface:

Após o gdb iniciado, você presenciará sua saída padrão, que é algo parecido com o texto a seguir:

Dentro da interface do gdb, execute o comando “run” e brinque com o programa até o erro acontecer. No meu caso a saída foi essa:

Voltando a interface do gdb, após o programa ter “crashado”, os dois principais comandos para navegar na pilha de execução são “backtrace” e “frame”, que, respectivamente, mostram a pilha de execução e escolhem um frame/instante na pilha/linha-de-execução.

E assim descobrimos, usando o gdb, que o programa travou exatamente na linha 42, após a função ler_clientes ter sido chamada pela função main. Podemos usar o comando “print” para imprimir o valor de variáveis/expressões que sejam válidas no contexto.

E assim descobrimos que há um ponteiro inválido na memória e o programa “crashou” quando tentamos acessá-lo. As duas opções a partir de agora são (1) examinar o código e descobrir que código inseriu um ponteiro inválido em memória ou (2) continuar usando o auxílio do gdb para descobrir a fonte do erro. Como o código é muito simples, é fácil ver que eu “esqueci” de inicializar o ponteiro dos objetos que são inseridos na variável “clientes” (isso, é claro, só é fácil depois que já descobrimos qual é o erro com a ajuda do gdb).

Caso você queira continuar a usar a ajuda do gdb para inspecionar o estado do programa em tempo de execução, os próximos comandos que seriam lhe úteis seriam “watch”, “break”, “step” e “continue”.

Para referência, deixo abaixo o resto de minha sessão do gdb, onde continuo examinando o programa até descobrir que código faz a inserção de um ponteiro inválido. E recomendo que você já tenha executado o gdb nesse momento, ou então irá ver esse monte de texto e não vai entender nada, achando que é algo muito difícil…

Algo que quero destacar é que o código-fonte é de “um programa em desenvolvimento” e, consequentemente, bem curto. Mas reflita sobre o que aconteceria se ele fosse grande (4000 linhas ou algo parecido). Usando o gdb, o processo de encontrar o erro seria o mesmo, bem fácil.

Avaliação curto-circuito

Existem alguns conceitos de linguagens de programação úteis, mas que são tão simples que se tornam um “tabu”. Você não presenciará veteranos discutindo tais assuntos, pois não há nada há se discutir de tão simples que são, mas são conceitos úteis que deveriam ser disseminados para os novatos desse universo. Um desses conceitos é, dentro do pedaço de universo com o qual eu tenho mais contato, o conceito de avaliação curto-circuito.

Esse conceito se refere a propriedade que alguns operadores possuem. Tal propriedade garante uma ordem de avaliação e que, quando for desnecessário continuar a avaliação para descobrir o resultado, ela será interrompida. É chegado o momento… para um exemplo!

A saída da função g, do exemplo anterior, usa o operador lógico binário && (AND) e sua saída independe da propriedade de avaliação curto-circuito. A tabela a seguir resume as saídas possíveis:

a f(b) g(a,b)
false ? false
true ? ?

A partir da tabela anterior é possível perceber que, caso o valor de a seja false, não precisamos avaliar a expressão f(b). Avaliar, avaliar e avaliar é a ideia-chave para entender a avaliação curto-circuito. O que avaliar a expressão f(b) significa? Se a (sub-)expressão não possuir efeitos colaterais, não faz diferença. Que tal refletir sobre o comportamento de código a seguir?

O código do exemplo anterior explora o fato do operador lógico binário && garantir avaliação curto-circuito. Na verdade, esse é um truque bem comum de encontrar em “códigos de verdade”. Graças a avaliação curto-circuito, é garantido que a sub-expressão val->answer != 42 não será avaliada caso val == NULL. Eu tenho bastante confiança de que você já entendeu a importância da avaliação curto-circuito nesse exemplo, mas para o caso de esse texto estar sendo lido por alguém que entrou muito recentemente no mundo da programação (ou no mundo da programação em C), vou explicar mais profundamente: a sub-expressão val->answer faz um desreferenciamento de ponteiro e, caso val == NULL, a expressão irá gerar um erro em tempo de execução (provavelmente a aplicação vai fechar imediatamente), mas isso não ocorrerá graças a avaliação curto-circuito.

Antes de explorar as consequências desse importante conceito no desempenho da aplicação, uma expansão do exemplo anterior para reforçar a ideia:

Desempenho

Essa seção é só um alerta para o caso de você, paranoico por desempenho, ter sido estimulado a preferir (ou o contrário) os operadores que garantem avaliação curto-circuito para atingir o máximo de desempenho.

A primeira observação que podemos fazer é que o caminho de execução no caso desses operadores será diferente, pois algumas vezes ele será mais curto devido a não-necessidade de avaliar algumas sub-expressões. Menos passos de execução significa que o trabalho é feito mais rápido, afinal isso é o básico de análise de algoritmos, certo? Errado! Só porque algo é teoricamente mais rápido, não quer dizer que na prática vai executar mais rápido, pois (1) a teoria que você usou pode não estar modelando todas as partes importantes do sistema ou (2) algumas instruções podem ter custos maiores (acesso a memória, por exemplo). Um fator que deve ser considerado é a predição de qual ramo será executado.

Eu acabo de fazer algo terrível. Eu introduzi outro conceito a um possível leitor maniaco por desempenho que sacrificará legibilidade de código por código possivelmente mais rápido. Caso isso tenha acontecido, sugiro que você cave mais fundo e pesquise pelas instruções cmov. São instruções que condicionalmente movem um valor e livram o programa da necessidade de realizar um pulo condicional. Isso significa que se você cegamente tentar otimizar o código removendo caminhos (e pulos de instruções), é possível que seu código execute mais lento que um código limpo e claro escrito por alguém que não está preocupado com desempenho.

Uma última observação é que o compilador (e não você!), quando possuir acesso a todos os códigos necessários, saberá qual a melhor decisão a tomar. Sempre use um profiler (coisa que eu deveria estar fazendo)!

OFF-TOPIC

Bom, já que se foi discutido sobre a (não) avaliação de expressões, vou citar uma proposta legal para o próximo padrão do C++ que permitiria eliminar a reavaliação de (mais algumas) sub-expressões comuns: http://isocpp.org/files/papers/n3744.pdf

C++’s best feature

Vinipsmaker:

I think I could make a beautiful XML construction code exploring this feature. I wish some scripting language adopt this feature.

Postado originalmente em Andrzej's C++ blog:

C++, if you want to learn all of it, is big, difficult and tricky. If you look at what some people do with it, you might get scared. New features are being added. It takes years to learn every corner of the language.

But you do not need to learn all of it. Effective use of C++ requires only the knowledge of a couple of its essential features. In this post, I am going to write about one C++ feature that I consider one of the most important. The one that makes me choose C++ rather than other popular programming languages.

Ver original 2.062 mais palavras

Splines extraction on Kopf-Lischinski algorithm, part 0

Introduction

This post is a continuation of “Splines extraction on Kopf-Lischinski algorithm, part 1“. The title contains “part 0″, because the algorithm step described here should be executed before the algorithm step described in “part 1″.

This blog post is kind of unstructured, but don’t worry, because I’m aware of that and is intentional.

Generalized Voronoi diagram generation

The algorithm described in this section was kind of documented already, but the documentation wasn’t good enough to be part of a post, then it was keep as a private home-made PDF.

Well, a Voronoi diagram is a black box where you put some points (the seeds) and you get some polygons (the cells). Each polygon contains all points that are closer to its seed than any other seed. There is a good article on Wikipédia and I won’t explain any further.

Kopf-Lischinski algorithm executes a bunch of operations on a graph and it uses a Voronoi diagrams to extract a visual representation from this graph. The simplest form of a Voronoi diagram works with 2D points-seeds, but we have higher-dimentional Voronoi diagrams, Voronoi diagrams using different distance functions and even Voronoi diagrams using complex non-points seeds. We are interested in these Voronoi diagrams using complex non-points seeds.

The below image has a representation of the output graph of the Kopf-Lischinski algorithm and its Voronoi diagram representation. The graph nodes are represented by circles, where nodes with the same color are similar and usually are connected. The connections of the nodes are represented by green lines.

An accurate generalized Voronoi diagram

An accurate generalized Voronoi diagram

The generalized Voronoi diagram is visual, then there is no special meaning to explain it in the previous image. The seeds of this diagram aren’t points, they are line segments. You just need to break a green line in two and add each half to its containing cell. You can note that some polygons aren’t convex.

The graph used as input has certain constraints that enable us to use some simple and fast operations instead of a full-featured and complex algorithm.

If a Voronoi cell is a polygon containing all points that are closer to its seed than any other seed, we can determine the edge of a Voronoi cell by the midpoint of two adjacent seeds. If we generate a vertex for each of its 8 directions, we will get an accurate Voronoi diagram.

A simplified generalized Voronoi diagram

A simplified generalized Voronoi diagram

We can get a simplified Voronoi diagram by forgetting about the top, bottom, left and right vertices (if we just generate the diagonal vertices). The simplified version doesn’t contain concave polygons.

The act of generating diagonal vertices is more complex than the act of generating the other vertices. We need to check if there is a connection with the other cell and, if this connection exists, generate two vertices. If the connection doesn’t exist, we generate a single vertex, but its position depends on the existence of a connection between its neighbors. Look the following figure.

A simplified generalized Voronoi diagram (detailed)

A simplified generalized Voronoi diagram (detailed)

All information we need to generate the Voronoi diagram is located within its neighbors and the only extra tool we need to generate the points is the midpoint procedure. This is old news and it was already implemented in libdepixelize.

Metadata extraction

When we generate B-Splines using Kopf-Lischinski algorithm we need a way to separate points that create sharp corners and smooth points. The Kopf-Lischinski algorithm has techniques just to handle this issue. In libdepixelize, I decided to merge the point smoothness computation and Voronoi generation in one single phase. This is the phase where we can gather lot of info about the graph and we can propagate the smoothness data to later phases.

One note about the algorithm of this “metadata extraction” section is that some points will disappear during polygon union and we don’t care if the metadata about these points are accurate, then we can simplify the algorithm exploring this property. The below image will be citated all time during this time to how explain this algorithm:

Vertex types

Vertex types

There are two types of vertices generated in this special Voronoi diagram:

  • White type: The type of the one labelled with “#1″. Node “#1″ is contained by three cells, one purple and two yellows. The two yellow cells will be merged during polygon-union. There are two possibilities for the remaining cell in this kind of node:
    • When it has the same color. Then the node will disappear during polygon-union and we don’t care about its “smoothness” attribute.
    • When it has a different color. Then we say it is a valence-2 node.
  • Cyan type: The type of the one labelled with “#2″. This type of node can appear in the border of the image and isn’t smooth or in the center of 4 cells and its smoothness isn’t predictable in advance. If it appears in center of four cells, then:
    • It can be in the middle of 4-connected cells and we don’t care about its “smoothness” attribute, because this node will disappear.
    • It can be in the middle of a valence-2 node and will be smooth.
    • It can be a valence-3 node and things start to get complex. After the polygon union, this node will be part of three different polygon and only two of these three nodes will share the same value for the “smoothness” attribute.

Problem explained, it’s time to algorithm! The algorithm is kind of repetitive (if we iterate the bottom-right node, compare with bottom and right nodes, then do all it again, but use nodes of different directions…), but the principle is the same for all “repetitive” code, then I’m only going to put the important parts and you’ll be able to see the full algorithm implemented in libdepixelize within a few hours. Lastly, this isn’t the first algorithm I came up with and I made a lot of iteractions already (lots of crumpled paper on my room’s floor), but I think the result can perform pretty fast and I’m content. This post is kind of a documentation and it will help me to not forget what I wanted to do in the code.

layout

The above image represents the analysed data in the following code example, except for the fact that we don’t know what are the colors of the cells. We are iterating on the middle point of the image and the current iterated cell is cell A. The algorithm also uses the concept of “shading edge” and “contour edge” described in Kopf-Lischinski algorithm paper.

All images in this post were created using Inkscape and its awesome alignment tools.

%d blogueiros gostam disto: