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, 0 insertions, 581 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 deleted file mode 100644 index 2a19e7355..000000000 --- a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/polygon.go +++ /dev/null @@ -1,581 +0,0 @@ -// 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 -} |