[Bf-blender-cvs] [519a6c425d7] experimental-build: rigid deform modifier
Jacques Lucke
noreply at git.blender.org
Wed Feb 13 20:49:44 CET 2019
Commit: 519a6c425d7225618478a43f4e0fa10e56287a53
Author: Jacques Lucke
Date: Wed Feb 13 20:48:56 2019 +0100
Branches: experimental-build
https://developer.blender.org/rB519a6c425d7225618478a43f4e0fa10e56287a53
rigid deform modifier
hopefully I managed to get rid of external dependencies...
===================================================================
M build_files/cmake/macros.cmake
M extern/CMakeLists.txt
A extern/CholUp/CMakeLists.txt
A extern/CholUp/source/CholUp/CholUp.hpp
A extern/CholUp/source/CholUp/EliminationTreeMethods.cpp
A extern/CholUp/source/CholUp/EliminationTreeMethods.h
A extern/CholUp/source/CholUp/Matrix.hpp
A extern/CholUp/source/CholUp/Ordering.h
A extern/CholUp/source/CholUp/SparseMatrix.h
A extern/CholUp/source/CholUp/SparseMatrix_impl.h
A extern/CholUp/source/CholUp/SparseSupernodal.h
A extern/CholUp/source/CholUp/SupernodalCholesky.h
A extern/CholUp/source/CholUp/Timer.cpp
A extern/CholUp/source/CholUp/Timer.hpp
A extern/CholUp/source/CholUp/main.cpp
M intern/CMakeLists.txt
A intern/fast_svd/CMakeLists.txt
A intern/fast_svd/source/FastSVD.cpp
A intern/fast_svd/source/FastSVD.hpp
A intern/fast_svd/source/Singular_Value_Decomposition_Givens_QR_Factorization_Kernel.hpp
A intern/fast_svd/source/Singular_Value_Decomposition_Jacobi_Conjugation_Kernel.hpp
A intern/fast_svd/source/Singular_Value_Decomposition_Kernel_Declarations.hpp
A intern/fast_svd/source/Singular_Value_Decomposition_Main_Kernel_Body.hpp
A intern/fast_svd/source/Singular_Value_Decomposition_Preamble.hpp
M release/scripts/startup/bl_operators/__init__.py
A release/scripts/startup/bl_operators/rigiddeform.py
M release/scripts/startup/bl_ui/properties_data_modifier.py
M source/blender/blenkernel/BKE_mesh_runtime.h
M source/blender/blenlib/BLI_edgehash.h
M source/blender/blenloader/intern/readfile.c
M source/blender/blenloader/intern/writefile.c
M source/blender/editors/object/object_intern.h
M source/blender/editors/object/object_modifier.c
M source/blender/editors/object/object_ops.c
M source/blender/editors/space_outliner/outliner_draw.c
M source/blender/makesdna/DNA_modifier_types.h
M source/blender/makesrna/RNA_access.h
M source/blender/makesrna/intern/rna_modifier.c
M source/blender/modifiers/CMakeLists.txt
M source/blender/modifiers/MOD_modifiertypes.h
A source/blender/modifiers/intern/MOD_rigiddeform.c
A source/blender/modifiers/intern/MOD_rigiddeform_system.cc
A source/blender/modifiers/intern/MOD_rigiddeform_system.h
A source/blender/modifiers/intern/MOD_rigiddeform_system.hpp
A source/blender/modifiers/intern/MOD_rigiddeform_system_wrapper.cc
M source/blender/modifiers/intern/MOD_util.c
===================================================================
diff --git a/build_files/cmake/macros.cmake b/build_files/cmake/macros.cmake
index 5b6e3fa0011..8d1677267cf 100644
--- a/build_files/cmake/macros.cmake
+++ b/build_files/cmake/macros.cmake
@@ -672,6 +672,7 @@ function(SETUP_BLENDER_SORTED_LIBS)
bf_intern_mikktspace
bf_intern_dualcon
bf_intern_cycles
+ extern_cholup
cycles_device
cycles_render
cycles_graph
@@ -691,6 +692,7 @@ function(SETUP_BLENDER_SORTED_LIBS)
bf_intern_clog
bf_intern_opensubdiv
bf_intern_numaapi
+ bf_intern_fast_svd
)
if(NOT WITH_SYSTEM_GLOG)
@@ -1060,7 +1062,7 @@ function(get_blender_version)
# So cmake depends on BKE_blender.h, beware of inf-loops!
CONFIGURE_FILE(${CMAKE_SOURCE_DIR}/source/blender/blenkernel/BKE_blender_version.h
- ${CMAKE_BINARY_DIR}/source/blender/blenkernel/BKE_blender_version.h.done)
+ ${CMAKE_BINARY_DIR}/source/blender/blenkernel/BKE_blender_version.h.done)
file(STRINGS ${CMAKE_SOURCE_DIR}/source/blender/blenkernel/BKE_blender_version.h _contents REGEX "^#define[ \t]+BLENDER_.*$")
@@ -1381,15 +1383,15 @@ function(find_python_package
unset(PYTHON_${_upper_package}_PATH CACHE)
find_path(PYTHON_${_upper_package}_PATH
NAMES
- ${package}
+ ${package}
HINTS
- "${PYTHON_LIBPATH}/"
- "${PYTHON_LIBPATH}/python${PYTHON_VERSION}/"
- "${PYTHON_LIBPATH}/python${_PY_VER_MAJOR}/"
+ "${PYTHON_LIBPATH}/"
+ "${PYTHON_LIBPATH}/python${PYTHON_VERSION}/"
+ "${PYTHON_LIBPATH}/python${_PY_VER_MAJOR}/"
PATH_SUFFIXES
- site-packages
- dist-packages
- vendor-packages
+ site-packages
+ dist-packages
+ vendor-packages
NO_DEFAULT_PATH
)
diff --git a/extern/CMakeLists.txt b/extern/CMakeLists.txt
index 2b18be71941..376b1d0e987 100644
--- a/extern/CMakeLists.txt
+++ b/extern/CMakeLists.txt
@@ -34,6 +34,7 @@ endif()
add_subdirectory(rangetree)
add_subdirectory(wcwidth)
+add_subdirectory(CholUp)
if(WITH_BULLET)
if(NOT WITH_SYSTEM_BULLET)
diff --git a/extern/CholUp/CMakeLists.txt b/extern/CholUp/CMakeLists.txt
new file mode 100644
index 00000000000..53eefcaaed8
--- /dev/null
+++ b/extern/CholUp/CMakeLists.txt
@@ -0,0 +1,21 @@
+set(INC
+ .
+)
+
+set(INC_SYS
+ ${EIGEN3_INCLUDE_DIRS}
+)
+
+set(SRC
+ source/CholUp/EliminationTreeMethods.cpp
+
+ source/CholUp/EliminationTreeMethods.h
+ source/CholUp/Matrix.hpp
+ source/CholUp/SparseMatrix_impl.h
+ source/CholUp/SparseMatrix.h
+ source/CholUp/SparseSupernodal.h
+ source/CholUp/SupernodalCholesky.h
+ source/CholUp/CholUp.hpp
+)
+
+blender_add_lib(extern_cholup "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/extern/CholUp/source/CholUp/CholUp.hpp b/extern/CholUp/source/CholUp/CholUp.hpp
new file mode 100644
index 00000000000..76688e57968
--- /dev/null
+++ b/extern/CholUp/source/CholUp/CholUp.hpp
@@ -0,0 +1 @@
+#include "SupernodalCholesky.h"
diff --git a/extern/CholUp/source/CholUp/EliminationTreeMethods.cpp b/extern/CholUp/source/CholUp/EliminationTreeMethods.cpp
new file mode 100644
index 00000000000..a44403ea03a
--- /dev/null
+++ b/extern/CholUp/source/CholUp/EliminationTreeMethods.cpp
@@ -0,0 +1,118 @@
+#include "EliminationTreeMethods.h"
+#include "SparseMatrix.h"
+
+namespace CholUp {
+
+int ereach(const SparseMatrix<double>& A, int NS, int k, int k0, const int* parent, const int* colMap, int* s, int* w)
+{
+ int i, len;
+ int top = NS;
+ int sk = colMap[k];
+
+ w[sk] = k;
+
+ for(int p = A.col[k]; p < A.diag[k]; ++p)
+ {
+ i = colMap[A.row[p]];
+
+ for(len = 0; w[i] < k0; i = parent[i])
+ {
+ s[len++] = i;
+ w[i] = k;
+ }
+
+ while(len > 0) s[--top] = s[--len];
+ }
+
+ return top;
+}
+
+void firstdesc (int n, int *parent, int *post, int *first, int *level)
+{
+ int len, i, k, r, s ;
+ for (i = 0 ; i < n ; i++) first [i] = -1 ;
+ for (k = 0 ; k < n ; k++)
+ {
+ i = post [k] ; /* node i of etree is kth postordered node */ len =0; /* traverse from i towards the root */
+ for (r = i ; r != -1 && first [r] == -1 ; r = parent [r], len++)
+ first [r] = k ;
+ len += (r == -1) ? (-1) : level [r] ; /* root node or end of path */
+ for (s = i ; s != r ; s = parent [s]) level [s] = len-- ;
+ }
+}
+
+int tdfs(int j, int k, int *head, const int *next, int *post, int *stack)
+{
+ int i, p, top = 0;
+ if (!head || !next || !post || !stack) return -1;
+
+ stack[0] = j;
+
+ while(top >= 0)
+ {
+ p = stack[top];
+ i = head[p];
+ if(i == -1)
+ {
+ --top;
+ post[k++] = p;
+ } else
+ {
+ head[p] = next[i];
+ stack[++top] = i;
+ }
+ }
+
+ return k;
+}
+
+void postOrdering(const int* parent, const int n, int* post)
+{
+ int k = 0;
+ int* w = new int[3 * n];
+
+ int* head = w;
+ int* next = w + n;
+ int* stack = w + 2 * n;
+
+ for(int j = 0; j < n; ++j) head[j] = -1;
+
+ for(int j = n-1; j >= 0; --j)
+ {
+ if(parent[j] == -1) continue;
+
+ next[j] = head[parent[j]];
+ head[parent[j]] = j;
+ }
+
+ for(int j = 0; j < n; ++j)
+ {
+ if(parent[j] != -1) continue;
+ k = tdfs(j, k, head, next, post, stack);
+ }
+
+ delete[] w;
+}
+
+int leaf (int i, int j, const int *first, int *maxfirst, int *prevleaf,
+ int *ancestor, int *jleaf)
+{
+ int q, s, sparent, jprev ;
+ if (!first || !maxfirst || !prevleaf || !ancestor || !jleaf) return (-1) ;
+ *jleaf = 0 ;
+ if (i <= j || first [j] <= maxfirst [i]) return (-1) ; /* j not a leaf */
+ maxfirst [i] = first [j] ; /* update max first[j] seen so far */
+ jprev = prevleaf [i] ; /* jprev = previous leaf of ith subtree */
+ prevleaf [i] = j ;
+ *jleaf = (jprev == -1) ? 1: 2 ; /* j is first or subsequent leaf */
+ if (*jleaf == 1) return (i) ; /* if 1st leaf, q = root of ith subtree */
+ for (q = jprev ; q != ancestor [q] ; q = ancestor [q]) ;
+ for (s = jprev ; s != q ; s = sparent)
+ {
+ sparent = ancestor [s] ; /* path compression */
+ ancestor [s] = q ;
+ }
+ return (q) ; /* q = least common ancester (jprev,j) */
+}
+
+} /* namespace CholUp */
\ No newline at end of file
diff --git a/extern/CholUp/source/CholUp/EliminationTreeMethods.h b/extern/CholUp/source/CholUp/EliminationTreeMethods.h
new file mode 100644
index 00000000000..f9be05f455f
--- /dev/null
+++ b/extern/CholUp/source/CholUp/EliminationTreeMethods.h
@@ -0,0 +1,113 @@
+#pragma once
+
+#include "SparseMatrix.h"
+
+namespace CholUp {
+
+int tdfs(int j, int k, int *head, const int *next, int *post, int *stack);
+
+void postOrdering(const int* parent, const int n, int* post);
+
+int leaf (int i, int j, const int *first, int *maxfirst, int *prevleaf,
+ int *ancestor, int *jleaf);
+
+void firstdesc (int n, int *parent, int *post, int *first, int *level);
+
+int ereach(const SparseMatrix<double>& A, int NS, int k, int k0, const int* parent, const int* colMap, int* s, int* w);
+
+template<class MatrixType>
+void computeColCounts(const MatrixType& A, int* parent, int* post, int* colcount /* out*/)
+{
+ int i, j, k, n, J, s, p, q, jleaf, *maxfirst, *prevleaf,
+ *ancestor, *w, *first, *delta ;
+ n = A.ncols;
+
+ s = 4*n;
+
+ delta = colcount;
+ w = new int[s]; /* get workspace */
+
+ ancestor = w ; maxfirst = w+n ; prevleaf = w+2*n ; first = w+3*n ;
+ for (k = 0 ; k < s ; k++) w [k] = -1 ; /* clear workspace w [0..s-1] */
+
+ for (k = 0 ; k < n ; k++) /* find first [j] */
+ {
+ j = post [k] ;
+ delta [j] = (first [j] == -1) ? 1 : 0 ; /* delta[j]=1 if j is a leaf */
+ for ( ; j != -1 && first [j] == -1 ; j = parent [j]) first [j] = k ;
+ }
+
+ const int *ATp = A.col;
+ const int *ATi = A.row;
+
+ for (i = 0 ; i < n ; i++) ancestor [i] = i ; /* each node in its own set */
+
+ for (k = 0 ; k < n ; k++)
+ {
+ j = post [k] ; /* j is the kth node in postordered etree */
+ if (parent [j] != -1) delta [parent [j]]-- ; /* j is not a root */
+ for (J = j ; J != -1 ; J = -1) /* J=j for LL'=A case */
+ {
+ for (p = A.diag[J] + 1 ; p < ATp [J+1] ; p++)
+ {
+ i = ATi [p] ;
+ q = leaf (i, j, first, maxfirst, prevleaf, ancestor, &jleaf);
+ if (jleaf >= 1) delta [j]++ ; /* A(i,j) is in skeleton */
+ if (jleaf == 2) delta [q]-- ; /* account for overlap in q */
+ }
+ }
+
+ if (parent [j] != -1) ancestor [j] = parent [j] ;
+ }
+ for (j = 0 ; j < n ; j++) /* sum up delta's of each child */
+ {
+ if (parent [j] != -1) colcount [parent [j]] += colcount [j] ;
+ }
+
+ delete[] w;
+}
+
+template<class MatrixType>
+void rowCounts(const MatrixType& A, int* parent, int* post, int* rowcount)
+{
+ int n = A.col.size() - 1;
+ const int* Ap = A.col.data();
+ const int* Ai = A.row.data(); /* get A */
+
+ int* w = new int[5 * n]; /* get workspace */
+ auto ancestor = w ;
+ auto maxfirst = w+n ;
+ auto prevleaf = w+2*n ;
+ auto first = w+3*n ;
+ auto level = w+4*n ;
+
+ firstdesc(n, parent, post, first, level) ;
+
+ for(int i = 0 ; i < n ; i++)
+ {
+ rowcount [i] = 1; /* count the diagonal of L */
+ prevleaf [i] = -1; /* no previous leaf of the ith row subtree */
+ maxfirst [i] = -1; /* max first[j] for node j in ith subtree */
+ ancestor [i] = i; /* every node is in its own set, by itself */
+ }
+
+ int jleaf;
+
+ for(int k = 0 ; k < n ; k++)
+ {
+ int j = post [k]; /* j is the kth node in the postordered etree */
+ for (int p = Ap [j] ; p < Ap [j+1] ; p++)
+ {
+ int i = Ai [p] ;
+ int q = leaf (i, j, first, maxfirst, prevleaf, ancestor, &jleaf) ;
+ if (jleaf) rowcount [i] += (level [j] - level [q]) ;
+ }
+
+ if (parent [j] != -1) ancestor [j] = parent [j] ;
+
+ }
+
+ delete[] w;
+}
+
+} /* namespace CholUp */
\ No newline at end of file
diff --git a/extern/CholUp/source/CholUp/Matrix.
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list