# Complex 3d forms on the fly

## Recommended Posts

I'm working on designing a space strategy game(still deciding between turn based and rts... i'm thinking turn based with real time battles). Anyhow, one of my key decisions at the moment is to go 2d or 3d. One system I want desperately to include is a border system. Basically after you've explored so much unclaimed space you're able to declare it to be under your ownership until someone tries to take it. The problem is this: I want to do the game in 3d, because so far I haven't thought of any other major difficulties in doing it 3d as opposed to 2d other than the border system. If done as a 2d game I'd be using a hexagon based system that would be all but invisible to the player. However with 3d I'm unable to figure out how I would draw the border. The way I want the border to look is basically a growing line or field around friendly territories (or enemy) whenever the player pushes a button to turn it on (not on all the time mind you). I've figured out how to calculate the points involved, but I haven't yet figured out how to connect them. Obviously I can look at it and say "start here and go here", but I haven't figured out a valid algorithm to connect the shapes. Here's a two dimensional example. The X's represent points around the far left star I would want to establish a border around. If I could figure out the principles behind drawing the shape in two dimensions I can't see the principles being much more difficult in three dimensions. I've practically beat my head against the wall trying to come up with an algorithm to figure out what order to connect the points in. After I figured out the order I assume I could string together some triangle strips to actually draw the thing (but I'm not 100% on that either). I would gladly accept someone else's infinite wisdom on the most efficient way to do this. Thanks all.

##### Share on other sites
Sounds like you need to calculate the bounding hull from a bunch of points. While thats not too hard in 2d, its really quite tricky to do in 3d. Perhaps QHull could save you some time.

##### Share on other sites
To connect the points in 2D, I would determine the Z-value of the cross product from an arbitrary starting point to each of the other points, then loop through them in order (starting and ending with the selected starting point).

Of course, that only works in two dimensions. It may be possible to use a similar method with higher-dimensional products, but I don't know how you would get polygons out of that.

-rc

##### Share on other sites
OrangyTang
-Thanks for a fast response! I will look into QHull. Depending on speed it seems like it's something I could use. Otherwise, I may have to try other alternatives to achieve the end results I want.

RabidCow
-Also thanks for a fast response. Just for my own enlightenment I would like to understand the explanation you have given me. Would you mind giving a detailed example?

Thanks again!

##### Share on other sites
If your 2d points all lie on a single plane in 3d, you could create a copy of the 2d polygon and move it along the normal of the plane, then connect the points. Or you could try subdividing the 2d poly in to triangles?

just my 2 pennies!

##### Share on other sites
Unfortunately, if I go with a 3dimensional solution I'll have more than one plane.

I also had another thought. How taxing are the spherical shapes that can be automatically generated in directx on the processor? My thought is simply to generate a sphere of influence around around systems and space stations rather than worrying about complex shapes.

The trouble I can see is if something interupted the sphere. For instance if I had a spherical boundry of control around a sytem, but a neighboring system became controlled by an enemy empire then the boundry would be "squashed" on one side only. In that situation I would need a way to slice the sphere or flatten it. Keep in mind this doesn't have to be done in real time if I'm doing a turn based system. Hrm :/

Thanks again for all the help.

##### Share on other sites
Hi,

Just some random thoughts...

Why not always treat the border as a 2d overlay on the 3D view. That is project all the points that make up the border and join them up in 2D. Evreytime the camera moves you update the border based on the new projected positions.

Alternatively how about a metaball scheme, each ball based on a planet or territory owned. You'll proberbly need to predetermine the effective range/radius of each metaball per planet, so that they can link up with neighbouring ones. An advantage of metaballs being you can have positive or negative space, thus accurately describing the border with neighbouring enemy territories.

##### Share on other sites
noisecrime -
I love both of your ideas. I had briefly considered projecting it as a 2d image over the current 3d display, but i'm not sure how clearly you would be able to see the border. I would have to experiment and find out. Of course, I still need to figure out how to connect 2d points (which I haven't quite got a grasp on yet).

The meatball idea was kind of what I was getting at in my previous post talking about the spheres around each body or station. As seen above the trouble is if I have something that would restrict the border on one side. An example below.

I would need some easy way to deform the shapes. Again thank you everyone for helping.

##### Share on other sites
Ooo, metaballs, now theres a good idea. :) A 2D only solution wouldn't be much good I think, since it only provides a visual indication, you wouldn't actually be able to use it for gameplay stuff as that would require finding the proper 3d solution.

Theres a good article on metaballs on gamasutra, which covers calculation and rendering. Or you could improvise and project your metaballs' fields onto your viewing plane and solve it in 2d as well (and solve the actual equations at a point for gameplay stuff).

##### Share on other sites
HAHAHAHAHAHA
I can't believe it. I totally read that as MEAT balls instead of metaballs. I just assumed it was analagous. I'll check out the article. Thanks everyone.

Edit:
I haven't found the article on gamasutra yet, but I have found some information on metaballs. First reaction: O_o

I may have to crack a mathbook or two on this one. I'll keep working at it though. Once again... thanks.

Edit again:
Read the gamasutra article. Once again O_o
Anyway I do think this is a very viable solution to my problem... IF I can understand it and apply it practically. I want to get a working rendering example before I decide on it. I get the feeling it's going to be hard to find too many code examples.

[Edited by - Jackbunny on September 3, 2004 9:59:10 PM]

