BRPI0808986A2

BRPI0808986A2 - Geração automática de instruções de construção para construção de modelos de elemento

Info

Publication number: BRPI0808986A2
Application number: BRPI0808986-8A
Authority: BR
Inventors: Jakob Sprogoe Jakobsen; Jesper Martin Enrstvang; Ole Juul Kristensen; Jacob Allerelli
Original assignee: Lego As
Priority date: 2007-03-16
Filing date: 2008-03-14
Publication date: 2014-09-09
Also published as: KR20090125272A; US7979251B2; JP2010521727A; CA2680256C; BRPI0808986B1; CA2680256A1; HK1138092A1; DK2135222T3; US20080228450A1; CN101675458A; CN101675458B; WO2008113768A1; EP2135222B1; ATE479167T1; EP2135222A1; MX2009009733A; DE602008002331D1; ES2351272T3; KR101470665B1

Description

Relatório Descritivo da Patente de Invenção para "GERAÇÃO AUTOMÁTICA DE INSTRUÇÕES DE CONSTRUÇÃO PARA CONSTRUÇÃO DE MODELOS DE ELEMENTO".

Campo Técnico

A presente invenção refere-se à geração de instruções de cons

trução para construção de modelos de elementos.

Sumário

Há vários tipos conhecidos de conceitos de modelagem de conjuntos de brinquedo de construção física. Conceitos especialmente modula10 res ou semimodulares são muito populares visto que fornecem uma experiência de brincar interessante e um desafio. Tipicamente, esses conceitos fornecem um conjunto de elementos de construção pré-fabricados que podem ser interconectados entre si em algum modo predeterminado por meio de elementos de conexão dos elementos pré-fabricados. Os elementos de 15 construção pré-fabricados lembram objetos bem conhecidos adaptados a uma tarefa de modelagem específica. Desse modo, por exemplo, na construção de um modelo de uma casa os elementos de construção podem se parecer com tijolos de parede, telhas, portas e janelas. O objetivo de selecionar os elementos de construção desse modo é que o trabalho envolvido 20 com a construção de um modelo de uma casa é reduzido significativamente em comparação com uma situação onde todos os detalhes da casa devem ser definidos cada vez em que um novo modelo deve ser feito. Entretanto, a liberdade total na construção de uma casa ou outro objeto é equilibrado pela simplicidade de construir o modelo.

Por exemplo, os conjuntos de construção de brinquedo disponí

veis sob o nome LEGO compreendem uma pluralidade de tipos diferentes de elementos de construção interconectáveis com protuberâncias e cavidades correspondentes como elementos de conexão. Os elementos de conexão são dispostos de acordo com padrões de grade regulares, desse modo per30 mitindo uma ampla variedade de interconexões entre os elementos de construção .

Tipicamente, tais conjuntos de construção de brinquedo compreendem um conjunto de elementos de construção apropriado para criar um ou mais modelos de construção, por exemplo, um animal, um robô, ou outra criatura, um carro, um avião, uma espaçonave, um edifício ou similares. Tipicamente, um conjunto de construção inclui ainda instruções de cons5 trução impressas ou instruções de montagem que ilustram como construir um certo modelo a partir dos elementos de construção do conjunto. Não obstante, é uma característica interessante de tais conjuntos de construção que os mesmos inspirem as crianças a criarem seus próprios modelos.

Tipicamente, as instruções de construção encerradas em um 10 conjunto de construção de brinquedo compreendem uma seqüência de imagens que ilustram etapa por etapa como e em qual ordem acrescentar os elementos de construção ao modelo. Tais instruções de construção têm a vantagem de que são fáceis de seguir, mesmo para crianças sem grande experiência em conjuntos de construção de brinquedo e/ou sem habilidade 15 de leitura.

Geralmente uma instrução de construção para um modelo pode ser considerada como uma seqüência de etapas e subetapas de construção na qual elementos de construção são montados. A seqüência inicia com um ou mais elementos de construção iniciais e desenvolve através de uma série 20 de etapas até a montagem total que é uma construção do modelo. Em cada etapa um elemento de construção único ou uma submontagem de elementos de construção é acrescentado. Para fins da presente descrição, o termo submontagem se refere a um subconjunto de elementos de construção interconectados do modelo de elemento de construção. O acréscimo de uma 25 submontagem em vez de um elemento de construção pode envolver, desse modo, uma instrução de construção subordinada para aquela submontagem a ser acrescentada à instrução de construção principal. Para fins da presente descrição, uma tal instrução de construção subordinada também será denominada uma subetapa. Desse modo, a seqüência de etapas pode ser ge30 ralmente representada como uma árvore ramificada de etapas onde cada ramo contém instruções de construção subordinadas.

Anteriormente, tais instruções de construção foram geradas manualmente, por exemplo, por determinar manualmente etapas de construção razoáveis, desenhar as instruções correspondentes em um sistema CAD, e finalmente imprimir as instruções desse modo geradas. Embora tais instruções de construção sejam de alta qualidade, isto é, sejam fáceis de seguir, 5 os processos de produção acima têm a desvantagem de que exigem grande habilidade e são de muito esforço. Como conseqüência, instruções de construção existem somente tipicamente para modelos de elemento de construção projetados pelo fabricante dos elementos de construção. Em particular, os métodos da técnica anterior acima para gerar instruções de construção 10 não são apropriados para crianças que desejam produzir instruções de construção para seus próprios modelos, o que permitiria que eles compartilhassem seus modelos com seus amigos.

Mais recentemente, instruções de construção foram geradas em forma eletrônica em vez de impressa. Em particular, instruções de constru15 ção animadas onde as etapas de construção mais complicadas são animadas. A produção de tais instruções de construção, entretanto, ainda envolve um projeto e um desenho/animação das etapas de construção por projetistas especializados.

Em um sistema complexo como o sistema LEGO, o número de 20 instruções de construção possíveis para um modelo cresce exponencialmente com o número de elementos de construção no modelo. Consequentemente, é geralmente um problema para um processo de instrução de construção automática determinar um conjunto de instruções de alta qualidade a partir do número virtualmente infinito de instruções de construção possíveis para 25 um dado modelo. Desse modo, é desejável fornecer um processo automatizado que gere instruções fáceis de seguir, trabalhável mesmo para modelos complexos. É adicionalmente desejável fornecer um tal processo que gera instruções de construção em um tempo razoável em um hardware computacional razoável.

É adicionalmente desejável fornecer um método para gerar ins

truções de construção que seja apropriado para crianças que desejam produzir instruções de construção para seus próprios modelos, o que permitiria que elas compartilhassem seus modelos com seus amigos e ainda aperfeiçoassem a experiência de brincar. Em particular, é desejável fornecer métodos que exigem pouca ou nenhuma interação de usuário e entradas que sejam prontamente disponíveis para o usuário.

5 O projeto de instruções de construção etapa por etapa eficazes e

fáceis de entender foi também o tema de pesquisa. A publicação de Internet "Designing Effective step-by-step assembly instructions", de M. Agrawala e outros, recuperado de http://qraphics.stanford.edu/papers/assemblv instructions/. descreve princípios de projeto para instruções de montagem eficazes com base em psicologia cognitiva. Esse artigo descreve ainda um sistema computadorizado para gerar instruções de montagem com base em informações sobre cada um dos objetos a ser montado, a orientação de montagem e o ponto de vista de câmera para renderização gráfica, informações de agrupamento, informações sobre prendedores, a importância das partes, simetrias, e sobre limitações na ordem de montagem. Com base nessa entrada, o sistema calcula uma seqüência de etapas de montagem com base em um algoritmo de busca extensa levando em consideração as limitações dadas. É um problema do sistema da técnica anterior acima que é computacionalmente caro e requer dados de entrada complicados, desse modo exigindo um alto grau de pensamento abstrato do usuário.

O pedido de patente internacional publicado WO 2005/124696 descreve um processo automatizado para gerar instruções de construção para um modelo de construção virtual no qual as instruções de construção utilizam uma ordem seqüencial de etapas determinada pela ordem de etapas 25 de construção utilizada por um usuário durante construção do modelo virtual em um ambiente de construção virtual. Embora esse método da técnica anterior forneça um processo automatizado fácil de utilizar, permanece um problema aumentar a qualidade de instruções de construção automaticamente geradas.

É descrito aqui um método implementado por computador de ge

rar instruções de construção para um modelo de elemento de construção, o modelo incluindo uma pluralidade de elementos de construção, as instruções de construção sendo indicativas de uma ordem seqüencial de etapas de construção para construir o modelo de elemento e construção, cada etapa de construção incluindo acrescentar pelo menos um elemento de construção ao modelo de elemento de construção; o método compreendendo:

5 - determinar, de uma representação digital do modelo de ele

mento de construção, pelo menos uma seqüência de etapas de desconstrução para pelo menos parcialmente desconstruir o modelo de elemento de construção em elementos de construção, cada etapa de desconstrução incluindo retirar pelo menos um elemento de construção a partir do modelo de elemento de construção;

- determinar pelo menos uma etapa de construção da ordem seqüencial de etapas de construção com base pelo menos em uma pluralidade de etapas de desconstrução.

Consequentemente, foi percebido que uma seqüência de etapas de construção pode ser determinada eficientemente por determinar uma ou mais seqüências de etapas de desconstrução.

Uma desconstrução de construção para um modelo pode ser considerado como um processo de seqüência/interativo de etapas e subetapas no qual elementos de construção são desmontados. A seqüência inicia 20 com o modelo completo e prossegue através de uma série de etapas. Em uma desconstrução completa o processo continua até que todos os elementos de construção tenham sido desconectados do modelo, enquanto em uma desconstrução parcial, o processo termina quando somente um modelo de parte residual predeterminada permanece. Em cada etapa um único elemen25 to de construção ou uma submontagem de elementos de construção é desconectado. A desconexão de uma submontagem em vez de um elemento de construção pode envolver, desse modo, uma desconstrução de construção subordinada para aquela submontagem a ser associada à desconstrução de construção principal. Tal desconstrução de construção subordinada também 30 será denominada uma subetapa. Desse modo, similar à construção de edificação, a seqüência de etapas do processo de desconstrução é geralmente uma árvore ramificada de etapas onde cada ramo contém desconstruções de construção subordinadas.

Quando uma desconstrução de construção pode ser encontrada, essa informação pode ser utilizada no processo de gerar uma seqüência de construção. Consequentemente as etapas de construção podem ser deter5 minadas responsivas a uma etapa de determinar uma seqüência de desconstrução. Além disso, verificou-se que a busca por uma seqüência de desconstrução que atenda certos critérios de seleção é possível com recursos computacionais razoáveis e resulta em instruções de construção de alta qualidade.

Verificou-se ainda que as instruções de construção geradas por

esse método computacionalmente simples são fáceis de entender por usuários, em particular crianças.

Além disso, como a única entrada da instrução de construção é a representação digital de um modelo de elemento de construção, por e15 xemplo, como gravado durante um processo de geração de modelo virtual, é fácil para um usuário gerar as instruções de construção sem exigir que o usuário possua habilidades de projeto ou conhecimento abstrato sobre geometria, limitações, etc. Adicionalmente, a geração das instruções de construção é independente da ordem na qual o usuário construiu efetivamente o 20 modelo virtual. Isso pode ser vantajoso, uma vez que um ambiente de construção virtual pode permitir a execução de etapas de construção em uma ordem que pode ser difícil ou mesmo impossível de executar com um modelo de mundo real físico.

Em algumas modalidades, o método compreende:

- determinar, a partir de uma representação digital do modelo de

elemento de construção, uma ordem seqüencial de etapas de desconstrução para desconstruir o modelo de elemento de construção em elementos de construção, cada etapa de desconstrução incluindo retirar pelo menos um elemento de construção do modelo de elemento de construção;

- inverter a ordem seqüencial determinada de etapas de des

construção para obter a ordem seqüencial de etapas de construção.

Se uma desconstrução de construção pode ser encontrada, a mesma pode ser revertida, fornecendo uma instrução de construção, exatamente como é possível desconstruir um modelo passando através de uma instrução de construção reversa. Consequentemente, uma seqüência de etapas de construção pode ser determinada, de forma eficiente, por determi5 nar uma ou mais seqüências de etapas de desconstrução e então reverter a ordem de etapas de desconstrução para obter uma seqüência de etapas de construção. É uma vantagem que esse processo exija somente a geração de uma seqüência de desconstrução única.

Em modalidades alternativas, o método compreende executar um processo iterativo, onde uma iteração do processo iterativo compreende:

- obter uma ordem seqüencial de etapas de construção que resulte de uma iteração anterior, a ordem seqüencial de etapas de construção resultando em um primeiro modelo em peças;

- determinar uma etapa de construção subsequente indicativa de uma conexão de pelo menos um elemento de construção subsequente ao

primeiro modelo em peças resultando em um segundo modelo em peças.

- determinar se o modelo de elemento de construção é desconstrutível por uma seqüência de etapas de desconstrução para desconstruir o modelo de elemento de construção resultando no segundo modelo em pe

ças;

- se o modelo de elemento de construção for determinado como sendo desconstrutível pela seqüência de etapas de desconstrução para desconstruir o modelo de elemento de construção resultando no segundo modelo em peças, anexando à etapa de construção subsequente determinada à

ordem seqüencial obtida de etapas de construção.

Consequentemente, nessa modalidade, cada etapa de construção é determinada de tal modo que o modelo em peças resultante pode ser obtido por uma desconstrução parcial do modelo completo. Como conseqüência, um processo eficiente para gerar instruções de construção é forne30 cido por um processo de construção onde uma desconstrução do modelo completo até o estágio de construção atual é simulada em cada etapa de construção. Essa modalidade trabalha por construção (iniciando a partir de um conjunto vazio de blocos, terminando com o modelo completo), em vez de ser totalmente baseada em uma desconstrução. Uma vez que esse é um modo mais intuitivo para um usuário considerar instruções de construção, 5 permite modos poderosos e de uso mais fácil de se permitir que usuários interajam com o processo de gerar instruções de construção. Um exemplo de uma interação de usuário poderia ser fazer objeções a qualquer bloco sugerido, e obter uma sugestão alternativa. Essa interação simples permite, na realidade, que usuários gerem instruções de construção particularmente 10 de alta qualidade em um período de tempo muito curto e necessidade mínima de interação de usuário. Além disso, o gerador pode assegurar que limitações difíceis nunca são violadas, e consequentemente não importa o que o usuário faça objeção, somente sugestões razoáveis são feitas.

Por conseguinte, em uma modalidade, a etapa de determinar uma etapa de construção subsequente pode incluir receber uma entrada de usuário, por exemplo, na forma de pelo menos uma entre sugestão, aprovação e rejeição de uma etapa de construção.

A etapa de determinar se o modelo de elemento de construção é desconstrutível por uma seqüência de etapas de desconstrução para des20 construir o modelo de elemento de construção resultando no segundo modelo em peças pode incluir a etapa de determinar se o modelo de elemento de construção é de tal modo desconstrutível por uma seqüência de etapas de desconstrução, onde cada etapa de desconstrução é selecionada por um ou mais conjunto predeterminado de critérios de seleção. Consequentemente, 25 um método eficiente é fornecido que foi considerado como fornecendo instruções de construção de alta qualidade.

