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.
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.
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.
best regards,
Luc
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
