Programa para cálculo e visualização
do fecho convexo tridimensional
Relatório de Projeto
Gilberto da Silva Hemerly
Julho de 2001
1. Introdução
O objetivo deste projeto é a implementação de um programa que possa, a partir de um conjunto de vértices tridimensionais fornecidos pelo usuário, calcular e exibir o fecho convexo dos mesmos. O programa deve conter uma interface gráfica que permita que, com o mouse ou teclado, o usuário possa rotacionar e transladar a figura do fecho convexo nas três dimensões. Para facilitar a visualização, várias as faces do fecho serão desenhadas em várias cores diferentes.
Para o desenvolvimento do programa, adotou-se o padrão a linguagem C++ e o padrão Win32, que permite que o programa seja executado em qualquer sistema operacional Windows de 32-bits, ou qualquer outro sistema operacional que possa emulá-lo. A programação da interface gráfica foi escrita utilizando o Graphics Device Interface (GDI) do sistema operacional e a biblioteca de funções WGL, que permitem uma melhor integração do GDI com o OpenGL. Esta última foi a biblioteca utilizada para a manipulação e renderização do fecho convexo tridimensional.
2. Fecho Convexo Tridimensional
O algoritmo de fecho convexo tridimensional utilizado foi obtido, gratuitamente, da biblioteca Wild Magic da Magic Software, cuja especialização é computação gráfica em tempo real. Sendo assim, o algoritmo executa em pouco tempo, pois é bastante otimizado. Uma desvantagem do algoritmo é que o fecho convexo por ele calculado é composto apenas por triangulos. O algoritmo automaticamente triangulariza faces com maior número de arestas. O algoritmo está contido nos seguintes arquivos:
além dos arquivos dos arquivos de cabeçalho (.h) e inline (.inl) apropriados. Vale ressaltar que o algoritmo é executado através de métodos contidos em uma classe. Basta instanciar uma classe do tipo ConvexHull3D e passar para o construtor os pontos no espaço. A partir daí, obtém-se os vértices dos triângulos que formam o fecho convexo através de uma chamada ao método GetTriangles. A definição da classe ConvexHull3D é a seguinte (com os comentários originais dos autores):
namespace Mgc {
class MAGICFM ConvexHull3D{
public: // Construction and destruction. ConvexHull3D does not take ownership
// of the input array. The application is responsible for deleting it. ConvexHull3D (int iVertexQuantity, const Vector3* akVertex);
~ConvexHull3D (); // smallest axis-aligned box containing the vertices
float GetXMin () const;
float GetXMax () const;
float GetXRange () const;
float GetYMin () const;
float GetYMax () const;
float GetYRange () const;
float GetZMin () const;
float GetZMax () const;
float GetZRange () const;
int GetTriangleQuantity () const;
const Triangle& GetTriangle (int i) const;
const Triangle* GetTriangles () const;
// tweaking parameters
static float& Epsilon (); // default = 0.00001
static float& Range (); // default = 10.0
static int& TSize (); // default = 75
static int& QuantityFactor (); // default = 16protected:
// smallest axis-aligned box containing the vertices
float m_fXMin, m_fXMax, m_fXRange;
float m_fYMin, m_fYMax, m_fYRange;
float m_fZMin, m_fZMax, m_fZRange;
// triangles
int m_iTriangleQuantity;
Triangle* m_akTriangle;
static float ms_fEpsilon;
static float ms_fRange;
static int ms_iTSize;
static int ms_iQuantityFactor;
};
3 Visualização
Após o cálculo do fecho convexo, o programa então desenha todos as faces do fecho para que a mesma possa ser visualizada. Para isso, utilizou-se a biblioteca OpenGL para renderização e manipulação das faces, e a biblioteca WGL para a integração do OpenGL com as janelas do ambiente Windows. O código de visualização está nos arquivos main.cpp e wgl.cpp. Inicialmente o usuário está olhando em direção a origem do espaço. É possível transladar, rotacionar, aproximar-se ou afastar-se do fecho no espaço interativamente usando o mouse ou teclado. As funções são as seguintes:
Também é possível redimensionar a janela do programa. Quando isto ocorre, o viewport OpenGL também será ajustado.
4 Input do programa
Para fornecer ao programa os pontos cujo fecho deve ser calculado, o usuário deve faze-lo através de um arquivo texto comum. Este arquivo deve conter as coordenadas dos pontos, na seguinte ordem: X Y Z. Por exemplo, para fornecer as coordenadas de pontos cujo fecho é o tetraedro seguinte (visualizado pelo programa):
colocaríamos os seguintes pontos no arquivo:
0 0 0
50 0 0
0 50 0
0 0 50
Foram necessários cinco pontos pois este é o número mínimo de pontos que o algoritmo aceita. Note que os primeiros números em cada linhas são correspondentes a coordenada x, o segundo a coordenada y e o terceiro a coordenada z. Os pontos não precisam estar em linhas diferentes; poderiam estar todos na mesma linha, desde que respeitada a ordem das coordenadas mencionada acima.
O arquivo pode ser passado com o parâmetro do executável. Se nenhum parâmetro for fornecido, então o programa abrirá uma caixa de diálogo para que o usuário selecione então o arquivo.
5. Bibliografia
[1] M. J. Laszlo, Computational Geometry and computer graphics in C++, Prentice Hall, Upper Saddle River, NJ, 1996.
[2] J. Neider, T. Davis e M. Woo, OpenGL Programming Guide, Addison-Wesley, Reading, MS, 1993.
[3] C. Petzold, Programming Windows 95, Microsoft Press, Redmond, WA, 1996.
[4] J. O'Rourke, Computational Geometry in C, Cambridge University Press, Cambridge, 1998.
[5] Magic Software, Wild Magic Graphics Library. www.magic-software.com