Em algumas modalidades, a determinação da ordem seqüencial de etapas de desconstrução compreende executar um processo iterativo, onde uma iteração do processo iterativo compreende:

- obter um modelo de peças anterior que resulta de uma itera

ção anterior;

determinar pelo menos um elemento de construção para desconectar do modelo de peças anterior resultando em um modelo de peças novo.

Consequentemente, o processo inicia com o modelo completo e gera uma seqüência de parte de modelo por retirar, em cada iteração, um ou 5 mais elementos de construção. Embora uma busca por instruções de construção de alta qualidade exija geralmente retrocesso, e desse modo seja computacionalmente muito caro e mesmo excessivamente caro para modelos grandes, verificou-se que a desconstrução de construção pode ser realizada por um algoritmo de uma passagem que é muito menos exigente no 10 hardware computacional.

Geralmente, em um sistema de construção complexo, como o sistema de construção de brinquedo comercializado sob o nome LEGO, pode não ser possível para alguns modelos serem desconstruídos elemento de construção por elemento de construção, porque alguns elementos de cons15 trução podem travar entre si de tal modo que nenhum elemento de construção único pode ser desconectado. Entretanto, geralmente todos os modelos podem ser desconectados por retirar, em cada etapa, um único elemento de construção ou uma submontagem de elementos de construção.

Por conseguinte, em algumas modalidades, a determinação de pelo menos um elemento de construção inclui:

determinar um conjunto de submontagens candidatas do modelo em peças anterior, cada submontagem candidata incluindo elementos de construção interconectados respectivos do modelo em peças anterior;

selecionar, de acordo com um primeiro conjunto de critérios de seleção predeterminados, um único elemento de construção ou um do conjunto determinado de submontagens candidatas para ser desconectado do modelo em peças anterior resultando no novo modelo em peças.

Consequentemente, em algumas modalidades, submontagens são tratadas como elementos de pseudoconstrução para fins da seqüência de desconstrução. Entretanto, o número de submontagens possíveis de um modelo de elemento de construção geralmente cresce exponencialmente com o número de elementos de construção no modelo. Como conseqüência, mesmo para modelos de tamanho moderado uma abordagem de parte superior para baixo para busca através de todas as submontagens possíveis e seleção, dados certos critérios, de uma submontagem a ser desconectada é computacionalmente excessivamente caro, embora uma tal abordagem pos5 sa bem ser exeqüível ao considerar exclusivamente retirada de elementos de construção únicos.

Em algumas modalidades, o método descrito aqui combina a abordagem de parte superior para baixo acima com uma abordagem parte inferior para cima para gerar submontagens candidatas para serem submeti10 das à busca parte superior para baixo. A geração de submontagem candidata pode ser realizada de acordo com um conjunto de um ou mais subprocessos geradores ou um segundo conjunto de critérios de seleção, desse modo resultando em um subconjunto de submontagens candidatas do conjunto de todas as submontagens possíveis do modelo. Consequentemente, a abor15 dagem parte inferior para cima é utilizada para aparar o espaço de busca antes de executar a abordagem parte superior para baixo computacionalmente cara.

A dissecação acima da busca de parte superior - para baixo e geração de parte inferior - para cima resulta em um processo que é computacionalmente mais barato, programaticamente mais fácil, e facilmente extensível, por exemplo, por adição de subprocessos geradores adicionais para gerar submontagens candidatas.

Além disso, a abordagem acima provê um controle aperfeiçoado, uma vez que provê um mecanismo para controlar o número de submon25 tagem candidata a gerar, desse modo fornecendo um mecanismo para equilibrar custo computacional contra qualidade das instruções de construção resultantes e para ajustar o tamanho do grupo de candidatos para quaisquer exigências de tempo e hardware dadas.

Em algumas modalidades, pelo menos um do segundo conjunto de critérios de seleção inclui determinar uma resistência de conexão da conexão de uma ou mais submontagens candidatas com o modelo em peças anterior. Consequentemente, submontagens são geradas/selecionadas de acordo com a resistência de sua conexão ao restante do modelo em peças anterior. Verificou-se que essa estratégia de seleção/geração para submontagens resulta em instruções de construção particularmente de alta qualidade.

5 Regras de seleção adicionais ou alternativas para selecionar e

ficientemente submontagens candidatas compreendem determinar alterações na direção de construção e/ou submontagens que são conectadas de forma móvel a modelo em peças anterior, por exemplo, por intermédio de uma articulação ou conexão de junção, uma corrediça, etc.

Em algumas modalidades o método compreende representar o

modelo em peças anterior por uma estrutura de dados indicativa de um gráfico, por exemplo, um gráfico não-orientado, incluindo nós indicativos dos respectivos elementos de construção do modelo em peças anterior e bordas conectando nós respectivos indicativos de conexões entre elementos de 15 construção correspondentes. Por representar o modelo em peças anterior como um gráfico, técnicas de divisão de gráfico e outras técnicas conhecidas a partir da teoria de gráfico (vide, por exemplo, "Graph Theory and its applications" de Jonathan L. Gross e Jay Yellen, Chapman & Hall/CRC, segunda edição, 2006) podem ser utilizadas para identificar eficientemente submon20 tagens candidatas apropriadas, por exemplo, por identificar nós de articulação ou pares de articulação no gráfico, de modo a identificar submontagens que são ligadas ao restante do modelo em peças anterior por um elemento de construção de articulação único ou por um par de elementos de construção. Consequentemente, um modelo de elementos de construção interco25 nectados corresponde a um gráfico conectado, e uma submontagem corresponde a um subgráfico conectado.

Os nós e/ou bordas do gráfico podem ter um ou mais atributos respectivos associados aos mesmos correspondendo a atributos dos elementos de construção e conexões correspondentes, respectivamente. Por 30 exemplo, nós do gráfico podem ter um ou mais dos seguintes atributos ligados a eles: tipo do elemento de construção, volume de elemento de construção, geometria/formato do elemento de construção, massa do elemento de construção de volume, uma caixa de limitação do elemento de construção, uma posição do elemento de construção em um sistema de coordenada, uma direção principal de construção associada ao elemento de construção, as posições, tipos, e/ou direções de elementos de conexão do elemento de 5 conexão, e/ou similares. Similarmente, bordas do gráfico podem ter um ou mais dos seguintes atributos associados a eles: tipo de conexão, resistência de conexão, direção de conexão, e/ou similares. Quando as bordas do gráfico têm valores/pesos respectivos associados a elas, indicativos da resistência de conexão respectivas das conexões, métodos de divisão de gráficos 10 particularmente eficientes, como métodos para encontrar cortes mínimos podem ser utilizados para obter instruções de construção de alta qualidade.

Em algumas modalidades, cada elemento de construção compreende um ou mais elementos de conexão adaptados para engatar-se com um ou mais elementos de conexão correspondentes de outro elemento de 15 construção para fornecer uma conexão entre o elemento de construção e o outro elemento de construção. Tais elementos de conexão podem impor restrições adicionais em possíveis colocações de elementos de construção, visto que uma conexão é somente possível entre elementos de conexão compatíveis, por exemplo, protuberâncias que se adaptam em cavidades corres20 pondentes, quando colocadas em uma posição correta em relação mútua. Cada elemento de conexão pode ter associado ao mesmo uma classe de elemento de conexão, cada classe de elemento de conexão tendo associado à mesma uma resistência de conexão. Em algumas modalidades, o método compreende determinar o valor de resistência de conexão associado de uma 25 borda que corresponde a uma conexão entre dois elementos de construção a partir pelo menos do número e classes respectivas de elementos de conexão contribuindo para a conexão correspondente. Consequentemente, um método eficiente e preciso para calcular/estimar resistências de conexão em um modelo de elemento de construção é fornecido.

Em algumas modalidades, a determinação do valor de resistên

cia de conexão associado compreende determinar a resistência de conexão a partir pelo menos do número e classes respectivas de elementos de conexão que contribuem para a conexão correspondente e a partir de um valor dos dois elementos de construção, desse modo não somente levando em consideração a resistência de conexão como também o tamanho dos elementos de construção, e desse modo se os elementos de construção são fáceis de segurar e manipular durante o processo de construção.

Em algumas modalidades, a determinação de pelo menos um elemento de construção a desconectar a partir do modelo em peças anterior resultando em um novo modelo em peças compreende computar uma ou mais funções de peso para pelo menos um de um subconjunto dos elemen10 tos de construção e um conjunto de submontagens candidatas de elementos de construção; e selecionar um entre um elemento de construção único e uma submontagem baseada em uma comparação das funções de peso computadas. Consequentemente, uma estrutura escalonável, extensível e flexível para o processo de seleção é fornecida, que pode ser modificada ou 15 estendida por funções de peso alternativas ou adicionais, e onde critérios de seleção diferentes podem ser ponderados relativamente entre si de acordo com sua importância/prioridade. As funções de peso podem incluir qualquer função apropriada de uma ou mais propriedades de um ou mais elementos de construção.

Em algumas modalidades, pelo menos uma ou mais funções de

peso tem uma gama de resultados possíveis incluindo uma primeira subfaixa indicativa de um grau de adequação para ser desconectado e uma segunda subfaixa indicativa de um grau de inadequação para ser desconectado, desse modo permitindo atribuir pesos positivos e negativos a elementos de construção e/ou submontagens.

Por conseguinte, em algumas modalidades, a seleção de um único elemento de construção ou submontagem baseada em uma comparação das funções de peso computadas inclui computar um peso total a partir de uma ou mais funções de peso computadas; onde a computação do peso 30 total inclui atribuir um valor na segunda faixa ao peso total, se pelo menos uma das funções de peso computadas tiver um resultado na segunda faixa, desse modo fornecendo uma veto-estratégia que evita que elementos de construção e/ou submontagens sejam desconectados que não atendam certos critérios, embora possam obter um elevado peso a partir de outras funções de peso.

Os exemplos de funções de peso que se verificou resultar em 5 instruções de construção de alta qualidade incluem uma função de peso que determina se um elemento de construção ou submontagem é fisicamente desprendível ou se a direção de desconexão do elemento de construção ou submontagem é, por exemplo, bloqueada por outras partes do modelo. Por exemplo, uma tal função de peso pode ser eficientemente calculada por 10 computar uma geometria estirada do elemento de construção ou submontagem.

Outro exemplo de tais funções de peso inclui uma função de peso que atribui um peso inferior a elementos de construção de articulação e/ou elementos de construção que são compreendidos em um par de articu15 lações de elementos de construção ou submontagens, de modo a evitar dividir o modelo em modelos em peças separadas/desconectadas. Quando as funções de peso incluem uma função de peso que diminui com o número de outros elementos de construção com os quais o elemento de construção ou submontagem é - diretamente ou através de outros elementos de constru20 ção - conectado, é assegurado que partes separadas pequenas sejam rapidamente removidas do modelo, se ocorrer.

Quando uma das funções de peso é uma função de uma resistência de conexão de conexões entre elementos de construção de uma submontagem, elementos de construção e submontagens que são facilmen25 te desconectáveis a partir do modelo restante podem ser favorecidas. Em particular, verificou-se que uma função de peso que atribui um peso mais elevado a elementos de construção e submontagens tendo uma conectividade interna mais forte e uma conectividade externa mais fraca, resultam em instruções de construção de qualidade elevada. Além disso, em uma tal fun30 ção de peso, a resistência de conectividade pode ser calculada como uma resistência em relação ao volume dos elementos de construção interconectados ou submontagens. Ainda exemplos adicionais de funções de peso apropriadas incluem funções de peso que são funções de pelo menos uma propriedade do elemento de construção ou submontagem e uma propriedade de um elemento de construção ou submontagem desconectada durante uma iteração 5 anterior do processo iterativo, desse modo permitindo favorecer a retirada de submontagens ou elementos de construção simetricamente posicionados, elementos de construção ou submontagens que estão localizados em uma proximidade mútua, e/ou similar. Os exemplos de tais propriedades incluem a posição de elementos de construção em relação a um sistema de coorde10 nada, um tipo de elemento de construção e/ou similar. Em algumas modalidades, uma função de peso pode ser ainda uma função de uma propriedade de mais de um elemento de construção retirado em iterações anteriores. Por exemplo, uma ou mais das iterações anteriores poderia ser atribuída com pesos diferentes ao comparar modelos em peças; por exemplo, a iteração 15 mais recente poderia ser atribuída a um peso mais elevado do que as iterações anteriores.

As modalidades do método descrito aqui recebem uma representação digital do modelo de elemento de construção. Uma tal representação digital pode ser fornecida por qualquer processo apropriado, por exem20 pio, um ambiente de construção implementado por computador e/ou um processo para gerar uma representação digital de um modelo de elemento de construção a partir, por exemplo, de uma ou mais imagens, como imagens de um modelo físico ou outro objeto. Um tal processo é descrito na US 7.092.899. Nesse processo uma representação digital de um modelo de e25 Iemento de construção de um item é criado a partir de um modelo CAD ou um conjunto de imagens bidimensionais de um item tridimensional. Algumas modalidades de representações digitais podem incluir informações indicativas dos tipos, posição, e/ou interconexão de elementos de construção, etc. em qualquer formato de dados apropriado. As modalidades de representa30 ções digitais podem incluir ainda informações sobre atributos de modelo global, atributos de elementos de construção individuais, como um tipo de elemento de construção, cor, tamanho, caixa de limitação, etc. Um ambiente de construção implementado por computador para construir iterativamente um modelo de elemento de construção virtual pode compreender um programa de computador que, quando executado em um computador, provê uma interface de usuário gráfico que permite a um usuá5 rio manipular modelos de elemento de construção virtual, incluindo operações como selecionar elementos de construção, acrescentar elementos de construção ao modelo, eliminar elementos de construção do modelo, alterar a orientação de um elemento de construção, alterar propriedades de um eIemento de construção, por exemplo, cor, tipo, tamanho e/ou similares, visu10 alizar um modelo, salvar uma representação digital de um modelo, carregar uma representação digital de um modelo anteriormente salvo, etc. Os elementos de construção virtuais podem ser cópias virtuais de elementos de construção física correspondentes, isto é, ter tamanho relativo correspondente, formato, cor, etc.

Um ambiente de construção implementado por computador po

de ser configurado para executar um conjunto predeterminado de restrições impostas nas posições relativas de elementos de construção em relação mútua, como detecção de colisão entre elementos de construção. Por exemplo, as restrições correspondem às restrições correspondentes aplicáveis aos 20 elementos de construção física correspondentes, desse modo assegurando que um modelo de elemento de construção virtual possa ser efetivamente construído a partir também dos elementos de construção física correspondentes. Consequentemente, é uma vantagem que o método assegura que as instruções de construção geradas sejam efetivamente realizáveis, isto é, 25 levem a um resultado desejado.