##### Share on other sites
Metaballs or meatballs which ever you prefer ;)

Persoanlly the best resource I found was
http://www.astronomy.swin.edu.au/~pbourke/modelling/polygonise/

Its a straight forward implementation, relatively easy to get ot grips with, but not very optimised.

Taking it a step further with some good optimisations is this (DX version I think) demo and source code
http://www.angelcode.com/dev/metaballs/

About the border issue, how different do you want it from the image you posted? To me that image looks perfectly valid if each plaent is controlled by different players. Its late and I can't quite visualise what would happen in this case if you used a negative value metaball on the enmey planet. I imagine it will cut into the players border, but wouldn't be flat.

Then again can't you just let the player border encrouch on other borders, the overlap would be no-mans land. As long as the metaball never encompasses an emeny planet.

OrangyTang:
Why do you say the 2D version wouldn't be usable in game? I don't see what the problem is, other than of course the 2d border changing as the camera moves, might cause some artifacts or popping. What am I missing?

##### Share on other sites
I'm not dedicated to image I posted. It was just an example to show what I was getting at. Overlapping is a possibility as is negative space. Actually overlapping might be ideal.

The important thing I want to get to is to be able to declare a 3d border that makes sense and is extendable (by use of space station) in order to set up trade embargos and other such controls.

I'm liking where this is going if I can work up the technical details. I haven't even started working on the graphic engine... all design up to this point. I was hoping if I could get a lot of back end code done and most of the design I might find some support for the graphics part of the engine.

BTW if you didn't see my edits to my above post ^^^ there they are.

##### Share on other sites
Hi again,

Not sure why, but i was intrugied by this problem, so i dug out some old 2D metaball code and played around to see how it worked.

Sadly I don't think it really matches with mine/your expectations, at least not without a considerable amount of tweaking. I've included a jpg of a series of quick tests i did.

Image

Each row represents a single test, the first image per row shows 6 planets and the border field generated by them. The subsequent six images show the border field when one planet is made an enemy. The first and second row unfortunately had the planet field influence set to a random range, which skewed the results somewhat, the final row has each planet with the same amount of influence.

The first row shows just how badly metaballs will work with simply setting the enemy planet to a negative charge/influence. I then decided when displaying the players border that the enemy influence would be divided by 16 (arbitary number), this worked better as can be seen in row 2. However row 3 looks better due to allp planets having the same influence value.

So no real answer to you problem in the images, but hopefully they show the issues you'll need to address.

However more importantly I realised that this system is most likely inappropriate for the problem especially in 3D due to the number of polygons that will have to be generated. You can tell by the 2D version that the border needs a fair number of lines to build (that would escalate in 3D with polygons)and this is at quite a low grid resolution.

3d Metaballs are pretty intensive polygons wise for optimal smoothness. In your case though i imagine the actual size of the metaball space is going to be extreme (being in space) and will require a high resolution grid to produce anything like a smooth border. It may still be worth investigating as metaballs are usually generated in 1 unit volume and then scaled up (simplifies some of the maths) and the resolution can be changed on the fly. So you may find some acceptable level of resolution vs polygon count.

I do think the metaball system has some merit, however i'd definetly investigate doing this as a 2D overlay instead of a 3D mesh for the reasons i give above. There are a number of properties that can be tweaked from the influence/charge value to using positive/negative charges etc.

##### Share on other sites
so there I was a little dejected by the metaballs, so i started thinking about other methods.

How about putting a massive billboard of a circular glow in the middle of each planet/base. It doesn't have to be a bright glow, more a dull blue, something that has a slightly different tone to the blackness of space. I'm not sure what blending you can use to acheive enemy spaces, but maybe something to think about.

edit>>>
O.k thinking about this some more, and I beleive you've set yourself up a very difficult if not impossible task in 3D. I don't mean the game can't be 3D, but the game map shouldn't.

The problem as I see it with a 'true' 3D game map is that when displaying the border you can get into all sorts of problems if say several planets/bases are in a line in front of the camera - what on earth should the border look like then? Should you see the border rings of each planet?

Now a 3D metaballs, might work in this situation, but as I said above I think the polygon count required will end up killing your framerate. Could still be worth testing though

Maybe just go for the easy solution. The game mapi is essentially 2D when viewed from above (or any singular direction). the planets/bases do NOT have to be in the same plane, you just can't have one on top of another (proberbly need some sort of min distance between planets). This way when the player presses the border view key, the camera can sweep up to the overhead view, and you can display a 2D emtaball or alternative solution. When the player releases the key, it goes back to viewing the game space.

well just my thoughts

##### Share on other sites
Thank you for your obviously very extensive thought on the subject. :D I haven't been able to get to the computer for a couple of days. I see the problems you have pointed out with the metaball system.

I've considered the difficulties involved with a 3d star system and overlapping systems. I had already planned on implementing a sytem to prevent overlaps from the default view. I hadn't thought about applying the border system to a 2d view only. That's a rather brilliant idea.

At this point I'm thinking of going with the billboard idea. Using a circular texture on the billboard. Although I'm still not positive what to do with overlap. It'd be nice if I could change the color of any non transparent pixels that overlapped any other non transparent pixels (on the billboards of course). I can't imagine that's an efficient thing to do, however.

Thanks once again for you extremely valuable input.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628385
• Total Posts
2982391

• 10
• 9
• 15
• 24
• 11