extractLightsMerge.cpp

/* -*-c++-*- */

/**
 * convert Env map Regions to Lights
 */
void createLightsFromRegions(const SatRegionVector& regions,
                             LightVector& lights, const float* rgba,
                             const double maxLum, const int width,
                             const int height, const int nc,
                             const SummedAreaTable& lumSat) {
    const double maxR = lumSat.getMaxR();
    const double maxG = lumSat.getMaxG();
    const double maxB = lumSat.getMaxB();
    const double weigth = lumSat.getWeightAccumulation();

    const uint imgSize = width * height;
    double weight = (4.0 * PI) / ((double)(imgSize));

    // convert region into lights
    for (SatRegionVector::const_iterator region = regions.begin();
         region != regions.end(); ++region) {
        Light l;

        // init values
        l._merged = false;
        l._mergedNum = 0;

        l._x = region->_x;
        l._y = region->_y;
        l._w = region->_w;
        l._h = region->_h;

        // set light at centroid
        l._centroidPosition = region->centroid();

        // light area Size
        l._areaSize = region->areaSize();

        const uint i = static_cast<uint>(l._centroidPosition[1] * width +
                                         l._centroidPosition[0]);

        // compute area values, as SAT introduce precision errors
        // due to high sum values against small data values
        // we use here less error inducing computations
        double r = rgba[i * nc + 0];
        double g = rgba[i * nc + 1];
        double b = rgba[i * nc + 2];
        {
            double y =
                ((double)l._centroidPosition[1] + 1.0) / (double)(height + 1);
            double solidAngle = cos(PI * (y - 0.5)) * weight;
            l._luminancePixel = luminance(r, g, b) * solidAngle;
        }

        double rSum = 0.0;
        double gSum = 0.0;
        double bSum = 0.0;
        double lumSum = 0.0;

        for (int y1 = l._y; y1 < l._y + l._h; ++y1) {
            const double posY = ((double)y1 + 1.0) / (double)(height + 1.0);
            const double solidAngle = cos(PI * (posY - 0.5)) * weight;

            for (int x1 = l._x; x1 < l._x + l._w; ++x1) {
                const uint i = (x1 + (y1 * width)) * nc;

                r = rgba[i];
                g = rgba[i + 1];
                b = rgba[i + 2];

                lumSum += luminance(r, g, b) * solidAngle;

                rSum += r;
                gSum += g;
                bSum += b;
            }
        }

        // normalize
        lumSum *= (4.0 * PI) / weigth;
        l._sum = lumSum;

        l._variance =
            ((l._sum * l._sum) / l._areaSize) - (l._lumAverage * l._lumAverage);

        // Colors
        l._rAverage = rSum / l._areaSize;
        l._gAverage = gSum / l._areaSize;
        l._bAverage = bSum / l._areaSize;
        l._lumAverage = lumSum / l._areaSize;

        // make all value 0..1 now
        l._x = static_cast<double>(l._x) / (double)width;
        l._y = static_cast<double>(l._y) / (double)height;
        l._w = static_cast<double>(l._w) / (double)width;
        l._h = static_cast<double>(l._h) / (double)height;
        l._areaSize = l._w * l._h;

        l._centroidPosition[0] = l._centroidPosition[0] / (double)width;
        l._centroidPosition[1] = l._centroidPosition[1] / (double)height;

        // if value out of bounds
        l._error = l._sum > maxLum;
        l._sortCriteria = l._areaSize;

        lights.push_back(l);
    }
}

/*
 *  Merge a light into another and store a copy inside the parent
 */