Em algumas modalidades, instruções de construção são geradas como uma seqüência de representações gráficas como imagens. Cada representação gráfica pode incluir uma renderização gráfica de um modelo de elemento de construção parcial também mencionado como modelo em 30 peças, desse modo fornecendo instruções de construção fáceis de seguir onde cada representação gráfica corresponde a uma etapa no processo de construção onde um número predeterminado de elementos de construção é acrescentado ao modelo. Desse modo, todos os modelos em peças ou somente um subconjunto dos modelos em peças que compõem a seqüência de construção determinada podem ser incluídos nas instruções de construção finais, visto que uma ou mais etapas da seqüência de construção podem 5 ser combinadas em uma única imagem das instruções de construção. Um usuário pode determinar facilmente quais elementos de construção devem ser acrescentados em cada etapa e como devem ser adicionados por comparar duas representações gráficas consecutivas.

Quando o método compreende ainda fornecer uma interface de 10 usuário para visualizar as representações gráfica, onde a interface de usuário facilita preferivelmente uma manipulação controlada por usuário das representações gráficas geradas, a representação digital do modelo de elemento de construção pode ser convenientemente visualizada em um computador. Em particular, uma vez que a representação digital do modelo inclui 15 todas as informações necessárias para a geração das instruções de construção, instruções de construção podem ser convenientemente comunicadas de um computador para outro, por exemplo, armazenadas em um meio de armazenagem, enviadas através de uma rede de comunicação, por exemplo, como um anexo de e-mail, uploaded em um servidor de rede, ou similar. 20 Um recebedor da representação digital pode desse modo visualizar a representação gráfica e manipular a mesma, por exemplo, alterar um ângulo de visualização, zoom, alterar as operações de visualização e/ou similar. Consequentemente, os usuários podem comunicar facilmente suas instruções de construção a amigos. É uma vantagem adicional que a representação digital 25 não necessita incluir uma renderização gráfica de cada etapa das instruções, desse modo mantendo o tamanho do arquivo da representação digital pequeno. Além disso, uma vez que a representação digital pode compreender todas as informações de modelo relevantes, o recebedor de um modelo pode até mesmo modificar o modelo antes de gerar as instruções de construção.

Em algumas modalidades, as instruções de construção podem

ser geradas em um formato de arquivo predeterminado, desse modo permitindo a geração de instruções de construção impressa e/ou eletrônica. Os exemplos de formatos de arquivo apropriados incluem HTML, XML1 BMP, TIFF1 etc.

Em algumas modalidades, o número predeterminado de elementos de construção adicionais acrescentados em uma etapa das instruções em etapas é selecionável por usuário, desse modo permitindo que um usuário selecione entre instruções de etapa por etapa muito detalhadas, onde, por exemplo, cada etapa corresponde à colocação de um único elemento de construção novo, e instruções muito compactas onde cada etapa corresponde a um número maior de elementos de construção recentemente colocados. Em algumas modalidades o número de elementos de construção acrescentados em cada etapa é igual em todas as etapas. Em outras modalidades, o número de elementos de construção adicionais acrescentados pode ser diferente para etapas diferentes das instruções de construção. Por exemplo, o tamanho da etapa pode ser controlado por um usuário para cada etapa, desse modo permitindo a geração de instruções de definição mais alta para partes mais complicadas da construção.

A presente invenção pode ser implementada em modos diferentes incluindo o método descrito acima e a seguir, um sistema de processamento de dados e meios de produto adicionais, cada um fornecendo um ou £0 mais dos benefícios e vantagens descritos com relação ao método primeiramente mencionado, e cada um tendo uma ou mais modalidades preferidas que corresponda a modalidades preferidas descritas com relação ao método primeiramente mencionado e descrito nas reivindicações dependentes relacionadas ao mesmo.

Em particular, as características do método descrito acima e a

seguir podem ser implementadas em software e realizadas em um sistema de processamento de dados ou outro meio de processamento causado pela execução de instruções executáveis por computador. As instruções podem ser meios de código de programa carregadas em uma memória, como uma 30 RAM, a partir de um meio de armazenagem ou a partir de outro computador através de uma rede de computadores. Alternativamente, as características descritas podem ser implementadas por conjunto de circuitos de ligação física em vez de software ou em combinação com software.

Por conseguinte, a invenção refere-se ainda a um sistema de processamento de dados adaptado para executar o método descrito acima e a seguir. A invenção refere-se ainda a um programa de computador que 5 compreende meio de código de programa para executar todas as etapas do método descrito acima e a seguir quando o programa é rodado em um computador. A invenção refere-se ainda a um produto de programa de computador que compreende meio de código de programa para executar o método descrito acima e a seguir quando o produto de programa de computador é 10 rodado em um computador. O meio de código de programa pode ser armazenado em um meio legível por computador e/ou incorporado como um sinal de dados propagado.

Em algumas modalidades, o programa de computador compreende um primeiro componente de software para gerar uma representação digital do modelo de elemento de construção; e um segundo componente de software para gerar instruções de construção a partir da representação digital gerada, desse modo fornecendo um componente de software separado par Ier a representação digital de um modelo e apresentar as instruções de construção correspondentes. Consequentemente, ao comunicar as instruções de construção um usuário pode comunicar a representação digital juntamente com o segundo componente de software, desse modo fornecendo uma representação independente compacta das instruções de construção que pode ser vista pelo recebedor sem a necessidade de software adicional. Será reconhecido, entretanto que os dois processos, isto é, a geração de uma representação digital de um modelo e a geração das instruções de construção podem ser integradas em um único componente de software. Breve Descrição dos Desenhos

A invenção será explicada mais completamente abaixo com relação a uma modalidade preferida e com referência ao desenho, no qual:

As figuras 1a-b mostram um sistema de processamento de da

dos para gerar instruções de construção de modelos de elementos de construção; A figura 2 mostra um fluxograma de uma modalidade da geração de instruções de construção geral;

A figura 3 mostra um fluxograma de uma modalidade de um processo para gerar uma seqüência de etapas de desconstrução;

A figura 4 ilustra um exemplo de um elemento de construção e

seus elementos de conexão;

A figura 5 ilustra uma modalidade de uma estrutura de dados para representar digitalmente um modelo de elemento de construção;

A figura 6 ilustra uma modalidade de uma interface de usuário gráfico de uma aplicação de instrução de construção;

A figura 7 ilustra uma representação de um modelo de elemento de construção como um gráfico não-orientado;

As figuras 8 a 13 mostram exemplos que ilustram modalidades de critérios de seleção;

A figura 14 mostra um fluxograma de outra modalidade da gera

ção de instrução de construção geral;

A figura 15 mostra um fluxograma de uma modalidade de um processo para gerar uma seqüência de etapas de desconstrução de uma desconstrução parcial;

A figura 16 mostra um fluxograma de outra modalidade da gera

ção de instruções de construção geral.

Descrição detalhada

As figuras 1a-b mostram um sistema de processamento de dados para gerar e manipular modelos legíveis por computador de objetos geométricos.

A figura 1a mostra uma vista esquemática de um exemplo de um sistema de computador. O sistema de computador compreende um computador apropriadamente programado 101, por exemplo, um computador pessoal, que compreende um display 120, um teclado 121 e um mouse 30 de computador 122 e/ou outro dispositivo de indicação, como uma mesa sensível ao toque, um track bali, uma caneta de luz, uma tela sensível ao toque ou similar. O sistema de computador designado 101 é adaptado para gerar instruções de construção a partir de uma representação digital de um modelo de elemento de construção. O sistema de computador 101 pode ser adicionalmente adaptado para facilitar projeto, armazenamento, manipulação e 5 compartilhamento de modelos de elemento de construção virtuais bem como geração de instruções de construção, como descrito aqui. O sistema de computador 101 pode ser utilizado como um sistema independente ou como um cliente em um sistema de cliente/servidor. Em algumas modalidades, o sistema de computador compreende ainda uma ou mais interfaces para co10 nectar o computador a uma rede de computador, por exemplo, a Internet.

A figura 1b mostra um diagrama de blocos de um sistema de processamento de dados para gerar instruções de construção para modelos de elemento de construção. O computador 101 compreende memória 102 que pode ser parcialmente implementada como um meio de memória volátil 15 e parcialmente como meio de memória não-volátil, por exemplo, uma memória de acesso aleatório (RAM) e um disco rígido. A memória tem armazenada na mesma intérprete de código de modelo 107, gerador de código de modelo 108, tratador de evento Ul 109, aplicação de modelagem 110, e gerador de instruções de construção 113, cada um executável pela unidade de 20 processamento central 103. Além disso, a memória tem armazenada na mesma, dados de modelo 111, isto é, um conjunto de estruturas de dados que representa uma representação digital de um modelo de elemento de construção.

O intérprete de código 107 é adaptado para Ier e interpretar uma 25 representação digital que define um modelo, por exemplo, código que representa as estruturas de dados dos elementos de construção de um modelo. Em uma modalidade preferida o intérprete de código é adaptado para Ier uma representação digital do modelo e converter tal modelo em um formato gráfico conhecido para apresentação em um display de computador, preferi30 velmente uma renderização 3D do modelo.

O tratador de evento-UI 109 é adaptado para converter a interação de um usuário com uma interface de usuário em comandos adequados de usuário reconhecíveis pelo gerador de código 108. Um conjunto de comandos reconhecíveis e possíveis pode compreender: obter um elemento de construção a partir de uma biblioteca de elementos, colocar um elemento de construção para ser conectado com outro elemento de construção, desco5 nectar um elemento de construção, descartar um elemento de construção, manipular um elemento de construção, um grupo de elementos de construção, etc, por exemplo, por iniciar uma rotação, etc. Juntamente com cada comando, pode haver associado um conjunto de parâmetros respectivos, por exemplo, coordenadas de cursor com relação ao sistema de coordenadas de 10 display, tipos de elementos de construção, etc.

O gerador de código 108 pode ser adicionalmente adaptado para modificar as estruturas de dados de um modelo em resposta aos comandos de um usuário. Como tarefa simultânea ou subsequente, o intérprete de código pode ser executado para apresentar o resultado do gerador de código.

A aplicação de modelagem 110 é adaptada para controlar memória, arquivos, a interface de usuário, etc.

Uma modalidade de uma modelagem de realidade virtual é descrita em US 6.389.375. Além disso, uma modalidade do processo de colocar 20 de forma interativa um novo elemento de construção virtual em uma cena que inclui uma estrutura 3D é descrita no pedido internacional publicado W004104811. Os dois documentos são incorporados aqui a título de referência na íntegra.

A aplicação de instrução de construção 113 é adaptada para Ier 25 uma representação digital de um modelo e gerar uma instrução de construção a partir dos dados de modelo de leitura, como descrito aqui. A aplicação de instrução de construção 113 pode prover ainda uma interface de usuário para exibir modelos em peças, de acordo com a seqüência armazenada de etapas de construção, como descrito aqui, ou qualquer outro formato de saí30 da apropriado para as instruções de construção geradas. A aplicação de instrução de construção 113 pode utilizar funções fornecidas pelo intérprete de código 107 e o tratador de evento Ul 109 para a leitura e renderização gráfica dos modelos e para receber entrada de usuário, respectivamente. Em modalidades alternativas, a aplicação de instrução de construção é independente, isto é, não depende de componentes de software externos. Em algumas modalidades, a aplicação de instrução de construção gera as instruções 5 de construção em um formato de arquivo apropriado, por exemplo, em forma imprimível.

Um usuário 105 é capaz de interagir com o sistema de computador 101 por intermédio da interface de usuário 106, compreendendo preferivelmente uma interface de usuário gráfico exibida em uma tela de computador, e um ou mais dispositivos de entrada como um teclado e/ou um dispositivo de indicação. Para carregar, salvar ou comunicar modelos, descrições geométricas ou outros dados, o sistema de computador compreende uma unidade de entrada/saída (l/O) 104. A unidade de entrada/saída pode ser utilizada como uma interface para tipos diferentes de mídia de armazenagem e tipos diferentes de redes de computador, por exemplo, a Internet. Além disso, a unidade de entrada/saída (l/O) 104 pode ser utilizada para permutar modelos com outros usuários, por exemplo, interativamente. A permuta de dados entre a memória 102, a unidade de processamento central (CPU) 103, a interface de usuário (UI) 106, e a unidade de entrada/saída 104 é realizada por meio do barramento de dados 112.

Observa-se que o sistema de processamento de dados da figura

1 pode ser configurado para executar tanto a aplicação de modelagem como a aplicação de instruções de construção. Entretanto, em outras modalidades o sistema de processamento de dados pode ser configurado para executar 25 somente a aplicação de instrução de construção baseada em dados de modelo recebidos de outro computador, por exemplo, um computador no qual uma aplicação de modelagem ou outra aplicação para gerar uma representação de modelo digital é executada. De modo similar, no outro computador, a aplicação de modelagem pode ser instalada sozinha ou em combinação 30 com a aplicação de instrução de construção.

A figura 2 mostra um fluxograma de uma modalidade da geração de instrução de construção. Na etapa S1, o processo recebe uma representação digital de um modelo de elemento de construção, por exemplo, como criado por um módulo de geração de modelo, por exemplo, a aplicação de modelagem 110 da figura 1b, ou por qualquer outro processo apropriado.

A representação digital pode ser recuperada de uma mídia de

armazenagem 203, por exemplo, o disco rígido local do computador rodando a aplicação de instrução de construção, um CD ROM, um disquete ou similares. Alternativa ou adicionalmente, a representação digital do modelo pode ser armazenada remotamente, por exemplo, recebida de outro computador 10 de uma rede de computador onde é armazenada. Por exemplo, a representação digital pode ser carregada a partir de um servidor de rede, onde pode ser tornada disponível para um ou mais usuários. Os exemplos de estruturas de dados da representação digital serão descritos abaixo.

Nas etapas subsequentes S2 - S4, a aplicação de instrução de 15 construção gera uma instrução de construção 205 a partir da representação digital carregada. Em uma modalidade, a aplicação de instrução de construção gera uma seqüência de vistas 3D ou modelos em peças, onde cada modelo em peças é distinguido do modelo em peças imediatamente precedente em que um número predeterminado de elementos de construção adicionais 20 é acrescentado ao modelo de acordo com uma seqüência de etapas de construção determinadas pelo processo de instrução de construção como descrito aqui. As instruções de construção 205 podem ser apresentadas eletronicamente, impressas, ou apresentadas em outro modo apropriado. Em algumas modalidades, a geração das instruções de construção pode ser 25 controlada por um usuário 204. Por exemplo, o usuário pode selecionar o número de elementos de construção adicionais a ser acrescentado em cada etapa. Além disso, o usuário pode manipular as vistas 3D geradas, incluindo alterações da posição de uma câmera, etc, como será descrito abaixo. O usuário 204 pode ser o mesmo ou um usuário diferente do usuário 202.

Em particular, na etapa S2, o processo gera uma seqüência de

desconstrução a partir da representação digital recebida do modelo, por exemplo, na forma de uma lista seqüencial de elementos de construção e/ou submontagens do modelo. O processo gera ainda seqüências de desconstrução subordinadas para as submontagens da lista seqüencial. Em uma modalidade, o processo representa a seqüência de desconstrução como uma árvore ramificada de etapas onde cada ramo pode conter desconstru5 ções de construção subordinadas. Uma modalidade de um processo para gerar uma seqüência de desconstrução será descrita em maior detalhe abaixo.

Na etapa S3, o processo reverte a seqüência de desconstrução gerada para obter uma seqüência de construção.

Na etapa S4, o processo gera instruções de construção a partir

