Thread: RE: [Algorithms] Bsp and collision detection
Brought to you by:
vexxed72
From: Gribb, G. <gg...@ra...> - 2001-11-30 13:20:25
|
Interesting rant. I would claim that everything in a game, including collision, is cosmetic. For example, less "realistic" is often more = fun. =20 Polygons can approximate the real world as well as curves. For given = level of quality, one or the other may perform better. Neither curves, nor polygons are good approximations of many real world objects, like say = an oak tree. =20 Compact descriptions of reality don't exist. -Gil -----Original Message----- From: Neil McLaughlin [mailto:bi...@me...] Sent: Friday, November 30, 2001 6:47 AM To: Gdalgorithms-List Subject: Re: [Algorithms] Bsp and collision detection Hello, =20 Collision Detection can't be that easy because I still haven't seen convincing collisions in any games or simulations. Not on curved = surfaces anyhow. Just bounding box or sphere approximations. Let's see some = curved surfaces like a marble rolling around inside a network of pipes or a = toilet or something. How about two ropes colliding? Does anyone know of such simulations available? =20 =20 For years now everyone seems focused on cosmetics - multitextures and lighting and shadows (which are also just approximations). So games = look so much prettier but they still don't work. Could this explain why 2D games are still a huge hit? I'd like to see better simulations that = feature infinite scalablity and curved surface interaction and seamless articulation. =20 =20 Polygons in general will never support real collisions - so having a separate 3d Editor spit out triangles and then trying to manipulate = them convincingly with a 3d Engine will never work - no matter what the = processor power or bandwidth. We need a higher level 3d primitive if we're ever going to simulate reality, and once we have such an (implicit) format, = we can directly point sample versus tesselate. =20 =20 Neil McLaughlin =20 =20 ----- Original Message -----=20 From: R=E9my Rakic <mailto:ra...@gc...> =20 To: Gdalgorithms-List <mailto:gda...@li...> = Sent: Friday, November 30, 2001 6:05 AM Subject: [Algorithms] Bsp and collision detection Hi everyone, i just can stop finding everyone talking about how fast, easy and = pleasant to write was collision detection using bsp trees. But unfortunately, = even though google helps, i couldn't find nothing interesting enough to get started with it. Does anyone have references, links, papers, websites, that would help a = lot ? I was also wondering whether those algorithms could be used also in a = hybrid engine (octree with mini-bsp inside for instance), or does general = collision detection algorithms for the octree and then for the bsp have to be performed ? How does one do it when using multiple data structures like = this ? Thanks in advance R=E9my Rakic _______________________________________________ GDAlgorithms-list mailing list GDA...@li... <mailto:GDA...@li...>=20 https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list <https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list>=20 |
From: Gribb, G. <gg...@ra...> - 2001-11-30 13:23:12
|
In this day and age, I would say bsp trees are a fairly lousy solution = to the collision detection problem. Modern geometry does not bsp well. = People use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy=20 > and pleasant > to write was collision detection using bsp trees. But=20 > unfortunately, even > though google helps, i couldn't find nothing interesting enough to = get > started with it. > Does anyone have references, links, papers, websites, that=20 > would help a lot > ? >=20 > I was also wondering whether those algorithms could be used=20 > also in a hybrid > engine (octree with mini-bsp inside for instance), or does=20 > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data=20 > structures like this > ? >=20 > Thanks in advance > R=E9my Rakic >=20 >=20 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >=20 |
From: Neil M. <bi...@me...> - 2001-11-30 13:40:26
|
An Oak Tree is a good example of the sort of stuff I'd like to see = interactive - I want to climb the tree and/or explore the inside of = arteries - walk along the wall, and when I come upon the branching area, = smoothly enter. Not just boxy 45 or 90 angle tunnels. Does anyone = know of such examples available? An oak tree IS a curved surface - a higher order curved surface - like a = branching artery (seamless articulation). It's a series of Swept = surfaces that are stitched together. =20 In Computers & Graphics 22,6 (Fellner/Havemann 2/1999) they examined = Max and Maya scenes and determined that to achieve the several orders of = magnitude increase required for true reality simulations we need a more = "compact and abstract format". =20 This means implicit surfaces - for example a sphere is just an equation = - why tesselate and carry around all those polygons, only to have to = sort through them to do collisions? We need all shapes to use the same type of equation - so we have = predictablity between any two shapes.=20 John Synder did some work on Generative Modeling, mentioned in the = latest Watt book. He went on to be chairman MS graphics research lab. = Pixar doesn't use any polygons or textures. =20 Compact descripition really do exist. I've developed such a compact = description. Neil McLaughlin ----- Original Message -----=20 From: Gribb, Gil=20 To: Gdalgorithms-List=20 Sent: Friday, November 30, 2001 8:23 AM Subject: RE: [Algorithms] Bsp and collision detection In this day and age, I would say bsp trees are a fairly lousy solution = to the collision detection problem. Modern geometry does not bsp well. = People use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy=20 > and pleasant > to write was collision detection using bsp trees. But=20 > unfortunately, even > though google helps, i couldn't find nothing interesting enough to = get > started with it. > Does anyone have references, links, papers, websites, that=20 > would help a lot > ? >=20 > I was also wondering whether those algorithms could be used=20 > also in a hybrid > engine (octree with mini-bsp inside for instance), or does=20 > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data=20 > structures like this > ? >=20 > Thanks in advance > R=E9my Rakic >=20 >=20 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >=20 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list |
From: Pierre T. <p.t...@wa...> - 2001-11-30 14:52:56
|
>In this day and age, I would say bsp trees are a fairly lousy solution = to >the collision detection problem. Modern geometry does not bsp well. = People >use it because they don't know any other way to do it. That's probably true enough. >Collision Detection can't be that easy because I still haven't seen = convincing >collisions in any games or simulations. Not on curved surfaces anyhow. = Just >bounding box or sphere approximations. Let's see some curved surfaces = like >a marble rolling around inside a network of pipes or a toilet or = something. >How about two ropes colliding? Does anyone know of such simulations = available? Maybe you should check more games and/or simulations ? :) Curved surfaces are not exactly better or worse than polygons, they're = another way to handle the reality-to-screen mapping, period. There also = are CD methods for them, sure. For example in mechanical simulations and = virtual prototyping, most companies don't use polygons - they need = perfect accuracy. So everything is handled with math equations, = including CD. Hint: it's not fast. Else you can use alternative interactive CD methods such as distance = fields : works for everything including curved surfaces and/or = deformable models, provides everything needed for collision response, = etc. But it's also an approximation. Two ropes: I'd say a polygonal approximation works well here. Maybe you = should define "convincing" then. >An Oak Tree is a good example of the sort of stuff I'd like to see = interactive -=20 >I want to climb the tree and/or explore the inside of arteries - walk = along the >wall, and when I come upon the branching area, smoothly enter. Not = just >boxy 45 or 90 angle tunnels. Does anyone know of such examples = available? I'm not sure to get that. Don't you think there's something between = "boxy 45 or 90 angle tunnels" and the "compact reality description" = you're talking about ? Take that Oak Tree, tesselate it enough, use a = good old BV-tree, and here it is. Not perfect but "interactive" and = accurate enough to fool the eye. We don't use something else because I = don't think we need something else in most cases, simple. In the same way the color buffer is limited to a 8 bits range for each = RGB component. It's also far from ideal (and beginning to change), but = we have to deal with it simply because we wouldn't do anything = otherwise. >This means implicit surfaces - for example a sphere is just an equation >why tesselate and carry around all those polygons, only to have to sort >through them to do collisions? Why tesselate =3D> because CD is just a tiny part of the process. We = need to render as well, for example. I think this is just a matter of = feasibility : with infinite processing power maybe we wouldn't be using = polygons at all. For now, we must get the job done so we use them, no = big deal. I'm not sure it's worth a thread, is it ? >Compact descripition really do exist. I've developed such a compact = description. An interesting problem would be CD against fractal surfaces. You want = "all shapes to use the same type of equation", but maybe it's not = possible. As we all know, many natural objects are best modeled using a = fractal approach, whereas a sphere (perfect, by definition) is quite the = opposite. Doing sphere-vs-sphere CD is the most trivial thing. At the = opposite side of the spectrum, I'd say colliding a fractal landscape (or = any other fractal object) against another fractal landscape is a totally = different kettle of fish. If you stop at one scale and tesselate, you're = actually using polygons and that's "cheating" (according to our new = goal, global unification). If you use the equations, well, you're on for = a long ride since most fractal things have infinite details (standard = image of the infinite zoom). So what do we do ? We approximate, which is = probably coherent with the initial underlying limited computer = precision. Sorry, all of that is probably OT and not very constructive. >Some kind of dynamic AABB tree ? Yup, would be my best bet. Something like this ? http://www.idt.mdh.se/~tla/projects.htm Pierre |
From: Erik H. <er...@un...> - 2001-11-30 13:58:11
|
So how would someone in the know solve the collision problem for modern geometry? I was under the impression that bsp is the favoured method to do collisio= n detection for static geometry (perhaps that is not a part of modern geometry?). Evidently a lot of people seem to be augmenting bsp by using other schemes for spatial indexing as well but when it comes to detecting surface intersections bsp still seems a valid approach. ----- Original Message ----- From: "Gribb, Gil" <gg...@ra...> To: "Gdalgorithms-List" <gda...@li...> Sent: Friday, November 30, 2001 2:23 PM Subject: RE: [Algorithms] Bsp and collision detection In this day and age, I would say bsp trees are a fairly lousy solution to the collision detection problem. Modern geometry does not bsp well. Peopl= e use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy > and pleasant > to write was collision detection using bsp trees. But > unfortunately, even > though google helps, i couldn't find nothing interesting enough to get > started with it. > Does anyone have references, links, papers, websites, that > would help a lot > ? > > I was also wondering whether those algorithms could be used > also in a hybrid > engine (octree with mini-bsp inside for instance), or does > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data > structures like this > ? > > Thanks in advance > R=E9my Rakic > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list |
From: Pierre T. <p.t...@wa...> - 2001-11-30 15:31:54
|
>I was under the impression that bsp is the favoured method to do collision >detection for static geometry (perhaps that is not a part of modern >geometry?). A BSP is good to handle the camera-vs-world CD, but not that good to handle the objects-vs-world cases. Stan Melax's Gamasutra article exposes some of the problems you'll encounter there. At the end of his article, he hints about the use of AABB-trees in Neverwinter Nights, as if it was a more efficient approach for modern geometries (I carefully avoid saying "better approach" since both methods are actually good, with various tradeoffs). I like AABB-trees because : - they're robust (no need to tweak them with epsilon values as with BSPs - see Charles Bloom's notes) - they're very generic (works with everything from convex stuff to polygon soups) - they're fast & easy to build (I build them on-the-fly, no painful scene compilation) - they're efficient You can do ray-mesh, primitive-mesh, mesh-mesh CD with near optimal performance each time, and it simply works. I like that. Here's an old demo doing camera-vs-world CD using Opcode: http://www.codercorner.com/CollideTest.zip I just do a sphere-vs-meshes test here (you can change the sphere parameters in the ini file). It's not perfect (it was just a quick test, not polished enough), it's far from "optimal" (parsing the whole list of meshes each time, savage time stepping, etc), but it's been 10 lines of code to call Opcode. The trees are built on-the-fly, and you can move the objects where you want (F3), it doesn't need recompiling anything (actually there's a static AABB tree - used for VFC only - rebuilt each time you move a mesh but as you'll see that's perfectly free). You can also tesselate/modify some meshes some more with some menu options: the AABB trees are lazy-rebuilt and everything keeps working. It would also work with moving meshes even if there isn't any in that (old, DOS-days) scene. (~46000 faces in the world) Pierre |
From: Neal T. <nea...@nt...> - 2001-11-30 16:25:36
|
From Pierre Terdiman: >I like AABB-trees because : >- they're robust (no need to tweak them with epsilon values as with BSPs - >see Charles Bloom's notes) >- they're very generic (works with everything from convex stuff to polygon >soups) >- they're fast & easy to build (I build them on-the-fly, no painful scene >compilation) >- they're efficient If you represent the entire world as an tree of individual object bounding volumes (whether an AABB tree or whatever), might it make collision response harder? What I'm thinking about here is that rather than colliding with a single surface (e.g. a BSP tree) and nudging the colliding object out along the surface normal to allow for numerical accuracy problems, you would potentially be colliding with more than one object which between them represented the "world surface", making it harder to apply a sensible "nudge". Neal Tringham (Sick Puppies / Empire Interactive) |
From: Emmanuel A. <emm...@wi...> - 2001-11-30 14:16:36
|
This is a partial answer... So what would be a modern and efficient solution ? Some kind of dynamic AABB tree ? Emmanuel > -----Original Message----- > From: Gribb, Gil [mailto:gg...@ra...] > Sent: vendredi 30 novembre 2001 14:24 > To: Gdalgorithms-List > Subject: RE: [Algorithms] Bsp and collision detection >=20 >=20 > In this day and age, I would say bsp trees are a fairly lousy=20 > solution to > the collision detection problem. Modern geometry does not bsp=20 > well. People > use it because they don't know any other way to do it. > -Gil >=20 >=20 > > Hi everyone, > > i just can stop finding everyone talking about how fast, easy=20 > > and pleasant > > to write was collision detection using bsp trees. But=20 > > unfortunately, even > > though google helps, i couldn't find nothing interesting=20 > enough to get > > started with it. > > Does anyone have references, links, papers, websites, that=20 > > would help a lot > > ? > >=20 > > I was also wondering whether those algorithms could be used=20 > > also in a hybrid > > engine (octree with mini-bsp inside for instance), or does=20 > > general collision > > detection algorithms for the octree and then for the bsp have to be > > performed ? How does one do it when using multiple data=20 > > structures like this > > ? > >=20 > > Thanks in advance > > R=E9my Rakic > >=20 > >=20 > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > >=20 >=20 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >=20 |
From: Gribb, G. <gg...@ra...> - 2001-11-30 15:10:11
|
>>An Oak Tree is a good example of the sort of stuff I'd like to see interactive - I want to climb the tree and/or explore the inside of = arteries - walk along the wall, and when I come upon the branching area, = smoothly enter. Not just boxy 45 or 90 angle tunnels. Does anyone know of = such examples available? I don't see a game here. How would you climb a tree with a controller = and would it be fun? >>An oak tree IS a curved surface - a higher order curved surface - = like a branching artery (seamless articulation). It's a series of Swept = surfaces that are stitched together. =20 No it isn't. The surface of an oak tree, is ummmmm a surface, and it = isn't flat, but I don't think you could call it a curved surface because it = is differentiable nowhere. You can probably come up with a compact = description of something that looks like an oak tree. But if I give you an actual, physical oak tree, you won't be able to come up with a compact = description of it. You can come up with a compact approximation to it, but I see no reason to believe that curved surfaces would be the best way to = approximate an oak tree. >>In Computers & Graphics 22,6 (Fellner/Havemann 2/1999) they = examined Max and Maya scenes and determined that to achieve the several orders of magnitude increase required for true reality simulations we need a more "compact and abstract format". =20 >>This means implicit surfaces - for example a sphere is just an = equation - why tesselate and carry around all those polygons, only to have to sort through them to do collisions? Spheres are boring. And so are curves. Everything compact by definition = has a low information content. Implicit surfaces are not a magic bullet.=20 > We need all shapes to use the same type of equation - so we have predictablity between any two shapes.=20 Modeling polygonal shapes (and many things in my office are polygonal) = with curves is a waste of resources and time. > John Synder did some work on Generative Modeling, mentioned in the = latest Watt book. He went on to be chairman MS graphics research lab. Pixar doesn't use any polygons or textures. =20 I thought you wanted realizm? Pixars stuff is cool, but it doesn't look = real by any stretch. Texture (and bump ect) maps are a nice compact = approximation for lots of real things. For example, street signs. Pixar does have = flat surfaces in there stuff, and these would be well represented by = polygons. >Compact descripition really do exist. I've developed such a compact description. huh? Such as? -Gil Neil McLaughlin ----- Original Message -----=20 From: Gribb, Gil=20 To: Gdalgorithms-List=20 Sent: Friday, November 30, 2001 8:23 AM Subject: RE: [Algorithms] Bsp and collision detection In this day and age, I would say bsp trees are a fairly lousy solution = to the collision detection problem. Modern geometry does not bsp well. = People use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy=20 > and pleasant > to write was collision detection using bsp trees. But=20 > unfortunately, even > though google helps, i couldn't find nothing interesting enough to = get > started with it. > Does anyone have references, links, papers, websites, that=20 > would help a lot > ? >=20 > I was also wondering whether those algorithms could be used=20 > also in a hybrid > engine (octree with mini-bsp inside for instance), or does=20 > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data=20 > structures like this > ? >=20 > Thanks in advance > R=E9my Rakic >=20 >=20 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >=20 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list |
From: Neil M. <bi...@me...> - 2001-11-30 15:31:52
|
I don't see a game here.=20 Ok, so you could do it if you wanted, but it's too boring? >How would you climb a tree with a controller and>would it be fun? The tree is parametric, so if you wanted to "drive" on the tree you'd = use a steering wheel - You drive on the tree like a skateboard moves on = a hill. - you move in Cylindrical coordinates - like driving a ship = across the ocean - a captain doesn't move the ship along a line in = Cartesian coordinates and recheck the collisions 60 times per second = against with a tesselated Earth - reality is not tesselated. =20 >>An oak tree IS a curved surface -=20 No it isn't.=20 No it isn't? If you don't think arteries can be reprented as curved = surfaces you haven't studied medical technology. I just emailed you a = picture of a tree that I made with curved surfaces. (Can I post images = on this group?) It's not ONE curved surface, but it's also not 1 = Million triangles. There's an "in between" that the 1.8 Gigahertz can = handle, as can Unified Architecture. =20 >Compact descripition really do exist. huh? Such as? Divide and conquer. All shapes can be made of Swept Surfaces. I'd = love to show a demo of my work. Also see Generative Modeling in Siggraph. Mark my words, polygons will become Obsolete! Ha ha ha ha ha !!! =20 >:) Neil McLaughlin ----- Original Message -----=20 From: Gribb, Gil=20 To: Gdalgorithms-List=20 Sent: Friday, November 30, 2001 10:10 AM Subject: RE: [Algorithms] Bsp and collision detection >>An Oak Tree is a good example of the sort of stuff I'd like to see interactive - I want to climb the tree and/or explore the inside of = arteries - walk along the wall, and when I come upon the branching area, = smoothly enter. Not just boxy 45 or 90 angle tunnels. Does anyone know of = such examples available? I don't see a game here.=20 >>An oak tree IS a curved surface - a higher order curved surface - = like a branching artery (seamless articulation). It's a series of Swept = surfaces that are stitched together. =20 No it isn't. The surface of an oak tree, is ummmmm a surface, and it = isn't flat, but I don't think you could call it a curved surface because it = is differentiable nowhere. You can probably come up with a compact = description of something that looks like an oak tree. But if I give you an actual, physical oak tree, you won't be able to come up with a compact = description of it. You can come up with a compact approximation to it, but I see = no reason to believe that curved surfaces would be the best way to = approximate an oak tree. >>In Computers & Graphics 22,6 (Fellner/Havemann 2/1999) they = examined Max and Maya scenes and determined that to achieve the several orders of magnitude increase required for true reality simulations we need a = more "compact and abstract format". =20 >>This means implicit surfaces - for example a sphere is just an = equation - why tesselate and carry around all those polygons, only to have to = sort through them to do collisions? Spheres are boring. And so are curves. Everything compact by = definition has a low information content. Implicit surfaces are not a magic bullet.=20 > We need all shapes to use the same type of equation - so we have predictablity between any two shapes.=20 Modeling polygonal shapes (and many things in my office are polygonal) = with curves is a waste of resources and time. > John Synder did some work on Generative Modeling, mentioned in the = latest Watt book. He went on to be chairman MS graphics research lab. Pixar doesn't use any polygons or textures. =20 I thought you wanted realizm? Pixars stuff is cool, but it doesn't = look real by any stretch. Texture (and bump ect) maps are a nice compact = approximation for lots of real things. For example, street signs. Pixar does have = flat surfaces in there stuff, and these would be well represented by = polygons. >Compact descripition really do exist. I've developed such a compact description. huh? Such as? -Gil Neil McLaughlin ----- Original Message -----=20 From: Gribb, Gil=20 To: Gdalgorithms-List=20 Sent: Friday, November 30, 2001 8:23 AM Subject: RE: [Algorithms] Bsp and collision detection In this day and age, I would say bsp trees are a fairly lousy solution = to the collision detection problem. Modern geometry does not bsp well. = People use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy=20 > and pleasant > to write was collision detection using bsp trees. But=20 > unfortunately, even > though google helps, i couldn't find nothing interesting enough to = get > started with it. > Does anyone have references, links, papers, websites, that=20 > would help a lot > ? >=20 > I was also wondering whether those algorithms could be used=20 > also in a hybrid > engine (octree with mini-bsp inside for instance), or does=20 > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data=20 > structures like this > ? >=20 > Thanks in advance > R=E9my Rakic >=20 >=20 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >=20 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list |
From: Michael P. <MPo...@cy...> - 2001-11-30 15:15:47
|
2D Games are -still- a hit (PC wise *) because of a few reasons: a) They run on older hardware - not everyone has the latest 3D card, i.e. GeForce 3. b) 2D used to look WAY better then 3D for certain styles. i.e Load up Monkey Island (1 or 2), or Grim Fandigo - those 2D art stills are just goreous - how many polys would you need to replicate the same look in 3D? Look at Diablo 2 - especially act 2, and act 5. We didn't have the polygon budget a few years ago to do that nice "dome palace." Another sub-reason, is 2D worlds have lots of "little environment details". i.e. Load up Half-Life and look at how most of the 3D rooms feel so barren. My desk at work is "cluttered" with tons of objects, yet most 3D games, if they have a desk, will have a few objects (due to memory restrictions.) MGS2 has done an awesome job of an interactive world. c) It's much easier for the artists to make something look good from one side, then from all directions. ;-) Allthough this is less of an argument with everything being done up as a high poly model first. I'd say 3D is *finally* starting able to match the quality of 2D. Luigi's Mansion looks very cool. I just picked up ICO last nite -- absolutely breathtaking visuals. (Gameplay wise it reminds me of Prince of Persia for some reason.) You're partially correct - in our quest for realistic real-time rendering, gameplay along the way got ignored at times. * The best selling games on PCs this year are, The Sims, Diablo, Roller Coaster Tycoon, Age of Empires - all 2D games. -----Original Message----- From: Neil McLaughlin [mailto:bi...@me...] Sent: Friday, November 30, 2001 7:47 AM To: Gdalgorithms-List Subject: Re: [Algorithms] Bsp and collision detection Hello, =20 For years now everyone seems focused on cosmetics - multitextures and lighting and shadows (which are also just approximations). So games look so much prettier but they still don't work. Could this explain why 2D games are still a huge hit? |
From: Matthew N. <Ma...@re...> - 2001-11-30 15:28:31
|
> b) 2D used to look WAY better then 3D for certain styles. i.e Load up > Monkey Island (1 or 2), or Grim Fandigo - those 2D art stills are just > goreous - how many polys would you need to replicate the same look in > 3D?=20 Umm, wasn't Grim Fandango 3D? And pretty low poly 3D at that? Matt. |
From: <mpo...@ed...> - 2001-11-30 15:50:16
|
>> b) 2D used to look WAY better then 3D for certain styles. i.e Load up >> Monkey Island (1 or 2), or Grim Fandigo - those 2D art stills are just >> goreous - how many polys would you need to replicate the same look in >> 3D? >Umm, wasn't Grim Fandango 3D? And pretty low poly 3D at that? Only the characters were made using polygons. The remaining was made of hand drawned backgrounds. Mickael Pointier |
From: Adam M. <amo...@dp...> - 2001-11-30 16:22:36
|
> Only the characters were made using polygons. The remaining was made > of hand drawned backgrounds. > I believe the backgrounds are prerendered 3D scenes, not drawn but modeled. -- -- Adam Moravanszky http://n.ethz.ch/student/adammo/ |
From: Matthew N. <Ma...@re...> - 2001-11-30 16:04:12
|
There seem to be two issues here that are getting slightly mixed up. There's one question of what is the best representational format for graphics and collision detection in a computer simulation and there's another, not necessarily related question of what representation is closer to reality. While curves may prove to be a better system for computer simulation in the long term (though they're not very friendly to current PC 3D hardware when dynamically tesselated) they're certainly not any better a representation of reality than polygons. Neither bears much resemblance to the real world - there are no smooth curves in real objects, it all comes down to atoms in the end! As for Pixar not using polys, are you sure about that? I thought they used Renderman which is poly based. There's a common misconception that Pixar do ray tracing but that's not true. I seem to remember reading about Monsters Inc. recently and reading that they used loads of polys for the big furry blue guy's hair but I could be wrong about that... Matt. -----Original Message----- From: Neil McLaughlin [mailto:bi...@me...] Sent: 30 November 2001 13:41 To: Gdalgorithms-List Subject: Re: [Algorithms] Bsp and collision detection An Oak Tree is a good example of the sort of stuff I'd like to see interactive - I want to climb the tree and/or explore the inside of arteries - walk along the wall, and when I come upon the branching area, smoothly enter. Not just boxy 45 or 90 angle tunnels. Does anyone know of such examples available? An oak tree IS a curved surface - a higher order curved surface - like a branching artery (seamless articulation). It's a series of Swept surfaces that are stitched together. =20 In Computers & Graphics 22,6 (Fellner/Havemann 2/1999) they examined Max and Maya scenes and determined that to achieve the several orders of magnitude increase required for true reality simulations we need a more "compact and abstract format". =20 This means implicit surfaces - for example a sphere is just an equation - why tesselate and carry around all those polygons, only to have to sort through them to do collisions? We need all shapes to use the same type of equation - so we have predictablity between any two shapes.=20 John Synder did some work on Generative Modeling, mentioned in the latest Watt book. He went on to be chairman MS graphics research lab. Pixar doesn't use any polygons or textures. =20 Compact descripition really do exist. I've developed such a compact description. Neil McLaughlin ----- Original Message -----=20 From: Gribb, Gil=20 To: Gdalgorithms-List=20 Sent: Friday, November 30, 2001 8:23 AM Subject: RE: [Algorithms] Bsp and collision detection In this day and age, I would say bsp trees are a fairly lousy solution to the collision detection problem. Modern geometry does not bsp well. People use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy=20 > and pleasant > to write was collision detection using bsp trees. But=20 > unfortunately, even > though google helps, i couldn't find nothing interesting enough to get > started with it. > Does anyone have references, links, papers, websites, that=20 > would help a lot > ? >=20 > I was also wondering whether those algorithms could be used=20 > also in a hybrid > engine (octree with mini-bsp inside for instance), or does=20 > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data=20 > structures like this > ? >=20 > Thanks in advance > R=E9my Rakic >=20 >=20 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >=20 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list |
From: Neil M. <bi...@me...> - 2001-11-30 16:47:27
|
Perhaps Pixar does use polygons and I'm mistaken but Tony DeRose spoke = about not getting so attached to texture maps, and said they don't use = them. Snyders work in 1992 rendered photorealistic scenes with direct = ray tracing - something only possible in a scene composed of all = implicit surfaces. Reality is infinitely scalable - all objects are made of other things = until they are too small to be seen. Our eye point samples the world to a certain resolution and certain number of = colors. I'd like to see a similar rendering approach eventually. I'm = not saying make a game today based on it. If you want to represent an entire city or jungle, you can in a small = amount of memory with the right implicit surfaces. Then, just tesselate = what you need for the immediate area. This has strong internet uses as = well as supporting collisions and photorealism. Of course, non-polygons is a few years away - I'm not unhappy with the = GeForce2 or OpenGL, but it's worth thinking about -=20 ----- Original Message -----=20 From: Matthew Newport=20 To: Neil McLaughlin ; Gdalgorithms-List=20 Sent: Friday, November 30, 2001 11:07 AM Subject: RE: [Algorithms] Bsp and collision detection There seem to be two issues here that are getting slightly mixed up. There's one question of what is the best representational format for graphics and collision detection in a computer simulation and there's another, not necessarily related question of what representation is closer to reality. While curves may prove to be a better system for computer simulation in the long term (though they're not very friendly to current PC 3D hardware when dynamically tesselated) they're = certainly not any better a representation of reality than polygons. Neither = bears much resemblance to the real world - there are no smooth curves in = real objects, it all comes down to atoms in the end! As for Pixar not using polys, are you sure about that? I thought they used Renderman which is poly based. There's a common misconception = that Pixar do ray tracing but that's not true. I seem to remember reading about Monsters Inc. recently and reading that they used loads of polys for the big furry blue guy's hair but I could be wrong about that... Matt. -----Original Message----- From: Neil McLaughlin [mailto:bi...@me...] Sent: 30 November 2001 13:41 To: Gdalgorithms-List Subject: Re: [Algorithms] Bsp and collision detection An Oak Tree is a good example of the sort of stuff I'd like to see interactive - I want to climb the tree and/or explore the inside of arteries - walk along the wall, and when I come upon the branching = area, smoothly enter. Not just boxy 45 or 90 angle tunnels. Does anyone know of such examples available? An oak tree IS a curved surface - a higher order curved surface - like = a branching artery (seamless articulation). It's a series of Swept surfaces that are stitched together. =20 In Computers & Graphics 22,6 (Fellner/Havemann 2/1999) they examined Max and Maya scenes and determined that to achieve the several orders = of magnitude increase required for true reality simulations we need a = more "compact and abstract format". =20 This means implicit surfaces - for example a sphere is just an = equation - why tesselate and carry around all those polygons, only to have to sort through them to do collisions? We need all shapes to use the same type of equation - so we have predictablity between any two shapes.=20 John Synder did some work on Generative Modeling, mentioned in the latest Watt book. He went on to be chairman MS graphics research lab. Pixar doesn't use any polygons or textures. =20 Compact descripition really do exist. I've developed such a compact description. Neil McLaughlin ----- Original Message -----=20 From: Gribb, Gil=20 To: Gdalgorithms-List=20 Sent: Friday, November 30, 2001 8:23 AM Subject: RE: [Algorithms] Bsp and collision detection In this day and age, I would say bsp trees are a fairly lousy solution to the collision detection problem. Modern geometry does not bsp well. People use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy=20 > and pleasant > to write was collision detection using bsp trees. But=20 > unfortunately, even > though google helps, i couldn't find nothing interesting enough to = get > started with it. > Does anyone have references, links, papers, websites, that=20 > would help a lot > ? >=20 > I was also wondering whether those algorithms could be used=20 > also in a hybrid > engine (octree with mini-bsp inside for instance), or does=20 > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data=20 > structures like this > ? >=20 > Thanks in advance > R=E9my Rakic >=20 >=20 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >=20 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list |
From: <ra...@gc...> - 2001-11-30 17:30:51
|
Neil Mc Laughlin wrote: "Of course, non-polygons is a few years away - I'm not unhappy with the GeForce2 or OpenGL, but it's worth thinking about -" What are we gonna use instead ?? |
From: Neil M. <bi...@me...> - 2001-11-30 18:02:00
|
> What are we gonna use instead ?? My software!=20 :) ----------------------------------- My Predictions on how polygons will become obsolete: 1) 2003 A new type of surface shows up in a game or games, and creates a = new element of gameplay - a new genre. Ex. A snake that slithers over = arbitrary terrain. A dynamic Octopus that can grab stuff. A guy with a = whip that can wrap around anything he whips. Branching smooth artery = simulations. A car with wheels that squish when it goes over jumps. = Games that let you dig twisting tunnels anywhere - (sorry if none of = this sounds fun to Gil). 2) 2003 More games follow suit using the same surface type 3) 2004 The first "all implicit" game arrives - still using polygons but = with dynamic tesselation. 4) 2005 Hardware support follows - the first non-polygon demo is = available - directly point sampled, interactive photorealism. 5) 2006 Color-by-number direct scene rendering becomes standard - = suddenly we have streamable VR on the internet, objects collide, physics = are far more accurate, leaves blow in the wind, the #1 game is Tree = Climber '06, I become immortal, and Gil becomes a believer. |
From: Gribb, G. <gg...@ra...> - 2001-11-30 16:10:34
|
(plain text would be much appreciated since when I convert to plain text I lose the indenting) I don't see a game here. Ok, so you could do it if you wanted, but it's too boring? Yes, we could make Extream Tree Climber 2001, but I would never choose a rendering and collision technology without knowing how the game is gonna play. And the theory is probably less important than more mundane concerns like how well the artists can work with the technology. >How would you climb a tree with a controller and>would it be fun? >The tree is parametric, so if you wanted to "drive" on the tree you'd use a steering wheel - You drive on the tree like a skateboard moves on a hill. - you move in Cylindrical coordinates - like driving a ship across the ocean - a captain doesn't move the ship along a line in Cartesian coordinates and recheck the collisions 60 times per second against with a tesselated Earth - reality is not tesselated. You miss the point, reality is neither polygons NOR parametric surfaces. Polygons are better for some things, parameteric surfaces are better for some things. If the coordinate system is cartisian, cylindrical or whatever is quite irrelevant since it is not something the player senses anyway. You certainly don't want to do game math in the natural parameterization of a curved surface. (cause we want things like constant velocity, gravity ect). >>An oak tree IS a curved surface - No it isn't. No it isn't? If you don't think arteries can be reprented as curved surfaces you haven't studied medical technology. I just emailed you a picture of a tree that I made with curved surfaces. (Can I post images on this group?) It's not ONE curved surface, but it's also not 1 Million triangles. There's an "in between" that the 1.8 Gigahertz can handle, as can Unified Architecture. A tree is just a tree, and has no concise mathematical description. Sure a tree can be represented by curves, polygons, points, volumes, cubes, or chalk on a chalk board. But none of these representations are a tree, and they have different properties from each other. "represent everything with curves" is a silly oversimplification of the process of making games, game art, and game engines. I personally like subdivision surfaces, because they are both polygons and surfaces. >Compact descripition really do exist. huh? Such as? >>> Divide and conquer. All shapes can be made of Swept Surfaces. I'd love to show a demo of my work. Also see Generative Modeling in Siggraph. Mark my words, polygons will become Obsolete! Ha ha ha ha ha !!! They may become obsolete. As I think bsp trees have. But they are not going to be obsolete for at least 3 product cycles, so I don't lose a whole lot of sleep over it. Going with your approach today is suicide. -Gil |
From: Dean C. <dea...@cr...> - 2001-11-30 16:12:41
|
If the only tool you have have is a hammer, everything looks like a nail. (Or something like that) Pixar do uses polygons and surfaces, procedural and discete textures. They use the correct tool for the job, and its very rarely swept surfaces. The current state of the art is direct evualation of sub-division surfaces, but flat things in a Pixar movie are still modeled with polygons. To be more correct the ideal represenation of a physical surface is fuzzy, there is no 'surface'. So you assertation that the world is not tesselated, also applies to the world is not a curved surface. Its more like a iso-surface using quantum field theory to control the electromagnetic interactions (light + collisions). Bye, Deano Dean Calver, Lead Programmer, Creature Labs. -----Original Message----- From: Neil McLaughlin [mailto:bi...@me...] Sent: 30 November 2001 15:34 To: Gdalgorithms-List Subject: Re: [Algorithms] Bsp and collision detection I don't see a game here. Ok, so you could do it if you wanted, but it's too boring? >How would you climb a tree with a controller and>would it be fun? The tree is parametric, so if you wanted to "drive" on the tree you'd use a steering wheel - You drive on the tree like a skateboard moves on a hill. - you move in Cylindrical coordinates - like driving a ship across the ocean - a captain doesn't move the ship along a line in Cartesian coordinates and recheck the collisions 60 times per second against with a tesselated Earth - reality is not tesselated. >>An oak tree IS a curved surface - No it isn't. No it isn't? If you don't think arteries can be reprented as curved surfaces you haven't studied medical technology. I just emailed you a picture of a tree that I made with curved surfaces. (Can I post images on this group?) It's not ONE curved surface, but it's also not 1 Million triangles. There's an "in between" that the 1.8 Gigahertz can handle, as can Unified Architecture. >Compact descripition really do exist. huh? Such as? Divide and conquer. All shapes can be made of Swept Surfaces. I'd love to show a demo of my work. Also see Generative Modeling in Siggraph. Mark my words, polygons will become Obsolete! Ha ha ha ha ha !!! >:) Neil McLaughlin ----- Original Message ----- From: Gribb, <mailto:gg...@ra...> Gil To: Gdalgorithms-List <mailto:gda...@li...> Sent: Friday, November 30, 2001 10:10 AM Subject: RE: [Algorithms] Bsp and collision detection >>An Oak Tree is a good example of the sort of stuff I'd like to see interactive - I want to climb the tree and/or explore the inside of arteries - walk along the wall, and when I come upon the branching area, smoothly enter. Not just boxy 45 or 90 angle tunnels. Does anyone know of such examples available? I don't see a game here. >>An oak tree IS a curved surface - a higher order curved surface - like a branching artery (seamless articulation). It's a series of Swept surfaces that are stitched together. No it isn't. The surface of an oak tree, is ummmmm a surface, and it isn't flat, but I don't think you could call it a curved surface because it is differentiable nowhere. You can probably come up with a compact description of something that looks like an oak tree. But if I give you an actual, physical oak tree, you won't be able to come up with a compact description of it. You can come up with a compact approximation to it, but I see no reason to believe that curved surfaces would be the best way to approximate an oak tree. >>In Computers & Graphics 22,6 (Fellner/Havemann 2/1999) they examined Max and Maya scenes and determined that to achieve the several orders of magnitude increase required for true reality simulations we need a more "compact and abstract format". >>This means implicit surfaces - for example a sphere is just an equation - why tesselate and carry around all those polygons, only to have to sort through them to do collisions? Spheres are boring. And so are curves. Everything compact by definition has a low information content. Implicit surfaces are not a magic bullet. > We need all shapes to use the same type of equation - so we have predictablity between any two shapes. Modeling polygonal shapes (and many things in my office are polygonal) with curves is a waste of resources and time. > John Synder did some work on Generative Modeling, mentioned in the latest Watt book. He went on to be chairman MS graphics research lab. Pixar doesn't use any polygons or textures. I thought you wanted realizm? Pixars stuff is cool, but it doesn't look real by any stretch. Texture (and bump ect) maps are a nice compact approximation for lots of real things. For example, street signs. Pixar does have flat surfaces in there stuff, and these would be well represented by polygons. >Compact descripition really do exist. I've developed such a compact description. huh? Such as? -Gil Neil McLaughlin ----- Original Message ----- From: Gribb, Gil To: Gdalgorithms-List Sent: Friday, November 30, 2001 8:23 AM Subject: RE: [Algorithms] Bsp and collision detection In this day and age, I would say bsp trees are a fairly lousy solution to the collision detection problem. Modern geometry does not bsp well. People use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy > and pleasant > to write was collision detection using bsp trees. But > unfortunately, even > though google helps, i couldn't find nothing interesting enough to get > started with it. > Does anyone have references, links, papers, websites, that > would help a lot > ? > > I was also wondering whether those algorithms could be used > also in a hybrid > engine (octree with mini-bsp inside for instance), or does > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data > structures like this > ? > > Thanks in advance > Rémy Rakic > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... <mailto:GDA...@li...> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list <https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list> > _______________________________________________ GDAlgorithms-list mailing list GDA...@li... <mailto:GDA...@li...> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list <https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list> _______________________________________________ GDAlgorithms-list mailing list GDA...@li... <mailto:GDA...@li...> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list <https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list> |
From: Killpack, C. <Ch...@ea...> - 2001-11-30 17:20:57
|
Some distinctions =20 Renderman - This is an interface to the renderer. It defines a bytestream protocol, and C language bindings. Pixar proposed and maintains the Renderman interface. Since it is only an interface, implementation can va= ry. =20 Renderman Compliance - a set of features that your implementation must support in order to be 'Renderman-compliant' =20 PRMan - Pixar's implementation of the Renderman spec. It's a polygon base= d renderer. =20 BMRT - Larry Gritz's implementation. It renders the scene using raytracin= g. Also has global illumination (Monte Carlo methods for radiosity and photo= n maps). =20 Now to the nitty gritty... =20 The Renderman interface describes the scene as primitives. These include quadrics (sphere, torus, cone, disk), bicubic patches (of varying bases), NURBS (including trimmed), etc. =20 PRMan is based upon the Reyes Rendering Architecture.* These Reyes render= ing architecture 'dices' primitives into grids of micropolygons. A micropolyg= on is a bilinear patch. Generally a micropolygon is 1/2 pixel on each side. Anti-aliasing is achieved by super-sampling. The amount of supersampling (the scale of the framebuffer compared to the final image) is controllabl= e through the Renderman spec, but by default is 2x in each axis (hence a micropolygon being generally 1/2 pixel across on each side). =20 The grid is then busted into individual micropolygons, which are then bou= nd, culled against viewing frustum, displaced, shaded and finally placed into the z-buffered framebuffer. =20 *Phew* Hope that helps! :) =20 Chris =20 =20 * "The Reyes Image Rendering Architecture", Cook, Carpenter, Catmull SIGGRAPH 1987 =20 -----Original Message----- From: Neil McLaughlin [mailto:bi...@me...] Sent: Friday, November 30, 2001 8:49 AM To: Gdalgorithms-List Subject: Re: [Algorithms] Bsp and collision detection Perhaps Pixar does use polygons and I'm mistaken but Tony DeRose spoke about not getting so attached to texture maps, and said they don't use th= em. Snyders work in 1992 rendered photorealistic scenes with direct ray traci= ng - something only possible in a scene composed of all implicit surfaces. =20 Reality is infinitely scalable - all objects are made of other things unt= il they are too small to be seen. Our eye point samples the world to a certain resolution and certain number of colors. I'd like to see a similar rendering approach eventually. I'm no= t saying make a game today based on it. =20 If you want to represent an entire city or jungle, you can in a small amo= unt of memory with the right implicit surfaces. Then, just tesselate what yo= u need for the immediate area. This has strong internet uses as well as supporting collisions and photorealism. =20 Of course, non-polygons is a few years away - I'm not unhappy with the GeForce2 or OpenGL, but it's worth thinking about -=20 ----- Original Message -----=20 From: Matthew <mailto:Ma...@re...> Newport=20 To: Neil McLaughlin <mailto:bi...@me...> ; Gdalgorithms-List <mailto:gda...@li...> =20 Sent: Friday, November 30, 2001 11:07 AM Subject: RE: [Algorithms] Bsp and collision detection There seem to be two issues here that are getting slightly mixed up. There's one question of what is the best representational format for graphics and collision detection in a computer simulation and there's another, not necessarily related question of what representation is closer to reality. While curves may prove to be a better system for computer simulation in the long term (though they're not very friendly to current PC 3D hardware when dynamically tesselated) they're certainly not any better a representation of reality than polygons. Neither bears much resemblance to the real world - there are no smooth curves in real objects, it all comes down to atoms in the end! As for Pixar not using polys, are you sure about that? I thought they used Renderman which is poly based. There's a common misconception that Pixar do ray tracing but that's not true. I seem to remember reading about Monsters Inc. recently and reading that they used loads of polys for the big furry blue guy's hair but I could be wrong about that... Matt. -----Original Message----- From: Neil McLaughlin [mailto:bi...@me...] Sent: 30 November 2001 13:41 To: Gdalgorithms-List Subject: Re: [Algorithms] Bsp and collision detection An Oak Tree is a good example of the sort of stuff I'd like to see interactive - I want to climb the tree and/or explore the inside of arteries - walk along the wall, and when I come upon the branching area, smoothly enter. Not just boxy 45 or 90 angle tunnels. Does anyone know of such examples available? An oak tree IS a curved surface - a higher order curved surface - like a branching artery (seamless articulation). It's a series of Swept surfaces that are stitched together. =20 In Computers & Graphics 22,6 (Fellner/Havemann 2/1999) they examined Max and Maya scenes and determined that to achieve the several orders of magnitude increase required for true reality simulations we need a more "compact and abstract format". =20 This means implicit surfaces - for example a sphere is just an equation - why tesselate and carry around all those polygons, only to have to sort through them to do collisions? We need all shapes to use the same type of equation - so we have predictablity between any two shapes.=20 John Synder did some work on Generative Modeling, mentioned in the latest Watt book. He went on to be chairman MS graphics research lab. Pixar doesn't use any polygons or textures. =20 Compact descripition really do exist. I've developed such a compact description. Neil McLaughlin ----- Original Message -----=20 From: Gribb, Gil=20 To: Gdalgorithms-List=20 Sent: Friday, November 30, 2001 8:23 AM Subject: RE: [Algorithms] Bsp and collision detection In this day and age, I would say bsp trees are a fairly lousy solution to the collision detection problem. Modern geometry does not bsp well. People use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy=20 > and pleasant > to write was collision detection using bsp trees. But=20 > unfortunately, even > though google helps, i couldn't find nothing interesting enough to get > started with it. > Does anyone have references, links, papers, websites, that=20 > would help a lot > ? >=20 > I was also wondering whether those algorithms could be used=20 > also in a hybrid > engine (octree with mini-bsp inside for instance), or does=20 > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data=20 > structures like this > ? >=20 > Thanks in advance > R=E9my Rakic >=20 >=20 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... <mailto:GDA...@li...>=20 > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list <https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list>=20 >=20 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... <mailto:GDA...@li...>=20 https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list <https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list>=20 |
From: Matthew N. <Ma...@re...> - 2001-11-30 17:49:40
|
Sorry, I should have included a disclaimer that I don't really know very much about Renderman :-) My only knowledge of it comes from references to it in 'Texturing and Modelling, a Procedural Approach' which I haven't looked at for a while... That book (great book btw) doesn't try and teach you Renderman, but it does refer to it in some chapters and has some code snippets. So do Pixar model predominantly with quadrics, patches, NURBS etc. and just end up tesselating to sub-pixel polys for rendering? Or do they use polygonal modelling as well? In the 'making of' feature on the Shrek DVD they talk about their character models being 800,000 polys and the wireframe and flat shaded stuff you see looks like it's just poly-based modelling that Dreamworks are doing. One nifty feature of Renderman that is mentioned in 'Texturing and Modelling' is the procedural texturing functionality. With pixel shader support now starting to appear on the latest 3D cards there's some exciting possibilities for doing these effects in real time on a PC, though pixel shaders don't seem quite general enough at the moment to get really creative... Whoops, wondering way off the original topic here! Matt. -----Original Message----- From: Killpack, Chris [mailto:Ch...@ea...] Sent: 30 November 2001 17:21 To: Gdalgorithms-List Subject: RE: [Algorithms] Bsp and collision detection Some distinctions Renderman - This is an interface to the renderer. It defines a bytestream protocol, and C language bindings. Pixar proposed and maintains the Renderman interface. Since it is only an interface, implementation can vary. Renderman Compliance - a set of features that your implementation must support in order to be 'Renderman-compliant' PRMan - Pixar's implementation of the Renderman spec. It's a polygon based renderer. BMRT - Larry Gritz's implementation. It renders the scene using raytracing. Also has global illumination (Monte Carlo methods for radiosity and photon maps). Now to the nitty gritty... The Renderman interface describes the scene as primitives. These include quadrics (sphere, torus, cone, disk), bicubic patches (of varying bases), NURBS (including trimmed), etc. PRMan is based upon the Reyes Rendering Architecture.* These Reyes rendering architecture 'dices' primitives into grids of micropolygons. A micropolygon is a bilinear patch. Generally a micropolygon is 1/2 pixel on each side. Anti-aliasing is achieved by super-sampling. The amount of supersampling (the scale of the framebuffer compared to the final image) is controllable through the Renderman spec, but by default is 2x in each axis (hence a micropolygon being generally 1/2 pixel across on each side). The grid is then busted into individual micropolygons, which are then bound, culled against viewing frustum, displaced, shaded and finally placed into the z-buffered framebuffer. *Phew* Hope that helps! :) Chris * "The Reyes Image Rendering Architecture", Cook, Carpenter, Catmull SIGGRAPH 1987 -----Original Message----- From: Neil McLaughlin [mailto:bi...@me...] Sent: Friday, November 30, 2001 8:49 AM To: Gdalgorithms-List Subject: Re: [Algorithms] Bsp and collision detection Perhaps Pixar does use polygons and I'm mistaken but Tony DeRose spoke about not getting so attached to texture maps, and said they don't use them. Snyders work in 1992 rendered photorealistic scenes with direct ray tracing - something only possible in a scene composed of all implicit surfaces. Reality is infinitely scalable - all objects are made of other things until they are too small to be seen. Our eye point samples the world to a certain resolution and certain number of colors. I'd like to see a similar rendering approach eventually. I'm not saying make a game today based on it. If you want to represent an entire city or jungle, you can in a small amount of memory with the right implicit surfaces. Then, just tesselate what you need for the immediate area. This has strong internet uses as well as supporting collisions and photorealism. Of course, non-polygons is a few years away - I'm not unhappy with the GeForce2 or OpenGL, but it's worth thinking about -=20 ----- Original Message -----=20 From: Matthew Newport=20 To: Neil McLaughlin ; Gdalgorithms-List=20 Sent: Friday, November 30, 2001 11:07 AM Subject: RE: [Algorithms] Bsp and collision detection There seem to be two issues here that are getting slightly mixed up. There's one question of what is the best representational format for graphics and collision detection in a computer simulation and there's another, not necessarily related question of what representation is closer to reality. While curves may prove to be a better system for computer simulation in the long term (though they're not very friendly to current PC 3D hardware when dynamically tesselated) they're certainly not any better a representation of reality than polygons. Neither bears much resemblance to the real world - there are no smooth curves in real objects, it all comes down to atoms in the end! As for Pixar not using polys, are you sure about that? I thought they used Renderman which is poly based. There's a common misconception that Pixar do ray tracing but that's not true. I seem to remember reading about Monsters Inc. recently and reading that they used loads of polys for the big furry blue guy's hair but I could be wrong about that... Matt. -----Original Message----- From: Neil McLaughlin [mailto:bi...@me...] Sent: 30 November 2001 13:41 To: Gdalgorithms-List Subject: Re: [Algorithms] Bsp and collision detection An Oak Tree is a good example of the sort of stuff I'd like to see interactive - I want to climb the tree and/or explore the inside of arteries - walk along the wall, and when I come upon the branching area, smoothly enter. Not just boxy 45 or 90 angle tunnels. Does anyone know of such examples available? An oak tree IS a curved surface - a higher order curved surface - like a branching artery (seamless articulation). It's a series of Swept surfaces that are stitched together. =20 In Computers & Graphics 22,6 (Fellner/Havemann 2/1999) they examined Max and Maya scenes and determined that to achieve the several orders of magnitude increase required for true reality simulations we need a more "compact and abstract format". =20 This means implicit surfaces - for example a sphere is just an equation - why tesselate and carry around all those polygons, only to have to sort through them to do collisions? We need all shapes to use the same type of equation - so we have predictablity between any two shapes.=20 John Synder did some work on Generative Modeling, mentioned in the latest Watt book. He went on to be chairman MS graphics research lab. Pixar doesn't use any polygons or textures. =20 Compact descripition really do exist. I've developed such a compact description. Neil McLaughlin ----- Original Message -----=20 From: Gribb, Gil=20 To: Gdalgorithms-List=20 Sent: Friday, November 30, 2001 8:23 AM Subject: RE: [Algorithms] Bsp and collision detection In this day and age, I would say bsp trees are a fairly lousy solution to the collision detection problem. Modern geometry does not bsp well. People use it because they don't know any other way to do it. -Gil > Hi everyone, > i just can stop finding everyone talking about how fast, easy=20 > and pleasant > to write was collision detection using bsp trees. But=20 > unfortunately, even > though google helps, i couldn't find nothing interesting enough to get > started with it. > Does anyone have references, links, papers, websites, that=20 > would help a lot > ? >=20 > I was also wondering whether those algorithms could be used=20 > also in a hybrid > engine (octree with mini-bsp inside for instance), or does=20 > general collision > detection algorithms for the octree and then for the bsp have to be > performed ? How does one do it when using multiple data=20 > structures like this > ? >=20 > Thanks in advance > R=E9my Rakic >=20 >=20 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >=20 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list |
From: <phi...@pl...> - 2001-11-30 18:40:29
|
Super Monkey Ball on the GC does pretty convincing sphere-curved surfac= e collision. Mind you, that's pretty much all it does... ...besides, collision detection itself isn't the hard part. The hard pa= rt is responding... Cheers, Phil = =20 "Neil McLaughlin" = =20 <bi...@me...> To: = "Gdalgorithms-List" =20 Sent by: <gdalgor= ith...@li...> =20 gda...@li...urc cc: = =20 eforge.net Subject:= Re: [Algorithms] Bsp and collision =20 detectio= n =20 = =20 11/30/2001 04:46 AM = =20 = =20 = =20 Hello, Collision Detection=A0can't be that easy because I still haven't seen convincing collisions in any games or simulations. Not on curved surfa= ces anyhow.=A0=A0Just=A0bounding box or sphere approximations.=A0=A0 Let's= see some curved surfaces like a marble rolling around inside a network of pipes = or a toilet or something.=A0 How about two ropes colliding?=A0 Does anyone = know of such simulations available? For years now everyone seems focused on cosmetics - multitextures and lighting and shadows (which are also just approximations).=A0=A0=A0 So= games look so much prettier=A0but=A0they still don't work.=A0=A0=A0Could thi= s explain why 2D games are still a huge hit?=A0=A0I'd like to see better simulations= that feature=A0infinite scalablity and curved surface interaction and seaml= ess articulation. Polygons in general will never support real collisions - so having=A0a= separate 3d Editor spit out triangles and then trying to manipulate th= em convincingly with a 3d Engine will never work - no matter what the processor power or bandwidth.=A0=A0=A0We need a higher level 3d primit= ive if we're ever going to simulate reality, and once we have such an (implic= it) format, we can directly point sample versus tesselate. Neil McLaughlin ----- Original Message ----- From: R=E9my Rakic To: Gdalgorithms-List Sent: Friday, November 30, 2001 6:05 AM Subject: [Algorithms] Bsp and collision detection Hi everyone, i just can stop finding everyone talking about how fast, easy and plea= sant to write was collision detection using bsp trees. But unfortunately, e= ven though google helps, i couldn't find nothing interesting enough to get= started with it. Does anyone have references, links, papers, websites, that would help = a lot ? I was also wondering whether those algorithms could be used also in a hybrid engine (octree with mini-bsp inside for instance), or does general collision detection algorithms for the octree and then for the bsp have to be performed ? How does one do it when using multiple data structures like= this ? Thanks in advance R=E9my Rakic _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list = |