2D Map to Donut, 3D map to "strange 4D object"

Anything and everything that's related to OGRE or the wider graphics field that doesn't fit into the other forums.
Post Reply
madtulip
Halfling
Posts: 78
Joined: Thu Nov 18, 2004 6:35 pm
Contact:

2D Map to Donut, 3D map to "strange 4D object"

Post by madtulip » Tue Mar 15, 2005 8:19 pm

if we take a look on a 2d world, like sid meiers civilisation representing the earth, but still beeing a square there is the option to leve the map on the left and return to the map on the right (a sphere world). you see some problems with converting a square 2d map to such a sphere, the north and southsides of the world. therefor its also possible to "donut " the world, rather then sphere it, so you can also leave the map north and reenter the map from the south. so 2d map gets 3d donut, mathematicaly.

what about a 3d world with the same options ? i would like to leave the cube my world is in topside and return from the bottom, left and return from the right, and front and return from the back.

i could just

Code: Select all

int minimum = 0;
int maximum = 1000; // i.e. the x dimensions of my world

if (pos.x <= minimum) // if we leave the one end
{
pos.x = maximum; // return from the other
}
but that would lead to some problems
1: im a ship in space, and i dont want to recognise the boarder by suddenly jumping directly into objects when reentering the cube. the ship must be able to "see" over that edge of the cube that it is passing soon.

the 2D to sphere and 2D to donut problem

even if i can see over the boarder, my cube would have 6 adjectant cubes, all containing the same objects as the first one. what if i leave the cube not directly through one side of the cube, but through one of the 2d or 3d edges he has got ? and even worse. how to look over into thoese diagonal adjectant cubes ? that would lead to 3*3*3 = 27 cubes, only to fake the effekt of this one middle cube 4d donut world.

is there maybe a scenemanager parameter i could simple call to tell him i want to simulate a 4d donut world and get rid of this in my eyes and approach horribly performancekilling rpoblem ?
0 x

Phonomania
Kobold
Posts: 26
Joined: Tue Sep 14, 2004 12:56 pm
Location: israel
Contact:

Post by Phonomania » Tue Mar 15, 2005 10:21 pm

i think you dont have to use too much geometric imagination here(cube , donut 3d , 4d etc). all what you describe can be achieved with 'endless terrain' thing. read PLSM2 threads or ask Tuan Curanes about it .
0 x

User avatar
:wumpus:
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 3067
Joined: Tue Feb 10, 2004 12:53 pm
Location: The Netherlands

Post by :wumpus: » Wed Mar 16, 2005 12:50 am

This is called 'periodic boundary conditions' and currently none of the publicly available Ogre scene managers use this as it's generally not very useful.
I'm not even sure the standard algorithms like quadtree, octree are usable in this scenario.
If you insist on this you'd need to write your own scene manager (you can copy a lot from Octree probably) that handles visibility of objects differently near the edges.

You can also wait for the portal scene manager to be available (I believe pjcast is working on one), then you can make the sides of the cube portals.
0 x

madtulip
Halfling
Posts: 78
Joined: Thu Nov 18, 2004 6:35 pm
Contact:

Post by madtulip » Wed Mar 16, 2005 11:43 am

@ wumpus, thats what i wanted to know. thx. the bad thing is that im in c++ for about 4 weaks in a row now and i dont think ill be able to build my own scenemanager (im just yet dealing with the concept of 3d to 2d conversion and rayquery).ill think ill put that problem at the bottom of the todo stack. maybe Tuan Curanes come here and has a solution.maybe this sort of scene manager is avaible some day, maybe im able to build one myself later, much later :) thx.
0 x

betterhere
Gnoblar
Posts: 9
Joined: Tue Mar 15, 2005 5:41 pm

Re: 2D Map to Donut, 3D map to "strange 4D object"

Post by betterhere » Wed Mar 16, 2005 6:04 pm

