xref: /trunk/main/basegfx/source/polygon/b3dpolygonclipper.cxx (revision cf6516809c57e1bb0a940545cca99cdad54d4ce2)

/**************************************************************
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 *************************************************************/



// MARKER(update_precomp.py): autogen include statement, do not remove
#include "precompiled_basegfx.hxx"

#include <basegfx/polygon/b3dpolygonclipper.hxx>
#include <osl/diagnose.h>
#include <basegfx/polygon/b3dpolygontools.hxx>
#include <basegfx/numeric/ftools.hxx>
#include <basegfx/matrix/b3dhommatrix.hxx>
#include <basegfx/polygon/b3dpolygontools.hxx>
#include <basegfx/range/b3drange.hxx>
#include <basegfx/point/b2dpoint.hxx>
#include <basegfx/range/b2drange.hxx>
#include <basegfx/color/bcolor.hxx>

//////////////////////////////////////////////////////////////////////////////

namespace basegfx
{
    namespace
    {
        inline bool impIsInside(const B3DPoint& rCandidate, double fPlaneOffset, tools::B3DOrientation ePlaneOrthogonal)
        {
            if(tools::B3DORIENTATION_X == ePlaneOrthogonal)
            {
                return fTools::moreOrEqual(rCandidate.getX(), fPlaneOffset);
            }
            else if(tools::B3DORIENTATION_Y == ePlaneOrthogonal)
            {
                return fTools::moreOrEqual(rCandidate.getY(), fPlaneOffset);
            }
            else
            {
                return fTools::moreOrEqual(rCandidate.getZ(), fPlaneOffset);
            }
        }

        inline double impGetCut(const B3DPoint& rCurrent, const B3DPoint& rNext, double fPlaneOffset, tools::B3DOrientation ePlaneOrthogonal)
        {
            if(tools::B3DORIENTATION_X == ePlaneOrthogonal)
            {
                return ((fPlaneOffset - rCurrent.getX())/(rNext.getX() - rCurrent.getX()));
            }
            else if(tools::B3DORIENTATION_Y == ePlaneOrthogonal)
            {
                return ((fPlaneOffset - rCurrent.getY())/(rNext.getY() - rCurrent.getY()));
            }
            else
            {
                return ((fPlaneOffset - rCurrent.getZ())/(rNext.getZ() - rCurrent.getZ()));
            }
        }

        void impAppendCopy(B3DPolygon& rDest, const B3DPolygon& rSource, sal_uInt32 nIndex)
        {
            rDest.append(rSource.getB3DPoint(nIndex));

            if(rSource.areBColorsUsed())
            {
                rDest.setBColor(rDest.count() - 1L, rSource.getBColor(nIndex));
            }

            if(rSource.areNormalsUsed())
            {
                rDest.setNormal(rDest.count() - 1L, rSource.getNormal(nIndex));
            }

            if(rSource.areTextureCoordinatesUsed())
            {
                rDest.setTextureCoordinate(rDest.count() - 1L, rSource.getTextureCoordinate(nIndex));
            }
        }

        void impAppendInterpolate(B3DPolygon& rDest, const B3DPolygon& rSource, sal_uInt32 nIndA, sal_uInt32 nIndB, double fCut)
        {
            const B3DPoint aCurrPoint(rSource.getB3DPoint(nIndA));
            const B3DPoint aNextPoint(rSource.getB3DPoint(nIndB));
            rDest.append(interpolate(aCurrPoint, aNextPoint, fCut));

            if(rSource.areBColorsUsed())
            {
                const BColor aCurrBColor(rSource.getBColor(nIndA));
                const BColor aNextBColor(rSource.getBColor(nIndB));
                rDest.setBColor(rDest.count() - 1L, interpolate(aCurrBColor, aNextBColor, fCut));
            }

            if(rSource.areNormalsUsed())
            {
                const B3DVector aCurrVector(rSource.getNormal(nIndA));
                const B3DVector aNextVector(rSource.getNormal(nIndB));
                rDest.setNormal(rDest.count() - 1L, interpolate(aCurrVector, aNextVector, fCut));
            }

            if(rSource.areTextureCoordinatesUsed())
            {
                const B2DPoint aCurrTxCo(rSource.getTextureCoordinate(nIndA));
                const B2DPoint aNextTxCo(rSource.getTextureCoordinate(nIndB));
                rDest.setTextureCoordinate(rDest.count() - 1L, interpolate(aCurrTxCo, aNextTxCo, fCut));
            }
        }
    }
} // end of namespace basegfx

//////////////////////////////////////////////////////////////////////////////

