1 /* Copyright (c) 2011 Khaled Mamou (kmamou at gmail dot com)
2 All rights reserved.
3
4
5 Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
6
7 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
8
9 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
10
11 3. The names of the contributors may not be used to endorse or promote products derived from this software without specific prior written permission.
12
13 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
14 */
15
16 #ifndef _CRT_SECURE_NO_WARNINGS
17 #define _CRT_SECURE_NO_WARNINGS
18 #endif
19
20 #include "btConvexHullComputer.h"
21 #include "vhacdMesh.h"
22 #include "FloatMath.h"
23 #include <fstream>
24 #include <iosfwd>
25 #include <iostream>
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string>
29
30 namespace VHACD {
Mesh()31 Mesh::Mesh()
32 {
33 m_diag = 1.0;
34 }
~Mesh()35 Mesh::~Mesh()
36 {
37 }
38
ComputeCenter(void)39 Vec3<double>& Mesh::ComputeCenter(void)
40 {
41 const size_t nV = GetNPoints();
42 if (nV)
43 {
44 double center[3];
45 uint32_t pcount = uint32_t(GetNPoints());
46 const double *points = GetPoints();
47 uint32_t tcount = uint32_t(GetNTriangles());
48 const uint32_t *indices = (const uint32_t *)GetTriangles();
49 FLOAT_MATH::fm_computeCentroid(pcount, points, tcount, indices, center);
50 m_center.X() = center[0];
51 m_center.Y() = center[1];
52 m_center.Z() = center[2];
53 m_minBB = GetPoint(0);
54 m_maxBB = GetPoint(0);
55 for (size_t v = 1; v < nV; v++)
56 {
57 Vec3<double> p = GetPoint(v);
58 if (p.X() < m_minBB.X())
59 {
60 m_minBB.X() = p.X();
61 }
62 if (p.Y() < m_minBB.Y())
63 {
64 m_minBB.Y() = p.Y();
65 }
66 if (p.Z() < m_minBB.Z())
67 {
68 m_minBB.Z() = p.Z();
69 }
70 if (p.X() > m_maxBB.X())
71 {
72 m_maxBB.X() = p.X();
73 }
74 if (p.Y() > m_maxBB.Y())
75 {
76 m_maxBB.Y() = p.Y();
77 }
78 if (p.Z() > m_maxBB.Z())
79 {
80 m_maxBB.Z() = p.Z();
81 }
82 }
83 }
84 return m_center;
85 }
86
ComputeVolume() const87 double Mesh::ComputeVolume() const
88 {
89 const size_t nV = GetNPoints();
90 const size_t nT = GetNTriangles();
91 if (nV == 0 || nT == 0) {
92 return 0.0;
93 }
94
95 Vec3<double> bary(0.0, 0.0, 0.0);
96 for (size_t v = 0; v < nV; v++) {
97 bary += GetPoint(v);
98 }
99 bary /= static_cast<double>(nV);
100
101 Vec3<double> ver0, ver1, ver2;
102 double totalVolume = 0.0;
103 for (int32_t t = 0; t < int32_t(nT); t++) {
104 const Vec3<int32_t>& tri = GetTriangle(t);
105 ver0 = GetPoint(tri[0]);
106 ver1 = GetPoint(tri[1]);
107 ver2 = GetPoint(tri[2]);
108 totalVolume += ComputeVolume4(ver0, ver1, ver2, bary);
109 }
110 return totalVolume / 6.0;
111 }
112
ComputeConvexHull(const double * const pts,const size_t nPts)113 void Mesh::ComputeConvexHull(const double* const pts,
114 const size_t nPts)
115 {
116 ResizePoints(0);
117 ResizeTriangles(0);
118 btConvexHullComputer ch;
119 ch.compute(pts, 3 * sizeof(double), (int32_t)nPts, -1.0, -1.0);
120 for (int32_t v = 0; v < ch.vertices.size(); v++) {
121 AddPoint(Vec3<double>(ch.vertices[v].getX(), ch.vertices[v].getY(), ch.vertices[v].getZ()));
122 }
123 const int32_t nt = ch.faces.size();
124 for (int32_t t = 0; t < nt; ++t) {
125 const btConvexHullComputer::Edge* sourceEdge = &(ch.edges[ch.faces[t]]);
126 int32_t a = sourceEdge->getSourceVertex();
127 int32_t b = sourceEdge->getTargetVertex();
128 const btConvexHullComputer::Edge* edge = sourceEdge->getNextEdgeOfFace();
129 int32_t c = edge->getTargetVertex();
130 while (c != a) {
131 AddTriangle(Vec3<int32_t>(a, b, c));
132 edge = edge->getNextEdgeOfFace();
133 b = c;
134 c = edge->getTargetVertex();
135 }
136 }
137 }
Clip(const Plane & plane,SArray<Vec3<double>> & positivePart,SArray<Vec3<double>> & negativePart) const138 void Mesh::Clip(const Plane& plane,
139 SArray<Vec3<double> >& positivePart,
140 SArray<Vec3<double> >& negativePart) const
141 {
142 const size_t nV = GetNPoints();
143 if (nV == 0) {
144 return;
145 }
146 double d;
147 for (size_t v = 0; v < nV; v++) {
148 const Vec3<double>& pt = GetPoint(v);
149 d = plane.m_a * pt[0] + plane.m_b * pt[1] + plane.m_c * pt[2] + plane.m_d;
150 if (d > 0.0) {
151 positivePart.PushBack(pt);
152 }
153 else if (d < 0.0) {
154 negativePart.PushBack(pt);
155 }
156 else {
157 positivePart.PushBack(pt);
158 negativePart.PushBack(pt);
159 }
160 }
161 }
IsInside(const Vec3<double> & pt) const162 bool Mesh::IsInside(const Vec3<double>& pt) const
163 {
164 const size_t nV = GetNPoints();
165 const size_t nT = GetNTriangles();
166 if (nV == 0 || nT == 0) {
167 return false;
168 }
169 Vec3<double> ver0, ver1, ver2;
170 double volume;
171 for (int32_t t = 0; t < int32_t(nT); t++) {
172 const Vec3<int32_t>& tri = GetTriangle(t);
173 ver0 = GetPoint(tri[0]);
174 ver1 = GetPoint(tri[1]);
175 ver2 = GetPoint(tri[2]);
176 volume = ComputeVolume4(ver0, ver1, ver2, pt);
177 if (volume < 0.0) {
178 return false;
179 }
180 }
181 return true;
182 }
ComputeDiagBB()183 double Mesh::ComputeDiagBB()
184 {
185 const size_t nPoints = GetNPoints();
186 if (nPoints == 0)
187 return 0.0;
188 Vec3<double> minBB = m_points[0];
189 Vec3<double> maxBB = m_points[0];
190 double x, y, z;
191 for (size_t v = 1; v < nPoints; v++) {
192 x = m_points[v][0];
193 y = m_points[v][1];
194 z = m_points[v][2];
195 if (x < minBB[0])
196 minBB[0] = x;
197 else if (x > maxBB[0])
198 maxBB[0] = x;
199 if (y < minBB[1])
200 minBB[1] = y;
201 else if (y > maxBB[1])
202 maxBB[1] = y;
203 if (z < minBB[2])
204 minBB[2] = z;
205 else if (z > maxBB[2])
206 maxBB[2] = z;
207 }
208 return (m_diag = (maxBB - minBB).GetNorm());
209 }
210
211 #ifdef VHACD_DEBUG_MESH
SaveVRML2(const std::string & fileName) const212 bool Mesh::SaveVRML2(const std::string& fileName) const
213 {
214 std::ofstream fout(fileName.c_str());
215 if (fout.is_open()) {
216 const Material material;
217
218 if (SaveVRML2(fout, material)) {
219 fout.close();
220 return true;
221 }
222 return false;
223 }
224 return false;
225 }
SaveVRML2(std::ofstream & fout,const Material & material) const226 bool Mesh::SaveVRML2(std::ofstream& fout, const Material& material) const
227 {
228 if (fout.is_open()) {
229 fout.setf(std::ios::fixed, std::ios::floatfield);
230 fout.setf(std::ios::showpoint);
231 fout.precision(6);
232 size_t nV = m_points.Size();
233 size_t nT = m_triangles.Size();
234 fout << "#VRML V2.0 utf8" << std::endl;
235 fout << "" << std::endl;
236 fout << "# Vertices: " << nV << std::endl;
237 fout << "# Triangles: " << nT << std::endl;
238 fout << "" << std::endl;
239 fout << "Group {" << std::endl;
240 fout << " children [" << std::endl;
241 fout << " Shape {" << std::endl;
242 fout << " appearance Appearance {" << std::endl;
243 fout << " material Material {" << std::endl;
244 fout << " diffuseColor " << material.m_diffuseColor[0] << " "
245 << material.m_diffuseColor[1] << " "
246 << material.m_diffuseColor[2] << std::endl;
247 fout << " ambientIntensity " << material.m_ambientIntensity << std::endl;
248 fout << " specularColor " << material.m_specularColor[0] << " "
249 << material.m_specularColor[1] << " "
250 << material.m_specularColor[2] << std::endl;
251 fout << " emissiveColor " << material.m_emissiveColor[0] << " "
252 << material.m_emissiveColor[1] << " "
253 << material.m_emissiveColor[2] << std::endl;
254 fout << " shininess " << material.m_shininess << std::endl;
255 fout << " transparency " << material.m_transparency << std::endl;
256 fout << " }" << std::endl;
257 fout << " }" << std::endl;
258 fout << " geometry IndexedFaceSet {" << std::endl;
259 fout << " ccw TRUE" << std::endl;
260 fout << " solid TRUE" << std::endl;
261 fout << " convex TRUE" << std::endl;
262 if (nV > 0) {
263 fout << " coord DEF co Coordinate {" << std::endl;
264 fout << " point [" << std::endl;
265 for (size_t v = 0; v < nV; v++) {
266 fout << " " << m_points[v][0] << " "
267 << m_points[v][1] << " "
268 << m_points[v][2] << "," << std::endl;
269 }
270 fout << " ]" << std::endl;
271 fout << " }" << std::endl;
272 }
273 if (nT > 0) {
274 fout << " coordIndex [ " << std::endl;
275 for (size_t f = 0; f < nT; f++) {
276 fout << " " << m_triangles[f][0] << ", "
277 << m_triangles[f][1] << ", "
278 << m_triangles[f][2] << ", -1," << std::endl;
279 }
280 fout << " ]" << std::endl;
281 }
282 fout << " }" << std::endl;
283 fout << " }" << std::endl;
284 fout << " ]" << std::endl;
285 fout << "}" << std::endl;
286 return true;
287 }
288 return false;
289 }
SaveOFF(const std::string & fileName) const290 bool Mesh::SaveOFF(const std::string& fileName) const
291 {
292 std::ofstream fout(fileName.c_str());
293 if (fout.is_open()) {
294 size_t nV = m_points.Size();
295 size_t nT = m_triangles.Size();
296 fout << "OFF" << std::endl;
297 fout << nV << " " << nT << " " << 0 << std::endl;
298 for (size_t v = 0; v < nV; v++) {
299 fout << m_points[v][0] << " "
300 << m_points[v][1] << " "
301 << m_points[v][2] << std::endl;
302 }
303 for (size_t f = 0; f < nT; f++) {
304 fout << "3 " << m_triangles[f][0] << " "
305 << m_triangles[f][1] << " "
306 << m_triangles[f][2] << std::endl;
307 }
308 fout.close();
309 return true;
310 }
311 return false;
312 }
313
LoadOFF(const std::string & fileName,bool invert)314 bool Mesh::LoadOFF(const std::string& fileName, bool invert)
315 {
316 FILE* fid = fopen(fileName.c_str(), "r");
317 if (fid) {
318 const std::string strOFF("OFF");
319 char temp[1024];
320 fscanf(fid, "%s", temp);
321 if (std::string(temp) != strOFF) {
322 fclose(fid);
323 return false;
324 }
325 else {
326 int32_t nv = 0;
327 int32_t nf = 0;
328 int32_t ne = 0;
329 fscanf(fid, "%i", &nv);
330 fscanf(fid, "%i", &nf);
331 fscanf(fid, "%i", &ne);
332 m_points.Resize(nv);
333 m_triangles.Resize(nf);
334 Vec3<double> coord;
335 float x, y, z;
336 for (int32_t p = 0; p < nv; p++) {
337 fscanf(fid, "%f", &x);
338 fscanf(fid, "%f", &y);
339 fscanf(fid, "%f", &z);
340 m_points[p][0] = x;
341 m_points[p][1] = y;
342 m_points[p][2] = z;
343 }
344 int32_t i, j, k, s;
345 for (int32_t t = 0; t < nf; ++t) {
346 fscanf(fid, "%i", &s);
347 if (s == 3) {
348 fscanf(fid, "%i", &i);
349 fscanf(fid, "%i", &j);
350 fscanf(fid, "%i", &k);
351 m_triangles[t][0] = i;
352 if (invert) {
353 m_triangles[t][1] = k;
354 m_triangles[t][2] = j;
355 }
356 else {
357 m_triangles[t][1] = j;
358 m_triangles[t][2] = k;
359 }
360 }
361 else // Fix me: support only triangular meshes
362 {
363 for (int32_t h = 0; h < s; ++h)
364 fscanf(fid, "%i", &s);
365 }
366 }
367 fclose(fid);
368 }
369 }
370 else {
371 return false;
372 }
373 return true;
374 }
375 #endif // VHACD_DEBUG_MESH
376 }
377