diff options
Diffstat (limited to 'Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/polygon.go')
| -rw-r--r-- | Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/polygon.go | 581 |
1 files changed, 581 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/polygon.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/polygon.go new file mode 100644 index 000000000..2a19e7355 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/polygon.go @@ -0,0 +1,581 @@ +// Copyright 2011 The draw2d Authors. All rights reserved. +// created: 27/05/2011 by Laurent Le Goff +package raster + +const ( + POLYGON_CLIP_NONE = iota + POLYGON_CLIP_LEFT + POLYGON_CLIP_RIGHT + POLYGON_CLIP_TOP + POLYGON_CLIP_BOTTOM +) + +type Polygon []float64 + +type PolygonEdge struct { + X, Slope float64 + FirstLine, LastLine int + Winding int16 +} + +//! A more optimized representation of a polygon edge. +type PolygonScanEdge struct { + FirstLine, LastLine int + Winding int16 + X Fix + Slope Fix + SlopeFix Fix + NextEdge *PolygonScanEdge +} + +//! Calculates the edges of the polygon with transformation and clipping to edges array. +/*! \param startIndex the index for the first vertex. + * \param vertexCount the amount of vertices to convert. + * \param edges the array for result edges. This should be able to contain 2*aVertexCount edges. + * \param tr the transformation matrix for the polygon. + * \param aClipRectangle the clip rectangle. + * \return the amount of edges in the result. + */ +func (p Polygon) getEdges(startIndex, vertexCount int, edges []PolygonEdge, tr [6]float64, clipBound [4]float64) int { + startIndex = startIndex * 2 + endIndex := startIndex + vertexCount*2 + if endIndex > len(p) { + endIndex = len(p) + } + + x := p[startIndex] + y := p[startIndex+1] + // inline transformation + prevX := x*tr[0] + y*tr[2] + tr[4] + prevY := x*tr[1] + y*tr[3] + tr[5] + + //! Calculates the clip flags for a point. + prevClipFlags := POLYGON_CLIP_NONE + if prevX < clipBound[0] { + prevClipFlags |= POLYGON_CLIP_LEFT + } else if prevX >= clipBound[2] { + prevClipFlags |= POLYGON_CLIP_RIGHT + } + + if prevY < clipBound[1] { + prevClipFlags |= POLYGON_CLIP_TOP + } else if prevY >= clipBound[3] { + prevClipFlags |= POLYGON_CLIP_BOTTOM + } + + edgeCount := 0 + var k, clipFlags, clipSum, clipUnion int + var xleft, yleft, xright, yright, oldY, maxX, minX float64 + var swapWinding int16 + for n := startIndex; n < endIndex; n = n + 2 { + k = (n + 2) % len(p) + x = p[k]*tr[0] + p[k+1]*tr[2] + tr[4] + y = p[k]*tr[1] + p[k+1]*tr[3] + tr[5] + + //! Calculates the clip flags for a point. + clipFlags = POLYGON_CLIP_NONE + if prevX < clipBound[0] { + clipFlags |= POLYGON_CLIP_LEFT + } else if prevX >= clipBound[2] { + clipFlags |= POLYGON_CLIP_RIGHT + } + if prevY < clipBound[1] { + clipFlags |= POLYGON_CLIP_TOP + } else if prevY >= clipBound[3] { + clipFlags |= POLYGON_CLIP_BOTTOM + } + + clipSum = prevClipFlags | clipFlags + clipUnion = prevClipFlags & clipFlags + + // Skip all edges that are either completely outside at the top or at the bottom. + if clipUnion&(POLYGON_CLIP_TOP|POLYGON_CLIP_BOTTOM) == 0 { + if clipUnion&POLYGON_CLIP_RIGHT != 0 { + // Both clip to right, edge is a vertical line on the right side + if getVerticalEdge(prevY, y, clipBound[2], &edges[edgeCount], clipBound) { + edgeCount++ + } + } else if clipUnion&POLYGON_CLIP_LEFT != 0 { + // Both clip to left, edge is a vertical line on the left side + if getVerticalEdge(prevY, y, clipBound[0], &edges[edgeCount], clipBound) { + edgeCount++ + } + } else if clipSum&(POLYGON_CLIP_RIGHT|POLYGON_CLIP_LEFT) == 0 { + // No clipping in the horizontal direction + if getEdge(prevX, prevY, x, y, &edges[edgeCount], clipBound) { + edgeCount++ + } + } else { + // Clips to left or right or both. + + if x < prevX { + xleft, yleft = x, y + xright, yright = prevX, prevY + swapWinding = -1 + } else { + xleft, yleft = prevX, prevY + xright, yright = x, y + swapWinding = 1 + } + + slope := (yright - yleft) / (xright - xleft) + + if clipSum&POLYGON_CLIP_RIGHT != 0 { + // calculate new position for the right vertex + oldY = yright + maxX = clipBound[2] + + yright = yleft + (maxX-xleft)*slope + xright = maxX + + // add vertical edge for the overflowing part + if getVerticalEdge(yright, oldY, maxX, &edges[edgeCount], clipBound) { + edges[edgeCount].Winding *= swapWinding + edgeCount++ + } + } + + if clipSum&POLYGON_CLIP_LEFT != 0 { + // calculate new position for the left vertex + oldY = yleft + minX = clipBound[0] + + yleft = yleft + (minX-xleft)*slope + xleft = minX + + // add vertical edge for the overflowing part + if getVerticalEdge(oldY, yleft, minX, &edges[edgeCount], clipBound) { + edges[edgeCount].Winding *= swapWinding + edgeCount++ + } + } + + if getEdge(xleft, yleft, xright, yright, &edges[edgeCount], clipBound) { + edges[edgeCount].Winding *= swapWinding + edgeCount++ + } + } + } + + prevClipFlags = clipFlags + prevX = x + prevY = y + } + + return edgeCount +} + +//! Creates a polygon edge between two vectors. +/*! Clips the edge vertically to the clip rectangle. Returns true for edges that + * should be rendered, false for others. + */ +func getEdge(x0, y0, x1, y1 float64, edge *PolygonEdge, clipBound [4]float64) bool { + var startX, startY, endX, endY float64 + var winding int16 + + if y0 <= y1 { + startX = x0 + startY = y0 + endX = x1 + endY = y1 + winding = 1 + } else { + startX = x1 + startY = y1 + endX = x0 + endY = y0 + winding = -1 + } + + // Essentially, firstLine is floor(startY + 1) and lastLine is floor(endY). + // These are refactored to integer casts in order to avoid function + // calls. The difference with integer cast is that numbers are always + // rounded towards zero. Since values smaller than zero get clipped away, + // only coordinates between 0 and -1 require greater attention as they + // also round to zero. The problems in this range can be avoided by + // adding one to the values before conversion and subtracting after it. + + firstLine := int(startY + 1) + lastLine := int(endY+1) - 1 + + minClip := int(clipBound[1]) + maxClip := int(clipBound[3]) + + // If start and end are on the same line, the edge doesn't cross + // any lines and thus can be ignored. + // If the end is smaller than the first line, edge is out. + // If the start is larger than the last line, edge is out. + if firstLine > lastLine || lastLine < minClip || firstLine >= maxClip { + return false + } + + // Adjust the start based on the target. + if firstLine < minClip { + firstLine = minClip + } + + if lastLine >= maxClip { + lastLine = maxClip - 1 + } + edge.Slope = (endX - startX) / (endY - startY) + edge.X = startX + (float64(firstLine)-startY)*edge.Slope + edge.Winding = winding + edge.FirstLine = firstLine + edge.LastLine = lastLine + + return true +} + +//! Creates a vertical polygon edge between two y values. +/*! Clips the edge vertically to the clip rectangle. Returns true for edges that + * should be rendered, false for others. + */ +func getVerticalEdge(startY, endY, x float64, edge *PolygonEdge, clipBound [4]float64) bool { + var start, end float64 + var winding int16 + if startY < endY { + start = startY + end = endY + winding = 1 + } else { + start = endY + end = startY + winding = -1 + } + + firstLine := int(start + 1) + lastLine := int(end+1) - 1 + + minClip := int(clipBound[1]) + maxClip := int(clipBound[3]) + + // If start and end are on the same line, the edge doesn't cross + // any lines and thus can be ignored. + // If the end is smaller than the first line, edge is out. + // If the start is larger than the last line, edge is out. + if firstLine > lastLine || lastLine < minClip || firstLine >= maxClip { + return false + } + + // Adjust the start based on the clip rect. + if firstLine < minClip { + firstLine = minClip + } + if lastLine >= maxClip { + lastLine = maxClip - 1 + } + + edge.Slope = 0 + edge.X = x + edge.Winding = winding + edge.FirstLine = firstLine + edge.LastLine = lastLine + + return true +} + +type VertexData struct { + X, Y float64 + ClipFlags int + Line int +} + +//! Calculates the edges of the polygon with transformation and clipping to edges array. +/*! Note that this may return upto three times the amount of edges that the polygon has vertices, + * in the unlucky case where both left and right side get clipped for all edges. + * \param edges the array for result edges. This should be able to contain 2*aVertexCount edges. + * \param aTransformation the transformation matrix for the polygon. + * \param aClipRectangle the clip rectangle. + * \return the amount of edges in the result. + */ +func (p Polygon) getScanEdges(edges []PolygonScanEdge, tr [6]float64, clipBound [4]float64) int { + var n int + vertexData := make([]VertexData, len(p)/2+1) + for n = 0; n < len(vertexData)-1; n = n + 1 { + k := n * 2 + vertexData[n].X = p[k]*tr[0] + p[k+1]*tr[2] + tr[4] + vertexData[n].Y = p[k]*tr[1] + p[k+1]*tr[3] + tr[5] + // Calculate clip flags for all vertices. + vertexData[n].ClipFlags = POLYGON_CLIP_NONE + if vertexData[n].X < clipBound[0] { + vertexData[n].ClipFlags |= POLYGON_CLIP_LEFT + } else if vertexData[n].X >= clipBound[2] { + vertexData[n].ClipFlags |= POLYGON_CLIP_RIGHT + } + if vertexData[n].Y < clipBound[1] { + vertexData[n].ClipFlags |= POLYGON_CLIP_TOP + } else if vertexData[n].Y >= clipBound[3] { + vertexData[n].ClipFlags |= POLYGON_CLIP_BOTTOM + } + + // Calculate line of the vertex. If the vertex is clipped by top or bottom, the line + // is determined by the clip rectangle. + if vertexData[n].ClipFlags&POLYGON_CLIP_TOP != 0 { + vertexData[n].Line = int(clipBound[1]) + } else if vertexData[n].ClipFlags&POLYGON_CLIP_BOTTOM != 0 { + vertexData[n].Line = int(clipBound[3] - 1) + } else { + vertexData[n].Line = int(vertexData[n].Y+1) - 1 + } + } + + // Copy the data from 0 to the last entry to make the data to loop. + vertexData[len(vertexData)-1] = vertexData[0] + + // Transform the first vertex; store. + // Process mVertexCount - 1 times, next is n+1 + // copy the first vertex to + // Process 1 time, next is n + + edgeCount := 0 + for n = 0; n < len(vertexData)-1; n++ { + clipSum := vertexData[n].ClipFlags | vertexData[n+1].ClipFlags + clipUnion := vertexData[n].ClipFlags & vertexData[n+1].ClipFlags + + if clipUnion&(POLYGON_CLIP_TOP|POLYGON_CLIP_BOTTOM) == 0 && + vertexData[n].Line != vertexData[n+1].Line { + var startIndex, endIndex int + var winding int16 + if vertexData[n].Y < vertexData[n+1].Y { + startIndex = n + endIndex = n + 1 + winding = 1 + } else { + startIndex = n + 1 + endIndex = n + winding = -1 + } + + firstLine := vertexData[startIndex].Line + 1 + lastLine := vertexData[endIndex].Line + + if clipUnion&POLYGON_CLIP_RIGHT != 0 { + // Both clip to right, edge is a vertical line on the right side + edges[edgeCount].FirstLine = firstLine + edges[edgeCount].LastLine = lastLine + edges[edgeCount].Winding = winding + edges[edgeCount].X = Fix(clipBound[2] * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = 0 + edges[edgeCount].SlopeFix = 0 + + edgeCount++ + } else if clipUnion&POLYGON_CLIP_LEFT != 0 { + // Both clip to left, edge is a vertical line on the left side + edges[edgeCount].FirstLine = firstLine + edges[edgeCount].LastLine = lastLine + edges[edgeCount].Winding = winding + edges[edgeCount].X = Fix(clipBound[0] * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = 0 + edges[edgeCount].SlopeFix = 0 + + edgeCount++ + } else if clipSum&(POLYGON_CLIP_RIGHT|POLYGON_CLIP_LEFT) == 0 { + // No clipping in the horizontal direction + slope := (vertexData[endIndex].X - + vertexData[startIndex].X) / + (vertexData[endIndex].Y - + vertexData[startIndex].Y) + + // If there is vertical clip (for the top) it will be processed here. The calculation + // should be done for all non-clipping edges as well to determine the accurate position + // where the edge crosses the first scanline. + startx := vertexData[startIndex].X + + (float64(firstLine)-vertexData[startIndex].Y)*slope + + edges[edgeCount].FirstLine = firstLine + edges[edgeCount].LastLine = lastLine + edges[edgeCount].Winding = winding + edges[edgeCount].X = Fix(startx * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = Fix(slope * FIXED_FLOAT_COEF) + + if lastLine-firstLine >= SLOPE_FIX_STEP { + edges[edgeCount].SlopeFix = Fix(slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - + edges[edgeCount].Slope<<SLOPE_FIX_SHIFT + } else { + edges[edgeCount].SlopeFix = 0 + } + + edgeCount++ + } else { + // Clips to left or right or both. + slope := (vertexData[endIndex].X - + vertexData[startIndex].X) / + (vertexData[endIndex].Y - + vertexData[startIndex].Y) + + // The edge may clip to both left and right. + // The clip results in one or two new vertices, and one to three segments. + // The rounding for scanlines may produce a result where any of the segments is + // ignored. + + // The start is always above the end. Calculate the clip positions to clipVertices. + // It is possible that only one of the vertices exist. This will be detected from the + // clip flags of the vertex later, so they are initialized here. + var clipVertices [2]VertexData + + if vertexData[startIndex].X < + vertexData[endIndex].X { + clipVertices[0].X = clipBound[0] + clipVertices[1].X = clipBound[2] + clipVertices[0].ClipFlags = POLYGON_CLIP_LEFT + clipVertices[1].ClipFlags = POLYGON_CLIP_RIGHT + } else { + clipVertices[0].X = clipBound[2] + clipVertices[1].X = clipBound[0] + clipVertices[0].ClipFlags = POLYGON_CLIP_RIGHT + clipVertices[1].ClipFlags = POLYGON_CLIP_LEFT + } + + var p int + for p = 0; p < 2; p++ { + // Check if either of the vertices crosses the edge marked for the clip vertex + if clipSum&clipVertices[p].ClipFlags != 0 { + // The the vertex is required, calculate it. + clipVertices[p].Y = vertexData[startIndex].Y + + (clipVertices[p].X- + vertexData[startIndex].X)/slope + + // If there is clipping in the vertical direction, the new vertex may be clipped. + if clipSum&(POLYGON_CLIP_TOP|POLYGON_CLIP_BOTTOM) != 0 { + if clipVertices[p].Y < clipBound[1] { + clipVertices[p].ClipFlags = POLYGON_CLIP_TOP + clipVertices[p].Line = int(clipBound[1]) + } else if clipVertices[p].Y > clipBound[3] { + clipVertices[p].ClipFlags = POLYGON_CLIP_BOTTOM + clipVertices[p].Line = int(clipBound[3] - 1) + } else { + clipVertices[p].ClipFlags = 0 + clipVertices[p].Line = int(clipVertices[p].Y+1) - 1 + } + } else { + clipVertices[p].ClipFlags = 0 + clipVertices[p].Line = int(clipVertices[p].Y+1) - 1 + } + } + } + + // Now there are three or four vertices, in the top-to-bottom order of start, clip0, clip1, + // end. What kind of edges are required for connecting these can be determined from the + // clip flags. + // -if clip vertex has horizontal clip flags, it doesn't exist. No edge is generated. + // -if start vertex or end vertex has horizontal clip flag, the edge to/from the clip vertex is vertical + // -if the line of two vertices is the same, the edge is not generated, since the edge doesn't + // cross any scanlines. + + // The alternative patterns are: + // start - clip0 - clip1 - end + // start - clip0 - end + // start - clip1 - end + + var topClipIndex, bottomClipIndex int + if (clipVertices[0].ClipFlags|clipVertices[1].ClipFlags)& + (POLYGON_CLIP_LEFT|POLYGON_CLIP_RIGHT) == 0 { + // Both sides are clipped, the order is start-clip0-clip1-end + topClipIndex = 0 + bottomClipIndex = 1 + + // Add the edge from clip0 to clip1 + // Check that the line is different for the vertices. + if clipVertices[0].Line != clipVertices[1].Line { + firstClipLine := clipVertices[0].Line + 1 + + startx := vertexData[startIndex].X + + (float64(firstClipLine)-vertexData[startIndex].Y)*slope + + edges[edgeCount].X = Fix(startx * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = Fix(slope * FIXED_FLOAT_COEF) + edges[edgeCount].FirstLine = firstClipLine + edges[edgeCount].LastLine = clipVertices[1].Line + edges[edgeCount].Winding = winding + + if edges[edgeCount].LastLine-edges[edgeCount].FirstLine >= SLOPE_FIX_STEP { + edges[edgeCount].SlopeFix = Fix(slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - + edges[edgeCount].Slope<<SLOPE_FIX_SHIFT + } else { + edges[edgeCount].SlopeFix = 0 + } + + edgeCount++ + } + } else { + // Clip at either side, check which side. The clip flag is on for the vertex + // that doesn't exist, i.e. has not been clipped to be inside the rect. + if clipVertices[0].ClipFlags&(POLYGON_CLIP_LEFT|POLYGON_CLIP_RIGHT) != 0 { + topClipIndex = 1 + bottomClipIndex = 1 + } else { + topClipIndex = 0 + bottomClipIndex = 0 + } + } + + // Generate the edges from start - clip top and clip bottom - end + // Clip top and clip bottom may be the same vertex if there is only one + // clipped vertex. + + // Check that the line is different for the vertices. + if vertexData[startIndex].Line != clipVertices[topClipIndex].Line { + edges[edgeCount].FirstLine = firstLine + edges[edgeCount].LastLine = clipVertices[topClipIndex].Line + edges[edgeCount].Winding = winding + + // If startIndex is clipped, the edge is a vertical one. + if vertexData[startIndex].ClipFlags&(POLYGON_CLIP_LEFT|POLYGON_CLIP_RIGHT) != 0 { + edges[edgeCount].X = Fix(clipVertices[topClipIndex].X * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = 0 + edges[edgeCount].SlopeFix = 0 + } else { + startx := vertexData[startIndex].X + + (float64(firstLine)-vertexData[startIndex].Y)*slope + + edges[edgeCount].X = Fix(startx * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = Fix(slope * FIXED_FLOAT_COEF) + + if edges[edgeCount].LastLine-edges[edgeCount].FirstLine >= SLOPE_FIX_STEP { + edges[edgeCount].SlopeFix = Fix(slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - + edges[edgeCount].Slope<<SLOPE_FIX_SHIFT + } else { + edges[edgeCount].SlopeFix = 0 + } + } + + edgeCount++ + } + + // Check that the line is different for the vertices. + if clipVertices[bottomClipIndex].Line != vertexData[endIndex].Line { + firstClipLine := clipVertices[bottomClipIndex].Line + 1 + + edges[edgeCount].FirstLine = firstClipLine + edges[edgeCount].LastLine = lastLine + edges[edgeCount].Winding = winding + + // If endIndex is clipped, the edge is a vertical one. + if vertexData[endIndex].ClipFlags&(POLYGON_CLIP_LEFT|POLYGON_CLIP_RIGHT) != 0 { + edges[edgeCount].X = Fix(clipVertices[bottomClipIndex].X * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = 0 + edges[edgeCount].SlopeFix = 0 + } else { + startx := vertexData[startIndex].X + + (float64(firstClipLine)-vertexData[startIndex].Y)*slope + + edges[edgeCount].X = Fix(startx * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = Fix(slope * FIXED_FLOAT_COEF) + + if edges[edgeCount].LastLine-edges[edgeCount].FirstLine >= SLOPE_FIX_STEP { + edges[edgeCount].SlopeFix = Fix(slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - + edges[edgeCount].Slope<<SLOPE_FIX_SHIFT + } else { + edges[edgeCount].SlopeFix = 0 + } + } + + edgeCount++ + } + + } + } + } + + return edgeCount +} |