da seqüência de construção gerada, por exemplo, como uma seqüência de imagens ou outras representações de modelos em peças, onde em cada modelo em peças um ou mais dos elementos de construção e submontagens a partir da lista gerada são acrescentados em comparação com o mo15 delo em peças anterior. O processo pode armazenar as instruções gradas e/ou transmitir as mesmas em qualquer forma apropriada, como descrito aqui.

A figura 3 mostra um fluxograma de um exemplo de um processo de desconstrução de um modelo M. O processo de desconstrução des20 constrói o modelo M com base em uma representação digital do modelo completo M, incluindo todos os elementos de construção no modelo (etapa 301). A entrada do modelo M inclui informações sobre os elementos de construção individuais, como tamanho/dimensões, número de botões, características especiais como articulações, pinos, eixos, etc. dos elementos de 25 construção. A representação digital também inclui informação sobre onde no modelo cada elemento de construção é colocado, por exemplo, por especificar as posições respectivas (x, y, z) dos elementos de construção com relação a um sistema de coordenadas apropriado.

Na etapa 302, o processo de desconstrução testa se há elementos de construção deixados no modelo M (ou um modelo em peças resultante de uma iteração anterior) para serem desconectados. Caso haja ainda elementos de construção no modelo, o processo prossegue na etapa 303 onde o processo seleciona/gera uma ou mais submontagens candidatas para retirada do modelo M. As submontagens candidatas incluem elementos de construção interconectados. Na etapa subsequente 304, o processo seleciona um elemento de construção ou uma das submontagens candidatas 5 geradas (E) para ser desconectado de acordo com um primeiro conjunto de critérios de seleção predeterminados. Esse primeiro conjunto de critérios de seleção predeterminados atribui pesos a cada elemento de construção e submontagem gerada, de acordo com funções de peso predeterminadas, cujos exemplos serão descritos mais completamente abaixo. Consequente10 mente, o processo determina um elemento de construção ou submontagem a partir de um grupo de candidatos, onde o grupo inclui todos os elementos de construção individuais e as submontagens candidatas geradas. Consequentemente, para fins do processo de seleção, as submontagens podem ser consideradas como sendo tratadas como elementos de pseudoconstru15 ção além dos elementos de construção efetivos. Para fins da presente descrição, membros do grupo de elementos de construção e submontagens candidatas também serão referidos como candidatos para retirada.

As submontagens candidatas na etapa 303 são encontradas/selecionadas por intermédio de um segundo conjunto de critérios de seleção, que são uma determinação de como o modelo pode ser separado/cortado. Os exemplos de tais critérios de seleção serão descritos mais completamente abaixo.

Na etapa 305, o processo desconecta o elemento de construção ou submontagem E selecionada na etapa 304 a partir do modelo, isto é, gera 25 um novo modelo em peças M-M\E onde o elemento de construção selecionado de todos os elementos de construção da submontagem candidata selecionada é retirado. O processo mantém uma estrutura de dados indicativa da seqüência de desconstrução, e atualiza a estrutura de dados com informações sobre o elemento de construção/submontagem desconectado. A 30 seqüência é armazenada, de modo que possa ser revertida posteriormente para obter uma instrução de construção.

Se o processo selecionar uma submontagem para ser desconectada, a submontagem selecionada pode ser desconstruída por executar o processo de desconstrução em. um modo recursivo na etapa 307 (isto é, com a submontagem selecionada E servindo como modelo de entrada M), antes de retornar à etapa 302 para continuar o processo de desconstrução 5 iterativo e encontrar o próximo elemento de construção a desconectar do modelo em peças restante, isto é, o modelo M’=M\E.

Quando não há mais elementos de construção no modelo, o modelo é totalmente desconstruído, e o processo de desconstrução para na etapa 308.

Consequentemente, uma modalidade do processo de descons

trução descrito acima pode ser expressa pelo seguinte pseudocódigo:

Deconstruct model M:

Let Candidates be the set of ali bricks in M

Let Result be an empty sequence of bricks

While (Candidates is not empty)

Let D be the subset of Candidates that are detachable

Let b be the "best detachable" brick from D

Add b to Result

Remove b from Candidates

Return Result

No pseudocódigo acima a seleção do bloco "mais bem desprendível" corresponde à seleção executada na etapa 304 acima, isto é, uma seleção com base em um conjunto de critérios de seleção predeterminados, por exemplo, um ou mais dos critérios de seleção descritos abaixo.

É uma vantagem selecionar primeiramente as submontagens candidatas, que podem ser desconectadas do modelo e então posteriormente atribuir a cada candidata pesos de acordo com a preferência de desconectar, que é computacionalmente possível tratar a seleção, ao separar a mesma em mais etapas, uma vez que a ponderação de submontagens somente é executada em um subconjunto de todas as submontagens possíveis do modelo.

Um exemplo de um processo de desconstrução é descrito por 5 um dos inventores na tese "Computer-aided generation of building instructions for LEGO models", de Jacob Allerelli, Department of Mathematics and Computer Science, University of Southern Denmark, junho de 2006, que é incorporada aqui a título de referência. A seguir, os exemplos de regras de seleção do segundo conjunto de critérios de seleção para determinar sub10 montagens candidatas na etapa 303 serão descritos em maior detalhe. Esses critérios de seleção também serão mencionados como heurística de corte.

Cortes mínimos/divisão de gráfico:

Foi percebido que submontagens candidatas apropriadas podem ser determinadas de forma eficiente utilizando técnicas de divisão de gráfico para dividir gráficos em subgráficos. Para essa finalidade, o processo representa o modelo em uma estrutura de dados indicativa de um gráfico não direcionado incluindo nós e bordas que conectam nós, no qual os nós representam elementos de construção e as bordas representam conexões entre elementos de construção. Um tal gráfico também será mencionado como gráfico de conectividade. Um exemplo, de um gráfico de conectividade é mostrado na figura 7. A figura 7a mostra um exemplo de um modelo de elemento de construção que inclui elementos de construção a, b, c, d e e. A figura 7b mostra o gráfico de conectividade correspondente com nós a, b, c, d, e.

Os itens de dados de borda da estrutura de dados de gráfico podem incluir um atributo indicativo da resistência de conexão (física) da conexão correspondente entre os elementos de construção conectados pela conexão representada pela borda. Assim um processo de divisão de gráfico 30 para identificar um corte de peso mínimo do gráfico resulta em uma submontagem de tal modo que a força/resistência física necessária para desconectar a submontagem é pelo menos aproximadamente minimizada. Desse modo, as submontagens mais frouxamente conectadas são selecionadas. Um exemplo de determinar a resistência de conexão entre elementos de construção será descrito em maior detalhe abaixo.

Alteração de direção de construção:

É vantajoso cortar um modelo onde uma alteração em direção

de construção ocorrer. Alterações em direção de construção podem ocorrer quando elementos de construção são interconectados ao longo de pelo menos duas direções de construção. As posições de alterações na direção de construção podem ser encontradas por buscas de gráfico locais no gráfico 10 de conectividade. Uma direção de construção pode ser definida por associar um atributo de direção com cada elemento de construção. Alternativa ou adicionalmente uma direção de construção pode ser definida por atribuir um atributo de direção às conexões entre elementos de construção. Para essa finalidade, os nós e/ou bordas do gráfico de conectividade podem ter atribu15 tos associados aos mesmos indicativos de uma direção de construção da conexão correspondente.

Cortes de articulação de elemento de construção único: Elementos de construção que interconectam dois ou mais elementos de construção/submontagem são denominados elementos de construção de articulação, e podem ser bons pontos/nós de corte para separação do modelo. Após identificação, um elemento de construção de articulação pode ser incluído na submontagem separada, isto é, ser retirado, ou o elemento de construção de articulação pode ser excluído da submontagem separada, isto é, não ser retirado. No gráfico, elementos de construção de articulação podem, por exemplo, ser indicados - por exemplo, pela denominada coloração de gráfico - e desse modo facilmente localizados. Nós de articulação do gráfico de conectividade podem ser encontrados por qualquer algoritmo apropriado para encontrar nós de articulação de um gráfico, por exemplo, com base em uma primeira busca de profundidade (vide, por exemplo, "Graph theory and its applications" de Jonathan L. Gross e Jay Yellen, Chapman & Hall/CRC, segunda edição, 2006).

Cortes do par de articulações de elemento de construção: O termo par de articulações se refere a dois elementos de construção que interconectam duas ou mais submontagens separadas, isto é, pares de elementos de construção cuja retirada faz com que o modelo se separe em duas submontagens separadas. As submontagens conectadas 5 ao restante do modelo por elementos de construção de articulação ou pares de articulação podem ser submontagens candidatas úteis para fins de gerar instruções de construção.

Pares de articulação podem ser encontrados por um processo onde uma lista A de todos os nós de articulação no gráfico de conectividade 10 G é salva. Então um gráfico G’ é gerado, onde um nó não-articulação n em G é retirado. Uma lista B de todos os nós de articulação em G’ é salva. Para cada nó m em B\A, os seguintes pares de articulação são encontrados: (n, m). Esse processo é repetido para todos os nós de não articulação n no gráfico G.

Conexão de junção ou de articulação:

Uma conexão de articulação é uma articulação entre um ou mais elementos de construção em torno de uma direção de articulação. Um elemento de construção pode incluir uma articulação interna ou um elemento de conexão de articulação para fornecer uma conexão de articulação entre 20 dois ou mais elementos de construção. Submontagens conectadas ao resto do modelo por uma conexão de articulação podem ser submontagens candidatas para fins de gerar instruções de construção. Tais montagens podem ser identificadas no gráfico de conectividade, quando bordas do gráfico têm atributos associados indicativos da presença de estruturas de articulação. 25 Por exemplo, o processo pode buscar subgráficos do gráfico de conectividade que são conectados ao restante do gráfico de conectividade somente por uma ou mais conexões de articulação. A figura 12b ilustra um elemento de construção tendo um elemento de conexão 1201 para fornecer uma conexão de articulação. Será entendido, que outros tipos de conexões móveis podem 30 ser úteis para identificar também submontagens candidatas, por exemplo, conexões de junção, conexões deslizantes, etc.

Casos especiais: Alguns elementos de construção são especiais no modo em que são conectáveis a outros elementos de construção somente em uma maneira. Os exemplos desses elementos de construção são figuras tendo um elemento de conexão único sob a base da figura, vidro nas janelas, pneus em 5 rodas, vagões de trem em trilhos, etc. Esses elementos de construção especiais são, portanto, candidatos que podem ser cortados do modelo em sua conexão externa, isto é, onde são conectados a um elemento de construção arbitrário diferente de seu elemento de construção correspondente.

Consequentemente, no acima, diversas heurísticas de corte pa10 ra identificar submontagens candidatas foram reveladas. Uma heurística de corte ou uma combinação de mais heurísticas de corte, como descrito acima, pode ser desse modo utilizada durante o processo de desconstrução para encontrar eficientemente submontagens entre o número grande de todas as submontagens possíveis de um modelo.

Como descrito acima, em uma modalidade, cada candidata de

retirada - isto é, cada um dos elementos de construção do modelo e cada uma das submontagens candidatas que são selecionadas pelo(s) processo(s) de heurística de corte alternativo(s) ou acima - é ponderada por intermédio de uma ou mais funções de peso de modo a encontrar a candidata de 20 retirada com o peso mais elevado, isto é, a candidata de retirada E mais apropriada para ser removida do modelo (etapa 304), e então essa candidata de retirada selecionada é desconectada (etapa 305).

Em uma modalidade, as funções de peso são selecionadas de tal modo que cada função de peso aumentará a chance de uma submonta25 gem/elemento de construção ser selecionado ou rejeitará a submontagem/elemento de construção de ser selecionado, com base nos critérios que implementa. O processo combina os resultados de todas as funções de peso para cada submontagem/elemento de construção de modo a obter um peso geral para a submontagem/elemento de construção. O processo pode então 30 selecionar a submontagem/elemento de construção com o peso mais elevado. Quando as funções de ponderação individuais são selecionadas, de acordo com um esquema de ponderação uniforme, o conjunto de funções de ponderação é facilmente alterável.

Por exemplo, em uma modalidade, cada função de peso resulta em um peso. Um peso é um número real na faixa [0, ..., 1] ou um número inteiro negativo (-1, -2, -3, ...). Se a desconexão de uma submonta5 gem/elemento de construção for favorecida, o peso atribuído à submontagem/ elemento de construção está na faixa [0, ..., 1], onde 0 é atribuído quando não é desfavorecido nem favorecido para desconectar uma submontagem/elemento de construção, e 1 é atribuído quando a desconexão é ótima. Os números reais entre esses dois extremos indicam favorecimento de 10 desconexão entre os mesmos. Se a desconexão for desfavorecida, a função de peso resulta em um peso negativo atribuído à submontagem/elemento de construção na faixa (-1, -2, -3, ...), onde os valores negativos diferentes indicam quão desfavorecido é uma desconexão. Será reconhecido que outros conjuntos de funções de peso podem ser definidos tendo faixas diferentes.

Funções de peso tendo duas faixas separadas podem ser utili

zadas para implementar um esquema veto, por exemplo, como descrito abaixo:

Para cada submontagem/elemento de construção x, cada um conjunto de funções de peso é avaliada, e os pesos individuais respectivos são combinados como a seguir: se não houver pesos negativos (denominados "VETO"s) entre os pesos atribuídos para x, todos os pesos são acumulados para obter um peso total. Se, por outro lado, houver um ou mais VETOs entre os pesos atribuídos, todos os pesos não VETO são descartados, isto é, definidos iguais a 0. De acordo com isso, uma boa submontagem/elemento de construção para desconectar é uma que é isenta de VETOs e tenha um peso acumulado elevado. Por outro lado, após uma submontagem/elemento de construção receber um VETO, não pode deixar o estado de VETO até a próxima iteração na desconstrução. Se todos os elementos de construção/submontagens obtiverem pesos negativos, o processo pode selecionar o elemento de construção com o peso negativo total tendo o menor valor absoluto. Alternativamente, o processo pode retroceder uma ou mais iterações e tentar selecionar uma submontagem / elemento de construção diferente, solicitar uma interação de usuário ou prosseguir em outro modo apropriado.

Verificou-se que o esquema de ponderação acima resulta em instruções de construção de alta qualidade quando uma desconstrução é 5 encontrada onde, em cada etapa, há pelo menos uma submontagem/elemento de construção que é isento de VETOs.

Um número de exemplos de funções de peso será descrito agora em maior detalhe:

Estratégia de desprender;

Um exemplo de uma função de peso determina se uma sub

montagem/elemento de construção a ser desconectada é fisicamente acessível e desprendível do resto do modelo. Para essa finalidade, a função de peso verifica se uma ou mais das duas exigências a seguir são atendidas:

