KD-обход-дерева (трассировка лучей) - я пропускаю случай?
Всегда используйте отдельный столбец, суррогатный ключ если вообще возможный. Это делает соединения, а также вставляет/обновляет/удаляет намного более чистый, потому что Вы только ответственны за отслеживание единственной информации для поддержания записи.
Затем по мере необходимости, складывают Ваши бизнес-ключи как уникальные ограничения или индексы. Это сохранит Вас целостностью данных неповрежденный.
Бизнес-логика / естественные ключи может измениться, но физический ключ таблицы никогда не должен изменяться.
2 ответа
На всякий случай, если кому-то интересно - я совершил ошибку, не рассмотрев особый случай, описанный в этой статье
http://www.cs.utexas.edu/ftp/pub/ techreports / tr88-07.pdf стр. 12
Это происходит, если один многоугольник лежит на плоскости разделения, так что он является частью обеих ячеек, и луч проходит через обе ячейки. если тестируется ближняя ячейка, но фактическое пересечение происходит в пространстве дальней ячейки (это возможно, потому что многоугольник, который пересекается, является частью обеих ячеек), тогда все еще существует вероятность, что в дальней ячейке может быть найдено пересечение, которое на самом деле ближе, чем уже найденный. Следовательно - если найденное t для пересечения больше, чем tSplit, тогда уже должна быть протестирована farCell
I've taken a different approach to the problem, here's what I do:
if(ray.direction(current_node.split_axis)>0) {
near=current_node.left_child
far=current_node.right_child
} else {
near=current_node.right_child
far=current_node.left_child
}
tsplit=(current_node.split_value-ray.origin[current_node.split_axis])/ray.direction[current_node.split_axis]
if(tsplit>current_stack.tmax||tsplit<0) {
only near child
} else if(tsplit<tmin) {
only far child
} else {
both childs
}
You see that I don't use the origin of the ray for choosing which of the left/right child is near/far, and I take in account the case you named C by using the tsplit<0 condition