Task45 Editing
The current RegionImpl is based entirely on screen-parallel rectangles. This means that intersecting, merge_intersect, apply_transform etc will always pick the largest rectangle containing the area. Unfortunately, we need a more generic Region, with non-screen parallel edges and negative space. This task will track that rewrite, from design to coding.
A few thoughts. We need performance, so it would be best to make the merge/intersect/subtract functions as simple as possible and make the bounds/outline/span functions do whatever little mathematics they each need. I first thought that this could be done by keeping two lists, first of positive space, secondly of negative space. Unfortunately, a-b+b != a+b-b when manipulating regions. The other trouble is that the semantics are not well-formed with regards to handling disconnected spaces. It might somehow be necessary to contain a Region in two pieces, like an over-sized = sign perhaps. What is the outline() supposed to look like, given that a Path must be fully connected? Should we allow discontiguous regions at all?
An interesting thing to look at in this area is LibArt's micro-tile arrays: http://www.levien.com/libart/uta.html They're quite a clever solution; quite precise coverage, while staying space and time efficient. Not as efficient as a bounding box to manipulate, but still, efficient :-) It's not clear how to simply steal the idea and use it, though; they assume a discretized (ie, pixel-based) space (possibly we could fake this for purposes of Region calculation), it's not clear that they remain as nice to deal with when wrapped in a CORBA struct (though in the local case, this might not be a problem; and it certainly wouldn't be if we were to pull traversals out of CORBA-space), and I'm not sure that they're particularly efficient to rotate, which is a case we might care about optimizing for (perhaps a similar mechanism using multiple bounding/covering spheres instead of boxes could be made to work?). Still, a nice bit of tech, definitely something to look at for ideas. BTW, do we ever actually use outline()? It strikes me as the wrong way to do things, but I may just be prejudiced (and/or misremembering what exactly Regions are used for).
Doh, glancing at bug84 reminds me that I'm totally wrong about what Regions are; I think I was thinking of Allocations or somesuch. If we need Regions that are truly precise, then I suppose we need to be thinking about efficient ways to store/manipulate the class of shapes that can be described as the interior of arbitrary closed paths... (What do we do if someone wants a circular clip? Do we need to support Beziers etc. here too?)
Yes, I think so... And pathes need not be connected either, so there can be pathes like the = sign nicholas used as an exampl What is the region of a 3D object by the way? The screen area covered by it? Or do we need a '3D Region' (== volume) for those? 3Dwm works with non-aligned bounding cubes (which get split up similarly to a OctTree (or QuadTree in our code) for easier colission detection.
I don't see how our Path type is capable of holding a disconnected shape. It's just a sequence of points in 3-space. Could you come up with example coordinates? As for 3D regions, the Region can store the z-coordinates just like the x and y ones. For issues like clipping, we only care about the xy-region anyhow, so we would want to project the 3d object onto the xy-plane and damage that shape. And to njs, no we never use outline() yet. It's not even implemented yet. That's the problem.
Nicholas, you are right... I read something about a Path being able to consist of several segments... Now where was that? /me hopes he did not confuse Fresco and LibArt.
I just noticed that an allocation is actually a region and a transformation. It's not clear to me what that's supposed to mean, especially since we're going to support properly transformed regions, with the implementation in this task. Is there some mix-up in the design where half of modern Fresco was designed with screen parallel regions in mind while the other half wasn't?
Well, after task139 we're almost certainly going to support paths like the equal shape I mentioned. Stefan said he'd like to look into changing the RegionImpl after we get a fancy Path finished.
not logged in
register
Home