Preenchendo um polígono: desempenho da regra de enrolamento vs Mesmo Regra Odd

Question

Para um polígono complexo. (Ie: auto interseção) a escolha entre o enrolamento ou a Even-Odd enchendo regras faz a diferença na forma como o polígono é preenchido

Mas para polígonos não se cruzam há alguma diferença de desempenho entre o as regras de preenchimento Mesmo Odd enrolamento ou. Eu entendo que seria implentation específico, mas qual dos algoritmos é mais pesca para polígonos não complexos.

Um acompanhamento pergunta o que é a complexidade (ie O (o quê?)) De cada um desses algoritmos. Eu quero saber se vale a pena se livrar de alguns pontos no polígono (principalmente duplica ou aqueles que estão na mesma linha) para melhorar o desempenho.

PS: Se é importante em tudo, eu estou usando xlib

PPS: posso confirmar que o problema não está relacionado ao hardware como a utilização de uma placa gráfica diferente não altera o desempenho

Answer 1

Hoje, a maioria das implementações de X usar o hardware 2D da sua placa gráfica para que a diferença entre os dois é provavelmente insignificante.

Uma vez que esta é uma questão de desempenho, as chances da minha resposta estar correta é cerca de 10%, embora (com o desempenho, você tem 90% de chance de estar errado sem medir). Se você quiser ter certeza, não há nenhuma maneira, mas para escrever um pequeno teste de desempenho e veja por si mesmo.

x11perf pode ajudar.

Você pode encontrar o algoritmo para o hardware de preenchimento polígono independente aqui: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD

Há uma segunda versão que é muito mais rápido se tiver certeza de seu polígono é convexo: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD

A segunda versão ignora a regra de preenchimento (que não se aplica ao polígono convexo). Comentários sobre o algoritmo: http: // CVSweb .xfree86.org / CVSweb / xc / programas / Xserver / mi / mipoly.h? rev = CABEÇA

O algoritmo funciona da seguinte forma: Ele calcula o contorno, em seguida, cria objetos de extensão (que são apenas um x, y coordenar e uma largura) entre as bordas. Se você usar a regra EvenOdd, mais objetos extensão será criada se houver cruzamentos. Se não houver nenhum (por exemplo, quando o polígono é convexo), então você não vai notar uma diferença de tempo de execução porque a regra enchimento equivale a uma variável booleana no circuito principal do miFillPolygon (ou seja, a maior parte do código é o mesmo para ambos regras de preenchimento).

Tentando melhorar o desempenho através da otimização do contorno do polígono não vai comprar-lhe muito no caso comum, exceto se você sabe que seus polígonos contêm um número muito elevado de pontos desnecessários (por exemplo, você pode se livrar de metade do número de pontos no caso comum). Otimizando um polígono com <10 pontos provavelmente vai custar mais do que ele consegue.

Mas, novamente: Este são todas baseadas em intuição ou o conhecimento de um artigo de idade. Se você quer saber se erros em seu cartão gfx motorista mexer com o resultado, você tem que sujar as mãos e escrever um teste que mede quanto tempo cada caso preciso. Não há nenhuma maneira de dizer o tempo de execução de qualquer algoritmo complexo, simplesmente olhando para ele por causa de fatores externos: velocidade das rotinas de alocação de memória, quantidade de memória livre (quando é que a troca de início), o número de núcleos de CPU que você pode usar, quantas outros processos irá lutar com você para a CPU, escorando do polígono final sobre a tela, detalhes de implementação e otimizações, erros, etc.