Triangulate Them Polygons!
Blitz3D Forums/Blitz3D Programming/Triangulate Them Polygons!
| ||
| Hi, I just put up in the code archives my source to my triangulate polygon toy thing-a-ma-jigger. I really did find this interesting and hope mabie by sharing this that somebody may actaully one day figure out my coding style and learn from it in some way. Props to Fredborg for supplying the link to the source of PolyTri! I had fun doing my version. This is pretty much all I'm going to do with this code. Hope ye likes! :) http://www.blitzbasic.com/codearcs/codearcs.php?code=816 edit: oh, It basically demostrates triangulating points of a polygon that you plot. The plane that the points are on can be at any orientation. Don't forget to plot your points in a clockwise orderly fashion. |
| ||
| Hi Todd, That's pretty nice :) I'll release the PolyTri one, in a few days, it's a bit more flexible than yours. (Or at least I think it is ;) |
| ||
| I realized that I wasn't coding it in a way to make it more "plug-n-playable". So, I just went ahead and made it into a little toy like thing just so I can see the results faster. I think I may have overdid my 3d maths a bit, but at least I have a better understanding of it now. Definetly looking forward in seeing your version! :) |
| ||
| I dunno why, but I like stuff like this. But, the question is: what are you guys using it for? |
| ||
| Personally, It's going to help me in my CSG boolean operations when splitting polys. Also, it's perfect for me to "automagically" create standard proper convex/concave shaped portals for use with occlusion culling. |
| ||
| I've been playing around with occlusion culling as well. Currently I extract the edges that makes the outline of my occluding object and then I "create" planes using the vertices of each edge and the cameraposition. Then I simply check if entities are behind each plane(Just like frustum culling, but reversed). The problem I have is to order the edge vertices by clockwise order. Currently I'm using Grahams method using the angle to each point to sort them, but it's not working well when two points are too near to each other. The occluder is made by creating a very simple convex hull around the "carefully" selected entity. It wouldn't be good to use every entity as an occluder as it would slow down the occlusion test to a point where it would defeat it's own purpose(to get better framerates). A house or a hill are examples of good occluders while a bush or a small rock are bad occluders. Also, the occluder must be a certain distance from the camera before it's used in the occluder test. An occluder that is too far away wouldn't be worth testing(I think you know why). By the way, the edge extracting is a simple way to outline an object with black edges by simply drawing black line between the edges vertices, however the line command slowed down my application ALOT and so far I only got it to work with convex objects(spheres, boxes and cylinders). |
| ||
| Thats what I'm working out on paper at the moment too for my CSG operation's triagnle edge splitting part where I need to keep new vertices in clockwise order for each new poly. |
| ||
| Sweenie, if I was doing something like creating an outline of an object with extracted edge vertex points to create planes with, I would do something like this: Since an edge point of triangle should connect to another edge point of the adjacent triangle I would take the first extracted edge and compare it's edge points with the second extracted edge points. Then store them in a clockwise order in a list. Then take the second triangle edge points and compare them to the third triangle edge points and store the new points in the last of the list to keep them in clockwise order. And so on... basically in a syncronise order. Ofcoarse, this idea is working on the idea where you pick the triangles that have the needed edges in a clockwise order in the first place. If you can do above, then you can easily use a triangulation method against those new points like with what I did for my triangulation toy program. Hopefully, Fredborg will have a nice easy plugable triangulation code here soon if you need that or you can roll your own. Hope that may spark an idea or two for ya... |
| ||
| Todd have you looked at my CSG stuff yet? CSG Function It has a triangle splitting function, along a plane. |
| ||
| Yes, I did look at it some time ago. You did a very nice job with it indeed. What I'm doing is trying to learn the process of coding CSG myself and I am doing it in C/C++ userlib functions. If I remmeber correctly, your csg functions where sort of like WorldCraft csg where the object's polygon faces where facing outwards. I remmeber doing something with the code you provided to get the csg to act like maplet's csg and it basically worked. But, I remmeber where if you csg in the same spot, the csg would add polygons then on the next same csg operation it would delete polygons ( and so on... ) on the coplanar plane where one side of each object would share. Basically, I just decided to start from scratch and roll my own. Now, I am finally doing it for my level editor I'm working on. Edit: ok, I might do it in C/C++... depends if my csg ops are fast enough in blitz. |
| ||
| My triangulate toy code is a little bit cleaner now. Took out some left over unused variables. Plus, I had fixed a message that needed to be displayed when you step through the triangulation process with your space bar. |
| ||
| My method might not be the best, but here is how I do it. First I build a list of all unique edges in the mesh. Every edge belong to two triangles so for every edge I store the index to these two triangles. Then, in the mainloop I iterate through each edge and do a backfacecull of the two triangles. If one triangle is hidden and one is visible I got myself an outline edge. To make sure that the edge is clockwise aligned, I simply perform a trianglearea calculation using the two vertices of the edge and the midpoint of the mesh. Since the outline is a 2D-shape I do the triangleareacheck in 2D, that is, the vertexpositions and midpoint is projected to screencoordinates before doing the calculation. If the trianglearea is negative I flip the vertices(or rather the variables that holds the vertexindices) Finally, I create the planes using every edge and the cameraposition. I just got it working last night, but was to tired to test if this really gives me a speedboost.(Can't wait to get home)... By the way, the meshes I use for occluding must be convex, solid and have shared vertices. It can have "unshared" vertices if I rewrite the code that build a list of edges.(Maybe later) Tonight I will clean up the code(quiet a mess right now) and try to optimize the code(At least I will try) and then I will post the code. |
| ||
| By the way Todd, do a googlesearch on "giftwrap" and "convex hull" and you should find some pages with good reading. |
| ||
| Yup, I know about convex hulls but they limit me because of it's convex nature. Try ploting points in a shape of an "S". You wont end up with a solid "S" shape because it's properties contains concave attributes. I haven't heard of "giftwrap" yet though. I did try to search for it on google but came up with bunch of personalized gifts type links. So I gave up quickly on that. Good to hear that you got it working last night. Looking forward in seeing your code in action. :) |
| ||
| Giftwrap is one of the many methods to get the convex hull and you get the points in clockwise order too, but you are absolutely right that this is worthless when you want concave shapes. By the way, wouldn't it be easier if you draw lines between every new point you add. That way you get a kind of "preview/outline" version of what the triangulated object would look like. The user can also see directly where the points shouldn't be placed. You could also prevent a new line(point) from intersecting another line(could be an optional feature) |
| ||
| Yeah, I should of done that. I'll go ahead and put lines in there and put in my line intersection code to help not cross edges like that. It crossed my mind before, but I was just lazy. It'll be later on today or tommorrow before I add that. Right now I need to finish up my CSG stuff. |
   |