1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
5 #![allow(unused_parens)]
7 use crate::aacoverage::{CCoverageBuffer, c_rInvShiftSize, c_antiAliasMode, c_nShift, CCoverageInterval, c_nShiftMask, c_nShiftSize, c_nHalfShiftSize};
8 use crate::hwvertexbuffer::CHwVertexBufferBuilder;
9 use crate::matrix::{CMILMatrix, CMatrix};
10 use crate::nullable_ref::Ref;
11 use crate::aarasterizer::*;
12 use crate::geometry_sink::IGeometrySink;
13 use crate::helpers::Int32x32To64;
15 use typed_arena_nomut::Arena;
17 //-----------------------------------------------------------------------------
22 // Trapezoidal anti-aliasing implementation
24 // >>>> Note that some of this code is duplicated in sw\aarasterizer.cpp,
25 // >>>> so changes to this file may need to propagate.
27 // pursue reduced code duplication
30 macro_rules! MIL_THR {
32 $e//assert_eq!($e, S_OK);
38 // Optimize for speed instead of size for these critical methods
42 //-------------------------------------------------------------------------
44 // Coordinate system encoding
46 // All points/coordinates are named as follows:
48 // <HungarianType><CoordinateSystem>[X|Y][Left|Right|Top|Bottom]VariableName
50 // Common hungarian types:
55 // Coordinate systems:
56 // Pixel - Device pixel space assuming integer coordinates in the pixel top left corner.
57 // Subpixel - Overscaled space.
59 // To convert between Pixel to Subpixel, we have:
60 // nSubpixelCoordinate = nPixelCoordinate << c_nShift;
61 // nPixelCoordinate = nSubpixelCoordinate >> c_nShift;
63 // Note that the conversion to nPixelCoordinate needs to also track
64 // (nSubpixelCoordinate & c_nShiftMask) to maintain the full value.
66 // Note that since trapezoidal only supports 8x8, c_nShiftSize is always equal to 8. So,
67 // (1, 2) in pixel space would become (8, 16) in subpixel space.
70 // Indicates which coordinate is being referred to.
72 // [Left|Right|Top|Bottom]
73 // When referring to trapezoids or rectangular regions, this
74 // component indicates which edge is being referred to.
77 // Descriptive portion of the variable name
79 //-------------------------------------------------------------------------
82 //-------------------------------------------------------------------------
84 // Function: IsFractionGreaterThan
87 // Determine if nNumeratorA/nDenominatorA > nNumeratorB/nDenominatorB
89 // Note that we assume all denominators are strictly greater than zero.
91 //-------------------------------------------------------------------------
92 fn IsFractionGreaterThan(
93 nNumeratorA: INT, // Left hand side numerator
94 /* __in_range(>=, 1) */ nDenominatorA: INT, // Left hand side denominator
95 nNumeratorB: INT, // Right hand side numerator
96 /* __in_range(>=, 1) */ nDenominatorB: INT, // Right hand side denominator
100 // nNumeratorA/nDenominatorA > nNumeratorB/nDenominatorB
101 // iff nNumeratorA*nDenominatorB/nDenominatorA > nNumeratorB, since nDenominatorB > 0
102 // iff nNumeratorA*nDenominatorB > nNumeratorB*nDenominatorA, since nDenominatorA > 0
104 // Now, all input parameters are 32-bit integers, so we need to use
105 // a 64-bit result to compute the product.
108 let lNumeratorAxDenominatorB = Int32x32To64(nNumeratorA, nDenominatorB);
109 let lNumeratorBxDenominatorA = Int32x32To64(nNumeratorB, nDenominatorA);
111 return (lNumeratorAxDenominatorB > lNumeratorBxDenominatorA);
114 //-------------------------------------------------------------------------
116 // Function: IsFractionLessThan
119 // Determine if nNumeratorA/nDenominatorA < nNumeratorB/nDenominatorB
121 // Note that we assume all denominators are strictly greater than zero.
123 //-------------------------------------------------------------------------
126 nNumeratorA: INT, // Left hand side numerator
127 /* __in_range(>=, 1) */ nDenominatorA: INT, // Left hand side denominator
128 nNumeratorB: INT, // Right hand side numerator
129 /* __in_range(>=, 1) */ nDenominatorB: INT, // Right hand side denominator
133 // Same check as previous function with less than comparision instead of
134 // a greater than comparison.
137 let lNumeratorAxDenominatorB = Int32x32To64(nNumeratorA, nDenominatorB);
138 let lNumeratorBxDenominatorA = Int32x32To64(nNumeratorB, nDenominatorA);
140 return (lNumeratorAxDenominatorB < lNumeratorBxDenominatorA);
144 //-------------------------------------------------------------------------
146 // Function: AdvanceDDAMultipleSteps
149 // Advance the DDA by multiple steps
151 //-------------------------------------------------------------------------
153 AdvanceDDAMultipleSteps(
154 pEdgeLeft: &CEdge, // Left edge from active edge list
155 pEdgeRight: &CEdge, // Right edge from active edge list
156 nSubpixelYAdvance: INT, // Number of steps to advance the DDA
157 nSubpixelXLeftBottom: &mut INT, // Resulting left x position
158 nSubpixelErrorLeftBottom: &mut INT, // Resulting left x position error
159 nSubpixelXRightBottom: &mut INT, // Resulting right x position
160 nSubpixelErrorRightBottom: &mut INT // Resulting right x position error
164 // In this method, we need to be careful of overflow. Expected input ranges for values are:
166 // edge points: x and y subpixel space coordinates are between [-2^26, 2^26]
167 // since we start with 28.4 space (and are now in subpixel space,
168 // i.e., no 16x scale) and assume 2 bits of working space.
170 // This assumption is ensured by TransformRasterizerPointsTo28_4.
172 #[cfg(debug_assertions)]
174 let nDbgPixelCoordinateMax = (1 << 26);
175 let nDbgPixelCoordinateMin = -nDbgPixelCoordinateMax;
177 assert!(pEdgeLeft.X.get() >= nDbgPixelCoordinateMin && pEdgeLeft.X.get() <= nDbgPixelCoordinateMax);
178 assert!(pEdgeLeft.EndY >= nDbgPixelCoordinateMin && pEdgeLeft.EndY <= nDbgPixelCoordinateMax);
179 assert!(pEdgeRight.X.get() >= nDbgPixelCoordinateMin && pEdgeRight.X.get() <= nDbgPixelCoordinateMax);
180 assert!(pEdgeRight.EndY >= nDbgPixelCoordinateMin && pEdgeRight.EndY <= nDbgPixelCoordinateMax);
183 // errorDown: (0, 2^30)
184 // Since errorDown is the edge delta y in 28.4 space (not subpixel space
185 // like the end points), we have a larger range of (0, 2^32) for the positive
186 // error down. With 2 bits of work space (which TransformRasterizerPointsTo28_4
187 // ensures), we know we are between (0, 2^30)
190 let nDbgErrorDownMax: INT = (1 << 30);
191 assert!(pEdgeLeft.ErrorDown > 0 && pEdgeLeft.ErrorDown < nDbgErrorDownMax);
192 assert!(pEdgeRight.ErrorDown > 0 && pEdgeRight.ErrorDown < nDbgErrorDownMax);
195 // errorUp: [0, errorDown)
197 assert!(pEdgeLeft.ErrorUp >= 0 && pEdgeLeft.ErrorUp < pEdgeLeft.ErrorDown);
198 assert!(pEdgeRight.ErrorUp >= 0 && pEdgeRight.ErrorUp < pEdgeRight.ErrorDown);
202 // Advance the left edge
205 // Since each point on the edge is withing 28.4 space, the following computation can't overflow.
206 *nSubpixelXLeftBottom = pEdgeLeft.X.get() + nSubpixelYAdvance*pEdgeLeft.Dx;
208 // Since the error values can be close to 2^30, we can get an overflow by multiplying with yAdvance.
209 // So, we need to use a 64-bit temporary in this case.
210 let mut llSubpixelErrorBottom: LONGLONG = pEdgeLeft.Error.get() as LONGLONG + Int32x32To64(nSubpixelYAdvance, pEdgeLeft.ErrorUp);
211 if (llSubpixelErrorBottom >= 0)
213 let llSubpixelXLeftDelta = llSubpixelErrorBottom / (pEdgeLeft.ErrorDown as LONGLONG);
215 // The delta should remain in range since it still represents a delta along the edge which
216 // we know fits entirely in 28.4. Note that we add one here since the error must end up
218 assert!(llSubpixelXLeftDelta < INT::MAX as LONGLONG);
219 let nSubpixelXLeftDelta: INT = (llSubpixelXLeftDelta as INT) + 1;
221 *nSubpixelXLeftBottom += nSubpixelXLeftDelta;
222 llSubpixelErrorBottom -= Int32x32To64(pEdgeLeft.ErrorDown, nSubpixelXLeftDelta);
225 // At this point, the subtraction above should have generated an error that is within
226 // (-pLeft->ErrorDown, 0)
228 assert!((llSubpixelErrorBottom > -pEdgeLeft.ErrorDown as LONGLONG) && (llSubpixelErrorBottom < 0));
229 *nSubpixelErrorLeftBottom = (llSubpixelErrorBottom as INT);
232 // Advance the right edge
235 // Since each point on the edge is withing 28.4 space, the following computation can't overflow.
236 *nSubpixelXRightBottom = pEdgeRight.X.get() + nSubpixelYAdvance*pEdgeRight.Dx;
238 // Since the error values can be close to 2^30, we can get an overflow by multiplying with yAdvance.
239 // So, we need to use a 64-bit temporary in this case.
240 llSubpixelErrorBottom = pEdgeRight.Error.get() as LONGLONG + Int32x32To64(nSubpixelYAdvance, pEdgeRight.ErrorUp);
241 if (llSubpixelErrorBottom >= 0)
243 let llSubpixelXRightDelta: LONGLONG = llSubpixelErrorBottom / (pEdgeRight.ErrorDown as LONGLONG);
245 // The delta should remain in range since it still represents a delta along the edge which
246 // we know fits entirely in 28.4. Note that we add one here since the error must end up
248 assert!(llSubpixelXRightDelta < INT::MAX as LONGLONG);
249 let nSubpixelXRightDelta: INT = (llSubpixelXRightDelta as INT) + 1;
251 *nSubpixelXRightBottom += nSubpixelXRightDelta;
252 llSubpixelErrorBottom -= Int32x32To64(pEdgeRight.ErrorDown, nSubpixelXRightDelta);
255 // At this point, the subtraction above should have generated an error that is within
256 // (-pRight->ErrorDown, 0)
258 assert!((llSubpixelErrorBottom > -pEdgeRight.ErrorDown as LONGLONG) && (llSubpixelErrorBottom < 0));
259 *nSubpixelErrorRightBottom = (llSubpixelErrorBottom as INT);
262 //-------------------------------------------------------------------------
264 // Function: ComputeDeltaUpperBound
267 // Compute some value that is >= nSubpixelAdvanceY*|1/m| where m is the
268 // slope defined by the edge below.
270 //-------------------------------------------------------------------------
272 ComputeDeltaUpperBound(
273 pEdge: &CEdge, // Edge containing 1/m value used for computation
274 nSubpixelYAdvance: INT // Multiplier in synopsis expression
277 let nSubpixelDeltaUpperBound: INT;
280 // Compute the delta bound
283 if (pEdge.ErrorUp == 0)
286 // No errorUp, so simply compute bound based on dx value
289 nSubpixelDeltaUpperBound = nSubpixelYAdvance*(pEdge.Dx).abs();
294 let nAbsErrorUp: INT;
297 // Compute abs of (dx, error)
299 // Here, we can assume errorUp > 0
302 assert!(pEdge.ErrorUp > 0);
307 nAbsErrorUp = pEdge.ErrorUp;
312 // Dx < 0, so negate (dx, errorUp)
314 // Note that since errorUp > 0, we know -errorUp < 0 and that
315 // we need to add errorDown to get an errorUp >= 0 which
316 // also means substracting one from dx.
319 nAbsDx = -pEdge.Dx - 1;
320 nAbsErrorUp = -pEdge.ErrorUp + pEdge.ErrorDown;
324 // Compute the bound of nSubpixelAdvanceY*|1/m|
326 // Note that the +1 below is included to bound any left over errorUp that we are dropping here.
329 nSubpixelDeltaUpperBound = nSubpixelYAdvance*nAbsDx + (nSubpixelYAdvance*nAbsErrorUp)/pEdge.ErrorDown + 1;
332 return nSubpixelDeltaUpperBound;
335 //-------------------------------------------------------------------------
337 // Function: ComputeDistanceLowerBound
340 // Compute some value that is <= distance between
341 // (pEdgeLeft->X, pEdgeLeft->Error) and (pEdgeRight->X, pEdgeRight->Error)
343 //-------------------------------------------------------------------------
345 ComputeDistanceLowerBound(
346 pEdgeLeft: &CEdge, // Left edge containing the position for the distance computation
347 pEdgeRight: &CEdge // Right edge containing the position for the distance computation
351 // Note: In these comments, error1 and error2 are theoretical. The actual Error members
354 // distance = (x2 + error2/errorDown2) - (x1 + error1/errorDown1)
355 // = x2 - x1 + error2/errorDown2 - error1/errorDown1
356 // >= x2 - x1 + error2/errorDown2 , since error1 < 0
357 // >= x2 - x1 - 1 , since error2 < 0
358 // = pEdgeRight->X - pEdgeLeft->X - 1
360 // In the special case where error2/errorDown2 >= error1/errorDown1, we
361 // can get a tigher bound of:
363 // pEdgeRight->X - pEdgeLeft->X
365 // This case occurs often in thin strokes, so we check for it here.
368 assert!(pEdgeLeft.Error.get() < 0);
369 assert!(pEdgeRight.Error.get() < 0);
370 assert!(pEdgeLeft.X <= pEdgeRight.X);
372 let mut nSubpixelXDistanceLowerBound: INT = pEdgeRight.X.get() - pEdgeLeft.X.get();
375 // If error2/errorDown2 < error1/errorDown1, we need to subtract one from the bound.
376 // Note that error's are actually baised by -1, we so we have to add one before
377 // we do the comparison.
380 if (IsFractionLessThan(
381 pEdgeRight.Error.get()+1,
382 pEdgeRight.ErrorDown,
383 pEdgeLeft.Error.get()+1,
387 // We can't use the tighter lower bound described above, so we need to subtract one to
388 // ensure we have a lower bound.
390 nSubpixelXDistanceLowerBound -= 1;
393 return nSubpixelXDistanceLowerBound;
395 pub struct CHwRasterizer<'x, 'y, 'z> {
396 m_rcClipBounds: MilPointAndSizeL,
397 m_matWorldToDevice: CMILMatrix,
398 m_pIGeometrySink: &'x mut CHwVertexBufferBuilder<'y, 'z>,
399 m_fillMode: MilFillMode,
401 DynArray<MilPoint2F> *m_prgPoints;
402 DynArray<BYTE> *m_prgTypes;
403 MilPointAndSizeL m_rcClipBounds;
404 CMILMatrix m_matWorldToDevice;
405 IGeometrySink *m_pIGeometrySink;
406 MilFillMode::Enum m_fillMode;
409 // Complex scan coverage buffer
412 CCoverageBuffer m_coverageBuffer;
414 CD3DDeviceLevel1 * m_pDeviceNoRef;*/
415 //m_coverageBuffer: CCoverageBuffer,
418 //-------------------------------------------------------------------------
420 // Function: CHwRasterizer::ConvertSubpixelXToPixel
423 // Convert from our subpixel coordinate (x + error/errorDown)
424 // to a floating point value.
426 //-------------------------------------------------------------------------
427 fn ConvertSubpixelXToPixel(
433 assert!(rErrorDown > f32::EPSILON);
434 return ((x as f32) + (error as f32)/rErrorDown)*c_rInvShiftSize;
437 //-------------------------------------------------------------------------
439 // Function: CHwRasterizer::ConvertSubpixelYToPixel
442 // Convert from our subpixel space to pixel space assuming no
445 //-------------------------------------------------------------------------
446 fn ConvertSubpixelYToPixel(
450 return (nSubpixel as f32)*c_rInvShiftSize;
453 impl<'x, 'y, 'z> CHwRasterizer<'x, 'y, 'z> {
454 //-------------------------------------------------------------------------
456 // Function: CHwRasterizer::RasterizePath
459 // Internal rasterizer fill path. Note that this method follows the
460 // same basic structure as the software rasterizer in aarasterizer.cpp.
462 // The general algorithm used for rasterization is a vertical sweep of
463 // the shape that maintains an active edge list. The sweep is done
464 // at a sub-scanline resolution and results in either:
465 // 1. Sub-scanlines being combined in the coverage buffer and output
466 // as "complex scans".
467 // 2. Simple trapezoids being recognized in the active edge list
468 // and output using a faster simple trapezoid path.
470 // This method consists of the setup to the main rasterization loop
473 // 1. Setup of the clip rectangle
474 // 2. Calling FixedPointPathEnumerate to populate our inactive
476 // 3. Delegating to RasterizePath to execute the main loop.
478 //-------------------------------------------------------------------------
479 pub fn RasterizePath(
484 pmatWorldTransform: &CMILMatrix
488 // Default is not implemented for arrays of size 40 so we need to use map
489 let mut inactiveArrayStack: [CInactiveEdge; INACTIVE_LIST_NUMBER!()] = [(); INACTIVE_LIST_NUMBER!()].map(|_| Default::default());
490 let mut pInactiveArray: &mut [CInactiveEdge];
491 let mut pInactiveArrayAllocation: Vec<CInactiveEdge>;
492 let mut edgeHead: CEdge = Default::default();
493 let mut edgeTail: CEdge = Default::default();
494 let pEdgeActiveList: Ref<CEdge>;
495 let mut edgeStore = Arena::new();
497 let mut edgeContext: CInitializeEdgesContext = CInitializeEdgesContext::new(&mut edgeStore);
499 edgeContext.ClipRect = None;
501 edgeTail.X.set(i32::MAX); // Terminator to active list
502 edgeTail.StartY = i32::MAX; // Terminator to inactive list
504 edgeTail.EndY = i32::MIN;
505 edgeHead.X.set(i32::MIN); // Beginning of active list
506 edgeContext.MaxY = i32::MIN;
508 edgeHead.Next.set(Ref::new(&edgeTail));
509 pEdgeActiveList = Ref::new(&mut edgeHead);
510 //edgeContext.Store = &mut edgeStore;
512 edgeContext.AntiAliasMode = c_antiAliasMode;
513 assert!(edgeContext.AntiAliasMode != MilAntiAliasMode::None);
515 // If the path contains 0 or 1 points, we can ignore it.
521 let nPixelYClipBottom: INT = self.m_rcClipBounds.Y + self.m_rcClipBounds.Height;
523 // Scale the clip bounds rectangle by 16 to account for our
524 // scaling to 28.4 coordinates:
526 let mut clipBounds : RECT = Default::default();
527 clipBounds.left = self.m_rcClipBounds.X * FIX4_ONE!();
528 clipBounds.top = self.m_rcClipBounds.Y * FIX4_ONE!();
529 clipBounds.right = (self.m_rcClipBounds.X + self.m_rcClipBounds.Width) * FIX4_ONE!();
530 clipBounds.bottom = (self.m_rcClipBounds.Y + self.m_rcClipBounds.Height) * FIX4_ONE!();
532 edgeContext.ClipRect = Some(&clipBounds);
534 //////////////////////////////////////////////////////////////////////////
535 // Convert all our points to 28.4 fixed point:
537 let mut matrix: CMILMatrix = (*pmatWorldTransform).clone();
538 AppendScaleToMatrix(&mut matrix, TOREAL!(16), TOREAL!(16));
540 let coverageBuffer: CCoverageBuffer = Default::default();
541 // Initialize the coverage buffer
542 coverageBuffer.Initialize();
544 // Enumerate the path and construct the edge table:
546 hr = MIL_THR!(FixedPointPathEnumerate(
551 edgeContext.ClipRect,
557 if (hr == WGXERR_VALUEOVERFLOW)
559 // Draw nothing on value overflow and return
565 let nTotalCount: UINT; nTotalCount = edgeContext.Store.len() as u32;
566 if (nTotalCount == 0)
568 hr = S_OK; // We're outta here (empty path or entirely clipped)
572 // At this point, there has to be at least two edges. If there's only
573 // one, it means that we didn't do the trivially rejection properly.
575 assert!((nTotalCount >= 2) && (nTotalCount <= (UINT::MAX - 2)));
577 pInactiveArray = &mut inactiveArrayStack[..];
578 if (nTotalCount > (INACTIVE_LIST_NUMBER!() as u32 - 2))
580 pInactiveArrayAllocation = vec![Default::default(); nTotalCount as usize + 2];
582 pInactiveArray = &mut pInactiveArrayAllocation;
585 // Initialize and sort the inactive array:
587 let nSubpixelYCurrent = InitializeInactiveArray(
594 let mut nSubpixelYBottom = edgeContext.MaxY;
596 assert!(nSubpixelYBottom > 0);
598 // Skip the head sentinel on the inactive array:
600 pInactiveArray = &mut pInactiveArray[1..];
603 // Rasterize the path
606 // 'nPixelYClipBottom' is in screen space and needs to be converted to the
607 // format we use for antialiasing.
609 nSubpixelYBottom = nSubpixelYBottom.min(nPixelYClipBottom << c_nShift);
611 // 'nTotalCount' should have been zero if all the edges were
612 // clipped out (RasterizeEdges assumes there's at least one edge
615 assert!(nSubpixelYBottom > nSubpixelYCurrent);
617 IFC!(self.RasterizeEdges(
628 //-------------------------------------------------------------------------
630 // Function: CHwRasterizer::new
633 // 1. Ensure clean state
634 // 2. Convert path to internal format
636 //-------------------------------------------------------------------------
638 pIGeometrySink: &'x mut CHwVertexBufferBuilder<'y, 'z>,
639 fillMode: MilFillMode,
640 pmatWorldToDevice: Option<CMatrix<CoordinateSpace::Shape,CoordinateSpace::Device>>,
641 clipRect: MilPointAndSizeL,
645 // PS#856364-2003/07/01-ashrafm Remove pixel center fixup
647 // Incoming coordinate space uses integers at upper-left of pixel (pixel
648 // center are half integers) at device level.
650 // Rasterizer uses the coordinate space with integers at pixel center.
652 // To convert from center (1/2, 1/2) to center (0, 0) we need to subtract
653 // 1/2 from each coordinate in device space.
655 // See InitializeEdges in aarasterizer.ccp to see how we unconvert for
656 // antialiased rendering.
659 let mut matWorldHPCToDeviceIPC = pmatWorldToDevice.unwrap_or(CMatrix::Identity());
660 matWorldHPCToDeviceIPC.SetDx(matWorldHPCToDeviceIPC.GetDx() - 0.5);
661 matWorldHPCToDeviceIPC.SetDy(matWorldHPCToDeviceIPC.GetDy() - 0.5);
667 // There's an opportunity for early clipping here
669 // However, since the rasterizer itself does a reasonable job of clipping some
670 // cases, we don't early clip yet.
673 m_fillMode: fillMode,
674 m_rcClipBounds: clipRect,
675 m_pIGeometrySink: pIGeometrySink,
676 m_matWorldToDevice: matWorldHPCToDeviceIPC,
680 //-------------------------------------------------------------------------
682 // Function: CHwRasterizer::SendGeometry
685 // Tessellate and send geometry to the pipeline
687 //-------------------------------------------------------------------------
688 pub fn SendGeometry(&mut self,
696 // Rasterize the path
698 let count = points.len() as u32;
699 IFR!(self.RasterizePath(
703 &self.m_matWorldToDevice.clone(),
706 IFC!(self.RasterizePath(
707 self.m_prgPoints.as_ref().unwrap().GetDataBuffer(),
708 self.m_prgTypes.as_ref().unwrap().GetDataBuffer(),
709 self.m_prgPoints.as_ref().unwrap().GetCount() as u32,
710 &self.m_matWorldToDevice,
715 // It's possible that we output no triangles. For example, if we tried to fill a
716 // line instead of stroke it. Since we have no efficient way to detect all these cases
717 // up front, we simply rasterize and see if we generated anything.
720 if (self.m_pIGeometrySink.IsEmpty())
722 hr = WGXHR_EMPTYFILL;
725 RRETURN1!(hr, WGXHR_EMPTYFILL);
728 //-------------------------------------------------------------------------
730 // Function: CHwRasterizer::SendGeometryModifiers
732 // Synopsis: Send an AA color source to the pipeline.
734 //-------------------------------------------------------------------------
735 fn SendGeometryModifiers(&self,
736 pPipelineBuilder: &mut CHwPipelineBuilder
741 let pAntiAliasColorSource = None;
743 self.m_pDeviceNoRef.GetColorComponentSource(
744 CHwColorComponentSource::Diffuse,
745 &pAntiAliasColorSource
748 IFC!(pPipelineBuilder.Set_AAColorSource(
749 pAntiAliasColorSource
755 //-------------------------------------------------------------------------
757 // Function: CHwRasterizer::GenerateOutputAndClearCoverage
760 // Collapse output and generate span data
762 //-------------------------------------------------------------------------
764 GenerateOutputAndClearCoverage<'a>(&mut self, coverageBuffer: &'a CCoverageBuffer<'a>,
769 let nPixelY = nSubpixelY >> c_nShift;
771 let pIntervalSpanStart: Ref<CCoverageInterval> = coverageBuffer.m_pIntervalStart.get();
773 IFC!(self.m_pIGeometrySink.AddComplexScan(nPixelY, pIntervalSpanStart));
775 coverageBuffer.Reset();
780 //-------------------------------------------------------------------------
782 // Function: CHwRasterizer::ComputeTrapezoidsEndScan
785 // This methods takes the current active edge list (and ycurrent)
786 // and will determine:
788 // 1. Can we output some list of simple trapezoids for this active
789 // edge list? If the answer is no, then we simply return
790 // nSubpixelYCurrent indicating this condition.
792 // 2. If we can output some set of trapezoids, then what is the
793 // next ycurrent, i.e., how tall are our trapezoids.
795 // Note that all trapezoids output for a particular active edge list
796 // are all the same height.
798 // To further understand the conditions for making this decision, it
799 // is important to consider the simple trapezoid tessellation:
801 // ___+_________________+___
802 // / + / \ + \ '+' marks active edges
805 // /__+__/___________________\__+__\
808 // Note that 1+1/edge_slope is the required expand distance to ensure
809 // that we cover all pixels required.
811 // Now, we can fail to output any trapezoids under the following conditions:
812 // 1. The expand regions along the top edge of the trapezoid overlap.
813 // 2. The expand regions along the bottom edge of the trapezoid overlap
814 // within the current scanline. Note that if the bottom edges overlap
815 // at some later point, we can shorten our trapezoid to remove the
818 // The key to the algorithm at this point is to detect the above condition
819 // in our active edge list and either update the returned end y position
820 // or reject all together based on overlapping.
822 //-------------------------------------------------------------------------
824 fn ComputeTrapezoidsEndScan(&mut self,
825 pEdgeCurrent: Ref<CEdge>,
826 nSubpixelYCurrent: INT,
827 nSubpixelYNextInactive: INT
831 let mut nSubpixelYBottomTrapezoids;
832 let mut pEdgeLeft: Ref<CEdge>;
833 let mut pEdgeRight: Ref<CEdge>;
836 // Trapezoids should always start at scanline boundaries
839 assert!((nSubpixelYCurrent & c_nShiftMask) == 0);
842 // If we are doing a winding mode fill, check that we can ignore mode and do an
843 // alternating fill in OutputTrapezoids. This condition occurs when winding is
844 // equivalent to alternating which happens if the pairwise edges have different
845 // winding directions.
848 if (self.m_fillMode == MilFillMode::Winding)
850 let mut pEdge = pEdgeCurrent;
851 while pEdge.EndY != INT::MIN {
852 // The active edge list always has an even number of edges which we actually
853 // assert in ASSERTACTIVELIST.
855 assert!(pEdge.Next.get().EndY != INT::MIN);
857 // If not alternating winding direction, we can't fill with alternate mode
859 if (pEdge.WindingDirection == pEdge.Next.get().WindingDirection)
861 // Give up until we handle winding mode
862 nSubpixelYBottomTrapezoids = nSubpixelYCurrent;
863 return nSubpixelYBottomTrapezoids;
866 pEdge = pEdge.Next.get().Next.get();
871 // For each edge, we:
873 // 1. Set the new trapezoid bottom to the min of the current
874 // one and the edge EndY
876 // 2. Check if edges will intersect during trapezoidal shrink/expand
879 nSubpixelYBottomTrapezoids = nSubpixelYNextInactive;
881 let mut pEdge = pEdgeCurrent;
882 while pEdge.EndY != INT::MIN {
886 // Updated nSubpixelYBottomTrapezoids based on edge EndY.
888 // Since edges are clipped to the current clip rect y bounds, we also know
889 // that pEdge->EndY <= nSubpixelYBottom so there is no need to check for that here.
892 nSubpixelYBottomTrapezoids = nSubpixelYBottomTrapezoids.min(pEdge.EndY);
897 // Check that edges will not overlap during trapezoid shrink/expand.
901 pEdgeRight = pEdge.Next.get();
903 if (pEdgeRight.EndY != INT::MIN)
906 // __A__A'___________________B'_B__
907 // \ + \ / + / '+' marks active edges
910 // \__+__\____________/__+__/
913 // We need to determine if position A' <= position B' and that position C' <= position D'
914 // in the above diagram. So, we need to ensure that both the distance between
915 // A and B and the distance between C and D is greater than or equal to:
917 // 0.5 + |0.5/m1| + 0.5 + |0.5/m2| (pixel space)
918 // = shiftsize + halfshiftsize*(|1/m1| + |1/m2|) (subpixel space)
920 // So, we'll start by computing this distance. Note that we can compute a distance
921 // that is too large here since the self-intersection detection is simply used to
922 // recognize trapezoid opportunities and isn't required for visual correctness.
925 let nSubpixelExpandDistanceUpperBound: INT =
927 + ComputeDeltaUpperBound(&*pEdgeLeft, c_nHalfShiftSize)
928 + ComputeDeltaUpperBound(&*pEdgeRight, c_nHalfShiftSize);
931 // Compute a top edge distance that is <= to the distance between A' and B' as follows:
932 // lowerbound(distance(A, B)) - nSubpixelExpandDistanceUpperBound
935 let nSubpixelXTopDistanceLowerBound: INT =
936 ComputeDistanceLowerBound(&*pEdgeLeft, &*pEdgeRight) - nSubpixelExpandDistanceUpperBound;
939 // Check if the top edges cross
942 if (nSubpixelXTopDistanceLowerBound < 0)
944 // The top edges have crossed, so we are out of luck. We can't
945 // start a trapezoid on this scanline
947 nSubpixelYBottomTrapezoids = nSubpixelYCurrent;
948 return nSubpixelYBottomTrapezoids;
952 // If the edges are converging, we need to check if they cross at
953 // nSubpixelYBottomTrapezoids
956 // 1) \ / 2) \ \ 3) / /
960 // The edges converge iff (dx1 > dx2 || (dx1 == dx2 && errorUp1/errorDown1 > errorUp2/errorDown2).
962 // Note that in the case where the edges do not converge, the code below will end up computing
963 // the DDA at the end points and checking for intersection again. This code doesn't rely on
964 // the fact that the edges don't converge, so we can be too conservative here.
967 if (pEdgeLeft.Dx > pEdgeRight.Dx
968 || ((pEdgeLeft.Dx == pEdgeRight.Dx)
969 && IsFractionGreaterThan(pEdgeLeft.ErrorUp, pEdgeLeft.ErrorDown, pEdgeRight.ErrorUp, pEdgeRight.ErrorDown)))
972 let nSubpixelYAdvance: INT = nSubpixelYBottomTrapezoids - nSubpixelYCurrent;
973 assert!(nSubpixelYAdvance > 0);
976 // Compute the edge position at nSubpixelYBottomTrapezoids
979 let mut nSubpixelXLeftAdjustedBottom = 0;
980 let mut nSubpixelErrorLeftBottom = 0;
981 let mut nSubpixelXRightBottom = 0;
982 let mut nSubpixelErrorRightBottom = 0;
984 AdvanceDDAMultipleSteps(
988 &mut nSubpixelXLeftAdjustedBottom,
989 &mut nSubpixelErrorLeftBottom,
990 &mut nSubpixelXRightBottom,
991 &mut nSubpixelErrorRightBottom
995 // Adjust the bottom left position by the expand distance for all the math
996 // that follows. Note that since we adjusted the top distance by that
997 // same expand distance, this adjustment is equivalent to moving the edges
998 // nSubpixelExpandDistanceUpperBound closer together.
1001 nSubpixelXLeftAdjustedBottom += nSubpixelExpandDistanceUpperBound;
1004 // Check if the bottom edge crosses.
1006 // To avoid checking error1/errDown1 and error2/errDown2, we assume the
1007 // edges cross if nSubpixelXLeftAdjustedBottom == nSubpixelXRightBottom
1008 // and thus produce a result that is too conservative.
1011 if (nSubpixelXLeftAdjustedBottom >= nSubpixelXRightBottom)
1015 // At this point, we have the following scenario
1020 // \/ | | nSubpixelYAdvance
1024 // We want to compute h1. We know that:
1026 // h1 / nSubpixelYAdvance = d1 / (d1 + d2)
1027 // h1 = nSubpixelYAdvance * d1 / (d1 + d2)
1029 // Now, if we approximate d1 with some d1' <= d1, we get
1031 // h1 = nSubpixelYAdvance * d1 / (d1 + d2)
1032 // h1 >= nSubpixelYAdvance * d1' / (d1' + d2)
1034 // Similarly, if we approximate d2 with some d2' >= d2, we get
1036 // h1 >= nSubpixelYAdvance * d1' / (d1' + d2)
1037 // >= nSubpixelYAdvance * d1' / (d1' + d2')
1039 // Since we are allowed to be too conservative with h1 (it can be
1040 // less than the actual value), we'll construct such approximations
1043 // Note that d1' = nSubpixelXTopDistanceLowerBound which we have already
1046 // d2 = (x1 + error1/errorDown1) - (x2 + error2/errorDown2)
1047 // = x1 - x2 + error1/errorDown1 - error2/errorDown2
1048 // <= x1 - x2 - error2/errorDown2 , since error1 < 0
1049 // <= x1 - x2 + 1 , since error2 < 0
1050 // = nSubpixelXLeftAdjustedBottom - nSubpixelXRightBottom + 1
1053 let nSubpixelXBottomDistanceUpperBound: INT = nSubpixelXLeftAdjustedBottom - nSubpixelXRightBottom + 1;
1055 assert!(nSubpixelXTopDistanceLowerBound >= 0);
1056 assert!(nSubpixelXBottomDistanceUpperBound > 0);
1058 #[cfg(debug_assertions)]
1059 let nDbgPreviousSubpixelXBottomTrapezoids: INT = nSubpixelYBottomTrapezoids;
1062 nSubpixelYBottomTrapezoids =
1064 (nSubpixelYAdvance * nSubpixelXTopDistanceLowerBound) /
1065 (nSubpixelXTopDistanceLowerBound + nSubpixelXBottomDistanceUpperBound);
1067 #[cfg(debug_assertions)]
1068 assert!(nDbgPreviousSubpixelXBottomTrapezoids >= nSubpixelYBottomTrapezoids);
1070 if (nSubpixelYBottomTrapezoids < nSubpixelYCurrent + c_nShiftSize)
1072 // We no longer have a trapezoid that is at least one scanline high, so
1075 nSubpixelYBottomTrapezoids = nSubpixelYCurrent;
1076 return nSubpixelYBottomTrapezoids;
1082 pEdge = pEdge.Next.get();
1086 // Snap to pixel boundary
1089 nSubpixelYBottomTrapezoids = nSubpixelYBottomTrapezoids & (!c_nShiftMask);
1092 // Ensure that we are never less than nSubpixelYCurrent
1095 assert!(nSubpixelYBottomTrapezoids >= nSubpixelYCurrent);
1098 // Return trapezoid end scan
1102 return nSubpixelYBottomTrapezoids;
1106 //-------------------------------------------------------------------------
1108 // Function: CHwRasterizer::OutputTrapezoids
1111 // Given the current active edge list, output a list of
1114 // _________________________
1118 // /_____/___________________\_____\
1121 // We output a trapezoid where the distance in X is 1+1/m slope on either edge.
1122 // Note that we actually do a linear interpolation for coverage along the
1123 // entire falloff region which comes within 12.5% error when compared to our
1124 // 8x8 coverage output for complex scans. What is happening here is
1125 // that we are applying a linear approximation to the coverage function
1126 // based on slope. It is possible to get better linear interpolations
1127 // by varying the expanded region, but it hasn't been necessary to apply
1128 // these quality improvements yet.
1130 //-------------------------------------------------------------------------
1132 OutputTrapezoids(&mut self,
1133 pEdgeCurrent: Ref<CEdge>,
1134 nSubpixelYCurrent: INT, // inclusive
1135 nSubpixelYNext: INT // exclusive
1140 let nSubpixelYAdvance: INT;
1141 let mut rSubpixelLeftErrorDown: f32;
1142 let mut rSubpixelRightErrorDown: f32;
1143 let mut rPixelXLeft: f32;
1144 let mut rPixelXRight: f32;
1145 let mut rSubpixelLeftInvSlope: f32;
1146 let mut rSubpixelLeftAbsInvSlope: f32;
1147 let mut rSubpixelRightInvSlope: f32;
1148 let mut rSubpixelRightAbsInvSlope: f32;
1149 let mut rPixelXLeftDelta: f32;
1150 let mut rPixelXRightDelta: f32;
1152 let mut pEdgeLeft = pEdgeCurrent;
1153 let mut pEdgeRight = (*pEdgeCurrent).Next.get();
1155 assert!((nSubpixelYCurrent & c_nShiftMask) == 0);
1156 assert!(pEdgeLeft.EndY != INT::MIN);
1157 assert!(pEdgeRight.EndY != INT::MIN);
1160 // Compute the height our trapezoids
1163 nSubpixelYAdvance = nSubpixelYNext - nSubpixelYCurrent;
1166 // Output each trapezoid
1172 // Compute x/error for end of trapezoid
1175 let mut nSubpixelXLeftBottom: INT = 0;
1176 let mut nSubpixelErrorLeftBottom: INT = 0;
1177 let mut nSubpixelXRightBottom: INT = 0;
1178 let mut nSubpixelErrorRightBottom: INT = 0;
1180 AdvanceDDAMultipleSteps(
1184 &mut nSubpixelXLeftBottom,
1185 &mut nSubpixelErrorLeftBottom,
1186 &mut nSubpixelXRightBottom,
1187 &mut nSubpixelErrorRightBottom
1190 // The above computation should ensure that we are a simple
1191 // trapezoid at this point
1193 assert!(nSubpixelXLeftBottom <= nSubpixelXRightBottom);
1195 // We know we have a simple trapezoid now. Now, compute the end of our current trapezoid
1197 assert!(nSubpixelYAdvance > 0);
1200 // Computation of edge data
1203 rSubpixelLeftErrorDown = pEdgeLeft.ErrorDown as f32;
1204 rSubpixelRightErrorDown = pEdgeRight.ErrorDown as f32;
1205 rPixelXLeft = ConvertSubpixelXToPixel(pEdgeLeft.X.get(), pEdgeLeft.Error.get(), rSubpixelLeftErrorDown);
1206 rPixelXRight = ConvertSubpixelXToPixel(pEdgeRight.X.get(), pEdgeRight.Error.get(), rSubpixelRightErrorDown);
1208 rSubpixelLeftInvSlope = pEdgeLeft.Dx as f32 + pEdgeLeft.ErrorUp as f32/rSubpixelLeftErrorDown;
1209 rSubpixelLeftAbsInvSlope = rSubpixelLeftInvSlope.abs();
1210 rSubpixelRightInvSlope = pEdgeRight.Dx as f32 + pEdgeRight.ErrorUp as f32/rSubpixelRightErrorDown;
1211 rSubpixelRightAbsInvSlope = rSubpixelRightInvSlope.abs();
1213 rPixelXLeftDelta = 0.5 + 0.5 * rSubpixelLeftAbsInvSlope;
1214 rPixelXRightDelta = 0.5 + 0.5 * rSubpixelRightAbsInvSlope;
1216 let rPixelYTop = ConvertSubpixelYToPixel(nSubpixelYCurrent);
1217 let rPixelYBottom = ConvertSubpixelYToPixel(nSubpixelYNext);
1219 let rPixelXBottomLeft = ConvertSubpixelXToPixel(
1220 nSubpixelXLeftBottom,
1221 nSubpixelErrorLeftBottom,
1222 pEdgeLeft.ErrorDown as f32
1225 let rPixelXBottomRight = ConvertSubpixelXToPixel(
1226 nSubpixelXRightBottom,
1227 nSubpixelErrorRightBottom,
1228 pEdgeRight.ErrorDown as f32
1232 // Output the trapezoid
1235 IFC!(self.m_pIGeometrySink.AddTrapezoid(
1236 rPixelYTop, // In: y coordinate of top of trapezoid
1237 rPixelXLeft, // In: x coordinate for top left
1238 rPixelXRight, // In: x coordinate for top right
1239 rPixelYBottom, // In: y coordinate of bottom of trapezoid
1240 rPixelXBottomLeft, // In: x coordinate for bottom left
1241 rPixelXBottomRight, // In: x coordinate for bottom right
1242 rPixelXLeftDelta, // In: trapezoid expand radius for left edge
1243 rPixelXRightDelta // In: trapezoid expand radius for right edge
1247 // Update the edge data
1250 // no need to do this if edges are stale
1252 pEdgeLeft.X.set(nSubpixelXLeftBottom);
1253 pEdgeLeft.Error.set(nSubpixelErrorLeftBottom);
1254 pEdgeRight.X.set(nSubpixelXRightBottom);
1255 pEdgeRight.Error.set(nSubpixelErrorRightBottom);
1258 // Check for termination
1261 if (pEdgeRight.Next.get().EndY == INT::MIN)
1267 // Advance edge data
1270 pEdgeLeft = pEdgeRight.Next.get();
1271 pEdgeRight = pEdgeLeft.Next.get();
1279 //-------------------------------------------------------------------------
1281 // Function: CHwRasterizer::RasterizeEdges
1284 // Rasterize using trapezoidal AA
1286 //-------------------------------------------------------------------------
1288 RasterizeEdges<'a, 'b>(&mut self,
1289 pEdgeActiveList: Ref<'a, CEdge<'a>>,
1290 mut pInactiveEdgeArray: &'a mut [CInactiveEdge<'a>],
1291 coverageBuffer: &'b CCoverageBuffer<'b>,
1292 mut nSubpixelYCurrent: INT,
1293 nSubpixelYBottom: INT
1296 let hr: HRESULT = S_OK;
1297 let mut pEdgePrevious: Ref<CEdge>;
1298 let mut pEdgeCurrent: Ref<CEdge>;
1299 let mut nSubpixelYNextInactive: INT = 0;
1300 let mut nSubpixelYNext: INT;
1302 pInactiveEdgeArray = InsertNewEdges(
1306 &mut nSubpixelYNextInactive
1309 while (nSubpixelYCurrent < nSubpixelYBottom)
1311 ASSERTACTIVELIST!(pEdgeActiveList, nSubpixelYCurrent);
1314 // Detect trapezoidal case
1317 pEdgePrevious = pEdgeActiveList;
1318 pEdgeCurrent = pEdgeActiveList.Next.get();
1320 nSubpixelYNext = nSubpixelYCurrent;
1322 if (!IsTagEnabled!(tagDisableTrapezoids)
1323 && (nSubpixelYCurrent & c_nShiftMask) == 0
1324 && pEdgeCurrent.EndY != INT::MIN
1325 && nSubpixelYNextInactive >= nSubpixelYCurrent + c_nShiftSize
1328 // Edges are paired, so we can assert we have another one
1329 assert!(pEdgeCurrent.Next.get().EndY != INT::MIN);
1332 // Given an active edge list, we compute the furthest we can go in the y direction
1333 // without creating self-intersection or going past the edge EndY. Note that if we
1334 // can't even go one scanline, then nSubpixelYNext == nSubpixelYCurrent
1337 nSubpixelYNext = self.ComputeTrapezoidsEndScan(Ref::new(&*pEdgeCurrent), nSubpixelYCurrent, nSubpixelYNextInactive);
1338 assert!(nSubpixelYNext >= nSubpixelYCurrent);
1341 // Attempt to output a trapezoid. If it turns out we don't have any
1342 // potential trapezoids, then nSubpixelYNext == nSubpixelYCurent
1343 // indicating that we need to fall back to complex scans.
1346 if (nSubpixelYNext >= nSubpixelYCurrent + c_nShiftSize)
1348 IFC!(self.OutputTrapezoids(
1357 // Rasterize simple trapezoid or a complex scanline
1360 if (nSubpixelYNext > nSubpixelYCurrent)
1362 // If we advance, it must be by at least one scan line
1364 assert!(nSubpixelYNext - nSubpixelYCurrent >= c_nShiftSize);
1366 // Advance nSubpixelYCurrent
1368 nSubpixelYCurrent = nSubpixelYNext;
1370 // Remove stale edges. Note that the DDA is incremented in OutputTrapezoids.
1372 while (pEdgeCurrent.EndY != INT::MIN)
1374 if (pEdgeCurrent.EndY <= nSubpixelYCurrent)
1376 // Unlink and advance
1378 pEdgeCurrent = pEdgeCurrent.Next.get();
1379 pEdgePrevious.Next.set(pEdgeCurrent);
1385 pEdgePrevious = pEdgeCurrent;
1386 pEdgeCurrent = pEdgeCurrent.Next.get();
1393 // Trapezoid rasterization failed, so
1394 // 1) Handle case with no active edges, or
1395 // 2) fall back to scan rasterization
1398 if (pEdgeCurrent.EndY == INT::MIN)
1400 nSubpixelYNext = nSubpixelYNextInactive;
1404 nSubpixelYNext = nSubpixelYCurrent + 1;
1405 if (self.m_fillMode == MilFillMode::Alternate)
1407 IFC!(coverageBuffer.FillEdgesAlternating(pEdgeActiveList, nSubpixelYCurrent));
1411 IFC!(coverageBuffer.FillEdgesWinding(pEdgeActiveList, nSubpixelYCurrent));
1415 // If the next scan is done, output what's there:
1416 if (nSubpixelYNext > (nSubpixelYCurrent | c_nShiftMask))
1418 IFC!(self.GenerateOutputAndClearCoverage(coverageBuffer, nSubpixelYCurrent));
1421 // Advance nSubpixelYCurrent
1422 nSubpixelYCurrent = nSubpixelYNext;
1424 // Advance DDA and update edge list
1425 AdvanceDDAAndUpdateActiveEdgeList(nSubpixelYCurrent, pEdgeActiveList);
1432 if (nSubpixelYCurrent == nSubpixelYNextInactive)
1434 pInactiveEdgeArray = InsertNewEdges(
1438 &mut nSubpixelYNextInactive
1444 // Output the last scanline that has partial coverage
1447 if ((nSubpixelYCurrent & c_nShiftMask) != 0)
1449 IFC!(self.GenerateOutputAndClearCoverage(coverageBuffer, nSubpixelYCurrent));