[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