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.

Answer 2

Am I correct that a ray can never land in the light green box? i.e. rays are stopped when they reach the light green area? Are there any rules determining if a ray lands on the red area, on the dark green area, or passes through both of them?

If these rules are independent of the size of the car, but only depend on the relative position of the "end point" of the ray, e.g. if rays to the middle of the front of the car surface do always land on the free space around the car, then the relation of the quantity of rays with cost d, c, or e are independent of the size of the car. The quantity of rays with cost f (marked yellow) is just the rest of the rays, i.e. rays that do not have cost d, c, or e.

This means that in a first step, calculate the optimal (minimal) sum of costs, given the constant ratio of costs for d/c/e and knowing that the remainder of the rays have costs f.

Example: you have 5% of rays with cost c (turquoise lines), 10% of rays with cost e (red lines), and 40% of rays with cost d (green lines), and 45% of rays with cost f (yellow lines). Therefore for each ray with cost c you have two rays with cost e and eight rays with cost d. All the remaining rays have cost f.

-> let x be the number of rays with cost c, then total costs are: 1*c*x + 2*e*x + 8*d*x + (totalNumberOfRays - (1+2+8)*x) * f

Now find the minimum of this function (which is easy because it is a linear function, but probably you have some constraints on the size of your car), and use the resulting x to calculate the size of your car: if you had in the beginning e.g. 10 rays with cost c, and the resulting x is 5, you have to find the car size which produces only 5 rays of costs c, i.e. the car width and length each should be multiplied by 0.5.

Now, the only thing I hope, is that my assumptions were right :-)

(Other options that I thought of, in case my assumptions are wrong, are grouping the rays together in a certain way, and only do the calculations per group)