15148066105

Committed 20 May 2025 09:14PM UTC coverage: 74.445% (+0.06%) from 74.385%

Build # 15148066105

Build Type

push

github

Committed by

Razakhel

Commit Message

[Data/MarchingSquares] Added a marching squares implementation

- It can be computed from a boolean 2D grid

Run Details

33 of 34 new or added lines in 2 files covered. (97.06%)

1 existing line in 1 file now uncovered.

8256 of 11090 relevant lines covered (74.45%)

1732.8 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.77

/src/RaZ/Data/MarchingSquares.cpp

#include "RaZ/Data/Grid2.hpp"
#include "RaZ/Data/MarchingSquares.hpp"
#include "RaZ/Data/Mesh.hpp"

#include "tracy/Tracy.hpp"

namespace Raz {

namespace {

constexpr std::array<Vec2f, 4> edgeVertices = {
  Vec2f(0.5f, 0.f), // Bottom
  Vec2f(1.f, 0.5f), // Right
  Vec2f(0.5f, 1.f), // Top
  Vec2f(0.f, 0.5f)  // Left
};

enum VertexPosition {
  NONE   = -1,
  BOTTOM = 0,
  RIGHT  = 1,
  TOP    = 2,
  LEFT   = 3
};

constexpr std::array<std::array<int8_t, 4>, 16> linesIndices = {{
  { NONE,   NONE,   NONE,   NONE  }, // 0000
  { LEFT,   BOTTOM, NONE,   NONE  }, // 0001
  { BOTTOM, RIGHT,  NONE,   NONE  }, // 0010
  { LEFT,   RIGHT,  NONE,   NONE  }, // 0011
  { TOP,    RIGHT,  NONE,   NONE  }, // 0100
  { LEFT,   TOP,    BOTTOM, RIGHT }, // 0101
  { BOTTOM, TOP,    NONE,   NONE  }, // 0110
  { LEFT,   TOP,    NONE,   NONE  }, // 0111
  { LEFT,   TOP,    NONE,   NONE  }, // 1000
  { BOTTOM, TOP,    NONE,   NONE  }, // 1001
  { LEFT,   BOTTOM, TOP,    RIGHT }, // 1010
  { TOP,    RIGHT,  NONE,   NONE  }, // 1011
  { LEFT,   RIGHT,  NONE,   NONE  }, // 1100
  { BOTTOM, RIGHT,  NONE,   NONE  }, // 1101
  { LEFT,   BOTTOM, NONE,   NONE  }, // 1110
  { NONE,   NONE,   NONE,   NONE  }  // 1111
}};

uint8_t computeCellConfiguration(const Grid2b& grid, std::size_t widthIndex, std::size_t heightIndex) {
  // Computing a single number according to the corners' values:
  //
  // 8 - 4
  // |   |
  // 1 - 2
  //
  // O - O            O - O            O - X            X - X
  // |   |  -> 0      |   |  -> 1      |   |  -> 5      |   |  -> 15
  // O - O            X - O            X - O            X - X

  return static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex    ))        // Bottom-left
       | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex    ) << 1u)  // Bottom-right
       | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex + 1) << 2u)  // Top-right
       | static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex + 1) << 3u); // Top-left
}

} // namespace

Mesh MarchingSquares::compute(const Grid2b& grid) {
  ZoneScopedN("MarchingSquares::compute");

  if (grid.getWidth() < 2 || grid.getHeight() < 2)
    throw std::invalid_argument("[MarchingSquares] The input grid's width & height must be at least 2.");

  Mesh mesh;
  Submesh& submesh = mesh.addSubmesh();
  std::vector<Vertex>& vertices = submesh.getVertices();
  std::vector<unsigned int>& indices = submesh.getTriangleIndices();

  const Vec2f globalOffset(static_cast<float>(grid.getWidth() - 1) * 0.5f, static_cast<float>(grid.getHeight() - 1) * 0.5f);

  for (std::size_t heightIndex = 0; heightIndex < grid.getHeight() - 1; ++heightIndex) {
    for (std::size_t widthIndex = 0; widthIndex < grid.getWidth() - 1; ++widthIndex) {
      const uint8_t cellConfig = computeCellConfiguration(grid, widthIndex, heightIndex);
      const std::array<int8_t, 4>& edgeIndices = linesIndices[cellConfig];
      const Vec2f localOffset(static_cast<float>(widthIndex), static_cast<float>(heightIndex));

      for (std::size_t edgeIndex = 0; edgeIndex < edgeIndices.size(); edgeIndex += 2) {
        if (edgeIndices[edgeIndex] == NONE)
          break;

        const Vec2f firstPoint  = edgeVertices[edgeIndices[edgeIndex    ]] - globalOffset + localOffset;
        const Vec2f secondPoint = edgeVertices[edgeIndices[edgeIndex + 1]] - globalOffset + localOffset;
        vertices.emplace_back(Vertex{ Vec3f(firstPoint, 0.f) });
        vertices.emplace_back(Vertex{ Vec3f(firstPoint, 0.f) });
        vertices.emplace_back(Vertex{ Vec3f(secondPoint, 0.f) });

        indices.emplace_back(static_cast<unsigned int>(vertices.size() - 3));
        indices.emplace_back(static_cast<unsigned int>(vertices.size() - 2));
        indices.emplace_back(static_cast<unsigned int>(vertices.size() - 1));
      }
    }
  }

  return mesh;
}

} // namespace Raz

