On 5/22/11 4:20 AM, Luc Maisonobe wrote: > Hello, > > The BSP tree code introduced recently into [math] was written > several years ago, in the Java 4 days. The implementation was > already dimension independent (and even topology-independent) and > used simple interfaces like Point (which was a marker interface > without any methods), Hyperplane, Transform ... The > implementations of these interfaces were aware of the dimension, > so for example an hyperplane in 3D is a Plane, but an hyperplane > in 2D is a Line.
Question number 1, is this level of abstraction practically useful? Need to ask this both for dimension and topology. > > This implied lots of casts between types and the developer had to > be aware of what types were currently used. This is tricky and > error-prone, especially when looking at the BSP tree. BSP-tree are > recursive from a geometry point of view: we split space, then > split the resulting half space, the split again and again to > create a large number of convex polytopes which are at least glued > together to form non-convex shapes. BSP-tree are also recursive > from a dimension point of view as for example a 3D shape is > defined in the 3D space, the cutting planes are 2D sub-spaces in > the 3D space, the boundaries (facets) are themselves 2D shapes > (polygons) inside these 2D planes, these 2D shapes are defined by > 2D BSP-trees, which cutting planes are 1D lines, which ... So from > a type point of view we go from 3D to 2D to 1D and use the whole > set of classes and interfaces at each dimension: Hyperplane, > SubHyperplane, SplitSubHyperplane, Point, Region ... > > I am trying to simplify this and use generics to both avoid typing > errors and having a code that can be understood and maintained. A > classical error I have already made a large number of time during > development was to mix dimensions. A typical example occurs while > dealing with hyperplanes, as one can see a point belonging to the > hyperplane both as a point in the n dimensions space or as a point > in the n-1 dimensions hyperplane. I wonder if generics are really the right way to do this. Have you considered just making dimensionality an attribute? > The start point for the refactoring was to add generics and use > HyperPlane<Vector3D>, BSPTree<Vector3D> and the likes. > Unfortunately, I am facing some unexpected (and interesting) > problems. Since BSPTree needs to both handle the global space and > the cut hyperplanes, it needs to be parameterized with the two > dimensions, so it appeared I should rather use BSPTree<Vector3D, > Point2D>. But then, the sub-hyperplanes inside a BSPTree > themselves are parameterized by Point2D and need to access 1D > points. These sub-hyperplanes should be SubHyperplane<Point2D, > Point1D>. As these sub-hyperplanes are stored in BSPTree, either > the attributes in BSPTree should use raw types or should also have > the parameters an be BSPTree<Vector3D, Point2D, Point1D>. We have > here a recursive type definition and the recursion stop condition > corresponds to dimension 0. > > I don't know yet how to set up something simple and type-safe. My > current guess is that I should separate some interfaces in two > interfaces, say Hyperplane<SpacePoint> and Embedding<SpacePoint, > SubSpacePoint>, even if the implementation (for example Plane in > 3D) would implement both interfaces. > > If someone has another idea, I would be interested to read about it. The only thing that occurs to me is to move to using attributes for dimensionality. If you need arbitrary dimension support, you will effectively have to do this; otherwise what you are suggesting above is a little complicated but should work. The real question is how important is type-safety as defined above. This is sort of like ensuring matrix operations are well defined by exhaustively typing columns. With bounded dimensions you could do that; but how bad is it really to have the dimension-checking attribute-based at runtime? Phil > > best regards, > Luc > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [email protected] > For additional commands, e-mail: [email protected] > > --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
