Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
32 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

Interface class woes

Started by
8 comments, last by doctorsixstring 19 years, 8 months ago
I want to implement a set of Shape classes to be used for collision detection, visibility culling, and picking. I want to be able to test for intersection between a combination of any two shapes, like this: 

Shape* sphere = new Sphere(D3DXVECTOR3(0.0f, -5.0f, 10.0f), 10.0f);
Shape* line_segment = new Segment(D3DXVECTOR3(0.0f, 0.0f, 10.0f), D3DXVECTOR3(-5.0f, 0.0f, 5.0f));

int test_result = sphere->TestIntersection(line_segment);
My current implementation works, but it is not very elegant. As you might guess from above, I have a Shape interface class that all shapes derive from. This interface class contains a "TestIntersection()" function that takes as a parameter all other shape classes, and is therefore implemented in all shape classes. Here is the definition of the Shape interface class, plus an example child class: Shape interface class 

struct Shape
{
	virtual int TestIntersection(Point) = 0;
	virtual int TestIntersection(Segment) = 0;
	virtual int TestIntersection(Ray) = 0;
	virtual int TestIntersection(Line) = 0;
	virtual int TestIntersection(Plane) = 0;
	virtual int TestIntersection(Sphere) = 0;
	virtual int TestIntersection(Box) = 0;
	virtual int TestIntersection(Cone) = 0;
	virtual int TestIntersection(Cylinder) = 0;
};

struct Sphere : public Shape
{
	D3DXVECTOR3 m_center;	// center of sphere in model space
	float m_sphere_radius;	// radius of sphere

	Sphere();
	Sphere(D3DXVECTOR3 center, float sphere_radius);

	int TestIntersection(Point);
	int TestIntersection(Segment);
	int TestIntersection(Ray);
	int TestIntersection(Line);
	int TestIntersection(Plane);
	int TestIntersection(Sphere);
	int TestIntersection(Box);
	int TestIntersection(Cone);
	int TestIntersection(Cylinder);
};
As you can see, I need to modify the interface class every time I want to add a new type of shape. Is there a cleaner way to do this? The "proper OO" method? Thanks in advance, Mike
Advertisement
I had a similar problem in one of my programs at work - I solved it by having essentially a map of functors indexed by a pair of object types. You'd register the functors with a generic collision system and for a given collision, look up the two type collision pair from your system and call the functor. Essentially you pull the collision out of the classes and have a separate manager class to do the collision tests between objects.

It's pretty much the only way I found that did what I wanted without having to manually maintain each class with extra collisions. Plus the way it sis now makes it impossible to add user collision types.
Regardless of whether I use functors or not, I would basically need a class like this, correct?

