0007546: llCastRay only partly implemented

Notes
(0028129) Magnuz (reporter) 2015-04-29 09:25 edited on: 2015-05-03 00:08	Patch to implement llCastRay fully, minus some of its worst SL quirks, is attached: Uses pure geometry, bounding boxes, meshing and no physics for prims, sculpts, meshes, avatars and terrain. Implements all flags, reject types and data flags. Can handle both objects/groups and prims/parts, by configuration. Since opinions seem to differ on what is expected or desired behavior, even in SL, there are a number of configuration options available (in OpenSimDefault.ini): Safety margin on guessing mesh bounding box. Max returned hits separately per prim/part, object/group and total. Reporting hits on exit. Filter on prim/part properties instead of object/group properties. Detect hits in attachments (despite attachment position being real quirky). May sometimes be inaccurate owing to calculation precision and a bug in libopenmetaverse PrimMesher. (PrimMesher adds end faces on circular extrusion, even when not needed and despite it tries not to. This gives ghost surfaces inside uncut prims, like if they had an infinitely narrow cut. This implementation tries to dodge this, using the same filter principle as PrimMesher, but for some reason functioning, unlike in PrimMesher. However, the fix is a bit rough, to save time, and on rare occasions may cause small glitches in the meshed prim.) In SL, an uncut box gives 1 hit on entry of outer surface, while a hollow box can result in up to 8 hits: 2 identical on entry of outer surface, 2 identical on exit of inner surface, 2 identical on re-entry of inner surface and 2 identical on exit of outer surface. This implementation only reports 2 hits: 1 on entry of outer surface and 1 on entry of inner surface. It may however be configured to report exits as well, even if that does not seem to be intended behavior in SL. This patch adds a new llCastRay and renames the old one to llOldCastRay (to make a clean and more easily reviewed patch), but does not remove the parts of the old implementation, since these are scattered and may sometimes be used by other functions as well. This implementation only re-uses the struct Tri from the old implementation. (edited: removed now invalid comment about mesh)

(0028152) vegaslon (reporter) 2015-05-01 12:08	Testing this patch the first thing that I notice and reasonably so is that llCastRay is 3 times slower to complete then in SecondLife as well as the old implementation. While this is a blessing as far as having better accuracy that is needed, it is a not fast enough to be used in weapon systems but still is need as far as NPC navigation is concerned. Ideally would like to see access to the the older less accurate but faster version as well.

(0028153) Magnuz (reporter) 2015-05-01 15:32	Thank you for your feedback, vegaslon. I updated the patch with a configuration parameter to set to use the old version of llCastRay. It should be technically possible to use it directly by calling llCastRayV1 as well, but I think it requires a setup in the interface I'm not familiar with, and I think it's a no-no to add own llFunctions. Maybe the old or new one could be moved to an OSSL function instead, if needed. In my performance tests, the new version was 60-80% slower than the old one, but I guess it depends a lot on the environment. Detailed meshes with up to 131072 triangles each should be real performance killers with the new version, while meshed, by Meshmerizer PrimMesher, plain boxes have only 16 triangles (should be 12), plain cylinders 100 (should be 96) and plain toruses 1200 (should be 1152). I never compared speed to SL, but I can imagine they cache more data than OpenSimulator, like proper bounding boxes for multi-part objects and meshes, to boost performance. The new llCastRay tries to filter on bounding boxes for parts and bounding rectangles for triangles, before doing the hit detection in the triangles, but it's still bound to be slower than just looking at straight boxes like the old llCastRay does.

(0028154) Magnuz (reporter) 2015-05-02 07:29	I made an attempt to optimize the algorithms for filtering, using a bounding sphere model before the projected bounding box model. The bounding sphere gives a 1 to 3 times bigger cross area than the bounding box, depending on angles, but it reduces calculations by about 75% (from 609 float multiplications and 220 float additions to 135 float multiplications and 68 float additions), if it can discard the part. In a test environment with many and "heavy" (=many triangles) parts in the path of the ray, it doesn't make much difference, but in a test environment with few and "light" (=few triangles) parts in the path of the ray, it's actually slightly faster than the original implementation now. The patch is updated with this optimization as well.

