[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [37562] branches/soc-2011-avocado/blender: Basic implementation of the seam generation algorithm is done.
shuvro sarker
shuvro05 at gmail.com
Thu Jun 16 19:32:24 CEST 2011
Revision: 37562
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=37562
Author: shuvro
Date: 2011-06-16 17:32:24 +0000 (Thu, 16 Jun 2011)
Log Message:
-----------
Basic implementation of the seam generation algorithm is done. The code is restructured to make it more efficient. Most of the restructure ideas are given by Elubie. Some crashes are handled, Non-manifold mesh support is added with the restructured code. Combinatorial centers are added to make the result more accurate.
Modified Paths:
--------------
branches/soc-2011-avocado/blender/intern/autoseam/AutoseamUtility.cpp
branches/soc-2011-avocado/blender/intern/autoseam/AutoseamUtility.h
branches/soc-2011-avocado/blender/intern/autoseam/CMakeLists.txt
branches/soc-2011-avocado/blender/intern/autoseam/autoseam_C_API.cpp
branches/soc-2011-avocado/blender/intern/autoseam/autoseam_C_API.h
branches/soc-2011-avocado/blender/source/blender/editors/mesh/autoseam_tools.c
Added Paths:
-----------
branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.cpp
branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.h
branches/soc-2011-avocado/blender/intern/autoseam/AutoseamEigenspace.cpp
branches/soc-2011-avocado/blender/intern/autoseam/AutoseamEigenspace.h
Added: branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.cpp
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.cpp (rev 0)
+++ branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.cpp 2011-06-16 17:32:24 UTC (rev 37562)
@@ -0,0 +1,107 @@
+#include "AutoseamAdjacency.h"
+
+
+AutoseamAdjacency::AutoseamAdjacency(int dimension)
+{
+ m_adjacency = MatrixXd::Zero(dimension, dimension);
+}
+
+void AutoseamAdjacency::set(int row, int col, float value)
+{
+ m_adjacency(row, col) = value;
+ m_adjacency(col, row) = value;
+ // m_adjacency(row, col) = 1.0f;
+ // m_adjacency(col, row) = 1.0f;
+}
+
+
+int AutoseamAdjacency::get(int row, int col)
+{
+ return m_adjacency(row, col) > 0.9 ? 1 : 0;
+}
+
+AutoseamAdjacency::~AutoseamAdjacency()
+{
+ clear_eigenspaces();
+}
+
+void AutoseamAdjacency::clear_eigenspaces()
+{
+
+ for (std::vector<AutoseamEigenspace*>::iterator it = m_eigenspaces.begin(); it != m_eigenspaces.end(); ++it)
+ {
+ delete (*it);
+ }
+ m_eigenspaces.clear();
+}
+
+bool AutoseamAdjacency::generate_seam()
+{
+ MatrixXd& a = m_adjacency;
+
+ clear_eigenspaces();
+
+ int n = a.rows();
+ for (int i=0; i<n;++i) {
+ a(i,i) = 0.0;
+ double rowsum = a.row(i).sum();
+ a(i,i) = -rowsum;
+ }
+
+ Eigen::SelfAdjointEigenSolver<MatrixXd> es(a);
+ Eigen::VectorXd evalues(es.eigenvalues());
+ int f = 0;
+ bool found = false;
+ int seam_length=0;
+ MatrixXd aplus;
+ MatrixXd aminus;
+ while ( (f < n) && (f<30) ) {
+ // Eigenvalues seem to be sorted largest to smallest, we need the 30 smallest
+ // in the future only those will be calculated by the algorithm (if we use ARPACK)
+ AutoseamEigenspace* aes = new AutoseamEigenspace(evalues[n-f-1], es.eigenvectors().col(n-f-1));
+
+ // split Eigenspace into two subspaces F+ and F- where the ith entry in the eigenvector is positive/negative
+ aes->split();
+
+
+ aes->fill_adjacency(a, aplus, aminus);
+ // We filter out eigenspaces that give non-connected F+ and F- as in the paper
+ if (is_graph_connected(aplus) && is_graph_connected(aminus)) {
+ m_eigenspaces.push_back(aes);
+ found = true;
+ } else {
+ delete aes;
+ }
+ f++;
+ }
+ return found;
+}
+
+int AutoseamAdjacency::get_num_splits()
+{
+ return m_eigenspaces.size();
+}
+
+void AutoseamAdjacency::get_split(int n, int *fplus, unsigned int* nplus, int* fminus, unsigned int* nminus)
+{
+ if(m_eigenspaces.size())
+ m_eigenspaces[n]->get(fplus, nplus, fminus, nminus);
+ else
+ printf("No seam generation is possible");
+}
+
+// get the longest seam with connected subgraphs F+ and F-
+int AutoseamAdjacency::get_best_split()
+{
+ int max_length= 0;
+ int best= 0;
+ for (int i=0; i < m_eigenspaces.size(); ++i) {
+ AutoseamEigenspace* aes = m_eigenspaces[i];
+ int len = aes->get_seam_length(m_adjacency);
+ if (len>max_length) {
+ max_length = len;
+ best = i;
+ }
+ }
+ return best;
+}
\ No newline at end of file
Added: branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.h
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.h (rev 0)
+++ branches/soc-2011-avocado/blender/intern/autoseam/AutoseamAdjacency.h 2011-06-16 17:32:24 UTC (rev 37562)
@@ -0,0 +1,29 @@
+#ifndef AUTOSEAM_ADJACENCY_H
+#define AUTOSEAM_ADJACENCY_H
+
+#include "AutoseamUtility.h"
+#include "AutoseamEigenspace.h"
+#include <vector>
+
+class AutoseamAdjacency
+{
+ public:
+ AutoseamAdjacency(int dimension);
+ ~AutoseamAdjacency();
+
+ void set(int row, int col, float value);
+ int get(int row, int col);
+ const Eigen::MatrixXd& getMatrix() const { return m_adjacency; }
+ bool generate_seam();
+ void clear_eigenspaces();
+ int get_num_splits();
+ int get_best_split();
+ void get_split(int n, int *fplus, unsigned int* nplus, int* fminus, unsigned int* nminus);
+
+ private:
+ Eigen::MatrixXd m_adjacency;
+ std::vector<AutoseamEigenspace*> m_eigenspaces;
+
+};
+
+#endif
Added: branches/soc-2011-avocado/blender/intern/autoseam/AutoseamEigenspace.cpp
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/AutoseamEigenspace.cpp (rev 0)
+++ branches/soc-2011-avocado/blender/intern/autoseam/AutoseamEigenspace.cpp 2011-06-16 17:32:24 UTC (rev 37562)
@@ -0,0 +1,78 @@
+#include "AutoseamEigenspace.h"
+
+
+AutoseamEigenspace::AutoseamEigenspace(double eigenval, const Eigen::VectorXd& eigenvector)
+: e(eigenval), v(eigenvector)
+{
+
+}
+
+void AutoseamEigenspace::split()
+{
+ m_fplus.clear();
+ m_fminus.clear();
+ int n = v.size();
+ for (int i=0; i<n;++i) {
+ if (v[i] >= 0) {
+ m_fplus.push_back(i);
+ } else {
+ m_fminus.push_back(i);
+ }
+ }
+}
+
+
+void AutoseamEigenspace::fill_adjacency(const Eigen::MatrixXd& adj, Eigen::MatrixXd& adj_plus, Eigen::MatrixXd& adj_minus)
+{
+ adj_plus.resize(m_fplus.size(), m_fplus.size());
+ adj_minus.resize(m_fminus.size(), m_fminus.size());
+
+ int m, n;
+ for (m=0; m<m_fplus.size(); ++m) {
+ for (n=0; n<m_fplus.size(); ++n) {
+ adj_plus(m,n) = adj(m_fplus[m], m_fplus[n]);
+ }
+ }
+ for (m=0; m<m_fplus.size(); ++m) {
+ adj_plus(m,m) = 0.0;
+ }
+ for (m=0; m<m_fminus.size(); ++m) {
+ for (n=0; n<m_fminus.size(); ++n) {
+ adj_minus(m,n) = adj(m_fminus[m], m_fminus[n]);
+ }
+ }
+ for (m=0; m<m_fminus.size(); ++m) {
+ adj_minus(m,m) = 0.0;
+ }
+}
+
+
+void AutoseamEigenspace::get(int *fplus, unsigned int* nplus, int* fminus, unsigned int* nminus)
+{
+ for (int i=0; i<m_fplus.size(); ++i) {
+ fplus[i] = m_fplus[i];
+ }
+
+ *nplus = m_fplus.size();
+ for (int i=0; i<m_fminus.size(); ++i) {
+ fminus[i] = m_fminus[i];
+ }
+ *nminus = m_fminus.size();
+}
+
+
+int AutoseamEigenspace::get_seam_length(const Eigen::MatrixXd& adj)
+{
+ int count= 0;
+ for (int m = 0; m < m_fplus.size(); ++m)
+ {
+ for (int n = 0; n < m_fminus.size(); ++n) {
+ if (adj( m_fplus[m], m_fminus[n] ) > 0.05 ) {
+ count++;
+ break;
+ }
+ }
+ }
+ return count;
+}
+
Added: branches/soc-2011-avocado/blender/intern/autoseam/AutoseamEigenspace.h
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/AutoseamEigenspace.h (rev 0)
+++ branches/soc-2011-avocado/blender/intern/autoseam/AutoseamEigenspace.h 2011-06-16 17:32:24 UTC (rev 37562)
@@ -0,0 +1,24 @@
+#ifndef AUTOSEAM_EIGENSPACE
+#define AUTOSEAM_EIGENSPACE
+
+#include <vector>
+#include "AutoseamUtility.h"
+
+class AutoseamEigenspace
+{
+ public:
+ AutoseamEigenspace(double eigenval, const Eigen::VectorXd& eigenvector);
+ void split();
+ void fill_adjacency(const Eigen::MatrixXd& adj, Eigen::MatrixXd& adj_plus, Eigen::MatrixXd& adj_minus);
+ void get(int *fplus, unsigned int* nplus, int* fminus, unsigned int* nminus);
+ int get_seam_length(const Eigen::MatrixXd& adj);
+
+ private:
+ double e;
+ Eigen::VectorXd v;
+
+ std::vector<int> m_fplus;
+ std::vector<int> m_fminus;
+};
+
+#endif
Modified: branches/soc-2011-avocado/blender/intern/autoseam/AutoseamUtility.cpp
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/AutoseamUtility.cpp 2011-06-16 17:14:38 UTC (rev 37561)
+++ branches/soc-2011-avocado/blender/intern/autoseam/AutoseamUtility.cpp 2011-06-16 17:32:24 UTC (rev 37562)
@@ -25,19 +25,8 @@
*
* ***** END GPL LICENSE BLOCK *****
*/
-
-#include <Eigen/Core>
-#include <Eigen/Dense>
-#include <Eigen/Eigenvalues>
-
-#include <iostream>
-
#include "AutoseamUtility.h"
-using Eigen::MatrixXd;
-
-
-
AutoseamUtility::AutoseamUtility()
{
m_A << 1.0f, 2.0f, 0.0f,
Modified: branches/soc-2011-avocado/blender/intern/autoseam/AutoseamUtility.h
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/AutoseamUtility.h 2011-06-16 17:14:38 UTC (rev 37561)
+++ branches/soc-2011-avocado/blender/intern/autoseam/AutoseamUtility.h 2011-06-16 17:32:24 UTC (rev 37562)
@@ -30,7 +30,15 @@
#define DUMMY_CLASS_H_INCLUDED
#include <Eigen/Core>
+#include <Eigen/Dense>
+#include <Eigen/Eigenvalues>
+#include <iostream>
+using Eigen::MatrixXd;
+
+
+
+
class AutoseamUtility
{
public:
@@ -44,4 +52,43 @@
};
+enum GraphNodeColor { White, Gray, Black };
+
+static void depth_first_search(const MatrixXd& adjacency, int u, GraphNodeColor state[])
+{
+ int nNodes = adjacency.cols();
+ state[u] = Gray;
+ for (int v = 0; v < nNodes; v++) {
+ if (u != v) {
+ double adj = adjacency(u, v);
+ if ((adj>0.005) && state[v] == White) {
+ depth_first_search(adjacency, v, state);
+ }
+ }
+ }
+ state[u] = Black;
+}
+
+static bool is_graph_connected(const MatrixXd& adjacency)
+{
+ int nNodes = adjacency.cols();
+ if (nNodes > 0) {
+ GraphNodeColor *state = new GraphNodeColor[nNodes];
+ for (int i = 0; i < nNodes; i++)
+ state[i] = White;
+ depth_first_search(adjacency, 0, state);
+ bool connected = true;
+ for (int i = 0; i < nNodes; i++) {
+ if ( state[i] != Black ) {
+ connected = false;
+ break;
+ }
+ }
+ delete [] state;
+ return connected;
+ } else {
+ return false;
+ }
+}
+
#endif
\ No newline at end of file
Modified: branches/soc-2011-avocado/blender/intern/autoseam/CMakeLists.txt
===================================================================
--- branches/soc-2011-avocado/blender/intern/autoseam/CMakeLists.txt 2011-06-16 17:14:38 UTC (rev 37561)
+++ branches/soc-2011-avocado/blender/intern/autoseam/CMakeLists.txt 2011-06-16 17:32:24 UTC (rev 37562)
@@ -33,6 +33,10 @@
autoseam_C_API.cpp
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list