Nice one.
I might test this algorithm in my rasterizer to reduce the massive overdraw.
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.
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.
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.
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).
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 
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:
// 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;
}
}
}
}
}
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.
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.
Very cool Orangy Tang! I found two bugs (red dots are where the mouse was):
http://n4te.com/temp/sight.gif
Left is the mouse on a vertex. Right is mouse on the left edge.
i have wasted the last 30 minutes trying to replicate the bugs mentioned above but no luck
seems perfectly made here
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.
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?
I knew there’d be an edge case or two that I’d missed, cheers. 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.
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/ 8)
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
Keith
yeah, it would be awesome if you made it using slick ;D. Make it much easier for some of us to use lol.
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
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/index.php/topic,3112.msg17153.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
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.