Jump to content
  • Advertisement
Sign in to follow this  
DarkMatter2008

Scanconversion problem.

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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;

// Constraints
int 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Erik Rufelt
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.


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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!