Page 1 of 2

New kind of maze/world?

Posted: Fri Aug 17, 2007 5:40 pm
by Mentat
As some of you might know, I'm working of Wire V.2 . Well, I've been fiddeling around with the Z axis, and on one of my check runs, another bug popped up (well...it wasn't a bug in the sense that the code was bad. I just changed one of my initial variables). But was in the form of looking down a hall, like a maze.

So...

Posted: Fri Aug 17, 2007 8:10 pm
by Stoves
Your posting privileges ... revoked for 5 minutes!

Posted: Fri Aug 17, 2007 8:52 pm
by Mentat
Huh?

Posted: Mon Aug 20, 2007 8:21 pm
by Mentat
How do I fill in an arbitrary polygon bounded by lines?

Posted: Tue Aug 21, 2007 1:48 pm
by Joe
Mentat wrote:How do I fill in an arbitrary polygon bounded by lines?
EDIT: oops, gave some wrong advice here. Dismiss it.

Posted: Tue Aug 21, 2007 4:16 pm
by Mentat
I mean color. I need a quick way to fill in already made polygons for my RPG. Many polygons.

Posted: Wed Aug 22, 2007 4:25 am
by k7
I would use paint, the position where the paint is targeted is the average of the two x values (x1, x2), and the average of the y values (y1, y2). That paints in the center of the shape.

Posted: Wed Aug 22, 2007 6:31 am
by Mentat
So it fills the entire polygon up? :)

Posted: Wed Aug 22, 2007 1:11 pm
by Joe
Not a good idea. I've tried that before and the paint will miss the center in certain cases. And it also won't fill the entire triangle all the time (the corners will block the paint fill from reaching the empty pixels).

What you want to do is make your own triangle-drawing algorithm. What you need to do is calculate the slope between the vertices and then fill it in from top to bottom using LINE statements.

There are some tutorials on it somewhere. I can't find any for basic though. I'll make another post with examples when I have more time.

Posted: Wed Aug 22, 2007 4:27 pm
by Mentat
Thanks. :D

Posted: Wed Aug 22, 2007 9:25 pm
by Joe
Okay, I managed to code an example. I have a FB version if you want that too. It's commented, so it should be fairly easy to follow. All you need to have is an understanding of slopes or interpolation. Also, check out relsoft's tutorial on this: http://rel.betterwebber.com/mytutes/3dt ... apter3.htm; about halfway down you'll find the tutorial on polygon filling. It'll help fill in the gaps if you don't quite get how this example works. He has a whole series on 3D that's a very good read. I recommend it. You can find it here.

Code: Select all

'- Triangle fill example (QB Version)
'- by Joe King
'- 2007-08-22

TYPE tVertex
    
    x AS INTEGER
    y AS INTEGER
    
END TYPE

DECLARE SUB WireTriangle (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex, col AS INTEGER)
DECLARE SUB FillTriangle (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex, col AS INTEGER)
DECLARE SUB SortVertices (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex)

'OPTION EXPLICIT

'- gfx resolution data
DIM resX AS INTEGER, resY AS INTEGER
resX = 320: resY = 200

SCREEN 13

'- vertex data
DIM v1 AS tVertex
DIM v2 AS tVertex
DIM v3 AS tVertex

'- generation data
DIM numTriangles AS INTEGER
DIM fillcol AS INTEGER
DIM bordcol AS INTEGER
DIM n AS INTEGER
    
numTriangles = 500
    
'- cycle through and draw all the triangles
FOR n = 1 TO numTriangles

    '- randomly generate the triangle vertex coordinates
    v1.x = RND(1) * resX: v1.y = RND(1) * resY
    v2.x = RND(1) * resX: v2.y = RND(1) * resY
    v3.x = RND(1) * resX: v3.y = RND(1) * resY
    '- randomly generate the fill and border colors
    fillcol = RND(1) * 8 + 7
    bordcol = fillcol - 8
    
    '- draw the filled triangle
    FillTriangle v1, v2, v3, fillcol
    '- draw the border (the wireframe version) to verify that the fill
    '- is working correctly
    WireTriangle v1, v2, v3, bordcol
                                
    WAIT &H3DA, 8 '- delay to let the viewer see what's happening
    