1) todas as direções ao longo das quais uma submontagem/elemento de construção é desprendível/conectável são paralelas. A função de peso pode determinar, desse modo, a direção de construção e/ou a direção de conexão de todas as conexões de um elemento de construção, por exemplo, com base em atributos associados ao nó e/ou bordas correspondentes no gráfico de conectividade. Se todas as direções forem paraleIas, o elemento de construção pode ser desconectado por um movimento de translação. Por exemplo, os elementos de construção 803 da figura 8a têm duas direções de conexão que não são paralelas: são conectados ao eixo 802 e ao elemento de construção 804. A conexão ao eixo 802 tem uma direção associada paralela ao eixo 802, uma vez que a retirada do elemento de construção 803 a partir do eixo 802 exigiria um movimento do elemento de construção 803 em uma direção ao longo do eixo 802. A conexão ao elemento de construção 804, por outro lado tem uma direção ortogonal ao eixo, a saber, na direção dos botões que se projetam para fora da superfície superior do elemento de construção 804. Consequentemente a retirada do elemento de construção 803 pode causar tensão no modelo e ser de difícil execução para, por exemplo, uma criança sem desconectar simultaneamente outras conexões do modelo. A figura 12 mostra exemplos de elementos de construção com suas respectivas direções de desprendimento indicadas por setas.

2) o deslocamento de um elemento de construção/submontagem em uma direção de conexão não resulta em uma colisão 5 com outros elementos de construção do modelo. Por exemplo, a função de peso pode determinar uma caixa de limite do elemento de construção/submontagem, e determinar se uma translação da caixa de limite por uma distância predeterminada na direção de conexão resulta em uma colisão/interação com outro elemento de construção. A figura 13 ilustra um mo10 delo no qual o elemento de construção 1301 é móvel ao longo de sua direção de desprendimento por uma distância d. Alternativamente, a função de peso pode calcular uma geometria de submontagem/elemento de construção estirada na direção de conexão, e determinar se a geometria estirada colide com quaisquer outros elementos de construção/submontagens. A 15 quantidade de espaço que um elemento de construção ocupa pode ser representada por volumes geométricos simples. Por exemplo, um elemento de construção com 2x4 botões, por exemplo, como mostrado na figura 4 pode ter associado ao mesmo 9 caixas de colisão: uma caixa de colisão enche o elemento de construção inteiro exceto pelos 8 botões, e os 8 botões enchem 20 uma caixa de colisão cada. Essa informação pode ser utilizada para estimar se os elementos de construção colidem/sobrepõem. As informações de caixa de colisão podem ser utilizadas para calcular a geometria/formato/forma estirada que representa o espaço que é necessário para desconectar um elemento de construção.

Um exemplo de como calcular o formato/forma/geometria esti

rada pode compreender encontrar uma direção, que é um vetor d, no qual o elemento de construção pode ser desconectado. O elemento de construção tem N volumes de colisão (por exemplo, N=9 como no exemplo do elemento de construção com 2x4 botões acima) e uma posição (x, y, z).

Tendo um elemento de construção BE, um vetor d e o modelo

Μ, o processo de desprender pode incluir as seguintes etapas: para cada volume de colisão k no BE, p1 indica posição k’s. p2 indica posição k’s quando o BE é movido de p1 ao longo do vetor d. Uma vez que cada volume de colisão é uma caixa com 8 cantos, haverá 8 pontos em p1 e 8 pontos em p2. No total haverá 16 pontos em um conjunto de pontos. Quando os volumes de colisão são convexos esse conjunto de pontos constituirá uma figura convexa f.

O processo testa se a figura f colide com quaisquer elementos de construção do modelo M. Se a figura f colidir com quaisquer elementos de construção do modelo Μ, o elemento de construção BE não pode ser desconectado. Se a figura f não colidir com nenhum elemento de construção no modelo Μ, o processo pode testar o volume de colisão seguinte.

Finalmente, se nenhuma das figuras f dos volumes de colisão N colidir com quaisquer elementos de construção do modelo Μ, o elemento de construção BE pode ser desconectado de acordo com a estratégia de desprender.

O efeito dessa estratégia é que assegura pelo menos aproxima

damente que a desconstrução (e desse modo a construção reversa) do elemento de construção / submontagem é fisicamente possível sem colocar tensão física no modelo.

O exemplo a seguir de uma função de peso evita desconexão de elementos de construção/submontagens que não são fisicamente desprendíveis (ou pelo menos somente facilmente):

Peso(x) = -1, se pelo menos uma das condições acima 1) e 2) não for atendida para x,

0, de outro modo Estratégia de articulação:

Como mencionado acima, submontagens/elementos de construção cuja retirada faz com que o modelo se divida em duas ou mais partes separadas são denominadas submontagens/elementos de construção de articulação. A desconexão de submontagens/elementos de construção de 30 articulação pode resultar em instruções de construção que mostram submontagens/elementos de construção separados que parecem flutuar/voar em relação mútua em uma renderização 3D das instruções de construção. Isso pode ser indesejável, porque complica a desconstrução e desse modo também a instrução de construção.

A seguinte função de peso evita desconexão de submontagens/elementos de construção de articulação:

Peso(x) = -1 se x for uma submontagem/elemento de constru

ção de articulação

0 se não for

Consequentemente, elementos de construção de articulação são fortemente desfavorecidos, desse modo evitando submontagens/elementos de construção que voam.

Em uma modalidade alternativa, a função de peso atribui um peso neutro, por exemplo, peso=0 se x for uma submontagem/elemento de construção de articulação, e um peso positivo, por exemplo, peso=1, se x não for uma submontagem/elemento de construção de articulação. Conse15 quentemente, nessa modalidade a desconexão dos elementos de articulação não é desfavorecida nem favorecida. Isso mostra que os pesos diferentes podem ser ajustados de modo a adaptar o esquema de ponderação a efeitos desejados diferentes. Ainda em outra modalidade, pesos diferentes são atribuídos dependendo de se a função de peso é calculada para um e20 Iemento de construção individual ou uma submontagem. Por exemplo, em uma modalidade, se x for uma submontagem, o peso(x) é definido em -1 para submontagens de articulação e em 0, se x não for uma submontagem de articulação, enquanto no caso de x ser um elemento de construção individual, o peso(x) é definido em 0 para elementos de construção de articula25 ção e +1 de outro modo. Consequentemente, nessa modalidade, a desconexão de uma submontagem de articulação é evitada, enquanto a desconexão de elementos de construção de articulação é meramente desfavorecida.

Estratégia de integração:

Há situações onde não é possível evitar submontagens/elementos de construção desconectados (ou "voando") no modelo em peças restante. Um exemplo de uma tal situação é mostrado na figura 8a, que mostra um elemento de engrenagem 801 posicionado em um eixo 802 o qual se projeta através de furos correspondentes de elementos de construção 803. Ao desconstruir o modelo, o eixo 802 pode ser retirado, resultando no elemento de engrenagem 801 permanecendo desconectado do resto do modelo, como mostrado na figura 8b.

Em uma tal situação pode ser desejável retirar o elemento des

conectado 801 o mais rápido possível do modelo, resultando na situação mostrada na figura 8c.

A retirada rápida de elementos desconectados pode ser favorecida por uma função de peso atribuindo um peso crescente a submontagens/elementos de construção que são (direta ou indiretamente) conectados a um número menor de outros elementos de construção: um exemplo de uma tal função de peso é:

Peso(x) = 1 / (number_of_building elements_connected_to_x + 1) para todas as submontagens/elementos de construção x No exemplo da figura 8b, as funções de peso acima atribuem o

peso 1 a pequena engrenagem 801, uma vez que não é conectada a nenhum outro elemento de construção ou submontagem. Por outro lado, os outros elementos de construção são atribuídos com peso 1/6, porque fazem parte de uma montagem que inclui os cinco elementos designados 803, 804 e 805.

A estratégia de integração reduz, desse modo, o número de etapas durante as quais submontagens ou elementos de construção "que voam" inevitáveis são mostradas na instrução de construção resultante.

Estratégia de similaridade:

A estratégia de similaridade se refere a simetrias em constru

ção/desconstrução. Ao empregar uma estratégia de similaridade no processo de construção, a construção pode se tornar provavelmente simétrica, o que simplificará o processo de desconstrução. Para executar uma desconstrução com base nisso, uma função, que indica quanto dois elementos de construção AeB são "similares" pode ser determinada como a seguir.

Funções de peso determinam coordenadas A’s e B’s em um sistema de coordenadas onde o eixo geométrico y corresponde a uma direção de construção principal, por exemplo, uma direção vertical. O eixo geométrico x e o eixo geométrico z correspondem a outras direções de construção principais, por exemplo, direções horizontais.

Se B for o último elemento de construção que foi desconectado, então uma função de peso para determinar se A e B são similares, pode ter a seguinte forma:

Peso(x) = soma de

a se A e B for o mesmo tipo de elemento de construção

b se A e B tiverem a mesma coordenada x ou a mesma coordenada z no sistema de coordenadas

c se A e B tiverem os mesmos atributos (como cor, decoração

etc.)

para pesos predeterminados a, b, c onde a+b+c=1.

Um peso mais elevado do que 0 reflete algum grau de similaridade. Critérios alternativos e/ou adicionais também poderiam ser considerados.

A estratégia é desconectar uma submontagem/elemento de construção, que é similar aos últimos elementos/s de construção ou submontagem (ns) desconectados. O efeito dessa estratégia é que um modelo, que contém partes simétricas, será frequentemente simetricamente desconstruído.

Um exemplo da estratégia de similaridade para desconstrução é dado na figura 9 que ilustra um exemplo de três etapas de desconstrução consecutivas nas figuras 9a)-c), respectivamente. Vê-se a partir da figura 9 25 que na parte esquerda do modelo, primeiramente um elemento de construção oblongo 901 é desconectado e posteriormente um elemento de construção oblongo similar 902, que é colocado em relação simétrica ao primeiro elemento de construção oblongo, é desconectado. A etapa seguinte poderia ser desconectar os dois elementos de construção oblongos similares 903 na 30 parte direita do modelo.

Estratégia de base:

Submontagens ou elementos de construção especiais, como placas grandes ou placas de formato irregular serão frequentemente um eIemento de construção de partida/base do modelo, e serão posteriormente o último elemento de construção a desconectar. Para examinar se uma placa ou outro elemento de construção é um elemento de construção de partida, o tipo e/ou tamanho do mesmo pode ser comparado com o tipo/tamanho dos outros elementos de construção, ou ser comparado com um valor limite indicando quando um elemento de construção é grande, uma vez que um elemento de construção de partida será frequentemente grande, porque forma a base do modelo. Além disso, também pode ser examinado se um elemento de construção grande é um elemento de construção de base por analisar quão para baixo é colocado no modelo. Um elemento de construção sendo grande e sendo colocado no fundo do modelo é provavelmente um elemento de construção de partida. Para essa finalidade, os nós do gráfico de conectividade podem ter associado aos mesmos atributos respectivos indicativos do tamanho/volume dos elementos de construção. Alternativamente, o processo de instrução de construção pode permitir que um usuário indique um elemento de construção de partida, por exemplo, por indicar um elemento de construção de partida com um mouse ou outro dispositivo de indicação. Por conseguinte, uma função de peso que evita que os elementos de construção de partida sejam removidos do modelo pode ter a seguinte forma:

Peso(x) = -1 se x for um elemento de construção de partida

0 se não for.

Alternativamente, a função de peso pode atribuir o peso 0 se x for uma submontagem/elemento de construção de partida desse modo indi25 cando que a desconexão de x não é favorecida, enquanto atribui um peso positivo elevado, por exemplo, peso = 1 se x não for uma submontagem/elemento de construção de partida, porque então a desconexão é favorecida.

O efeito é que na instrução de construção resultante algumas submontagens ou elementos de construção de base comuns serão conectados inicialmente ou cedo no processo de construção.

Estratégia de integridade de subetapa: De acordo com uma modalidade, para cada submontagem candidata x, há dois aspectos de contribuição que refletem/contribuem para a qualidade da conectividade. O primeiro aspecto é a resistência da conectividade interna entre os elementos de construção da submontagem x, e o segundo aspecto é a resistência da conectividade externa dos elementos de construção da submontagem x. Se a conectividade interna for relativamente forte e a conectividade externa for relativamente fraca, pode-se esperar que a submontagem seja removível, uma vez que os elementos de construção na submontagem são fortemente conectados aos outros elementos de construção na qual submontagem, e somente fracamente conectados ao resto do modelo. De forma correspondente, durante o processo de construção uma submontagem que tem uma conexão interna forte e uma conexão fraca ao resto do modelo pode ser construída relativamente fácil como uma submontagem estável e conectada ao restante do modelo sem o risco de que a submontagem se divida durante o processo de fixação.

Para investigar quão fortemente uma submontagem é internamente conectada, isto é, como os diferentes elementos de construção da submontagem são conectadas entre si, o gráfico de conectividade ou outra representação apropriada de conectividade entre todos os elementos de 20 construção pode ser utilizada. O gráfico de conectividade pode incluir pesos que refletem a resistência física entre elementos de construção, como descrito acima, por exemplo, quando cada borda tem um atributo/peso associado ao mesmo indicativo da resistência da conexão correspondente.

Por exemplo, cada elemento de construção pode incluir um ou 25 mais elementos de conexão para engatar elementos de conexão correspondentes de outros elementos de construção de modo a fornecer uma conexão entre os elementos de construção. Por exemplo, a figura 4 mostra um exemplo de um elemento de construção com protuberâncias na forma de botões adaptadas para engatar furos (também mencionados como antibotões) de 30 outro elemento de construção. Em geral, elementos de construção podem ter elementos de conexão de uma ou mais classes diferentes de elementos de conexão, cada classe de elemento de conexão ou cada par de classes de elemento de conexão pode fornecer uma conexão de uma resistência correspondente. A resistência total de uma conexão entre dois elementos de construção pode ser desse modo determinada/estimada a partir do número de elementos de conexão/pares de elementos de conexão cooperantes que 5 contribuem para a conexão entre dois elementos de construção, e a partir dos tipos/classes respectivos dos elementos de conexão de contribuição. Por exemplo, o processo pode acrescentar as resistências de conexão individuais para obter uma resistência de conexão total. Informações sobre o número e tipos de elementos de conexão contribuindo para a uma conexão 10 podem ser obtidas da representação digital do modelo de elemento de construção e/ou incluídas nos nós e/ou bordas do gráfico de conectividade. Os exemplos de estruturas de dados que suportam a definição de elementos de conexão são descritos em WO 04/034333.

Por exemplo, a resistência de uma conexão entre elementos de

construção x e y pode ser calculada como a seguir:

Resistência (x,y) = ^ScN(c)

c

5

onde a soma examina rapidamente todas as classes de conexão c, Sc é a resistência de conexão de classe de conexão c, e N(c) é o número de elementos de conexão de classe c contribuindo para a conexão entre x e y.

Um exemplo de como a resistência física de uma conexão pode ser determinada entre dois elementos de construção x e y do tipo mostrado na figura 4 e tendo elementos de conexão na forma de pares de botão/antibotão (ou furo), pinos e eixos pode ser definido como a seguir:

Resistência (x,y) = soma de:

1 para cada par de botão/antibotão de conexão 10 para cada pino 5 para cada eixo

Será reconhecido que os valores numéricos no exemplo acima

servem meramente como um exemplo.

A resistência efetiva da conectividade pode ser estimada ainda mais precisamente quando o cálculo da resistência efetiva leva ainda em consideração a geometria dos elementos de construção.

Por exemplo, a figura 10 mostra duas submontagens, cada uma incluindo dois elementos de construção interconectados por um único elemento de conexão da forma descrita com relação à figura 4. Entretanto, embora a submontagem da figura 10a seja bem conectada, isto é, difícil de desmontar, a submontagem da figura 10b não o é, visto que seria muito fácil para um usuário retirar o elemento de construção 1001 da placa de base 1002. O processo pode ajustar essa diferença por incorporar o volume ou massa do elemento de construção menor/mais leve em relação à resistência de sua conexão. Alternativa ou adicionalmente outra quantidade apropriada indicativa das propriedades geométricas do elemento de construção pode ser utilizada. Isso simula quão fácil é, por exemplo, para um usuário segurar o elemento de construção com os dedos do usuário, uma vez que um elemento de construção grande é mais fácil de segurar do que um elemento de construção pequeno.

Consequentemente, uma tal função de peso modificada pode ser expressa como:

Conexão(x,y) = resistência(x.y) / mínimo (volume de x, volume

de y)

Assim no exemplo mostrado na figura 10, as duas submontagens têm a mesma resistência entre elementos de construção, porque nos dois casos o elemento de construção pequeno é conectado em um par de botão-antibotão. Entretanto, na submontagem da figura 10a, o elemento de 25 construção menor 1003 tem um volume menor, enquanto na submontagem da figura 10b o elemento de construção menor 1001 tem um volume maior, de modo que a conexão de função (x,y) será maior para a submontagem da figura 10a.

Um exemplo de uma função de peso com base na medida de conectividade acima pode ser como a seguir:

Peso(x) = -1 se x for uma submontagem e

Sua conexão interna mais fraca < valor limite interno -1 se x for uma submontagem e sua conexão externa mais forte > valor limite externo

0 de outro modo

Os valores de limite para as conexões interna e externa podem ser predeterminados, controlados por usuário, empiricamente encontrados ou de outro modo adequadamente definidos.

O ajuste dos valores de limite é um modo eficaz de regular a quantidade e qualidade de subetapas na instrução de construção resultante. Por definir os valores de limite em valores relativamente elevados, poucas 10 submontagens candidatas de alta qualidade podem ser obtidas em vez de obter muitas de qualidade inferior. Isso torna o processo de desconstrução mais fácil e mais rápido.

Estratégia mais próxima:

Submontagens/elementos de construção também podem ser 15 cedidas um peso de acordo com sua distância a partir da submontagem/elemento de construção anteriormente desconectado. Mais especificamente, o peso(x) pode ser uma função da distância, distância quadrada, ou outra medida de distância apropriada do centro de massa de x para o centro de massa da submontagem/elemento de construção, que foi anteriormente 20 desconectada. Será entendido que em vez do centro de massa, outro ponto de referência apropriado dos elementos de construção/submontagens pode ser utilizado.

Elementos de construção que estão mais próximos da submontagem/elemento de construção anteriormente desconectado pode receber 25 peso mais elevado. Quando elementos de construção estão se contatando mutuamente pelo menos em um ponto, a distância entre os mesmos pode ser definida em zero. A estratégia mais próxima pode diferenciar entre elementos de construção que encostam-se às superfícies um do outro e elementos de construção apenas contatando entre si em seus cantos, como 30 ilustrado na figura 11a e figura 11b, respectivamente. Em uma modalidade, uma função de peso pode ser desse modo uma função crescente do tamanho da área de encosto entre dois elementos de construção. O fato de se os elementos de construção encostam ou não entre si ou estão de outro modo em contato entre si pode ser determinado com base na caixa de limite ou outra informação geométrica armazenada como parte da representação digital. Um modo de aproximar uma tal medida é pelo cálculo da distância maior 5 entre os pontos dos respectivos elementos de construção. Quanto maior é essa distância, menor é geralmente a área de encosto como ilustrado pela figura 11.

Estratégia de empilhar:

Ao construir um modelo será frequentemente preferível construir 10 da parte inferior e para cima. Portanto, um peso pode ser atribuído a uma submontagem/elemento de construção de acordo com sua distância a partir do elemento de construção mais baixo no modelo. Quanto mais distante uma submontagem/elemento de construção está da parte inferior, mais elevado um peso será atribuído no processo de desconstrução. Consequente15 mente, em geral uma função de ponderação pode ser uma função crescente das coordenadas de um elemento de construção ao longo de uma ou mais direções de um sistema de coordenadas.

Consequentemente, acima um número de exemplos de funções de peso foi descrito, cada um correspondendo a uma estratégia de descons20 trução de modelo correspondente. Será entendido que um processo de desconstrução pode incluir funções de peso alternativas ou adicionais e/ou estratégias de desconstrução alternativas ou adicionais. Além disso, funções de peso alternativas e/ou adicionais podem ser definidas correspondendo às estratégias de desconstrução descritas aqui.

Será adicionalmente reconhecido que algumas das estratégias

descritas aqui têm um ou mais parâmetros que podem variar para reforçar um aspecto ou outro do resultado, desse modo tornando a estrutura uma ferramenta para gerar instruções de construção por interação humana, em vez de uma caixa preta.

Os inventores obtiveram resultados particularmente bons com

uma combinação de funções de peso que correspondem às seguintes estratégias para assegurar a integridade da desconstrução de construção. Juntos podem formar a espinha dorsal de uma modalidade de um gerador automático de instruções de construção que provê bons resultados sem a necessidade de interação de usuário:

- estratégia de desprender: somente permite desconexão de eIementos de construção ou submontagens que sejam fisicamente possíveis

retirar, dada a geometria e conectividade do elemento de construção ou submontagem.

- estratégia de integridade de subetapa: somente permite desconectar montagens que são fortemente conectadas internamente, e fraca

mente conectadas externamente. A exigência exata pode variar para assegurar subetapas de qualidade desejada, como descrito acima.

- estratégia de articulação: somente permite desconectar submontagens que não dividem o modelo em duas ou mais montagens desconectadas. Além disso, desfavorece a desconexão de elementos de constru

ção individuais que dividem o modelo em duas ou mais submontagens desconectadas.

- estratégia de integração: se um elemento de construção de articulação individual foi retirado, retire os elementos de construção ou submontagens desconectados o mais rápido possível.

Em uma modalidade, as quatro estratégias acima mencionadas

- desprender, integração de subetapa, articulação e integração - são utilizadas para toda construção/desconstrução, ao passo que uma ou mais estratégias adicionais, por exemplo, uma ou mais das estratégias restantes descritas aqui, por exemplo, similaridade, base, mais próxima e empilhar podem

ser utilizadas para ajustar o resultado em situações diferentes. Tais estratégias podem ser selecionáveis por um usuário.

A figura 4 ilustra um exemplo de um elemento de construção e seus elementos de conexão. Em particular, a figura 4 mostra uma vista em perspectiva de um elemento de construção 401. O elemento de construção

401 tem uma superfície superior 402 com oito botões 403a-h que podem engatar-se com furos correspondentes de outro elemento de construção, por exemplo, furos na superfície inferior de outro elemento de construção. De forma correspondente, o elemento de construção 401 compreende uma superfície inferior (não-mostrada) com furos correspondentes. O elemento de construção 401 compreende ainda superfícies laterais 404 que não compreendem nenhum elemento de conexão.

Geralmente, os elementos de conexão podem ser agrupados

em classes diferentes de elementos de conexão, por exemplo, conectores, receptores, e elementos misturados. Conectores são elementos de conexão que podem ser recebidos por um receptor de outro elemento de construção, desse modo fornecendo uma conexão entre os elementos de construção. 10 Por exemplo, um conector pode adaptar-se entre partes de outro elemento, em um furo ou similar. Receptores são elementos de conexão que podem receber um conector de outro elemento de construção. Elementos misturados são partes que podem funcionar tanto como receptor como conector, tipicamente dependendo do tipo do elemento de conexão cooperante do ou15 tro elemento de construção.

Elementos de construção do tipo ilustrado na figura 4 são disponíveis sob o nome LEGO em uma grande variedade de formatos, tamanhos e cores. Além disso, tais elementos de construção são disponíveis com uma variedade de elementos de conexão diferentes. Entende-se que o elemento 20 de construção acima meramente serve como exemplos de possíveis elementos de construção.

A figura 5 ilustra uma modalidade de uma estrutura de dados para representar digitalmente um modelo de elemento de construção. A estrutura de dados 501 pode compreender um ou mais registros de dados 502 25 incluindo parâmetros de modelo global referentes ao modelo inteiro. Os exemplos de tais parâmetros de modelo incluem um nome de modelo, um nome do criador de um modelo, um número de versão de programa da aplicação de modelagem, uma data de criação, etc. A estrutura de dados de modelo 501 compreende ainda uma lista 503 ou outra estrutura apropriada 30 de registros de dados de elemento de construção. No exemplo da figura 5, a lista compreende N registros de dados "Elemento de construção 1", "elemento de construção 2", ..., "Elemento de construção J"....."Elemento de construção N". Cada registro de dados de elemento de construção da lista 503 tem a estrutura ilustrada pela estrutura de dados 504 para "Elemento de construção J".

Em particular, cada registro de dados de elemento de construção compreende um ID de elemento de construção 505, que indica um identificador correspondendo ao tipo de elemento de construção. O ID de elemento de construção pode identificar exclusivamente as propriedades do elemento de construção ou tipo de elemento de construção.

O registro de dados de elemento de construção pode compreender ainda um número de atributos de elemento de construção 506 indicando um ou mais atributos do elemento de construção, como cor, textura, decorações, etc.

Além disso, o registro de dados de elemento de construção 504 compreende itens de dados 507 e 508 que representam a posição e orienta15 ção de um sistema de coordenadas interno do elemento de construção, respectivamente. A posição e orientação do elemento de construção são definidas pelas coordenadas de uma origem do sistema de coordenadas interno do elemento de construção com relação a um sistema de coordenadas "mundial" global, e pela orientação do sistema de coordenadas interno com 20 relação ao sistema de coordenadas global.

Um exemplo de um formato de dados para armazenar modelos de elementos de construção que inclui uma hierarquia de sistemas de coordenadas é descrito na patente US número 6.389.375.

Além disso, o registro de dados do elemento de construção 504 25 pode compreender itens de dados 509 e 510 que representam uma ou mais caixas de limite e dados de conectividade do elemento de construção, respectivamente, utilizados na detecção de propriedades de conectividade do elemento de construção com outros elementos de construção. Uma modalidade de uma representação dos dados de conectividade do tipo de elemen30 tos de construção mostrados na figura 4 inclui estruturas de dados que representam os planos definidos pela superfície de uma caixa de limite do eIemento de construção. Os elementos de conexão do elemento de construção são localizados nesses planos, de tal modo que cada elemento de conexão tem um eixo geométrico associado a ele. Os eixos geométricos de todos os elementos de conexão no mesmo plano correspondem a respectivos pontos de grade de uma grade regular, por exemplo, uma grade ortogo5 nal, com distâncias fixas entre pontos de grade vizinhos. Os planos associados ao elemento de construção 401 da figura 4 são paralelos em pares entre si, e incluem um conjunto de planos horizontais que correspondem às superfícies superior e inferior do elemento de construção e um número de planos verticais correspondendo às superfícies laterais do elemento de construção. 10 As distâncias entre pontos de grade vizinhos podem ser iguais em todos os planos horizontais. Em algumas modalidades, as distâncias entre pontos de grade vizinhos em planos verticais são diferentes das distâncias entre pontos de grade vizinhos em planos horizontais. Uma representação digital das propriedades de conectividade dos elementos de construção do tipo mostra15 do na figura 4 são descritos em WO 04/034333 que é incorporada na íntegra aqui a título de referência.

Entende-se que a representação digital pode ser codificada em qualquer formato de arquivo ou dados apropriado, por exemplo, como um arquivo binário, como um arquivo de texto de acordo com linguagem de des20 crição de modelagem predeterminada, ou similar. Será adicionalmente entendido que outras modalidades de informação digital podem utilizar estruturas de dados alternativas ou adicionais e/ou representam dados de modelo alternativos ou adicionais.

A figura 6 ilustra uma modalidade de uma interface de usuário 25 gráfico de um programa de aplicação de instrução de construção. A interface de usuário compreende uma área de visualização 701 que ilustra uma representação gráfica de uma etapa de um conjunto de instruções de construção de etapa por etapa. A representação gráfica mostra uma vista 3D de um modelo em peças 702 mostrado a partir de uma posição de câmera prede30 terminada. O modelo em peças 702 consiste em um subconjunto de todos os elementos de construção do modelo completo, onde o subconjunto inclui os elementos de construção inicialmente posicionados. A área de visualização 701 compreende ainda uma representação gráfica 703 dos elementos de construção mais recentemente colocados, isto é, os elementos de construção que distinguem o presente modelo em peças 702 do modelo em peças da etapa anterior. Nesse exemplo, são os elementos de construção 714, 5 715, e 716 do modelo em peças 702.

A interface de usuário compreende ainda um elemento de controle deslizante 709 que pode ser movido em intervalos distintos por uma operação de arrasto correspondente com o mouse, permitindo que um usuário selecione alguma das etapas das instruções etapa por etapa. No exemplo 10 da figura 6, três elementos de construção novos são acrescentados em cada etapa das instruções.

A interface de usuário compreende ainda elementos de controle de botão 705 que permitem que um usuário invoque um número de funções frequentemente utilizadas como movimento seqüencialmente através das 15 representações gráficas em uma direção para frente e para trás, respectivamente, saltando para a primeira e última etapa das instruções, alterando a posição de câmera, imprimindo as instruções de construção geradas, e iniciando uma função "auto-play". A função auto-play exibe a seqüência de modelos em peças uma a uma de tal modo que cada modelo em peças é mos20 trada por um período de tempo predeterminado. Preferivelmente, o usuário pode configurar o tempo de visualização para cada modelo em peças na função auto-play.

Finalmente, a interface de usuário compreende diversos menus suspensos 704, permitindo que um usuário inicie funcionalidade como fun25 ção de ajudar, funções para alterar a posição da câmera, funções zoom, etc. Além disso, a funcionalidade fornecida pela aplicação de instrução de construção inclui o carregamento de representações digitais, uma função imprimir para imprimir as representações gráficas dos modelos em peças e funções exportar para exportar a seqüência de representações gráficas dos modelos 30 em peças, por exemplo, em um formato HTML ou qualquer outro formato de arquivo gráfico apropriado, como HF, JPG, BMP, etc.

Exemplos adicionais de funções fornecidas pela aplicação de instrução de construção incluem uma função de lista de material, permitindo a um usuário visualizar ou imprimir uma lista de todos os elementos de construção no modelo.

A figura 14 mostra um fluxograma de outra modalidade da geração de instrução de construção. Na etapa S1, o processo recebe uma representação digital M de um modelo de elemento de construção, por exemplo, como descrito com relação à etapa S1 da figura 2.

Nas etapas subsequentes S2 - S12, a aplicação de instrução de construção gera uma instrução de construção 205 a partir da representação digital carregada. A instrução de construção gerada 205 pode estar em uma forma como descrito com relação à figura 2.