1	#include "RaZ/Data/Grid2.hpp"
2	#include "RaZ/Data/MarchingSquares.hpp"
3	#include "RaZ/Data/Mesh.hpp"
4
5	#include "tracy/Tracy.hpp"
6
7	namespace Raz {
8
9	namespace {
10
11	constexpr std::array<Vec2f, 4> edgeVertices = {
12	Vec2f(0.5f, 0.f), // Bottom
13	Vec2f(1.f, 0.5f), // Right
14	Vec2f(0.5f, 1.f), // Top
15	Vec2f(0.f, 0.5f) // Left
16	};
17
18	enum VertexPosition {
19	NONE = -1,
20	BOTTOM = 0,
21	RIGHT = 1,
22	TOP = 2,
23	LEFT = 3
24	};
25
26	constexpr std::array<std::array<int8_t, 4>, 16> linesIndices = {{
27	{ NONE, NONE, NONE, NONE }, // 0000
28	{ LEFT, BOTTOM, NONE, NONE }, // 0001
29	{ BOTTOM, RIGHT, NONE, NONE }, // 0010
30	{ LEFT, RIGHT, NONE, NONE }, // 0011
31	{ TOP, RIGHT, NONE, NONE }, // 0100
32	{ LEFT, TOP, BOTTOM, RIGHT }, // 0101
33	{ BOTTOM, TOP, NONE, NONE }, // 0110
34	{ LEFT, TOP, NONE, NONE }, // 0111
35	{ LEFT, TOP, NONE, NONE }, // 1000
36	{ BOTTOM, TOP, NONE, NONE }, // 1001
37	{ LEFT, BOTTOM, TOP, RIGHT }, // 1010
38	{ TOP, RIGHT, NONE, NONE }, // 1011
39	{ LEFT, RIGHT, NONE, NONE }, // 1100
40	{ BOTTOM, RIGHT, NONE, NONE }, // 1101
41	{ LEFT, BOTTOM, NONE, NONE }, // 1110
42	{ NONE, NONE, NONE, NONE } // 1111
43	}};
44
45	uint8_t computeCellConfiguration(const Grid2b& grid, std::size_t widthIndex, std::size_t heightIndex) {	19✔
46	// Computing a single number according to the corners' values:
47	//
48	// 8 - 4
49	// \| \|
50	// 1 - 2
51	//
52	// O - O O - O O - X X - X
53	// \| \| -> 0 \| \| -> 1 \| \| -> 5 \| \| -> 15
54	// O - O X - O X - O X - X
55
56	return static_cast<uint8_t>(grid.getValue(widthIndex, heightIndex )) // Bottom-left	19✔
57	\| static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex ) << 1u) // Bottom-right	19✔
58	\| static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex + 1) << 2u) // Top-right	19✔
59	\| static_cast<uint8_t>(grid.getValue(widthIndex, heightIndex + 1) << 3u); // Top-left	19✔
60	}
61
62	} // namespace
63
64	Mesh MarchingSquares::compute(const Grid2b& grid) {	6✔
65	ZoneScopedN("MarchingSquares::compute");
66
67	if (grid.getWidth() < 2 \|\| grid.getHeight() < 2)	6✔
68	throw std::invalid_argument("[MarchingSquares] The input grid's width & height must be at least 2.");	2✔
69
70	Mesh mesh;	4✔
71	Submesh& submesh = mesh.addSubmesh();	4✔
72	std::vector<Vertex>& vertices = submesh.getVertices();	4✔
73	std::vector<unsigned int>& indices = submesh.getTriangleIndices();	4✔
74
75	const Vec2f globalOffset(static_cast<float>(grid.getWidth() - 1) * 0.5f, static_cast<float>(grid.getHeight() - 1) * 0.5f);	4✔
76
77	for (std::size_t heightIndex = 0; heightIndex < grid.getHeight() - 1; ++heightIndex) {	8✔
78	for (std::size_t widthIndex = 0; widthIndex < grid.getWidth() - 1; ++widthIndex) {	23✔
79	const uint8_t cellConfig = computeCellConfiguration(grid, widthIndex, heightIndex);	19✔
80	const std::array<int8_t, 4>& edgeIndices = linesIndices[cellConfig];	19✔
81	const Vec2f localOffset(static_cast<float>(widthIndex), static_cast<float>(heightIndex));	19✔
82
83	for (std::size_t edgeIndex = 0; edgeIndex < edgeIndices.size(); edgeIndex += 2) {	35✔
84	if (edgeIndices[edgeIndex] == NONE)	33✔
85	break;	17✔
86
87	const Vec2f firstPoint = edgeVertices[edgeIndices[edgeIndex ]] - globalOffset + localOffset;	16✔
88	const Vec2f secondPoint = edgeVertices[edgeIndices[edgeIndex + 1]] - globalOffset + localOffset;	16✔
89	vertices.emplace_back(Vertex{ Vec3f(firstPoint, 0.f) });	96✔
90	vertices.emplace_back(Vertex{ Vec3f(firstPoint, 0.f) });	96✔
91	vertices.emplace_back(Vertex{ Vec3f(secondPoint, 0.f) });	96✔
92
93	indices.emplace_back(static_cast<unsigned int>(vertices.size() - 3));	16✔
94	indices.emplace_back(static_cast<unsigned int>(vertices.size() - 2));	16✔
95	indices.emplace_back(static_cast<unsigned int>(vertices.size() - 1));	16✔
96	}
97	}
98	}
99
100	return mesh;	8✔
NEW 101	}	×
102
103	} // namespace Raz

Razakhel / RaZ / 15148066105

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous