Branch data Line data Source code
1 : : /* *****************************************************************
2 : : MESQUITE -- The Mesh Quality Improvement Toolkit
3 : :
4 : : Copyright 2010 Sandia National Laboratories. Developed at the
5 : : University of Wisconsin--Madison under SNL contract number
6 : : 624796. The U.S. Government and the University of Wisconsin
7 : : retain certain rights to this software.
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 License
20 : : (lgpl.txt) 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 : : (2010) [email protected]
24 : :
25 : : ***************************************************************** */
26 : :
27 : : /** \file DomainUtil.cpp
28 : : * \brief
29 : : * \author Jason Kraftcheck
30 : : */
31 : :
32 : : #include "Mesquite.hpp"
33 : : #include "DomainUtil.hpp"
34 : : #include "MeshInterface.hpp"
35 : : #include "MsqVertex.hpp"
36 : : #include "MsqError.hpp"
37 : :
38 : : namespace MBMesquite
39 : : {
40 : : namespace DomainUtil
41 : : {
42 : :
43 : 4 : void bounding_box( const MsqVertex* coords, size_t num_coords, Vector3D& min, Vector3D& max )
44 : : {
45 : 4 : min = max = coords[0];
46 [ + + ]: 160 : for( size_t i = 1; i < num_coords; ++i )
47 : : {
48 [ + + ]: 624 : for( int j = 0; j < 3; ++j )
49 : : {
50 [ + + ]: 468 : if( coords[i][j] < min[j] ) min[j] = coords[i][j];
51 [ + + ]: 468 : if( coords[i][j] > max[j] ) max[j] = coords[i][j];
52 : : }
53 : : }
54 : 4 : }
55 : :
56 : 4 : double max_box_extent( const MsqVertex* vertex_array, size_t num_vertices )
57 : : {
58 [ + - ][ + - ]: 4 : Vector3D min, max;
59 [ + - ]: 4 : bounding_box( vertex_array, num_vertices, min, max );
60 [ + - ]: 4 : max -= min;
61 [ + - ][ + - ]: 4 : return ( max[0] >= max[1] && max[0] >= max[2] ) ? max[0] : ( max[1] >= max[2] ) ? max[1] : max[2];
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
62 : : }
63 : :
64 : 4 : void get_fixed_vertices( Mesh* mesh, const Mesh::VertexHandle* verts, size_t num_verts,
65 : : std::vector< Mesh::VertexHandle >& fixed_verts, MsqError& err )
66 : : {
67 [ + - ]: 4 : std::vector< bool > fixed( num_verts );
68 [ + - ][ + - ]: 8 : mesh->vertices_get_fixed_flag( verts, fixed, num_verts, err );MSQ_ERRRTN( err );
[ - + ][ # # ]
[ # # ][ - + ]
69 [ + + ][ + - ]: 488 : for( size_t i = 0; i < num_verts; ++i )
70 [ + - ][ + + ]: 488 : if( fixed[i] ) fixed_verts.push_back( verts[i] );
[ + - ]
71 : : }
72 : :
73 : 4 : bool non_colinear_vertices( const MsqVertex* verts, size_t num_verts, Vector3D coords_out[3], double epsilon )
74 : : {
75 : : // This function will attempt to find trhee non-colinear
76 : : // vertices from the input list. Further, it will attempt
77 : : // to select three such vertices that are relatively far
78 : : // apart so as to minimize rounding error in any calculation
79 : : // using the results of this function.
80 : :
81 : : // Non-colinear, by definition, must be at least trhee unique points.
82 [ - + ]: 4 : if( num_verts < 3 ) return false;
83 : :
84 : : // Begin with the first input vertex
85 : 4 : size_t first_idx = 0;
86 : :
87 : : // Choose the vertex furthest from the initial one
88 : 4 : size_t second_idx = 1;
89 [ + - ][ + - ]: 4 : double dist_sqr = ( verts[first_idx] - verts[second_idx] ).length_squared();
90 [ + + ]: 156 : for( size_t i = 2; i < num_verts; ++i )
91 : : {
92 [ + - ][ + - ]: 152 : double ds = ( verts[second_idx] - verts[i] ).length_squared();
93 [ + + ]: 152 : if( ds > dist_sqr )
94 : : {
95 : 4 : dist_sqr = ds;
96 : 4 : second_idx = i;
97 : : }
98 : : }
99 : : // fail if all vertices are coincident
100 [ - + ]: 4 : if( dist_sqr <= epsilon * epsilon ) return false;
101 : :
102 : : // re-select the first vertex as the one furthest from the second
103 [ + + ]: 160 : for( size_t i = 1; i < num_verts; ++i )
104 : : {
105 [ + - ][ + - ]: 156 : double ds = ( verts[second_idx] - verts[i] ).length_squared();
106 [ - + ]: 156 : if( ds > dist_sqr )
107 : : {
108 : 0 : dist_sqr = ds;
109 : 0 : first_idx = i;
110 : : }
111 : : }
112 : :
113 : : // select the third vertex as the one furthest from the line formed
114 : : // by the first two vertices
115 [ + - ]: 4 : Vector3D b = verts[first_idx];
116 [ + - ]: 4 : Vector3D m = verts[second_idx] - b;
117 [ + - ][ + - ]: 4 : Vector3D mx = m * ( 1.0 / m.length_squared() );
118 : 4 : dist_sqr = -1.0;
119 : 4 : size_t third_idx = 0;
120 [ + + ]: 164 : for( size_t i = 0; i < num_verts; ++i )
121 : : {
122 [ + - ][ + - ]: 160 : double t = mx % ( verts[i] - b );
123 [ + - ][ + - ]: 160 : double ds = ( ( b + t * m ) - verts[i] ).length_squared();
[ + - ][ + - ]
124 [ + + ]: 160 : if( ds > dist_sqr )
125 : : {
126 : 8 : third_idx = i;
127 : 8 : dist_sqr = ds;
128 : : }
129 : : }
130 : : // fail if all vertices are colinear
131 [ - + ]: 4 : if( dist_sqr <= epsilon * epsilon ) return false;
132 : :
133 [ + - ]: 4 : coords_out[0] = verts[first_idx];
134 [ + - ]: 4 : coords_out[1] = verts[second_idx];
135 [ + - ]: 4 : coords_out[2] = verts[third_idx];
136 : 4 : return true;
137 : : }
138 : :
139 : 0 : bool non_coplanar_vertices( const MsqVertex* verts, size_t num_verts, Vector3D coords_out[4], double epsilon )
140 : : {
141 : : // This function will attempt to find four non-coplanar
142 : : // vertices from the input list. Further, it will attempt
143 : : // to select four such vertices that are relatively far
144 : : // apart so as to minimize rounding error in any calculation
145 : : // using the results of this function.
146 : :
147 : : // Non-coplanar, by definition, must be at least four unique points.
148 [ # # ]: 0 : if( num_verts < 4 ) return false;
149 : :
150 : : // Get three non-colinear vertices
151 [ # # ][ # # ]: 0 : if( !non_colinear_vertices( verts, num_verts, coords_out, epsilon ) ) return false;
152 : :
153 : : // The plane of the first three vertices:
154 [ # # ][ # # ]: 0 : Vector3D norm = ( coords_out[1] - coords_out[0] ) * ( coords_out[2] - coords_out[0] );
[ # # ]
155 [ # # ][ # # ]: 0 : norm /= norm.length();
156 [ # # ]: 0 : double d = -( norm % coords_out[0] );
157 : :
158 : : // Search for the fourth vertex that is furthest from the plane
159 : : // of the first three
160 : 0 : double dist = -1.0;
161 [ # # ]: 0 : for( size_t i = 0; i < num_verts; ++i )
162 : : {
163 [ # # ]: 0 : double disti = fabs( norm % verts[i] + d );
164 [ # # ]: 0 : if( disti > dist )
165 : : {
166 : 0 : dist = disti;
167 [ # # ]: 0 : coords_out[3] = verts[i];
168 : : }
169 : : }
170 : :
171 : : // fail if all vertices are colinear
172 : 0 : return ( dist > epsilon );
173 : : }
174 : :
175 : : } // namespace DomainUtil
176 [ + - ][ + - ]: 72 : } // namespace MBMesquite
|
