src/lib/cell.cpp

//
// AutoCoast: Automatic Coastline scenery generator for Flight Simulator
//
// Copyright (c) 2004, Takuya Murakami. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// cellarea.cc : Cell/Area process

#include <math.h>
#include <list>

#include "vector.hpp"
#include "cell.hpp"
#include "bgl.hpp"
#include "opt.hpp"

///////////////////////////////////////////////////////////////////////
// Cell

Cell::Cell(void)
{
        cellData = NULL;
}

Cell::~Cell()
{
        if (cellData) delete cellData;
}

// Convert coordinates
double Cell::x2lon(int u)
{
        double lon = u * 360.0 / 768.0 - 180.0;
        if (lon < 0) lon += 360.0;      // 0 to 360

        return lon;
}

int Cell::lon2x(double lon)
{
        if (lon > 180) lon -= 360;      // -180 to 180
        return (int)((lon + 180.0) * 768.0 / 360.0);
}

double Cell::y2lat(int v)
{
        return 90.0 - v * 180.0 / 512.0;
}

int Cell::lat2y(double lat)
{
        return (int)((90.0 - lat) * 512.0 / 180.0);
}

void Cell::setid(int xx, int yy)
{
        x = xx;
        y = yy;

        bbox.xmin = x2lon(x);
        bbox.xmax = x2lon(x+1);
        if (bbox.xmax == 0.0) bbox.xmax = 360.0;
        
        bbox.ymax = y2lat(y);
        bbox.ymin = y2lat(y+1);

        for (int u = 0; u < 32; u++) {
                for (int v = 0; v < 32; v++) {
                        area[u][v].setid(u, v, bbox);
                }
        }
}

bool Cell::Clipping(DataSet *source)
{
        if (cellData) {
                delete cellData;
        }

        cellData = source->Clipping(bbox);
        if (source->isEmpty(bbox)) {
                return false;
        }

        for (int u = 0; u < 32; u++) {
                for (int v = 0; v < 32; v++) {
                        area[u][v].Clipping(cellData);
                        area[u][v].setType();
                }
        }

        return true;
}

void Cell::checkFill(LwmDataChunk *chunk, int u, int v, int blocksz)
{
        int uu, vv;
        int type, firsttype;

        if (area[u][v].mark) return;    // already done...

        firsttype = area[u][v].getType();       // initial...
        if (isLand(firsttype)) {
                // AreaFill does not work for land area!
                // We must use land class or fill it with a polygon.
                return;
        }

        for (uu = u; uu < u + blocksz; uu++) {
                for (vv = v; vv < v + blocksz; vv++) {
                        type = area[uu][vv].getType();

                        if (isLand(type)) return; // mix!
                }
        }

        // okay fill area...
        chunk->DataAreaFill(blocksz, 0, u, v);

        // set mark
        for (uu = u; uu < u + blocksz; uu++) {
                for (vv = v; vv < v + blocksz; vv++) {
                        area[uu][vv].mark = true;
                }
        }
}

//
// Generate LWM bgl data                        
void Cell::GenLwmBgl(LwmBgl *bgl)
{
        int u, v, blocksz;
        LwmDataChunk *chunk = (LwmDataChunk *)bgl->NewDataChunk(x, y, bbox);

        for (u = 0; u < 32; u++) {
                for (v = 0; v < 32; v++) {
                        area[u][v].mark = false;
                }
        }

        // First, generate AreaFill for water.
        for (blocksz = 16; blocksz >= 1; blocksz = blocksz / 2) {
                for (u = 0; u < 32; u += blocksz) {
                        for (v = 0; v < 32; v += blocksz) {
                                checkFill(chunk, u, v, blocksz);
                        }
                }
        }

        // Next, fill all land area.
        for (u = 0; u < 32; u++) {
                for (v = 0; v < 32; v++) {
                        if (area[u][v].getType() != T_LAND) continue;

                        // near the shoreline??
                        const int K = AcOpts.landWidth;
                        bool match = false;
                        for (int uu = u - K; uu <= u + K; uu++) {
                                for (int vv = v - K; vv <= v + K; vv++) {
                                        if (uu < 0 || uu >= 32 ||
                                            vv < 0 || vv >= 32) continue;

                                        int t = area[uu][vv].getType();
                                        if (t == T_MIX_WATER || t == T_MIX_LAND) {
                                                match = true;
                                                break;
                                        }
                                }
                        }

                        if (match) {
                                // fill this area...
                                area[u][v].FillLand(chunk);
                        }
                }
        }
                                        
        // Next, draw polygons.
        for (u = 0; u < 32; u++) {
                for (v = 0; v < 32; v++) {
                        area[u][v].DrawLwmPolygon(chunk);
                }
        }
}

//
// Generate VTP bgl data
//
void Cell::GenVtpBgl(VtpBgl *bgl)
{
        VtpDataChunk *chunk = (VtpDataChunk *)bgl->NewDataChunk(x, y, bbox);

        int level, i;
        GpcPolygon shorelines;

        // Extract shorelines from all polygons in the cell.
        for (level = 1; level <= 4; level++) {
                GpcPolygon *poly = cellData->get(level);

                if (poly->isEmpty() ||
                    poly->isFull(bbox)) continue;

                for (i = 0; i < poly->numVList(); i++) {
                        ExtractShoreline(&shorelines, poly->getVList(i), level);
                }
        }

        int n = shorelines.numVList();
        if (n == 0) {
                // No shorelines.
                return;
        }

        // Mask default VTP shoreline.
        for (int u = 0; u < 32; u++) {
                for (int v = 0; v < 32; v++) {
                        chunk->DataArea(u, v, 0, 0);    // numTexture=0, autocalc=0
                }
        }


        // Start drawing polygons
        chunk->DataArea(x & 0x1f, y & 0x1f, 1, 1);      // numTexture=1, autocalc=1
        chunk->TextureStart(n);

        for (i = 0; i < n; i++) {
                // Interpolate vertices.
                // We must need at least one vertex in each LOD13 cell...
                GpcVertexList *vl = InterPolateVTPPoints(shorelines.getVList(i));

                // Draw polygons
                int np = vl->numVertices();
                chunk->PolyStart(np);
                for (int j = 0; j < np; j++) {
                        double x = (vl->vx(j) - bbox.xmin) / (bbox.xmax - bbox.xmin) * 
                                (12240 - 4080) + 4080;
                        double y = (bbox.ymax - vl->vy(j)) / (bbox.ymax - bbox.ymin) * 
                                (12240 - 4080) + 4080;

                        chunk->WidePoint((int)x, (int)y, (j == 0) ? 1 : 0);
                        if (j == 0) {
                                chunk->WidePointWidth(AcOpts.textureWidth);
                        }
                }

                delete vl;
        }
}

//
// Extract shorelines
//
void Cell::ExtractShoreline(GpcPolygon *shorelines, GpcVertexList *vlist, int level)
{
        bool needInvert = false;

        // Fix draw starting point
        vlist->modifyStartPointFromEdge(bbox);

        // Check drawing order of the line.
        //   Left side of the line will be land, right side will be water.
        //   If not, we set needInvert flag to invert drawing order.
        if (vlist->isLeftHand()) {
                if (!isLand(level)) {
                        needInvert = true;
                }
        } else {
                if (isLand(level)) {
                        needInvert = true;
                }
        }

        // check drawing
        int drawStartPoint = -1;
        int n = vlist->numVertices();
        int prev, flags = 0;
        bool allInside = true;

        for (int i = 0; i < n; i++) {
                prev = flags;
                flags = bbox.checkEdge(vlist->vx(i), vlist->vy(i));
                if (flags) allInside = false;
                
                if (i == 0) continue;

                //fprintf(stderr, (flags) ? "_" : "*");

                // check drawing start point
                if (drawStartPoint < 0) {
                        // Check if we leaved from previous edge?
                        if ((prev & ~flags) != 0 &&
                            (prev & flags) == 0) {
                                // start drawing.
                                drawStartPoint = i - 1;
                                //fprintf(stderr, "S");
                        }
                }

                // check drawing end point
                if (drawStartPoint >= 0 && flags != 0) {
                        // reached to edge.
                        PutShoreLine(shorelines, vlist,
                                     drawStartPoint, i, needInvert);
                        drawStartPoint = -1;
                        //fprintf(stderr, "E");
                }
        }
        //fprintf(stderr, "\n");

        // No vertices are on any edge. Draw all lines...
        if (allInside) {
                PutShoreLine(shorelines, vlist, 0, n - 1, needInvert, true);
        }

        shorelines->BuildVertexListFromGpcPolygon();
}