NEXT n
    
SLEEP
END

'- SUB FillTriangle
'-
'- Draws a solid triangle with the given vertices and color
'-
'-\
SUB FillTriangle (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex, col AS INTEGER)
    
    CONST ZERO = 1E-32

    DIM x1 AS SINGLE, x2 AS SINGLE
    DIM slope12 AS SINGLE
    DIM slope13 AS SINGLE
    DIM slope23 AS SINGLE
    DIM stp AS INTEGER
    DIM y AS INTEGER
    
    '- vertices must be sorted before filling the triangle
    SortVertices v1, v2, v3
    
    '- calculate slopes
    '- the numbers appended at the end of the slope variables designate which
    '- line it is referring to (ex. slope12 mean the slope of the line between
    '- v1 and v2)
    '- the "+ ZERO" adds the dividend by a very small number to avoid division
    '- by zero erros
    slope12 = (v1.x - v2.x) / ((v1.y - v2.y) + ZERO)
    slope13 = (v1.x - v3.x) / ((v1.y - v3.y) + ZERO)
    slope23 = (v2.x - v3.x) / ((v2.y - v3.y) + ZERO)
    
    '- get starting sides
    x1 = v1.x
    x2 = v1.x
    
    '- determine which way we will be traveling while filling the triangle,
    '- either up or down
    IF v1.y <= v2.y THEN stp = 1 ELSE stp = -1
    
    '- draw first half
    FOR y = v1.y TO v2.y - 1 STEP stp
    
        LINE (x1, y)-(x2, y), col
    
        x1 = x1 + slope12
        x2 = x2 + slope13
    
    NEXT y
    
    x1 = v2.x
    
    '- draw second half
    FOR y = v2.y TO v3.y STEP stp
    
        LINE (x1, y)-(x2, y), col
    
        x1 = x1 + slope23
        x2 = x2 + slope13
    
    NEXT y
    
END SUB

'- SortVertices
'-
'- Sorts the given vertices by their y-value
'-
'-\
SUB SortVertices (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex)
    
    DIM vTop AS tVertex
    DIM vMid AS tVertex
    DIM vBtm AS tVertex
    
    IF v1.y <= v2.y AND v1.y <= v3.y THEN
        
        vTop.x = v1.x: vTop.y = v1.y
        
        IF v2.y <= v3.y THEN
            vMid.x = v2.x: vMid.y = v2.y
            vBtm.x = v3.x: vBtm.y = v3.y
        ELSE
            vMid.x = v3.x: vMid.y = v3.y
            vBtm.x = v2.x: vBtm.y = v2.y
        END IF
        
    ELSEIF v2.y <= v1.y AND v2.y <= v3.y THEN
        
        vTop.x = v2.x: vTop.y = v2.y
        
        IF v1.y <= v3.y THEN
            vMid.x = v1.x: vMid.y = v1.y
            vBtm.x = v3.x: vBtm.y = v3.y
        ELSE
            vMid.x = v3.x: vMid.y = v3.y
            vBtm.x = v1.x: vBtm.y = v1.y
        END IF
        
    ELSE
        
        vTop.x = v3.x: vTop.y = v3.y
        
        IF v1.y <= v2.y THEN
            vMid.x = v1.x: vMid.y = v1.y
            vBtm.x = v2.x: vBtm.y = v2.y
        ELSE
            vMid.x = v2.x: vMid.y = v2.y
            vBtm.x = v1.x: vBtm.y = v1.y
        END IF
        
    END IF

    v1.x = vTop.x: v1.y = vTop.y
    v2.x = vMid.x: v2.y = vMid.y
    v3.x = vBtm.x: v3.y = vBtm.y
    
END SUB

'- SUB WireTriangle
'-
'- Draw a wireframe triangle with the given vertices and color
'-
'-\
SUB WireTriangle (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex, col AS INTEGER)
    
    LINE (v1.x, v1.y)-(v2.x, v2.y), col
    LINE (v2.x, v2.y)-(v3.x, v3.y), col
    LINE (v3.x, v3.y)-(v1.x, v1.y), col
    
