uvgVPCCenc 1.2.0
uvgVPCCenc is an open-source real-time V-PCC encoder library written in C++ from scratch.
Loading...
Searching...
No Matches
utilsPatchGeneration.hpp
Go to the documentation of this file.
1/*****************************************************************************
2 * This file is part of uvgVPCCenc V-PCC encoder.
3 *
4 * Copyright (c) 2024-present, Tampere University, ITU/ISO/IEC, project contributors
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without modification,
8 * are permitted (subject to the limitations in the disclaimer below) provided that the following conditions are met:
9 *
10 * * Redistributions of source code must retain the above copyright notice, this
11 * list of conditions and the following disclaimer.
12 *
13 * * Redistributions in binary form must reproduce the above copyright notice, this
14 * list of conditions and the following disclaimer in the documentation and/or
15 * other materials provided with the distribution.
16 *
17 * * Neither the name of Tampere University, ITU/ISO/IEC nor the names of its
18 * contributors may be used to endorse or promote products derived from
19 * this software without specific prior written permission.
20 *
21 * NO EXPRESS OR IMPLIED LICENSES TO ANY PARTY'S PATENT RIGHTS ARE GRANTED BY THIS LICENSE.
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
24 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
25 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
26 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
27 * INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION HOWEVER CAUSED AND ON
29 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 * INCLUDING NEGLIGENCE OR OTHERWISE ARISING IN ANY WAY OUT OF THE USE OF THIS
32 ****************************************************************************/
33
35
36#pragma once
37
38#include <sys/types.h>
39
40#include <cstdint>
41#include <vector>
42
43#include <robin_hood.h>
44#include "utils/constants.hpp"
45#include "uvgutils/utils.hpp"
46#include "uvgutils/log.hpp"
47
48
49using namespace uvgvpcc_enc;
50
51// TODO(lf): how to handle this type of lut table variable ?
52// NOLINTNEXTLINE(cert-err58-cpp)
53static const std::array<std::vector<std::array<int, 3>>, 9> adjacentPointsSearch = {{
54 // Adjacent shift for squared distance 1
55 {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}},
56 // Adjacent shift for squared distance 2
57 {{1, 1, 0},
58 {1, -1, 0},
59 {-1, 1, 0},
60 {-1, -1, 0},
61 {0, 1, 1},
62 {0, 1, -1},
63 {0, -1, 1},
64 {0, -1, -1},
65 {1, 0, 1},
66 {-1, 0, 1},
67 {1, 0, -1},
68 {-1, 0, -1}},
69 // Adjacent shift for squared distance 3
70 {{1, 1, 1}, {1, 1, -1}, {1, -1, 1}, {1, -1, -1}, {-1, 1, 1}, {-1, 1, -1}, {-1, -1, 1}, {-1, -1, -1}},
71 // Adjacent shift for squared distance 4
72 {{2, 0, 0}, {-2, 0, 0}, {0, 2, 0}, {0, -2, 0}, {0, 0, 2}, {0, 0, -2}},
73 // Adjacent shift for squared distance 5
74 {{2, 1, 0}, {2, -1, 0}, {1, 2, 0}, {1, -2, 0}, {-1, 2, 0}, {-1, -2, 0}, {-2, 1, 0}, {-2, -1, 0},
75 {0, 2, 1}, {0, 2, -1}, {0, 1, 2}, {0, 1, -2}, {0, -1, 2}, {0, -1, -2}, {0, -2, 1}, {0, -2, -1},
76 {1, 0, 2}, {-1, 0, 2}, {2, 0, 1}, {-2, 0, 1}, {2, 0, -1}, {-2, 0, -1}, {1, 0, -2}, {-1, 0, -2}},
77 // Adjacent shift for squared distance 6
78 {{2, 1, 1}, {2, 1, -1}, {2, -1, 1}, {2, -1, -1}, {1, 2, 1}, {1, 2, -1}, {1, 1, 2}, {1, 1, -2},
79 {1, -1, 2}, {1, -1, -2}, {1, -2, 1}, {1, -2, -1}, {-1, 2, 1}, {-1, 2, -1}, {-1, 1, 2}, {-1, 1, -2},
80 {-1, -1, 2}, {-1, -1, -2}, {-1, -2, 1}, {-1, -2, -1}, {-2, 1, 1}, {-2, 1, -1}, {-2, -1, 1}, {-2, -1, -1}},
81 // Adjacent shift for squared distance 7 (does not exist in an integer grid)
82 {},
83 // Adjacent shift for squared distance 8
84 {{2, 2, 0},
85 {2, -2, 0},
86 {-2, 2, 0},
87 {-2, -2, 0},
88 {0, 2, 2},
89 {0, 2, -2},
90 {0, -2, 2},
91 {0, -2, -2},
92 {2, 0, 2},
93 {-2, 0, 2},
94 {2, 0, -2},
95 {-2, 0, -2}},
96 // Adjacent shift for squared distance 9
97 {{3, 0, 0}, {-3, 0, 0}, {0, 3, 0}, {0, -3, 0}, {0, 0, 3}, {0, 0, -3}, {2, 2, 1}, {2, 2, -1}, {2, 1, 2}, {2, 1, -2},
98 {2, -1, 2}, {2, -1, -2}, {2, -2, 1}, {2, -2, -1}, {1, 2, 2}, {1, 2, -2}, {1, -2, 2}, {1, -2, -2}, {-1, 2, 2}, {-1, 2, -2},
99 {-1, -2, 2}, {-1, -2, -2}, {-2, 2, 1}, {-2, 2, -1}, {-2, 1, 2}, {-2, 1, -2}, {-2, -1, 2}, {-2, -1, -2}, {-2, -2, 1}, {-2, -2, -1}},
100}};
101
102
103// All 122 shift vectors stored in a single contiguous block of memory
104static constexpr std::array<std::array<int, 3>, 122> adjacentPointsSearchFlat = {{
105 // Adjacent shift for squared distance 1 (Offset 0, Size 6)
106 {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1},
107
108 // Adjacent shift for squared distance 2 (Offset 6, Size 12)
109 {1, 1, 0}, {1, -1, 0}, {-1, 1, 0}, {-1, -1, 0}, {0, 1, 1}, {0, 1, -1},
110 {0, -1, 1}, {0, -1, -1}, {1, 0, 1}, {-1, 0, 1}, {1, 0, -1}, {-1, 0, -1},
111
112 // Adjacent shift for squared distance 3 (Offset 18, Size 8)
113 {1, 1, 1}, {1, 1, -1}, {1, -1, 1}, {1, -1, -1},
114 {-1, 1, 1}, {-1, 1, -1}, {-1, -1, 1}, {-1, -1, -1},
115
116 // Adjacent shift for squared distance 4 (Offset 26, Size 6)
117 {2, 0, 0}, {-2, 0, 0}, {0, 2, 0}, {0, -2, 0}, {0, 0, 2}, {0, 0, -2},
118
119 // Adjacent shift for squared distance 5 (Offset 32, Size 24)
120 {2, 1, 0}, {2, -1, 0}, {1, 2, 0}, {1, -2, 0}, {-1, 2, 0}, {-1, -2, 0}, {-2, 1, 0}, {-2, -1, 0},
121 {0, 2, 1}, {0, 2, -1}, {0, 1, 2}, {0, 1, -2}, {0, -1, 2}, {0, -1, -2}, {0, -2, 1}, {0, -2, -1},
122 {1, 0, 2}, {-1, 0, 2}, {2, 0, 1}, {-2, 0, 1}, {2, 0, -1}, {-2, 0, -1}, {1, 0, -2}, {-1, 0, -2},
123
124 // Adjacent shift for squared distance 6 (Offset 56, Size 24)
125 {2, 1, 1}, {2, 1, -1}, {2, -1, 1}, {2, -1, -1}, {1, 2, 1}, {1, 2, -1}, {1, 1, 2}, {1, 1, -2},
126 {1, -1, 2}, {1, -1, -2}, {1, -2, 1}, {1, -2, -1}, {-1, 2, 1}, {-1, 2, -1}, {-1, 1, 2}, {-1, 1, -2},
127 {-1, -1, 2}, {-1, -1, -2}, {-1, -2, 1}, {-1, -2, -1}, {-2, 1, 1}, {-2, 1, -1}, {-2, -1, 1}, {-2, -1, -1},
128
129 // Adjacent shift for squared distance 7 does not exist in an integer grid.
130
131 // Adjacent shift for squared distance 8 (Offset 80, Size 12)
132 {2, 2, 0}, {2, -2, 0}, {-2, 2, 0}, {-2, -2, 0}, {0, 2, 2}, {0, 2, -2},
133 {0, -2, 2}, {0, -2, -2}, {2, 0, 2}, {-2, 0, 2}, {2, 0, -2}, {-2, 0, -2},
134
135 // Adjacent shift for squared distance 9 (Offset 92, Size 30)
136 {3, 0, 0}, {-3, 0, 0}, {0, 3, 0}, {0, -3, 0}, {0, 0, 3}, {0, 0, -3}, {2, 2, 1}, {2, 2, -1}, {2, 1, 2}, {2, 1, -2},
137 {2, -1, 2}, {2, -1, -2}, {2, -2, 1}, {2, -2, -1}, {1, 2, 2}, {1, 2, -2}, {1, -2, 2}, {1, -2, -2}, {-1, 2, 2}, {-1, 2, -2},
138 {-1, -2, 2}, {-1, -2, -2}, {-2, 2, 1}, {-2, 2, -1}, {-2, 1, 2}, {-2, 1, -2}, {-2, -1, 2}, {-2, -1, -2}, {-2, -2, 1}, {-2, -2, -1}
139}};
140
141static constexpr std::array<size_t, 9> adjacentPointsSearchFlatOffsets = {
142 0,
143 6,
144 18,
145 26,
146 32,
147 56,
148 80,
149 80,
150 92
151};
152
153
154const std::array<uvgutils::VectorN<uint8_t, 3>, 114> patchColors = {{
155 // Red color is for points not being part of a patch before the 2D projection.
156 {139, 0, 0}, {165, 42, 42}, {178, 34, 34}, {220, 20, 60}, {255, 99, 71}, {255, 127, 80}, {205, 92, 92}, {240, 128, 128},
157 {233, 150, 122}, {250, 128, 114}, {255, 160, 122}, {255, 69, 0}, {255, 140, 0}, {255, 165, 0}, {255, 215, 0}, {184, 134, 11},
158 {218, 165, 32}, {238, 232, 170}, {189, 183, 107}, {240, 230, 140}, {255, 255, 0}, {32, 178, 170}, {0, 128, 128}, {0, 139, 139},
159 {0, 255, 255}, {0, 255, 255}, {224, 255, 255}, {0, 206, 209}, {72, 209, 204}, {175, 238, 238}, {176, 224, 230}, {95, 158, 160},
160 {70, 130, 180}, {100, 149, 237}, {0, 191, 255}, {30, 144, 255}, {173, 216, 230}, {135, 206, 235}, {135, 206, 250}, {25, 25, 112},
161 {0, 0, 128}, {0, 0, 139}, {0, 0, 205}, {0, 0, 255}, {65, 105, 225}, {138, 43, 226}, {75, 0, 130}, {72, 61, 139},
162 {106, 90, 205}, {123, 104, 238}, {147, 112, 219}, {139, 0, 139}, {148, 0, 211}, {153, 50, 204}, {186, 85, 211}, {128, 0, 128},
163 {216, 191, 216}, {221, 160, 221}, {238, 130, 238}, {255, 0, 255}, {218, 112, 214}, {199, 21, 133}, {219, 112, 147}, {255, 20, 147},
164 {255, 105, 180}, {255, 182, 193}, {255, 192, 203}, {250, 235, 215}, {245, 245, 220}, {255, 228, 196}, {255, 235, 205}, {245, 222, 179},
165 {255, 248, 220}, {255, 250, 205}, {250, 250, 210}, {255, 255, 224}, {139, 69, 19}, {160, 82, 45}, {210, 105, 30}, {205, 133, 63},
166 {244, 164, 96}, {222, 184, 135}, {210, 180, 140}, {188, 143, 143}, {255, 228, 181}, {255, 222, 173}, {255, 218, 185}, {255, 228, 225},
167 {255, 240, 245}, {250, 240, 230}, {253, 245, 230}, {255, 239, 213}, {255, 245, 238}, {245, 255, 250}, {112, 128, 144}, {119, 136, 153},
168 {176, 196, 222}, {230, 230, 250}, {255, 250, 240}, {240, 248, 255}, {248, 248, 255}, {240, 255, 240}, {255, 255, 240}, {240, 255, 255},
169 {255, 250, 250}, {0, 0, 0}, {105, 105, 105}, {128, 128, 128}, {169, 169, 169}, {192, 192, 192}, {211, 211, 211}, {220, 220, 220},
170 {245, 245, 245}, {255, 255, 255},
171}};
172
173// Look Up Table of the dot product's values depending on the projection plane and the point's PPI
174 // normalsDotProducts[i][j] is the dot product value of the current point's corresponding normal of PPI = i with the corresponding normal of PPI = j
175static const std::array<std::array<int8_t,6>, 6> normalsDotProducts = {{
176
177 {1, 0, 0, -1, 0, 0},
178
179 {0, 1, 0, 0, -1, 0},
180
181 {0, 0, 1, 0, 0, -1},
182
183 {-1, 0, 0, 1, 0, 0},
184
185 {0, -1, 0, 0, 1, 0},
186
187 {0, 0, -1, 0, 0, 1}
188
189}};
190
191
192template <typename T, typename TT>
193inline double dotProduct(const std::array<T, 3>& arr1, const std::array<TT, 3>& arr2) {
194 return arr1[0] * arr2[0] + arr1[1] * arr2[1] + arr1[2] * arr2[2];
195}
196
197// Hash function for vector3
198template <typename T>
199struct vector3Hash {
200 size_t operator()(const uvgutils::VectorN<T, 3>& vector) const {
201 std::hash<T> hasher;
202 size_t hash = 0;
203 for (const auto& elem : vector) {
204 // Use a simple hash combining algorithm
205 hash ^= hasher(elem) + 0x9e3779b9 + (hash << 6U) + (hash >> 2U);
206 }
207 return hash;
208 }
209};
210
211// REFINE SEGMENTATION CLASSES AND STRUCTS
212enum class VoxClass : uint8_t {
213 NO_EDGE = 0x00, // one ppi-vaue in a voxel
214 INDIRECT_EDGE = 0x01, // adjcent voxels of M_DIRECT_EDGE, S_DIRECT_EDGE
215 M_DIRECT_EDGE = 0x10, // multiple points && more than two ppi-values in a voxel TODO(lf)verify if typo -> (more than one instead no ?)
216 S_DIRECT_EDGE = 0x11 // single-point in a voxel, considered as a direct edge-voxel
217};
218
219struct VoxelAttribute {
220 bool updateFlag_;
221 VoxClass voxClass_;
222 size_t voxPPI_;
223 std::array<size_t, 6> voxScore_;
224 // Voxel score is a PPI histogram : how many points inside the voxel is associated with each projection planes //
225
228};
229
230
231
232template <typename keyType>
233inline keyType location1DFromCoordinates(const int x, const int y, const int z, const size_t gdb, const size_t gdb2) {
234 return static_cast<keyType>(x) + (static_cast<keyType>(y) << gdb) + (static_cast<keyType>(z) << gdb2);
235}
236
237template <typename keyType>
238inline keyType location1DFromPoint(const uvgutils::VectorN<typeGeometryInput, 3>& point, const size_t gdb, const size_t gdb2) {
239 return location1DFromCoordinates<keyType>(point[0],point[1],point[2],gdb,gdb2);
240}
241
242// The voxelization is done so to have those three vectors sharing the same order (that is sharing the same voxel index) :
243// -> A list of voxel (vector of coordinates)
244// -> A list of list of points (vector of vector of point index). This associate a voxel with the points inside it.
245// -> A list of voxel PPI (vector of PPI (int))
246//
247// Example with a voxel index i:
248// voxelizedPointsGeometry[i] stores the coordinate of the voxel i
249// voxelIdToPointsId[i] stores the index of the points inside the voxel i
250// voxelsPPIs[i] stores the PPI of the voxel i
251//
252// The use of a map is needed as several points can be inside one voxel. We want to find in a fast way if the current point resides in a voxel
253// that has already been created. For an input point j: voxelCoordToVoxelIndex[ voxelCoordsOf(j) ] = i
254//
255// This structure makes computation easier for the patch generation and for applying voxel data to points data.
256// To achieve this, we need a temporary map that interfaces the voxel coordinates with the voxel index in those three list.
257
258// voxelizedPointsGeometry -> list of the voxels. That is, a list of the coordinates of the voxels.
259// voxelIdToPointsId -> For each voxel, stores the index of the points inside. A voxel is defined by a voxel index, that is given by the
260// filling order of the vector. Thus, the third voxel to be added to this structure will have a voxel index of 2.
261// voxelCoordToVoxelIndex -> Temporary structure. Associate a voxel to its index in 'voxelIdToPointsId' (its voxel index). This structure is a
262// map whose key is a voxel coordinate and the value is a voxel index.
263//
264// For each point if the input point cloud :
265// Compute the coordinates of the voxel inside which the current point should be.
266// If those voxel coordinates are already in the map 'voxelCoordToVoxelIndex':
267// Add the current input point index to the list of points index of the found voxel.
268// That is, add the current input point index to the list of points of the voxel in 'voxelIdToPointsId'
269// If those voxel coordinates are not in the map 'voxelCoordToVoxelIndex':
270// Create a new item in the map 'voxelCoordToVoxelIndex'. This associates the voxel coordinates to its voxel index (the current size
271// of the list of voxel === the index of this voxel in the list of voxel). Add a new voxel to 'voxelIdToPointsId'. This associates the
272// voxel index (the current size of the list of voxel === the index of this voxel in the list of voxel) to an empty list of input
273// point index. Create a new voxel by adding the voxel coordinates in the voxel list 'voxelizedPointsGeometry'. Add the current input
274// point index to the list of points index of the new voxel. That is, add the current input point index to the list of points of the
275// voxel in 'voxelIdToPointsId'
276
277// Notice that in the refined segmentation, the inputPointsGeometry can be the voxelizedPointsGeometry. Indeed, when the voxelization is
278// activated, the refined segmentation is applying a second voxelization step. The created voxelized point cloud is then the result of two
279// voxelizations.
280inline void voxelization(
281 const std::vector<uvgutils::VectorN<typeGeometryInput, 3>>& inputPointsGeometry,
282 std::vector<uvgutils::VectorN<typeGeometryInput, 3>>& voxelizedPointsGeometry,
283 std::vector<size_t>& pointsIdToVoxelId,
284 const size_t inputBitResolution,
285 const size_t outputBitResolution
286)
287{
288 uvgutils::Logger::log<uvgutils::LogLevel::TRACE>("PATCH GENERATION", "Voxelization from " + std::to_string(inputBitResolution) + " to " +
289 std::to_string(outputBitResolution) + " bits of resolution.\n");
290 pointsIdToVoxelId.resize(inputPointsGeometry.size());
291
292 const size_t voxelizationShift = inputBitResolution - outputBitResolution;
293 const typeGeometryInput shift = static_cast<typeGeometryInput>(voxelizationShift);
294
295 const size_t approximateVoxelCount = 1U << (outputBitResolution * 2U);
296 voxelizedPointsGeometry.reserve(approximateVoxelCount);
297
298 robin_hood::unordered_map<uvgutils::VectorN<typeGeometryInput, 3>, size_t, vector3Hash<typeGeometryInput>> voxelCoordToVoxelIndex;
299 voxelCoordToVoxelIndex.reserve(approximateVoxelCount);
300 size_t voxelIndex = 0;
301 for (size_t inputPointIndex = 0; inputPointIndex < inputPointsGeometry.size(); ++inputPointIndex) {
302 const uvgutils::VectorN<typeGeometryInput, 3> & inputPoint = inputPointsGeometry[inputPointIndex];
303
304 uvgutils::VectorN<typeGeometryInput, 3> voxCoord{static_cast<typeGeometryInput>(static_cast<uint32_t>(inputPoint[0]) >> shift),
305 static_cast<typeGeometryInput>(static_cast<uint32_t>(inputPoint[1]) >> shift),
306 static_cast<typeGeometryInput>(static_cast<uint32_t>(inputPoint[2]) >> shift)};
307
308 auto [it, inserted] = voxelCoordToVoxelIndex.try_emplace(voxCoord, voxelIndex);
309 if (inserted) {
310 voxelizedPointsGeometry.emplace_back(voxCoord);
311 voxelIndex++;
312 }
313 pointsIdToVoxelId[inputPointIndex] = voxelCoordToVoxelIndex[voxCoord];
314 }
315}
uvgutils::VectorN
Definition utils.hpp:50
uvgvpcc_enc
Definition uvgvpccenc.hpp:49
uvgvpcc_enc::typeGeometryInput
uint16_t typeGeometryInput
Definition constants.hpp:49
VoxelAttribute
Definition utilsPatchGeneration.hpp:219
VoxelAttribute::updateFlag_
bool updateFlag_
Definition utilsPatchGeneration.hpp:220
VoxelAttribute::voxScore_
std::array< size_t, 6 > voxScore_
Definition utilsPatchGeneration.hpp:223
VoxelAttribute::voxPPI_
size_t voxPPI_
Definition utilsPatchGeneration.hpp:222
VoxelAttribute::VoxelAttribute
VoxelAttribute()
Definition utilsPatchGeneration.hpp:226
VoxelAttribute::voxClass_
VoxClass voxClass_
Definition utilsPatchGeneration.hpp:221
vector3Hash
Definition utilsPatchGeneration.hpp:199
vector3Hash::operator()
size_t operator()(const uvgutils::VectorN< T, 3 > &vector) const
Definition utilsPatchGeneration.hpp:200
VoxClass
VoxClass
Definition utilsPatchGeneration.hpp:212
location1DFromCoordinates
keyType location1DFromCoordinates(const int x, const int y, const int z, const size_t gdb, const size_t gdb2)
Definition utilsPatchGeneration.hpp:233
dotProduct
double dotProduct(const std::array< T, 3 > &arr1, const std::array< TT, 3 > &arr2)
Definition utilsPatchGeneration.hpp:193
patchColors
const std::array< uvgutils::VectorN< uint8_t, 3 >, 114 > patchColors
Definition utilsPatchGeneration.hpp:154
location1DFromPoint
keyType location1DFromPoint(const uvgutils::VectorN< typeGeometryInput, 3 > &point, const size_t gdb, const size_t gdb2)
Definition utilsPatchGeneration.hpp:238
voxelization
void voxelization(const std::vector< uvgutils::VectorN< typeGeometryInput, 3 > > &inputPointsGeometry, std::vector< uvgutils::VectorN< typeGeometryInput, 3 > > &voxelizedPointsGeometry, std::vector< size_t > &pointsIdToVoxelId, const size_t inputBitResolution, const size_t outputBitResolution)
Definition utilsPatchGeneration.hpp:280
Generated by doxygen 1.9.8