Как нарисовать 3D-ландшафт с треугольниками?

Question

У меня есть 3D-массив булевых элементов, который представляет собой 3D-ландшафт. В настоящее время я могу рисовать его, вычерчивая точку в позиции, заданной ее x y и z в массиве, и выглядит так.

Что я не могу понять, так это то, как я рисовал бы это с помощью треугольников, поэтому он выглядит как реальный ландшафт. Я тоже не хочу рисовать кубик.

Есть ли какие-либо алгоритмы для получения точек, которые нужно нарисовать (помните, что ради эффективности нужно нарисовать только точки на внешней стороне суши)?

Answer 1

Абсолютно замечательный вопрос! Я не мог удержаться, но играть с коробками, так как коробки сексуальны. На самом деле довольно легко создавать коробки с скрытыми лицами, опущенными.

Следующий алгоритм принимает список трехмерных позиций true в вашей сетке, который легко получить, просто просматривая сетку и заполняя массив. Также с этим форматом данных вы можете хранить гораздо большую сетку при условии, что ландшафт достаточно разрежен. Наверху, извинения за мои спартанские для каждого цикла, я просто хотел иметь код на месте и не писать десятки объектов функций или использовать лямбды. Также извинения за использование C++ вместо Java, у меня нет javac дома, и я все равно не очень хорош. Здесь идет:

#include <vector> 
#include <map> 
#include <set> 
#include <utility> 
#include <assert.h> 
#include <math.h> 

struct Pos3 { 
    int x, y, z; 

    Pos3(int _x = 0, int _y = 0, int _z = 0); 
    bool operator <(const Pos3 &other) const; 
}; 

std::vector<int> index_buffer; 
std::vector<float> vertex_buffer; 

void onInitialize() 
{ 
    const int N = 32; 
    std::vector<Pos3> points; 
    GeneratePoints(points, N); 
    // input: bunch of points in NxNxN box (easy to get from a boolean array, 
    // can have much larger terrains if stored like this) 

    std::set<Pos3> point_set; 
    point_set.insert(points.begin(), points.end()); 
    // put all the points to a set to be able to lookup neighbors (not needed with an array) 

    std::vector<std::vector<int> > polygons; 
    polygons.reserve(3 * points.size()); // guess 
    std::map<Pos3, int> vertex_map; 
    for(size_t i = 0, n = points.size(); i < n; ++ i) { 
     Pos3 p = points[i], corners[8] = { 
      p, Pos3(p.x + 1, p.y, p.z), Pos3(p.x + 1, p.y + 1, p.z), Pos3(p.x, p.y + 1, p.z), 
      Pos3(p.x, p.y, p.z + 1), Pos3(p.x + 1, p.y, p.z + 1), Pos3(p.x + 1, p.y + 1, p.z + 1), 
      Pos3(p.x, p.y + 1, p.z + 1) 
     }; 
     // get corners of a cube 

     static const int sides[][3 + 4] = { 
      0, -1, 0, 4, 5, 1, 0,   1, 0, 0, 5, 6, 2, 1, 
      0, 1, 0, 6, 7, 3, 2,   -1, 0, 0, 7, 4, 0, 3, 
      0, 0, -1, 0, 1, 2, 3,   0, 0, 1, 7, 6, 5, 4 
     }; 
     // directions and side quad indices 

     for(int j = 0; j < 6; ++ j) { 
      Pos3 n(p.x + sides[j][0], p.y + sides[j][1], p.z + sides[j][2]); // position of a neighbor 
      if(point_set.find(n) != point_set.end()) 
       continue; // have a neighbor, will not triangulate this side 

      polygons.resize(polygons.size() + 1); 
      std::vector<int> &poly = polygons.back(); // or use emplace_back() in c++11 
      poly.resize(4); // form quads 
      for(int v = 0; v < 4; ++ v) { 
       Pos3 vert = corners[sides[j][3 + v]]; 
       std::map<Pos3, int>::iterator it; // use map to reuse vertices 
       if((it = vertex_map.find(vert)) == vertex_map.end()) 
        vertex_map[vert] = poly[v] = vertex_map.size(); // new vertex 
       else 
        poly[v] = (*it).second; // existing vertex 
      } 
     } 
     // generate sides, skip invisible sides 
     // note that this still triangulates cavities, would have to flood-fill 
     // outside area and then set all that is not outside to opaque (did not 
     // solve that as this is also a valid behavior) 
    } 

    vertex_buffer.resize(vertex_map.size() * 3); 
    for(std::map<Pos3, int>::const_iterator it = vertex_map.begin(), e = vertex_map.end(); it != e; ++ it) { 
     size_t i = (*it).second * 3; 
     vertex_buffer[i + 0] = ((*it).first.x + .5f)/(N + 1) * 2 - 1; 
     vertex_buffer[i + 1] = ((*it).first.y + .5f)/(N + 1) * 2 - 1; 
     vertex_buffer[i + 2] = ((*it).first.z + .5f)/(N + 1) * 2 - 1; 
    } 
    // convert points from the discrete domain 
    // to a unit 3D cube centered around the origin 

    index_buffer.reserve(polygons.size() * 2 * 3); // approximate number of triangles 
    for(size_t i = 0, n = polygons.size(); i < n; ++ i) { 
     const std::vector<int> &poly = polygons[i]; 
     for(size_t j = 2, n = poly.size(); j < n; ++ j) { 
      index_buffer.push_back(poly[0]); 
      index_buffer.push_back(poly[j]); 
      index_buffer.push_back(poly[j - 1]); 
     } 
    } 
    // convert polygons (those are actually quads) to triangles 
} 

