Esferas Geodésicas: Refinamento de Malhas Triangulares

Posted Jan 29, 2026 Updated Jan 31, 2026

By João Pedro dos Reis Mendes

12 min read

Contexto

Este post documenta a solução de um exercício da disciplina de verão Temas de Computação Visual - 2026 do IMPA, especificamente sobre Modelagem Geométrica. O objetivo é criar um modelo geométrico de uma esfera geodésica através do refinamento progressivo de malhas triangulares, utilizando sólidos platônicos como base.

O Problema

O exercício propõe criar um modelo geométrico no formato OBJ para uma esfera geodésica, obtida refinando faces triangulares usando como malha inicial um sólido platônico de faces triangulares (tetraedro, octaedro ou icosaedro).

Requisitos principais:

Após cada refinamento, projetar os vértices na esfera unitária
Utilizar uma tabela hash para unificar os vértices
Exportar o resultado em formato OBJ

Fundamentação Teórica

Esferas Geodésicas

Uma esfera geodésica é uma aproximação poliédrica de uma esfera construída através da subdivisão iterativa de um poliedro base. O processo gera uma malha triangular cada vez mais refinada que se aproxima de uma esfera perfeita.

Sólidos Platônicos como Base

Existem três sólidos platônicos compostos apenas por faces triangulares:

Tetraedro: 4 vértices, 6 arestas, 4 faces
Octaedro: 6 vértices, 12 arestas, 8 faces
Icosaedro: 12 vértices, 30 arestas, 20 faces

Para este exercício, escolhi o icosaedro como malha inicial, pois ele possui o maior número de faces triangulares, resultando em uma aproximação mais uniforme da esfera desde o início.

Processo de Refinamento

O refinamento de cada triângulo segue o esquema de subdivisão 1-para-4:

Calcular o ponto médio de cada aresta do triângulo
Projetar esses pontos médios na esfera unitária
Conectar os pontos médios, criando 4 novos triângulos

Este processo quadruplica o número de faces a cada iteração:

Nível 0 (icosaedro): 20 faces
Nível 1: 80 faces
Nível 2: 320 faces
Nível 3: 1,280 faces
Nível $n$: $20 \times 4^n$ faces

Projeção na Esfera Unitária

Para garantir que todos os vértices permaneçam na superfície da esfera, após calcular cada ponto médio $\mathbf{p} = (x, y, z)$, aplicamos a normalização:

\[\mathbf{p}_{normalizado} = \frac{\mathbf{p}}{||\mathbf{p}||} = \frac{(x, y, z)}{\sqrt{x^2 + y^2 + z^2}}\]

Esta operação projeta o ponto radialmente sobre a esfera unitária.

Solução Implementada

Estrutura de Dados

O código utiliza três estruturas principais:

  
struct Vec3
{
    double x, y, z;
    
    Vec3 normalized() const
    {
        double len = std::sqrt(x*x + y*y + z*z);
        if (len > 0)
            return Vec3(x/len, y/len, z/len);
        return *this;
    }
    
    // Operador para usar como chave no map
    bool operator<(const Vec3& v) const
    {
        if (x != v.x) return x < v.x;
        if (y != v.y) return y < v.y;
        return z < v.z;
    }
};

  
struct Triangle
{
    int v1, v2, v3;
    Triangle(int a, int b, int c) : v1(a), v2(b), v3(c) {}
};

Unificação de Vértices com Hash Table

Um aspecto crucial da implementação é evitar a duplicação de vértices. Quando dois triângulos adjacentes são refinados, eles compartilham uma aresta e, consequentemente, devem compartilhar o mesmo ponto médio.

Para isso, utilizei um std::map como tabela hash:

  
std::map<std::pair<int, int>, int> midpointCache;

std::pair<int, int> makeKey(int a, int b)
{
    return (a < b) ? std::make_pair(a, b) : std::make_pair(b, a);
}

A função makeKey garante que a aresta entre os vértices $i$ e $j$ sempre gere a mesma chave, independentemente da ordem $(i,j)$ ou $(j,i)$.

