Freestyle: minor optimization for space from mesh importing to feature edge detection.
[blender.git] / source / blender / freestyle / intern / winged_edge / WingedEdgeBuilder.cpp
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/freestyle/intern/winged_edge/WingedEdgeBuilder.cpp
22  *  \ingroup freestyle
23  *  \brief Class to render a WingedEdge data structure from a polyhedral data structure organized in nodes
24  *         of a scene graph
25  *  \author Stephane Grabli
26  *  \date 28/05/2003
27  */
28
29 #include <set>
30
31 #include "WingedEdgeBuilder.h"
32
33 #include "../geometry/GeomUtils.h"
34
35 #include "../scene_graph/NodeShape.h"
36
37 using namespace std;
38
39 namespace Freestyle {
40
41 void WingedEdgeBuilder::visitIndexedFaceSet(IndexedFaceSet& ifs)
42 {
43         if (_pRenderMonitor && _pRenderMonitor->testBreak())
44                 return;
45         WShape *shape = new WShape;
46         if (!buildWShape(*shape, ifs)) {
47                 delete shape;
48                 return;
49         }
50         shape->setId(ifs.getId().getFirst());
51         //ifs.setId(shape->GetId());
52 }
53
54 void WingedEdgeBuilder::visitNodeShape(NodeShape& ns)
55 {
56         //Sets the current material to iShapeode->material:
57         _current_frs_material = &(ns.frs_material());
58 }
59
60 void WingedEdgeBuilder::visitNodeTransform(NodeTransform& tn)
61 {
62         if (!_current_matrix) {
63                 _current_matrix = new Matrix44r(tn.matrix());
64                 return;
65         }
66
67         _matrices_stack.push_back(_current_matrix);
68         Matrix44r *new_matrix = new Matrix44r(*_current_matrix * tn.matrix());
69         _current_matrix = new_matrix;
70 }
71
72 void WingedEdgeBuilder::visitNodeTransformAfter(NodeTransform&)
73 {
74         if (_current_matrix)
75                 delete _current_matrix;
76
77         if (_matrices_stack.empty()) {
78                 _current_matrix = NULL;
79                 return;
80         }
81
82         _current_matrix = _matrices_stack.back();
83         _matrices_stack.pop_back();
84 }
85
86 bool WingedEdgeBuilder::buildWShape(WShape& shape, IndexedFaceSet& ifs)
87 {
88         unsigned int vsize = ifs.vsize();
89         unsigned int nsize = ifs.nsize();
90         //soc unused - unsigned tsize = ifs.tsize();
91
92         const real *vertices = ifs.vertices();
93         const real *normals = ifs.normals();
94         const real *texCoords = ifs.texCoords();
95
96         real *new_vertices;
97         real *new_normals;
98
99         new_vertices = new real[vsize];
100         new_normals = new real[nsize];
101
102         // transform coordinates from local to world system
103         if (_current_matrix) {
104                 transformVertices(vertices, vsize, *_current_matrix, new_vertices);
105                 transformNormals(normals, nsize, *_current_matrix, new_normals);
106         }
107         else {
108                 memcpy(new_vertices, vertices, vsize * sizeof(*new_vertices));
109                 memcpy(new_normals, normals, nsize * sizeof(*new_normals));
110         }
111
112         const IndexedFaceSet::TRIANGLES_STYLE *faceStyle = ifs.trianglesStyle();
113
114         vector<FrsMaterial> frs_materials;
115         if (ifs.msize()) {
116                 const FrsMaterial *const *mats = ifs.frs_materials();
117                 for (unsigned i = 0; i < ifs.msize(); ++i)
118                         frs_materials.push_back(*(mats[i]));
119                 shape.setFrsMaterials(frs_materials);
120         }
121
122 #if 0
123         const FrsMaterial *mat = (ifs.frs_material());
124         if (mat)
125                 shape.setFrsMaterial(*mat);
126         else if (_current_frs_material)
127                 shape.setFrsMaterial(*_current_frs_material);
128 #endif
129         const IndexedFaceSet::FaceEdgeMark *faceEdgeMarks = ifs.faceEdgeMarks();
130
131         // sets the current WShape to shape
132         _current_wshape = &shape;
133
134         // create a WVertex for each vertex
135         buildWVertices(shape, new_vertices, vsize);
136
137         const unsigned int *vindices = ifs.vindices();
138         const unsigned int *nindices = ifs.nindices();
139         const unsigned int *tindices = NULL;
140         if (ifs.tsize()) {
141                 tindices = ifs.tindices();
142         }
143
144         const unsigned int *mindices = NULL;
145         if (ifs.msize())
146                 mindices = ifs.mindices();
147         const unsigned int *numVertexPerFace = ifs.numVertexPerFaces();
148         const unsigned int numfaces = ifs.numFaces();
149
150         for (unsigned int index = 0; index < numfaces; index++) {
151                 switch (faceStyle[index]) {
152                         case IndexedFaceSet::TRIANGLE_STRIP:
153                                 buildTriangleStrip(new_vertices, new_normals, frs_materials, texCoords, faceEdgeMarks, vindices,
154                                                    nindices, mindices, tindices, numVertexPerFace[index]);
155                                 break;
156                         case IndexedFaceSet::TRIANGLE_FAN:
157                                 buildTriangleFan(new_vertices, new_normals, frs_materials, texCoords, faceEdgeMarks, vindices,
158                                                  nindices, mindices, tindices, numVertexPerFace[index]);
159                                 break;
160                         case IndexedFaceSet::TRIANGLES:
161                                 buildTriangles(new_vertices, new_normals, frs_materials, texCoords, faceEdgeMarks, vindices,
162                                                nindices, mindices, tindices, numVertexPerFace[index]);
163                                 break;
164                 }
165                 vindices += numVertexPerFace[index];
166                 nindices += numVertexPerFace[index];
167                 if (mindices)
168                         mindices += numVertexPerFace[index];
169                 if (tindices)
170                         tindices += numVertexPerFace[index];
171                 faceEdgeMarks++;
172         }
173
174         delete[] new_vertices;
175         delete[] new_normals;
176
177         if (shape.GetFaceList().size() == 0) // this may happen due to degenerate triangles
178                 return false;
179
180 #if 0
181         // compute bbox
182         shape.ComputeBBox();
183         // compute mean edge size:
184         shape.ComputeMeanEdgeSize();
185 #endif
186
187         // Parse the built winged-edge shape to update post-flags
188         set<Vec3r> normalsSet;
189         vector<WVertex *>& wvertices = shape.getVertexList();
190         for (vector<WVertex *>::iterator wv = wvertices.begin(), wvend = wvertices.end(); wv != wvend; ++wv) {
191                 if ((*wv)->isBoundary())
192                         continue;
193                 if ((*wv)->GetEdges().size() == 0) // This means that the WVertex has no incoming edges... (12-Sep-2011 T.K.)
194                         continue;
195                 normalsSet.clear();
196                 WVertex::face_iterator fit = (*wv)->faces_begin();
197                 WVertex::face_iterator fitend = (*wv)->faces_end();
198                 for (; fit != fitend; ++fit) {
199                         WFace *face = *fit;
200                         normalsSet.insert(face->GetVertexNormal(*wv));
201                         if (normalsSet.size() != 1) {
202                                 break;
203                         }
204                 }
205                 if (normalsSet.size() != 1) {
206                         (*wv)->setSmooth(false);
207                 }
208         }
209
210         // Adds the new WShape to the WingedEdge structure
211         _winged_edge->addWShape(&shape);
212
213         return true;
214 }
215
216 void WingedEdgeBuilder::buildWVertices(WShape& shape, const real *vertices, unsigned vsize)
217 {
218         WVertex *vertex;
219         for (unsigned int i = 0; i < vsize; i += 3) {
220                 vertex = new WVertex(Vec3r(vertices[i], vertices[i + 1], vertices[i + 2]));
221                 vertex->setId(i / 3);
222                 shape.AddVertex(vertex);
223         }
224 }
225
226 void WingedEdgeBuilder::buildTriangleStrip(const real * /*vertices*/, const real *normals, vector<FrsMaterial>& /*iMaterials*/,
227                                            const real *texCoords, const IndexedFaceSet::FaceEdgeMark *iFaceEdgeMarks,
228                                            const unsigned *vindices, const unsigned *nindices, const unsigned *mindices,
229                                            const unsigned *tindices, const unsigned nvertices)
230 {
231         unsigned nDoneVertices = 2; // number of vertices already treated
232         unsigned nTriangle = 0;     // number of the triangle currently being treated
233         //int nVertex = 0;            // vertex number
234
235         WShape *currentShape = _current_wshape; // the current shape being built
236         vector<WVertex *> triangleVertices;
237         vector<Vec3r> triangleNormals;
238         vector<Vec2r> triangleTexCoords;
239         vector<bool> triangleFaceEdgeMarks;
240
241         while (nDoneVertices < nvertices) {
242                 //clear the vertices list:
243                 triangleVertices.clear();
244                 //Then rebuild it:
245                 if (0 == nTriangle % 2) { // if nTriangle is even
246                         triangleVertices.push_back(currentShape->getVertexList()[vindices[nTriangle] / 3]);
247                         triangleVertices.push_back(currentShape->getVertexList()[vindices[nTriangle + 1] / 3]);
248                         triangleVertices.push_back(currentShape->getVertexList()[vindices[nTriangle + 2] / 3]);
249
250                         triangleNormals.push_back(Vec3r(normals[nindices[nTriangle]], normals[nindices[nTriangle] + 1],
251                                                         normals[nindices[nTriangle] + 2]));
252                         triangleNormals.push_back(Vec3r(normals[nindices[nTriangle + 1]], normals[nindices[nTriangle + 1] + 1],
253                                                         normals[nindices[nTriangle + 1] + 2]));
254                         triangleNormals.push_back(Vec3r(normals[nindices[nTriangle + 2]], normals[nindices[nTriangle + 2] + 1],
255                                                         normals[nindices[nTriangle + 2] + 2]));
256
257                         if (texCoords) {
258                                 triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle]], texCoords[tindices[nTriangle] + 1]));
259                                 triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle + 1]],
260                                                                   texCoords[tindices[nTriangle + 1] + 1]));
261                                 triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle + 2]],
262                                                                   texCoords[tindices[nTriangle + 2] + 1]));
263                         }
264                 }
265                 else {                 // if nTriangle is odd
266                         triangleVertices.push_back(currentShape->getVertexList()[vindices[nTriangle] / 3]);
267                         triangleVertices.push_back(currentShape->getVertexList()[vindices[nTriangle + 2] / 3]);
268                         triangleVertices.push_back(currentShape->getVertexList()[vindices[nTriangle + 1] / 3]);
269
270                         triangleNormals.push_back(Vec3r(normals[nindices[nTriangle]], normals[nindices[nTriangle] + 1],
271                                                         normals[nindices[nTriangle] + 2]));
272                         triangleNormals.push_back(Vec3r(normals[nindices[nTriangle + 2]], normals[nindices[nTriangle + 2] + 1],
273                                                         normals[nindices[nTriangle + 2] + 2]));
274                         triangleNormals.push_back(Vec3r(normals[nindices[nTriangle + 1]], normals[nindices[nTriangle + 1] + 1],
275                                                         normals[nindices[nTriangle + 1] + 2]));
276
277                         if (texCoords) {
278                                 triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle]], texCoords[tindices[nTriangle] + 1]));
279                                 triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle + 2]],
280                                                                   texCoords[tindices[nTriangle + 2] + 1]));
281                                 triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle + 1]],
282                                                                   texCoords[tindices[nTriangle + 1] + 1]));
283                         }
284                 }
285                 triangleFaceEdgeMarks.push_back((iFaceEdgeMarks[nTriangle / 3] & IndexedFaceSet::FACE_MARK) != 0);
286                 triangleFaceEdgeMarks.push_back((iFaceEdgeMarks[nTriangle / 3] & IndexedFaceSet::EDGE_MARK_V1V2) != 0);
287                 triangleFaceEdgeMarks.push_back((iFaceEdgeMarks[nTriangle / 3] & IndexedFaceSet::EDGE_MARK_V2V3) != 0);
288                 triangleFaceEdgeMarks.push_back((iFaceEdgeMarks[nTriangle / 3] & IndexedFaceSet::EDGE_MARK_V3V1) != 0);
289                 if (mindices) {
290                         currentShape->MakeFace(triangleVertices, triangleNormals, triangleTexCoords, triangleFaceEdgeMarks,
291                                                mindices[nTriangle / 3]);
292                 }
293                 else {
294                         currentShape->MakeFace(triangleVertices, triangleNormals, triangleTexCoords, triangleFaceEdgeMarks, 0);
295                 }
296                 nDoneVertices++; // with a strip, each triangle is one vertex more
297                 nTriangle++;
298         }
299 }
300
301 void WingedEdgeBuilder::buildTriangleFan(const real * /*vertices*/, const real * /*normals*/, vector<FrsMaterial>& /*iMaterials*/,
302                                          const real * /*texCoords*/, const IndexedFaceSet::FaceEdgeMark * /*iFaceEdgeMarks*/,
303                                          const unsigned * /*vindices*/, const unsigned * /*nindices*/, const unsigned * /*mindices*/,
304                                          const unsigned * /*tindices*/, const unsigned /*nvertices*/)
305 {
306         // Nothing to be done
307 }
308
309 void WingedEdgeBuilder::buildTriangles(const real * /*vertices*/, const real *normals, vector<FrsMaterial>& /*iMaterials*/,
310                                        const real *texCoords, const IndexedFaceSet::FaceEdgeMark *iFaceEdgeMarks,
311                                        const unsigned *vindices, const unsigned *nindices, const unsigned *mindices,
312                                        const unsigned *tindices, const unsigned nvertices)
313 {
314         WShape *currentShape = _current_wshape; // the current shape begin built
315         vector<WVertex *> triangleVertices;
316         vector<Vec3r> triangleNormals;
317         vector<Vec2r> triangleTexCoords;
318         vector<bool> triangleFaceEdgeMarks;
319
320         // Each triplet of vertices is considered as an independent triangle
321         for (unsigned int i = 0; i < nvertices / 3; i++) {
322                 triangleVertices.push_back(currentShape->getVertexList()[vindices[3 * i] / 3]);
323                 triangleVertices.push_back(currentShape->getVertexList()[vindices[3 * i + 1] / 3]);
324                 triangleVertices.push_back(currentShape->getVertexList()[vindices[3 * i + 2] / 3]);
325
326                 triangleNormals.push_back(Vec3r(normals[nindices[3 * i]], normals[nindices[3 * i] + 1],
327                                                 normals[nindices[3 * i] + 2]));
328                 triangleNormals.push_back(Vec3r(normals[nindices[3 * i + 1]], normals[nindices[3 * i + 1] + 1],
329                                                 normals[nindices[3 * i + 1] + 2]));
330                 triangleNormals.push_back(Vec3r(normals[nindices[3 * i + 2]], normals[nindices[3 * i + 2] + 1],
331                                                 normals[nindices[3 * i + 2] + 2]));
332
333                 if (texCoords) {
334                         triangleTexCoords.push_back(Vec2r(texCoords[tindices[3 * i]], texCoords[tindices[3 * i] + 1]));
335                         triangleTexCoords.push_back(Vec2r(texCoords[tindices[3 * i + 1]], texCoords[tindices[3 * i + 1] + 1]));
336                         triangleTexCoords.push_back(Vec2r(texCoords[tindices[3 * i + 2]], texCoords[tindices[3 * i + 2] + 1]));
337                 }
338
339                 triangleFaceEdgeMarks.push_back((iFaceEdgeMarks[i] & IndexedFaceSet::FACE_MARK) != 0);
340                 triangleFaceEdgeMarks.push_back((iFaceEdgeMarks[i] & IndexedFaceSet::EDGE_MARK_V1V2) != 0);
341                 triangleFaceEdgeMarks.push_back((iFaceEdgeMarks[i] & IndexedFaceSet::EDGE_MARK_V2V3) != 0);
342                 triangleFaceEdgeMarks.push_back((iFaceEdgeMarks[i] & IndexedFaceSet::EDGE_MARK_V3V1) != 0);
343         }
344         if (mindices)
345                 currentShape->MakeFace(triangleVertices, triangleNormals, triangleTexCoords, triangleFaceEdgeMarks,
346                                        mindices[0]);
347         else
348                 currentShape->MakeFace(triangleVertices, triangleNormals, triangleTexCoords, triangleFaceEdgeMarks, 0);
349 }
350
351 void WingedEdgeBuilder::transformVertices(const real *vertices, unsigned vsize, const Matrix44r& transform, real *res)
352 {
353         const real *v = vertices;
354         real *pv = res;
355
356         for (unsigned int i = 0; i < vsize / 3; i++) {
357                 HVec3r hv_tmp(v[0], v[1], v[2]);
358                 HVec3r hv(transform * hv_tmp);
359                 for (unsigned int j = 0; j < 3; j++)
360                         pv[j] = hv[j] / hv[3];
361                 v += 3;
362                 pv += 3;
363         }
364 }
365
366 void WingedEdgeBuilder::transformNormals(const real *normals, unsigned nsize, const Matrix44r& transform, real *res)
367 {
368         const real *n = normals;
369         real *pn = res;
370
371         for (unsigned int i = 0; i < nsize / 3; i++) {
372                 Vec3r hn(n[0], n[1], n[2]);
373                 hn = GeomUtils::rotateVector(transform, hn);
374                 for (unsigned int j = 0; j < 3; j++)
375                         pn[j] = hn[j];
376                 n += 3;
377                 pn += 3;
378         }
379 }
380
381 } /* namespace Freestyle */