C++ (Qt)struct Triangle { int m_index[3]; // индексы вертексов int m_iEdges[3]; // индексы ребер }; struct Edge { bool operator < ( const Edge & other ) const { return m_ver < other.m_ver; } // data typedef std::pair<int> TPair; TPair m_ver; // индексы вертексов ребра (first < second) TPair m_fac; // индексы фейсов (Triangle) шарящих ребро (second = -1 если ребро открыто)};
C++ (Qt) class Vertex { public: Vector3D coord; Vector3D normal; Vector3D texCoord; }; class Edge { public: int p1; //начало в правильном порядке обхода int p2; //конец int mid; //середина, или -1 если пока не делили int e1; //ребра полученные при делении int e2; //ребра полученные при делении Edge(int _p1 = -1, int _p2 = -1, int _mid = -1, int _e1m = -1, int _e2m = -1); }; class Triangle { public: Triangle(const Triangle &); Triangle(Mesh * m = 0, int _p1 = -1, int _p2 = -1, int _p3 = -1, int _e12 = -1, int _e23 = -1, int _e31 = -1); virtual ~Triangle(); int p1, p2, p3; //индексы вершин int e12, e23, e31; //индексы рёбер Vector3D P1() const; //вершина 1 Vector3D P2() const; //вершина 2 Vector3D P3() const; //вершина 3 bool IsVisible(float frustum[6][4], double r, Vector3D eye);}; void Mesh::Subdivine(int polygons, const QVector<Triangle> & triangles, float frustum[6][4]) { int iTr = triangles.size(); int vertex = vertices.size();//начальное число вертексов for(int i=0;i<iTr;++i) { newTriangles[i] = triangles[i]; //записываем начальные фейсы } QVector<Triangle> * pNewTriangles = &newTriangles, * pNewTriangles1 = &newTriangles1; QVector<Edge> * pEdges = &iEdges, * pNewEdges = &newEdges; int iEdge; //номер добавляемого ребра while(iTr < polygons) //мы хотим polygons фейсов { int iVisible = 0; for(int in = 0; in < iTr; ++in) { Triangle t = (*pNewTriangles)[in]; if(t.IsVisible(frustum, eye, R)) //стоит ли дяльше разбивать этот треугольник { visibleTriangles[iVisible] = t; ++iVisible; } } if(iVisible == 0) break; iTr = 0; iEdge=0; //новых ребер будет не больше 9*iVisible for(int iv = 0; iv < 9*iVisible; ++iv) { (*pNewEdges)[iv] = Edge(); } for(int iv = 0; iv < iVisible; ++iv) { Triangle t = visibleTriangles[iv]; Vertex p12, p13, p23; //новые вершины int i12, i13, i23, e1m12,e2m12,e1m31,e3m31,e2m23,e3m23; //новые ребра //выбираем индексы поделенного ребра или делим ребро if((*pEdges)[t.e12].mid >=0) { i12 = (*pEdges)[t.e12].mid; //точка середины if((*pNewEdges)[(*pEdges)[t.e12].e1m].p1 == t.p1) { e1m12 = (*pEdges)[t.e12].e1m; //ребра нового фейса e2m12 = (*pEdges)[t.e12].e2m; } else { e1m12 = (*pEdges)[t.e12].e2m; e2m12 = (*pEdges)[t.e12].e1m; } } else { p12.coord = (t.P1() + (t.P2() - t.P1())/2.).Normalized()*R; //проецируем середину на сферу vertices[vertex] = p12; //новый вертекс i12 = vertex; ++vertex; //новые 2 ребра (*pEdges)[t.e12].mid = i12; Edge e1(t.p1, i12), e2(t.p2, i12); (*pNewEdges)[iEdge] = e1; e1m12 = iEdge; ++iEdge; (*pEdges)[t.e12].e1m = e1m12; (*pNewEdges)[iEdge] = e2; e2m12 = iEdge; ++iEdge; (*pEdges)[t.e12].e2m = e2m12; } // //тоже самое для оставшихся ребер // //добавляем 4 фейса (*pNewTriangles1)[iTr] = Triangle(this, t.p1, i12, i13, e1m12, e1312, e1m31); (*pNewTriangles1)[iTr+1] = Triangle(this, t.p2, i23, i12, e2m23, e1223, e2m12); (*pNewTriangles1)[iTr+2] = Triangle(this, t.p3, i13, i23, e3m31, e2313, e3m23); (*pNewTriangles1)[iTr+3] = Triangle(this, i12, i23, i13, e1223, e2313, e1312); iTr += 4; } nEdges = iEdge; qSwap(pNewTriangles, pNewTriangles1); qSwap(pNewEdges, pEdges); } //переписываем результат edges = *pEdges; newTriangles = *pNewTriangles; nTriangles = iTr; nVertices = vertices.size(); }
C++ (Qt)bool IsVisible(float frustum[6][4], double r, Vector3D eye);
C++ (Qt)class Edge {public: int p1; // начало в правильном порядке обхода int p2; // конец int p3; // новое начало если ребро было обрезано фрустумом (p3 == p1 если нет, -1 если ребро невидимо) int p4; // новый конец... (p4 == p2 если нет, -1 если невидимо) bool operator < ( const Edge & other ) const { if (qMin(p1, p2) < qMin(other.p1, other.p2)) return triue; if (qMin(p1, p2) > qMin(other.p1, other.p2)) return false; return qMax(p1, p2) < qMax(other.p1, other.p2); } ...};
C++ (Qt)QVector<Edge> BuildEdges( QVector<Triangle> & tri ){ QVector<Edge> dst; QMap<Edge, int> eMap; for (int i = 0; i < tri.size(); ++i) { Triangle & t = tri[i]; for (int j = 0; j < 3; ++j) { Edge edge = t.GetEdge(j); int & val = eMap[edge]; if (!val) { // ребро еще не добавлено в мапу dst.push_back(edge); val = edge.size(); // сохраняем в мапе индекс ребра + 1 } t.SetEdgeIndex(j, val - 1); // вписываем индекс ребра в фейс } } return dst;}
