Modelação Geométrica com Restrições

Fábio Miguel Gonçalves Pinheiro

Dissertação para Obtenção do Grau de Mestre em

Engenharia Informática e de Computadores

Orientador: Prof. António Paulo Teles de Menezes Correia Leitão

JúriPresidente: Prof. Daniel Jorge Viegas Gonçalves

Orientador: Prof. António Paulo Teles de Menezes Correia LeitãoVogal: Prof. David Manuel Martins de Matos

Maio 2016

Agradecimentos

Gostaria de agradecer a todos aqueles que estiveram presentes e me apoiaram ao longo da minha vidaacadémica e em particular durante a realização desta dissertação.

Ao meu orientador Professor António Menezes Leitão pelo apoio, disponibilidade e espírito crítico queem muito contribuíram para o resultado final agora apresentado.

A FCT/MEC pela bolsa de investigação que me foi atribuída, relativa ao projeto “Rosetta - The Genera-tive Design Tool: PTDC/ATP-AQI/5224/2012”, com fundos nacionais PIDDAC.

A todos os colegas e professores com quem trabalhei ao longo do curso.

A todos os meus amigos por estarem sempre presentes com palavras de amizade e incentivo.

Aos meus pais e irmão, o meu profundo agradecimento pelo acompanhamento, perseverança, dedica-ção e apoio incondicional ao longo de toda a minha vida.

i

Abstract

Geometric modeling requires the specification of position, orientation and size of geometric entities.However, the modeler often does not know a priori these properties, but knows other properties thatcan be used to bound and solve the first. These constraints must be calculated in order to discoverthe missing properties. Currently, modelers make this process or part of it manually, making it timeconsuming.

This document presents the tools most widely used for geometric modeling in the area of generativedesign, through programming, containing functionality for specifying relationships and constraints be-tween geometric entities, and that automate part of the geometric modeling process. In this work wepropose a solution which automates the entire process of calculating the geometric properties from con-straints. The proposed solution addresses the problem of values accuracy, functionality expansion andintegration with other tools.

Our geometric constraints solving system is based on transforming the geometric model into sets ofmathematical equations that describe it, which are solved by Maxima, an algebraic computing systemscapable of symbolic manipulation.

Our solution is intended to assist modelers with the mathematical complexity of the geometric model-ing, helping them to follow the geometric construction modeling approach using their preferred tools.

Keywords: Macro; Maxima; Geometric Modelling; Geometric Constraints; Racket; Rosetta

iii

Resumo

A modelação geométrica requer a especificação da localização, orientação e dimensão das entidades ge-ométricas. Contudo, o modelador frequentemente não conhece essas propriedades a priori, mas conheceoutras que podem ser usadas para restringir e resolver as primeiras. Essas restrições têm de ser proces-sadas de forma a descobrir as propriedades em falta. Atualmente, os modeladores fazem este processo,ou parte dele, manualmente, uma processo moroso.

Este documento apresenta as ferramentas mais usadas atualmente para modelação geométrica, na áreade desenho generativo, através de programação, e ferramentas com funcionalidades que premitam es-pecificar de relações e restrições entre as entidades geométricas, e que automatizam parte do processode modelação geométrica. Neste trabalho apresentamos uma proposta de solução que automatiza todoo processo de calcular as propriedades geométricas a partir de restrições. A solução proposta aborda oproblema de exatidão das soluções, expansibilidade das funcionalidades e integração com outras ferra-mentas.

O nosso sistema de resolução de restrições geométricas baseia-se em transformar as entidades geométri-cas e as restrições entre elas em sistemas de equações matemáticas que descreve o modelo geométrico.Estes sistemas são depois resolvidos pelo Maxima, um sistemas de computação algébrica e manipulaçãosimbólica.

Pretende-se assistir os modeladores com a complexidade matemática envolvida na modelação geomé-trica, ajudando-os a seguir a abordagem de modelação por construção geométrica nas suas ferramentasde preferência.

Palavras-Chave: Macro; Maxima; Modelação Geométrica; Racket; Restrições Geométricas; Rosetta

v

Conteúdo

Lista de Tabelas viii

Lista de Figuras xi

Glossário xiii

1 Introdução 11.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Estrutura do documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Estado da Arte 52.1 Conceitos Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 Problema de Satisfação de Restrições . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1.2 Grau de Liberdade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.3 Generalização do CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.4 Domínio do CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.5 Técnicas para Resolver CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1.6 Robustez e Exatidão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Ferramentas de Restrição Geométrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2.1 Grasshopper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2.2 Eukleides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.3 ThingLab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2.4 GeoSolver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2.5 TikZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3 Sistemas de Computação Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Arquitetura 193.1 Entidade Geométrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.1.1 Propriedades das Entidades Geométricas . . . . . . . . . . . . . . . . . . . . . . . . 223.1.2 Entidade ‘value’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.1.3 Entidade ‘point’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.1.4 Entidade ‘line’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.1.5 Entidade ‘circle’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.1.6 Entidade ‘sphere’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2 Biblioteca de Funções Geométricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2.1 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.3 Comunicação do Núcleo de Cálculo Matemático . . . . . . . . . . . . . . . . . . . . . . . . 27

vii

3.3.1 Inicialização do Maxima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3.2 Canal de Comunicação e Formatação de Mensagens . . . . . . . . . . . . . . . . . . 29

3.3.3 Processamento de resultados do Maxima . . . . . . . . . . . . . . . . . . . . . . . . 30

3.4 Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.4.1 Criação de Entidades Geométricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.4.2 Funções Disponíveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.4.3 Estrutura auxiliar das Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.4.4 Macros Higiénicas de Racket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.5 Geração das Equações Matemáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.5.1 Representação Matemática das Entidades Geométricas . . . . . . . . . . . . . . . . 36

3.5.1.1 Entidade ‘point’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.5.1.2 Entidade ‘sphere’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.5.1.3 Entidade ‘circle’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.5.1.4 Entidade ‘line’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.5.1.5 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.5.2 Entidade ‘form’ e as estruturas ‘mathProblem’ e ‘property’ . . . . . . . . . . . . . . 38

3.5.3 Restrição de Interseção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.5.4 Restrição de Pontos de Superfície . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.5.5 Função de Linhas Paralelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.5.6 Função de Círculos Tangentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.6 Despacho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.7 Integração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4 Avaliação 474.1 Robustez e Exatidão da Linguagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.2 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.3 Núcleo de Cálculo Matemático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.4 Expansão da Linguagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.4.1 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5 Conclusões 555.1 Trabalho Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.1.1 Melhoria de Funcionalidades Implementadas . . . . . . . . . . . . . . . . . . . . . 57

5.1.2 Novas Funcionalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.1.3 Operações Bidimensionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.1.4 Integração com Bibliotecas de Funções Geométricas . . . . . . . . . . . . . . . . . . 59

5.1.5 Integração com outros Sistemas de Cálculo Matemático . . . . . . . . . . . . . . . . 59

5.1.6 Otimizações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.1.6.1 Resolução do problema de comunicação . . . . . . . . . . . . . . . . . . . 60

5.1.6.2 Problemas Geométricos Recorrentes . . . . . . . . . . . . . . . . . . . . . 60

5.1.6.3 Reexecução do Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.1.7 Considerações Futuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.2 ConstraintGM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Bibliografia 61

A Listagem de Funções das Entidades 67

viii

Glossário

ix

x

Lista de Tabelas

2.1 Lista de APIs e ferramentas de programação dos CAD. . . . . . . . . . . . . . . . . . . . . 102.2 Lista de ferramentas de desenho generativo. . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Ferramentas de Cálculo Matemático. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1 Formatação das mensagens pelas funções de comunicação. . . . . . . . . . . . . . . . . . . 30

xi

Lista de Figuras

1.1 Modelação por construção geométrica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Construção geométrica de um pentágono com régua e compasso. . . . . . . . . . . . . . . 2

2.1 Grasshopper - Exemplo de código e respetivo resultado. . . . . . . . . . . . . . . . . . . . 122.2 Circunferência de Feuerbach, também conhecido com Circunferência de nove pontos. . . 122.3 Plataforma GeoSolver - Decomposição em árvore do problema e respectiva solução. . . . 142.4 Modelação por construção geométrica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.1 Organização dos módulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2 Fluxo de informação Núcleo de Cálculo Matemático. . . . . . . . . . . . . . . . . . . . . . 273.3 Retas tangentes entre círculos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1 Cenário onze do benchmark. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2 Cenário doze do benchmark. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

xiii

Glossário

BFG Biblioteca de Funções Geométricas. 25, 26, 42, 43, 47–49, 55, 56, 59, 60

BIM Building Information Model. 9, 10

CAD Computer-Aided Design. 2–4, 9, 10

CGAL Computational Geometry Algorithms Library. 8, 26, 59

CSOP Constraint satisfaction optimization problem. 6

CSP Constraint Satisfaction Problem. 5–7, 9, 13, 14, 16, 20, 27

DoF Degree of Freedom. 6, 13–15, 56

DSL Domain-Specific Language. 19

NCM Núcleo de Cálculo Matemático. 20, 23, 25, 27, 28, 30, 31, 35–37, 39, 40, 42, 43, 47–50, 53–56, 59, 61

PCSP Partial constraint satisfaction problem. 6

xv

Capítulo 1

Introdução

A modelação geométrica requer a especificação da localização, orientação e dimensão das entidades ge-ométricas. Contudo, é frequente o modelador não conhecer essas propriedades a priori, mas conheceroutras que possam ser usadas para restringir e resolver essas propriedades. Por exemplo, o modeladorpode restringir entidades geométricas através da especificação de relações com outras entidades, essasrelações podem ser incidência, tangência, paralelismo, perpendicularidade, distância, volume, entre ou-tras. Essas restrições têm de ser processadas de forma a descobrir a localização, orientação e dimensãodas entidades geométricas. Atualmente, os modeladores fazem este processo ou parte dele manual-mente, tornando-se muito moroso.

As restrições geométricas também podem ser usadas a posteriori. Isto é, o conjunto de restrições geo-métricas pode ser usado para validar automaticamente um modelo geométrico. Por exemplo, por lei,as escadas não podem ter uma inclinação maior do que um determinado limite, e cada degrau tem queser menor do que uma determinada altura. Todas essas restrições podem ser verificadas automatica-mente por um sistema, detetando assim, infrações e permitindo informar de imediato o utilizador casoo conjunto das mesmas esteja a ser violado.

A modelação através da especificação de restrições geométricas é muito útil, pois possibilita que o mo-delador se expresse sem que tenha que passar pelo demorado processo de encontrar a localização, ori-entação e dimensão das entidades geométricas.

Exemplo 1: considere que se pretende modelar a figura com a seguinte descrição. A figura é compostapor quatro pontos (A, C, M e T ), três linhas (AC, AT e MT) e uma circunferência; a circunferência estácentrada em C; a linha AT é tangente à circunferência e passa no ponto A; o ponto M é a interseção entrea linha AC e a linha perpendicular a esta que passa no ponto T. Apesar de todas estas especificações,o modelo geométrico continua com alguns graus de liberdade, tais como: os pontos ainda não têm asua localização exata, embora existam relações entre eles, o raio da circunferência não está definido eexistem duas possíveis tangentes se o ponto A não estiver contido na circunferência. Contudo, pode-seinferir que o raio da circunferência não pode ser maior que a distância entre A e C, uma vez que o pontoA tem de estar fora da circunferência (centrada em C) para que a tangente possa existir. Uma possívelsolução destas especificações está ilustrada na Figura 1.1.

Com as especificações descritas não é possível concluir a localização final dos pontos, o que é um pro-blema, pois a maioria das ferramentas de modelação geométrica necessitam dessas informações. Paradesenhar uma linha é necessária a localização do ponto inicial e do ponto final. Desta forma, é difícil

1

A

C

T

M

Figura 1.1: Modelação por construção geométrica. A figura satisfaz as especificações/restrições descri-tas no Exemplo 1.

modelar as especificações acima, uma vez que o utilizador tem de calcular a localização desses pontos.Este processo é moroso requerendo a resolução de problemas geométricos através de técnicas matemá-ticas potencialmente complexas. Todavia, o processo de modelação pode ser melhorado usando umaferramenta adequada que suporte a especificação das restrições geométricas na criação do próprio mo-delo.

Exemplo 2: considere a criação de um pentágono tal como descrito no artigo de Harry Mairson [1],através do método de construção geométrica tradicional, ilustrado na Figura 1.2. O método começa apartir dum dos lados do pentágono (o segmento de reta AB da figura), usando a régua e o compassopara encontrar interseções e assim construir o resto da figura. A utilidade deste tipo de raciocínio ésubestimado pelas aplicações de desenho assistido por computador CAD, o que faz com que o utilizadorgaste o seu tempo a pensar como modelar o problema. No entanto, uma modelação declarativa atravésda especificação de restrições geométricas poderia facilitar todo o processo de modelação, exprimindoa intenção do desenhador diretamente no modelo geométrico.

Figura 1.2: Construção geométrica de um pentágono com régua e compasso. Imagem adaptada doartigo [1, Figura 1].

2

Recentemente, novas abordagens têm sido introduzidas no processo de modelação de design e arquite-tura, bastante flexíveis e aptas a lidar com as necessidades atuais dos modeladores. O Desenho Genera-tivo é uma delas e pode ser definido como a criação de formas determinada por algoritmos. Nos últimosanos tem havido uma crescente procura por ferramentas que permitam a implementação de algoritmospara Desenho Generativo.

Em arquitetura, os projetos são cada vez mais sofisticados, tanto ao nível de tamanho como ao nível decomplexidade. Por isso, os custos de pequenas alterações aos projetos tornam-se incomportáveis, sobre-tudo quando se usam os métodos tradicionais de modelação. Por isso, os grandes ateliers de arquiteturaestão a virar-se para a programação de forma a modelar os edifícios, criando a necessidade de arquitetoscom conhecimentos de programação e de ferramentas dedicadas para o efeito. Para responder a essanecessidade, algumas universidades incluíram nos cursos de graduação de arquitetura uma disciplinade programação.

Uma dessas ferramentas é o Rosetta, um ambiente de programação que permite o uso de diferenteslinguagens de programação em diversas aplicações de CAD. Esta aplicação tem como objetivo libertaros utilizadores de estarem presos a uma família de aplicações CAD, facilitando assim a portabilidade.Por outro lado, o Rosetta, tal como a maioria das ferramentas deste tipo, não possui mecanismos paraespecificação de restrições geométricas. [2, 3]

Este documento analisa várias linguagens de programação dedicadas à modelação geométrica, que su-portem a especificação de restrições geométricas. Entre estas linguagens encontram-se: Eukleides [4],Tikz [5], ThingLab [6], GeoSolver [7] e Grasshopper [8]. Estas linguagens de programação foram cri-adas com objetivos e finalidades distintas, mas todas elas proporcionam ao utilizador funcionalidadesque permitem descrever o modelo geométrico, de forma a auxiliar o desenhador a manter-se fiel ao seumodelo mental.

Adicionalmente, o documento responde às seguintes questões:

• Como resolver um conjunto de restrições e quais as principais dificuldades?

• Quais são as ferramentas existentes que permitem especificar restrições geométricas a fim de faci-litar o processo de modelação geométrica?

• Como é efetuada a interação entre o utilizador e essas ferramentas?

Objetivos

O objetivo deste trabalho é criar um sistema que permita ao utilizador fazer modelação geométrica atra-vés da especificação de restrições geométricas numa linguagem de programação. E o objetivo secundá-rio é dar a possibilidade de integrar o nosso sistema com o sistema desenvolvido no projeto Rosetta, afim de estender o poder descritivo da modelação geométrica do Rosetta com a especificação de restriçõesgeométricas.

Pretende-se fornecer ao utilizador final a possibilidade de fazer a modelação por construção geomé-trica. Deste modo o utilizador pode descrever relações e restrições entre as entidades geométricas, semque estas tenham que estar à partida totalmente definidas. Pretendemos, assim, retirar do utilizador acomplexidade matemática envolvida na modelação geométrica.

3

A integração com projeto Rosetta oferece ao utilizador a possibilidade de combinar este género de mo-delação com a modelação e funcionalidades oferecidas pelas ferramentas CAD preferidas dos utiliza-dores. Isto permite-nos focar em oferecer ao utilizador a possibilidade de usar as restrições geométricasna criação do modelo, para além de permitir ter uma forma de demonstração visual das capacidades dosistema.

Tendo em consideração o objetivo secundário, assumiu-se que a maioria dos utilizadores são arquitetoscom reduzidos conhecimentos de programação. Por isso, pretende-se que as funcionalidades criadaspara a descrição de restrições geométricas sejam de simples utilização e de fácil perceção. No entanto,pretende-se proporcionar aos utilizadores que tenham mais conhecimentos de programação, poderemestender as funcionalidades do sistema criado, de uma forma fácil e uniforme que possa ser partilhadacom os restantes utilizadores.

Estrutura do documento

Neste capítulo introduziu-se o problema e os objetivos do trabalho. O capítulo 2 apresenta o trabalhorelacionado e identifica os conceitos relacionados com o problema de satisfação de restrições, focando-sena resolução de restrições geométricas e na importância da exatidão dos resultados. Por fim, são anali-sadas ferramentas relacionadas com o problema de resolução de restrições geométricas. No capítulo 3apresenta-se a proposta de solução onde é explicada a arquitetura do trabalho desenvolvido, identifi-cação da metodologia aplicada, avaliação de diferentes hipóteses e decisões tomadas que contribuírampara o desenho da ferramenta, e, ainda, um comentário sobre as dificuldades encontradas e sobre aevolução da solução ao longo do desenvolvimento do trabalho. No capítulo 4 avalia-se a solução desen-volvida, compara-se o desempenho das duas soluções implementadas, analisam-se os sistemas de com-putação algébrica e manipulação simbólica, e compara-se a solução final com as principais ferramentasexistentes no mercado. No capítulo 5 são apresentadas conclusões finais e são propostos trabalhos arealizar no futuro.

4

Capítulo 2

Estado da Arte

Nesta capítulo é analisado o estado-da-arte relacionado com restrições geométricas, linguagens de mo-delação e ferramentas de desenho arquitetural, incluindo conceitos gerais que envolvem as restriçõesgeométricas.

Conceitos Gerais

As restrições geométricas são limitações colocadas às entidades geométricas. Dependendo do conjuntode restrições usadas no modelo geométrico, este pode ter diversos graus de liberdade. Se o conjuntode restrições estiver totalmente restringido, existe apenas uma solução possível, ou seja, a localização,orientação e dimensão das entidades geométricas têm valores fixos.

As restrições geométricas podem ser expressas matematicamente por um sistema de equações, porexemplo, a restrição que especifica que o ponto A = (xa, ya, za) está mais perto da origem que o pontoB = (xb, yb, zb) pode ser representada em notação matemática por uma inequação (Fórmula 2.1) que dizque a distância do ponto A à origem deve ser menor que a distância do ponto B à origem.√

x2a + y2

a + z2a <

√x2

b + y2b + z2

b (2.1)

As propriedades de uma entidade geométrica são um conjunto de características da própria entidade.Por exemplo, um cone tem as seguintes propriedades: raio da base, altura, localização do vértice de topo,localização do centro da base, direção do cone, volume, área de superfície, área lateral, área da base,entre outras. Muitas das propriedades estão relacionadas entre elas, por exemplo, a área de superfície éigual à soma da área lateral e da área da base, a direção do cone pode ser obtida através da localização dovértice de topo e do centro da base. Desta forma, a mesma entidade geométrica pode ser descrita atravésde diferentes conjuntos de propriedades. Por exemplo, uma esfera é habitualmente descrita através doraio e centro, mas pode ser descrita através de quatro pontos de superfície não colineares.

Problema de Satisfação de Restrições

O Problema de Satisfação de Restrições (CSP) é um problema matemático (definição 1) que consiste numconjunto de objetos cujo estado deve satisfazer todas as restrições, ou seja, consiste em encontrar um va-

5

lor para cada variável (conjunto V da definição 1), entre os valores associados a essas variáveis (conjuntoD da definição 1), e onde as restrições (conjunto C da definição 1) especificam que determinados valoresnão podem ser usados em conjunto.

Definição 1 O CSP é o triplo P =(V,D,C) [9, 10] onde:

• V = v1, ..., vn é o conjunto de variáveis.

• D = D1, ..., Dn é o domínio das variáveis, isto é, Di representa os valores que estão associados a vi e queeste pode assumir.

• C = c1, ... cm é o conjunto de restrições, onde cada c ∈ C é um subconjunto do produto cartesiano Πi∈Vc Di

onde Π é o produtório/piatório e Vc ⊆ V é o conjunto de variáveis em c.

O CSP é um problema altamente combinatorial e habitualmente da classe NP-completo.1 [9]

Grau de Liberdade

O grau de liberdade (DoF) de um CSP refere-se ao número de possíveis soluções do CSP. O CSP podeestar demasiado restringido (Over-Constrained), pouco restringido (Under-Constrained) ou totalmente res-tringido (Well-Constrained). Contudo não é óbvio saber à partida qual é DoF de um conjunto de restri-ções. Considere-se os seguintes exemplos, onde queremos calcular o valor da variável x, que existe numespaço unidimensional e está restringida pelas seguintes inequações:

• x > 1∧ x < 1⇒ (Over-constrained) não existe solução para o CSP.

• 1 < x < 2⇒ (Under-constrained) existem inúmeras soluções para o CSP.

• x ≥ 1∧ x ≤ 1⇒ (Well-constrained) existe uma só solução para o CSP.

Generalização do CSP

