Thread: [Algorithms] sort and sweep / sweep and prune and just touching objects
Brought to you by:
vexxed72
From: <Pau...@sc...> - 2009-06-18 14:41:20
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Hi guys, I'm running into a few issues with my sort and sweep broad-phase algorithm. It comes down to bounds in an axis with identical values. Most of the stuff i've read about using an array based method for sorting your axis values say a good optimisation (for the overlap test) is to compare bound indices instead of bound values. But in the case where there are identical bound values in the axis, this breaks down since some of them would be reported as overlapping and some would not depending on where they were in the array. Unfortunately this case comes up a lot in our game. So do i need to compare bound values in all cases? Is there another way around this? Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBSjpRynajGqjtoMHxAQiZ2gf/ZcIToOT/o1LNU4RKP70AZtIbEek2lObO g1M7VbLNmgP9vRZUIRcr/4kNi9W/o2IIPguTfNYtOiBWZ5N8cVmgwOzF25DUR2Kq dhF7zPMK5mAZj+e3PBFEJaBwXZFockqBt44ekTV+z4jA3AZfjgvRr+By+oSXc9QU ym566w1L3pUIfwZaj3b2X7IKVG6GeFitQ2s/21QlFUUSBlw9W0N7Alsl8SKhgqrP rHfqSjNKtxjR6at3TApMsS73PMXPZjJJxth7uClwnEy53tEbH3TADVjuFU+EYYIZ qI9dyiqAklFRjir3lI8uwUqJzthzDb5qQZrgNqegORQGB2Z/75Yosw== =xzS9 -----END PGP SIGNATURE----- |
From: Jon W. <jw...@gm...> - 2009-06-18 15:29:48
|
Pau...@sc... wrote: > So do i need to compare bound values in all cases? Is there another way > around this? > In a stable sort, you generally have a tie breaker, such as the "this" pointer of the value in question, in the case of a tie. Sincerely, jw |
From: <Pau...@sc...> - 2009-06-18 16:27:47
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > In a stable sort, you generally have a tie breaker, such as the "this" > pointer of the value in question, in the case of a tie. Hmmm, wouldn't that mean i'd need to do the expensive value vs value test anyway first? ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBSjpq+HajGqjtoMHxAQjxSwf9FZYsHOhF5iq6fAYKT+3HSwpwlVAiahQG WlA5GZvrwS8PkmDUjOqwxMCZdT59T7OgGw7RXvmbZiukoLuFI7gcILT+UKDmCgDB nx+KKSVg67g+EEijKiQnJ1yzX7+hnFdLJAio9IUzAnJGXDbNBzS0ILr5Lf7YoqVK 6yO0jCS4fhef4DKz1I7eQ+RqKhCogIQn5LbICji3Y6yRz61t5zJgyb+uFvuuGzOD 8k8x45n8M8vkjNcBzl50fDqHU4OYl6jkpdwselOp/RUCI7qNz4k5pmnuXlpVSdjC 0dyVDrjrkNjlfqLbGABSmm5SM5edy89zXiaoJPBEYCZ90mW97qx0rQ== =5OzP -----END PGP SIGNATURE----- |
From: Jon W. <jw...@gm...> - 2009-06-18 17:06:14
|
Pau...@sc... wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA256 > > >> In a stable sort, you generally have a tie breaker, such as the "this" >> pointer of the value in question, in the case of a tie. >> > > Hmmm, wouldn't that mean i'd need to do the expensive value vs value test > anyway first? > If the problem is that the same value maps to multiple indices, then I don't see why -- you get a stable sort by checking index (as long as the index relates to the value). If the problem is that the same index maps to multiple values, then yes, you need to check values. If the problem is that you have non-unique values, which map to non-unique indices, but you want an ordering between separate values with the same value/index, then using a tie-breaker is one solution. Sincerely, jw |
From: <Pau...@sc...> - 2009-06-18 17:55:53
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > If the problem is that the same value maps to multiple indices, then I > don't see why -- you get a stable sort by checking index (as long as the > index relates to the value). The values are sorted correctly, the trouble is when i come to detect whether the is a 1d overlap of bounds, i can't check the indices instead of the values because one value maps to many indices in the case of exactly touching objects: i.e. A-------B C-------D E---------F Indices: A B C D E F 0 2 1 4 3 5 So if you were to check C to see if it were before B by index you'd get a positive, but checking E for before B gives a negative even though both B,C and E have the same actual value. Hope i haven't messed that example up :) Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBSjp/mHajGqjtoMHxAQhwfQgAkuRIr44cCNt86GsEVgfqceS2v22QPmHy TlZZSHp5LSdjKGQCbj5YznMzhZdbmNKFj9Xj+DCzG9KQHU1ShBnh5t0xljDiQ9EV aNmMjRo2J7JpqXw+p01rwk9NLuzcNbjxYYDMy8s8ddYDc9Av0eD+IFzSfZIb6Upb mX6PV7BGlGtmeKvLSR46YKpgEF53aHIkY1WF3HF9yprJzqdVlbZzHRONMwO1h47s VvGPFBYdqRBcwQ12WHIOCCLgV6ec7nW5fKbXzOZ4ejh2KMlMEG3o5qu8bVR3LyZY ufN3TlkfU8s4L5JALwH4osJKhvjTGe15bp4JS0MSFm+JkaJXhZqB1A== =wi0P -----END PGP SIGNATURE----- |
From: Jon W. <jw...@gm...> - 2009-06-18 18:20:51
|
Pau...@sc... wrote: > A-------B > C-------D > E---------F > > Indices: > > A B C D E F > 0 2 1 4 3 5 > > So if you were to check C to see if it were before B by index you'd get a > positive, but checking E for before B gives a negative even though both > B,C and E have the same actual value. > In this case, the tie breaker could be that end points are sorted before start points. That goes into the sorting function, not the index testing function. Although if you support resting/touching contact, you probably want the tie breaker to be end points go after beginning points... Sincerely, jw -- Revenge is the most pointless and damaging of human desires. |
From: <Pau...@sc...> - 2009-06-19 08:57:52
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > In this case, the tie breaker could be that end points are sorted before > start points. That goes into the sorting function, not the index testing > function. > Although if you support resting/touching contact, you probably want the > tie breaker to be end points go after beginning points... Someone mailed me off-line and said a way to get around this problem is to artificially bias end points so that min points have their lowest bit cleared from the value and max bits have their lowest bit set, that way a max can never have the same value as a min. Of course this could lead to false positives, but since its a broadphase algorithm this isn't the end of the world. Additionally, if we've entered the realm of false positives you might as well quantise the values to unsigned ints/shorts and then you can compare integers instead of floats... Not sure if that was the same as what you are suggesting (the first part)? Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBSjtMznajGqjtoMHxAQgnOQf/aEsMSMDcFOlDCp9BjJV4W8INk45Mlnuw nGqcK4dMxkfZ/B88pv7S1KmXCuQmpwcnyovKKvsF/kvOsePmyTSKqCrnNAkAkGAx op6SdI7KbBksiqVg6at7ZggQomk3NtNasWpFT/ZDcggbQdYiy6IOt5b2Fg/0p2L9 E8+D5KRX2C9JHX8lxUn3tAxeWgCnEwkbQzS7iE1KF3ePDTeadvq5qO5rRn2Yua41 Zeu+WWxfBN/sK35vxbyyXenbgupiGqjr6YhKaMXSysZO4QX9IGGVBM27C2biOzlJ 8jaggnplGoPXs98SJUbMAXLkgQWJznm8Q/bRmTXdqRl+O3EOZ+VXJw== =8PdK -----END PGP SIGNATURE----- |