recalculate ray tracing/casting costs when changing size of rectangle

Question

I have an array of "rays" which I need to measure the costs in relation to the rectangular boxes below. The outer red box is always 1m larger than the dark green box and light green box is 10cm smaller than the dark green box. If a ray

1. passes through the dark green box I would assign cost c
2. ands on the dark green box I would assign cost d
3. lands on the red area i would assign cost e
4. does not intersect the dark green box and not land in red box, cost f
5. and d < f < c < e

I currently have the following data structures and functions to calculate the cost. I am required to calculate the cost for the given rectangles (represented by 4 xy coordinates), but at the same time, find the approximate/local optimal length/width of the dark green rectangle(i.e shrink or grow the dimension by holding the closest corner of the rectangle fixed) such that the cost is minimum.

A concrete example is the screenshot below. The smaller rectangle corresponds to the dark green box in the figure. Green lines are the rays with cost d, yellow lines cost f and the turquoise lines are the ones with cost c. If I fix the top left hand corner of the inner rectangle and reduce the width, I can reduce the turqoise rays from cost c to f.

My question is, I am stuck at how should I alter my code or change my data structure, such that I can find the best dimensions by only recomputing the affected rays (i.e without looping through all the rays again).

struct VRay{
    float range, x, y;
    enum RayType{ PASSTHROUGH, FREE, SURFACE, OCCLUDED, UNIFORM};
    RayType r;
};
struct VScan{
    VRay rays[401];
    int closestIdx;
    int firstIdx;
    int lastIdx;
} vscan;

The function to calculate the costs:

for (int i = 0; i < 401; i++){
       VRay& r = vscan.rays[i];

       Vector2f cray(r.y, -r.x);
       bool ppBound = false;
       bool ppSurf = false;
       Vector2f vertex =  outBox.row(0);
       Vector2f vertexSurf = surface.row(0);

       float init = cray.dot(vertex);
       float initSurf = cray.dot(vertexSurf);
       //this part finds whether ray intersects rectangle or not 
       for (int j = 1; j < 4; j++){
            Vector2f v2 = outBox.row(j);
            Vector2f vSurf =  surface.row(j);

            float i2 = cray.dot(v2);
            float iSurf = cray.dot(vSurf);

            if (i2 * init < 0){
                ppBound =  true;
            }

            if (iSurf * initSurf < 0){
                ppSurf = true;
            }
       }

       //ray does not intersect all rectangles
       if (!ppBound){
          z += log(1/100.);
          continue;
       }

        //ray is inside red box
        if (inPolygon(outBox, r)){
            //ray inside dark green box 
            if (inPolygon(surface, r)){
                //ray inside light green box
                if (inPolygon(inBox,r))
                    c  = passTCost;
                else
                    c = surfaceCost;
            }
            else{
                c = freeCost; //free space
            }
        }
        else if (ppSurf){
            c = passTCost; //before all boxes
        }
        else { //ray does not intersect dark green box
            z += log(1/100.);
            continue;
        }

        z += -(c * c)/(2 * deviation * deviation);
    }

Answer 1

If I understand you right, you want vary the size of the dark green rectangle such that it retains a common center with the light green rectangle the edges of both remain parallel. The dark green rectangle will never leave the red one at any point and will never be smaller than the light green one. Red and light green rectangle remain constant. You only want to recalculate those rays that might change their cost if you vary the dark green rectangle (DGR from now on...).

So my proposition is as follows: Have another std::vector<VRay*> being empty at the start, and a second sum variable. In a first run, calculate your costs as you do. Additionally, for each ray, decide if it might change at all when varying the DGR.

If it could, add a pointer to it to the vector above, otherwise, add its current cost to the second sum. From now on, you only have to re-calculate those rays in the pointer vector and add the pre-calculated sum of the other ones to this new sum.

How to decide, if a ray might change cost? Well, those not crossing the red rectangle will not, of course. Those ending in the light green rectangle won't either, as well as those crossing both the light green and the red rectangle. So the relevant rays are those ending within the red rectangle, but not within the light green one and additionally those entirely crossing the red one but not intersecting the light green one.

A further optimisation can be gatherd if you consider the maximum DGR (if it is not necessarily parallel to the red one): Those lines not intersecting this maximum rectangle or ending in front of it won't ever change either.