Changeset 1072 for GTP/trunk/Lib/Vis/Preprocessing
- Timestamp:
- 07/03/06 02:03:59 (18 years ago)
- Location:
- GTP/trunk/Lib/Vis/Preprocessing/src
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
GTP/trunk/Lib/Vis/Preprocessing/src/Containers.h
r1001 r1072 4 4 #include <vector> 5 5 #include <queue> 6 #include <map> 6 7 7 8 using namespace std; … … 54 55 typedef vector<IndexedBoundingBox> IndexedBoundingBoxContainer; 55 56 57 typedef std::map<int, Intersectable *> ObjectMap; 58 56 59 } 57 60 -
GTP/trunk/Lib/Vis/Preprocessing/src/Intersectable.h
r1020 r1072 8 8 9 9 struct VssRayContainer; 10 class KdLeaf; 10 11 11 12 class Intersectable { … … 17 18 int mMailbox; 18 19 19 // unique object Id20 /// unique object Id 20 21 int mId; 21 22 22 // universal counter23 /// universal counter 23 24 int mCounter; 24 25 25 // object based pvs26 /// object based pvs 26 27 KdPvs mKdPvs; 27 28 29 /// kd leaves that this intersectable belongs to 30 std::vector<KdLeaf *> mKdLeaves; 31 28 32 enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE, VIEW_CELL, OGRE_MESH_INSTANCE }; 29 33 -
GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.h
r1002 r1072 188 188 /** pointers to occluders contained in this node */ 189 189 ObjectContainer mObjects; 190 190 191 /** Objects that are part of several leaves. 192 */ 193 ObjectMap mMultipleObjects; 194 191 195 /** Ray set description of the rays passing through this node */ 192 196 PassingRaySet mPassingRays; -
GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp
r1052 r1072 5253 5253 5254 5254 // export rays 5255 if ( 1&& mExportRays)5255 if (0 && mExportRays) 5256 5256 { 5257 5257 exporter->ExportRays(visRays, RgbColor(0, 1, 0)); … … 5262 5262 // HACK: export without clip plane 5263 5263 const bool b = mUseClipPlaneForViz; 5264 mUseClipPlaneForViz = false; 5264 if (0) 5265 mUseClipPlaneForViz = false; 5265 5266 5266 5267 ExportViewCellsForViz(exporter); … … 5336 5337 5337 5338 raysOut = min((int)rays.size(), 100); 5338 5339 Debug << "here12 " << raysOut << endl;5340 5339 5341 5340 // collect intial view cells -
GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp
r1047 r1072 1230 1230 ++ contributingSamples; 1231 1231 1232 // note: vss rays are never deleted 1232 1233 if (0) leaf->mVssRays.push_back(new VssRay(*ray)); 1233 1234 } … … 1610 1611 bestAxis = axis; 1611 1612 } 1612 else if (nCostRatio[axis] < nCostRatio[bestAxis]) 1613 /*else if (nCostRatio[axis] < nCostRatio[bestAxis]) 1614 { 1613 1615 Debug << "taking split along longest axis (" << bestAxis << ") instead of (" << axis << ")" << endl; 1614 1616 }*/ 1617 1615 1618 } 1616 1619 else … … 1629 1632 1630 1633 //-- assign values 1634 1631 1635 axis = bestAxis; 1632 1636 pFront = nProbFront[bestAxis]; … … 1646 1650 1647 1651 //Debug << "best axis: " << bestAxis << " pos " << nPosition[bestAxis] << endl; 1648 //Debug << "!!!!!!!!!!!!!!" << endl; 1652 1649 1653 return nCostRatio[bestAxis]; 1650 1654 } … … 1659 1663 { 1660 1664 // HACK matt: subdivide regularily to certain depth 1661 if (data.mDepth < 0) 1662 { 1663 cout << "d: " << data.mDepth << endl; 1665 if (data.mDepth < 0) // question matt: why depth < 0 ? 1666 { 1667 cout << "depth: " << data.mDepth << endl; 1668 1664 1669 // return axis aligned split 1665 1670 AxisAlignedBox3 box; … … 1675 1680 bestPlane = Plane3(norm, position); 1676 1681 splitAxis = axis; 1682 1677 1683 return true; 1678 1684 } … … 2509 2515 2510 2516 2511 void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const 2517 void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, 2518 bool onlyValid) const 2512 2519 { 2513 2520 ViewCell::NewMail(); -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp
r1052 r1072 777 777 ++ contributingSamples; 778 778 779 // warning: rays get never deleted! 779 780 if (0) leaf->mVssRays.push_back(new VssRay(*ray)); 780 781 } … … 803 804 float pos; 804 805 805 // float values => don't compare with exact values806 806 if (0) 807 807 { 808 // float values => don't compare with exact values 808 809 minBand += Limits::Small; 809 810 maxBand -= Limits::Small; … … 816 817 817 818 pos = (*ri).ExtrapOrigin(axis); 818 // clamp to min / max band819 if (0) ClipValue(pos, minBand, maxBand);820 819 820 if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band 821 821 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 822 822 pos, (*ri).mRay)); 823 823 824 824 pos = (*ri).ExtrapTermination(axis); 825 // clamp to min / max band 826 if (0) ClipValue(pos, minBand, maxBand); 825 826 if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band 827 827 828 828 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, … … 831 831 832 832 stable_sort(mSplitCandidates->begin(), mSplitCandidates->end()); 833 } 834 835 836 int VspTree::GetPvsContribution(Intersectable *object) const 837 { 838 int pvsContri = 0; 839 840 KdPvsMap::const_iterator kit, kit_end = object->mKdPvs.mEntries.end(); 841 842 Intersectable::NewMail(); 843 844 // Search kd leaves this object is attached to 845 for (kit = object->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 846 { 847 KdNode *l = (*kit).first; 848 849 // new object found during sweep 850 // => increase pvs contribution of this kd node 851 if (!l->Mailed()) 852 { 853 l->Mail(); 854 ++ pvsContri; 855 } 856 } 857 858 return pvsContri; 859 } 860 861 862 void VspTree::PrepareHeuristics(const RayInfoContainer &rays) 863 { 864 ObjectContainer objects; 865 866 // Collect all pvs that can be seen from the view cell 867 CollectPvs(rays, objects); 868 869 // adjust kd node info table 870 // for each object the entry must be updated 871 // which belongs to the same kd nodes 872 ObjectContainer::const_iterator oit, oit_end = objects.end(); 873 874 for (oit = objects.begin(); oit != oit_end; ++ oit) 875 { 876 Intersectable *obj = *oit; 877 // TODO 878 //UpdateKdNodeInfo(obj); 879 } 880 } 881 882 883 int VspTree::GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes) 884 { 885 // TODO: 886 // use kd info table to apply set theory in order to 887 // sort out dublicate pvs entries due to objects which 888 // belong to more than one kd leaves. 889 #if TODO 890 KdPvsMap::const_iterator kit, kit_end = obj->mKdPvs.mEntries.end(); 891 892 // Search kd leaves this object is attached to 893 for (kit = obj->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 894 { 895 KdNode *l = (*kit).first; 896 897 // new object found during sweep 898 // => increase pvs contribution of this kd node 899 if (!l->Mailed()) 900 { 901 l->Mail(); 902 ++ pvsContr; 903 } 904 } 905 #endif 906 return 0; 833 907 } 834 908 … … 875 949 RayInfoContainer::const_iterator ri, ri_end = rays.end(); 876 950 877 // set all object as belonging to the front pvs 951 //-- set all object as belonging to the front pvs 952 878 953 for(ri = rays.begin(); ri != ri_end; ++ ri) 879 954 { … … 1015 1090 1016 1091 1092 void VspTree::EvalPvsIncr(ObjectMap &multipleObjects, 1093 KdLeaf *leaf, 1094 const SortableEntry &ci, 1095 int &pvsLeft, 1096 int &pvsRight) const 1097 { 1098 int pvsSize = 0; 1099 1100 if (ci.type == SortableEntry::ERayMin) 1101 { 1102 if (!leaf->Mailed()) 1103 { 1104 leaf->Mail(); 1105 pvsLeft += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size(); 1106 1107 // add duplicates 1108 ObjectMap::const_iterator oit, oit_end = leaf->mMultipleObjects.end(); 1109 1110 for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit) 1111 { 1112 const int id = (*oit)->first; 1113 Intersectable *object = (*oit)->second; 1114 1115 if (multipleObjects[id] != object) // object not previously in pvs 1116 { 1117 multipleObjects[id] = object; 1118 ++ pvsLeft; 1119 } 1120 1121 } 1122 } 1123 } 1124 else if (ci.type == SortableEntry::ERayMax) 1125 { 1126 if (-- leaf->mCounter == 0) 1127 pvsRight += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size(); 1128 } 1129 } 1130 1131 1132 float VspTree::EvalKdCostHeuristics(const RayInfoContainer &rays, 1133 const AxisAlignedBox3 &box, 1134 const int pvsSize, 1135 const int axis, 1136 float &position) 1137 { 1138 const float minBox = box.Min(axis); 1139 const float maxBox = box.Max(axis); 1140 1141 const float sizeBox = maxBox - minBox; 1142 1143 const float minBand = minBox + mMinBand * sizeBox; 1144 const float maxBand = minBox + mMaxBand * sizeBox; 1145 1146 SortSplitCandidates(rays, axis, minBand, maxBand); 1147 1148 // go through the lists, count the number of objects left and right 1149 // and evaluate the following cost funcion: 1150 // C = ct_div_ci + (ql*rl + qr*rr)/queries 1151 1152 int pvsl = 0; 1153 int pvsr = pvsSize; 1154 1155 int pvsBack = pvsl; 1156 int pvsFront = pvsr; 1157 1158 float sum = (float)pvsSize * sizeBox; 1159 float minSum = 1e20f; 1160 1161 1162 // if no good split can be found, take mid split 1163 position = minBox + 0.5f * sizeBox; 1164 1165 // the relative cost ratio 1166 float ratio = /*Limits::Infinity;*/99999999.0f; 1167 bool splitPlaneFound = false; 1168 1169 Intersectable::NewMail(); 1170 KdNode::NewMail(); 1171 1172 RayInfoContainer::const_iterator ri, ri_end = rays.end(); 1173 1174 //-- set all kd nodes as belonging to the front pvs 1175 1176 for (ri = rays.begin(); ri != ri_end; ++ ri) 1177 { 1178 Intersectable *oObject = (*ri).mRay->mOriginObject; 1179 1180 if (oObject) 1181 { 1182 KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end(); 1183 1184 for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 1185 { 1186 KdNode *node = (*kit).first; 1187 1188 if (!node->Mailed()) 1189 { 1190 node->Mail(); 1191 //node->mCounter = 1; 1192 } 1193 else 1194 { 1195 //++ node->mCounter; 1196 } 1197 } 1198 } 1199 1200 Intersectable *tObject = (*ri).mRay->mTerminationObject; 1201 1202 if (tObject) 1203 { 1204 KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end(); 1205 1206 for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 1207 { 1208 KdNode *node = (*kit).first; 1209 1210 if (!node->Mailed()) 1211 { 1212 node->Mail(); 1213 //node->mCounter = 1; 1214 } 1215 else 1216 { 1217 //++ node->mCounter; 1218 } 1219 } 1220 } 1221 } 1222 1223 Intersectable::NewMail(); 1224 1225 vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end(); 1226 1227 ObjectMap multipleObjectsLeft, multipleObjectsRight; 1228 1229 1230 // -- traverse through visibility events 1231 1232 for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci) 1233 { 1234 VssRay *ray; 1235 ray = (*ci).ray; 1236 1237 Intersectable *oObject = ray->mOriginObject; 1238 1239 KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end(); 1240 1241 if (oObject) 1242 { 1243 for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 1244 { 1245 KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first); 1246 1247 EvalPvsIncr(multipleObjectsLeft, node, *ci, pvsl, pvsr); 1248 } 1249 } 1250 1251 Intersectable *tObject = ray->mOriginObject; 1252 1253 if (tObject) 1254 { 1255 for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit) 1256 { 1257 KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first); 1258 1259 EvalPvsIncr(multipleObjectsRight, node, *ci, pvsl, pvsr); 1260 } 1261 } 1262 1263 1264 // Note: sufficient to compare size of bounding boxes of front and back side? 1265 if (((*ci).value >= minBand) && ((*ci).value <= maxBand)) 1266 { 1267 sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value); 1268 1269 //Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << endl; 1270 //Debug << "cost= " << sum << endl; 1271 1272 if (sum < minSum) 1273 { 1274 splitPlaneFound = true; 1275 1276 minSum = sum; 1277 position = (*ci).value; 1278 1279 pvsBack = pvsl; 1280 pvsFront = pvsr; 1281 } 1282 } 1283 } 1284 1285 1286 // -- compute cost 1287 1288 const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize(); 1289 const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize(); 1290 1291 const float pOverall = sizeBox; 1292 const float pBack = position - minBox; 1293 const float pFront = maxBox - position; 1294 1295 const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit); 1296 const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit); 1297 const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit); 1298 1299 const float oldRenderCost = penaltyOld * pOverall + Limits::Small; 1300 const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack; 1301 1302 if (splitPlaneFound) 1303 { 1304 ratio = newRenderCost / oldRenderCost; 1305 } 1306 //if (axis != 1) 1307 //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox) 1308 // <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl; 1309 1310 return ratio; 1311 } 1312 1313 1314 #if TODO 1315 1316 float VspTree::EvalLocalCostHeuristicsNonIncremential(const RayInfoContainer &rays, 1317 const AxisAlignedBox3 &box, 1318 const int pvsSize, 1319 const int axis, 1320 float &position) 1321 { 1322 const float minBox = box.Min(axis); 1323 const float maxBox = box.Max(axis); 1324 1325 const float sizeBox = maxBox - minBox; 1326 1327 const float minBand = minBox + mMinBand * sizeBox; 1328 const float maxBand = minBox + mMaxBand * sizeBox; 1329 1330 SortSplitCandidates(rays, axis, minBand, maxBand); 1331 1332 // go through the lists, count the number of objects left and right 1333 // and evaluate the following cost funcion: 1334 // C = ct_div_ci + (ql*rl + qr*rr)/queries 1335 1336 int pvsl = 0; 1337 int pvsr = pvsSize; 1338 1339 int pvsBack = pvsl; 1340 int pvsFront = pvsr; 1341 1342 float sum = (float)pvsSize * sizeBox; 1343 float minSum = 1e20f; 1344 1345 1346 // if no good split can be found, take mid split 1347 position = minBox + 0.5f * sizeBox; 1348 1349 // the relative cost ratio 1350 float ratio = /*Limits::Infinity;*/99999999.0f; 1351 bool splitPlaneFound = false; 1352 1353 Intersectable::NewMail(); 1354 1355 RayInfoContainer::const_iterator ri, ri_end = rays.end(); 1356 1357 //-- set all object as belonging to the front pvs 1358 1359 for(ri = rays.begin(); ri != ri_end; ++ ri) 1360 { 1361 // Note: sufficient to compare size of bounding boxes of front and back side? 1362 if (((*ci).value >= minBand) && ((*ci).value <= maxBand)) 1363 { 1364 sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value); 1365 1366 //Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << endl; 1367 //Debug << "cost= " << sum << endl; 1368 1369 if (sum < minSum) 1370 { 1371 splitPlaneFound = true; 1372 1373 minSum = sum; 1374 position = (*ci).value; 1375 1376 pvsBack = pvsl; 1377 pvsFront = pvsr; 1378 } 1379 } 1380 } 1381 1382 1383 // -- compute cost 1384 1385 const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize(); 1386 const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize(); 1387 1388 const float pOverall = sizeBox; 1389 const float pBack = position - minBox; 1390 const float pFront = maxBox - position; 1391 1392 1393 const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit); 1394 const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit); 1395 const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit); 1396 1397 const float oldRenderCost = penaltyOld * pOverall + Limits::Small; 1398 const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack; 1399 1400 if (splitPlaneFound) 1401 { 1402 ratio = newRenderCost / oldRenderCost; 1403 } 1404 //if (axis != 1) 1405 //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox) 1406 // <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl; 1407 1408 return ratio; 1409 } 1410 #endif 1411 1412 1017 1413 float VspTree::SelectSplitPlane(const VspTraversalData &tData, 1018 1414 AxisAlignedPlane &plane, … … 1699 2095 1700 2096 2097 void VspTree::CollectPvs(const RayInfoContainer &rays, 2098 ObjectContainer &objects) const 2099 { 2100 RayInfoContainer::const_iterator rit, rit_end = rays.end(); 2101 2102 Intersectable::NewMail(); 2103 2104 for (rit = rays.begin(); rit != rays.end(); ++ rit) 2105 { 2106 VssRay *ray = (*rit).mRay; 2107 2108 Intersectable *object; 2109 object = ray->mOriginObject; 2110 2111 if (object) 2112 { 2113 if (!object->Mailed()) 2114 { 2115 object->Mail(); 2116 objects.push_back(object); 2117 } 2118 } 2119 2120 object = ray->mTerminationObject; 2121 2122 if (object) 2123 { 2124 if (!object->Mailed()) 2125 { 2126 object->Mail(); 2127 objects.push_back(object); 2128 } 2129 } 2130 } 2131 } 2132 2133 1701 2134 int VspTree::ComputePvsSize(const RayInfoContainer &rays) const 1702 2135 { … … 2576 3009 << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), " 2577 3010 << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), " 2578 //<< "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "3011 << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), " 2579 3012 << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), " 2580 3013 << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), " … … 2586 3019 2587 3020 3021 2588 3022 /*********************************************************************/ 2589 3023 /* class HierarchyManager implementation */ 2590 3024 /*********************************************************************/ 3025 3026 2591 3027 2592 3028 HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree): -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h
r1047 r1072 868 868 float &pBack); 869 869 870 /** Sorts split candidates for surface area heuristics for axis aligned splits. 870 /** Sorts split candidates along the specified axis. 871 The split candidates are generated on possible visibility 872 events (i.e., where ray segments intersect the ray boundaries). 873 The sorted candidates are needed to compute the SAH. 874 871 875 @param polys the input for choosing split candidates 872 876 @param axis the current split axis … … 877 881 float minBand, 878 882 float maxBand); 883 884 /** Prepares objects for SAH. 885 */ 886 void PrepareHeuristics(const RayInfoContainer &rays); 887 888 /** Computes pvs increase with respect to the previous pvs for SAH. 889 */ 890 int GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes); 891 892 /** Returns absolute pvs contribution of this object. 893 */ 894 int GetPvsContribution(Intersectable *object) const; 879 895 880 896 /** Computes best cost for axis aligned planes. … … 886 902 float &position); 887 903 904 float EvalKdCostHeuristics(const RayInfoContainer &rays, 905 const AxisAlignedBox3 &box, 906 const int pvsSize, 907 const int axis, 908 float &position); 909 void EvalPvsIncr(ObjectMap &multipleObjects, 910 KdLeaf *leaf, 911 const SortableEntry &ci, 912 int &pvsLeft, 913 int &pvsRight) const; 914 915 888 916 /** Subdivides the rays into front and back rays according to the split plane. 889 917 … … 918 946 */ 919 947 int ComputePvsSize(const RayInfoContainer &rays) const; 948 949 /** Collects pvs from rays. 950 */ 951 void CollectPvs(const RayInfoContainer &rays, 952 ObjectContainer &objects) const; 920 953 921 954 /** Returns true if tree can be terminated.
Note: See TracChangeset
for help on using the changeset viewer.