/* Stuff to convert */ /* Last edited on 2015-10-01 00:00:30 by stolfilocal */ salamic_r2_t salamic_mesh_Side_slice(salamic_mesh_i3_t *vi, salamic_mesh_i3_t *vj, float Z); /* Intersects the line {vi--vj} with a horizontal plane at the given {Z} coordinate. The line must not be horizontal. */ salamic_r2_Segment_t salamic_mesh_Face_slice(salamic_mesh_i3_face_t *t, float Z); /* Computes the intersection of a face {t} with an horizontal plane with given {Z}-coordinate, yielding a segment on that plane. Assumes that the intersection is not empty. */ /* DOUBLY LINKED LISTS OF FACES */ typedef struct salamic_mesh_Face_Node_t { salamic_mesh_i3_face_t *t; struct salamic_mesh_Face_Node_t *next; struct salamic_mesh_Face_Node_t *prev; } salamic_mesh_Face_Node_t; /* Node of a ddoubly linked list of face pointers. */ typedef struct salamic_mesh_Face_List_t { salamic_mesh_Face_Node_t *head; salamic_mesh_Face_Node_t *tail; } salamic_mesh_Face_List_t; /* Header of a doubly linked list of face pointers. */ salamic_mesh_Face_List_t salamic_mesh_Face_List_create (void); /* Creates the header of an enpty doubly linked list of faces. */ void salamic_mesh_Face_List_insert (salamic_mesh_i3_face_t *t, salamic_mesh_Face_List_t *l); /* Inserts the face ponter {t} in the doubly linked list whose header is {*l}. */ void salamic_mesh_Face_List_union (salamic_mesh_Face_List_t *l1, salamic_mesh_Face_List_t *l2); /* Appends all nodes of the doubly linked list whose header is {*l2} to the list whose header is {*l1}, making {*l2} empty. */ void salamic_mesh_Face_List_remove (salamic_mesh_Face_List_t *l, salamic_mesh_Face_Node_t *node); /* Removes the node {node} from the doubly linked list whose header is {*l}. */ vec_typedef(salamic_loop_vec_t,salamic_loop_vec,salamic_loop_t); typedef void salamic_closer_proc_t (salamic_mesh_t *mesh, float Z, vector *segs); /* Type of a procedure that may be called by a slicer to process a list of segments {segs} resulting from intersction of a mesh {mesh} with a horizontal plane at the given {Z} coordinate. */ /* Select the loop closing procedure: */ salamic_closer_t *closer = NULL; select (o->closer) in { case salamic_closer_TRIVIAL: closer = &closer_trivial; break; case salamic_closer_TOPO: closer = &closer_topo; break; case salamic_closer_BENTLEY: closer = &closer_bentley; break; default: assert(FALSE); } long timeIni = Timer::getTimeMs(); switch (checkASCIIFile(modelFile)) { // case FILE_AMF_ASCII: // if(0!=amfToMeshInMemory(modelFile, &mesh)) // return 1; // break; case FILE_STL_ASCII: if (stlToMeshInMemory(modelFile, &mesh, false)!=0) return 1; break; case FILE_STL_BIN: if (stlToMeshInMemory(modelFile, &mesh, true)!=0) return 1; break; case -1: cerr << "File error!!" << endl; return 1; break; default: cerr << "Unexpected error" << endl; return 1; break; } fprintf(stderr, "Mesh has %d faces\n", mesh.meshSize); // // Optional Model Rotation Around COG Point using GLM Library // glm::mat4 mat = glm::mat4(1.0f); // glm::fquat quaternion = glm::fquat(DEG_TO_RAD(eulerAngles)); // This glm func wants values as radians // float angle = glm::angle(quaternion); // glm::highp_fvec3 axis = glm::axis(quaternion); // mat = glm::rotate(mat, angle, axis); // mesh.transform(mat); // Generate Slices // vector > slicesWithLineSegs; string path = modelFile; string lastFile; size_t pos = path.find_last_of("/"); if(pos != std::string::npos) { lastFile.assign(path.begin() + pos + 1, path.end()); } else { lastFile = path; } struct stat filestatus; stat(modelFile, &filestatus); size_t fileSize = filestatus.st_size; // salamic_stl_r3_t aabb = mesh.meshAABBSize(); // if (stats) { // const size_t nSlices = 1+(int)(aabb.z/delta); // double sumTriHeight; // float avgTriHeight; // for (auto t : mesh.mesh) { // sumTriHeight += t.zMax - t.zMin; // } // avgTriHeight = sumTriHeight / mesh.size(); // cout << lastFile << "," << (int)aabb.x << " x " << (int)aabb.y << " x " << (int)aabb.z << "," << mesh.size() << "," << avgTriHeight << "," << (int)(fileSize/1024) << "," << delta << "," << nSlices << endl; // return 0; // } clock_t slice_begin = clock(); vector P = compute_P (&mesh, delta, deltaMin, deltaMax); fprintf(stderr, "Slicing with %d planes\n", (int)P.size()); /* The loop closing procedure: */ // vector closer (salamic_mesh_t *mesh, float Z, vector *segs) { // } // !!! Should sort mesh if requested. !!! bool_t srt = mesh.sorted; if (trivialSlicing) { salamic_stl_r3_trivial_slicing_slice (&mesh, P, NULL); } // else if (huang) { // Huang (&mesh, slicesWithLineSegs, delta, P); // } // else if (sang) { // Sang (&mesh, slicesWithLineSegs, delta, P); // } else if (incrementalSlicing) { salamic_r3_incremental_slicing_slice (&mesh, P, delta, srt, NULL); } long slice_end = Timer::getTimeMs(); timeslice = double(slice_end - slice_begin)/CLOCKS_PER_SEC; // long timeEnd = Timer::getTimeMs(); // // timeTotal = timeEnd - timeIni; // lock_t contour_begin = clock(); // lock_t contour_end = clock(); // imecontour = double(contour_end - contour_begin)/CLOCKS_PER_SEC; // // // // lock_t slice_begin = clock(); // // // clock_t slice_end = clock(); // timeslice = double(slice_end - slice_begin)/CLOCKS_PER_SEC; // // /*Loop-closure:*/ // clock_t contour_begin = clock(); // for (size_t p = 0; p < k; p++) { // if (!segs[p].empty()) { // LoopClosureIterative (segs[p], slicesWithLineSegs); // } // } // clock_t contour_end = clock(); // timecontour = double(contour_end - contour_begin)/CLOCKS_PER_SEC; // // #ifdef USE_OWN // free (vector); // #endif // return 0; // cout << slicer << "," << lastFile << ",#" << mesh.size() << "," << delta << ",#" << nplanes << "," << visits << "," << intersections << "," << timeBuild << ",@" << timeslice << ",@" << timecontour << "," << timeTotal << ", sort: " << timeSort << ", kbar: " << ((double)intersections/(double)mesh.size()) << endl; //exportSingleSVGFormat ("out.svg", slicesWithLineSegs, mesh.meshAABBSize()); //exportSingleSVGFormat3D (slicesWithLineSegs, mesh.meshAABBSize()); //exportSingleSVGFormat4D (slicesWithLineSegs, mesh.meshAABBSize()); return 0; } void swap(salamic_stl_r3_t &a, salamic_stl_r3_t &b) { salamic_stl_r3_t temp = a; a = b; b = temp; } typedef struct _sweeplane { salamic_stl_r3_t p1; salamic_stl_r3_t p2; long int id; } sweep_point; bool_t spcompare (sweep_point t1, sweep_point t2) { if (t1.p1.x == t2.p1.x) { return t1.p1.y < t2.p1.y; } else { return t1.p1.x < t2.p1.x; } } bool_t spfind (sweep_point t1, sweep_point t2) { if ((t1.p1.x == t2.p1.x) && (t1.p1.y == t2.p1.y) && (t1.id != t2.id)) { return true; } else { return false; } } #define ERROR -1 int checkASCIIFile(const char *fileName) { string line1, line2; ifstream input(fileName); if (!input.good()) return -1; getline(input, line1); getline(input, line2); //cout << fileName << endl; //cout << line1 << endl; //cout << line2 << endl; //bool_t solid = regex_match(line1, regex("(solid)(.*)")); //bool_t facet = regex_match(line1, regex("(.*)(facet)(.*)")); //bool_t xml = regex_match(line1, regex("(.*)(xml)(.*)")); //bool_t amf = regex_match(line1, regex("(.*)(amf)(.*)")); //if (regex_match(line1, regex("(.*)(solid)(.*)")) && regex_match(line2, regex("(.*)(facet)(.*)"))) if (line1.find("solid")!=string::npos && line2.find("facet")!=string::npos) return FILE_STL_ASCII; //if (regex_match(line1, regex("xml")) && regex_match(line2, regex("amf"))) if (line1.find("xml")!=string::npos && line2.find("amf")!=string::npos) return FILE_AMF_ASCII; //return (line1.find("solid") && line2.find("facet")); return FILE_STL_BIN; } // int removeNegativeCoords(const salamic_mesh_t &mesh, salamic_mesh_t *nmesh) { // //salamic_mesh_t nmesh; // float tx, ty, tz; // // tx = mesh.vMin.x < 0 ? (-1 * mesh.vMin.x) : 0; // ty = mesh.vMin.y < 0 ? (-1 * mesh.vMin.y) : 0; // tz = mesh.vMin.z < 0 ? (-1 * mesh.vMin.z) : 0; // // for (const salamic_stl_face_t &t : mesh.mesh) { // //salamic_stl_face_t nt = t; // // //for (int p = 0; p < 3;++p) { // // salamic_stl_face_t nt(t.normal, // salamic_stl_r3_t(t.v[0].x + tx, t.v[0].y + ty, t.v[0].z + tz), // salamic_stl_r3_t(t.v[1].x + tx, t.v[1].y + ty, t.v[1].z + tz), // salamic_stl_r3_t(t.v[2].x + tx, t.v[2].y + ty, t.v[2].z + tz) // ); // //} // // nmesh->push_back(nt); // } // // return 0; // // } salamic_mesh_t salamic_mesh_create(void) { salamic_mesh_t mesh; mesh.meshSize = 0; mesh.T.clear(); mesh.sorted = false; return mesh; } // // move 3D Model coordinates to be center around COG(0,0,0) // void normalize() { // salamic_stl_r3_t halfBbox = (vMax - vMin)/2.0f; // //salamic_stl_r3_t start = vMin + halfBbox; // //for (const salamic_stl_face_t &t : mesh) { // //salamic_stl_face_t t1; // //t1 = t - start; // //} // vMin = halfBbox*-1.0f; // vMax = halfBbox; // } // void push_back(salamic_stl_face_t &t) { // meshSize++; // if (ordered) { // orderedMesh[t.zMin][t.zMax].push_back(t); // } else { // long sortIni = Timer::getTimeMs(); // if (sort_faces) { // mesh.insert(t); // } // else { // T.push_back(t); // } // long sortEnd = Timer::getTimeMs(); // timeSort += (sortEnd - sortIni); // } // for (size_t i = 0; i < 3; ++i) { // if (t.v[i].x < vMin.x) vMin.x = t.v[i].x; // if (t.v[i].y < vMin.y) vMin.y = t.v[i].y; // if (t.v[i].z < vMin.z) vMin.z = t.v[i].z; // if (t.v[i].x > vMax.x) vMax.x = t.v[i].x; // if (t.v[i].y > vMax.y) vMax.y = t.v[i].y; // if (t.v[i].z > vMax.z) vMax.z = t.v[i].z; // } // } // salamic_stl_r3_t meshAABBSize() const { // return salamic_stl_r3_t(vMax.x-vMin.x, vMax.y-vMin.y, vMax.z-vMin.z); // } // multiset& getMesh() { return mesh; } // zMinFaceMap& getOrderedMesh() { return orderedMesh; } // const zMinFaceMap& getOrderedMesh() const { return orderedMesh; } // const multiset& getMesh() const { return mesh; } // const vector& getT() const { return T; } // // Mesh COG point should be at (0,0,0) // int transform(const glm::mat4 &mat) { // //for (const salamic_stl_face_t &t : mesh) { // //t.transform(mat); // //} // return 0; // } // int amfToMeshInMemory(const char *amfFile, FaceMesh *mesh) { // //long timeIni, timeEnd; // //clock_t timeIni, timeEnd; // long timeIni = Timer::getTimeMs(); // XMLDocument doc; // std::vector points; // doc.LoadFile(amfFile); // // XMLElement *m = doc.FirstChildElement()->FirstChildElement("object")->FirstChildElement("mesh"); // XMLElement *vertices = m->FirstChildElement("vertices"); // // for (XMLElement *vert = vertices->FirstChildElement("vert"); vert; vert = vert->NextSiblingElement()) // { // XMLElement *coords = vert->FirstChildElement("coordinates"); // float x = atof(coords->FirstChildElement("x")->GetText()); // float y = atof(coords->FirstChildElement("y")->GetText()); // float z = atof(coords->FirstChildElement("z")->GetText()); // // //long timeIni = Timer::getTimeMs(); // //timeIni = clock(); // //auto timeIni = chrono::high_resolution_clock::now(); // // points.push_back(salamic_stl_r3_t(x,y,z)); // // //timeEnd = clock(); // //auto timeEnd = chrono::high_resolution_clock::now(); // //long timeEnd = Timer::getTimeMs(); // //timeBuild += timeEnd - timeIni; // // //timeBuild += chrono::duration_cast(timeEnd - timeIni); // } // // XMLElement *volume = m->FirstChildElement("volume"); // //int count=0; // for (XMLElement *face = volume->FirstChildElement("face"); face; face = face->NextSiblingElement()) // { // //std::cout << "salamic_stl_face_t " << count++ << ":" << std::endl; // salamic_stl_r3_t v_1 = points[atoi(face->FirstChildElement("v1")->GetText())]; // salamic_stl_r3_t v_2 = points[atoi(face->FirstChildElement("v2")->GetText())]; // salamic_stl_r3_t v_3 = points[atoi(face->FirstChildElement("salamic_stl_r3_t")->GetText())]; // //long timeIni = Timer::getTimeMs(); // //timeIni = clock(); // //auto timeIni = chrono::high_resolution_clock::now(); // salamic_stl_face_t t(salamic_stl_r3_t(0,0,0), v_1, v_2, v_3); // // mesh->push_back(t); // //long timeEnd = Timer::getTimeMs(); // //timeBuild += timeEnd - timeIni; // //timeEnd = clock(); // //auto timeEnd = chrono::high_resolution_clock::now(); // // //timeBuild += chrono::duration_cast(timeEnd - timeIni); // //std::cout << "\tv1: (x: " << v1.x << "; y: " << v1.y << "; z: " << v1.z << ")" << std::endl; // //std::cout << "\tv2: (x: " << v2.x << "; y: " << v2.y << "; z: " << v2.z << ")" << std::endl; // //std::cout << "\tv3: (x: " << salamic_stl_r3_t.x << "; y: " << salamic_stl_r3_t.y << "; z: " << salamic_stl_r3_t.z << ")" << std::endl; // //std::cout << "-----------------------" << std::endl; // } // // long timeEnd = Timer::getTimeMs(); // timeBuild += timeEnd - timeIni; // // return 0; // } void salamic_mesh_recompute_box(salamic_mesh_t *mesh); /* Recomputes the bounding box of {mesh} from the face vertices. */ void salamic_mesh_box_include(salamic_stl_r3_t *vMin, salamic_stl_r3_t *vMax, salamic_stl_r3_t *v); /* Updates the bounding bbox corners {vMin,vMax} to include the point {v}. */ void salamic_mesh_recompute_box(salamic_mesh_t *mesh) { for (size_t i = 0; i < mesh->meshSize; i++) { salamic_stl_face_t *t = &(mesh->T.at(i)); salamic_mesh_box_include(&(mesh->vMin), &(mesh->vMax), &(t->v[0])); salamic_mesh_box_include(&(mesh->vMin), &(mesh->vMax), &(t->v[1])); salamic_mesh_box_include(&(mesh->vMin), &(mesh->vMax), &(t->v[2])); } } void salamic_mesh_box_include(salamic_stl_r3_t *vMin, salamic_stl_r3_t *vMax, salamic_stl_r3_t *v) { if (v->x < vMin->x) { vMin->x = v->x; } if (v->x > vMax->x) { vMax->x = v->x; } if (v->y < vMin->y) { vMin->y = v->y; } if (v->y > vMax->y) { vMax->y = v->y; } if (v->z < vMin->z) { vMin->z = v->z; } if (v->z > vMax->z) { vMax->z = v->z; } } salamic_r2_t salamic_mesh_Side_slice(salamic_stl_r3_t *vi, salamic_stl_r3_t *vj, float Z) { double dx = vj->x - vi->x; double dy = vj->y - vi->x; double dz = vj->z - vi->z; assert(dz != 0); double frac = (Z - vi->z)/dz; float xint = (float)(frac*dx + (double)vi->x); float yint = (float)(frac*dy + (double)vi->y); return (salamic_r2_t){ .x = xint, .y = yint }; } salamic_r2_Segment_t salamic_mesh_Face_slice(salamic_stl_face_t *t, float Z) { assert((t->zMin < Z) && (t->zMax > Z)); int np = 0; /* Number of segment endpoints found */ salamic_r2_Segment_t seg; for (int i = 0; i < 3; i++) { /* Get side {i} of face: */ int j = (i == 2 ? 0 : i+1); salamic_stl_r3_t *vi = &(t->v[i]); salamic_stl_r3_t *vj = &(t->v[j]); /* Check for intersection of plane with {vi--vj}. */ /* Must consider segment closed at bottom and open at top in case {Z} goes through a vert. */ float vzMin = (vi->z < vj->z ? vi->z : vj->z); float vzMax = (vi->z > vj->z ? vi->z : vj->z); if ((vzMin <= Z) && (vzMax > Z)) { salamic_r2_t p = salamic_mesh_Side_slice(vi, vj, Z); assert(np < 2); seg.v[np] = p; np++; } } assert(np == 2); return seg; } salamic_mesh_Face_List_t salamic_mesh_Face_List_create (void) { salamic_mesh_Face_List_t list; list.head = NULL; list.tail = NULL; return list; } void salamic_mesh_Face_List_insert (salamic_stl_face_t *t, salamic_mesh_Face_List_t *l) { salamic_mesh_Face_Vert_t *vert = (salamic_mesh_Face_Vert_t *)malloc(sizeof(salamic_mesh_Face_Vert_t)); vert->t = t; vert->next = l->head; vert->prev = NULL; if (l->head == NULL) { /*New head*/ l->head = l->tail = vert; } else { l->head->prev = vert; l->head = vert; } } void salamic_mesh_Face_List_union (salamic_mesh_Face_List_t *l1, salamic_mesh_Face_List_t *l2) { if ((l1->head != NULL) && (l2->head != NULL)) { l1->tail->next = l2->head; l2->head->prev = l1->tail; l1->tail = l2->tail; } else if (l2->head != NULL) { l1->head = l2->head; l1->tail = l2->tail; } l2->head = NULL; l2->tail = NULL; } void salamic_mesh_Face_List_remove (salamic_mesh_Face_List_t *l, salamic_mesh_Face_Vert_t *vert) { if ((vert->prev == NULL) && (vert->next == NULL)) { l->head = NULL; l->tail = NULL; } else if (vert->prev == NULL) { vert->next->prev = NULL; l->head = vert->next; } else if (vert->next == NULL) { vert->prev->next = NULL; l->tail = vert->prev; } else { salamic_mesh_Face_Vert_t *next = vert->next; salamic_mesh_Face_Vert_t *prev = vert->prev; next->prev = prev; prev->next = next; } free(vert); } // void salamic_r3_Trangle_transform(salamic_stl_face_t *t, const glm::mat4 *mat) { // salamic_stl_r3_transform(&(t->v[0]), mat); salamic_stl_r3_transform(&(t->v[1]), mat); salamic_stl_r3_transform(&(t->v[2]), mat); // salamic_stl_face_fixZMinZmax(t); // } /* salamic_stl_face_t& operator-=(const salamic_stl_r3_t &pt) { v[0]-=pt; v[1]-=pt; v[2]-=pt; return *this;} bool operator<(const salamic_stl_face_t &t) { return zMin < t.zMin; } friend ostream& operator<<(ostream& os, const salamic_stl_face_t& t) { os << "V0: (" << t.v[0] << "); V1: (" << t.v[1] << "); V2: (" << t.v[2] << ")"; return os; } // @return -1 = all face is on plane back side // 0 = plane intersects the face // 1 = all face is on plane front side // -2 = error in function int checkInterception(const salamic_r3_Plane_t &plane, LineMesh &lm) const { salamic_r3_Segment_t ls; vector segments; size_t cntFront=0, cntBack=0; for (size_t j=0; j<3; ++j) { float distance = plane.distanceToPoint(v[j]); if (distance<0) ++cntBack; else ++cntFront; } if (3 == cntBack) return -1; else if (3 == cntFront) return 1; size_t lines[] = {0,1,1,2,2,0}; for (size_t i=0; i<3; ++i) { salamic_stl_r3_t a = v[lines[i*2+0]]; salamic_stl_r3_t b = v[lines[i*2+1]]; if (a>b) swap(a,b); const float da = plane.distanceToPoint(a); const float db = plane.distanceToPoint(b); if ((da*db < 0 || 0 == da || 0 == db) && (da != db)) { ls.v[0] = a; ls.v[1] = b; segments.push_back(ls); } } if (2 == segments.size()) { //salamic_stl_r3_t a = segments[0].v[0]; //salamic_stl_r3_t b = segments[0].v[1]; //cout << "A1: " << a.x << "|" << a.y << "|" << a.z << " / " << b.x << "|" << b.y << "|" << b.z << endl; lm[segments[0]].push_back(segments[1]); lm[segments[1]].push_back(segments[0]); //a = segments[1].v[0]; //b = segments[1].v[1]; //cout << "A2: " << a.x << "|" << a.y << "|" << a.z << " / " << b.x << "|" << b.y << "|" << b.z << endl; } else return -2; return 0; } int salamic_r3_Trangle_getSegment (const salamic_r3_Plane_t *plane, salamic_r3_Segment_t *ls) { //CCW face: size_t lines[] = {0,1,1,2,2,0}; salamic_stl_r3_t intersectPoints[3]; int size = 0; for (size_t i = 0; i < 3; i++) { salamic_stl_r3_t a = v[lines[i*2+0]]; salamic_stl_r3_t b = v[lines[i*2+1]]; if (a>b) swap(a,b); const float da = plane.distanceToPoint(a); const float db = plane.distanceToPoint(b); if ((da * db) <= 0) { //Intersection factor between 0 and 1: const float s = da/(da-db); salamic_stl_r3_t bMinusa = b - a; salamic_stl_r3_t r = a + bMinusa * s; r.x = round (r.x * 100.0) / 100.0; r.y = round (r.y * 100.0) / 100.0; r.z = round (r.z * 100.0) / 100.0; intersectPoints[i] = r; size++; } } ls.v[0] = intersectPoints[0]; for (int i = 1; i < size; i++) { if ((intersectPoints[0] != intersectPoints[i]) || (size == 2)) { ls.v[1] = intersectPoints[i]; return 0; } } ls.v[1] = intersectPoints[1]; return 0; } // @return -1 = all face is on plane front/back side // 0 = plane intersects the face int intersectPlane(const salamic_r3_Plane_t &plane, salamic_r3_Segment_t &ls) const { size_t front = 0, back = 0; visits++; for (size_t i = 0; i < 3; i++) { float distance = plane.distanceToPoint(v[i]); if (distance < 0) { back++; } else { front++; } } if ( (back == 3) || (front == 3) ) { //cout << "sem interseccao" << endl; return -1; } //CCW salamic_stl_face_t: size_t lines[] = {0,1,1,2,2,0}; salamic_stl_r3_t intersectPoints[3]; //std::vector intersectPoints; int size = 0; for (size_t i = 0; i < 3; i++) { salamic_stl_r3_t a = v[lines[i*2+0]]; salamic_stl_r3_t b = v[lines[i*2+1]]; if (a>b) swap(a,b); const float da = plane.distanceToPoint(a); const float db = plane.distanceToPoint(b); if ((da * db) <= 0) { //Intersection factor between 0 and 1: const float s = da/(da-db); salamic_stl_r3_t bMinusa = b - a; salamic_stl_r3_t r = a + bMinusa * s; //r.x = roundIt(r.x, 2); //r.y = roundIt(r.y, 2); //r.z = roundIt(r.z, 2); //CUIDADO COMENTEI O CODIGO ABAIXO r.x = round (r.x * 100.0) / 100.0; r.y = round (r.y * 100.0) / 100.0; r.z = round (r.z * 100.0) / 100.0; intersectPoints[i] = r; size++; //intersectPoints.push_back(r); } } ls.v[0] = intersectPoints[0]; //for (int i = 1; i < intersectPoints.size(); i++) { for (int i = 1; i < size; i++) { if ((intersectPoints[0] != intersectPoints[i]) || (size == 2)) { ls.v[1] = intersectPoints[i]; return 0; } } //throw logic_error("Error in interceptPlane"); //return -2; ls.v[1] = intersectPoints[1]; return 0; //return 0; } }; class salamic_stl_face_Comparer_t { public: bool operator() (const salamic_stl_face_t &t1, const salamic_stl_face_t &t2) const { if (t1.zMin == t2.zMin) return t1.zMax < t2.zMax; else return t1.zMin < t2.zMin; } }; bool salamic_stl_face_compare (salamic_stl_face_t t1, salamic_stl_face_t t2) { if (t1.zMin == t2.zMin) { //cout << "t1: " << t1.zMax << ", t2: " << t2.zMax << endl; //if (t1.zMax < t2.zMax) { cout << "t1 menor" << endl; } return t1.zMax < t2.zMax; } else return t1.zMin < t2.zMin; } */ salamic_r2_t salamic_closer_trivial_find(vector *segs, salamic_r2_t u); /* Looks in {segs} for a segment with one of the endpoints equel to {u}. If finds one, erases that segment, and returns the other endpoint. If does not find one, returns a point at infinity. */ salamic_r2_t salamic_closer_trivial_find(vector *segs, salamic_r2_t u) { for (vector::iterator j = segs->begin(); j != segs->end(); ++j) { salamic_r2_t v0 = j->v[0]; salamic_r2_t v1 = j->v[1]; if ((v0.x == u.x) && (v0.y == u.y)) { segs->erase(j); return v1; } else if ((v1.x == u.x) && (v1.y == u.y)) { segs->erase(j); return v0; } } } void salamic_closer_trivial_close(vector *segs, vector *loops) { loops->clear(); while (segs->size() > 0) { /* Get another contour: */ salamic_r2_Polygon_t contour; /* Get the first segment: */ salamic_r2_t last; salamic_r2_t current; salamic_r2_t prev; { vector::iterator i = segs->begin(); last = i->v[0]; current = i->v[1]; contour.push_back(current); prev = last; segs->erase(i); } /* Get additional segments until loop is closed: */ do { /* Find and delete another segment with endpoint {current}, advance {prev,current} */ salamic_r2_t next = salamic_closer_trivial_find(segs, current); if ((next.x == +INFINITY) || (next.y == +INFINITY)) { /* Open contour?! */ assert(false); } assert((next.x != prev.x) || (next.y != prev.y)); prev = current; current = next; contour.push_back(current); } while ((current.x != last.x) || (current.y != last.y)); loops->push_back(contour); } } struct salamic_r2_Vertex_Hasher_t { int operator() (const salamic_r2_t *v) const { int h = salamic_r2_hash (*v); return h; } } typedef struct salamic_r2_Vertex_Pair_t { salamic_r2_t v, w; /* Two neighbors of the key point, or {+INFINITY} if not defined. */ } salamic_r2_Vertex_Pair; typedef unordered_map NeighborTable_t; /* The neighbor hash table for {LoopClosureIterative}. */ void AddNeighborToTable(NeighborTable_t *H, salamic_r2_t *u, salamic_r2_t *v); /* Adds to the neighbor tale {H} the point {v} as a neighbor of {u}. There must be at most one neighbor of {u} already in the table. */ /* IMPLEMENTATIONS */ void AddNeighborToTable(NeighborTable_t *H, salamic_r2_t *u, salamic_r2_t *v) { salamic_r2_Vertex_Pair vw = H[*u]; NeighborTable_t::const_iterator entry = H->find(h); if (entry == H->end()) { // No neighbors yet: salamic_r2_Vertex_Pair_t value = (salamic_r2_Vertex_Pair_t){ .v = *v, .w = (salamic_r2_t){ +INFINITY, +INFINITY } }; H[*u] = value; } else { // Some neighbors already -- must be only one. salamic_r2_t key = entry->first; assert((key.x == u->x) && (key.y == u->y)); salamic_r2_Vertex_Pair_t value = entry->second; assert((value.w.x == +INFINITY) && (value.w.y == +INFINITY)); value.w = (*v); H[u] = value; } } void salamic_r2_loop_closure_close (vector segs, vector &loops) { /*Creating the hash table of proper size.*/ NeighborTable_t H; /*Filling the hash table.*/ for (std::vector::iterator i = segs.begin(); i != segs.end(); i++) { salamic_r2_Segment_t *q = i; AddNeighborToTable(H, &(q->v[0]), &(q->v[1])); AddNeighborToTable(H, &(q->v[1]), &(q->v[0])); } /*Loop-closure.*/ int numContours = 0; salamic_stl_r3_t v, tail; while (! H.empty()) { Polygon_t P; salamic_r2_t prev; salamic_r2_t current; salamic_r2_t last; int j; { auto it = H.begin(); /* First vertex: */ salamic_r2_t u = it->first; P.push_back(u); j = 1; /* Second and last vertices: */ salamic_r2_Vertex_Pair vw = it->second; P.push_back(vw->v); j = 2; prev = u; current = vw->v; last = vw->w; H.erase(u); } /* Collect other vertices: */ do { salamic_r2_t next; { it = H.find(current); assert (it != H.end()); salamic_r2_t key = it->first; assert((key.x == current->x) && (key.y == current->y)); salamic_r2_Vertex_Pair vw = it->second; if ((vw.v.x == prev.x) && (vw.v.y == prev.y)) { next = vw->w; } else if ((vw.w.x == prev.x) && (vw.w.y == prev.y)) { next = vw.v; } else { assert(false); } H.erase(key); } P.push_back(next); prev = current; current = next; } while ((current.x != last.x) || (current.y != last.y)); numContours++; loops.push_back(P); } } int salamic_slicer_Minetto_binary_search (float zMin, vector P) { int k = P.size(); assert(k >= 1); if (zMin >= P[k-1]) { return k; } /* Binary search: */ int l = -1; /* Inferior Z index. */ int r = k; /* Superior Z index. .*/ while (r - l > 1) { /* At this point, {zMin} is between {P[l]} and {P[r]}. */ int m = (l + r)/2; assert((0 <= m) && (m < k)); if (zMin >= P[m]) { l = m; } else { r = m; } } return r; } salamic_mesh_Face_List_t* salamic_slicer_Minetto_buildLists (bool srt, double delta, salamic_mesh_t *mesh, vector P) { int k = P.size(); /* Number of planes. */ salamic_mesh_Face_List_t* L = (salamic_mesh_Face_List_t *)malloc((k+1)*sizeof(salamic_mesh_Face_List_t)); for (size_t p = 0; p <= k; p++) { L[p] = salamic_mesh_Face_List_create(); } salamic_stl_face_Vector_t *T = &(mesh->T); int n = T->size(); /* Number of faces. */ if (delta > 0.0) { /* Uniform slicing - compute list index: */ for (salamic_stl_face_Vector_t::iterator it = T->begin(), itEnd = T->end(); it != itEnd; ++it) { salamic_stl_face_t *t = &(*it); int p; if (t->zMin < P[0]) { p = 0; } else if (t->zMin > P[k-1]) { p = k; } else { p = floor((t->zMin - P[0])/delta) + 1; } salamic_mesh_Face_List_insert(t, &(L[p])); } } else if (srt) { /* Slicing of a pre-sorted mesh - merge {zMin}s and {P}: */ salamic_stl_face_Vector_t::iterator it = T->begin(); salamic_stl_face_Vector_t::iterator itEnd = T->end(); double zprev = -INFINITY; for (int p = 0; p <= k; p++) { float Zp = (p < k ? P[k] : +INFINITY); salamic_stl_face_t *t = &(*it); assert(t->zMin >= zprev); while ((it != itEnd) && (t->zMin < Zp)) { salamic_mesh_Face_List_insert (t, &(L[p])); zprev = t->zMin; it++; } } } else { /* General case: */ for (salamic_stl_face_Vector_t::iterator it = T->begin(), itEnd = T->end(); it != itEnd; ++it) { salamic_stl_face_t *t = &(*it); int p = salamic_slicer_Minetto_binary_search(t->zMin, P); assert((p >= 0) && (p <= k)); salamic_mesh_Face_List_insert (t, &(L[p])); } } return L; } void salamic_slicer_Minetto_slice (salamic_mesh_t *mesh, vector P, float delta, bool srt, salamic_r3_Closure_Proc_t *closer) { int k = P.size(); vector segs; //int miss = 0; /* Classify faces by the plane gaps that contain their {zMin}: */ salamic_mesh_Face_List_t* L = salamic_slicer_Minetto_buildLists(srt, delta, mesh, P); /* Now perform a plane sweep from bottom to top: */ salamic_mesh_Face_List_t A = salamic_mesh_Face_List_create(); /* Active face list. */ for (int p = 0; p < k; p++) { /* Add faces that start between {P[p-1]} and {P[p]}: */ salamic_mesh_Face_List_union (&A, &(L[p])); /* Scan the active faces: */ segs.clear(); salamic_mesh_Face_Node_t *aux = A.head; while (aux != NULL) { assert(aux->t->zMin < P[p]); salamic_mesh_Face_Node_t *next = aux->next; if (aux->t->zMax < P[p]) { /* Face is exhausted: */ salamic_mesh_Face_List_remove(&A, aux); } else { /* Compute intersection: */ salamic_r2_Segment_t seg = salamic_mesh_Face_slice(aux->t, P[p]); segs.push_back(seg); } aux = next; } if (closer != NULL) { /* Process the segments: */ closer(mesh, P[p], &segs); } } free(L); } int salamic_slicer_Minetto_binary_search (float zMin, vector P); /* Assumes that {P} is a list of {k} strictly increasing {Z} coordinates. Returns an integer {p} such that {P[p-1] < zMin < P[p]}. As special cases, if {zMin < P[0]} returns 0; if {zMin > P[k-1]} returns {k}. */ salamic_mesh_Face_List_t* salamic_slicer_Minetto_buildLists (bool srt, double delta, salamic_mesh_t *mesh, vector P); /* Assumes that {P[0..k-1]} is a list of {k} strictly increasing {Z} coordinates. Returns a vector of {k+1} lists {L[0..k]} such that {L[p]} contains all faces of the {mesh} that have {zMin} between {P[p-1]} and {P[p]}, assuming that {P[-1] = -oo} and {P[k] = +oo}. If {delta > 0}, assumes that {P[p]-P[p-1] = delta} for {p} in {1..k-1}. If {srt} is true, assumes that the faces are already sorted by increasing {zMin}. */