Algoritmo de Refinamento

O método refine() implementa a subdivisão 1-para-4:

  
void refine() {
    std::vector<Triangle> newFaces;
    midpointCache.clear();
    
    for (const auto& tri : faces) {
        // Obtém os pontos médios de cada aresta
        int a = getMiddlePoint(tri.v1, tri.v2);
        int b = getMiddlePoint(tri.v2, tri.v3);
        int c = getMiddlePoint(tri.v3, tri.v1);
        
        // Cria 4 novos triângulos
        newFaces.push_back(Triangle(tri.v1, a, c));
        newFaces.push_back(Triangle(tri.v2, b, a));
        newFaces.push_back(Triangle(tri.v3, c, b));
        newFaces.push_back(Triangle(a, b, c));
    }
    
    faces = newFaces;
}

A função getMiddlePoint calcula e cacheia os pontos médios:

  
int getMiddlePoint(int v1, int v2)
{
    auto key = makeKey(v1, v2);
    
    // Verifica se já existe no cache
    auto it = midpointCache.find(key);
    if (it != midpointCache.end()) {
        return it->second;
    }
    
    // Calcula o ponto médio
    Vec3 p1 = vertices[v1];
    Vec3 p2 = vertices[v2];
    Vec3 middle = (p1 + p2) * 0.5;
    
    // Projeta na esfera unitária
    middle = middle.normalized();
    
    // Adiciona aos vértices
    vertices.push_back(middle);
    int index = vertices.size() - 1;
    
    // Armazena no cache
    midpointCache[key] = index;
    
    return index;
}

Inicialização do Icosaedro

Os vértices do icosaedro foram fornecidos :

  
void initializeIcosahedron() {
    vertices = {
        Vec3(0, 0.30901699437495, -0.5),
        Vec3(0.30901699437495, 0.5, 0),
        Vec3(-0.30901699437495, 0.5, 0),
        Vec3(0, 0.30901699437495, 0.5),
        Vec3(0, -0.30901699437495, 0.5),
        Vec3(-0.5, 0, 0.30901699437495),
        Vec3(0.5, 0, 0.30901699437495),
        Vec3(0, -0.30901699437495, -0.5),
        Vec3(0.5, 0, -0.30901699437495),
        Vec3(-0.5, 0, -0.30901699437495),
        Vec3(0.30901699437495, -0.5, 0),
        Vec3(-0.30901699437495, -0.5, 0)
    };
    
    // Normaliza para esfera unitária
    for (auto& v : vertices) {
        v = v.normalized();
    }
    
    // 20 faces do icosaedro
    faces = {
        Triangle(0, 2, 1), Triangle(3, 1, 2), Triangle(3, 5, 4),
        Triangle(3, 4, 6), Triangle(0, 8, 7), Triangle(0, 7, 9),
        Triangle(4, 11, 10), Triangle(7, 10, 11), Triangle(2, 9, 5),
        Triangle(11, 5, 9), Triangle(1, 6, 8), Triangle(10, 8, 6),
        Triangle(3, 2, 5), Triangle(3, 6, 1), Triangle(0, 9, 2),
        Triangle(0, 1, 8), Triangle(7, 11, 9), Triangle(7, 8, 10),
        Triangle(4, 5, 11), Triangle(4, 10, 6)
    };
}

Exportação para OBJ

O formato OBJ é simples e amplamente suportado:

  
void exportOBJ(const std::string& filename) {
    std::ofstream file(filename);
    
    file << std::fixed << std::setprecision(8);
    
    // Escreve os vértices
    for (const auto& v : vertices) {
        file << "v " << v.x << " " << v.y << " " << v.z << "\n";
    }
    
    // Escreve as faces (OBJ usa índices começando em 1)
    for (const auto& f : faces) {
        file << "f " << (f.v1 + 1) << " " << (f.v2 + 1) 
             << " " << (f.v3 + 1) << "\n";
    }
    
    file.close();
}