void mergeLight(Light& lightParent, Light& lightChild) {
    // exclude from next merges
    lightChild._merged = true;

    const double x = lightParent._x;
    const double y = lightParent._y;
    const double w = lightParent._w;
    const double h = lightParent._h;

    lightParent._x = std::min(x, lightChild._x);
    lightParent._y = std::min(y, lightChild._y);

    lightParent._w =
        std::max(x + w, (lightChild._x + lightChild._w)) - lightParent._x;
    lightParent._h =
        std::max(y + h, (lightChild._y + lightChild._h)) - lightParent._y;

    lightParent.childrenLights.push_back(lightChild);

    // light is bigger, better candidate to main light
    lightParent._mergedNum++;

    lightParent._sum += lightChild._sum;

    double newAreaSize = lightParent._areaSize + lightChild._areaSize;
    double ratioParent = lightParent._areaSize / newAreaSize;
    double ratioChild = lightChild._areaSize / newAreaSize;

    lightParent._rAverage =
        lightParent._rAverage * ratioParent + lightChild._rAverage * ratioChild;
    lightParent._gAverage =
        lightParent._gAverage * ratioParent + lightChild._gAverage * ratioChild;
    lightParent._bAverage =
        lightParent._bAverage * ratioParent + lightChild._bAverage * ratioChild;

    // newAreaSize = lightParent._w * lightParent._h;
    lightParent._areaSize = newAreaSize;
    lightParent._lumAverage = lightParent._sum / newAreaSize;

    // lightChild._sortCriteria = lightChild._lumAverage;
    lightChild._sortCriteria = lightChild._sum;
    // lightChild._sortCriteria = lightChild._areaSize;
    // lightParent._sortCriteria = lightParent._sum;
}

/*
 * not a constructor, not struct member as it's specific for merge
 *  we copy only parts
 */
void lightCopy(Light& lDest, const Light& lSrc) {
    lDest._error = lSrc._error;
    lDest._merged = lSrc._merged;
    lDest._mergedNum = lSrc._mergedNum;
    lDest._x = lSrc._x;
    lDest._y = lSrc._y;
    lDest._w = lSrc._w;
    lDest._h = lSrc._h;
    lDest._centroidPosition[0] = lSrc._centroidPosition[0];
    lDest._centroidPosition[1] = lSrc._centroidPosition[1];
    lDest._areaSize = lSrc._areaSize;
    lDest._sum = lSrc._sum;
    lDest._variance = lSrc._variance;
    lDest._lumAverage = lSrc._lumAverage;
    lDest._rAverage = lSrc._rAverage;
    lDest._gAverage = lSrc._gAverage;
    lDest._bAverage = lSrc._bAverage;
    lDest._luminancePixel = lSrc._luminancePixel;
}
/*
 * intersect lights with another light
 */
bool intersectLightAgainstLights2D(const LightVector& lights,
                                   const Light& lightCandidate,
                                   const double border) {
    if (lights.empty()) return true;

    double x1 = lightCandidate._x - border;
    double y1 = lightCandidate._y - border;
    double x2 = x1 + lightCandidate._w + border;
    ;
    double y2 = y1 + lightCandidate._h + border;
    ;

    for (LightVector::const_iterator l = lights.begin(); l != lights.end();
         ++l) {
        if (!(l->_y > y2 || l->_y + l->_h < y1 || l->_x > x2 ||
              l->_x + l->_w < x1)) {
            return true;
        }
    }

    return false;
}

/**
 * Merge small area light neighbour with small area light neighbours
 */
