File indexing completed on 2026-04-09 07:48:52
0001
0002
0003 #include <iostream>
0004 #include "OpticksCSG.h"
0005 #include "scanvas.h"
0006
0007 #define DEBUG 1
0008 #include "csg_classify.h"
0009
0010 void print_LUT( const LUT& lut, OpticksCSG_t typecode, const char* notes )
0011 {
0012 int width = 4+1 ;
0013 int height = 4+1 ;
0014 int xscale = 18 ;
0015 int yscale = 6 ;
0016
0017 int mx = 2 ;
0018 int my = 2 ;
0019
0020 scanvas canvas(width, height, xscale, yscale );
0021
0022 canvas.draw( 0,0, mx, my, CSG::Name(typecode) );
0023
0024 for(int ix=0 ; ix < width-1 ; ix++)
0025 for(int iy=0 ; iy < height-1 ; iy++)
0026 {
0027 canvas.drawch( ix,iy, 0, 0, '+' );
0028 canvas.drawch( ix,iy, 0, yscale-1, '+' );
0029
0030 for(int ixx=1 ; ixx < xscale ; ixx++ ) canvas.drawch( ix,iy, ixx, 0, '-' );
0031 for(int iyy=1 ; iyy < yscale ; iyy++ ) canvas.drawch( ix,iy, 0, iyy, '|' );
0032 }
0033
0034
0035 int ix = width-1 ;
0036 for(int iy=0 ; iy < height-1 ; iy++)
0037 {
0038 canvas.drawch( ix,iy, 0, 0, '+' );
0039 for(int iyy=1 ; iyy < yscale ; iyy++ ) canvas.drawch( ix,iy, 0, iyy, '|' );
0040 }
0041
0042 int iy = height-1 ;
0043 for(int ix=0 ; ix < width-1 ; ix++)
0044 {
0045 canvas.drawch( ix,iy, 0, 0, '+' );
0046 for(int ixx=1 ; ixx < xscale ; ixx++ ) canvas.drawch( ix,iy, ixx, 0, '-' );
0047 }
0048 canvas.drawch( width-1,height-1, 0,0, '+' );
0049
0050
0051 for(int a=0 ; a < 3 ; a++)
0052 {
0053 IntersectionState_t A_state = (IntersectionState_t)a ;
0054 canvas.drawch( 0,a+1, mx+0,my+0, 'A' );
0055 canvas.draw( 0,a+1, mx+2,my+0, IntersectionState::Name(A_state) );
0056 }
0057
0058 for(int b=0 ; b < 3 ; b++)
0059 {
0060 IntersectionState_t B_state = (IntersectionState_t)b ;
0061 canvas.drawch( b+1,0, mx+0,my+0, 'B' );
0062 canvas.draw( b+1,0, mx+2,my+0, IntersectionState::Name(B_state) );
0063 }
0064
0065 for(int c=1 ; c < 3 ; c++)
0066 {
0067 bool A_closer = c == 1 ;
0068 canvas.drawch( 0,0, mx+0, my+c, A_closer ? 'A' : 'B' );
0069 canvas.draw( 0,0, mx+2, my+c, "Closer" );
0070 }
0071
0072 for(int c=0 ; c < 2 ; c++)
0073 for(int b=0 ; b < 3 ; b++)
0074 for(int a=0 ; a < 3 ; a++)
0075 {
0076 bool A_closer = c == 0 ;
0077 IntersectionState_t A_state = (IntersectionState_t)a ;
0078 IntersectionState_t B_state = (IntersectionState_t)b ;
0079 int ictrl = lut.lookup( typecode , A_state, B_state, A_closer ) ;
0080 const char* ctrl = CTRL::Name(ictrl) ;
0081 assert( strlen(ctrl) < unsigned(xscale) );
0082
0083 canvas.draw( b+1, a+1, mx+0, my+c+1, ctrl );
0084 }
0085 canvas.print();
0086 printf("%s\n", notes);
0087 }
0088
0089
0090 const char* REFERENCE = R"LITERAL(
0091
0092 http://xrt.wikidot.com/doc:csg
0093
0094 http://xrt.wdfiles.com/local--files/doc%3Acsg/CSG.pdf
0095
0096 A ray is shot at each sub-object to find the nearest intersection, then the
0097 intersection with the sub-object is classified as one of entering, exiting or
0098 missing it. Based upon the combination of the two classifications, one of
0099 several actions is taken:
0100
0101 1. returning a hit
0102 2. returning a miss
0103 3. changing the starting point of the ray for one of the objects and then
0104 shooting this ray, classifying the intersection. In this case, the state
0105 machine enters a new loop.
0106
0107
0108 Note that when there is a MISS on either side, the LUT results
0109 are the same no matter what leftIsCloser is set to for all
0110 operations : UNION, INTERSECTION, DIFFERENCE.
0111
0112 )LITERAL" ;
0113
0114 const char* UNION = R"LITERAL(
0115 +-----------------+-----------------+-----------------+-----------------+
0116 | | | | |
0117 | union | B Enter | B Exit | B Miss |
0118 | A Closer | | | |
0119 | B Closer | | | |
0120 | | | | |
0121 +-----------------+-----------------+-----------------+-----------------+
0122 | | | | |
0123 | A Enter | | | |
0124 | | RETURN_A | LOOP_A | RETURN_A |
0125 | | RETURN_B | RETURN_B | RETURN_A |
0126 | | | | |
0127 +-----------------+-----------------+-----------------+-----------------+
0128 | | | | |
0129 | A Exit | | | |
0130 | | RETURN_A | RETURN_B | RETURN_A |
0131 | | LOOP_B | RETURN_A | RETURN_A |
0132 | | | | |
0133 +-----------------+-----------------+-----------------+-----------------+
0134 | | | | |
0135 | A Miss | | | |
0136 | | RETURN_B | RETURN_B | RETURN_MISS |
0137 | | RETURN_B | RETURN_B | RETURN_MISS |
0138 | | | | |
0139 +-----------------+-----------------+-----------------+-----------------+
0140
0141 (A Enter, B Enter)
0142 origin outside both -> return closest
0143
0144 (A Exit, B Exit)
0145 origin inside both -> return furthest
0146
0147 (A Exit, B Enter)
0148 origin inside A
0149
0150 * if A closer return A (means disjoint)
0151 * if B closer loop B (to find the otherside of it, and then compare again)
0152
0153
0154
0155
0156 UX1 : UNION FROM INSIDE ONE UX2 : UNION FROM OUTSIDE 0,1,2
0157 UX3 : UNION FROM INSIDE BOTH 3,4,5
0158
0159 +-----------------------+ +-----------------------+
0160 | B | | B |
0161 +------------------+ | +------------------+ |
0162 | A | | | | A | | |
0163 | | | | | | | |
0164 | | | | | | | |
0165 | 0- - - 1 - - - 2 - - - - - - -[3] 0 -[1]- - - - 2 | |
0166 | E X X E E 3 - 4 - - - - - - -[5]
0167 | | | | | | X X
0168 | +-------|---------------+ | +-------|---------------+
0169 | | | |
0170 | | | |
0171 +------------------+ +------------------+
0172
0173
0174 0: origin 0: origin
0175 1: B Enter 1: A Enter
0176 2: A Exit 2: B Enter
0177 1,2: B Closer ==> LOOP_B 1,2: A Closer ==> RETURN_A
0178 3: B Exit
0179 2,3: A closer ==> RETURN_B 3: origin
0180 4: A Exit
0181 5: B Exit
0182 4,5 A Closer ==> RETURN_B
0183
0184
0185 UX4 : DISJOINT UNION 0,[1],2
0186
0187
0188 +---------------------+ +---------------------+
0189 | A | | B |
0190 | | | |
0191 | | | |
0192 | | | |
0193 | | | |
0194 | 0- - - - - [1] - - - - - - -2 |
0195 | X E |
0196 | | | |
0197 | | | |
0198 | | | |
0199 +---------------------+ +---------------------+
0200
0201
0202 0: origin
0203 1: A Exit
0204 2: B Enter
0205 1,2: A Closer ==> RETURN_A [1]
0206
0207 )LITERAL" ;
0208
0209
0210 const char* INTERSECTION = R"LITERAL(
0211 +-----------------+-----------------+-----------------+-----------------+
0212 | | | | |
0213 | intersection | B Enter | B Exit | B Miss |
0214 | A Closer | | | |
0215 | B Closer | | | |
0216 | | | | |
0217 +-----------------+-----------------+-----------------+-----------------+
0218 | | | | |
0219 | A Enter | | | |
0220 | | LOOP_A | RETURN_A | RETURN_MISS |
0221 | | LOOP_B | LOOP_B | RETURN_MISS |
0222 | | | | |
0223 +-----------------+-----------------+-----------------+-----------------+
0224 | | | | |
0225 | A Exit | | | |
0226 | | LOOP_A | RETURN_A | RETURN_MISS |
0227 | | RETURN_B | RETURN_B | RETURN_MISS |
0228 | | | | |
0229 +-----------------+-----------------+-----------------+-----------------+
0230 | | | | |
0231 | A Miss | | | |
0232 | | RETURN_MISS | RETURN_MISS | RETURN_MISS |
0233 | | RETURN_MISS | RETURN_MISS | RETURN_MISS |
0234 | | | | |
0235 +-----------------+-----------------+-----------------+-----------------+
0236
0237
0238 Ordering states (Closer,Further)
0239
0240
0241 (Enter, Enter) -> Loop Closer
0242 Find otherside of Closer Enter (by advancing t_min and intersecting that constituent again and then comparing again)
0243
0244 ::
0245
0246 +-------------+
0247 | A |
0248 | +------|-------+ 0:Origin
0249 | | | B | 1:A_Enter
0250 0- - -1 - - [2]- - -3 | 2:B_Enter
0251 E E X | (1:A_Enter,2:B_Enter) => A_Closer => LOOP_A : Closer one => 3
0252 | | | | 3:A Exit
0253 +------|------+ | (2:B Enter,3:A Exit) => RETURN_B 2:B_Enter
0254 | |
0255 +--------------+
0256
0257 (Enter, Exit) -> Return Closer One : the Enter
0258
0259
0260
0261 (Exit, Enter) -> Loop Closer (the Exit)
0262 One might first imagine that having just exited so there will be no otherside ?
0263 But that assumes simple convex constituent shapes whereas the alg needs to
0264 handle less simple shapes like torus or annulus
0265
0266
0267 (Exit, Exit) -> Return Closer Exit
0268 Both isect classified as Exit means origin is inside both,
0269 hence the closer isect is needed as it is the nature of
0270 CSG_INTERSECTION to pick the shape formed from the overlap
0271 of the constituents
0272
0273
0274
0275 Thinking of ROTH diagrams for intersection
0276
0277
0278 |--------------|
0279
0280 |------------------|
0281
0282 |-----------------|
0283
0284 Enters: | | |
0285
0286 Exits: | | |
0287
0288
0289 farthest enter | |
0290 | | nearest exit
0291
0292 For an overlap need::
0293
0294 farthest_enter < nearest_exit
0295
0296
0297 |-----------|
0298
0299 |------------|
0300
0301 Enters: | |
0302
0303 Exits: | |
0304
0305
0306 nearest exit | | farthest enter
0307
0308 No overlap as::
0309
0310 nearest_exit < farthest_enter
0311
0312
0313
0314
0315
0316
0317
0318 Consider INTERSECTION between an ordinary bounded A and an unbounded B (eg phicut or thetacut)
0319
0320 * assume that find a way to special case reclassify "B Miss" into "B Exit"
0321 for rays going in the appropriate range of directions
0322
0323 * currently complement miss flips the signbits of isect.xyz
0324 but only signbit of isect.x is read as the signal for complemented miss
0325
0326 * rationalize the signalling (note that are re-using isect when there is miss
0327 and hence no intersection to pass info up the tree)
0328
0329 1. isect.x signbit for complement miss
0330 2. isect.y signbit for unbounded miss that can be promoted to unbounded exit
0331
0332 * hmm this is only applicable when start "inside" B as can only EXIT_B when start inside
0333 * how to check are inside an infinite phicut ? check (o.x,o.y) ? signed distances ?
0334 * think about a very thin wedge phicut and pure-z (eg orthographic view looking directly
0335 down on the cake) most of the time will miss the phicut hence do not want to
0336 promote that miss : as the phicut is effectively not there.
0337
0338 * as the "otherside" of B is at infinity the comparison will always be "A Closer"
0339
0340
0341 ::
0342
0343 .
0344 => MISS /
0345 2:B_MISS /
0346 2 / B : unbounded
0347 / /
0348 / /
0349 / /
0350 / /
0351 / /
0352 +----------1-A_EXIT--/-------------+
0353 | A / / . . . . . . .|
0354 | / / . . . . . . . |
0355 | 0 / . . . 0--->---1----------- 2:B_MISS
0356 | / . . . . . . . . A_EXIT
0357 | + . 0 . . . . . . .| (A_EXIT, B_MISS) => RETURN_MISS
0358 | \ / . . . . . . . |
0359 | 1 . . . . . . . .| (A_EXIT, B_EXIT) => A_Closer => RETURN_A
0360 | / \ . . . . . . . |
0361 +---------------2---\--------------+
0362 \
0363 1:B_EXIT \
0364 2:A_EXIT \
0365 1,2:B_Closer \
0366 => RETURN_B
0367
0368
0369
0370
0371
0372
0373 IX1 : INTERSECTION FROM INSIDE ONE 0,[1],2 IX2 : INTERSECTION FROM OUTSIDE 0,1,[2],3
0374 IX3 : INTERSECTION FROM INSIDE BOTH 4,[5],6
0375
0376 +-----------------------+ +-----------------------+
0377 | B | | B |
0378 +------------------+ | +------------------+ |
0379 | A | | | | A | | |
0380 | | | | | | 4 -[5]- - - - - - - 6
0381 | | | | | | | |
0382 | 0- - -[1]- - - 2 | 0 - 1 - - - - [2] - - -3 |
0383 | | | | | | | |
0384 | | | | | | | |
0385 | +-------|---------------+ | +-------|---------------+
0386 | | | |
0387 | | | |
0388 +------------------+ +------------------+
0389
0390
0391 0: origin 0: origin
0392 1: B Enter 1: A Enter
0393 2: A Exit 2: B Enter
0394 1,2: B Closer ==> RETURN_B => [1] 1,2: A Closer => LOOP_A 1->3
0395 3: A Exit
0396 3,2: B Closer => RETURN_B => [2]
0397
0398
0399 4: origin
0400 5: A Exit
0401 6: B Exit
0402 5,6: A Closer ==> RETURN_A [5]
0403
0404
0405
0406
0407
0408
0409
0410
0411 The below shapes are not permissable as there is no common overlap
0412 giving such a shape to a MULTI_INTERSECT may abort and will give incorrect intersects.
0413
0414
0415 +------+
0416 +---|------|-----+
0417 | | | |
0418 | | | |
0419 | +------+ |
0420 | +----|-----+
0421 +-----------|----+ |
0422 +----------+
0423
0424 +----+ +-----+ +-----+
0425 | | | | | |
0426 - -E - - - - - E- - - - - - E- - - - - -
0427 | | | | | |
0428 +----+ +-----+ +-----+
0429
0430
0431 )LITERAL" ;
0432
0433 const char* DIFFERENCE = R"LITERAL(
0434 +-----------------+-----------------+-----------------+-----------------+
0435 | | | | |
0436 | difference | B Enter | B Exit | B Miss |
0437 | A Closer | | | |
0438 | B Closer | | | |
0439 | | | | |
0440 +-----------------+-----------------+-----------------+-----------------+
0441 | | | | |
0442 | A Enter | | | |
0443 | | RETURN_A | LOOP_A | RETURN_A |
0444 | | LOOP_B | LOOP_B | RETURN_A |
0445 | | | | |
0446 +-----------------+-----------------+-----------------+-----------------+
0447 | | | | |
0448 | A Exit | | | |
0449 | | RETURN_A | LOOP_A | RETURN_A |
0450 | | RETURN_FLIP_B | RETURN_FLIP_B | RETURN_A |
0451 | | | | |
0452 +-----------------+-----------------+-----------------+-----------------+
0453 | | | | |
0454 | A Miss | | | |
0455 | | RETURN_MISS | RETURN_MISS | RETURN_MISS |
0456 | | RETURN_MISS | RETURN_MISS | RETURN_MISS |
0457 | | | | |
0458 +-----------------+-----------------+-----------------+-----------------+
0459
0460
0461
0462 DX1 : DIFFERENCE FROM INSIDE ONE 0,[1],2 DX2 : DIFFERENCE FROM OUTSIDE 0,[1],2
0463 DX3 : DIFFERENCE FROM INSIDE BOTH 4,5,6
0464
0465 +-----------------------+ +-----------------------+
0466 | B | | B |
0467 +------------------+ | +------------------+ |
0468 | A | | | | A | | |
0469 | | | | | | 4 - 5 - - - - - - - 6
0470 | | | | | | | |
0471 | 0- - -[1]> - - 2 | 0 - <[1] - - - - 2 | |
0472 | | | | | | | |
0473 | | | | | | | |
0474 | +-------|---------------+ | +-------|---------------+
0475 | | | |
0476 | | | |
0477 +------------------+ +------------------+
0478
0479
0480 0: origin 0: origin
0481 1: B Enter 1: A Enter
0482 2: A Exit 2: B Enter
0483 1,2: B Closer => RETURN_FLIP_B [1]> 1,2: A Closer => RETURN_A [1]
0484
0485
0486 4: origin
0487 5: A Exit
0488 6: B Exit
0489 5,6: A Closer => LOOP_A => A MISS
0490 ==> RETURN_MISS
0491
0492 )LITERAL" ;
0493
0494 int main(int argc, char** argv)
0495 {
0496 printf("%s\b", REFERENCE);
0497 LUT lut ;
0498 switch( argc > 1 ? argv[1][0] : 'A' )
0499 {
0500 case 'U': print_LUT(lut, CSG_UNION , UNION ); break ;
0501 case 'I': print_LUT(lut, CSG_INTERSECTION , INTERSECTION ); break ;
0502 case 'D': print_LUT(lut, CSG_DIFFERENCE , DIFFERENCE ); break ;
0503 default:
0504 print_LUT(lut, CSG_UNION , UNION );
0505 print_LUT(lut, CSG_INTERSECTION , INTERSECTION );
0506 print_LUT(lut, CSG_DIFFERENCE , DIFFERENCE );
0507 }
0508 return 0 ;
0509 }
0510
