Revision: 77637
http://sourceforge.net/p/brlcad/code/77637
Author: brlcad
Date: 2020-10-24 17:07:09 +0000 (Sat, 24 Oct 2020)
Log Message:
-----------
applied sf patch # 558 (Improved bounding box time complexity) from Vikram
Atreya. this improved the bot bounding box calculation to only consider
referenced vertices without testing all vertices or all face vertex references
thus cutting the number of tests by a third.
Modified Paths:
--------------
brlcad/trunk/src/librt/primitives/bot/bot.c
Modified: brlcad/trunk/src/librt/primitives/bot/bot.c
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/bot.c 2020-10-24 14:11:20 UTC (rev
77636)
+++ brlcad/trunk/src/librt/primitives/bot/bot.c 2020-10-24 17:07:09 UTC (rev
77637)
@@ -52,6 +52,8 @@
#include "./bot_edge.h"
#include "../../librt_private.h"
+//adding time only for now, delete later******
+//#include <time.h>
#define MAXHITS 128
@@ -422,30 +424,39 @@
int
rt_bot_bbox(struct rt_db_internal *ip, point_t *min, point_t *max, const
struct bn_tol *UNUSED(tol)) {
struct rt_bot_internal *bot_ip;
+ size_t vert_index;
size_t tri_index;
- point_t p1, p2, p3;
+ point_t p1;
size_t pt1, pt2, pt3;
RT_CK_DB_INTERNAL(ip);
bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
RT_BOT_CK_MAGIC(bot_ip);
+
+ struct bu_bitv *visit_vert = bu_bitv_new(bot_ip->num_vertices);
VSETALL((*min), INFINITY);
VSETALL((*max), -INFINITY);
+ /* iterate through all faces of the BoT and mark vertices that are being
reached in the bit-vector */
for (tri_index = 0; tri_index < bot_ip->num_faces; tri_index++) {
- pt1 = bot_ip->faces[tri_index*3];
- pt2 = bot_ip->faces[tri_index*3 + 1];
- pt3 = bot_ip->faces[tri_index*3 + 2];
- VMOVE(p1, &bot_ip->vertices[pt1*3]);
- VMOVE(p2, &bot_ip->vertices[pt2*3]);
- VMOVE(p3, &bot_ip->vertices[pt3*3]);
- VMINMAX((*min), (*max), p1);
- VMINMAX((*min), (*max), p2);
- VMINMAX((*min), (*max), p3);
+ pt1 = bot_ip->faces[tri_index*3];
+ pt2 = bot_ip->faces[tri_index*3 + 1];
+ pt3 = bot_ip->faces[tri_index*3 + 2];
+ BU_BITSET(visit_vert,pt1);
+ BU_BITSET(visit_vert,pt2);
+ BU_BITSET(visit_vert,pt3);
+ }
+ /* Check max and min of vertices marked */
+ for(vert_index = 0; vert_index < bot_ip->num_vertices; vert_index++){
+ if(BU_BITTEST(visit_vert,vert_index)){
+ VMOVE(p1, &bot_ip->vertices[vert_index*3]);
+ VMINMAX((*min), (*max), p1);
+ }
}
+ bu_bitv_free(visit_vert);
- /* Prevent the RPP from being 0 thickness */
+ /* Make sure the RPP created is not of zero volume */
if (NEAR_EQUAL((*min)[X], (*max)[X], SMALL_FASTF)) {
(*min)[X] -= SMALL_FASTF;
(*max)[X] += SMALL_FASTF;
@@ -458,6 +469,7 @@
(*min)[Z] -= SMALL_FASTF;
(*max)[Z] += SMALL_FASTF;
}
+
return 0;
}
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
