# scan line algorithm is too slow?

This is my code of the algorithm for making triangles :-

private void sort(){
int temp = Math.round(m_Vertex1.getPosition().getX());
int temp2 = Math.round(m_Vertex2.getPosition().getX());
int temp3 = Math.round(m_Vertex3.getPosition().getX());

m_minX = Math.min(temp3, Math.min(temp, temp2));    //Sorting the X values
m_maxX = Math.max(temp3, Math.max(temp, temp2));

temp = Math.round(m_Vertex1.getPosition().getY());
temp2 = Math.round(m_Vertex2.getPosition().getY());
temp3 = Math.round(m_Vertex3.getPosition().getY());

m_minY = Math.min(temp3, Math.min(temp, temp2));    // Sorting the Y values
m_maxY = Math.max(temp3, Math.max(temp, temp2));
}

public void DrawTriangle(){
new Line(m_Vertex1, m_Vertex2, m_display).DrawLine(Optional.of(EdgeOnePoints));     //Getting all the points on the boundary of the triangle
new Line(m_Vertex2, m_Vertex3, m_display).DrawLine(Optional.of(EdgeTwoPoints));
new Line(m_Vertex1, m_Vertex3, m_display).DrawLine(Optional.of(EdgeThreePoints));

Vector2D start = Vector2D.zero();
Vector2D end = Vector2D.zero();

for(float i = m_minY; i <= m_maxY ;i++){        //Iterating from top to bottom of the triangle

for(float j = m_minX; j <= m_maxX; j++){    //Iterating left to right of the triangle
Vector2D temp = new Vector2D(j,i);

if(EdgeOnePoints.contains(temp) || EdgeTwoPoints.contains(temp) || EdgeThreePoints.contains(temp)){
if(start.equals(Vector2D.zero())){      // Getting the first point of intersection between the triangle and the scanline
start = temp;
}else{
if(EdgeOnePoints.contains(start) && !EdgeOnePoints.contains(temp)){     // Checking if start point and end point are on the same edge or not, if not then it is a valid point else not.
end = temp;
break;
}else if(EdgeTwoPoints.contains(start) && !EdgeTwoPoints.contains(temp)){
end = temp;
break;
}else if(EdgeThreePoints.contains(start) && !EdgeThreePoints.contains(temp)){
end = temp;
break;
}
}
}
}

if(!start.equals(Vector2D.zero()) && !end.equals(Vector2D.zero())){ //if both start and end points are available then draw then fill all the points in between them.
for(float j = start.getX(); j <= end.getX(); j++){
new Point(new Vector2D(j, i), PixelData.white(), m_display).DrawPoint();
}
}

start = Vector2D.zero();
end = Vector2D.zero();
}
}


Now i have couple of problems with it :-

1. It is a tortoise, i have tested it on a old machine and just with 2 rotating triangles, the frame rate is below 30.

2. i get this weird line in between the triangle at some specific position when rotating the triangle.

I don't care much about the second problem but can anyone help me making this algorithm fast. should i use something like flood fill or boundary fill algorithm ?

• Are you writing a rasterizer in Java? – Syntac_ Jun 9 '16 at 8:48
• @Syntac_ Yes the language is Java. – A---B Jun 9 '16 at 9:06

## 1 Answer

One red flag is the use of new several times within the loop. Memory allocation doesn't belong in a rasterizer! :) Certainly you should not need to allocate a Point object (which is used once and then immediately discarded) and do a method call on it, just in order to fill a single pixel! The pixels are hopefully stored as a flat array of bytes, so just write directly to the appropriate address in it. Similarly, don't allocate a Vector2D every time through, just create one (ideally on the stack, if the language you're using allows for it), and re-use it.

Secondly, the algorithm you're using doesn't seem to be a true scanline rasterizer. It iterates over the pixels in each line from left to right, performing edge tests on every single pixel to determine whether it's inside or outside, and recording when that state changes in the start and end variables.

The way a scanline rasterizer is supposed to work (which is much faster) is to calculate the intersection points of each edge with the scanline (using good old school algebra line-line intersection math). Ideally you would have already categorized and sorted the three edges as left, right, or horizontal and therefore once you have the intersection points, it's easy to figure out the interval that the triangle covers on the scanline. Then you can iterate over that and shade or fill each pixel.

Finally, I'm not sure if this is a real issue or not, but there are a lot of method calls for relatively trivial things like checking whether vectors are equal, or doing an edge-vs-point test. Hopefully the compiler is inlining all those, but you might want to check the generated code to see. If it's not, you could see a fair speedup by manually inlining that stuff, and possibly manually "destructuring" the vectors (i.e. replace a Vector2D variable by two explicit x and y variables).

• re new, it looks more like c#, not c++, though OP has not explicitly specified. – Rotem Jun 9 '16 at 8:17
• Actually looks more like Java. – Rotem Jun 9 '16 at 8:27
• @Rotem I don't think there is any way of knowing the language except when i tell that it is Java. – A---B Jun 9 '16 at 9:06
• @ritwik In c# the Math methods are capitalized, e.g. Round(), not round(). – Rotem Jun 9 '16 at 9:08
• @Rotem ok that's legit. – A---B Jun 9 '16 at 9:09