(0028155) Magnuz (reporter) 2015-05-02 16:30	I made a second attempt to optimize calculations, by caching some calculated and re-used values (transformed vertices) requiring rather heavy calculations. It seems this optimization doesn't increase speed much though. Still, I updated the patch with it, in case it may be more efficient in other environments than the one I tested. Both optimizations are configurable on/off, with default on.

(0028156) nebadon (administrator) 2015-05-02 16:32	I suspect the only sane way to do Raycasting is to use the Physics engine, C# probably wont ever be fast enough.

(0028157) dahlia (administrator) 2015-05-02 16:44	I agree with nebadon. The physics engine has all the geometry already and can do ray intersection tests extremely fast. If the physics engine is not accessible from the scripting api then maybe we need to make it accessible.

(0028159) vegaslon (reporter) 2015-05-02 18:05	Yes me and Robert talked about that today. It is on the list for bulletsim and has been partially started. The biggest challenge there was the filter that llCastRay has setup, as far as the physic engine knows everything is actively physical or static physical.

(0028161) Magnuz (reporter) 2015-05-02 22:08	I decided to compare performance between the different llCastRay variants properly, and set up what I consider being a lazy but somewhat realistic model environment for it: A region with 4096 torus prims (heaviest prims triangle-wise) in 16 linksets plus a few scattered prims, minor linksets and one avatar with 120 prims in attachments (yay for old prim hair with resizers) with in total some 140 scripts. The cast ray was set up a bit tilted to intersect 17 prims in 3 linksets, of which one mesh, plus ground and avatar, returning the 16 nearest hits (3 discarded). Each variant was tested 10 times with Stopwatch timers. The tests were run on a dedicated server Intel Core i7-3770 3.40GHz, with 32 GB DDR3 RAM, 2 x 3 TB SATA 6 Gb/s HDD 7200 rpm Software-RAID 1, with Ubuntu 14.04.2 LTS 32 bit with Mono 3.12.1 and MySQL 5.5.41, running in total 70 single-region sims and one ROBUST instance. The result was a bit surprising, and off from my preliminary one-time runs, probably owing to random fluctuations and the fact that the first time the cast ray script was ran after a region restart, it took 1.5-3.5 times longer than the following runs. This first run was discarded in each set of runs below. Bottom line is, the new implementation of llCastRay is about 4 times faster than the original in my setup, and the attempted optimizations makes no real difference. Also, the number of prims present and intersected doesn't affect the speed all that much, possibly owing to some script overhead taking about half the time in my full test setup (compare the last two lines below from a previous setup with a lot fewer prims and a different ray path). llCastRay original, +4096 toruses, 5 hits (only 1 hit per link set): 0.069463±0.003922 s llCastRay, without bounding sphere, without cache, +4096 toruses, 16 hits: 0.017147±0.003221 s llCastRay, with bounding sphere, with cache, +4096 toruses, 16 hits: 0.016479±0.0010264 s llCastRay, without bounding sphere, with cache, +4096 toruses, 16 hits: 0.016462±0.002156 s llCastRay, with bounding sphere, without cache, +4096 toruses, 16 hits: 0.017236±0.002763 s llCastRay, with bounding sphere, with cache, no toruses, 10 hits: 0.007320±0.000369 s llCastRay, with bounding sphere, without cache, no toruses, 10 hits: 0.008283±0.001380 s

(0028163) dahlia (administrator) 2015-05-02 22:38	I'm not sure I consider that a typical region or setup. Your hardware is far above what many users use. Your code will need to generate geometry for each unique shape it needs to raycast test. For simple prims such as boxes this can be quite fast. For twisted path cut torii this can be fairly slow, up to 5 milliseconds per prim shape on some installations. If the object is a sculpty or a mesh then there is asset retrieval and decompression and decoding time to add. All this geometry already exists in memory. The meshing subsystem maintains a geometry cache which it shares with the physics engine. What should happen is some means be made available so this geometry could be accessed by your raycast, or perhaps you could pass raycast requests to the physics engine. ODE already does raycasts for camera collisions. I'm not sure what bullet has available but I know it has BVH-accelerated raycast capability internally. I'm not rejecting the patch; you obviously have a good understanding of a raycast process and we do appreciate your contributions. However I'd prefer to see your implementation be defaulted to off and be enabled by config options as lower end installations will likely suffer performance problems with excessive use or rogue scripts. Also be aware that your implementation may be replaced in favor of a solution which does not duplicate functionality and/or makes more efficient use of existing resources should they become accessible in the future.

(0028164) Magnuz (reporter) 2015-05-02 23:31 edited on: 2015-05-03 05:20	Based on the results from my performance testing, I cleaned the bounding sphere and vertex caching from the patch, to simplify the code some. As per request from dahlia, I set the configuration default to use the old implementation of llCastRay. To make the new version default, the following lines need to be added to the [LL-Functions] sections of OpenSim.ini: ; Use new version 2 of llCastRay as default if true ; This gives better accuracy and speed on some servers, but may be slower on other servers UseLlCastRayV2 = true To call the new version without making it default, set the bit value 512 in RC_DATA_FLAGS when calling llCastRay: llCastRay(start, end [..., RC_DATA_FLAGS, 512 \| ...]); (edited: updated instructions after minor update to patch for better structure and easier testing)

(0028165) Magnuz (reporter) 2015-05-02 23:48 edited on: 2015-05-02 23:50	@dahlia: I'm no friend of code duplication, so if there is already cached meshes, they should be used rather than re-generating them, and if there is already logic to detect ray hits properly in them, it should be used rather than this patch, at least if it improves performance. Also, I'm doing this because I need a fully functioning llCastRay, not to see my name in git blame. If the patch isn't merged, I'll probably patch my own sims with it anyway, until a hopefully better solution is merged into core. I'm new to OpenSimulator code and C# programming, so the patches I've provided the last few months have been an interesting challenge and a learning experience for me. Basically I've just learned what has been needed to get the job done from reviewing existing code and some googling. I'm sure people with better knowledge about OpenSimulator code and C# programming could do it better, so I have no problem with such better solutions replacing my patches.

(0028166) Magnuz (reporter) 2015-05-03 00:31	There are 238 lines out of 760 in LSL_Api.cs in this patch that deals with creating and handling different types of meshes alone, besides ray hit detection in SimpleMesh. If cached meshes in a uniform format could be made available, this alone could shave about 1/3 of the patch off, even besides any performance boost, so such a possibility would be welcome.

(0028167) dahlia (administrator) 2015-05-03 00:40	@Magnuz, I'm sure your patches are much appreciated by the community. I also realize that the existing geometry cache and physics raycast are probably not accessible at all from where the LSL API is and it may not be easy to make them accessible. I know many people have been disssatisified with the existing llCastRay implementation. It's also the way open source improves over time for one to implement something and others to build on it. I don't currently have any scripts or objects which use llCastRay so I'd like to let a few others who can test this and add some feedback. If nobody does in a few days, maybe you and I can chat about a good test script. I don't want to hold this up either, if someone else wants to commit it before I do then that's fine. If not, I'll try to get this in for you in a couple days or less.

(0028168) vegaslon (reporter) 2015-05-03 03:26	http://wiki.secondlife.com/wiki/LlCastRay_Test [^] may be a good place to make sure the llCastRay function is working the same as in Sl.

(0028172) Magnuz (reporter) 2015-05-03 15:27	I looked over ttp://wiki.secondlife.com/wiki/LlCastRay_Test [^] but didn't run any of the tests there. Some comments to the descriptions though: Norm and position correctness test. Using meshing, it's impossible to achieve the "perfect sphere" mentioned. Since they seem to accept a 1% error in position and normal, it could work with a well meshed spherical polyhedron 36x18 facets, since cos(5°)^2 (360°/36/2, largest error in the middle of an equatorial facet) is 0.992404. A meshed prim sphere with 24x12 facets will fail though, since cos(7.5°)^2 is 0.982963. Multiple hits correctness test. Should work. llCastRay() resource limit test. Will fail since throttling isn't implemented. If the parameter m_maxHitsInCastRay is set to 0, llCastRay v2 will exit without attempting any hit detections though. Object filter test. Should work.

