Branch data Line data Source code
1 : : /*
2 : : *
3 : : *
4 : : * Copyright (C) 2004 Sandia Corporation. Under the terms of Contract DE-AC04-94AL85000
5 : : * with Sandia Corporation, the U.S. Government retains certain rights in this software.
6 : : *
7 : : * This file is part of facetbool--contact via [email protected]
8 : : *
9 : : * This library is free software; you can redistribute it and/or
10 : : * modify it under the terms of the GNU Lesser General Public
11 : : * License as published by the Free Software Foundation; either
12 : : * version 2.1 of the License, or (at your option) any later version.
13 : : *
14 : : * This library is distributed in the hope that it will be useful,
15 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 : : * Lesser General Public License for more details.
18 : : *
19 : : * You should have received a copy of the GNU Lesser General Public
20 : : * License along with this library; if not, write to the Free Software
21 : : * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 : : *
23 : : *
24 : : *
25 : : */
26 : :
27 : : #include <math.h>
28 : : #include <deque>
29 : : #include <algorithm>
30 : :
31 : : #include "FBPolyhedron.hpp"
32 : : #include "FBStructs.hpp"
33 : : #include "FBRetriangulate.hpp"
34 : : #include "CubitDefines.h"
35 : : #include "CubitMessage.hpp"
36 : : #include "CubitVector.hpp"
37 : : #include "GfxDebug.hpp"
38 : : const double BOX_CRACK = 1.e-4;
39 : :
40 [ # # ][ # # ]: 0 : FBPolyhedron::FBPolyhedron()
[ # # ][ # # ]
[ # # ]
41 : : {
42 : :
43 : 0 : polyxmin = polyymin = polyzmin = CUBIT_DBL_MAX;
44 : 0 : polyxmax = polyymax = polyzmax = -polyxmin;
45 [ # # ][ # # ]: 0 : hashobj = new IntegerHash(NUMHASHBINS,20);
46 : 0 : original_numtris = 0;
47 : :
48 : 0 : }
49 : :
50 [ # # ][ # # ]: 0 : FBPolyhedron::~FBPolyhedron()
[ # # ][ # # ]
[ # # ]
51 : : {
52 : : unsigned int i;
53 : :
54 [ # # ][ # # ]: 0 : delete hashobj;
55 [ # # ][ # # ]: 0 : delete kdtree;
56 [ # # ][ # # ]: 0 : for ( i = 0; i < verts.size(); i++ ) {
57 [ # # ][ # # ]: 0 : delete verts[i];
[ # # ]
58 : : }
59 : :
60 [ # # ][ # # ]: 0 : for ( i = 0; i < tris.size(); i++ ) {
61 [ # # ][ # # ]: 0 : delete tris[i];
[ # # ]
62 : : }
63 : :
64 [ # # ][ # # ]: 0 : for ( i = 0; i < dudded_tris.size(); i++ ) {
65 [ # # ][ # # ]: 0 : delete dudded_tris[i];
[ # # ]
66 : : }
67 : :
68 [ # # ][ # # ]: 0 : for ( i = 0; i < orphaned_edges.size(); i++ )
69 : : {
70 [ # # ][ # # ]: 0 : delete orphaned_edges[i];
[ # # ]
71 : : }
72 : 0 : }
73 : :
74 : :
75 : :
76 : :
77 : 0 : CubitStatus FBPolyhedron::makepoly(const std::vector<double>& coords,
78 : : const std::vector<int>& connections,
79 : : std::vector<int> *f_c_indices)
80 : : {
81 : : int hashvalue, parent, cubitfacetindex;
82 : : int cubitedge0index, cubitedge1index, cubitedge2index;
83 : : unsigned int i;
84 : : FB_Coord *mycoord;
85 : : FB_Triangle *mytri;
86 : : CubitStatus status;
87 [ # # ]: 0 : FSBOXVECTOR boxvector;
88 [ # # ]: 0 : std::vector<int>::iterator dpi;
89 : 0 : status = CUBIT_SUCCESS;
90 : :
91 [ # # ][ # # ]: 0 : for ( i = 0; i < coords.size(); i += 3 ) {
92 : :
93 [ # # ][ # # ]: 0 : mycoord = new FB_Coord(coords[i],coords[i+1],coords[i+2]);
[ # # ][ # # ]
[ # # ]
94 [ # # ][ # # ]: 0 : hashvalue = makeahashvaluefrom_coord(coords[i],coords[i+1],coords[i+2]);
[ # # ][ # # ]
95 [ # # ][ # # ]: 0 : hashobj->addtoHashList(hashvalue,verts.size());
96 [ # # ]: 0 : verts.push_back(mycoord);
97 : : }
98 [ # # ]: 0 : numpts = verts.size();
99 : 0 : parent = -1;
100 [ # # ]: 0 : if ( f_c_indices ){
101 [ # # ]: 0 : dpi = f_c_indices->begin();
102 : : }
103 [ # # ][ # # ]: 0 : for ( i = 0; i < connections.size(); i += 3 ) {
104 : : //as a safety check make, not only do we see if we have the
105 : : // f_c_indices vector, but make sure we don't go past the end of
106 : : // that vector.
107 [ # # ][ # # ]: 0 : if ( f_c_indices && (i<f_c_indices->size())){
[ # # ][ # # ]
108 [ # # ]: 0 : cubitfacetindex = *dpi;
109 [ # # ][ # # ]: 0 : cubitedge0index = *(dpi+1);
110 [ # # ][ # # ]: 0 : cubitedge1index = *(dpi+2);
111 [ # # ][ # # ]: 0 : cubitedge2index = *(dpi+3);
112 [ # # ]: 0 : dpi += 4;
113 : : }
114 : : else {
115 : 0 : cubitfacetindex = 0;
116 : 0 : cubitedge0index = cubitedge1index = cubitedge2index = 0;
117 : : }
118 [ # # ][ # # ]: 0 : mytri = new FB_Triangle(connections[i],connections[i+1],connections[i+2],
[ # # ]
119 : : parent,cubitfacetindex,cubitedge0index,
120 [ # # ][ # # ]: 0 : cubitedge1index,cubitedge2index);
121 [ # # ]: 0 : make_tri_boundingbox(mytri);
122 : :
123 [ # # ]: 0 : boxvector.push_back(&mytri->boundingbox); // for the KdTree
124 : :
125 [ # # ]: 0 : make_tri_plane_coeffs(mytri);
126 : :
127 [ # # ]: 0 : tris.push_back(mytri);
128 : :
129 : : }
130 : :
131 [ # # ]: 0 : numtris = original_numtris = tris.size();
132 [ # # ][ # # ]: 0 : kdtree = new KDTree();
133 [ # # ]: 0 : kdtree->makeKDTree(numtris,boxvector);
134 : :
135 [ # # ]: 0 : return status;
136 : : }
137 : :
138 : 0 : bool FBPolyhedron::boxintersection(FBPolyhedron *otherpoly)
139 : : {
140 : : double xmin, ymin, zmin, xmax, ymax, zmax;
141 : :
142 : 0 : xmin = otherpoly->polyxmin;
143 : 0 : ymin = otherpoly->polyymin;
144 : 0 : zmin = otherpoly->polyzmin;
145 : 0 : xmax = otherpoly->polyxmax;
146 : 0 : ymax = otherpoly->polyymax;
147 : 0 : zmax = otherpoly->polyzmax;
148 : :
149 [ # # ][ # # ]: 0 : if ( (polyxmin > xmax) || (polyxmax < xmin) ) return false;
150 [ # # ][ # # ]: 0 : if ( (polyymin > ymax) || (polyymax < ymin) ) return false;
151 [ # # ][ # # ]: 0 : if ( (polyzmin > zmax) || (polyzmax < zmin) ) return false;
152 : :
153 : 0 : return true;
154 : : }
155 : :
156 : 0 : int FBPolyhedron::makeahashvaluefrom_coord(double x, double y, double z)
157 : : {
158 : : double mantissasum;
159 : :
160 [ # # ]: 0 : if ( fabs(x) < 1.e-3 ) x = 0.0;
161 [ # # ]: 0 : if ( fabs(y) < 1.e-3 ) y = 0.0;
162 [ # # ]: 0 : if ( fabs(z) < 1.e-3 ) z = 0.0;
163 : 0 : mantissasum = (int)(10000.0*fabs(x) + 0.5) +
164 : 0 : (int)(10000.0*fabs(y) + 0.5) +
165 : 0 : (int)(10000.0*fabs(z) + 0.5);
166 : :
167 : 0 : return (int)(mantissasum) % NUMHASHBINS;
168 : : }
169 : :
170 : 0 : int FBPolyhedron::addavertex(double x, double y, double z)
171 : : {
172 : : int hashvalue, i, ifoundit;
173 : : int *hasharrayptr, hasharraysize;
174 : : double xval, yval, zval;
175 : : FB_Coord *mycoord, *newcoord;
176 : :
177 [ # # ]: 0 : hashvalue = makeahashvaluefrom_coord(x,y,z);
178 : :
179 [ # # ]: 0 : hasharrayptr = hashobj->getHashBin(hashvalue,&hasharraysize);
180 : :
181 : 0 : ifoundit = -1;
182 [ # # ]: 0 : for ( i = 0; i < hasharraysize; i++ ) {
183 [ # # ]: 0 : mycoord = verts[hasharrayptr[i]];
184 : 0 : xval = mycoord->coord[0];
185 : 0 : yval = mycoord->coord[1];
186 : 0 : zval = mycoord->coord[2];
187 [ # # ][ # # ]: 0 : if ( ( fabs(xval-x) < EPSILON ) &&
188 [ # # ]: 0 : ( fabs(yval-y) < EPSILON ) &&
189 : 0 : ( fabs(zval-z) < EPSILON ) ) {
190 : 0 : ifoundit = hasharrayptr[i];
191 : 0 : break;
192 : : }
193 : : }
194 [ # # ]: 0 : if ( ifoundit == -1 ) {
195 [ # # ][ # # ]: 0 : newcoord = new FB_Coord(x,y,z);
196 [ # # ]: 0 : ifoundit = verts.size();
197 [ # # ]: 0 : verts.push_back(newcoord);
198 [ # # ]: 0 : hashobj->addtoHashList(hashvalue,ifoundit);
199 : : }
200 [ # # ]: 0 : verts[ifoundit]->is_on_boundary = true;
201 : 0 : return ifoundit;
202 : :
203 : : }
204 : :
205 : 0 : void FBPolyhedron::putnewpoints(std::vector<double>& newpoints)
206 : : {
207 : : double coordinate;
208 : : unsigned int i;
209 : :
210 : : // numpts is the original number of points. Any new points were added
211 : : // onto the end of the verts vector.
212 : :
213 [ # # ][ # # ]: 0 : if ( verts.size() > numpts ) {
214 [ # # ][ # # ]: 0 : for ( i = numpts; i < verts.size(); i++ ) {
215 [ # # ]: 0 : coordinate = verts[i]->coord[0];
216 [ # # ]: 0 : newpoints.push_back(coordinate);
217 [ # # ]: 0 : coordinate = verts[i]->coord[1];
218 [ # # ]: 0 : newpoints.push_back(coordinate);
219 [ # # ]: 0 : coordinate = verts[i]->coord[2];
220 [ # # ]: 0 : newpoints.push_back(coordinate);
221 : : }
222 : : }
223 : 0 : }
224 : :
225 : 0 : void FBPolyhedron::putedges(std::vector<int>& newedges)
226 : : {
227 [ # # ]: 0 : std::deque<unsigned int> edgedeque;
228 [ # # ]: 0 : std::multimap<unsigned int,unsigned int>::iterator p3;
229 : : unsigned int startedge, startvert, edgnum;
230 [ # # ]: 0 : std::multimap<unsigned int,unsigned int>::iterator pub;
231 : : unsigned int first, second;
232 : : unsigned int i, numedgesadded;
233 : : int v0, v1;
234 : : bool foundone;
235 : :
236 [ # # ][ # # ]: 0 : for ( i = 0; i < intersection_edges.size(); i++ ) {
237 [ # # ]: 0 : v0 = intersection_edges[i]->v0;
238 [ # # ]: 0 : v1 = intersection_edges[i]->v1;
239 : :
240 : 0 : edgnum = i;
241 [ # # ][ # # ]: 0 : edgmmap.insert(std::pair<const unsigned int, unsigned int>(v0,edgnum));
242 [ # # ][ # # ]: 0 : edgmmap.insert(std::pair<const unsigned int, unsigned int>(v1,edgnum));
243 : : }
244 : 0 : numedgesadded = 0;
245 : 0 : startedge = 0;
246 : :
247 [ # # ][ # # ]: 0 : while ( numedgesadded < intersection_edges.size() ) {
248 [ # # ][ # # ]: 0 : if ( intersection_edges[startedge]->mark == true ) {
249 : 0 : startedge++;
250 : 0 : continue;
251 : : }
252 [ # # ]: 0 : startvert = v0 = intersection_edges[startedge]->v0;
253 [ # # ]: 0 : v1 = intersection_edges[startedge]->v1;
254 [ # # ]: 0 : intersection_edges[startedge]->mark = true;
255 : 0 : numedgesadded += 1;
256 [ # # ]: 0 : edgedeque.push_back(v0);
257 [ # # ]: 0 : edgedeque.push_back(v1);
258 : :
259 : 0 : foundone = true;
260 : :
261 [ # # ]: 0 : while ( foundone == true ) {
262 [ # # ]: 0 : p3 = edgmmap.find(v1);
263 [ # # ]: 0 : pub = edgmmap.upper_bound(v1);
264 : :
265 [ # # ][ # # ]: 0 : if ( p3 != edgmmap.end() ) {
[ # # ]
266 [ # # ]: 0 : do {
267 : 0 : foundone = false;
268 [ # # ]: 0 : first = p3->first;
269 [ # # ]: 0 : second = p3->second;
270 [ # # ][ # # ]: 0 : if ( (second == startedge) && (first == startvert) ) {
271 : 0 : break;
272 : : }
273 [ # # ][ # # ]: 0 : if ( (intersection_edges[second]->v0 != v0) &&
[ # # ][ # # ]
274 [ # # ]: 0 : (intersection_edges[second]->v1 != v0) ) {
275 [ # # ][ # # ]: 0 : if ( intersection_edges[second]->mark == true ) {
276 [ # # ]: 0 : p3++;
277 : 0 : continue;
278 : : }
279 [ # # ][ # # ]: 0 : if (intersection_edges[second]->v0 == v1 ) {
280 [ # # ]: 0 : v1 = intersection_edges[second]->v1;
281 [ # # ]: 0 : v0 = intersection_edges[second]->v0;
282 : : } else {
283 [ # # ]: 0 : v1 = intersection_edges[second]->v0;
284 [ # # ]: 0 : v0 = intersection_edges[second]->v1;
285 : : }
286 [ # # ]: 0 : intersection_edges[second]->mark = true;
287 : 0 : numedgesadded += 1;
288 [ # # ]: 0 : edgedeque.push_back(v1);
289 : 0 : foundone = true;
290 : : }
291 [ # # ]: 0 : p3++;
292 [ # # ][ # # ]: 0 : } while ( (p3 != pub) && (foundone == false) );
[ # # ]
293 [ # # ]: 0 : if ( foundone == false ) break;
294 : : }
295 : : } // end while ( foundone == true )
296 : 0 : v1 = startvert;
297 : 0 : foundone = true;
298 [ # # ]: 0 : while ( foundone == true ) {
299 [ # # ]: 0 : p3 = edgmmap.find(v1);
300 [ # # ]: 0 : pub = edgmmap.upper_bound(v1);
301 : :
302 [ # # ][ # # ]: 0 : if ( p3 != edgmmap.end() ) {
[ # # ]
303 [ # # ]: 0 : do {
304 : 0 : foundone = false;
305 [ # # ]: 0 : first = p3->first;
306 [ # # ]: 0 : second = p3->second;
307 [ # # ][ # # ]: 0 : if ( (intersection_edges[second]->v0 == v1) ||
[ # # ][ # # ]
308 [ # # ]: 0 : (intersection_edges[second]->v1 == v1) ) {
309 [ # # ][ # # ]: 0 : if ( intersection_edges[second]->mark == true ) {
310 [ # # ]: 0 : p3++;
311 : 0 : continue;
312 : : }
313 [ # # ][ # # ]: 0 : if (intersection_edges[second]->v0 == v1 ) {
314 [ # # ]: 0 : v1 = intersection_edges[second]->v1;
315 [ # # ]: 0 : v0 = intersection_edges[second]->v0;
316 : : } else {
317 [ # # ]: 0 : v1 = intersection_edges[second]->v0;
318 [ # # ]: 0 : v0 = intersection_edges[second]->v1;
319 : : }
320 [ # # ]: 0 : intersection_edges[second]->mark = true;
321 : 0 : numedgesadded += 1;
322 [ # # ]: 0 : edgedeque.push_front(v1);
323 : 0 : foundone = true;
324 : : }
325 [ # # ]: 0 : p3++;
326 [ # # ][ # # ]: 0 : } while ( (p3 != pub) && (foundone == false) );
[ # # ]
327 [ # # ]: 0 : if ( foundone == false ) break;
328 : : }
329 : : }
330 : :
331 [ # # ]: 0 : unsigned int size = edgedeque.size();
332 : :
333 [ # # ]: 0 : if ( size > 0 ) {
334 [ # # ]: 0 : newedges.push_back(size);
335 [ # # ]: 0 : for ( i = 0; i < size; i++ ) {
336 [ # # ][ # # ]: 0 : newedges.push_back(edgedeque[i]);
337 : : }
338 : : }
339 [ # # ]: 0 : edgedeque.clear();
340 : 0 : startedge++;
341 : : } // end while ( numedgesadded < intersection_edges.size() )
342 : :
343 [ # # ][ # # ]: 0 : newedges.push_back(0);
344 : :
345 : :
346 : 0 : }
347 : :
348 : 0 : bool FBPolyhedron::edge_exists(int v0, int v1)
349 : : {
350 : 0 : bool exists = false;
351 : : unsigned int i;
352 : :
353 [ # # ]: 0 : for ( i = 0; i < intersection_edges.size(); i++ ) {
354 [ # # ][ # # ]: 0 : if ( ( (intersection_edges[i]->v0 == v0) &&
355 [ # # ][ # # ]: 0 : (intersection_edges[i]->v1 == v1) ) ||
356 [ # # ]: 0 : ( (intersection_edges[i]->v0 == v1) &&
357 : 0 : (intersection_edges[i]->v1 == v0) ) ) {
358 : 0 : exists = true;
359 : 0 : break;
360 : : }
361 : : }
362 : :
363 : 0 : return exists;
364 : : }
365 : :
366 : 0 : CubitStatus FBPolyhedron::retriangulate(std::vector<int>& newfacets,
367 : : std::vector<int>& newfacetsindex)
368 : : {
369 : : CubitStatus status;
370 : : FBRetriangulate *retriangulater;
371 : : unsigned int i;
372 : :
373 : 0 : status = CUBIT_SUCCESS;
374 [ # # ]: 0 : for ( i = 0; i < tris.size(); i++ ) {
375 [ # # ]: 0 : if ( tris[i]->dudded == true ) {
376 : 0 : tris[i]->parent = (int)i;
377 [ # # ]: 0 : retriangulater = new FBRetriangulate(verts, tris, newfacets, newfacetsindex);
378 : 0 : status = retriangulater->retriangulate_this_tri(i, orphaned_edges);
379 [ # # ]: 0 : delete retriangulater;
380 : : }
381 : :
382 : : }
383 : :
384 : 0 : return status;
385 : : }
386 : :
387 : 0 : CubitStatus FBPolyhedron::retriangulate(std::vector<int>& newfacets)
388 : : {
389 : : CubitStatus status;
390 : : FBRetriangulate *retriangulater;
391 : : unsigned int i;
392 : :
393 : 0 : status = CUBIT_SUCCESS;
394 [ # # ]: 0 : for ( i = 0; i < tris.size(); i++ ) {
395 [ # # ]: 0 : if ( tris[i]->dudded == true ) {
396 [ # # ]: 0 : tris[i]->parent = (int)i;
397 [ # # ][ # # ]: 0 : retriangulater = new FBRetriangulate(verts, tris, newfacets);
398 [ # # ]: 0 : status = retriangulater->retriangulate_this_tri(i, orphaned_edges);
399 [ # # ]: 0 : std::vector<FB_Edge*>::iterator iter;
400 [ # # ][ # # ]: 0 : delete retriangulater;
401 : : }
402 : :
403 : : }
404 : :
405 : 0 : return status;
406 : : }
407 : :
408 : 0 : bool FBPolyhedron::edge_exists_in_tri(FB_Triangle& tri, int v0, int v1)
409 : : {
410 : : FB_Edge *edge;
411 [ # # ]: 0 : std::vector<FB_Edge*>::iterator dp;
412 : :
413 [ # # ]: 0 : dp = tri.edge_list.begin();
414 [ # # ][ # # ]: 0 : while ( dp != tri.edge_list.end() ) {
[ # # ]
415 [ # # ]: 0 : edge = *dp;
416 [ # # ][ # # ]: 0 : if ( ( ( (edge->v0) == v0 ) && ( (edge->v1) == v1 ) ) ||
[ # # ]
417 [ # # ]: 0 : ( ( (edge->v0) == v1 ) && ( (edge->v1) == v0 ) ) )
418 : 0 : return true;
419 [ # # ]: 0 : dp++;
420 : : }
421 : :
422 : 0 : return false;
423 : : }
424 : :
425 : 0 : void FBPolyhedron::add_new_triangle_data()
426 : : {
427 : : unsigned int i;
428 : : FB_Triangle *tri;
429 : :
430 [ # # ]: 0 : for ( i = original_numtris; i < tris.size(); i++ ) {
431 : :
432 : 0 : tri = tris[i];
433 : : // make the bounding box
434 : 0 : make_tri_boundingbox(tri);
435 : : // make the plane coefficients
436 : 0 : make_tri_plane_coeffs(tri);
437 : : }
438 : :
439 : 0 : }
440 : :
441 : 0 : void FBPolyhedron::make_tri_plane_coeffs(FB_Triangle *tri)
442 : : {
443 : : FB_Coord *mycoord;
444 : : double x1, x2, x3, y1, y2, y3, z1, z2, z3, e1x, e1y, e1z, e2x, e2y, e2z;
445 : : double a, b, c, d, dtemp;
446 : :
447 : 0 : mycoord = verts[tri->v0];
448 : 0 : x1 = mycoord->coord[0];
449 : 0 : y1 = mycoord->coord[1];
450 : 0 : z1 = mycoord->coord[2];
451 : 0 : mycoord = verts[tri->v1];
452 : 0 : x2 = mycoord->coord[0];
453 : 0 : y2 = mycoord->coord[1];
454 : 0 : z2 = mycoord->coord[2];
455 : 0 : mycoord = verts[tri->v2];
456 : 0 : x3 = mycoord->coord[0];
457 : 0 : y3 = mycoord->coord[1];
458 : 0 : z3 = mycoord->coord[2];
459 : 0 : e1x = x1 - x2; e1y = y1 - y2; e1z = z1 - z2;
460 : 0 : e2x = x3 - x2; e2y = y3 - y2; e2z = z3 - z2;
461 : 0 : a = e1z*e2y - e2z*e1y;
462 : 0 : b = e1x*e2z - e2x*e1z;
463 : 0 : c = e1y*e2x - e2y*e1x;
464 : 0 : dtemp = sqrt(a*a + b*b + c*c);
465 [ # # ]: 0 : if ( dtemp > EPSILON2 ) {
466 : 0 : a /= dtemp;
467 : 0 : b /= dtemp;
468 : 0 : c /= dtemp;
469 : : } else {
470 [ # # ][ # # ]: 0 : PRINT_WARNING("small-area triangle\n");
471 : : }
472 : 0 : d = -(a*x1 + b*y1 + c*z1);
473 : 0 : tri->a = a; tri->b = b; tri->c = c; tri->d = d;
474 : :
475 : 0 : }
476 : :
477 : 0 : void FBPolyhedron::make_tri_boundingbox(FB_Triangle *tri)
478 : : {
479 : : double xmin, ymin, zmin, xmax, ymax, zmax;
480 : : int j;
481 : : int connections[3];
482 : : FB_Coord *mycoord;
483 : :
484 : 0 : xmin = ymin = zmin = CUBIT_DBL_MAX;
485 : 0 : xmax = ymax = zmax = -xmin;
486 : 0 : connections[0] = tri->v0; connections[1] = tri->v1; connections[2] = tri->v2;
487 [ # # ]: 0 : for ( j = 0; j < 3; j++ ) { // make the bounding box
488 [ # # ]: 0 : mycoord = verts[connections[j]];
489 [ # # ]: 0 : xmin = ( xmin < mycoord->coord[0] ) ? xmin : mycoord->coord[0];
490 [ # # ]: 0 : xmax = ( xmax > mycoord->coord[0] ) ? xmax : mycoord->coord[0];
491 [ # # ]: 0 : ymin = ( ymin < mycoord->coord[1] ) ? ymin : mycoord->coord[1];
492 [ # # ]: 0 : ymax = ( ymax > mycoord->coord[1] ) ? ymax : mycoord->coord[1];
493 [ # # ]: 0 : zmin = ( zmin < mycoord->coord[2] ) ? zmin : mycoord->coord[2];
494 [ # # ]: 0 : zmax = ( zmax > mycoord->coord[2] ) ? zmax : mycoord->coord[2];
495 : : }
496 [ # # ]: 0 : if ( (xmax - xmin) < BOX_CRACK ) {
497 : 0 : xmax += BOX_CRACK; xmin -= BOX_CRACK;
498 : : }
499 [ # # ]: 0 : if ( (ymax - ymin) < BOX_CRACK ) {
500 : 0 : ymax += BOX_CRACK; ymin -= BOX_CRACK;
501 : : }
502 [ # # ]: 0 : if ( (zmax - zmin) < BOX_CRACK ) {
503 : 0 : zmax += BOX_CRACK; zmin -= BOX_CRACK;
504 : : }
505 : 0 : tri->boundingbox.xmin = xmin; tri->boundingbox.xmax = xmax;
506 : 0 : tri->boundingbox.ymin = ymin; tri->boundingbox.ymax = ymax;
507 : 0 : tri->boundingbox.zmin = zmin; tri->boundingbox.zmax = zmax;
508 : :
509 : : // Update the object's bounding box
510 [ # # ]: 0 : polyxmin = ( polyxmin < xmin ) ? polyxmin : xmin;
511 [ # # ]: 0 : polyymin = ( polyymin < ymin ) ? polyymin : ymin;
512 [ # # ]: 0 : polyzmin = ( polyzmin < zmin ) ? polyzmin : zmin;
513 [ # # ]: 0 : polyxmax = ( polyxmax > xmax ) ? polyxmax : xmax;
514 [ # # ]: 0 : polyymax = ( polyymax > ymax ) ? polyymax : ymax;
515 [ # # ]: 0 : polyzmax = ( polyzmax > zmax ) ? polyzmax : zmax;
516 : :
517 : 0 : }
518 : :
519 : 0 : void FBPolyhedron::removeduddedtriangles() // Compacts the tris vector
520 : : {
521 : : unsigned int i;
522 : : int j;
523 : :
524 : 0 : j = 0;
525 [ # # ]: 0 : for ( i = 0; i < tris.size(); i++ ) {
526 [ # # ]: 0 : if ( tris[i]->dudded == true )
527 : : {
528 : 0 : dudded_tris.push_back(tris[i]);
529 : : }
530 : : else
531 : : {
532 : 0 : tris[j] = tris[i];
533 : 0 : j++;
534 : : }
535 : : }
536 : 0 : tris.resize(j);
537 : 0 : }
538 : :
539 : : //find the largest and smallest angles in this triangle
540 : 0 : bool FBPolyhedron::min_max_angles_in_fb_triangle(FB_Triangle *triangle,
541 : : double& min_angle,
542 : : double& max_angle)
543 : : {
544 [ # # ]: 0 : CubitVector vert_0(verts[triangle->v0]->coord[0],
545 [ # # ]: 0 : verts[triangle->v0]->coord[1],
546 [ # # ][ # # ]: 0 : verts[triangle->v0]->coord[2]);
547 [ # # ]: 0 : CubitVector vert_1(verts[triangle->v1]->coord[0],
548 [ # # ]: 0 : verts[triangle->v1]->coord[1],
549 [ # # ][ # # ]: 0 : verts[triangle->v1]->coord[2]);
550 [ # # ]: 0 : CubitVector vert_2(verts[triangle->v2]->coord[0],
551 [ # # ]: 0 : verts[triangle->v2]->coord[1],
552 [ # # ][ # # ]: 0 : verts[triangle->v2]->coord[2]);
553 [ # # ][ # # ]: 0 : CubitVector sides[3];
554 [ # # ][ # # ]: 0 : sides[0] = vert_1 - vert_0;
555 [ # # ][ # # ]: 0 : sides[1] = vert_2 - vert_1;
556 [ # # ][ # # ]: 0 : sides[2]= vert_0 - vert_2;
557 [ # # ][ # # ]: 0 : if(sides[0].length_squared() < EPSILON ||
[ # # ]
558 [ # # ][ # # ]: 0 : sides[1].length_squared() < EPSILON ||
[ # # ]
559 [ # # ]: 0 : sides[2].length_squared() < EPSILON ){
560 : 0 : min_angle =0.0;
561 : 0 : max_angle =180.0;
562 : 0 : return false;
563 : : }
564 : : double curr_angle;
565 [ # # ][ # # ]: 0 : min_angle = sides[1].interior_angle(-sides[0]);
566 : 0 : max_angle = min_angle;
567 [ # # ][ # # ]: 0 : curr_angle = sides[2].interior_angle(-sides[1]);
568 [ # # ]: 0 : if(curr_angle<min_angle){
569 : 0 : min_angle=curr_angle;
570 : : }
571 [ # # ]: 0 : if(curr_angle>max_angle){
572 : 0 : min_angle=curr_angle;
573 : : }
574 [ # # ][ # # ]: 0 : curr_angle = sides[0].interior_angle(-sides[2]);
575 [ # # ]: 0 : if(curr_angle<min_angle){
576 : 0 : min_angle=curr_angle;
577 : : }
578 [ # # ]: 0 : if(curr_angle>max_angle){
579 : 0 : min_angle=curr_angle;
580 : : }
581 : 0 : return true;
582 : :
583 : : }
584 : : //draw the "boundary edges" of the polyhedron.
585 : 0 : void FBPolyhedron::debug_draw_boundary_edges(int color)
586 : : {
587 : : unsigned int i;
588 : 0 : FB_Triangle* triangle=NULL;
589 [ # # ]: 0 : for(i = 0; i<tris.size(); i++){
590 [ # # ]: 0 : if(!tris[i]->dudded){
591 [ # # ]: 0 : triangle = tris[i];
592 : 0 : unsigned int counter = 0;
593 [ # # ]: 0 : CubitVector vert_0(verts[triangle->v0]->coord[0],
594 [ # # ]: 0 : verts[triangle->v0]->coord[1],
595 [ # # ][ # # ]: 0 : verts[triangle->v0]->coord[2]);
596 [ # # ]: 0 : CubitVector vert_1(verts[triangle->v1]->coord[0],
597 [ # # ]: 0 : verts[triangle->v1]->coord[1],
598 [ # # ][ # # ]: 0 : verts[triangle->v1]->coord[2]);
599 [ # # ]: 0 : CubitVector vert_2(verts[triangle->v2]->coord[0],
600 [ # # ]: 0 : verts[triangle->v2]->coord[1],
601 [ # # ][ # # ]: 0 : verts[triangle->v2]->coord[2]);
602 [ # # ]: 0 : if(triangle->cubitedge0index){
603 : 0 : counter++;
604 [ # # ]: 0 : GfxDebug::draw_line(vert_0, vert_1, color);
605 : : }
606 [ # # ]: 0 : if(triangle->cubitedge1index){
607 : 0 : counter++;
608 [ # # ]: 0 : GfxDebug::draw_line(vert_1, vert_2, color);
609 : : }
610 [ # # ]: 0 : if(triangle->cubitedge2index){
611 : 0 : counter++;
612 [ # # ]: 0 : GfxDebug::draw_line(vert_2, vert_0, color);
613 : : }
614 [ # # ][ # # ]: 0 : if(counter != triangle->edge_list.size()){
615 [ # # ][ # # ]: 0 : PRINT_WARNING("Possible debug problem.\n");
[ # # ][ # # ]
616 : : }
617 : : }
618 : : }
619 : 0 : }
620 : :
621 : : //draw a single triangle
622 : 0 : void FBPolyhedron::debug_draw_fb_triangle(FB_Triangle *triangle)
623 : : {
624 [ # # ]: 0 : CubitVector vert_0(verts[triangle->v0]->coord[0],
625 [ # # ]: 0 : verts[triangle->v0]->coord[1],
626 [ # # ][ # # ]: 0 : verts[triangle->v0]->coord[2]);
627 [ # # ]: 0 : CubitVector vert_1(verts[triangle->v1]->coord[0],
628 [ # # ]: 0 : verts[triangle->v1]->coord[1],
629 [ # # ][ # # ]: 0 : verts[triangle->v1]->coord[2]);
630 [ # # ]: 0 : CubitVector vert_2(verts[triangle->v2]->coord[0],
631 [ # # ]: 0 : verts[triangle->v2]->coord[1],
632 [ # # ][ # # ]: 0 : verts[triangle->v2]->coord[2]);
633 [ # # ]: 0 : GfxDebug::draw_point(vert_0, CUBIT_RED_INDEX);
634 [ # # ]: 0 : GfxDebug::draw_point(vert_1, CUBIT_RED_INDEX);
635 [ # # ]: 0 : GfxDebug::draw_point(vert_2, CUBIT_RED_INDEX);
636 [ # # ]: 0 : GfxDebug::draw_line(vert_0, vert_1, CUBIT_BLUE_INDEX);
637 [ # # ]: 0 : GfxDebug::draw_line(vert_1, vert_2, CUBIT_BLUE_INDEX);
638 [ # # ]: 0 : GfxDebug::draw_line(vert_2, vert_0, CUBIT_BLUE_INDEX);
639 : 0 : int draw_normal = 1;
640 [ # # ]: 0 : if(draw_normal){
641 [ # # ][ # # ]: 0 : CubitVector center_pos = (vert_0+vert_1+vert_2)/3.0;
[ # # ]
642 [ # # ][ # # ]: 0 : CubitVector opp_pos = center_pos + (vert_1-vert_0)*(vert_2-vert_0);
[ # # ][ # # ]
643 [ # # ]: 0 : GfxDebug::draw_line(center_pos, opp_pos, CUBIT_WHITE_INDEX);
644 : : }
645 : 0 : }
646 : :
647 : : //get the largest and smallest angles in the polyhedron. That is,
648 : : //find the largest angle in any triangle in the polyhedron and find
649 : : //the smallest angle in any triangle in the polyhedron.
650 : 0 : bool FBPolyhedron::min_max_angles_in_polyhedron(double& min_angle,
651 : : double& max_angle)
652 : : {
653 : : double curr_min;
654 : : double curr_max;
655 [ # # ][ # # ]: 0 : if(tris.size() < 1){
656 : 0 : min_angle = 0.0;
657 : 0 : max_angle = 180.0;
658 : 0 : return false;
659 : : }
660 [ # # ][ # # ]: 0 : min_max_angles_in_fb_triangle(tris[0], min_angle, max_angle);
661 : : unsigned int i;
662 [ # # ][ # # ]: 0 : for(i = 1; i<tris.size(); i++){
663 [ # # ][ # # ]: 0 : if(!min_max_angles_in_fb_triangle(tris[i], curr_min, curr_max)){
[ # # ]
664 : 0 : return false;
665 : : }
666 [ # # ]: 0 : if(curr_min<min_angle){
667 : 0 : min_angle=curr_min;
668 : : }
669 [ # # ]: 0 : if(curr_max>max_angle){
670 : 0 : max_angle=curr_max;
671 : : }
672 : : }
673 : 0 : return true;
674 [ + - ][ + - ]: 6540 : }
675 : :
676 : : #ifdef KEEP_BOYD10_KEEP
677 : : //function that attempts to remove small angles be flipping edges...
678 : : bool FBPolyhedron::remove_small_angles_in_triangle_range(int lower_index,
679 : : int upper_index)
680 : : {
681 : : //we currently only handle obtuse, degenerate triangles...
682 : : //see if the triangle falls in this range
683 : : int mydebug = 0;
684 : : const double min_angle_in_degrees = 1;
685 : : const double max_angle_in_degrees = 120;
686 : : int j;
687 : : for(j=lower_index;j<upper_index;j++){
688 : : //this triangle has an extremely small angl
689 : : double min_angle, max_angle;
690 : : if(!min_max_angles_in_fb_triangle(tris[j], min_angle, max_angle))
691 : : return false;
692 : :
693 : : if(min_angle < min_angle_in_degrees && max_angle>max_angle_in_degrees)
694 : : {
695 : : //PRINT_INFO("Found a degenerate, obtuse triangle.\n");
696 : : //two vertices on longest edge of degenerate triangle
697 : : int longest_edge_v1 = 0;
698 : : int longest_edge_v2 = 0;
699 : : //all vertices on triangle
700 : : int v_indices[3];
701 : : v_indices[0]=tris[j]->v0;
702 : : v_indices[1]=tris[j]->v1;
703 : : v_indices[2]=tris[j]->v2;
704 : : double longest_length = -1.0;
705 : : double temp_length = 0.0;
706 : : int k=0;
707 : : //find the longest edge
708 : : for(k=0;k<3;k++){
709 : : CubitVector v1(verts[v_indices[k]]->coord[0],
710 : : verts[v_indices[k]]->coord[1],
711 : : verts[v_indices[k]]->coord[2]);
712 : : CubitVector v2(verts[v_indices[(k+1)%3]]->coord[0],
713 : : verts[v_indices[(k+1)%3]]->coord[1],
714 : : verts[v_indices[(k+1)%3]]->coord[2]);
715 : : temp_length = (v1-v2).length_squared();
716 : :
717 : : if(temp_length>longest_length){
718 : : longest_length = temp_length;
719 : : longest_edge_v1 = v_indices[k];
720 : : longest_edge_v2 = v_indices[(k+1)%3];
721 : : }
722 : : }
723 : : //look for the other triangle in this range that shares this edge
724 : : int found_it = 0;
725 : : k=0;
726 : : while (!found_it && k < (int)tris.size()){
727 : : if(k!=j && tris[k]->are_fb_coords_in_fb_triangle(
728 : : longest_edge_v1,longest_edge_v2)){
729 : : found_it=1;
730 : : }
731 : : if(!found_it){
732 : : k++;
733 : : }
734 : : }
735 : : //we have found the two triangles adjacent to the longest
736 : : //edge of the degenerate tri.
737 : : if(!found_it){
738 : : //PRINT_WARNING("Didn't find the other triangle\n");
739 : : return false;
740 : : }
741 : : // PRINT_INFO("Found it... j = %i, k = %i\n",j,k);
742 : : // PRINT_INFO("edge lists sizes %i, %i\n",tris[j]->edge_list.size(),tris[k]->edge_list.size());
743 : : double min_angle_before_swap;
744 : : min_max_angles_in_fb_triangle(tris[j], min_angle_before_swap,
745 : : max_angle);
746 : : // PRINT_INFO("Inititial tri j angle = %f\n",min_angle);
747 : : min_max_angles_in_fb_triangle(tris[k], min_angle, max_angle);
748 : : if(min_angle<min_angle_before_swap){
749 : : min_angle_before_swap = min_angle;
750 : : }
751 : : if(mydebug){
752 : : PRINT_INFO("Inititial tri k angle = %f\n",min_angle);
753 : : GfxDebug::clear();
754 : : debug_draw_fb_triangle(tris[j]);
755 : : debug_draw_fb_triangle(tris[k]);
756 : : GfxDebug::mouse_xforms();
757 : : }
758 : : //now do a swap to remove the longest edge...
759 : : int other_vj;
760 : : int other_vk;
761 : : int index_for_j = 0;
762 : : int index_for_k =0;
763 : : int old_value_for_j=0;
764 : : int old_value_for_k=0;
765 : : if(tris[j]->v0 == longest_edge_v1 ||
766 : : tris[j]->v0 == longest_edge_v2 ){
767 : : if(tris[j]->v1 == longest_edge_v1 ||
768 : : tris[j]->v1 == longest_edge_v2){
769 : : other_vj =tris[j]->v2;
770 : : index_for_j=1;
771 : : }
772 : : else{
773 : : other_vj =tris[j]->v1;
774 : : index_for_j=0;
775 : : }
776 : : }
777 : : else{
778 : : other_vj =tris[j]->v0;
779 : : index_for_j=2;
780 : : }
781 : : if(tris[k]->v0 == longest_edge_v1 ||
782 : : tris[k]->v0 == longest_edge_v2 ){
783 : : if(tris[k]->v1 == longest_edge_v1 ||
784 : : tris[k]->v1 == longest_edge_v2){
785 : : other_vk = tris[k]->v2;
786 : : old_value_for_k=tris[k]->v1;
787 : : tris[k]->v1=other_vj;
788 : : index_for_k = 1;
789 : : }
790 : : else{
791 : : other_vk = tris[k]->v1;
792 : : old_value_for_k=tris[k]->v0;
793 : : tris[k]->v0=other_vj;
794 : : index_for_k=0;
795 : : }
796 : : }
797 : : else{
798 : : other_vk = tris[k]->v0;
799 : : old_value_for_k=tris[k]->v2;
800 : : tris[k]->v2=other_vj;
801 : : index_for_k=2;
802 : : }
803 : : if(index_for_j == 0){
804 : : old_value_for_j=tris[j]->v0;
805 : : tris[j]->v0=other_vk;
806 : : }
807 : : else if(index_for_j == 1){
808 : : old_value_for_j=tris[j]->v1;
809 : : tris[j]->v1=other_vk;
810 : : }
811 : : else{
812 : : old_value_for_j=tris[j]->v2;
813 : : tris[j]->v2=other_vk;
814 : : }
815 : : double min_angle_after_swap;
816 : : min_max_angles_in_fb_triangle(tris[j], min_angle_after_swap,
817 : : max_angle);
818 : : // PRINT_INFO("Modified tri j angle = %f\n",min_angle);
819 : : min_max_angles_in_fb_triangle(tris[k], min_angle, max_angle);
820 : : if(min_angle<min_angle_after_swap){
821 : : min_angle_after_swap=min_angle;
822 : : }
823 : : if(min_angle_after_swap < min_angle_before_swap){
824 : : // PRINT_WARNING("Swap was unsuccessful in removing bad angle.");
825 : : if(index_for_j == 0){
826 : : tris[j]->v0=old_value_for_j;
827 : : }
828 : : else if(index_for_j == 1){
829 : :
830 : : tris[j]->v1=old_value_for_j;
831 : : }
832 : : else{
833 : : tris[j]->v2=old_value_for_j;
834 : : }
835 : : if(index_for_k == 0){
836 : : tris[k]->v0=old_value_for_k;
837 : : }
838 : : else if(index_for_k == 1){
839 : :
840 : : tris[k]->v1=old_value_for_k;
841 : : }
842 : : else{
843 : : tris[k]->v2=old_value_for_k;
844 : : }
845 : : }
846 : : if(mydebug){
847 : : PRINT_INFO("Modified tri k angle = %f\n",min_angle);
848 : : GfxDebug::clear();
849 : : debug_draw_fb_triangle(tris[j]);
850 : : debug_draw_fb_triangle(tris[k]);
851 : : GfxDebug::mouse_xforms();
852 : : }
853 : : }
854 : : }
855 : : return true;
856 : :
857 : : }
858 : : #endif
859 : :
860 : :
|
