00001 /* 00002 File: MeshJoin.cc 00003 00004 Notes: Requires triangles to share a single vertex array 00005 00006 Calling conventions: 00007 Call Init() with the number of vertices in the model 00008 Call StartGroup() for each surface group 00009 Call AddTriangle for all faces in that group 00010 Call EndGroup() when done. 00011 Repeat the last 3 calls as necessary. 00012 00013 Author: Andrew Willmott 00014 00015 Notes: 00016 */ 00017 00018 #include "MeshJoin.h" 00019 00020 #define MJ_DBG if (0) cerr 00021 00022 static Int tNextEdge3[3] = { 1, 2, 0 }; 00023 static Int tNextEdge4[4] = { 1, 2, 3, 0 }; 00024 00025 Void MeshJoin::Init(Int numVertices) 00026 { 00027 vertexFaces = new FacePtr[numVertices]; 00028 vertexEdges = new Edge[numVertices]; 00029 SELF.numVertices = numVertices; 00030 surfaceVertices = numVertices; 00031 } 00032 00033 Void MeshJoin::StartGroup() 00034 { 00035 Int i; 00036 00037 for (i = 0; i < numVertices; i++) 00038 vertexFaces[i] = 0; 00039 for (i = 0; i < numVertices; i++) 00040 vertexEdges[i] = 0; 00041 } 00042 00043 Bool MeshJoin::EdgesMatch( 00044 FacePtr face1, 00045 Edge edge1, 00046 FacePtr face2, 00047 Edge edge2 00048 ) 00049 { 00050 return( 00051 // shared vertex? 00052 (face1->index[edge1] == face2->index[edge2]) 00053 // same normal? 00054 && (dot(face1->Normal(), face2->Normal()) > 0.1) 00055 // same material? 00056 && (face1->Reflectance() == face2->Reflectance()) 00057 ); 00058 } 00059 00060 00061 Void MeshJoin::AddTriangle(Face *addFace) 00062 { 00063 Int i, j, k; 00064 Int n = addFace->Sides(); 00065 Int *nextEdge; 00066 FacePtr curFace, *curFacePtr; 00067 Edge curEdge, *curEdgePtr; 00068 Int vIndex; 00069 Bool match[4]; 00070 00071 if (addFace->IsTri()) 00072 nextEdge = tNextEdge3; 00073 else 00074 nextEdge = tNextEdge4; 00075 00076 /* 00077 Each vertex has a list of unmatched incident edges 00078 (where unmatched means that we haven't found a neighbouring 00079 triangle along that edge.) 00080 When we add a triangle, we first check to see whether 00081 an edge is present in this list. If it is, we remove it, 00082 and connect the two faces along that edge. If it is not, 00083 we add it to the list. 00084 */ 00085 00086 // for all vertices... 00087 00088 for (i = 0; i < n; i++) 00089 { 00090 j = nextEdge[i]; // next vertex 00091 k = nextEdge[j]; 00092 00093 addFace->clrIdx[i] = addFace->index[i]; 00094 00095 MJ_DBG << "vertex " << j << " = " << addFace->index[j] << endl; 00096 00097 // Check outgoing edge against the vertex's 00098 // edge list. 00099 00100 // we will be looking at vertex j 00101 // incident edge is (i)->(j), outgoing edge is (j)->(k) 00102 00103 vIndex = addFace->index[j]; 00104 00105 // we first check the edge list at vertex (j) and try 00106 // to locate an edge which starts from vertex (i). 00107 00108 curFacePtr = &vertexFaces[vIndex]; 00109 curEdgePtr = &vertexEdges[vIndex]; 00110 curFace = *curFacePtr; 00111 curEdge = *curEdgePtr; 00112 00113 match[j] = false; 00114 00115 while (curFace) 00116 { 00117 // Do we have an edge match? 00118 MJ_DBG << "checking edge to vertex " << curFace->index[curEdge] 00119 << endl; 00120 00121 if (EdgesMatch(curFace, curEdge, addFace, k)) 00122 { 00123 MJ_DBG << "matched." << endl; 00124 00125 // Yes! remove curEdge from the list 00126 *curFacePtr = curFace->nbFace[curEdge]; 00127 *curEdgePtr = curFace->nbEdge[curEdge]; 00128 00129 // connect the two triangles that share this edge 00130 addFace->nbFace[j] = curFace; 00131 addFace->nbEdge[j] = curEdge; 00132 curFace->nbFace[curEdge] = addFace; 00133 curFace->nbEdge[curEdge] = j; 00134 00135 Assert(addFace->index[j] == curFace->index[nextEdge[curEdge]], 00136 "1st vertices"); 00137 Assert(addFace->index[k] == curFace->index[curEdge], 00138 "2nd vertices"); 00139 00140 // and quit. 00141 match[j] = true; 00142 break; 00143 } 00144 00145 MJ_DBG << "didn't match." << endl; 00146 00147 // If not, move on to next edge... 00148 curFacePtr = &curFace->nbFace[curEdge]; 00149 curEdgePtr = &curFace->nbEdge[curEdge]; 00150 curFace = *curFacePtr; 00151 curEdge = *curEdgePtr; 00152 } 00153 00154 // If there was no match, we add the incoming edge to the vertex's 00155 // edge list. 00156 } 00157 00158 for (i = 0; i < n; i++) 00159 { 00160 j = nextEdge[i]; // next vertex 00161 00162 if (!match[i]) 00163 { 00164 vIndex = addFace->index[j]; 00165 00166 MJ_DBG << "adding unmatched edge " << i << " to list." << endl; 00167 // set this edge to point to first member of the list... 00168 addFace->nbFace[i] = vertexFaces[vIndex]; 00169 addFace->nbEdge[i] = vertexEdges[vIndex]; 00170 00171 // then set the start of the list to point to this edge 00172 vertexFaces[vIndex] = addFace; 00173 vertexEdges[vIndex] = i; 00174 } 00175 } 00176 } 00177 00178 Void MeshJoin::SetFaceChainVertices(Face *f, Int edge, Int i) 00179 // Sets the colour index to i of all faces connected to f around 00180 // the point at the end of 'edge'. 00181 { 00182 if (!f) 00183 return; 00184 00185 Int ccwEdge; 00186 00187 // find the next face around the point 00188 if (f->IsTri()) 00189 ccwEdge = tNextEdge3[edge]; 00190 else 00191 ccwEdge = tNextEdge4[edge]; 00192 00193 f->clrIdx[ccwEdge] = i; 00194 00195 SetFaceChainVertices(f->nbFace[ccwEdge], f->nbEdge[ccwEdge], i); 00196 } 00197 00198 Void MeshJoin::EndGroup() 00199 { 00200 Int i, n; 00201 FacePtr curFace, nextFace; 00202 Edge curEdge, nextEdge; 00203 00204 // Finally, we pass through the vertex face lists again, and 00205 // set the neighbour fields of all unmatched edges to 0, 00206 // to mark that they're not connected to anything. 00207 // (We have to do this because we've been using these fields 00208 // to help store the unconnected edge list.) 00209 00210 // For vertices that share several disconnected faces (i.e., there 00211 // is a surface discontinuity adjacent to the edge), we must make 00212 // sure that each disconnected segment has its own colour/normal 00213 // corresponding to that vertex. Otherwise we end up using the 00214 // same colour for two faces that share a vertex but are not 00215 // continuous. 00216 00217 for (i = 0; i < numVertices; i++) 00218 // Cycle through the remaining unmatched edges. 00219 { 00220 // head of the edge list for this vertex 00221 curFace = vertexFaces[i]; 00222 curEdge = vertexEdges[i]; 00223 00224 while (curFace) 00225 { 00226 // Store next edge... 00227 nextFace = curFace->nbFace[curEdge]; 00228 nextEdge = curFace->nbEdge[curEdge]; 00229 00230 // clear nbFace pointer 00231 curFace->nbFace[curEdge] = 0; 00232 00233 // move on to next edge in the list 00234 curFace = nextFace; 00235 curEdge = nextEdge; 00236 00237 // Fill in a new colour index for all faces connected to this edge 00238 // around this vertex. 00239 // (Need to do this for all unmatched edges but the first one, 00240 // which retains its original setting.) 00241 if (curFace) 00242 SetFaceChainVertices(curFace, curEdge, surfaceVertices++); 00243 } 00244 } 00245 } 00246 00247 Int MeshJoin::Finished() 00248 { 00249 delete[] vertexFaces; 00250 delete[] vertexEdges; 00251 return(surfaceVertices); 00252 }