(0028175) Magnuz (reporter) 2015-05-03 22:52	For anyone wanting to test with llCastRay, I added an updated version of the tool I use myself, an LSL script llCastRayTest3. Drop it into a simple prim, and it will reshape that prim into a marker stick, which you can then edit to change length, drag and rotate to mark the ray path you want. When clicking the marker stick, you get a dialog to cast ray, get info, reset, and toggle all the llCastRay flags and implementation version. The one thing missing is the possibility to set the max number of returned hits, because I ran out of dialog buttons and was too lazy to make sub-dialogs. When you cast the ray, it will return the first max 16 hits reported, the number of hits and the time the cast took.

(0028176) dahlia (administrator) 2015-05-04 00:23	I see in the code that the setting should be "UseLlCastRayV1 = false" to enable the new functionality, but you had "UseLlCastRayV2 = true". Those attempting to test the new functionality should probably take note to use "UseLlCastRayV1 = false"

(0028177) dahlia (administrator) 2015-05-04 00:35	ok I pushed it after adding the new config parameter to OpenSimDefaults.ini. I didn't test it very well; since it's defaulting to off I'll let others play with it and hopefully comment here. Thanks for the patch :)

(0028179) Magnuz (reporter) 2015-05-04 09:03	@dahlia Thank you, but an old version of the patch (0001-Implement-llCastRay-fully-simplified.patch instead of 0001-Implement-llCastRay-V2.patch) was applied. Please, apply the incremental patch 0001-Patch-llCastRay-fully-simplified-to-V2.patch to update to the most recent version. This will add the possibility to pick old or new implementation in the call (see note above), avoid slowing down the old implementation, and correct some comments in code. From my benchmarking, it seems just forwarding a call from the old to the new llCastRay or vice versa increases call time by several milliseconds. Since the old llCastRay will probably remain the main one for now, it's unnecessary to slow that one down. Therefore, the call order is reversed in the most recent patch, so calls are forwarded from the old to the new llCastRay.

(0028180) nebadon (administrator) 2015-05-04 10:07	I applied 0001-Patch-llCastRay-fully-simplified-to-V2.patch to master git > http://opensimulator.org/viewgit/?a=commit&p=opensim&h=c96ee68953eb31fc2ad6d1df9b7a4bb19c584e17 [^]

(0028191) dahlia (administrator) 2015-05-04 13:17	Magnuz, I would like any method which generates geometry to be unavailable to scripts unless specifically enabled in the config file. I had intended to request this for your prior patch which used bounding boxes but it was applied before I had a chance to comment.

(0028192) dahlia (administrator) 2015-05-04 13:29	the RC_USE_V2 does not exist in the SL documentation for llCastRay. We typically do not add new definitions to LSL functions, rather we add them to os* functions. This flag should be removed.

(0028193) nebadon (administrator) 2015-05-04 13:42	I agree with dahlia, sorry I missed that on first pass. Magnuz if you want please provide another patch to remove this, or I can do it in a bit myself if dahlia doesn't do it first :)

(0028194) nebadon (administrator) 2015-05-04 13:43	I am just going to revert this patch for now.

(0028195) nebadon (administrator) 2015-05-04 13:46	reverted for now please discuss with dahlia :)

(0028209) Magnuz (reporter) 2015-05-04 23:53	The new incremental patch 0001-Implement-llCastRay-V2.8.patch tries to meet the requested criteria by configuration: EnableLlCastRayV2 = false Enables llCastRay V2 if true but does not make it deafult. Comes with the "warning lable": Gives better accuracy and can be faster on some servers, but slower on others, compared to previous version of llCastRay. Generates geometry meshes and can therefore use much system resources. UseLlCastRayV2AsDefault = false Makes llCastRay V2 default only if it is enabled. DataFlagToCallLlCastRayV2 = 512 Makes it possible to call llCastRay V2 when enabled but not default. This is valuable for testing and evaluating without needing to change configuration and restart the sim. It may also be useful in the probably rare cases that both versions are desired, e.g. if the old, sometimes faster, version is needed for combat systems, and the better accuracy of the new version is needed to navigate NPC's. I don't consider the last parameter as adding new functionality or definitions, since the two versions of llCastRay really just implement the SL functionality to various degrees, and the parameter is non-functional in the probably typical cases that the new version is disabled or the new version is both enabled and default.