Existem ainda alguns problemas mais genéricos, tais como o problema de otimização de satisfação derestrições (CSOP - Constraint satisfaction optimization problem) e o problema de satisfação parcial de restri-ções (PCSP - Partial constraint satisfaction problem). O CSOP é um problema de otimização, cujo objetivoé encontrar a solução ou soluções que tenham um custo mínimo. Um exemplo típico é o problema decalendarização com o mínimo de horas livres. O PCSP é mais genérico que o CSOP, é habitualmenteaplicado em cenário onde o DoF é over-constrained Um exemplo típico é o problema de máxima utili-dade (maximum utility problem), este problema é apresentado no artigo [11] assim como uma descriçãodo PCSP.

Domínio do CSP

Quando se fala no domínio de um CSP refere-se ao domínio das variáveis (conjunto D da definição1), ou seja, ao conjunto de valores que cada variável pode assumir. A grande maioria da investigaçãoefetuada sobre CSP assume que o conjunto de valores é finito. Por esta razão, quase todos os algoritmosde resolução do CSP funcionam com essa condição. Para além disso, é mais simples do que o caso

1NP-completo é a classe de problemas que são ao mesmo tempo NP (dada uma solução, é verificável em tempo polinomial) eNP-difícil (um problema de decisão H é NP-difícil, quando para qualquer outro problema NP L, existe uma redução de L para Hem tempo polinomial)

6

infinito. Um algoritmo simplista que resolve estes CSP seria tentar todas as combinações de valorespossíveis entre as variáveis até encontrar uma solução. Os algoritmos que tentam tratar os CSP comvariáveis que podem assumir infinitos valores têm duas grandes condicionantes: a primeira é exigirmuito mais poder computacional para tentar resolver o CSP; a segunda é não serem capazes de garantirque não existe solução ou mais soluções que as encontradas. Podemos ainda subclassificar os CSP comdomínio infinito em discreto (por exemplo, x ∈ Z) e contínuo (por exemplo, x ∈ [0, π]).

Técnicas para Resolver CSP

Em [12, 13] são apresentadas cinco metodologias diferentes para resolver os CSPs, estas são:

• Propagação local de restrições: Esta metodologia representa o CSP num grafo não direcional,usado para propagar as restrições geométricas. Contudo, o grafo não pode conter ciclos.

• Resolução numérica de restrições: esta metodologia representa o CSP com um sistema de equa-ções algébricas e tenta encontrar soluções. Os algoritmos usados são capazes de lidar com grandessistemas não-lineares mas assumem que o CSP está totalmente restringido e que cada variávelpode apenas assumir um conjunto finito de valores.

• Manipulação simbólica: esta metodologia representa o CSP com um sistema de equações e usamétodos de manipulação simbólica para os resolver. Esta técnica pode concluir que a soluçãoexiste mas ser incapaz de a encontrar, ou necessitar de tempo e memória exponenciais, conformea complexidade do CSP.

• Procura heurística: esta metodologia representa o CSP com fatos e regras que utiliza para criar umteste procedimental para encontrar soluções, semelhante à linguagem Prolog. Contudo, os algorit-mos usados são pouco escaláveis a nível computacional. Desta forma, são incapazes de lidar comgrandes sistemas de restrições [6].

• Simplificação de CSP: esta metodologia é composta por duas fases e representa o CSP com umgrafo. Na primeira fase, as dependências entre os nós do grafo são analisadas, para que o pro-blema possa ser decomposto em vários sub-problemas mais simples chamados clusters. A soluçãodo problema inicial é a junção das soluções desses clusters, que normalmente são independentesou contêm poucas dependências entre eles. Na segunda fase, os clusters são formados e resol-vidos individualmente usando outras técnicas (resolução numérica de restrições e manipulaçãosimbólica).

A maior parte da investigação efetuada na resolução de CSP foca-se nos problemas mais simples, ondesó existe uma solução e onde as variáveis podem assumir um conjunto reduzido de valores, muitasdas vezes, valores booleanos. A investigação efetuada nos problemas mais complexos usa algoritmosotimizados para o contexto do CSP em questão, parando procuras que, à partida, sabe-se que não fazemsentido no contexto do problema, reduzindo assim o número de possíveis caminhos para a procura dasolução. Porém, isto faz com que as técnicas usadas não sejam genéricas.

7

Robustez e Exatidão

A falta de robustez ou exatidão é um problema bem conhecido no campo da modelação geométrica [14].Isto, acontece porque muitos dos algoritmos de modelação geométrica são desenvolvidos a partir dealgoritmos de computação gráfica, onde o tempo de computação é mais importante do que a exatidãodo modelo geométrico. No entanto, na modelação geométrica, os resultados podem ser reutilizadospara cálculos posteriores, enquanto na computação gráfica os resultados são usados essencialmentepara visualização.

Ainda existem muitos algoritmos de modelação geométrica que são implementados com uma precisãofinita, geralmente a aritmética de vírgula flutuante da máquina, tornando-o dependente da especificaçãodo software e do hardware.

Um exemplo típico é o caso de descobrir se duas retas são ou não paralelas. Para responder a estaquestão compara-se o declive de cada uma das retas. Infelizmente, se o declive for representado porum float, o seu cálculo pode envolve erros de representação e arredondamentos. Uma forma de mitigareste problema é usando aritmética de precisão arbitrária à custa de poder computacional. Este problemaleva a que as ferramentas se comportem de forma errada. Por exemplo, podem afirmar que duas retasnão são paralelas, embora teoricamente elas sejam, ou vice-versa, devido a discrepâncias mínimas entreos valores do declive. O que algumas aplicações, como o AutoCAD, fazem é assumir que as retas nãoparalelas têm declives significativamente diferentes, ou seja, duas retas são paralelas se a diferença entreos declives for inferior a um determinado valor suficientemente pequeno.

O CGAL é uma bibliotecas que tentam fornecer algoritmos robustos para modelação geométrica, talcomo apresentado no artigo [15]. O artigo [16] fala sobre a aplicação do CGAL no contexto académico eno contexto industrial.

Mas, mesmo usando estas bibliotecas, os seus criadores fornecem um conjunto de boas práticas, como,evitar os valores numéricos que as máquinas não consigam representar com precisão ou operações queusem ou produzem esses números.

Por exemplo, acima apresentámos a restrição do ponto A = (xa, ya, za) estar mais perto da origem que oponto B = (xb, yb, zb), e, para descrever a restrição, comparamos as distâncias de cada ponto à origem.Infelizmente, isto implica o cálculo de raízes quadradas (Fórmula 2.1), o que poderá produzir resultadosinexatos. Contudo, para comparar as duas distâncias não precisamos de calcular o valor da distânciaem si. Assim, como boa prática, devíamos ter comparado o quadrado da distância (Fórmula 2.2) dospontos à origem, evitando o cálculo das raízes quadradas, uma vez que esta operação pode envolverarredondamentos e representações inexatas de valores.

x2a + y2

a + z2a < x2

b + y2b + z2

b (2.2)

Ferramentas de Restrição Geométrica

Existe uma crescente procura de linguagens de programação que permitem fazer desenho generativo.Contudo, poucas oferecem a possibilidade de especificar restrições geométricas, e quase todas elas ne-cessitam de conseguir resolver a restrição no momento em que é especificada. Nesta secção, vamosdiscutir algumas das ferramentas de software e linguagens de programação que oferecem capacidades

8

de modelação através da especificação de restrições geométricas. A resolução de CSPs é um problemacomplexo e difícil de aplicar a um tema especifico como modelação geométrica. Para além disso, nãoquisemos limitar a nossa área de estudo só a resolução de restrições geométricas. Por isso, alargámosa nossa procura de ferramentas e aplicações para o que está a ser atualmente usado para satisfazer asnecessidades cobertas pelo nosso tema.