If the point of view in your strange 4D world is near the corner and you look into the corner, wouldn't the view look like a kalidescope(SP?!) image? I don't really think your strange 4D object would work as you imagine. I think what you want is a world where if you have two adjacent sphere objects, and they start heading in opposite directions, they will end up hitting each other on the opposite side of contact they started with. I think that is a power of 10 more complicated than a doughnut world! And I am brand new to OGRE but its a safe bet it can't be done on it. I would imagine it would take a good team of physics experts and a 500Ghz machine.,

Maybe you should just make a literal doughnut shaped boundary to your world.
0 x

User avatar
DWORD
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 1365
Joined: Tue Sep 07, 2004 12:43 pm
Location: Aalborg, Denmark
Contact:

Re: 2D Map to Donut, 3D map to "strange 4D object"

Post by DWORD » Wed Mar 16, 2005 6:18 pm

betterhere wrote:(...) I think that is a power of 10 more complicated than a doughnut world! And I am brand new to OGRE but its a safe bet it can't be done on it. I would imagine it would take a good team of physics experts and a 500Ghz machine.
Huh?! :shock:

I think all madtulip wants is a cubic level which wraps around at the edges, so when you walk out one side of the cube you end up on the opposite. The 4 dimensional object is just a way to imagine the connection between the edges if I understand it correctly. I would say it's a safe bet that it's possible to do this in Ogre, but you'll have to implement it yourself as :wumpus: mentioned. ;)

Edit: If what you meant was that it would be necessary to render an infinite amount of identical levels, I don't think that is necessary. If the level is any big, it'll probably be unnoticeable if you just render one extra copy in the directions where you can see into the other sides of the level.
0 x

User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
Contact:

Post by jacmoe » Wed Mar 16, 2005 6:29 pm

It could probably be made up using the paging landscape scene manager -> using multiple pages of the same page (so to speak) .. :)
0 x
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.

User avatar
Attis SH
Kobold
Posts: 28
Joined: Sun May 18, 2003 9:42 am
Location: Budapest, Hungary

Post by Attis SH » Wed Mar 16, 2005 6:31 pm

Why don't you convert the game to use a spherical world? The drawback of a spherical world is that it is only really useful with hexagons. In my project I have an icosahedron based spherical world which is being drawn using 10 terrain patches.

Is the donut approach so useful? I agree that it would be cool to play on a torus world, and also the 2d->3d conversion is interesting. Another similar approach would be to use a Ring World like in Larry Niven's book or in the game HALO.
0 x

betterhere
Gnoblar
Posts: 9
Joined: Tue Mar 15, 2005 5:41 pm

Re: 2D Map to Donut, 3D map to "strange 4D object"

Post by betterhere » Thu Mar 17, 2005 4:14 am

DWORD wrote:
betterhere wrote:(...) I think that is a power of 10 more complicated than a doughnut world! And I am brand new to OGRE but its a safe bet it can't be done on it. I would imagine it would take a good team of physics experts and a 500Ghz machine.
Huh?! :shock:

I think all madtulip wants is a cubic level which wraps around at the edges, so when you walk out one side of the cube you end up on the opposite. The 4 dimensional object is just a way to imagine the connection between the edges if I understand it correctly. I would say it's a safe bet that it's possible to do this in Ogre, but you'll have to implement it yourself as :wumpus: mentioned. ;)

Edit: If what you meant was that it would be necessary to render an infinite amount of identical levels, I don't think that is necessary. If the level is any big, it'll probably be unnoticeable if you just render one extra copy in the directions where you can see into the other sides of the level.
The original post said "the ship must be able to "see" over that edge of the cube that it is passing soon." I take that to mean seeing the "other side" of the world before hitting the boundary of the cube. But, lets say you are looking at the corner of the cube. In the multiple cube scenario, you would be able to see parts of 7 different cubes. The parts you would see would not look like a smooth transition to the other side. It would look like a fragmented mess. Trying to sort that math mess out for the view to be correct would be nearly impossible.
0 x