(0028360) Magnuz (reporter) 2015-05-10 11:45	The new incremental patch 0001-Patch-llCastRay-fully-simplified-to-V3.patch is a thorough rework of the previously committed implementation. It reduces the post-processing of meshes substantially by transforming just the 2 ray endpoints instead of 8 bounding box corners for every prim/mesh/avatar, and 10s to 1000s of mesh vertices for each potentially hit prim/mesh/avatar. On a high end server it reduces call time by 30% and on a more average laptop by 50% in my benchmark tests. It removes runtime swap between versions but adds configuration of mesh detail level to enable fine-tuning of performance. It also fixes a few corner cases, removes some redundant code and increases robustness some by additional checks. The name was changed to V3, since this is the third major implementation in OpenSimulator core after the Aurora (2011-07-12) and Avination (2012-06-13) implementations.

(0028364) dahlia (administrator) 2015-05-12 15:53	Applied V3 patch. Thank you Magnuz! :)

(0028365) nebadon (administrator) 2015-05-12 22:01	Magnuz if you have more patches please start a new mantis, close this one if you are happy with the code applied to core, thanks for the great work!

(0028366) Magnuz (reporter) 2015-05-13 00:16	Verified code and function, so closing. Thank you for the feedback helping me to (hopefully) improve the implementation. If it will become possible to tap into cached geometry meshes, this should be a rather easy fix that could improve performance quite a bit. If native physics code can be used to replace parts or all of this implementation to improve performance, please do so.

(0028368) dahlia (administrator) 2015-05-13 13:34	I did alter the mesh cache to make it shared. The cache is usually used by ODE but I see that BulletSim isn't using it. The cache exists in Meshmerizer.cs and instantiating a Meshmerizer object and requesting mesh geometry thru it can make use of the shared cache. It may not actually work better in all cases as the process of generating a mesh for physics is somewhat more involved than just getting one via PrimMesher, but it could be a lot faster if many similar raycasts are done. I would like to see some throttling applied to llCastRay, perhaps similar to the SL implementation, and if such throttling existed than we could let the V3 implementation default to enabled. I'd also rather see the raycast method in Scene be enhanced, perhaps by passing it to the physics engine, and llCastRay could just use the method in Scene. Regardless, I don't expect you spend time to do any of this now that you have a working implementation in core and I am grateful for your contributions.

