Geometria simples por trás de qualquer estrada

Na última postagem do blog, expliquei o que sustenta as estradas geradas proceduralmente: a estrutura de dados, ou seja, a informação mínima necessária para descrever qualquer trecho de infraestrutura viária. A resposta para essa pergunta fundamental foi um conjunto de seções transversais abstratas da estrada, cada uma armazenando um instantâneo de como a via se apresenta naquele ponto específico (ou, melhor dizendo, naquela linha). Chamei-as simplesmente de: perfis.

Uma boa analogia que não tive inspiração para fazer na ocasião era compará-las com splines de Bezier. Para armazenar uma spline de Bezier, não é necessário salvar toda a curva explicitamente, mas apenas os pontos de ancoragem e as posições dos manípulos. Com um pouco de matemática e algumas fórmulas, é possível reconstruir o caminho real a qualquer momento por meio de interpolação entre os pontos de controle.

No meu sistema, a representação baseada em perfis funciona da mesma forma. Os perfis são as informações de controle, e a geometria real que define o traçado da estrada é o resultado da interpolação desses perfis. Neste novo artigo, vou detalhar como estou calculando a parte roxa. Como interpolar entre esses perfis verdes para gerar trajetos suaves, paralelos e visualmente agradáveis?

Na minha primeira postagem, expliquei por que iniciei essa jornada: percebi que a maioria dos desenvolvedores de games estava usando a ferramenta errada para o trabalho, renderizando estradas expandindo uma spline de Bezier central. Desde o início, sabia que queria usar apenas linhas retas e arcos circulares para construir a forma real da estrada.

Com os pré-requisitos estabelecidos, reduzimos nosso problema a uma questão puramente geométrica: Dados dois perfis em posições e orientações arbitrárias, como conectamos seus respectivos pontos finais usando arcos paralelos e suaves?

Uma propriedade geométrica simples de círculos nos oferece uma simplificação imediata. Pontos igualmente espaçados ao longo de um raio traçam arcos concêntricos quando rotacionados ao redor do mesmo centro. Desde que nossos perfis tenham comprimentos iguais, precisamos resolver o trajeto apenas para um par de pontos finais correspondentes. Aplicando a mesma construção em toda a extensão do perfil, naturalmente resultam em trajetos paralelos.

O problema, então, se reduz a: Dados dois pontos AAA e BBB com seus respectivos vetores de direção dA⃗ e dB⃗, encontrar um arco circular que conecte AAA a BBB e seja tangente a dA⃗ em AAA e a dB⃗ em BBB.

Provavelmente você já adivinhou sem mergulhar nos cálculos. Dois pontos arbitrários, cada um com um vetor tangente prescrito, nem sempre podem ser conectados por um único arco circular tangente a ambos os vetores. Na verdade, trata-se de um caso especial e ótimo quando isso é possível, ou seja, quando os pontos coincidentemente estão sobre o mesmo círculo.

Pode parecer que nos encurralamos em uma situação sem saída. As restrições que estabelecemos simplesmente não podem ser satisfeitas. Mas, ao mesmo tempo, na vida real, estradas existem e são definidas apenas por arcos e linhas retas. A solução é aliviar um pouco as restrições, permitindo que cada arco também tenha uma extensão em linha reta até encontrar o ponto ao longo da linha tangente.

É assim que a construção se desenvolve:

O Teorema da Tangente-Raio nos diz que um raio é sempre perpendicular à tangente no ponto de contato. Portanto, se OM e OA são raios do mesmo círculo, isso significa que o círculo será tangente às linhas de continuação em M e A.

Só resta provar que OM = OA. A demonstração é bastante simples. Considere os triângulos retângulos OCM e OCA, ambos com a hipotenusa OC em comum. Como escolhemos M de forma que CM = CA, concluímos que os triângulos são congruentes e, portanto, OM = OA, comprovando que O é, de fato, o centro de um círculo que passa por M e A.

