00001 /* 00002 File: MRVertex.cc 00003 00004 Function: Implements multi-res vertices used in edge contractions 00005 00006 Author: Andrew Willmott 00007 00008 Notes: 00009 */ 00010 00011 #include "gcl/MRVertex.h" 00012 #include "gcl/MRModel.h" 00013 #include "gcl/VecUtil.h" 00014 #include <stdio.h> 00015 00016 // use tree codes to speed things up for the simpler models 00017 //#define GCL_MR_USE_TREECODE 00018 00019 MRVertex::MRVertex() : 00020 parent(-1), 00021 level(0) 00022 { 00023 child[0] = -1; 00024 child[1] = -1; 00025 face[0] = -1; 00026 face[1] = -1; 00027 } 00028 00029 Void MRVertex::SetContraction( 00030 MRVertexes &vertices, 00031 Int iv, 00032 MRFlagsList &flags, 00033 Int child0, 00034 Int child1, 00035 Int face0, 00036 Int face1, 00037 GCLReal err 00038 ) 00039 { 00040 MRVertex &cv0 = vertices[child0], &cv1 = vertices[child1]; 00041 00042 Assert(IsRoot(), "Setting already contracted vertex"); 00043 flags[iv].Set(MRV_Inside); 00044 00045 child[0] = child0; 00046 child[1] = child1; 00047 face[0] = face0; 00048 face[1] = face1; 00049 00050 Assert(cv0.IsRoot(), "child[0] already contracted!"); 00051 Assert(cv1.IsRoot(), "child[1] already contracted!"); 00052 cv0.parent = iv; 00053 cv1.parent = iv; 00054 } 00055 00056 Void MRVertex::PrintID() 00057 { 00058 printf("v: level %d", level); 00059 // if (flags.IsSet(MRV_Inside)) 00060 // printf(" [inside]"); 00061 // if (flags.IsSet(MRV_Active)) 00062 // printf(" [active]"); 00063 if (IsLeaf()) 00064 printf(" [leaf]"); 00065 if (IsRoot()) 00066 printf(" [root]"); 00067 printf("\n"); 00068 } 00069 00070 Bool MRVertex::CanContract(Int iv, MRFlagsList &flags) 00071 { 00072 if (IsLeaf()) 00073 return(false); 00074 else 00075 return( 00076 flags[child[0]].IsSet(MRV_Active) && 00077 flags[child[1]].IsSet(MRV_Active) 00078 ); 00079 } 00080 00081 Bool MRVertex::CanExpand(Int iv, MRFlagsList &flags) 00082 { 00083 return(!IsLeaf() && flags[iv].IsSet(MRV_Active)); 00084 } 00085 00086 Void MRVertex::Contract(Int iv, MRFlagsList &flags) 00087 { 00088 Assert(flags[child[0]].IsSet(MRV_Active) && flags[child[1]].IsSet(MRV_Active), 00089 "contraction children are not active"); 00090 Assert(!flags[iv].IsSet(MRV_Active) && flags[iv].IsSet(MRV_Inside), 00091 "contraction target is active or not inside"); 00092 00093 flags[iv].Set(MRV_Active); 00094 flags[iv].UnSet(MRV_Inside); 00095 00096 flags[child[0]].UnSet(MRV_Active); 00097 flags[child[1]].UnSet(MRV_Active); 00098 00099 if (face[0] >= 0) 00100 flags[face[0]].UnSet(MRV_FaceActive); 00101 if (face[1] >= 0) 00102 flags[face[1]].UnSet(MRV_FaceActive); 00103 } 00104 00105 Void MRVertex::Expand(Int iv, MRFlagsList &flags) 00106 { 00107 flags[iv].UnSet(MRV_Active); 00108 flags[iv].Set(MRV_Inside); 00109 00110 flags[child[0]].Set(MRV_Active); 00111 flags[child[1]].Set(MRV_Active); 00112 00113 if (face[0] >= 0) 00114 flags[face[0]].Set(MRV_FaceActive); 00115 if (face[1] >= 0) 00116 flags[face[1]].Set(MRV_FaceActive); 00117 } 00118 00119 Void MRSetupHierarchy( 00120 MRVertexes &vertices, 00121 Int iv, 00122 TreeCodes &treeCodes, 00123 Int &height, 00124 Int level, 00125 Int treeCode 00126 ) 00128 { 00129 MRVertex &v = vertices[iv]; 00130 00131 v.level = level; 00132 00133 if (!v.IsLeaf()) 00134 { 00135 if (level >= 32) 00136 treeCode = 0xDEAD; 00137 00138 MRSetupHierarchy(vertices, v.child[0], 00139 treeCodes, height, level + 1, treeCode); 00140 00141 if (level < 32) 00142 treeCode = treeCode | (1 << level); 00143 00144 MRSetupHierarchy(vertices, v.child[1], 00145 treeCodes, height, level + 1, treeCode); 00146 } 00147 else 00148 { 00149 if (height <= level) 00150 height = level + 1; 00151 00152 treeCodes[iv] = treeCode; 00153 } 00154 } 00155 00156 Void MRVertex::PullProps(MRVertexes &vertices) 00157 { 00158 if (IsLeaf()) 00159 return; 00160 00161 vertices[child[0]].PullProps(vertices); 00162 vertices[child[1]].PullProps(vertices); 00163 00164 areaNormal = vertices[child[0]].areaNormal + vertices[child[1]].areaNormal; 00165 } 00166 00167 // --- MRCodes methods ------------------------------------------------------ 00168 00169 MRCodes::MRCodes() 00170 { 00171 } 00172 00173 Void MRCodes::AdjustVertices(MRVertexes &vertices, MRFlagsList &flags, 00174 Int faceIndexes[3], Int leafIndexes[3]) 00184 { 00185 Int i, j; 00186 00187 for (i = 0; i < 3; i++) 00188 { 00189 j = faceIndexes[i]; 00190 00191 if (flags[j].IsSet(MRV_Inside)) 00192 { 00193 #ifdef GCL_MR_USE_TREECODE 00194 if (vertices[j].level < 32) 00195 { 00196 UInt32 b = treeCode[i]; 00197 00198 // shift so child bit for first level is at position 0 00199 b >>= vertices[j].level; 00200 00201 // while we're still inside the boundary, move down the 00202 // tree, using the treeCode as a guide. 00203 00204 while (vertices[j].level < 32 && flags[j].IsSet(MRV_Inside)) 00205 { 00206 Assert(!flags[j].IsSet(MRV_Active), 00207 "vertex is both inside _and_ active"); 00208 00209 j = vertices[j].child[b & 1]; // move down. 00210 b >>= 1; // find next child bit 00211 } 00212 00213 if (flags[j].IsSet(MRV_Active)) 00214 { 00215 v[i] = j; 00216 continue; 00217 } 00218 } 00219 #endif 00220 // if can't use treeCode to get down to the active vertex, punt 00221 // to the leaves and move up. 00222 j = leafIndexes[i]; 00223 } 00224 00225 // move up the tree until we hit active vertex 00226 while (!flags[j].IsSet(MRV_Active)) 00227 { 00228 Assert(!vertices[j].IsRoot(), "no active vertex before top of vertex tree"); 00229 j = vertices[j].parent; 00230 } 00231 00232 faceIndexes[i] = j; 00233 } 00234 }