blender
/
blender
136
406
Fork 589
Code Issues 6.2k Pull Requests 757 Projects 19 Wiki Activity

3D Texturing: Replace pointers with indexes in pbvh_uv_islands 

Replace the pointers in the MeshEdge with indexes, removing MeshPrimitive and MeshVertex.

Code cleanup proposed by the geometry nodes to make the data structures more reusable by
other areas of Blender as well. Old implementation was to focused to the texture painting.

Initial the idea was to do the same with the data structures in UVIslands, but there some
concerns were raised that requires a different design than expected from a clean-up patch.

Concerns raised about converting UVIslands:
* Maps between UVPrimitive, UVEdge and UVVertex will be stored inside the UVIsland.
   During UVIsland extraction detected islands can be merged. When they are merged all
   Indexes should be updated.
* It is not possible to pre-allocate all buffers as they grow, what will lead to more re-allocations. The current
   implementation uses a VectorList to ensure that re-allocations don't require the data to be
   moved to the newly allocated memory. We could store some information about last used
   sizes in runtime data to reduce the re-allocation overhead.
* Solution would require index based access inside a VectorList, which might increase the
   complexity.
* UVIslands during 3d texturing is used as intermediate data, the final data is stored as PackedPixelRows.
   We could proceed converting UVIslands as well, but that would lower the performance noticeably.
   3D texturing has performance requirements, so when doing so we should make sure that
   it matches that as well.

Reviewed By: HooglyBoogly

Maniphest Tasks: T101740

Differential Revision: https://developer.blender.org/D16752
This commit is contained in:
Jeroen Bakker 2023-01-12 08:35:14 +01:00 committed by Jeroen Bakker
parent 0349a6e6e0
commit b9177014b6
Notes: blender-bot 2023-02-14 08:38:14 +01:00 
Referenced by issue #101740, 3D Texturing: Use struct of arrays for UV Islands (pbvh)
4 changed files with 366 additions and 300 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

2
source/blender/blenkernel/BKE_pbvh_pixels.hh
View File

@ -51,7 +51,7 @@ struct PaintGeometryPrimitives {
int64_t mem_size() const
{
return size() * sizeof(int3);
return this->vert_indices.as_span().size_in_bytes();
}
};

40
source/blender/blenkernel/intern/pbvh_pixels.cc
View File

