Le 22/05/2011 22:09, Phil Steitz a écrit :
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.
Yes, it allow to share some really difficult code and separate the tree
logic (walking trees, splitting cells, merging sub-trees ...) from the
geometry (computing planes, lines, circles intersection). Once the logic
of the algorithm is validated, using it for other geometry contexts is
far easier, we only have to tackle geometric problems.
It is also the way it is already implemented since a few years (this is
old code that simply needs some cleaning).
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?
This would work only for Euclidean spaces, and I need to extend this to
sphere.
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?
Thanks for the hint, I'll look at it.
I am currently trying another idea, simpler than my previous one.
Basically, I have only one parameter Space which is implemented as
Euclidean3D, Euclidean2D, Euclidean1D and serve almost only as a marker.
All top level interfaces depend only on this parameter:
Hyperplane<S extends Space>, SubHyperplane<S extends Space>, BSPTree<S
extends Space> ...
The recursion stated above is now hidden in the implementation of
SubHyperplane using an abstract class:
AbstractSubHyperplane<S extends Space, T extends Space>
implements SubHyperplane<S>.
So everything is declared using only the largest dimension (S), but the
concrete class can rely on elements defined in lower dimensions (T). It
seems to work with only a few casts and suppressWarning. I agree I
cannot have a complete type safe system here.
Thanks,
Luc
Phil
best regards,
Luc
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