O trajeto final, portanto, é um arco de AAA a MMM seguido por uma linha reta de MMM a BBB. Uma linha reta, depois um arco. Essa é a técnica toda.

Alguns engenheiros de CAD podem ler isso e rir: “Isso é apenas um filete de canto”. Sim, o que acabei de descrever não é novidade; trata-se de uma construção conhecida como filete de duas linhas. Mas com um detalhe: um ponto tangencial sempre é fixo, e o outro é resolvido matematicamente. Uma forma ainda mais prática de visualizar isso (especialmente para quem usa ferramentas como Illustrator ou Figma) é pensar na aplicação de um raio de canto infinito em um canto de uma forma geométrica.

Agora que temos uma maneira confiável de suavizar um trajeto entre dois pontos finais com direções prescritas, podemos voltar ao problema real: conectar um perfil de origem a um perfil de destino.

Na maioria dos casos, isso é bastante direto. Se os dois perfis tiverem comprimentos iguais e suas linhas de continuação se intersectarem de forma razoável, conectar os perfis completos é apenas aplicar a mesma construção duas vezes em suas extremidades correspondentes. Em outras palavras, resolvemos o mesmo problema geométrico em ambos os lados da seção transversal da estrada, e as duas bordas naturalmente se manterão paralelas.

Assim, a maioria dos segmentos de estrada comuns se resume a repetir esse truque exato entre o perfil inicial e o final. É assim que o processo se desenvolve visualmente:

Claro, nem todo par válido de perfis está posicionado de forma tão conveniente que suas linhas de continuação se intersectam e podem formar um filete.

O próximo bloco na estrada (com licença pelo trocadilho) é resolver outros casos especiais, que na verdade não são tão excepcionais assim. O método acima simplesmente não funciona quando essas linhas de continuação não se intersectam. Imagine a seguinte configuração.

Este cenário é perfeitamente válido, pois estradas não apenas curvam, mas também podem se deslocar lateralmente. Em outras palavras, um veículo pode estar alinhado com as rodas posicionadas em AB em um momento e precisar chegar suavemente a CD. Na prática, isso significa que ele deve primeiro virar para um lado e depois para o outro, formando um trajeto em formato de “S”.

Um único arco não consegue estabelecer essa transição; pelo menos dois são necessários. Portanto, uma nova abordagem é necessária. Lembrei-me de ter visto esse tipo de deslocamento exatamente com trilhos de trem da LEGO enquanto brincava com minha filha.

Encadeando dois arcos com direções de curvatura opostas, obteríamos uma transição suave em formato de “S”. Foi então que percebi: não é necessário resolver tudo em um único passo. Basta encontrar uma maneira de conectar os mesmos blocos construtivos primários.

A tarefa é encontrar um perfil intermediário em algum ponto entre os dois que nos permita dividir o problema em dois, que já sabemos como resolver usando os mesmos dois ingredientes: linhas retas e arcos.

Embora eu tenha dito que splines não são uma boa opção como representação primária da forma de uma estrada, elas são perfeitas para uma coisa: encontrar uma posição e orientação candidata adequada para esse perfil intermediário. A melhor correspondência aqui é a spline cúbica de Hermite entre o centro do perfil de origem e o de destino.

A spline cúbica de Hermite recebe dois pontos A e B e dois vetores tangentes dA e dB, interpolando suavemente entre eles. Para t=0, obtemos o ponto inicial. Para t=1, o ponto final. Para qualquer valor de t entre 0 e 1, obtemos um trajeto suave que coincide com as direções tangentes especificadas em ambos os pontos finais.

Em teoria, o local “ideal” para inserir o perfil intermediário é no ponto de inflexão, onde a curva muda sua curvatura. Existe, na verdade, uma maneira matematicamente sofisticada de encontrar esse ponto exato calculando as derivadas de primeira e segunda ordem da spline e resolvendo uma equação polinomial de terceiro grau. Quem quiser se aprofundar pode conferir mais detalhes aqui.

Mas eu disse que a matemática era simples, certo? Na prática, não precisamos de tanta precisão. Para magnitudes razoáveis de dA e dB (aproximadamente entre 1.0 e 1.5 vezes a distância entre os pontos centrais), simplesmente avaliar a spline de Hermite em t=0.5 fornece uma aproximação muito boa de onde ocorre essa transição de curvatura.

Avaliar P(0.5) nos dá a posição central do perfil. (onde P(t) é a forma paramétrica da spline de Hermite)

Se, em um espaço cartesiano, a derivada primeira (variação em y sobre variação em x) indica a inclinação do gráfico em um valor específico de x, então, para uma curva paramétrica em 2D, a derivada primeira fornece o vetor velocidade: como o ponto se move à medida que t muda. Se pensarmos em t como tempo, isso representa tanto a velocidade quanto a direção do movimento.

No nosso caso, estamos interessados apenas na direção, que é, na verdade, a tangente. Simplesmente avaliar P’(0.5) fornece a direção tangente naquele ponto ao longo da curva. Do ponto de vista de programação, P e P’ são apenas fórmulas simples que são avaliadas em tempo constante (O(1)).

Até este ponto, podemos lidar com a maioria das conexões úteis entre perfis. Mas ainda existem alguns cenários especiais que merecem discussão.

O primeiro deles é quando as linhas de continuação são paralelas e apontam na mesma direção. Essa situação tem uma construção muito limpa: usar um semicírculo de um lado, seguido por um segmento reto.

A última família irritante de casos especiais é quando as linhas de continuação não se intersectam de uma forma que possa ser resolvida com um único perfil intermediário.

Tenho certeza de que, com esforço suficiente, uma solução universal pode ser construída para esses cenários também. Ficaria genuinamente feliz em ouvir ideias de pessoas que tenham sugestões aqui.

Mas, às vezes, basta aceitar algumas limitações na sua ferramenta e construir restrições de design que impeçam completamente o usuário de cair nesses cenários. Em vez de perseguir toda disposição impossível, decidi incorporar uma restrição diretamente na ferramenta de posicionamento de estradas.

Ao dividir o plano ao meio usando a linha infinita do perfil de origem, se o usuário tentar posicionar o próximo perfil no semiplano “atrás”, forço que esse novo perfil tenha a mesma orientação do perfil de origem. Isso reduz a configuração a um dos casos especiais mais simples acima, que já podem ser conectados de forma robusta.

Neste ponto, temos o bloco construtivo principal da rede viária: uma maneira de conectar dois perfis suavemente usando apenas linhas retas e arcos circulares. Isso nos dá a liberdade de desenhar estradas em qualquer formato.

O próximo passo é descobrir como estabelecer dinamicamente cruzamentos quando estradas se encontram e unir esses blocos construtivos em redes mais complexas. É sobre isso que falarei na próxima postagem do blog.

Para entender como encontrar matematicamente esse ponto de inflexão, precisamos pensar no que as derivadas de primeira e segunda ordem de uma curva paramétrica nos dizem sobre sua natureza naquele ponto. A derivada primeira P’(t) indica a direção do movimento, enquanto a derivada segunda P’’(t) mostra como essa direção muda ao longo do tempo, ou seja, como a curva está se curvando (sua curvatura).

Uma boa maneira de visualizar isso é pensar em P’(t) como a direção para onde os faróis do carro apontam e em P’’(t) como a direção em que o volante está virando. O ponto de inflexão é o momento em que essas duas direções se alinham; a curva brevemente para antes de mudar de direção.

Para determinar se dois vetores estão alinhados, podemos calcular o produto vetorial entre eles. O resultado é zero quando têm a mesma direção ou direções opostas. Portanto, matematicamente, encontrar o ponto de inflexão é equivalente a resolver a equação P’(t) × P’’(t) = 0.

Olá 👋 Eu compartilho uma nova postagem no blog aproximadamente uma vez por mês. Se você achar meu trabalho interessante e quiser ficar por dentro, cadastre seu e-mail abaixo. Garanto que nunca vou encher sua caixa de entrada com spam.