Na etapa S2 o processo inicializa o processo. Em particular, o processo inicializa uma estrutura de dados Result para reter a seqüência de construção a ser gerada. O processo inicializa a seqüência Result para ser 15 uma seqüência vazia. O processo inicializa ainda um conjunto de elementos de construção candidatos, indicados Candidates, para ser o conjunto de todos os elementos de construção e submontagens no modelo M. Consequentemente, como nas modalidades anteriores, o processo pode determinar mais submontagens candidatas para retirada do modelo M e tratar submon20 tagens como elementos de construção generalizados. As submontagens candidatas podem ser encontradas/selecionadas por intermédio de um conjunto de critérios de seleção, que são uma determinação de como o modelo pode ser separado/cortado. Os exemplos de tais critérios de seleção foram descritos mais completamente acima, em particular o segundo conjunto de 25 critérios de seleção descrito com relação à etapa 303 da figura 3. Será reconhecido que em outras modalidades, o processo pode somente considerar elementos de construção.

Na etapa S3, o processo determina se o conjunto Candidates está vazio, isto é, se todos os elementos de construção foram processados. Se esse for o caso, o processo prossegue na etapa S12; de outro modo o processo prossegue na etapa S4.

Nas etapas S4-S11, o processo determina se uma etapa de construção b resultando em um novo modelo em peças pode ser encontrada de tal modo que o modelo completo M pode ser desconstruído nesse novo modelo em peças.

Em particular, na etapa S4, o processo gera um conjunto auxiliar 5 C de elementos de construção e submontagem como uma cópia do conjunto Candidates.

Na etapa S5, o processo determina se o conjunto C está vazio, isto é, se um candidato b foi identificado. Se esse for o caso, o processo retorna para a etapa S3; de outro modo o processo prossegue na etapa S6.

Na etapa S6, o processo seleciona um elemento de construção

candidato b - ou uma submontagem candidata - a partir do conjunto C.

A seleção de candidatos na presente modalidade pode ser feita em um modo similar ao da seleção de um elemento de construção para retirada no caso de desconstrução da modalidade anterior, isto é, por intermé15 dio de um conjunto de critérios de seleção. Em particular, os critérios de seleção podem ser baseados em uma ou mais funções de peso que representam estratégias de construção diferentes como uma ou mais das funções de peso descritas acima, em particular as funções de peso do primeiro conjunto de critérios de seleção descritos com relação à etapa 304 da figura 3. Algu20 mas funções de peso podem ser idênticas ou quase idênticas nas versões construtiva e desconstrutiva, respectivamente, por exemplo, como as funções de peso descritas em maior detalhe acima. Por exemplo, uma estratégia pode atribuir um peso a elementos de construção de acordo com sua distância a partir do elemento de construção acrescentado na etapa anterior. 25 O processo pode então selecionar o elemento de construção mais próximo ao elemento de construção anteriormente adicionado. Outras funções de peso podem ser bem diferentes. Por exemplo, a ‘estratégia de articulação’ no caso de desconstrução descrita acima, evita quebrar o gráfico de conectividade, ao passo que no caso construtivo da presente modalidade simples30 mente assegura que um elemento de construção é selecionado o qual efetivamente conecta a qualquer elemento de construção anteriormente selecionado. Não obstante, nos dois casos elementos de construção "que voam" são evitados. Uma vez que as funções de peso descritas aqui podem ponderar submontagens (elementos de pseudoconstrução) bem como elementos de construção simples, o processo tanto construtivo como desconstrutivo pode ser generalizado para tratar de submontagens. Como no caso destrutivo simples, isso não somente é prático como às vezes desejável.

Alternativa ou adicionalmente, a seleção de um candidato pode parcial ou totalmente ser baseado em uma interação/entrada de usuário. Por exemplo, o processo pode receber uma entrada de usuário indicativa de um candidato b. Alternativamente, o processo pode selecionar, por exemplo, 10 aleatoriamente ou com base nas funções de peso descritas acima, um ou mais candidatos possíveis e indicar o(s) candidato(s) para o usuário. O processo pode receber então uma entrada de usuário indicativa de uma aprovação ou rejeição de um ou mais candidatos sugeridos.

Na etapa S7, o processo gera uma seqüência de desconstrução 15 parcial a partir da representação digital recebida do modelo para baixo até o modelo residual obtenível pela união da seqüência de construção atual Result e o candidato selecionado b. A seqüência de desconstrução pode ser gerada na forma de uma lista seqüencial de elementos de construção e/ou submontagens do modelo. O processo pode gerar ainda seqüências de des20 construção subordinadas para as submontagens da lista seqüencial. Em uma modalidade, o processo representa a seqüência de desconstrução como uma árvore ramificada de etapas onde cada ramo pode conter desconstruções de construção subordinadas.

Uma modalidade de um processo para gerar uma seqüência de desconstrução parcial será descrita em maior detalhe abaixo.

Na etapa S8, o processo determina se uma seqüência de desconstrução poderia ser encontrada. Se o processo de desconstrução da etapa S7 obtiver sucesso na determinação de uma seqüência de desconstrução, o processo prossegue na etapa S9; de outro modo o processo prossegue na etapa S10.

Na etapa S9, o processo atualiza os conjuntos Candidates, Result e C. Em particular, o processo acrescenta o candidato selecionado b à seqüência de resultado atual Result1 retira o candidato b do conjunto de candidatos Candidates, e retira todos os elementos do conjunto auxiliar C (visto que um candidato bem sucedido foi identificado). O processo então retorna para S5.

5 Na etapa S10, o processo retira b do conjunto auxiliar C de can

didatos ainda a experimentar. Na etapa S11, o processo determina se há ainda candidatos restantes em C. Se esse for o caso, o processo retorna para a etapa S5 para identificar um candidato alternativo; de outro modo o processo termina, por exemplo, com uma mensagem ou indicador de erro 10 apropriado indicando que a geração de uma instrução de construção construtiva falhou. Por exemplo, essa situação pode ocorrer se o modelo for restrito em excesso e/ou se as funções de peso utilizadas durante o processo de desconstrução representando as limitações de construção do modelo forem demasiadamente fortes/restritivas. Consequentemente, em tais casos, 15 algumas ou todas as funções de peso utilizadas no processo de desconstrução podem ser relaxadas/enfraquecidas, por exemplo, automaticamente ou por uma interação de usuário, e o processo pode ser reiniciado com as funções de peso relaxadas.

Na etapa S12, o processo gera instruções de construção a partir 20 da seqüência de construção gerada Result, por exemplo, como uma seqüência de imagens ou outras representações de modelos em peças, onde em cada modelo em peças um ou mais dos elementos de construção e submontagens a partir da lista gerada Result são adicionados em comparação com o modelo em peças anterior. O processo pode armazenar as instru25 ções geradas e/ou transmitir as mesmas em qualquer forma apropriada como descrito aqui.

A figura 15 mostra um fluxograma de um exemplo de um processo de desconstrução parcial de um modelo M para baixo até um modelo residual N. O processo de desconstrução desconstroi o modelo M com base 30 em uma representação digital do modelo completo M, incluindo todos os eIementos de construção no modelo (etapa 301). A entrada do modelo M inclui informações sobre os elementos de construção individuais, como tamanho/dimensões, número de botões, características especiais como articulações, pinos, eixos, etc, dos elementos de construção. A representação digital também inclui informações sobre onde no modelo cada elemento de construção é colocado, por exemplo, por especificar as posições respectivas (x, 5 y, z) dos elementos de construção com relação a um sistema de coordenadas apropriado. O processo recebe ainda informações sobre o conjunto residual N, isto é, um submodelo do modelo M. O processo de desconstrução parcial gera uma seqüência de etapas de desconstrução, onde em cada etapa de desconstrução um ou mais elementos de construção de M\N (isto é, 10 elementos de construção do modelo M que não são incluídos no modelo residual N) são retirados até que somente o modelo residual N seja deixado.

Na etapa 302 o processo de desconstrução testa se há elementos de construção restantes no modelo M\N (ou um modelo em peças M’\N resultante de uma iteração anterior) a serem desconectados. Se houver ain15 da elementos de construção a serem retirados no modelo, o processo prossegue na etapa 303 onde o processo seleciona/gera uma ou mais submontagens candidatas para retirada do modelo M\N (ou um modelo em peças M’\N resultante de uma iteração anterior). As submontagens candidatas incluem elementos de construção interconectados. Na etapa subsequente 20 304, o processo seleciona um elemento de construção ou uma das submontagens candidatas geradas (E) a serem desconectadas de acordo com um primeiro conjunto de critérios de seleção predeterminados, por exemplo, como descrito com relação à figura 3. As submontagens candidatas na etapa 303 podem ser encontradas/selecionadas por intermédio de um segundo 25 conjunto de critérios de seleção, que são uma determinação de como o modelo pode ser separado/cortado. Os exemplos de tais critérios de seleção foram descritos mais completamente acima.

Na etapa 305, o processo desconecta o elemento de construção ou submontagem E selecionado na etapa 304 do modelo, isto é, gera um novo modelo em peças M’=M/E onde o elemento de construção selecionado de todos os elementos de construção da submontagem candidata selecionada é retirado. O processo pode manter uma estrutura de dados indicativa da seqüência de desconstrução, e atualizar a estrutura de dados com informações sobre b elemento de construção/submontagem desconectado.

Se o processo selecionar uma submontagem para ser desconectada, a submontagem selecionada pode ser desconstruída por executar o processo de desconstrução em um modo recursivo na etapa 307 (isto é, com a submontagem selecionada Eeo modelo residual N servindo como entradas), antes de retornar à etapa 302 para continuar o processo de desconstrução iterativo e encontrar o elemento de construção seguinte a desconectar do modelo em peças restante, isto é, o modelo M’\N = M\(EuN).

Quando não há mais elementos de construção para serem removidos do modelo M que não fazem parte também do modelo residual N, as desconstruções parciais do modelo M para baixo em modelo residual N são concluídas, e o processo de desconstrução para na etapa 308.

Consequentemente, geralmente verificou-se que para um dado modelo M, se M pode ser desconstruído em N, então N pode ser construído em M. Em outras palavras, uma construção no estágio N é um modelo intermediário apropriado durante uma seqüência de etapas de construção, se (e somente se) o modelo total M pode ser desconstruído para baixo no mesmo.

A modalidade de um processo para gerar uma seqüência de construção descrita com relação às figuras 14 e 15 pode ser expressa pelo seguinte pseudocódigo: Construct niodel Μ:

Let Candidates be. the set of ali briçkg and aubassemblies in M Let Result be an empty sequence of bricks

Whíle !Candidatas is rsot empty)

Let C be a copy of Candidates

While (C is not empty}

Let b be a brick from C

If (Decoostruct M down to Ianion of Result and b) ) Remove ali. bricks from C Candidates = Candidates \ b Add b to Result Else

Eemove b fxoro C If {C is empty)

Let Candidates be fche set of ali bricks in M/N;

Mhile iÇandidstes is not empty)

Let D be tfee subset of Caadidates that are detacfaable If {D is empty)

Returo False;

Else

Let b be the "best detachable" bxick from D;

Remove h from Candidates;

Return True;

No pseudocódigo acima a seleção do bloco "mais bem desprendível" corresponde à seleção executada na etapa 304 acima, isto é, uma seleção baseada em um conjunto de critérios de seleção predeterminados, por exemplo, um ou mais dos critérios de seleção descritos acima.

Uma modalidade do processo também pode ser expressa pelo seguinte pseudocódigo; um fluxograma dessa modalidade é mostrado na figura 16:

Construct model M:

Let Candidates be the set of ali bricks and suhassemblies in M Let Result be a ti empty seguence of bricks

While iCandidates is not empty)

Let C be a copy of Candidates If (Find construction step b from C)

Add b t.o Re s-u It Candidates = Candidates \ b Ilse

Error: "constxuctive Building instruction not possible”'

Return False

Retnrn True

Find construction step b from C:

While (C .is not empty)

Let b be a 'good' brick from C

If (Deconstruct M dcwn to {union of Result and b) }

Return True Else

Remove b from C

Return False, Consequentemente, nessa modalidade, a determinação com relação a se uma etapa de construção seguinte b pode ser encontrada é implementada como uma função separada. A figura 16a mostra o processo geral, enquanto a figura 16b mostra um fluxograma de um exemplo da fun5 ção que identifica uma etapa de construção seguinte válida/possível.

O processo inicia com uma etapa de entrada S1 e uma etapa de inicialização S2 como descrito com relação à figura 14. Na etapa S3, o processo determina se o conjunto Candidates está vazio, isto é, se todos os elementos de construção foram processados. Se esse for o caso, o processo 10 prossegue na etapa S12 com a geração das instruções de construção como descrito acima; de outro modo o processo prossegue na etapa S4.

Na etapa S4, o processo gera um conjunto auxiliar C de elementos de construção e submontagem como uma cópia do conjunto Candidates.

Na etapa S20 o processo determina se uma etapa de constru15 ção seguinte válida b pode ser encontrada. Se esse for o caso, o processo atualiza as estruturas de dados Results e Candidates, por anexar a etapa identificada b à estrutura de dados Results, e por retirar o elemento de construção correspondente (ou submontagem) a partir da estrutura de dados Candidates; o processo retorna então para a etapa S3. Se nenhuma etapa 20 de construção válida puder ser encontrada, o processo termina, por exemplo, com um indicador de erro apropriado ou mensagem indicando que a geração de uma instrução de construção construtiva falhou, como descrita com relação à figura 14.

A figura 16a mostra um fluxograma de um exemplo de etapa de implementar subprocesso S20: inicialmente, o processo determina se o conjunto C está vazio, isto é, se todos os candidatos b foram processados. Se esse for o caso, o processo retorna um valor indicado que nenhum candidato válido b pode ser encontrado; de outro modo o processo prossegue na etapa S6.

Na etapa S6, o processo seleciona um elemento de construção candidato b - ou uma submontagem candidata - a partir do conjunto C, por exemplo, como descrito com relação à etapa S6 da figura 14.

Na etapa S7, o processo gera uma seqüência de desconstrução parcial a partir da representação digital recebida do modelo para baixo ao modelo residual obtenível pela união da seqüência de construção atual Result e o candidato selecionado b, como descrito com relação à etapa S7 da figura 14.

Se o processo de desconstrução da etapa S7 tiver sucessão na

determinação de uma seqüência de desconstrução, o processo retorna um valor indicando que o processo teve sucesso; de outro modo o processo prossegue na etapa S10.

Na etapa S10, o processo remove b do conjunto auxiliar C de candidatos ainda a experimentar, e retorna ao início do subprocesso para determinar se C está vazio.

Nesse exemplo, a função "Deconstruct modelo M down to N" pode ser a mesma função como no exemplo acima.

Nas modalidades descritas com relação às figuras 14-16, uma construção de um modelo com N elementos de construção toma N etapas de construção, e geralmente para cada etapa de construção, várias desconstruções podem ter de ser feitas para encontrar um bloco candidato b que é válido.

O número de iterações exigidas pode ser estimado como a se20 guir: uma instrução de construção construtiva completa de N blocos necessita aproximadamente N etapas de construção. Cada etapa de construção pode necessitar aproximadamente N/2 desconstruções. Cada desconstrução consiste em aproximadamente N etapas de desconstrução. Cada etapa de desconstrução requer aproximadamente N/2 ponderações de bloco. No total, 25 uma Instrução de Construção construtiva total pode exigir até aproximadamente (ΝΛ4)/4 ponderações de elementos de construção. Isso é ainda muito melhor do que χΛΝ ponderações necessárias para uma busca de retrocesso simples. Similarmente, o processo desconstrutivo total descrito com relação às figuras 2 e 3 requer aproximadamente (ΝΛ2)/2 ponderações.

