🔒 Locked

Intersection Test Design

Started by Opwiz Feb 25, 2005 at 5:45 AM 2 replies 900+ views

Original Post

Feb 25, 2005 at 5:45 AM

Currently I'm having a base interface "Extent" that Ray, Point, Sphere, AABB, etc. classes implements. The interface contains the method TestIntersection(Extent) that is used to test an arbitrary extent for intersection. The method consist of a series of if-else statements to check the type of the extent and then call appropriate intersection method (or throw a NotImplementedException if not possible to test for intersection). This design makes some sense since I test for containment as well as intersection so AABB-Sphere is not the same as Sphere-AABB so no duplicate code exist. Also I need to be able to test two arbitrary extents for intersection, i.e. unknownExtent.TestIntersection(unknownExtent2) works. However, I see a few problems with my current design: 1. My intersection algorithms are not in one place but spread across the code. 2. I feel that intersection code does not really belong in the Ray, Point, etc. classes. 3. I might in some cases want to only test for containment or intersection not both. I might want to be able to test for intersection as well as get the point/line of intersection. Then I'll need to add even more methods which will clutter my classes even more (or even worse result in duplicate code). So does anyone have any idea of how a good design might look like? Any design pattern that might be relevant here?

Eelco

237

Eelco

Feb 25, 2005 at 5:52 AM

yeah these kind of things suck.

sphere.intersect(ray) should callthe same code as ray.intersect(sphere)

however, you dont want any duplicated code ofcource.

i think good old functional programming does a nice job here. just create a bunch of functions for all different intersection tests you want to implement, and redirect the class methods to these functions. (some overhead, but if you were after real speed you wouldnt be writing such a generalized thing)

umbrae

Feb 25, 2005 at 7:00 AM

I'm quite fond of the visitor design pattern but I'm sure another pattern may fit better. The only problem with this pattern is that you get a whole bunch of methods, but it is more elegant than if-else's in my opinion.

This is in pseudo code, however you want to be able to access the collisionHandler class is up to you, it could just be a bunch of C functions. You could also use the singleton design pattern.

class (class name) : (parent / super name)

class Extent    void visit(Extent object)            void acceptPoint(Point object)    void acceptRay(Ray object)    void acceptSphere(Sphere object)    void acceptAABB(AABB object)class collisionHandler    void collidePointPoint(Point object1, Point object2)    void collidePointRay(Point object1, Ray object2)    void collidePointSphere(Point object1, Sphere object2)    void collidePointAABB(Point object1, AABB object2)    void collideRayRay(Ray object1, Ray object2)    void collideRaySphere(Ray object1, Sphere object2)    void collideRayAABB(Ray object1, AABB object2)    void collideSphereSphere(Sphere object1, Sphere object2)    void collideSphereAABB(Sphere object1, AABB object2)    void collideAABBAABB(AABB object1, AABB object2)class Point : Extent    void visit(Extent object)        object.acceptPoint(self)class Ray : Extent    void visit(Extent object)        object.acceptRay(self)        class Sphere : Extent    void visit(Extent object)        object.acceptSphere(self)        class AABB : Extent    void visit(Extent object)        object.acceptAABB(self)class Point : Extent    void acceptPoint(Point object)        collisionHandler.collidePointPoint(self, object)            void acceptRay(Ray object)        collisionHandler.collidePointRay(self, object)            void acceptSphere(Sphere object)        collisionHandler.collidePointSphere(self, object)        void acceptAABB(AABB object)        collisionHandler.collidePointAABB(self, object)                class Ray : Extent    void acceptPoint(Point object)        collisionHandler.collidePointRay(object, self)        void acceptRay(Ray object)        collisionHandler.collideRayRay(self, object)            void acceptSphere(Sphere object)        collisionHandler.collideRaySphere(self, object)        void acceptAABB(AABB object)        collisionHandler.collideRayAABB(self, object)class Sphere : Extent    void acceptPoint(Point object)        collisionHandler.collidePointSphere(object, self)        void acceptRay(Ray object)        collisionHandler.collideRaySphere(object, self)        void acceptSphere(Sphere object)        collisionHandler.collideSphereSphere(self, object)            void acceptAABB(AABB object)        collisionHandler.collideSphereAABB(self, object)class AABB : Extent    void acceptPoint(Point object)        collisionHandler.collidePointAABB(object, self)            void acceptRay(Ray object)        collisionHandler.collideRayAABB(object, self)            void acceptSphere(Sphere object)        collisionHandler.collideSphereAABB(object, self)            void acceptAABB(AABB object)        collisionHandler.collideAABBAABB(self, object)

You set it all off by having two references to the Extents that you want to test...

Extent aExtent b

Then you call

a.visit(b)

b.visit(a)

it doesn't matter.

By the way, all methods are void, replace them with the result that you want (if just simple intersection test then obviously bool, etc).

But you also say that for you it actually does matter what order they are tested in, well then you just have to re-route the appropriate methods to the new ones in collisionHandler. Although I am confused as to the advantage of this.

By the way, if anyone likes the look of this pseudo code, I am currently working on a language that will look like this :).

[Edited by - umbrae on February 25, 2005 4:00:02 PM]

Opwiz

Author

Opwiz

Feb 25, 2005 at 9:58 AM

Quote:
Original post by Eelco
yeah these kind of things suck.

sphere.intersect(ray) should callthe same code as ray.intersect(sphere)

however, you dont want any duplicated code ofcource.

i think good old functional programming does a nice job here. just create a bunch of functions for all different intersection tests you want to implement, and redirect the class methods to these functions. (some overhead, but if you were after real speed you wouldnt be writing such a generalized thing)

Not a bad idea. I'll probably do this.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.