Bill
Gremlin
Posts: 167
Joined: Sun Sep 26, 2004 11:50 pm
Location: Arkansas

Post by Bill » Thu Mar 17, 2005 5:31 am

The parts you would see would not look like a smooth transition to the other side. It would look like a fragmented mess.
I think you could make is smooth. It's just like a repeating texture; you just have to make it the same on each side. If it's a space game than it's easy, you just have nothing at the boundary and it will all match up.

I don't think it's that hard mathematically either. You just have to render all the bits from all the appropriate portions of the volume. It's just a matter of cutting out all the right bits and translating them to where you need them rendered.
Last edited by Bill on Tue Mar 22, 2005 6:11 pm, edited 1 time in total.
0 x

madtulip
Halfling
Posts: 78
Joined: Thu Nov 18, 2004 6:35 pm
Contact:

Post by madtulip » Thu Mar 17, 2005 12:15 pm

i think i must excuse for my english, there are some missunderstandings here. i dont want to make a 3d world donuts shape. that was just an example of how an infinit 2d world would be created. this is used in praxis by civilisation (the option is even called "donuts shaped world" if i remember correctly). get yourself a donut and a biro. point somewhere on the donuts surface. the surface (not the interior or the air aound it) is the 2d map. now you can draw a line from your staringpoint back to your startingpoint without any break if you just draw into the same direction.i.e. you can draw a circle directly on the topside of the donus, as many times as you want. or you can draw forward and down, then down and backward till you reach the bottomside then up and backward (throug the hole in the middle) and back up and forward till you reach the topside again.i both cases you can draw a line constantly in the same direction that returns to its staringpoint.

its obvious that if a 2d infinit space is 3d a 3d infinit space must be 4d, at least if you want to use that biro methode(if you could in 4d space), ofcourse the coordinated on the surface of the donut are not used in a 3d way. they are only 2d.

the thing that im going to do, as long as a scenemanager with better performance then my code will produce isnt avaible:

imaging a 6 sides dice. stack 27 of them to form a bigger dice (3dice*3dice*3dice). the one in the middle that cant be seen from outside,because its all covered with dices, and therefor also cant "look" back at me is my world. all other 26 surrounding dices are exact copys of my world. they are orientated in the same way as my world (i.e. the "6" is upside and the "3" is backside on any of the 27 dices)

if the dice in the middle (my world) would look from its side "6" to the adjectant dice it would see "1" (the oposite side of "6" on every dice (the summ of the oposite numbers on dices is allways 7)) so this way i can see the other worlds, representing the oposide edge of my world (at least an exact copy of it) when looking over "the boarder" of my world. as soon as i walk over the topside boarder of my world i would (in the programm) change the coordinates so that we reenter the world (the middle dice) again from the bottom.think of this for the edges also, its not perleidoskope.

to optimise this i would cut some parts of the surrounding dice away (not placing models in them). i would leave only the sides that face the middle dice and a bit of space behind them. i would leave excatly as much as i could look far when i stand directly at the border of the middle dice, looking over the border but having not crossed it yet. i would save the least space for the dice in the middle of the 3*3 sides that have one side connected to surrounding air and 5 sides to other dice. a bit more for the dice that have 2 side connecting to air and 4 sides connecting to dices and the most for the dices in the corners of the big dice, as i have to leave only maximalViewdistance*3 of space here.

lets say the viewdistance =1

size of the middle dice = (20*viewdistance)^3 = 20^3 = 8000

size of "1 side to air" dice
(20*viewdistance)^2)*viewdistance = (20^2)*1 = 400
nr of "1 side to air" dice = 6
space for all "1 side to air" dices = 400*6 = 2400

size of "2 side to air" dice
(20)*(viewdistance^2) = 20*1^2 = 20
nr of "2 side to air" dice = 12
space for all "2 side to air" dices = 20*12 = 240

