[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [29498] branches/soc-2010-rohith291991: Voronoi Cells code (BFS from constrained faces) done.
Rohith B V
rohith291991 at gmail.com
Thu Jun 17 00:22:59 CEST 2010
Revision: 29498
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=29498
Author: rohith291991
Date: 2010-06-17 00:22:59 +0200 (Thu, 17 Jun 2010)
Log Message:
-----------
Voronoi Cells code (BFS from constrained faces) done. Seems to work correctly for high poly meshes as well. So far so good. A lot of optimization will be necessary later though.
Modified Paths:
--------------
branches/soc-2010-rohith291991/source/blender/modifiers/intern/MOD_quadrangulate.c
Added Paths:
-----------
branches/soc-2010-rohith291991/intern/comiso/extern/CMesh.h
branches/soc-2010-rohith291991/intern/comiso/intern/CMesh.cpp
Added: branches/soc-2010-rohith291991/intern/comiso/extern/CMesh.h
===================================================================
--- branches/soc-2010-rohith291991/intern/comiso/extern/CMesh.h (rev 0)
+++ branches/soc-2010-rohith291991/intern/comiso/extern/CMesh.h 2010-06-16 22:22:59 UTC (rev 29498)
@@ -0,0 +1,73 @@
+#ifndef CMESH_H
+#define CMESH_H
+
+#include "comiso.h"
+
+//flags for CFace
+#define CF_CONSTRAINED (1)
+#define CF_VISITED (1<<2)
+
+//flags for CEdge
+#define CE_MARKED (1)
+
+//flags for CVert
+#define CV_MARKED (1)
+
+struct CFace;
+struct CEdge;
+struct CVert;
+
+typedef struct CVert
+{
+
+int * neighbors; //Indices of all neighboring vertices
+int index; //Index of the vertex
+int flag; //Flag for various purposes (if needed)
+int numNeighbors; //Number of neighboring vertices
+float co[3]; //Coordinates of the vertex
+
+}CVert;
+
+typedef struct CEdge{
+
+int index; //Index of the edge
+int p;// Period Jump for v1-v2. For v2-v1 it is -p
+int flag; //Flag for various purposes (eg. Cut graph)
+int v[2]; // Indices of vertices
+
+}CEdge;
+
+typedef struct CFace{
+
+int * neighbors; //Indices of all neighboring faces
+int index; //Index of the face
+int group; //Group index of the face
+int flag; //Flag for various purposes
+int numNeighbors; //Number of neighboring faces
+int v[4];// Indices of vertices. v4 is -1 if it is a triangle
+double theta; // Angle that the principle direction field makes with the edge represented by v1-v2
+
+}CFace;
+
+typedef struct CMesh
+{
+
+CVert* verts; //Vertex data
+CEdge * edges; //Edge data
+CFace * faces; //Face data
+int numFaces,numEdges,numVerts; // Self explanatory
+
+}CMesh;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+int generateVoronoiCells(CMesh * mesh);
+int generateDirectionField(CMesh *mesh);
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
Added: branches/soc-2010-rohith291991/intern/comiso/intern/CMesh.cpp
===================================================================
--- branches/soc-2010-rohith291991/intern/comiso/intern/CMesh.cpp (rev 0)
+++ branches/soc-2010-rohith291991/intern/comiso/intern/CMesh.cpp 2010-06-16 22:22:59 UTC (rev 29498)
@@ -0,0 +1,121 @@
+#include "../extern/CMesh.h"
+#include <vector>
+
+int generateVoronoiCells(CMesh* mesh)
+{
+
+ std::vector<std::vector <int>> currentFaces; //List of faces to expand for BFS/Dijkstra
+ int numCF=0; //Number of constrained faces
+ int j=0;
+
+ for(int i=0;i<mesh->numFaces;i++)
+ if(mesh->faces[i].flag & CF_CONSTRAINED)
+ {
+ mesh->faces[i].flag|= CF_VISITED;
+ mesh->faces[i].group=mesh->faces[i].index;
+ numCF++;
+ }
+
+ currentFaces.resize(numCF);
+
+ for(int i=0;i<mesh->numFaces;i++)
+ if(mesh->faces[i].flag & CF_CONSTRAINED)
+ {
+ currentFaces[j].push_back(mesh->faces[i].index);
+ j++;
+ }
+
+//Iterative BFS
+int terminate=1;
+
+while(terminate)
+{
+
+ terminate=0;
+
+ for(int i=0;i<numCF;i++)
+ {
+
+ std::vector<int> newFaces;
+ newFaces.resize(0);
+
+ for(int j=0;j<currentFaces[i].size();j++)
+ {
+
+ terminate++;
+
+ int index=currentFaces[i][j];
+ CFace *face=&(mesh->faces[index]);
+
+ for(int k=0;k<face->numNeighbors;k++)
+ {
+
+ int nIndex=face->neighbors[k];
+
+ if(!(mesh->faces[nIndex].flag & CF_VISITED))
+ {
+
+ mesh->faces[nIndex].flag |= CF_VISITED;
+ mesh->faces[nIndex].group=face->group;
+ newFaces.push_back(nIndex);
+
+ //Mark common vertices
+ for(int l=0;l<4;l++)
+ for(int k=0;k<4;k++)
+ if( (mesh->faces[index].v[l] == mesh->faces[nIndex].v[k])
+ && mesh->faces[index].v[k]!=-1)
+ mesh->verts[mesh->faces[index].v[l]].flag |= CV_MARKED;
+
+ }
+
+ }
+
+ }
+
+ currentFaces[i].resize(newFaces.size());
+
+ for(int l=0;l<newFaces.size();l++)
+ currentFaces[i][l]=newFaces[l];
+
+ }
+}
+
+// Mark visited edges
+// Remaining edges are in cut graph
+
+for(int i=0;i<mesh->numEdges;i++)
+{
+ int v1=mesh->edges[i].v[0];
+ int v2=mesh->edges[i].v[1];
+
+ if(mesh->verts[v1].flag & CV_MARKED
+ && mesh->verts[v2].flag & CV_MARKED )
+ {
+ mesh->edges[i].flag |= CE_MARKED;
+ mesh->edges[i].p=0;
+ }
+
+}
+
+//Dummy error condition
+if(0)
+{
+return 0;
+}
+
+return 1;
+}
+
+//TODO
+// Uses CoMiSo
+
+int generateDirectionField(CMesh* mesh)
+{
+
+if(0)
+{
+return 0;
+}
+
+return 1;
+}
Modified: branches/soc-2010-rohith291991/source/blender/modifiers/intern/MOD_quadrangulate.c
===================================================================
--- branches/soc-2010-rohith291991/source/blender/modifiers/intern/MOD_quadrangulate.c 2010-06-16 19:27:29 UTC (rev 29497)
+++ branches/soc-2010-rohith291991/source/blender/modifiers/intern/MOD_quadrangulate.c 2010-06-16 22:22:59 UTC (rev 29498)
@@ -26,6 +26,7 @@
#include "DNA_meshdata_types.h"
#include "comiso.h"
+#include "CMesh.h"
#include "BLI_math.h"
#include "BKE_cdderivedmesh.h"
@@ -61,18 +62,25 @@
{
Comiso solver;
+ CMesh cm;
CVect solution;
QuadrangulateModifierData *dmd = (QuadrangulateModifierData*) md;
DerivedMesh *dm = derivedData, *result = NULL;
MVert *mvert;
MFace *mface;
- int totvert, totface;
+ MEdge *medge;
+ int totvert, totface,totedge;
int a, numTris;
+ int i,j;
+ int l,k;
mvert = dm->getVertArray(dm);
+ medge = dm->getEdgeArray(dm);
mface = dm->getFaceArray(dm);
+
totvert = dm->getNumVerts(dm);
totface = dm->getNumFaces(dm);
+ totedge = dm->getNumEdges(dm);
//--------------Quadrangulate Tool--------------//
@@ -81,6 +89,7 @@
for (a=0; a<totface; a++)
{
MFace *mf = &mface[a];
+ mf->flag;
numTris++;
if (mf->v4) numTris++;
}
@@ -94,11 +103,139 @@
//TODO
+ //Copy DerivedMesh into CMesh and fill in relevant face/vertex connectivity data
+
+ cm.numVerts=totvert;
+ cm.numEdges=totedge;
+ cm.numFaces=totface;
+
+
+ cm.verts=MEM_mallocN(sizeof(CVert)*totvert, "vertices");
+ cm.edges=MEM_mallocN(sizeof(CEdge)*totedge, "edges");
+ cm.faces=MEM_mallocN(sizeof(CFace)*totface, "faces");
+
+ for(a=0;a<totvert;a++)
+ {
+
+ cm.verts[a].co[0] = mvert[a].co[0];
+ cm.verts[a].co[1] = mvert[a].co[1];
+ cm.verts[a].co[2] = mvert[a].co[2];
+
+ cm.verts[a].index = a;
+ cm.verts[a].flag = 0;
+ cm.verts[a].neighbors = NULL;
+ cm.verts[a].numNeighbors = 0;
+
+ }
+
+ for(a=0;a<totedge;a++)
+ {
+
+ cm.edges[a].v[0] = medge[a].v1;
+ cm.edges[a].v[1] = medge[a].v2;
+
+ cm.edges[a].index = a;
+ cm.edges[a].flag = 0;
+ cm.edges[a].p = 0;
+
+ }
+
+ for(a=0;a<totface;a++)
+ {
+
+ cm.faces[a].v[0] = mface[a].v1;
+ cm.faces[a].v[1] = mface[a].v2;
+ cm.faces[a].v[2] = mface[a].v3;
+
+ if(mface[a].v4)
+ cm.faces[a].v[3] = mface[a].v4;
+ else
+ cm.faces[a].v[3] = -1;
+
+ cm.faces[a].neighbors = NULL;
+ cm.faces[a].numNeighbors = 0;
+ cm.faces[a].index = a;
+ cm.faces[a].group = 0;
+ cm.faces[a].flag = 0;
+ cm.faces[a].theta = 0;
+
+ }
+
+
+ for(i=0;i<totface;i++)
+ for(j=i+1;j<totface;j++)
+ if(j!=i)
+ {
+
+ int count=0;
+
+ for(l=0;l<4;l++)
+ {
+ for(k=0;k<4;k++)
+ {
+
+ if(cm.faces[i].v[l]==cm.faces[j].v[k]&&cm.faces[j].v[k]!=-1)
+ count++;
+
+ }
+
+ }
+ if(count>=2)
+ {
+ if(cm.faces[i].neighbors==NULL)
+ cm.faces[i].neighbors=MEM_mallocN((sizeof(int)*(++cm.faces[i].numNeighbors)),"neighbors");
+ else
+ cm.faces[i].neighbors=MEM_reallocN(cm.faces[i].neighbors,(sizeof(int)*(++cm.faces[i].numNeighbors)));
+
+ cm.faces[i].neighbors[cm.faces[i].numNeighbors-1]=cm.faces[j].index;
+
+ if(cm.faces[j].neighbors==NULL)
+ cm.faces[j].neighbors=MEM_mallocN((sizeof(int)*(++cm.faces[j].numNeighbors)),"neighbors");
+ else
+ cm.faces[j].neighbors=MEM_reallocN(cm.faces[j].neighbors,(sizeof(int)*(++cm.faces[j].numNeighbors)));
+
+ cm.faces[j].neighbors[cm.faces[j].numNeighbors-1]=cm.faces[i].index;
+
+ }
+
+
+ }
+
+ for(i=0;i<totface;i++)
+ {
+
+ printf("Face Index: %d\n",cm.faces[i].index);
+ printf("Neighbors: ");
+
+ for(j=0;j<cm.faces[i].numNeighbors;j++)
+ printf("%d ",cm.faces[i].neighbors[j]);
+
+ printf("\n");
+
+ }
+
+ cm.faces[3].flag |= CF_CONSTRAINED;
+ cm.faces[10].flag |= CF_CONSTRAINED;
+
+ generateVoronoiCells(&cm);
+
+ for(a=0;a<totface;a++)
+ printf("Group no: %d\n",cm.faces[a].group);
+
+
+ //TODO Get efficient and correct way to mark edges of cut graph
+
+ for(a=0;a<totedge;a++)
+ if(!(cm.edges[a].flag & CE_MARKED))
+ printf("Edge not marked: %d\n",cm.edges[a].index);
+
// Extract face angles, period jumps and other relevant data from the mesh
+ //generateDirectionField(&cm);
//Set up constraint and mesh matrices and ids to round
+
// USE BLENDER MEM FUNCS
// Fill solver.mdata
More information about the Bf-blender-cvs
mailing list