Changeset 354

Timestamp:

10/28/05 14:46:59 (19 years ago)

Author:

bittner

Message:

sampling node selection changes

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• Intersectable.h (modified) (1 diff)
• KdTree.cpp (modified) (2 diffs)
• KdTree.h (modified) (1 diff)
• Makefile (modified) (7 diffs)
• Mesh.cpp (modified) (2 diffs)
• Mesh.h (modified) (2 diffs)
• SamplingPreprocessor.cpp (modified) (9 diffs)
• SamplingPreprocessor.h (modified) (1 diff)
• Vector3.cpp (modified) (2 diffs)
• preprocessor.pro (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/Intersectable.h

@@ -43 +43 @@
   virtual int GetRandomSurfacePoint(Vector3 &point, Vector3 &normal) = 0;
 
+        virtual int
+        GetRandomVisibleSurfacePoint(Vector3 &point,
+                                                                                                                         Vector3 &normal,
+                                                                                                                         const Vector3 &viewpoint,
+                                                                                                                         const int maxTries
+                                                                                                                         ) = 0;
+
         virtual ostream &Describe(ostream &s) = 0;
         

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

@@ -641 +641 @@
 KdNode *
 KdTree::FindRandomNeighbor(KdNode *n,
-                           bool onlyUnmailed
-                           )
+                                                                                                         bool onlyUnmailed
+                                                                                                         )
 {
   stack<KdNode *> nodeStack;
@@ -811 +811 @@
   return totalPvsSize;
 }
+
+
+KdNode *
+KdTree::GetRandomLeaf(const bool onlyUnmailed)
+{
+        stack<KdNode *> nodeStack;
+  nodeStack.push(mRoot);
+
+        int mask = rand();
+        
+  while (!nodeStack.empty()) {
+    KdNode *node = nodeStack.top();
+    nodeStack.pop();
+    if (node->IsLeaf()) {
+      if ( (!onlyUnmailed || !node->Mailed()) )
+                                return node;
+    } else {
+      KdInterior *interior = (KdInterior *)node;
+                        // random decision
+                        if (mask&1)
+                                nodeStack.push(interior->mBack);
+                        else
+                                nodeStack.push(interior->mFront);
+                        mask = mask>>1;
+                }
+        }
+  return NULL;
+}

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.h

@@ -305 +305 @@
   KdNode *
   FindRandomNeighbor(KdNode *n,
-                     bool onlyUnmailed
-                     );
-
+                                                                                 bool onlyUnmailed
+                                                                                 );
+        
   
   KdNode *
   KdTree::GetRandomLeaf(const Plane3 &halfspace);