Существует и еще какой-то код, который генерирует нормали (опущено для ясности), выходной сигнал выглядит следующим образом:

форма представляет собой множество Жюлиа генерируется на дискретной решетке вы можете распознать фигуру, когда вы поворачиваете ее вокруг.

Это на самом деле очень похоже на то, что вы получили бы от триангуляции Делоне, если бы вы могли легко удалить свои внутренние точки. Сгенерированная форма полая. В форме могут быть некоторые «пузыри», в случае, если булевы также содержат пузырь (не происходит с Джулией). Это легко фиксируется путем заливки булевых элементов, чтобы заполнить их.

Далее мы можем применить Catmull-Clark подразделение для того, чтобы получить более гладкую сетку:

typedef std::map<std::pair<int, int>, std::pair<size_t, int> > EdgeMap; 

static bool Get_EdgeID(size_t &eid, int a, int b, EdgeMap &edges) 
{ 
    std::pair<int, int> e(std::min(a, b), std::max(a, b)); 
    EdgeMap::iterator it = edges.find(e); 
    if(it == edges.end()) { 
     edges[e] = std::make_pair(eid = edges.size(), 1); // id, count 
     return true; // new edge 
    } else { 
     eid = (*it).second.first; // get id 
     ++ (*it).second.second; // increase count 
     return false; // no new edge 
    } 
} 

void CatClark(std::vector<std::vector<int> > &src_quads, std::vector<float> &src_verts) 
{ 
    const static float vpw[4] = {9.0f, 3.0f, 1.0f, 3.0f}; 
    const static float epw[4] = {3.0f, 3.0f, 1.0f, 1.0f}; 

    std::vector<std::vector<int> > dst_quads(src_quads.size() * 4, std::vector<int>(4)); // will produce quads 
    std::vector<float> dst_verts(src_verts.size() + src_quads.size() * 3, 0); // alloc s¨pace for vertices 

    EdgeMap edges; 
    std::vector<int> face_valences(src_verts.size()/3, 0); 
    const size_t off_vp = src_quads.size(), off_ep = off_vp + src_verts.size()/3; 
    for(size_t j = 0; j < off_vp; ++ j) { 
     assert(src_quads[j].size() == 4); // otherwise won't work 
     size_t eid[4]; 
     for(int k = 0; k < 4; ++ k) { 
      int quad[4]; 
      for(int i = 0; i < 4; ++ i) 
       quad[i] = src_quads[j][(i + k) & 3]; // get the 4 vertices (but rotate them each k iteration) 
      if(Get_EdgeID(eid[k], quad[0], quad[1], edges)) // create edges 
       dst_verts.insert(dst_verts.end(), 3, .0f); // must add new vertex to accomodate subdivided edge point 
      ++ face_valences[quad[0]]; // update face-valence 
      for(int n = 0; n < 3; ++ n) 
       dst_verts[j * 3 + n] += 0.25f * src_verts[quad[0] * 3 + n]; // increment face point 
      for(int i = 0; i < 4; ++ i) { 
       for(int n = 0; n < 3; ++ n) { 
        dst_verts[(off_vp + quad[0]) * 3 + n] += vpw[i] * src_verts[quad[i] * 3 + n]; // incremente vertex point 
        dst_verts[(off_ep + eid[k]) * 3 + n] += epw[i] * src_verts[quad[i] * 3 + n]; // increment edge point 
       } 
      } 
     } 
     for(int k = 0; k < 4; ++ k) { // make child faces 
      dst_quads[4 * j + k][0] = j; 
      dst_quads[4 * j + k][4] = off_ep + eid[(3 + k) & 3]; 
      dst_quads[4 * j + k][5] = off_ep + eid[(0 + k) & 3]; 
      dst_quads[4 * j + k][6] = off_vp + src_quads[j][k]; 
     } 
    } 
    for(size_t j = 0, n = src_verts.size()/3; j < n; ++ j) { 
     for(int n = 0; n < 3; ++ n) 
      dst_verts[(off_vp + j) * 3 + n] *= 0.0625f/float(face_valences[j]); 
    } 
    for(EdgeMap::const_iterator it = edges.begin(), e = edges.end(); it != e; ++ it) { 
     size_t j = (*it).second.first; 
     float rvalence = 0.1250f/float((*it).second.second); 
     for(int n = 0; n < 3; ++ n) 
      dst_verts[(off_ep + j) * 3 + n] *= rvalence; 
    } 
    dst_quads.swap(src_quads); 
    dst_verts.swap(src_verts); 
} 