END SUB

Posted: Thu Aug 23, 2007 9:42 am
by MystikShadows
Nice example. Worked great here :-)....

Posted: Thu Aug 23, 2007 4:11 pm
by Lachie Dazdarian
FB version, please.

Posted: Thu Aug 23, 2007 9:09 pm
by Joe

Code: Select all

'- Triangle fill example (FB Version)
'- by Joe King
'- 2007-08-22

TYPE tVertex
    
    x AS INTEGER
    y AS INTEGER
    
END TYPE

DECLARE SUB WireTriangle (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex, col AS INTEGER)
DECLARE SUB FillTriangle (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex, col AS INTEGER)
DECLARE SUB SortVertices (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex)

OPTION EXPLICIT

'- gfx resolution data
DIM resX AS INTEGER, resY AS INTEGER
resX = 320: resY = 200

SCREENRES resX, resY

'- vertex data
DIM v1 AS tVertex
DIM v2 AS tVertex
DIM v3 AS tVertex

'- generation data
DIM numTriangles AS INTEGER
DIM fillcol AS INTEGER
DIM bordcol AS INTEGER
DIM n AS INTEGER
    
numTriangles = 500
    
'- cycle through and draw all the triangles
FOR n = 1 TO numTriangles

    '- randomly generate the triangle vertex coordinates
    v1.x = RND(1) * resX: v1.y = RND(1) * resY
    v2.x = RND(1) * resX: v2.y = RND(1) * resY
    v3.x = RND(1) * resX: v3.y = RND(1) * resY
    '- randomly generate the fill and border colors
    fillcol = RND(1) * 8 + 7
    bordcol = fillcol - 8
    
    '- draw the filled triangle
    FillTriangle v1, v2, v3, fillcol
    '- draw the border (the wireframe version) to verify that the fill
    '- is working correctly
    WireTriangle v1, v2, v3, bordcol
                                
    SCREENSYNC  '- delay to let the viewer see what's happening
    
NEXT n
    
SLEEP
END

'- SUB WireTriangle
'-
'- Draw a wireframe triangle with the given vertices and color
'-
'-\
SUB WireTriangle (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex, col AS INTEGER)
    
    LINE (v1.x, v1.y) - (v2.x, v2.y), col
    LINE (v2.x, v2.y) - (v3.x, v3.y), col
    LINE (v3.x, v3.y) - (v1.x, v1.y), col
    
END SUB

'- SUB FillTriangle
'-
'- Draws a solid triangle with the given vertices and color
'-
'-\
SUB FillTriangle (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex, col AS INTEGER)
    
    DIM x1 AS SINGLE, x2 AS SINGLE
    DIM slope12 AS SINGLE
    DIM slope13 AS SINGLE
    DIM slope23 AS SINGLE
    DIM stp AS INTEGER
    DIM y AS INTEGER
    
    '- vertices must be sorted before filling the triangle
    SortVertices v1, v2, v3
    
    '- calculate slopes
    '- the numbers appended at the end of the slope variables designate which
    '- line it is referring to (ex. slope12 mean the slope of the line between
    '- v1 and v2)
    slope12 = (v1.x - v2.x) / (v1.y - v2.y)
    slope13 = (v1.x - v3.x) / (v1.y - v3.y)
    slope23 = (v2.x - v3.x) / (v2.y - v3.y)
    
    '- get starting sides
    x1 = v1.x
    x2 = v1.x
    
    '- determine which way we will be traveling while filling the triangle,
    '- either up or down
    IF v1.y <= v2.y THEN stp = 1 ELSE stp = -1
    
    '- draw first half
    FOR y = v1.y TO v2.y - 1 STEP stp
    
        LINE (x1, y) - (x2, y), col
    
        x1 = x1 + slope12
        x2 = x2 + slope13
    
    NEXT y
    
    x1 = v2.x
    
    '- draw second half
    FOR y = v2.y TO v3.y STEP stp
    
        LINE (x1, y) - (x2, y), col
    
        x1 = x1 + slope23
        x2 = x2 + slope13
    
    NEXT y
    
END SUB

