Blender V5.3
xpbd_constraint_coloring.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
6
8
9namespace blender::xpbd {
10
11template<typename PointID, typename GetConstraintPointIdsFn>
12inline int color_constraints(GetConstraintPointIdsFn &&get_constraint_point_ids_fn,
13 MutableSpan<int> r_colors)
14{
15 const int constraints_num = r_colors.size();
16 MultiValueMap<PointID, int> constraints_by_point;
17 for (const int constraint_i : IndexRange(constraints_num)) {
18 for (const PointID &point_id : get_constraint_point_ids_fn(constraint_i)) {
19 constraints_by_point.add(point_id, constraint_i);
20 }
21 }
22 int colors_num = 0;
23 for (const int constraint_i : IndexRange(constraints_num)) {
24 Vector<int> used_colors;
25 for (const PointID &point_id : get_constraint_point_ids_fn(constraint_i)) {
26 for (const int other_constraint_i : constraints_by_point.lookup(point_id)) {
27 if (other_constraint_i >= constraint_i) {
28 continue;
29 }
30 used_colors.append_non_duplicates(r_colors[other_constraint_i]);
31 }
32 }
33 int best_color = 0;
34 while (used_colors.contains(best_color)) {
35 best_color++;
36 }
37 r_colors[constraint_i] = best_color;
38 colors_num = std::max(colors_num, best_color + 1);
39 }
40 return colors_num;
41}
42
43template<typename PointID, typename GetConstraintPointIdsFn>
45 GetConstraintPointIdsFn &&get_constraint_points_fn,
46 const int constraints_num,
47 LinearAllocator<> &memory)
48{
49 if (constraints_num == 0) {
50 return {};
51 }
52 Array<int> colors(constraints_num);
53 const int colors_num = color_constraints<PointID>(get_constraint_points_fn, colors);
54 Array<Vector<int>> color_indices(colors_num);
55 for (const int constraint_i : IndexRange(constraints_num)) {
56 color_indices[colors[constraint_i]].append(constraint_i);
57 }
58 ConstraintColoring coloring;
59 for (const int color_i : IndexRange(colors_num)) {
60 const IndexMask mask = IndexMask::from_indices<int>(color_indices[color_i], memory);
61 coloring.colors.append(mask);
62 }
63 return coloring;
64}
65
67 LinearAllocator<> &memory)
68{
70 [&](const int constraint_i) { return Span<int>(&affected_points[constraint_i], 1); },
71 affected_points.size(),
72 memory);
73}
74
76 LinearAllocator<> &memory)
77{
79 [&](const int constraint_i) { return Span<int>(&affected_points[constraint_i][0], 2); },
80 affected_points.size(),
81 memory);
82}
83
85 LinearAllocator<> &memory)
86{
88 [&](const int constraint_i) { return affected_points[constraint_i]; },
89 affected_points.size(),
90 memory);
91}
92
94{
95 return ConstraintColoring{{IndexMask(constraints_num)}};
96}
97
98} // namespace blender::xpbd
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
constexpr IndexRange()=default
Span< Value > lookup(const Key &key) const
void add(const Key &key, const Value &value)
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr int64_t size() const
Definition BLI_span.hh:256
bool contains(const T &value) const
void append_non_duplicates(const T &value)
ConstraintColoring color_constraints__unary(const Span< int > affected_points, LinearAllocator<> &memory)
ConstraintColoring generic_constraint_coloring(GetConstraintPointIdsFn &&get_constraint_points_fn, const int constraints_num, LinearAllocator<> &memory)
ConstraintColoring color_constraints__n_ary(const GroupedSpan< int > affected_points, LinearAllocator<> &memory)
ConstraintColoring color_constraints__binary(const Span< int2 > affected_points, LinearAllocator<> &memory)
ConstraintColoring color_constraints__all_independent(const int constraints_num)
int color_constraints(GetConstraintPointIdsFn &&get_constraint_point_ids_fn, MutableSpan< int > r_colors)