My recent projects for procedurally generated 3d levels I started out trying to check whether a point was in a polygon, actually within each triangle. It worked to a point but wasn't perfect so I checked out line intersections which where 100% accurate.
In my code I've stored 3 sets of data arrays, vertex table, edge table and triangle table. All I have to do now is to check the intersections between edges only. At the end of the whole generation algorithm the edge table isn't used (only for creating the wall mesh) but it is the most important during the generation.
Once the base map (ie the floor) has been done, it get's tessellated, copied to the roof and the edges are used to create the walls. And using a noise algorithm the floor is turned into a sloping dungeon.
See here on my current progress:
http://forum.thegamecreators.com/?m=forum_view&t=193276&b=8
I'm at the stage now where the mesh is being created into separate groups so that rendering can be done quicker by hiding sectiond of the dungeon that are too far away.
This is the current line intersection code I'm using:
bool PROC_MAP::line_intersect(float x1, float y1, float x2, float y2,
float x3, float y3, float x4, float y4) {
float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
if ( d == 0 ) return 0; // exit if lines are parallel
// Get the x and y
float pre = (x1*y2 - y1*x2), post = (x3*y4 - y3*x4);
float x = ( pre * (x3 - x4) - (x1 - x2) * post ) / d;
float y = ( pre * (y3 - y4) - (y1 - y2) * post ) / d;
// Check if the x and y coordinates are within both lines
if ( x < min(x1, x2) || x > max(x1, x2) || // REMOVE STL min() and max()
x < min(x3, x4) || x > max(x3, x4) ) return 0;
if ( y < min(y1, y2) || y > max(y1, y2) ||
y < min(y3, y4) || y > max(y3, y4) ) return 0;
return 1;
}
Which is better than searching for a point in a triangle or polygon...
EDIT: One thing to note now if you're going down this route that if you are comparing edges with this method then you might find that a newly generated edge's points might just need "nudging" a little. The source to my code is available on the above page if you want to have a look at it to see what I mean...
Mental arithmetic? Me? (That's for computers) I can't subtract a fart from a plate of beans!
Warning! May contain Nuts!