namespace basegfx
{
    namespace tools
    {
        B3DPolyPolygon clipPolygonOnOrthogonalPlane(const B3DPolygon& rCandidate, B3DOrientation ePlaneOrthogonal, bool bClipPositive, double fPlaneOffset, bool bStroke)
        {
            B3DPolyPolygon aRetval;

            if(rCandidate.count())
            {
                const B3DRange aCandidateRange(getRange(rCandidate));

                if(B3DORIENTATION_X == ePlaneOrthogonal && fTools::moreOrEqual(aCandidateRange.getMinX(), fPlaneOffset))
                {
                    // completely above and on the clip plane.
                    if(bClipPositive)
                    {
                        // add completely
                        aRetval.append(rCandidate);
                    }
                }
                else if(B3DORIENTATION_X == ePlaneOrthogonal && fTools::lessOrEqual(aCandidateRange.getMaxX(), fPlaneOffset))
                {
                    // completely below and on the clip plane.
                    if(!bClipPositive)
                    {
                        // add completely
                        aRetval.append(rCandidate);
                    }
                }
                else if(B3DORIENTATION_Y == ePlaneOrthogonal && fTools::moreOrEqual(aCandidateRange.getMinY(), fPlaneOffset))
                {
                    // completely above and on the clip plane.
                    if(bClipPositive)
                    {
                        // add completely
                        aRetval.append(rCandidate);
                    }
                }
                else if(B3DORIENTATION_Y == ePlaneOrthogonal && fTools::lessOrEqual(aCandidateRange.getMaxY(), fPlaneOffset))
                {
                    // completely below and on the clip plane.
                    if(!bClipPositive)
                    {
                        // add completely
                        aRetval.append(rCandidate);
                    }
                }
                else if(B3DORIENTATION_Z == ePlaneOrthogonal && fTools::moreOrEqual(aCandidateRange.getMinZ(), fPlaneOffset))
                {
                    // completely above and on the clip plane.
                    if(bClipPositive)
                    {
                        // add completely
                        aRetval.append(rCandidate);
                    }
                }
                else if(B3DORIENTATION_Z == ePlaneOrthogonal && fTools::lessOrEqual(aCandidateRange.getMaxZ(), fPlaneOffset))
                {
                    // completely below and on the clip plane.
                    if(!bClipPositive)
                    {
                        // add completely
                        aRetval.append(rCandidate);
                    }
                }
                else
                {
                    // prepare loop(s)
                    B3DPolygon aNewPolygon;
                    B3DPoint aCurrent(rCandidate.getB3DPoint(0L));
                    const sal_uInt32 nPointCount(rCandidate.count());
                    const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
                    bool bCurrentInside(impIsInside(aCurrent, fPlaneOffset, ePlaneOrthogonal) == bClipPositive);

                    if(bCurrentInside)
                    {
                        impAppendCopy(aNewPolygon, rCandidate, 0L);
                    }

                    if(bStroke)
                    {
                        // open polygon, create clipped line snippets.
                        for(sal_uInt32 a(0L); a < nEdgeCount; a++)
                        {
                            // get next point data
                            const sal_uInt32 nNextIndex((a + 1L == nPointCount) ? 0L : a + 1L);
                            const B3DPoint aNext(rCandidate.getB3DPoint(nNextIndex));
                            const bool bNextInside(impIsInside(aNext, fPlaneOffset, ePlaneOrthogonal) == bClipPositive);

                            if(bCurrentInside != bNextInside)
                            {
                                // change inside/outside
                                if(bNextInside)
                                {
                                    // entering, finish existing and start new line polygon
                                    if(aNewPolygon.count() > 1L)
                                    {
                                        aRetval.append(aNewPolygon);
                                    }

                                    aNewPolygon.clear();
                                }

                                // calculate and add cut point
                                const double fCut(impGetCut(aCurrent, aNext, fPlaneOffset, ePlaneOrthogonal));
                                impAppendInterpolate(aNewPolygon, rCandidate, a, nNextIndex, fCut);

                                // pepare next step
                                bCurrentInside = bNextInside;
                            }

                            if(bNextInside)
                            {
                                impAppendCopy(aNewPolygon, rCandidate, nNextIndex);
                            }

                            // pepare next step
                            aCurrent = aNext;
                        }

                        if(aNewPolygon.count() > 1L)
                        {
                            aRetval.append(aNewPolygon);
                        }
                    }
                    else
                    {
                        // closed polygon, create single clipped closed polygon
                        for(sal_uInt32 a(0L); a < nEdgeCount; a++)
                        {
                            // get next point data, use offset
                            const sal_uInt32 nNextIndex((a + 1L == nPointCount) ? 0L : a + 1L);
                            const B3DPoint aNext(rCandidate.getB3DPoint(nNextIndex));
                            const bool bNextInside(impIsInside(aNext, fPlaneOffset, ePlaneOrthogonal) == bClipPositive);

                            if(bCurrentInside != bNextInside)
                            {
                                // calculate and add cut point
                                const double fCut(impGetCut(aCurrent, aNext, fPlaneOffset, ePlaneOrthogonal));
                                impAppendInterpolate(aNewPolygon, rCandidate, a, nNextIndex, fCut);

                                // pepare next step
                                bCurrentInside = bNextInside;
                            }

                            if(bNextInside && nNextIndex)
                            {
                                impAppendCopy(aNewPolygon, rCandidate, nNextIndex);
                            }

                            // pepare next step
                            aCurrent = aNext;
                        }

                        if(aNewPolygon.count() > 2L)
                        {
                            aNewPolygon.setClosed(true);
                            aRetval.append(aNewPolygon);
                        }
                    }
                }
            }

            return aRetval;
        }