'- SortVertices
'-
'- Sorts the given vertices by their y-value
'-
'-\
SUB SortVertices (v1 AS tVertex, v2 AS tVertex, v3 AS tVertex)
    
    DIM vTop AS tVertex
    DIM vMid AS tVertex
    DIM vBtm AS tVertex
    
    IF v1.y <= v2.y AND v1.y <= v3.y THEN
        
        vTop.x = v1.x: vTop.y = v1.y
        
        IF v2.y <= v3.y THEN
            vMid.x = v2.x: vMid.y = v2.y
            vBtm.x = v3.x: vBtm.y = v3.y
        ELSE
            vMid.x = v3.x: vMid.y = v3.y
            vBtm.x = v2.x: vBtm.y = v2.y
        END IF
        
    ELSEIF v2.y <= v1.y AND v2.y <= v3.y THEN
        
        vTop.x = v2.x: vTop.y = v2.y
        
        IF v1.y <= v3.y THEN
            vMid.x = v1.x: vMid.y = v1.y
            vBtm.x = v3.x: vBtm.y = v3.y
        ELSE
            vMid.x = v3.x: vMid.y = v3.y
            vBtm.x = v1.x: vBtm.y = v1.y
        END IF
        
    ELSE
        
        vTop.x = v3.x: vTop.y = v3.y
        
        IF v1.y <= v2.y THEN
            vMid.x = v1.x: vMid.y = v1.y
            vBtm.x = v2.x: vBtm.y = v2.y
        ELSE
            vMid.x = v2.x: vMid.y = v2.y
            vBtm.x = v1.x: vBtm.y = v1.y
        END IF
        
    END IF

    v1.x = vTop.x: v1.y = vTop.y
    v2.x = vMid.x: v2.y = vMid.y
    v3.x = vBtm.x: v3.y = vBtm.y
    
END SUB

Posted: Fri Aug 24, 2007 5:56 am
by Mentat
Could raycasting be used to fill wireframes?

Posted: Fri Aug 24, 2007 10:24 am
by Joe
Do you mean raytracing? There's a big difference between the two. Raytracing can fill polygons, but it's really processor intensive and generally slow even on today's computers. You'd have a lot of trouble trying to do real-time graphics with that method. But if you aren't and only care to produce pre-rendered images then raytracing is worth learning.

Raycasting is the "flat" form of raytracing, in which you only cast rays on a 2d plane.

Posted: Fri Aug 24, 2007 4:33 pm
by Mentat
I mean throwing rays at auxilery lines and painting around them, thus not "missing". Like this:
+-----+
|......./|
|...../..|
|.../....|
|./......|
+-----+
Where the "/" is the aux line and the dots are paint, and the boder is a square or something.

Posted: Sun Aug 26, 2007 12:09 am
by Joe
I don't quite see what you're talking about. :?

Could you explain it in a little more detail?

Posted: Sun Aug 26, 2007 8:19 am
by Mentat
Ok. Imagine you have a cube. One auxilary line (I made the name up) just connects one pair of diagonal vertices for each face. Then, later on paint both sides of the same color of the Aux line (but not the edges! Otherwise the computer will make a mistake and paint all over the place :) ). However, have the aux lines painted BEFORE the edges, so very thin sides might be ignored and thus avoiding missing. Once that's done, paint on both sides of the aux lines. Of course, you can do other neat things with the auxs.

Posted: Sun Aug 26, 2007 9:54 pm
by Joe
Hmm, I don't know. If you mean splitting up the polygon into triangles and painting them then that won't fix anything. When I said that using paint wasn't a good idea to fill polygons, I was referring to any arbitrary polygon including triangles. Just set up your own triangle filler using paint and try many different triangle shapes and you'll see what I mean. It won't only mess up some of the painting, but you won't be able to paint triangles on top of other triangles. Anyway, if I still don't understand your idea, then it's best just to try it out for yourself and see if it works.

Some examples of what I'm talking about:

Triangle not filled all the way:
http://z8.invisionfree.com/Delta_Code/i ... id=2497881

Can't paint triangles on top of other triangles:
http://z8.invisionfree.com/Delta_Code/i ... id=2497883