class CollisionSystem{public:	int TestIntersection(Point* point, Point* another_point);	int TestIntersection(Point* point, Segment* segment);	int TestIntersection(Point* point, Ray* ray);	int TestIntersection(Point* point, Line* line);	int TestIntersection(Point* point, Plane* plane);	int TestIntersection(Point* point, Sphere* sphere);	int TestIntersection(Point* point, Box* box);	int TestIntersection(Point* point, Frustum* frustum);	int TestIntersection(Point* point, Cone* cone);	int TestIntersection(Point* point, Cylinder* cylinder);	int TestIntersection(Segment* segment, Point* point);	int TestIntersection(Segment* segment, Segment* another_segment);	int TestIntersection(Segment* segment, Ray* ray);	int TestIntersection(Segment* segment, Line* line);	int TestIntersection(Segment* segment, Plane* plane);	int TestIntersection(Segment* segment, Sphere* sphere);	int TestIntersection(Segment* segment, Box* box);	int TestIntersection(Segment* segment, Frustum* frustum);	int TestIntersection(Segment* segment, Cone* cone);	int TestIntersection(Segment* segment, Cylinder* cylinder);	int TestIntersection(Ray* ray, Point* point);	int TestIntersection(Ray* ray, Segment* segment);	int TestIntersection(Ray* ray, Ray* another_ray);	int TestIntersection(Ray* ray, Line* line);	int TestIntersection(Ray* ray, Plane* plane);	int TestIntersection(Ray* ray, Sphere* sphere);	int TestIntersection(Ray* ray, Box* box);	int TestIntersection(Ray* ray, Frustum* frustum);	int TestIntersection(Ray* ray, Cone* cone);	int TestIntersection(Ray* ray, Cylinder* cylinder);	int TestIntersection(Line* line, Point* point);	int TestIntersection(Line* line, Segment* segment);	int TestIntersection(Line* line, Ray* ray);	int TestIntersection(Line* line, Line* another_line);	int TestIntersection(Line* line, Plane* plane);	int TestIntersection(Line* line, Sphere* sphere);	int TestIntersection(Line* line, Box* box);	int TestIntersection(Line* line, Frustum* frustum);	int TestIntersection(Line* line, Cone* cone);	int TestIntersection(Line* line, Cylinder* cylinder);	int TestIntersection(Plane* plane, Point* point);	int TestIntersection(Plane* plane, Segment* segment);	int TestIntersection(Plane* plane, Ray* ray);	int TestIntersection(Plane* plane, Line* line);	int TestIntersection(Plane* plane, Plane* another_plane);	int TestIntersection(Plane* plane, Sphere* sphere);	int TestIntersection(Plane* plane, Box* box);	int TestIntersection(Plane* plane, Frustum* frustum);	int TestIntersection(Plane* plane, Cone* cone);	int TestIntersection(Plane* plane, Cylinder* cylinder);	int TestIntersection(Sphere* sphere, Point* point);	int TestIntersection(Sphere* sphere, Segment* segment);	int TestIntersection(Sphere* sphere, Ray* ray);	int TestIntersection(Sphere* sphere, Line* line);	int TestIntersection(Sphere* sphere, Plane* plane);	int TestIntersection(Sphere* sphere, Sphere* another_sphere);	int TestIntersection(Sphere* sphere, Box* box);	int TestIntersection(Sphere* sphere, Frustum* frustum);	int TestIntersection(Sphere* sphere, Cone* cone);	int TestIntersection(Sphere* sphere, Cylinder* cylinder);	int TestIntersection(Box* box, Point* point);	int TestIntersection(Box* box, Segment* segment);	int TestIntersection(Box* box, Ray* ray);	int TestIntersection(Box* box, Line* line);	int TestIntersection(Box* box, Plane* plane);	int TestIntersection(Box* box, Sphere* sphere);	int TestIntersection(Box* box, Box* another_box);	int TestIntersection(Box* box, Frustum* frustum);	int TestIntersection(Box* box, Cone* cone);	int TestIntersection(Box* box, Cylinder* cylinder);	int TestIntersection(Frustum* frustum, Point* point);	int TestIntersection(Frustum* frustum, Segment* segment);	int TestIntersection(Frustum* frustum, Ray* ray);	int TestIntersection(Frustum* frustum, Line* line);	int TestIntersection(Frustum* frustum, Plane* plane);	int TestIntersection(Frustum* frustum, Sphere* sphere);	int TestIntersection(Frustum* frustum, Box* box);	int TestIntersection(Frustum* frustum, Frustum* another_frustum);	int TestIntersection(Frustum* frustum, Cone* cone);	int TestIntersection(Frustum* frustum, Cylinder* cylinder);	int TestIntersection(Cone* cone, Point* point);	int TestIntersection(Cone* cone, Segment* segment);	int TestIntersection(Cone* cone, Ray* ray);	int TestIntersection(Cone* cone, Line* line);	int TestIntersection(Cone* cone, Plane* plane);	int TestIntersection(Cone* cone, Sphere* sphere);	int TestIntersection(Cone* cone, Box* box);	int TestIntersection(Cone* cone, Frustum* frustum);	int TestIntersection(Cone* cone, Cone* another_cone);	int TestIntersection(Cone* cone, Cylinder* cylinder);	int TestIntersection(Cylinder* cylinder, Point* point);	int TestIntersection(Cylinder* cylinder, Segment* segment);	int TestIntersection(Cylinder* cylinder, Ray* ray);	int TestIntersection(Cylinder* cylinder, Line* line);	int TestIntersection(Cylinder* cylinder, Plane* plane);	int TestIntersection(Cylinder* cylinder, Sphere* sphere);	int TestIntersection(Cylinder* cylinder, Box* box);	int TestIntersection(Cylinder* cylinder, Frustum* frustum);	int TestIntersection(Cylinder* cylinder, Cone* cone);	int TestIntersection(Cylinder* cylinder, Cylinder* another_cylinder);};


note: You may notice semi-duplicate functions in there, like TestIntersection(Ray*, Line*) and TestIntersection(Line*, Ray*). One of the functions would simply call the other, to allow the functions to be used either way.

It would be quite large, and it really seems like there could be a better way. Every time a new class is added I would add another block of TestIntersection() functions.

evolutional, with your method of using the shape pair as an index to functors, how do you get the type of the shapes at run-time? Do you simply have a GetType() function and an enumerated list of object types?

Any other thoughts?

- Mike
Take a look at this article and see if you can use it:

TITLE: Another example of multiple dispatching


[ This tip is here so you can recognize evil when you see it.
Don't use multiple dispatching. Its klunky and does not maintain
well. -adc ]


PROBLEM: scofield@apollo.HP.COM (Cary Scofield)

Recently, I heard someone, in the context of describing an invocation
technique in object-oriented programming, use the phrase "double
dispatching" (as a particular case of "multi-way dispatching"),
saying that it was an idea borrowed from CLOS and that it could be
done in C++.