uint mergeLights(LightVector& lights, LightVector& newLights, const uint width,
                 const uint height, const double areaSizeMax,
                 const double lengthSizeMax, const double luminanceMaxLight,
                 const double degreeMerge) {
    // discard or keep Light too near an current light
    const double border = degreeMerge * PI / 360.0;

    uint numMergedLightTotal;

    numMergedLightTotal = 0;

    // for each light we try to merge with all other intersecting lights
    // that are in the same neighborhood of the sorted list of lights
    // where neighbors are of near same values
    for (LightVector::iterator lightIt = lights.begin();
         lightIt != lights.end(); ++lightIt) {
        // already merged in a previous light
        // we do nothing
        if (lightIt->_merged) continue;

        Light lCurrent;
        lightCopy(lCurrent, *lightIt);
        double x1 = lCurrent._x - border;
        double y1 = lCurrent._y - border;
        double x2 = x1 + lCurrent._w + border;
        double y2 = y1 + lCurrent._h + border;

        uint numMergedLight;

        // current area Size will change when getting merges
        // we store initial values to prevent merging
        // with light too low
        const double areaSizeCurrent = lCurrent._areaSize;

        do {
            numMergedLight = 0;

            // could start at current light
            // lights is sorted by areasize from small to big
            for (LightVector::iterator l = lights.begin(); l != lights.end();
                 ++l) {
                // ignore already merged into another
                if (l->_merged) continue;

                // ignore itself
                if (l == lightIt) continue;

                // if merged do new size will be problematic
                const double newX = std::min(lCurrent._x, l->_x);
                const double newY = std::min(lCurrent._y, l->_y);

                const double newParentSizeW =
                    std::max(lCurrent._x + lCurrent._w, (l->_x + l->_w)) - newX;
                if (lengthSizeMax < newParentSizeW) continue;

                const double newParentSizeH =
                    std::max(lCurrent._y + lCurrent._h, (l->_y + l->_h)) - newY;

                if (lengthSizeMax < newParentSizeH) continue;

                bool intersect2D = !(l->_y > y2 || l->_y + l->_h < y1 ||
                                     l->_x > x2 || l->_x + l->_w < x1);
                // try left/right border as it's a env wrap
                // complexity arise, how to merge...and then retest after
                /*
                  if (!intersect2D ){
                  if( x == 0 ){
                  //check left borders
                  intersect2D = !(l->_y-border > y+h || l->_y+l->_h+border < y
                  || l->_x-border > width + w || l->_x+l->_w+border < width);
                  }else if( x+w == width ){
                  //check right borders
                  intersect2D = !(l->_y-border > y+h || l->_y+l->_h+border < y
                  || l->_x-border > w + (width - x) || l->_x+l->_w+border <
                  (width - x));
                  }
                  }
                */

                //  share borders
                if (intersect2D) {
                    // remove from previous merge if any
                    for (LightVector::iterator lBigIt = newLights.begin();
                         lBigIt != newLights.end(); ++lBigIt) {
                        if (l == lBigIt) {
                            newLights.erase(lBigIt);
                            break;
                        }
                    }

                    mergeLight(lCurrent, *l);

                    x1 = lCurrent._x - border;
                    y1 = lCurrent._y - border;
                    x2 = x1 + lCurrent._w + border;
                    y2 = y1 + lCurrent._h + border;

                    numMergedLight++;
                    numMergedLightTotal++;
                }
            }

            // if we're merging we're changing borders
            // means we have new neighbours
            // or light now included inside our area
        } while (numMergedLight > 0);

        if (lCurrent._mergedNum > 0) {
            lCurrent._sortCriteria = lCurrent._areaSize;
            lCurrent._sortCriteria = lCurrent._sum;
            newLights.push_back(lCurrent);
        }
    }

    // count merged light
    numMergedLightTotal = 0;
    for (LightVector::iterator lCurrent = newLights.begin();
         lCurrent != newLights.end(); ++lCurrent) {
        if (!lCurrent->_merged) numMergedLightTotal += lCurrent->_mergedNum;
    }

    if (1) {
        // fill new array with light that wasn't merged at all
        for (LightVector::iterator lCurrent = lights.begin();
             lCurrent != lights.end(); ++lCurrent) {
            // add remaining non merged lights
            if (!lCurrent->_merged && lCurrent->_mergedNum == 0) {
                lCurrent->_lumAverage = lCurrent->_sum / lCurrent->_areaSize;

                // lCurrent->_sortCriteria = lCurrent->_lumAverage;
                lCurrent->_sortCriteria = lCurrent->_sum;

                newLights.push_back(*lCurrent);
            }
        }
    }

    return numMergedLightTotal;
}

