# Scanconversion problem.

This topic is 3450 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello All, I'm currently in the process of creating a software 3D renderer for the benifit of my learning more then anything. I'm up to the stage where I'm trying to scanconvert my projected triangles, the scan converter doesn't seem to work on some polys, however if I rotate the mesh 180 degrees these polys get drawn and the ones that were getting drawn before the rotate don't. I'm wondering if there something missing from the books I have been reading on the subject of scan-conversion, I have modified with the order in which the scan converter accesses the vectors to go backwards, there's some improvement, should the order of the vectors in a triangle matter to the scan-converter? Thanks in advance.

##### Share on other sites
Yes it can matter.. usually you always begin with the topmost point, and then draw each row of pixels in the triangle until you reach the bottom point. Unless you're already doing that and I misunderstand your question.. =)
You can loop through all your points, checking which one is the topmost, and set that point as index 0, and keep the other points in order after. If you have points 0 1 2 3 4, and point 3 is at the top, the new order is 3 4 0 1 2.

##### Share on other sites
So re-order the points so the top most is first, cool, I'll give that a go now and let you know how it goes :)

##### Share on other sites
It's improved it by 50 percent, but there's still a lot of polygons not showing.

##### Share on other sites
How is it failing?
I think you need to show screenshots and code to identify your problem.. how exactly are you drawing the polygon?
If you start at the top vertex, you should trace the polygon in opposite directions along it's edges, counter-clockwise and clockwise. You trace each direction until you hit a point that is exactly in the vertical center of a pixel. When you do, the counter-clockwise trace is the 'left' point, and the clockwise trace is 'right'. You then draw one scanline between these 2 points. After that you continue tracing, and do the same at the next pixel center. When the two traces meet, you are done.

##### Share on other sites
http://s459.photobucket.com/albums/qq319/y_s_wheeler/?action=view¤t=faultyTeapot.jpg

Here you go, the red wireframe parts are where the scan converter hasn't even bothered. The black (empty) ones with no wireframe are where it might have just attempted one scan.

#include "scanConvert.h"#include "LIMITS.h"#include <stdlib.h>int top = 0;int bottom = 0;int scansCount = 0;// Constraintsint minX = 0;int maxX = 0;int minY = 0;int maxY = 0;Scan *scans;ViewWindow *view;int getTop(){	return top;}int getBottom(){	return bottom;}void setViewWindow(ViewWindow *v){	view = v;}void resetScan(Scan *scan){	scan->left = INT_MAX;	scan->right = INT_MIN;}Scan* getScan(int i){	return scans+i;}void clearScans() {	for (int i=top; i<=bottom; i++) {		resetScan(scans + i);	}	top = INT_MAX;	bottom = INT_MIN;}void setBoundary(int x, Scan *scan) {	if (x < scan->left) {		scan->left = x;	}	if (x-1 > scan->right) {		scan->right = x-1;	}}bool validate(Scan *scan) {	return scan->left <= scan->right;}void makeScansArray() {	int height = view->bounds.height + view->bounds.y;	if (scans == (Scan*)0) //null	{		scans = (Scan*) malloc(height * sizeof(Scan));		scansCount = height;		top = 0;		bottom = height - 1;	}else if(scansCount != height) {		free(scans);		scans = (Scan*) malloc(height * sizeof(Scan));		scansCount = height;		top = 0;		bottom = height - 1;	}	minX = view->bounds.x;	maxX = minX + view->bounds.width - 1;	minY = view->bounds.y;	maxY = minY + view->bounds.height - 1;}bool convert(Poly *poly){	makeScansArray();	clearScans();	top = max(minY, ceil(min(poly->v1.y, poly->v2.y, poly->v3.y))); //yMin of tri;	bottom = min(maxY, floor(max(poly->v1.y, poly->v2.y, poly->v3.y))); //yMax of tri;	Vector *vectors[] = {&poly->v1, &poly->v2, &poly->v3, &poly->v1};	// Suggestion from a form, re-orders, top first	//int i = 0;	//int j = 0;	//float count = INT_MAX;	//while(i<3)	//{	//	if(vectors->y < count){	//		count = vectors->y;	//		j = i;	//	}	//	i++;	//}	//i = 0;	//while(i<j)	//{	//	vectors[0] = vectors[1];	//	vectors[1] = vectors[2];	//	vectors[2] = vectors[3];	//	vectors[3] = vectors[0];	//	i++;	//}	for (int i=0; i<3; i++) {		Vector *v1 = vectors;		Vector *v2 = vectors[i+1];		// ensure v1.y < v2.y		if (v1->y > v2->y) {			Vector temp;			copyVector(v1, &temp);			copyVector(v2, v1);			copyVector(&temp, v2);		}		float dy = v2->y - v1->y;		if(dy==0) // Line is horizontal, No intersection, puesdo code says <0.5 but I think it should be ==0		{			continue;		}		float dx = v2->x - v1->x;		int y = top;		while(y<=bottom)		{			if((v1->y < y && v2->y < y) ||(v1->y > y && v2->y > y))			{				y++;				continue; // No intersection			}			float d = ((y - v1->y)*dx)/dy;			setBoundary(v1->x + d, scans + y);			y++;		}	}	// check if visible (any valid scans)	for (int i=top; i<=bottom; i++) {		if (validate(scans+i)) {			return true;		}	}	return false;}

##### Share on other sites
Quote:
 Original post by DarkMatter2008 for (int i=0; i<3; i++) { Vector *v1 = vectors; Vector *v2 = vectors[i+1];

Are you sure that's correct?
It seems as though i+1 goes outside a valid index, when i == 2. Perhaps you want v2 = vectors[i<2?i+1:0].

If that's not it.. I don't exactly see from the code what method you are using. What I talked about in my last post is when you trace the edges of the polygon and fill in the pixels between them. There is also the possibility to, combined with the first method, or by simply checking some bounding box of the polygon, test each pixel for intersection with the polygon. Is this what you are doing?
In that case, are you using barycentric coordinates?
Checking whether a point is inside a triangle should be fairly straight-forward.

What I'm trying to say is.. I understand that you want to fill triangles.. other than that I have no idea, as to what method you are using =)

EDIT: Perhaps I see now.. are you going through each line touching the triangle, from top to bottom, and setting the leftmost and rightmost point on that line that belongs to the triangle? By checking intersections with each edge in the polygon..

##### Share on other sites
Yeah, that's what I'm currently doing, grabing each line and seeing where it interects, I have read this method in two books but when I have implemented them I get problems.

as for this
Vector *v1 = vectors;Vector *v2 = vectors[i+1];

I did this
Vector *vectors[] = {&poly->v1, &poly->v2, &poly->v3, &poly->v1};

so that I would have one less if statement.

##### Share on other sites
Quote:
 Original post by Erik RufeltYes it can matter.. usually you always begin with the topmost point, and then draw each row of pixels in the triangle until you reach the bottom point. Unless you're already doing that and I misunderstand your question.. =)You can loop through all your points, checking which one is the topmost, and set that point as index 0, and keep the other points in order after. If you have points 0 1 2 3 4, and point 3 is at the top, the new order is 3 4 0 1 2.

Got it working!!!! :D You were not far off, what I did was to sort the points in the triangle in order of height, the highest being first, instead of setting the start index to the highest.

• 17
• 11
• 12
• 9
• 49
• ### Forum Statistics

• Total Topics
631394
• Total Posts
2999756
×