1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_basegfx.hxx"
26 
27 #include <basegfx/raster/rasterconvert3d.hxx>
28 #include <basegfx/polygon/b3dpolygon.hxx>
29 #include <basegfx/polygon/b3dpolypolygon.hxx>
30 #include <basegfx/point/b3dpoint.hxx>
31 
32 //////////////////////////////////////////////////////////////////////////////
33 // implementations of the 3D raster converter
34 
35 namespace basegfx
36 {
37     void RasterConverter3D::addArea(const B3DPolygon& rFill, const B3DHomMatrix* pViewToEye)
38     {
39 	    const sal_uInt32 nPointCount(rFill.count());
40 
41 	    for(sal_uInt32 a(0); a < nPointCount; a++)
42 	    {
43 		    addEdge(rFill, a, (a + 1) % nPointCount, pViewToEye);
44 	    }
45     }
46 
47     void RasterConverter3D::addArea(const B3DPolyPolygon& rFill, const B3DHomMatrix* pViewToEye)
48     {
49 	    const sal_uInt32 nPolyCount(rFill.count());
50 
51 	    for(sal_uInt32 a(0); a < nPolyCount; a++)
52 	    {
53 		    addArea(rFill.getB3DPolygon(a), pViewToEye);
54 	    }
55     }
56 
57     RasterConverter3D::RasterConverter3D()
58     :	InterpolatorProvider3D(),
59 	    maLineEntries()
60     {}
61 
62     RasterConverter3D::~RasterConverter3D()
63     {}
64 
65     void RasterConverter3D::rasterconvertB3DArea(sal_Int32 nStartLine, sal_Int32 nStopLine)
66     {
67 	    if(maLineEntries.size())
68 	    {
69 		    OSL_ENSURE(nStopLine >= nStartLine, "nStopLine is bigger than nStartLine (!)");
70 
71             // sort global entries by Y, X once. After this, the vector
72 		    // is seen as frozen. Pointers to it's entries will be used in the following code.
73 		    ::std::sort(maLineEntries.begin(), maLineEntries.end());
74 
75 		    // local parameters
76 		    ::std::vector< RasterConversionLineEntry3D >::iterator aCurrentEntry(maLineEntries.begin());
77 		    ::std::vector< RasterConversionLineEntry3D* > aCurrentLine;
78 		    ::std::vector< RasterConversionLineEntry3D* > aNextLine;
79 		    ::std::vector< RasterConversionLineEntry3D* >::iterator aRasterConversionLineEntry3D;
80 		    sal_uInt32 nPairCount(0);
81 
82 		    // get scanlines first LineNumber as start
83 		    sal_Int32 nLineNumber(::std::max(aCurrentEntry->getY(), nStartLine));
84 
85 		    while((aCurrentLine.size() || aCurrentEntry != maLineEntries.end()) && (nLineNumber < nStopLine))
86 		    {
87 			    // add all entries which start at current line to current scanline
88 			    while(aCurrentEntry != maLineEntries.end())
89 			    {
90 				    const sal_Int32 nCurrentLineNumber(aCurrentEntry->getY());
91 
92 				    if(nCurrentLineNumber > nLineNumber)
93 				    {
94 					    // line is below current one, done (since array is sorted)
95 					    break;
96 				    }
97 				    else
98 				    {
99 					    // less or equal. Line is above or at current one. Advance it exactly to
100 					    // current line
101 					    const sal_uInt32 nStep(nLineNumber - nCurrentLineNumber);
102 
103 					    if(!nStep || aCurrentEntry->decrementRasterConversionLineEntry3D(nStep))
104 					    {
105 						    // add when exactly on current line or when incremet to it did not
106 						    // completely consume it
107 						    if(nStep)
108 						    {
109 							    aCurrentEntry->incrementRasterConversionLineEntry3D(nStep, *this);
110 						    }
111 
112 						    aCurrentLine.push_back(&(*(aCurrentEntry)));
113 					    }
114 				    }
115 
116 				    aCurrentEntry++;
117 			    }
118 
119 			    // sort current scanline using comparator. Only X is used there
120 			    // since all entries are already in one processed line. This needs to be done
121 			    // everytime since not only new spans may have benn added or old removed,
122 			    // but incrementing may also have changed the order
123 			    ::std::sort(aCurrentLine.begin(), aCurrentLine.end(), lineComparator());
124 
125 			    // process current scanline
126 			    aRasterConversionLineEntry3D = aCurrentLine.begin();
127 			    aNextLine.clear();
128 			    nPairCount = 0;
129 
130 			    while(aRasterConversionLineEntry3D != aCurrentLine.end())
131 			    {
132 				    RasterConversionLineEntry3D& rPrevScanRasterConversionLineEntry3D(**aRasterConversionLineEntry3D++);
133 
134 				    // look for 2nd span
135 				    if(aRasterConversionLineEntry3D != aCurrentLine.end())
136 				    {
137 					    // work on span from rPrevScanRasterConversionLineEntry3D to aRasterConversionLineEntry3D, fLineNumber is valid
138 					    processLineSpan(rPrevScanRasterConversionLineEntry3D, **aRasterConversionLineEntry3D, nLineNumber, nPairCount++);
139 				    }
140 
141 				    // increment to next line
142 				    if(rPrevScanRasterConversionLineEntry3D.decrementRasterConversionLineEntry3D(1))
143 				    {
144 					    rPrevScanRasterConversionLineEntry3D.incrementRasterConversionLineEntry3D(1, *this);
145 					    aNextLine.push_back(&rPrevScanRasterConversionLineEntry3D);
146 				    }
147 			    }
148 
149 			    // copy back next scanline if count has changed
150 			    if(aNextLine.size() != aCurrentLine.size())
151 			    {
152 				    aCurrentLine = aNextLine;
153 			    }
154 
155 			    // increment fLineNumber
156 			    nLineNumber++;
157 		    }
158 	    }
159     }
160 
161     void RasterConverter3D::addEdge(const B3DPolygon& rFill, sal_uInt32 a, sal_uInt32 b, const B3DHomMatrix* pViewToEye)
162     {
163 	    B3DPoint aStart(rFill.getB3DPoint(a));
164 	    B3DPoint aEnd(rFill.getB3DPoint(b));
165 	    sal_Int32 nYStart(fround(aStart.getY()));
166 	    sal_Int32 nYEnd(fround(aEnd.getY()));
167 
168 	    if(nYStart != nYEnd)
169 	    {
170 		    if(nYStart > nYEnd)
171 		    {
172 			    ::std::swap(aStart, aEnd);
173 			    ::std::swap(nYStart, nYEnd);
174 			    ::std::swap(a, b);
175 		    }
176 
177 		    const sal_uInt32 nYDelta(nYEnd - nYStart);
178 		    const double fInvYDelta(1.0 / nYDelta);
179 		    maLineEntries.push_back(RasterConversionLineEntry3D(
180 			    aStart.getX(), (aEnd.getX() - aStart.getX()) * fInvYDelta,
181 			    aStart.getZ(), (aEnd.getZ() - aStart.getZ()) * fInvYDelta,
182 			    nYStart, nYDelta));
183 
184 		    // if extra interpolation data is used, add it to the last created entry
185 		    RasterConversionLineEntry3D& rEntry = maLineEntries[maLineEntries.size() - 1];
186 
187 		    if(rFill.areBColorsUsed())
188 		    {
189 			    rEntry.setColorIndex(addColorInterpolator(rFill.getBColor(a), rFill.getBColor(b), fInvYDelta));
190 		    }
191 
192 		    if(rFill.areNormalsUsed())
193 		    {
194 			    rEntry.setNormalIndex(addNormalInterpolator(rFill.getNormal(a), rFill.getNormal(b), fInvYDelta));
195 		    }
196 
197 		    if(rFill.areTextureCoordinatesUsed())
198 		    {
199 			    if(pViewToEye)
200 			    {
201 				    const double fEyeA(((*pViewToEye) * aStart).getZ());
202 				    const double fEyeB(((*pViewToEye) * aEnd).getZ());
203 
204 				    rEntry.setInverseTextureIndex(addInverseTextureInterpolator(
205 					    rFill.getTextureCoordinate(a),
206 					    rFill.getTextureCoordinate(b),
207 					    fEyeA, fEyeB, fInvYDelta));
208 			    }
209 			    else
210 			    {
211 				    rEntry.setTextureIndex(addTextureInterpolator(
212 					    rFill.getTextureCoordinate(a),
213 					    rFill.getTextureCoordinate(b),
214 					    fInvYDelta));
215 			    }
216 		    }
217 	    }
218     }
219 
220     void RasterConverter3D::rasterconvertB3DEdge(const B3DPolygon& rLine, sal_uInt32 nA, sal_uInt32 nB, sal_Int32 nStartLine, sal_Int32 nStopLine, sal_uInt16 nLineWidth)
221     {
222         B3DPoint aStart(rLine.getB3DPoint(nA));
223         B3DPoint aEnd(rLine.getB3DPoint(nB));
224         const double fZBufferLineAdd(0x00ff);
225 		static bool bForceToPolygon(false);
226 
227         if(nLineWidth > 1 || bForceToPolygon)
228         {
229             // this is not a hairline anymore, in most cases since it's an oversampled
230             // hairline to get e.g. AA for Z-Buffering. Create fill geometry.
231             if(!aStart.equal(aEnd))
232             {
233 		        reset();
234 		        maLineEntries.clear();
235 
236                 B2DVector aVector(aEnd.getX() - aStart.getX(), aEnd.getY() - aStart.getY());
237                 aVector.normalize();
238             	const B2DVector aPerpend(getPerpendicular(aVector) * ((static_cast<double>(nLineWidth) + 0.5) * 0.5));
239                 const double fZStartWithAdd(aStart.getZ() + fZBufferLineAdd);
240                 const double fZEndWithAdd(aEnd.getZ() + fZBufferLineAdd);
241 
242                 B3DPolygon aPolygon;
243                 aPolygon.append(B3DPoint(aStart.getX() + aPerpend.getX(), aStart.getY() + aPerpend.getY(), fZStartWithAdd));
244                 aPolygon.append(B3DPoint(aEnd.getX() + aPerpend.getX(), aEnd.getY() + aPerpend.getY(), fZEndWithAdd));
245                 aPolygon.append(B3DPoint(aEnd.getX() - aPerpend.getX(), aEnd.getY() - aPerpend.getY(), fZEndWithAdd));
246                 aPolygon.append(B3DPoint(aStart.getX() - aPerpend.getX(), aStart.getY() - aPerpend.getY(), fZStartWithAdd));
247                 aPolygon.setClosed(true);
248 
249                 addArea(aPolygon, 0);
250             }
251         }
252         else
253         {
254             // it's a hairline. Use direct RasterConversionLineEntry creation to
255             // rasterconvert lines as similar to areas as possible to avoid Z-Fighting
256 	        sal_Int32 nYStart(fround(aStart.getY()));
257 	        sal_Int32 nYEnd(fround(aEnd.getY()));
258 
259 	        if(nYStart == nYEnd)
260 	        {
261 		        // horizontal line, check X
262 		        const sal_Int32 nXStart(static_cast<sal_Int32>(aStart.getX()));
263 		        const sal_Int32 nXEnd(static_cast<sal_Int32>(aEnd.getX()));
264 
265 		        if(nXStart != nXEnd)
266 		        {
267 			        reset();
268 			        maLineEntries.clear();
269 
270 			        // horizontal line, create vertical entries. These will be sorted by
271 			        // X anyways, so no need to distinguish the case here
272 			        maLineEntries.push_back(RasterConversionLineEntry3D(
273 				        aStart.getX(), 0.0,
274 				        aStart.getZ() + fZBufferLineAdd, 0.0,
275 				        nYStart, 1));
276 			        maLineEntries.push_back(RasterConversionLineEntry3D(
277 				        aEnd.getX(), 0.0,
278 				        aEnd.getZ() + fZBufferLineAdd, 0.0,
279 				        nYStart, 1));
280 		        }
281 	        }
282 	        else
283 	        {
284 		        reset();
285 		        maLineEntries.clear();
286 
287 		        if(nYStart > nYEnd)
288 		        {
289 			        ::std::swap(aStart, aEnd);
290 			        ::std::swap(nYStart, nYEnd);
291 		        }
292 
293 		        const sal_uInt32 nYDelta(static_cast<sal_uInt32>(nYEnd - nYStart));
294 		        const double fInvYDelta(1.0 / nYDelta);
295 
296 		        // non-horizontal line, create two parallell entries. These will be sorted by
297 		        // X anyways, so no need to distinguish the case here
298 		        maLineEntries.push_back(RasterConversionLineEntry3D(
299 			        aStart.getX(), (aEnd.getX() - aStart.getX()) * fInvYDelta,
300 			        aStart.getZ() + fZBufferLineAdd, (aEnd.getZ() - aStart.getZ()) * fInvYDelta,
301 			        nYStart, nYDelta));
302 
303 		        RasterConversionLineEntry3D& rEntry = maLineEntries[maLineEntries.size() - 1];
304 
305 		        // need to choose a X-Distance for the 2nd edge which guarantees all pixels
306 		        // of the line to be set. This is exactly the X-Increment for one Y-Step.
307 		        // Same is true for Z, so in both cases, add one increment to them. To also
308 		        // guarantee one pixel per line, add a minimum of one for X.
309 		        const double fDistanceX(fabs(rEntry.getX().getInc()) >= 1.0 ? rEntry.getX().getInc() : 1.0);
310 
311 		        maLineEntries.push_back(RasterConversionLineEntry3D(
312 			        rEntry.getX().getVal() + fDistanceX, rEntry.getX().getInc(),
313 			        rEntry.getZ().getVal() + rEntry.getZ().getInc(), rEntry.getZ().getInc(),
314 			        nYStart, nYDelta));
315 	        }
316         }
317 
318         if(maLineEntries.size())
319         {
320 	        rasterconvertB3DArea(nStartLine, nStopLine);
321         }
322     }
323 
324     void RasterConverter3D::rasterconvertB3DPolyPolygon(const B3DPolyPolygon& rFill, const B3DHomMatrix* pViewToEye, sal_Int32 nStartLine, sal_Int32 nStopLine)
325     {
326 	    reset();
327 	    maLineEntries.clear();
328 	    addArea(rFill, pViewToEye);
329 	    rasterconvertB3DArea(nStartLine, nStopLine);
330     }
331 
332     void RasterConverter3D::rasterconvertB3DPolygon(const B3DPolygon& rLine, sal_Int32 nStartLine, sal_Int32 nStopLine, sal_uInt16 nLineWidth)
333     {
334 	    const sal_uInt32 nPointCount(rLine.count());
335 
336 	    if(nPointCount)
337 	    {
338 		    const sal_uInt32 nEdgeCount(rLine.isClosed() ? nPointCount : nPointCount - 1);
339 
340 		    for(sal_uInt32 a(0); a < nEdgeCount; a++)
341 		    {
342 			    rasterconvertB3DEdge(rLine, a, (a + 1) % nPointCount, nStartLine, nStopLine, nLineWidth);
343 		    }
344 	    }
345     }
346 } // end of namespace basegfx
347 
348 //////////////////////////////////////////////////////////////////////////////
349 // eof
350