Would any of you OO/C++ geeks care to shed some light on this
particular topic, please?


RESPONSE: rmartin@rcmcon.com (Robert Martin), 1 Feb 94

Single dispatch is simple. The function selected depends upon the
type that it is applied to. If we say shape->draw(), then the actual
draw function that is called depends upon the type of the shape. If
the shape is a square, the draw function for square is called. If it
is a circle then the draw function for circle is called.

Multi-dispatch is similar, except that the actual function called
depends upon more than one type. Consider:

double IntersectionArea(const Shape&, const Shape&);

What function can be used to calculate the intersection area of two
shapes? It depends upon the the types of the two shapes. The
algorithm will be different for every different combination of shapes.

Assume that there are three different derivatives of Shape: Circle,
Square and Polygon. Then we would need to write:

double IntersectionArea(const Square&, const Square&)
double IntersectionArea(const Square&, const Circle&)
double IntersectionArea(const Square&, const Polygon&)
double IntersectionArea(const Circle&, const Square&)
double IntersectionArea(const Circle&, const Circle&)
double IntersectionArea(const Circle&, const Polygon&)
double IntersectionArea(const Polygon&, const Square&)
double IntersectionArea(const Polygon&, const Circle&)
double IntersectionArea(const Polygon&, const Polygon&)

This covers all the cases. However it does not help us with
polymorphism.

Shape& x = /* some derivative */;
Shape& y = /* some derivative */;
double area = IntersectionArea(x,y); // This has no meaning since we
// don't know the true types.

We can simulate double polymorphic dispatch in C++ by using a nasty
trick. Unfortunately, this trick breaks the nice dependency structure
of the OO code; as you'll see.

class Shape
{
public:
virtual double IntersectionArea(const Shape&) = 0;
virtual double CircleIntersectionArea(const Circle&) = 0;
virtual double SquareIntersectionArea(const Square&) = 0;
virtual double PolygonIntersectionArea(const Polygon&) = 0;
};

class Square : public Shape
{
public:
virtual double IntersectionArea(const Shape& s)
{return s.SquareIntersectionArea(*this);}

virtual double CircleIntersectionArea(const Circle& c)
{return IntersectonArea(*this, c);}

virtual double SquareIntersectionArea(const Square& s)
{return IntersectionArea(*this, s);}

virtual double PolygonIntersectionArea(const Polygon& p)
{return IntersectionArea(*this, p);}
};

// I leave the other derivatives as an excersize.

double IntersectionArea(const Shape& s1, const Shape& s2)
{
return s1.IntersectionArea(s2);
}

Now we have a polymorphic double dispatch. This works, but it has the
unfortunate characteristic that the source code for the base class
depends upon the source code for the derived classes. This thwarts one
of the strongest benefits of OO, the ability to isolate abstractions
from details.

Still, if you have reason to believe that there will not be any (or
many) more derivatives of Shape in the future, then this mechanism has
some benefit.

Clearly, if there will be many more derivatives of Shape in the
future, then this method is unmanagable simply due to the geometric
explosion of cominations.

Forged3D world editor
I think you have pushed interface abstraction to too fine a level of granuality.

The code that is looking for a collision will know the bounding volume the best - e.g. the viewing frustrum is a different "volume" than a raycast line for picking, but both are a collision detection problem.

The scene graph should have a simple and fast object culling mechanism - e.g oct-tree or sphere-tree. It's objective is to reduce the solution space to something manageable - not find the exact boundries and conditions of the collision.

e.g. Find a sphere that encompasses the viewing frustrum, use that sphere to quickly cull the impossible objects, then perform plane clipping on this (greatly reduced) set of objects. Your plane clipping function should understand your scene graph - the tree of meshes and accompying data (e.g. pre-calculated bounding spheres).

For picking, you would again cull using the sphere of the view-frustrum, and then test for interection with the raycast segment.

This way you have to write one function for each shape that clips a scene graph, not an untrackable combinatorial explosion.

This is just the beginning, collision detection becomes massively more complicated once objects start moving and you want to find the point-in-time that intersection occured. You have to work with slices of time, so if you detect a (potential) collision within that time slice, you may need to figure out when that potential intersection occured so you can see if the objects where at the correct position to collide. If the time slice was very long, a railgun raycast would be like a kill-wire, but the slug only occupies a small portion of segment at a given instance, not the whole segment simutaneously. Figure out the time the intersection could have occured at, and you can figure out if both objects occupied the same space at the same time (direct hit!).
- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
If you're looking at double dispatch, check out Modern C++ Design, there's a chapter about it in there.
[email=algorhythmic@transcendenz.co.uk]algorhythmic[/email] | home | xltronic | whatever you do will be insignificant, but it is very important that you do it - mahatma gandhi
Magmai - Are you saying that instead of creating a set of shapes that can intersect in any possible combination, I should put shape-combo-specific code exactly where it is needed in the engine? For instance, the line segment intersection code would go in the Pick() function of my scene graph, and object collisions would be in some sort of Entity->TestCollision(Entity*) function?