size of "3 side to air" dice
viewdistance^3 = 1^3 = 1
nr of "2 side to air" dice = 8
space for all "3 side to air" dices = 1*8 = 8

summ of surrounding dice space : 2400+240+8 = 2648

compared to the 8000 of the middle dice (the world) that are only 33.1%.
so if worldsize would be 20 times as much as viewdistance i would have to operate in 133,1% of the space needed for the world itself to realise this. compared to the 2700% when not cutting space of the surrounding dices this looks rather small to me. maybe its not that performance killer. i gotta check out where to get the value for viewdistance from :)

edit :
so where is the 4d donut ? its not there. but if it was it would save that 33.1% of performace :roll: and that was what im looking for

edit :
the loss of performance should be even less. this additional 33.1% of space wont use the same performance as 33.1% of the real world, because some though methodes like collision detection and such dont have to be performed in that additional space, its only for the "see over the boarder" effekt.things that happen there also happen in the real world smoewhere. so no need to double this, apart from the grafiks

the kaleidoskop effekt would result if the size of the world would be less then the viewdistance.
0 x

User avatar
DWORD
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 1365
Joined: Tue Sep 07, 2004 12:43 pm
Location: Aalborg, Denmark
Contact:

Post by DWORD » Thu Mar 17, 2005 12:48 pm

I think this 3*3*3 dices way suits very well with the octree scenemanager; it would effectively cut away invisible parts of all of the levels. If you set the octree dimensions to surround your 3*3*3 level cubes, and then a suitable depth, I think you can in fact get really good performance.
0 x

madtulip
Halfling
Posts: 78
Joined: Thu Nov 18, 2004 6:35 pm
Contact:

Post by madtulip » Thu Mar 17, 2005 2:11 pm

i dont understand the use of the scenemanager and its internal structure. i guess the octree is responsile for only rendering entities in your cone of view. that would explain the increasing fps when looking into a direction where no entities are.

so dont i use this octree automaticly if i just make my world 133,1% and only use the inner 100%. i would defines zones in the inner 100%. if a node enters such a zone i would simply make a copy of the node and attached entitie and put that replicate at the propper position in the outer 33.1%. if that node then leaves that zone in direction center of the 100% i would remove his replicate again. if that node leaves that zone in direction out of the 100% i would place him inside the inner 100% at the other side of the cube again and reposition his replicate.