Claims

1. Método implementado por computador de gerar instruções de construção para um modelo de elemento de construção, o modelo incluindo uma pluralidade de elementos de construção, as instruções de construção sendo indicativas de uma ordem seqüencial de etapas de construção para construir o modelo de elemento de construção, cada etapa de construção incluindo acrescentar pelo menos um elemento de construção ao modelo de elemento de construção; o método compreendendo: - determinar, de uma representação digital do modelo de elemento de construção, pelo menos uma seqüência de etapas de desconstrução para pelo menos parcialmente desconstruir o modelo de elemento de construção em elementos de construção, cada etapa de desconstrução incluindo retirar pelo menos um elemento de construção a partir do modelo de elemento de construção; - determinar pelo menos uma etapa de construção da ordem seqüencial de etapas de construção com base pelo menos em uma pluralidade de etapas de desconstrução; em que a determinação da seqüência de etapas de desconstrução compreende executar um processo iterativo, em que uma iteração do processo iterativo compreende: - obter um modelo em peças anterior resultante de uma iteração anterior; - determinar pelo menos um elemento de construção a desconectar do modelo em peças anterior resultando em um novo modelo em peças, em que a determinação de pelo menos um elemento de construção a desconectar do modelo em peças anterior inclui: - determinar um conjunto de submontagens candidatas do modelo em peças anterior, cada submontagem candidata incluindo elementos de construção interconectados respectivos do modelo em peças anterior; em que a determinação do conjunto de submontagens candidatas compreende selecionar as submontagens candidatas de acordo com um segundo conjunto de critérios de seleção; e em que pelo menos um do segundo conjunto de critérios de seleção inclui determinar uma resistência de conexão da conexão de uma ou mais das submontagens candidatas com o modelo em peças anterior; - selecionar, de acordo com um primeiro conjunto de critérios de seleção predeterminados, um elemento de construção único ou um do conjunto determinado de submontagens candidatas para ser desconectado do modelo em peças anterior resultando no novo modelo em peças.

2. Método de acordo com a reivindicação 1; em que os elementos de construção são interconectáveis ao longo de pelo menos duas direções de construção; e em que pelo menos um do segundo conjunto de critérios de seleção inclui determinar uma ou mais posições no modelo em peças anterior em que uma alteração em direção de construção ocorre.

3. Método de acordo com qualquer uma das reivindicações 1 e2; em que um ou mais elementos de construção inclui um elemento conector para fornecer uma conexão móvel em torno de pelo menos uma direção; e em que pelo menos um do segundo conjunto de critérios de seleção inclui determinar uma ou mais submontagens conectadas de forma móvel ao modelo em peças anterior.

4. Método de acordo com qualquer uma das reivindicações 1 a3, compreendendo ainda determinar uma seqüência de etapas de desconstrução para cada submontagem selecionada para retirada durante iteração do processo iterativo.

5. Método de acordo com qualquer uma das reivindicações 1 a4, compreendendo representar o modelo em peças anterior por uma estrutura de dados indicativa de um gráfico que incluem nós indicativos de elementos de construção respectivos do modelo em peças anterior e bordas que conectam nós respectivos indicativos de conexões entre elementos de construção correspondentes.

6. Método de acordo com a reivindicação 5, em que uma borda do gráfico tem um valor de resistência de conexão associado indicativo de uma resistência de conexão de uma conexão entre elementos de construção correspondendo a nós conectados pela borda.

7. Método de acordo com a reivindicação 6, em que cada elemento de construção compreende um ou mais elementos de conexão adaptado para engatar com um ou mais elementos de conexão correspondentes de outro elemento de construção para fornecer uma conexão entre o elemento de construção e o outro elemento de construção, cada elemento de conexão tendo associado a ele uma classe de elemento de conexão, cada classe de elemento de conexão tendo associado a ela uma resistência de conexão e em que o método compreende determinar o valor de resistência de conexão associada de uma borda correspondendo a uma conexão entre dois elementos de construção pelo menos do número e classes respectivas de elementos de conexão contribuindo para a conexão correspondente.

8. Método de acordo com a reivindicação 6 ou 7, em que a determinação do valor de resistência de conexão associado compreende determinar a resistência de conexão do número e classes respectivas de elemento de conexão que contribuem para a conexão correspondente e de um volume dos dois elementos de construção.

9. Método de acordo com qualquer uma das reivindicações 5 a 8, compreendendo executar um processo de divisão de gráfico para determinar um conjunto de submontagens candidatas do modelo em peças anterior inclui.

10. Método de acordo com qualquer uma das reivindicações 5 a 9, em que uma borda do gráfico tem um valor associado indicativo de uma direção de construção de uma conexão entre elementos de construção que correspondem a nós conectados pela borda.

11. Método de acordo com qualquer uma das reivindicações 5 a 10, compreendendo identificar um ou mais nós de articulação do gráfico de modo a determinar um conjunto de submontagens candidatas do modelo em peças anterior.

12. Método de acordo com qualquer uma das reivindicações 5 a 11, compreendendo identificar um ou mais pares de nós de articulação do gráfico de modo a determinar um conjunto de submontagens candidatas do modelo em peças anterior.

13. Método de acordo com qualquer uma das reivindicações 5 a . 12, em que um ou mais elementos de construção inclui um conector para fornecer uma conexão móvel em torno de pelo menos uma direção, e em que pelo menos um entre um nó e uma borda do gráfico tem um valor associado indicativo de uma presença de uma conexão móvel.

14. Método de acordo com qualquer uma das reivindicações 1 a .13, em que a determinação de pelo menos um elemento de construção a desconectar do modelo em peças anterior resultando em um novo modelo em peças compreende computar uma ou mais funções de peso para pelo menos um de um subconjunto dos elementos de construção e um conjunto de submontagens candidatas de elementos de construção; e selecionar um de um elemento de construção único e uma submontagem baseado em uma comparação das funções de peso computadas.

15. Método de acordo com a reivindicação 14, em que pelo menos uma de uma ou mais funções de peso tem uma faixa de resultados possíveis incluindo uma primeira subfaixa indicativa de um grau de adequação a ser desconectado e uma segunda subfaixa indicativa de um grau de inadequação para ser desconectada.

16. Método de acordo com a reivindicação 15, em que a seleção de um único elemento de construção ou submontagem baseada em uma comparação das funções de peso computadas inclui computar um peso total de uma ou mais funções de peso computadas; em que a computação do peso total inclui atribuir um valor na segunda faixa ao peso total, se pelo menos uma das funções de peso computadas tiver um resultado na segunda faixa.

17. Método de acordo com qualquer uma das reivindicações 14 a 16, em que cada elemento de construção inclui um ou mais elementos de conexão para engatar com um ou mais elementos de conexão correspondentes de outro dos elementos de construção; em que cada elemento de conexão define uma direção de desconexão ao longo da qual o elemento de construção é desconectável de outro elemento de construção; e em que o cálculo de uma primeira de uma ou mais funções de peso para um elemento de construção ou submontagem compreende determinar se as respectivas direções de desconexão de todos os conectores do elemento de construção ou submontagem que são conectados a um ou mais outros elementos de construção do modelo em peças anterior são paralelos entre si.

18. Método de acordo com a reivindicação 17, em que o cálculo da primeira função de peso para um elemento de construção ou submontagem compreende ainda determinar uma distância mínima entre o elemento de construção ou submontagem para qualquer outro elemento de construção ou submontagem do modelo em peças anterior em uma direção de desconexão.

19. Método de acordo com a reivindicação 17, em que o cálculo da primeira função de peso para um elemento de construção ou submontagem compreende ainda - determinar uma geometria estirada do elemento de construção ou submontagem, em que a geometria estirada é estirada em uma direção de desconexão, e - determinar se a geometria estirada intersecta com qualquer outro elemento de construção ou submontagem do modelo em peças anterior.

20. Método de acordo com qualquer uma das reivindicações 14 a 19, em que o cálculo de uma segunda de uma ou mais funções de peso para um elemento de construção ou submontagem compreende ainda determinar se o elemento de construção ou submontagem é um elemento de construção de articulação ou submontagem.

21. Método de acordo com qualquer uma das reivindicações 14 a 20, em que o cálculo de uma terceira de uma ou mais funções de peso para um elemento de construção ou submontagem compreende ainda determinar se o elemento de construção ou submontagem é uma parte de um par de articulação de elementos de construção ou submontagens.

22. Método de acordo com qualquer uma das reivindicações 14 a 21, em que uma quarta de uma ou mais funções de peso para um elemento de construção ou submontagem é uma função que diminui com o número de outros elementos de construção aos quais o elemento de construção ou submontagem está conectado.

23. Método de acordo com qualquer uma das reivindicações 14 a 22, em que uma quinta de uma ou mais funções de peso é uma função de uma resistência de conexão de conexões entre elementos de construção ou submontagem.

24. Método de acordo com a reivindicação 23, em que o cálculo da quinta função de peso compreende determinar uma resistência de conexão mais fraca entre elementos de construção interconectados da submontagem, e em que a quinta função de peso é uma função decrescente da resistência de conexão mais fraca determinada.

25. Método de acordo com qualquer uma das reivindicações 14 a 24, em que uma sexta de uma ou mais funções de peso é uma função de uma resistência de conexão de conexões de elementos de construção de uma submontagem com outros elementos de construção do modelo em peças anterior.

26. Método de acordo com a reivindicação 25, em que o cálculo da sexta função de peso compreende determinar uma resistência de conexão mais forte entre os elementos de construção da submontagem e um ou mais outros elementos de construção do modelo em peças anterior não incluído na submontagem, e em que a sexta função de peso é uma função decrescente da resistência de conexão mais forte determinada.

27. Método de acordo com qualquer uma das reivindicações 14 a 24, em que uma sétima de uma ou mais funções de peso de um elemento de construção ou submontagem é uma função de uma coordenada de uma posição do elemento de construção ou submontagem ao longo de uma direção predeterminada em relação a um sistema de coordenadas.

28. Método de acordo com qualquer uma das reivindicações 14 a 27, em que uma oitava de uma ou mais funções de peso de um elemento de construção ou submontagem é uma função de pelo menos uma propriedade do elemento de construção e submontagem e uma propriedade de um elemento de construção ou submontagem desconectada durante uma iteração anterior do processo iterativo.

29. Método de acordo com a reivindicação 28, em que a oitava função de peso é uma função de uma distância entre o elemento de construção ou submontagem e um elemento de construção ou submontagem desconectado durante uma iteração anterior do processo iterativo.

30. Método de acordo com a reivindicação 28 ou 29, em que a oitava função de peso é uma função de uma medida predeterminada de similaridade indicativa de pelo menos uma relação espacial predeterminada entre o elemento de construção ou submontagem e um elemento de construção ou submontagem desconectada durante uma iteração anterior do processo iterativo, e uma comparação de um ou mais atributos associados ao elemento de construção ou submontagem e um elemento de construção ou submontagem desconectado durante uma iteração anterior do processo iterativo.

31. Método implementado por computador de gerar instruções de construção para um modelo de elemento de construção, o modelo incluindo uma pluralidade de elementos de construção, as instruções de construção sendo indicativas de uma ordem seqüencial de etapas de construção para construir o modelo de elemento de construção, cada etapa de construção incluindo acrescentar pelo menos um elemento de construção ao modelo de elemento de construção; o método compreendendo executar um processo iterativo, em que uma iteração do processo iterativo compreende: - obter uma ordem seqüencial de etapas de construção resultante de uma iteração anterior, a ordem seqüencial de etapas de construção resultando em um primeiro modelo em peças; - determinar uma etapa de construção subsequente da ordem seqüencial de etapas de construção baseada pelo menos em uma pluralidade de etapas de desconstrução por executar as seguintes etapas: - determinar uma etapa de construção candidata indicativa de uma conexão de pelo menos um elemento de construção subsequente ao primeiro modelo em peças resultando em um segundo modelo em peças, - determinar, a partir de uma representação digital do modelo de elemento de construção, pelo menos uma seqüência de etapas de desconstrução para pelo menos desconstruir parcialmente o modelo de elemento de construção em elementos de construção, cada etapa de desconstrução incluindo retirar pelo menos um elemento de construção do modelo de elemento de construção de modo a determinar se o modelo de elemento de construção é desconstrutível por uma seqüência de etapas de desconstrução para desconstruir o modelo de elemento de construção resultando no segundo modelo em peças; - se o modelo de elemento de construção for determinado como sendo desconstrutível pela seqüência de etapas de desconstrução para desconstruir o modelo de elemento de construção resultando no segundo modelo em peças, anexando a etapa de construção subsequente candidata determinada como etapa de construção subsequente à ordem seqüencial obtida, de etapas de construção.

32. Método de acordo com a reivindicação 31, em que os elementos de construção são mutuamente interconectados.

33. Método de acordo com qualquer uma das reivindicações 1 a32, em que a representação digital inclui coordenadas de posição respectivas de cada um dos elementos de construção com relação a um sistema de coordenadas predeterminado.

34. Método de acordo com qualquer uma das reivindicações 1 a 33, compreendendo ainda gerar a representação digital do modelo de elemento de construção por meio de um ambiente de construção implementado por computador para construir interativamente um modelo de elemento de construção virtual.

35. Método de acordo com qualquer uma das reivindicações 1 a 34, compreendendo gerar uma seqüência de representações gráficas de uma seqüência correspondente de modelos em peças incluindo um modelo em peças inicial, uma seqüência de modelos em peças incrementais, e um modelo completo; em que cada um dos modelos em peças incrementais inclui todos os elementos de construção do modelo em peças incrementai imediatamente anterior da seqüência e um número predeterminado de elementos de construção adicionais a partir da pluralidade de elementos de construção, em que os elementos de construção adicionais são determinados pela seqüência determinada de etapas de construção.

36. Método de acordo com a reivindicação 35, compreendendo ainda fornecer uma interface de usuário que facilita uma manipulação controlada por usuário das representações gráficas geradas.

37. Sistema de processamento de dados tendo armazenado no mesmo, meios de código de programa adaptados para fazer com que o sistema de processamento de dados execute as etapas do método, como definido em qualquer uma das reivindicações 1 a 36, quando os meios de código de programa são executados no sistema de processamento de dados.

38. Produto de programa de computador compreendendo meio de código de programa adaptado para fazer com que um sistema de processarnento de dados execute as etapas do método como definido em qualquer uma das reivindicações 1 a 36, quando o meio de código de programa é executado no sistema de processamento de dados.

39. Produto de programa de computador de acordo com a reivindicação 38, compreendendo um meio legível por computador tendo armazenado no mesmo o meio de código de programa.

40. Sinal de dados de computador incorporado em uma onda portadora e representando seqüências de instruções que, quando executadas por um sistema de processamento de dados, fazem com que o sistema de processamento de dados execute as etapas do método como definido em qualquer uma das reivindicações 1 a 36.