// we now have merged big area light, which are the zone with the most light
// possible now we mush restrict those to smallest possible significant light
// possible reducing it to a near directional light as much as possible
uint selectLights(LightVector& mergedLights, LightVector& newLights,
                  const uint width, const uint height, const double areaSizeMax,
                  const double luminanceMaxLight, const double envLuminanceSum,
                  const double degreeMerge) {
    // discard or keep light too near an current light
    const double border = degreeMerge * PI / 360.0;
    ;  // static_cast <uint> (sqrt (areaSizeMax) / 2.0);

    uint numMergedLightTotal = 0;

    for (LightVector::iterator lightIt = mergedLights.begin();
         lightIt != mergedLights.end(); ++lightIt) {
        // already merged, we find in lights the light intersecting
        uint numMergedLight = 0;

        // if light "splittable"
        // and light already over ratio, need to cut it
        if (lightIt->_mergedNum > 0) {
            LightVector& lights = lightIt->childrenLights;

            // sort to get most powerful light first
            std::sort(lights.begin(), lights.end());

            // take biggest and merge a bit
            Light lCurrent;
            lightCopy(lCurrent, lights[0]);
            double x1 = lCurrent._x - border;
            double y1 = lCurrent._y - border;
            double x2 = x1 + lCurrent._w + border;
            double y2 = y1 + lCurrent._h + border;

            // reset children lights to start over merge process
            for (LightVector::iterator l = lights.begin() + 1;
                 l != lights.end(); ++l) {
                l->_merged = false;
            }

            do {
                numMergedLight = 0;

                for (LightVector::iterator l = lights.begin() + 1;
                     l != lights.end(); ++l) {
                    // ignore already merged or itself
                    if (l->_merged) continue;

                    bool intersect2D = !(l->_y > y2 || l->_y + l->_h < y1 ||
                                         l->_x > x2 || l->_x + l->_w < x1);

                    if (intersect2D &&
                        intersectLightAgainstLights2D(lCurrent.childrenLights,
                                                      *l, border)) {
                        mergeLight(lCurrent, *l);

                        x1 = lCurrent._x - border;
                        y1 = lCurrent._y - border;
                        x2 = x1 + lCurrent._w + border;
                        y2 = y1 + lCurrent._h + border;

                        numMergedLight++;
                    }
                }
            } while (numMergedLight > 0);

            lCurrent._sortCriteria = lCurrent._sum;
            newLights.push_back(lCurrent);

            numMergedLightTotal += lCurrent._mergedNum;

        } else {
            lightIt->_sortCriteria = lightIt->_lumAverage;
            lightIt->_sortCriteria = lightIt->_sum;
            newLights.push_back(*lightIt);
            numMergedLightTotal += lightIt->_mergedNum;
        }
    }

    return numMergedLightTotal;
}

uint mergeNearLights(LightVector& mergedLights, const double areaSizeMax,
                     const double lengthSizeMax, const double degreeMerge) {
    // discard or keep light too near an current light
    const double border = degreeMerge * PI / 180.0;
    ;  // static_cast <uint> (sqrt (areaSizeMax) / 2.0);
    uint numMergedLightTotal;

    numMergedLightTotal = 0;

    for (int i = 0; i < mergedLights.size(); ++i) {
        Light* lightCurrent = &(mergedLights[i]);  //.at(i);

        // already merged light into another
        if (lightCurrent->_merged) continue;

        double x1 = lightCurrent->_x - border;
        double y1 = lightCurrent->_y - border;
        double x2 = x1 + lightCurrent->_w + border;
        double y2 = y1 + lightCurrent->_h + border;

        // reset children lights to start over merge process
        int j = 0;
        for (LightVector::iterator l = mergedLights.begin();
             l != mergedLights.end(); ++j) {
            if (i == j) {
                ++l;
                continue;
            }

            // pick only smallest & near lights,
            // grow until not bigger than areaSize
            // if merged, what would be new Size
            // only test merged size (allow for intersections of merged)
            const double newX = std::min(lightCurrent->_x, l->_x);
            const double newY = std::min(lightCurrent->_y, l->_y);

            const double newParentSizeW =
                std::max(lightCurrent->_x + lightCurrent->_w, (l->_x + l->_w)) -
                newX;
            if (lengthSizeMax < newParentSizeW) continue;
            const double newParentSizeH =
                std::max(lightCurrent->_y + lightCurrent->_h, (l->_y + l->_h)) -
                newY;
            if (lengthSizeMax < newParentSizeH) continue;

            bool intersect2D = !(l->_y > y2 || l->_y + l->_h < y1 ||
                                 l->_x > x2 || l->_x + l->_w < x1);

            if (intersect2D) {
                mergeLight(*lightCurrent, *l);

                x1 = lightCurrent->_x - border;
                y1 = lightCurrent->_y - border;
                x2 = x1 + lightCurrent->_w + border;
                y2 = y1 + lightCurrent->_h + border;

                l = mergedLights.erase(l);

                numMergedLightTotal++;
            } else {
                ++l;
            }
        }
    }
}