MySQL 3D «Заливка» Реализация

Question

У меня есть таблица MySQL со следующей структурой:

CREATE TABLE IF NOT EXISTS `np_voxels` (
    `world` VARCHAR(16) NOT NULL, 
    `x` INT NOT NULL, 
    `y` INT NOT NULL, 
    `z` INT NOT NULL, 
    `value` DOUBLE NOT NULL DEFAULT 0, 
    `property_id` INT NULL, 
    PRIMARY KEY (`world`, `x`, `y`, `z`) , 
    INDEX `np_fk_voxels_properties_idx` (`property_id` ASC) , 
    CONSTRAINT `np_fk_voxels_properties` 
    FOREIGN KEY (`property_id`) 
    REFERENCES `np_properties` (`property_id`) 
    ON DELETE NO ACTION 
    ON UPDATE NO ACTION) 
ENGINE = InnoDB; 

Я хочу два запросов на выборку, которые могут найти все подключенные воксели данные исходный воксель, которые соответствуют определенному условию. Один WHERE world = @world AND value > @minvalue AND property_id IS NULL, а другой WHERE world = @world AND property_id = @property_id. Используемый алгоритм заполнения залива должен быть достаточно быстрым, чтобы он не вызывал заметного запаздывания (это будет использоваться на игровом сервере). Также должна быть ограничивающая рамка, расположенная на начальном вокселе, из которого запрос не может исчезнуть. На оси y это будет идти от 0 до @ymax. По умолчанию для этого будет 31. Для оси x и z, это должно выходить @hdistance от начала x или z.

Входной

• @world
• @startx
• @starty
• @startz
• @minvalue или @property_id (Зависит, что программа ищет.)
• @hdistance По умолчанию: 13
• @ymax По умолчанию: 31

Я искал в Google, и не нашел существующую реализацию в MySQL. Я не понимаю, как работают более быстрые и сложные алгоритмы заливки потока, чтобы попытаться написать это самостоятельно.

Answer 1

Быстрая заливка-заливка НЕ ​​должна быть реализована в SQL. Вы можете загрузить все необходимые данные в ваше приложение в соответствующие структуры (возможно, некоторое представление графика или 3d-массив в зависимости от плотности ваших данных) и запустить стек/очередь или любую другую реализацию, которую вы можете записать на языке программирования. Потоп-заполнение по определению является рекурсивным (даже если оно часто реализуется циклами), а SQL не подходит для рекурсии или циклов.

Но есть что-то, что может быть использовано в mysql, даже если это не нормальное решение SQL. Существует специальный механизм для обработки графиков - OQGRAPH. Он доступен в MariaDB и, возможно, может быть установлен в MySQL.

Он поддерживает эффективное хранение комбинаторных графиков, сетка которых является только особым случаем и может вычислять кратчайшие пути и достижимость. На странице примеров он знает dijkstras и breadth_first - последний должен использоваться в качестве реализации заливки наводнения.

В зависимости от ваших потребностей вы должны иметь возможность написать что-то более совершенное, потому что вы можете адаптировать его к своей конкретной ноге. Но если вы хотите экспериментировать и сравнивать большую реализацию, вы можете попробовать.