Na página web da disciplina de Computer Design da universidade “Massachusetts Institute of Tech-nology” (http://academy.cba.mit.edu/classes/computer_design), pode-se encontrar uma classifi-cação de ferramentas e aplicações relacionadas com o tema deste trabalho, de seguia vamos analisaralgumas destas ferramentas.

Estas aplicações disponibilizam funcionalidades que ajudam o utilizador a criar o modelo geométrico,incluindo a possibilidade de impor relações e restrições entre as entidades geométricas, mas poucasdelas permitem a modelação através de programação.

Muitas destas aplicações disponibilizam ferramentas e APIs para que possam interagir com outras apli-cações. Isto leva à existência de ferramentas que oferecem funcionalidades integradas com as ferramen-tas CAD, possibilitando assim ao utilizador fazer modelação geométrica através de uma linguagem deprogramação. Entretanto, a modelação geométrica disponibilizada que primita a especificação de res-trições geométricas são limitadas. Por exemplo, enquanto numa aplicação CAD existem diversas inter-faces gráficas especializadas para ajudar o utilizador a criar circunferências a partir de retas tangentesou pontos de superfície, entre outras, na API oferecida pela aplicação existem reduzidas maneiras decriar circunferências, nomeadamente com o centro e o raio. A tabela 2.1 apresenta as característicasmais interessantes de algumas destas ferramentas. A maioria das ferramentas requer conhecimentos deprogramação, sendo pouco adequadas para quem se inicia na programação. Isto constitui uma barreirainicial que faz com que muitos arquitetos desistam à partida.

A tabela 2.2 apresenta ferramentas que permitem ao utilizador fazer modelação geométrica através deuma descrição do modelo com recurso a especificação de restrições geométricas. Contudo, a maiorparte destas ferramentas necessitam que a restrição seja imediatamente resolvida no momento em que outilizador a aplica, ou seja, modelo tem que ter informação suficiente para que a operação seja aplicadaimediatamente. Para além disso, as ferramentas, têm uma interface gráfica que impossibilita a criaçãode procedimento automatizados para aplicar estas operações e gerar geometria.

Na introdução, demos o exemplo das escadas, que tinham de respeitar um conjunto de regras: por leinão podiam ter uma inclinação maior que um certo ângulo e cada degrau tem uma altura máxima.Estas restrições podem ser automaticamente validadas por um sistema de satisfação de restrições. Asaplicações Building Information Model (BIM) têm-se tornado populares um pouco nesse sentido deobrigar o utilizador a respeitar um conjunto de regras enquanto modela o edifício. Nestas aplicações, osobjetos têm muita semântica associada, não se limitando à forma geométrica, tentando englobar todo ociclo de vida da construção do edifício. Por exemplo, dois tubos independentes não se podem intersetarfisicamente ou as janelas tem de estar numa parede e não podem estar no mesmo sítio que outras janelasou portas, entre outras restrições. Uma ferramenta BIM não permite a criação de um modelo onde umaconduta de ar passe por um pilar de betão. No enquanto, nas ferramentas CAD é tudo apenas geometria.

Todavia, as aplicações BIM são menos adequadas para modelação geométrica que as aplicações CAD,dificultando mesmo o trabalho de modelação aos arquitetos, porque obrigam-nos a definir logo o ma-terial dos objetos (modelo ‘X’ marca ‘A’) no processo de desenho. Estas especificações fazem variar oconjunto de regras que é necessário satisfazer.

9

Por esta razão, decidiu-se dar mais importância à análise de ferramentas de modelação puras, umavez que as ferramentas BIM tal como apresentadas afastam-se do âmbito do trabalho. As ferramentasBIM estão a evoluir muito na ótica de avaliação de restrições geométricas a posteriori, e os objetivos dotrabalho são mais na ótica do processo de criação do modelo geométrico, desta forma as ferramentasCAD são mais interessantes para o trabalho.

A tabela 2.1 apresenta ferramentas que permitem trabalhar diretamente com as aplicações CAD, que vãoao encontro das necessidades de desenho generativo. De seguida, vamos analisar em pormenor algumasdestas ferramentas, mais concretamente, a linguagem de programação Grasshopper, uma aplicação parao CAD Rhinoceros 3D, pelo fato de ser uma linguagem de programação visual, o que é uma característicainteressante, porque reduz o impacto da barreira inicial de requerer conhecimentos de programação.Da tabela 2.2 escolhemos quatro ferramentas, reconhecidas pelas características distintas e interessantespara o nosso tema (nível de conhecimento de programação requisitado, técnicas usadas para resolvemas restrições, finalidades para que foram desenvolvidas), estas ferramentas são: Eukleides, GeoSolver,ThingLab e TikZ.

Tabela 2.1: Lista de APIs e ferramentas de programação dos CAD.

Ferramentas CAD CaracterísticasActiveX Automation

for nanoCAD nanoCAD Linguagens JavaScript e VBScript

Antimony Própriaaplicação

Linguagem de programação visual e textual(Python); Excelente mecanismo de CSG

AutoCAD .Net API AutoCAD Grande poder descritivoAutoLisp AutoCAD Dialeto de Lisp

Grasshopper Rhino Linguagem de programação visual

ObjectARX AutoCAD Grande poder descritivo; Requer vastosconhecimentos de programação

Python scriptingfor Rhino Rhino Linguagem Python

RhinoScript Rhino Linguagem VBScript

Rosetta [2, 3] diversasaplicações

Fácil de aprender; Termos arquiteturais;Suporta diversas linguagens de programação

Sketchup Ruby API Sketchup Linguagem Ruby, Semelhante a língua natural;Boa integração com ferramentas CAD

Visual Lisp AutoCAD Linguagem de programação visualActiveX Automation for nanoCAD - http://nanocad.com/page/Programming1/CSG (Constructive solid geometry) - é um técnica usado na modelação geométrica de sólidos, através de ope-

rações binárias, por exemplo as operação de união e interseção em sólidos.AutoCAD .Net API - http://docs.autodesk.com/ACD/2010/ENU/AutoCAD%20.NET%20Developer%27s%

20Guide/

AutoLisp - http://en.wikipedia.org/wiki/AutoLISP/Grasshopper - http://www.grasshopper3d.com/ObjectARX - http://en.wikipedia.org/wiki/ObjectARX/Python scripting for Rhino - http://wiki.mcneel.com/developer/python/RhinoScript - http://www.rhinoscript.org/Sketchup Ruby API - http://www.sketchup.com/intl/en/developer/Visual Lisp - http://www.afralisp.net/visual-lisp/

Grasshopper

É uma linguagem de programação visual, usada principalmente para a criação de algoritmos de desenhogenerativo, que depois geram geometria na aplicação CAD Rhinoceros 3D. [8]

No Grasshopper, as funções são chamadas componentes e a maioria desses componentes geram geome-

10

Tabela 2.2: Lista de ferramentas e bibliotecas de desenho generativo que permitemfazer restrições geométricas.

Ferramentas Interface Características

Cabri IG 3D; Lógica de construção geométricaclássica (régua e compasso)

CaRMetal IG 2.5D; Macros; Scripting em JavaScriptCinderella IG Geometria hiperbólica; Scripting em CindyScript

CGAL [15] LP Biblioteca de C++ de algoritmos geométricosespecializada em robustez

Dr. Geo II IG Logica do Smalltalk; Fácil de estender a ferramentaEukleides [4] LP Linguagem de programação declarativa

GCLC/Wingclc IG Construções geométricas baseadasem expressões matemáticas

Geogebra IG 3D; Expressões matemáticas; CAS; Scripting

GeoSolver [17] LP Biblioteca de Python especializadaem restrições geométricas

Kaleidoscope [18] LP Linguagem de programação de restriçãoThingLab [6] IG e LP Paradigma de programação dataflow

TikZ [5] LP Desenho do vetorial através especificaçõesIG — Interface Gráfica

LP — Linguagem de ProgramaçãoCabri - http://www.cabri.com/CaRMetal - http://en.wikipedia.org/wiki/CaRMetal/Cinderella - http://www.cinderella.de/Dr. Geo II - http://www.drgeo.eu/GCLC/Wingclc - http://poincare.matf.bg.ac.rs/~janicic//gclc/Geogebra - http://www.geogebra.org/

tria 3D que depois é exibida no Rhinoceros. Alguns dos componentes permitem ao utilizador encontrarintersecções [8] entre: duas linhas, uma linha e um arco, uma linha e um círculo, entre dois círculos,duas esferas, três planos, e outros. Existe um componente diferente para realizar cada uma destas ope-rações. No Grasshopper, os componentes podem ser combinados, ou seja, os resultados de uns sãousados como parâmetros de entrada noutros componentes e os arredondamentos vão-se acumulando,o que pode provocar problemas de robustez e validade dos resultados.

O inconveniente do Grasshopper é que a complexidade do código não é escalável com a complexidadedo modelo, uma vez que o código é visualizado bidimensionalmente, este torna-se rapidamente difí-cil de navegar, e por consequência difícil de compreender, à medida que adicionamos complexidadeao modelo, como se pode observar na Figura 2.1. No artigo [19], comparam-se as linguagens de pro-gramação visual com as linguagens de programação textual: A medida que o código vai ganhandocomplexidade, por norma, torna-se mais produtivo usar uma linguagem de programação textual queuma visual. Por outro lado, uma linguagem de programação visual é mais fácil e rápida para novosutilizadores apreenderem e começarem a usar.

Eukleides

É uma linguagem de programação criada com o objetivo de descrever e gerar figuras bidimensionais.Esta ferramenta está disponível em [4], sob a licença GNU General Public License.

Os programas escritos em Eukleides consistem numa parte declarativa onde os objetos geométricos sãodefinidos e noutra parte onde os objetos são desenhados. Para além disso, Eukleides é uma linguagemde programação completa, com condições lógicas, estruturas iterativas e definição de funções, sendo

11

Figura 2.1: Grasshopper - Exemplo de código e respetivo resultado. Imagem retirada de http:

//rhinocentre.blogspot.pt (Maio de 2015).

capaz de lidar com os tipos básicos de uma linguagem de programação, mas também com entidadesgeométricas.

A Figura 2.2 e o código 2.1 são dois exemplo do Eukleides, que ilustram algumas das capacidadesdesta linguagem. A linguagem modelação textual do Eukleides é pouco verbosa, contudo isso a trona-apouco compreensível ao leitor. Por exemplo, na primeira linha do código 2.1 são descrito três pontosque constituem os vértices de um triângulo reto no ponto B, em que o comprimento de AB = 5 unidadese que o angulo B̂AC = 25o. O restante código é apenas para desenhar o triângulo e a circunferência quepassa pelos seus vértices.

Código 2.1: Eukleides - Código de um tri-ângulo reto inscrito numa circunferência.A B C right 5, 25deg

draw

(A.B.C)

circle(A, B, C)

end

Figura 2.2: Circunferência de Feuer-bach, também conhecido com Circun-ferência de nove pontos.

12

Código 2.2: Classe da restrição do ponto intermédio de uma linha em ThinLag.1 Class MidPointLine

2 Superclasses

3 Geometric Object

4 Part Descriptions

5 line: a Line

6 midpoint: a Point

7 Constraints

8 midpoint = (line pointl + line point2)/2

9 midpoint <-- (line pointl + line point2)/2

10 line point1 <-- midpoint * 2 - line point2

11 line point2 <-- midpoint * 2 - line point1

ThingLab

É um ambiente de programação visual e foi pensado com o objetivo de ser um sistema computacio-nal para a propagação de restrições. O utilizador especifica as restrições na interface gráfica que estadisponibiliza. As restrições são representadas como nós de um grafo que o sistema usa para propagarinformação de umas partes para outras de forma a decidir se, e como, as restrições podem ser satisfeitas.Nesta análise estamos a referir-nos a uma das primeiras versões desta ferramenta, relatada no artigo [6],para analisar a metodologia particular de avaliação e execução do código.

Cada restrição tem um conjunto de métodos associados e cada um destes métodos representa uma formadistinta de satisfazer essa restrição. Como se pode observar na secção das restrições (“Constraints”) docódigo 2.2, a restrição é satisfeita se um desses métodos devolver qualquer valor diferente de ‘FALSE’.

O ThingLab foi especialmente criado por cima da linguagem Smalltalk para permitir o estilo de progra-mação “Data Flow,” tornando-o particularmente interessante para o nosso tema. O “Data Flow” é umparadigma de programação para modelar o programa como uma série de ligações por onde a informa-ção circula livremente. Estas ligações são funções que servem para transformar e propagar valores noCSP. A escrita das classes que representam restrições requer conhecimentos intermédios de programa-ção e uma boa compreensão tanto do funcionamento do sistema como de noções de matemática e degeometria. A resolução de restrições usando o paradigma “Data Flow” é discutido no artigo [20].

Contudo, em ThingLab, todos os métodos alternativos para satisfazer as restrições têm de ser expli-citamente descritos para que o paradigma de “Data Flow” funcione. No código 2.2, da classe da res-trição do ponto intermédio de uma reta, existem quatro maneiras diferentes de satisfazer esta res-trição, logo existem quatro métodos para a resolver. A restrição tem três campos de entrada/saídade valores (as duas extremidades da reta e o ponto intermédio). Existe métodos implementados ecada um resolve em ordem a um campo em falta. Estes métodos, quando são chamados (conformeo campo que falta), satisfazem sempre a restrição devolvendo o valor do campo em falta. O quartométodo é chamado quando temos os três campos à partida, e neste caso, o método é uma função(pmedio = (piniciodelinha + p f imdelinha)/2) que devolve um valor booleano: caso esse valor seja ‘FALSE’,o teste falha, significando que o conjunto de restrições não pode ser satisfeito. Para além disto, estatécnica não funciona bem para CSPs com vários graus de liberdade (DoF - under-constrained) e é poucoescalável porque o número de métodos chamados cresce exponencialmente com o número de restrições.

13

GeoSolver

O GeoSolver é uma biblioteca escrita em Python, uma linguagem de programação dinâmica de propó-sito geral. A biblioteca é usada para analisar e resolver restrições geométricas [7]. É capaz de tratar derestrições geométricas relativamente simples em modelos tridimensionais, tais como: a distância entredois pontos, ângulo entre três pontos, entre outros. O GeoSolver tenta encontrar soluções genéricas, ouseja, mesmo que o CSP tenha mais que uma solução (DoF - under-constrained), a biblioteca tenta achartodas as soluções. [17, 12]

O GeoSolver têm uma plataforma com uma interface gráfica (Figura 2.3), que pode ser usado para editaras restrições e ajudar o utilizador a escolher uma solução em particular. Esta ferramenta auxiliar temuma abordagem interessante porque mostra ao utilizador a decomposição do problema em árvore, deforma a ajudar a compreendêr os conflitos que possam existir entre as restrições. Por outro lado, é poucoconveniente mostrar esta informação interna ao utilizador, porque não é fácil compreendê-la, uma vezque está diretamente relacionada com as técnicas usadas para resolver o CSP e porque qualquer simplesalteração no conjunto de restrições pode gerar uma decomposição completamente distinta.

Esta biblioteca é relativamente nova, havendo pouca documentação sobre ela. Para além disso, pouco sesabe sobre a escalabilidade dos seus algoritmos e não é mencionado nenhuma vez o problema da robus-tez e exatidão dos resultados. Requer ainda que o utilizador já tenha conhecimentos de programação eque compreenda a decomposição do problema em árvore.

Figura 2.3: Plataforma GeoSolver - Decomposição em árvore do problema e respectiva solução. Imagemretirada de [7] (Maio de 2015).

14

TikZ

É uma linguagem usada para produzir figuras vetoriais num espaço bidimensional, através de descri-ções geométricas e algébricas. Os programas de TikZ são escritos em LATEX2 com uma sintaxe especial,invocando macros de TEX3. O TikZ fornece uma sintaxe facilmente extensível com um elevado nível deabstração, enquanto a sua linguagem companheira, PGF4, fornece uma sintaxe de baixo nível. Estas eas restantes informações foram baseadas no manual “TikZ & PGF: Manual for version 2.10” [5].

Código 2.3: Código TikZ usado para gerar a Figura 1.1.1 \begin{tikzpicture}

2 \coordinate [label=below:A] (a) at (5,3);

3 \node [circle ,draw] (c) at (2,2) [minimum size =90pt] {$C$};

4 \coordinate [label=below:T] (t) at (tangent cs:node=c,point ={(a)},solution =2);

5 \draw (a) -- (t);

6 \draw (c.center) -- (a);

7 \coordinate [label=below:M] (m) at ($(a)!(t)!(c)$);

8 \draw (t) -- (m);

9 \end{tikzpicture}

A primeira figura do documento (Figura 2.4), é uma possível solução ao exemplo inicial e foi geradaa partir do código 2.3. Embora as coordenadas exatas dos pontos e o raio da circunferência sejamdesconhecidas na especificação do exemplo inicial, estas têm que ser especificadas nos programas deTikZ, porque as restrições do modelo em TikZ têm que estar totalmente restringidas (DoF do tipo well-constrained), ou seja, só pode haver uma solução possível. Por isso, nas linhas 2 e 3 do código é definidoo valor do raio e a localização dos pontos. Para criar a reta TM (perpendicular à reta AC que passapor T), o ponto M é calculado usando a sintaxe “($(A)!(T)!(C)$)” (linha 7 do código), que descreve oponto T projetado na reta que passa nos pontos A e C. Para fazer a tangente, o TikZ tem um sistemade coordenadas chamado “tangent” (linha 4 do código), que permite a computação do ponto tangenteatravés da seguinte sintaxe: <node><point><number>. O campo “node” é o objeto geométrico ondequeremos criar a tangente. O campo “point” é o ponto por onde a tangente deve passar. Finalmente, ocampo “number” é a solução que queremos escolher. Uma vez que existem duas soluções de tangentesà circunferência que passa pelo ponto, é necessário escolher uma em concreto. O critério de ordenaçãousado por omissão é a ordem pela qual estas são encontradas pelo algoritmo utilizado, sendo pouco útilquando pretendemos escolher uma solução em particular, contudo existem operações que permitemordenar as soluções encontradas.

A

C

T

M

Figura 2.4: Modelação por construção geométrica. A figura satisfaz as especificações/restrições descri-tas no Exemplo 1.

O TikZ permite ao utilizador definir novos sistemas de coordenadas para satisfazer as suas necessidades,usando o PGF como outras bibliotecas de matemática/cálculo. Pensar na tangente como um sistema de

2LATEX é uma linguagem de marcação (markup language) constituída por um conjunto de macros de TEX, que visa reduzir atarefa do utilizador para a escrita do conteúdo, LATEX cuidar de todo o processo de formatação.

3TEX - é um sistema de tipografia criado por Donald Knuth em 1978, considerado atualmente um dos sistemas de digitaçãodigital mais sofisticados do mundo.

4PGF (portable graphics format) é a camada que fornece um conjunto de comandos básicos para a produção de gráficos.

15

coordenadas é interessante e permite ao utilizador selecionar a solução pretendida, caso exista mais queuma. No entanto, para os espaços tridimensionais, a seleção da solução tem de ser mais sofisticada. NoAutoCAD5 existe um conjunto de operações para selecionar pontos ‘interessantes’ (pontos de intersec-ções, pontos cardeais, pontos intermédios, pontos mais próximos e mais distantes, entre outros): estaseleção é efetuada no próprio modelo através da interface gráfica. Embora funcione bem para modelosbidimensionais, é complicado e confuso para modelos tridimensionais, devido a não existir uma relaçãode dimensão espacial de um para um entre o modelo tridimensional e o monitor e rato. Contudo, a ideiado sistema de coordenadas podia ser aplicado no espaço tridimensionais. Por exemplo, imaginando quequeremos a tangente entre uma esfera e um ponto, mas existem infinitas soluções. Podemos então pen-sar nas soluções como sendo a superfície lateral de um cone, que contem a esfera e cujo vértice do coneé o ponto onde passa a tangente. Assim, seleciona-se a tangente pretendida através de um ângulo, a sin-taxe será semelhante à do TikZ com a diferença de, em vez de ser um número para selecionar a solução,seria um ângulo.

Sistemas de Computação Matemática

As ferramentas para resolução de problemas matemáticos, podem ser usadas para resolver os CSP, umavez que estes podem ser transformados em sistemas de equações. Por isso, analisámos várias ferramen-tas que podem ser usadas para resolver os CSP. Estamos interessados em sistemas com a capacidadede computação algébrica para resolver os sistemas de equações que descrevem os CSP, e nas capaci-dades de manipulação simbólica, para que a resolução desses sistemas de equações seja feita de formasimbólica para garantir a exatidão dos resultados, evitando assim problemas de arredondamentos.

Para além da computação algébrica e manipulação simbólica, pode ser interessante para o tema destetrabalho usufruir de funcionalidades específicas de alguns ramos da matemática, que podem ser úteispara descrever os modelos geométricos, tais como: álgebra geométrica, álgebra comutativa, matemáticadiscreta, teoria de grupos, entre outros.

Existe uma grande variedade de sistemas de cálculo matemático. A tabela 2.3 apresenta alguns dos maisinteressantes para o tema, baseado: nas capacidades de resolução, nos ramos da matemática em que sefocam, e em termos de comunidade e suporte. Contudo muitas das ferramentas especializam-se apenasem certos ramos da matemática, com algoritmos eficientes e poderosos para resolver esses problemas,mas depois são incompletos noutros ramos. Algumas das ferramentas de cálculo são de propósito geral,cobrindo um vasto espectro dos ramos da matemática, incluindo computação algébrica e manipulaçãosimbólica. O Axiom, o Maxima, o Mathematica e o Yacas são algumas destas ferramentas.

Existe ainda software especializado exclusivamente para escolher o melhor ramo/grupo de algoritmospara resolver determinados problemas. O CPLEX [21] destaca-se nesta área: este software é uma fer-ramenta poderosa da IBM para fazer a otimização de problemas matemáticos, escolhendo a melhorabordagem para os resolver.

5AutoCAD é um software assistido por computador (CAD) 2D e 3D e é usado em uma ampla gama de indústrias, por arquite-tos, gerentes de projeto, engenheiros, designers gráficos e outros profissionais.

16

Tabela 2.3: Ferramentas de Cálculo Matemático.

Ferramentas Principais CaracterísticasAxiom álgebra de propósito geral; fortemente tipificadoGAP álgebra discreta; teoria grupo computacional; análise combinatória

Jasymca computação simbólica; computação algébricaREDUCE cálculos algébricos gerais

SINGULAR álgebra comutativa; computações polinomiais; geometria algébricaYacas álgebra computacional; precisão arbitrária; manipulação simbólica

Maxima manipulação simbólica; matemática geralMathematica computação matemática simbólica; matemática geral

Sage álgebra; análise combinatória; matemática numérica; teoria dos númerosAxiom - http://axiom-developer.org/GAP - http://www.gap-system.org/Jasymca - http://webuser.hs-furtwangen.de/~dersch/REDUCE - http://reduce-algebra.com/SINGULAR - http://www.singular.uni-kl.de/Yacas - http://yacas.sourceforge.net/Maxima - http://maxima.sourceforge.net/Mathematica - https://www.wolfram.com/mathematica/Sage - http://www.sagemath.org/

17

18

Capítulo 3

Arquitetura

É apresentado neste capítulo o sistema desenvolvido, o ConstraintGM, que é uma linguagem específicode domínio (DSL) área da geometria, que desenvolvemos para descrever e resolver problemas geomé-tricos através da especificação de restrições.

A solução consiste na criação de uma linguagem dedicada à resolução de problema geométricos, deforma a ajudar os seus utilizadores na criação de modelos geométricos, especificando relações entreentidades geométricas que restringem o espaço geométrico das mesmas, com o propósito de expandiras funcionalidades da ferramenta Rosetta.

A linguagem é específica ao domínio da modelação geométrica e permite especificar declarativamenterelações entre entidades geométricas que restringem o modelo geométrico. Estas descrições são depoisanalisadas e o solver mais adequado é escolhido para as resolver de forma a que o modelo geométricocumpra todas as restrições. São então determinados valores concretos para as variáveis não inicialmenteconhecidas, conforme as propriedades que se pretender obter, como a localização, orientação, tamanho.

Criámos dois solvers como abordagens distintas para resolver as restrições:

• Biblioteca de Funções Geométricas - Esta abordagem é usada pela maioria das ferramentas anali-sadas e consiste em funções específicas para resolver determinados tipos de cenários.

• Núcleo de Cálculo Matemático - Esta abordagem consiste em converter o problema geométricopara um problema matemático e resolve-lo usando métodos analíticos.

Durante a análise efetuada às linguagens e ferramentas existentes para modelação geométrica, repará-mos que estas disponibilizam algumas capacidades de expansão, dentro de certos termos, como porexemplo a adição de funções para resolver problemas geométricos específicos. Reparámos ainda quea comunidade partilhava essas extensões para resolver problemas geométricos específicos. Por exem-plo, a comunidade do AutoLisp partilha o código, existindo muitas bibliotecas; o TiKZ permite até criarnovos sistemas de coordenadas; no Grasshopper para além dos exemplos do código (visual) partilha-dos entre os utilizador, ainda existem dois componentes para programação que permitem implementarnovas funções usando as linguagens de programação VB, C#, entre outras.

Por isso, a linguagem foi pensada para dois tipos de utilizadores, aos quais chamamos utilizadores finaise utilizadores avançados. Ao longo do documento referimo-nos a esses utilizadores:

19

• O utilizador final é aquele que apenas pretende usar a funcionalidade disponível para resolver pro-blemas geométricos. A funcionalidade disponível não só inclui a funcionalidade base da solução,implementada por nós, como também a funcionalidade implementada por terceiros (utilizadoresavançados).

• O utilizador avançado é aquele que pretende expandir e adaptar a linguagem às suas necessidades.

Assim, a linguagem foi desenhada com uma arquitetura modular, pensada para ser facilmente expan-dida em termos de:

• Entidades geométricas.

• Funções geométricas, especializadas em resolver cenários específicos.

• Integração com outras bibliotecas e ferramentas que disponibilizam as suas funções geométricas.

• Especificação de relações entre entidades geométricas.

Tiramos partido das capacidades de meta programação do Racket para criar essa arquitetura modu-lar. Assim o código implementado, que suporta a linguagem, é executado em fases distintas (fase degeração de código e fase de execução). Por isso, criámos assim macros para ajudar a expandir o domí-nio da linguagem, escrevendo código que é executado nessas fases distintas. As macros servem aindapara integrar os diferentes módulos da arquitetura e uniformizá-la, garantindo que as extensões respei-tam a arquitetura de todo o sistema e funcionam corretamente com outras extensões. Isto não limita outilizador na adição de funcionalidades fora dos âmbitos acima referidos, mas a responsabilidade deintegrar com a arquitetura atual da solução deixa de ser garantida de forma automática, enquanto asmacros criadas mantinham essa responsabilidade para os âmbitos acima referidos, os quais achamosmais importantes e interessantes para adicionar funcionalidade.

No capítulo anterior tínhamos uma secção dedicada ao problema de satisfação de restrições (CSP). Umavez que assentamos parte da nossa solução sobre um NCM, não tivemos a necessidade de implementaro nosso próprio sistema de satisfação de restrições.

A organização dos módulos da arquitetura é apresentado na Figura 3.1.

Entidade Geométrica

Esta secção apresenta algumas das entidades geométricas e as suas propriedades, que estão atualmentedisponíveis na linguagem. A maioria das entidades são formas geométricas clássicas de uma, duas outrês dimensões. O utilizador final pode usar estas entidades para descrever o seu cenário geométrico.Para além das formas geométricas clássicas, existem outras entidades que o utilizador final não necessitade conhecer. Por exemplo, a entidade form, constituída por um conjunto de variáveis, é usada pararepresentar um espaço geométrico, que pode variar desde o vazio até todo o espaço. No código, o termoentity refere-se a uma entidade geométrica.

Exemplos de formas geométricas:

• zero dimensões: ponto (point);

• uma dimensão: linha (line);

• duas dimensões (superfície): círculo (circle);

20

ConstraintGM

Core EntidadesGeométricas

Biblioteca de FunçõesGeométricas

Núcleo de CálculoMatemático

dispatcher

dispatcher-benchmark

entities-declaration

instantiating

main-constraints

entity-macro-utils

entity-macro

circle

constraints

form

line

point

sphere

value

var

geometric-functions-lib

intersections-2d-lib

utilities-2d-lib

utilities-3d-lib

communication

entities-properties

geometric-restrictions

mathProblem-utilities

mathProblem-structure

mathematical-symbols

property

Figura 3.1: Organização dos módulos

• três dimensões (sólido): esfera (sphere);

Embora existam formas geométricas que representam espaços geométricos tridimensionais, bidimensi-onais e unidimensionais, as instâncias destas entidades são sempre representadas num espaço tridimen-sional.

Existem ainda outras três entidades que o utilizador final não necessita de conhecer: value, var econstraints. Estas são exceções, não representando um espaço geométrico concreto. São usadas paracriar limitações no espaço geométrico das outras entidades. A entidade value é usada para definir valo-res nas propriedades das outras entidades. As instâncias de value podem ter o valor por definir, destaforma representa qualquer valor real “(−∞;+∞)”. As entidades geométricas podem partilhar a mesmainstância de value. A entidade constraints é usada para definir restrições nas outras entidades. Porexemplo, cortar uma esfera ao meio, limitar uma linha ao primeiro quadrante, restringir variáveis. Nocódigo 3.1, definimos uma variável e limitamos o intervalo de valores possíveis a um número positivo“[0,+∞)”, podendo ser usado para acrescentar lógica à propriedade raio de uma esfera.

Código 3.1: Definição da variável raio.

1 (define raio (new -constraints (~a (entity -id (new -value)) ">0")))

A entidade var é uma junção e evolução das entidades value e constraints, foi criada com o objetivode as substituir. As instâncias de var podem depender umas das outras, sendo a sua relação expressapor expressões matemáticas. Contudo, algumas funcionalidades da entidade var, ainda estão a serimplementadas, funcionando neste momento apenas como suporte para a entidade form. Na secção 3.3explicamos com mais detalhe a utilidade destas entidades geométricas e a sua evolução.

A estrutura mathProblem, representada no código 3.2, permite guardar a informação sobre o problemamatemático, que descreve o modelo geométrico. O mathProblem começa no estado ‘por resolver’, onde é

21

possível adicionar descrições das entidades e restrições através da função mathProblem-add-property.A função mathProblem-solve passa o mathProblem ao estado ‘resolvido’, onde só é possível obter infor-mação da estrutura, incluindo a solução do problema matemático. As responsabilidades do mathProblem

passam por: gerar as equações matemáticas corretamente; saber quais as variáveis dependentes e inde-pendentes; limitar as soluções conforme as restrições (ex. uma variável que representa um raio nãopode ser negativa); fazer processamento (parsing) das soluções do sistema de cálculo; analisar todas asvariáveis dependentes; atualizar os valores das variáveis com as soluções obtidas.

Código 3.2: Estrutura ‘mathProblem’.

1 (struct mathProblem

2 (id entitiesProperty restrictions tmpEquation

3 solutionsMaxima idMaxima state)

4 #:auto -value 'uninitialized

5 #: transparent #: mutable)

67 (define (new -mathProblem

8 [entitiesProperty '()]

9 [restrictions '()]

10 [tmpEquation 'uninitialized]

11 [solutionsMaxima 'uninitialized]

12 [idMaxima 'uninitialized]

13 [state 'NEW])

14 (mathProblem (gensym 'mathID) entitiesProperty restrictions

15 tmpEquation solutionsMaxima idMaxima state))

Propriedades das Entidades Geométricas

Uma entidade geométrica contém propriedades que pode ser usado para descrever a entidade e relacionar-se com outras entidades. Algumas destas propriedades só fazem sentido na própria entidade ou numconjunto limitado, como o raio. Contudo, outras propriedades fazem sentido em categorias de enti-dades, como é o caso do volume na categoria dos sólidos, e ainda existem outras operações que sãouniversais, por exemplo, operações Translação, Rotação e Escala.

Por exemplo, o utilizador pode desejar descrever uma entidade da categoria sólido em termos do seuvolume, pode-se usar o conceito de volume para relacionar o raio com outras descrições da superfícieesférica. Com isto queremos dar ao utilizador a possibilidade de fazer descrições com intersecção desólidos, como por exemplo:

(intersection (sphere-space sphere1) (sphere-space sphere2))

Contudo, não foi possível disponibilizar este tipo de operações com sólidos porque os sistemas de cál-culo matemático não são capazes de lidar com inequações, como referido na secção 2.3.

A operação intersection (interseção) recebe como argumento um número arbitrário de entidades ecria um mathProblem. A operação sphere-surface devolve a equação que descreve a superfície daesfera, segundo a fórmula [(x − x0)

2 + (y− y0)2 + (z− z0)

2 = r2]. A operação sphere-space devolvea expressão matemática que descreve a própria esfera, segundo a fórmula [(x− x0)

2 + (y− y0)2 + (z−

z0)2 >= r2], que se traduz em inequações.

22

Entidade ‘value’

A entidade value é especial, o utilizador final não precisa de saber da existência desta entidade, nemo utilizador avançado necessita de compreender o seu funcionamento. A entidade é utilizada interna-mente pelo código gerado durante a expansão das macros de forma a abstrair as variáveis do NCM. Estaentidade é usada como estrutura para guardar valores, cada instância representa um valor, que pode es-tar inicialmente indefinido. Se a instância de value tiver o valor indefinido, esta é representada pelo seusímbolo único como uma variável no sistema de computação algébrica e manipulação simbólica. Todasas instâncias de entity contêm um símbolo único, que é gerado automaticamente na sua criação. Aentidade value está implementada com seguinte código:

Código 3.3: Estrutura da entidade ‘value’.

1 (entity -type value

2 ([v any 'unset]))

3 ...

4 (entity -build value)

Durante o tempo de expansão e, em particular entre as chamadas às macros entity-type e entity-buildpodem ser redefinidos os objetos das estruturas auxiliares usadas por estas mesmas macros. Tal rede-finição tem efeitos no código gerado. Estas alterações afetam qualquer entidade criada/expandida nofuturo que utilize o tipo value. A estrutura value não existe durante o tempo de expansão, esta vai sercriada em tempo de execução pelo código gerado durante a expansão de entity-build. Estas alteraçõesafetam:

• As funções genéricas das entidades flat-values e update-values que são avaliadas de formaespecial;

• A geração de funções, cria mais duas funções usadas para aceder ao campo ‘v’, as funções value-se value-n. Enquanto value-v devolve o conteúdo do campo ‘v’, value-s devolve esse conteúdono formato de string, e value-n devolve em formato numérico de Racket.

• A função que valida o tipo durante a criação das entidades aceita também uma string ou um valornumérico de Racket, devolvendo uma entidade value. Desta forma, qualquer outra entidade queesteja à espera da entidade value pode receber uma instância da entidade value ou qualquer outroobjecto que seja válido na criação do value.

Entidade ‘point’

A entidade point representa um ponto ou uma localização no espaço tridimensional. A entidade pointestá implementada com o seguinte código:

Código 3.4: Estrutura da entidade ‘point’.

1 (entity -type point

2 ([x value]

3 [y value]

4 [z value 0]))

5 ...

6 (entity -build point)

23

Na secção 3.4.4 explicado em mais ditame o funcionamento das macros. Depois da descrição da enti-dade geométrica point através das macros, uma instância da entidade pode ser criada através da funçãonew-point. Esta função recebe três parâmetros, que representam as coordenadas ‘x’, ‘y’ e ‘z’ respetiva-mente; por omissão o valor da coordenada ‘z’ é 0. Existe ainda um construtor extra, que permite criarinstâncias da entidade com todos os campos ainda por definir, chamado new-point-unset, que é açúcarsintático para “(new-point (new-value) (new-value) (new-value))”.

Entidade ‘line’

A entidade line representa uma reta no espaço geométrico, pode também representar uma semirretaou um segmento de reta. A entidade line está implementada com o seguinte código:

Código 3.5: Estrutura da entidade ‘line’.

1 (entity -type line

2 ([start point (new -point 0 0)]

3 [end point (new -point 1 0)]

4 [direction point 'unset]

5 [length value 'unset]

6 [subtype symbol 'straight ]))

7 (entity -build line)

A maneira mais típica para definir uma reta é utilizando dois pontos não coincidentes que pertençam àreta. Embora seja igualmente válido indicar um ponto, um vetor de direção e um comprimento caso setrate de um segmento de reta.

A entidade line permite representar tipos de linha reta através do seu campo subtype, através dossímbolos: straight, semistraight e segment, que representam respetivamente, a reta, a semirreta e osegmento de reta, das quais dependem as equações matemáticas geradas. Por exemplo, numa interseçãocom uma reta, existe uma variável matemática, que relaciona os pontos start e end com a interseção. Essavariável é ‘0’ se a interseção for o ponto start e é ‘1’ se for o ponto end. Desta forma, filtramos as soluçõescom base nessa variável, se for um segmento de reta, o seu valor tem que estar contido entre ‘0’ e ‘1’, nocaso de uma semirreta, a variável tem que ser maior que zero;

Como trabalho futuro queremos expandir a funcionalidade da macro entity-type para que esta per-mita:

• obrigar os pontos, campo start e end a não serem coincidentes;

• limitar o campo subtype a um conjunto de símbolos (straight, semistraight, segment);

• definir, logo à partida, que o campo length tem que ter um valor positivo.

Por outras palavras, pretendemos durante o tempo de expansão, gerar código que valide essas con-dições (relações entre as propriedades das entidades). Por exemplo, na macro entity-type pode seradicionado um parâmetro com a keywork conditions, que recebe durante a descrição da entidade ge-ométrica uma lista de relações matemáticas entre as propriedades, essas relações são validades sempreuma das propriedades condicionadas é modificada. Mais concretamente no código 3.5, as propriedadesstart e end estariam relacionadas com a propriedade direction, assim como a propriedade length nocaso de subtype for “segment”.

24

Entidade ‘circle’

A entidade circle representa um círculo no espaço tridimensional. A entidade circle está implemen-tada com o seguinte código:

Código 3.6: Estrutura da entidade ‘circle’.

1 (entity -type circle

2 ([ center point (new -point 0 0)]

3 [radius value 1]

4 #;[ normal vector (new -vector 0 0 1)]))

5 (entity -build circle)

Falta implementar a parte correspondente ao vetor normal, neste momento todos os círculos estão noplano ‘xy’ ou num plano paralelo.

Entidade ‘sphere’

A entidade sphere representa um esfera no espaço tridimensional. A entidade sphere está implemen-tada com o seguinte código:

Código 3.7: Estrutura da entidade ‘sphere’.

1 (entity -type sphere

2 ([ center point (new -point 0 0 0)]

3 [radius value 1]))

4 (entity -build sphere)

Biblioteca de Funções Geométricas

Nesta secção vamos analisar a Biblioteca de Funções Geométricas (BFG). A biblioteca tem como obje-tivo implementar funções que permitem resolver restrições geométricas para cenários comuns de formaeficaz e eficiente. Esta biblioteca segue a lógica das restantes ferramentas existentes no mercado, imple-mentando algoritmos especializados em resolver cada uma das restrições geométricas.

Na linguagem desenvolvida, os problemas geométricos são abordados de forma genérica, recorrendo asistemas de computação algébrica e manipulação simbólica para resolver os sistemas de equações querepresentam as restrições do modelo geométrico. Dedicámos a maior parte do esforço de implementa-ção nesta abordagem mais genérica através do Núcleo de Cálculo Matemático (NCM). Esta bibliotecaserve só para demonstrar as vantagens e desvantagens em relação à solução genérica, e como as duasabordagens podem-se complementar.

Verificámos que nos repositórios de ‘packages’ de Racket, não existem bibliotecas que implementem nati-vamente funções que permitem trabalhar com restrições geométricas. Uma solução válida seria integrarcom bibliotecas nativas de outras linguagens, usando módulos que permitem integrar linguagens noRacket. Por exemplo, “Python for DrRacket” [22] e “P2R - Processing to Racket” [23] são exemplosdestes módulos, que permite usar respetivamente ‘packages’ de Python e Processing em Racket.

25

Uma ferramenta que seria interessante integrar com a nossa BFG seria a biblioteca CGAL [16, 24, 15].Esta biblioteca é um projeto implementado em C++, que fornece algoritmos geométricos eficientes eviáveis em termos de obter resultados teoricamente corretos. O CGAL é usado em várias áreas quenecessitam de cálculo geométrico, tais como: computação gráfica, desenho assistido por computador,biologia molecular, entre outras.

Contudo, a solução seguida para criar BFG foi implementar à mão, na linguagem Racket, os algoritmosgeométricos. Os algoritmos implementados foram escolhidos conforme as necessidades para resolveros casos de uso.

A BFG é composto por cinco módulos, quatro dos quais localizados na diretoria “function-module”:

• “utilities-2d-lib”

• “utilities-3d-lib”

• “intersections-2d-lib”

• “geometric-functions-lib”

Estes são totalmente independentes do resto do sistema, ou seja, nenhuma das funções utiliza as estru-turas implementadas de outros módulos.

Todas as funções da biblioteca, estão disponíveis no módulo “geometric-functions-lib”. Contudo, cadafunção espera o seu conjunto particular de parâmetro e formato do resultado. Desta forma, criamosa macro mask para facilitar a integração com os restantes módulos e estruturas de dados. A macromask permite definir que os parâmetros que cada função recebe e como são extraídas automaticamentedas entidades geométricas. Para além disso, também é definido como são tratados os resultados dasfunções. Esta parte do código está implementada no módulo “functions-mask” da diretoria “core”,cujas funcionalidades já dependem do resto da arquitetura, em particular, das entidades geométricas.

Os módulos “utilities-2d-lib” e “utilities-3d-lib” disponibilizam funções úteis para os utilizadores im-plementarem outras funções. São usadas pelas funções do módulo “intersections-2d-lib”.

No módulo “intersections-2d-lib” existem três algoritmos para cálculo de intersecção, especializadospara resolver a interseção entre: duas linhas, duas circunferências, ou uma circunferência e uma linha.

Cada algoritmo disponibiliza ainda um conjunto de primitivas para ajudar o utilizador a tratar dos casosespeciais. Por exemplo, na interseção entre duas circunferências, existem as seguintes primitivas: saberse existe alguma interseção (intersects-circle-circle?); saber se as circunferências são tangentes(tangent-circle-circle?); calcular o ponto de interseção entre círculos tangentes (caso os círculos nãosejam tangentes a função reporta um erro) (tangent-circle-circle); calcular as interseções e, casonão existam, a função reporta um erro (intersections-circle-circle); existem ainda outras funçõesauxiliares.

Estas primitivas foram implementadas no início do trabalho, tendo como objetivo ajudar o utilizadorfinal, facilitando a escrita do código. O utilizador, ao usar a função adequada, deixa de precisar de efe-tuar verificações adicionais ao resultado, uma vez que a função mais abrangente dos algoritmos temvários resultados possíveis. Por exemplo, o utilizador quer modelar um determinado cenário, a interse-ção de duas circunferências, contudo o modelo só faz sentido se as circunferências forem tangentes. Aousar a função tangent-circle-circle o utilizador já estará a validar que as duas circunferências sãotangentes e não é necessário escrever código adicional para tornar o programa robusto.

26

Embora estas primitivas estejam disponíveis ao utilizador final, a função intersection-dispatcher,explicada na secção 3.6, apenas usa a função mais abrangente dos algoritmos, definida pela macro mask.

• Algoritmo de interseção entre duas retas: O algoritmo para calcular a interseção entre duas retasé baseado na pagina web Wolfram [25] e no artigo [26].

• Algoritmo de interseção entre circunferência e reta: O algoritmo para calcular a interseção entreum reta e uma circunferência é baseado na pagina web Wolfram [27] e no artigo [28].

• Algoritmo de interseção entre duas circunferências: O algoritmo para calcular a interseção entreduas circunferências é baseado no artigo [29].

Sumário

O utilizador que pretenda utilizar apenas a biblioteca de funções geométricas, pode simplesmente im-portar o módulo “geometric-functions-lib”. Este contém todas as funções da biblioteca e depende ape-nas dos módulos da diretoria “function-module”, sendo totalmente independentes das estruturas quesuportam as entidades geométricas. O utilizador pode expandir facilmente estas bibliotecas, criandonovos algoritmos ou integrando com outras bibliotecas já implementadas, com a ajuda da macro mask.Esta macro ajuda a encapsular a função, disponibilizando uma função de alto nível com meta informa-ção sobre como suportar as entidades geométricas.

Comunicação do Núcleo de Cálculo Matemático

Nesta secção é analisado o modo como a comunicação é efetuada com o NCM, e como os resultados sãorefletidos de volta ao modelo geométrico. O Maxima foi escolhido como sistema de cálculo matemáticousado pelo NCM. Este sistema destacou-se dos restantes por ser principalmente por ser um projeto opensource e estar implementado em Common Lisp, uma linguagem com a mesma descendência do Racket,o que nos permitiu tirar partido para implementar a comunicação.

As capacidades de resolução disponibilizadas pelo NCM evitaram a implementação de algoritmos deresolução CSP. A forma implementada para resolver os CSP, descritos nos modelos geométricos, centra-se na conversão da descrição do modelo num problema matemático, sendo posteriormente resolvido porum NCM.

Figura 3.2: Fluxo de informação Núcleo de Cálculo Matemático.

27

A Figura 3.2 representa o fluxo de informação NCM. Assim que o problema geométrico é passado aoNCM a informação é recolhida do conjunto das entidades geométricas envolvidas (diretamente e indi-retamente) e das relações entre elas. A informação é analisada e são geradas equações que descrever omodelo geométrico, estas são depois passadas ao sistema de cálculo matemático, depois os resultadossão processados e as entidades são atualizadas com as propriedades deduzidas.

A gama de problemas geométricos solúveis é atualmente limitada pela capacidade dos NCM a resol-ver inequações, por exemplo, a interseção entre sólidos em que o resultado é um sólido. Existem noMaxima algumas extensões que permitem trabalhar com inequações e que poderiam ser usadas paracomplementar a gama de problema geométricos solúveis. Uma das extensões que testámos permiteresolver apenas inequações lineares. A segunda extensão experimentada permite ‘resolver’ inequaçõescom base na teoria de conjuntos. Contudo, as capacidades de resolução são limitadas e as soluçõescontêm frequentemente inequações que podem ser simplificadas. Por outro lado, a utilização destas ex-tensões específicas do Maxima dificultaria a integração futura com outros NCM, desta forma decidimosnão tirar partido destas funcionalidades.

Os módulos implementados para fins de comunicação com o Maxima, analisados nesta secção podemser usados independentemente do resto do sistema. Estes módulos disponibilizam as funcionalidadesdo Maxima na linguagem Racket, e foram testados em sistemas operativos Windows e Ubuntu, maisconcretamente nas verções Windoes 7, 8.1 e 10 e no Ubuntu 14.04.

O código correspondente à comunicação com Maxima pode ser dividido nas seguintes etapas:

• Inicializar

• Criação de canais de comunicação

• Configuração

• Geração das mensagens

• Envio e receção de mensagem (em diferentes modos)

• Parsing dos resultados.

Inicialização do Maxima

É necessário inicializar o Maxima, criar os túneis (socket) para comunicação e configurar o NCM. Paraeste efeito o utilizador final tem à sua disposição a função start-maxima. A função recebe opcional-mente dois argumentos através das keywords: path e port. A keyword path permite especificar a loca-lização do programa Maxima, em caso de omissão questionamos o sistema operativo pela localizaçãodo programa, funciona para Windows e Unix (linhas 2-8 do código 3.8). A keyword port permite espe-cificar o port que é usado para a comunicação, em caso de omissão o port 8080 é usado se não estiverocupado, se estiver disposta um erro. No futuro podemos, simplesmente procurar um port que estejadisponível.

O Maxima é depois inicializado na função start-maxima-execute, o parâmetro “�very-quiet” é pas-sado como argumento, reduzindo assim a mensagem de boas vindas a um número que indica a versãodo Maxima. O processamento da mensagem das boas vindas é especial, uma vez que, a estrutura damensagem difere de todas as outras, e este parâmetro simplifica a mensagem. São criados três canaisde comunicação, estes são do tipo parameter acessíveis no resto do código. Os canais socket-out e

28

socket-in são usados respetivamente para enviar e receber mensagens, o socket-err é o canal parareceber mensagens de erro, mas por norma o Maxima envia para seu standard output, ou seja, as mensa-gens de erro são enviadas para o canal socket-in e têm de ser tratadas.

Código 3.8: Função para inicializar o Maxima.

1 (define (start -maxima

2 #:path [path (find -executable -path

3 (case (system -type 'os)

4 [(unix) "maxima "]

5 [( windows) "maxima.bat"]

6 [else "maxima "]))]

7 #:port [port 8080])

8 (current -maxima -path path)

9 (current -maxima -port port)

10 (start -maxima -execute)

11 (send/receive -maxima null 'starting -maxima)

12 (maxima -configuration))

Por último, configura-se o Maxima, de forma a facilitar o parsing das mensagens e filtar mensagens dealerta inesperadas, com os seguintes parâmetros do Maxima:

• "display2d:false" - Obrigando a que seja expresso num formato unidimensional, ou seja, numasequência de carateres. Por padrão, o Maxima tem noção do tamanho da janela de output e formataos resultados para ser facilmente legível para um humano;

• "ratprint:false" - Evita as mensagem de aviso, quando passamos ao Maxima números deci-mais, e este converte-os para frações (ex: “rat: replaced -2.25 by -9/4 = -2.25”);

• "linsolvewarn:false" - Evita a mensagem de aviso, quando existe um conjunto de equaçõesredundantes (ex: “Dependent equations eliminated”);

• "linel:1000" - Evita que as mensagens do Maxima tenham muitos carateres new-line;

• "realonly:true" - Evita soluções com números complexos;

• "radexpand:all" - Obriga a que as expressões sejam apresentadas de forma expandida, obrigandoa que iguais sejam expressas da mesma forma.

Canal de Comunicação e Formatação de Mensagens

Para além da linguagem matemática do Maxima, existe forma de chamar diretamente funções Lisp doMaxima, e de aceder a linguagem interna ao sistema de símbolos matemáticos.

• send/receive-maxima - Enviar e receber dados dos canais de comunicação, usando o protocoloTCP. É uma função de baixo nível, usadas chamadas primitivas do Racket, sendo depois usadaspelas restantes funções de comunicação.

• send/receive-maxima-mathematica - Envia e recebe mensagens usando a linguagem matemáticado Maxima;

• send/noreceive-maxima-mathematica - Semelhante à função send/receive-maxima-mathematica,mas o Maxima não envia os resultados.

29

• send/receive-maxima-lisp - Permite aceder a linguagem base do Maxima, as mensagens envia-das e recebidas estão na sintaxe de Common Lisp;

• send/receive-maxima-lispMathematica - Envia mensagens usando a linguagem matemática doMaxima, mas as mensagens recebidas usam a linguagem simbólica, interna ao Maxima.

• send/receive-maxima-display - Converte a linguagem de símbolos interna ao Maxima em ex-pressões matemáticas facilmente legíveis por humanos.

Na tabela 3.1, é apresentada a formatação para criar os efeitos mencionados acima. É ainda adicionado oseguinte pedido a cada chamada “:lisp $linenum n”, que devolve uma referência para a última ope-ração realizada no Maxima, para evitar um bug existente. O Maxima não garante que a sua mensagemseja totalmente entregue no canal de comunicação, este comportamento varia de sistema operativo parasistema operativo. Para ultrapassar o problema fazemos uma nova e simples chamada para garantirque a mensagem anterior é totalmente entregue. Isto permite ainda verificar que a chamada foi cor-retamente executada e que não existem erros no canal socket-in, porque sabemos exatamente qual oresultado esperado pela segunda chamada.

Tabela 3.1: Formatação das mensagens pelas funções de comunicação.Onde “∼a” é substituído pelo argumento da função de comunicação (string), e “∼n” é substituído pelocaractere new-line.

Nome da função de comunicação Formatação da mensagemsend/receive-maxima-mathematica “∼a;∼n”send/noreceive-maxima-mathematica “∼a$∼n”send/receive-maxima-lisp “:lisp ∼a∼n”send/receive-maxima-lispMathematica “:lisp #$∼a$∼n”send/receive-maxima-display “:lisp (maxima-display `∼a)∼n”

Processamento de resultados do Maxima

O Maxima é invocado de cada vez que queremos resolver o problema matemático, e cada chamada temuma mensagem, que tem que ser interpretada, o seu significado processado, e os resultados refletidosno modelo geométrico.

As chamadas ao Maxima são feitas através da função send/receive-maxima-lispMathematica, ondeas expressões matemáticas nas mensagens vêm num formato simbólico semelhante a Lisp, mas internoao Maxima. A parte do parsing das mensagens tira proveito dessa sintaxe e a cada variável de cadasolução é extraída a expressão matemática nessa sintaxe interna, que depois, e conforme necessário, éconvertido para a sintaxe matemática do Maxima, usando a função send/receive-maxima-display.

Depois de extrair os resultados é necessário interpretar o seu significado a nível lógico e para esse efeitoforam criadas as entidades form e var.

A entidade form é composta por três instâncias de var, relacionadas entre si, que representam um espaçogeométrico. Esta é usada como uma entidade genérica, sendo muito útil para tratar de um espaçogeométrico que não sabemos, à partida, a forma.

Todas as entidades geométricas podem ser convertidas na entidade form. A conversão de form para asoutras entidades está apenas implementado algumas.

As entidades form e var foram criadas para ajudar a interpretar o significado das soluções do NCM.

30

Imagine que se pretende calcular a interseção entre duas entidades line, através do NCM, a abordagemingénua para interpretar os resultados seria tratar para cada um dos cenários geométricos possíveisindividualmente:

1. Suportar o caso habitual, ou seja, a expressão matemática que representa um ponto;

2. Suportar os casos extraordinários:

(a) Se as linhas não se cruzarem, então a expressão matemática é nula.

(b) Se as duas linhas forem retas coincidentes, então a expressão matemática é equivalente àprópria linha.

3. Suportar todos os outros casos especiais, onde as line não representam retas completas. Esta en-tidade pode representar: uma semirreta, um segmento de reta, e ainda secções numa reta. Destaforma, a solução, além de poder ser qualquer uma das soluções acima, ainda pode ser: um con-junto de pontos, secções da reta, entre outras.

Essa primeira abordagem não iria escalar em termos de funcionalidades e voltávamos a ter os mes-mos problemas que a abordagem clássica para resolver problemas geométricos (funções especializadaspara tipos de cenário geométricos). O problema é tratar individualmente todos os cenários possíveispara cada combinação de entidades e no mesmo espaço geométrico poder ser descrito por diferentesexpressões matemáticas.

A entidade form foi criada especialmente para agilizar o processo de interpretação de resultados doNCM. A solução encontrada torna o código mais robusto e como é um problema recorrente para qual-quer operação que envolva o NCM, torna o código reutilizável. Qualquer resultado do NCM começapor ser transformado numa instância de form, que depois é convertido noutra entidade, esta conversãosó é realizada se o conteúdo da entidade form representar a entidade para a qual está a ser convertida.Por exemplo, a função form->points converte instâncias de form para uma lista de point, se e só se,form representar o vazio ou pontos no espaço. O utilizador pode expandir esse conjunto de funções deconversão de entidade, conforme a sua necessidade.

Macros

Nesta secção são apresentadas as estruturas das entidades geométricas e a forma como estas são criadasautomaticamente pelas macros. Analisamos ainda a geração de código e as diferentes fases de execu-ção. A secção apresenta, ainda, as macros criadas e os cuidados que tivemos para tornar a linguagemfacilmente expansível.

Os pilares da linguagem de domínio específico assentam sobre as macros criadas, cuja sintaxe especí-fica é apresentada ao longo desta secção. As macros armazenam meta-informação sobre as entidadesgeométricas em estruturas auxiliares, que só existem durante a expansão do código. Deste modo, ameta-informação é usada para gerar as entidades e funções que as relacionam.

Toda a nossa implementação baseada em macros é inspirada no trabalho de Matthew Flatt, principal-mente em três dos seus artigos: [30]; [31]; [32].

31

Criação de Entidades Geométricas

Todas as entidades são criadas através das macros entity-type e entity-build, chamadas nesta sequên-cia. O código 3.9 exemplifica a utilização destas macros onde se define a entidade point, que representauma localização no espaço. Durante a implementação das macros tivemos em consideração: (i) permitira rastreabilidade do código quando este é gerado, (ii) refatorizar o código das macros à medida que maisfuncionalidades são adicionadas, e (iii) as macros aceitam múltiplas sintaxes evitando assim a criaçãode múltiplas macros semelhantes, ou seja, a mesma macro aceita varias combinações de parâmetros.Algumas das funcionalidades usadas para atingir esses objetivos estão descritas no artigo “Languagesas libraries” [33].

Código 3.9: Estrutura da entidade geométrica ‘point’.

1 (entity -type point

2 ([x value]

3 [y value]

4 [z value 0]))

5 (entity -build point)

A macro entity-type gera código para as duas fases distintas, fase 0 (tempo de execução) e a fase 1(tempo de expansão). O conceito de fases é conhecido em Racket como phases.

Na fase 0 é construída a estrutura mutável que guardará as instâncias de point “[(struct point

entity (x y z) #:transparent #:mutable)]”.

A fase 1 acrescenta à estrutura auxiliar ‘IDtable’ informação sobre a entidade que se pretende definir, deforma a partilhar essa meta-informação entre diferentes execuções. Esta lógica de programação atravésde macros está explicada no artigo [31]. Todas as estruturas de entidades geométricas são subestruturasda estrutura entity, que contendo apenas um campo id, é gerada automaticamente identificando ainstância de qualquer entidade. A macro entity-build gera código apenas para a fase 0. É nestamacro que todas as funções básicas das entidades são definidas. O código gerado tem o seguinte aspeto:“(begin ($define (op1 agrs1 ...) body1) ($define (op2 agrs2 ...) body2))”.

A macro $define difere apenas da função define simplesmente pela primeira chamar provide com afunção que se pretende definir, com o intuito de disponibilizar as funções nos restantes módulos. Arazão pela qual entity-type e entity-build são duas macros separadas é para que se possa redefiniras operações e definir novas conforme necessário. Estas operações são, por sua vez, usadas automatica-mente pelas entidades dependentes, tendo um impacto direto do código gerado nas funções definidas.

De seguida, definimos a sintaxe das macros e nas subsecções seguintes descrevemos as operações bási-cas definidas pelas macros entity-type e entity-build. A macro entity-type têm a seguinte sintaxe:“(entity-type name (field-type-default ...))”

• name — o identificador da entidade geométrica.

• field-type-default - o identificador e tipo dos campos da entidade, este parâmetro pode ser dotipo “(field-name field-type)” ou do tipo “(field-name field-type field-default)”.

– field-name — o identificador do campo.

– field-type — o identificador de uma entidade geométrica previamente definida ou, em al-ternativa, o símbolo any.

32

– field-default — um valor opcional usado por omissão no construtor desta entidade.

A macro entity-build usa a estrutura criada pela macro entity-build para expandir o código. Essecódigo corre em tempo de execução (fase 0), definindo todas as estruturas e funções disponibilizadas aoutilizador final. A macro entity-build têm a seguinte sintaxe: “(entity-build name)”, onde:

• name — o identificador da entidade previamente definida através de entity-type.

Funções Disponíveis

Encontra-se disponível, no anexo A, uma listagem das funções que são definidas de forma mecanizadapelas macros entity-type e entity-build. As funções listadas são apenas as que estão disponíveisos utilizadores (utilizador final e utilizador avançado). Existem outras funções geradas pelas macrosque estão apenas disponíveis internamente no sistema, e que são apenas usadas pelo código gerado porestas e outras macros.

Por exemplo, os construtores de instâncias das entidades geométricas validam os argumentos passados eem alguns casos até encasular os argumentos em estruturas. O encapsulamento ocorre quando o campoesperado é do tipo var e value, mas o argumento passado é uma string com uma expressão matemáticaou um número de Racket. Isto evita que o utilizador final tenha de saber da existência destas entidades.Mas existem outros construtores que, como forma de otimização, não fazem estas validações, e que estãoapenas disponíveis internamente, usadas pelo código gerado pelas várias macros.

Estrutura auxiliar das Macros

No módulo “entity-macro-utils” está definida a estrutura IDtable, responsável por guardar a meta-informação das entidades geométricas.

Sem estas estruturas, não seria possível partilhar meta-informação sobre a estrutura das entidades entrediferentes módulos, o que obrigaria que as entidades fossem definidas todas num mesmo módulo. Asprimeiras implementações da macro responsável por criar as entidades tinham este problema, o queimpedia a expansão da linguagem em módulos separados e limitava a partilha destas expansões entre osutilizadores. Adicionar uma nova entidade implicaria modificar o módulo das entidades. Revolvemosesse problema com a implementação atual das macros entity-type e entity-build.

Código 3.10: Estruturas auxiliares das macros entity-type e entity-build.

1 (define IDtable (make -free -id-table))

2 (struct \$ID (id description fields fieldsRef fieldsSet oldConstructor

3 newConstructor copyConstructor guard $\lambda$? provide)

4 \#: transparent \#: mutable)

5 (struct \$FIELD (name type order default $\lambda$ ref)

6 \#: transparent \#: mutable)

7 (struct \$FUNC (name call defined ?)

8 \#: transparent \#: mutable)

Caso estejamos a definir novas operações básicas ou a modificar as existentes, é importante compreendera estrutura da IDtable, em particular se for necessário usar ou partilhar meta-informação com outrasentidades geométricas. Quase todas as funções auxiliares desta estrutura são funções de ordem superior,

33

recebendo funções como argumentos que são depois usadas pela macro entity-build, alterando ocomportamento desta última.

Durante a fase 1, a macro entity-type expande o código. Na fase 0 é acrescentada a meta-informação naestrutura auxiliar. Esta meta-informação é depois usada pela macro entity-build que gera as entidadese funções durante a mesma fase.

Macros Higiénicas de Racket

Tal como documentado no artigo de Matthew Flatt [30], esta é a forma correcta de fazer com que umasmacros tenham efeitos sobre outras que correm em módulos separados, devido ao isolamento entrefases e entre módulos, também conhecida como macros higiénicas (hygienic macros), que está na baseda linguagem Racket.

Simplificando o princípio, que está na base partilha de informação durante a fase 1 e entre diferentesmódulos em Racket, suponha o seguinte cenário com quatro módulos:

• Módulo 1 — declara e exporta: (i) duas listas inicialmente vazias, uma existente durante a fase 1 eoutra durante a fase 0, (ii) uma macro que recebe um símbolo e ao expandir adiciona corretamenteo símbolo às listas e imprime-o no standard output durante a fase 1, no fim chama ainda a macrocom o símbolo ‘X’;

• Módulo 2 — importa o primeiro módulo e chama a macro com o símbolo ‘A’;

• Módulo 3 — importa o primeiro módulo e chama a macro com o símbolo ‘B’;

• Módulo 4 — importa os primeiros três módulos pela ordem em que foram apresentados.

Verifica-se o seguinte:

• a lista que existe durante a fase 1 contém os seguintes símbolos: ‘X’, ‘A’ e ‘B’. Estes símbolos sãoinseridos a medida que os módulos são importados pelo módulo 4. Ao importar o módulo 1, édefinido uma lista contendo o símbolo ‘X’, ao importar os módulos 2 e 3 são inseridos os símbolos‘A’ e ‘B’ na lista que só existe durante a fase 1.

• o output apresentado é “X X A X B” devido a:

– ‘X’ — o módulo 1 é importado pelo módulo 4;

– ‘X; A’ — o módulo 1 é importado pelo módulo 2, que, por sua vez, é importado no módulo 4;

– ‘X; B’ — o módulo 1 é importado pelo módulo 3, que, por sua vez, é importado no módulo 4;

• a lista que existe durante a fase 0 contém apenas o símbolo ‘X’, adicionado durante a execução docódigo expandido pelo módulo 1.

A razão pela qual as macros entity-type e entity-build estão separadas, é para que seja possível mo-dificar a meta-informação criando comportamentos específicos às entidades. Por exemplo, isto permitedefinir novas funções para aceder ao campo ‘v’ da entidade value/var com funcionalidade específica,mais concretamente as funções value-s/var-s devolve o campo V como uma expressão matemáticaque é depois passado ao sistema de cálculo matemático. Por outra palavras: (i) se o campo da estruturacontiver um valor do tipo número então este é convertido numa cadeira de carateres à qual chamámosexpressão matemática, (ii) se o campo contiver uma expressão matemática então esta é devolvida, (iii)

34

se o campo estiver indefinido então a expressão matemática devolvido é o símbolo único que representaa variável.

Geração das Equações Matemáticas

Nesta secção é analisada a representação matemática das entidades geométricas, o modo como são ge-radas as equações que descrevem as entidades geométricas e quais os aspetos a serem consideradosdurante a criação de novas entidades. As propriedades das entidades e as restrições entre elas são con-vertidas em expressões matemáticas. Desta forma, o modelo geométrico é transformado num problemamatemático. Posteriormente, estas expressões são transmitidas ao NCM para que resolva o problemacomputando as variáveis que não são diretamente definidas. Todo este processo é automático e o utili-zador final nunca precisará de se preocupar com o modelo matemático.

De seguida, são listadas as funções e estruturas dos modelos matemáticos, que os utilizadores podemusar para definir o seu modelo através de restrições. Estas funcionalidades criam internamente o pro-blema matemático que descreve o modelo geométrico.

• No módulo “entities-properties” estão definidas as seguintes funções:

– entity-form-equation

– point-form-equation

– right-angle-equation

– line-direction-vector-X/Y/Z

– line-form-equation

– line-deltas-equation

– line-slope-equation2d

– circle-form-equation

– circle-form-equation2d

– circle-tangentToPoint-equation2d

– sphere-form-equation

• No módulo “geometric-restrictions”: estão definidas as seguintes funções de alto nível:

– intersection

– parallel-line

– tangent-circles

– tangent-circle-line

– entity-surface-points

• Os módulos “mathProblem-structure” e “mathProblem-utilities” é onde está implementado a es-trutura ‘mathProblem’ e todas as funcionalidades nela integrados. Estes módulos são responsáveispor representar o modelo matemático, e usam o módulo de comunicação para fazer chamadas ao

35

NCM. O NCM resolve as restrições e calcula os valores pretendidos. A estrutura mathProblem jáfoi apresentada em parte na secção 3.1.

• O módulo “property” implementa a estrutura ‘property’. Esta estrutura representa as proprieda-des das entidades (ex. raio, superfície, volume), sendo usada por mathProblem.

• O módulo “mathematical-symbols” contém a lista de símbolos matemáticos disponibilizados, e arespetiva conversão para o NCM, por exemplo, os símbolos π ou pi, e (constante de Napier), entreoutros. Os utilizadores podem usar estes símbolos na definição de expressões matemáticas. Estemódulo serve para manter o código dos utilizadores independentes do NCM, uma vez que cadasistema tem os seus símbolos específicos.

Representação Matemática das Entidades Geométricas

Em secções anteriores foi referido que mathProblem descreve um problema matemático, que por suavez, representa um problema geométrico. Adicionalmente, existe um conjunto de funções que geraequações matemáticas para descrever partes do problema. Contudo, essa função não cria as equaçõesque são passadas ao NCM, em vez disso, cria instâncias da estrutura property. É esta estrutura quecontém a informação necessária para gerar as equações. As equações são geradas o mais tarde possível,quando se pretende efetivamente resolver o problema matemático. Essa resolução é efetuada através dafunção properties-equations que recebe uma lista com as instancias de property e devolve as equa-ções matemáticas codificadas por cadeias de caracteres. A partir desse momento o problema matemáticofica estático e não é possível adicionar novas instancias de property.

O motivo pelo qual definimos a arquitetura deste modo, é que, embora as property sejam auto-contidase consigam gerar, por si, conjuntos de equações, elas não são independentes umas das outras. Por exem-plo, evita a criação de equações repetidas, mantém informação das variáveis do sistema de equações ea sua origem. Por exemplo, a função properties-vars recebe uma lista com instâncias de property edevolve uma lista (com identificadores) de todas as variáveis por descobrir.

A estrutura property contém os seguintes campos: entity, equationFormat, equationFormatInput,vars, restrictions.

• Campo entity — indica a instância da entidade geométrica à qual a property se refere.

• Campo equationFormat — indica a formatação das equações que são geradas. É explicado emdetalhe nas subsecções seguintes.

• Campo equationFormatInput — é uma lista com funções que extraem a informação da própriaentidade de acordo com a formatação das equações. Atualmente, a informação extraída é pas-sada diretamente, mas, caso seja necessário aplicar operações sobre esses dados, é possível colocarfunções de ordem superior na lista.

• Campo vars — é uma lista de variáveis envolvidas no problema matemático.

• Campo restrictions — é uma lista de restrições matemáticas aplicadas às variáveis (ex. o raiode um círculo é um número positivo). Estas são usadas para filtrar as soluções do NCM. Estafuncionalidade serve para mitigar o problema de não ser possível definir as restrições atravésde inequações, filtrando apenas as soluções. Contudo, a não utilização de inequações torna aestrutura menos expressiva e por isso mais limitada.

36

Entidade ‘point’

A entidade point representa um ponto no espaço. A função (point-form-equation point form) per-mite gerar as equações matemáticas que relacionam as variáveis de ‘point’ com as de ‘form’. A relação édireta: os campos ‘x’, ‘y’ e ‘z’ da entidade ‘point’ correspondem respetivamente aos campos ‘x’, ‘y’ e‘z’da entidade ‘form’, desta forma são criadas três equações.

Entidade ‘sphere’

A função (sphere-form-equation sphere form) permite gerar as equações matemáticas, limitando ainstância da entidade form ao espaço geométrico da superfície esférica, com a seguinte equação:

(x− a)2 + (y− b)2 + (z− c) = r2

Onde x, y e z são as variáveis da entidade form, a, b, e c as variáveis que representam o centro do círculo,e r o raio do círculo. É aplicado o filtro r > 0 às soluções eliminando as soluções de raio negativo.

Entidade ‘circle’

A função (circle-form-equation2d circle form) permite gerar as equações matemáticas que limi-tam a entidade form ao espaço geométrico da circunferência do círculo com as seguintes equações:

(x− a)2 + (y− b)2 = r2

z = c

Estas variáveis têm o mesmo significado que as variáveis da esfera, descritas acima. Existe também umfiltro que limita às soluções de raio positivo.

Como referido da subsecção 3.1.5, a descrição da entidade círculo está atualmente limitada ao plano‘xy’ ou paralelo a este, faltando implementar o vetor normal de modo a permitir a definição do planoque inscreve o círculo. Quando esta funcionalidade for implementada, será necessário criar a funçãocircle-form-equation, que permita descrever a circunferência inscrita noutros planos. Uma possí-vel solução para descrever o problema matemático seria combinar as equações resultantes da funçãosphere-form-equation com equações que descrevam o plano em que o círculo está inscrito. Contudo,como existem muitas formas de descrever os mesmos problemas matemáticos, é importante investigaras diversas formas de descrever matematicamente circunferências no espaço, e concluir qual a melhorpara ser usada pelo NCM.

Entidade ‘line’

A descrição matemática da entidade “linha” foi a que mais se alterou ao longo da evolução do projeto.Inicialmente a linguagem implementada era apenas bidimensional. As retas estavam implementadascomo função matemática, primeiro, pela equação geral da reta, depois, pela equação reduzida da reta(y = m ∗ x+ b). Ainda assim, estas possibilitavam representar retas verticais (paralelas ao eixo y). Numasegunda fase, evolui-se para a forma canónica da reta, possibilitando a representação de retas verticais.

37

Numa terceira fase, evolui-se para um sistema tridimensional. Por experiência com o Maxima, deu-se preferência à forma paramétrica em detrimento da forma vetorial. A forma paramétrica da linha,atualmente implementada, é:

x = a× t + A

y = b× t + B

z = c× t + C

Neste sistema, x, y e z são as variáveis da entidade form e a, b e c são as variáveis que representamo vetor ‘direção’ entre dois pontos da reta. As variáveis A, B e C definem um dos pontos da reta, e oparâmetro t é uma variável temporária que “desloca” o ponto inicial (A, B, C) ao longo da reta.

Conforme o tipo de linha (campo subtype da entidade line), são aplicados os seguintes filtros às solu-ções:

• No caso de uma semirreta (semistraight) é aplicado o filtro (t > 0).

• No caso de um segmento de reta (segment) são aplicados os filtros (t > 0; t < 1).

• No caso de uma reta (straight) não é aplicado nenhum filtro às soluções.

Sumário

Existem muitas formas de descrever os mesmos problemas matemáticos. Para cada uma das várias for-mas de descrever uma linha é possível encontrar um cenário específico na qual se dá preferência a umaespecífica. Mas a forma paramétrica das equações da reta revelou-se cobrir totalmente os casos de uso.Durante a implementação destas equações, diversos artigos da área da matemática foram explorados,com o intuito de descobrir a melhor forma de descrever as entidades geométricas em equações. Da ex-periência adquirida concluímos que a melhor forma é evoluir o âmbito do conjunto de casos de uso àmedida que vão surgindo, mesmo que isso implique alterar o formato da descrição matemática. Atual-mente o utilizador final apenas tem acesso à forma paramétrica, e como trabalho futuro é interessantesuportar simultaneamente as diferentes descrições da mesma propriedade.

Entidade ‘form’ e as estruturas ‘mathProblem’ e ‘property’

A maioria das funções do módulo “entities-properties” cria instâncias de property, capaz de gerar con-juntos de equações que descrevem as extremidades, fronteiras ou superfícies das entidades geométricas.Por exemplo, a função circle-form-equation descreve a circunferência da fronteira do círculo. A des-crição de sólidos e áreas necessitaria de recorrer a inequações, por isso não foi possível implementarnesta fase.

A função entity-form-equation aceita vários tipos de entidades geométricas (point, line, circle,sphere) e chama a função correspondente para descrever o espaço geométrico da superfície dessa en-tidade. Estas funções recebem duas entidades geométricas: entidade da qual se pretende descrever asuperfície, e a entidade form onde será limitado o espaço geométrico. O resultado da função é umainstância do tipo property.

38

O código 3.11 exemplifica o funcionamento interno da entidade form, onde o seu espaço geométrico érestringido de forma a calcular a interseção entre uma linha e uma circunferência. As operações usa-das no código são de baixo nível que normalmente seriam usadas pelos utilizadores avançados paraimplementar novas operações de alto nível. Atualmente, a operação de interseção através do núcleode calculo matemático está disponível pela função intersection do módulo “geometric-restrictions”,como uma função de alto nível, um vez que, a resolução da restrição é calculada através de técnicasde manipulação simbólica e computação algébrica, os resultados obtidos são mais fiáveis que outrastécnicas que recorram a arredondamentos.

Na primeira linha é criada uma instância da entidade form, chamada ‘f1’. Inicialmente ‘f1’ representatodo o espaço. Nas linhas 5 e 6 são criadas as propriedades que relacionam as variáveis de ‘f1’ com asvariáveis de ‘l1’ e ‘c1’. A primeira e segunda função entity-form-equation chamam respetivamenteline-form-equation e circle-form-equation, definindo ‘p1’ e ‘p2’. A property ‘p1’ limita o espaçogeométrico de ‘f1’ à reta ‘l1‘. A property ‘p2’ limita o espaço geométrico de ‘f1’ a circunferência docírculo ‘c1‘. Na linha 8, as equações são geradas, isto é, o problema matemático é criado e passado aoNCM. Os resultados são processados, em particular, actualiza-se todas as variáveis (não só as de ‘f1’)das instâncias de property cujo valor esteja indefinido. Por último, na linha 9, caso esteja definida, éextraída de ‘f1’ uma lista de pontos geométricos, da qual são criadas instâncias da entidade point.

Por norma, as instâncias de entidade form são temporárias, ou seja, caso são sejam explicitamente grava-das, são eliminadas pelo Garbage Collection do Racket. Em muitas situações, basta atualizar as variáveisdo modelo com os resultados da solução. Desta forma, a função form->points não é habitualmente cha-mada. Caso se pretenda encontrar o ponto de interseção, é recomendado que este ponto seja declaradono problema matemático, em termos de código. Nesse caso, seria necessário substituir as linhas 8 e 9pelas linhas 11, 12 e 13.

Código 3.11: Exemplo de utilização ‘mathProblem’.

1 (define f1 (new -form -unset))

2 (define l1 (new -point -10 0) (new -point 10 0))

3 (define c1 (new -point 0 0) 1)

45 (define p1 (entity -form -equation l1 f1))

6 (define p2 (entity -form -equation c1 f1))

78 (mathProblem -resolve p1 p2)

9 (form ->points f1)

1011 ;( define point1 (new -point -unset))

12 ;( define p3 (entity -form -equation point1 f1)

13 ;( mathProblem -resolve p1 p2 p3)

Restrição de Interseção

A função intersection especifica o espaço de interseção a partir de um número arbitrário de entidades.A função devolve uma instância de form que representa a interseção das extremidades das entidades.Por exemplo, na interseção entre duas retas existem três cenários possíveis: as retas não se intersetame o resultado é vazio, as retas intersetam-se num ponto ou as retas são coincidentes. Numa abordagemclássica teríamos que tratar individualmente cada um dos cenários e para cada combinação de entida-

39

des. Mas a solução implementada é genérica, o que permite a combinação de funcionalidades ao longode toda a arquitetura.

A função equation-entity-edge recebe a entidade geométrica e a entidade form. A função de interse-ção recebe entidades como parâmetros e existe uma entidade temporária do tipo form, esta é passadacomo parâmetro nas chamadas à função equation-entity-edge juntamente com as outras entidadesgeométricas. As equações geradas são passadas ao NCM, que soluciona em ordem às variáveis. Osresultados são depois refletidos de volta no modelo geométrico, limitando assim os valores possíveisnão definidos nas entidades. A entidade form pode ser convertida nas outras entidades. Contudo, nestemomento, apenas a conversão para entidade point está implementada, ou seja, neste momento apenasfunciona em cenários cujo resultado final da intersecção é vazio, um ponto, ou um conjunto de pontos.

Mesmo que o objetivo seja só descobrir pontos de interseção, recomenda-se que estes sejam declaradosà priori com variáveis não definidas através do construtor new-point-unset, que, uma vez entregues àfunção intersection, atualizará todas as variáveis não definidas com os resultados obtidos do NCM.

A função intersection recebe adicionalmente a entidade form através da keyword #:intersection-form.Caso a função não receba este argumento, é construída uma instância de entidade representante de todoo espaço geométrico. A passagem deste argumento permite combinar funcionalidades, ou aplicar res-trições. Por exemplo, pode-se limitar o espaço de interseção ao plano xy, definindo a variável ‘z’ daentidade form a zero (set-form-z! form 0).

Restrição de Pontos de Superfície

A função entity-surface-points recebe uma entidade geométrica e um número arbitrário de pontos.A localização de cada ponto é restringido à superfície da primeira entidade geométrica. Esta função éequivalente à função entity-form-equation mas otimizada para pontos.

Função de Linhas Paralelas

A função parallel-line recebe duas retas e limita as entidades geométricas do tipo line para quesejam paralelas. As variáveis de uma das retas são limitadas de acordo o vetor ‘direção’ calculado paraa outra reta. As retas são paralelas se o vetor de ‘direção’ for igual em ambas.

Função de Círculos Tangentes

A função tangent-circles recebe duas instâncias de círculo, e devolve uma lista do pontos tangentesentre os círculos que podem variar entre:

• zero tangentes - se os círculos forem coincidentes ou se um estiver contido no outro sem se inter-setarem.

• uma tangente - se os círculos se intersetarem num ponto e um estiver contido no outro.

• duas tangentes - se os círculos se intersetarem em dois pontos (duas tangentes externas aos círcu-los).

• três tangentes - se os círculos se intersetam num único ponto, ou seja, os círculos também sãotangentes (duas tangentes externas e uma que passa no ponto de intersecção).

40

• quatro tangentes - se os círculos estiverem separados (duas tangentes externas e duas tangentesinternas, como ilustrado na Figura 3.3).

Figura 3.3: Retas tangentes entre círculos.

O código 3.12 demonstra a implementação da função tangent-circles. Entre as várias construçõesgeométricas possíveis que foram implementadas, o código representa uma das soluções implementa-das e a disponibilizada ao utilizador final. Baseia-se numa descrição geométrica: começa por defi-nir 4 pontos (dois ao centro dos círculos e um ponto em cada circunferência) (reutilização da funçãocircle-form-equation2d). Depois restringe a localização dos pontos assegurando que o ângulo for-mado pelos pontos é um ângulo reto (90 graus). Para isso foi usado a restrição right-angle-equation

com os pontos: centro de um dos círculos, o respetivo ponto de superfície e o ponto de superfície dooutro círculo. A restrição fica completa aplicando o mesmo tipo de restrição ao outro círculo.

Código 3.12: Implementação da função ‘tangent-circles’.

1 (define (tangent -circles circle1 circle2)

2 (unless (circle? circle1) (error 'circles -tangent "The 1* agr is not a circle

"))

3 (unless (circle? circle2) (error 'circles -tangent "The 2* agr is not a circle

"))

4 (let* ([c1 #; center1 (circle -center circle1)]

5 [c2 #; center2 (circle -center circle2)]

6 [r1 (circle -radius -s circle1)]

7 [r2 (circle -radius -s circle2)]

8 [sp1 #; surfacePoint1 (new -point -unset)]

9 [sp2 #; surfacePoint2 (new -point -unset)]

10 [eq1 (right -angle -equation c2 sp2 sp1)]

11 [eq2 (right -angle -equation sp2 sp1 c1)]

12 [eq3 (circle -form -equation2d circle1 sp1)]

13 [eq4 (circle -form -equation2d circle2 sp2)])

14 (mathProblem -resolve

15 eq1 eq2 eq3 eq4

16 #: restrictions

17 `(,(~a "(" "is(matrix (["( point -x-s sp1)"] ,["(point -y-s sp1)"]) # matrix

(["( point -x-s sp2)"],["(point -y-s sp2)"]))"

18 "or " "is("r1"+"r2"=sqrt ("(point -x-s c2)"-"(point -x-s c1)")^2 + ("(point -y

-s c2)"-"(point -y-s c1)")^2)" ")")))))

41

Despacho

Nesta secção é analisada a implementação da operação de despacho entre o NCM e a BFG. O despachotem a função de escolher qual o método mais adequado para resolver o problema, abstraindo o utili-zador dessa escolha. Por norma, o método mais adequado são as funções da BFG, mas apenas quandoestas estejam disponíveis.

Neste momento, apenas se encontra implementado o despacho para as funções de interseção, comoforma de demonstração da funcionalidade e para propósitos de benchmarking. Na secção 4.2, é compa-rado o custo computacional da BFG com NCM, na secção seguinte (4.3) são analisadas alguns aspetossobre as capacidades de resolução dos dois métodos. Na secção 4.1 são discutidos algumas considera-ções sobre a veracidade e exatidão dos resultados obtidos pelos dois métodos.

A função intersection-dispatcher faz o despacho para a operação de interseção entre o NCM e aBFG e contém a seguinte assinatura “(intersection-dispatcher . objs)”. Esta função escolhe,conforme o modelo, as funções que devem ser aplicadas para cálculo da interseção, tendo preferên-cia pelas funções geométricas existentes no BFG por serem eficientes (2d-intersection-line-line*;2d-intersection-circle-line*; 2d-intersection-circle-circle*) antes de usar a função genéricado NCM (intersection).

Para as funções de despacho é importante manter as interfaces das funções equivalentes. Desta forma, afunção intersection-dispatcher recebe um número arbitrário de entidades geométricas assim comoa função intersection. Além disso, usamos a macro mask para uniformizar o parâmetro de entrada esaída das funções geométricas.

Os argumentos das funções geométricas são ordenados por ordem alfabética conforme os tipos das en-tidades geométricas. Desta forma, fazemos uso da propriedade comutativa da operação de interseção.Os argumentos de entrada da função intersection-dispatcher são ordenados da mesma forma. O re-sultado das funções geométricas é uma lista de entidades (neste momento, as funções apenas devolvementidades do tipo point). Esta lista não tem qualquer ordem específica e pode variar. O utilizador deveaplicar filtros e/ou ordenar a lista, conforme as necessidades.

Cada uma das funções geométricas tem um conjunto de condições que têm que ser respeitadas paraque possam ser usadas. Caso as condições não correspondam a nenhuma das funções, a função maisgenérica “intersection” é usada, que usa o NCM.

Para a função 2d-intersection-line-line* ser usada, os argumentos de entrada têm que ser duaslinhas, no caso da função 2d-intersection-circle-line* têm que ser um círculo e uma linha e no casoda função 2d-intersection-circle-circle* têm que ser dois círculos. Além disso, todas as entidadespoint contidos nos argumentos de entrada têm que ter o campo “x” e “y” bem definidos (um valorcompletamente definido) e o campo “z” com o valor “0”. Falta ainda verificar algumas condições, taiscomo (i) a line tem que ser uma reta, (as implementações atuais das funções geométricas não estãopreparadas para lidar com semirreta ou segmento de reta), e (ii) a entidade circle tem que estar noplano ‘xy’ ou paralelo.

Existem diferenças fundamentais entre a BFG e o NCM. Na BFG, a solução está bem definida: tanto ostipos como os resultados esperados são conhecidos à partida. Por outro lado, o NCM é usado como so-lução genérica e só se sabem os tipos dos argumentos em tempo de execução. A solução genérica efetuapassos adicionais quando comparada com a solução especializada, um dos quais sendo a atualizaçãodas variáveis (entidade value ou var) envolvidas no problema, restringindo o seu espaço de valores,

42

tanto nas entidades que queremos calcular, como nas entidades que são passadas como argumento.Pelo contrário, as funções da BFG não atualizam os valores das entidades. A BFG efetua arredonda-mentos, enquanto o NCM utiliza técnicas de manipulação simbólica e computação algébrica, evitandopor completo os arredondamentos. Evitando desta forma o problema da falta de robustez e exatidão. Asolução genérica do NCM requer o uso de um sistema de computação algébrica e manipulação simbó-lica que tem um custo computacional elevado em relação à BFG. No capítulo seguinte, comparamos odesempenho das duas soluções.

Integração

Nesta secção são apresentados os possíveis métodos para integrar a linguagem criada noutras lingua-gens e ferramentas. Faz parte dos objetivos deste trabalho estender o poder expressivo do Rosetta, porisso tivemos especial atenção na integração entre as duas linguagens. Mas é igualmente importantepensar também numa integração mais genérica, para que a linguagem ConstraintGM possa ser usadanum contexto desacoplado do Rosetta.

O Racket é uma linguagem multi-paradigma que suporta multilinguagem, ou seja, é fácil de integrarcom código escrito em diferentes linguagens e até linguagens com diferentes paradigmas, como pro-gramação funcional, programação com objetos, entre outras. Desta forma o Racket permite definir naprimeira linha de cada módulo o dialeto a ser usado, através do comando “#lang”. Cada dialeto temum parser associado (também conhecido como language reader), tal permite suportar linguagens com di-ferentes sintaxes. No nosso projeto, evitámos criar o nosso próprio dialeto, para que seja possível usar opróprio parser da linguagem Racket (“#lang racket”). Desta forma, qualquer linguagem que use o dialetodo Racket consegue integrar diretamente com a linguagem criada. O Rosetta é uma destas linguagens,por isso, qualquer utilizador consegue usar diretamente, no código, as funções disponibilizadas pelalinguagem criada.

Seria possível evoluir para uma integração mais intrínseca com o Rosetta, através da criação da função(send2rosetta) que especificasse para cada entidade geométrica a função, ou funções, do Rosetta quedeveriam ser chamadas com o intuito de recriar um objeto com uma semântica equivalente à instância daentidade geométrica. Isto poderia ser implementado de forma semelhante à função entity-map-fields

usado a funcionalidade generics do Racket (a interface genérica permite associar funções genéricas aosmétodos conforme os tipos dos argumentos). Contudo, como as entidades da nossa linguagem podemnão ter uma equivalência em Racket, poderá ser necessário chamar mais que uma função do Rosetta deforma a recriar a semântica pretendida.

Um aspeto a ter em conta são as propriedades das entidades geométricas poderem não ser equivalentesaos argumentos das funções do Rosetta. Em particular, na nossa solução, a entidade linha (line) permiteque seja descrita por formas distintas. Por exemplo, a entidade pode ser representada pela:

• localização das duas extremidades;

• localização de uma extremidade, um vetor e o comprimento (o campo comprimento só é usado sea instância representar um segmento de reta ou uma semirreta);

No Rosetta, a sintaxe para a criação de uma linha requer as duas extremidades. Embora exista outraalternativa, nenhuma equivale diretamente à nossa representação “extremidade, vetor, comprimento”.Assim seria necessário calcular a localização da extremidade em falta, imediatamente antes de passar osargumentos à função do Rosetta. Para além disso, as entidades podem não estar totalmente restringidas

43

no espaço. Nestas situações é devolvido erro ao utilizador para que este complemente a informação emfalta.

Pensámos também numa perspetiva de uma integração mais genérica, com o objetivo de facilitar adescrição do problema geométrico e extração dos valores pretendidos, abstraindo o utilizador final to-talmente das entidades de baixo nível (value; var; entre outras). Por isso, está a ser implementada amacro geometric-constraints. Esta contém uma sintaxe semelhante ao let de Racket, mas permiteao utilizador fazer a discrição do problema geométrico, simplificando a passagem das propriedadesdas entidades com parâmetros para funções de terceiros (ex. funções do Rosetta que permitem criargeometria). Além disso, permite encapsular ainda todas as funções disponibilizadas pela linguagem.

A assinatura da macro geometric-constraints, a sua expansão, um exemplo de utilização e a suarespetiva expansão, são apresentados respetivamente pelo código 3.13, 3.14, 3.15 e 3.16. O exemploespecifica a criação de um círculo no Rosetta centrado na interseção de duas retas.

Código 3.13: Assinatura da macro geometric-constraints.

1 (geometric -constraints (agr ...)

2 (constraint ...)

3 body ...)

45 agr = name # Syntactic sugar for ``(name (new -value)) ''.

6 | (name valor) # Where `name ' it an identifier and `value 'is a number or

mathematical expression.

7 constraint # Specification of the geometric model with geometric constraints.

8 body # Expressions that uses the identifiers ('name ') to access the variables.

Código 3.14: Expansão da macro geometric-constraints.

1 (let ((name valor) ...)

2 constraint ...

3 (let ((name (value -v name)) ...)

4 body ...)))))))

Código 3.15: Exemplo de utilização do macro geometric-constraints.

1 (geometric -constraints (x1

2 y1

3 (r 2))

4 (intersection (new -line (new -xyz 3.5 $\frac {1}{3}$) (new -xyz "-%pi" " -1/5"))

5 (new -line (new -xyz -10 "0") (new -xyz +10 0))

6 #:point (new -xyz x1 y1))

7 (circle x1 y1 10) Create a circle on Rosetta , with radius 10 and centered on

the intersection point.

Código 3.16: Expansão do código do exemplo 3.15.

1 (let ((x1 (new -value))

2 (y1 (new -value))

3 (r 2))

4 (intersection (new -line (new -xyz 3.5 $\frac {1}{3}$) (new -xyz "-%pi" " -1/5"))

5 (new -line (new -xyz -10 "0") (new -xyz +10 0))

6 #:point (new -xyz x1 y1))

44

7 (let ((x1 (value -v x1))

8 (y1 (value -v y1)))

9 (circle x1 y1 10)))

Tal como referido previamente nesta secção, foi usado o mesmo dialeto que a própria linguagem Racketusa. Desta forma, ao integrar com o Racket garantimos ao mesmo tempo uma forte integração comoutros sistemas e linguagens de programação.

Para além da simples disponibilização de funções no Racket, focámo-nos em funcionalidades com o in-tuito de facilitar a sua utilização. Dos dois métodos de integração analisados, concluímos que o métodosend2rosetta acarretava duas principais desvantagens:

• É necessário requisitar os módulos que constituem o Rosetta, numa versão predefinida, mesmoque o utilizador não a utilize. Um melhoramento seria ter toda a implementação da integraçãonum submódulo [30]. Desta forma, o utilizador podia requisitar o submódulo explicitamente,caso quisesse usar as duas linguagens, mas o submódulo continuaria a estar restringido numaversão especifica do Rosetta. Como o Rosetta está ainda em desenvolvimento, tal implicaria umesforço adicional para manter compatível a versão atualizada da linguagem.

• A outra grande desvantagem vem da pouca utilidade que esta integração traz para o utilizador. Apartir dos casos de uso, as funções especificas para transferir as entidades geométricas para o Ro-setta são pouco utilizadas; na maioria das situações, apenas se quer descobrir alguns valores, quedepois são usados para criar geometria do lado do Rosetta, não fazendo esta parte da descriçãoinicial do modelo. A macro geometric-constraints foi pensada para estes cenários. A lingua-gem ConstraintGM é a ferramenta que permite ao utilizador abstrair-se do aspeto matemáticoassociado à construção geométrica.

45

46

Capítulo 4

Avaliação

Uma vez implementado o sistema proposto nas secções anteriores, avalia-se o desempenho de execuçãodo sistema e a arquitetura da linguagem criada.

As funcionalidades descritas, nos casos de uso, da proposta inicial deste projeto, foram implementadasem dois solvers, nomeadamente o NCM e a BFG. Contudo, constitui um conjunto limitado de funcionali-dades para se considerar um sistema suficientemente funcional para as necessidades de um modelador.A limitação da quantidade de funcionalidade implementada deve-se principalmente ao tempo limitadopara a implementação do projeto, e também, ao facto de se concentrar esforços na arquitetura da lingua-gem.

A estratégia de avaliação passa pelos seguintes aspetos:

• Robustez e exatidão da linguagem, no sentido que as soluções obtidas são corretas em termosteóricos e não contêm erros de precisão ou que estes são mitigados.

• Benchmark a comparar o desempenho entre o NCM e a BFG.

• Extensibilidade da linguagem.

• Benchmark de modelação com utilizadores especialistas (modeladores) de modo a comparar a lin-guagem proposta e outras ferramentas e/ou linguagem modelação.

As subsecções seguintes expressam os resultados da avaliação de cada aspeto. Contudo, não foi possívelefetuar o benchmark de modelação com utilizadores especialistas porque os resultados seriam conside-rados pouco fidedignos, devido ao restrito número de funcionalidades efetivamente implementadas.

Na secção 4.4, é demonstrado a facilidade de estender a linguagem com um conjunto de funcionalidadescompletamente novo, tirando partido da arquitetura modular que permite combinar as funcionalidadespara descrever restrições complexas, com resultados positivos.

Robustez e Exatidão da Linguagem

Na linguagem criada, a robustez e exatidão dos resultados obtidos depende do solver usado para resol-ver as restrições geométricas.

47

A BFG apresenta alguns desafios de implementação, nomeadamente aspetos de vertente numérica, emconcreto, arredondamento numérico. A implementação possui algumas propriedades que ajudam amitigar o problema de robustez e exatidão dos resultados, apresentado na secção 2.1.6. Uma vez que asfunções geométricas são implementadas em Racket, o problema é mitigado por capacidades da próprialinguagem.

Essas capacidades envolvem o facto de os números em Racket se dividirem em duas categorias, exatose inexatos:

• Os números inexatos são representados com vírgula flutuante e expoente, o que provoca o pro-blema de exatidão, como explicado na secção 2.1.6.

• Os números exatos dividem-se em números inteiros e números fracionários.

– Os números inteiros são representados em binário sem qualquer problema de precisão.

– Os números fracionários são representados por dois números inteiros, um numerador e umdenominador.

Como boa prática, o utilizador deve usar sempre que possível, números exatos. Por exemplo, em al-ternativa ao número inexato “0.5”, deve-se usar “1/2”, que é um número exato fracionário. Contudo,as operações aritméticas básicas têm um custo acrescido quando os operandos são números fracioná-rios. Adicionalmente existem operações que produzem números inexatos, como é o exemplo da raizquadrada (“sqrt”).

No NCM, o problema da robustez e exatidão dos resultados é resolvido por completo, pelas capacidadesda manipulação simbólica do sistema de resolução matemática.

Ao contrário do Racket, as operações e o NCM não usam nem produzem números decimais. Se o utili-zador escrever números decimais no código, estes são automaticamente convertidos para uma fração.

Benchmark

Esta secção descreve os resultados da avaliação de performance do NCM e da BFG.

A máquina onde o benchmark foi realizado possui as seguintes características:

• CPU - i5-3320M (3.30 GHz);

• 8GB RAM (a execução do programa Racket está limitada a 512MB);

• DrRacket, versão 6.3.0.3;

• Maxima, versão 5.34.1, usando Lisp CLISP 2.49.

O tempo de inicialização do NCM é uma constante, independente da complexidade da descrição derestrições geométricas. O Maxima é inicializado cada vez que o programa Racket é executado, em mediademora 2011 ms (milissegundos).

O benchmark compara o tempo de execução real, para um conjunto de cenários que possibilita a compa-ração da função intersection-dispatcher com a função intersection. Todos os cenários constituemo cálculo de interseções entre duas entidades geométricas, onde existem funções geométricas capazesde resolver esses cenários. Foi usado o tempo de real de execução em alternativa ao tempo de CPU, para

48

incluir o tempo de comunicação e computação do Maxima. Quanto maior o valor, pior o despacho dosistema.

Na tabela seguinte são apresentados os tempos para cada um dos solvers. Os cenários envolverem aresolução da mesma restrição mil vezes, de forma a obter tempos significativos e aumentar a precisãoda medição.

CenárioTempo execução (ms) Speed-up da função

geométrica para o MaximaFunção geométrica

Maxima Biblioteca de Funções

1 26885 64 420intersection-line-line

2 26858 35 767

3 31930 39 818intersection-circle-line4 20395 27 755

5 20261 21 844

6 11531 19 606

intersection-circle-circle

7 18688 20 9348 20303 21 9669 16436 33 498

10 27162 42 64611 28373 37 766

Todos os cenários constituem problemas distintos, por envolverem entidades geométricas diferentes, oupor ser geometricamente diferentes (variando o número de soluções).

O despacho do NCM pode ser melhorada consideravelmente. Como descrito na secção de comunicação3.3, o número de ciclos de comunicação entre o Racket e o Maxima pode ser reduzido para metadese resolver o problema de comunicação do Maxima. O conteúdo da comunicação também pode serreduzido, uma vez que está feito para ser humanamente legível para propósitos de debug do códigogerado na linguagem do Maxima.

Para além disso, as funções geométricas assumem determinados pressupostos que são verificados nafunção “intersection”, contêm casos de paragem específicos ao problema geométrico (por exemplo,dois círculos só se podem intersetar se a distancia entre os seus centros for inferior à soma dos seusraios), são usados números decimais em vez de números fracionários e as interseções são só entre duasentidades geométricas. Isso são tudo condições que favorecem as funções geométricas em relação aoNCM neste benchmark.

Resumindo, como esperado, a BFG supera em termos de performance o NCM, por várias ordens degrandeza, com um Speed-up médio de 810, variando entre 420 e 966.

Núcleo de Cálculo Matemático

Na secção anterior medimos a performance do NCM com a BFG em vários cenários diferentes. Nestasecção vamos analisar um desses cenários, mais concretamente os últimos dois. Ele descrevem a inter-seção de dois circunferências de diferentes tamanhos no plano, que se intersetam em dois pontos. Nocenário onze os centros das circunferências estão alinhados na vertical ou horizontal e no cenário doze,estes estão alinhados na diagonal. O Maxima consegue resolver o sistema de equações para o cenárioonze, mas para alguns caso particulares (vamos chamar cenário doze), quando os centros das circun-

49

ferências estão alinhados diagonal o Maxima não é capaz de chegar a uma solução para o sistema. Ocódigo enviado ao Maxima é o seguinte:

Código 4.1: Código Maxima que descreve o cenário onze do benchmark. Figura 4.1.

solve ([(x-1) ^2+(y-1)^2 = 1,(x-1) ^2+(y-0)^2 = (3/2) ^2],[x,y]);

Código 4.2: Código Maxima que descreve o cenário doze. Figura 4.2.

solve ([(x-1) ^2+(y-1)^2 = 1,(x-0) ^2+(y-0)^2 = (3/2) ^2],[x,y]);

Como podemos analisar pelo código gerado para descrever os dois casos, estes diferem apenas numnúmero, mas por algum motivo o Maxima não consegue reduzir a equação do cenário onze, apenas ado doze com a solução 4.1. Experimentámos resolver exatamente as mesmas equações usando o Mathe-matica, o qual conseguiu resolver sem problema, com as seguintes soluções, 4.2 e 4.3, para os cenáriosonze e doze respetivamente.

O Maxima consegue resolver o cenário onze, com a seguinte solução:[[x = −3

√7− 88

, y =98

],

[x =

3√

7 + 88

, y =98

]](4.1)

O Wolfram Mathematica consegue resolver estes cenários, com as seguintes soluções:[[x = 1− 3

√7

8, y =

98

],

[x = 1 +

3√

78

, y =98

]](4.2)

[[x =

1316−√

11916

, y =1316

+

√11916

],

[x =

1316

+

√11916

, y =1316−√

11916

]](4.3)

Este exemplo serve apenas para demonstrar a diferença entre diferentes sistemas de computação algé-brica e manipulação simbólica. No futuro, seria interessante incorporar na solução diferentes sistemaspara o domínio da linguagem criada, ou seja, para resolver sistemas de equações que descrevem en-tidades geométricas, restrições e relações entre essas entidades. No início do projeto, testámos váriosnúcleos de cálculo, e mesmo ao longo de toda a implementação comparámos as capacidades de reso-lução do Maxima com o Mathematica, e estavam ao mesmo nível. Este é um exemplo que o Maxima(versão 5.34.1) não conseguiu resolver e que o Mathematica conseguiu. Isto não quer dizer que umsistema tenha mais ou menos poder de resolução que o outro, apenas que são diferentes um do outro.

A escolha do Maxima como sistema de computação algébrica e manipulação simbólica usado pelo NCMa foi uma boa opção. Cuntudo o conhecimento obtido ao longo do desenvolvimento levamos a pensarque Mathematica podia ser sido opção mais adequada para o trabalho. Evitada assim algumas dificul-dades encontradas na comunicação com o Maxima através de ‘socket’ do sistema operativo.

Expansão da Linguagem

Esta secção é dedicada aos utilizadores avançados, que pretendam expandir a funcionalidade da lingua-gem criada.

50

Figura 4.1: Cenário onze do benchmark. Figura 4.2: Cenário doze do benchmark.

No início deste projeto, examinámos diversas linguagens de programação, tais como o AutoLisp e Gras-shopper. Estas são bastante populares e amplamente usadas pelos arquitetos. Reparámos ainda, que acomunidade de utilizadores contribuía ativamente para melhorar estas ferramentas, e que os exemplose algoritmos implementados por estes constituem uma grande parte da funcionalidade disponibilizada.

Por este motivo, desde o início, tivemos a preocupação de como os utilizadores, podiam expandir asfuncionalidades da linguagem e partilhar com a comunidade, a este utilizador chamamos utilizadoravançado. Para isso, dividimos os módulos em secções distintas e independentes, criamos macros paraajudar na expansão dessas secções, fazendo a integração entre as secções distintas de forma automática.Assim, o utilizador pode expandir uma funcionalidade em particular, usando funcionalidades imple-mentadas por diferentes utilizadores avançados, e partilhar com a comunidade.

O caso de uso que vamos examinar nesta secção é um dos exemplos referidos na introdução. Pretende-secriar uma esfera a partir de quatro pontos de superfície.

A primeira coisa a fazer é criar a entidade geométrica, que represente a esfera, uma vez que ainda nãoexiste. Contudo, podemo-nos basear na entidade círculo (“circle”), porque, matematicamente estassão semelhantes.

A estrutura que suporta a entidade geométrica da esfera é criada através das macros “entity-type” e“entity-build”, e usa as entidades: “point” e “value”. Neste momento, a entidade geométrica, esfera,pode ser implementada com o código 4.3. O campo “radius”, representa o raio da esfera, mas o seuvalor não está restringido a um valor positivo, porque ainda não é possível definir restrições através damacro.

Código 4.3: Implementação da esfera como entidade geométrica (sphere).

1 #lang racket

2 (require "entity -macro.rkt")

3 (require "point.rkt")

4 (require "value.rkt")

56 (entity -type sphere

7 ([ center point (new -point 0 0)]

8 [radius value 1]))

910 (entity -build sphere)

51

O segundo passo é criar a função que gere equações matemáticas a partir das variáveis da esfera, res-tringindo o espaço da superfície desta. O código seguinte representa uma possível implementação destafunção.

Código 4.4: Propriedade que descreve a superfície esférica em equações matemáticas.

1 (define (sphere -form -equation sphere form)

2 (let ([c (sphere -center sphere)]

3 [r (sphere -radius -s sphere)]

4 [Fx (point -x-s form)]

5 [Fy (point -y-s form)]

6 [Fz (point -z-s form)])

7 (make -property sphere

8 "(~a-~a)^2+(~a-~a)^2+(~a-~a)^2 = ~a\^2"

9 `((,Fx ,(point -x-s c) ,Fy ,(point -y-s c) ,Fz ,(point -z-s c) ,

r))

10 `(,Fx ,Fy ,Fz)

11 `(,(~a "is(" r ">0)")))))

Encontramos uma limitação que obrigaria a mexer no código já implementado da linguagem criada, aqual não tivemos tempo de melhorar. A função geral (“entity-form-equation”) está implementadadiretamente na “fase 0”: esta função é responsável por saber como gerar as equações para descrevema entidade geométrica conforma a entidade passada, chamando a função especializada em descrevera superfície dessa entidade. Uma vez que é implementada diretamente no código e não através daexpansão da fase anterior, tivemos que adicionar a linha 6 a função do código 4.5, o que criar problemasde integração com outras expansões que também tenham que alterar esta função, como trabalho futuroproponho que o código desta função seja criada na fase de expansão.

Código 4.5: Implementação da função entity-form-equation.

1 (define (entity -form -equation e form)

2 (match e

3 [(? point? a) (point -form -equation a form)]

4 [(? line? a) (line -form -equation a form)]

5 [(? circle? a) (circle -form -equation2d a form)]

6 [(? sphere? a) (sphere -form -equation a form)]

7 [_ (error 'entity -form -equation "unsupported entity ")]))

Uma solução, para o problema acima seria criar uma estrutura auxiliar, à semelhança das estruturasusadas na macro “entity-type” (“$ID”; “$FIELD”; “$FUNC”), ou mesmo reutilizando estas estruturas.De forma, a guardar meta-informação sobre funções, implementadas a posteriori, que depois seria usadopelas funções gerais já implementadas, como por exemplo a função “entity-form-equation”.

Mais concretamente, a solução foi criar duas novas macros, uma que guardasse meta-informação sobreas funções criadas pelo utilizador, e a outra para expandir o código da função “entity-form-equation”,no tempo de compilação (“fase 1”), ou seja, as linhas 3, 4, 5 e 6, da função seriam geradas pela expansãodo código, a partir da meta-informação.

Por último, criamos a operação que pretendíamos, ou seja, relacionar a entidade geométrica com umconjunto de pontos, restringindo a localização dos pontos a superfície da entidade. Esta função podeser implementada da seguinte forma:

52

Código 4.6: Função entity-surface-points.

1 (define (entity -surface -points #:debug[debug false] entity . points)

2 (mathProblem -getEntityWithValues

3 (apply mathProblem -resolve

4 (map (lambda (p) (entity -form -equation entity p))

5 points) #:debug debug)

6 entity))

Adicionalmente, podemos criar um teste para validar que está tudo a funcionar corretamente. O código4.7 representa um teste à função “entity-surface-points” e o seu resultado pode ser observado nolisting 4.8.

O artigo [31] explica qual o sítio correto para escrever código de teste em Racket, que é faze-lo dentrodo próprio módulo, usando o submódulo chamado “test”. Estes submódulos, contém uma série depropriedades, ideais para testar o código, principalmente se tivermos código para a fase de expansão,por exemplo, o submódulo “test” é executado após o módulo principal e todos ou outros submódulos,serem expandidos e executados. O código dentro deste submódulo é apenas executado quando estamosa correr o módulo principal diretamente, ou seja, o “test” não executado quando importamos o móduloprincipal.

Uma parte do tempo de implementação é dedicada a escrever testes, e, atualmente, quase todas as fun-ções de todos os módulos deste projeto têm código de teste associado. O único código associado atestes, contido fora do submódulo “test”, é para efeitos de depuração do NCM. As funções que traba-lham com equações matemáticas ou com o próprio núcleo de cálculo, aceitam um parâmetro adicionalcom a keyword “debug”, caso contenha o valor ‘TRUE’, é escrita para o standard output informação sobreo modelo matemático.

Para um utilizador avançando, que esteja a trabalhar com as equações matemáticas, pode ser útil conhe-cer está funcionalidade, uma vez que é a única maneira de ter a noção do módulo matemático (internoao sistema). Isto, porque quando analisamos a ferramenta GeoSolver na secção 2.2.4, concluímos queseria difícil para o utilizador compreender o modelo interno do sistema. Desta forma, quisemos abstraircompletamente o utilizador final do nosso sistema de resolução de restrições através do NCM, para queeste nunca seja obrigado a se preocupar com os pormenores matemáticos envolvidos na resolução dasrestrições geométricas.

Código 4.7: Testes à função “entity-surface-points'’.

1 (module+ test

2 (displayln ">entity -surface -points; expected result: x=24/19; y= -16/19; z

=4/19; r=3* sqrt (470) /19")

3 (let ([p1 (new -point 3 2 1)]

4 [p2 (new -point 1 -2 -3)]

5 [p3 (new -point 2 1 3)]

6 [p4 (new -point -1 1 2)]

7 [s (new -sphere (new -point -unset) (new -value))])

8 (entity -surface -points s p1 p2 p3 p4)))

Código 4.8: Resultados dos testes da função “entity-surface-points”.

1 >Test points2sphere (expected result: x=24/19; y= -16/19; z=4/19; r=3* sqrt (470)

/19)

53

2 (sphere

3 'id_sphere_59829

4 (point

5 'id_point_59827

6 (value 'id_value_59824 "24/19")

7 (value 'id_value_59825 " -16/19")

8 (value 'id_value_59826 "4/19"))

9 (value 'id_value_59828 "(3* sqrt (2)*sqrt (5)*sqrt (47))/19"))

Sumário

Nós, como responsáveis desta linguagem especifica de domínio, podemos integrar as expansões dispo-nibilizadas pela comunidade com o projeto base. Para isso basta: importar as entidades geométricas, nomódulo “enities-declaration”; importar as funções especializadas, no módulo “function-mask”; impor-tar as funções, que usam o NCM, no módulo “entities-properties”.

Embora o caso de uso do utilizador fosse apenas ter a funcionalidade de restringir uma esfera, indi-cando quatro pontos de superfície, o resultado obtido foi muito mais que esta funcionalidade específica.A grande vantagem de termos uma arquitetura modular (inspirada no ThingLab 2.2.3) é que pode com-binar as funcionalidades. Neste exemplo, para além do pretendido, obtivemos:

• Capacidade de restringir os pontos à superfície de uma esfera (o oposto que inicialmente preten-díamos, ou seja, a função inversa);

• Capacidade de restringir as propriedades nos pontos de superfície duma entidade e na própriaentidade geométrica (um misto entre a função inversa e o que pretendíamos)

• Capacidade de restringir qualquer entidade geométrica, pelos pontos de superfície, desde que estaseja suportada pela função “entity-form-equation”.

• Capacidades de restringir a esfera, não só pelos pontos de superfície, mas também pelas outrasrestrições já implementadas. Por exemplo, a função “intersection”, está neste momento a funci-onar apenas com as alterações referidas neste secção.

Esta secção demonstra as grandes vantagem da linguagem criada, o que nos diferencia das abordagem“clássicas”, usadas pelas ferramentas de modelação. Em termos de extensibilidade, os resultados obti-dos são muito positivos, ultrapassando as nossas próprias expetativas. A arquitetura da implementaçãoda linguagem ConstraintGM facilita a extensibilidade dos módulos e a integração entre eles.

54

Capítulo 5

Conclusões

Este documento aborda o tema de modelação por construção geométrica, através da descrição de re-lações e restrições entre entidades geométricas. A solução proposta, para a resolução das restrições nadescrição do modelo, baseia-se na transformação destas descrições do modelo geométrico num pro-blema matemático. Para o efeito, foi desenvolvida uma linguagem de domínio específico, de modo queas descrições geométricas sejam definidas com recurso à descrição de restrições, a qual se designa porConstraintGM.

Analisou-se um conjunto diverso de ferramentas e linguagens de programação dedicadas à modelaçãogeométrica, das quais foram levantados os seus pontos fortes e fracos. Estes foram tidos em contadurante o desenvolvimento da solução, levando a que a linguagem de domínio desenvolvida suportasseuma descrição declarativa do modelo geométrico, e que fossem disponibilizadas funcionalidades deexpansão e integração de novas restrições geométricas na linguagem de domínio. Adicionalmente, oproblema de robustez e exatidão dos resultados foi abordado com técnicas analíticas e de manipulaçãosimbólica.

A solução é composta por dois solvers alternativos, que resolvem as restrições geométricas de mododistinto, demonstrando vantagens e desvantagens, um em relação ao outro.

O solver designado por Biblioteca de Funções Geométricas (BFG) assenta numa abordagem clássicapartilhada pela maioria das ferramentas analisadas. Nesta abordagem, os problemas geométricos sãoresolvidos por funções especializadas na resolução de problemas geométricos específicos. Consequente-mente, a sua implementação tem que assegurar todos os casos possíveis, entidades envolvidas e cenáriosdistintos.

O solver designado por Núcleo de Cálculo Matemático (NCM) aborda o problema de forma genérica,usando para o efeito um sistema de computação algébrica e manipulação simbólica. Este solver permiteuma descrição declarativa do modelo, no qual o modelo é restringido iterativamente, passo-a-passo, eonde se pode aplicar operações e declarar relações.

O NCM apresenta uma arquitetura modular inspirada no Thinglab [6], de forma que as operações im-plementadas neste solver descrevem relações entre variáveis. Isto permite que as variáveis sejam resol-vidas em múltiplos sentidos, ou seja, o problema matemático é manipulado de modo que as variáveisdesconhecidas sejam resolvidas a partir das conhecidas. Estas funções podem ser constituídas pelacombinação de várias restrições geométricas.

55

Nesta abordagem, a descrição do modelo geométrico é transformado num problema matemático, oqual é resolvido pelo sistema de computação algébrica e manipulação simbólica. A solução apresen-tada ainda tem a grande vantagem de suportar modelos geométricos onde o DoF é Under-Constrainedou Well-Constrained, ou seja, mesmo que o modelo geométrico descrito pelo utilizador não esteja to-talmente restringido, é possível interrogar as propriedades das entidades geométricas se estas foremmatematicamente dedutíveis a partir da descrição atual.

Em relação ao problema da robustez e exatidão, os resultados obtidos diferem conforme o solver usado.A falta de robustez ou exatidão é um problema bem conhecido no campo da modelação geométrica[14]. Isto acontece porque muitos dos algoritmos de modelação geométrica são desenvolvidos a partirde algoritmos de computação gráfica, onde o tempo de computação é mais importante do que a exa-tidão do modelo geométrico, constituindo um problema em modelação geométrica devido a erros dearredondamento, onde resultados podem ser reutilizados para cálculos posteriores.

Usando a BFG, o problema não é resolvido completamente, mas mitigado através da existência de nú-meros fracionários do Racket.

Usando o NCM, o problema é resolvido devido às capacidades de manipulação simbólica do sistema decomputação algébrica.

Existe ainda um conjunto de boas práticas que os utilizadores devem seguir de modo a evitar este tipode problemas, descritas no artigo [15]. Em suma, passa por evitar, sempre que possível, os tipos derepresentação numérica inexatas e operações por natureza computacionalmente inexatas.

Durante a realização do benchmark, comprovou-se que em termos de despacho, a BFG é três ordens degrandeza mais rápido que o NCM, como era esperado. Em grande parte, porque o NCM envolve acomunicação com o processo do sistema de cálculo e a resolução de um conjunto de equações atravésde métodos analíticos, enquanto que no BFG se trata de um procedimento em Racket.

Na definição da arquitetura da solução foram considerados dois tipos de utilizador: final e avançado.

O utilizador final pretende apenas utilizar as funcionalidades da linguagem, com ou sem extensões.Estes utilizadores apenas necessitam de conhecer as entidades geométricas básicas e as operações dealto nível para definir restrições no modelo.

O utilizador avançado pretende expandir o domínio da linguagem. Para tal, foram criadas macrospara ajudá-lo a expandir o domínio da linguagem, uniformizar e automatizar a integração dos diversosmódulos, garantindo desta forma que as expansões de diferentes utilizadores funcionem em conjunto.Em particular, o utilizador avançado necessita de compreender a arquitetura da solução, em especial aparte que estiver a expandir. Por exemplo, ao adicionar entidades geométricas, precisa de compreenderas macros entity-type e entity-build, caso adicione funções geométricas à BFG deve usar a macromask, e se pretender adicionar funcionalidades e desenvolver novos tipos de restrições geométricas temde compreender como o problema matemático é gerado.

A arquitetura da solução é modular, oferecendo ao utilizador avançado a possibilidade de desenvolvernovas restrições geométricas. As funcionalidades dos diferentes módulos da arquitetura são integradasdurante a fase de expansão (fase 0) com auxílio a macros, possibilitando a combinação das novas funci-onalidades. Desta forma, o código disponibilizado ao utilizador final é praticamente todo gerado pelasmacros. O código é gerado segundo a meta informação guardada nas estruturas auxiliares das macros,que apenas existem durante a fase de expansão. O conteúdo dessas estruturas pode ser modificadopelos utilizadores avançados, que, para o efeito, foram desenvolvidas macros específicas. As macros

56

têm ainda como objetivo separar os diferentes módulos: (i) facilitar a expansão da linguagem criada, (ii)integrar automaticamente os diferentes módulos independentemente implementados pelos utilizadoresavançados.

A complexidade em expandir a linguagem com novas entidades e funcionalidades depende da formacomo é possível converter o modelo geométrico num problema matemático. Por exemplo, representaras extremidades de um quadrado é relativamente simples, podendo decompor-se em quatro linhas.Contudo, representar uma curva paramétrica pode parecer mais complexo, embora seja o ideal parauma representação matemática: é semelhante à entidade line mas contém uma expressão matemáticaque descreve a curva.

Demonstrou-se também que o conjunto de problemas geométricos que se conseguiria descrever emproblemas matemáticos seria muito superior caso fossem usadas inequações para descrever matemati-camente os cenários geométricos. Contudo, os atuais sistemas de computação algébrica são limitadosno que se trata na resolução de sistemas de inequações.

A linguagem ConstraintGM está dependente das atuais capacidades de resolução dos sistemas de ma-nipulação simbólica e computação algébrica. Não obstante, pelo fato deste género de sistemas ter apli-cabilidade em diversas áreas, a área científica que os contemplam, amplamente requisitada, tem de-monstrado constante evolução. Assim, o conjunto de problemas solúveis pela linguagem criada está emconstante evolução.

A solução proposta não pretende substituir a metodologia dos utilizadores nem as ferramentas atuais,mas sim complementá-las, oferecendo como principal funcionalidade a modelação através de constru-ções geométricas e a descrição de relações e restrições entre as entidades geométricas, como as descritasno livro de George E Martin [34]. Adicionalmente, a linguagem ConstraintGM procura abstrair o utili-zador da complexidade matemática envolvida na modelação das construções geométricas.

Concluímos que o nosso trabalho atingiu o principal objetivo proposto, que consistia em fornecer aoutilizador a possibilidade de fazer modelação por construções geométricas através da descrição de res-trições geométricas. Adicionalmente, conseguimos também atingir o objetivo secundário, porque é pos-sível utilizar esta ferramenta com o Rosetta, uma vez que o nosso sistema é importado como um módulodo Racket. Em relação a este ponto, consideramos ter desenvolvido uma ferramenta que é fácil de uti-lizar e entender por parte dos nossos utilizadores finais e, ao mesmo tempo, conseguimos criar umaferramenta fácil de estender por utilizadores mais avançados.

Trabalho Futuro

Ao longo dos capítulos anteriores foram referidos diversos aspetos que poderiam ser alvos de melhoria.Esta secção faz um levantamento e analisa em pormenor os aspetos mais relevantes e refere, ainda,outros aspetos a melhorar na linguagem ConstraintGM.

Melhoria de Funcionalidades Implementadas

Como foi referido ao longo do capítulo sobre a arquitetura, existem algumas funcionalidades que estãoparcialmente implementadas, entre as quais:

57

• Melhorar a macro descrita na secção 3.7, para facilitar a utilização das funcionalidades da liguagemConstraintGM aos utilizadores finais.

• Evoluir a implementação das funcionalidades da entidade var — entidade que acabará por subs-tituir definitivamente a entidade value.

• Melhorar a entidade circle, adicionando funcionalidades que permitam definir o plano em queo círculo está inscrito, por exemplo com um vetor normal ao plano. Neste momento só é possívelcriar círculos em planos paralelos ao plano ‘xy’.

Novas Funcionalidades

Existe ainda um conjunto de funcionalidades que são relevantes e úteis aos utilizadores finais, facili-tando assim o processo de modelação:

• Implementar outros sistemas de coordenadas, em especial, sistema de coordenadas esféricas esistema de coordenadas cilíndricas.

• Oferecer ao utilizador final a possibilidade de definir o seu próprio sistema de coordenadas e criarmacros que facilitem a sua utilização.

• Implementar as operações de translação, rotação e dimensionamento em cima dos vários sistemasde coordenadas.

• Aumentar o número de tipo de restrições de modelação disponíveis, implementando novas restri-ções e entidades geométricas. Uma vez que se pretende remover/reduzir a complexidade mate-mática do processo de modelação, as entidades mais interessantes a adicionar contêm um contextomatemático complexo para o utilizador final, o que as torna ideais para implementar na arquite-tura.

• Melhorar o suporte fornecido ao utilizador avançado na criação de funções geométricas gerais,ou seja, uma função para suportar várias entidades diferentes, invocando a função mais específicapara a entidade (equivalente ao conceito de overloading no paradigma orientado a objetos). Des-crito na secção 4.4, a função “entity-form-equation” foi implementada manualmente em tempode execução (fase 0), contudo isso impediria que extensões independentes, cuja implementaçãomodificasse esta mesma função, funcionassem em conjunto. A solução passa pela criação da fun-ção 4.4 e outras do género durante a expansão do código (fase 1). Esta solução é explicada em maisdetalhe na secção 4.4.

Operações Bidimensionais

A linguagem ConstraintGM começou por tratar modelos geométricos bidimensionais, mas rapida-mente se percebeu a importância da modelação tridimensional. Por isso, durante todo o projeto houvea preocupação de implementar o sistema num modelo tridimensional.

Contudo, o utilizador avançado pode necessitar implementar funções/construções geométricas que sófuncionam em duas dimensões. É importante criar uma macro para o ajudar na criação dessas funções.Esta macro será responsável por gerar o código necessário de validação, verificando se todas entidadesgeométricas envolvidas se situam no mesmo plano.

58

Se as entidades geométricas não estiverem no plano ‘xy’, esta macro deveria ser capaz de criar um sis-tema de coordenadas que faz a transposição do plano das entidades para o plano ‘xy’. Desta forma asoperações bidimensionais podem ser disponibilizadas para qualquer plano, sem alteração à implemen-tação das operações.

Integração com Bibliotecas de Funções Geométricas

Na secção 3.2 é apresentada a parte das arquiteturas referentes a BFG. As funções foram implementadasem Racket, uma vez que não existem funções geométricas implementadas na linguagem de programa-ção usada, disponibilizando assim a qualquer programador de Racket a capacidades de trabalhar comrestrições geométricas. Além disso, a BFG foi criada para fins demonstrativos e de benchmark, de formaa desmontar as vantagens e desvantagens dos dois solvers.

Ainda na secção 3.2 é referido que a BFG podia ser integrada com bibliotecas de outras linguagens, comopor exemplo a biblioteca CGAL, usando módulos que permitem integrar linguagens no Racket. Porexemplo, “Python for DrRacket” [22] e “P2R - Processing to Racket” [23] são exemplos destes módulos,que permitem usar respetivamente ‘packages’ de Python e Processing em Racket.

Integração com outros Sistemas de Cálculo Matemático

Outro aspeto é a integração do NCM com outros sistemas de computação algébrica e manipulação sim-bólica, como o Mathematica, permitindo ao utilizador a escolha do sistema de cálculo mais adequadoao problema. Na arquitetura da linguagem foram considerados aspetos a fim de garantir a indepen-dência do NCM na utilização de símbolos matemáticos no código, de forma a garantir que o códigocriado pelo utilizador não fique dependente do sistema de cálculo. É importante não disponibilizarfuncionalidades que dependam das especificidades do sistema de resolução matemática, sem que o uti-lizador esteja restringido na utilização das funcionalidades de um sistema cálculo específico. Emboraseja desaconselhado, o utilizador pode quer usar as funcionalidades específicas de um sistema de cál-culo matemático, por isso pretendemos que este seja capaz de o fazer de forma consciente. A maneiramais correta de o fazer passa pela disponibilização das funcionalidades em módulos separados ou sub-módulos que o utilizador terá que importar no seu código em conjunto com o módulo principal dalinguagem ConstraintGM.

Além disso, há sempre a possibilidade de um determinado sistema de cálculo conseguir resolver siste-mas de equações que outros ou mesmo versões anteriores do mesmo não consigam. Assim demonstra-seas vantagens em o utilizador ter o poder de escolha do sistema de cálculo em vez de limitar logo à par-tida. A escolha dos sistemas de cálculo a serem ou não usados, seria uma configuração inicial no nossosistema.

Em alternativa, a utilização simultânea de vários sistemas de cálculo pode-se revelar interessante porquedemonstrou-se serem complementares nas capacidades, isto é, uns são melhores para certos problemasdo que outros e vice-versa. Numa solução deste tipo, os sistemas de cálculo computavam o problemade forma concorrente até que o mais rápido devolvesse o resultado, o qual seria usado. Podemos aindadirecionar o problema à escolha do núcleo, escolhendo heuristicamente o método mais adequado pararesolver cada um dos problemas, à semelhança do CPLEX [21].

A primeira escolha enquanto sistema de cálculo matemático foi o Maxima, por ser um sistema de cál-culo de contexto geral, gratuito, código aberto, implementado numa linguagem descendente de LISP, e

59

principalmente pela capacidade de resolução de problemas matemáticos ao nível de outras ferramentas.Contudo, existe a necessidade de medir a sua capacidade e performance desenvolvendo um cenário debenchmark de modo a comparar o tempo de computação e a sua capacidade de resolução de sistemas deequações representantes de problemas geométricos. Para tal, é necessário previamente integrar outrossistemas de cálculo matemático na arquitetura.

Otimizações

Resolução do problema de comunicação

Na subsecção 3.3.2 foi identificado um problema no Maxima, uma vez que este não garante a serializaçãocompleta para o canal de comunicação. Verificou-se ainda que este comportamento não é constantequando comparado entre os sistemas operativos Windows e Linux. De modo a forçar a serializaçãopor parte do Maxima, uma chamada adicional é efetuada (“:lisp $linenum n”). A chamada interagediretamente com o interpretador de Lisp do Maxima, onde este problema não existe.

Esta solução não implica qualquer alteração ao Maxima, contudo suspeita-se que o problema seja sim-ples de resolver no lado do Maxima. Eventualmente, faltará invocar o método flush ou equivalente emdeterminados modos de comunicação.

Caso este problema seja resolvido, todo o código associado a esta solução encontrada pode ser removido,reduzindo, assim, para metade o número de chamadas efetuadas ao sistema computação algébrica emanipulação simbólica.

Problemas Geométricos Recorrentes

Outra possível otimização encontra-se nos casos onde o problema geométrico se repete. Esta otimizaçãoconsiste em criar, durante a execução, uma função nativa da linguagem Racket capaz de realizar oscálculos necessários para a resolução do problema geométrico.

Segue uma possível solução. Começa-se por converter o problema geométrico que se repete num pro-blema matemático, de forma semelhante à resolução de qualquer outro problema geométrico, mas com aexceção de que em vez de usar imediatamente todos os valores conhecidos, até então, nas equações, usa-se variáveis para valores passíveis de serem alterados em cada iteração desse padrão. De seguida, usa-seo sistema de computação algébrica e manipulação simbólica para resolver o problema matemático emordem às variáveis que se pretende obter. De seguida a expressão matemática obtida como solução étraduzida automaticamente em código Racket equivalente. Com isto evita-se invocar o sistema de cál-culo em cada iteração do padrão, resolvendo as iterações do padrão nativamente na linguagem, semtodo o elevado custo de geração das equações, e de comunicação e computação do sistema de cálculo.

Contudo, é necessário detetar esses padrões, sendo o mais simples de implementar e igualmente útil adisponibilização ao utilizador de funcionalidades na própria linguagem para construir padrões geomé-tricos. A função gerada poderia ser disponibilizada na BFG.

Reexecução do Código

Durante a implementação e a depuração do código, o utilizador final executa muitas vezes o programa,introduzindo alterações locais. Contudo, a maior parte do modelo geométrico não é afetado com essas

60

pequenas alterações. Isto é especialmente evidente ao observar-se a metodologia usada pelos arquite-tos. Eles investem tanto ou mais tempo a ‘afinar’ o modelo geométrico do que a criá-lo, introduzindopequenas variações nos valores dos argumentos/parâmetros das funções geométricas.

Em cada reexecução, o sistema de computação algébrica e manipulação simbólica é inicializado e osmesmos sistemas de equações são resolvidos com os mesmos valores, exceto reduzidas exceções.

Ao usar apenas a parte funcional da linguagem do sistema de cálculo matemático (com a exceção deparâmetros de configuração que podem ser executados diversas vezes), verifica-se a propriedade daidempotência1, ou seja, as funções não criam efeitos secundários. Assim, é possível, não só retornarimediatamente os resultados anteriormente calculados e guardados em cache, mas também manter a ins-tância do sistema de cálculo persistente entre as execuções, evitando o tempo de inicialização. Simples-mente simulam-se as chamadas ao NCM, uma vez que a ordem de execução não influência, devolve-seo resultado anteriormente calculado caso esteja no histórico. Caso contrário, segue a execução normal.Só é necessário garantir que o REPL (read–eval–print loop) da aplicação do sistema de cálculo está numestado consistente, ou seja, que o interpretador do sistema de cálculo terminou a última interpretaçãosem erros e que está a espera da próxima instrução.

Considerações Futuras

Para trabalho futuro, considerou-se igualmente importante a criação de novas restrições e entidadesgeométricas a partir da descrição de Ontologia de Geometria Descritiva, e vice-versa. Uma vez que ameta-informação guardada nas estruturas auxiliares das macros é semelhante à informação contida nasOntologias, estas podiam ser usadas para preencher as estruturas auxiliares, sendo então usadas pelasmacros, durante a fase 1, para expandir o código, criando funções e entidades geométricas para a fase 0.

ConstraintGM

O projeto desenvolvido durante a realização da tese está disponível no seguinte link: https://bitbucket.org/FabioPinheiro/geometric-constraints

1Idempotência: “ f (x) = yU f (x′) = y′Ux = x′ => y = y′”

61

62

Bibliografia

[1] Harry George Mairson. Functional geometry and the traité de lutherie: Functional pearl. In ACMSIGPLAN Notices, volume 48, pages 123–132. ACM, 2013.

[2] António Menezes Leitão. Programação para arquitectura. Rosetta manual, 2012.

[3] José Lopes and António Leitão. Portable Generative Design for CAD applications. 2011.

[4] Eukleides - A geometry drawing language. From Eukleides Web Page: http://www.eukleides.org. Accessed: 2015-05-20.

[5] Till Tantau. Tikz & pgf: Manual for version 2.10, 2012.

[6] Alan Borning. The programming language aspects of thinglab, a constraint-oriented simulationlaboratory. ACM Transactions on Programming Languages and Systems (TOPLAS), 3(4):353–387, 1981.

[7] GeoSolver. From GeoSolver Web Page: http://geosolver.sourceforge.net. Accessed: 2015-05-20.

[8] Andrew Payne and Rajaa Issa. The grasshopper primer. Zen ‘Edition. Robert McNeeI & Associates,2009.

[9] O. Le Roux, V. Gaildrat, and R. Caube. Constraint satisfaction techniques for the generation phasein declarative modeling. In Muhammad Sarfraz, editor, Geometric Modeling: Techniques, Applications,Systems and Tools, pages 193–215. Springer Netherlands, 2004.

[10] Francesca Rossi, Peter Van Beek, and Toby Walsh. Handbook of constraint programming. Elsevier,2006.

[11] Chris Voudouris and Edward Tsang. Partial constraint satisfaction problems and guided local se-arch. Proc., Practical Application of Constraint Technology (PACT’96), London, pages 337–356, 1996.

[12] Hilderick A.; Bronsvoort Willem F. de Regt, Rogier; van der Meiden. A workbench for geometricconstraint solving. Computer-Aided Design and Applications, 5(1-4):471–482, 2008.

[13] Maurice Dohmen. A survey of constraint satisfaction techniques for geometric modeling. Compu-ters & Graphics, 19(6):831–845, 1995.

[14] Chee-Keng Yap. Towards exact geometric computation. Computational Geometry, 7(1):3–23, 1997.

[15] Menelaos I. Karavelas. Exact geometric and algebraic computations in cgal. In Komei Fukuda,Jorisvander Hoeven, Michael Joswig, and Nobuki Takayama, editors, Mathematical Software–ICMS2010, volume 6327 of Lecture Notes in Computer Science, pages 96–99. Springer Berlin Heidelberg,2010.

63

[16] Eric Berberich and Eric Berberich. CGAL–reliable geometric computing for academia and industry.In Hoon Hong and Chee Yap, editors, Mathematical Software–ICMS 2014, volume 8592 of LectureNotes in Computer Science, pages 191–197. Springer Berlin Heidelberg, 2014.

[17] Hilderick A. Van Der Meiden and Willem F. Bronsvoort. A non-rigid cluster rewriting approach tosolve systems of 3d geometric constraints. Computer-aided design, 42(1):36–49, 2010.

[18] Gus Lopez, Bjorn Freeman-Benson, and Alan Borning. Kaleidoscope: A constraint imperativeprogramming language. In Constraint Programming, pages 313–329. Springer, 1994.

[19] António Leitão, Luís Santos, and José Lopes. Programming languages for generative design: Acomparative study. International Journal of Architectural Computing, 10(1):139–162, 2012.

[20] Harold Abelson, Gerald Jay Sussman, and Julie Sussman. Structure and interpretation of computerprograms. Justin Kelly, 1996.

[21] IBM IBM ILOG CPLEX. High-performance mathematical programming engine. International Busi-ness Machines Corp, 2010.

[22] Pedro Palma Ramos and António Menezes Leitão. Implementing Python for DrRacket. In MariaJoão Varanda Pereira, José Paulo Leal, and Alberto Simões, editors, 3rd Symposium on Languages,Applications and Technologies, volume 38 of OpenAccess Series in Informatics (OASIcs), pages 127–141,Dagstuhl, Germany, 2014. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[23] Hugo Correia and António Menezes Leitão. Combining processing with racket. In Languages,Applications and Technologies, pages 101–112. Springer, 2015.

[24] Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr. The cgalkernel: A basis for geometric computation. In MingC. Lin and Dinesh Manocha, editors, AppliedComputational Geometry Towards Geometric Engineering, volume 1148 of Lecture Notes in ComputerScience, pages 191–202. Springer Berlin Heidelberg, 1996.

[25] Line-line intersection. From MathWorld–A Wolfram Web Resource: http://mathworld.wolfram.com/Line-LineIntersection.html. Accessed: 2016-04-27.

[26] Mark Berg, Marc Kreveld, Mark Overmars, and Otfried Cheong Schwarzkopf. Computational Geo-metry: Algorithms and Applications, chapter Computational Geometry, pages 1–17. Springer BerlinHeidelberg, Berlin, Heidelberg, 2000.

[27] Circle-line intersection. From MathWorld–A Wolfram Web Resource: http://mathworld.

wolfram.com/Circle-LineIntersection.html. Accessed: 2016-04-27.

[28] Art Johnson, Richard Rhoad, George Milauskas, and Robert Whipple. Geometry for enjoymentand challenge, rev. ed.(s), 1991.

[29] Erich Hartmann. Geometry and algorithms for computer aided design. Darmstadt University ofTechnology, 2003.

[30] Matthew Flatt. Submodules in racket: you want it when, again? In ACM SIGPLAN Notices, vo-lume 49, pages 13–22. ACM, 2013.

[31] Matthew Flatt. Composable and compilable macros:: you want it when? In ACM SIGPLAN Notices,volume 37, pages 72–83. ACM, 2002.

64

[32] Matthew Flatt. Binding as sets of scopes. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACTSymposium on Principles of Programming Languages, pages 705–717. ACM, 2016.

[33] Sam Tobin-Hochstadt, Vincent St-Amour, Ryan Culpepper, Matthew Flatt, and Matthias Felleisen.Languages as libraries. In ACM SIGPLAN Notices, volume 46, pages 132–141. ACM, 2011.

[34] George Edward Martin. Geometric constructions. Springer Science & Business Media, 2012.

65

66

Apêndice A

Listagem de Funções das Entidades

• Construtores que estão disponíveis aos utili-zadores, para criar instâncias das entidadesgeométricas:

– new-var

– new-value

– new-point

– new-point-unset

– new-form

– new-form-unset

– new-line

– new-circle

– new-constraints

– new-sphere

• Funções para criar instâncias das entidadesgeométricas à imagem de outras entidades:

– copy-var

– copy-value

– copy-point

– copy-form

– copy-line

– copy-circle

– copy-constraints

– copy-sphere

• Funções para verificar o tipo da entidade. Afunção entity-get-type devolve o símbolocorrespondente da entidade geométrica.

– entity?

– var?

– value?

– point?

– form?

– line?

– circle?

– constraints?

– sphere?

• Funções para consultar os campos das enti-dades geométricas:

– entity-id

– var-x

– var-y

– var-z

– point-x

– point-y

– point-z

– form-x

– form-y

– form-z

– line-start

– line-end

– line-direction

– line-length

– line-subtype

– circle-center

– circle-radius

67

– constraints-math

– constraints-entity

– sphere-center

– sphere-radius

• Funções para modificar os campos das enti-dades geométricas:

– set-entity-id!

– set-var-x!

– set-var-y!

– set-var-z!

– set-point-x!

– set-point-y!

– set-point-z!

– set-form-x!

– set-form-y!

– set-form-z!

– set-line-start!

– set-line-end!

– set-line-direction!

– set-line-length!

– set-line-subtype!

– set-circle-center!

– set-circle-radius!

– set-constraints-math!

– set-constraints-entity!

– set-sphere-center!

– set-sphere-radius!

• Funções para consultar os sub-campos dasentidades geométrica:

– point-y-v

– point-z-set?

– point-z-n

– point-z-s

– point-z-v

– point-y-s

– point-x-set?

– point-x-n

– point-x-s

– point-x-v

– point-y-set?

– point-y-n

– form-y-s

– form-y-refs

– form-y-v

– form-z-s

– form-z-refs

– form-x-refs

– form-x-s

– form-x-v

– form-z-v

– line-direction-z-v

– line-direction-z

– line-direction-y-s

– line-direction-x-set?

– line-direction-x-n

– line-direction-x-s

– line-direction-x-v

– line-direction-y-set?

– line-direction-y-n

– line-direction-x

– line-length-set?

– line-length-n

– line-length-s

– line-length-v

– line-start-y

– line-start-y-v

– line-start-z-set?

– line-start-z-n

– line-start-z-s

– line-start-z-v

– line-start-z

– line-start-y-s

– line-start-x-set?

– line-start-x-n

– line-start-x-s

– line-start-x-v

– line-start-y-set?

– line-start-y-n

– line-start-x

68

– line-end-y

– line-end-y-v

– line-end-z-set?

– line-end-z-n

– line-end-z-s

– line-end-z-v

– line-end-z

– line-end-y-s

– line-end-x-set?

– line-end-x-n

– line-end-x-s

– line-end-x-v

– line-end-y-set?

– line-end-y-n

– line-end-x

– line-direction-y

– line-direction-y-v

– line-direction-z-set?

– line-direction-z-n

– line-direction-z-s

– circle-radius-n

– circle-center-y

– circle-center-y-v

– circle-center-z-set?

– circle-center-z-n

– circle-center-z-s

– circle-center-z-v

– circle-center-z

– circle-center-y-s

– circle-center-x-set?

– circle-center-x-n

– circle-center-x-s

– circle-center-x-v

– circle-center-y-set?

– circle-center-y-n

– circle-center-x

– circle-radius-set?

– circle-radius-s

– circle-radius-v

– constraints-math-v

– constraints-math-refs

– constraints-math-s

– sphere-radius-n

– sphere-center-y

– sphere-center-y-v

– sphere-center-z-set?

– sphere-center-z-n

– sphere-center-z-s

– sphere-center-z-v

– sphere-center-z

– sphere-center-y-s

– sphere-center-x-set?

– sphere-center-x-n

– sphere-center-x-s

– sphere-center-x-v

– sphere-center-y-set?

– sphere-center-y-n

– sphere-center-x

– sphere-radius-set?

– sphere-radius-s

– sphere-radius-v

• Funções genéricas da class entityGen, definidas através das capacidades generics do Racket. Asmacros entity-type e entity-build definem automaticamente as quatro funções seguintes, es-pecializadas para cada uma das entidades geométricas.

– entity-copy - Cria uma nova instância da entidade geométrica a imagem da entidade passadacomo argumento.

– entity-get-type - Devolve um símbolo que representa a entidade geométrica.

– entity-map-fields - Mapeia a função passada como argumento aos campos da entidade, simi-lar à função map do Racket.

– entity-recursive-map-fields - Similar à função entity-map-fields, mas recursiva para os

69

campos que são entidades.

• Funções especiais de value e var.

– flat-values - Transforma listas e sub-listas com instâncias de value numa lista única, equiva-lente a função flat do Racket; é usada em conjunto com a função genérica “entity-recursive-map-fields”.

– update-values - Recebe uma lista de pares (key-value) e atualiza as instâncias de values cujoid é igual à key, com os valores correspondentes; é usada para refletir no modelo as soluçõesdo Maxima.

– flat-vars - Semelhante à função flat-values mas para instâncias de var.

– update-vars - Semelhante à função update-values mas para instâncias de var.

– var-independent? - Verifica se a instância de var é independente de todas as outras instâncias.

70

Glossário

BFG Biblioteca de Funções Geométricas. 25, 26, 42, 43, 47–49, 55, 56, 59, 60

BIM Building Information Model. 9, 10

CAD Computer-Aided Design. 2–4, 9, 10

CGAL Computational Geometry Algorithms Library. 8, 26, 59

CSOP Constraint satisfaction optimization problem. 6

CSP Constraint Satisfaction Problem. 5–7, 9, 13, 14, 16, 20, 27

DoF Degree of Freedom. 6, 13–15, 56

DSL Domain-Specific Language. 19

NCM Núcleo de Cálculo Matemático. 20, 23, 25, 27, 28, 30, 31, 35–37, 39, 40, 42, 43, 47–50, 53–56, 59, 61

PCSP Partial constraint satisfaction problem. 6