Isometric shadow casting light.

Game development specific discussions.
Post Reply
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

that is very good... but still are not getting the speed I would expect... it looks like it is all because of something in the shadowcast routine - the speed doubles if both those calls in the main are commented out... but the only thing that I can see that is slow in there is the sin/cos... but they are only called 4 times each! argh...

drats... its the 'paint' command...... hmmmmm.... ok, what is an alternative? it takes up ALOT of time!
Boromir
Posts: 463
Joined: Apr 30, 2015 19:28
Location: Oklahoma,U.S., Earth,Solar System
Contact:

Re: Isometric shadow casting light.

Post by Boromir »

We could make a triangle rasterizer.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

Boromir wrote:We could make a triangle rasterizer.
yeah, was thinking along those lines too... here is my chain of thought:

We like what the paint command does, but, we know more info than it expects and so it is slower than needs to be - we know the exact dimensions of the area to be filled whereas it has to test EVERY pixel to check for the boundary color...

other info we know:

- the area will always have at least one edge being along an edge of the light box (don't know how useful this is)
- the area will be defined by a polygon with minimum 4 points and a max of 6? points

PROBLEM DEFINED:
How to quickly clear a polygonal area defined by 4 to 6 points?
Last edited by leopardpm on Apr 02, 2017 3:04, edited 1 time in total.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

dodicat is good at these kind of 'polygon' type things... he chimed in before with the line/ray intersection, but we had already passed that chain of thought with the home-rolled line drawing routine...
Boromir
Posts: 463
Joined: Apr 30, 2015 19:28
Location: Oklahoma,U.S., Earth,Solar System
Contact:

Re: Isometric shadow casting light.

Post by Boromir »

Right now the max points is 5 I believe.
I'm pretty bad with rasterization. I'm going to see if I can research some simple methods. I have two rasterizers lying around in my stuff. One was fairly fast but it didn't make perfectly smooth fills.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

Boromir wrote:Right now the max points is 5 I believe.
I think that it can include TWO light box corner points in addition to other 4 that we have calculated...
Boromir
Posts: 463
Joined: Apr 30, 2015 19:28
Location: Oklahoma,U.S., Earth,Solar System
Contact:

Re: Isometric shadow casting light.

Post by Boromir »

Image
This is the biggest and widest shadow possible. The red points are the 5 corners.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

ok, after a bit of google and some thought... here is my idea...

All of these polygons will be of the simple type: convex NOT concave... this is good

for speed, we want to fill it row by row so we can utilize the Fast Pset efficiently as possible - this will be speedilicious!

so, given a set of points which define a polygon, we first find the top-most point(s). What we will do is trace out the outer edge of the polygon, pixel by pixel in two halves:
Image
Now we will follow each ray to the next point via bresenhams.... doing one side until the y-value changes 1, then do the other side until it also goes down one which will mean they will be at the exact same y value.... then we draw a line between them... rinse and repeat until done
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

I have done some work with convex polygons, have routines with ordering all the points and such... let me find them and see how useful they might be...

Here is my testing program to find the convex polygon which encompasses all of a given set of points... lots of extra stuff we don't need, in fact, probably none of it is needed... but still interesting... Just discovered that this code is NOT completed! argh... this can make concave polygons as well... that is wrong... don't know where my finished routine is... drats!

Code: Select all

' this currently only makes the upper left quadrant convex... just need to do same thing
' to remaining 3 quadrants, perhaps then be able to simplify into shorter, more general routine...DONE!
'
type vertice
    x as integer
    y as integer
    s as double
end type

type hulldata
    p as integer  'pointer to actual point(vertice)
    s as double   'slope to next point
end type


dim shared as vertice points(99)
dim shared as hulldata Leftpoints(99), RightPoints(99), polygon(99), leftmost, rightmost

dim shared as integer NumOfPoints, offsetX=300, offsetY=300

dim shared as integer cp = 1, tp = 0, polypnt = 0
dim shared as integer Key, extraspace, loops = 0

'
'============================ subs =================================
'

sub show(x as integer, y as integer, lr as integer, w as integer, a as integer, b as integer, c as double)
        Circle (x+offsetX, y+offsetY), 3, RGB(0,255,255) ',,,, F
        locate 7+lr*2+extraspace,w : print using "p(##) = p(##) s(###.###)";a;b;c
        color rgb(255,255,255)
end sub



screenres 800,600,32

'randomize timer

do
    loops +=1
    cls
    color rgb(255,255,255)
' make random points and print them
'
'    locate 2,5 : Print "RND List:"
'    locate 3,5 : print "Pnt  X / Y "
'
NumOfPoints = 50 ' int(rnd*10)+5
for p as integer = 1 to NumOfPoints
    points(p).x = 2*int(rnd*100)+1
    points(p).y = 2*int(rnd*100)+1
    'locate 2+(p*2),5
    'print using "##  ###/###";p;points(p).x;points(p).y
    Circle (points(p).x+offsetX, points(p).y+offsetY), 2, RGB(255,0,0) ,,,, f
next p

'sort the array of points, stupid slow bubblesort
'
dim as integer exchange = 1, passnum = NumOfPoints - 1
while passnum > 0 and exchange = 1
    exchange = 0
    for i as integer = 1 to passnum
        if points(i).y > points(i+1).y then
            exchange = 1
            swap points(i), points(i+1)
        end if
    next i
    passnum -= 1
wend

' print out sorted list
'
'    locate 2,20 : Print "'Y' SORTED List:"
'    locate 3,20 : print "Pnt  X / Y "
'
'for p as integer = 1 to NumOfPoints
'    locate 2+(p*2),20
'    print using "##  ###/###";p;points(p).x;points(p).y
'next p


'
' find left/right points
'
leftmost.p = 1
rightmost.p = 1

for p as integer = 1 to NumOfPoints
    if points(p).x < points(leftmost.p).x then 
        leftmost.p = p
    end if
    
    if points(p).x > points(rightmost.p).x then
        rightmost.p = p
    end if
next p

' show left & right most points, and Top & Bottom
'
    Circle (points(leftmost.p).x + offsetX, points(leftmost.p).y + offsetY), 4, RGB(0,255,0) ,,,, F
    Circle (points(leftmost.p).x + offsetX, points(leftmost.p).y + offsetY), 2, RGB(255,0,0) ,,,, F

    Circle (points(rightmost.p).x + offsetX, points(rightmost.p).y + offsetY), 4, RGB(0,0,255) ,,,, F
    Circle (points(rightmost.p).x + offsetX, points(rightmost.p).y + offsetY), 2, RGB(255,0,0) ,,,, F
    
    circle (points(1).x+offsetX, points(1).y+offsetY), 5, RGB(255,255,255) ' top
    circle (points(NumOfPoints).x+offsetX, points(NumOfPoints).y+offsetY), 5, RGB(255,255,255) ' bottom
    
    locate 2,50 : print using " Loop ###";loops
    locate 4,50 : print using " leftmost (##) ### / ###";leftmost.p;points(leftmost.p).x;points(leftmost.p).y
    locate 6,50 : print using "rightmost (##) ### / ###";rightmost.p;points(rightmost.p).x;points(rightmost.p).y


'
' initialize routine: top to middle first, then bottom to middle
'
' Enter routine with: Y-SORTED LIST from TOP to BOTTOM: points()
'                                      Point most left: leftmost
'                                     Point most right: rightmost
'
dim as integer TopHighX, BotHighX, TopLowX, BotLowX
dim as integer lp = 0, rp = 0, flpb = 0, frpb = 100, maxp = leftmost.p, minp = rightmost.p
dim as double CurSlope, pp2Slope, pp3Slope

if maxp < minp then swap maxp, minp

leftpoints(0).s = 0 ' set Top point slope to 0
leftpoints(1).s = 0 ' set Top point slope to 0
extraspace = 0

'
' Here is Convex Hull Routine...
'

' setup for TOP
    TophighX = points(1).x + 1
    ToplowX = points(1).x - 1
' setup for BOTTOM
    BotHighX = points(NumOfPoints).x + 1
    BotLowX = points(NumOfPoints).x - 1
    
for p as integer = 1 to maxp ' from top of list to the max point of either left or right)
    ' can p start at 2? we don't need to check TOP point

' is point on the TOP or BOTTOM of the list? This value is different for left & right side
' left side middle = leftmost.p
' right side middle = rightmost.p
' 
' leftp = (numofpoints - (p-leftmost.p))
' rightp = (numofpoints - (p-rightmost.p))
'
' if p < leftmost.p  and points(p).x      <  TopHighx then point is upper left
' if p > leftmost.p  and points(leftp).x  <= BotHighx then point is lower left
' if p < rightmost.p and points(p).x      >  TopLowx then point is upper right
' if p > rightmost.p and points(rightp).x >= BotLowx then point is lower right


    if points(p).x < TopHighX then ' is this a valid 'left' point?
        '--------------------------------------------------------------- 
        '---------- In this section, we have not yet advanced 'lp', so it is pointing to the 'previous' point UNTIL 
        '---------- the current point passes the non-concave test below....
        '---------------------------------------------------------------
        if lp > 0 then 'calc slope between last point and this point
            CurSlope = (points(p).y - points(leftpoints(lp).p).y) / (points(p).x - points(leftpoints(lp).p).x)
        else
            CurSlope = 0 ' this special case for first point
        end if
        
        ' check to see if this point makes the previous point(s) concave... and deal with them
        if CurSlope > leftpoints(lp).s then 
            ' compare current point slope to previous point slope
            ' if previous point is concave, get rid of it by setting its values to current points values
            ' by NOT advancing 'lp' and recalculating slope from second previous point back (lp-1)
            
            CurSlope = (points(p).y - points(leftpoints(lp-1).p).y) / (points(p).x - points(leftpoints(lp-1).p).x)
            
            ' also check to see if the 2nd and 3rd point back is concave as well... 
            ' actually, this should recursively check all the way back to the Top point ideally....
            '
            if lp > 2 then
                pp2Slope = (points(p).y - points(leftpoints(lp-2).p).y) / (points(p).x - points(leftpoints(lp-2).p).x)
                if pp2Slope < CurSlope then
                    ' if the second point back is concave then set pointer (lp) back to there and save that new slope
                    CurSlope = pp2Slope
                    lp -= 1
                    ' now check third point back...
                    if lp > 2 then
                        pp3Slope = (points(p).y - points(leftpoints(lp-2).p).y) / (points(p).x - points(leftpoints(lp-2).p).x)
                        if pp3Slope < CurSlope then
                            ' if the third point back is concave then set pointer (lp) back to there and save that new slope
                            CurSlope = pp3Slope
                            lp -= 1
                        end if
                    end if
                end if
            end if
            
            color rgb(0,0,255)
            extraspace+=1
        else
            lp +=1   'inc num of left points (counter/index)
            color rgb(255,255,255)
        end if
        
        LeftPoints(lp).p = p
        leftpoints(lp).s = CurSlope
        TopHighX = points(p).x
        
        if lp > flpb then flpb = lp  ' remember the last left point on the top to help create polygon list below

        show(points(p).x, points(p).y, lp, 30, lp, p, leftpoints(lp).s)
    end if

    if points(p).x > ToplowX then
        rp +=1   'inc num of right points (counter/index)
        RightPoints(rp).p = p
        TopLowX = points(p).x
        
        if rp>1 then 'calc slope between last point and this point
            RightPoints(rp).s = (points(RightPoints(rp).p).y - points(RightPoints(rp-1).p).y) / (points(RightPoints(rp).p).x -points(RightPoints(rp-1).p).x)
        end if
    end if
next p



for p as integer = NumOfPoints to minp step - 1 ' from BOTTOM of list to the min point of either left or right)

    if points(p).x <= BotHighX then
        lp +=1   'inc num of left points (counter/index)
        LeftPoints(lp).p = p
        BotHighX = points(p).x
        
        color rgb(255,0,0) : show(points(p).x, points(p).y, lp, 30, lp, p, leftpoints(lp).s)
    end if

    if points(p).x >= BotLowX then
        rp +=1   'inc num of right points (counter/index)
        RightPoints(rp).p = p
        BotLowX = points(p).x
        
        if rp < frpb then frpb = rp  ' remember the first right point on the bottom to help create polygon list below

        color rgb(255,0,0) : show(points(p).x, points(p).y, rp, 65, rp, p, rightpoints(rp).s)
    end if
next p





'
' now build one list of points, in counter-clockwise(or ccw) order wthout duplicates...
' (can also be clockwise if desired...)
'

' build polygon from top point going left(ccw)
dim as integer pp = 0, tp = 1, bp

' top left section
    for p as integer = 1 to flpb 'misnamed, flpb is the Last Left Point on the Top
        pp += 1 :  polygon(pp) = leftpoints(p)
    next p

' bottom left section
    for bp = lp to (flpb+1) step -1
        if leftpoints(bp).p <> polygon(pp).p then ' don't copy duplicates
            pp += 1 : polygon(pp) = leftpoints(bp)
        end if
    next bp

' bottom right section
    for p as integer = frpb to rp
        if rightpoints(p).p <> polygon(pp).p then ' don't copy duplicates
            pp += 1 : polygon(pp) = rightpoints(p)
        end if
    next p

' top right section
    for p as integer = (frpb-1) to 1 step -1
        if rightpoints(p).p <> polygon(pp).p then ' don't copy duplicates
            pp += 1 : polygon(pp) = rightpoints(p)
        end if
    next p

' remove duplicate start point from end of list, if it is there...
if polygon(1).p = polygon(pp).p then pp -=1

' then simplify list, removing all cncave points (use turn right/left method...or my slope method)
' the result will be a convex polygon



'
' show final list and draw the polygon!
'
color rgb(255,255,0)
pset(points(polygon(pp).p).x + offsetX, points(polygon(pp).p).y + offsetY), rgb(0,255,0)
for p as integer = 1 to pp
        locate 7+p*2,2
        print using "pp(##) = p(##) s(###.###)";p;polygon(p).p;polygon(p).s
        ' draw it
        line -(points(polygon(p).p).x + offsetX, points(polygon(p).p).y + offsetY), rgb(0,255,0)
next p


Key = getkey
loop until Key = 27
Last edited by leopardpm on Apr 02, 2017 5:53, edited 1 time in total.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

in any case, the first thing to do is to figure out the polygon points we don't have = the light box corner(s). Since there are only 4 corners, is simple just to test each one (with the getslope routine) to see if its slope is between the slopes of the two points on the object we already calc'd... easy peasy!

Now we have X amount of points (i defer to your 5 points, but it shouldnt matter how many...), we find the one with the lowest Y value, and if there are multiple points with same Y value then the one with the smallest X value will be the start for the left side, and the one with the highest X value will be the start for the right side... if only one point, then it will be the start for both sides...

we really should go ahead and convert the current data structure for holding point info so that it has an easy index number:
instead of this:

Code: Select all

type box
    p1 as point2d
    p2 as point2d
    p3 as point2d
    p4 as point2d
    p5 as point2d
    declare sub draw(img as any ptr)
end type
we use this:

Code: Select all

type box
    p(5) as point2d
    declare sub draw(img as any ptr)
end type
(why are there 5 points? will go look at code again...ah ha... calc'd center point for each box...hmmmm). Maybe to make more clear, use this structure then:

Code: Select all

type box
    p(4) as point2d
    cntr as point2d
    declare sub draw(img as any ptr)
end type
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

question:
How do we each work on this, making code changes et al, yet we cannot easily combine the programs? I keep on make the same changes to your code each time I download your latest changes.... maybe is not important
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

BTW - we should also find the Bottom-Most point(s) and note its Y value as this will be the test to end out of the whole routine...
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

As just a starting speed reference, with the code below, I am getting 31-33 fps with cursor right in the middle of 4 boxes. When I comment out the paint command, I get 52-53 fps. My hope is that we can cut the paint command time in half, which should result in a final frame rate of about 42-43 fps... I hope, because this whole poly-fill routine will be some work!

This code uses the 'all boxes in one image' technique as an optimization, as well as optimized all the calc's which divided the light box length and width repeatedly. Also replaced the box UDT to P(x) and cntr points as well as tab formatted most of code as a starting point...

Code: Select all

'2d Quad-Shadow caster
'by Ezekiel Gutierrez and Leopardpm
'
'requires light.bmpx 800x400 for the glow
'
const scrw=1280
const scrh=1024

const pi = 4 * atn(1)
dim shared as double DtoR = pi / 180   ' degrees * DtoR = radians

Dim shared As Integer lw=800,lh=400,lwh=400,lhh=200

type point2d
    x as integer
    y as integer
end type

type box
    p(4) as point2d
    cntr as point2d
    declare sub draw(img as any ptr)
end type

Public Sub Lined(p1 as point2d,p2 as point2d,xs as integer,ys as integer,sw as integer,sh as integer,byref p3 as point2d)
    dim as Single xnew,ynew
    Dim As Single dx,dy,x3,y3,x2,y2,ynum,den,num,numadd,xinc1,xinc2,yinc1,yinc2
    x3=p1.x:y3=p1.y
    x2=p2.x:y2=p2.y
    dx = abs(x2 - x3):dy = abs(y2 - y3):xnew = x3:ynew = y3
    
    if x2 >= x3 Then xinc1 = 1:xinc2 = 1 else xinc1 = -1:xinc2 = -1
    if y2 >= y3 Then yinc1 = 1:yinc2 = 1 else yinc1 = -1:yinc2 = -1
    
    if dx >= dy Then _
      xinc1 = 0:yinc2 = 0:den = dx:num = dx / 2:numadd = dy Else _
      xinc2 = 0:yinc1 = 0:den = dy:num = dy / 2:numadd = dx
    
    While 1
      if xnew>xs+sw then p3.x=xnew:p3.y=ynew:exit sub
      if xnew<xs    then p3.x=xnew:p3.y=ynew:exit sub
      if ynew>ys+sh then p3.x=xnew:p3.y=ynew:exit sub
      if ynew<ys    then p3.x=xnew:p3.y=ynew:exit sub
      num += numadd
      if num >= den Then   num -= den:xnew += xinc1:ynew += yinc1
      xnew += xinc2:ynew += yinc2
    Wend
End Sub

public function getslope(p1 as point2d, _
                  p2 as point2d) as integer
        dim as integer xdif,ydif
        xdif = p2.x - p1.x
        ydif = p2.y - p1.y
        return atan2(ydif, xdif)*(180 / pi)
end function

public sub makepoint(angle as integer,plight as point2d, _
              p1 as point2d, _
              byref p2 as point2d)
    p2.x=p1.x-(Cos(angle*DtoR)*(200))
    p2.y=p1.y-(Sin(angle*DtoR)*(200))
    lined(p1,p2,plight.x-(lwh),plight.y-(lhh),lw,lh,p2)
end sub

sub box.draw(img as any ptr)
    line img,(p(1).x,p(1).y-20) - (p(2).x,p(2).y-20) ,rgb(255,0,0)
    line img,(p(2).x,p(2).y-20) - (p(2).x,p(2).y)    ,rgb(255,0,0)
    line img,(p(2).x,p(2).y)    - (p(4).x,p(4).y)    ,rgb(255,0,0)
    line img,(p(3).x,p(3).y)    - (p(4).x,p(4).y)    ,rgb(255,0,0)
    line img,(p(3).x,p(3).y)    - (p(3).x,p(3).y-20) ,rgb(255,0,0)
    line img,(p(3).x,p(3).y-20) - (p(1).x,p(1).y-20) ,rgb(255,0,0)
    line img,(p(4).x,p(4).y)    - (p(4).x,p(4).y-20) ,rgb(255,0,0)
    line img,(p(2).x,p(2).y-20) - (p(4).x,p(4).y-20) ,rgb(255,0,0)
    line img,(p(3).x,p(3).y-20) - (p(4).x,p(4).y-20) ,rgb(255,0,0)
    paint img,(p(1).x+1,p(1).y+3) ,rgb(50,0,0),  rgb(255,0,0)
    paint img,(p(1).x-1,p(1).y+3) ,rgb(100,0,0), rgb(255,0,0)
    paint img,(p(1).x,p(1).y-1)   ,rgb(255,0,0), rgb(255,0,0)
end sub

declare sub shadowcast(box1 as box,plight as point2d,img as any ptr,col as Integer,lw As Integer,lh As Integer)

screenres scrw,scrh,32
dim as box boxes(99)

    Dim as point2d plight1,plight2

    for y as integer=0 to 9
        For x As Integer=0 To 10
            with boxes(x+(y*10))
            .p(1).x=100+(x*80) 'box
            .p(1).y=90 +(y*80)'    co-ordinate 1
            .p(2).x=80+(x*80)'box
            .p(2).y=100+(y*80)'    co-ordinate 2
            .p(3).x=120+(x*80)'box
            .p(3).y=100+(y*80)'    co-ordinate 3
            .p(4).x=100+(x*80)'box
            .p(4).y=110+(y*80)'    co-ordinate 4
            .cntr.x=100+(x*80)'(.p(1).x+.p(2).x+.p(3).x+.p(4).x)/4
            .cntr.y=100+(y*80)'(.p(1).y+.p(2).y+.p(3).y+.p(4).y)/4
            end With
        Next x
    next y

'create light glow from 32 bit bitmap
    dim as any ptr light1,light2,light
    light=imagecreate(lw,lh)
    light1=imagecreate(lw,lh)
    light2=imagecreate(lw,lh)
    bload "light big.bmpx",light
'====================================
    color rgb(255,255,255),rgb(0,0,0)
    
' Make the Background image (the isometric grid)
    dim as any ptr back
    back=imagecreate(scrw,scrh,rgb(0,0,0))
    
    For i As Integer=0 To 1700 Step 20
        Line back,(0,i)-(scrw,i-scrw/2),RGB(150,0,50)
    Next
    
    For i As Integer=-700 To 1024 Step 20
        Line back,(0,i)-(scrw,i+scrw/2),RGB(150,0,100)
    Next

' Make the foreground image (all the boxes)
    dim as any ptr front
    front=imagecreate(scrw,scrh,rgb(0,0,0))
    line front, (0,0)-(scrw-1,scrh-1), rgb(255,0,255),bf ' magic pink

    For i as Integer=0 To UBound(boxes)
        boxes(i).draw(front)
    next i

    dim as integer fps,frames
    dim as double prevtime
    prevtime=timer
    plight2.x=200
    plight2.y=200
    
Do
    GetMouse plight1.x,plight1.y'put light.x and y at mouse
    
    screenlock
        Put (0,0),back,pset
        
        Put light1,(0,0),light,PSet
        Put light2,(0,0),light,pset
        
        For i as integer=0 to UBound(boxes)
           If boxes(i).cntr.x > plight1.x-lwh Andalso boxes(i).cntr.x < plight1.x+lwh Andalso boxes(i).cntr.y > plight1.y-lhh Andalso boxes(i).cntr.y < plight1.y+lhh  Then
              shadowcast(boxes(i),plight1,light1,i,lw,lh)'cast shadow
           End If
        next i
        for i as integer=0 to UBound(boxes)
           If boxes(i).cntr.x > plight2.x-lwh Andalso boxes(i).cntr.x < plight2.x+lwh Andalso boxes(i).cntr.y > plight2.y-lhh Andalso boxes(i).cntr.y < plight2.y+lhh  Then
              shadowcast(boxes(i),plight2,light2,i,lw,lh)'cast shadow
           End if
        next i
        
        put (plight1.x-lwh,plight1.y-lhh),light1,alpha
        put (plight2.x-lwh,plight2.y-lhh),light2,alpha
        
        Put (0,0),front,trans

        Locate 1,1
        print "fps ";fps
    screenunlock
    
    sleep 1
    frames+=1
    if timer-1>prevtime then fps=frames:frames=0:prevtime=timer
loop until multikey(1)


sub shadowcast(box1 as box,plight as point2d,img as any ptr,col as Integer,lw As Integer,lh As integer)
    dim as point2d shad1,shad2
    dim as integer slope1,slope2,slope3,slope4
    
    dim as point2d ch1,ch2
    dim as integer testval=-200,testval2
    'calculate differences for each point
    
    with box1
        slope1=getslope(.p(2),plight)'+180
        slope2=getslope(.p(4),plight)'+180
        slope3=getslope(.p(1),plight)'+180
        slope4=getslope(.p(3),plight)'+180
        dim as integer k,k1,k2,k3,k4
        if slope1>0 then k+=1:k1=1
        if slope2>0 then k+=1:k2=1
        if slope3>0 then k+=1:k3=1
        if slope4>0 then k+=1:k4=1
        if k>0 andalso k<4 andalso plight.x<(box1.p(2).x+box1.p(3).x)/2 then
            if k1=1 then slope1-=360
            if k2=1 then slope2-=360
            if k3=1 then slope3-=360
            if k4=1 then slope4-=360
        end if
        '===================================================
        if slope1>testval then testval=slope1:ch1=.p(2)      ':chx2=x:chy2=y2
        if slope2>testval then testval=slope2:ch1=.p(4)     ':chx2=x:chy2=y
        if slope3>testval then testval=slope3:ch1=.p(1)       ':chx2=x2:chy2=y2
        if slope4>testval then testval=slope4:ch1=.p(3)      ':chx2=x2:chy2=y
        testval2=testval
        if slope1<testval2 then testval2=slope1:ch2=.p(2)
        if slope2<testval2 then testval2=slope2:ch2=.p(4)
        if slope3<testval2 then testval2=slope3:ch2=.p(1)
        if slope4<testval2 then testval2=slope4:ch2=.p(3)
        '===================================================
    end with
    'use selected points
    makepoint(testval,plight,ch1,shad1)'create first point
    makepoint(testval2,plight,ch2,shad2)'create second point
    
        dim as point2d p1=shad1,p2=ch1,p3=ch2,p4=shad2
    'draw shadow outline
        p1.x-= plight.x-(lwh)
        p1.y-= plight.y-(lhh)
        p2.x-= plight.x-(lwh)
        p2.y-= plight.y-(lhh)
        p3.x-= plight.x-(lwh)
        p3.y-= plight.y-(lhh)
        p4.x-= plight.x-(lwh)
        p4.y-= plight.y-(lhh)
        
        Line img,(p1.x,p1.y)-(p2.x,p2.y),rgba(col,0,0,0)
        Line img,(p2.x,p2.y)-(p3.x,p3.y),rgba(col,0,0,0)
        Line img,(p4.x,p4.y)-(p3.x,p3.y),rgba(col,0,0,0)
    
    'fill shadow outline
    paint img,((p1.x+p2.x+p3.x+p4.x)/4, _
               (p1.y+p2.y+p3.y+p4.y)/4),rgba(col,0,0,0),rgba(col,0,0,0)
end sub
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

LOL - I am such a slooooow programmer....

here is what I got so far in the routine... it is setup for testing, each iteration it makes 5 random points, sorts them, then determines wich 'side' each point is so they are ready to hand off to the respective Bresenham routine (right side or left side one).... soooo tedious....

Code: Select all

' =====================================================
' ===============  CONVEX POLYGON FILL ROUTINE  =======
' =====================================================

type vertice
    x as integer
    y as integer
    side as integer
end type

type hulldata
    p as integer  'pointer to actual point(vertice)
    s as double   'slope to next point
end type


dim shared as vertice points(5), leftPTS(5),rightPTS(5)
dim shared as hulldata Leftpoints(99), RightPoints(99), polygon(99), TopMost, BottomMost
dim shared as integer NumOfPoints, offsetX=300, offsetY=300
dim shared as integer Key, extraspace, loops = 0

screenres 800,600,32

randomize timer

do
    loops +=1
    cls
    color rgb(255,255,255)
'
' make random points (within designated areas...) and show them
'   
    NumOfPoints = 5 : Points(0).x = NumOfPoints
    points(1).x = int(rnd*390)+11     'upper left
    points(1).y = int(rnd*290)+11

    points(2).x = int(rnd*390)+401    'upper right
    points(2).y = int(rnd*290)+11

    points(3).x = int(rnd*190)+11     'center left
    points(3).y = int(rnd*200)+301

    points(4).x = int(rnd*190)+601    'center right
    points(4).y = int(rnd*200)+301

    points(5).x = int(rnd*400)+201    'bottom center
    points(5).y = int(rnd*90)+501
    
    for p as integer = 1 to NumOfPoints
        Circle (points(p).x, points(p).y), 2, RGB(255,0,0) ,,,, f
    next p

' ======================================================================
' ============== ENTER ROUTINE HERE 
' ==============   with all points in array points(5)
' ==============   points(0).x = NumberOfPoints  (should be four or five)
' ======================================================================

NumOfPoints = Points(0).x
'
'sort the array of points, from top to bottom, and left to right
'
    dim as integer exchange = 1, passnum = NumOfPoints - 1
    while passnum > 0 and exchange = 1
        exchange = 0
        for i as integer = 1 to passnum
            if points(i).y > points(i+1).y then
                exchange = 1
                swap points(i), points(i+1)
            end if
            
            ' if the Y values are same, then sort based on x values...
            if points(i).y = points(i+1).y then
                if points(i).x > points(i+1).x then
                    exchange = 1
                    swap points(i), points(i+1)
                end if
            end if
        next i
        passnum -= 1
    wend

'
' find Top-Most and Bottom-Most points, show them
'
    TopMost.p = 1
    BottomMost.p = NumOfPoints
    circle (points(1).x, points(1).y), 5, RGB(255,255,255) ' top
    circle (points(NumOfPoints).x, points(NumOfPoints).y), 5, RGB(255,255,255) ' bottom

'
' calc main left/right dividing slope...
'
    dim as integer TLP, TRP
    dim as double MainSlope, CurSlope
    MainSlope = (points(1).x - points(NumOfPoints).x) / (points(1).y - points(NumOfPoints).y)
    
    for p as integer = 2 to NumOfPoints-1
        CurSlope = (points(1).x - points(p).x) / (points(1).y - points(p).y)
        if CurSlope < MainSlope then
            points(p).side = -1
        else
            points(p).side = 1
        end if
        'print MainSlope, curSlope, p, points(p).side
    next p
    
    TLP = 1   ' set top Left Point to the first point
    TRP = 1   ' set Top Right Point same as Top Left Point
    points(1).side = 0  ' set first point side to 0 (means is on BOTH sides)

    ' check for same y value of first two points
    if points(1).y = points(2).y then
        points(2).side =  1 ' set second point to RIGHT side only
        points(1).side = -1 ' set first point to LEFT side only, 0 means BOTH sides
        TRP = 2        ' set Top Right Point to the second point
    end if
    
    locate 2,1 : print "Main Slope = ";MainSlope

    for p as integer = 1 to NumOfPoints
        print
        print using "(#) (### / ###) = ##";p;points(p).x;points(p).y;points(p).side
    next p
       
    
    Key = getkey
loop until Key = 27
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Isometric shadow casting light.

Post by leopardpm »

ARGH! Almost got it.....

Image

but there are problems....

Image

my mind hurts, here is code if you care to try to decypher it... lord knows I can't!

I figured out that I could avoid the whole bresenhan's line draw between the points of the polygon because I already knew the total change in Y-values between the top point and the bottom point, so all I needed was the slope between each point and as I iterate through the y-values, just add the slop to the x value each time.... I think it will work, but my mind won't right now... I tried to comment things, but there are 'spare parts' lying around and it is confusing... if you spot the problem, please let me know!!! lol

My thought is that it is 'missing' detecting when it has come to the next point of the polygon where it then needs to change its slope to go on to the next point... i don't know

Code: Select all

' =====================================================
' ===============  CONVEX POLYGON FILL ROUTINE  =======
' =====================================================

type vertice
    x as integer
    y as integer
    side as integer
    NLP as integer   ' the next left side point
    NRP as integer   ' the next right side point
    Lslp as double   ' this is the slope from this point towards the next point ON THE LEFT SIDE!
    Rslp as double   ' this is the slope from this point towards the next point ON THE RIGHT SIDE!
end type


dim shared as vertice points(5)
dim shared as integer NumOfPoints
dim shared as integer Key, extraspace, loops = 0

screenres 800,600,32

randomize timer

do
    loops +=1
    cls
    color rgb(255,255,255)
'
' make random points (within designated areas...) and show them
'   
    NumOfPoints = 5 : Points(0).x = NumOfPoints
    points(1).x = int(rnd*390)+11     'upper left
    points(1).y = int(rnd*290)+11

    points(2).x = int(rnd*390)+401    'upper right
    points(2).y = int(rnd*290)+11

    points(3).x = int(rnd*190)+11     'center left
    points(3).y = int(rnd*200)+301

    points(4).x = int(rnd*190)+601    'center right
    points(4).y = int(rnd*200)+301

    points(5).x = int(rnd*400)+201    'bottom center
    points(5).y = int(rnd*90)+501
    
    for p as integer = 1 to NumOfPoints
        Circle (points(p).x, points(p).y), 4, RGB(255,0,0) ,,,, f
    next p

' ======================================================================
' ============== ENTER ROUTINE HERE 
' ==============   with all points in array points(5)
' ==============   points(0).x = NumberOfPoints  (should be four or five)
' ======================================================================

NumOfPoints = Points(0).x
'
'sort the array of points, from top to bottom, and left to right
'
    dim as integer exchange = 1, passnum = NumOfPoints - 1
    while passnum > 0 and exchange = 1
        exchange = 0
        for i as integer = 1 to passnum
            if points(i).y > points(i+1).y then
                exchange = 1
                swap points(i), points(i+1)
            end if
            
            ' if the Y values are same, then sort based on x values...
            if points(i).y = points(i+1).y then
                if points(i).x > points(i+1).x then
                    exchange = 1
                    swap points(i), points(i+1)
                end if
            end if
        next i
        passnum -= 1
    wend

'
' find Top-Most and Bottom-Most points, show them
'

    circle (points(1).x, points(1).y), 5, RGB(255,255,255) ' top
    circle (points(NumOfPoints).x, points(NumOfPoints).y), 5, RGB(255,255,255) ' bottom

'
' calc main left/right dividing slope...
'
    dim as integer TLP, TRP
    dim as double MainSlope, CurSlope
    MainSlope = (points(1).x - points(NumOfPoints).x) / (points(1).y - points(NumOfPoints).y)
    
    for p as integer = 2 to NumOfPoints-1
        CurSlope = (points(1).x - points(p).x) / (points(1).y - points(p).y)
        if CurSlope < MainSlope then
            points(p).side = -1
        else
            points(p).side = 1
        end if
        'print MainSlope, curSlope, p, points(p).side
    next p
    
    TLP = 1   ' set top Left Point to the first point
    TRP = 1   ' set Top Right Point same as Top Left Point
    points(1).side = 0  ' set first point side to 0 (means is on BOTH sides)

    ' check for same y value of first two points
    if points(1).y = points(2).y then
        points(2).side =  1 ' set second point to RIGHT side only
        points(1).side = -1 ' set first point to LEFT side only, 0 means BOTH sides
        TRP = 2        ' set Top Right Point to the second point
    end if
    
    ' NOW, figure out the slopes of each point ot the next point on same side!
    dim as integer curleftpoint = TLP, currightpoint = TRP, nextLeft, nextRight
    dim as integer q
    
    ' find all the left points, calc each slope
    do
        ' find next left point
        nextLeft = curleftpoint
        do
            nextLeft += 1
        loop while points(nextLeft).side > 0
            
        ' got the next left, now calc slope to it from current left
        points(curleftpoint).Lslp = (points(curleftpoint).x - points(nextLeft).x) / (points(curleftpoint).y - points(nextLeft).y)
        ' save this next point
        points(curleftpoint).NLP = nextLeft
        curleftpoint = nextLeft
    loop while points(nextleft).side <> 0  'until at bottom point
        
        
    ' find all the right points, calc each slope
    do
        ' find next right point
        nextRight = currightpoint
        do
            nextRight += 1
        loop while points(nextRight).side < 0

        ' got the next right, now calc slope to it from current right
        points(currightpoint).Rslp = (points(currightpoint).x - points(nextRight).x) / (points(currightpoint).y - points(nextRight).y)
        ' save this next point
        points(currightpoint).NRP = nextRight
        currightpoint = nextRight
    loop while points(nextRight).side <> 0  'until at bottom point
    
    
    locate 2,1 : print "Main Slope = ";MainSlope

    for p as integer = 1 to NumOfPoints
        print
        print using "(#) (### / ###) side(##) Lslp(###.###)  Rslp(###.###)";p;points(p).x;points(p).y;points(p).side;points(p).Lslp;points(p).Rslp;
    next p
       

' ok, now we got a sorted array of points, each identified as to which 'side' they are on
' lets determine how many yvalues there will be in total...
    dim as integer NumOfYvalues = points(NumOfPoints).y - points(1).y + 1

    ' set the initial x-values for both sides..
    dim as double Lx = points(TLP).x , Rx = points(TRP).x
    ' set the current point for each side
    dim as integer CLP = TLP, CRP = TRP
    
    for yvalue as integer = points(1).y + 1 to points(NumOfPoints).y  'iterate through all the yvalues
        ' calc the x-value for this y value for both Left and Right
        Lx += points(CLP).Lslp : Rx += points(CRP).Rslp

        ' draw the line between the to xvalues at this yvalue
        line (int(Lx), yvalue) - (int(Rx), yvalue), rgb(0,255,0)

        ' check to see if reached next left/right points...
        if int(Lx) = points(points(CLP).NLP).x and yvalue = points(points(CLP).NLP).y then
            ' change current left point to the next left point!
            CLP = points(CLP).NLP
        end if

        if int(Rx) = points(points(CRP).NRP).x and yvalue = points(points(CRP).NRP).y then
            ' change current right point to the next right point!
            CRP = points(CRP).NRP
        end if
    next yvalue


    Key = getkey
loop until Key = 27

Post Reply