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 topologyindependent) 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 subtrees ...) 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
>> errorprone, especially when looking at the BSP tree. BSPtree 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 nonconvex shapes. BSPtree 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 subspaces in
>> the 3D space, the boundaries (facets) are themselves 2D shapes
>> (polygons) inside these 2D planes, these 2D shapes are defined by
>> 2D BSPtrees, 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 n1 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 subhyperplanes inside a BSPTree
>> themselves are parameterized by Point2D and need to access 1D
>> points. These subhyperplanes should be SubHyperplane<Point2D,
>> Point1D>. As these subhyperplanes 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 typesafe. 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 typesafety 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 dimensionchecking attributebased 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, email: devunsubscribe@commons.apache.org
>> For additional commands, email: devhelp@commons.apache.org
>>
>>
>
>
> 
> To unsubscribe, email: devunsubscribe@commons.apache.org
> For additional commands, email: devhelp@commons.apache.org
>
>

To unsubscribe, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
