uvgVPCCenc 1.1.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 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 the Tampere University or 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 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
25 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26 * INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION HOWEVER CAUSED AND ON
28 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * INCLUDING NEGLIGENCE OR OTHERWISE ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ****************************************************************************/
32
34
35#pragma once
36
37#include "utils/utils.hpp"
38#include "uvgvpcc/log.hpp"
39#include <cstdint>
40#include <fstream>
41#include <vector>
42#include "robin_hood.h"
43
44using namespace uvgvpcc_enc;
45
46
47// TODO(lf): how to handle this type of lut table variable ?
48// NOLINTNEXTLINE(cert-err58-cpp)
49static const std::array<std::vector<Vector3<int32_t>>, 9> adjacentPointsSearch = {{
50 // Adjacent shift for squared distance 1
51 {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}},
52 // Adjacent shift for squared distance 2
53 {{1, 1, 0},
54 {1, -1, 0},
55 {-1, 1, 0},
56 {-1, -1, 0},
57 {0, 1, 1},
58 {0, 1, -1},
59 {0, -1, 1},
60 {0, -1, -1},
61 {1, 0, 1},
62 {-1, 0, 1},
63 {1, 0, -1},
64 {-1, 0, -1}},
65 // Adjacent shift for squared distance 3
66 {{1, 1, 1}, {1, 1, -1}, {1, -1, 1}, {1, -1, -1}, {-1, 1, 1}, {-1, 1, -1}, {-1, -1, 1}, {-1, -1, -1}},
67 // Adjacent shift for squared distance 4
68 {{2, 0, 0}, {-2, 0, 0}, {0, 2, 0}, {0, -2, 0}, {0, 0, 2}, {0, 0, -2}},
69 // Adjacent shift for squared distance 5
70 {{2, 1, 0}, {2, -1, 0}, {1, 2, 0}, {1, -2, 0}, {-1, 2, 0}, {-1, -2, 0}, {-2, 1, 0}, {-2, -1, 0},
71 {0, 2, 1}, {0, 2, -1}, {0, 1, 2}, {0, 1, -2}, {0, -1, 2}, {0, -1, -2}, {0, -2, 1}, {0, -2, -1},
72 {1, 0, 2}, {-1, 0, 2}, {2, 0, 1}, {-2, 0, 1}, {2, 0, -1}, {-2, 0, -1}, {1, 0, -2}, {-1, 0, -2}},
73 // Adjacent shift for squared distance 6
74 {{2, 1, 1}, {2, 1, -1}, {2, -1, 1}, {2, -1, -1}, {1, 2, 1}, {1, 2, -1}, {1, 1, 2}, {1, 1, -2},
75 {1, -1, 2}, {1, -1, -2}, {1, -2, 1}, {1, -2, -1}, {-1, 2, 1}, {-1, 2, -1}, {-1, 1, 2}, {-1, 1, -2},
76 {-1, -1, 2}, {-1, -1, -2}, {-1, -2, 1}, {-1, -2, -1}, {-2, 1, 1}, {-2, 1, -1}, {-2, -1, 1}, {-2, -1, -1}},
77 // Adjacent shift for squared distance 7 (does not exist in an integer grid)
78 {},
79 // Adjacent shift for squared distance 8
80 {{2, 2, 0},
81 {2, -2, 0},
82 {-2, 2, 0},
83 {-2, -2, 0},
84 {0, 2, 2},
85 {0, 2, -2},
86 {0, -2, 2},
87 {0, -2, -2},
88 {2, 0, 2},
89 {-2, 0, 2},
90 {2, 0, -2},
91 {-2, 0, -2}},
92 // Adjacent shift for squared distance 9
93 {{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},
94 {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},
95 {-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}},
96}};
97
98template <typename T, typename TT>
99inline double dotProduct(const std::array<T, 3>& arr1, const std::array<TT, 3>& arr2) {
100 return arr1[0] * arr2[0] + arr1[1] * arr2[1] + arr1[2] * arr2[2];
101}
102
103
104// Hash function for vector3
105template <typename T>
107 size_t operator()(const Vector3<T>& vector) const {
108 std::hash<T> hasher;
109 size_t hash = 0;
110 for (const auto& elem : vector) {
111 // Use a simple hash combining algorithm
112 hash ^= hasher(elem) + 0x9e3779b9 + (hash << 6U) + (hash >> 2U);
113 }
114 return hash;
115 }
116};
117
118
119
120
121
122
123// The voxelization is done so to have those three vectors sharing the same order (that is sharing the same voxel index) :
124// -> A list of voxel (vector of coordinates)
125// -> A list of list of points (vector of vector of point index). This associate a voxel with the points inside it.
126// -> A list of voxel PPI (vector of PPI (int))
127//
128// Example with a voxel index i:
129// voxelizedPointsGeometry[i] stores the coordinate of the voxel i
130// voxelIdToPointsId[i] stores the index of the points inside the voxel i
131// voxelsPPIs[i] stores the PPI of the voxel i
132//
133// 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
134// that has already been created. For an input point j: voxelCoordToVoxelIndex[ voxelCoordsOf(j) ] = i
135//
136// This structure makes computation easier for the patch generation and for applying voxel data to points data.
137// To achieve this, we need a temporary map that interfaces the voxel coordinates with the voxel index in those three list.
138
139// voxelizedPointsGeometry -> list of the voxels. That is, a list of the coordinates of the voxels.
140// voxelIdToPointsId -> For each voxel, stores the index of the points inside. A voxel is defined by a voxel index, that is given by the
141// filling order of the vector. Thus, the third voxel to be added to this structure will have a voxel index of 2.
142// voxelCoordToVoxelIndex -> Temporary structure. Associate a voxel to its index in 'voxelIdToPointsId' (its voxel index). This structure is a
143// map whose key is a voxel coordinate and the value is a voxel index.
144//
145// For each point if the input point cloud :
146// Compute the coordinates of the voxel inside which the current point should be.
147// If those voxel coordinates are already in the map 'voxelCoordToVoxelIndex':
148// Add the current input point index to the list of points index of the found voxel.
149// That is, add the current input point index to the list of points of the voxel in 'voxelIdToPointsId'
150// If those voxel coordinates are not in the map 'voxelCoordToVoxelIndex':
151// Create a new item in the map 'voxelCoordToVoxelIndex'. This associates the voxel coordinates to its voxel index (the current size
152// of the list of voxel === the index of this voxel in the list of voxel). Add a new voxel to 'voxelIdToPointsId'. This associates the
153// 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
154// point index. Create a new voxel by adding the voxel coordinates in the voxel list 'voxelizedPointsGeometry'. Add the current input
155// 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
156// voxel in 'voxelIdToPointsId'
157
158
159// Notice that in the refined segmentation, the inputPointsGeometry can be the voxelizedPointsGeometry. Indeed, when the voxelization is
160// activated, the refined segmentation is applying a second voxelization step. The created voxelized point cloud is then the result of two
161// voxelizations.
162inline void voxelization(
163 const std::vector<Vector3<typeGeometryInput>>& inputPointsGeometry,
164 std::vector<Vector3<typeGeometryInput>>& voxelizedPointsGeometry,
165 std::vector<std::vector<size_t>>& voxelIdToPointsId,
166 const size_t inputBitResolution,
167 const size_t outputBitResolution)
168{
169 Logger::log<LogLevel::TRACE>("PATCH GENERATION",
170 "Voxelization from " + std::to_string(inputBitResolution) + " to " + std::to_string(outputBitResolution) + " bits of resolution.\n");
171
172 const size_t voxelizationShift = inputBitResolution - outputBitResolution;
173 const typeGeometryInput shift = static_cast<typeGeometryInput>(voxelizationShift);
174
175 const size_t approximateVoxelCount = 1U << (outputBitResolution * 2U);
176 voxelizedPointsGeometry.reserve(approximateVoxelCount);
177 voxelIdToPointsId.reserve(approximateVoxelCount);
178
180 voxelCoordToVoxelIndex.reserve(approximateVoxelCount);
181
182 const size_t inputSize = inputPointsGeometry.size();
183 for (size_t inputPointIndex = 0; inputPointIndex < inputSize; ++inputPointIndex) {
184 const Vector3<typeGeometryInput> & inputPoint = inputPointsGeometry[inputPointIndex];
185
187 static_cast<typeGeometryInput>(static_cast<uint32_t>(inputPoint[0]) >> shift),
188 static_cast<typeGeometryInput>(static_cast<uint32_t>(inputPoint[1]) >> shift),
189 static_cast<typeGeometryInput>(static_cast<uint32_t>(inputPoint[2]) >> shift)
190 };
191
192 size_t voxelIndex = voxelizedPointsGeometry.size();
193 auto [it, inserted] = voxelCoordToVoxelIndex.try_emplace(voxCoord, voxelIndex);
194 if (inserted) {
195 voxelizedPointsGeometry.emplace_back(voxCoord);
196 voxelIdToPointsId.emplace_back();
197 voxelIdToPointsId.back().reserve(16);
198 }
199
200 voxelIdToPointsId[it->second].push_back(inputPointIndex);
201 }
202}
Definition robin_hood.h:921
std::pair< iterator, bool > try_emplace(const key_type &key, Args &&... args)
Definition robin_hood.h:1835
void reserve(size_t c)
Definition robin_hood.h:2084
Definition utils.hpp:56
Definition log.hpp:48
uint16_t typeGeometryInput
Definition utils.hpp:46
Definition utilsPatchGeneration.hpp:106
size_t operator()(const Vector3< T > &vector) const
Definition utilsPatchGeneration.hpp:107
void voxelization(const std::vector< Vector3< typeGeometryInput > > &inputPointsGeometry, std::vector< Vector3< typeGeometryInput > > &voxelizedPointsGeometry, std::vector< std::vector< size_t > > &voxelIdToPointsId, const size_t inputBitResolution, const size_t outputBitResolution)
Definition utilsPatchGeneration.hpp:162
double dotProduct(const std::array< T, 3 > &arr1, const std::array< TT, 3 > &arr2)
Definition utilsPatchGeneration.hpp:99