Execução e Resultados

O programa aceita o número de subdivisões como argumento:

  
g++ -std=c++11 -o geodesic prime.cpp
./geodesic 3

Saída:

Gerando esfera geodésica com 3 subdivisões...
Refinamento 1...
Refinamento 2...
Refinamento 3...
Arquivo exportado: geodesic_sphere_3.obj
Vértices: 642
Faces: 1280

Icosaedro Original

Após 3 refinamentos

Progressão do Refinamento

Nível	Vértices	Faces	Arestas
0	12	20	30
1	42	80	120
2	162	320	480
3	642	1,280	1,920
4	2,562	5,120	7,680
5	10,242	20,480	30,720
6	40,962	81,920	122,880

A relação de Euler para poliedros ($V - E + F = 2$) é mantida em todos os níveis, confirmando a integridade topológica da malha.

Análise de Complexidade

Complexidade Espacial

Vértices: $O(4^n)$ - cresce exponencialmente com o nível de refinamento
Faces: $O(4^n)$ - cada face se divide em 4
Cache: $O(E)$ onde $E$ é o número de arestas, proporcional ao número de faces

Complexidade Temporal

Por refinamento: $O(F)$ onde $F$ é o número de faces atual
Total para $n$ refinamentos: $O(\sum_{i=0}^{n-1} 4^i) = O(4^n)$

Código Completo

  
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <iomanip>
#include <sstream>

struct Vec3
{
    double x, y, z;
    
    Vec3(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) {}
    
    Vec3 operator+(const Vec3& v) const
    {
        return Vec3(x + v.x, y + v.y, z + v.z);
    }
    
    Vec3 operator*(double s) const
    {
        return Vec3(x * s, y * s, z * s);
    }
    
    double length() const
    {
        return std::sqrt(x*x + y*y + z*z);
    }
    
    Vec3 normalized() const
    {
        double len = length();
        if (len > 0)
        {
            return Vec3(x/len, y/len, z/len);
        }
        return *this;
    }
    
    bool operator<(const Vec3& v) const
    {
        if (x != v.x) return x < v.x;
        if (y != v.y) return y < v.y;
        return z < v.z;
    }
};

struct Triangle
{
    int v1, v2, v3;
    Triangle(int a, int b, int c) : v1(a), v2(b), v3(c) {}
};

class GeodesicSphere
{
private:
    std::vector<Vec3> vertices;
    std::vector<Triangle> faces;
    std::map<std::pair<int, int>, int> midpointCache;
    
    std::pair<int, int> makeKey(int a, int b)
    {
        return (a < b) ? std::make_pair(a, b) : std::make_pair(b, a);
    }
    
    int getMiddlePoint(int v1, int v2)
    {
        auto key = makeKey(v1, v2);
        
        auto it = midpointCache.find(key);
        if (it != midpointCache.end()) {
            return it->second;
        }
        
        Vec3 p1 = vertices[v1];
        Vec3 p2 = vertices[v2];
        Vec3 middle = (p1 + p2) * 0.5;
        
        middle = middle.normalized();
        
        vertices.push_back(middle);
        int index = vertices.size() - 1;
        
        midpointCache[key] = index;
        
        return index;
    }
    
public:
    void initializeIcosahedron()
    {
        vertices = {
            Vec3(0, 0.30901699437495, -0.5),
            Vec3(0.30901699437495, 0.5, 0),
            Vec3(-0.30901699437495, 0.5, 0),
            Vec3(0, 0.30901699437495, 0.5),
            Vec3(0, -0.30901699437495, 0.5),
            Vec3(-0.5, 0, 0.30901699437495),
            Vec3(0.5, 0, 0.30901699437495),
            Vec3(0, -0.30901699437495, -0.5),
            Vec3(0.5, 0, -0.30901699437495),
            Vec3(-0.5, 0, -0.30901699437495),
            Vec3(0.30901699437495, -0.5, 0),
            Vec3(-0.30901699437495, -0.5, 0)
        };
        
        for (auto& v : vertices)
        {
            v = v.normalized();
        }
        
        faces =
        {
            Triangle(0, 2, 1), Triangle(3, 1, 2), Triangle(3, 5, 4),
            Triangle(3, 4, 6), Triangle(0, 8, 7), Triangle(0, 7, 9),
            Triangle(4, 11, 10), Triangle(7, 10, 11), Triangle(2, 9, 5),
            Triangle(11, 5, 9), Triangle(1, 6, 8), Triangle(10, 8, 6),
            Triangle(3, 2, 5), Triangle(3, 6, 1), Triangle(0, 9, 2),
            Triangle(0, 1, 8), Triangle(7, 11, 9), Triangle(7, 8, 10),
            Triangle(4, 5, 11), Triangle(4, 10, 6)
        };
    }
    