that would result in a maximum of 7 replicates in the case that your in an endge of the inner 100% (the endge is shadowed(overlapped) by 1 "3 side to air" dice, 3 "2 side to air"dice and 3 "1 side to air" dice as far as i can think now.

its a pitty, but i dont know how to implant this to a scenemanager. i would just do it internaly in my programm. cant be that hard if you unterstand the internal structure of the differen scenemanagers.maybe ill post my code for that.

hmm octree and cone of view. less copy intensive would it be if i cut the parts of the cone of view that hang over the boarder of the 100% and paste them at the correstponding otherside of the 100%, inside the 100%. that would not need the 7 replicates.

Step 1
Image
Step 2
Image

this image is shot from the top down on the dice. the coordinate we cannot see (the depth) is asumed to be centered in the cube (half way down) the fat black square is are the 100% of space. the thin grey lines gepresend the overshadowed sectors.the triangulars are our code of view. green ist completly in the 100% and has not to be cut. blue and red are outside and have to be cut and pasted at different position inside the 100%

the math i would do step by step, using just one cut each time, repositioning the images at x - Cube.Delta.x
0 x

lodi
Greenskin
Posts: 103
Joined: Sat Jul 24, 2004 7:06 pm

Post by lodi » Thu Mar 17, 2005 4:32 pm

You're thinking about it too much; just set your draw distance to something reasonable (half a cube width, etc.) and draw 27 of them (each in its own scenenode).

Code first, optimize never (or *later*, and only when absolutely necessary).
0 x

User avatar
:wumpus:
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 3067
Joined: Tue Feb 10, 2004 12:53 pm
Location: The Netherlands

Post by :wumpus: » Thu Mar 17, 2005 5:38 pm

I'm very interested in the specific reason why you need this.
0 x

madtulip
Halfling
Posts: 78
Joined: Thu Nov 18, 2004 6:35 pm
Contact:

Post by madtulip » Sun Mar 20, 2005 2:24 pm

@wumpus

well i want my application to be an arcade type space shooter. like r-type, or xenon megablast, but in 3d and with free movement (unlike the 2d versions from the 80`s where the screen was always scrolling). in order to enter the next level you need to kill everyone in your current level (i stole the storyline from doom).as i want to focus on the action and not on the realistics i need to keep him close to enemys all the time. its damn boring if the space is just standart and you fly into one direction without finding the last enemy. he could be everywhere in a normal 3d space. so in my approach to the space you can nearly fly into one direction and will find him sooner or later.

i copied that princilpe from a 2d arcade space shooter i played on amiga a few years ago. the 2d space was "donut" shaped and it worked pretty well.in that game it prooved to be a goot idead to just fly strait ahead and shoot everyone infront of you, not caring for them in your back. as youll be in theire back soon, if your faster then they are.im not sure if you belive that thats a good approach, but i had much fun with it :)

@lodi

i like it to be as good as i can do. thats part of the fun with programming for me.the result ofcourse is important also.i started so many projects like this in my life. and none of them got to a final or even playable version. mostly because of spagetti code gotos in good old basics times or because i was simply unable to read my own code after a few weeks of break. this time. everting gets //comments. structure in the programm is very important for me. every 3 or 4 days i go over the code of the last days and make it look clean, comment, try to optimise it and clean up. i personaly think that thats very important.
later on i want a friend of mine to help me with ki and some faster collision detection methodes, and i dont want to present a heap of "working code" then.
0 x

User avatar
tuan kuranes
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 2653
Joined: Wed Sep 24, 2003 8:07 am
Location: Haute Garonne, France
Contact:

Post by tuan kuranes » Mon Mar 21, 2005 3:59 pm

check http://happypenguin.org/show?BMExt-GLtron for a tron gl games that has the "torus" infinite map thing.

I think Spoke was trying to achieve sort of that in IPLSM ogre addons. PLSM2 doesn't handle that case for now
0 x

alex
Kobold
Posts: 31
Joined: Tue Apr 20, 2004 8:58 am
Location: Australia

Post by alex » Mon Mar 21, 2005 5:24 pm

Your interpretation of the 2d wrapping play area being a 3d donut is correct in a way, but if you look at what is actually happening, the player is basically being wrapped to the other extreme of the x or y dimensions of the play area. The fact that it turns out to approximate a donut shape is a happy co-incidence. I don't ever think about that when I'm wrapping a player to the other side of a playfield. Its as simple as saying

Code: Select all

if player x position > play area max x dimension
{
      player x position = player x position - play area max x dimension
}
Repeating the above for each direction the player can leave, which in a cube is only 6. (X > maxX, X< minX, Y>maxY, Y<minY, Z>maxZ, Z<minZ). All you need to think about is wrapping the player to the opposite x/y/z co-ordinate of the play-cube, and how to draw beyond that boundry. For all we know, the shape is some kind of weird meta-donut in 4 dimensions, but it doesn't really matter for the purposes of getting it to work.
[/code]
0 x
All projects on hold for the time being.

User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
Contact:

Post by jacmoe » Mon Mar 21, 2005 6:39 pm

That does not solve the problem of being able to look into the next area (which is, in fact, behind you). :wink:
So, I guess a simplified version of IPLSM could do it.
You have to load/unload a page, depending on viewer orientation and velocity .. :?: :idea:

[AFTERTHOUGHT]
Well, you could try and render the view behind you to a texture as a way to fake being able to look into what's really behind you - and then warp the player back there as he/she enters ...
[/AFTERTHOUGHT]
0 x
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.

alex
Kobold
Posts: 31
Joined: Tue Apr 20, 2004 8:58 am
Location: Australia

Post by alex » Tue Mar 22, 2005 4:05 pm

I thought about it for a bit, maybe setting up a billboard thats always kept at a certain distance away from the camera, scaled to fill the viewport, and on that billboard render an area behind the player - but it would look ugly and wouldn't work around the edges of the play area.

How about creating 9 copies of everything, placed on all edges of the play box, with the downside that every manipulation would need to happen 9 times.

How about creating a box that extends from the camera and forward encompasing the entire field of view. If this box leaves the play area on the top, then mathematically wrap to the bottom of the field, and create duplicates of any objects inside the box back up the top of the field. Do the same for if it leaves the sides or front or back. This would be an elegant solution, albeit tricky to implement.
0 x
All projects on hold for the time being.

alex
Kobold
Posts: 31
Joined: Tue Apr 20, 2004 8:58 am
Location: Australia

Re: 2D Map to Donut, 3D map to "strange 4D object"

Post by alex » Tue Mar 22, 2005 4:10 pm

i could just

Code: Select all

int minimum = 0;
int maximum = 1000; // i.e. the x dimensions of my world

if (pos.x <= minimum) // if we leave the one end
{
pos.x = maximum; // return from the other
}
By the way, rather than doing pos.x = maximum, to wrap, do pos.x = pos.x + maximum, so that velocity artifacts dont occur. Think about it: if you are travelling forward and move 8 pixels in one frame, but the edge of the play area is only 4 pixels away, then in reality you will pass the edge by four pixels. If you simply shift the player to the opposite side, you've dropped 4 pixels of movement. Instead, you want to move the player by the length of the play area, so the player ends up 4 pixels inside the opposite edge.

So I'm nitpicky, sue me.
0 x
All projects on hold for the time being.

User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
Contact:

Post by jacmoe » Tue Mar 22, 2005 6:49 pm

I think is would be easy to implement box-like world, and use render to texture for the borders - so that you can see "to the other side" - and then warp the player back. :wink:
0 x
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.

madtulip
Halfling
Posts: 78
Joined: Thu Nov 18, 2004 6:35 pm
Contact:

Post by madtulip » Wed Mar 23, 2005 1:50 am

this ideas are all good :) and the only real point to concider is which one is the least resource wasting. i think ill stay with my 27 cube version for now, as i dont know how to render to texture and as the scanning box infront of the camera would effectivly do the same as my 27 cube model, but just on the fly.

i approximatet the worst lost of fps to be 33,1% if the dimension of cubezise to viewdistance are 20 to 1. i could only test your ideas to see if it works better.

and alex, of course the donut is not neaded if you want this 6 conditions in 3d space or 4 conditions in 2d space for leaving and reentering the world. but if you wrap a piece of paper, a 2d world. you can produce a donut without having to cut something away or glue something to it (if its elastic at least :) ...... ) an that is the elegant solution, the 0% performance loss, becuase there are 0% of paper that have to be used 2 times (cut away) or used extra (glue something to it - copy parts of the scene).

i like to see how many folks are wrapping theire head around this :)

is theire maybe a queue that holds all the nodes and meshes in the scene (without knowing any other information like theire name)i could just went through via( get first obj, if this obj != last object, get next obj) to process this 27 cube idea from a center spot and be able to produce a more general code which i could present as a solution later on. ill have a look at the scenemanager tomorrow. im to tired atm. dont exspect any usefull code from me regarding this topic in the next few days.

offtopic
-------------------------------------------------------------------------------------
there are 3 doors, behind one of them is the big price that you want. you can choose one of the doors. then the gamemaster opens one of the remaining 2 doors. behind the door he just opend there is not the big price. now you may change your door selection. would you :) ?
0 x

Post Reply