Issue History
Date Modified	Username	Field	Change
2015-04-29 09:21	Magnuz	New Issue
2015-04-29 09:21	Magnuz	File Added: 0001-Implement-llCastRay-fully.patch
2015-04-29 09:25	Magnuz	Note Added: 0028129
2015-04-29 09:25	Magnuz	Status	new => patch included
2015-04-29 09:25	Magnuz	Relationship added	related to 0006623
2015-04-29 09:25	Magnuz	Relationship added	related to 0007351
2015-04-29 09:25	Magnuz	Relationship added	related to 0007374
2015-04-29 09:26	Magnuz	Relationship added	related to 0007375
2015-04-29 09:26	Magnuz	Relationship added	related to 0007512
2015-05-01 12:08	vegaslon	Note Added: 0028152
2015-05-01 14:51	Magnuz	File Deleted: 0001-Implement-llCastRay-fully.patch
2015-05-01 14:52	Magnuz	File Added: 0001-Implement-llCastRay-fully.patch
2015-05-01 15:32	Magnuz	Note Added: 0028153
2015-05-02 07:29	Magnuz	Note Added: 0028154
2015-05-02 07:29	Magnuz	File Added: 0001-Implement-llCastRay-fully-optimization-1.patch
2015-05-02 07:29	Magnuz	File Deleted: 0001-Implement-llCastRay-fully.patch
2015-05-02 16:26	Magnuz	File Added: 0001-Implement-llCastRay-fully-optimization-2.patch
2015-05-02 16:26	Magnuz	File Deleted: 0001-Implement-llCastRay-fully-optimization-1.patch
2015-05-02 16:30	Magnuz	Note Added: 0028155
2015-05-02 16:32	nebadon	Note Added: 0028156
2015-05-02 16:44	dahlia	Note Added: 0028157
2015-05-02 18:05	vegaslon	Note Added: 0028159
2015-05-02 22:08	Magnuz	Note Added: 0028161
2015-05-02 22:38	dahlia	Note Added: 0028163
2015-05-02 23:04	Magnuz	File Added: 0001-Implement-llCastRay-fully-simplified.patch
2015-05-02 23:05	Magnuz	File Deleted: 0001-Implement-llCastRay-fully-optimization-2.patch
2015-05-02 23:31	Magnuz	Note Added: 0028164
2015-05-02 23:48	Magnuz	Note Added: 0028165
2015-05-02 23:50	Magnuz	Note Edited: 0028165	View Revisions
2015-05-03 00:08	Magnuz	Note Edited: 0028129	View Revisions
2015-05-03 00:31	Magnuz	Note Added: 0028166
2015-05-03 00:40	dahlia	Note Added: 0028167
2015-05-03 03:26	vegaslon	Note Added: 0028168
2015-05-03 05:12	Magnuz	File Added: 0001-Implement-llCastRay-V2-fully.patch
2015-05-03 05:13	Magnuz	File Deleted: 0001-Implement-llCastRay-fully-simplified.patch
2015-05-03 05:20	Magnuz	Note Edited: 0028164	View Revisions
2015-05-03 15:06	Magnuz	File Added: 0001-Implement-llCastRay-V2.patch
2015-05-03 15:06	Magnuz	File Deleted: 0001-Implement-llCastRay-V2-fully.patch
2015-05-03 15:27	Magnuz	Note Added: 0028172
2015-05-03 22:36	Magnuz	File Added: llCastRayTest3.lsl.txt
2015-05-03 22:38	Magnuz	File Added: llCastRayTest3.lsl
2015-05-03 22:38	Magnuz	File Deleted: llCastRayTest3.lsl.txt
2015-05-03 22:38	Magnuz	File Deleted: llCastRayTest3.lsl
2015-05-03 22:39	Magnuz	File Added: llCastRayTest3.lsl.txt
2015-05-03 22:52	Magnuz	Note Added: 0028175
2015-05-04 00:23	dahlia	Note Added: 0028176
2015-05-04 00:35	dahlia	Note Added: 0028177
2015-05-04 09:02	Magnuz	File Added: 0001-Patch-llCastRay-fully-simplified-to-V2.patch
2015-05-04 09:03	Magnuz	Note Added: 0028179
2015-05-04 10:07	nebadon	Note Added: 0028180
2015-05-04 10:07	nebadon	Status	patch included => resolved
2015-05-04 10:07	nebadon	Resolution	open => fixed
2015-05-04 10:07	nebadon	Assigned To	=> nebadon
2015-05-04 13:17	dahlia	Note Added: 0028191
2015-05-04 13:29	dahlia	Note Added: 0028192
2015-05-04 13:42	nebadon	Note Added: 0028193
2015-05-04 13:43	nebadon	Note Added: 0028194
2015-05-04 13:46	nebadon	Note Added: 0028195
2015-05-04 13:46	nebadon	Status	resolved => patch feedback
2015-05-04 23:48	Magnuz	File Added: 0001-Implement-llCastRay-V2.8.patch
2015-05-04 23:53	Magnuz	Note Added: 0028209
2015-05-04 23:53	Magnuz	Status	patch feedback => patch included
2015-05-10 11:43	Magnuz	File Added: 0001-Patch-llCastRay-fully-simplified-to-V3.patch
2015-05-10 11:43	Magnuz	File Deleted: 0001-Patch-llCastRay-fully-simplified-to-V2.patch
2015-05-10 11:43	Magnuz	File Deleted: 0001-Implement-llCastRay-V2.8.patch
2015-05-10 11:45	Magnuz	Note Added: 0028360
2015-05-12 15:53	dahlia	Note Added: 0028364
2015-05-12 22:01	nebadon	Note Added: 0028365
2015-05-12 22:01	nebadon	Status	patch included => resolved
2015-05-13 00:16	Magnuz	Note Added: 0028366
2015-05-13 00:16	Magnuz	Status	resolved => closed
2015-05-13 13:34	dahlia	Note Added: 0028368
2015-05-14 10:02	Magnuz	Relationship added	related to 0007568
2015-05-16 14:09	Magnuz	Relationship added	related to 0007575
2015-05-20 22:51	nebadon	Relationship added	related to 0007582
2015-05-23 05:20	Magnuz	Relationship added	related to 0007587