Sorry your browser is not supported!

I'm currently working on reworking my A* pathfinding algorithm so that the pathfinding grid is created based on the projection of 3D objects in DarkGDK onto the xz-plane, but in order to generate the projection polygon for each object I need to compute the union of the individual 2D polygons projected onto the plane by the 3D polygons from the object. I've searched online for different algorithms to compute the union of multiple 2d polygons but I haven't found any I can use. If someone could link me to one or explain how to do it that would be great. Thanks

This is what I used to make pathfinding: use Sparky's to check the squares on the "grid" to see if there is collision there ("SC_RayCast()")

The points in my algorithm are not grids, I take the 2d Polygons projected onto the xz plane by the 3d Object an then extend the points out from the vertices of the polygon to use as waypoints. What I need is an algorithm for combining the many triangular polygons to form a single polygon for each object.

For each object, loop through it's vertices, and measure it's distance from the center. BUT, you measure the distance along the XZ plane, so ignore the Y axis. When you have a list of all the vertices, simply take their XZ positions, and there you have a list of 2D vertices for an object.

Haven't tried it, but it sounds accurate enough!

I already have a list of the vertices. What I did is project each polygon from the object onto the plane and store them up in an array. Now I have an array of polygons that will all intersect or border each other. Next I need to know how to take all of these triangles and combine them into 1 single polygon. All I want is an algorithm that computes the union of a set of 2D polygons.

As you are projecting your polygons onto the XZ plane, you should also be capturing the face indeces of the vertices that are making up each polygon. Assumingly, your XZ projection is a flat representation of the 3D object - much like UV unwrapping - therefore looping back through the face indeces and using the appropriate vertices should reconstruct your flat object as a combination of all of the polygons.

To get the union of two 2d polygons, take a point on one polygon which is not inside the other. Then follow the lines clock-wise around the object until you hit an intersection. When this happens, take the intersecting line to the left and follow that round, and continue doing that.

To check if a point is in a polygon, create an imaginary horizontal line from that point to somewhere off to the left, outside the polygon. It is a simple matter to calculate the number of lines intersecting this horizontal line. If it is even the point is not in the polygon

If you know the order of the vertices, it should be easy to move around clockwise, and to determine which way at an intersection is 'to the left' just take one end of the intersecting line, and check which side of the current line it is on.

For algorithms such as line intersection, point on which side of line, etc. there are hundreds of resources on the internet, so google it

I love that! Such out of the box thinking

@ Latch

I honestly didn't understand most of that. I did minimal research on the object meshes and stuff. Mostly just enough to figure out how to get the vertices for each polygon in the mesh and its real-world coordinates. Here is what I'm doing right now to get the triangles: I create an array called Triangles and then read through the memblock of the object 3 verts at a time and save the x and z data. I haven't even gotten to the objects angle yet, but that works the same way rotation works in the standard spherical coordinate system does plus the zangle doesn't it? If you have any suggestions I'd be glad to hear them.

@ Diggsey

That method you described is actually similar to the method I was thinking about trying. Until yesterday I hadn't looked as the polygons as oriented so I never thought about tracing edges and moving outward from the polygons. Since you posted it I'm assuming it should work the way I thought it would, and it naturally solves the problem of filling "holes" in something like a donut. This is the first time I've worked with polygon type stuff since I wrote a simple 3D polygon rendering/camera thing for my 9th grade java class so I'm not all that confident in my theories. And I have been searching the internet and reading some papers but most of the algorithms I came across weren't just simple polygon union and involved all the other stuff such as holes that I didn't want to mess with, so I'm going to try this out and see how it works. THX for the tips.

*edit* nvm

@zotaster

I was thinking about how to do that forever yesterday on the car ride up to my family's cabin and after I realized the number of intersections would determine the points position I almost cried.

I guess what I was saying was, taking UV unwrapping as an example as a 3d projection onto a 2d plane. In an already made 3d object, each face/polygon is made up of vertices. These vertices are indexed in the face information. If you project a 3d vertex onto a 2d plane using the vertex of a specific polygon, the vertex number will correspond to the vertex index of the face. If you keep track of the faces' indexes of vertices, you only have to recreate each polygon in the XZ plane by grabbing the face vertex numbers.

So if triangle 1 came from a cube using vertices 1,2 and 3 which is information stored in the faces indexes, then to recreate triangle 1, you use the 2d vertices that came from the original 3d object. Maybe I'm missing something but it almost sounds like you are ending up with a soup of vertices and you are trying to figure out how to tessalate them. Your polygon information in terms of which vertices make up the polygon is already stored in the 3d object mesh information. If you project vertex 1 from XYZ to simply XZ, it's still vertex 1 . No?

But doesn't each set of three vertices withing a memblock refer to a specific polygon on a mesh? The darkGDK documentation doesn't say anything about the the face data seperate from the vertex data and this seems to be the way its done in kelindinbrae's memblock matrix so I assumed it was standard...

I'm probably just misunderstanding your goal. I'm thinking you are taking a 3d model of say a house or a terrain or something and projecting it onto a 2d plain - kinda like unwrapping the polygons of a model for texturing - basically flatting it out . Each face or polygon is made up of vertices. No mystery there. Whether the polygon/face is in 3d or in 2d, it is still made up of the same vertices, though their individual x,y, and z compenents will be different. Perhaps this doesn't apply to DarkGDK but I assume it does if you can make a memblock out of a mesh - if a 3d mesh is made into a memblock, the memblock stores the vertex numbers that make up the individual polygons/faces in the face information. The actual vertices are stored elsewhere and these vertices are referenced by the face data so it can tell the mesh how to build the 3d object. If you project a 3d object onto a 2d plane, face 1 on the 2d plane is still going to be made up of the same vertex numbers as face 1 in the 3d mesh. So you don't have to calculate which vertices to use to make the new polygon. If two polygons are sharing the same vertex, then that's going to be in the face indexes.


Not necessarily. You could, for example, have a disc where vertex 1 is in the center of the flat top of the surface. A series of triangles could be created from the outside ring to vertex 1 to create the surface of the disc. There could be 100 triangles each refrencing vertex 1. Vertex 1 IS NOT constantly repeated as a set of cooridnates every three vertices. It's only created once in the series of vertices and then referenced by the face indexes.

Maybe you are just starting off with a soup of vertices that have no polygon order and don't come from an already made 3d object. Maybe that's the difference in what I'm suggesting and therefore doesn't apply.

Kelebrindaes memblock matrix builds the matrix from a soup of vertices that are caclulated based on the size of the matrix. The soup has a specific order so they are easy to manage. The method of polygon creation that kelebrindea is using is to create each tile with it's own set of vertices to allow greater flexibility with the texturing control of each matrix tile. This increased flexibility increases the number of vertices beyond what is necessary to just create the matrix itself. A 2x2 memblock matrix created by kelebrindae's method uses 16 vertices. If you were to build the memblock matrix without needing such precise individual texturing control for each tile, you could use 9 vertices. You would still have texturing control, but it would be global for the whole matrix instead of local to individual tiles.

The method of unioning all the polygons of the vertices should be basically the same if you are staring with a non-tessalated soup of vertices. I was just trying to save you some time by telling you to just grab the polygon information out of the face-vertex indexes to build your XZ mesh.