-  
+
+        KdNode *
+        GetRandomLeaf(const bool onlyUnmailed = false);
+
   int
   FindNeighbors(KdNode *n,

trunk/VUT/GtpVisibilityPreprocessor/src/Makefile

@@ -1 +1 @@
 #############################################################################
 # Makefile for building: preprocessor
-# Generated by qmake (1.07a) (Qt 3.3.2) on: Tue Oct 18 16:48:33 2005
+# Generated by qmake (1.07a) (Qt 3.3.2) on: Wed Oct 26 17:55:30 2005
 # Project:  preprocessor.pro
 # Template: app
@@ -39 +39 @@
 ####### Files
 
-HEADERS =       
+HEADERS =       Halton.h
 SOURCES =       Preprocessor.cpp \
                 SamplingPreprocessor.cpp \
@@ -68 +68 @@
                 Polygon3.cpp \
                 ViewCell.cpp \
-                ViewCellBsp.cpp
+                ViewCellBsp.cpp \
+                Halton.cpp
 OBJECTS =       Preprocessor.obj \
                 SamplingPreprocessor.obj \
@@ -97 +98 @@
                 Polygon3.obj \
                 ViewCell.obj \
-                ViewCellBsp.obj
+                ViewCellBsp.obj \
+                Halton.obj
 FORMS = 
 UICDECLS =      
@@ -188 +190 @@
         -$(DEL_FILE) ViewCell.obj
         -$(DEL_FILE) ViewCellBsp.obj
+        -$(DEL_FILE) Halton.obj
 
 
@@ -371 +374 @@
                 Matrix4x4.h \
                 Vector3.h \
+                Halton.h \
                 common.h \
                 
@@ -606 +610 @@
                 
 
+Halton.obj: Halton.cpp  \
+                Halton.h \
+                
+
 ####### Install
 

trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.cpp

@@ -289 +289 @@
 
 int
+Mesh::GetRandomVisibleSurfacePoint(Vector3 &point,
+                                                                                                                                         Vector3 &normal,
+                                                                                                                                         const Vector3 &viewpoint,
+                                                                                                                                         const int maxTries
+                                                                                                                                         )
+{
+        Plane3 plane;
+        int faceIndex = RandomValue(0, mFaces.size()-1);
+        for (int tries = 0; tries < maxTries; tries++) {
+                Face *face = mFaces[faceIndex];
+                plane = GetFacePlane(faceIndex);
+                
+                if (plane.Side(viewpoint) > 0) {
+                        point = Vector3(0,0,0);
+                        float sum = 0.0f;
+                        // pickup a point inside this triangle
+                        for (int i = 0; i < face->mVertexIndices.size(); i++) {
+                                float r = RandomValue(0,1);
+                                sum += r;
+                                point += mVertices[face->mVertexIndices[i]]*r;
+                        }
+                        point *= 1.0f/sum;
+                        break;
+                }
+        }
+        
+        normal = plane.mNormal;
+        return (tries < maxTries) ? faceIndex + 1 : 0;
+}
+
+
+int
 MeshInstance::CastRay(
                                                                                         Ray &ray
@@ -313 +345 @@
   return mMesh->GetRandomSurfacePoint(point, normal);
 }
+
+int
+MeshInstance::GetRandomVisibleSurfacePoint(Vector3 &point,
+                                                                                                                                                                         Vector3 &normal,
+                                                                                                                                                                         const Vector3 &viewpoint,
+                                                                                                                                                                         const int maxTries
+                                                                                                                                                                         )
+{
+        return mMesh->GetRandomVisibleSurfacePoint(point, normal, viewpoint, maxTries);
+}
+
 
 int

trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.h

@@ -145 +145 @@
   int GetRandomSurfacePoint(Vector3 &point, Vector3 &normal);
 
+        int
+        GetRandomVisibleSurfacePoint(Vector3 &point,
+                                                                                                                         Vector3 &normal,
+                                                                                                                         const Vector3 &viewpoint,
+                                                                                                                         const int maxTries
+                                                                                                                         );
+                
         virtual ostream &Describe(ostream &s) {
                 return s<<"Mesh #vertices="<<mVertices.size()<<" #faces="<<mFaces.size();
@@ -161 +168 @@
 
   int GetRandomSurfacePoint(Vector3 &point, Vector3 &normal);
+
+        int
+        GetRandomVisibleSurfacePoint(Vector3 &point,
+                                                                                                                         Vector3 &normal,
+                                                                                                                         const Vector3 &viewpoint,
+                                                                                                                         const int maxTries
+                                                                                                                         );
 
 

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -148 +148 @@
 int
 SamplingPreprocessor::CastRay(Intersectable *object,
-                                                                                                                        Ray &ray)
+                                                                                                                        Ray &ray,
+                                                                                                                        const bool reverseRay
+                                                                                                                        )
 {
         int sampleContributions = 0;
@@ -168 +170 @@
                 {
                         mBspTree->CastRay(ray);
-                                        
-                        sampleContributions += AddObjectSamples(object, ray);
-                                
+                        
+                        if (!reverseRay)
+                                sampleContributions += AddObjectSamples(object, ray);
+                        
                         if (!ray.intersections.empty()) // second intersection found
-                        {
-                                sampleContributions += 
-                                        AddObjectSamples(ray.intersections[0].mObject, ray);
-                        }
+                                {
+                                        sampleContributions += 
+                                                AddObjectSamples(ray.intersections[0].mObject, ray);
+                                }
                 }
         }
@@ -181 +184 @@
                 {
                         if (ray.leaves.size()) {
-                                sampleContributions += AddNodeSamples(object, ray);
+                                if (!reverseRay)
+                                        sampleContributions += AddNodeSamples(object, ray);
                                 
                                 if (ray.intersections.size()) {
@@ -274 +278 @@
                         // to the mesh
                         rays++;
-                        edgeSamplesContributions += CastRay(object, ray);
+                        edgeSamplesContributions += CastRay(object, ray, false);
                 }
         }
         return edgeSamplesContributions;
+}
+
+KdNode *
+SamplingPreprocessor::GetNodeToSample(Intersectable *object)
+{
+        int pvsSize = object->mKdPvs.GetSize();
+        KdNode *nodeToSample = NULL;
+        
+        bool samplePvsBoundary = false;
+        if (pvsSize && samplePvsBoundary) {
+                // this samples the nodes from the boundary of the current PVS
+                // mail all nodes from the pvs
+                Intersectable::NewMail();
+                KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
+                
+                for (; i != object->mKdPvs.mEntries.end(); i++) {
+                        KdNode *node = (*i).first;
+                        node->Mail();
+                }
+                
+                int maxTries = 2*pvsSize;
+                Debug << "Finding random neighbour" << endl;    
+                for (int tries = 0; tries < 10; tries++) {
+                        int index = RandomValue(0, pvsSize - 1);
+                        KdPvsData data;
+                        KdNode *node;
+                        object->mKdPvs.GetData(index, node, data);
+                        nodeToSample = mKdTree->FindRandomNeighbor(node, true);
+                        if (nodeToSample)
+                                break;
+                }
+        } else {
+                // just pickup a random node
+                //              nodeToSample = mKdTree->GetRandomLeaf(Plane3(normal, point));
+                nodeToSample = mKdTree->GetRandomLeaf();
+        }
+        return nodeToSample;
+}
+
+void
+SamplingPreprocessor::VerifyVisibility(Intersectable *object)
+{
+        // mail all nodes from the pvs
+        Intersectable::NewMail();
+        KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
+        for (; i != object->mKdPvs.mEntries.end(); i++) {
+                KdNode *node = (*i).first;
+                node->Mail();
+        }
+        Debug << "Get all neighbours from PVS" << endl;
+        vector<KdNode *> invisibleNeighbors;
+        // get all neighbors of all PVS nodes
+        i = object->mKdPvs.mEntries.begin();
+        for (; i != object->mKdPvs.mEntries.end(); i++) {
+                KdNode *node = (*i).first;
+                mKdTree->FindNeighbors(node, invisibleNeighbors, true);
+                AxisAlignedBox3 box = object->GetBox();
+                for (int j=0; j < invisibleNeighbors.size(); j++) {
+                        int visibility = ComputeBoxVisibility(mSceneGraph,
+                                                                                                                                                                                mKdTree,
+                                                                                                                                                                                box,
+                                                                                                                                                                                mKdTree->GetBox(invisibleNeighbors[j]),
+                                                                                                                                                                                1e-6f);
+                        //            exit(0);
+                }
+                // now rank all the neighbors according to probability that a new
+                // sample creates some contribution
+        }
 }
 
@@ -312 +384 @@
                 Real maxTime = 0;
                 int maxTimeIdx = 0;
-
+                int reverseSamples = 0;
                 bool collectSamplesForBsp = 
                         (mViewCellsType == BSP_VIEW_CELLS) &&
@@ -329 +401 @@
                                 pvsSize = object->mKdPvs.GetSize();
                                                 
-                        if (0 && pvsSize) {
-                                // mail all nodes from the pvs
-                                Intersectable::NewMail();
-                                KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
-                          
-                                for (; i != object->mKdPvs.mEntries.end(); i++) {
-                                        KdNode *node = (*i).first;
-                                        node->Mail();
-                                }
-                                
-                                int maxTries = 2*pvsSize;
-                                Debug << "Finding random neighbour" << endl;    
-                                for (int tries = 0; tries < 10; tries++) {
-                                        index = RandomValue(0, pvsSize - 1);
-                                        KdPvsData data;
-                                        KdNode *node;
-                                        object->mKdPvs.GetData(index, node, data);
-                                        nodeToSample = mKdTree->FindRandomNeighbor(node, true);
-                                        if (nodeToSample)
-                                                break;
-                                }
-                        }
                         
                         if (0 && pvsSize && mPass == 1000 ) {
-                                // mail all nodes from the pvs
-                                Intersectable::NewMail();
-                                KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
-                                for (; i != object->mKdPvs.mEntries.end(); i++) {
-                                        KdNode *node = (*i).first;
-                                        node->Mail();
-                                }
-                                Debug << "Get all neighbours from PVS" << endl;
-                                vector<KdNode *> invisibleNeighbors;
-                                // get all neighbors of all PVS nodes
-                                i = object->mKdPvs.mEntries.begin();
-                                for (; i != object->mKdPvs.mEntries.end(); i++) {
-                                        KdNode *node = (*i).first;
-                                        mKdTree->FindNeighbors(node, invisibleNeighbors, true);
-                                        AxisAlignedBox3 box = object->GetBox();
-                                        for (int j=0; j < invisibleNeighbors.size(); j++) {
-                                                int visibility = ComputeBoxVisibility(mSceneGraph,
-                                                                                                                                                                                                        mKdTree,
-                                                                                                                                                                                                        box,
-                                                                                                                                                                                                        mKdTree->GetBox(invisibleNeighbors[j]),
-                                                                                                                                                                                                        1e-6f);
-                                                //            exit(0);
-                                        }
-                                        // now rank all the neighbors according to probability that a new
-                                        // sample creates some contribution
-                                }
+                                VerifyVisibility(object);
                         }
                         
@@ -389 +414 @@
                         bool debug = false; //(object->GetId() >= 2199);
                         if (viewcellSample) {
-                                nodeToSample = mKdTree->GetRandomLeaf(Plane3(normal, point));
+                                //mKdTree->GetRandomLeaf(Plane3(normal, point));
+
+                                for (int k=0; k < mSamplesPerPass; k++) {
+                                        bool reverseSample = false;
                                         
-                                for (int k=0; k < mSamplesPerPass; k++) {
+                                        nodeToSample = GetNodeToSample(object);
+                                        
                                         if (nodeToSample) {
-                                                int maxTries = 5;
-                                                
-                                                for (int tries = 0; tries < maxTries; tries++) {
-                                                        direction = mKdTree->GetBox(nodeToSample).GetRandomPoint() - point;
-                                                        
-                                                        if (DotProd(direction, normal) > Limits::Small)
-                                                                break;                                                  
+                                                Vector3 pointToSample = mKdTree->GetBox(nodeToSample).GetRandomPoint();
+                                                if (object->GetRandomVisibleSurfacePoint( point, normal, pointToSample, 5 )) {
+                                                        direction = pointToSample - point;
+                                                } else {
+                                                        reverseSamples++;
+                                                        reverseSample = true;
+                                                        direction = point - pointToSample;
+                                                        point = pointToSample;
                                                 }
-                                                if (tries == maxTries)
-                                                        direction = UniformRandomVector(normal);
-                                                
-                                                if (debug) {
-                                                        cout<<
-                                                                "normal "<<normal<<endl<<
-                                                                "tries "<<tries<<endl<<
-                                                                "dir="<<direction<<endl;
-                                                }
-
                                         }
                                         else {
@@ -418 +438 @@
                                         // construct a ray
                                         SetupRay(ray, point, direction, Ray::LOCAL_RAY);
-                        
-                                        sampleContributions = CastRay(object, ray);
+                                        
+                                        sampleContributions = CastRay(object, ray, reverseSample);
 
                                         //-- CORR matt: put block inside loop
@@ -541 +561 @@
                                  << 100*passContributingSamples/(float)passSamples<<"%)" << " avgPVS="
                                  << pvsSize/(float)objects.size() << endl 
-                                 << "avg ray contrib=" << avgRayContrib << endl;
-                
+                                 << "avg ray contrib=" << avgRayContrib << endl
+                                 << "reverse samples [%]" << reverseSamples/(float)passSamples*100.0f << endl;
+
                 mStats <<
                         "#Pass\n" <<mPass<<endl<<

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.h

@@ -49 +49 @@
 
         int
-        CastRay(Intersectable *object, Ray &ray);
+        CastRay(Intersectable *object, Ray &ray, const bool reverseSample);
+
+        KdNode *
+        GetNodeToSample(Intersectable *object);
+        void
+        VerifyVisibility(Intersectable *object);
 
         int

trunk/VUT/GtpVisibilityPreprocessor/src/Vector3.cpp

@@ -1 +1 @@
 #include "Matrix4x4.h"
 #include "Vector3.h"
+#include "Halton.h"
 
 float Vector3::sDistTolerance = 0.002f;
@@ -195 +196 @@
 UniformRandomVector(const Vector3 &normal)
 {
-  float r1 = RandomValue(0.0f, 1.0f);
-  float r2 = RandomValue(0.0f, 1.0f);
-  float cosTheta = 1.0f - r1;
+        //  float r1 = RandomValue(0.0f, 1.0f);
+        //  float r2 = RandomValue(0.0f, 1.0f);
+        float r1, r2;
+        
+        halton2.GetNext(r1, r2);
+        
+        
+        float cosTheta = 1.0f - r1;
   float sinTheta = sqrt(1 - sqr(cosTheta));
   float fi = 2.0f*M_PI*r2;

trunk/VUT/GtpVisibilityPreprocessor/src/preprocessor.pro

@@ -23 +23 @@
 
 # Input
-HEADERS += 
+HEADERS += Halton.h
 
 
@@ -33 +33 @@
 Exporter.cpp Camera.cpp X3dParser.cpp MeshKdTree.cpp Pvs.cpp \
 MutualVisibility.cpp Triangle3.cpp Rectangle3.cpp Plane3.cpp Polygon3.cpp \
-ViewCell.cpp ViewCellBsp.cpp
+ViewCell.cpp ViewCellBsp.cpp Halton.cpp