@ -1,6 +1,7 @@
/* SPDX-License-Identifier: GPL-2.0-or-later
* Copyright 2022 Blender Foundation. All rights reserved. */
#include "BKE_attribute.hh"
#include "BKE_customdata.h"
#include "BKE_mesh.h"
#include "BKE_mesh_mapping.h"
@ -105,10 +106,10 @@ static void update_geom_primitives(PBVH &pbvh, const uv_islands::MeshData &mesh_
{
PBVHData &pbvh_data = BKE_pbvh_pixels_data_get(pbvh);
pbvh_data.clear_data();
for (const uv_islands::MeshPrimitive &mesh_primitive : mesh_data.primitives) {
pbvh_data.geom_primitives.append(int3(mesh_primitive.vertices[0].vertex->v,
mesh_primitive.vertices[1].vertex->v,
mesh_primitive.vertices[2].vertex->v));
for (const MLoopTri &looptri : mesh_data.looptris) {
pbvh_data.geom_primitives.append(int3(mesh_data.loops[looptri.tri[0]].v,
mesh_data.loops[looptri.tri[1]].v,
mesh_data.loops[looptri.tri[2]].v));
}
}
@ -134,7 +135,7 @@ struct UVPrimitiveLookup {
for (VectorList<uv_islands::UVPrimitive>::UsedVector &uv_primitives :
uv_island.uv_primitives) {
for (uv_islands::UVPrimitive &uv_primitive : uv_primitives) {
lookup[uv_primitive.primitive->index].append_as(Entry(&uv_primitive, uv_island_index));
lookup[uv_primitive.primitive_i].append_as(Entry(&uv_primitive, uv_island_index));
}
}
uv_island_index++;
@ -143,11 +144,11 @@ struct UVPrimitiveLookup {
};
struct EncodePixelsUserData {
const uv_islands::MeshData *mesh_data;
Image *image;
ImageUser *image_user;
PBVH *pbvh;
Vector<PBVHNode *> *nodes;
const float2 *ldata_uv;
const uv_islands::UVIslandsMask *uv_masks;
/** Lookup to retrieve the UV primitives based on the primitive index. */
const UVPrimitiveLookup *uv_primitive_lookup;
@ -158,6 +159,7 @@ static void do_encode_pixels(void *__restrict userdata,
const TaskParallelTLS *__restrict /*tls*/)
{
EncodePixelsUserData *data = static_cast<EncodePixelsUserData *>(userdata);
const uv_islands::MeshData &mesh_data = *data->mesh_data;
Image *image = data->image;
ImageUser image_user = *data->image_user;
PBVHNode *node = (*data->nodes)[n];
@ -183,9 +185,9 @@ static void do_encode_pixels(void *__restrict userdata,
data->uv_primitive_lookup->lookup[geom_prim_index]) {
uv_islands::UVBorder uv_border = entry.uv_primitive->extract_border();
float2 uvs[3] = {
entry.uv_primitive->get_uv_vertex(0)->uv - tile_offset,
entry.uv_primitive->get_uv_vertex(1)->uv - tile_offset,
entry.uv_primitive->get_uv_vertex(2)->uv - tile_offset,
entry.uv_primitive->get_uv_vertex(mesh_data, 0)->uv - tile_offset,
entry.uv_primitive->get_uv_vertex(mesh_data, 1)->uv - tile_offset,
entry.uv_primitive->get_uv_vertex(mesh_data, 2)->uv - tile_offset,
};
const float minv = clamp_f(min_fff(uvs[0].y, uvs[1].y, uvs[2].y), 0.0f, 1.0f);
const int miny = floor(minv * image_buffer->y);
@ -355,16 +357,16 @@ static void update_pixels(PBVH *pbvh, Mesh *mesh, Image *image, ImageUser *image
return;
}
const float2 *ldata_uv = static_cast<const float2 *>(
CustomData_get_layer(&mesh->ldata, CD_PROP_FLOAT2));
if (ldata_uv == nullptr) {
const StringRef active_uv_name = CustomData_get_active_layer_name(&mesh->ldata, CD_PROP_FLOAT2);
if (active_uv_name.is_empty()) {
return;
}
uv_islands::MeshData mesh_data({pbvh->looptri, pbvh->totprim},
{pbvh->mloop, mesh->totloop},
pbvh->totvert,
{ldata_uv, mesh->totloop});
const AttributeAccessor attributes = mesh->attributes();
const VArraySpan<float2> uv_map = attributes.lookup<float2>(active_uv_name, ATTR_DOMAIN_CORNER);
uv_islands::MeshData mesh_data(
{pbvh->looptri, pbvh->totprim}, {pbvh->mloop, mesh->totloop}, pbvh->totvert, uv_map);
uv_islands::UVIslands islands(mesh_data);
uv_islands::UVIslandsMask uv_masks;
@ -380,20 +382,20 @@ static void update_pixels(PBVH *pbvh, Mesh *mesh, Image *image, ImageUser *image
ushort2(tile_buffer->x, tile_buffer->y));
BKE_image_release_ibuf(image, tile_buffer, nullptr);
}
uv_masks.add(islands);
uv_masks.add(mesh_data, islands);
uv_masks.dilate(image->seam_margin);
islands.extract_borders();
islands.extend_borders(uv_masks);
islands.extend_borders(mesh_data, uv_masks);
update_geom_primitives(*pbvh, mesh_data);
UVPrimitiveLookup uv_primitive_lookup(mesh_data.looptris.size(), islands);
EncodePixelsUserData user_data;
user_data.mesh_data = &mesh_data;
user_data.pbvh = pbvh;
user_data.image = image;
user_data.image_user = image_user;
user_data.ldata_uv = ldata_uv;
user_data.nodes = &nodes_to_update;
user_data.uv_primitive_lookup = &uv_primitive_lookup;
user_data.uv_masks = &uv_masks;

480
source/blender/blenkernel/intern/pbvh_uv_islands.cc
View File

@ -28,27 +28,40 @@ static void uv_primitive_append_to_uv_vertices(UVPrimitive &uv_primitive)
}
/* -------------------------------------------------------------------- */
/** \name MeshPrimitive
/** \name Mesh Primitives
* \{ */
MeshUVVert *MeshPrimitive::get_other_uv_vertex(const MeshVertex *v1, const MeshVertex *v2)
int primitive_get_other_uv_vertex(const MeshData &mesh_data,
const MLoopTri &looptri,
const int v1,
const int v2)
{
BLI_assert(vertices[0].vertex == v1 || vertices[1].vertex == v1 || vertices[2].vertex == v1);
BLI_assert(vertices[0].vertex == v2 || vertices[1].vertex == v2 || vertices[2].vertex == v2);
for (MeshUVVert &uv_vertex : vertices) {
if (!ELEM(uv_vertex.vertex, v1, v2)) {
return &uv_vertex;
const Span<MLoop> mesh_loops = mesh_data.loops;
BLI_assert(ELEM(v1,
mesh_loops[looptri.tri[0]].v,
mesh_loops[looptri.tri[1]].v,
mesh_loops[looptri.tri[2]].v));
BLI_assert(ELEM(v2,
mesh_loops[looptri.tri[0]].v,
mesh_loops[looptri.tri[1]].v,
mesh_loops[looptri.tri[2]].v));
for (const int loop : looptri.tri) {
const int vert = mesh_loops[loop].v;
if (vert != v1 && vert != v2) {
return vert;
}
}
return nullptr;
return -1;
}
bool MeshPrimitive::has_shared_uv_edge(const MeshPrimitive *other) const
bool primitive_has_shared_uv_edge(const Span<float2> uv_map,
const MLoopTri &looptri,
const MLoopTri &other)
{
int shared_uv_verts = 0;
for (const MeshUVVert &vert : vertices) {
for (const MeshUVVert &other_vert : other->vertices) {
if (vert.uv == other_vert.uv) {
for (const int loop : looptri.tri) {
for (const int other_loop : other.tri) {
if (uv_map[loop] == uv_map[other_loop]) {
shared_uv_verts += 1;
}
}
@ -56,33 +69,34 @@ bool MeshPrimitive::has_shared_uv_edge(const MeshPrimitive *other) const
return shared_uv_verts >= 2;
}
static const MeshUVVert &get_uv_vert(const MeshPrimitive &mesh_primitive, const MeshVertex *vert)
static int get_uv_loop(const MeshData &mesh_data, const MLoopTri &looptri, const int vert)
{
for (const MeshUVVert &uv_vert : mesh_primitive.vertices) {
if (uv_vert.vertex == vert) {
return uv_vert;
for (const int loop : looptri.tri) {
if (mesh_data.loops[loop].v == vert) {
return loop;
}
}
BLI_assert_unreachable();
return mesh_primitive.vertices[0];
return looptri.tri[0];
}
static bool has_vertex(const MeshPrimitive &mesh_primitive, const MeshVertex &mesh_vertex)
static bool has_vertex(const MeshData &mesh_data, const MLoopTri &looptri, const int vert)
{
for (int i = 0; i < 3; i++) {
if (mesh_primitive.vertices[i].vertex == &mesh_vertex) {
const int vert_i = mesh_data.loops[looptri.tri[i]].v;
if (vert_i == vert) {
return true;
}
}
return false;
}
rctf MeshPrimitive::uv_bounds() const
rctf primitive_uv_bounds(const MLoopTri &looptri, const Span<float2> uv_map)
{
rctf result;
BLI_rctf_init_minmax(&result);
for (const MeshUVVert &uv_vertex : vertices) {
BLI_rctf_do_minmax_v(&result, uv_vertex.uv);
for (const int loop : looptri.tri) {
BLI_rctf_do_minmax_v(&result, uv_map[loop]);
}
return result;
}
@ -93,43 +107,13 @@ rctf MeshPrimitive::uv_bounds() const
/** \name MeshData
* \{ */
static void mesh_data_init_vertices(MeshData &mesh_data)
{
mesh_data.vertices.reserve(mesh_data.verts_num);
for (int64_t i = 0; i < mesh_data.verts_num; i++) {
MeshVertex vert;
vert.v = i;
mesh_data.vertices.append(vert);
}
}
static void mesh_data_init_primitives(MeshData &mesh_data)
{
mesh_data.primitives.reserve(mesh_data.looptris.size());
for (int64_t i = 0; i < mesh_data.looptris.size(); i++) {
const MLoopTri &tri = mesh_data.looptris[i];
MeshPrimitive primitive;
primitive.index = i;
primitive.poly = tri.poly;
for (int j = 0; j < 3; j++) {
MeshUVVert uv_vert;
uv_vert.loop = tri.tri[j];
uv_vert.vertex = &mesh_data.vertices[mesh_data.loops[uv_vert.loop].v];
uv_vert.uv = mesh_data.mloopuv[uv_vert.loop];
primitive.vertices.append(uv_vert);
}
mesh_data.primitives.append(primitive);
}
}
static void mesh_data_init_edges(MeshData &mesh_data)
{
mesh_data.edges.reserve(mesh_data.looptris.size() * 2);
EdgeHash *eh = BLI_edgehash_new_ex(__func__, mesh_data.looptris.size() * 3);
for (int64_t i = 0; i < mesh_data.looptris.size(); i++) {
const MLoopTri &tri = mesh_data.looptris[i];
MeshPrimitive &primitive = mesh_data.primitives[i];
Vector<int, 3> edges;
for (int j = 0; j < 3; j++) {
int v1 = mesh_data.loops[tri.tri[j]].v;
int v2 = mesh_data.loops[tri.tri[(j + 1) % 3]].v;
@ -144,82 +128,96 @@ static void mesh_data_init_edges(MeshData &mesh_data)
edge_index = mesh_data.edges.size();
*edge_index_ptr = POINTER_FROM_INT(edge_index + 1);
MeshEdge edge;
edge.vert1 = &mesh_data.vertices[v1];
edge.vert2 = &mesh_data.vertices[v2];
edge.vert1 = v1;
edge.vert2 = v2;
mesh_data.edges.append(edge);
MeshEdge *edge_ptr = &mesh_data.edges.last();
mesh_data.vertices[v1].edges.append(edge_ptr);
mesh_data.vertices[v2].edges.append(edge_ptr);
mesh_data.vert_to_edge_map.add(edge_index, v1, v2);
}
MeshEdge *edge = &mesh_data.edges[edge_index];
edge->primitives.append(&primitive);
primitive.edges.append(edge);
edges.append(edge_index);
}
mesh_data.primitive_to_edge_map.add(edges, i);
}
/* Build edge to neighboring triangle map. */
mesh_data.edge_to_primitive_map = EdgeToPrimitiveMap(mesh_data.edges.size());
for (const int prim_i : mesh_data.looptris.index_range()) {
for (const int edge_i : mesh_data.primitive_to_edge_map[prim_i]) {
mesh_data.edge_to_primitive_map.add(prim_i, edge_i);
}
}
BLI_edgehash_free(eh, nullptr);
}
static const int64_t INVALID_UV_ISLAND_ID = -1;
static constexpr int INVALID_UV_ISLAND_ID = -1;
/**
* NOTE: doesn't support weird topology where unconnected mesh primitives share the same uv
* island. For a accurate implementation we should use implement an uv_prim_lookup.
*/
static void extract_uv_neighbors(Vector<MeshPrimitive *> &prims_to_add, MeshPrimitive *primitive)
static void extract_uv_neighbors(const MeshData &mesh_data,
const Span<int> uv_island_ids,
const int primitive_i,
Vector<int> &prims_to_add)
{
for (MeshEdge *edge : primitive->edges) {
for (MeshPrimitive *other_primitive : edge->primitives) {
if (primitive == other_primitive) {
for (const int edge : mesh_data.primitive_to_edge_map[primitive_i]) {
for (const int other_primitive_i : mesh_data.edge_to_primitive_map[edge]) {
if (primitive_i == other_primitive_i) {
continue;
}
if (other_primitive->uv_island_id != INVALID_UV_ISLAND_ID) {
if (uv_island_ids[other_primitive_i] != INVALID_UV_ISLAND_ID) {
continue;
}
if (primitive->has_shared_uv_edge(other_primitive)) {
prims_to_add.append(other_primitive);
if (primitive_has_shared_uv_edge(mesh_data.uv_map,
mesh_data.looptris[primitive_i],
mesh_data.looptris[other_primitive_i])) {
prims_to_add.append(other_primitive_i);
}
}
}
}
static void mesh_data_init_primitive_uv_island_ids(MeshData &mesh_data)
static int mesh_data_init_primitive_uv_island_ids(MeshData &mesh_data)
{
for (MeshPrimitive &primitive : mesh_data.primitives) {
primitive.uv_island_id = INVALID_UV_ISLAND_ID;
}
mesh_data.uv_island_ids.reinitialize(mesh_data.looptris.size());
mesh_data.uv_island_ids.fill(INVALID_UV_ISLAND_ID);
int64_t uv_island_id = 0;
Vector<MeshPrimitive *> prims_to_add;
for (MeshPrimitive &primitive : mesh_data.primitives) {
int uv_island_id = 0;
Vector<int> prims_to_add;
for (const int primitive_i : mesh_data.looptris.index_range()) {
/* Early exit when uv island id is already extracted during uv neighbor extractions. */
if (primitive.uv_island_id != INVALID_UV_ISLAND_ID) {
if (mesh_data.uv_island_ids[primitive_i] != INVALID_UV_ISLAND_ID) {
continue;
}
prims_to_add.append(&primitive);
prims_to_add.append(primitive_i);
while (!prims_to_add.is_empty()) {
MeshPrimitive *primitive = prims_to_add.pop_last();
primitive->uv_island_id = uv_island_id;
extract_uv_neighbors(prims_to_add, primitive);
const int other_primitive_i = prims_to_add.pop_last();
mesh_data.uv_island_ids[other_primitive_i] = uv_island_id;
extract_uv_neighbors(mesh_data, mesh_data.uv_island_ids, other_primitive_i, prims_to_add);
}
uv_island_id++;
}
mesh_data.uv_island_len = uv_island_id;
return uv_island_id;
}
static void mesh_data_init(MeshData &mesh_data)
{
mesh_data_init_vertices(mesh_data);
mesh_data_init_primitives(mesh_data);
mesh_data_init_edges(mesh_data);
mesh_data_init_primitive_uv_island_ids(mesh_data);
mesh_data.uv_island_len = mesh_data_init_primitive_uv_island_ids(mesh_data);
}
MeshData::MeshData(const Span<MLoopTri> looptris,
const Span<MLoop> loops,
const int verts_num,
const Span<float2> mloopuv)
: looptris(looptris), verts_num(verts_num), loops(loops), mloopuv(mloopuv)
const Span<float2> uv_map)
: looptris(looptris),
verts_num(verts_num),
loops(loops),
uv_map(uv_map),
vert_to_edge_map(verts_num),
edge_to_primitive_map(0),
primitive_to_edge_map(looptris.size())
{
mesh_data_init(*this);
}
@ -241,7 +239,8 @@ UVVertex::UVVertex()
uv_vertex_init_flags(*this);
}
UVVertex::UVVertex(const MeshUVVert &vert) : vertex(vert.vertex), uv(vert.uv)
UVVertex::UVVertex(const MeshData &mesh_data, const int loop)
: vertex(mesh_data.loops[loop].v), uv(mesh_data.uv_map[loop])
{
uv_vertex_init_flags(*this);
}
@ -252,10 +251,10 @@ UVVertex::UVVertex(const MeshUVVert &vert) : vertex(vert.vertex), uv(vert.uv)
/** \name UVEdge
* \{ */
bool UVEdge::has_shared_edge(const MeshUVVert &v1, const MeshUVVert &v2) const
bool UVEdge::has_shared_edge(const Span<float2> uv_map, const int loop_1, const int loop_2) const
{
return (vertices[0]->uv == v1.uv && vertices[1]->uv == v2.uv) ||
(vertices[0]->uv == v2.uv && vertices[1]->uv == v1.uv);
return (vertices[0]->uv == uv_map[loop_1] && vertices[1]->uv == uv_map[loop_2]) ||
(vertices[0]->uv == uv_map[loop_2] && vertices[1]->uv == uv_map[loop_1]);
}
bool UVEdge::has_shared_edge(const UVVertex &v1, const UVVertex &v2) const
@ -269,22 +268,21 @@ bool UVEdge::has_shared_edge(const UVEdge &other) const
return has_shared_edge(*other.vertices[0], *other.vertices[1]);
}
bool UVEdge::has_same_vertices(const MeshVertex &vert1, const MeshVertex &vert2) const
bool UVEdge::has_same_vertices(const int vert1, const int vert2) const
{
return (vertices[0]->vertex == &vert1 && vertices[1]->vertex == &vert2) ||
(vertices[0]->vertex == &vert2 && vertices[1]->vertex == &vert1);
return (vertices[0]->vertex == vert1 && vertices[1]->vertex == vert2) ||
(vertices[0]->vertex == vert2 && vertices[1]->vertex == vert1);
}
bool UVEdge::has_same_uv_vertices(const UVEdge &other) const
{
return has_shared_edge(other) &&
has_same_vertices(*other.vertices[0]->vertex, *other.vertices[1]->vertex);
;
has_same_vertices(other.vertices[0]->vertex, other.vertices[1]->vertex);
}
bool UVEdge::has_same_vertices(const MeshEdge &edge) const
{
return has_same_vertices(*edge.vert1, *edge.vert2);
return has_same_vertices(edge.vert1, edge.vert2);
}
bool UVEdge::is_border_edge() const
@ -292,7 +290,7 @@ bool UVEdge::is_border_edge() const
return uv_primitives.size() == 1;
}
UVVertex *UVEdge::get_other_uv_vertex(const MeshVertex *vertex)
UVVertex *UVEdge::get_other_uv_vertex(const int vertex)
{
if (vertices[0]->vertex == vertex) {
return vertices[1];
@ -307,7 +305,7 @@ UVVertex *UVEdge::get_other_uv_vertex(const MeshVertex *vertex)
* \{ */
UVVertex *UVIsland::lookup(const UVVertex &vertex)
{
int64_t vert_index = vertex.vertex->v;
const int vert_index = vertex.vertex;
Vector<UVVertex *> &vertices = uv_vertex_lookup.lookup_or_add_default(vert_index);
for (UVVertex *v : vertices) {
if (v->uv == vertex.uv) {
@ -328,7 +326,7 @@ UVVertex *UVIsland::lookup_or_create(const UVVertex &vertex)
UVVertex *result = &uv_vertices.last();
result->uv_edges.clear();
/* v is already a key. Ensured by UVIsland::lookup in this method. */
uv_vertex_lookup.lookup(vertex.vertex->v).append(result);
uv_vertex_lookup.lookup(vertex.vertex).append(result);
return result;
}
@ -388,11 +386,11 @@ bool UVIsland::has_shared_edge(const UVPrimitive &primitive) const
return false;
}
bool UVIsland::has_shared_edge(const MeshPrimitive &primitive) const
bool UVIsland::has_shared_edge(const MeshData &mesh_data, const int primitive_i) const
{
for (const VectorList<UVPrimitive>::UsedVector &primitives : uv_primitives) {
for (const UVPrimitive &prim : primitives) {
if (prim.has_shared_edge(primitive)) {
if (prim.has_shared_edge(mesh_data, primitive_i)) {
return true;
}
}
@ -405,23 +403,27 @@ void UVIsland::extend_border(const UVPrimitive &primitive)
for (const VectorList<UVPrimitive>::UsedVector &primitives : uv_primitives) {
for (const UVPrimitive &prim : primitives) {
if (prim.has_shared_edge(primitive)) {
append(primitive);
this->append(primitive);
}
}
}
}
static UVPrimitive *add_primitive(UVIsland &uv_island, MeshPrimitive &primitive)
static UVPrimitive *add_primitive(const MeshData &mesh_data,
UVIsland &uv_island,
const int primitive_i)
{
UVPrimitive uv_primitive(&primitive);
UVPrimitive uv_primitive(primitive_i);
const MLoopTri &primitive = mesh_data.looptris[primitive_i];
uv_island.uv_primitives.append(uv_primitive);
UVPrimitive *uv_primitive_ptr = &uv_island.uv_primitives.last();
for (MeshEdge *edge : primitive.edges) {
const MeshUVVert &v1 = get_uv_vert(primitive, edge->vert1);
const MeshUVVert &v2 = get_uv_vert(primitive, edge->vert2);
for (const int edge_i : mesh_data.primitive_to_edge_map[primitive_i]) {
const MeshEdge &edge = mesh_data.edges[edge_i];
const int loop_1 = get_uv_loop(mesh_data, primitive, edge.vert1);
const int loop_2 = get_uv_loop(mesh_data, primitive, edge.vert2);
UVEdge uv_edge_template;
uv_edge_template.vertices[0] = uv_island.lookup_or_create(UVVertex(v1));
uv_edge_template.vertices[1] = uv_island.lookup_or_create(UVVertex(v2));
uv_edge_template.vertices[0] = uv_island.lookup_or_create(UVVertex(mesh_data, loop_1));
uv_edge_template.vertices[1] = uv_island.lookup_or_create(UVVertex(mesh_data, loop_2));
UVEdge *uv_edge = uv_island.lookup_or_create(uv_edge_template);
uv_primitive_ptr->edges.append(uv_edge);
uv_edge_append_to_uv_vertices(*uv_edge);
@ -493,7 +495,7 @@ static std::optional<UVBorderCorner> sharpest_border_corner(UVIsland &island)
/** The inner edge of a fan. */
struct InnerEdge {
MeshPrimitive *primitive;
const MLoopTri *primitive;
/* UVs order are already applied. So `uvs[0]` matches `primitive->vertices[vert_order[0]]`. */
float2 uvs[3];
int vert_order[3];
@ -502,23 +504,24 @@ struct InnerEdge {
bool found : 1;
} flags;
InnerEdge(MeshPrimitive *primitive, MeshVertex *vertex) : primitive(primitive)
InnerEdge(const MeshData &mesh_data, const MLoopTri *primitive, int vertex)
: primitive(primitive)
{
flags.found = false;
/* Reorder so the first edge starts with the given vertex. */
if (primitive->vertices[1].vertex == vertex) {
if (mesh_data.loops[primitive->tri[1]].v == vertex) {
vert_order[0] = 1;
vert_order[1] = 2;
vert_order[2] = 0;
}
else if (primitive->vertices[2].vertex == vertex) {
else if (mesh_data.loops[primitive->tri[2]].v == vertex) {
vert_order[0] = 2;
vert_order[1] = 0;
vert_order[2] = 1;
}
else {
BLI_assert(primitive->vertices[0].vertex == vertex);
BLI_assert(mesh_data.loops[primitive->tri[0]].v == vertex);
vert_order[0] = 0;
vert_order[1] = 1;
vert_order[2] = 2;
@ -539,29 +542,32 @@ struct Fan {
} flags;
Fan(MeshVertex &vertex)
Fan(const MeshData &mesh_data, const int vertex)
{
flags.full = true;
MeshEdge *current_edge = vertex.edges[0];
MeshPrimitive *stop_primitive = current_edge->primitives[0];
MeshPrimitive *previous_primitive = stop_primitive;
int current_edge = mesh_data.vert_to_edge_map[vertex].first();
const int stop_primitive = mesh_data.edge_to_primitive_map[current_edge].first();
int previous_primitive = stop_primitive;
while (true) {
bool stop = false;
for (MeshPrimitive *other : current_edge->primitives) {
for (const int other_primitive_i : mesh_data.edge_to_primitive_map[current_edge]) {
if (stop) {
break;
}
if (other == previous_primitive) {
if (other_primitive_i == previous_primitive) {
continue;
}
for (MeshEdge *edge : other->edges) {
if (edge == current_edge || (edge->vert1 != &vertex && edge->vert2 != &vertex)) {
const MLoopTri &other_looptri = mesh_data.looptris[other_primitive_i];
for (const int edge_i : mesh_data.primitive_to_edge_map[other_primitive_i]) {
const MeshEdge &edge = mesh_data.edges[edge_i];
if (edge_i == current_edge || (edge.vert1 != vertex && edge.vert2 != vertex)) {
continue;
}
inner_edges.append(InnerEdge(other, &vertex));
current_edge = edge;
previous_primitive = other;
inner_edges.append(InnerEdge(mesh_data, &other_looptri, vertex));
current_edge = edge_i;
previous_primitive = other_primitive_i;
stop = true;
break;
}
@ -587,15 +593,15 @@ struct Fan {
return result;
}
void mark_already_added_segments(const UVVertex &uv_vertex)
void mark_already_added_segments(const MeshData &mesh_data, const UVVertex &uv_vertex)
{
for (InnerEdge &fan_edge : inner_edges) {
fan_edge.flags.found = false;
const MeshVertex *v0 = fan_edge.primitive->vertices[fan_edge.vert_order[0]].vertex;
const MeshVertex *v1 = fan_edge.primitive->vertices[fan_edge.vert_order[1]].vertex;
const int v0 = mesh_data.loops[fan_edge.primitive->tri[fan_edge.vert_order[0]]].v;
const int v1 = mesh_data.loops[fan_edge.primitive->tri[fan_edge.vert_order[1]]].v;
for (const UVEdge *edge : uv_vertex.uv_edges) {
const MeshVertex *e0 = edge->vertices[0]->vertex;
const MeshVertex *e1 = edge->vertices[1]->vertex;
const int e0 = edge->vertices[0]->vertex;
const int e1 = edge->vertices[1]->vertex;
if ((e0 == v0 && e1 == v1) || (e0 == v1 && e1 == v0)) {
fan_edge.flags.found = true;
break;
@ -604,17 +610,17 @@ struct Fan {
}
}
void init_uv_coordinates(UVVertex &uv_vertex)
void init_uv_coordinates(const MeshData &mesh_data, UVVertex &uv_vertex)
{
for (InnerEdge &fan_edge : inner_edges) {
int64_t other_v = fan_edge.primitive->vertices[fan_edge.vert_order[0]].vertex->v;
if (other_v == uv_vertex.vertex->v) {
other_v = fan_edge.primitive->vertices[fan_edge.vert_order[1]].vertex->v;
int other_v = mesh_data.loops[fan_edge.primitive->tri[fan_edge.vert_order[0]]].v;
if (other_v == uv_vertex.vertex) {
other_v = mesh_data.loops[fan_edge.primitive->tri[fan_edge.vert_order[1]]].v;
}
for (UVEdge *edge : uv_vertex.uv_edges) {
const UVVertex *other_uv_vertex = edge->get_other_uv_vertex(uv_vertex.vertex);
int64_t other_edge_v = other_uv_vertex->vertex->v;
int64_t other_edge_v = other_uv_vertex->vertex;
if (other_v == other_edge_v) {
fan_edge.uvs[0] = uv_vertex.uv;
fan_edge.uvs[1] = other_uv_vertex->uv;
@ -630,29 +636,31 @@ struct Fan {
}
};
static void add_uv_primitive_shared_uv_edge(UVIsland &island,
static void add_uv_primitive_shared_uv_edge(const MeshData &mesh_data,
UVIsland &island,
UVVertex *connected_vert_1,
UVVertex *connected_vert_2,
float2 uv_unconnected,
MeshPrimitive *mesh_primitive)
const int mesh_primitive_i)
{
UVPrimitive prim1(mesh_primitive);
UVPrimitive prim1(mesh_primitive_i);
const MLoopTri &looptri = mesh_data.looptris[mesh_primitive_i];
MeshUVVert *other_vert = mesh_primitive->get_other_uv_vertex(connected_vert_1->vertex,
connected_vert_2->vertex);
const int other_vert_i = primitive_get_other_uv_vertex(
mesh_data, looptri, connected_vert_1->vertex, connected_vert_2->vertex);
UVVertex vert_template;
vert_template.uv = uv_unconnected;
vert_template.vertex = other_vert->vertex;
vert_template.vertex = other_vert_i;
UVVertex *vert_ptr = island.lookup_or_create(vert_template);
const MeshUVVert *mesh_vert_1 = &get_uv_vert(*mesh_primitive, connected_vert_1->vertex);
const int loop_1 = get_uv_loop(mesh_data, looptri, connected_vert_1->vertex);
vert_template.uv = connected_vert_1->uv;
vert_template.vertex = mesh_vert_1->vertex;
vert_template.vertex = mesh_data.loops[loop_1].v;
UVVertex *vert_1_ptr = island.lookup_or_create(vert_template);
const MeshUVVert *mesh_vert_2 = &get_uv_vert(*mesh_primitive, connected_vert_2->vertex);
const int loop_2 = get_uv_loop(mesh_data, looptri, connected_vert_2->vertex);
vert_template.uv = connected_vert_2->uv;
vert_template.vertex = mesh_vert_2->vertex;
vert_template.vertex = mesh_data.loops[loop_2].v;
UVVertex *vert_2_ptr = island.lookup_or_create(vert_template);
UVEdge edge_template;
@ -670,52 +678,55 @@ static void add_uv_primitive_shared_uv_edge(UVIsland &island,
island.uv_primitives.append(prim1);
}
static MeshPrimitive *find_fill_border(const MeshVertex &v1,
const MeshVertex &v2,
const MeshVertex &v3)
static int find_fill_border(const MeshData &mesh_data, const int v1, const int v2, const int v3)
{
for (MeshEdge *edge : v1.edges) {
for (MeshPrimitive *primitive : edge->primitives) {
if (has_vertex(*primitive, v1) && has_vertex(*primitive, v2) && has_vertex(*primitive, v3)) {
return primitive;
for (const int edge_i : mesh_data.vert_to_edge_map[v1]) {
for (const int primitive_i : mesh_data.edge_to_primitive_map[edge_i]) {
const MLoopTri &looptri = mesh_data.looptris[primitive_i];
if (has_vertex(mesh_data, looptri, v1) && has_vertex(mesh_data, looptri, v2) &&
has_vertex(mesh_data, looptri, v3)) {
return primitive_i;
}
}
}
return nullptr;
return -1;
}
/**
* Find a primitive that can be used to fill give corner.
* Will return nullptr when no primitive can be found.
* Will return -1 when no primitive can be found.
*/
static MeshPrimitive *find_fill_border(UVBorderCorner &corner)
static int find_fill_border(const MeshData &mesh_data, UVBorderCorner &corner)
{
if (corner.first->get_uv_vertex(1) != corner.second->get_uv_vertex(0)) {
return nullptr;
return -1;
}
if (corner.first->get_uv_vertex(0) == corner.second->get_uv_vertex(1)) {
return nullptr;
return -1;
}
UVVertex *shared_vert = corner.second->get_uv_vertex(0);
for (MeshEdge *edge : shared_vert->vertex->edges) {
if (corner.first->edge->has_same_vertices(*edge)) {
for (MeshPrimitive *primitive : edge->primitives) {
MeshVertex *other_vert = primitive->get_other_uv_vertex(edge->vert1, edge->vert2)->vertex;
for (const int edge_i : mesh_data.vert_to_edge_map[shared_vert->vertex]) {
const MeshEdge &edge = mesh_data.edges[edge_i];
if (corner.first->edge->has_same_vertices(edge)) {
for (const int primitive_i : mesh_data.edge_to_primitive_map[edge_i]) {
const MLoopTri &looptri = mesh_data.looptris[primitive_i];
const int other_vert = primitive_get_other_uv_vertex(
mesh_data, looptri, edge.vert1, edge.vert2);
if (other_vert == corner.second->get_uv_vertex(1)->vertex) {
return primitive;
return primitive_i;
}
}
}
}
return nullptr;
return -1;
}
static void add_uv_primitive_fill(UVIsland &island,
UVVertex &uv_vertex1,
UVVertex &uv_vertex2,
UVVertex &uv_vertex3,
MeshPrimitive &fill_primitive)
const int fill_primitive_i)
{
UVPrimitive uv_primitive(&fill_primitive);
UVPrimitive uv_primitive(fill_primitive_i);
UVEdge edge_template;
edge_template.vertices[0] = &uv_vertex1;
edge_template.vertices[1] = &uv_vertex2;
@ -731,48 +742,53 @@ static void add_uv_primitive_fill(UVIsland &island,
island.uv_primitives.append(uv_primitive);
}
static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_uv_distance)
static void extend_at_vert(const MeshData &mesh_data,
UVIsland &island,
UVBorderCorner &corner,
float min_uv_distance)
{
int border_index = corner.first->border_index;
UVBorder &border = island.borders[border_index];
UVVertex *uv_vertex = corner.second->get_uv_vertex(0);
Fan fan(*(uv_vertex->vertex));
Fan fan(mesh_data, uv_vertex->vertex);
if (!fan.flags.full) {
return;
}
fan.init_uv_coordinates(*uv_vertex);
fan.mark_already_added_segments(*uv_vertex);
fan.init_uv_coordinates(mesh_data, *uv_vertex);
fan.mark_already_added_segments(mesh_data, *uv_vertex);
int num_to_add = fan.count_num_to_add();
if (num_to_add == 0) {
MeshPrimitive *fill_primitive_1 = corner.second->uv_primitive->primitive;
MeshPrimitive *fill_primitive_2 = corner.first->uv_primitive->primitive;
int fill_primitive_1_i = corner.second->uv_primitive->primitive_i;
int fill_primitive_2_i = corner.first->uv_primitive->primitive_i;
MeshPrimitive *fill_primitive = find_fill_border(corner);
const int fill_primitive_i = find_fill_border(mesh_data, corner);
/*
* Although the fill_primitive can fill the missing segment it could lead to a squashed
* triangle when the corner angle is near 180 degrees. In order to fix this we will
* always add two segments both using the same fill primitive.
*/
if (fill_primitive) {
fill_primitive_1 = fill_primitive;
fill_primitive_2 = fill_primitive;
if (fill_primitive_i != -1) {
fill_primitive_1_i = fill_primitive_i;
fill_primitive_2_i = fill_primitive_i;
}
float2 center_uv = corner.uv(0.5f, min_uv_distance);
add_uv_primitive_shared_uv_edge(island,
add_uv_primitive_shared_uv_edge(mesh_data,
island,
corner.first->get_uv_vertex(1),
corner.first->get_uv_vertex(0),
center_uv,
fill_primitive_1);
fill_primitive_1_i);
UVPrimitive &new_prim_1 = island.uv_primitives.last();
add_uv_primitive_shared_uv_edge(island,
add_uv_primitive_shared_uv_edge(mesh_data,
island,
corner.second->get_uv_vertex(0),
corner.second->get_uv_vertex(1),
center_uv,
fill_primitive_2);
fill_primitive_2_i);
UVPrimitive &new_prim_2 = island.uv_primitives.last();
/* Update border after adding the new geometry. */
@ -798,8 +814,7 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
for (int i = 0; i < num_to_add; i++) {
float2 old_uv = current_edge->get_other_uv_vertex(uv_vertex->vertex)->uv;
MeshVertex *shared_edge_vertex =
current_edge->get_other_uv_vertex(uv_vertex->vertex)->vertex;
int shared_edge_vertex = current_edge->get_other_uv_vertex(uv_vertex->vertex)->vertex;
float factor = (i + 1.0f) / (num_to_add + 1.0f);
float2 new_uv = corner.uv(factor, min_uv_distance);
@ -811,15 +826,17 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
}
/* Find primitive that shares the current edge and the segment edge. */
MeshPrimitive *fill_primitive = find_fill_border(
*uv_vertex->vertex,
*shared_edge_vertex,
*segment.primitive->vertices[segment.vert_order[1]].vertex);
if (fill_primitive == nullptr) {
const int fill_primitive_i = find_fill_border(
mesh_data,
uv_vertex->vertex,
shared_edge_vertex,
mesh_data.loops[segment.primitive->tri[segment.vert_order[1]]].v);
if (fill_primitive_i == -1) {
continue;
}
MeshVertex *other_prim_vertex =
fill_primitive->get_other_uv_vertex(uv_vertex->vertex, shared_edge_vertex)->vertex;
const MLoopTri &fill_primitive = mesh_data.looptris[fill_primitive_i];
const int other_prim_vertex = primitive_get_other_uv_vertex(
mesh_data, fill_primitive, uv_vertex->vertex, shared_edge_vertex);
UVVertex uv_vertex_template;
uv_vertex_template.vertex = uv_vertex->vertex;
@ -833,7 +850,7 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
UVVertex *vertex_3_ptr = island.lookup_or_create(uv_vertex_template);
add_uv_primitive_fill(
island, *vertex_1_ptr, *vertex_2_ptr, *vertex_3_ptr, *fill_primitive);
island, *vertex_1_ptr, *vertex_2_ptr, *vertex_3_ptr, fill_primitive_i);
segment.flags.found = true;
@ -849,13 +866,15 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
{
/* Add final segment. */
float2 old_uv = current_edge->get_other_uv_vertex(uv_vertex->vertex)->uv;
MeshVertex *shared_edge_vertex =
current_edge->get_other_uv_vertex(uv_vertex->vertex)->vertex;
MeshPrimitive *fill_primitive = find_fill_border(
*uv_vertex->vertex, *shared_edge_vertex, *corner.second->get_uv_vertex(1)->vertex);
if (fill_primitive) {
MeshVertex *other_prim_vertex =
fill_primitive->get_other_uv_vertex(uv_vertex->vertex, shared_edge_vertex)->vertex;
int shared_edge_vertex = current_edge->get_other_uv_vertex(uv_vertex->vertex)->vertex;
const int fill_primitive_i = find_fill_border(mesh_data,
uv_vertex->vertex,
shared_edge_vertex,
corner.second->get_uv_vertex(1)->vertex);
if (fill_primitive_i != -1) {
const MLoopTri &fill_primitive = mesh_data.looptris[fill_primitive_i];
const int other_prim_vertex = primitive_get_other_uv_vertex(
mesh_data, fill_primitive, uv_vertex->vertex, shared_edge_vertex);
UVVertex uv_vertex_template;
uv_vertex_template.vertex = uv_vertex->vertex;
@ -868,7 +887,7 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
uv_vertex_template.uv = corner.second->get_uv_vertex(1)->uv;
UVVertex *vertex_3_ptr = island.lookup_or_create(uv_vertex_template);
add_uv_primitive_fill(
island, *vertex_1_ptr, *vertex_2_ptr, *vertex_3_ptr, *fill_primitive);
island, *vertex_1_ptr, *vertex_2_ptr, *vertex_3_ptr, fill_primitive_i);
UVPrimitive &new_prim = island.uv_primitives.last();
UVBorderEdge new_border(new_prim.get_uv_edge(shared_edge_vertex, other_prim_vertex),
@ -912,7 +931,9 @@ static void reset_extendability_flags(UVIsland &island)
}
}
void UVIsland::extend_border(const UVIslandsMask &mask, const short island_index)
void UVIsland::extend_border(const MeshData &mesh_data,
const UVIslandsMask &mask,
const short island_index)
{
reset_extendability_flags(*this);
@ -932,7 +953,8 @@ void UVIsland::extend_border(const UVIslandsMask &mask, const short island_index
/* Found corner is outside the mask, the corner should not be considered for extension. */
const UVIslandsMask::Tile *tile = mask.find_tile(uv_vertex->uv);
if (tile && tile->is_masked(island_index, uv_vertex->uv)) {
extend_at_vert(*this, *extension_corner, tile->get_pixel_size_in_uv_space() * 2.0f);
extend_at_vert(
mesh_data, *this, *extension_corner, tile->get_pixel_size_in_uv_space() * 2.0f);
}
/* Mark that the vert is extended. */
uv_vertex->flags.is_extended = true;
@ -1071,7 +1093,7 @@ float2 UVBorderCorner::uv(float factor, float min_uv_distance)
/** \name UVPrimitive
* \{ */
UVPrimitive::UVPrimitive(MeshPrimitive *primitive) : primitive(primitive)
UVPrimitive::UVPrimitive(const int primitive_i) : primitive_i(primitive_i)
{
}
@ -1100,16 +1122,17 @@ bool UVPrimitive::has_shared_edge(const UVPrimitive &other) const
return false;
}
bool UVPrimitive::has_shared_edge(const MeshPrimitive &primitive) const
bool UVPrimitive::has_shared_edge(const MeshData &mesh_data, const int primitive_i) const
{
for (const UVEdge *uv_edge : edges) {
const MeshUVVert *v1 = &primitive.vertices.last();
for (int i = 0; i < primitive.vertices.size(); i++) {
const MeshUVVert *v2 = &primitive.vertices[i];
if (uv_edge->has_shared_edge(*v1, *v2)) {
const MLoopTri &primitive = mesh_data.looptris[primitive_i];
int loop_1 = primitive.tri[2];
for (int i = 0; i < 3; i++) {
int loop_2 = primitive.tri[i];
if (uv_edge->has_shared_edge(mesh_data.uv_map, loop_1, loop_2)) {
return true;
}
v1 = v2;
loop_1 = loop_2;
}
}
return false;
@ -1118,9 +1141,11 @@ bool UVPrimitive::has_shared_edge(const MeshPrimitive &primitive) const
/**
* Get the UVVertex in the order that the verts are ordered in the MeshPrimitive.
*/
const UVVertex *UVPrimitive::get_uv_vertex(const uint8_t mesh_vert_index) const
const UVVertex *UVPrimitive::get_uv_vertex(const MeshData &mesh_data,
const uint8_t mesh_vert_index) const
{
const MeshVertex *mesh_vertex = primitive->vertices[mesh_vert_index].vertex;
const MLoopTri &looptri = mesh_data.looptris[this->primitive_i];
const int mesh_vertex = mesh_data.loops[looptri.tri[mesh_vert_index]].v;
for (const UVEdge *uv_edge : edges) {
for (const UVVertex *uv_vert : uv_edge->vertices) {
if (uv_vert->vertex == mesh_vertex) {
@ -1149,11 +1174,11 @@ UVEdge *UVPrimitive::get_uv_edge(const float2 uv1, const float2 uv2) const
return nullptr;
}
UVEdge *UVPrimitive::get_uv_edge(const MeshVertex *v1, const MeshVertex *v2) const
UVEdge *UVPrimitive::get_uv_edge(const int v1, const int v2) const
{
for (UVEdge *uv_edge : edges) {
const MeshVertex *e1 = uv_edge->vertices[0]->vertex;
const MeshVertex *e2 = uv_edge->vertices[1]->vertex;
const int e1 = uv_edge->vertices[0]->vertex;
const int e2 = uv_edge->vertices[1]->vertex;
if ((e1 == v1 && e2 == v2) || (e1 == v2 && e2 == v1)) {
return uv_edge;
}
@ -1238,16 +1263,16 @@ float UVBorderEdge::length() const
/** \name UVIslands
* \{ */
UVIslands::UVIslands(MeshData &mesh_data)
UVIslands::UVIslands(const MeshData &mesh_data)
{
islands.reserve(mesh_data.uv_island_len);
for (int64_t uv_island_id = 0; uv_island_id < mesh_data.uv_island_len; uv_island_id++) {
islands.append_as(UVIsland());
UVIsland *uv_island = &islands.last();
for (MeshPrimitive &primitive : mesh_data.primitives) {
if (primitive.uv_island_id == uv_island_id) {
add_primitive(*uv_island, primitive);
for (const int primitive_i : mesh_data.looptris.index_range()) {
if (mesh_data.uv_island_ids[primitive_i] == uv_island_id) {
add_primitive(mesh_data, *uv_island, primitive_i);
}
}
}
@ -1260,11 +1285,11 @@ void UVIslands::extract_borders()
}
}
void UVIslands::extend_borders(const UVIslandsMask &islands_mask)
void UVIslands::extend_borders(const MeshData &mesh_data, const UVIslandsMask &islands_mask)
{
ushort index = 0;
for (UVIsland &island : islands) {
island.extend_border(islands_mask, index++);
island.extend_border(mesh_data, islands_mask, index++);
}
}
@ -1299,15 +1324,16 @@ float UVIslandsMask::Tile::get_pixel_size_in_uv_space() const
return min_ff(1.0f / tile_resolution.x, 1.0f / tile_resolution.y);
}
static void add_uv_island(UVIslandsMask::Tile &tile,
static void add_uv_island(const MeshData &mesh_data,
UVIslandsMask::Tile &tile,
const UVIsland &uv_island,
int16_t island_index)
{
for (const VectorList<UVPrimitive>::UsedVector &uv_primitives : uv_island.uv_primitives) {
for (const UVPrimitive &uv_primitive : uv_primitives) {
const MeshPrimitive *mesh_primitive = uv_primitive.primitive;
const MLoopTri &looptri = mesh_data.looptris[uv_primitive.primitive_i];
rctf uv_bounds = mesh_primitive->uv_bounds();
rctf uv_bounds = primitive_uv_bounds(looptri, mesh_data.uv_map);
rcti buffer_bounds;
buffer_bounds.xmin = max_ii(
floor((uv_bounds.xmin - tile.udim_offset.x) * tile.mask_resolution.x), 0);
@ -1324,9 +1350,9 @@ static void add_uv_island(UVIslandsMask::Tile &tile,
for (int x = buffer_bounds.xmin; x < buffer_bounds.xmax + 1; x++) {
float2 uv(float(x) / tile.mask_resolution.x, float(y) / tile.mask_resolution.y);
float3 weights;
barycentric_weights_v2(mesh_primitive->vertices[0].uv,
mesh_primitive->vertices[1].uv,
mesh_primitive->vertices[2].uv,
barycentric_weights_v2(mesh_data.uv_map[looptri.tri[0]],
mesh_data.uv_map[looptri.tri[1]],
mesh_data.uv_map[looptri.tri[2]],
uv + tile.udim_offset,
weights);
if (!barycentric_inside_triangle_v2(weights)) {
@ -1341,11 +1367,11 @@ static void add_uv_island(UVIslandsMask::Tile &tile,
}
}
void UVIslandsMask::add(const UVIslands &uv_islands)
void UVIslandsMask::add(const MeshData &mesh_data, const UVIslands &uv_islands)
{
for (Tile &tile : tiles) {
for (int index = 0; index < uv_islands.islands.size(); index++) {
add_uv_island(tile, uv_islands.islands[index], index);
for (const int i : uv_islands.islands.index_range()) {
add_uv_island(mesh_data, tile, uv_islands.islands[i], i);
}
}
}

144
source/blender/blenkernel/intern/pbvh_uv_islands.hh
View File

@ -31,59 +31,86 @@
#include "BLI_rect.h"
#include "BLI_vector.hh"
#include "BLI_vector_list.hh"
#include "BLI_virtual_array.hh"
#include "DNA_meshdata_types.h"
namespace blender::bke::pbvh::uv_islands {
struct MeshEdge;
struct MeshPrimitive;
struct UVBorder;
struct UVEdge;
struct UVIslands;
struct UVIslandsMask;
struct UVPrimitive;
struct UVPrimitiveEdge;
struct MeshData;
struct UVVertex;
struct MeshVertex {
int64_t v;
Vector<MeshEdge *> edges;
};
struct MeshUVVert {
MeshVertex *vertex;
float2 uv;
int64_t loop;
};
struct MeshEdge {
MeshVertex *vert1;
MeshVertex *vert2;
Vector<MeshPrimitive *> primitives;
int vert1;
int vert2;
};
/** Represents a triangle in 3d space (MLoopTri). */
struct MeshPrimitive {
int64_t index;
int64_t poly;
Vector<MeshEdge *, 3> edges;
Vector<MeshUVVert, 3> vertices;
class VertToEdgeMap {
Array<Vector<int>> edges_of_vert_;
/**
* UV island this primitive belongs to. This is used to speed up the initial uv island
* extraction and should not be used afterwards.
*/
int64_t uv_island_id;
public:
VertToEdgeMap() = delete;
VertToEdgeMap(const int verts_num)
{
edges_of_vert_.reinitialize(verts_num);
}
/** Get the vertex that is not given. Both given vertices must be part of the MeshPrimitive. */
MeshUVVert *get_other_uv_vertex(const MeshVertex *v1, const MeshVertex *v2);
void add(const int edge_i, const int v1, const int v2)
{
edges_of_vert_[v1].append(edge_i);
edges_of_vert_[v2].append(edge_i);
}
Span<int> operator[](const int vert_i) const
{
return edges_of_vert_[vert_i];
}
};
/** Get the UV bounds for this MeshPrimitive. */
rctf uv_bounds() const;
class EdgeToPrimitiveMap {
Array<Vector<int>> primitives_of_edge_;
/** Is the given MeshPrimitive sharing an edge. */
bool has_shared_uv_edge(const MeshPrimitive *other) const;
public:
EdgeToPrimitiveMap() = delete;
EdgeToPrimitiveMap(const int edges_num)
{
primitives_of_edge_.reinitialize(edges_num);
}
void add(const int primitive_i, const int edge_i)
{
primitives_of_edge_[edge_i].append(primitive_i);
}
Span<int> operator[](const int edge_i) const
{
return primitives_of_edge_[edge_i];
}
};
class TriangleToEdgeMap {
Array<std::array<int, 3>> edges_of_triangle_;
public:
TriangleToEdgeMap() = delete;
TriangleToEdgeMap(const int edges_num)
{
edges_of_triangle_.reinitialize(edges_num);
}
void add(const Span<int> edges, const int tri_i)
{
std::copy(edges.begin(), edges.end(), edges_of_triangle_[tri_i].begin());
}
Span<int> operator[](const int tri_i) const
{
return edges_of_triangle_[tri_i];
}
};
/**
@ -95,23 +122,32 @@ struct MeshData {
const Span<MLoopTri> looptris;
const int64_t verts_num;
const Span<MLoop> loops;
const Span<float2> mloopuv;
const Span<float2> uv_map;
VertToEdgeMap vert_to_edge_map;
Vector<MeshPrimitive> primitives;
Vector<MeshEdge> edges;
Vector<MeshVertex> vertices;
EdgeToPrimitiveMap edge_to_primitive_map;
TriangleToEdgeMap primitive_to_edge_map;
/**
* UV island each primitive belongs to. This is used to speed up the initial uv island
* extraction and should not be used afterwards.
*/
Array<int> uv_island_ids;
/** Total number of found uv islands. */
int64_t uv_island_len;
public:
explicit MeshData(const Span<MLoopTri> looptris,
const Span<MLoop> loops,
explicit MeshData(Span<MLoopTri> looptris,
Span<MLoop> loops,
const int verts_num,
const Span<float2> mloopuv);
const Span<float2> uv_map);
};
struct UVVertex {
MeshVertex *vertex;
int vertex;
/* Position in uv space. */
float2 uv;
@ -124,22 +160,22 @@ struct UVVertex {
} flags;
explicit UVVertex();
explicit UVVertex(const MeshUVVert &vert);
explicit UVVertex(const MeshData &mesh_data, const int loop);
};
struct UVEdge {
std::array<UVVertex *, 2> vertices;
Vector<UVPrimitive *, 2> uv_primitives;
UVVertex *get_other_uv_vertex(const MeshVertex *vertex);
bool has_shared_edge(const MeshUVVert &v1, const MeshUVVert &v2) const;
UVVertex *get_other_uv_vertex(const int vertex_index);
bool has_shared_edge(Span<float2> uv_map, const int loop_1, const int loop_2) const;
bool has_shared_edge(const UVEdge &other) const;
bool has_same_vertices(const MeshEdge &edge) const;
bool is_border_edge() const;
private:
bool has_shared_edge(const UVVertex &v1, const UVVertex &v2) const;
bool has_same_vertices(const MeshVertex &vert1, const MeshVertex &vert2) const;
bool has_same_vertices(const int v1, const int v2) const;
bool has_same_uv_vertices(const UVEdge &other) const;
};
@ -147,26 +183,26 @@ struct UVPrimitive {
/**
* Index of the primitive in the original mesh.
*/
MeshPrimitive *primitive;
const int primitive_i;
Vector<UVEdge *, 3> edges;
explicit UVPrimitive(MeshPrimitive *primitive);
explicit UVPrimitive(const int primitive_i);
Vector<std::pair<UVEdge *, UVEdge *>> shared_edges(UVPrimitive &other);
bool has_shared_edge(const UVPrimitive &other) const;
bool has_shared_edge(const MeshPrimitive &primitive) const;
bool has_shared_edge(const MeshData &mesh_data, int other_triangle_index) const;
/**
* Get the UVVertex in the order that the verts are ordered in the MeshPrimitive.
*/
const UVVertex *get_uv_vertex(const uint8_t mesh_vert_index) const;
const UVVertex *get_uv_vertex(const MeshData &mesh_data, const uint8_t mesh_vert_index) const;
/**
* Get the UVEdge that share the given uv coordinates.
* Will assert when no UVEdge found.
*/
UVEdge *get_uv_edge(const float2 uv1, const float2 uv2) const;
UVEdge *get_uv_edge(const MeshVertex *v1, const MeshVertex *v2) const;
UVEdge *get_uv_edge(const int v1, const int v2) const;
bool contains_uv_vertex(const UVVertex *uv_vertex) const;
const UVVertex *get_other_uv_vertex(const UVVertex *v1, const UVVertex *v2) const;
@ -266,24 +302,26 @@ struct UVIsland {
/** Initialize the border attribute. */
void extract_borders();
/** Iterative extend border to fit the mask. */
void extend_border(const UVIslandsMask &mask, const short island_index);
void extend_border(const MeshData &mesh_data,
const UVIslandsMask &mask,
const short island_index);
private:
void append(const UVPrimitive &primitive);
public:
bool has_shared_edge(const UVPrimitive &primitive) const;
bool has_shared_edge(const MeshPrimitive &primitive) const;
bool has_shared_edge(const MeshData &mesh_data, const int primitive_i) const;
void extend_border(const UVPrimitive &primitive);
};
struct UVIslands {
Vector<UVIsland> islands;
explicit UVIslands(MeshData &mesh_data);
explicit UVIslands(const MeshData &mesh_data);
void extract_borders();
void extend_borders(const UVIslandsMask &islands_mask);
void extend_borders(const MeshData &mesh_data, const UVIslandsMask &islands_mask);
};
/** Mask to find the index of the UVIsland for a given UV coordinate. */
@ -324,7 +362,7 @@ struct UVIslandsMask {
* Add the given UVIslands to the mask. Tiles should be added beforehand using the 'add_tile'
* method.
*/
void add(const UVIslands &islands);
void add(const MeshData &mesh_data, const UVIslands &islands);
void dilate(int max_iterations);
};