2D #21
Comments
|
Definitely! As long as its to do with rendering or maths, it can go in Pyrr =). And I'm more than happy to accept help. Feel free to do some development and do a pull request. Let me know if you need any help in navigating the code base. |
|
My comment about Pyrr not being vectorized didn;t make it to github I guess. I saw that your roadmap actually does include working on arrays of geometries, and not just one at a time. I would be happy to take this on. I'll fork this project and start soon. In case you're curious, I'd replace Eventually, I'd like to use a GDAL like style where one would call I'd also like to see a focus on speed, providing a Data Oriented Design ORM to the objects as much as possible. Using numpy arrays pretty much does this, but we can lay out the lines (for example) in the array however is fastest and the user doesn't need to know. So, a (6,N) array may be slightly faster than an (N,2,3) array. I will write tests also. Looking forward to this. -Elliot |
|
One of the major design considerations of Pyrr was to keep the 'numpy way' of working on batches of data. I've tried to keep all functionality in both procedural and OO APIs. Any reason to stage the conversion to np.array (ie the I'm happy for the data to be laid out however makes sense. Be aware that I the only OO implementations I've created so far are for Quaternions, Matrices and Vectors. If the API breaks we'll have to increment the major version. Cheers, |
|
Let me know if you need any help =) |
|
I'm in the process of writing an example of the api I am thinking of. When |
|
Heyoh. I created an example of the API I am thinking of. https://github.com/Permafacture/python-computational-geometry Regarding some of the previous points:
I don't believe you've done this. Everything in geometric_tests.py is writen for single geometries at a time. You could use numpy.vectorize, but this is still really just a for loop, not the real vectorization numpy provides through ufuncs.
In my repo, geometric tests are added to geometric objects through metaprogramming. So, one writes a function for intersection between a line and a box once (as you have), and then both line and box objects have a method for intersecting the other. These methods have meaningful docstrings too, and help() works well on the geometry objects. The objects are not single instances of geometries, but sets, basically a wrapper around an array, giving it methods appropriate to the data in that array. If you want the intersection between two lines, you just add only one line to each Segments2d object. The result would be a 1x1 grid, so you'd have to get pts[0][0] instead of just getting a single point returned, which seems like a mild hastle for having the same API work for single and sets of vectors in an efficient way.
Well, convert is a method in the Geometry superclass, so it is "higher level". But my thinking is to not do unnecessary array creations. Just add geometries to the object by whatever means you want and they are compiled to an array right when it is needed. Also, this allows the computation of properties such as normals, determinants or what have you only when/if they are asked for. The results are "cached" as properties of the objects so they won't be recomputed. When the data is recompiled (lines are added), the cache is invlidated.
Sure. I don't think any basic functions are being obscured here. It's not many layers. Specific geometries inherit from the Geometry superclass, and geometric tests are added at run time. By the way, if you are at all interested in this direction, another step I would consider is taking CGAL or GEOS functions and turning them into numpy ufuncs, which would add a lot of fast, tested, geometric tests to the project right away. |
Totally true. I've wanted Pyrr to do this but I haven't had the time / experience with np to figure out the best way to do some of these. I also haven't had to use many of these functions in this way so I haven't had the motivation. Essentially what you've written is a way of managing collections of object types, and that sounds fine to me. I'll number things to make it easier to track points. The Geometry class you've provided seems ok, although it's more of a collection (perhaps geometry is the correct term anyway? I'm not a mathematician =P). I'd probably rename clear_properties to _clear_cache. Also, set the default dtype to None to be consistent with the rest of the API.
Ok, so the existing geometric tests could be improved to be vectorised, if thats too much effort then just build the higher level content on top of it, and it can be refactored later. As long as the API is appropriate then the internal logic is trivial. I planned to do automatic selection of geometric tests using the same methods I did with the Vector / Quaternion / Matrix objects. This would work for a Line, Sphere, etc. So if you create a *Collection class that then uses dispatch methods to compare to other collections, then that should work. You could also hijack some operators to make it easier. I think & works well for intersection. Doesn't have to have any though if it could be ambiguous.
If something can be scavenged / utilised to our benefit, I'm all for it. Thanks for your input =) It's good to get some fresh eyes and input. Cheers, |
I agree. I should change it to GeometryCollection or something.
I agree totally. Thought of it myself only after posting.
Okay
I saw the multiple dispatch stuff and realized it was similar to what I was doing. I like that API style better. I'm not sure how to combine that with the other decorators I already have, which make it so one only has to write the geometric test once and that's it. Then it is a method of both geometries it applies to. The meta-programming is getting deep: more research required.
I don't like this. It possibly complicates/obfuscates things with little/no practical gain. What is your use case, btw? Are there any geometric tests you'd like to be using in the batched format soon? |
|
Tbh I haven't used many of the functions in Pyrr yet. I had a think about the dtype, and I think you're right. I left them as None because I was trying to match np interfaces where it made sense. But we're creating 'objects' not generic buffers. So a good default makes sense. It should be np.float. You're right about the operators, it's too much magic. I think it's convenient with vectors, but applying it haphazardly would be an attempt to corrupt python itself. In some places we'd need to return different types. Also, spheres need more than just intersections, you want normals and penetration distances (derivable from the intersection). or Perhaps the intersection returns an intersection object? Unsure on what is best. Do you have any preference or experience with other APIs that you found worked well? If you used multipledispatch, the function would have to be hand coded for each type. The function names try and follow a standard, so something like this sounds about right I'm not sure how you'd manage the return types. I think this would prove cumbersome in the long run. Perhaps the return type isn't important and just returning straight np arrays is ok, but I have a feeling you'd want to pass that to another collection for further checks. But this doesn't work so well for some operations on things like spheres (distance, normal, etc). I see you're using results with a mask, this may be ok for now to get the initial API up. Perhaps multipledispatch is a simpler solution for now. Just manually code the functions and worry about adding awesome magic later? I'll leave that up to you. If you don't want to manually write the caching, I've had success with this library These are just some ideas, I don't want to paralyse you with a second voice conflicting with your goals. I know how that feels. Cheers |
|
I'll address some of those questions by writing some actual code, but theres a couple things worth talking about more here.
Unfortunately, this isn't really true. I have used GDAL, and in that library a line segment intersecting a line segment could be a point OR line segment. A line instersecting a rectangle could be a line segment OR a point. A polygon intersecting a polygon could be a point, line OR polygon! These are anoying subtleties.
Like I said, I've only worked with GDAL. It was nice, but not vectorized, which is why I want to work on a new project. I think the results should be geometry collections also. Maybe in some cases, one would want a special geometry collection for the result. But for spheres, could we not just use a line segment? It has a normal and distance, and would contain information about the portions of the spheres that intersected. I think we should stick to cases we know we care about to really get things working in a useable way, but it is good to keep an eye out on annyoing generalities/specifics that could come up later and bite us if we aren't paying attention.
I think the mask is important for the results to make sense. If you find the intersection between 10000 rays and 1000 rectangles, getting back a flat array of 3461 points doesn't do anything for you. You need to know (probably) what rays and rectangles intersected to get those points. The mask lets us keep the meangingful structure of the result and operate on a flat array of the result when needed. Numpy has masked arrays also, which would reduce the return value to a single object rather than an array and mask. I need to research this a bit more to make sure there are no gotchas. A problem/question I see here is that a user defined geometry collection is a flat list of geometries, but a result is a grid. How do I keep track of the result's corispondance to the original collections through multiple queries? Like, find all the intersections between two sets of lines [N lines intersects M lines gives (N,M) points]. Find what rectangles contain those intersections points [(N,M) points within P rectangles gives (N,M,P) bools?]. What lines have points of intersection that are within a given rectangle? I guess we could have results just always become one more dimension than the arguments, and the user answers their questions with slices. So, results [:,:,3] would be an (N,M) array of points of intersections that are within the 4th rectangle... So, here's a good example of a first use case. Raytracing rays and triangles. First you'd test for intersection between the rays and the bounding boxes of the triangles (to save expensive computations where there is clearly no intersection). Then, where they pass that test, get the point of intersection if it exists. Then, query all those triangles for their properties at that point of intersection (normal, color, reflective/refractive qualities). For POV raytracing, those colors, etc, need to correlate to the original rays, because the rays corispond to pixels on the screen. Just off the top of my head, this could look like: Hmm, so maybe each axis needs to be named after the geometry colelction instance it represents? Using a dictionary lookup or recarray? Happy new year, |
|
I believe your example above could be solved with an extra return value, which is an index of what an object collided with. So the intersection could instead be a tuple of indices with an intersection value. Whether the tuple is indices, a masked array of booleans, or what-not isn't important. As an object wrapper, it sounds like there needs to be the ability to I'm not sure how you'd wrap that as objects. Curious to see what you're thinking. |
|
Hey, I've got some messy code (embarassed to show it at this point) that is starting to do what I want. Here's how a user uses it (only does line intersections right now): if __name__ == '__main__':
import matplotlib.pyplot as plt
from composite_geometry import Lines2d
from base_geometry import Vec2d
n = 5
begins1 = np.random.randint(-25,25,(n,2))
ends1 = np.random.randint(-25,25,(n,2))
segs1 = Lines2d(begin=begins1,end=ends1)
m=7
begins2 = np.random.randint(-25,25,(m,m,2))
ends2 =np.random.randint(-25,25,(m,m,2))
segs2 = Lines2d(begin=begins2,end=ends2)
#plot segments
xs,ys = export2mpl(segs1)
plt.plot(xs,ys,'b') #blue solid
xs,ys = export2mpl(segs2)
plt.plot(xs,ys,'g--') #dashed green
#plot the begining of all segments in segs2
xs,ys = export2mpl(segs2['begin'])
plt.plot(xs,ys,'ko') #black dot
#Set up result object (not calculated untill results are access)
result = LineLineIntersect(segs1,segs2)
###plot segs2 from begining to first intersection###
#Get the parameter of point intersections in the frame of segs2
ub = result.points[segs2] #actually triggers calculation
#result.lines[segs2], the line segments representing co-linear overlap
# has not been calculated, but would be if accessed
axis = 2 #manually specify the axis representing segs2
shortest = np.nanmin(ub.arr,axis=axis) #smallest parameter is first intersection
pts = segs2.eval_param(shortest)
#create new line segments that represent segs2 from begining to first intersection
short_lines = Lines2d(begin=segs2['begin'].arr, end=pts.arr)
xs,ys =batched_mpl(short_lines)
plt.plot(xs,ys,'g') #solid green
plt.show()Result:
I'm a bit stuck mucking through making better tools for using named axes (Ie, shortest = min(ub.arr,axis=segs1)). I thought a good next step is to see if I can make this code do some of what you are actually using it for. If it is more performant (which I strongly suspect) and more useful to you, I'll know to keep going. I'd prefer to keep as much communication public as possible, but if this one bug report is not the best forum for communication, we could use email (list-serve?) My email address is my user name at gmail. |
|
I agree regarding public communication. Github is fine by me =) There may be a number of things that could possibly be done to make the code simpler. But the internals may be more complex than I realise. Regarding matching functionality to use. Cheers |
|
Hey, FYI, don't play with it too much. So far I've changed the base gemetries to subclasses of ndarray, added cacheable properties to base geometries, and changed the static and cacheable properties to be properties rather than dictionary items. so I think slices should be invalid. Otherwise, you spend more time in python land creating a sliced object that has sliced cahced properties (if they've been cached yet) without knowing that you are causing this overhead. This would be bad for calculating results and such where you just want to operate on raw arrays. There will likely be a downcast method ( You're still creating a new array when you call raw to get ready to do slices (instead of getting a memory view), but in performace critical sections, one can probably reuse these arrays in calculating the results anyways. |
|
Sorry, I intended to play around and even brainstorm independently (without looking too much to see how an independent solution works) but I haven't had a chance. The changes you mention above are things I was thinking of adding to what you'd suggested anyway, so great work with that. I would avoid removing functionality where it makes sense. I'd rather not be an encumbrance for the sake of performance. How are you handling the edge case intersection results. Eg. line intersections where the result is another line? I'm for-seeing myself being busy for the immediate future. I'll try to find some time to take a look. |
|
I get being busy. No rush. I'd expect to get my library up to the same functionality as yours before you even consider working with it. This would include a performace comparison for real world problems (problems you already deal with). It's not a fork, but a different approach to the same question. Once I have the API about right, I might try adding transformations and see if I can get my abandoned pyglet project to go faster. Transformations (not using numpy) are like 80% of the run time: https://vimeo.com/66736654 and https://vimeo.com/65989831 the segment segment intersect object has points and lines attributes, which are cached (not calculated unless needed). I would later add a result level mask so that the intersect returning lines doesn't check the combinations that are already known to have a points intersersection. Letting slices/masks/etc not work is not actually removing functionality, but just not implementing it. But, users would expect numpy array like objects to support slicing so I get what you mean. Maybe a flag could enable/disable the overhead, and users who want errors when using the objects inefficiently could have them. |
|
"Transformations (not using numpy) are like 80% of the run time" |
|
Physics with pymunk (wraps a C library), graphics with openGL and marching squares with OpenCV. So, no, Python is the glue. Transformations are the only heavy lifting in python, and I pay the price. Still, 60 fps is not awful. |
|
That kind of thing (and some of the stuff in PyRR) could be accelerated very easily via use of the Numba JIT. Numba has a lot of nice hooks for defining ufuncs without resorting to C code as well. Unfortunately Numba is a pretty heavy install (it's not a simple pip install and would require the LLVM to be around). The easiest way to set it up is the Anaconda distro. I haven't mentioned Numba earlier as it would break interop with a lot of pure python projects, but if you are already using something like OpenCV it probably doesn't matter as that lib isn't very venv friendly either Could be worth considering a numba based fork? The more compatible option would be Cython acceleration but it's still a bit of a pain. |
|
I found opencv to be as user friendly as numpy. What have you found unfriendly about it? I don't really care about that demo. It would just be an test at using pyrr for performance, and inform the design. Numba sounds cool, but if I did care about that demo, it would be as an easily distibutable game engine with user friendly installation. Once pyrr is vectorized, I think cython or wrapping gdal into numpy would be good steps. Cython is a bit of a pain to start using, but distributes more easily, which is important. |
|
From memory I found OpenCV hard to install via pip in a virtualenv. I Using OpenCV itself isn't too bad but the underlying C bindings do show On Fri, Apr 10, 2015 at 3:12 PM, Elliot Hallmark notifications@github.com
|
I couldn't find any way to communicate other than filing a bug.
I've been programming in python as a hobby for 5 years. I contributed heavily to a now abandoned non sequential ray tracer using cython. My interest in ray tracing is for optics but I know it can be applied to many fields and I'd like there to be a go to python library for scientists.
I'm very interested in contributing to a fast python geometry library. Specifically, in computing intersections and normals of rays and 2D surfaces (even more specifically, rational b splines) for 2d ray tracing. Bivariate b splines are a more than a bit over my head, but I'd be interested in that 3D possibility. In 3d, I'd be willing to go as far as a triangular mesh.
Is there any interest here in 2d geometry or computing normals (which I'd use for raytracing)?
The text was updated successfully, but these errors were encountered: