Help Wanted. Math Fun.

[Argh]

I need an algorithm that will get every heightmap square a,b within a polygon formed from 2D points in a table.

Preferably should have a version that handles concave and convex shapes, since convex is considerably more CPU time.

If anybody here with the experience with creating these sorts of algorithms would be willing to contribute one, I need this for my mini-project of the week.

I suspect that this is very close to the algorithm I need, but this is well outside my area of expertise:

http://www.ecse.rpi.edu/Homepages/wrf/R ... npoly.html

[smoth]

what are you asking for? Sounds like some basic trig

[Evil4Zerggin]

This is essentially the same problem as filling the pixels of a polygon on the screen, look for that, e.g. scanline polygon fill algorithm. I think the method in your link is the standard method for doing so.

[Argh]

I think the method in your link is the standard method for doing so.

I think so too, but I'm not sure how to apply it to my table of points.

Basically, I'm using some invisible Pieces to get some X,Y coordinates in worldspace, and I need to take those X,Y points and perform that algorithm on them, to obtain the resulting heightmap points as shown in the diagram.

[Argh]

C'mon, people.

It's for a good cause. I have most of it working already, although it looks like I need to talk to certain people about the borked shadowmap projections again.

[smoth]

Cool stuff argh for the first time, I really think I can say that you have really done something groundbreaking in the engine!

so grats

[Gota]

How is that working?are those some sort of features or something?

[Evil4Zerggin]

I added a Google search link (repeat) to my last post, I don't know if it was in time for you to see it. I'm not sure which has the best explanation (this one looks pretty straightforward at least) but they all describe the same thing; I'm sure you can figure something out. Just replace "pixels" with "heightmap squares" and "screen edge" with "map edge".

[Niobium]

That link you posted shows exactly how to do it... So what are you actually asking for here?

[Argh]

I really think I can say that you have really done something groundbreaking in the engine!

Well, thanks. Personally, I thought rewriting Kloot's GLSL so that it would run on my hardware and on ATi was a lot more challenging than this mini-project, tbh.

And zxswg deserves the main credit anyhow, for going ahead and writing the first demonstration of these ideas on the engine. I guess you missed that screen he posted. I just decided that if he'd gotten it done to that extent, I should probably figure out how to get it working in a way that's actually feasible.

I should say, also, that this is not some panacea, nor a real breakthrough, in terms of polish.

It has serious problems with the engine (see shadowmap projection issues, etc.) so it's more of a technical stunt than a practical approach to building maps atm, unfortunately. I can mitigate the errors by doing some tricks with the drawing (get rid of the shadowmap pass for the unitIDs used to generate the objects, for a start) but there are other issues, like the fact that none of the ARB shaders designed for SMF work when the map isn't being drawn (which is stupid, since the heightmap's still there, but whatever, that's a feature request).

All that said, it could probably become a credible alternative to SMF... if the engine can be adjusted in a few ways, and people built enough tiles, and we had some better tech for a few things. Meh, I'll talk about that stuff later.

That link you posted shows exactly how to do it... So what are you actually asking for here?

I am asking for some hand-holding, basically. I don't know how to translate that from C to Lua, the syntax is completely different.

OK... source...

Code: Select all

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
	 (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

Arguments:
nvert = Number of vertices in the polygon. Whether to repeat the first vertex at the end is discussed below.
vertx, verty = Arrays containing the x- and y-coordinates of the polygon's vertices.
testx, testy = X and Y coordinate of the test point.

So... for example... how would I express this in Lua?

Code: Select all

for (i = 0, j = nvert-1; i < nvert; j = i++)

And what does *vertx mean? Does it mean it's a member of that array? I know it may seem stupid, but I really don't know how to translate this into Lua, which is the primary problem here.

[smoth]

And zxswg deserves the main credit anyhow, for going ahead and writing the first demonstration of these ideas on the engine. I guess you missed that screen he posted.

I am aware of his work but that doesn't mean that you have not done something good.

[Niobium]

Code: Select all

local function pnpoly(vertx, verty, testx, testy)

	local i = 1
	local j = #vertx
	local c = false

	while (i <= #vertx) do
		
		if (((verty[i] > testy) ~= (verty[j] > testy)) and (testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i])) then
			c = not c
		end
		
		j = i
		i = i + 1
	end
	
	return c
end

There you go. I even tested it, works with convex/concave/vert/horz lines etc.

[imbaczek]

if you'll have many such polygons, you'll need a BSP tree or something similar. in that case, read how doom works.

[knorke]

for (i = 0, j = nvert-1; i < nvert; j = i++)

<->
i = 0
j = nvert - 1
while i < nvert do

• j = i
  i = i + 1

end

*vertx is a pointer to the array, its used to pass it into the function. members would be like vertx[0] for the first item and vertx[99] for last, if you have 100 titems.
disclaimer: not sure if doing it rite at all, i just googled "lua editor" and messed around but it seems to give the same output.

edit:
pfff too slow. but its colorfull.

[Master-Athmos]

if you'll have many such polygons, you'll need a BSP tree or something similar. in that case, read how doom works.

Hmmm ... why?
He just needs frustrum culling. BSP-trees are only there not to render something behind what you can see. That is if you're in a room the BSP-tree makes sure that the entire level behind that room (which you cannot see) doesn't get rendered. As we're talking about a RTS engine with a top-down view there'll be just a single layer of tiles but nothing behind them you want to be excluded from rendering. Even if he'd want to do a second layer for e.g. underground tunnels he wouldn't need BSP but just a switch to change between rendering either the terrain or the underground level...

[manolo_]

if thats what i believe, it would become AWESOME

[Argh]

KK, Niobium's code appears to be working. Thanks for the help, people!

More when I have actually gotten something done, content-wise, and I'll release a demo / source when it's not fugly.

If anybody wants a further challenge... I need a way to build a heightmap ramp using an arbitrary set of 4 points, so that we can have ramps that aren't just simplistic between heights.

[smoth]

look to ca, it has ramp building stuffs.