?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
changed: gcc8 base update
[opensg.git] / Source / System / NodeCores / Drawables / Nurbs / Internal / OSGDCTPMesh.cpp
blob4144b755ae4ee1deaf7a20d279e3cd5b36d8d2c7
1 /*---------------------------------------------------------------------------*\
2 * OpenSG NURBS Library *
3 * *
4 * *
5 * Copyright (C) 2001-2006 by the University of Bonn, Computer Graphics Group*
6 * *
7 * http://cg.cs.uni-bonn.de/ *
8 * *
9 * contact: edhellon@cs.uni-bonn.de, guthe@cs.uni-bonn.de, rk@cs.uni-bonn.de *
10 * *
11 \*---------------------------------------------------------------------------*/
12 /*---------------------------------------------------------------------------*\
13 * License *
14 * *
15 * This library is free software; you can redistribute it and/or modify it *
16 * under the terms of the GNU Library General Public License as published *
17 * by the Free Software Foundation, version 2. *
18 * *
19 * This library is distributed in the hope that it will be useful, but *
20 * WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
22 * Library General Public License for more details. *
23 * *
24 * You should have received a copy of the GNU Library General Public *
25 * License along with this library; if not, write to the Free Software *
26 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
27 * *
28 \*---------------------------------------------------------------------------*/
29 /*---------------------------------------------------------------------------*\
30 * Changes *
31 * *
32 * *
33 * *
34 * *
35 * *
36 * *
37 \*---------------------------------------------------------------------------*/
38 #ifdef WIN32
39 # pragma warning (disable : 985)
40 #endif
41 #include "OSGDCTPMesh.h"
42
43 OSG_USING_NAMESPACE
44
45 #ifdef _DEBUG
46 #ifdef WIN32
47 #undef THIS_FILE
48 static char THIS_FILE[] = __FILE__;
49 #endif
50 #endif
51
52 const char DCTPMesh::ff_const_1[] = "BEGINTRIANGLESOUP";
53 const char DCTPMesh::ff_const_2[] = "BEGINQUADSOUP";
54
55 DCTPMesh::DCTPMesh() :
56 vertices ( ),
57 #ifdef OSG_NO_EDGE_SET
58 edges ( ),
59 #else
60 edges ( ),
61 #endif
62 faces ( ),
63 vertex_count(0 ),
64 edge_count (0 ),
65 face_count (0 ),
66 invalid (true)
67 {
68 }
69
70 DCTPMesh::~DCTPMesh()
71 {
72 dctpvertexset::iterator vend = vertices.end();
73 #ifdef OSG_NO_EDGE_SET
74 dctpedgevector::iterator eend = edges.end();
75 #else
76 dctpedgeset::iterator eend = edges.end();
77 #endif
78 dctpfacevector::iterator fend = faces.end();
79
80 for(dctpvertexset::iterator i1 = vertices.begin(); i1 != vend; ++i1)
81 {
82 delete *i1;
83 }
84
85 #ifdef OSG_NO_EDGE_SET
86
87 for(dctpedgevector::iterator i2 = edges.begin(); i2 != eend; ++i2)
88 #else
89
90 for(dctpedgeset::iterator i2 = edges.begin(); i2 != eend; ++i2)
91 #endif
92 {
93 delete *i2;
94 }
95
96 for(dctpfacevector::iterator i3 = faces.begin(); i3 != fend; ++i3)
97 {
98 delete *i3;
99 }
100 }
101
102 DCTPVertex *DCTPMesh::AddVertex(Vec3d v)
103 {
104 DCTPVertex *nv = new DCTPVertex;
105 if(!nv)
106 return nv;
107 invalid = false;
108 nv->coords = v;
109
110 std::pair<dctpvertexset::iterator, bool> siv;
111 siv = vertices.insert(nv);
112 if(!siv.second)
113 {
114 // std::cerr << "AddVertex: already in: " << v << std::endl;
115 delete nv;
116 nv = *(siv.first);
117 }
118 else
119 {
120 // std::cerr << "AddVertex: adding vx.: " << v << std::endl;
121 nv->id = vertex_count++;
122 }
123 return nv;
124 }
125
126 #ifdef OSG_INTEGER_MESH
127 int DCTPMesh::directEdge(vec3i& from, vec3i& into)
128 {
129 #else
130 int DCTPMesh::directEdge(Vec3d& from, Vec3d& into)
131 {
132 #endif
133 DCTPVertex *from_vp = new DCTPVertex;
134 DCTPVertex *into_vp = new DCTPVertex;
135 if(!from_vp || !into_vp)
136 {
137 std::cerr << "Not enuf memory!" << std::endl;
138 return -2;
139 }
140 from_vp->coords = from;
141 into_vp->coords = into;
142
143 // std::cerr << "directEdge in... coords: " << from << " " << into << std::endl;
144 dctpvertexset::iterator v1,v2, vend = vertices.end(); v1 =
145 vertices.find(from_vp); if(v1 == vend)
146 {
147 delete from_vp;
148 delete into_vp;
149 return -1;
150 }
151 v2 = vertices.find(into_vp);
152 if(v2 == vend)
153 {
154 delete from_vp;
155 delete into_vp;
156 return -1;
157 }
158 // std::cerr << "still directEdge..." << std::endl;
159 // std::cerr.precision( DCTP_PRECISION );
160 // std::cerr << "v1->coords: " << (*v1)->coords << " v2->coords: " << (*v2)->coords << std::endl;
161 delete from_vp;
162 delete into_vp;
163 std::vector<DCTPEdge*>::iterator eend = (*v1)->edges.end();
164
165 for(std::vector<DCTPEdge*>::iterator i = (*v1)->edges.begin(); i != eend; ++i)
166 {
167 DCTPVertex *tv1, *tv2;
168 (*i)->getVertices(tv1, tv2);
169 if(DCTPVecIsEqual(tv1->coords, (*v1)->coords) &&
170 DCTPVecIsEqual(tv2->coords, (*v2)->coords) )
171 {
172 ++(*i)->orientation;
173 return 0;
174 }
175 if(DCTPVecIsEqual(tv1->coords, (*v2)->coords) &&
176 DCTPVecIsEqual(tv2->coords, (*v1)->coords) )
177 {
178 --(*i)->orientation;
179 return 0;
180 }
181 }
182
183 return -1;
184 }
185
186 DCTPEdge *DCTPMesh::AddEdge(DCTPVertex *v1, DCTPVertex *v2, int orient)
187 {
188 #ifdef OSG_NO_EDGE_SET
189 DCTPEdge *pcl_edge;
190 const unsigned int cui_edge_cnt = UInt32(v1->edges.size());
191 unsigned int ui_edge;
192 DCTPVertex *pcl_ev1;
193 DCTPVertex *pcl_ev2;
194
195 for(ui_edge = 0; ui_edge < cui_edge_cnt; ++ui_edge)
196 {
197 pcl_edge = v1->edges[ui_edge];
198 pcl_edge->getVertices(pcl_ev1, pcl_ev2);
199 if( (v2 == pcl_ev1) || (v2 == pcl_ev2) )
200 {
201 return pcl_edge;
202 }
203 }
204
205 invalid = false;
206 pcl_edge = new DCTPEdge(v1, v2, orient);
207 // std::cerr << "4-" << pcl_edge << " " << v1 << " " << v2 << std::endl;
208 v1->edges.push_back(pcl_edge);
209 v2->edges.push_back(pcl_edge);
210 edges.push_back(pcl_edge);
211
212 return pcl_edge;
213 #else
214 DCTPEdge *ne = new DCTPEdge(v1, v2, orient);
215 if(!ne)
216 return ne;
217
218 invalid = false;
219 std::pair<dctpedgeset::iterator, bool> sie;
220 // bool newas = false;
221 /*
222 dctpedgeset::iterator ee = edges.end();
223 for (dctpedgeset::iterator i = edges.begin(); i !=ee; ++i ) {
224 DCTPVertex *tt1, *tt2;
225 (*i)->getVertices( tt1, tt2 );
226 std::cerr << "edgeid: " << (*i)->id << " v1: " << (void*) tt1 << " " << (void*) tt2
227 << std::endl;
228 }
229 */
230 sie = edges.insert(ne);
231 if(!sie.second)
232 {
233 delete ne;
234 return *(sie.first);
235 // ne = *(sie.first);
236 // newas = true;
237 }
238 else
239 {
240 // DCTPVertex *zz1, *zz2;
241 // ne->getVertices( zz1, zz2 );
242 // std::cerr << "Inserting new edge: " << (void*) zz1 << " " << (void*) zz2;
243 // std::cerr << " with coords: " << v1->coords << " " << v2->coords << std::endl;
244 ne->id = edge_count++;
245 // }
246 // if ( !newas ) {
247 v1->edges.push_back(ne);
248 v2->edges.push_back(ne);
249 }
250
251 return ne;
252 #endif
253 }
254
255
256 DCTPFace *DCTPMesh::AddFace(void)
257 {
258 DCTPFace *nf = new DCTPFace;
259 if(!nf)
260 return NULL;
261 invalid = false;
262 nf->id = face_count++;
263 faces.push_back(nf);
264
265 return nf;
266 }
267
268 int DCTPMesh::AddTriangle(Vec3d v1, Vec3d v2, Vec3d v3, double norm)
269 {
270 DCTPVertex *nv1 = AddVertex(v1);
271 DCTPVertex *nv2 = AddVertex(v2);
272 DCTPVertex *nv3 = AddVertex(v3);
273 if(!nv1 || !nv2 || !nv3)
274 return -1;
275
276 DCTPEdge *ne1 = AddEdge(nv1, nv2, 0);
277 DCTPEdge *ne2 = AddEdge(nv2, nv3, 0);
278 DCTPEdge *ne3 = AddEdge(nv3, nv1, 0);
279 if(!ne1 || !ne2 || !ne3)
280 return -1;
281
282 DCTPFace *nf = AddFace();
283 if(!nf)
284 return -1;
285
286 invalid = false;
287 //do this here, to be able to dump valid data in DCTPEdge::AddFace
288 #ifdef OSG_UNION_TRI_QUAD
289 nf->orig_face[0] = nv1;
290 nf->orig_face[1] = nv2;
291 nf->orig_face[2] = nv3;
292 nf->orig_face[3] = NULL;
293 #else
294 nf->orig_triangle[0] = nv1;
295 nf->orig_triangle[1] = nv2;
296 nf->orig_triangle[2] = nv3;
297 // FIXME: is it really necessary? Any other (better) way to distinguish
298 // FIXME: between triangle and quad faces?
299 nf->orig_quad[0] = NULL;
300 nf->orig_quad[1] = NULL;
301 nf->orig_quad[2] = NULL;
302 nf->orig_quad[3] = NULL;
303 #endif
304 nf->norm = norm;
305
306 ne1->AddFace(nf);
307 ne2->AddFace(nf);
308 ne3->AddFace(nf);
309
310 nv1->faces.push_back(nf);
311 nv2->faces.push_back(nf);
312 nv3->faces.push_back(nf);
313
314 nf->vertices.push_back(nv1);
315 nf->vertices.push_back(nv2);
316 nf->vertices.push_back(nv3);
317 nf->edges.push_back(ne1);
318 nf->edges.push_back(ne2);
319 nf->edges.push_back(ne3);
320
321 return 0;
322 }
323
324 int DCTPMesh::AddQuadSide(DCTPVertex *l, DCTPVertex *r, DCTPVertex *m, DCTPFace *nf)
325 {
326 if(m)
327 {
328 DCTPEdge *ue1 = AddEdge(l, m, 0);
329 DCTPEdge *ue2 = AddEdge(m, r, 0);
330 if(!ue1 || !ue2)
331 return -1;
332 ue1->AddFace(nf);
333 ue2->AddFace(nf);
334 nf->edges.push_back(ue1);
335 nf->edges.push_back(ue2);
336 l->faces.push_back(nf);
337 m->faces.push_back(nf);
338 r->faces.push_back(nf);
339 }
340 else
341 {
342 DCTPEdge *ue = AddEdge(l, r, 0);
343 if(!ue)
344 return -1;
345 ue->AddFace(nf);
346 nf->edges.push_back(ue);
347 l->faces.push_back(nf);
348 r->faces.push_back(nf);
349 }
350
351 return 0;
352 }
353
354
355 /* (nv1) ul bool[0] ur (nv2)
356 * X-----+-----X
357 * | |
358 * | |
359 * bool[3] + + bool[1]
360 * | |
361 * | |
362 * X-----+-----X
363 * ll bool[2] lr (nv3)
364 * (nv4) (nv4)
365 *
366 *
367 * Note that this function adds vertices in clockwise order, i.e.
368 * nv1, nv,2 nv3, nv4 if there are no middle vertices.
369 *
370 * Note that z coordinates are truncated to 0. This is essentially
371 * a 2D function using only (x, y) coords
372 */
373 int DCTPMesh::AddQuadTreeLeaf(Vec3d ul, Vec3d lr, bool *sides, double norm)
374 {
375 Vec3d ur, ll;
376 ur[0] = lr[0]; ur[1] = ul[1]; ur[2] = 0.0;
377 ll[0] = ul[0]; ll[1] = lr[1]; ll[2] = 0.0;
378
379 DCTPVertex *nv1 = AddVertex(ul);
380 DCTPVertex *nv2 = AddVertex(ur);
381 DCTPVertex *nv3 = AddVertex(lr);
382 DCTPVertex *nv4 = AddVertex(ll);
383 if(!nv1 || !nv2 || !nv3 || !nv4)
384 return -1;
385
386 DCTPFace *nf = AddFace();
387 if(!nf)
388 return -1;
389
390 #ifdef OSG_UNION_TRI_QUAD
391 nf->orig_face[0] = nv1;
392 nf->orig_face[1] = nv2;
393 nf->orig_face[2] = nv3;
394 nf->orig_face[3] = nv4;
395 #else
396 nf->orig_quad[0] = nv1;
397 nf->orig_quad[1] = nv2;
398 nf->orig_quad[2] = nv3;
399 nf->orig_quad[3] = nv4;
400 // FIXME: is it really necessary? Any other (better) way to distinguish
401 // FIXME: between triangle and quad faces?
402 nf->orig_triangle[0] = NULL;
403 nf->orig_triangle[1] = NULL;
404 nf->orig_triangle[2] = NULL;
405 #endif
406 nf->norm = norm;
407
408 if(sides[0])
409 {
410 Vec3d umv;
411 umv[0] = (ur[0] + ul[0]) / 2.0;
412 umv[1] = ur[1];
413 umv[2] = 0.0;
414 DCTPVertex *um = AddVertex(umv);
415 if(!um)
416 return -1;
417 AddQuadSide(nv1, nv2, um, nf);
418 nf->vertices.push_back(nv1); // we have to add these here because
419 nf->vertices.push_back(um); // on subsequent sides we mustn't add
420 nf->vertices.push_back(nv2); // some vertices in order to avoid duplications
421 }
422 else
423 {
424 AddQuadSide(nv1, nv2, NULL, nf);
425 nf->vertices.push_back(nv1); // see comment above
426 nf->vertices.push_back(nv2);
427 }
428 if(sides[1])
429 {
430 Vec3d rmv;
431 rmv[0] = ur[0];
432 rmv[1] = (ur[1] + lr[1]) / 2.0;
433 rmv[2] = 0.0;
434 DCTPVertex *rm = AddVertex(rmv);
435 if(!rm)
436 return -1;
437 AddQuadSide(nv2, nv3, rm, nf);
438 nf->vertices.push_back(rm); // we don't need to push nv2 !!!
439 nf->vertices.push_back(nv3);
440 }
441 else
442 {
443 AddQuadSide(nv2, nv3, NULL, nf);
444 nf->vertices.push_back(nv3); // see comment above
445 }
446 if(sides[2])
447 {
448 Vec3d lmv;
449 lmv[0] = (lr[0] + ll[0]) / 2.0;
450 lmv[1] = lr[1];
451 lmv[2] = 0.0;
452 DCTPVertex *lm = AddVertex(lmv);
453 if(!lm)
454 return -1;
455 AddQuadSide(nv3, nv4, lm, nf);
456 nf->vertices.push_back(lm); // we don't need to push nv3 !!!
457 nf->vertices.push_back(nv4);
458 }
459 else
460 {
461 AddQuadSide(nv3, nv4, NULL, nf);
462 nf->vertices.push_back(nv4); // see comment above
463 }
464 if(sides[3])
465 {
466 Vec3d lemv;
467 lemv[0] = ll[0];
468 lemv[1] = (ll[1] + ul[1]) / 2.0;
469 lemv[2] = 0.0;
470 DCTPVertex *lem = AddVertex(lemv);
471 if(!lem)
472 return -1;
473 AddQuadSide(nv4, nv1, lem, nf);
474 nf->vertices.push_back(lem); // we don't need to push nv4 or nv1 !!!
475 }
476 else
477 {
478 AddQuadSide(nv4, nv1, NULL, nf);
479 }
480 return 0;
481 }
482
483 /*
484 * Note: in the SubdivideQuad() function we assume that the quads
485 * were added this way:
486 *
487 * v1 .----. v2
488 * | |
489 * v4 `----' v3
490 *
491 */
492 DCTPFace* DCTPMesh::AddQuad(Vec3d v1, Vec3d v2, Vec3d v3, Vec3d v4, double norm)
493 {
494 DCTPVertex *nv1 = AddVertex(v1);
495 DCTPVertex *nv2 = AddVertex(v2);
496 DCTPVertex *nv3 = AddVertex(v3);
497 DCTPVertex *nv4 = AddVertex(v4);
498 if(!nv1 || !nv2 || !nv3 || !nv4)
499 {
500 return NULL;
501 }
502
503 DCTPEdge *ne1 = AddEdge(nv1, nv2, 0);
504 DCTPEdge *ne2 = AddEdge(nv2, nv3, 0);
505 DCTPEdge *ne3 = AddEdge(nv3, nv4, 0);
506 DCTPEdge *ne4 = AddEdge(nv4, nv1, 0);
507 if(!ne1 || !ne2 || !ne3 || !ne4)
508 {
509 return NULL;
510 }
511
512 DCTPFace *nf = AddFace();
513 if(!nf)
514 {
515 return NULL;
516 }
517
518 invalid = false;
519 #ifdef OSG_UNION_TRI_QUAD
520 nf->orig_face[0] = nv1;
521 nf->orig_face[1] = nv2;
522 nf->orig_face[2] = nv3;
523 nf->orig_face[3] = nv4;
524 #else
525 nf->orig_quad[0] = nv1;
526 nf->orig_quad[1] = nv2;
527 nf->orig_quad[2] = nv3;
528 nf->orig_quad[3] = nv4;
529 // FIXME: is it really necessary? Any other (better) way to distinguish
530 // FIXME: between triangle and quad faces?
531 nf->orig_triangle[0] = NULL;
532 nf->orig_triangle[1] = NULL;
533 nf->orig_triangle[2] = NULL;
534 #endif
535
536 ne1->AddFace(nf);
537 ne2->AddFace(nf);
538 ne3->AddFace(nf);
539 ne4->AddFace(nf);
540
541 nv1->faces.push_back(nf);
542 nv2->faces.push_back(nf);
543 nv3->faces.push_back(nf);
544 nv4->faces.push_back(nf);
545
546 nf->vertices.resize(4);
547 nf->vertices[0] = nv1;
548 nf->vertices[1] = nv2;
549 nf->vertices[2] = nv3;
550 nf->vertices[3] = nv4;
551 nf->edges.resize(4);
552 nf->edges[0] = ne1;
553 nf->edges[1] = ne2;
554 nf->edges[2] = ne3;
555 nf->edges[3] = ne4;
556 nf->norm = norm;
557
558 return nf;
559 }
560
561
562 bool DCTPMesh::isInvalid(void)
563 {
564 return invalid;
565 }
566
567 DCTPVertex * DCTPMesh::SplitEdge(DCTPEdge *edge, double t)
568 {
569 /* if ( t < 0.0 || t > 1.0 )
570 {
571 std::cerr << "out of range" << std::endl;
572 return NULL;
573 }*/
574 DCTPVertex *v1, *v2;
575 edge->getVertices(v1, v2);
576 // if ( t < DCTP_EPS ) return v1;
577 // if ( t > 1 - DCTP_EPS ) return v2;
578
579 // std::cerr << "split: " << v1->coords << " - " << v2->coords << ": " << t << std::endl;
580
581 DCTPVertex *nv = new DCTPVertex;
582
583 if(!nv)
584 {
585 std::cerr << "DCTPMesh::SplitEdge: Out of memory... " << std::endl;
586 return NULL;
587 }
588
589 nv->coords = v1->coords + (v2->coords - v1->coords) * t;
590
591 // add new vertex
592 std::pair<dctpvertexset::iterator, bool> siv;
593 siv = vertices.insert(nv);
594 if(!siv.second)
595 {
596 // we already had this vertex in the mesh. Either the mesh is
597 // corrupted/degenerate, or we've already applied this exact
598 // SplitEdge operator.
599 // or the splitvertex is very close to the ends of the edge... ;)
600 delete nv;
601 nv = *(siv.first);
602 if(nv->edges.size() > 0)
603 {
604 std::cerr << "DCTPMesh::SplitEdge: error: inserting already existing splitvertex with edges..." << std::endl;
605 // std::cerr << "DCTPMesh::SplitEdge: error: numofedges: " << nv->edges.size()
606 // << std::endl;
607 // std::cerr << "DCTPMesh::SplitEdge: error: point location: " << nv->coords
608 // <<std::endl;
609 }
610 return nv;
611 }
612 else
613 {
614 nv->id = vertex_count++;
615 }
616
617 // modify old (original) edge to (v1, nv)
618 #ifdef OSG_NO_EDGE_SET
619 edge->setVertices(v1, nv);
620 // std::cerr << "old: " << v1->coords << " - " << nv->coords << std::endl;
621 #else
622 // for this we have to erase the edge from the set
623 // modify its vertices and insert it again.
624 // NOTE: the _pointer_ itself does not change, only its iterator
625 dctpedgeset::iterator edgeit = edges.find(edge);
626 if(edgeit == edges.end() )
627 {
628 std::cerr << "splitedge: edge not found" << std::endl;
629 exit(-1);
630 }
631 edges.erase(edgeit);
632 edge->setVertices(v1, nv);
633 std::pair<dctpedgeset::iterator, bool> sie1;
634 sie1 = edges.insert(edge);
635 if(!sie1.second)
636 {
637 std::cerr << "DCTPMesh::SplitEdge: error: reinserting already existing splitedge (this shouldn't happen)" << std::endl;
638 return NULL;
639 }
640 #endif
641
642 // add original edge to nv
643 // std::cerr << "1-" << edge << " " << nv << std::endl;
644 nv->edges.push_back(edge);
645
646 // add original edge's faces to nv
647 nv->faces.insert(nv->faces.end(), edge->faces.begin(), edge->faces.end() );
648 //// if ( edge->f1 ) nv->faces.push_back( edge->f1 );
649 //// if ( edge->f2 ) nv->faces.push_back( edge->f2 );
650
651 // create new edge between ( nv, v2 )
652 #ifdef OSG_NO_EDGE_SET
653 DCTPEdge *ne = AddEdge(nv, v2, edge->orientation);
654 v2->edges.pop_back(); // remove edge from old vertex (is added later...)
655 // std::cerr << "new: " << nv->coords << " - " << v2->coords << std::endl;
656 #else
657 DCTPEdge *ne = new DCTPEdge(nv, v2, edge->orientation);
658 if(!ne)
659 {
660 std::cerr << "DCTPMesh::SplitEdge: Out of memory... " << std::endl;
661 return NULL;
662 }
663 ne->id = edge_count++;
664
665 std::pair<dctpedgeset::iterator, bool> sie;
666 sie = edges.insert(ne);
667 if(!sie.second)
668 {
669 delete ne;
670 ne = *(sie.first);
671 std::cerr << "DCTPMesh::SplitEdge: error: inserting already existing splitedge (this shouldn't happen)" << std::endl;
672 return NULL;
673 }
674
675 // add new edge to nv
676 nv->edges.push_back(ne);
677 #endif
678
679 // add original edge's faces to the new edge
680 ne->faces.insert(ne->faces.end(), edge->faces.begin(), edge->faces.end() );
681 //// ne->f1 = edge->f1; // Note: we don't have to check here :)
682 //// ne->f2 = edge->f2;
683
684 // change v2's `edge' edge to `ne'
685 std::vector<DCTPEdge*>::iterator v2ee = v2->edges.end();
686 std::vector<DCTPEdge*>::iterator i;
687
688 for(i = v2->edges.begin(); i != v2ee; ++i)
689 if(*i == edge)
690 break;
691
692 if(i == v2ee)
693 {
694 std::cerr << " DCTPMesh::SplitEdge: error: couldn't find original edge in v2 " << std::endl;
695 return NULL;
696 }
697 *i = ne;
698
699 // store the new vertex and the new edge for all incident facez0rz
700 dctpfacevector::iterator fe = edge->faces.end();
701
702 for(dctpfacevector::iterator f = edge->faces.begin(); f != fe; ++f)
703 {
704 (*f)->vertices.push_back(nv);
705 (*f)->edges.push_back(ne);
706 }
707
708 /*
709 if ( edge->f1 ) {
710 edge->f1->vertices.push_back( nv );
711 edge->f1->edges.push_back( ne );
712 }
713 if ( edge->f2 ) {
714 edge->f2->vertices.push_back( nv );
715 edge->f2->edges.push_back( ne );
716 }
717 */
718
719 //propagate `edgeinfo' to the new edge
720 ne->edgeinfo = edge->edgeinfo;
721
722 return nv;
723 }
724
725 double DCTPMesh::computeEdgePointDst(DCTPEdge *edg, Vec3d& pnt)
726 {
727 DCTPVertex *pp0,*pp1;
728 Vec3d p0, p1, pd;
729 edg->getVertices(pp0, pp1);
730 p0 = pp0->coords; p1 = pp1->coords;
731 Vec3d v = p1 - p0;
732 Vec3d w = pnt - p0;
733 double c1 = v[0] * w[0] + v[1] * w[1] + v[2] * w[2];
734 if(c1 <= 0)
735 {
736 pd = p0;
737 Vec3d dist = pnt - p0;
738 return sqrt(dist.squareLength() );
739 }
740 double c2 = v.squareLength();
741 if(c2 <= c1)
742 {
743 pd = p1;
744 Vec3d dist = pnt - p1;
745 return sqrt(dist.squareLength() );
746 }
747 double b = c1 / c2;
748 pd = v * b;
749 pd = pd + p0;
750 Vec3d dist = pnt - pd;
751 return sqrt(dist.squareLength() );
752 }
753
754 DCTPVertex* DCTPMesh::SplitEdge(DCTPEdge *edge, const Vec3d& p)
755 {
756
757 DCTPVertex *v1, *v2;
758 edge->getVertices(v1, v2);
759 #ifdef OSG_INTEGER_MESH
760 vec3i &p1 = v1->coords;
761 vec3i &p2 = v2->coords;
762 #else
763 Vec3d &p1 = v1->coords;
764 Vec3d &p2 = v2->coords;
765 #endif
766 if(DCTPVecIsEqual(p, p1) )
767 return v1;
768 if(DCTPVecIsEqual(p, p2) )
769 return v2;
770
771 Vec3d quickhack = p;
772 double dist = computeEdgePointDst(edge, quickhack);
773 // DEBUG
774 // std::cerr << "SplitEdge, checkpoint I. distance = " << dist << std::endl;
775 #ifdef OSG_INTEGER_MESH
776 if(dist > 0.999)
777 #else
778 if(dist > 1e-9)
779 #endif
780 {
781 #ifdef _DEBUG
782 // std::cerr << "DCTPMesh::SplitEdge, dist too big " << dist << std::endl;
783 #endif
784 return NULL;
785 }
786 // DEBUG
787 // std::cerr << "SplitEdge, checkpoint II.\n";
788 Vec3d lng_vec1 = p1 - p2;
789 double lng1 = sqrt(lng_vec1.squareLength() );
790 Vec3d lng_vec2 = p - p1;
791 double lng2 = sqrt(lng_vec2.squareLength() );
792 double par = lng2 / lng1;
793 return SplitEdge(edge, par);
794 }
795
796 /*
797 * MoveVertex: move a vertex in 3D space.
798 * This must be a separate function, since the vertices are
799 * stored in a set, and the key is their position in 3D space,
800 * so the vertex must be taken out of the set and inserted back
801 * after it was moved.
802 * The pointer to the vertex does not change, only its iterator.
803 * Returns zero on success, and a negative value on failure.
804 */
805 int DCTPMesh::MoveVertex(DCTPVertex *vert, Vec3d &newpos)
806 {
807 if(DCTPVecIsEqual(vert->coords, newpos) )
808 return 0;
809 dctpvertexset::iterator vi = vertices.find(vert);
810 if(vi == vertices.end() )
811 return -1;
812
813 vertices.erase(vi);
814 vert->coords = newpos;
815 std::pair<dctpvertexset::iterator, bool> vinsert;
816 vinsert = vertices.insert(vert);
817 if(!vinsert.second)
818 {
819 std::cerr << "DCTPMesh::MoveVertex: error: reinserting already existing vertex (this shouldn't happen) " <<
820 newpos[0] << " " << newpos[1] << " " << newpos[2] << std::endl;
821 return -2;
822 }
823 return 0;
824 }
825
826 #ifndef OSG_INTEGER_MESH
827 /*
828 * SplitFace: split a face using a sequence of predefined
829 * points. The points must all lie on the edge, plus
830 * be ordered. The result vector contains pointers to the newly inserted
831 * vertices, so that the following holds:
832 *
833 * res[ i ]->coords = points[ i ].
834 */
835 int DCTPMesh::SplitFace(DCTPEdge *edge, DCTPVec3dvector &points, dctpvertexvector &res)
836 {
837 DCTPVertex *v1, *v2;
838 DCTPVertex *v;
839 res.clear();
840 edge->getVertices(v1, v2);
841 Vec3d &lp = points[points.size() - 1];
842 Vec3d &fp = points[0];
843
844 if(DCTPVecIsEqual(lp, fp) ) // just one point
845 {
846 DCTPVertex *nv = SplitFace(edge, lp);
847 if(!nv)
848 return -1;
849 res.push_back(nv);
850 return 0;
851 }
852 if( (v1->coords - lp).squareLength() < (v1->coords - fp).squareLength() )
853 v = v1;
854 else
855 v = v2;
856 // v is the vertex closer to lp.
857 DCTPVec3dvector::size_type k = points.size();
858
859 for(DCTPVec3dvector::size_type i = 0; i < k; ++i)
860 {
861 DCTPVertex *nv = SplitFace(edge, points[i]);
862 if(!nv)
863 return -1;
864 res.push_back(nv);
865 edge = findEdge(nv, v);
866 } //for
867
868 return 0;
869 }
870
871 /*
872 * Split a face, by splitting an edge.
873 * This possibly has an effect on all faces that are incident on the edge.
874 * Presupposes that all affected faces are triangles.
875 *
876 */
877 DCTPVertex *DCTPMesh::SplitFace(DCTPEdge *edge, const Vec3d& p)
878 {
879 // First we have to do an edgesplit, on the edge.
880 DCTPVertex *v1, *v2;
881 edge->getVertices(v1, v2);
882 if(DCTPVecIsEqual(p, v1->coords) )
883 return v1;
884 if(DCTPVecIsEqual(p, v2->coords) )
885 return v2;
886
887 DCTPVertex *nv = SplitEdge(edge, p);
888 if(!nv)
889 return NULL;
890
891 dctpfacevector::iterator fe = edge->faces.end();
892
893 // actually split all the faces belonging to the edge
894 for(dctpfacevector::iterator i = edge->faces.begin(); i != fe; ++i)
895 SplitOneFace(*i, edge, nv);
896
897 return nv;
898 }
899
900 /*
901 * Finish splitting up a face, do the necessary "bookkeeping".
902 *
903 */
904 void DCTPMesh::SplitOneFace(DCTPFace *f, DCTPEdge *edge, DCTPVertex *nv)
905 {
906 DCTPVertex *left, *right, *third;
907 DCTPEdge *e1, *e2, *e3;
908 unsigned int i;
909
910 edge->getVertices(left, right);
911 if(left == nv)
912 {
913 left = right; right = NULL;
914 }
915 if(right == nv)
916 right = NULL;
917
918 //DEBUGCHECK
919 if(right)
920 std::cerr << "DCTPMesh::SplitOneFace: something strange..." << std::endl;
921
922 //we must find the edge which is:
923 // - edge over `f'
924 // - has `nv' as one of its vertices
925 // - not equal to `edge'
926 e3 = NULL;
927 std::vector<DCTPEdge*>::iterator fee = f->edges.end();
928
929 for(std::vector<DCTPEdge*>::iterator e = f->edges.begin(); e != fee; ++e)
930 {
931 DCTPVertex *tv1, *tv2;
932 if(*e != edge)
933 {
934 (*e)->getVertices(tv1, tv2);
935 if(tv1 == nv || tv2 == nv)
936 {
937 e3 = *e;
938 break;
939 } //if
940 } //if
941 } //for
942
943 if(!e3)
944 std::cerr << "DCTPMesh::SplitOneFace: something strange #1.5..." << std::endl;
945 e3->getVertices(right, third);
946 if(right == nv)
947 {
948 right = third; third = NULL;
949 }
950 if(third == nv)
951 third = NULL;
952 if(third)
953 std::cerr << "DCTPMesh::SplitOneFace: something strange #2..." << std::endl;
954
955 for(i = 0; i < 3; ++i)
956 #ifdef OSG_UNION_TRI_QUAD
957
958
959
960 if(f->orig_face[i] != left && f->orig_face[i] != right)
961 {
962 third = f->orig_face[i]; break;
963 }
964
965 #else
966
967
968
969 if(f->orig_triangle[i] != left && f->orig_triangle[i] != right)
970 {
971 third = f->orig_triangle[i]; break;
972 }
973 #endif
974 if(!third)
975 std::cerr << "DCTPMesh::SplitOneFace: something strange #3..." << std::endl;
976
977 e1 = findEdge(left, third);
978 if(!e1)
979 std::cerr << "DCTPMesh::SplitOneFace: something strange #4..." << std::endl;
980 e2 = findEdge(third, right);
981 if(!e2)
982 std::cerr << "DCTPMesh::SplitOneFace: something strange #5..." << std::endl;
983
984 //create new unoriented edge between 'third' and 'nv'
985 DCTPEdge *ne = AddEdge(third, nv, 0);
986 //modify `f' such as:
987 //change e2 to ne
988 e2->RemoveFace(f);
989 ne->AddFace(f);
990 f->RemoveEdge(e2);
991 f->AddEdge(ne);
992
993 //replace `right' with `nv'
994 for(i = 0; i < 3; ++i)
995 #ifdef OSG_UNION_TRI_QUAD
996
997
998
999 if(f->orig_face[i] == right)
1000 {
1001 f->orig_face[i] = nv;
1002 }
1003
1004 #else
1005
1006
1007
1008 if(f->orig_triangle[i] == right)
1009 {
1010 f->orig_triangle[i] = nv;
1011 }
1012 #endif
1013 f->ReplaceVertex(right, nv);
1014 //remove last vertex of `f', which must be `nv'
1015 if(f->vertices[f->vertices.size() - 1] != nv)
1016 std::cerr << "DCTPMesh::SplitOneFace: something strange #6..." << std::endl;
1017 f->vertices.resize(f->vertices.size() - 1);
1018
1019 //remove `f' from right
1020 right->RemoveFace(f);
1021
1022 //remove `e3' from `f', since SplitEdge added it
1023 f->RemoveEdge(e3);
1024 //remove `f' from `e3', since SplitEdge added it
1025 e3->RemoveFace(f);
1026
1027 //OK, we're done with `f' so let's create the new face and fill it in!
1028 DCTPFace *nf = AddFace();
1029 //add the new edges
1030 nf->AddEdge(ne);
1031 nf->AddEdge(e2);
1032 nf->AddEdge(e3);
1033
1034 if(f->vertices.size() != 3)
1035 std::cerr << "DCTPMesh::SplitOneFace: something strange #7..." << std::endl;
1036
1037 //add the vertices _in order_
1038 //FIXME: it could be more efficient if we create `nf' before, and copy
1039 //everything from `f', and replace `left' with `nv'
1040 for(i = 0; i< 3; ++i)
1041 {
1042 #ifdef OSG_UNION_TRI_QUAD
1043 if(f->orig_face[i] == left)
1044 nf->orig_face[i] = nv;
1045 else if(f->orig_face[i] == nv)
1046 nf->orig_face[i] = right;
1047 else
1048 nf->orig_face[i] = f->orig_face[i];
1049 #else
1050 if(f->orig_triangle[i] == left)
1051 nf->orig_triangle[i] = nv;
1052 else if(f->orig_triangle[i] == nv)
1053 nf->orig_triangle[i] = right;
1054 else
1055 nf->orig_triangle[i] = f->orig_triangle[i];
1056 #endif
1057
1058 if(f->vertices[i] == left)
1059 nf->vertices.push_back(nv);
1060 else if(f->vertices[i] == nv)
1061 nf->vertices.push_back(right);
1062 else
1063 nf->vertices.push_back(f->vertices[i]);
1064 } //for
1065
1066 //add `nf' to its vertices
1067 nv->AddFace(nf);
1068 third->AddFace(nf);
1069 right->AddFace(nf);
1070
1071 //and to its edges
1072 ne->AddFace(nf);
1073 e2->AddFace(nf);
1074 e3->AddFace(nf);
1075
1076 } //end SplitOneFace
1077 #endif
1078
1079
1080 /*
1081 * Subdivide the current (quad) face into four smaller faces.
1082 * Change the values of the current face to be the upper left
1083 * quarter, and generate new faces, edges, etc. for the other
1084 * three quarters.
1085 */
1086 int DCTPMesh::SubdivideQuad(DCTPFace *f)
1087 {
1088
1089 Vec3d n, s, e, w;
1090 DCTPVertex *np = NULL, *sp = NULL, *ep = NULL, *wp = NULL;
1091
1092 #ifdef OSG_UNION_TRI_QUAD
1093 n = (f->orig_face[0]->coords + f->orig_face[1]->coords) * 0.5;
1094 s = (f->orig_face[2]->coords + f->orig_face[3]->coords) * 0.5;
1095 e = (f->orig_face[1]->coords + f->orig_face[2]->coords) * 0.5;
1096 w = (f->orig_face[3]->coords + f->orig_face[0]->coords) * 0.5;
1097 #else
1098 n = (f->orig_quad[0]->coords + f->orig_quad[1]->coords) * 0.5;
1099 s = (f->orig_quad[2]->coords + f->orig_quad[3]->coords) * 0.5;
1100 e = (f->orig_quad[1]->coords + f->orig_quad[2]->coords) * 0.5;
1101 w = (f->orig_quad[3]->coords + f->orig_quad[0]->coords) * 0.5;
1102 #endif
1103
1104 // iterate through the vertices and do splitedges if necessary
1105 std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
1106 std::vector<DCTPVertex*>::iterator i;
1107
1108 for(i = f->vertices.begin(); i != ve; ++i)
1109 {
1110 if(DCTPVecIsEqual( (*i)->coords, n) )
1111 np = *i;
1112 if(DCTPVecIsEqual( (*i)->coords, s) )
1113 sp = *i;
1114 if(DCTPVecIsEqual( (*i)->coords, e) )
1115 ep = *i;
1116 if(DCTPVecIsEqual( (*i)->coords, w) )
1117 wp = *i;
1118 }
1119
1120 #ifdef OSG_UNION_TRI_QUAD
1121 if(!np)
1122 np = SplitEdge(getEdgeFromFace(f, f->orig_face[0], f->orig_face[1]), 0.5);
1123 if(!sp)
1124 sp = SplitEdge(getEdgeFromFace(f, f->orig_face[2], f->orig_face[3]), 0.5);
1125 if(!ep)
1126 ep = SplitEdge(getEdgeFromFace(f, f->orig_face[1], f->orig_face[2]), 0.5);
1127 if(!wp)
1128 wp = SplitEdge(getEdgeFromFace(f, f->orig_face[3], f->orig_face[0]), 0.5);
1129 #else
1130 if(!np)
1131 np = SplitEdge(getEdgeFromFace(f, f->orig_quad[0], f->orig_quad[1]), 0.5);
1132 if(!sp)
1133 sp = SplitEdge(getEdgeFromFace(f, f->orig_quad[2], f->orig_quad[3]), 0.5);
1134 if(!ep)
1135 ep = SplitEdge(getEdgeFromFace(f, f->orig_quad[1], f->orig_quad[2]), 0.5);
1136 if(!wp)
1137 wp = SplitEdge(getEdgeFromFace(f, f->orig_quad[3], f->orig_quad[0]), 0.5);
1138 #endif
1139
1140 //these removals must be done after the splitedge operators
1141 //go through the edges of the face, and remove this face
1142 //from each edge.
1143 std::vector<DCTPEdge*>::iterator ee = f->edges.end();
1144
1145 for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
1146 (*ed)->RemoveFace(f);
1147
1148 //go through the vertices of the face, and remove this face
1149 //from each vertex.
1150 ve = f->vertices.end();
1151
1152 for(i = f->vertices.begin(); i != ve; ++i)
1153 (*i)->RemoveFace(f);
1154
1155
1156 buildNewFaces(f, np, sp, wp, ep);
1157 return 0;
1158 }
1159
1160 void DCTPMesh::buildNewFaces(DCTPFace *f, DCTPVertex *np, DCTPVertex *sp, DCTPVertex *wp, DCTPVertex *ep)
1161 {
1162 //set up middle point
1163 Vec3d middle = (np->coords + sp->coords) * 0.5;
1164 DCTPVertex * middlev = AddVertex(middle);
1165 //set up new edges to/from middlepoint
1166 // v1 .----. v2
1167 // | |
1168 // v4 `----' v3
1169 std::vector<DCTPVertex *> vertsides[8];
1170
1171 setupSides(f, vertsides, 0.5, 0.5);
1172 sortSides(f, vertsides);
1173 //clear original face's edges and vertices
1174 f->edges.clear();
1175 f->vertices.clear();
1176
1177 DCTPVertex * quad_save[4];
1178 #ifdef OSG_UNION_TRI_QUAD
1179 quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
1180 quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
1181 #else
1182 quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
1183 quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
1184 #endif
1185
1186 //construct the vertices-vectors of the new faces
1187 std::vector<DCTPVertex *> vertsvec;
1188 //upper left
1189 vertsvec.push_back(wp);
1190 vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
1191 vertsvec.push_back(quad_save[0]);
1192 vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
1193 vertsvec.push_back(np);
1194 vertsvec.push_back(middlev);
1195 buildQuadFace(vertsvec, f);
1196 #ifdef OSG_UNION_TRI_QUAD
1197 f->orig_face[1] = np; f->orig_face[2] = middlev; f->orig_face[3] = wp;
1198 #else
1199 f->orig_quad[1] = np; f->orig_quad[2] = middlev; f->orig_quad[3] = wp;
1200 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1201 #endif
1202 //upper right
1203 vertsvec.clear();
1204 vertsvec.push_back(np);
1205 vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
1206 vertsvec.push_back(quad_save[1]);
1207 vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
1208 vertsvec.push_back(ep);
1209 vertsvec.push_back(middlev);
1210 // std::cerr <<"vertsvec size: " << vertsvec.size() << std::endl;
1211 f = buildQuadFace(vertsvec, NULL);
1212 #ifdef OSG_UNION_TRI_QUAD
1213 f->orig_face[0] = np; f->orig_face[1] = quad_save[1];
1214 f->orig_face[2] = ep; f->orig_face[3] = middlev;
1215 #else
1216 f->orig_quad[0] = np; f->orig_quad[1] = quad_save[1];
1217 f->orig_quad[2] = ep; f->orig_quad[3] = middlev;
1218 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1219 #endif
1220 //lower right
1221 vertsvec.clear();
1222 vertsvec.push_back(ep);
1223 vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
1224 vertsvec.push_back(quad_save[2]);
1225 vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
1226 vertsvec.push_back(sp);
1227 vertsvec.push_back(middlev);
1228 f = buildQuadFace(vertsvec, NULL);
1229 #ifdef OSG_UNION_TRI_QUAD
1230 f->orig_face[0] = middlev; f->orig_face[1] = ep;
1231 f->orig_face[2] = quad_save[2]; f->orig_face[3] = sp;
1232 #else
1233 f->orig_quad[0] = middlev; f->orig_quad[1] = ep;
1234 f->orig_quad[2] = quad_save[2]; f->orig_quad[3] = sp;
1235 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1236 #endif
1237 //lower left
1238 vertsvec.clear();
1239 vertsvec.push_back(sp);
1240 vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
1241 vertsvec.push_back(quad_save[3]);
1242 vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
1243 vertsvec.push_back(wp);
1244 vertsvec.push_back(middlev);
1245 f = buildQuadFace(vertsvec, NULL);
1246 #ifdef OSG_UNION_TRI_QUAD
1247 f->orig_face[0] = wp; f->orig_face[1] = middlev;
1248 f->orig_face[2] = sp; f->orig_face[3] = quad_save[3];
1249 #else
1250 f->orig_quad[0] = wp; f->orig_quad[1] = middlev;
1251 f->orig_quad[2] = sp; f->orig_quad[3] = quad_save[3];
1252 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1253 #endif
1254 }
1255
1256 /*
1257 * Subdivide the current (quad) face into two smaller faces.
1258 * Change the values of the current face to be the upper
1259 * half, and generate new faces, edges, etc. for the other
1260 * quad.
1261 */
1262 int DCTPMesh::SubdivideQuadNS(DCTPFace *f)
1263 {
1264
1265 Vec3d e, w;
1266 DCTPVertex *ep = NULL, *wp = NULL;
1267
1268 #ifdef OSG_UNION_TRI_QUAD
1269 e = (f->orig_face[1]->coords + f->orig_face[2]->coords) * 0.5;
1270 w = (f->orig_face[3]->coords + f->orig_face[0]->coords) * 0.5;
1271 #else
1272 e = (f->orig_quad[1]->coords + f->orig_quad[2]->coords) * 0.5;
1273 w = (f->orig_quad[3]->coords + f->orig_quad[0]->coords) * 0.5;
1274 #endif
1275
1276 // iterate through the vertices and do splitedges if necessary
1277 std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
1278 std::vector<DCTPVertex*>::iterator i;
1279
1280 for(i = f->vertices.begin(); i != ve; ++i)
1281 {
1282 if(DCTPVecIsEqual( (*i)->coords, e) )
1283 ep = *i;
1284 if(DCTPVecIsEqual( (*i)->coords, w) )
1285 wp = *i;
1286 }
1287
1288 #ifdef OSG_UNION_TRI_QUAD
1289 if(!ep)
1290 ep = SplitEdge(getEdgeFromFace(f, f->orig_face[1], f->orig_face[2]), 0.5);
1291 if(!wp)
1292 wp = SplitEdge(getEdgeFromFace(f, f->orig_face[3], f->orig_face[0]), 0.5);
1293 #else
1294 if(!ep)
1295 ep = SplitEdge(getEdgeFromFace(f, f->orig_quad[1], f->orig_quad[2]), 0.5);
1296 if(!wp)
1297 wp = SplitEdge(getEdgeFromFace(f, f->orig_quad[3], f->orig_quad[0]), 0.5);
1298 #endif
1299
1300 //these removals must be done after the splitedge operators
1301 //go through the edges of the face, and remove this face
1302 //from each edge.
1303 std::vector<DCTPEdge*>::iterator ee = f->edges.end();
1304
1305 for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
1306 (*ed)->RemoveFace(f);
1307
1308 //go through the vertices of the face, and remove this face
1309 //from each vertex.
1310 ve = f->vertices.end();
1311
1312 for(i = f->vertices.begin(); i != ve; ++i)
1313 (*i)->RemoveFace(f);
1314
1315
1316 buildNewFacesNS(f, wp, ep);
1317 return 0;
1318 }
1319
1320 void DCTPMesh::buildNewFacesNS(DCTPFace *f, DCTPVertex *wp, DCTPVertex *ep)
1321 {
1322 //set up middle point
1323 #ifdef OSG_UNION_TRI_QUAD
1324 DCTPVertex *np = findVertex( (f->orig_face[0]->coords + f->orig_face[1]->coords) * 0.5);
1325 DCTPVertex *sp = findVertex( (f->orig_face[2]->coords + f->orig_face[3]->coords) * 0.5);
1326 #else
1327 DCTPVertex *np = findVertex( (f->orig_quad[0]->coords + f->orig_quad[1]->coords) * 0.5);
1328 DCTPVertex *sp = findVertex( (f->orig_quad[2]->coords + f->orig_quad[3]->coords) * 0.5);
1329 #endif
1330 //set up new edges
1331 // v1 .----. v2
1332 // | |
1333 // v4 `----' v3
1334 std::vector<DCTPVertex *> vertsides[8];
1335
1336 setupSides(f, vertsides, 0.5, 0.5);
1337 sortSides(f, vertsides);
1338 //clear original face's edges and vertices
1339 f->edges.clear();
1340 f->vertices.clear();
1341
1342 DCTPVertex * quad_save[4];
1343 #ifdef OSG_UNION_TRI_QUAD
1344 quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
1345 quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
1346 #else
1347 quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
1348 quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
1349 #endif
1350
1351 //construct the vertices-vectors of the new faces
1352 std::vector<DCTPVertex *> vertsvec;
1353 //upper
1354 vertsvec.push_back(quad_save[0]);
1355 vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
1356 if(np)
1357 vertsvec.push_back(np);
1358 vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
1359 vertsvec.push_back(quad_save[1]);
1360 vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
1361 vertsvec.push_back(ep);
1362 vertsvec.push_back(wp);
1363 vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
1364 buildQuadFace(vertsvec, f);
1365 #ifdef OSG_UNION_TRI_QUAD
1366 f->orig_face[2] = ep; f->orig_face[3] = wp;
1367 #else
1368 f->orig_quad[2] = ep; f->orig_quad[3] = wp;
1369 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1370 #endif
1371 /* std::cerr << "NS: " << f->orig_quad[ 0 ]->coords << " ";
1372 std::cerr << f->orig_quad[ 1 ]->coords << " ";
1373 std::cerr << f->orig_quad[ 2 ]->coords << " ";
1374 std::cerr << f->orig_quad[ 3 ]->coords << std::endl;*/
1375 //lower
1376 vertsvec.clear();
1377 vertsvec.push_back(wp);
1378 vertsvec.push_back(ep);
1379 vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
1380 vertsvec.push_back(quad_save[2]);
1381 vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
1382 if(sp)
1383 vertsvec.push_back(sp);
1384 vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
1385 vertsvec.push_back(quad_save[3]);
1386 vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
1387 f = buildQuadFace(vertsvec, NULL);
1388 #ifdef OSG_UNION_TRI_QUAD
1389 f->orig_face[0] = wp; f->orig_face[1] = ep;
1390 f->orig_face[2] = quad_save[2]; f->orig_face[3] = quad_save[3];
1391 #else
1392 f->orig_quad[0] = wp; f->orig_quad[1] = ep;
1393 f->orig_quad[2] = quad_save[2]; f->orig_quad[3] = quad_save[3];
1394 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1395 #endif
1396 /* std::cerr << f->orig_quad[ 0 ]->coords << " ";
1397 std::cerr << f->orig_quad[ 1 ]->coords << " ";
1398 std::cerr << f->orig_quad[ 2 ]->coords << " ";
1399 std::cerr << f->orig_quad[ 3 ]->coords << std::endl;*/
1400
1401 }
1402
1403 /*
1404 * Subdivide the current (quad) face into two smaller faces.
1405 * Change the values of the current face to be the left
1406 * half, and generate new faces, edges, etc. for the other
1407 * quad.
1408 */
1409 int DCTPMesh::SubdivideQuadEW(DCTPFace *f)
1410 {
1411
1412 Vec3d n, s;
1413 DCTPVertex *np = NULL, *sp = NULL;
1414
1415 #ifdef OSG_UNION_TRI_QUAD
1416 n = (f->orig_face[0]->coords + f->orig_face[1]->coords) * 0.5;
1417 s = (f->orig_face[2]->coords + f->orig_face[3]->coords) * 0.5;
1418 #else
1419 n = (f->orig_quad[0]->coords + f->orig_quad[1]->coords) * 0.5;
1420 s = (f->orig_quad[2]->coords + f->orig_quad[3]->coords) * 0.5;
1421 #endif
1422
1423 //iterate through the vertices and do splitedges if necessary
1424 std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
1425 std::vector<DCTPVertex*>::iterator i;
1426
1427 for(i = f->vertices.begin(); i != ve; ++i)
1428 {
1429 if(DCTPVecIsEqual( (*i)->coords, n) )
1430 np = *i;
1431 if(DCTPVecIsEqual( (*i)->coords, s) )
1432 sp = *i;
1433 }
1434
1435 #ifdef OSG_UNION_TRI_QUAD
1436 if(!np)
1437 np = SplitEdge(getEdgeFromFace(f, f->orig_face[0], f->orig_face[1]), 0.5);
1438 if(!sp)
1439 sp = SplitEdge(getEdgeFromFace(f, f->orig_face[2], f->orig_face[3]), 0.5);
1440 #else
1441 if(!np)
1442 np = SplitEdge(getEdgeFromFace(f, f->orig_quad[0], f->orig_quad[1]), 0.5);
1443 if(!sp)
1444 sp = SplitEdge(getEdgeFromFace(f, f->orig_quad[2], f->orig_quad[3]), 0.5);
1445 #endif
1446
1447 //these removals must be done after the splitedge operators
1448 //go through the edges of the face, and remove this face
1449 //from each edge.
1450 std::vector<DCTPEdge*>::iterator ee = f->edges.end();
1451
1452 for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
1453 (*ed)->RemoveFace(f);
1454
1455 //go through the vertices of the face, and remove this face
1456 //from each vertex.
1457 ve = f->vertices.end();
1458
1459 for(i = f->vertices.begin(); i != ve; ++i)
1460 (*i)->RemoveFace(f);
1461
1462
1463 buildNewFacesEW(f, np, sp);
1464 return 0;
1465 }
1466
1467 void DCTPMesh::buildNewFacesEW(DCTPFace *f, DCTPVertex *np, DCTPVertex *sp)
1468 {
1469 //set up middle point
1470 #ifdef OSG_UNION_TRI_QUAD
1471 DCTPVertex *ep = findVertex( (f->orig_face[1]->coords + f->orig_face[2]->coords) * 0.5);
1472 DCTPVertex *wp = findVertex( (f->orig_face[0]->coords + f->orig_face[3]->coords) * 0.5);
1473 #else
1474 DCTPVertex *ep = findVertex( (f->orig_quad[1]->coords + f->orig_quad[2]->coords) * 0.5);
1475 DCTPVertex *wp = findVertex( (f->orig_quad[0]->coords + f->orig_quad[3]->coords) * 0.5);
1476 #endif
1477 //set up new edges
1478 // v1 .----. v2
1479 // | |
1480 // v4 `----' v3
1481 std::vector<DCTPVertex *> vertsides[8];
1482
1483 setupSides(f, vertsides, 0.5, 0.5);
1484 sortSides(f, vertsides);
1485 //clear original face's edges and vertices
1486 f->edges.clear();
1487 f->vertices.clear();
1488
1489 DCTPVertex * quad_save[4];
1490 #ifdef OSG_UNION_TRI_QUAD
1491 quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
1492 quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
1493 #else
1494 quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
1495 quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
1496 #endif
1497
1498 //construct the vertices-vectors of the new faces
1499 std::vector<DCTPVertex *> vertsvec;
1500 //left
1501 vertsvec.push_back(quad_save[0]);
1502 vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
1503 vertsvec.push_back(np);
1504 vertsvec.push_back(sp);
1505 vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
1506 vertsvec.push_back(quad_save[3]);
1507 vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
1508 if(wp)
1509 vertsvec.push_back(wp);
1510 vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
1511 buildQuadFace(vertsvec, f);
1512 #ifdef OSG_UNION_TRI_QUAD
1513 f->orig_face[1] = np; f->orig_face[2] = sp;
1514 #else
1515 f->orig_quad[1] = np; f->orig_quad[2] = sp;
1516 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1517 #endif
1518 /* std::cerr << "EW: " << f->orig_face[ 0 ]->coords << " ";
1519 std::cerr << f->orig_face[ 0 ]->coords << " ";
1520 std::cerr << f->orig_face[ 1 ]->coords << " ";
1521 std::cerr << f->orig_face[ 2 ]->coords << " ";
1522 std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
1523 //right
1524 vertsvec.clear();
1525 vertsvec.push_back(np);
1526 vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
1527 vertsvec.push_back(quad_save[1]);
1528 vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
1529 if(ep)
1530 vertsvec.push_back(ep);
1531 vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
1532 vertsvec.push_back(quad_save[2]);
1533 vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
1534 vertsvec.push_back(sp);
1535 f = buildQuadFace(vertsvec, NULL);
1536 #ifdef OSG_UNION_TRI_QUAD
1537 f->orig_face[0] = np; f->orig_face[1] = quad_save[1];
1538 f->orig_face[2] = quad_save[2]; f->orig_face[3] = sp;
1539 #else
1540 f->orig_quad[0] = np; f->orig_quad[1] = quad_save[1];
1541 f->orig_quad[2] = quad_save[2]; f->orig_quad[3] = sp;
1542 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1543 #endif
1544 /* std::cerr << f->orig_face[ 0 ]->coords << " ";
1545 std::cerr << f->orig_face[ 1 ]->coords << " ";
1546 std::cerr << f->orig_face[ 2 ]->coords << " ";
1547 std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
1548
1549 }
1550
1551 /*
1552 * Subdivide the current (quad) face into two smaller faces.
1553 * Change the values of the current face to be the upper
1554 * half, and generate new faces, edges, etc. for the other
1555 * quad.
1556 */
1557 int DCTPMesh::SubdivideQuadNS(DCTPFace *f, double dRatio)
1558 {
1559
1560 Vec3d e, w;
1561 DCTPVertex *ep = NULL, *wp = NULL;
1562
1563 #ifdef OSG_UNION_TRI_QUAD
1564 e[0] = f->orig_face[2]->coords[0];
1565 w[0] = f->orig_face[3]->coords[0];
1566 e[1] = f->orig_face[2]->coords[1] + (f->orig_face[1]->coords[1] - f->orig_face[2]->coords[1]) * dRatio;
1567 e[1] = 10.0 * DCTP_EPS * floor(e[1] / (10.0 * DCTP_EPS) + 0.5);
1568 w[1] = e[1];
1569 e[2] = w[2] = 0.0;
1570 #else
1571 e = f->orig_quad[2]->coords + (f->orig_quad[1]->coords - f->orig_quad[2]->coords) * dRatio;
1572 w = f->orig_quad[3]->coords + (f->orig_quad[0]->coords - f->orig_quad[3]->coords) * dRatio;
1573 #endif
1574
1575 // std::cerr.precision( 16 );
1576 // std::cerr << "SudivideQuadNS: " << dRatio << std::endl;
1577 // f->dump_triangle( );
1578
1579 // iterate through the vertices and do splitedges if necessary
1580 std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
1581 std::vector<DCTPVertex*>::iterator i;
1582
1583 for(i = f->vertices.begin(); i != ve; ++i)
1584 {
1585 if(DCTPVecIsEqual( (*i)->coords, e) )
1586 ep = *i;
1587 if(DCTPVecIsEqual( (*i)->coords, w) )
1588 wp = *i;
1589 }
1590
1591 std::vector<DCTPEdge*>::iterator ee = f->edges.end();
1592 std::vector<DCTPEdge*>::iterator ei;
1593
1594 for(ei = f->edges.begin(); ei != ee; ++ei)
1595 {
1596 ep = SplitEdge(*ei, e);
1597 if(ep != NULL)
1598 break;
1599 }
1600
1601 ee = f->edges.end();
1602
1603 for(ei = f->edges.begin(); ei != ee; ++ei)
1604 {
1605 wp = SplitEdge(*ei, w);
1606 if(wp != NULL)
1607 break;
1608 }
1609
1610 if( (ep == NULL) || (wp == NULL) )
1611 {
1612 std::cerr << "error" << std::endl;
1613 }
1614
1615 // these removals must be done after the splitedge operators
1616 // go through the edges of the face, and remove this face
1617 // from each edge.
1618 ee = f->edges.end();
1619
1620 for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
1621 (*ed)->RemoveFace(f);
1622
1623 // go through the vertices of the face, and remove this face
1624 // from each vertex.
1625 ve = f->vertices.end();
1626
1627 for(i = f->vertices.begin(); i != ve; ++i)
1628 (*i)->RemoveFace(f);
1629
1630
1631 buildNewFacesNS(f, wp, ep, dRatio);
1632 return 0;
1633 }
1634
1635 void DCTPMesh::buildNewFacesNS(DCTPFace *f, DCTPVertex *wp, DCTPVertex *ep, double dRatio)
1636 {
1637 //set up middle point
1638 #ifdef OSG_UNION_TRI_QUAD
1639 DCTPVertex *np = findVertex( (f->orig_face[0]->coords + f->orig_face[1]->coords) * 0.5);
1640 DCTPVertex *sp = findVertex( (f->orig_face[3]->coords + f->orig_face[2]->coords) * 0.5);
1641 #else
1642 DCTPVertex *np = findVertex( (f->orig_quad[0]->coords + f->orig_quad[1]->coords) * 0.5);
1643 DCTPVertex *sp = findVertex( (f->orig_quad[3]->coords + f->orig_quad[2]->coords) * 0.5);
1644 #endif
1645 //set up new edges
1646 // v1 .----. v2
1647 // | |
1648 // v4 `----' v3
1649 std::vector<DCTPVertex *> vertsides[8];
1650
1651 setupSides(f, vertsides, 0.5, dRatio);
1652 sortSides(f, vertsides);
1653 //clear original face's edges and vertices
1654 f->edges.clear();
1655 f->vertices.clear();
1656
1657 DCTPVertex * quad_save[4];
1658 #ifdef OSG_UNION_TRI_QUAD
1659 quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
1660 quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
1661 #else
1662 quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
1663 quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
1664 #endif
1665
1666 //construct the vertices-vectors of the new faces
1667 std::vector<DCTPVertex *> vertsvec;
1668 //lower
1669 vertsvec.push_back(wp);
1670 vertsvec.push_back(ep);
1671 vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
1672 vertsvec.push_back(quad_save[2]);
1673 vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
1674 if(sp)
1675 vertsvec.push_back(sp);
1676 vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
1677 vertsvec.push_back(quad_save[3]);
1678 vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
1679 buildQuadFace(vertsvec, f);
1680 #ifdef OSG_UNION_TRI_QUAD
1681 f->orig_face[0] = wp; f->orig_face[1] = ep;
1682 // f->orig_face[ 2 ] = quad_save[ 2 ]; f->orig_face[ 3 ] = quad_save[ 3 ];
1683 #else
1684 f->orig_quad[0] = wp; f->orig_quad[1] = ep;
1685 // f->orig_quad[ 2 ] = quad_save[ 2 ]; f->orig_quad[ 3 ] = quad_save[ 3 ];
1686 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1687 #endif
1688 /* std::cerr << "NS: " << f << std::endl;
1689 std::cerr << f->orig_face[ 0 ]->coords << std::endl;
1690 std::cerr << f->orig_face[ 1 ]->coords << std::endl;
1691 std::cerr << f->orig_face[ 2 ]->coords << std::endl;
1692 std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
1693 //upper
1694 vertsvec.clear();
1695 vertsvec.push_back(quad_save[0]);
1696 vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
1697 if(np)
1698 vertsvec.push_back(np);
1699 vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
1700 vertsvec.push_back(quad_save[1]);
1701 vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
1702 vertsvec.push_back(ep);
1703 vertsvec.push_back(wp);
1704 vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
1705 f = buildQuadFace(vertsvec, NULL);
1706 #ifdef OSG_UNION_TRI_QUAD
1707 f->orig_face[0] = quad_save[0]; f->orig_face[1] = quad_save[1];
1708 f->orig_face[2] = ep; f->orig_face[3] = wp;
1709 #else
1710 f->orig_quad[0] = quad_save[0]; f->orig_quad[1] = quad_save[1];
1711 f->orig_quad[2] = ep; f->orig_quad[3] = wp;
1712 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1713 #endif
1714 /* std::cerr << f << std::endl;
1715 std::cerr << f->orig_face[ 0 ]->coords << std::endl;
1716 std::cerr << f->orig_face[ 1 ]->coords << std::endl;
1717 std::cerr << f->orig_face[ 2 ]->coords << std::endl;
1718 std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
1719
1720 }
1721
1722 /*
1723 * Subdivide the current (quad) face into two smaller faces.
1724 * Change the values of the current face to be the left
1725 * half, and generate new faces, edges, etc. for the other
1726 * quad.
1727 */
1728 int DCTPMesh::SubdivideQuadEW(DCTPFace *f, double dRatio)
1729 {
1730
1731 Vec3d n, s;
1732 DCTPVertex *np = NULL, *sp = NULL;
1733
1734 #ifdef OSG_UNION_TRI_QUAD
1735 n[0] = f->orig_face[0]->coords[0] + (f->orig_face[1]->coords[0] - f->orig_face[0]->coords[0]) * dRatio;
1736 n[0] = 10.0 * DCTP_EPS * floor(n[0] / (10.0 * DCTP_EPS) + 0.5);
1737 s[0] = n[0];
1738 n[1] = f->orig_face[0]->coords[1];
1739 s[1] = f->orig_face[3]->coords[1];
1740 n[2] = s[2] = 0.0;
1741 #else
1742 n = f->orig_quad[0]->coords + (f->orig_quad[1]->coords - f->orig_quad[0]->coords) * dRatio;
1743 s = f->orig_quad[3]->coords + (f->orig_quad[2]->coords - f->orig_quad[3]->coords) * dRatio;
1744 #endif
1745
1746 // std::cerr.precision( 4 );
1747 // std::cerr << "SudivideQuadEW: " << dRatio << std::endl;
1748 // f->dump_triangle( );
1749
1750 // iterate through the vertices and do splitedges if necessary
1751 std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
1752 std::vector<DCTPVertex*>::iterator i;
1753
1754 for(i = f->vertices.begin(); i != ve; ++i)
1755 {
1756 if(DCTPVecIsEqual( (*i)->coords, n) )
1757 np = *i;
1758 if(DCTPVecIsEqual( (*i)->coords, s) )
1759 sp = *i;
1760 }
1761
1762 std::vector<DCTPEdge*>::iterator ee = f->edges.end();
1763 std::vector<DCTPEdge*>::iterator ei;
1764
1765 for(ei = f->edges.begin(); ei != ee; ++ei)
1766 {
1767 np = SplitEdge(*ei, n);
1768 if(np != NULL)
1769 break;
1770 }
1771
1772 ee = f->edges.end();
1773
1774 for(ei = f->edges.begin(); ei != ee; ++ei)
1775 {
1776 sp = SplitEdge(*ei, s);
1777 if(sp != NULL)
1778 break;
1779 }
1780
1781 if( (np == NULL) || (sp == NULL) )
1782 {
1783 std::cerr << "error" << std::endl;
1784 }
1785
1786 //these removals must be done after the splitedge operators
1787 //go through the edges of the face, and remove this face
1788 //from each edge.
1789 /*std::vector< DCTPEdge* >::iterator*/
1790 ee = f->edges.end();
1791
1792 for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
1793 (*ed)->RemoveFace(f);
1794
1795 //go through the vertices of the face, and remove this face
1796 //from each vertex.
1797 ve = f->vertices.end();
1798
1799 for(i = f->vertices.begin(); i != ve; ++i)
1800 (*i)->RemoveFace(f);
1801
1802
1803 buildNewFacesEW(f, np, sp, dRatio);
1804 return 0;
1805 }
1806
1807 void DCTPMesh::buildNewFacesEW(DCTPFace *f, DCTPVertex *np, DCTPVertex *sp, double dRatio)
1808 {
1809 //set up middle point
1810 #ifdef OSG_UNION_TRI_QUAD
1811 DCTPVertex *ep = findVertex( (f->orig_face[2]->coords + f->orig_face[1]->coords) * 0.5);
1812 DCTPVertex *wp = findVertex( (f->orig_face[3]->coords + f->orig_face[0]->coords) * 0.5);
1813 #else
1814 DCTPVertex *ep = findVertex( (f->orig_quad[2]->coords + f->orig_quad[1]->coords) * 0.5);
1815 DCTPVertex *wp = findVertex( (f->orig_quad[3]->coords + f->orig_quad[0]->coords) * 0.5);
1816 #endif
1817 //set up new edges
1818 // v1 .----. v2
1819 // | |
1820 // v4 `----' v3
1821 std::vector<DCTPVertex *> vertsides[8];
1822
1823 setupSides(f, vertsides, dRatio, 0.5);
1824 sortSides(f, vertsides);
1825 //clear original face's edges and vertices
1826 f->edges.clear();
1827 f->vertices.clear();
1828
1829 DCTPVertex * quad_save[4];
1830 #ifdef OSG_UNION_TRI_QUAD
1831 quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
1832 quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
1833 #else
1834 quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
1835 quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
1836 #endif
1837
1838 //construct the vertices-vectors of the new faces
1839 std::vector<DCTPVertex *> vertsvec;
1840 //left
1841 vertsvec.push_back(quad_save[0]);
1842 vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
1843 vertsvec.push_back(np);
1844 vertsvec.push_back(sp);
1845 vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
1846 vertsvec.push_back(quad_save[3]);
1847 vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
1848 if(wp)
1849 vertsvec.push_back(wp);
1850 vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
1851 buildQuadFace(vertsvec, f);
1852 #ifdef OSG_UNION_TRI_QUAD
1853 f->orig_face[1] = np; f->orig_face[2] = sp;
1854 #else
1855 f->orig_quad[1] = np; f->orig_quad[2] = sp;
1856 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1857 #endif
1858 /* std::cerr << "EW: " << f << std::endl;
1859 std::cerr << f->orig_face[ 0 ]->coords << std::endl;
1860 std::cerr << f->orig_face[ 1 ]->coords << std::endl;
1861 std::cerr << f->orig_face[ 2 ]->coords << std::endl;
1862 std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
1863 //right
1864 vertsvec.clear();
1865 vertsvec.push_back(np);
1866 vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
1867 vertsvec.push_back(quad_save[1]);
1868 vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
1869 if(ep)
1870 vertsvec.push_back(ep);
1871 vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
1872 vertsvec.push_back(quad_save[2]);
1873 vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
1874 vertsvec.push_back(sp);
1875 f = buildQuadFace(vertsvec, NULL);
1876 #ifdef OSG_UNION_TRI_QUAD
1877 f->orig_face[0] = np; f->orig_face[1] = quad_save[1];
1878 f->orig_face[2] = quad_save[2]; f->orig_face[3] = sp;
1879 #else
1880 f->orig_quad[0] = np; f->orig_quad[1] = quad_save[1];
1881 f->orig_quad[2] = quad_save[2]; f->orig_quad[3] = sp;
1882 f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
1883 #endif
1884 /* std::cerr << f << std::endl;
1885 std::cerr << f->orig_face[ 0 ]->coords << std::endl;
1886 std::cerr << f->orig_face[ 1 ]->coords << std::endl;
1887 std::cerr << f->orig_face[ 2 ]->coords << std::endl;
1888 std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
1889
1890 }
1891
1892 DCTPFace * DCTPMesh::buildQuadFace(std::vector<DCTPVertex *> &verts, DCTPFace *f)
1893 {
1894 if(!f)
1895 f = AddFace();
1896 // std::cerr << "buildquadface numofedges begin: " << edge_count << std::endl;
1897 std::vector<DCTPVertex *>::size_type vs = verts.size() - 1;
1898
1899 for(std::vector<DCTPVertex *>::size_type i = 0; i < vs; ++i)
1900 {
1901 if(verts[i] != verts[i + 1])
1902 {
1903 // std::cerr << verts[ i ]->coords << verts[ i + 1 ]->coords << std::endl;
1904 DCTPEdge *ne = AddEdge(verts[i], verts[i + 1], 0); //new edge
1905 f->edges.push_back(ne);
1906 f->vertices.push_back(verts[i]);
1907 ne->AddFace(f);
1908 verts[i]->AddFace(f);
1909 }
1910 }
1911
1912 if(verts[vs] != verts[0])
1913 {
1914 // std::cerr << verts[ vs ]->coords << verts[ 0 ]->coords << std::endl;
1915 DCTPEdge *ne = AddEdge(verts[vs], verts[0], 0);
1916 f->edges.push_back(ne);
1917 f->vertices.push_back(verts[vs]);
1918 ne->AddFace(f);
1919 verts[vs]->AddFace(f);
1920 }
1921 f->norm = -1.0;
1922 // std::cerr << "buildquadface numofedges end: " << edge_count << std::endl;
1923
1924 return f;
1925 }
1926
1927 DCTPEdge *DCTPMesh::getEdgeFromFace(DCTPFace *f, DCTPVertex *v1, DCTPVertex *v2)
1928 {
1929 std::vector<DCTPEdge*>::iterator ee = f->edges.end();
1930
1931 for(std::vector<DCTPEdge*>::iterator i = f->edges.begin(); i != ee; ++i)
1932 {
1933 DCTPVertex *tv1, *tv2;
1934 (*i)->getVertices(tv1, tv2);
1935 if( (DCTPVecIsEqual(v1->coords, tv1->coords) &&
1936 DCTPVecIsEqual(v2->coords, tv2->coords) ) ||
1937 (DCTPVecIsEqual(v1->coords, tv2->coords) &&
1938 DCTPVecIsEqual(v2->coords, tv1->coords) ) )
1939 return *i;
1940 }
1941
1942 std::cerr << "DCTPMesh:getEdgeFromFace: nonexistant edge requested... " << std::endl;
1943 return NULL;
1944 }
1945
1946 void DCTPMesh::sortSides(DCTPFace *f, std::vector<DCTPVertex *> * sides)
1947 {
1948 std::sort(sides[0].begin(), sides[0].end(), sortnorth() );
1949 std::sort(sides[1].begin(), sides[1].end(), sortnorth() );
1950 std::sort(sides[2].begin(), sides[2].end(), sorteast() );
1951 std::sort(sides[3].begin(), sides[3].end(), sorteast() );
1952 std::sort(sides[4].begin(), sides[4].end(), sortsouth() );
1953 std::sort(sides[5].begin(), sides[5].end(), sortsouth() );
1954 std::sort(sides[6].begin(), sides[6].end(), sortwest() );
1955 std::sort(sides[7].begin(), sides[7].end(), sortwest() );
1956
1957 }
1958
1959 void DCTPMesh::setupSides(DCTPFace *f, std::vector<DCTPVertex *> * sides, double dXRatio, double dYRatio)
1960 {
1961 #ifdef OSG_UNION_TRI_QUAD
1962 Vec3d n = f->orig_face[0]->coords + (f->orig_face[1]->coords - f->orig_face[0]->coords) * dXRatio;
1963 Vec3d s = f->orig_face[3]->coords + (f->orig_face[2]->coords - f->orig_face[3]->coords) * dXRatio;
1964 #else
1965 Vec3d n = f->orig_quad[0]->coords + (f->orig_quad[1]->coords - f->orig_quad[0]->coords) * dXRatio;
1966 Vec3d s = f->orig_quad[3]->coords + (f->orig_quad[2]->coords - f->orig_quad[3]->coords) * dXRatio;
1967 #endif
1968 Vec3d middle = s + (n - s) * dYRatio;
1969 std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
1970
1971 for(std::vector<DCTPVertex*>::iterator i = f->vertices.begin(); i != ve; ++i)
1972 {
1973 //top left and right
1974 #ifdef OSG_UNION_TRI_QUAD
1975 if(osgAbs((*i)->coords[1] - f->orig_face[0]->coords[1]) < DCTP_EPS)
1976 {
1977 //left
1978 if( ((*i)->coords[0] > f->orig_face[0]->coords[0]) &&
1979 ((*i)->coords[0] < middle[0]))
1980 #else
1981 if(osgAbs((*i)->coords[1] - f->orig_quad[0]->coords[1]) < DCTP_EPS)
1982 {
1983 //left
1984 if( ((*i)->coords[0] > f->orig_quad[0]->coords[0]) &&
1985 ((*i)->coords[0] < middle[0]))
1986 #endif
1987
1988
1989
1990 sides[0].push_back(*i);
1991 //right
1992 #ifdef OSG_UNION_TRI_QUAD
1993 else if( ((*i)->coords[0] > middle[0]) &&
1994 ((*i)->coords[0] < f->orig_face[1]->coords[0]))
1995 #else
1996 else if( ((*i)->coords[0] > middle[0]) &&
1997 ((*i)->coords[0] < f->orig_quad[1]->coords[0]))
1998 #endif
1999
2000
2001
2002 sides[1].push_back(*i);
2003 } //end if
2004 //right up and down
2005 #ifdef OSG_UNION_TRI_QUAD
2006 if(osgAbs((*i)->coords[0] - f->orig_face[1]->coords[0]) < DCTP_EPS)
2007 {
2008 //up
2009 if( ((*i)->coords[1] < f->orig_face[1]->coords[1]) &&
2010 ((*i)->coords[1] > middle[1]))
2011 #else
2012 if(osgAbs((*i)->coords[0] - f->orig_quad[1]->coords[0]) < DCTP_EPS)
2013 {
2014 //up
2015 if( ((*i)->coords[1] < f->orig_quad[1]->coords[1]) &&
2016 ((*i)->coords[1] > middle[1]))
2017 #endif
2018
2019
2020
2021 sides[2].push_back(*i);
2022 //down
2023 #ifdef OSG_UNION_TRI_QUAD
2024 else if( ((*i)->coords[1] < middle[1]) &&
2025 ((*i)->coords[1] > f->orig_face[2]->coords[1]))
2026 #else
2027 else if( ((*i)->coords[1] < middle[1]) &&
2028 ((*i)->coords[1] > f->orig_quad[2]->coords[1]))
2029 #endif
2030
2031
2032
2033 sides[3].push_back(*i);
2034 } //end if
2035 //bottom left and right
2036 #ifdef OSG_UNION_TRI_QUAD
2037 if(osgAbs((*i)->coords[1] - f->orig_face[2]->coords[1]) < DCTP_EPS)
2038 {
2039 //right
2040 if( ((*i)->coords[0] < f->orig_face[2]->coords[0]) &&
2041 ((*i)->coords[0] > middle[0]))
2042 #else
2043 if(osgAbs((*i)->coords[1] - f->orig_quad[2]->coords[1]) < DCTP_EPS)
2044 {
2045 //right
2046 if( ((*i)->coords[0] < f->orig_quad[2]->coords[0]) &&
2047 ((*i)->coords[0] > middle[0]))
2048 #endif
2049
2050
2051
2052 sides[4].push_back(*i);
2053 //left
2054 #ifdef OSG_UNION_TRI_QUAD
2055 else if( ((*i)->coords[0] < middle[0]) &&
2056 ((*i)->coords[0] > f->orig_face[3]->coords[0]))
2057 #else
2058 else if( ((*i)->coords[0] < middle[0]) &&
2059 ((*i)->coords[0] > f->orig_quad[3]->coords[0]))
2060 #endif
2061
2062
2063
2064 sides[5].push_back(*i);
2065 } //end if
2066 //left up and down
2067 #ifdef OSG_UNION_TRI_QUAD
2068 if(osgAbs((*i)->coords[0] - f->orig_face[3]->coords[0]) < DCTP_EPS)
2069 {
2070 //down
2071 if( ((*i)->coords[1] > f->orig_face[3]->coords[1]) &&
2072 ((*i)->coords[1] < middle[1]))
2073 #else
2074 if(osgAbs((*i)->coords[0] - f->orig_quad[3]->coords[0]) < DCTP_EPS)
2075 {
2076 //down
2077 if( ((*i)->coords[1] > f->orig_quad[3]->coords[1]) &&
2078 ((*i)->coords[1] < middle[1]))
2079 #endif
2080
2081
2082
2083 sides[6].push_back(*i);
2084 //up
2085 #ifdef OSG_UNION_TRI_QUAD
2086 else if( ((*i)->coords[1] > middle[1]) &&
2087 ((*i)->coords[1] < f->orig_face[0]->coords[1]))
2088 #else
2089 else if( ((*i)->coords[1] > middle[1]) &&
2090 ((*i)->coords[1] < f->orig_quad[0]->coords[1]))
2091 #endif
2092
2093
2094
2095 sides[7].push_back(*i);
2096 } //end if
2097 } //end for
2098
2099 }
2100
2101
2102
2103
2104
2105
2106 unsigned long DCTPMesh::getNumOfVertices(void)
2107 {
2108 return vertex_count;
2109 }
2110
2111 unsigned long DCTPMesh::getNumOfFaces(void)
2112 {
2113 return face_count;
2114 }
2115
2116 void DCTPMesh::reinit(void)
2117 {
2118 if(invalid)
2119 return;
2120
2121 dctpvertexset::iterator vend = vertices.end();
2122 #ifdef OSG_NO_EDGE_SET
2123 dctpedgevector::iterator eend = edges.end();
2124 #else
2125 dctpedgeset::iterator eend = edges.end();
2126 #endif
2127 dctpfacevector::iterator fend = faces.end();
2128
2129 for(dctpvertexset::iterator v = vertices.begin(); v != vend; ++v)
2130 {
2131 delete *v;
2132 }
2133
2134 #ifdef OSG_NO_EDGE_SET
2135
2136 for(dctpedgevector::iterator e = edges.begin(); e != eend; ++e)
2137 #else
2138
2139 for(dctpedgeset::iterator e = edges.begin(); e != eend; ++e)
2140 #endif
2141 {
2142 delete *e;
2143 }
2144
2145 for(dctpfacevector::iterator f = faces.begin(); f != fend; ++f)
2146 {
2147 delete *f;
2148 }
2149
2150
2151 vertices.clear();
2152 edges.clear();
2153 faces.clear();
2154 vertex_count = 0;
2155 edge_count = 0;
2156 face_count = 0;
2157 invalid = true;
2158 }
2159
2160 DCTPVertex * DCTPMesh::findVertex(const Vec3d& v)
2161 {
2162 DCTPVertex *vert = new DCTPVertex;
2163 if(!vert)
2164 return NULL;
2165 vert->coords = v;
2166 dctpvertexset::iterator vi = vertices.find(vert);
2167 delete vert;
2168 if(vi == vertices.end() )
2169 return NULL;
2170 else
2171 return (*vi);
2172 }
2173
2174 DCTPEdge *DCTPMesh::findEdge(DCTPVertex *v1, DCTPVertex *v2)
2175 {
2176 #ifdef OSG_NO_EDGE_SET
2177 DCTPEdge *pcl_edge;
2178 const unsigned int cui_edge_cnt = UInt32(v1->edges.size());
2179 unsigned int ui_edge;
2180 DCTPVertex *pcl_ev1;
2181 DCTPVertex *pcl_ev2;
2182
2183 for(ui_edge = 0; ui_edge < cui_edge_cnt; ++ui_edge)
2184 {
2185 pcl_edge = v1->edges[ui_edge];
2186 pcl_edge->getVertices(pcl_ev1, pcl_ev2);
2187 if( (v2 == pcl_ev1) || (v2 == pcl_ev2) )
2188 {
2189 return pcl_edge;
2190 }
2191 }
2192
2193 return NULL;
2194 #else
2195 DCTPEdge *e = new DCTPEdge(v1, v2, 0);
2196 dctpedgeset::iterator ei = edges.find(e);
2197 delete e;
2198 if(ei == edges.end() )
2199 return NULL;
2200 else
2201 return (*ei);
2202 #endif
2203 }
2204
2205 DCTPEdge *DCTPMesh::findEdge(const Vec3d &vc1, const Vec3d &vc2)
2206 {
2207 DCTPVertex *v1 = findVertex(vc1);
2208 if(!v1)
2209 {
2210 // std::cerr << "findEdge: vertex1 not found." << std::endl;
2211 return NULL;
2212 }
2213 DCTPVertex *v2 = findVertex(vc2);
2214 if(!v2)
2215 {
2216 // std::cerr << "findEdge: vertex2 not found." << std::endl;
2217 return NULL;
2218 }
2219 // std::cerr << "seachring for edge " << v1->id << ", " << v2->id << std::endl;
2220 return findEdge(v1, v2);
2221 }
2222
2223
2224 void DCTPMesh::removeFace(unsigned int ui_face)
2225 {
2226 unsigned int ui_loop;
2227 unsigned int ui_loop_cnt;
2228 DCTPFace *pcl_face = faces[ui_face];
2229 DCTPEdge *pcl_edge;
2230 DCTPVertex *pcl_vertex;
2231 DCTPVertex *pcl_vertex2;
2232 #ifdef OSG_NO_EDGE_SET
2233 unsigned int ui_edge;
2234 unsigned int ui_edge_cnt = UInt32(edges.size());
2235 #endif
2236
2237 // remove edges
2238 ui_loop_cnt = UInt32(pcl_face->edges.size());
2239
2240 for(ui_loop = 0; ui_loop < ui_loop_cnt; ++ui_loop)
2241 {
2242 pcl_edge = pcl_face->edges[ui_loop];
2243 pcl_edge->RemoveFace(pcl_face);
2244 if(pcl_edge->faces.size() == 0)
2245 {
2246 // no faces left on edge
2247 pcl_edge->getVertices(pcl_vertex, pcl_vertex2);
2248 pcl_vertex->RemoveEdge(pcl_edge);
2249 pcl_vertex2->RemoveEdge(pcl_edge);
2250 #ifdef OSG_NO_EDGE_SET
2251
2252 for(ui_edge = 0; ui_edge < ui_edge_cnt; ++ui_edge)
2253 {
2254 if(edges[ui_edge] == pcl_edge)
2255 {
2256 --ui_edge_cnt;
2257 edges[ui_edge] = edges[ui_edge_cnt];
2258 edges.pop_back();
2259 ui_edge = ui_edge_cnt;
2260 }
2261 }
2262
2263 #else
2264 edges.erase(pcl_edge);
2265 #endif
2266 }
2267 }
2268
2269 // remove vertices
2270 ui_loop_cnt = UInt32(pcl_face->vertices.size());
2271
2272 for(ui_loop = 0; ui_loop < ui_loop_cnt; ++ui_loop)
2273 {
2274 pcl_vertex = pcl_face->vertices[ui_loop];
2275 pcl_vertex->RemoveFace(pcl_face);
2276 if(pcl_vertex->faces.size() == 0)
2277 {
2278 vertices.erase(pcl_vertex);
2279 }
2280 }
2281
2282 // finally remove face
2283 faces[ui_face] = faces[faces.size() - 1];
2284 faces.pop_back();
2285 }