Этот алгоритм был адаптирован для работы с STL контейнеров из Иниго «IQ» Quilez/RGBA «, хитрости и приемы для прошлых и будущих входов rgba », Breakpoint, 2007.

Это дает результат, очень похожий на то, что вы получите с маршевыми кубами/маршевыми тетраэдрами/маршевыми треугольниками, за исключением того, что он всегда имеет более высокое разрешение, чем у исходной решетки (с помощью вышеуказанных методов вы можете легко изменить разрешение триангуляции). Несколько иной точки зрения тех же данных:

Или без каркасные:

Полный исходный код вместе с Visual Studio рабочего пространства и win32 двоичные файлы можно найти на here. Он использует GLUT и старый конвейер с фиксированной функцией для отображения сгенерированной геометрии (только для простоты и переносимости, в противном случае я должен был бы включить GLEW или тому подобное). Мне очень понравилось заниматься с вашим вопросом, надеюсь, вам понравится выход ...

Если вы хотите использовать маршевые кубики, вы можете найти много демо онлайн или зарегистрироваться this real-time water simulation I did a couple years ago.

Answer 2

Если у вас есть точки, характеризующие внешнюю оболочку вашей местности, этот пакет очень хорошо (быстро) для вычисления триангуляции Делоне этого множества точек:

http://www.cs.bgu.ac.il/~benmoshe/DT/

Вы можете позже сделать каждый треугольников от триангуляции. Я сделал пару или методы для преобразования все обратно удваивается для использования с JOGL, которые могут оказаться полезными:

public static ArrayList<Point_dt[]> DTtoTriListDT(Delaunay_Triangulation DT){ 
ArrayList<Point_dt[]> triangles = new ArrayList<Point_dt[]>(); 
Point_dt[] triangle = new Point_dt[3]; 

Iterator<Triangle_dt> surface = DT.trianglesIterator(); 
while(surface.hasNext()){ 
    Triangle_dt tri = surface.next(); 
    triangle[0] = tri.p1(); 
    triangle[1] = tri.p2(); 
    triangle[2] = tri.p3(); 
    triangles.add(triangle); 
} 

return triangles;} 

и

public static ArrayList<double[][]> DTtoTriList(Delaunay_Triangulation DT){ 
ArrayList<Point_dt[]> trianglesdt = Algebra.DTtoTriListDT(DT); 
ArrayList<double[][]> triangles = new ArrayList<double[][]>(); 
double[][] triangle = new double[3][3]; 

Iterator<Point_dt[]> surface = trianglesdt.iterator(); 
while(surface.hasNext()){ 
    Point_dt[] tri = surface.next(); 

    triangle[0][0] = tri[0].x(); 
    triangle[0][1] = tri[0].y(); 
    triangle[0][2] = tri[0].z(); 

    triangle[1][0] = tri[1].x(); 
    triangle[1][1] = tri[1].y(); 
    triangle[1][2] = tri[1].z(); 

    triangle[2][0] = tri[2].x(); 
    triangle[2][1] = tri[2].y(); 
    triangle[2][2] = tri[2].z(); 

    triangles.add(triangle); 
} 

return triangles; 

}

У меня есть все это в классе алгебры (FYI). С помощью последнего метода вы получаете ArrayList с наборами деревьев из трех удвоений на каждую запись (каждый набор содержит три координаты каждой точки, а каждая запись - один треугольник).