INTEGRATION: CWS aw033 (1.1.2); FILE ADDED

2008/08/19 16:43:45 cl 1.1.2.4: fixed license files
2008/05/27 14:08:46 aw 1.1.2.3: #i39532# changes DEV300 m12 resync corrections
2007/01/22 17:32:05 aw 1.1.2.2: changes after resync
2006/05/12 11:34:51 aw 1.1.2.1: code for primitive support

1 files changed, 578 insertions, 0 deletions

diff --git a/basegfx/source/polygon/b3dpolygonclipper.cxx b/basegfx/source/polygon/b3dpolygonclipper.cxx
new file mode 100644
index 000000000000..93c446ff57a5
--- /dev/null
+++ b/basegfx/source/polygon/b3dpolygonclipper.cxx
@@ -0,0 +1,578 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2008 by Sun Microsystems, Inc.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * $RCSfile: b3dpolygonclipper.cxx,v $
+ *
+ * $Revision: 1.2 $
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 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