## D - Double Sided Virtual...or something like that

- Russ Lewis (35/35) Mar 10 2003 Here's a question for all of you programming gurus to figure out:
- Bill Cox (61/80) Mar 11 2003 Isn't this just a multi-method? I doubt that there is any nice
- Russell Lewis (17/17) Mar 11 2003 The problem I'm trying to solve is to determine the time of first/next
- Sean L. Palmer (14/31) Mar 11 2003 That's funny; this is exactly what Geometric Algebra is good for. Just...
- Russ Lewis (14/25) Mar 12 2003 The page is incredibly dense. The background doesn't make things too ea...
- Russ Lewis (8/10) Mar 12 2003 (I've also already done some research into using 5x5 matrices to model s...
- Sean L. Palmer (13/18) Mar 12 2003 From what I understand, a 5x5 matrix would be quite overspecified.
- Juarez Rudsatz (9/30) Mar 12 2003 Ok. I agree.
- Mike Wynn (1/14) Mar 12 2003 what does C# do ?
- Russ Lewis (17/26) Mar 15 2003 Thanks for the links. sommer is still to fast for me, but I found
- Bill Cox (13/37) Mar 11 2003 Ok, sounds like a real application for multimethods. Frankly, I'd just
- Burton Radons (60/64) Mar 11 2003 But common - the rigid-body physics library ODE does this. You can just...
- Walter (5/9) Apr 18 2003 That's what I'd do. Not the most elegant design, but if you put in a few
- Jeroen van Bemmel (4/4) Mar 11 2003 Scott Meyers gives a nice overview of this issue in "More effective C++"

Here's a question for all of you programming gurus to figure out: I have a class, called Shape, which is the base for lots of other classes. For some combinations of those types, I have defined interactions: void Foo(ShapeChild1,ShapeChild2); void Foo(ShapeChild1,ShapeChild3); void Foo(ShapeChild1,ShapeChild4); void Foo(ShapeChild3,ShapeChild4); I have an interface function that takes two Shape objects as its parameters: void Foo(Shape,Shape); Q: What is an easy, readable, and runtime-efficient way to have Foo(Shape,Shape) figure out which of the implementations to call based on the types of the arguments? That is, if the first Shape happens to actually be a ShapeChild1 and the second is a ShapeChild4, then I want Foo(Shape,Shape) to call Foo(ShapeChild1,ShapeChild4). Restrictions: 1) I need to support the ability to extend this library to include new Shape* classes...without changing the interface function Foo(Shape,Shape). So hard coding nested switches is NOT going to work. 2) I need to automatically detect (and throw an exception) if Foo(Shape,Shape) is called and there is no implementation for a given pair. It would be even better if I could determine at init time that there were some implementations missing. 3) I need to be able to support multiple add-ons to the library which might not know about each other. So making a requirement that "all addons must know about all previous shapes" won't be workable. Thoughts, guys? I have come up with any number of inelegant solutions...I figure that somebody here has a better one. Russ -- The Villagers are Online! http://villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]

Mar 10 2003

Russ Lewis wrote:Here's a question for all of you programming gurus to figure out: I have a class, called Shape, which is the base for lots of other classes. For some combinations of those types, I have defined interactions: void Foo(ShapeChild1,ShapeChild2); void Foo(ShapeChild1,ShapeChild3); void Foo(ShapeChild1,ShapeChild4); void Foo(ShapeChild3,ShapeChild4); I have an interface function that takes two Shape objects as its parameters: void Foo(Shape,Shape);[snip]Thoughts, guys? I have come up with any number of inelegant solutions...I figure that somebody here has a better one. RussIsn't this just a multi-method? I doubt that there is any nice implementation in D, or C++. We're stuck with emulating them. I'm basically against adding them to D. I've looked around a bit on the web, and haven't been convinced that D needs multimethods. If you're intersted, I've commented on what I found in a couple hours of browsing. ----------------------------------------- Multi-methods have been added to several statically compiled languages, including C++, Java, and Perl. IMO, advocates seem to have polymorphism fevor. Here's a web page that seems to exemplify this: http://www.yetanother.org/damian/seminars/Multimethods.html However, in a couple hours of searching, I couldn't find any major problems where multimethods are the only solution, or IMO the best solution. I checked a few intro pages to the language mentioned extensions above. I found two examples used. The first one problems mentioned was shape merging, where we want custom merge routines for merging squares and polygons, triangles and squares, etc. Given N shape types, you can write N*N merge routines, and call them as a multimethod. A better solution would be to convert all shapes to a generic type (for example, a polygon), write one merge routine, and then write routines to convert them back. That takes 2N+1 functions. If speed is the reason we're writing custom functions, then we probably need custom dispatch code as well. For example, if 99% of our shapes are rectangles (as is the case in EDA), you want to check for merging two rectangles first. The second problem mentioned was reading many types of documents (PDF, postscript, MS Word, etc), and rendering on multiple kinds of devices (printer, screen, ...). Writing custom routines for each of these combinations is a terrible idea. Anyone remember when each company writing DOS applications had to write custom printer drivers for each printer, as well as a custom screen driver? What a nightmare. Again, the solution is converting to a generic format (a bitmap, for example), and then writing the single format to each device. Digging a bit deeper, I found nice papers on efficient multimethod implementations. I looked for a "motivation" section in them, and found one for extending Java: "Java allows a new subclass to be added to an existing class in a modular way without requiring any modifications to existing code. However, Java (along with all other single-dispatch languages of which we are aware) does not allow a new method to be added to an existing class in a modular way." That's valid concern, but it's also solvable in other ways. For one, we can have "compile-time reflection classes" (as the OpenC++ guyes call it). Alternatively, we could add an extension capability that allows us to add methods to classes in separate source files. This capability has other uses as well. Another problem mentioned in several places is the "visitor" problem. It seems to be a problem that comes up in visiting complex class hierarchies in Java and C++. I read a short presentation on this problem, and at the end they suggested that another aproach to solving it is to write iterators that take call-back functions as parameters. If this seems ugly, then add enhanced iterator support so we can eliminate the call-backs. Another problem with multi-methods is they seem very complex to implement and support in statically compiled languages. I found multiple papers on the web describing novel ways to overcome obscure problems that come up. It looks really hairy. In short, the little bit of poking around I've done hasn't led me to believe multimethods belong in D. Bill

Mar 11 2003

The problem I'm trying to solve is to determine the time of first/next intersection between 2 4D Shapes. The shapes will all have mathematical formulas to represent them, but could be a wide variety of types (moving spheres, toroids, boxes, etc.) It is computationally impractical to convert complex 4D shapes into polygons. The two shapes might never intersect; they might intersect but far in the future. Whereever they intersect, I want to be able to determine their intersection with great precision, not an approximation as polygons would give me. The solution, as I see it, is to work out mathematical formulas for each pair of types. I can do that, though it will be hard. Now, I have to figure out how to use the right formula for each pair of types. One (ugly) solution is a 2D associative array of function pointers, taking ShapeID (an enum, probably) as indexes for both. But that seems hackish to me and requires that all of my Shape* classes get assigned their own ID...a problematic design.

Mar 11 2003

That's funny; this is exactly what Geometric Algebra is good for. Just add another dimension that squares to -1 to represent the time axis. For shapes such as spheres and planes you need 4 dimensions. So at minimum you're working on a 5D problem. But GA has these nifty meet and join operations that make the intersection almost trivial to compute once you have the shapes represented as multivectors of some sufficiently high dimension. http://www.iancgbell.clara.net/maths/geoalg1.htm#A33 If it were possible to represent any of your shapes as an array of multivectors, and were ok with getting arbitrary multivectors back, it could potentially be done with a single routine. Sean "Russell Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message news:3E6E16FD.2000600 deming-os.org...The problem I'm trying to solve is to determine the time of first/next intersection between 2 4D Shapes. The shapes will all have mathematical formulas to represent them, but could be a wide variety of types (moving spheres, toroids, boxes, etc.) It is computationally impractical to convert complex 4D shapes into polygons. The two shapes might never intersect; they might intersect but far in the future. Whereever they intersect, I want to be able to determine their intersection with great precision, not an approximation as polygons would give me. The solution, as I see it, is to work out mathematical formulas for each pair of types. I can do that, though it will be hard. Now, I have to figure out how to use the right formula for each pair of types. One (ugly) solution is a 2D associative array of function pointers, taking ShapeID (an enum, probably) as indexes for both. But that seems hackish to me and requires that all of my Shape* classes get assigned their own ID...a problematic design.

Mar 11 2003

"Sean L. Palmer" wrote:That's funny; this is exactly what Geometric Algebra is good for. Just add another dimension that squares to -1 to represent the time axis. For shapes such as spheres and planes you need 4 dimensions. So at minimum you're working on a 5D problem. But GA has these nifty meet and join operations that make the intersection almost trivial to compute once you have the shapes represented as multivectors of some sufficiently high dimension.http://www.iancgbell.clara.net/maths/geoalg1.htm#A33 If it were possible to represent any of your shapes as an array of multivectors, and were ok with getting arbitrary multivectors back, it could potentially be done with a single routine.The page is incredibly dense. The background doesn't make things too easy to read, either. Do you know of another, slower paced, intro to the subject? I saw, in my Computer Graphics course, how you could use 4x4 matrices to represent spheres and ellipsoids of all types. I certainly plan to use that in the Shape* class that handes ellipsoids. This multivector thing sounds like the same general idea, but generalized to N dimensions. Is that a fair analysis? In what way are multivectors different from transform matrices? Those, too, were sets of orthogonal vectors in a space. -- The Villagers are Online! http://villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]

Mar 12 2003

Russ Lewis wrote:I saw, in my Computer Graphics course, how you could use 4x4 matrices to represent spheres and ellipsoids of all types.(I've also already done some research into using 5x5 matrices to model spheres & ellipsoids that move or change size over time...) -- The Villagers are Online! http://villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]

Mar 12 2003

From what I understand, a 5x5 matrix would be quite overspecified. Here's a very gentle intro to some basic GA concepts: http://sinai.mech.fukui-u.ac.jp/gcj/software/GAcindy/GAcindy.htm And here's something about your speed: http://carol.wins.uva.nl/~leo/clifford/sommer.pdf There is plenty of material on the web about GA. I haven't tackled your problem but what I've read suggests this is what GA is good at. Check out Gaigen or boost::clifford if you want to do your own experiments. Sean "Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message news:3E6F53E6.993E07A4 deming-os.org...Russ Lewis wrote:spheres &I saw, in my Computer Graphics course, how you could use 4x4 matrices to represent spheres and ellipsoids of all types.(I've also already done some research into using 5x5 matrices to modelellipsoids that move or change size over time...)

Mar 12 2003

"Sean L. Palmer" <seanpalmer directvinternet.com> wrote in news:b4nu31$22vc$1 digitaldaemon.com:ip address is just 4 bytes ( or 4 ints for a v6 (3 ints and 4 bytes for compatibly with v4)) // don't quote me on that its the idea I'm trying to get across.Ok. I agree. The idea is a new representation for version numbers. The storage is not so important at first.assert(int.size == 4, "This code will only run in 32 bits cpus"); that or having the assert put the condition as a string in the message, so; assert( int.size == 4); would give "assert failed 'int.size==4' is not true at line xxxx in File yyyy"Both. Sometimes the check have few information.Automatic versioning? Like C# ? I have sugested only a simple manual versioning.3 - Module version Each module could have a .version property and a .vendor property. They will be assigned within the module:as much as I like the idea, alas it still fails to catch the usual problem .... you forget to increment your version number. the only automated solution I can see is allowing modules to be sectioned each section has its "signature" hashed and that is stored both in the module and any places it is imported.classes and structures could also use this (may be with an included length field as the first member)Yes. It also apply.

Mar 12 2003

what does C# do ?Automatic versioning? Like C# ? I have sugested only a simple manual versioning.3 - Module version Each module could have a .version property and a .vendor property. They will be assigned within the module:as much as I like the idea, alas it still fails to catch the usual problem .... you forget to increment your version number. the only automated solution I can see is allowing modules to be sectioned each section has its "signature" hashed and that is stored both in the module and any places it is imported.

Mar 12 2003

"Sean L. Palmer" wrote:From what I understand, a 5x5 matrix would be quite overspecified. Here's a very gentle intro to some basic GA concepts: http://sinai.mech.fukui-u.ac.jp/gcj/software/GAcindy/GAcindy.htm And here's something about your speed: http://carol.wins.uva.nl/~leo/clifford/sommer.pdf There is plenty of material on the web about GA. I haven't tackled your problem but what I've read suggests this is what GA is good at. Check out Gaigen or boost::clifford if you want to do your own experiments.Thanks for the links. sommer is still to fast for me, but I found http://www.mrao.cam.ac.uk/~clifford/introduction/intro/intro.html, which builds up to the concept of multivectors slowly. It allows somebody like me, who starts understanding only linear algebra, to build up to an understanding of a multivector is. I haven't yet fininshed the intro at that link, and I'm not even close to understanding how I could use multivectors to model shapes. But the experts think that GA is good for everything, including defining the kitchen sink. FWIW, my definition, as I understand so far: A multivector is the linear combination of spaces of different dimensions. Read the link, if anybody's interested. -- The Villagers are Online! http://villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]

Mar 15 2003

Russell Lewis wrote:The problem I'm trying to solve is to determine the time of first/next intersection between 2 4D Shapes. The shapes will all have mathematical formulas to represent them, but could be a wide variety of types (moving spheres, toroids, boxes, etc.) It is computationally impractical to convert complex 4D shapes into polygons. The two shapes might never intersect; they might intersect but far in the future. Whereever they intersect, I want to be able to determine their intersection with great precision, not an approximation as polygons would give me. The solution, as I see it, is to work out mathematical formulas for each pair of types. I can do that, though it will be hard. Now, I have to figure out how to use the right formula for each pair of types. One (ugly) solution is a 2D associative array of function pointers, taking ShapeID (an enum, probably) as indexes for both. But that seems hackish to me and requires that all of my Shape* classes get assigned their own ID...a problematic design.Ok, sounds like a real application for multimethods. Frankly, I'd just write a big if-then-else statement by hand to do the dispatch. Any programmer reading it will understand it right away, and maintaining it is not hard compared to writing all the functions. To get better speed, you could do a switch on a combination of the enumerated types, although that's pretty ugly. It C++, it would look something like: switch((typeA << SHAPE_TYPE_BITS) | typeB) { case SHAPE_A | SHAPE_A: return findIntersections((ShapeA *) a, (ShapeB *) b); ... } Bill

Mar 11 2003

Russell Lewis wrote:One (ugly) solution is a 2D associative array of function pointers, taking ShapeID (an enum, probably) as indexes for both. But that seems hackish to me and requires that all of my Shape* classes get assigned their own ID...a problematic design.But common - the rigid-body physics library ODE does this. You can just use ClassInfo: typedef Intersection delegate(Shape a, Shape b) Intersector; static Intersector[ClassInfo][ClassInfo] intersectList; static void registerIntersector(ClassInfo a, ClassInfo b, Intersector i) { intersectList[b][a] = i; } Intersection intersect(Shape other) { assert(other.classinfo in intersectList); assert(this.classinfo in intersectList[other.classinfo]); return intersectList[other.classinfo][this.classinfo]; } I'm on the fence. This is a helluva painful problem when it comes up, but it's also hard to think of any solution that would envelope a broad selection of its problem scope - my criteria would be incompatible to your own, in fact. When that happens, it indicates to me that the problem is trying to be solved at too high a level. Bringing it down a level lands me at associative arrays of delegates with ClassInfo, with a set of functions for best-match searching - which can be implemented with my templating syntax: /* Breadth-first multimethod search for two arguments. */ $Type multimethodSearch($Type[ClassInfo][ClassInfo] list, Object a, Object b) { ClassInfo ca; ClassInfo cb = b.classinfo; int bestDistance = -1; $Type best; int distance; for ( ; cb !== null; cb = cb.superclass, distance ++) { if (!(cb in list)) continue; $Type[ClassInfo] sublist = list[cb]; int adding; for (ca = a.classinfo; ca !== null; ca = ca.superclass, adding ++) if (ca in sublist && (bestDistance == -1 || distance + adding < bestDistance)) { bestDistance = distance + adding; best = sublist[ca]; break; } } if (bestDistance == -1) throw new Error(a.classinfo.name ~ " and " ~ b.classinfo.name ~ " have no matching method."); return best; } $RType multimethodSearchCall($RType delegate($AType a, $BType b)[ClassInfo][ClassInfo] list, $AType a, $BType b) { return multimethodSearch(list, a, b)(a, b); } ... return multimethodSearchCall(intersectList, this, other);

Mar 11 2003

"Russell Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message news:3E6E16FD.2000600 deming-os.org...One (ugly) solution is a 2D associative array of function pointers, taking ShapeID (an enum, probably) as indexes for both. But that seems hackish to me and requires that all of my Shape* classes get assigned their own ID...a problematic design.That's what I'd do. Not the most elegant design, but if you put in a few contracts to ensure that the IDs are set up correctly, it'll do the job efficiently.

Apr 18 2003

Scott Meyers gives a nice overview of this issue in "More effective C++" Item 31: "Making functions virtual w.r.t. more than one object" See e.g. http://www.paulgrenyer.co.uk/accu/mdevelopers/effectivecpp/, but for actual contents you need to buy the book. I have it, it's quite nice

Mar 11 2003