Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 [2] 3
  ignore  |  Print  
  Line of sight through 2d polygons (shadows, field of view)  (Read 27448 times)
0 Members and 1 Guest are viewing this topic.
Offline CommanderKeith
« Reply #30 - Posted 2009-10-11 14:37:08 »

That's fine.

nextM would be 2 if m == 1.

If m == 3, nextM would be 0.


Offline h3ckboy

JGO Coder


Medals: 5



« Reply #31 - Posted 2009-10-11 17:36:32 »

I think that I had figured it out. So m is supposed to be the point after j, and nextM is the point after that?

I have spent about an hour, and I think that I have a pretty solid grasp of about the first half of it.

it is actually pretty genious Smiley
Online Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #32 - Posted 2009-10-11 17:40:29 »

same as:

int nextM = (m+1) % points.size();

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline skinny boy

Junior Member





« Reply #33 - Posted 2009-10-11 18:44:14 »

not that i understood all that high level stuff you are talking about

here is my problem

downloaded the *.jar (which i assume is the compiled code)
and the dependency jar

so i double click the LineOfSight.jar and i am expecting it to work
(it works fine when using the jnlp)

it opens the "Progess : Just a few Moments: Quit (Button)" frame and never executes

what can i do to run it as a desktop ? (and not compiling the source i was given generously)
Offline CommanderKeith
« Reply #34 - Posted 2009-10-12 07:17:16 »

Hi skinny boy,

Look up how to include jars on the classpath so you can include JTS, and use the source code I provided rather than the jar. What IDE are you using? In netbeans it's easy to include jars.

same as:

int nextM = (m+1) % points.size();

That's cool, never seen that. Is there a similar thing for prevM which is like this with the conditional operator?
1  
int prevM = (m-1 < 0 ? points.size()-1 : m-1);


Cheers,
Keith

Online Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #35 - Posted 2009-10-12 09:26:17 »

1  
2  
3  
int range = points.size();
int nextM = (m+1) % range;
int prevM = (m-1+range) % range;

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline CommanderKeith
« Reply #36 - Posted 2009-10-12 09:45:05 »

Nice  Cool

Offline skinny boy

Junior Member





« Reply #37 - Posted 2009-10-12 12:13:41 »


Look up how to include jars on the classpath so you can include JTS, and use the source code I provided rather than the jar. What IDE are you using? In netbeans it's easy to include jars.

i use JCreator and i am seriously thinking about changing it
i will give it a shot when i have time
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #38 - Posted 2009-10-13 16:43:36 »

Pretty neat. So what's the actual algorithm going on here? Are you creating shadow polys from each object and then subtracting them from a big light poly to get the final light shape?

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline CommanderKeith
« Reply #39 - Posted 2009-10-13 17:41:02 »

Thanks a lot, this is pretty much the algorithm:

Make an empty list of points
Add all polygon points that have an unobstructed line to the eye (or light source)
Add all polygon intersection points that have an unobstructed line to the eye
Add all points on the sight polygon (or field of view) that have an unobstructed line to the eye
Sort the list by the angle of each point relative to the eye, from the x-axis
Search through the points and find any polygon points that are 'end points' which would cast a shadow.
Cast a ray from these points away from the eye, and find the intersection of this ray with the nearest polygon or the nearest edge of the sight polygon.
Add the intersection to the list, before or after the 'end point' depending on which side the end point is on.

It took a lot of trial and error to arrive at this method. I tried lots of other ways but they weren't stable. This one works fine so long as the eye is never collinear with any edges of the polygons, which i enforce by making the player unable to penetrate a slightly larger polygon, which i create using JTS. You pointed me to that so cheers Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #40 - Posted 2009-10-13 18:30:12 »

Nice one.

I might test this algorithm in my rasterizer to reduce the massive overdraw.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline CommanderKeith
« Reply #41 - Posted 2009-10-13 22:27:46 »

Cool, but then you'd lose the soft shadows. I was thinking about how to get soft shadows using this method - maybe you could do it by looking for the shadow-casting points and making a thin triangle polygon from the shadow-casting point, then you could fill that triangle with a smooth gradient.

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #42 - Posted 2009-10-13 22:35:22 »

Ah, that makes sense. I've thought about the "sort by angle and then walk around" approach before, but whenever I've gone over it in my head I've never managed to come up with a robust algorithm. I might have to have a crack at implementing it.

I'm also wondering whether it'd be possible to add soft shadows to it, it feels like it should be possible but again there's probably a whole bunch of extra edge cases it adds.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Nate

JGO Kernel


Medals: 147
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #43 - Posted 2009-10-14 01:16:11 »

For soft shadows you could move the eye a little and recompute the LOS.

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #44 - Posted 2009-10-14 09:28:27 »

For soft shadows you could move the eye a little and recompute the LOS.
That's not very soft. Or fast.

For non-sucky soft shadows you have to calculate the penumbra wedge at the edge of each shadow. For the inner half this is easy (since you're just drawing part of the existing light geometry with a gradient), the outer half is more problematic as you need to expand the existing light geometry while taking into account any extra occulders that are behind the shadow casting one.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #45 - Posted 2009-10-24 21:42:01 »

Thanks a lot, this is pretty much the algorithm:

Make an empty list of points
Add all polygon points that have an unobstructed line to the eye (or light source)
Add all polygon intersection points that have an unobstructed line to the eye
Add all points on the sight polygon (or field of view) that have an unobstructed line to the eye
Sort the list by the angle of each point relative to the eye, from the x-axis
Search through the points and find any polygon points that are 'end points' which would cast a shadow.
Cast a ray from these points away from the eye, and find the intersection of this ray with the nearest polygon or the nearest edge of the sight polygon.
Add the intersection to the list, before or after the 'end point' depending on which side the end point is on.

So I'm having a crack at doing this but can't seem to make it handle all the edge cases - could you elaborate on exactly how you're determining if a point is a casting edge or not?

I've been testing to see if the vertex is sharing an edge with faces pointing away and towards  thel light but this has issues when you've got faces exactly parallel with the light (and other quirks).

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline CommanderKeith
« Reply #46 - Posted 2009-10-25 03:10:39 »

Lol, I know, the corner cases are a pain. The way i solved the parallel problem was to do a line-line intersection test of each shadow-casting point to see if it can be used. The floating point imprecision of that calculation actually helped since it cut out lines that were exactly parallel  Smiley

When casting the shadow ray from the point, I cast it against all lines of all polygons, except for the 2 lines of the polygon from the point at which the ray emanates from.

You'll have to look at the code, it's too hard to explain in english. Here's the main bit:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
      // Make new points by casting a ray from the eye thru each obstacle end point and finding the closest intersection.
     for (int j = 0; j < sightPoints.size(); j++){
         int jPlus = (j+1 >= sightPoints.size() ? 0 : j+1);
         if (sightPoints.get(j).getType() == SightPoint.OBST_POINT){
            // see if the the points on the polygon on either side of this one are on the same side so a shadow can be cast
           SPObstPoint sp = (SPObstPoint)sightPoints.get(j);
            KPoint p = sp.getPoint();
            float angleRelativeToEye = sp.getAngleRelativeToEye();
            KPolygon polygon = sp.getPolygon();
            int pNum = sp.getPolygonPointNum();
            int pNumPlus = (pNum+1 >= polygon.getPoints().size() ? 0 : pNum+1);
            KPoint pPlus = polygon.getPoints().get(pNumPlus);
            int pNumMinus = (pNum-1 < 0 ? polygon.getPoints().size()-1 : pNum-1);
            KPoint pMinus = polygon.getPoints().get(pNumMinus);
            float pPlusRCCW = pPlus.relativeCCW(eye, p);
            float pMinusRCCW = pMinus.relativeCCW(eye, p);
            if (pPlusRCCW == pMinusRCCW){
               KPoint endOfRayPoint = p.createPointRelativeTo(angleRelativeToEye, getOriginalSightPolygon().getCircularBound()*2);
               KPoint closestIntersectionPoint = null;
               float closestDist = Float.MAX_VALUE;
               // cast a ray from the shadow point and find the closest intersection with the obstacles
              for (int k = 0; k < polygonAndDists.size(); k++){
                  PolygonAndDist polygonAndDist = polygonAndDists.get(k);
                  if (closestDist < polygonAndDist.getDistEyeToCenterLessCircBound()){
                     break;
                  }
                  KPolygon polygon2 = polygonAndDist.getPolygon();
                  if (polygon2.intersectionPossible(p, endOfRayPoint) == false){
                     // intersection is not possible, so skip to next obstacle.
                    continue;
                  }
                  ArrayList<KPoint> points = polygon2.getPoints();
                  for (int m = 0; m < points.size(); m++){
                     int mPlus = (m+1 >= points.size() ? 0 : m+1);
                     if (polygon == polygon2 && (pNum == m || pNum == mPlus)){
                        continue;
                     }
                     if (KPolygon.linesIntersect(p, endOfRayPoint, points.get(m), points.get(mPlus))){
                        KPoint intersection = KPolygon.getLineLineIntersection(p, endOfRayPoint, points.get(m), points.get(mPlus));
                        if (intersection != null){
                           float dist = eye.distance(intersection);
                           if (dist < closestDist){
                              closestDist = dist;
                              closestIntersectionPoint = intersection;
                           }
                        }
                     }
                  }
               }
               // also see if the closest intersection is with the sightPolygon
             
               if ((closestIntersectionPoint != null && closestDist < minEyeToSightPolygonPointDist) == false){
//                  boolean atLeastOneIntersection = false;
                 ArrayList<KPoint> points = this.getSightPolygon().getPoints();
                  for (int m = 0; m < points.size(); m++){
                     int mPlus = (m+1 >= points.size() ? 0 : m+1);
                     if (KPolygon.linesIntersect(p, endOfRayPoint, points.get(m), points.get(mPlus))){
//                        atLeastOneIntersection = true;
                       KPoint intersection = KPolygon.getLineLineIntersection(p, endOfRayPoint, points.get(m), points.get(mPlus));
                        if (intersection != null){
                           float dist = eye.distance(intersection);
                           if (dist < closestDist){
                              closestDist = dist;
                              closestIntersectionPoint = intersection;
                           }
                        }
                     }
                  }
                  // for debugging:
//                  if (atLeastOneIntersection == false || closestIntersectionPoint != null && closestDist > maxEyeToSightPolygonPointDist){
//                     System.out.println(this.getClass().getSimpleName()+": atLeastOneIntersection == "+atLeastOneIntersection+", closestIntersectionPoint != null, closestDist == "+closestDist+", maxEyeToSightPolygonPointDist == "+maxEyeToSightPolygonPointDist+", minEyeToSightPolygonPointDist == "+minEyeToSightPolygonPointDist+", sightPolygon.contains(p) == "+sightPolygon.contains(p)+", eye.distance(p) == "+eye.distance(p));
//                  }
              }
               if (closestIntersectionPoint != null){
                  SPShadowPoint newSightPoint = new SPShadowPoint(closestIntersectionPoint, angleRelativeToEye);
                  if (pPlusRCCW == 1 && pMinusRCCW == 1){
                     sightPoints.add(jPlus, newSightPoint);
                     j++;
                     continue;
                  }else if (pPlusRCCW == -1 && pMinusRCCW == -1){
                     sightPoints.add(j, newSightPoint);
                     j++;
                     continue;
                  }
               }
            }
         }
      }

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #47 - Posted 2009-10-26 01:04:58 »

Whoa, that's a whole lot more complicated than what I've got atm. Turned out my problem was a stupid rounding error in my sort comparator though.

Still fighting precision problems though - thinking of converting the whole lot to double precision to see if that'll help.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #48 - Posted 2009-10-27 00:26:41 »

Tweeking epsilons helped a lot, (but not completely). Anyway, here's my implementation: http://triangularpixels.com/Shadows/Shadows.html

Source coming after I've tidied it up a big.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Nate

JGO Kernel


Medals: 147
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #49 - Posted 2009-10-27 02:31:25 »

Very cool Orangy Tang! I found two bugs (red dots are where the mouse was):

Click to Play


Left is the mouse on a vertex. Right is mouse on the left edge.

Offline skinny boy

Junior Member





« Reply #50 - Posted 2009-10-27 03:25:55 »

i have wasted the last 30 minutes trying to replicate the bugs mentioned above but no luck

seems perfectly made here
Offline Nate

JGO Kernel


Medals: 147
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #51 - Posted 2009-10-27 03:29:30 »

Weird. The left one the mouse is on the upper left vertex of a square. The right one the mouse is on the left edge of any square.

Offline CommanderKeith
« Reply #52 - Posted 2009-10-27 06:48:31 »

Nice! Like in Nate's pictures, I can make it go haywire if I put the mouse cursor on the left edge of any square. The same thing happens in my implementation, that's why I don't allow the player to go on any edges.

It seems pretty stable and quick. Have you tried optimising it and doing an FPS test?

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #53 - Posted 2009-10-27 10:02:07 »

I knew there'd be an edge case or two that I'd missed, cheers. Smiley Probably just a precision problem, I'll try hacking in CommanderKeith's fix for that and upload a new version.

Algorithmically it's pretty terrible (there's *tons* of line vs. line collision checks going on) but it runs a lot faster than I though - here at least the bottleneck is the Java2D drawing rather than the casting. Plus I new a lot of objects and duplicate a lot of calculations, so there's lots that could be done faster.

I think next I need to put it into a game-like environment to see how it holds up - I'm worried that in a tile map level a lot of the 'funny' edge cases will occur a lot more frequently and might make it unusable.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline CommanderKeith
« Reply #54 - Posted 2009-11-14 04:10:30 »

I've reposted a faster version which
- minimises calls to Math.sqrt (by using distanceSq rather than distance) and Math.atan2. I tried Riven's FastMath class too but it turns out that the innacuracies cause errors in the algorithm.
- classifies occluding polygons into a quadrant based on its position relative to the eye (or light source) which allows the algorithm to avoid line-line intersections

While I was looking around for ideas to speed it up I found this topic on GameDev: http://www.gamedev.net/community/forums/topic.asp?topic_id=544523

which linked to this awesome soft-shadow implementation: http://www.andrewrussellstudios.com/blog/dbp09-complete/       Cool

It makes me want to have a go at soft shadows, but I'm hesitant to begin because I know it'll take so long to get right.

I also tried to make a version out of LWJGL since I was getting frustrated with java2D's slow performance when it comes to translucent fills. But I don't know how to fill concave polygons. I looked at how Kev Glass's Slick API does it, and it seems to triangulate/tesselate the polygon in software before rendering. But then some seem to use GLUT to triangulate automatically. Can anyone help?

Thanks  Smiley
Keith

Offline h3ckboy

JGO Coder


Medals: 5



« Reply #55 - Posted 2009-11-14 10:37:57 »

yeah, it would be awesome if you made it using slick Grin. Make it much easier for some of us to use lol.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #56 - Posted 2009-11-16 05:05:24 »

I've reposted a faster version which
- minimises calls to Math.sqrt (by using distanceSq rather than distance) and Math.atan2. I tried Riven's FastMath class too but it turns out that the innacuracies cause errors in the algorithm.
- classifies occluding polygons into a quadrant based on its position relative to the eye (or light source) which allows the algorithm to avoid line-line intersections

While I was looking around for ideas to speed it up I found this topic on GameDev: http://www.gamedev.net/community/forums/topic.asp?topic_id=544523

which linked to this awesome soft-shadow implementation: http://www.andrewrussellstudios.com/blog/dbp09-complete/       Cool

It makes me want to have a go at soft shadows, but I'm hesitant to begin because I know it'll take so long to get right.

I also tried to make a version out of LWJGL since I was getting frustrated with java2D's slow performance when it comes to translucent fills. But I don't know how to fill concave polygons. I looked at how Kev Glass's Slick API does it, and it seems to triangulate/tesselate the polygon in software before rendering. But then some seem to use GLUT to triangulate automatically. Can anyone help?

Thanks  Smiley
Keith


Yeah, you're going to want to divide the polygon into an array of triangles, and then you can use glDrawArrays(GL_TRIANGLES, myVertices, myTriangleCount) in order to draw the polygon with one draw call. Basically you can do this using a pretty simple algorithm where you find vertices that have obtuse angles and then draw triangles to every other vertex from that one. Have a look at this:

http://www.learner.org/courses/learningmath/geometry/session3/part_c/dividing.html#c5

See my work:
OTC Software
Offline CommanderKeith
« Reply #57 - Posted 2009-11-16 05:38:29 »

Thanks a lot Eli, that's a big help. So I take it that's the fastest way to get OGL to fill a concave polygon in a solid colour, but what about to do a tricky gradient fill, doesn't that require you to specify boundary edges? I've got no idea how to do that.

I actually posted the same question over at the lwjgl forums (http://lwjgl.org/forum/topics/changelogs/3112/msg/17153/view.html#msg17153) and have been researching the problem for a while. It seems that maybe openGL can do the tesselation in hardware which I assume might be better/quicker?

Thanks,
Keith

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #58 - Posted 2009-11-19 16:25:25 »

Thanks a lot Eli, that's a big help. So I take it that's the fastest way to get OGL to fill a concave polygon in a solid colour, but what about to do a tricky gradient fill, doesn't that require you to specify boundary edges? I've got no idea how to do that.

I actually posted the same question over at the lwjgl forums (http://lwjgl.org/forum/topics/changelogs/3112/msg/17153/view.html#msg17153) and have been researching the problem for a while. It seems that maybe openGL can do the tesselation in hardware which I assume might be better/quicker?

Thanks,
Keith
Hm, that's a good question. I wouldn't be surprised if you can do it in hardware - I've mostly messed with OpenGL ES (stripped for mobile devices) so I don't know about a lot of the upper level capabilities it has. In my experience glDrawArrays is fast (and usually faster than glBegin and glEnd) and probably the fastest option if you're not using textures or normals (in which case you should probably use glDrawElements). But like I said I'm no expert on OpenGL's full capabilities - so I could very well be wrong.

Eli

See my work:
OTC Software
Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #59 - Posted 2009-11-19 16:38:48 »

GLU utilities and in particular triangulation of polys is usually not done in hardware. For the simple reason the hardware only knows about triangles (and perhaps quads). As for NURBS and other "evaluators", i have no idea, nobody seems to talk about them anymore. 

There is however geometry shaders for newer hardware. But triangulation sounds like a bit of overkill for something that only needs to be done once.

I have no special talents. I am only passionately curious.--Albert Einstein
Pages: 1 [2] 3
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

radar3301 (11 views)
2014-09-21 23:33:17

BurntPizza (28 views)
2014-09-21 02:42:18

BurntPizza (19 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (27 views)
2014-09-20 20:14:06

BurntPizza (30 views)
2014-09-19 03:14:18

Dwinin (47 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (102 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!