What happens when I want to add laser beam weapons that will also use line intersection with various shapes? Or if I want the line to be able to project itself fully across the frustum so that it gives the illusion of having infinite length? Could you post some example pseudo-code of your design?

So far, it seems like having a shape-independent class (CollisionSystem) that contains all collision code is the best solution. Each shape class would only contain the geometry needed to define the shape (center point, radius, length, etc.). When a new shape class is added, I can simply add a new block of functions.

Also, I have been doing some research on double/multiple-dispatch. Although, I prefer my solution above.

- Mike
I'm weighing in against DD; I like your method sans the virtual functions. You'd call sg->pick(my_line,...) or sg->frustrum_cull(fustrum, ...) as opposed to sg->collide(some_shape).

Otherwise this is going to be an n! coding problem, and n will about double when you consider moving volumes. That's incredible number of functions to write! Or you need to sort the parameters by dynamic type, then you'll just have n<super>2</super> functions to write (which is still alot!). More work to code, more work at runtime, for the flexibility to have unknown bounding volumes at run-time (which are generally known at compile time).

Quote:
What happens when I want to add laser beam weapons that will also use line intersection with various shapes? Or if I want the line to be able to project itself fully across the frustum so that it gives the illusion of having infinite length? Could you post some example pseudo-code of your design?

The laser beam only needs to interact with a couple of shapes, the the bounding volume (sphere), the time-dialated bounding volume (capsule), triangles, and time-dilated triangles (three-sided box). Even the laser beam needs to be drawn using finite triangles, which means CD works the same for it as abything else.
A frustrum is 6 planes; you need to find scene graph nodes "above" the plane, and you need to support the same 4 shapes as the segment when doing so.

[Edited by - Magmai Kai Holmlor on August 22, 2004 4:18:27 PM]
- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
The solution that I'm using is to simply have a monostate which has the intersection test functions. The difference between what is being presented here is that we don't support tests between every different possible type of geometric object that you can think of. We only have support for those that are needed by the engine. Essentially it boils down to this: The world is in an AABB tree, the entities use sphere hierarchies, the weapons use lines, and then of course the frustum.

That leaves us with the following:
AABB to Sphere (for entity world collision)
AABB to Line (for weapons to world and ground clamping)
AABB to Frustum (for scene culling)
Line to Sphere (for weapon to entity)
Line to Line (for weapon to weapon)
Sphere to Sphere (for entity to entity)
*edit: I forgot to add that we do have line to triangle for use after the AABB has been found when the actual surface test is needed.

The point I'm trying to make is that unless you know you'll need forty million types of intersection tests, only write what you need. (Unless, of course, this is just an exercise in which case never mind ;P)

"You aren't going to need it"

As far as the actual collision detection "system" goes, I have been experimenting with double dispatch using a custom, lightweight, RTTI system along with some hash tables. I highly recommend checking out Modern C++ Design, as mentioned above. It has a good treatment on the topic.

Good luck!
- Jason Citron- Programmer, Stormfront Studios- www.stormfront.com
Thanks for the replies, guys. After playing around with my solution a bit, I realized that it would be way too much to code, and too difficult to implement. In addition, it doesn't look like a fundamental part of my code will work. I have dozens of TestIntersection() functions, each with two arguments (each a pointer to an object of a shape child class). The problem is that passing two generic Shape* pointers into the function doesn't work. The compiler can't figure out which function to call.

Therefore, I started working on a design similar to what you guys are describing. I made a list of all cases in which intersection testing would be needed (much like what Clash posted).

I think what I will do is write only the intersection functions I need for each object, based on my list of cases. For instance, the Frustum class would have the following member functions, used when culling a spatial tree (quadtree, octree, BSP):

TestIntersection_Sphere
TestIntersection_Box
TestIntersection_Cylinder
TestIntersection_QuadtreeNode
TestIntersection_OctreeNode

I'm going to keep working on this, and I will let you guys know how it ends up. Feel free to post any other suggestions/comments.

Thanks!

- Mike

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
AliAbdulKareem
Understanding the wavy-like shape in alpha-testing magnification for text rendering Graphics and GPU Programming
Advertisement

Recommended Tutorials

wwwwww
wwww Game Design and Theory
h4tt3n
Towards a Simpler, Stiffer, and more Stable Spring Math and Physics
Unlock Audio
Designing Synthesizer Patches Music and Sound FX
Gaiiden
The Core Mechanics of Influence Mapping Artificial Intelligence
Alconost
Continuous Localization for Software Development Companies Production and Management

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top