1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#include "Mesh/BsMeshUtility.h"
4#include "Math/BsVector4.h"
5#include "Math/BsVector3.h"
6#include "Math/BsVector2.h"
7#include "Math/BsPlane.h"
8
9namespace bs
10{
11 struct VertexFaces
12 {
13 UINT32* faces;
14 UINT32 numFaces = 0;
15 };
16
17 struct VertexConnectivity
18 {
19 VertexConnectivity(UINT8* indices, UINT32 numVertices, UINT32 numFaces, UINT32 indexSize)
20 :vertexFaces(nullptr), mMaxFacesPerVertex(0), mNumVertices(numVertices), mFaces(nullptr)
21 {
22 vertexFaces = bs_newN<VertexFaces>(numVertices);
23
24 resizeFaceArray(10);
25
26 for (UINT32 i = 0; i < numFaces; i++)
27 {
28 for (UINT32 j = 0; j < 3; j++)
29 {
30 UINT32 idx = i * 3 + j;
31 UINT32 vertexIdx = 0;
32 memcpy(&vertexIdx, indices + idx * indexSize, indexSize);
33
34 assert(vertexIdx < mNumVertices);
35 VertexFaces& faces = vertexFaces[vertexIdx];
36 if (faces.numFaces >= mMaxFacesPerVertex)
37 resizeFaceArray(mMaxFacesPerVertex * 2);
38
39 faces.faces[faces.numFaces] = i;
40 faces.numFaces++;
41 }
42 }
43 }
44
45 ~VertexConnectivity()
46 {
47 if (vertexFaces != nullptr)
48 bs_deleteN(vertexFaces, mNumVertices);
49
50 if (mFaces != nullptr)
51 bs_free(mFaces);
52 }
53
54 VertexFaces* vertexFaces;
55
56 private:
57 void resizeFaceArray(UINT32 numFaces)
58 {
59 UINT32* newFaces = (UINT32*)bs_alloc(numFaces * mNumVertices * sizeof(UINT32));
60
61 if (mFaces != nullptr)
62 {
63 for (UINT32 i = 0; i < mNumVertices; i++)
64 memcpy(newFaces + (i * numFaces), mFaces + (i * mMaxFacesPerVertex), mMaxFacesPerVertex * sizeof(UINT32));
65
66 bs_free(mFaces);
67 }
68
69 for (UINT32 i = 0; i < mNumVertices; i++)
70 vertexFaces[i].faces = newFaces + (i * numFaces);
71
72 mFaces = newFaces;
73 mMaxFacesPerVertex = numFaces;
74 }
75
76 UINT32 mMaxFacesPerVertex;
77 UINT32 mNumVertices;
78 UINT32* mFaces;
79 };
80
81 /** Provides base methods required for clipping of arbitrary triangles. */
82 class TriangleClipperBase // Implementation from: http://www.geometrictools.com/Documentation/ClipMesh.pdf
83 {
84 protected:
85 /** Single vertex in the clipped mesh. */
86 struct ClipVert
87 {
88 ClipVert() { }
89
90 Vector3 point = Vector3::ZERO;
91 Vector2 uv = Vector2::ZERO;
92 float distance = 0.0f;
93 UINT32 occurs = 0;
94 bool visible = true;
95 };
96
97 /** Single edge in the clipped mesh. */
98 struct ClipEdge
99 {
100 ClipEdge() { }
101
102 UINT32 verts[2];
103 Vector<UINT32> faces;
104 bool visible = true;
105 };
106
107 /** Single polygon in the clipped mesh. */
108 struct ClipFace
109 {
110 ClipFace() { }
111
112 Vector<UINT32> edges;
113 bool visible = true;
114 Vector3 normal = Vector3::ZERO;
115 };
116
117 /** Contains vertices, edges and faces of the clipped mesh. */
118 struct ClipMesh
119 {
120 ClipMesh() { }
121
122 Vector<ClipVert> verts;
123 Vector<ClipEdge> edges;
124 Vector<ClipFace> faces;
125 };
126
127 protected:
128 /**
129 * Register all edges and faces, using the mesh vertices as a basis. Assumes vertices are not indexed and that
130 * every three vertices form a face
131 */
132 void addEdgesAndFaces();
133
134 /** Clips the current mesh with the provided plane. */
135 INT32 clipByPlane(const Plane& plane);
136
137 /** Clips vertices of the current mesh by the provided plane. */
138 INT32 processVertices(const Plane& plane);
139
140 /** Clips edges of the current mesh. processVertices() must be called beforehand. */
141 void processEdges();
142
143 /** Clips the faces (polygons) of the current mesh. processEdges() must be called beforehand. */
144 void processFaces();
145
146 /**
147 * Returns a set of non-culled vertex indices for every visible face in the mesh. This should be called after
148 * clipping operation is complete to retrieve valid vertices.
149 */
150 void getOrderedFaces(FrameVector<FrameVector<UINT32>>& sortedFaces);
151
152 /** Returns a set of ordered and non-culled vertices for the provided face of the mesh */
153 void getOrderedVertices(const ClipFace& face, UINT32* vertices);
154
155 /** Calculates the normal for vertices related to the provided vertex indices. */
156 Vector3 getNormal(UINT32* sortedVertices, UINT32 numVertices);
157
158 /**
159 * Checks is the polygon shape of the provided face open or closed. If open, returns true and outputs endpoints of
160 * the polyline.
161 */
162 bool getOpenPolyline(ClipFace& face, UINT32& start, UINT32& end);
163
164 ClipMesh mesh;
165 };
166
167 void TriangleClipperBase::addEdgesAndFaces()
168 {
169 UINT32 numTris = (UINT32)mesh.verts.size() / 3;
170
171 UINT32 numEdges = numTris * 3;
172 mesh.edges.resize(numEdges);
173 mesh.faces.resize(numTris);
174
175 for (UINT32 i = 0; i < numTris; i++)
176 {
177 UINT32 idx0 = i * 3 + 0;
178 UINT32 idx1 = i * 3 + 1;
179 UINT32 idx2 = i * 3 + 2;
180
181 ClipEdge& clipEdge0 = mesh.edges[idx0];
182 clipEdge0.verts[0] = idx0;
183 clipEdge0.verts[1] = idx1;
184
185 ClipEdge& clipEdge1 = mesh.edges[idx1];
186 clipEdge1.verts[0] = idx1;
187 clipEdge1.verts[1] = idx2;
188
189 ClipEdge& clipEdge2 = mesh.edges[idx2];
190 clipEdge2.verts[0] = idx2;
191 clipEdge2.verts[1] = idx0;
192
193 ClipFace& clipFace = mesh.faces[i];
194
195 clipFace.edges.push_back(idx0);
196 clipFace.edges.push_back(idx1);
197 clipFace.edges.push_back(idx2);
198
199 clipEdge0.faces.push_back(i);
200 clipEdge1.faces.push_back(i);
201 clipEdge2.faces.push_back(i);
202
203 UINT32 verts[] = { idx0, idx1, idx2, idx0 };
204 for (UINT32 j = 0; j < 3; j++)
205 clipFace.normal += Vector3::cross(mesh.verts[verts[j]].point, mesh.verts[verts[j + 1]].point);
206
207 clipFace.normal.normalize();
208 }
209 }
210
211 INT32 TriangleClipperBase::clipByPlane(const Plane& plane)
212 {
213 int state = processVertices(plane);
214
215 if (state == 1)
216 return +1; // Nothing is clipped
217 else if (state == -1)
218 return -1; // Everything is clipped
219
220 processEdges();
221 processFaces();
222
223 return 0;
224 }
225
226 INT32 TriangleClipperBase::processVertices(const Plane& plane)
227 {
228 static const float EPSILON = 0.00001f;
229
230 // Compute signed distances from vertices to plane
231 int positive = 0, negative = 0;
232 for (UINT32 i = 0; i < (UINT32)mesh.verts.size(); i++)
233 {
234 ClipVert& vertex = mesh.verts[i];
235
236 if (vertex.visible)
237 {
238 vertex.distance = Vector3::dot(plane.normal, vertex.point) - plane.d;
239 if (vertex.distance >= EPSILON)
240 {
241 positive++;
242 }
243 else if (vertex.distance <= -EPSILON)
244 {
245 negative++;
246 vertex.visible = false;
247 }
248 else
249 {
250 // Point on the plane within floating point tolerance
251 vertex.distance = 0;
252 }
253 }
254 }
255 if (negative == 0)
256 {
257 // All vertices on nonnegative side, no clipping
258 return +1;
259 }
260 if (positive == 0)
261 {
262 // All vertices on nonpositive side, everything clipped
263 return -1;
264 }
265
266 return 0;
267 }
268
269 void TriangleClipperBase::processEdges()
270 {
271 for (UINT32 i = 0; i < (UINT32)mesh.edges.size(); i++)
272 {
273 ClipEdge& edge = mesh.edges[i];
274
275 if (edge.visible)
276 {
277 const ClipVert& v0 = mesh.verts[edge.verts[0]];
278 const ClipVert& v1 = mesh.verts[edge.verts[1]];
279
280 float d0 = v0.distance;
281 float d1 = v1.distance;
282
283 if (d0 <= 0 && d1 <= 0)
284 {
285 // Edge is culled, remove edge from faces sharing it
286 for (UINT32 j = 0; j < (UINT32)edge.faces.size(); j++)
287 {
288 ClipFace& face = mesh.faces[edge.faces[j]];
289
290 auto iterFind = std::find(face.edges.begin(), face.edges.end(), i);
291 if (iterFind != face.edges.end())
292 {
293 face.edges.erase(iterFind);
294
295 if (face.edges.empty())
296 face.visible = false;
297 }
298 }
299
300 edge.visible = false;
301 continue;
302 }
303
304 if (d0 >= 0 && d1 >= 0)
305 {
306 // Edge is on nonnegative side, faces retain the edge
307 continue;
308 }
309
310 // The edge is split by the plane. Compute the point of intersection.
311 // If the old edge is <V0,V1> and I is the intersection point, the new
312 // edge is <V0,I> when d0 > 0 or <I,V1> when d1 > 0.
313 float t = d0 / (d0 - d1);
314 Vector3 intersectPt = (1 - t)*v0.point + t*v1.point;
315 Vector2 intersectUv = (1 - t)*v0.uv + t*v1.uv;
316
317 UINT32 newVertIdx = (UINT32)mesh.verts.size();
318 mesh.verts.push_back(ClipVert());
319
320 ClipVert& newVert = mesh.verts.back();
321 newVert.point = intersectPt;
322 newVert.uv = intersectUv;
323
324 if (d0 > 0)
325 mesh.edges[i].verts[1] = newVertIdx;
326 else
327 mesh.edges[i].verts[0] = newVertIdx;
328 }
329 }
330 }
331
332 void TriangleClipperBase::processFaces()
333 {
334 for (UINT32 i = 0; i < (UINT32)mesh.faces.size(); i++)
335 {
336 ClipFace& face = mesh.faces[i];
337
338 if (face.visible)
339 {
340 // The edge is culled. If the edge is exactly on the clip
341 // plane, it is possible that a visible triangle shares it.
342 // The edge will be re-added during the face loop.
343
344 for (UINT32 j = 0; j < (UINT32)face.edges.size(); j++)
345 {
346 ClipEdge& edge = mesh.edges[face.edges[j]];
347 ClipVert& v0 = mesh.verts[edge.verts[0]];
348 ClipVert& v1 = mesh.verts[edge.verts[1]];
349
350 v0.occurs = 0;
351 v1.occurs = 0;
352 }
353 }
354
355 UINT32 start, end;
356 if (getOpenPolyline(mesh.faces[i], start, end))
357 {
358 // Polyline is open, close it
359 UINT32 closeEdgeIdx = (UINT32)mesh.edges.size();
360 mesh.edges.push_back(ClipEdge());
361 ClipEdge& closeEdge = mesh.edges.back();
362
363 closeEdge.verts[0] = start;
364 closeEdge.verts[1] = end;
365
366 closeEdge.faces.push_back(i);
367 face.edges.push_back(closeEdgeIdx);
368 }
369 }
370 }
371
372 bool TriangleClipperBase::getOpenPolyline(ClipFace& face, UINT32& start, UINT32& end)
373 {
374 // Count the number of occurrences of each vertex in the polyline. The
375 // resulting "occurs" values must be 1 or 2.
376 for (UINT32 i = 0; i < (UINT32)face.edges.size(); i++)
377 {
378 ClipEdge& edge = mesh.edges[face.edges[i]];
379
380 if (edge.visible)
381 {
382 ClipVert& v0 = mesh.verts[edge.verts[0]];
383 ClipVert& v1 = mesh.verts[edge.verts[1]];
384
385 v0.occurs++;
386 v1.occurs++;
387 }
388 }
389
390 // Determine if the polyline is open
391 bool gotStart = false;
392 bool gotEnd = false;
393 for (UINT32 i = 0; i < (UINT32)face.edges.size(); i++)
394 {
395 const ClipEdge& edge = mesh.edges[face.edges[i]];
396
397 const ClipVert& v0 = mesh.verts[edge.verts[0]];
398 const ClipVert& v1 = mesh.verts[edge.verts[1]];
399
400 if (v0.occurs == 1)
401 {
402 if (!gotStart)
403 {
404 start = edge.verts[0];
405 gotStart = true;
406 }
407 else if (!gotEnd)
408 {
409 end = edge.verts[0];
410 gotEnd = true;
411 }
412 }
413
414 if (v1.occurs == 1)
415 {
416 if (!gotStart)
417 {
418 start = edge.verts[1];
419 gotStart = true;
420 }
421 else if (!gotEnd)
422 {
423 end = edge.verts[1];
424 gotEnd = true;
425 }
426 }
427 }
428
429 return gotStart;
430 }
431
432 void TriangleClipperBase::getOrderedFaces(FrameVector<FrameVector<UINT32>>& sortedFaces)
433 {
434 for (UINT32 i = 0; i < (UINT32)mesh.faces.size(); i++)
435 {
436 const ClipFace& face = mesh.faces[i];
437
438 if (face.visible)
439 {
440 // Get the ordered vertices of the face. The first and last
441 // element of the array are the same since the polyline is
442 // closed.
443 UINT32 numSortedVerts = (UINT32)face.edges.size() + 1;
444 UINT32* sortedVerts = (UINT32*)bs_stack_alloc(sizeof(UINT32) * numSortedVerts);
445
446 getOrderedVertices(face, sortedVerts);
447
448 FrameVector<UINT32> faceVerts;
449
450 // The convention is that the vertices should be counterclockwise
451 // ordered when viewed from the negative side of the plane of the
452 // face. If you need the opposite convention, switch the
453 // inequality in the if-else statement.
454 Vector3 normal = getNormal(sortedVerts, numSortedVerts);
455 if (Vector3::dot(mesh.faces[i].normal, normal) < 0)
456 {
457 // Clockwise, need to swap
458 for (INT32 j = (INT32)numSortedVerts - 2; j >= 0; j--)
459 faceVerts.push_back(sortedVerts[j]);
460 }
461 else
462 {
463 // Counterclockwise
464 for (int j = 0; j <= (INT32)numSortedVerts - 2; j++)
465 faceVerts.push_back(sortedVerts[j]);
466 }
467
468 sortedFaces.push_back(faceVerts);
469 bs_stack_free(sortedVerts);
470 }
471 }
472 }
473
474 void TriangleClipperBase::getOrderedVertices(const ClipFace& face, UINT32* sortedVerts)
475 {
476 UINT32 numEdges = (UINT32)face.edges.size();
477 UINT32* sortedEdges = (UINT32*)bs_stack_alloc(sizeof(UINT32) * numEdges);
478 for (UINT32 i = 0; i < numEdges; i++)
479 sortedEdges[i] = face.edges[i];
480
481 // Bubble sort to arrange edges in contiguous order
482 for (UINT32 i0 = 0, i1 = 1, choice = 1; i1 < numEdges - 1; i0 = i1, i1++)
483 {
484 const ClipEdge& edge0 = mesh.edges[sortedEdges[i0]];
485
486 UINT32 current = edge0.verts[choice];
487 for (UINT32 j = i1; j < numEdges; j++)
488 {
489 const ClipEdge& edge1 = mesh.edges[sortedEdges[j]];
490
491 if (edge1.verts[0] == current || edge1.verts[1] == current)
492 {
493 std::swap(sortedEdges[i1], sortedEdges[j]);
494 choice = 1;
495 break;
496 }
497 }
498 }
499
500 // Add the first two vertices
501 sortedVerts[0] = mesh.edges[sortedEdges[0]].verts[0];
502 sortedVerts[1] = mesh.edges[sortedEdges[0]].verts[1];
503
504 // Add the remaining vertices
505 for (UINT32 i = 1; i < numEdges; i++)
506 {
507 const ClipEdge& edge = mesh.edges[sortedEdges[i]];
508
509 if (edge.verts[0] == sortedVerts[i])
510 sortedVerts[i + 1] = edge.verts[1];
511 else
512 sortedVerts[i + 1] = edge.verts[0];
513 }
514
515 bs_stack_free(sortedEdges);
516 }
517
518 Vector3 TriangleClipperBase::getNormal(UINT32* sortedVertices, UINT32 numVertices)
519 {
520 Vector3 normal(BsZero);
521 for (UINT32 i = 0; i <= numVertices - 2; i++)
522 normal += Vector3::cross(mesh.verts[sortedVertices[i]].point, mesh.verts[sortedVertices[i + 1]].point);
523
524 normal.normalize();
525 return normal;
526 }
527
528 /** Clips two-dimensional triangles against a set of provided planes. */
529 class TriangleClipper2D : public TriangleClipperBase
530 {
531 public:
532 /** @copydoc MeshUtility::clip2D */
533 void clip(UINT8* vertices, UINT8* uvs, UINT32 numTris, UINT32 vertexStride, const Vector<Plane>& clipPlanes,
534 const std::function<void(Vector2*, Vector2*, UINT32)>& writeCallback);
535
536 private:
537 /** Converts clipped vertices back into triangles and outputs them via the provided callback. */
538 void convertToMesh(const std::function<void(Vector2*, Vector2*, UINT32)>& writeCallback);
539
540 static const int BUFFER_SIZE = 64 * 3; // Must be a multiple of three
541 Vector2 vertexBuffer[BUFFER_SIZE];
542 Vector2 uvBuffer[BUFFER_SIZE];
543 };
544
545 void TriangleClipper2D::clip(UINT8* vertices, UINT8* uvs, UINT32 numTris, UINT32 vertexStride, const Vector<Plane>& clipPlanes,
546 const std::function<void(Vector2*, Vector2*, UINT32)>& writeCallback)
547 {
548 // Add vertices
549 UINT32 numVertices = numTris * 3;
550 mesh.verts.resize(numVertices);
551
552 if (uvs != nullptr)
553 {
554 for (UINT32 i = 0; i < numVertices; i++)
555 {
556 ClipVert& clipVert = mesh.verts[i];
557 Vector2 vector2D = *(Vector2*)(vertices + vertexStride * i);
558
559 clipVert.point = Vector3(vector2D.x, vector2D.y, 0.0f);
560 clipVert.uv = *(Vector2*)(uvs + vertexStride * i);
561 }
562 }
563 else
564 {
565 for (UINT32 i = 0; i < numVertices; i++)
566 {
567 ClipVert& clipVert = mesh.verts[i];
568 Vector2 vector2D = *(Vector2*)(vertices + vertexStride * i);
569
570 clipVert.point = Vector3(vector2D.x, vector2D.y, 0.0f);
571 }
572 }
573
574 addEdgesAndFaces();
575
576 for (int i = 0; i < 4; i++)
577 {
578 if (clipByPlane(clipPlanes[i]) == -1)
579 return;
580 }
581
582 convertToMesh(writeCallback);
583 }
584
585 void TriangleClipper2D::convertToMesh(const std::function<void(Vector2*, Vector2*, UINT32)>& writeCallback)
586 {
587 bs_frame_mark();
588 {
589 FrameVector<FrameVector<UINT32>> allFaces;
590 getOrderedFaces(allFaces);
591
592 // Note: Consider using Delaunay triangulation to avoid skinny triangles
593 UINT32 numWritten = 0;
594 assert(BUFFER_SIZE % 3 == 0);
595 for (auto& face : allFaces)
596 {
597 for (UINT32 i = 0; i < (UINT32)face.size() - 2; i++)
598 {
599 const Vector3& v0 = mesh.verts[face[0]].point;
600 const Vector3& v1 = mesh.verts[face[i + 1]].point;
601 const Vector3& v2 = mesh.verts[face[i + 2]].point;
602
603 vertexBuffer[numWritten] = Vector2(v0.x, v0.y);
604 uvBuffer[numWritten] = mesh.verts[face[0]].uv;
605 numWritten++;
606
607 vertexBuffer[numWritten] = Vector2(v1.x, v1.y);
608 uvBuffer[numWritten] = mesh.verts[face[i + 1]].uv;
609 numWritten++;
610
611 vertexBuffer[numWritten] = Vector2(v2.x, v2.y);
612 uvBuffer[numWritten] = mesh.verts[face[i + 2]].uv;
613 numWritten++;
614
615 // Only need to check this here since we guarantee the buffer is in multiples of three
616 if (numWritten >= BUFFER_SIZE)
617 {
618 writeCallback(vertexBuffer, uvBuffer, numWritten);
619 numWritten = 0;
620 }
621 }
622 }
623
624 if (numWritten > 0)
625 writeCallback(vertexBuffer, uvBuffer, numWritten);
626 }
627 bs_frame_clear();
628 }
629
630 /** Clips three-dimensional triangles against a set of provided planes. */
631 class TriangleClipper3D : public TriangleClipperBase
632 {
633 public:
634 /** @copydoc MeshUtility::clip3D */
635 void clip(UINT8* vertices, UINT8* uvs, UINT32 numTris, UINT32 vertexStride, const Vector<Plane>& clipPlanes,
636 const std::function<void(Vector3*, Vector2*, UINT32)>& writeCallback);
637
638 private:
639 /** Converts clipped vertices back into triangles and outputs them via the provided callback. */
640 void convertToMesh(const std::function<void(Vector3*, Vector2*, UINT32)>& writeCallback);
641
642 static const int BUFFER_SIZE = 64 * 3; // Must be a multiple of three
643 Vector3 vertexBuffer[BUFFER_SIZE];
644 Vector2 uvBuffer[BUFFER_SIZE];
645 };
646
647 void TriangleClipper3D::clip(UINT8* vertices, UINT8* uvs, UINT32 numTris, UINT32 vertexStride, const Vector<Plane>& clipPlanes,
648 const std::function<void(Vector3*, Vector2*, UINT32)>& writeCallback)
649 {
650 // Add vertices
651 UINT32 numVertices = numTris * 3;
652 mesh.verts.resize(numVertices);
653
654 if (uvs != nullptr)
655 {
656 for (UINT32 i = 0; i < numVertices; i++)
657 {
658 ClipVert& clipVert = mesh.verts[i];
659
660 clipVert.point = *(Vector3*)(vertices + vertexStride * i);
661 clipVert.uv = *(Vector2*)(uvs + vertexStride * i);
662 }
663 }
664 else
665 {
666 for (UINT32 i = 0; i < numVertices; i++)
667 {
668 ClipVert& clipVert = mesh.verts[i];
669 Vector2 vector2D = *(Vector2*)(vertices + vertexStride * i);
670
671 clipVert.point = Vector3(vector2D.x, vector2D.y, 0.0f);
672 }
673 }
674
675 addEdgesAndFaces();
676
677 for (int i = 0; i < 4; i++)
678 {
679 if (clipByPlane(clipPlanes[i]) == -1)
680 return;
681 }
682
683 convertToMesh(writeCallback);
684 }
685
686 void TriangleClipper3D::convertToMesh(const std::function<void(Vector3*, Vector2*, UINT32)>& writeCallback)
687 {
688 bs_frame_mark();
689 {
690 FrameVector<FrameVector<UINT32>> allFaces;
691 getOrderedFaces(allFaces);
692
693 // Note: Consider using Delaunay triangulation to avoid skinny triangles
694 UINT32 numWritten = 0;
695 assert(BUFFER_SIZE % 3 == 0);
696 for (auto& face : allFaces)
697 {
698 for (UINT32 i = 0; i < (UINT32)face.size() - 2; i++)
699 {
700 vertexBuffer[numWritten] = mesh.verts[face[0]].point;
701 uvBuffer[numWritten] = mesh.verts[face[0]].uv;
702 numWritten++;
703
704 vertexBuffer[numWritten] = mesh.verts[face[i + 1]].point;
705 uvBuffer[numWritten] = mesh.verts[face[i + 1]].uv;
706 numWritten++;
707
708 vertexBuffer[numWritten] = mesh.verts[face[i + 2]].point;
709 uvBuffer[numWritten] = mesh.verts[face[i + 2]].uv;
710 numWritten++;
711
712 // Only need to check this here since we guarantee the buffer is in multiples of three
713 if (numWritten >= BUFFER_SIZE)
714 {
715 writeCallback(vertexBuffer, uvBuffer, numWritten);
716 numWritten = 0;
717 }
718 }
719 }
720
721 if (numWritten > 0)
722 writeCallback(vertexBuffer, uvBuffer, numWritten);
723 }
724 bs_frame_clear();
725 }
726
727 void MeshUtility::calculateNormals(Vector3* vertices, UINT8* indices, UINT32 numVertices,
728 UINT32 numIndices, Vector3* normals, UINT32 indexSize)
729 {
730 UINT32 numFaces = numIndices / 3;
731
732 Vector3* faceNormals = bs_newN<Vector3>(numFaces);
733 for (UINT32 i = 0; i < numFaces; i++)
734 {
735 UINT32 triangle[3];
736 memcpy(&triangle[0], indices + (i * 3 + 0) * indexSize, indexSize);
737 memcpy(&triangle[1], indices + (i * 3 + 1) * indexSize, indexSize);
738 memcpy(&triangle[2], indices + (i * 3 + 2) * indexSize, indexSize);
739
740 Vector3 edgeA = vertices[triangle[1]] - vertices[triangle[0]];
741 Vector3 edgeB = vertices[triangle[2]] - vertices[triangle[0]];
742 faceNormals[i] = Vector3::normalize(Vector3::cross(edgeA, edgeB));
743
744 // Note: Potentially don't normalize here in order to weigh the normals
745 // by triangle size
746 }
747
748 VertexConnectivity connectivity(indices, numVertices, numFaces, indexSize);
749 for (UINT32 i = 0; i < numVertices; i++)
750 {
751 VertexFaces& faces = connectivity.vertexFaces[i];
752
753 normals[i] = Vector3::ZERO;
754 for (UINT32 j = 0; j < faces.numFaces; j++)
755 {
756 UINT32 faceIdx = faces.faces[j];
757 normals[i] += faceNormals[faceIdx];
758 }
759
760 normals[i].normalize();
761 }
762
763 bs_deleteN(faceNormals, numFaces);
764 }
765
766 void MeshUtility::calculateTangents(Vector3* vertices, Vector3* normals, Vector2* uv, UINT8* indices, UINT32 numVertices,
767 UINT32 numIndices, Vector3* tangents, Vector3* bitangents, UINT32 indexSize, UINT32 vertexStride)
768 {
769 UINT32 numFaces = numIndices / 3;
770 UINT32 vec2Stride = vertexStride == 0 ? sizeof(Vector2) : vertexStride;
771 UINT32 vec3Stride = vertexStride == 0 ? sizeof(Vector3) : vertexStride;
772
773 UINT8* positionBytes = (UINT8*)vertices;
774 UINT8* normalBytes = (UINT8*)normals;
775 UINT8* uvBytes = (UINT8*)uv;
776
777 Vector3* faceTangents = bs_newN<Vector3>(numFaces);
778 Vector3* faceBitangents = bs_newN<Vector3>(numFaces);
779 for (UINT32 i = 0; i < numFaces; i++)
780 {
781 UINT32 triangle[3];
782 memcpy(&triangle[0], indices + (i * 3 + 0) * indexSize, indexSize);
783 memcpy(&triangle[1], indices + (i * 3 + 1) * indexSize, indexSize);
784 memcpy(&triangle[2], indices + (i * 3 + 2) * indexSize, indexSize);
785
786 Vector3 p0 = *(Vector3*)&positionBytes[triangle[0] * vec3Stride];
787 Vector3 p1 = *(Vector3*)&positionBytes[triangle[1] * vec3Stride];
788 Vector3 p2 = *(Vector3*)&positionBytes[triangle[2] * vec3Stride];
789
790 Vector2 uv0 = *(Vector2*)&uvBytes[triangle[0] * vec2Stride];
791 Vector2 uv1 = *(Vector2*)&uvBytes[triangle[1] * vec2Stride];
792 Vector2 uv2 = *(Vector2*)&uvBytes[triangle[2] * vec2Stride];
793
794 Vector3 q0 = p1 - p0;
795 Vector3 q1 = p2 - p0;
796
797 Vector2 st1 = uv1 - uv0;
798 Vector2 st2 = uv2 - uv0;
799
800 float denom = st1.x * st2.y - st2.x * st1.y;
801 if (fabs(denom) >= 0e-8f)
802 {
803 float r = 1.0f / denom;
804
805 faceTangents[i] = (st2.y * q0 - st1.y * q1) * r;
806 faceBitangents[i] = (st1.x * q1 - st2.x * q0) * r;
807
808 faceTangents[i].normalize();
809 faceBitangents[i].normalize();
810 }
811
812 // Note: Potentially don't normalize here in order to weight the normals by triangle size
813 }
814
815 VertexConnectivity connectivity(indices, numVertices, numFaces, indexSize);
816 for (UINT32 i = 0; i < numVertices; i++)
817 {
818 VertexFaces& faces = connectivity.vertexFaces[i];
819
820 tangents[i] = Vector3::ZERO;
821 bitangents[i] = Vector3::ZERO;
822
823 for (UINT32 j = 0; j < faces.numFaces; j++)
824 {
825 UINT32 faceIdx = faces.faces[j];
826 tangents[i] += faceTangents[faceIdx];
827 bitangents[i] += faceBitangents[faceIdx];
828 }
829
830 tangents[i].normalize();
831 bitangents[i].normalize();
832
833 Vector3 normal = *(Vector3*)&normalBytes[i * vec3Stride];
834
835 // Orthonormalize
836 float dot0 = normal.dot(tangents[i]);
837 tangents[i] -= dot0*normal;
838 tangents[i].normalize();
839
840 float dot1 = tangents[i].dot(bitangents[i]);
841 dot0 = normal.dot(bitangents[i]);
842 bitangents[i] -= dot0*normal + dot1*tangents[i];
843 bitangents[i].normalize();
844 }
845
846 bs_deleteN(faceTangents, numFaces);
847 bs_deleteN(faceBitangents, numFaces);
848
849 // TODO - Consider weighing tangents by triangle size and/or edge angles
850 }
851
852 void MeshUtility::calculateTangentSpace(Vector3* vertices, Vector2* uv, UINT8* indices, UINT32 numVertices,
853 UINT32 numIndices, Vector3* normals, Vector3* tangents, Vector3* bitangents, UINT32 indexSize)
854 {
855 calculateNormals(vertices, indices, numVertices, numIndices, normals, indexSize);
856 calculateTangents(vertices, normals, uv, indices, numVertices, numIndices, tangents, bitangents, indexSize);
857 }
858
859 void MeshUtility::clip2D(UINT8* vertices, UINT8* uvs, UINT32 numTris, UINT32 vertexStride, const Vector<Plane>& clipPlanes,
860 const std::function<void(Vector2*, Vector2*, UINT32)>& writeCallback)
861 {
862 TriangleClipper2D clipper;
863 clipper.clip(vertices, uvs, numTris, vertexStride, clipPlanes, writeCallback);
864 }
865
866 void MeshUtility::clip3D(UINT8* vertices, UINT8* uvs, UINT32 numTris, UINT32 vertexStride, const Vector<Plane>& clipPlanes,
867 const std::function<void(Vector3*, Vector2*, UINT32)>& writeCallback)
868 {
869 TriangleClipper3D clipper;
870 clipper.clip(vertices, uvs, numTris, vertexStride, clipPlanes, writeCallback);
871 }
872
873 void MeshUtility::packNormals(Vector3* source, UINT8* destination, UINT32 count, UINT32 inStride, UINT32 outStride)
874 {
875 UINT8* srcPtr = (UINT8*)source;
876 UINT8* dstPtr = destination;
877 for (UINT32 i = 0; i < count; i++)
878 {
879 Vector3 src = *(Vector3*)srcPtr;
880
881 PackedNormal& packed = *(PackedNormal*)dstPtr;
882 packed.x = Math::clamp((int)(src.x * 127.5f + 127.5f), 0, 255);
883 packed.y = Math::clamp((int)(src.y * 127.5f + 127.5f), 0, 255);
884 packed.z = Math::clamp((int)(src.z * 127.5f + 127.5f), 0, 255);
885 packed.w = 128;
886
887 srcPtr += inStride;
888 dstPtr += outStride;
889 }
890 }
891
892 void MeshUtility::packNormals(Vector4* source, UINT8* destination, UINT32 count, UINT32 inStride, UINT32 outStride)
893 {
894 UINT8* srcPtr = (UINT8*)source;
895 UINT8* dstPtr = destination;
896 for (UINT32 i = 0; i < count; i++)
897 {
898 Vector4 src = *(Vector4*)srcPtr;
899 PackedNormal& packed = *(PackedNormal*)dstPtr;
900
901 packed.x = Math::clamp((int)(src.x * 127.5f + 127.5f), 0, 255);
902 packed.y = Math::clamp((int)(src.y * 127.5f + 127.5f), 0, 255);
903 packed.z = Math::clamp((int)(src.z * 127.5f + 127.5f), 0, 255);
904 packed.w = Math::clamp((int)(src.w * 127.5f + 127.5f), 0, 255);
905
906 srcPtr += inStride;
907 dstPtr += outStride;
908 }
909 }
910
911 void MeshUtility::unpackNormals(UINT8* source, Vector3* destination, UINT32 count, UINT32 stride)
912 {
913 UINT8* ptr = source;
914 for (UINT32 i = 0; i < count; i++)
915 {
916 destination[i] = unpackNormal(ptr);
917
918 ptr += stride;
919 }
920 }
921
922 void MeshUtility::unpackNormals(UINT8* source, Vector4* destination, UINT32 count, UINT32 stride)
923 {
924 UINT8* ptr = source;
925 for (UINT32 i = 0; i < count; i++)
926 {
927 PackedNormal& packed = *(PackedNormal*)ptr;
928
929 const float inv = (1.0f / 255.0f) * 2.0f;
930 destination[i].x = (packed.x * inv - 1.0f);
931 destination[i].y = (packed.y * inv - 1.0f);
932 destination[i].z = (packed.z * inv - 1.0f);
933 destination[i].w = (packed.w * inv - 1.0f);
934
935 ptr += stride;
936 }
937 }
938}