    void refine()
    {
        std::vector<Triangle> newFaces;
        midpointCache.clear();
        
        for (const auto& tri : faces)
        {
            int a = getMiddlePoint(tri.v1, tri.v2);
            int b = getMiddlePoint(tri.v2, tri.v3);
            int c = getMiddlePoint(tri.v3, tri.v1);
            
            newFaces.push_back(Triangle(tri.v1, a, c));
            newFaces.push_back(Triangle(tri.v2, b, a));
            newFaces.push_back(Triangle(tri.v3, c, b));
            newFaces.push_back(Triangle(a, b, c));
        }
        
        faces = newFaces;
    }
    
    void exportOBJ(const std::string& filename) {
        std::ofstream file(filename);
        if (!file.is_open()) {
            std::cerr << "Erro ao abrir arquivo: " << filename << std::endl;
            return;
        }
        
        file << std::fixed << std::setprecision(8);
        
        for (const auto& v : vertices)
        {
            file << "v " << v.x << " " << v.y << " " << v.z << "\n";
        }
        
        for (const auto& f : faces)
        {
            file << "f " << (f.v1 + 1) << " " << (f.v2 + 1) << " " << (f.v3 + 1) << "\n";
        }
        
        file.close();
        std::cout << "Arquivo exportado: " << filename << std::endl;
        std::cout << "Vértices: " << vertices.size() << std::endl;
        std::cout << "Faces: " << faces.size() << std::endl;
    }
};

int main(int argc, char* argv[])
{
    int subdivisions = 2; 
    
    if (argc > 1) {
        subdivisions = std::atoi(argv[1]);
        if (subdivisions < 0 || subdivisions > 6)
        {
            std::cout << " deve estar entre 0 e 6" << std::endl;
            return 1;
        }
    }
    
    
    GeodesicSphere sphere;
    sphere.initializeIcosahedron();
    
    for (int i = 0; i < subdivisions; i++)
    {
        std::cout << "iteracao " << (i + 1)  << std::endl;
        sphere.refine();
    }
    
    std::stringstream filename;
    filename << "geodesic_sphere_" << subdivisions << ".obj";
    sphere.exportOBJ(filename.str());
    
    return 0;
}

Para compilar e executar:

g++ main.cpp -o esfera
./esfera 2  # Gera esfera com 2 subdivisões

Conclusão

A implementação de uma esfera geodésica através do refinamento de um icosaedro demonstra conceitos importantes de modelagem geométrica computacional, incluindo subdivisão de malhas, projeção em superfícies implícitas e otimização de estruturas de dados.

O uso de tabelas hash para unificação de vértices é essencial para manter a eficiência e a integridade topológica da malha. A progressão geométrica do número de faces ($4^n$) mostra a necessidade de cuidado ao escolher o nível de refinamento, equilibrando qualidade visual e uso de recursos computacionais.

O resultado é uma aproximação poliédrica de alta qualidade de uma esfera, útil em diversas aplicações como computação gráfica, simulações físicas, análise de elementos finitos e modelagem científica.

IMPA, Computação Visual

This post is licensed under CC BY 4.0 by the author.