Archived

This topic is now archived and is closed to further replies.

AndreTheGiant

polygon representation

Recommended Posts

Ive been reading about BSP trees lately and I think I got the jist of it. I want to try and implement a simple bsp tree engine to see if I can do it. But nowhere did any of the articles I read on BSP trees mention how the polygons are stored. I know that you pick a polygon, and use its plane to partition the rest of the polygons into two groups: in front and behind. But how should I best represent a polygon? A triangle would only need 3 points in space, but for a square (or 4 gon), just having 4 points would be ambiguous because there is more than one way to connect the 4 points, right? So how do the ''pros'' represent polygons? I have a feeling the hardest part of this project is going to be the algorithms on the polygons, such as determining if one is in front of another, and splitting one against another.. etc. Especially if I dont choose the correct representation for a poly. Thanks for any advice. ----- It''''s not my fault I''''m the biggest and the strongest; I don''''t even exercise!

Share this post


Link to post
Share on other sites
While waiting for "pros" answers I can say this:

connecting of points is not ambiguous since you choose which way you do it and do it that way

If you assume that polygon lies in one plane then way which you connect vertices is not important (assuming polygon is convex).

I represent polygon by defining a "track" which is set of connected coordinates. You can make array .. whatever. Then you trianglize it (every time in the same way) and get triangles.
last step - render triangles.

hmmm Im not sure about problems with splitting ... Do you need to consume minimum memory and draw it fast or want to process it fast. Based on those assumptions I would choose my data structure.

Share this post


Link to post
Share on other sites
if you connect your verticies in the order in which they occur, and you store them in this correct order, then there can be no ambiguity even if you have n verticies......

if you wern''t storing them in order you''d have a headache and a half for anything larger than three, unless each point contained some sort of pointer to the next point, or you used lines. But both of those solutions cause problems because you could have invalid polygons, or a billion other problems.

I would say to represent your polys as lists of points and connect the points in a specified order. The only tricky this is complex poly''s that have holes in them, you would need to also contain a list of the inside hole(s).

The other problem with this is storing polys as just lists of points gives you no capability to have curved side(s) on the poly. For example if you wanted a poly in the shape of the letter D you''d have to cheat it, instead of plotting a curve from the top of the I portion of the D to the bottom.

Share this post


Link to post
Share on other sites