(Beginner?) Design Question

[Brian Byrne]

Happy Thanksgiving everyone,

I have a collection of various simple geometric objects (point, ray,
cube, box, sphere, pyramid, etc) and I want to write (fast, and thus
specific) functions that returns whether two objects intersect. I am
unsure how to structure this setup.

I see it in two basic ways. First, in each class I could add a member
function:

class Ray {
...
bool Intersects( const Box& box ) { ... }
bool Intersects( const Sphere& sphere ) { ... }
bool Intersects( ... ) { ... } /* Rest of objects */
...
};

Or I could place all "bool Intersects( ..., ... )" functions in a
single file for all pairs:

bool Intersects( const Ray& ray, const Box& box ) { ... }
....
bool Intersects( const Box& box, const Sphere& sphere ) { ... }
....

My number of geometric objects is limited so that writing all (N choose
2) functions is managable.

The first way seems more advantageous if each geometric object had a
common subclass (is this true?), but it seems messier because every
geometric class has to be able to "see" every other geometric class.
For example, adding a cone class would require me to edit every single
file. The second way seems more abstract in that each object need not
know of the others and all intersection code is centralized into a
single area.

Is there a better, solid, or more convectional way of doing this?

Thanks in advance,
Brian Byrne

 

[Ondra Holub]

Brian Byrne napsal:

Happy Thanksgiving everyone,

I have a collection of various simple geometric objects (point, ray,
cube, box, sphere, pyramid, etc) and I want to write (fast, and thus
specific) functions that returns whether two objects intersect. I am
unsure how to structure this setup.

I see it in two basic ways. First, in each class I could add a member
function:

class Ray {
...
bool Intersects( const Box& box ) { ... }
bool Intersects( const Sphere& sphere ) { ... }
bool Intersects( ... ) { ... } /* Rest of objects */
...
};

Or I could place all "bool Intersects( ..., ... )" functions in a
single file for all pairs:

I would use the second variant (separate functions).

One additional hint (which you probably know): You do not need all the
pairs, because intersection of A and B is the same as intersection of B
and A, so you can call only the other functions with swapped parameters.

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Happy Thanksgiving everyone,

I have a collection of various simple geometric objects (point, ray,
cube, box, sphere, pyramid, etc) and I want to write (fast, and thus
specific) functions that returns whether two objects intersect. I am
unsure how to structure this setup.

I see it in two basic ways. First, in each class I could add a member
function:

class Ray {
...
bool Intersects( const Box& box ) { ... }
bool Intersects( const Sphere& sphere ) { ... }
bool Intersects( ... ) { ... } /* Rest of objects */
...
};

Or I could place all "bool Intersects( ..., ... )" functions in a
single file for all pairs:

bool Intersects( const Ray& ray, const Box& box ) { ... }
...
bool Intersects( const Box& box, const Sphere& sphere ) { ... }
...

My number of geometric objects is limited so that writing all (N choose
2) functions is managable.

That depends on how large N you have, a quick calculation by me (which
means that it's not guaranteed to be correct) gives (N(N+1))/2 functions
for N objects (that's O(N^2)).

The first way seems more advantageous if each geometric object had a
common subclass (is this true?), but it seems messier because every
geometric class has to be able to "see" every other geometric class.

You mean common base-class right?

For example, adding a cone class would require me to edit every single
file. The second way seems more abstract in that each object need not
know of the others and all intersection code is centralized into a
single area.

Is there a better, solid, or more convectional way of doing this?

Can't really help you but if I were you I'd spend a couple of hours
thinking about finding a generic way to find out if two shapes
intersect, perhaps by dividing them into smaller pieces and see if the
pieces intersect. If you can do this then you can let them all derive
from a common base-class Shape. Then define a method
bool intersect(Shape& s)
which you override in each subclass. If you can manage this then you
only have to implement one method, that checks if a Shape intersect with
it, for each shape. This should be possible for simpler shapes.

 

[IR]

Happy Thanksgiving everyone,

I have a collection of various simple geometric objects (point,
ray, cube, box, sphere, pyramid, etc) and I want to write (fast,
and thus specific) functions that returns whether two objects
intersect. I am unsure how to structure this setup.

I see it in two basic ways. First, in each class I could add a
member function:

class Ray {
...
bool Intersects( const Box& box ) { ... }
bool Intersects( const Sphere& sphere ) { ... }
bool Intersects( ... ) { ... } /* Rest of objects */
...
};

Or I could place all "bool Intersects( ..., ... )" functions in a
single file for all pairs:

bool Intersects( const Ray& ray, const Box& box ) { ... }
...
bool Intersects( const Box& box, const Sphere& sphere ) { ... }
...

My number of geometric objects is limited so that writing all (N
choose 2) functions is managable.

If I'm not mistaken, the number of needed functions is N^2 for N
object types, of which you really need to implement only N(N+1)/2 as
Ondra and Erik pointed it out (which leaves N(N-1)/2 inline
forwarders).

The first way seems more advantageous if each geometric object had
a common subclass,

All the objects you mentionned (but the ray) should really derive
from a common class "BoundingSphere". This is the cheapest way I
know of, to be able to tell if two objects _may_ intersect, before
doing the real (and expensive, yet specific) computations.

You just need to ensure a BoundingSphere's center and radius are
adjusted by it's derived class everytime it is moved/resized, to
maintain the invariant.

(is this true?) but it seems messier because
every geometric class has to be able to "see" every other
geometric class. For example, adding a cone class would require me
to edit every single file. The second way seems more abstract in
that each object need not know of the others and all intersection
code is centralized into a single area.

Is there a better, solid, or more convectional way of doing this?

I'd personnaly go for the second way you mentionned, which seems
cleaner.

Additionnaly, I'd use a common ancestor for all objects (including
rays), which would allow for a "generic" dispatcher function in case
you only have references or pointers to base objects.

Something like...

struct SpatialObject
{
// Override in each subclass. The subclass knows it's own type,
// so it only has to dynamically determine other's type before
// calling the appropriate Intersects overload.
virtual bool Intersects(const SpatialObject& other) const = 0;
};

bool Intersects(const Ray&, const Box&);
//...

Note that this design is only useful if you need runtime
polymorphism, which is very likely IMO even though you didn't
mention it.

Hope this helps a bit.

 

[David Harmon]

On 23 Nov 2006 11:58:27 -0800 in comp.lang.c++, "Brian Byrne"

Is there a better, solid, or more convectional way of doing this?

This seems obviously to be the kind of problem where a few weeks of
carefree trial and error hacking can save hours of boring research... or
at least postpone it. For the N x N aspect of things, look for "double
dispatch" or "visitor pattern".