Commit: 5f986f04725894297022aded4f5e5f36631aebcb
Author: Jacques Lucke
Date: Tue Jan 29 22:09:50 2019 +0100
Branches: rigid_deform
https://developer.blender.org/rB5f986f04725894297022aded4f5e5f36631aebcb
store which vertices have an impact when setting new anchors
===================================================================
M source/blender/modifiers/intern/MOD_rigiddeform_system.cc
M source/blender/modifiers/intern/MOD_rigiddeform_system.hpp
===================================================================
diff --git a/source/blender/modifiers/intern/MOD_rigiddeform_system.cc
b/source/blender/modifiers/intern/MOD_rigiddeform_system.cc
index ca3a899c8b9..806bd2ff28a 100644
--- a/source/blender/modifiers/intern/MOD_rigiddeform_system.cc
+++ b/source/blender/modifiers/intern/MOD_rigiddeform_system.cc
@@ -28,7 +28,8 @@
#include <chrono>
-/* ************** Timer ***************** */
+/* Timer
+ **************************************/
class Timer {
const char *name;
@@ -54,34 +55,14 @@ Timer::~Timer() {
#define TIMEIT(name) Timer t(name);
-/* ************ Timer End *************** */
namespace RigidDeform {
- /* expects the anchor indices to be sorted */
- /* (6, [1, 4]) -> [0, 2, 3, 5, 1, 4] */
- static std::vector<uint> sort_vertices_by_anchors(const
std::vector<uint> &anchors, uint vertex_amount)
- {
- std::vector<uint> sorted;
-
- int anchor_index = 0;
- for (int i = 0; i < vertex_amount; i++) {
- if (anchor_index < anchors.size() && i ==
anchors[anchor_index]) {
- anchor_index++;
- continue;
- }
- sorted.push_back(i);
- }
-
- sorted.insert(sorted.end(), anchors.begin(), anchors.end());
- return sorted;
- }
-
/* Build Laplace Matrix
******************************************/
static std::vector<double> calc_total_weight_per_vertex(
- const std::vector<WeightedEdge> &edges,
+ const WeightedEdges &edges,
uint vertex_amount)
{
std::vector<double> total_weights(vertex_amount, 0);
@@ -109,11 +90,11 @@ namespace RigidDeform {
return std::cos(angle) / std::sin(angle);
}
- static std::vector<WeightedEdge> calculate_cotan_edge_weights(
+ static WeightedEdges calculate_cotan_edge_weights(
const Vectors &positions,
const std::vector<std::array<uint, 3>> &triangles)
{
- std::vector<WeightedEdge> edges;
+ WeightedEdges edges;
for (auto verts : triangles) {
std::array<double, 3> angles = triangle_corner_angles(
@@ -133,12 +114,13 @@ namespace RigidDeform {
return edges;
}
- static std::vector<Triplet> get_laplace_matrix_triplets(
- uint vertex_amount, std::vector<WeightedEdge> &edges)
+ static Triplets get_laplace_matrix_triplets(
+ uint vertex_amount,
+ const WeightedEdges &edges)
{
auto total_weights = calc_total_weight_per_vertex(edges,
vertex_amount);
- std::vector<Triplet> triplets;
+ Triplets triplets;
for (int i = 0; i < vertex_amount; i++) {
triplets.push_back(Triplet(i, i, total_weights[i]));
@@ -154,16 +136,144 @@ namespace RigidDeform {
return triplets;
}
- ReorderData::ReorderData(const std::vector<uint> &anchors, uint
vertex_amount)
+
+ /* Initialize
+ *****************************************/
+
+ RigidDeformSystem::RigidDeformSystem(
+ const Vectors &initial_positions,
+ const std::vector<std::array<uint, 3>> &triangles)
{
- m_new_to_orig = sort_vertices_by_anchors(anchors,
vertex_amount);
+ m_initial_positions = initial_positions;
+ m_edges = calculate_cotan_edge_weights(initial_positions,
triangles);
+ m_laplace_triplets =
get_laplace_matrix_triplets(this->vertex_amount(), m_edges);
+ }
- m_orig_to_new.resize(vertex_amount);
- for (int i = 0; i < vertex_amount; i++) {
- m_orig_to_new[m_new_to_orig[i]] = i;
+
+ /* Set Anchors
+ ******************************************/
+
+ void RigidDeformSystem::set_anchors(
+ const std::vector<uint> &anchor_indices)
+ {
+ m_order = ReorderData(anchor_indices, this->vertex_amount());
+ m_anchor_indices = anchor_indices;
+
+ this->update_inner_indices();
+ this->update_matrix();
+ this->update_impact_data();
+
+ m_solver = std::unique_ptr<Solver>(new Solver());
+ m_solver->compute(m_A_II.transpose() * m_A_II);
+ }
+
+ void RigidDeformSystem::update_inner_indices()
+ {
+ m_inner_indices = {};
+ for (uint i = 0; i < this->vertex_amount(); i++) {
+ if (m_order.is_inner__orig(i)) {
+ m_inner_indices.push_back(i);
+ }
}
+ }
- this->m_inner_amount = vertex_amount - anchors.size();
+ void RigidDeformSystem::update_matrix()
+ {
+ Triplets triplets_A_II, triplets_A_IB;
+ for (Triplet triplet : m_laplace_triplets) {
+ if (m_order.is_inner__orig(triplet.row())) {
+ uint reorder_row =
m_order.to_new(triplet.row());
+ if (m_order.is_inner__orig(triplet.col())) {
+ triplets_A_II.push_back(Triplet(
+ reorder_row,
+ m_order.to_new(triplet.col()),
+ triplet.value()));
+ }
+ else {
+ triplets_A_IB.push_back(Triplet(
+ reorder_row,
+
m_order.to_new_anchor(triplet.col()),
+ triplet.value()));
+ }
+ }
+ }
+
+ m_A_II = SparseMatrixD(m_order.inner_amount(),
m_order.inner_amount());
+ m_A_IB = SparseMatrixD(m_order.inner_amount(),
m_order.anchor_amount());
+ m_A_II.setFromTriplets(triplets_A_II.begin(),
triplets_A_II.end());
+ m_A_IB.setFromTriplets(triplets_A_IB.begin(),
triplets_A_IB.end());
+ }
+
+ void RigidDeformSystem::update_impact_data()
+ {
+ m_impact.m_edges = {};
+ std::vector<bool> has_impact = {};
+ this->get_impact_edges(m_impact.m_edges, has_impact);
+
+ m_impact.m_compact_amount = 0;
+ m_impact.m_compact_map.resize(this->vertex_amount());
+ for (uint i = 0; i < this->vertex_amount(); i++) {
+ if (has_impact[i]) {
+ m_impact.m_compact_map[i] =
m_impact.m_compact_amount;
+ m_impact.m_compact_amount++;
+ }
+ else {
+ m_impact.m_compact_map[i] = -1;
+ }
+ }
+ }
+
+ void RigidDeformSystem::get_impact_edges(
+ WeightedEdges &r_impact_edges,
+ std::vector<bool> &r_vertex_has_impact)
+ {
+ std::vector<bool> &has_impact = r_vertex_has_impact;
+ has_impact.resize(this->vertex_amount(), false);
+
+ for (WeightedEdge edge : m_edges) {
+ if (m_order.is_inner__orig(edge.v1) ||
m_order.is_inner__orig(edge.v2)) {
+ has_impact[edge.v1] = true;
+ has_impact[edge.v2] = true;
+ }
+ }
+ for (WeightedEdge edge : m_edges) {
+ if (has_impact[edge.v1] || has_impact[edge.v2]) {
+ r_impact_edges.push_back(edge);
+ has_impact[edge.v1] = true;
+ has_impact[edge.v2] = true;
+ }
+ }
+ }
+
+
+ /* Solve Inner Positions
+ ********************************************/
+
+ Vectors RigidDeformSystem::calculate_inner(
+ const Vectors &anchor_positions,
+ uint iterations)
+ {
+ assert(iterations > 0);
+ assert(this->anchor_indices().size() > 0);
+
+ std::vector<Eigen::Matrix3d> rotations(this->vertex_amount());
+ std::fill(rotations.begin(), rotations.end(),
Eigen::Matrix3d::Identity());
+
+ const std::array<Eigen::VectorXd, 3> b_preprocessed = {
+ m_A_IB * anchor_positions.get_coord(0),
+ m_A_IB * anchor_positions.get_coord(1),
+ m_A_IB * anchor_positions.get_coord(2),
+ };
+
+ uint iteration = 0;
+ while (true) {
+ iteration++;
+ Vectors new_inner_positions =
this->optimize_inner_positions(b_preprocessed, rotations);
+ if (iteration == iterations) {
+ return new_inner_positions;
+ }
+ rotations = this->optimize_rotations(anchor_positions,
new_inner_positions);
+ }
}
@@ -188,10 +298,10 @@ namespace RigidDeform {
const Vectors &anchor_positions,
const Vectors &new_inner_positions)
{
- std::vector<Eigen::Matrix3d> S(this->vertex_amount());
+ std::vector<Eigen::Matrix3d> S(m_impact.compact_amount());
for (uint i = 0; i < S.size(); i++) S[i].setZero();
- for (WeightedEdge edge : m_edges) {
+ for (WeightedEdge edge : m_impact.edges()) {
uint v1 = edge.v1;
uint v2 = edge.v2;
@@ -205,8 +315,8 @@ namespace RigidDeform {
Eigen::RowVector3d edge_new = edge_new_start -
edge_new_end;
Eigen::Matrix3d mat = edge.weight * edge_old * edge_new;
- S[v1] += mat;
- S[v2] += mat;
+ S[m_impact.compact_index(v1)] += mat;
+ S[m_impact.compact_index(v2)] += mat;
}
std::vector<Eigen::Matrix3d> R(S.size());
@@ -228,11 +338,11 @@ namespace RigidDeform {
**********************************************/
Vectors RigidDeformSystem::optimize_inner_positions(
- const Vectors &anchor_positions,
+ const std::array<Eigen::VectorXd, 3> &b_preprocessed,
const std::vector<Eigen::Matrix3d> &rotations)
{
Vectors new_inner_diffs =
this->calculate_new_inner_diffs(rotations);
- return this->solve_for_new_inner_positions(anchor_positions,
new_inner_diffs);
+ return this->solve_for_new_inner_positions(b_preprocessed,
new_inner_diffs);
}
Vectors RigidDeformSystem::calculate_new_inner_diffs(
@@ -241,30 +351,31 @@ namespace RigidDeform {
Vectors new_inner_diffs(m_order.inner_amount());
new_inner_diffs.set_zero();
- for (WeightedEdge edge : m_edges) {
+ for (WeightedEdge edge : m_impact.edges()) {
uint v1 = edge.v1;
uint v2 = edge.v2;
- bool v1_is_inner = m_order.is_inner__orig(v1);
- bool v2_is_inner = m_order.is_inner__orig(v2);
- if (!(v1_is_inner || v2_is_inner)) continue;
+ int v1_compact = m_impact.compact_index(v1);
+ int v2_compact = m_impact.compact_index(v2);
+ assert(v1_compact >= 0 && v2_compact >= 0);
Eigen::Vector3d old_edge = m_initial_positions[v1] -
m_initial_positions[v2];
- Eigen::Vector3d value = edge.weight / 2.0f *
(rotations[v1] + rotations[v2]) * old_edge;
+ Eigen::Vector3d value =
+ edge.weight / 2.0f * (rotations[v1_compact] +
rotations[v2_compact]) * old_edge;
- if (v1_is_inner) new_inner_diffs[m_order.to_new(v1)] +=
value;
- if (v2_is_inner) new_inner_diffs[m_order.to_new(v2)] -=
value;
+ if (m_order.is_inner__orig(v1))
new_inner_diffs[m_order.to_new(v1)] += value;
+ if (m_order.is_inner__orig(v2))
new_inner_diffs[m_order.to_new(v2)] -= value;
}
return new_inner_diffs;
}
Vectors RigidDeformSystem::solve_for_new_inner_positions(
- const Vectors &anchor_positions,
+ const std::array<Eigen::VectorXd, 3> &b_preprocessed,
const Vectors &new_inner_diffs)
{
Vectors new_inner_positions(m_order.inner_amount());
for (uint coord = 0; coord < 3; coord++) {
- Eigen::VectorXd b = new_inner_diffs.get_coord(coord) -
m_A_IB * anchor_positions.get_coord(coord);
+ Eigen::VectorXd b = new_inner_diffs.get_coord(coord) -
b_preprocessed[coord];
Eigen::VectorXd result =
m_solver->solve(m_A_II.transpose() * b);
new_inner_positions.set_coord(coord, result);
}
@@ -272,90 +383,43 @@ namespace RigidDeform {
}
- /* RigidDeformSystem
- ***************************************/
-
- RigidDeformSystem::RigidDeformSystem(
- c
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