//
// Put one shoreline
//
void Cell::PutShoreLine(GpcPolygon *shorelines, GpcVertexList *vlist, 
                        int st, int ed, bool needInvert, bool isLoop)
{
        ASSERT(ed > st);

        int n = ed - st + 1;
        if (isLoop) n++;

        GpcVertexList *vl = new GpcVertexList(n, NULL);

        gpc_vertex *s;
        gpc_vertex *d = vl->vertex(0);

        for (int i = 0; i < n ; i++) {
                if (isLoop && i == n - 1) {
                        s = vlist->vertex(st);  // loop
                } else {
                        s = vlist->vertex(st + i);
                }
                *d++ = *s;
        }

        if (needInvert) {
                vl->invert();
        }

        shorelines->AddVertexList(vl, false);
}

// LOD13 conversion
inline int x2ax(double x, BoundingBox &bbox)
{
        int xx = (int)((x - bbox.xmin) / (bbox.xmax - bbox.xmin) * 32);
        if (xx == 32) xx = 31;
        return xx;
}

inline int y2ay(double y, BoundingBox &bbox)
{
        int yy = (int)((y - bbox.ymin) / (bbox.ymax - bbox.ymin) * 32);
        if (yy == 32) yy = 31;
        return yy;
}

//
// Interpolate vertices
//
GpcVertexList *Cell::InterPolateVTPPoints(GpcVertexList *vl)
{
        int i, n;
        list<gpc_vertex>::iterator iter;

        // Create linked list of vertices.
        list<gpc_vertex> vlist;

        n = vl->numVertices();
        for (i = 0; i < n; i++) {
                ASSERT(bbox.isInbox(vl->vx(i), vl->vy(i)));
                vlist.push_back(*vl->vertex(i));
        }

        gpc_vertex v1, v2, vi;
        int ax1, ay1;
        int ax2, ay2;
        int ax3, ay3;
        int dx, dy;

        // check all sides...
        iter = vlist.begin();
        for (;;) {
                v1 = *iter;
                iter++;
                if (iter == vlist.end()) break;
                v2 = *iter;

                ax1 = x2ax(v1.x, bbox);
                ay1 = y2ay(v1.y, bbox);

                ax2 = x2ax(v2.x, bbox);
                ay2 = y2ay(v2.y, bbox);

                // Check if interpolation needed?
                dx = abs(ax1 - ax2);
                dy = abs(ay1 - ay2);
                if ((dx == 0 && dy <= 1) ||
                    (dx <= 1 && dy == 0)) {
                        // no interpolation
                        continue;
                }

                // We need interpolation.
                // Find interpolation point from v1 to v2.
                Vector fv(v1.x, v1.y);
                Vector dv(v2.x - v1.x, v2.y - v1.y);
                Vector point;

                double k = 0.5, kd = 0.25;
                bool tryagain = false;
                for (;;) {
                        point = fv + dv * k;
                        ax3 = x2ax(point.x, bbox);
                        ay3 = y2ay(point.y, bbox);
                                
                        if (ax3 == ax1 && ay3 == ay1) {
                                k += kd;
                        }
                        else if (ax3 == ax2 && ay3 == ay2) {
                                k -= kd;
                        }
                        else {
                                // found!
                                break;
                        }

                        kd = kd / 2.0;

                        if (kd < 1.0e-10) {
                                // oops! no interpolation point!
                                // dirty hack... slightly move 2nd point...
                                (*iter).y += 2.0e-6;
                                tryagain = true;
                                break;
                        }
                }
                if (tryagain) {
                        iter--;
                        continue;
                }
                
                vi.x = point.x;
                vi.y = point.y;

                // Interpolate a point.
                vlist.insert(iter, vi);

                // Go back to a point before interpolated point.
                iter--;
                iter--;
        }

        // Create VertexList
        n = vlist.size();
        GpcVertexList *nvl = new GpcVertexList(n, NULL);

        for (i = 0, iter = vlist.begin(); i < n; i++, iter++) {
                *(nvl->vertex(i)) = *iter;
        }
        ASSERT(iter == vlist.end());

        return nvl;
}