        B3DPolyPolygon clipPolyPolygonOnOrthogonalPlane(const B3DPolyPolygon& rCandidate, B3DOrientation ePlaneOrthogonal, bool bClipPositive, double fPlaneOffset, bool bStroke)
        {
            B3DPolyPolygon aRetval;

            for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
            {
                aRetval.append(clipPolygonOnOrthogonalPlane(rCandidate.getB3DPolygon(a), ePlaneOrthogonal, bClipPositive, fPlaneOffset, bStroke));
            }

            return aRetval;
        }

        B3DPolyPolygon clipPolyPolygonOnRange(const B3DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
        {
            B3DPolyPolygon aRetval;

            for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
            {
                aRetval.append(clipPolygonOnRange(rCandidate.getB3DPolygon(a), rRange, bInside, bStroke));
            }

            return aRetval;
        }

        B3DPolyPolygon clipPolygonOnRange(const B3DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
        {
            B3DPolyPolygon aRetval;

            if(rRange.isEmpty())
            {
                // clipping against an empty range. Nothing is inside an empty range, so the polygon
                // is outside the range. So only return if not inside is wanted
                if(!bInside && rCandidate.count())
                {
                    aRetval.append(rCandidate);
                }
            }
            else if(rCandidate.count())
            {
                const B3DRange aCandidateRange3D(getRange(rCandidate));
                const B2DRange aCandidateRange(
                    aCandidateRange3D.getMinX(), aCandidateRange3D.getMinY(),
                    aCandidateRange3D.getMaxX(), aCandidateRange3D.getMaxY());

                if(rRange.isInside(aCandidateRange))
                {
                    // candidate is completely inside given range, nothing to do. Is also true with curves.
                    if(bInside)
                    {
                        aRetval.append(rCandidate);
                    }
                }
                else if(!rRange.overlaps(aCandidateRange))
                {
                    // candidate is completely outside given range, nothing to do. Is also true with curves.
                    if(!bInside)
                    {
                        aRetval.append(rCandidate);
                    }
                }
                else
                {
                    // clip against the six planes of the range
                    // against lower X
                    aRetval = clipPolygonOnOrthogonalPlane(rCandidate, tools::B3DORIENTATION_X, bInside, rRange.getMinX(), bStroke);

                    if(aRetval.count())
                    {
                        // against lower Y
                        if(1L == aRetval.count())
                        {
                            aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Y, bInside, rRange.getMinY(), bStroke);
                        }
                        else
                        {
                            aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Y, bInside, rRange.getMinY(), bStroke);
                        }

                        if(aRetval.count())
                        {
                            // against higher X
                            if(1L == aRetval.count())
                            {
                                aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_X, !bInside, rRange.getMaxX(), bStroke);
                            }
                            else
                            {
                                aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_X, !bInside, rRange.getMaxX(), bStroke);
                            }

                            if(aRetval.count())
                            {
                                // against higher Y
                                if(1L == aRetval.count())
                                {
                                    aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Y, !bInside, rRange.getMaxY(), bStroke);
                                }
                                else
                                {
                                    aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Y, !bInside, rRange.getMaxY(), bStroke);
                                }
                            }
                        }
                    }
                }
            }

            return aRetval;
        }

        B3DPolyPolygon clipPolyPolygonOnRange(const B3DPolyPolygon& rCandidate, const B3DRange& rRange, bool bInside, bool bStroke)
        {
            B3DPolyPolygon aRetval;

            for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
            {
                aRetval.append(clipPolygonOnRange(rCandidate.getB3DPolygon(a), rRange, bInside, bStroke));
            }

            return aRetval;
        }

        B3DPolyPolygon clipPolygonOnRange(const B3DPolygon& rCandidate, const B3DRange& rRange, bool bInside, bool bStroke)
        {
            B3DPolyPolygon aRetval;

            if(rRange.isEmpty())
            {
                // clipping against an empty range. Nothing is inside an empty range, so the polygon
                // is outside the range. So only return if not inside is wanted
                if(!bInside && rCandidate.count())
                {
                    aRetval.append(rCandidate);
                }
            }
            else if(rCandidate.count())
            {
                const B3DRange aCandidateRange(getRange(rCandidate));

                if(rRange.isInside(aCandidateRange))
                {
                    // candidate is completely inside given range, nothing to do. Is also true with curves.
                    if(bInside)
                    {
                        aRetval.append(rCandidate);
                    }
                }
                else if(!rRange.overlaps(aCandidateRange))
                {
                    // candidate is completely outside given range, nothing to do. Is also true with curves.
                    if(!bInside)
                    {
                        aRetval.append(rCandidate);
                    }
                }
                else
                {
                    // clip against X,Y first and see if there's something left
                    const B2DRange aCandidateRange2D(rRange.getMinX(), rRange.getMinY(), rRange.getMaxX(), rRange.getMaxY());
                    aRetval = clipPolygonOnRange(rCandidate, aCandidateRange2D, bInside, bStroke);

                    if(aRetval.count())
                    {
                        // against lower Z
                        if(1L == aRetval.count())
                        {
                            aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Z, bInside, rRange.getMinZ(), bStroke);
                        }
                        else
                        {
                            aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Z, bInside, rRange.getMinZ(), bStroke);
                        }

                        if(aRetval.count())
                        {
                            // against higher Z
                            if(1L == aRetval.count())
                            {
                                aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Z, !bInside, rRange.getMaxZ(), bStroke);
                            }
                            else
                            {
                                aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Z, !bInside, rRange.getMaxZ(), bStroke);
                            }
                        }
                    }
                }
            }

            return aRetval;
        }

        B3DPolyPolygon clipPolygonOnPlane(const B3DPolygon& rCandidate, const B3DPoint& rPointOnPlane, const B3DVector& rPlaneNormal, bool bClipPositive, bool bStroke)
        {
            B3DPolyPolygon aRetval;

            if(rPlaneNormal.equalZero())
            {
                // not really a plane definition, return polygon
                aRetval.append(rCandidate);
            }
            else if(rCandidate.count())
            {
                // build transform to project planeNormal on X-Axis and pointOnPlane to null point
                B3DHomMatrix aMatrixTransform;
                aMatrixTransform.translate(-rPointOnPlane.getX(), -rPointOnPlane.getY(), -rPointOnPlane.getZ());
                const double fRotInXY(atan2(rPlaneNormal.getY(), rPlaneNormal.getX()));
                const double fRotInXZ(atan2(-rPlaneNormal.getZ(), rPlaneNormal.getXYLength()));
                if(!fTools::equalZero(fRotInXY) || !fTools::equalZero(fRotInXZ))
                {
                    aMatrixTransform.rotate(0.0, fRotInXZ, fRotInXY);
                }

                // transform polygon to clip scenario
                B3DPolygon aCandidate(rCandidate);
                aCandidate.transform(aMatrixTransform);

                // clip on YZ plane
                aRetval = clipPolygonOnOrthogonalPlane(aCandidate, tools::B3DORIENTATION_X, bClipPositive, 0.0, bStroke);

                if(aRetval.count())
                {
                    // if there is a result, it needs to be transformed back
                    aMatrixTransform.invert();
                    aRetval.transform(aMatrixTransform);
                }
            }

            return aRetval;
        }

        B3DPolyPolygon clipPolyPolygonOnPlane(const B3DPolyPolygon& rCandidate, const B3DPoint& rPointOnPlane, const B3DVector& rPlaneNormal, bool bClipPositive, bool bStroke)
        {
            B3DPolyPolygon aRetval;

            if(rPlaneNormal.equalZero())
            {
                // not really a plane definition, return polygon
                aRetval = rCandidate;
            }
            else if(rCandidate.count())
            {
                // build transform to project planeNormal on X-Axis and pointOnPlane to null point
                B3DHomMatrix aMatrixTransform;
                aMatrixTransform.translate(-rPointOnPlane.getX(), -rPointOnPlane.getY(), -rPointOnPlane.getZ());
                const double fRotInXY(atan2(rPlaneNormal.getY(), rPlaneNormal.getX()));
                const double fRotInXZ(atan2(-rPlaneNormal.getZ(), rPlaneNormal.getXYLength()));
                if(!fTools::equalZero(fRotInXY) || !fTools::equalZero(fRotInXZ))
                {
                    aMatrixTransform.rotate(0.0, fRotInXZ, fRotInXY);
                }

                // transform polygon to clip scenario
                aRetval = rCandidate;
                aRetval.transform(aMatrixTransform);

                // clip on YZ plane
                aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_X, bClipPositive, 0.0, bStroke);

                if(aRetval.count())
                {
                    // if there is a result, it needs to be transformed back
                    aMatrixTransform.invert();
                    aRetval.transform(aMatrixTransform);
                }
            }

            return aRetval;
        }

    } // end of namespace tools
} // end of namespace basegfx

//////////////////////////////////////////////////////////////////////////////

// eof