?  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 / OSGGraphTraverser.cpp
blob72de9607aba05b1615beeb4ca0e09b51c170433e
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
39 #include "OSGLog.h"
40
41 #include "OSGGraphTraverser.h"
42 #include "OSGpredicates.h"
43 #include "OSGNurbsPatchSurface.h" // for defines...
44
45 OSG_USING_NAMESPACE
46
47
48 #ifdef WIN32
49 #pragma warning (disable : 985)
50 #endif
51
52 #ifdef _DEBUG
53 #ifdef WIN32
54 #undef THIS_FILE
55 static char THIS_FILE[] = __FILE__;
56 #endif
57 #endif
58
59
60 /***********************************************************/
61 void GraphTraverser::Initialize(DirectedGraph<Vec2d, unsigned char>& gg, bool
62 usedelaunaytri)
63 {
64 g = &gg;
65 unsigned int ee = UInt32(g->nodes.size());
66 globalverts.resize(ee);
67
68 for(unsigned int i = 0; i < ee; ++i)
69 globalverts[i] = g->nodes[i].nodeinfo;
70
71 usedelaunay = usedelaunaytri;
72 polys.clear();
73 }
74
75
76
77 int GraphTraverser::triangulatePolygon(DCTPivector& nodes, bool bConvex)
78 {
79 #ifdef OSG_NURBS_DEBUG
80 unsigned int i;
81 #endif
82
83 SimplePolygon actpoly;
84 actpoly.vertices = nodes;
85 actpoly.is_marked = !usedelaunay;
86 #ifdef OSG_TRIANGULATE_CONVEX
87 if(bConvex)
88 {
89 actpoly.m_bConvex = bConvex;
90 // std::cerr <<"convex bcoz of bConvex" << std::endl;
91 }
92 else if(nodes.size() > 4)
93 {
94 actpoly.m_bConvex = actpoly.isConvex(globalverts);
95 // std::cerr <<"isconvex: " <<actpoly.m_bConvex << std::endl;
96 }
97 // std::cerr << "convex: " << actpoly.m_bConvex << std::endl;
98 #endif
99
100 /*
101 if( !m_bTriangulate )
102 {
103 polys.push_back( actpoly );
104 return 0;
105 }
106 */
107 // std::cerr << "calling triangulate... polyno:" << polys.size() << std::endl;
108 // std::cerr << "calling triangulate... nodes:" << nodes.size() << std::endl;
109 std::vector<SimplePolygon> newpolys;
110
111 int err = actpoly.triangulate(globalverts, newpolys);
112 if( (err) && (usedelaunay) )
113 {
114 // delaunay didn't work, so try any triangulation
115 newpolys.clear();
116 actpoly.is_marked = 1;
117 err = actpoly.triangulate(globalverts, newpolys);
118 }
119 if(err)
120 {
121 // simple triagulation didn't work, so try to fix polygon
122 newpolys.clear();
123 actpoly.fixAndTriangulate(globalverts, newpolys);
124 }
125 polys.insert(polys.end(), newpolys.begin(), newpolys.end() );
126 #ifdef OSG_NURBS_DEBUG
127 if(err)
128 {
129 // std::cerr <<"polyno after error: " << polys.size() << std::endl;
130 //DEBUG
131 //check for duplicated vertices passed to triangulate
132 DCTPVec2dset vset;
133 std::set <int> iset;
134 std::pair<DCTPVec2dset::iterator, bool> siv;
135 std::pair<std::set <int>::iterator, bool> niv;
136 unsigned int k = nodes.size();
137 std::cerr << "nodeids:";
138
139 for(i = 0; i < k; ++i)
140 std::cerr << " " << nodes[i];
141
142 std::cerr << std::endl;
143
144 for(i = 0; i < k; ++i)
145 {
146 siv = vset.insert(globalverts[nodes[i]]);
147 if(!siv.second)
148 {
149 std::cerr << "duplicate vertex passed: " << globalverts[nodes[i]] << " i: " << i << std::endl;;
150 }
151 niv = iset.insert(nodes[i]);
152 if(!niv.second)
153 {
154 std::cerr << "duplicate vertex index passed: " << nodes[i] << " i: " << i << std::endl;
155 }
156 } // for
157
158 //DEBUG END
159
160 /* std::cerr << "Dumping info: " << std::endl;
161 std::cerr.precision( 16 );
162 std::cerr << nodes.size() << std::endl;
163 for ( unsigned int i = 0; i < nodes.size(); ++i ) {
164 std::cerr.precision( 16 );
165 std::cerr << globalverts[ nodes[ i ] ] << std::endl;
166 }
167 std::cerr << std::endl;*/
168
169 // throw GraphTraverserError( GraphTraverserError::ERR_TRIANGULATE );
170 } //if err
171 #endif /* OSG_NURBS_DEBUG */
172
173 // std::cerr << " we have now: " << polys.size() << " triangles." << std::endl;
174 // std::cerr <<"triangulate out " << std::endl;
175 return 0;
176 }
177
178 int GraphTraverser::getADirectedEdge(void)
179 {
180 static bool beenhere = false;
181 if(!beenhere)
182 beenhere = true;
183 unsigned int e = UInt32(g->edges.size());
184 bool found = false;
185
186 for(unsigned int i = 0; i < e; ++i)
187 if(g->edges[i].direction && g->edges[i].valid)
188 {
189 e = i; found = true; break;
190 }
191
192 if(!found && !beenhere)
193 {
194 std::cerr << "No trimming thingie found!" << std::endl;
195 throw GraphTraverserError(ERR_NO_TRIMMING);
196 // abort();
197 }
198 else if(!found)
199 return -1;
200 // writeBoundary( e );
201 return e;
202 }
203
204 void GraphTraverser::handleEdge(int eid, int to_nid, int &from_nid /* double& ang*/)
205 {
206 // int from_nid;
207 if(g->edges[eid].to == to_nid)
208 from_nid = g->edges[eid].from;
209 else
210 from_nid = g->edges[eid].to;
211 /* Vec2d edge_vect =
212 g->nodes[ from_nid ].nodeinfo - g->nodes[ to_nid ].nodeinfo;
213 ang = osgATan2( edge_vect[1], edge_vect[0] );
214 if ( ang < 0.0 ) ang = 2 * M_PI + ang;*/
215 if(g->edges[eid].direction)
216 g->DeleteEdge(eid);
217 else
218 g->setEdgeDirection(eid, from_nid);
219 }
220
221 int GraphTraverser::getOtherEnd(int eid, int nid)
222 {
223 DirectedEdge<unsigned char>& e = g->edges[eid];
224
225 if(e.to == nid)
226 {
227 // std::cerr << "following edge reversed " << eid << " -> " << e.from << std::endl;
228 return e.from;
229 }
230 else
231 {
232 // std::cerr << "following edge " << eid << " -> " << e.to << std::endl;
233 return e.to;
234 }
235 }
236
237 int GraphTraverser::getOutGoingEdge(int nid)
238 {
239 DCTPivector::iterator ee = g->nodes[nid].edges.end();
240
241 for(DCTPivector::iterator i = g->nodes[nid].edges.begin();
242 i != ee; ++i)
243 if(g->edges[*i].direction &&
244 g->edges[*i].from == nid)
245 return *i;
246
247 return -1;
248 }
249
250 int GraphTraverser::Traverse(void)
251 {
252
253 //first find a directed edge
254 bool b_convex;
255 int edgeID = getADirectedEdge();
256 while(edgeID != -1)
257 {
258 b_convex = (g->edges[edgeID].edgeinfo == 0);
259 int start_node = g->edges[edgeID].from;
260 int leave = -1, act_node = g->edges[edgeID].to;
261 int last_node;
262 DCTPivector node_ids;
263 node_ids.push_back(start_node);
264 node_ids.push_back(act_node);
265 while(edgeID != -1)
266 {
267 if(g->edges[edgeID].edgeinfo)
268 b_convex = false;
269 handleEdge(edgeID, act_node, last_node);
270 edgeID = getNextEdge(act_node, last_node);
271 if(edgeID == -1)
272 break;
273 // std::cerr << "edgeID: " << edgeID << " g->edges[edgeID]: " << (void*) &g->edges[ edgeID ] << std::endl;
274 // std::cerr << "g->edges[ edgeID ].direction: " << g->edges[ edgeID ].direction << std::endl;
275 if(!g->edges[edgeID].direction && leave < 0)
276 leave = act_node;
277 act_node = getOtherEnd(edgeID, act_node);
278 if(start_node == act_node) //a polygon finished
279 {
280 if(g->edges[edgeID].edgeinfo)
281 b_convex = false;
282 handleEdge(edgeID, start_node, last_node);
283 triangulatePolygon(node_ids, b_convex);
284 b_convex = true;
285 node_ids.clear();
286 // std::cerr << " act_node: " << act_node << " start_node: " << start_node << " leave: " << leave << std::endl;
287 start_node = leave; leave = -1;
288 if(start_node != -1)
289 {
290 edgeID = getOutGoingEdge(start_node);
291
292 if(edgeID != -1)
293 {
294 node_ids.push_back(start_node);
295 act_node = getOtherEnd(edgeID, start_node);
296 // std::cerr << "new actnode: " << act_node << std::endl;
297 node_ids.push_back(act_node);
298 }
299 }
300 else
301 edgeID = -1;
302 }
303 else
304 {
305 const int ci_size2 = UInt32(node_ids.size()) - 2;
306 if(ci_size2 >= 0)
307 {
308 if(node_ids[ci_size2] == act_node)
309 {
310 // went in a dead end => delete last two nodes
311 node_ids.resize(ci_size2);
312 }
313 }
314 node_ids.push_back(act_node);
315 }
316 }
317 edgeID = getADirectedEdge();
318 }
319 return 0;
320 }
321
322 int GraphTraverser::getNextEdge(const int nodeid, const int previd /*const double& in_angle*/)
323 {
324 Vec2d prev_vect = g->nodes[previd].nodeinfo;
325 Vec2d node_vect = g->nodes[nodeid].nodeinfo;
326 int en = UInt32(g->nodes[nodeid].edges.size()); //numbah o' 3dg4z
327
328 if(en == 1) //most common case, along trimming curves over faces
329 {
330 int e0 = g->nodes[nodeid].edges[0];
331 /* if ( g->edges[ e0 ].from == nodeid &&
332 g->edges[ e0 ].direction )
333 {
334 // std::cerr << "tracing along graph " << nodeid << " -> " << e0 << std::endl;
335 return e0;
336 }*/
337 if( (g->edges[e0].from == nodeid) ||
338 (g->edges[e0].to == nodeid) )
339 {
340 return e0;
341 }
342 std::cerr << "Error " << nodeid << " <-> " << g->edges[e0].from << " -> " << g->edges[e0].to << std::endl;
343 std::cerr << "Error in GraphTraverser::getNextEdge()." << std::endl;
344 throw GraphTraverserError(ERR_GETNEXTEDGE);
345 // abort();
346 }
347
348 DCTPivector eid; //edge ids
349 // dvector ea; //edge angles
350
351 DCTPivector::iterator ee = g->nodes[nodeid].edges.end();
352
353 for(DCTPivector::iterator iv = g->nodes[nodeid].edges.begin();
354 iv != ee; ++iv)
355 {
356 DirectedEdge<unsigned char>& act_edge = g->edges[*iv];
357 if( ( (!act_edge.direction) || (act_edge.to != nodeid) ) &&
358 ( (act_edge.from != nodeid) || (act_edge.to != previd) ) &&
359 ( (act_edge.to != nodeid) || (act_edge.from != previd) ) )
360 {
361 eid.push_back(*iv);
362 /* DirectedNode< Vec2d > *nptr;
363 if ( act_edge.to == nodeid )
364 nptr = &( g->nodes[ act_edge.from ] );
365 else nptr = &( g->nodes[ act_edge.to ] );
366 Vec2d v = nptr->nodeinfo - node_vect;
367 double tmp = osgATan2( v[1], v[0] );
368 if ( tmp < 0.0 ) tmp = 2 * M_PI + tmp;
369 ea.push_back( tmp );
370 std::cerr << tmp << ", ";*/
371 }
372 }
373
374 // std::cerr << std::endl;
375 //DEBUG:
376 if(/*eid.size() != ea.size() ||*/ eid.size() == 0)
377 {
378 // std::cerr << "eid.size(): " << eid.size() << " ea.size(): " << ea.size() << std::endl;
379 // throw GraphTraverserError( ERR_ZERO_SIZE );
380 return -1;
381 }
382 //END DEBUG
383 double a[2], b[2], c[2], d[2];
384 unsigned int eae = UInt32(eid.size());
385 int leftmost = 0;
386 // std::cerr << prev_vect << " -> " << node_vect << std::endl;
387 a[0] = prev_vect[0];
388 a[1] = prev_vect[1];
389 b[0] = node_vect[0];
390 b[1] = node_vect[1];
391 if(g->edges[eid[0]].to == nodeid)
392 {
393 c[0] = g->nodes[g->edges[eid[0]].from].nodeinfo[0];
394 c[1] = g->nodes[g->edges[eid[0]].from].nodeinfo[1];
395 }
396 else
397 {
398 c[0] = g->nodes[g->edges[eid[0]].to].nodeinfo[0];
399 c[1] = g->nodes[g->edges[eid[0]].to].nodeinfo[1];
400 }
401 // std::cerr << node_vect << " -> (" << c[ 0 ] << ", " << c[ 1 ] << ")" << std::endl;
402 double orient = orient2d(a, b, c);
403
404 // std::cerr << "in_angle: " << in_angle << std::endl;
405 for(unsigned int i = 1; i < eae; ++i)
406 {
407 // std::cerr << "checking edge " << i << std::endl;
408 if(g->edges[eid[i]].to == nodeid)
409 {
410 d[0] = g->nodes[g->edges[eid[i]].from].nodeinfo[0];
411 d[1] = g->nodes[g->edges[eid[i]].from].nodeinfo[1];
412 }
413 else
414 {
415 d[0] = g->nodes[g->edges[eid[i]].to].nodeinfo[0];
416 d[1] = g->nodes[g->edges[eid[i]].to].nodeinfo[1];
417 }
418 // std::cerr << node_vect << " -> (" << d[ 0 ] << ", " << d[ 1 ] << ")" << std::endl;
419 double tmp = orient2d(a, b, d);
420 // std::cerr << orient << " " << tmp << std::endl;
421 // fails, if both are = 0.0, but next test would fail too...
422 // std::cerr << orient2d( b, c, d ) << std::endl;
423 if( (orient < 0.0) || (tmp > 0.0) )
424 {
425 if( ( (tmp > 0.0) && (orient <= 0.0) ) ||
426 ( (tmp == 0.0) && (orient < 0.0) ) ||
427 (orient2d(b, c, d) > 0.0) )
428 {
429 // std::cerr << b[ 0 ] << ", " << b[ 1 ] << std::endl;
430 // std::cerr << c[ 0 ] << ", " << c[ 1 ] << std::endl;
431 // std::cerr << d[ 0 ] << ", " << d[ 1 ] << std::endl;
432 // std::cerr << "found better edge!" << std::endl;
433 orient = tmp;
434 leftmost = i;
435 c[0] = d[0];
436 c[1] = d[1];
437 // std::cerr << node_vect << " -> (" << c[ 0 ] << ", " << c[ 1 ] << ")" << std::endl;
438 }
439 }
440 /* double tmp = ea[ i ] - in_angle;
441 // std::cerr << " tmp before" << tmp << "ea[i]: " << ea[i] << std::endl;
442 if ( tmp < 0.0 ) tmp = 2 * M_PI + tmp;
443 // std::cerr << "tmp: " << tmp << "angle: " << angle << std::endl;
444 if ( tmp > angle ) { leftmost = i; angle = tmp; }*/
445 }
446
447 // if ( leftmost == -1 ) throw GraphTraverserError( GraphTraverserError::ERR_ALL_ZERO );
448 // std::cerr << "leftmost: " << leftmost << "eae: " << eae << std::endl;
449 // std::cerr << "going left on graph " << nodeid << " -> " << eid[ leftmost ] << std::endl;
450 return eid[leftmost];
451 }